In this Chapter we will investigate what happens in SEQUENTIAL QUIZ SHOW(n,m) if two of the players cooperate, form a coalition, and share the total win or loss they achieve evenly or according to a predetermined formula. In Section 1 we look at fixed coalitions. In Section 2 we ask which coalitions are most likely to form provided the players of the coalition have to share total win or loss evenly. In Section 3 we drop this requirement of having to share evenly. Finally, in Section 4 we investigate what would be a fair share of the win if all three players work together.
This Chapter is a brief glimpse into cooperative game theory, which is otherwise not covered in this book.
Of course we are not just talking about a change of strategies, rather the game has totally changed. We are no longer playing the three-player game SEQUENTIAL QUIZ SHOW (10,4) but rather a two-player, variant with the Ann/Cindy coalition as one player and Beth the other one. The payoff for the coalition is the sum of the payoffs for Ann and Beth. And we also assume that Beth knows about this coalition --- otherwise we would have to enter the rather tricky field of games of incomplete information.
Here is the extensive form with backward induction analysis, where the payoff of the Ann/Cindy team
is written in red. The only difference in the strategies to the solution of the ordinary game is that
Cindy waits when it is her turn. This change increases the total payoff for the Ann/Cindy team from 2 2/3 to 3.
But it can be seen that Beth profits even more from Cindy not trying an answer---Beth's
expected payoff increases from 3 1/3 to 5. So Beth would probably not mind that Ann and Cindy
have a coalition. Or would she instead try to form a coalition with Ann or Cindy herself?
The analysis of this game, a 2-player game of the Ann/Beth coalition versus Cindy, is left as an exercise, but let us reveal the result. Again the players of the team play slightly different than how they would play if not in a team. Ann and Beth wait, but after Cindy has tried an answer and failed, Ann can wait again and let Beth give the correct answer. In this way, the expected total payoff of the Ann/Beth team goes up to 6 2/3, whereas Cindy stays at her expected payoff of 2/3.
Again Ann and Beth will not try an answer. Cindy can also afford not to try an answer, since she knows that Ann will try an answer next, and will only fail with probability 1/2, in which case Beth will win for the team. The expected payoff for the Beth/Cindy team is 5, one more than the sum of Beth's and Cindy's payoff in the non-team case. But Ann will also profit from this changed strategy, her payoff equals 3, also one more than in the ordinary case.
For this and the next sections, we use the following terminology: Let v(A), v(B), v(C), be the expected payoffs for Ann, Beth, and Cindy if the game is played without coalition, and let w(AB) be the expected total payoff of the coalition Ann/Beth, whereas w(C) means the expected payoff for Cindy provided she faces an Ann/Beth coalition. The values w(AC), w(B), w(BC) and w(A) are defined accordingly.
In the case n=10 and m=4, we have v(A)=2, v(B)=10/3=3.33, v(C)=2/3=0.67, w(AC)=3, w(B)=5, w(AB)=20/3=6.66, w(C)=2/3=0.67, w(BC)=5, w(A)=3, as has been shown in the previous section.
The expected values for each player, after the coalitions have divided the joint payoff 50:50, are shown in the following table:
| no team | Ann/Cindy | Ann/Beth | Beth/Cindy | |
| Ann | 2 | 1.5 | 3.33 | 3 |
| Beth | 3.33 | 5 | 3.33 | 2.5 |
| Cindy | 0.67 | 1.5 | 0.67 | 2.5 |
We get v(A)=8/3=2.67, v(B)=4, v(C)=4/3=1.33, w(AC)=4, w(B)=3.2, w(AB)=8, w(C)=4/3=1.33, w(BC)=6, w(A)=4.
The expected values for each player, after the coalitions have divided the joint payoff 50:50, are shown in the following table:
| no team | Ann/Cindy | Ann/Beth | Beth/Cindy | |
| Ann | 2.67 | 2 | 4 | 4 |
| Beth | 4 | 3.2 | 4 | 3 |
| Cindy | 1.33 | 2 | 1.33 | 3 |
Will some coalition form? And if, which coalition will form, and which split will result?
In order to investigate these questions, let us concentrate on the negotiation process, which takes place before the actual quiz show game is played. It makes sense to make a few assumptions about this process, and also to formalize it somewhat. So assume the three players are sitting around a table and talking about coalitions. Two players can tentatively agree on a coalition, including a split ratio, however, at any time only one coalition can tentatively exist, and no three player coalition is possible. If no tentative coalition exists, such a coalition is created if the two players involved agree to it, which they would only do, we assume, if both would get higher expected payoff. The third player obviously does not have to agree. If two players would have a tentative coalition including a split ratio, this ratio can not be changed, since for one player change would mean decreasing payoff. The existing tentative coalition can terminate in two ways. Either one of the two players involved announces that she is no longer interested in the coalition. We assume that she would do this only if her payoff without coalitions would be higher than her expectations in the coalition. Or, the coalition could terminate since one of the two players involved wants to form tentatively a coalition with the third player. Then the two players forming the new tentative coalition have to agree, and for that both have to have higher expectations than before.
Let us call a coalition stable if none of the two ways of terminating such a tentative coalition would occur, since the expected payoffs in the no-coalition case is not higher for both players involved, and also since any tentative new coalition involving the third player, and giving her a higher expected payoff, would necessarily decrease the expected payoff for the other player in the coalition.
The negotiation phase ends if no movement has been achieved for some time, or the two coalition players firmly believe that this is the coalition and split they want to go for. After that, the contracts are signed and the game is played. We assume that any such resulting coalition would be stable.
We express splits of win or loss not as percentages but rather in terms of the expected values. So, if for instance the Ann/Beth coalition would expect a joint payoff of 8, then 5:3 is a possible split, meaning that Ann carries 5/8 of the win or loss and Beth carries 3/8.
If Ann does not agree to a coalition, then she expects w(A) or v(A), depending on whether Beth and Cindy form a coalition or not. Therefore we may safely assume that Ann would not agree to a coalition and split where the expected value for her is less than the smaller one of v(A) and w(A). Let us look at two concrete cases:
We use the results in Section 2.1, v(A)=8/3=2.67, v(B)=4, v(C)=4/3=1.33, w(AC)=4, w(B)=3.2, w(AB)=8, w(C)=4/3=1.33, w(BC)=6, w(A)=4. Possible tentative coalitions are Ann/Beth with splits from 4.8:3.2 to 2.67:5.33, Ann/Cindy with the split of 2.67:1.33, and Beth/Cindy with splits from 3.2:2.8 to 4.67:1.33. The Ann/Cindy coalition is not stable, since almost every of the possible Ann/Beth coalitions are better for both Ann and Beth. However, the Ann/Beth coalitions with splits from to 4.8:3.2 to 3.33:4.67 are also not stable, since some Beth/Cindy coalitions are better for both Beth and Cindy. Take the example of a 4:4 split, and recall that Cindy expects w(C)=1.33 then. Now Beth and Cindy could profit from a coalition with a 4.3:1.7 split, for instance. The Beth/Cindy coalitions with splits from 3.2:2.8 to 4:4 are also not stable---Beth could terminate the tentative coalition and expect a payoff of 4 in the no-coalition case.
Therefore the only stable coalitions are Ann/Beth coalitions with splits from 3.33:4.67 to 2.67:5.33, and Beth/Cindy coalitions with splits from 4:4 to 4.67:1.33.
This case is actually more confusing---it can be shown, see the project below, that there exists no stable coalition.
Wouldn't it make most sense for all three players to form a coalition of all three? Ann, Beth, Cindy, and Ann again would wait, until Beth has only one answer left and can "dare" and answer. Of course, the payoff for the coalition would be n. We would need enforceable contracts before the game starts to ensure that Beth doesn't take the money and run, but shares it with Ann and Cindy according to a scheme they would have written into this contract.
Perfect so far, but how would they share the joint payoff of n? Obviously Ann, Beth, and Cindy each should get at least as much as they would get when playing alone, otherwise they may not cooperate. Moreover, for the same reason each possible coalition Ann/Beth, Ann/Cindy, and Beth/Cindy should get as least as much as they would get when forming these two-player coalitions. All such distributions are called the core.
The core is usually displayed graphically using barycentric coordinates.
Note that when we talk about a distribution of the win n, we talk about a triple (a,b,c)
of three numbers where a+b+c=n. As pairs of numbers are usually displayed in the plane,
triples of numbers can be represented in 3-dimensional space. However, the triples of
numbers summing up to n form a plane inside 3-dimensional space, and if we add the requirements
that all three numbers a, b, and c should be positive, we arrive at a triangle.
These triangle is now taken out of 3-dimensional space and put into the plane, see
the example to the right for n=10.
Triples (a,b,c) with nonnegative coordinates a, b, c and obeying a+b+c=10
correspond to points in the triangle.
The first coordinate expresses the distance of the point to the side on the bottom,
the second coordinate is the distance to the upper right side,
and the third coordinate is the distance to the upper left side.
The core for n=10 and m=4 is the shaded area in the figure. The requirements a ≥ 2, b ≥ 10/3, c ≥ 2/3 mean that the points must be beyond the green lines, and the requirements a+b ≥ 20/3, a+c ≥ 3, b+c ≥ 5 are visualized by the blue straight line borders.
The core is usually not one distribution, but many possible ones, but it could even contain no triple in some cases. Another concept that always gives a unique value is the so-called Shapley value. Assume that the grand coalition is build gradually, let's say Ann starts, then Beth joins to form a coalition with Ann, and then Cindy joins to form the grand coalition. Now assume that every player when joining the present coalition is promised the surplus the coalition gets due to this joined player. That means that Ann starts with an expectation of 2. When Beth joins, the expectation of the coalition raises to 20/3, therefore Beth brings 14/3 on the desk. Finally, when Cindy joins, the expectation raises to 10, therefore Cindy claims the difference of 10/3 for herself.
This procedure is certainly not fair. When Beth would start, and Ann would join, Ann could claim a surplus of 10/3 instead of the 2 she gets when starting the coalition. For this reason, the procedure described is performed for every possible ordering of the players, and then the average of the values for a player over all orderings is taken. In our case of three players there are six possible orderings, and the claims for the players for the orderings are shown in the table below:
| Ann starts with 2 | Beth adds 14/3 | Cindy adds missing 10/3 |
| Ann starts with 2 | Cindy adds 1 | Beth adds missing 7 |
| Beth starts with 10/3 | Ann adds 10/3 | Cindy adds missing 10/3 |
| Beth starts with 10/3 | Cindy adds 5/3 | Ann adds missing 5 |
| Cindy starts with 2/3 | Ann adds 7/3 | Beth adds missing 7 |
| Cindy starts with 2/3 | Beth adds 13/3 | Ann adds missing 5 |
The averages of these values, the Shapley values are 3.28 for Ann, 4.94 for Beth, and 1.78 for Cindy. This point is the black dot in the Figure above. In our case, it sits rather central inside the core. But this is not always the case.
Besides this intuitive description of the Shapley value, it can also be shown that this value has a number of desirable properties.