A zero-sum game is chosen at random, find the optimal strategy for player 1

237 Views Asked by At

A zero-sum game is chosen at random (0.5,0.5), player 1 knows which game was chosen and player 2 doesn't. The game is played infinitely often (no discount factor). Players only know the actions taken, not the payoffs.

$G_1=\bigl(\begin{smallmatrix} 0 & 4 &-2 \\ 0&4 &2 \end{smallmatrix}\bigr) $$ ,G_2=\bigl(\begin{smallmatrix} 4& 0 &2 \\ 4&0 &-2 \end{smallmatrix}\bigr) $

How would you play as player 1?

So if $G_1$ was chosen and I play {Bottom} too often, player 2 will realise at some point which matrix was chosen and then just play {Left} and we would get 0-0 from that point forward. The same claim is valid if $G_2$ was chosen just by replacing {Top} for {Bottom} and {Middle} for {Left}.

Is there a "best" strategy I can take to keep player 2 guessing which game was chosen and maximize my gain?

1

There are 1 best solutions below

0
On BEST ANSWER

Yes, an optimal strategy exists. We can compute exactly what player $1$'s payoffs under this optimal strategy (which I'll call the value of this game) will be.

Unfortunately, there are no general results showing how to actually construct those strategies, but once you've computed what the value of this game is, and you can find a strategy that attains this value, then clearly that strategy is optimal (but not necessarily uniquely so).

This result is due to Aumann and Maschler. The succeeding paragraphs summarise this result.

Let $p$ be the probability that $G_1$ is played.

Consider the game played only once, where $G_1$ is played with probability $p$, and only player $1$ is informed of which game is played. It is straightforward (albeit admittedly potentially tedious) to compute the value of this one-shot game. Call the value of this one-shot game $u(p)$.

Aumann and Maschler showed that the value of the infinitely repeated game you describe is given by

$$ cav[u(p)] $$

where $cav$ denotes the concavification operator. That is, $cav[f(x)]$ is the smallest concave function greater than or equal to $f$ (point-wise).

For more details on this result, I really do recommend the book linked above. Otherwise, Johannes Hörner also has a set of notes on repeated games with incomplete information, which covers this result.