1st International ICST Workshop on Tools for solving Structured Markov Chains

Research Article

Constrained Markov games with transition probabilities controlled by a single player

Download166 downloads
  • @INPROCEEDINGS{10.4108/smctools.2007.1977,
        author={Eitan Altman and Saswati Sarkar and Eilon Solan},
        title={Constrained Markov games with transition probabilities controlled by a single player},
        proceedings={1st International ICST Workshop on Tools for solving Structured Markov Chains},
        proceedings_a={SMCTOOLS},
        year={2010},
        month={5},
        keywords={},
        doi={10.4108/smctools.2007.1977}
    }
    
  • Eitan Altman
    Saswati Sarkar
    Eilon Solan
    Year: 2010
    Constrained Markov games with transition probabilities controlled by a single player
    SMCTOOLS
    ICST
    DOI: 10.4108/smctools.2007.1977
Eitan Altman1,*, Saswati Sarkar2,*, Eilon Solan3,*
  • 1: INRIA BP93 2004 route des Lucioles 06902 Sophia Antipolis FRANCE
  • 2: Dept. of Electrical and Systems Eng. University of Pennsylvania Philadelphia 19104, USA
  • 3: School of Mathematical Sciences Tel Aviv University ISRAEL
*Contact email: altman@sophia.inria.fr, swati@seas.upenn.edu, eilons@post.tau.ac.il

Abstract

We consider a two-players zero-sum Markov game with side constraints where only one player controls the transition probabilities. We reduce the problem to that of solving an equivalent linear program. Our approach is different than the one previously used to derive such linear programs [4, 5, 9]. We introduce a new type of constraints: the "subsciption constraints" along with standard constraints which we call "realization constraints". We extend the results obtained in [4, 5, 9] to the case where both players have constraints.