4
$\begingroup$

There's a little game in which two players take part. The game consists of ten rounds. In each round, the two players simultaneously choose a number between $1$ and $10$ inclusive. The player with the larger number receives two points. If their numbers are equal, then each player gets one point. Once a player has used a number, they cannot pick it again.

In reality, the game is played with poker cards so each player receives 1..10 from one color. Players place the cards face down and then turn them over once both players have picked a card and then the continue with the remaining cards.

There's a modified version where a third person looks at the played cards so players do not learn what cards the opponent has played the third person will only announce who had the higher card or draw/tie.

The game ends after all cards have been played. The winner is the one with the highest score.

Is there a strategy that beats a player randomly selecting cards and does this change in the modified version?

$\endgroup$
1
+50
$\begingroup$

There is no strategy that outperforms a player randomly selecting cards in either version of the game. Here's a way to see it.

Suppose your opponent declares a random strategy by shuffling her cards and laying them out, face down, in a row. From here on out, all choices are yours, including the choice of reshuffling your opponents cards, if you like. The first thing you realize, though, is that there is really no point in ever doing that, since all it would accomplish is to re-randomize an already random arrangement.

For the heck of it (and/or to free your hands so you can eat a sandwich), you lay your own cards out, face up, in a row matching your opponent's cards. You now implement your strategy by deciding which of your cards you want to play first. You play it against the face-down card across from it. After seeing who won the round (by turning your opponent's card over, in the main version of the game, or being told by a neutral third party who examines the face-down card, in the modified version), you continue to implement your strategy by deciding what to play next. You can, if you like, re-randomize your opponent's remaining cards, but again there is no gain in re-randomizing an already random arrangement, so you may as well once again play it against the card it's across from. This continues to the end of the game, at which point you realize that the outcome was essentially determined as soon as the cards were all laid on the table. That is, since there is no point in re-randomizing an already random arrangement, you might as well have simply played the cards as they lay across from each other at the outset, and done so in any order.

$\endgroup$
  • $\begingroup$ To complete your argument, you should point out that any sequence of moves you might make beats a random sequence exactly as often as it loses to a random sequence - so there is no 'magic sequence' of moves you could make that beats more than half of the random sequences that the opponent might make (discounting draws). Otherwise this argument can be adapted to show that there is no game in which any strategy beats the random selection of moves, which is clearly false. $\endgroup$ – John Gowers Aug 26 '16 at 12:36
  • $\begingroup$ @Donkey_2009, what I've actually shown here is that, in a game of this type (where players match cards one after another, regardless of the rule for determining who wins the round), if either player commits to a random strategy, then in effect both players are playing at random, so neither player can expect to do better than they would with a random strategy. I agree, there are games where you can take advantage of an opponent who plays at random, but those games are not of this type. $\endgroup$ – Barry Cipra Aug 26 '16 at 14:15
  • $\begingroup$ If I decide to start every game by playing a 10, then I am behaving very differently from a random player. $\endgroup$ – John Gowers Aug 26 '16 at 16:55
  • $\begingroup$ @Donkey_2009, true. And if I know that you always do that, then I can possibly take advantage of it. But if I commit to playing a (uniformly) random strategy, then it does not matter to either one of us what strategy you play, the expected (i.e., average) result will be the same. That's what I mean by "in effect." $\endgroup$ – Barry Cipra Aug 26 '16 at 20:43
  • 1
    $\begingroup$ @Donkey_2009: Be careful with quantifiers here. The question asks if the random player does no worse against any strategy, not whether there is a strategy that does no worse than all strategies against any strategy. The former is true, as Barry has shown, while the latter is very false, because simply knowing one of the opponent's move in advance is enough to give an advantage, and knowing all the opponent's moves in advance can allow you to win every round except one. $\endgroup$ – user21820 Aug 28 '16 at 2:21
0
$\begingroup$

Is there a strategy that beats a player randomly selecting cards?

No, it seems there isn't. We can see this by looking at all the possible game continuations and in each configuration deciding whether or not we can steer the game in our favor by making the correct choices.

To illustrate this, let's look at a variant of the game where each player has a low number of $N$ cards from $1$ to $N$, say $N=2$ or $N=3$ (there are $(N!)^2$ possible paths through a game with $N$ cards, so anything more than $N=3$ becomes really tedious).

For $N=2$, we can have the following paths:

$$\begin{matrix} 1 & 2 \\ 1 & 2 \end{matrix}\rightarrow \cases{ \underline{\begin{matrix} X & 2 \\ X & 2 \end{matrix} \rightarrow 2-2} \\ \underline{\begin{matrix} X & 2 \\ 1 & X \end{matrix} \rightarrow 2-2} \\ \underline{\begin{matrix} 1 & X \\ X & 2 \end{matrix} \rightarrow 2-2}\\ \begin{matrix} 1 & X \\ 1 & X \end{matrix} \rightarrow 2-2 }$$ Here, each row represent the cards of a player. The $X$'s represent what has been chosen. The final score is shown to the very right.

So we see that all game ends in a draw. Well, this was a boring case, one might object, since decision only comes into play after the first card has been removed (where neither player has any information to utilize), and the outcome of the game is fixed by then. Okay, let's do the same analysis in the case of $N=3$ then. I won't write out all the paths, but only show the possible outcomes of each of the $3^2$ possible positions after the first card has been removed:

$$\begin{matrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{matrix}\rightarrow \cases{3-3 \\ 3-3 \;\vee\;2-4\;\vee\;2-4\;\vee\;3-3 \\ 3-3\;\vee\;4-2\;\vee\;4-2\;\vee\;3-3 \\ 3-3 \\ 2-4\;\vee\;3-3\;\vee\;3-3\;\vee\;2-4 \\ 4-2\;\vee\;3-3\;\vee\;3-3\;\vee\;4-2 \\ 3-3 } $$

We see that if all outcomes are equally likely, each player will be expected to score the same on average.

In the case that there are four possible outcomes after the first card has been removed, can one not influence the game continuation in one's favor? No, since if you choose any card, it is equally likely you land in either one of the two different outcomes.

By induction (and just by noticing that we didn't gain any advantage even though we had more information about the state of the game), this can also be shown to be valid for any $N$.

Does this change in the modified version?

No, since it doesn't matter what we do in the first place.

$\endgroup$
  • $\begingroup$ codepad.org/YogtdYAU If I pick 1 as my first card and the opponent picks 4 randomly then by using the pick order (1,3,2,4) I'm guaranteed to not loose and even win in a few cases. $\endgroup$ – mroman Aug 24 '16 at 20:18
  • $\begingroup$ Right, that doesn't really matter. In case of N=4 the game is determined by the first pick. If your opponent started with 2 and you with 1 you'll always loose. $\endgroup$ – mroman Aug 24 '16 at 20:40
  • $\begingroup$ @mroman, yes, there's always a corresponding scenario that favors your opponent (and since the first round is random, there is no better strategy), although it is not a guaranteed loss. As a counter-example to your first example (where you chose 1,3,2,4), your opponent could (by chance) choose (2,4,3,1) and win. $\endgroup$ – Bobson Dugnutt Aug 25 '16 at 11:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.