I found the following problem on the page of the wonderful Science Blogs. It is in German. Let me translate it. Bernd writes two different numbers between 1 and 1000 on two cards of paper. Anna selects one, and after seeing it has to decide if she wants to keep it or change to the other card. The player with the higher card wins.

This is a case of a two person game with the following tactics for each player.

• Bernd: He can write any combination (i,j) with 1 <= i < j <= N.
• Anna: She can decide to change up to a number A with 1 <= A <= N.

Note that we simplified the situation for Anna. It does not make sense to change with 3, but not with a smaller number. Weather or not this simplification makes the outcome worse for Anna remains to be investigated.

Now, Bernd can select any of his tactics (i,j) with probability p(i,j), and Anna can select any of her tactics with probability q(A). The problem to select the optimal strategy (i.e. the distribution of probabilities) for each player can be solved with optimization. I have done similar problems with EMT on this page. I solved the problem above for (N=10) with a bit of code.

However, I want to spoil the solution here. If you want to try on your own, do not read further.

• Strategy for Bernd: Bernd should select the pairs (1,2),…,(N-1,N) at random with equal probability.
• Strategy for Anna: Before each game, Anna should select a number A from 1 to N-1 at random, and switch if her number is less or equal A.

Let us prove that this is optimal.

Assume, Anna selects tactics A. So she will change cards at any number smaller or equal A. Then Bernd will lose 1/(N-1) on average with his strategy. This is so, since the only case that makes a difference for him is the pair (A,A+1), where Anna wins all the time. So, no matter what tactics A Anna selects, the worst case is an average loss of 1/(N-1). Only if Anna would select A=N, he would do better.

Now assume, Bernd selects tactics (i,j). Then Anna, with her strategy, will win in any case if i<=A<j. In all other cases, the average result is 0. We need to find the worst case for Anna based on her strategy. That is indeed the case, if Bernd selects a pair (i,i+1) and it is equal to a win of 1/(N-1).

It is now clear that there cannot be a better strategy for either player. Anna cannot win more than Bernd loses on average.

With a bit more care in the proof, it is also clear that it would not help Anna to add more strategies. Assume, she rejects some numbers, and accepts others, instead of rejecting the numbers 1 to A altogether for some A. Then Bernds tactics will lose less or equal 1/(N-1) on average. For an example, assume Anna rejects 1 and 3. Then (1,2) will be a loss for Bernd, (2,3) will be a win, and (3,4) will be a loss, all other cases are 0 on average.

This is a very nice problem. I could not find a reference in the net, however. But it should be known.

Let me add the code for EMT.

>v1=flatten(dup(1:10,10));
>v2=flatten(dup((1:10)',10));
>i=nonzeros(v1<v2); v1=v1[i]; v2=v2[i]; 
>A=(1:10)';
>M=-((v1<=A)&&(A<v2)); 
>function game (R) ...
$## Maximizes G such that R'.q>=G, sum q_i = 1, q_i>=0.
$## Returns {q,G}.
$    m=rows(R); n=cols(R);
$    M=R|-1_ones(1,n); b=zeros(m,1)_1; eq=ones(m,1)_0;
$    c=zeros(1,n)|1; restr=ones(1,n)|0;
$    res=simplex(M,b,c,eq,restr,>max);
$    return {res[1:n]',res[-1]};
$endfunction
>{pB,res}=game(M); fraction res
 -1/9
>k=nonzeros(pB); fraction (pB[k]_v1[k]_v2[k])'
       1/9         1         2 
       1/9         2         3 
       1/9         3         4 
       1/9         4         5 
       1/9         5         6 
       1/9         6         7 
       1/9         7         8 
       1/9         8         9 
       1/9         9        10 
>{pA,res}=game(-M'); fraction res
 1/9
>fraction pA'|(1:10)'
       1/9         1 
       1/9         2 
       1/9         3 
       1/9         4 
       1/9         5 
       1/9         6 
       1/9         7 
       1/9         8 
       1/9         9 
         0        10

This looks a bit difficult. Here are some explanations.

The vectors v1 and v2 simply contain the pairs (i,j) with 1 <= i < j <= N = 10. The trick to get all pairs is to create matrices with 1 to 10 in each row resp. column and to „flatten“ them to vectors. Then we select only the pairs with i < j using the nonzeros() function of EMT.

The matrix M is then constructed in the following way: The element in row A and column (i,j)  is -1 (a loss for Bernd) if i <= A < j. This is the matrix of average outcomes if Anna selects A and Bernd selects (i.j).

The game() function calls the simplex algorithm for the following problem.

\(Mp \ge G, \quad \sum_k p_k = 1, \quad G \to \text{Max.}\)

The probabilities p(k) are then maximizing the worst case G, for all rows of M (tactics of Anna). The result is p and G. We print the nonzero elements of p along with the corresponding i and j.

The same is finally done with the problem seen from Anna’s side.

By the way, the fact that both results must be equal (besides the sign) is an application of duality in optimization.

Really a nice problem!