Prerequisites: Chapters 1, and 2.
In this chapter and its sibling, we discuss the simultaneous versions of different location games played on undirected graphs.
Note to the Teacher:
............
Excel File
Like a digraph, an undirected graph consists of vertices.
But instead of being connected by arcs with directions,
vertices are connected by undirected edges
that can be used both ways.
Usually they are visualized by curves connecting the two vertices.
Vertices connected by an edge are called adjacent.
Note that edges may cross, like in the graph to the right.
There is an edge connecting vertices 4 and 5, and another one connecting
vertices 3 and 6, but none connecting vertices 4 and 6.
Therefore vertices 4 and 6 are not adjacent, nor are vertices 3 and 5.
We use graphs for modeling transportation networks. The vertices represent the villages, and the edges the roads between the villages. Two villages are called adjacent if they are connected by a direct road. Crossings between edges should always be thought as one bridging over the other, therefore it is not possible to change the roads there.
Here you can play the game with different graphs: Graph 2, Graph 4, Graph 5, Graph 6, Graph 8, Graph 11, Graph 15,
Note that the game is a constant-sum game, since each islander goes to one doctor once a year. Thus the sum of the patients of both doctors equals the number of islanders. Note also that constant-sum games behave like zero-sum games---we just have to subtract half of the constant sum from each payoff to get a zero-sum game where both players would still play the same. As has been shown in the Simultaneous Games chapter, these features of the games, 2 players, symmetry, and constant-sum, imply that the payoffs in each Nash equilibrium are equal (half the number of vertices) for each player, and that every maximin move of Ann achieving a guarantee of half the number of vertices versus any such a maximin move for Beth forms a Nash equilibrium.
Continuing in this way, and keeping in mind that the game is symmetric, one can get the whole bimatrix of the game, which looks as follows:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| 1 | 7/2, 7/2 | 7/2, 7/2 | 4, 3 | 9/2, 5/2 | 7/2, 7/2 | 4, 3 | 9/2, 5/2 |
| 2 | 7/2, 7/2 | 7/2, 7/2 | 4, 3 | 4, 3 | 7/2, 7/2 | 4, 3 | 9/2, 5/2 |
| 3 | 3, 4 | 3, 4 | 7/2, 7/2 | 4, 3 | 7/2, 7/2 | 4, 3 | 4, 3 |
| 4 | 5/2, 9/2 | 3, 4 | 3, 4 | 7/2, 7/2 | 5/2, 9/2 | 7/2, 7/2 | 7/2, 7/2 |
| 5 | 7/2, 7/2 | 7/2, 7/2 | 7/2, 7/2 | 9/2, 5/2 | 7/2, 7/2 | 9/2, 5/2 | 4, 3 |
| 6 | 3, 4 | 3, 4 | 3, 4 | 7/2, 7/2 | 5/2, 9/2 | 7/2, 7/2 | 7/2, 7/2 |
| 7 | 5/2, 9/2 | 5/2, 9/2 | 3, 4 | 7/2, 7/2 | 3, 4 | 7/2, 7/2 | 7/2, 7/2 |
The Maximin moves for both players are moves 1, 2, and 5, and the corresponding values, the security levels, are 7/2 for each. Actually the four other moves 3, 4, 6, and 7 are weakly dominated by each of these moves. There are nine pure Nash equilibria, the shaded cells. As noted above, all of them must have payoffs of 7/2 for both players (but not all such fair outcomes, where both get 7/2, are pure Nash equilibria). Note also that every combination of choices of villages 1, 2, or 5 results in a Nash equilibrium.
All the examples above have Nash equilibria, but this isn't necessarily so.
The graph shown below has no (pure) Nash equilibrium.
The villagers of the island are not players of that game, since they don't make decisions. Still there is a payoff for them, having a doctor close to their home or not. The sum of all lengths of all paths from all vertices of the graph to the nearest doctor could be seen as a measure of how good the location of the doctors is to society---the smaller this number, the better. Let's call this number the distance sum, given the doctors locations. Finding a placement of two doctors minimizing the distance sum is tedious but not too difficult---all we have to do is to compute this distance sum for every possible combination. In the graph above, Graph 6, if both doctors go to vertex 1, the distance from vertices 1, 2, 3, ... and so on to the closest doctor (at vertex 1) are 0, 1, 1, 2, 1, 2, and 2. Therefore the distance sum for this placement is 0+1+1+2+1+2+2 = 9. If one doctor is located at vertex 1 and the other at vertex 2, the distance sum equals 0+0+1+2+1+2+1 = 7. If the doctors are located at vertices 2 and 5, the distance sum equals 1+0+1+1+0+1+1=5, which is lowest possible. Obviously letting the two doctors choose their location freely does not necessarily minimize this distance sum, and therefore does not maximize society's payoff.
Now we know that we only need to look for vertices that guarantee half the number of vertices as payoff in order to find all Nash equilibria. Still, is it possible to identify these vertices without performing the calculations but by looking at the structure of the graph? Do we know how many vertices of this type we have? Do we know which graphs have pure Nash equilibria and which one do not?
In this section, we will find answers to these questions for special graphs, namely trees. A tree is a graph where between any pair of vertices there is exactly only path. Examples are the graphs given below.
If we would only have one doctor to place, the good locations minimizing the distance sum are called the "median" and were first investigated by Camille Jordan for trees [Jordan 1869]. See and for the distance sums for the different vertices for our two trees. Thus the medians are vertex 6 in the first tree, and both vertices 6 and 8 for the second one. Note that these medians, the vertices minimizing the distance sum are exactly the vertices for the Maximin moves, the vertices with minimum branch-weight, in these two examples. In fact, Jordan found that the median for trees is always either just one vertex, or two adjacent vertices, and Bohdan Zelinka showed 199 years later that the median of a tree consists of exactly those (one or two) vertices minimizing the branch-weight [Zelinka 1968].
Therefore, the Nash equilibria locations for trees would be perfect for society if there would be only one doctor, but for two doctors, they are almost always suboptimal. Both doctors behave as if they would be the only doctor in the world. This is one of the cases where competition would not lead to a solution best for society. In the first example tree, for instance, both doctors will go to vertex 6. The distance sum for this equals 19. However, if one would go to vertex 2 and the other to vertex 6, the distance sum for these locations would be 9! Surprisingly, in the second tree the Nash equilibrium of vertex 6 against vertex 8 is also optimal for society, since the distance sum equals 15, the same as for locations at vertices 6 and 8, or locations at vertices 6 and 10, or at vertices 4 and 8, or at vertices 4 and 10. But this is mainly due to the tree being so small. For larger trees, the Nash equilibrium location is usually not optimal for society, not minimizing the distance sum.
Here you can play the game with different graphs: Graph 4, Graph 6, Graph 8, Graph 11, Graph 14. An example on a selection and the corresponding payoffs for the example Graph 6 considered before is given to the right.
We still have a symmetric simultaneous 2-player zero-sum game. But the number of options for each player is now much higher than before. If the village graph has n vertices, then each doctor has n options with both her offices placed in the same village. These options are obviously dominated. Then there are n·(n-1)/2 options with both offices in different villages. Together, each doctor has n+n·(n-1)/2 options. For our 7 vertex example Graph 6, this adds to 28 options for each doctor. In the 10-vertex Graph 4, we have 55 options for each doctor, so we are looking at a 55 × 55 matrix.
But we also still have a symmetric 2-player zero-sum game. So we still know that every pair of Maximin moves of the two players yields a pure Nash equilibrium, provided these Maximin moves carry a guaranteed payoff of half the number of vertices. But if the Maximin moves have a lower guaranteed payoff, there is no pure Nash equilibrium.
Another class of graphs that can be analyzed easily are grids like Graph 11 or Graph 15. The Maximin moves are always the vertices in the center of the grid, which is either just one vertex, or two adjacent vertices, or a small square, depending whether the dimensions of the grid are even or odd. If we look at larger and larger grids, we may arrive at a continuous game like the one here. The two players can place their office wverywhere inside a square. Note that distance here is the usual euclidean distance, different to the grid case, where the so-called "Manhattan distance" applies.
Games like this do not quite fit into our framework, since every player has infinitely many moves. Maximin moves and Nash equilibria can no longer be found by simply checking a finite list. Moreover, rather funny things can happen, like no Maximin move, for instance. Usually tools from Calculus are applied to games like this.
However, in our example, it is fairly simple to find the only existing pure Nash equilibrium. Both place their office directly in the middle of the city, since even if Beth knows that Ann is placing her office this way, she can not really exploit this information---her best response would be to place her office also directly in the middle of the city.
Variants with two or more locations for each doctor are also possible: Play the game here. An analysis of the game with more than one office may be very difficult.
Project:Doctor location on MOPS:
A MOP or maximal outerplanar graph
is obtained from a cycle by adding diagonal edges that do not cross each other
until no more edges are possible to draw without crossing.
An example is given to the right.
Can you describe how many Nash equilibria are possible for doctor location games on mops?
Try to start by analyzing a number of small and a little larger examples.