4
$\begingroup$

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.

$\endgroup$
  • $\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 Shor Sep 17 '13 at 0:51
  • $\begingroup$ I think there are several communities inside computer science working on related topics. $\endgroup$ – Markus Sep 17 '13 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 D Sep 17 '13 at 20:51
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.