Prerequisites: Chapters 1, 2, and 8.
In Lugano, the hometown of our College, there are two competing shuttle companies serving the airport in Milano-Malpenso, which is about 1 hour 15 minutes away. Of course they have different schedules, and nowadays they have slightly different starting points, but for years they were both starting in front of the railway station. Often, the shuttle from company A was supposed to leave just briefly before the shuttle from company B, and I couldn't help but wondering how many, or rather few, customers would really take this shuttle from company B. Probably only those few who arrive at the railway station in the short time interval after shuttle A leaves and before shuttle B leaves.
It is rather obvious that the schedule, in relation to the schedule of the other company, matters, and the more general question we address in this chapter is how this schedule should look like.
Let's concentrate on the part of driving from the city to the airport first. Of course, eventually these shuttles will also pick up passengers at the airport for the ride back to the city. This will be dealt with in section 1.2, whereas in section 1.3 we will combine both.
Note that this game is almost, but not totally zero-sum. There may be some passengers that don't find a shuttle, either since they have to leave for the airport earlier than the earliest shuttle, or since they have to leave four hours or more later than the latest shuttle leaves, and don't take a shuttle for that reason.
Take as example a=4 and b=23, in other words, passengers have to leave from 4:00 until 23:00 Assume further that Ann's shuttle leaves at 6:00, 10:00, 14:00, and 18:00, and Beth's shuttle leaves at 7:00, 11:00, 15:00, and 19:00. The following table displays the choices the 8 passengers at that time make---"A" for using Ann's shuttle, "B" for using Beth's, and "-" for using none.
| 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 |
| - | - | A | B | B | B | A | B | B | B | A | B | B | B | A | B | B | B | B | - |
Then Ann's shuttle leaving at 6:00 will have 8 passengers on board, and the same with Ann's shuttles at 10:00, 14:00, and 18:00. On the other hand, each of Beth's four shuttle journeys will have 24 passengers except the last, which will even transport 32 passengers. For simplicity let's assume that both shuttles are large buses, so that a shuttle must never leave passengers behind. Therefore Ann will transport 32 passengers, and Beth 104 passengers.
If we do this analysis for all possible pairs of start times for Ann's and Beth's shuttles, we get the following Normal form: There is an Excel sheet computing these values automatically.
| The bimatrix for a=4, b=23, passengers leaving between 4:00 and 23:00. | ||||
| 6,10,14,18 | 7,11,15,19 | 8,12,16,20 | 9,13,17,21 | 6,10,14,18 | 64, 64 | 32, 104 | 64, 80 | 96, 48 | 7,11,15,19 | 104, 32 | 64, 64 | 32, 104 | 64, 72 | 8,12,16,20 | 80, 64 | 104, 32 | 64, 64 | 32, 96 | 9,13,17,21 | 48, 96 | 72, 64 | 96, 32 | 60, 60 |
Let us abbreviate the move "6,10,14,18" by "M6", and so on. None of these moves is dominated. The Maximin move for both players is M9, expecting a minimum payoff of 48. If both players would play their Maximin move, both would get a payoff of 60. But this schedule would also minimize the number of passengers transported. All the 24 persons who have to leave at 6:00 or at 7:00 or at 8:00 would need other transportation.
The symmetric best response digraph is cyclic: The best response to M6 is M7, the best response to M7 is M8, the best response to M8 is M9, and the best response to M9 is M6. It is best to start one hour later than your opponent. That implies that there is no Nash equilibrium in pure strategies.
Therefore we should look for mixed Nash equilibria. Let us define three mixed strategies:
We claim that Mix1 versus Mix1 is a symmetric Nash equilibrium, and that Mix2 versus Mix3 are also Nash equilibria. Although finding them is at the moment a little beyond what we are supposed to do, at least checking the "Nashness" can be done in a rather straightforward way. We add these three mixed strategies to our pure strategies matrix:
| M6 | M7 | M8 | M9 | Mix1 | Mix2 | Mix3 | M6 | 64, 64 | 32, 104 | 64, 80 | 96, 48 | 66.7, 72 | 66.1, 70 | 65.9, 74.4 | M7 | 104, 32 | 64, 64 | 32, 104 | 64, 72 | 66.7, 67 | 69.8, 66.2 | 63.8, 68.5 | M8 | 80, 64 | 104, 32 | 64, 64 | 32, 96 | 66.7, 66.7 | 69.8, 66.1 | 65.9, 65.9 | M9 | 48, 96 | 72, 64 | 96, 32 | 60, 60 | 66.7, 63.7 | 69.8, 65.6 | 65.9, 61.7 | Mix1 | 72, 66.7 | 67, 66.7 | 66.7, 66.7 | 63.7, 66.7 | 66.7, 66.7 | 69.1, 66.7 | 65.3, 66.7 | Mix2 | 70, 66.1 | 66.2, 69.8 | 66.1, 69.8 | 65.6, 69.8 | 66.7, 69.1 | 68, 68 | 65.9, 69.8 | Mix3 | 74.4, 65.9 | 68.5, 63.8 | 65.9, 65.9 | 61.7, 65.9 | 66.7, 65.3 | 69.8, 65.9 | 64.9, 64.9 |
The symmetric best response digraph is shown to the right. Obviously Mix1 versus Mix1 and
Mix2 versus Mix3 are Nash equilibria.
Both players get a payoff of 12864/193=65.66 in the Mix1 versus Mix1 case. In the other two Nash equilibria there is essentially a mix of M6 and M8 versus a mix of M7 and M9. The player playing Mix2 gets an expected payoff of 9024/137=65.87, and the other player gets an expected payoff of 768/11=69.82%.
The payoffs of the three Nash equilibria are shown in the graph to the right.
If no communication is allowed between the players, then this game is difficult for both players, since it requires a certain amount of coordination between them in order to get a high payoff. If communication is allowed before the game starts, then the two players could agree to play one of the three Nash equilibria, whose payoff is shown in the graph. Which one would they agree upon? Without enforceable contracts and side-payments, probably the most likely outcome of the negotiation, the one considered fair by both players, would be the symmetric Nash equilibrium, since it is, as a symmetric one, rather focal. Both players could also expect a higher payoff as the 60 they would get if both play their Maximin move.
Would they obey the pre-game agreement? The answer obviously is: Yes. Remember that Nash equilibria are self-enforcing. If one player deviates, this player would make less or equal to what he or she would make by sticking to the agreement provided the other player obeys the agreement. Now remember that all these mixed Nash equilibria require both players to mix strategies with given probabilities. Since you couldn't even check whether the other players kept their promises--- except in cases where they would play some move with probability 0 in their agreed mixed strategy, they could always explain the outcome by (bad) luck, wouldn't that invite cheating? No---check on the bimatrix to assure yourself that a player deviating and playing any pure strategy cannot improve expected payoffs.
Note also that no pure strategies pair could serve as outcome of pregame negotiations. One player would always be tempted to deviate from such an agreement.
If we take the same start time c=a=4 and end time d=b=23 for passengers as in the analysis to the airport, we arrive at the following bimatrix: Again the Excel sheet can be used to compute this matrix.
| 7,11,15,19 | 8,12,16,20 | 9,13,17,21 | 10,14,18,22 | 7,11,15,19 | 64, 64 | 104, 32 | 80, 64 | 56, 96 | 8,12,16,20 | 32, 104 | 64, 64 | 104, 32 | 80, 64 | 9,13,17,21 | 64, 80 | 32, 104 | 64, 64 | 104, 32 | 10,14,18,22 | 96, 56 | 64, 80 | 32, 104 | 64, 64 |
This game has only one Nash equilibrium. It is symmetric and in mixed strategies. Both players use a mix of 17/33=52% of "7,11,15,19", 4/11=36% of "9,13,17,21", and 4/33=12% of "10,14,18,22", and get a payoff of 2272/33=68.85.
When to go to and from the airport are not independent decisions. If only one shuttle bus is to be used by a shuttle company, then it can not use the same time to leave from the city and from the airport. If we assume that the tour takes more than 1 hour, then even the combination of having a difference of 1 hour between leaving city and airport is impossible. Then there are only three possibilities:
Let us abbreviate these three moves by "6|8", "7|9", and "8|10". Although it is advantageous to go to the airport exactly one hour after the other shuttle does (since you collect three rounds of passengers, and the other shuttle only one), it is exactly the opposite for going back. For going back, it would be best to leave one hour before the other shuttle. So if you are forced to keep a regular pattern, any advantage you get for starting one hour later than the other in the city will be balanced by a disadvantage when coming back of almost equal weight.
For instance, if customers need the shuttle from 4:00 to 23:00 both ways, then the payoffs for both shuttle companies are equal in all occurring outcomes:
| 6|8 | 7|9 | 8|10 | 6|8 | 128, 128 | 136, 136 | 144, 144 | 7|9 | 136, 136 | 128, 128 | 136, 136 | 8|10 | 144, 144 | 136, 136 | 128, 128 |
Still they are different, so it is still worthwhile to analyze the game. We have five Nash equilibria, two pure ones of "6|8" versus "8|10" with payoff of 144 for both, and three mixed ones: 50% "6|8" and 50% "8|10" versus the same strategy, or versus the pure strategy "7|9". In each of these three mixed Nash equilibira, the payoffs for both players are 136.
Just to discuss a random example, assume that a=6 and b=20, the earliest passengers want to go to the airport at 6:00 and the latest at 20:00, and assume c=7 and d=21, the earliest passengers want to come from the airport at 7, and the latest at 21:00. Again the bimatrix can be computed on the Excel sheet.
| 6|8 | 7|9 | 8|10 | 6|8 | 83.5, 83.5 | 107, 107 | 120, 105 | 7|9 | 107, 107 | 83.5, 83.5 | 112, 92 | 8|10 | 105, 120 | 92, 112 | 77, 77 |
Although for the customers, the combination "6|8"-"8|10" would be best,
since with this combination 225 of 240 possible passengers would be transported,
this combination is not a Nash equilibrium. The player playing "8|10" would want to change to
"7|9". Actually there are five Nash equilibria, the two pure ones
"6|8" versus "7|9" with a payoff of 107 for both, and three mixed ones.
The two pure ones have also the highest number of passengers transported (214) of all Nash equilibria,
so maybe the authority should suggest this to both companies to make it a focal point.
Note also that although the payoffs are equal, the equilibria themselves are not symmetric,
so again pregame negotiations are necessary to talk about who will start at 6:00 and who at 7:00.