<p>This is a crosspost of <a href="https://math.stackexchange.com/questions/259530/mixed-vs-behavior-strategies-for-zero-sum-game-with-infinite-extensive-form">this post</a> on math.stackexchange, which didn't get any responses.</p>

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

<p><a href="http://en.wikipedia.org/wiki/Strategy_(game_theory)#Behavior_strategy" rel="nofollow noreferrer">Kuhn's theorem</a> 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.</p>

<p>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.  </p>

<p>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>

<hr>

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

<ol>
<li><p>An instance of the game is specified by a positive integer $n$, a distribution $P$ on $n$ arbitrary <em>items</em>, and a cost function $c$, where $c(i)\ge 0$ is the cost of <em>slot</em> $i\in[n]$.  Both players know $P$ and $c$.</p></li>
<li><p>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.</p></li>
<li><p>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.</p></li>
<li><p>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)})$.</p></li>
</ol>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2012-12-28T03:33:10.053Z
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
CC BY-SA 3.0
2012-12-28T04:00:29.513Z
@RahulSavani, thanks, here is (I think) a link to Aumann's article: http://www.princeton.edu/~erp/ERParchives/archivepdfs/M32.pdf . I will take a closer look.
Neal Young
CC BY-SA 3.0
2012-12-28T04:12:13.520Z
There's also a LaTeXed version on Aumann's webpage: http://www.ma.huji.ac.il/~raumann/pdf/Mixed%20and%20Behavior.pdf
Rahul Savani
CC BY-SA 3.0
2012-12-29T06:26:58.853Z
@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
<reference-request><gt.game-theory>
mixed vs behavior strategies for zero-sum game with infinite extensive form
Neal Young
# mixed vs behavior strategies for zero-sum game with infinite extensive form

(Asked by: username_0 on 2012-12-23)

This is a crosspost of [this post](https://math.stackexchange.com/questions/259530/mixed-vs-behavior-strategies-for-zero-sum-game-with-infinite-extensive-form) 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](http://en.wikipedia.org/wiki/Strategy_(game_theory)#Behavior_strategy) 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.

**Tags:** reference-request, gt.game-theory
> **Comments:**
> **username_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.  
> **username_0**: @RahulSavani, thanks, here is (I think) a link to Aumann's article: http://www.princeton.edu/~erp/ERParchives/archivepdfs/M32.pdf . I will take a closer look.  
> **username_1**: There's also a LaTeXed version on Aumann's webpage: http://www.ma.huji.ac.il/~raumann/pdf/Mixed%20and%20Behavior.pdf  
> **username_0**: @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).  

---

## 0 answers

