Constrained Markov games with transition probabilities controlled by a single player

Eitan Altman; Saswati Sarkar; Eilon Solan

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

Research Article

Constrained Markov games with transition probabilities controlled by a single player

Download516 downloads

Cite: BibTeX Plain Text

@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 Altman¹^,*, Saswati Sarkar²^,*, Eilon Solan³^,*

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.

Published: 2010-05-16
Modified: 2011-09-18

: http://dx.doi.org/10.4108/smctools.2007.1977