This is a crosspost of this post on math.stackexchange, which didn't get any responses.

For two-player games given in extensive ("game tree") form, there are several natural ways to define randomized strategies for the players. A mixed strategy is a probability distribution over pure strategies. A behavior strategy specifies, for each node in the game tree at which the player must play, a probability distribution on the possible moves.

Kuhn's theorem gives conditions under which these two notions are "equivalent". Equivalence here means, for example, that for any mixed strategy there is a behavior strategy that (for any fixed play of the opponent) gives the same distribution on outcomes.

I'm looking for theorems that extend Kuhn's theorem to games with infinite game trees. In particular, when one player has finitely many pure strategies, but the other player has uncountably many.

For the game I have in mind, I can make an educated guess at reasonable ways to formally define what a mixed strategy is for the player with uncountably many pure strategies, and I'm sure I can prove the results I want. I'm sure this must be a special case of known results, but I haven't been able to find a good, accessible reference to cite. Can anyone suggest a good reference? Thanks.

p.s. In case you're curious, here is the game I am studying:

  1. An instance of the game is specified by a positive integer $n$, a distribution $P$ on $n$ arbitrary items, and a cost function $c$, where $c(i)\ge 0$ is the cost of slot $i\in[n]$. Both players know $P$ and $c$.

  2. Player 1 plays first by choosing any permutation $P'$ of the distribution $P$. We then generate an infinite random sequence $x_1,x_2,\ldots$ of items by repeatedly and independently sampling from $P'$. The permutation $P'$ is not revealed to Player 2.

  3. At each time $t=1,2,\ldots$, the item $x_t$ is revealed to Player 2. If the item has not been seen before time $t$, Player 2 (without knowing $P'$ or future requests) must assign some slot $j$ to the item, where slot $j$ has not yet been assigned to any item.

  4. Once Player 2 has seen all $n$ items, he has assigned a unique slot $j(i)$ to each item $i$, and the game ends. Player 2 pays Player 1 the payout $\sum_{i=1}^n P'_i c({j(i)})$.

Each pure strategy of Player 1 is one of the $n!$ permutations of $P$. Each pure strategy of Player 2 is a function specifying, given any sequence $x_1,x_2,\ldots,x_t$ of items, where $x_t$ is the first occurrence of that item, which slot $j$ to assign to item $x_t$. (Note that a-priori Player 2 has uncountably many such pure strategies.) A behavior strategy for Player 2 is a function mapping each such sequence to a distribution on the unassigned slots.

It is a technical exercise to show that the (pure) greedy strategy for Player 2 (assign the slots in order of increasing cost) minimizes the maximum expected payoff. Also, playing uniformly at random is optimal for Player 1.

  • 1
    $\begingroup$ Probably you came across this already, but in case not: Robert Aumann, "Mixed and Behavior Strategies in Infinite Extensive Games," in Advances in Game Theory, Annals of Mathematics Study 52, edited by M. Dresher, L. S. Shapley, and A. W. Tucker, Princeton University Press, 1964, pp. 627-650. $\endgroup$ Dec 28, 2012 at 3:33
  • $\begingroup$ @RahulSavani, thanks, here is (I think) a link to Aumann's article: princeton.edu/~erp/ERParchives/archivepdfs/M32.pdf . I will take a closer look. $\endgroup$
    – Neal Young
    Dec 28, 2012 at 4:00
  • 2
    $\begingroup$ There's also a LaTeXed version on Aumann's webpage: ma.huji.ac.il/~raumann/pdf/Mixed%20and%20Behavior.pdf $\endgroup$ Dec 28, 2012 at 4:12
  • $\begingroup$ @RahulSavani, Aumann's paper is in the right general direction, but it's about the case when the players have uncountably many moves at each play. That case is much more complicated than what I'm looking for. FWIW, the question I'm asking should've been addressed in Borodin and El-Yaniv's "Online computation and competitive analysis", in Chapter 6, about foundations of randomized strategies (behavioral, mixed, and general). But, even though infinite games are common in online algorithms, B + E only address finite games (remarking informally that the results generalize to infinite games). $\endgroup$
    – Neal Young
    Dec 29, 2012 at 6:26


Your Answer

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

Browse other questions tagged or ask your own question.