A Two Persons Game (gameh)

Run LPL Code  ,  PDF Document

There exist many games involving two players in which the gain of one player is the loss of the other, and vice-versa; examples are: checkers, poker, chess, go, tic-tac-toe and many others. We call them zero-sum games. For more theoretical aspects see [4]. The question is, what is the best strategy to play the game. Let’s look at a particular game.

Problem

Two players play the following number game: Each chooses (secretly) a positive number. The numbers are then uncovered at the same time and compared. If the numbers are equal, neither of the players will get a payoff. If the numbers differ by one, then the player who has chosen the higher number obtains the sum of both, otherwise the player with the smaller number obtains the smaller of both. The play is repeated endlessly. Which number and how often should a player choose a number in each round? (The game has been described in [1].)

Before we model the problem, let us just play the game for a while to get a feeling for it. Player 1 might reason as follows: “If I choose a large number my loss can be big, so I better choose a small number – say 1 – and in the worst case my loss is only 3, if player 2 chooses 2.” Player 2 might reason on the same line. So they both choose 1, and nobody gets a payoff. In the next round player 1 might deviate from his strategy: “Well, since my opponent wants to minimize the risk, I’ll choose 2.” Player 2 might reason on a similar line: “My opponent certainly thinks that I am risk-averse and he will choose 2, I’ll anticipate his choice and I then choose 3, and get a high return.” This kind of reasoning may go on and on, and so each player will choose certain numbers with certain frequencies. We call the way (the frequencies) a player chooses his numbers a strategy.

Modeling Steps

The different actions to consider are the numbers. We define them as a set. Let’s say we restrict the game to numbers between 1 and 50.

1. The payoff of the game for the first player, if the first player draws the numberr i and the second player draws number j, can be defined by a matrix p_i,j. In this game the payoff is calculated as follows:

   

   The payoff for the second player is just –p_i,j, that is, the game is symmetric with respect to the payoffs.

2. The question is how frequently a particular number should be drawn by the player. Let’s introduce a variable for each number: x_i with i ∈ {1,…, 50}. x₁ = 0.12, for example, means that the number 1 is drawn in 12% of all draws by the first player. Hence, x_i is the frequency with which the first player should draw the number i.

3. The probability to draw a number i ∈{1,…, 50} is one, therefore we have:

   

4. Let p_i,j (with i,j ∈ {1,…, 50}) be the given payoff matrix for the first player, if player one draws the number i and player two draws the number j. Per round, the first player’s average gain is ∑ _ip_i,jx_i when player two draws a j. Hence, per round it is guaranteed to the first player to gain on average no less than

   

   He should choose x_i in such a way that this average gain is maximized.

Hence the complete model is

model gameh "A Two Persons Game"; 
    set   i,j :=[1..50]; 
    parameter  p{i,j} := 
      if(i>j+1,-j , i=j+1,i+j , i=j-1,-i-j, i<j-1,i); 
    variable   x{i}  "Strategy of player 1"; 
    constraint  R: sum{i} x = 1; 
    maximize gain: min{j} (sum{i} p*x); 
    Write{i|x}('Choose number %1d with probability %7.5f' n', i,x); 
    Write('The value of the game is %4.2f' n', gain); 
  end

We only did our consideration for the first player. Of course, in a similar way, we could introduce the point of view of the second player. If his strategy is y_j with j ∈{1,…, 50}, then his average gain per round is ∑ _jp_i,jy_j if the first player plays i. Hence, he has a guarantee not to loose more than max _i(∑ _jp_i,jy_j) per round. The second player then should minimize this quantity. The model then is;

It turns out that the two methods (maximizing the minimal gain and minimizing the maximal loss) lead to exactly the same strategy as for the first player. This follows from the famous Min-Max Theorem (see below). Therefore, we do not need to consider the second player. The problem stated for the second player in LPL code is as follows (see gameh0):

model gameh0 "A Number Game"; 
    set   i,j :=[1..50]; 
    parameter  p{i,j} := 
      if(i>j+1,-j , i=j+1,i+j , i=j-1,-i-j, i<j-1,i); 
    variable   y{j}  "Strategy of II"; 
    constraint  R: sum{i} y = 1; 
    minimize loss: max{i} (sum{j} p*y); 
    Write{j|y}('Choose number %1d with probability %7.5f' n',j,y); 
  end

The solution for this dual model is the same as for the first player, hence, they should both apply the same optimal mixing strategy.

Solution

The surprising result first is that numbers larger than 5 should never be used! Only the five first numbers should be chosen with frequencies as follows:

The table displays the optimal strategy. The value of the game is zero, because in the long run nobody will gain if both apply the optimal strategy. The value transferred from one player to another is zero!

One can generate a table of numbers reflecting the frequencies of the numbers to be chosen in an optimal strategy. The model that generates this table T_k,r of any size K × R with k = {1,…,K} and r = {1,…,R} is as follows (see gameht:

model gameh "A Two Persons Game"; 
    set   i,j :=[1..7]; 
    parameter  p{i,j} := 
      if(i>j+1,-j , i=j+1,i+j , i=j-1,-i-j, i<j-1,i); 
    variable   x{i}  "Strategy of player 1"; 
    constraint  R: sum{i} x = 1; 
    maximize gain: min{j} (sum{i} p*x); 
   
    x{i|i>1}:=x[i-1]+x[i]; 
    set k,r:=[1..34]; 
    parameter q{k,r}; n; 
    integer parameter T{k,r}:= 
       q[k,r]:=Rnd(0,1), n:=1, 
       while(q>x[n], n:=n+1), n; 
    Write{k}('%2d' n' , {r} T); 
  end

An extract of the resulting table T_k,r is given as follows:

 3 3 5 3 2 1 4 5 4 4 1 1 5 4 3 5 3 2 1 3 2 5 1 2 3 5 1 1 2 1   3 4 4 1 1 1 1 4 4 2 3 3 4 3 2 4 4 1 1 1 1 1 3 1 3 2 2 4 2 2   3 2 4 4 3 4 2 3 3 5 3 1 3 2 1 1 3 3 1 5 4 3 5 2 3 4 3 3 1 1   2 1 1 5 3 3 1 3 1 2 5 3 2 3 5 2 2 3 1 4 4 1 5 3 1 5 2 1 4 3   2 3 1 1 3 5 3 3 3 1 4 1 1 5 4 3 5 1 1 1 1 2 2 2 1 3 3 3 3 4

A optimal strategy for this game is to randomly choose a row or a column and then choose the numbers consecutively in that row/column, for example.

Further Comments

This game is an instance of a problem treated in Game Theory, called “Two-person zero-sum game”. The famous Min-Max Theorem applicable to these games says that

1. There is a number V , called the value of the game. if x_i and y_j are the optimal strategies for player I and II then this value is calculated by:

   

2. There is a mixed strategy for player I such that I’s average gain is at least V , no matter what player II does.

3. There is a mixed strategy for player II such that II’s average loss is at most V , no matter what player I does.

For our number game, we have V = 0 (because the payoff is symmetric – player I gains exactly what player II looses, and vice versa). That means if a player plays the optimal strategy his average gain is at least 0, and his average loss is at most 0, no matter what the opponent does.

Let’s compare various (possibly not optimal) strategies x_i and y_j for the two players. The average gain G1 for player I is calculated as follows: The expected payoff for player I from a single round (i,j) – that is, when player I chooses number i and player II chooses j – is: p_i,jx_iy_j. Therefore, the expected return for player I over all combinations (i,j) is

This is zero if both play the optimal strategy as specified by V . What happens if player II does not play the optimal strategy but player I does? Suppose, player II always plays 1 (y₁ = 1, y_i = 0 for i ⁄= 1). Calculating G1 for our game gives: G1 = 0. That is, if player I plays the optimal strategy and player II always plays the number 1, then there is no gain for player I. There is no guarantee for player I to make a positive gain, if he plays the optimal strategy even if his opponent does not play the optimal strategy. The Min-Max Theorem only says that a player with the optimal strategy get at least V whatever the opponent does. Suppose now that player I plays the optimal strategy and player II chooses any number between 1 and 10 with probability 10%. Then G1 = 1.1544554, so the average gain for player I is positive in this case. An implementation of various non-optimal strategies of player II is given in model gameh1.

Questions

1. Change the rules of the game to the following: “If the numbers are equal, none of the players will get a payoff. If the numbers differ by one or two, then the player who has chosen the higher number obtains the sum of both, otherwise the player with the smaller number obtains the smaller of both.” Find the optimal strategy.

2. Interpret the result after running the model, if you change the payoff matrix to:

        p{i,j}:= if(i>j+1,-j-1 , i=j+1,i+j , 
                      i=j-1,-i-j, i<j-1,i*2);

3. Tennis Strategy: Your opponent has a stronger forehand than backhand. To increase your chances of winning, how often should you return to her backhand side? Suppose your payoff matrix is as follows:

   ---

   	opp. forehand	opp. backhand
   your forehand	0.90	0.30
   your backhand	0.20	0.60

   Table 1: Payoff Matrix of Tennis Game

   ---

4. Here is another game from Mendelsohn: Two players simultaneously choose a positive integer between 1 and 100. If the numbers are equal there is no payoff. The player that chooses a number one larger than that chosen by his opponent wins 1. The player that chooses a number two or more larger than his opponent loses 2. Find the game matrix and solve the game.

Answers

1. All you need to do is to change the payoff matrix to

        p{i,j} := if(i>j+2,-j , i=j+2 or i=j+1,i+j , 
                       i=j-1 or i=j-2,-i-j, i<j-2,i);

   The optimal strategy then is as follows:

     Choose number  1 with probability  1.28155%    Choose number  3 with probability 19.74369%    Choose number  4 with probability  9.91102%    Choose number  5 with probability 12.99457%    Choose number  6 with probability 17.44642%    Choose number  7 with probability 14.53355%    Choose number  8 with probability  6.85685%    Choose number  9 with probability 13.05893%    Choose number 10 with probability  4.17343%

2. The value of the game (the objective function value) is 0.15, which means that the first player can make a guaranteed average gain of 0.15 at each round. This game is, of course, “unfair”. To make it fair, player one should pay 0.15 at each round to player two.

3. Use 40% forhand and 60% backhand, The game value is 0.48, this is the optimal strategy. The model is as follows (see gameh2 to run it):

   model gameh2 "Another Two Persons Game"; 
       set   i,j :=[forhand backhand]; 
       parameter  p{i,j} := [0.9 , 0.3 , 0.2 , 0.6]; 
       variable   x{i}; 
       constraint  R: sum{i} x = 1; 
       maximize gain: min{j} (sum{i} p*x); 
       Write{i|x}('Choose %s with probability %4.2f' n', i,x); 
       Write('The game value is %4.2f' n', gain); 
     end

4. The payoff matrix is given by:

   

   In LPL syntax:

     parameter p{i,j}:= 
         if(i>j+1,-2 , i=j+1,1 , i=j-1,-1, i<j-1,2);

   The optimal strategy is: x₁ = 0.25, x₂ = 0.50, x₃ = 0.25, meaning that number 1 and 3 are chosen in 25% of the cases and number 2 in 50% of the cases.

References