Game Theory through Examples

You have two lovely daughters, Ann and Beth. A friend gave you a few presents for them. You don't know how much each of these presents means to each of your daughters, but you want to be fair, and you want them to be as happy as possible. How would you distribute these items to them.

Depending on the number of presents, we get different problems. We will discuss the cases of 5 or 6 presents.

We assume first that the two daughters are so close to each other that they can also estimate the value of each item to their sister. The much more complicated "incomplete information" situation where this is not the case is briefly discussed in a later chapter.

Of course you could just distribute the items yourself. Since you don't have a clue about the values of the items to each of your daughters, it may seem fairest if you give each about the same number of items. Even though the procedure seems fair enough, the particular outcome may not be "fair" in the sense that one daughter may be (much) happier with your choice than the other. But the more obvious disadvantage of this method is that it is not very efficient---the items are distributed without considering their values to Ann and Beth. Since you don't know these values, but Ann and Beth do, they should get involved in the distribution process. This will assure that every daughter only gets items that are valuable to her.

You could ask Ann and Beth which items they prefer. But would they tell you the truth, or rather lie tactically? So maybe, instead of just asking them, you will set up a procedure to select the items in which Ann and Beth are involved. But you have to decide about the rules of this choice process, the "game". So your task here is not to play the game successfully---this is the task for Ann and Beth. Your task is rather to design a game that is "good" in a sense that will be explained in Section 1.

In this chapter, after discussing the goals of fairness and efficiency in the first section, we will present three families of simple possible games in the second section. In the newx two sections we compare them for 5 or 6 items, using simulations for different assumptions on the distribution of the values.

1. Goals of Fairness and Efficiency

1.1 The measurement scales of the values

We assume that the values for the items are on a ratio scale, and that the total utility for a player is just the sum of her values of all the items she gets. There are no two items that only make sense together, like left and right shoe, and no item is lowering the worth of another item. Both these assumptions are rather strong.

1.2 What is a fair distribution?

The next question is whether the values Ann and Beth assign to the items are comparable.

Let us use the following example:

values	D	E	F	G	H	I
Ann	6	62	48	58	26	4
Beth	71	81	72	39	98	17

In this example, Ann doesn't seem to value the items much. For each item except item G, Beth assigns a higher value than Ann. Should we maximize the sum of both their values and give all items except item G to the more grateful Beth? Or in the name of fairness, should we still give a few items to the more reserved Ann?

The answer to this question depends on whether the values are something absolute, or just subjective for each player. In the first case, which we call interpersonal comparability of values, yes, giving all items except G to Beth would be probably wise. But in the second case, we may want to make the decision that the sum of all items may have the same value for both players. Then we should use relative values, defined as the ratio of individual value of the item, diveded by the sum of all that player's values of all items. This is the approach we take in this Chapter.

In the example above, the sum of all values of the items for Ann equals 204, and the sum of all values of the items for Beth is 378. Therefore the relative values are:

values	D	E	F	G	H	I
Ann	6/204=3%	62/204=30%	48/204=24%	58/204=28%	26/204=13%	4/204=2%
Beth	71/378=19%	81/378=21%	72/378=19%	39/378=10%	98/378=26%	17/378=4%

Let us call the sum of Ann's relative values of the item she gets Ann's satisfaction, and the sum of Beth's relative values of the item Beth gets Beth's satisfaction. This leads to our first concept of fairness: An outcome is fairest if both players achieve the same satisfaction.

Now assume Ann and Beth played the game (with different items but always the same roles in the game) 100 times, and in 50 cases Ann won 85% and Beth 25% as relative values, and in the other 50 cases Ann won 25% and Beth 85%. What about the fairness? Overall the game doesn't favor any of the two player roles. Still you might feel a little uncomfortable using this game for your two daughters, since you know that one will be rather satisfied, and the other won't, and that will result in a fight. This can be expressed by saying that the average absolute value of the difference between the two relative values is 60%, which may be considered too high.

1.3 What is an efficient distribution?

It is easier to describe inefficiency: Distributions where Ann gets the three items she prefers least, and Beth also gets the three items she prefers least would obviously be very inefficient, since it is Pareto-dominated: By exchanging their items, both players would be able to increase their total value, which is, as mentioned above, supposed to be the sum of their values attached to the items they receive. Thus our first requirement for efficiency is that the outcome of such a distribution game should not lead to a Pareto-dominated outcome.

If we go beyond this requirement, in case of interpersonal comparability of values, we could just look at the sum of both players' values of the items obtained, i.e. the sum of Ann's and Beth's satisfaction. But this value is still not meaningful enough, since it depends on the data---the values both players attach to the items. If both preferences are close, we may always get the sum of Ann's and Beth's satisfaction not much higher than 100%, for instance. Therefore we define:

Actually this maximum possible sum of satisfactions is very easy to compute provided we know the values Ann and Beth attach to the items, which, remember, we usually don't know. But of course, to test our games, we look at examples where we know them. Each item goes to that player that attaches the higher relative value to it.

In the example above, under our assumption of interpersonal non-comparability, Ann should get items E, F, and G, with relative values 30%, 24%, and 28%, and Beth should get items D, H, and I with relative values 19%, 26%, and 4%. Ann's satisfactions is 82%, and Beth's satisfaction is 49%. The sum of both these satisfactions is 132%. This is the "Santa Claus" value against which those values from other distributions have to be compared.

1.4 Three additional features

We will mainly concentrate on inequity and inefficiency, but in the literature there are many more features measuring fairness and efficiency of an otcome.

2. Choosing-one-by-one Games

Starting with Ann, both alternate of selecting one item until all are chosen. If there are 6 items, we call the game ABABAB, for five items ABABA , and so on.

For instance, ABBABA is a game with 6 items where first Ann chooses one item, then Beth chooses two, then Ann chooses one, then Beth one, and finally Ann takes the remaining one. In the same way the games ABBAAB could be defined for 6 items, and the games ABBAB, ABBAA, and ABABB for five items.

2.1 Greedy strategy

Isn't the way how to play these games rather obvious? Wouldn't each player just the choose the most valuable remaining item(s) whenever she is to move? Let's call this strategy the "greedy" one. Try it yourself in this applet for 6 items, or in this applet for 5 items. Make frequent use of the "hint" button, and compare what you get if you follow the advice to the other case---you can just play the game several times iwth the same data.

There are situations where the greedy strategy is not best, and rational players would not play it. For instance, assume "ABABAB" is played, three items, D, E, F are left with values of a(D), a(E), a(F) for Ann and b(D), b(E), b(F) for Beth. ............................

2.2 Backwards Induction

Let us now focus for a moment on the number of moves. Taking the last remaining item is not considered a move, since there is no choice. Thus ABABAB is a five-move game, ABBABA a four-move game, and ABBAAB a three-move game. As we face sequential games with perfect information, the right way to analyze these games is backwards induction using extensive form.

As a slight digression, let us now compute the number of states in some of these games in the game tree or in the game digraph. Let us start with the game trees:

Once this positions have been generated, the arcs are rather obvious. For instance, in "ABBAAB" there is an arc from position "D/HI" to "DE/FHI" (and thus to "DEG/FHI") but not to "DE/FGI" (meaning "DEH/FGI"), since items are not taken back.

Note that this kind of reasoning requires that the players know the other player's values of the items. Wouldn' then without that requirement, in cases of incomplete information, the greedy strategy be best? It depends on what the players believe about the other players preferences, as we will discuss in a later chapter.

2.3 An abbreviated analysis

In our example introduced above, Ann and Beth playing just their greedy strategies would mean

Ann would first choose E with value 31,
then Beth would choose H with value 98,
then Ann would choose G with value 29,
then Beth would choose F with value 72,
then Ann would choose D with value 3,
and finally Beth would take the remaining I with value 17.

In this way, Ann would get a total value of 126 out of a possible 204 (62%), and Beth would get a total value of of 187 out of possible 378 (49%).

values	D	E	F	G	H	I
Ann	6 6	62 62	48 48	58 58	26 26	4 4
Beth	71 71	81 81	72 72	39 39	98 98	17 17

But actually Ann and Beth would deviate from their greedy strategies and, according to backward induction analysis, play as follows:

Ann first could choose either E or F, let's assume she chooses E.

In the second round, Beth could choose either D, H, or I, let's assume she chooses H.
Then Ann chooses F, not G, since she will get G later anyway, since it has such a low value for Beth.
Next Beth chooses D or I.
Next Ann chooses G in both cases,
and Beth takes the remaining item, I or D.

Note that the game, in this example, results in the most efficient outcome where Ann gets a total of 168 (a relative value of 82%) and Beth a total value of 186 (49%).

3. More Games

3.2. Cut and Choose

This game is well-known for dividing something that can be divided continuously, like a pizza or a cake. Ann cuts the pizza into two parts, and Beth chooses whatever part she wants, Ann has to take the remaining part. Our discrete version is as follows:

CUT AND CHOOSE: First Ann divides the six items into two heaps. Then Beth decides which heap she wants, and Ann gets the remaining heap.

This is a sequential game with two moves, perfect information, and no randomness. Since there are 2⁶=64 possible heaps, there are 64/2=32 ways of dividing the six items into two heaps. Ann has 32 possible moves, and Beth has two moves in each of the 32 positions she may find herself. The game is modeled in this Excel sheet.

Often the game is praised for being "fair" in the sense that nobody can really complain. At least in the continuous version, everybody gets at least 50% of the value the total pizza has for him- or herself. We will see below that this is no longer true for the discrete version---Ann can very well get less than 50%, although it is not very likely that she gets much less. On the other hand, Beth never gets less than 50%. Whereas this looks unfair to Ann, on closer inspection the game is tilted in favor of Ann (under some assumptions on the distribution of the values to the items). Below we will also analyze this advantage for Ann.

values	D	E	F	G	H	I
Ann	6	62	48	58	26	4
Beth	71	81	72	39	98	17

Ann would put D, F, and H into one heap, and E, G, I into the other. Beth would prefer and take the D-F-H heap, with a total value of 71+72+98=241 for Beth. This is a relative value of 241/378=64%. The total value of the remaining E-G-I heap for Ann is 62+58+4=124, or 124/204=61% relative value. The sum of both these relative values is only 125%, compared with 132% for game ABABAB.

3.2. Random and Exchange

We start by giving Ann and Beth both three items randomly. Then there are some rounds of exchanges played by Ann and Beth. Of course, they would only exchange one item against another one if both profit. There is a great variety of possible rules of these exchanges, we consider here the following:

RANDOM&EXCHANGE2: Each player gets three items randomly. Then Ann tells Beth which one of Beth's items she would like to have. Beth tells Ann which one of Ann's items she would like to have in exchange for that. If both agree with the deal, the two items are exchanged. Then a second round of possible exchanges fowllows, this time Beth proposing one of Ann's items first, followed by Ann proposing one of Beth's items, again followed by an exchange of these items if both agree.

4. Comparison of the games with 6 items

We will not be able to measure fairness and efficiency of the result obtained by the game you have chosen in the concrete example. We simply don't know the values Ann and Beth attach to the six items. But what we can do is testing the different games on given data, and computing efficiency and fairness there.

4.1 Worst Case

One of them getting less than 50%

Assume item 1 has a value of 100 to both players, and the other five are peanuts, having value of 1 each. The player not ending with this valuable item will never get more than 5% of the total value of all items (which is in this example 105) to her. Therefore no mechanism can guarantee that both players achieve some level, say 30% of what would be achievable. This result is different in continuous examples, like sharing a pizza using cut and choose. In the continuous case, it is possible to show that both Ann and Beth will end having at least 50% satisfaction.

What if the values of the items (for Ann) are more evenly distributed? Assume that the highest value of an item for Ann is not more than k times the lowest value of an item for Ann. ............

4.2 Average Case in Simulations

We simulated 2000 random distributions, where the 12 values of the items for Ann and Beth are independent random numbers with uniform distribution between 0 and 1. You can do this yourself in Excel sheet "..........xls". The graph on the right displays the results for the different methods, where "fairness" ........, and "efficiency" denotes the average difference between optimal sum of both relativie utilities, and the sum of both relative values achieved by the game in question. CUT&CHOOSE is the most effiecient game under these conditions, whereas both ABBABA and RANDOM&EXCHANGE2 are rather fair.

Parallel Preferences

The next question is: What happens if the preferences of Ann and Beth are somewhat similar? This is a rather reasonable assumption. Again we generated 12 independent random numbers a₁, ... a₆, b₁, ... b₆. Then in the first model, called "parallel preferences", Ann's value for items D, E, F, ... are a₁, 2*a₂, 3*a₃, ... and in the same way Beth's values are b₁, 2*b₂, 3*b₃, ... . In the other model, called "very parallel preferences", Ann's value for items D, E, F, ... are a₁, 0.5+a₂, 1+a₃, ... and in the same way Beth's values are b₁, 0.5+₂, 1+b₃, ... . This second model is stronger, since both Ann and Beth never prefer D over F, for instance, or E over G.

CUT&CHOOSE is still the most efficient game, and it is even rather fair provided the preferences are very parallel. This is easy to explain---in this case, the game is almost zero-sum, and both players get relative values close to 50%.

Opposing Preferences

The picture changes drastically for opposing preferences, complementing each other. Again we create 12 independent random numbers a₁, ... a₆, b₁, ... b₆, uniformly distributed between 0 and 1. Then Ann's value for items D, E, F, ... I are a₁, 2*a₂, ... 6*a₆, but Beth's values are 6*b₁, 5*b₂, ... b₆. The graph to the right shows the results of 2000 more simulations. CUT&CHOOSE now is by far the worst game, both for efficiency and for fairness.

Modified Fairness

Remember that we discussed a different, maybe more realistic fairness concept above. The graphs for this modified fairness concept are shown below. It turns out that methods ABBABA and RANDOM&EXCHANGE2 loose their impressive fairness feature. For parallel or very parallel preferences, CUT&CHOOSE is without serious competition, and in the independent case (the first graph), the fairness advantage of ABBABA and ABBAAB may not be enough to outweigh the efficiency advantage of CUT&CHOOSE. In case of opposing preferences, the four methods different to CUT&CHOOSE are even closer together. Obviously you could choose any game here, except CUT&CHOOSE.

Thus in conclusion, the simulations indicate that we should use the game CUT&CHOOSE except in cases of opposing (complementary) preferences.

n=0, m=0	n=1, m=0	n=1, m=1	n=2, m=1	n=2, m=2	n=3, m=2	n=3, m=3
1	6·1=6	6·5=30	15·4=60	15·6=90	20·3=60	20·1=20

Dividing Few Items I