I'm from Italy and here a very simple card game called Cucù (apparently in English it's called Ranter-Go-Round) is very popular during the Christmas holidays. It's a simple game but I've been struggling with its probabilities, so I've tried simplifying it so that it's easier to analyze. My simplified model is:
- There are two players: player 1 and the dealer.
- Player 1 plays first.
- In the deck there are the numbered cards $\: 1,2,3,4 $ (the 3-card case is easy).
- Each player is dealt one random card, face down. He may see it.
- The value of each card is its number.
- A player wins if his card is higher-valued than the opponent's.
- Player 1 may keep his own card or force the dealer to exchange cards. The dealer can see the card he receives.
- The dealer may keep his own card or exchange it with a random card from the deck.
- When the dealer ends his turn, the players reveal their cards in order to compare them and the game ends.
- The players are both infinitely intelligent (and they know it) and want to win.
It is the last item in the list that's giving me trouble, because it sounds like it should be well-defined but I've encountered some paradoxical problems.
Suppose I wanted to find the optimal strategy for player 1. This is merely a function of the value $c$ of his card that returns either "keep" or "exchange". All we need to know in order to find it is $P(K,c)$ and $P(E,c)$, the probabilities of losing if he (resp.) keeps or exchanges it.
$P(E,c)$ can be calculated quite straightforwardly. It is the probability that
- the dealer had a lower-valued card
- the dealer had a higher-valued card $d$ but, after the exchange, he exchanges $c$ with a card $>d$ from the deck
The behavior of the dealer is totally deterministic in this instance. However, when we turn to $P(K,c)$ we run into trouble, for $P(K,c)$ is the probability that
- the dealer exchanges with the deck and gets a card $\: >c$
- the dealer has a card $>c$ and does not exchange
Now, how are we supposed to calculate the probability that the dealer will exchange or will not? We ought to have the optimal strategy for the dealer, which is a function of his own card and the move which player 1 made. But for this the dealer should know the optimal strategy for player 1, else he wouldn't obtain as much information as possible from player 1's move, and he's infinitely intelligent so he wants to maximize his chances of winning. So the optimal strategy for player 1 depends on the optimal strategy for the dealer and vice versa, making it apparently impossible to calculate either!
It seems like we are stuck with an infinite, unsolvable regression that makes my brain melt. Should we content ourselves with heuristics? Is the optimal strategy even well-defined in this case?
EDIT: My attempt at generalizing for $n$ cards
In order to find the optimal strategy for Player 1, I tried the following approach. I calculated the maximum probability of losing if she keeps $c$ as the best strategy that the dealer could choose when Player 1 keeps $c$. The general strategy of the dealer when Player 1 keeps (since when she exchanges there is only one sensible strategy) assigns to each card $d$ a probability $0\le p_d \le 1$ of keeping it. It can be described with the vector $s=(p_1,p_2,\dots, p_n)$. Now the general form of the probability of losing $P(K,c,s)$ can be calculated (I have described the various cases above), and then get $\: \max\limits_sP(K,c,s)$ from it. Let us call $\alpha=\sum_{i=1}^{c-1} p_i$ and $\beta = \sum_{i=c+1}^{n} p_i$. Then $$P(K,c,s)=\frac{\beta}{n-1} + \frac1{n-1} \left ( \sum_{i=1}^{c-1} (1-p_i)\frac{n-c}{n-2} + \sum_{i=c+1}^{n} (1-p_i)\frac{n-c-1}{n-2} \right )$$ $$\cdots = \frac1{n-1} \left ( \beta \left ( 1+\frac{1+c-n}{n-2}\right ) + \alpha \left (\frac{c-n}{n-2} \right ) + n-c \right )$$ Now $P(K,c,s)$ can be maximized by simply maximizing $\beta$ and minimizing $\alpha$, i.e. $\beta=n-c \:$, $\alpha = 0$. So we have $$\overline P(K,c) := \: \max\limits_sP(K,c,s) = \frac{n-c}{n-1} \left ( 2+\frac{1+c-n}{n-2}\right )$$ The expression for $P(E,c)$ is also quite cumbersome: $$P(E,c)=\frac1{n-1} \left ( c-1 + \frac{(n-c-1)(n-c)}{2(n-2)}\right )$$ Now if $\: \overline P(K,c) < P(E,c)$ we should definitely keep, while if $\overline P(K,c) > P(E,c)$ we should definitely exchange. This inequality is quadratic but its solution agrees well with our intuition; it always yields a range containing $[1,t), t<n$ within which we should exchange $c$ and a range containing $(t,n]$ within which we should keep $c$. Incidentally, for $n=4$ it yields $t=3$, which is exactly your solution. This makes me think that it should be correct, i.e. this is the (pure) strategy Nash equilibrium for Player 1. What do you think? If it is correct, is there an easier way to arrive at the same solution?
EDIT 2
I realize that my lengthy calculation of $P(K,c,s)$ is completely unnecessary, because clearly the best strategy to defeat Player 1 when she keeps $c$ is by keeping a card if it is $>c$ and exchanging it if it is $<c$. The second thing I realized is that it is false that if $P(E,c)< \overline P(K,c)$ then Player 1 should exchange, because the best strategy for defeating her when she keeps $c$ might not work when Player 1 has cards $\not = c$. So this "threshold" I got is just an upper bound for the actual threshold (if it exists).
EDIT 3: Only now have I understood that a "threshold" must exist if there exists a pure strategy Nash equilibrium, because of the result that you have proven. This of course drastically reduces the possible strategies which must be compared.
EDIT 4, and TL;DR: Even when considering only strategies with a "threshold", finding the optimal strategy takes a lot of patience, unless I'm missing something. My approach is to calculate, for each strategy $x$ of Player 1, the probabilities $P(x,y)$ of her losing against every strategy $y$ of the dealer. The Nash equilibrium should then be all the strategies $\bar x$ and $\bar y$ such that $$P(\bar x, \bar y) = \min\limits_x \left( \max\limits_y P(x,y)\right )$$ Of course $x$ and $y$ vary across $n$ distinct strategies each, but the actual calculation is still quite difficult. Are there any shortcuts?
EDIT 5: I acknowledge that my definition of Nash equilibrium isn't correct (it is just a necessary condition) and that it makes calculations inconvenient. An easier way is to look for the threshold "near" $n/2$. Indeed this is a lot easier, and it is the natural generalization of @joriki's solution. It also yields similar results, i.e. there is indeed a strategy for Player 1 which does not depend on the dealer's strategy, i.e. it is the best response to all the strategies of the dealer.
Best Answer
You may want to familiarize yourself with the concepts of Nash equilibrium and pure and mixed strategies before reading this answer.
Player $1$ could potentially benefit from sometimes bluffing in a mixed strategy, but it seems unlikely, so let's first try to find a Nash equilibrium with pure strategies.
A pure strategy in this case amounts to what you describe: A function that says for each number Player $1$ might have whether to keep or exchange it. We can safely assume that this takes the form of keeping at or above a certain threshold and exchanging below.
If Player $1$ always keeps, then the dealer's best response is to keep the $3$ or $4$ and exchange the $1$ or $2$. In this case, the dealer's winning probability is $1$ if she was dealt the $4$, $\frac23$ if she was dealt the $3$, and $\frac12$ if she was dealt the $1$ or $2$, for a total of $\frac14\left(1+\frac23+\frac12+\frac12\right)=\frac23$. Here are the dealer's winning probabilities depending on the initial deal (Player $1$ is vertical, the dealer is horizontal):
\begin{array}{c|cc} &1&2&3&4\\\hline 1&&1&1&1\\ 2&1&&1&1\\ 3&\frac12&\frac12&&1\\ 4&0&0&0 \end{array}
If Player $1$ only exchanges the $1$, then the dealer's best response is again to keep $3$ or $4$ and exchange $1$ or $2$. (If the dealer has the $3$, Player $1$ has either the $2$ or the $4$; the $4$ can't be beaten and the $2$ is already beaten, so the dealer should keep.) In this case, if Player $1$ is dealt the $1$, the dealer's winning probability is $\frac12$; otherwise, if the dealer is dealt the $1$ it is again $\frac12$; if she is dealt the $2$ it is $\frac14$; if she is dealt the $3$ it is $\frac12$ and if she is dealt the $4$ it is $1$, for a total of $\frac14\cdot\frac12+\frac14\cdot\frac12+\frac16\left(\frac14+\frac12+1\right)=\frac{13}{24}$. Here again are the dealer's winning probabilities depending on the initial deal:
\begin{array}{c|cc} &1&2&3&4\\\hline 1&&1&\frac12&0\\ 2&1&&1&1\\ 3&\frac12&\frac12&&1\\ 4&0&0&0 \end{array}
If Player $1$ exchanges the $1$ and $2$, the dealer's best response is again to keep $3$ or $4$ and exchange $1$ or $2$. In this case the dealer's winning probabilities depending on the initial deal are as follows:
\begin{array}{c|cc} &1&2&3&4\\\hline 1&&1&\frac12&0\\ 2&1&&\frac12&0\\ 3&\frac12&\frac12&&1\\ 4&0&0&0 \end{array}
Now the dealer's overall winning probability is only $\frac5{12}$.
If Player $1$ exchanges the $1$, $2$ and $3$, the dealer's best response is again to keep $3$ or $4$ and exchange $1$ or $2$. In this case the dealer's winning probabilities depending on the initial deal are as follows:
\begin{array}{c|cc} &1&2&3&4\\\hline 1&&1&\frac12&0\\ 2&1&&\frac12&0\\ 3&1&1&&0\\ 4&0&0&0 \end{array}
The dealer's overall winning probability is again $\frac5{12}$.
Player $1$ can certainly not gain from exchanging the $4$, so that exhausts the possibilities.
Since the dealer's best response is independent of Player $1$'s strategy, Player $1$ can't gain by using a mixed strategy. Player $1$ should exchange the $1$ and $2$ and keep the $4$, and can decide with arbitrary probability whether to exchange the $3$; the dealer's best response is to exchange the $1$ and $2$ and to keep the $3$ and $4$. Player $1$ wins with probability $\frac7{12}$ and the dealer wins with probability $\frac5{12}$.
Incidentally, the strategies that one might intuitively choose without any analysis, namely that either player exchanges the two lower cards and keeps the two higher cards, form an equilibrium solution.
P.S.: Here's a more direct proof that the dealer should exchange $1$ and $2$ and keep $3$ and $4$: If she has the $1$, there's nothing to lose. If she has the $2$, there's also nothing to lose, since the only way she could be winning is against the $1$, and she'll still win against the $1$ after exchanging. Likewise, if she has the $4$, there's nothing to gain, and if she has the $3$, there's also nothing to gain, since the only way she could be losing is against the $4$, and she'll still lose against the $4$ after exchanging.
P.P.S.: To show that Player $1$ should keep $x+1$ if she keeps $x$, it suffices to show that keeping $x+1$ is at least as good as keeping $x$ and exchanging $x$ is at least as good as exchanging $x+1$.
The second part is straightforward: If we exchange, we get the same card no matter which card we had, and surely giving the dealer $x$ is at least as good as giving them $x+1$.
For the first part, we can compare deals pairwise: If the dealer has anything other than $x$ or $x+1$, keeping $x+1$ is at least as good as keeping $x$. If the dealer has $x$ or $x+1$, then keeping $x+1$ (while the dealer has $x$) is at least as good as if the dealer draws (since Player $1$ wins if the dealer doesn't draw), and keeping $x$ (while the dealer has $x+1$) is at most as good as if the dealer draws (since Player $1$ loses if the dealer doesn't draw), with the same chances for the draw. Since keeping $x+1$ is at least as good as keeping $x$ for each pair of deals, it's also at least as good on average.
This argument uses neither the number of cards nor the fact that for $4$ cards the dealer's strategy is independent of Player $1$'s strategy, so it holds for any number of cards (as long as we're comparing pure strategies).