7
$\begingroup$

A card game is played by splitting a face-down shuffled deck evenly between two players. The deck consists of cards numbered 1-52. Each player reveals the top card of their deck, and the player whose card has higher rank scores 1 point. Both cards are then discarded. The process is repeated until both decks have been depleted. The winner of the game is the one with the largest number of points.

Suppose you can cheat at this game: first, you know the contents, but not the order, of both decks. Second, each round before your opponent reveals a card, you can choose which card in your deck you will reveal. (That is, you can choose which card you will reveal next based on all of the information you have up to the point where the opponent will reveal a new card.)

My friend suggested that even if you can cheat in this way, there is no strategy you can play which will give you a higher score on average than playing at random. This doesn't seem true to me, but I've had trouble proving that cheating helps in simple cases, or proving (e.g. inductively) that it doesn't matter. Any help is appreciated.


Edit: If it helps, I've previously considered a simpler version of this game, in which you know the fixed order of your opponents' cards, which are played in order. If you are allowed to cheat in this deterministic version, you can optimize your score according to the following strategy. First, it suffices to establish a mapping between their cards and your cards --- the card you will play when they play their card. To create this mapping, list your cards in ascending order of rank and list their cards in the same way. If their highest ranked card beats your highest ranked card, pair it with your lowest-ranked card. Otherwise, pair it with the lowest-ranked card you have that still beats it. Remove both cards, and repeat this process.

Edit 2: Conjecture. Even if you cheat, there is no strategy which performs better than chance. In particular, regardless of which strategy you employ, your expected score is simply the probability that a random card from your deck beats a random card from their deck, times the total number of cards in each deck. If you create an $n\times n$ matrix whose $(i,j)$ entry is 1 if your $i$th card beats their $j$th card, your expected score on any strategy is 1/$n$ times the sum of the entries of the matrix. I think I have an inductive proof of this, but am still figuring out how to write it out formally.

$\endgroup$
  • $\begingroup$ Does this mean that you know what cards your opponent have? $\endgroup$ – Abhinav Feb 25 at 4:57
  • $\begingroup$ @Abhinav Yes, you know the contents of your opponent's deck and yours, but not the order. $\endgroup$ – user326210 Feb 25 at 5:08
  • $\begingroup$ There can be many combinations of your and your opponent's deck. I don't think there is a way using which you can win all the cases. For example if you have the numbers between $1$ to $26$ and your opponent has the rest cards. You can never win. $\endgroup$ – Abhinav Feb 25 at 5:33
  • $\begingroup$ @Abhinav Yes, that's right -- you can't always win. I am wondering if there's a strategy, which is a function of the cards you have and the cards that your opponent has, which will allow you to get the highest possible expected score (even if you can't win) given that your opponent plays cards uniformly at random. I already have a strategy for maximizing your expected score if your opponents cards are in a known fixed order. $\endgroup$ – user326210 Feb 25 at 7:21
5
$\begingroup$

Theorem: Even if you cheat, you cannot do better than chance. In particular, your expected number of points is equal to your probability of winning a single round between a random card of yours and a random card of your opponent's, times your total number of cards.

Proof: The proof is by induction. Suppose you and your opponent each have a deck of $n=2$ cards in a fixed but arbitrary order. Consider the payout matrix $\mathbf{P} = \begin{bmatrix}a&b\\c&d\end{bmatrix}$ which has a $1$ in entry $(i,j)$ if your $i$th card beats their $j$th card, and a 0 otherwise. If you choose row 1, your opponent will randomly choose a column $j$. Your payout will either be $a+d$ (if they choose column 1), or $b+c$ (if they choose column 2). Your expected payout on choosing row 1 is $(a+b+c+d)/2$. A similar argument shows the same expected payout on choosing row 2. This establishes the result that your choices do not influence the expected score when $n=2$.

In the inductive case, suppose you have an $(n+1)\times (n+1)$ payout matrix $\mathbf{P}$. Removing cards corresponds to removing a row/column from the matrix — let $\mathbf{P}^{i,\times}$ denote $\mathbf{P}$ with row $i$ deleted; $\mathbf{P}^{\times,j}$ with column $j$ deleted, and $\mathbf{P}^{i,j}$ with both deleted. Finally, let $|\mathbf{P}|$ denote the sum of all the entries of $\mathbf{P}$.

Now consider your strategy of choosing row $i$. Your opponent chooses a column $j$. For a given column $j$, your payout will be $P_{i,j}$, plus the expected payout resulting from continuing the game; by hypothesis, it is $\frac{1}{n}|\mathbf{P}^{i,j}|$. Hence when choosing row $i$, your expected payout over all opponent responses $j$ is:

$$\frac{1}{n+1} \sum_{j=1}^{n+1}\left[ P_{i,j} + \frac{1}{n}|\mathbf{P}^{i,j}|\right]$$

Note that the term $|\mathbf{P}^{i,j}|$ occurs once for each $j$ from 1 to $n+1$. Hence we can assemble the deleted columns into a single negative term $-|\mathbf{P}^{i,\times}|$.

$$\frac{1}{n+1} \sum_{j=1}^{n+1}\left[ P_{i,j} + \frac{1}{n}|\mathbf{P}^{i,j}|\right] = \frac{1}{n+1} \left[ \sum_{j=1}^{n+1} P_{i,j} + \frac{1}{n}\sum_{j=1}^{n+1}|\mathbf{P}^{i,j}|\right] = \frac{1}{n+1} \left[ \sum_{j=1}^{n+1} P_{i,j} + \frac{1}{n}\left(-|\mathbf{P}^{i,\times}| +\sum_{j=1}^{n+1}|\mathbf{P}^{i,\times}|\right)\right] = \frac{1}{n+1}\left[|\mathbf{P}^{i,\times}|+\sum_{j=1}^{n+1} P_{i,j}\right] = \frac{1}{n+1}|\mathbf{P}|$$

This establishes the result for the inductive case.

$\endgroup$

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.