7
$\begingroup$

The game “Higher or Lower” is a simple one in which playing cards are drawn randomly from a deck, and the player has to guess whether each subsequent card will be higher or lower in value than the previous.

What if "Higher or Lower" was played non-randomly, as a two-player game?

Let’s simplify the situation a little by removing the playing cards.

Player A must pick numbers from the range 1-50 without replacement. After the first number (n1) is announced by A, they pick the next (n2) in secret, and Player B must guess whether n2 is higher or lower than n1. B gains a point if they guess correctly, A gains a point if the guess is incorrect. Next, A secretly picks another number (n3) from those remaining, and B must guess whether it is higher or lower than n2. This process is repeated until all 50 numbers have been exhausted, with B guessing whether n(i+1) is higher or lower than n(i) each time.

The game is non-trivial because of one crucial feature: A's choices determine not only how easily B can guess the outcome, but also their range of options for the next pick. For example, if A's starting point is 2, then they might seek to thwart B by picking 1 as the next move with higher probability than all other numbers. However, if A does indeed pick 1, the next move is a free point to B as "higher" is the only option.

Is there a single optimum strategy for both players (and if so, what is it?), or must both players respond to the other’s strategies (and hence also, try to determine the opponent’s strategy)?

Note 1. Each player is competing against their own independent targets – I’m fairly sure that there is no strategy for A that will give a higher expected score than B’s. I’m asking about how A optimises their score in comparison with other hypothetical As, and the same for B.

Note 2. You can assume that both players have access to (pseudo-)random number generators, and as such are not vulnerable to being exploited via the human brain's notoriously bad performance in picking "randomly". You can also assume that both players have excellent memories, and have perfect knowledge of which numbers have already been picked.

Note 3. While I have a few hunches, I do not know the solution to this problem. If it has already been studied I would be interested to know.

$\endgroup$
  • $\begingroup$ good memory would probably help more than most strategies $\endgroup$ – Aequitas Nov 3 '17 at 12:52
  • $\begingroup$ @Aequitas Very true in practice! I'm thinking of the ideal case where memory is not a limitation. Added a note to clarify that. $\endgroup$ – user2390246 Nov 3 '17 at 13:21
  • $\begingroup$ Has a correct answer been given? If so, please don't forget to $\color{green}{\checkmark \small\text{Accept}}$ it. If not, some responses to the answerers to help steer them in the right direction would be helpful. $\endgroup$ – Rubio Nov 27 '17 at 2:22
4
$\begingroup$

I’ve got a recursive formula. Basically if C(i,j) denotes the expected score difference for B-A if there are i lower cards and j higher cards remaining and if 0 < i =< j then:

$C(i,j) = (C(i-1,j) + C(\lfloor(i+j-1)/2\rfloor, \lceil(i+j-1)/2\rceil)) / 2$
$C(0,j) = C(\lfloor(j-1)/2\rfloor, \lceil(j-1)/2\rceil) + 1$

Key points proved inductively:

- Whether A is going higher or lower, he tries to keep i and j as equal as possible.
- If he has the choice, A will always flip a coin to decide whether to go up or down. - All other strategies for A are (non-strictly) dominated.
- B also has a simple mixed strategy, based on the value of A's two dominant strategies.

I attach an image of a spreadsheet computing the actual values. There are two triangles: one shows the expected gain by B over A, for up to 12 cards. The other shows the same but each column is multiplied by a power of 2 to get an integer series. It’s not in OEIS but we could put it there or math SE to see if anyone can find a non-recursive formula.

enter image description here In looking for patterns one should focus on alternate columns. One pattern that I thought was cool was that the smallest term in alternate columns of the bottom triangle is 3, 13 & 55 - every third fibonacci number. And the next one 233 occurs in the correct column, but is no longer the minimum value. But 987 is nowhere to be seen. I have checked my arithmetic, and I think my table is correct, but it would be good if someone else can produce their own values independently for 10 cards and beyond.

$\endgroup$
  • $\begingroup$ Are you sure this really works? While it is true for smaller values, i=1, j=4 does not match my calculations. B(0,4)=2.5; B(1,3)= 1.75, but B(1,4)=2, and not 2.125 as your expression gives, I think. I might be wrong though. $\endgroup$ – elias Nov 4 '17 at 20:59
  • $\begingroup$ @elias I don’t think that A can do better than coin-flip because that will ensure that the pay-off is the same whichever guess B makes, which is the hallmark of a saddle-point. Please tell me if I am wrong! :) $\endgroup$ – Laska Nov 4 '17 at 21:03
  • $\begingroup$ Sure, I agree his optimal strategy is a coinflip, I also addressed this in my answer. However, it is not always between the two options you give, B(2,2)=1.5, and with that choice B(1,4)=(B(0,4)+B(2,2))/2 $\endgroup$ – elias Nov 4 '17 at 21:19
  • $\begingroup$ @elias: I agree - I will change my formulae $\endgroup$ – Laska Nov 4 '17 at 21:39
  • $\begingroup$ I think you are on the right track, but there is definitely some problem with the parentheses, I'm not sure how to interpret, and cannot compare with my results. Can you share your spreadsheet maybe? Thanks! $\endgroup$ – elias Nov 4 '17 at 23:18
5
$\begingroup$

Seems like an interesting, difficult problem! Here are my first thoughts. It's better to start analyzing the game for smaller decks.

  • For a three card deck, A's best strategy is to start with 2, then randomly choose between 1 and 3. B will guess the second card half the time, then always guess the last card, for 1.5 correct guesses on average.

  • For a four card deck, A's should start by choosing 2 or 3 (I will justify why later*). Say she chooses 2. For her next card, A can pick 1, 3 or 4. B must choose between high or low. Here is the payout matrix, which tells the total number of guesses B will get correct on average for each possible pair of choices: $$ \begin{array}{cc} & \text{A's choice}\\ \text{B's choice} & \begin{array}{c|ccc}&1&3&4\\\hline L&3&1.5&2\\H&2&2.5&3\end{array} \end{array} $$ For example, if A chooses 1, then B will certainly guess the last two cards correct, plus an extra correct guess if B guessed Low. If A chooses 3, then we are back in the 3 card situation discussed before, so B gets 1.5 guesses correct on average, plus an extra if Bob guessed high.

    Note that it is not wise for A to choose 4, since 3 is always a better option. However, among the remaining two options, there is no best pure strategy. Instead, the solution is for A to choose between 1 and 3 with equal odds. On the other hand, B's best strategy is to guess High 75% of the time and guess Low 25% of the time. This results in B getting 2.25 guesses correct on average. (*Note that if A had initially chosen 1 or 4, then B would get 2.5 guesses correct on average, so choosing 2 or 3 is indeed better).

  • For a five card deck, it seems intuitively obvious that A's best strategy is to start by choosing 3, then random choose between 2 and 4, then follow the four card strategy above. This causes B to get 0.5 + 2.25 = 2.75 correct guesses. If A initially chose 1 or 5, then B would get 1 + 2.25 = 3.25 correct guesses, which is worse.

    If A initially chooses 2, then the payoff matrix is$$ \begin{array}{cc} & \text{A's choice}\\ \text{B's choice} & \begin{array}{c|cccc}&1&3&4&5\\\hline L&3.5&2.25&2.25&2.5\\H&2.5&3.25&3.25&3.5\end{array} \end{array} $$ We can ignore the last columns: choosing 3 is identical to 4, while 5 is strictly worse for A. The solution for the game turns out be that A randomly chooses between 1 and 3 with equal odds, while B chooses High 5/8 = 62.5% of the time. This results in B getting 2.875 correct guesses, which is worse than the middle option.

It may seem like the last paragraph was useless, since A's best strategy was obviously to pick the middle number. However, this analysis would be useful for solving the six card deck. For the six card game, A should initially choose 3, then randomly choose between 2 and 4. If A chooses 4, then we are down to the 5 card game where A chose the middle card, and if A choose 2, we are down to the 5 card game where A chose 2, so we need to know the value of this game to solve the six card game.

In general, if we let Opt(n, k) be the value of the game where there are n cards left and the current card is the kth from the bottom, then one has to solve for Opt(n, k) in terms of Opt(n–1, k') for various values of k' by solving a payoff matrix game like the ones above. Perhaps a nice pattern emerges, but I think the only way to find it is to get your hands dirty.

$\endgroup$
  • 2
    $\begingroup$ Great work! I found a closed form for what you note as Opt(n,k). Still have to clear my notes, will post it afterwards. $\endgroup$ – elias Nov 4 '17 at 10:35
3
$\begingroup$

Let me add first, that the solution I give does not use any 'creative idea', only the usual math tools of game theory - to come up with the results, I used this solver. As I see it, this is much more a mathbook problem than a puzzle. As the calculations themselves aren't particularly interesting, I do not add the details of them, only publishing the end result. At some part I used some pattern matching instead of an actual proof, so there might be some errors. Furthermore, there might be always typos, please doublecheck before using my results. Maybe there is a workaround that does not need all this apparatus.

As Gareth already pointed out in his answer, it does not matter which numbers have been taken in earlier rounds, because the only thing matters is the relative ordering of the cards. Thus we can refer to any situation by two numbers: how many cards are left (which I will denote by $n$ as well), and the rank of the latest announced one among those (denoted by $k$; so $k=1$ means it is the smallest that was announced, $k=n$ means the largest).

I am using the very same approach that Mike did in his answer. I would like to point out that the actual values of the games are somewhat different from the numbers he used in his payoff-matrices (he counted how many times B will answer correctly, but according to the original question B gets one point deducted for every wrong answer), but the connection between his and my numbers are linear, and the calculations that are done on the payoff-matrices to determine the optimal strategies of the players are not affected by these.

The expected value of B's points

Before I can post the expected value of B's points for any $(n,k)$, I need to define some integer sequences (in an iterative way), which will be used in the expression.

Let $h^0_n = \text{round}(2^{n-3})$, that is from 0-index: $0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, ...$

Let $h^1_n = h^0_n$ if $n$ is odd, and $h^1_n = h^0_n + h^0_{n/2}$ if $n$ is even, that is $0, 0, 1, 1, 3, 4, 9, 16, 34, 64, 132, 256, 520, ...$

In general, let $h^i_n = h^{i-1}_n$ if $n$ is not divisible by $2^i$, and $h^i_n = h^{i-1}_n + h^0_{n/2^i}$ if $n$ is a multiple of $2^i$.

After enough steps of this iteration, the first few elements of the sequence won't change anymore. In some sense, there is a limit sequence $h^\infty$, which starts like: $0, 0, 1, 1, 3, 4, 9, 16, 35, 64, 132, 256, 521, ...$

The actual payoff values are then the following:

For $k>\lceil n/2 \rceil$: $v(n,k)=v(n,n+1-k)$, because of symmetry.

For $k=\lceil n/2 \rceil$: $$v(n,\lceil n/2 \rceil) = 1 + \sum_{i=2}^{\lfloor n/2 \rfloor}(h^\infty_i / 2^{2i-3})$$

For $k<\lceil n/2 \rceil$: $$v(n,\lceil n/2 \rceil -i) = v(n,\lceil n/2 \rceil) + \sum_{j=\lfloor n/2 \rfloor +1}^{\lfloor n/2 \rfloor +i}(h^\infty_j)/2^{n-3}$$

How to use the values given by the above expression to determine the optimal strategy of the players?

I will show this through the same example Mike used: $n=5, k=2$. The elements of the payoff matrix are based on the $v(n-1,i)$ values, adding or subtracting 1 depending on the relation between $k$ and $i$ matching B's choice. $$ \begin{array}{cc} & \text{A's choice}\\ \text{B's choice} & \begin{array}{c|cccc} &1&3&4&5\\ \hline L&v(4,1)+1&v(4,2)-1&v(4,3)-1&v(4,4)-1\\ H&v(4,1)-1&v(4,2)+1&v(4,3)+1&v(4,4)+1 \end{array} \end{array} $$ or, by replacing the values calculated by the expression above: $$ \begin{array}{cc} & \text{A's choice}\\ \text{B's choice} & \begin{array}{c|cccc} &1&3&4&5\\ \hline L&3&0.5&0.5&1\\ H&1&2.5&2.5&3 \end{array} \end{array} $$ Although these numbers are different from the ones used by Mike (he was using only the number of B's correct answers, while I use his points that is the difference between his correct and wrong answers - however, as the total number of answers is constant 4, these can be mutually expressed from each other, revealing a linear connection), the optimal strategy is the same: A should choose between '1' and '3' 50-50%, B should say 'High' with 62.5%.

You can confirm this with the solver I've linked previously, but don't forget to transpose the matrix and negate the elements, as it needs it in that form.

There is a slight difference for the very first step, when A announces the first number. He should make his choice based on the $v(50,k)$ values, as those are the actual payoff values. This leaves him with $k=25$ or $k=26$ as equivalent best choices. (Note he want's to maximize his own points, hence minimize B's in this zero-sum game.)

How did I come with the expression, and where I see some room for improvement

I calculated the game values recursively for $n \le 10$. Then I looked at the values and saw the pattern above emerging. Of course those numbers work even with $h^2$ instead of $h^\infty$, but my intuition says, the latter should be used in the general case - $n=50$ needs $h^4$. I might be totally wrong on this, any help is welcome.

As I can see, for every $n$, the payoff matrix will have a special form which allows A to exclude all but two choices (because the two elements in each column have a difference of +/-2). Maybe this part of the problem can be attacked to come up with some simplifications. While I was typing this, Laska provided a shorter answer, which might be the perfect answer.

$\endgroup$
2
$\begingroup$

Let me first of all check that I've understood. A announces a number (which is removed from the list), then secretly picks another number. B guesses whether that's higher or lower than A's announced number, and someone gets a point. Then we completely forget about that secretly-picked number, and now we do the same thing with the players the other way around. Is that right?

[EDITED to add:] No, it turns out that wasn't right. I'm busy right now but will edit this later to address the question as it now stands. Unless someone else has answered that question well by the time I get to it, of course.

If so:

It doesn't really matter which numbers have already been taken; all that matters is their ordering. In particular, your choices on one turn make no difference to the outcomes of later turns.

So the only question is this: You have n numbers still unguessed, which (because we only care about the ordering) we might as well pretend are 1,2,...,n. You now pick two of them (let's say a and b), announce a, and invite the other player to guess which of the two is higher. How do you maximize the probability that they guess wrong?

Well, obviously you don't announce 1 or n because then they will always guess correctly. Otherwise, you can choose a and then choose any probability you like for whether b is higher or lower, then use your random number generator to decide which to go for, and then pick a higher/lower number as appropriate. This applies just the same whichever a you pick. Unless you want to leak information to your opponent, you will use the same higher/lower probability whatever you pick for a. And then you maximize the worst-case probability that your opponent gets it wrong by always choosing to make the next number higher exactly half the time. And then it doesn't matter what guesses your opponent makes.

So, with best play each point goes with equal probability to either player, until you are down to just two numbers left when the guessing player gets the point. An optimal strategy is to (1) never announce the highest or lowest remaining number, and (2) make your secret number bigger than your announced number exactly half the time.

$\endgroup$
  • $\begingroup$ Isn't there some information leak (because of b becoming next rounds a) by the guesser knowing this strategy at n = 4? A won't choose 1 or 4, by symmetry, we can say he chooses a = 2. But B knows he won't choose 1 or 4 in the next round either, so can be sure b = 3. $\endgroup$ – elias Nov 3 '17 at 13:09
  • $\begingroup$ Ah, sorry, I explained badly. I will edit. The secretly-picked number becomes the new starting point for the second step. $\endgroup$ – user2390246 Nov 3 '17 at 13:16
  • $\begingroup$ I think your approach can be turned into a proper solution using recursion, but would like to see the lack of independence in the choices of a and b addressed. $\endgroup$ – elias Nov 3 '17 at 13:16
  • $\begingroup$ Sorry, I missed your interpretation of the question was different than mine. Question is now updated and clarified my concerns are valid. $\endgroup$ – elias Nov 3 '17 at 13:25

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.