Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

edit: No responses to this post after a week, so I'm cross-posting it to cstheory.stackexchange here.

I'm looking for a known theorem stating that, for appropriate kinds of two-player zero-sum games where player 1 has finitely many pure strategies and player 2 has uncountably many, every mixed strategy for player 2 has an "equivalent" behavior strategy.

This is analogous to Kuhn's theorem for finite games. I am sure this holds for the game I am studying, but instead of proving it from scratch I would like to cite an existing theorem.

Here is a 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.

I can make an educated guess at the right ways to formally define what a mixed strategy for Player 2 is, and I'm sure I can prove that each mixed strategy has an equivalent behavior strategy. Although I'm sure the latter fact must be a special case of known results, I haven't been able to find a good, accessible reference to cite. Can anyone suggest a good reference?

share|improve this question

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.