I am looking for a study that has examined whether and under which conditions (if any), an infinite and of possibly infinite horizon two person zero sum extensive form game with perfect information and finite discrete action space, has a value. I would appreciate very much any tips.
$\begingroup$
$\endgroup$
3
-
$\begingroup$ This question doesn't seem to have strong connections to computer science. Why are you asking this question here and not in math.SE or math overflow? $\endgroup$– Peter ShorCommented Sep 17, 2013 at 0:51
-
$\begingroup$ I think there are several communities inside computer science working on related topics. $\endgroup$– MarkusCommented Sep 17, 2013 at 7:20
-
$\begingroup$ @PeterShor, I think that's not true. This topic has been heavily studied by computer scientists in the last decade. The work of Marcin Jurdzinski, Krishnendu Chatterjee, Luca de Alfaro, is in this space. $\endgroup$– Vijay DCommented Sep 17, 2013 at 20:51
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
By the Ky Fan minimax theorem, if you can identify the strategy spaces of the two players with convex compact subsets of a locally convex topological vector space, and the payoff function $M(x, y)$ is convex and continuous in $y$ for any $x$, and also concave and continuous in $x$ for any $y$, then the minimax theorem holds.
answered Oct 17, 2013 at 14:20
$\begingroup$
$\endgroup$
I know of several variants of zero sum games with finite arenas and an with infinite time horizon, e.g. parity games, stochastic games. Infinite state variants of these have also been considered in several places, though I do not know of a good survey.
Examples of such games can be found in Krishnendu Chatterjee's works or in Nathalie Bertrand's works. A more classical work can be found here http://link.springer.com/chapter/10.1007%2F3-540-44685-0_36 This list is certainly not complete, but it might give you a starting point.
$\begingroup$
$\endgroup$
You may have a look at the following book
Automata, Logics, and Infinite Games, A Guide to Current Research, E. Grädel, W. Thomas, T. Wilke (Eds.), LNCS 2500 (2002)
