Check my solution on a card flipping game

Question

I'm trying to solve puzzle. Can someone please check my solution? Thank you!

I have four cards with values $1,2,3,4$ faced down. Each turn, I can either flip a card or do nothing. If I flip a card, I get the face value. If I don't, I get $2.5$. I have four turns. What's the optimal strategy (assuming you're risk neutral) and what is its expected value?

This is my solution. Let $V(a,b,c,d)$ denote the value at each state. The arguments of $V$ can only take zero or one, indicating whether a card is unflipped. For example, $V(1,0,0,0)$ is the value where the card with value $1$ is unflipped and $V(0,0,0,1)$ is the value where the card with value $4$ is unflipped.

I then work backwards. During my last turn, if the card that's unflipped is $1$ or $2$, I won't flip it. If it's $3$ or $4$, I will flip it. Then $V(1,0,0,0) = 9 + 2.5 = 11.5$, $V(0,1,0,0) = 10.5$, and $V(0,0,1,0) = V(0,0,0,1) = 10$.

It follows

$$V(1,1,0,0) = \max\left\{ \frac{1}{2} \left(V(1,0,0,0) + V(0,1,0,0)\right), 12\right\}$$

where the first argument in the max operator is the value of flipping and the second argument the value of not flipping.

I can back out $V(1,1,1,1)$ using this logic, until I realize I haven't proved that it's never optimal to stay input one round and then flip cards the next round.

Can I get a hint on this?

Answer 1

Let $U$ denote the set of cards (e.g., $U=\{1,2,3,4\}$). Let $X$ denote the subset of cards that have been flipped. Let $v(t,X)$ be the value of playing the game with $t$ turns remaining. Let $r$ be the reward for not flipping a card (e.g., $r=2.5$). Trivially, $v(0,X)=0$ for any $X$. Moreover, if $t>0$, $$ v(t,X)=\max\left\{ \frac{1}{\left|U\setminus X\right|}\left(\sum_{x\in U\setminus X}v(t-1,X\cup\{x\})+x\right),v(t-1,X)+r\right\} . $$

Remark. The above is understood w.r.t. the conventions $\sum_{x \in \emptyset} f(x) = 0$ and $0 / 0 = 0$.

This, with some simplifications, is implemented in the code below.

import functools
from typing import Tuple


def value(num_turns: int, no_flip_value: float, rewards: Tuple[float, ...]) -> float:
    @functools.lru_cache(maxsize=None)
    def _value(mask: Tuple[bool, ...], num_turns_left: int) -> float:
        if num_turns_left == 0:
            return 0.0
        num_unflipped = sum(1 for mask_i in mask if not mask_i)
        stop_value = num_turns_left * no_flip_value
        if num_unflipped == 0:
            return stop_value
        mean_flip_value = (
            sum(
                rewards[i]
                + _value(
                    mask=mask[:i] + (True,) + mask[i + 1 :],
                    num_turns_left=num_turns_left - 1,
                )
                for i, mask_i in enumerate(mask)
                if not mask_i
            )
            / num_unflipped
        )
        return max(mean_flip_value, stop_value)

    return _value(mask=(False,) * len(rewards), num_turns_left=num_turns)


answer = value(num_turns=4, no_flip_value=2.5, rewards=(1.0, 2.0, 3.0, 4.0))
print(answer)

Answer 2

The state of the game can after any of the steps be noted as a set of face-values shown of the cards already flipped plus a letter N for each step where no card was flipped. Initially the state is empty. After step one the set of 5 states is {1}, {2}, {3}, {4}, {N}. After 2 steps the states are {1,2}, {1,3},.. {3,4}, {1,N}, {2,N},.. {N,N}, 6 with two numbers, 4 with one number and a N, and one with two N. After 4 steps the states are {1,2,3,4}, {1,2,3,N},... {1,2,N,N}, ... {N,N,N,N}, one with 4 numbers, 4 with 3 numbers and a N, 6 with 2 numbers and 2 N, 4 with 1 number and three N, and one with 4 N.

These states can be organized in a poset (partially ordered set) where the initial state is at level 0, and each state at level i is linked to all states at level i+1 that may follow by either flipping or non-flipping. The value of the states at level 4 is the sum of the integers plus the number of N's times 2.5. The gambler tries to maximize the expectation value (EV) at each step.

If the gambler does not flip, the EV (I) would be the EV of the next state, defined by N added to the state; if the gambler flips, the EV (II) is 1/u times the sum of the expecation values of the next state by adding one of the yet non-flipped cards. [Here u is the number of cards not yet flipped.] Example: if the state is {3} it's recommended to flip because the EV of {1,3} is 10.25, the EV of {2,3} is 10.75 and the EV of {3,4} is 12 (mean of these u=3 EV is 11) and the EV of {3,N} is 10.5, smaller. The winning strategy is to assume that the EV of a state is the maximum of the two EV (I) and (II), which means the gambler decides to flip or not-to-flip branching with probability 1 or probability 1/u into a state of the next higher level.

This type of strategy and mathematics of probabilities is applicable to all kinds of multisets of cards with to-be-flipped face values and all values of (positive or negative) N-values. The list of 48 states (each followed by a "f" to recommend to flip, a "n" to recommend not to flip, a "u" meaning flip or non-flip have the same EV, a "e" meaning end-of-the game, and the EV after the recommended action) is:

. f 10.8125  
1    f 10.166666666666666  
12   f 10.0  
123  f 10.0  
1234 e 10.0  
123N e 8.5  
124  f 10.0  
124N e 9.5  
12N  f 9.0  
12NN e 8.0  
13   f 10.25  
134  n 10.5  
134N e 10.5  
13N  f 9.5  
13NN e 9.0  
14   f 10.25  
14N  u 10.0  
14NN e 10.0  
1N   f 9.5  
1NN  f 9.0  
1NNN e 8.5  
2    f 10.583333333333334  
23   f 10.75  
234  n 11.5  
234N e 11.5  
23N  u 10.0  
23NN e 10.0  
24   n 11.0  
24N  n 11.0  
24NN e 11.0  
2N   f 10.0  
2NN  f 9.666666666666666  
2NNN e 9.5  
3    f 11.0  
34   n 12.0  
34N  n 12.0  
34NN e 12.0  
3N   u 10.5  
3NN  n 10.5  
3NNN e 10.5  
4    n 11.5  
4N   n 11.5  
4NN  n 11.5  
4NNN e 11.5  
N    f 10.375  
NN   f 10.166666666666666  
NNN  u 10.0  
NNNN e 10.0  

So in summary the EV of the best strategy is 10.8125, and it's recommended to start with a flip, and to flip a second card if that first flip does not show the 4.