Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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. –  Rahul Savani Dec 28 '12 at 3:33
    
@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. –  Neal Young Dec 28 '12 at 4:00
2  
There's also a LaTeXed version on Aumann's webpage: ma.huji.ac.il/~raumann/pdf/Mixed%20and%20Behavior.pdf –  Rahul Savani Dec 28 '12 at 4:12
    
@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). –  Neal Young Dec 29 '12 at 6:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.