Analysis of WAITING FOR MR PERFECT I

Prerequisites: Chapters 1, 2, 4, 6, and 7.

There are several variants of these game, depending on the parameters.

• How many players are playing? More players means tougher competition.
• How many rounds are played? The smaller the number of rounds compared to the number of players, the tougher the game becomes.
• Population: What kind of awards are available, and what is the distribution? Is the population of awards huge (meaning that the distribution doesn't change through the different rounds) or small?

Throughout this chapter we assume that there are two players, and that three types of awards are possible, carrying payoffs of 1, 2, or 3 for both players. Cases where the awards carry different payoffs for the different players would also be interesting, but are not discussed here. We assume that in each round, the low payoff award 1 occurs with probability P(1), and the other two awards 2 and 3 with probabilities P(2) and P(3). Cases where the probabilities in a round depend on the awards drawn in the previous rounds would again be interesting, but are not treated here.

Two Rounds

In this chapter we will find the pure Nash equilibria in the two round case by using the normal form of the game. In the second part we will look into the mixed Nash equilibria of the two-round version, but mainly concentrate on the four round version, and will solve this using the extensive form.

1. The last round

Players always have the choice between expressing interest or rejecting an award, but in the last round they don't really have a choice as long as the awards are positive, which of course we may assume. Any player that doesn't yet have an award in the last round would express interest. The expected value of this last possible award is P(1)+2·P(2)+3·P(3). If both players are still without award, the expected payoff for both would be (P(1)+2·P(2)+3·P(3))/2, since the award is won with probability 1/2, and otherwsise the player didn't receive anything. But if one player already has an award, the expected payoff for the still awardless player equals P(1)+2·P(2)+3·P(3).

The reader may wonder here why we bother with P(1), P(2), and P(3), which will make all our formulas much more complicated, instead of selecting concrete values, like for instance P(1)=1/2, P(2)=1/3, and P(3)=1/6. The approach we use has one advantage: If we are later interested in different probability values, like P(1)=0.2, P(2)=0.3, and P(3)=0.5, for instance, then we don't have to repeat the whole analysis again--- rather we just change the parameters in the resulting formulas. This method, shifting from the concrete to the general, is very frequent in mathematics, and one of the reasons for the success and power of the mathematical method. If these parameters P(1), P(2), and P(3) confuse you in what follows, then please write down all formulas and replace the parameters by concrete values.

2. The eight pure strategies

Having settled that the players don't have a choice in the second round, let's now focus on the first round. In the first round, each player may face an award of value "1", "2", or "3", and has two options in each case. Therefore each player has 2³=8 pure strategies, which are encoded by the three-letter words NNN, ... III. The first letter indicates how the player would play if the first award would be a "1", with "N" indicating "no interest" and "I" indicating interest, and the same for the case of an award of value 2 and the second digit, and an award of value 3 and the last digit.

3. Computing the payoffs

Since each player has eight pure strategies, the normal form of the game would be an 8×8 bimatrix. How are the payoffs computed? Since we want to discuss the general case, let's assume that Ann plays strategy A₁A₂A₃, where the A_i are either the letter "N" or the letter "I", and Beth plays strategy B₁B₂B₃. We look at the payoffs for both players in each of the three cases where the first-round award is 1, 2, or 3 separately. Assume this first-round award is k, either 1, 2, or 3.

• If both are interested, i.e. if A_k=B_k="I", then each of the two players will get the award with probability 1/2, and with the remaining 1/2 probability will have to be satisfied with the award of the second round, whose expected value is P(1)+2·P(2)+3·P(3), as described above. Then the expected payoff for each player equals k/2+(P(1)+2·P(2)+3·P(3))/2 = (k+P(1)+2·P(2)+3·P(3))/2.
• If only one of them, let's say Ann, is interested, i.e. if A_k="I" and B_k="N", then Ann gets the first round award, therefore the payoff of k and Beth gets the second-round award with expected value P(1)+2·P(2)+3·P(3).
• Finally, if none of the players is interested in first-round awards of value k, then both fight over the second-round award, and have expected payoffs of (P(1)+2·P(2)+3·P(3))/2.

Having computed the payoffs for Ann and Beth for each of the three cases of a first-round award k of 1, 2, or 3, we now have to combine these formulas. What we do is computing another expected value, weighting the payoffs for the three cases by their probabilities P(1), P(2), and P(3). To give an example, if Ann chooses strategy "INI" and Beth chooses strategy "NII", then the expected payoff for Ann is

Let's for as moment get a little more concrete, and choose P(1)=1/2, P(2)=1/3, and P(3)=1/6. Then the 8×8 bimatrix normal form is:

	III	IIN	INI	INN	NII	NIN	NNI	NNN
III	1.667, 1.667	1.778, 1.556	1.722, 1.611	1.833, 1.5	1.5, 1.833	1.611, 1.722	1.556, 1.778	1.667, 1.667
IIN	1.556, 1.778	1.417, 1.417	1.611, 1.722	1.472, 1.361	1.389, 1.944	1.25, 1.583	1.444, 1.889	1.306, 1.528
INI	1.611, 1.722	1.722, 1.611	1.333, 1.333	1.444, 1.222	1.444, 1.889	1.556, 1.778	1.167, 1.5	1.278, 1.389
INN	1.5, 1.833	1.361, 1.472	1.222, 1.444	1.083, 1.083	1.333, 2.0	1.194, 1.639	1.056, 1.611	0.917, 1.25
NII	1.833, 1.5	1.944, 1.389	1.889, 1.444	2.0, 1.333	1.417, 1.417	1.528, 1.306	1.472, 1.361	1.583, 1.25
NIN	1.722, 1.611	1.583, 1.25	1.778, 1.556	1.639, 1.194	1.306, 1.528	1.167, 1.167	1.361, 1.472	1.222, 1.111
NNI	1.778, 1.556	1.889, 1.444	1.5, 1.167	1.611, 1.056	1.361, 1.472	1.472, 1.361	1.083, 1.083	1.194, 0.972
NNN	1.667 1.667	1.528 1.306	1.389 1.278	1.25 0.917	1.25 1.583	1.111 1.222	0.972 1.194	0.833 0.833

4. Domination

Some of these pure strategies look a little odd. For instance, in strategy "NIN" the player would express interest in the first round only for an award of value 2. Why would a player show interest for a "2" but not for a "3"? Still one could argue that a player playing this strategy just avoids the fight in case of a "3", leave the award to the other player, and then take whatever comes in the last round. However, we will see in this section that "NIN" is a strongly dominated strategy and should therefore not be played.

In the following we will compare strategies for Ann differing only in how they handle one value k of the first-round award whether one of them dominates the other. Such two strategies are fairly simple to compare, since in the two cases of having a first-round award different to k, the payoffs for Ann are identical no matter what Beth plays. Therefore to compare the payoffs for Ann for these two strategies, one only has to consider Ann's payoff in case the first round award equals k, and look at the two cases of Beth being interested in a value of k, or of not being interested. If one of Ann's strategies considered is better than the other in both these cases, then we have discovered strong domination.

When should Ann rather show interest in values of k in the first round? If (k+P(1)+2·P(2)+3·P(3))/2 > (P(1)+2·P(2)+3·P(3)), and if Beth is interested in a certain value k, then it is also preferable for Ann to be interested in that value k. The inequality condition is equivalent to k > P(1)+2·P(2)+3·P(3). If however Beth is not interested in a value k, then being interested in k is better for Ann than being not provided k > (P(1)+2·P(2)+3·P(3))/2. Therefore, for all values k > P(1)+2··P(2)+3··P(3), which is equivalent to

There are also cases where not being interested for some value k is always preferable to being interested for that value k, behavior for all other values being equal. If Beth is interested in k, then Ann not being interested in k is better for her than being interested provided P(1)+2·P(2)+3·P(3) > (k+P(1)+2·P(2)+3·P(3))/2$, i.e. if P(1)+2·P(2)+3·P(3) > k. If Beth is not interested in k, then A being interested in k is better for her than not being interested provided (P(1)+2·P(2)+3·P(3))/2 > k. Overall this domination occurs provided P(1)+2·P(2)+3·P(3) > 2k, which is equivalent to

Let us summarize our findings on domination:

Depending on whether P(2)+2·P(3) lies below 1 or between 1 and 2 we get two different cases, but there are in both cases 6 strongly dominated pure strategies. If P(2)+2·P(3)=1, we get 4 strongly dominated strategies and some weak domination. Let us now look into these three cases separately:

5. The reduced normal forms in the three cases

The case P(2)+2·P(3) < 1

After eliminating the strongly dominated strategies, we arrive at the following reduced bimatrix:

The two strategies agree on to express interest in case of an award of value 2 or 3 in the first round. Thus, all expected values in all combinations have a common ingredient of

• A_1,1 = B_1,1 = M+P(1)·(1+P(1)+2·P(2)+3·P(3))/2.
• A_2,2 = B_2,2 = M+P(1)·(P(1)+2·P(2)+3·P(3))/2.
• A_1,2 = B_2,1 = M+P(1).
• A_2,1 = B_1,2 = M+P(1)(P(1)+2·P(2)+3·P(3)).

Since P(2)+2·P(3) < 1, and therefore P(1)+2·P(2)+3·P(3) < 2, the four numbers are ordered as

The case P(2)+2·P(3) > 1

As in the previous case, we eliminate the strongly dominated strategies, and get the following IESD bimatrix:

The two strategies agree on not expressing interest in case of an award of value 1, and on expressing interest in case of a value of 3. All expected values in all combinations have a common ingredient of

• A_1,1 = B_1,1 N+P(2)·(2+P(1)+2·P(2)+3·P(3))/2.
• A_2,2 = B_2,2 = N+P(2)·(P(1)+2·P(2)+3·P(3))/2.
• A_1,2 = B_2,1 = N+P(2)·2.
• A_2,1 = B_1,2 = N+P(2)·(P(1)+2·P(2)+3·P(3)).

Since P(2)+2·P(3) > 1, and therefore P(1)+2·P(2)+3·P(3) > 2, the ordering of the four coefficients is

The case P(2)+2·P(3) = 1

There follows P(1)+2·P(2)+3·P(3)=2. The IESD process leaves the reduced bimatrix

This bimatrix has nine Nash equilibria in pure strategies: The six pairs (NII,III), (NII,INI), (III,NII), (INI,NII), (III,NNI), (NNI,III), which are Pareto-dominating the remaining three (NII,NII), (NII,NNI), and (NNI,NII).

Overall this result is not very surprising. It simply says that we have three cases depending on the expected value of the award in the second round P(1)+2·P(2)+3·P(3) is less than 2, larger than 2, or equal to 2. If it is less than 2, then we would be interested in an award of value 2 in the first round, since we would expect nothing higher. If P(1)+2·P(2)+3·P(3) is higher than 2, then an award of 2 in the first round becomes uninteresting. However, since both players know that one of them has to take the award in the first round, or otherwise they get into trouble, one of the players has to play the role of "dove" and express interest even if the first round award is not interesting enough. Only in the case of an expected value of the second round award higher than 2 and a first round award of 1, rebellion (not expressing interest) pays for the "dove" player, since even when both fight for the second round award, the expected value for both players remains larger than 1.

In the second part of "Waiting for Mr. Perfect" we will see how one more Nash equilibrium appears if we allow mixed strategies, and we will also analyze the slightly more surprising 4-round version.

Exercises

1. Analyse the two player, two rounds variant with awards of value 1, 2, or 3, starting with three awards of value 1, two awards of value 2, and only one award of value 3. In the first round one of these six awards is chosen randomly, and in the second round one of the remaining five awards is selected randomly.
2. How would the game change if the number of available rounds is not fixed at the beginning. Rather after every round, either the whole game ends (say with probability 1/5) or there is another round (with probability 4/5).
3. Discuss the two player, two rounds version with awards "C", "D", and "E", where "C" is worth 2 for Ann but 3 for Beth, "D" is worth 3 for Ann and 1 for Beth, and "E" is worth 1 for Ann and 2 for Beth.