Some Location Games

Prerequisites: Chapters 1, and 2.

In this chapter we discuss the simultaneous versions of different location games played on undirected graphs. We discuss two different games, one where two doctors have to choose their location, and one where two different restaurant chains choose locations for their restaurants. Depending on the underlying graphs, on the number of locations to choose we get rather different versions. but we will see that all these games share some interesting features, like existence of pure Nash equilibria. The corresponding sequential versions will be discussed later.

• 1. Doctor Location
  • 1.1 More than one location
  • 1.2 Geometric Version
• 2. Restaurant Location
  • 2.1 A first Graph (Graph 6)
  • 2.2 A second Graph (Graph 1)
  • 2.3 Weights
  • 2.4 Existence of pure Nash Equilibria
  • 2.5 More than one restaurant
• References
• Exercises and Projects

Like a digraph, an undirected graph consists of vertices. But instead of being connected by arcs with directions, some pairs of vertices are connected by edges which don't have a direction and 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 islands. 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 1, Graph 2, Graph 3, Graph 4, Graph 5, Graph 6

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. These features of the games allow us already to derive the following condition for pure Nash equilibria:

Note that this theorem does not say that those outcomes where both players get equal payoff are Nash equilibria. And although there are, under the condition mentioned above, always such outcomes---all outcomes where both players make identical choices--- there may not even be a pure 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.

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 negative of the sum of all lengths of the paths to the nearest doctor could be considered to be the payoff for the island society. Obviously letting the two doctors choose their location freely does not necessarily minimize this sum of path lengths, and therefore does not maximize society's payoff, as can be seen by the rather ridiculous choice of 1 versus 1. The sum of all path lengths to the nearest doctor is 9 here, whereas in the Nash equilibrium of 2 versus 5, this sum is as low as 5.

...

Play the game here. ...

Adam Smith coined the phrase "the invisible hand" in his book "The Wealth of Nation". This phrase stands for the claim that, if government allows the different agents to act freely, almost magically a solution best for the whole society will occur. Of course, nowadays we know that some mechanisms work like this and others don't. We have just seen in the previous section that letting doctors choose their location does not necessarily result in a solution desirable for the villagers. In this section we look at a differen model, where the invisible hand might work.

Play the game here on Graph 1, Graph 2, Graph 6, Graph 8, Graph 9, or Graph 10.

Different to the doctor version, the restaurant version is not a constant-sum game, since the total number of customers varies. If both restaurants are placed far apart, the total number of customers would normally be higher than if the restaurants are located in adjacent villages, or even in the same village. Let me explain how the payoffs are computed in these three cases. It turns out that they only depend on three quantities namely the number d(x) of neighbors of vertex x, the number d(y) of neighbors of y, and the number n(x,y) of common neighbors of the vertices x and y, where x and y are the locations of Ann's and Beth's restaurants.

• If both Ann's and Beth's restaurant are placed in the same village x, then they share these villagers as customers. In addition, they share the villagers of the adjacent villages every two years, meaning they share half the sum of the sizes of all adjacent villages each year. Therefore each restaurant can expect 1/2+(1/4)·d(x) villages as customers per year.
• If the restaurants are placed in different nonadjacent villages x and y, then x contributes 1 to Ann's payoff, each one of the n(x,y) common neighbors of x and y adds 1/4, and each one of the d(x)-n(x,y) other neighbors of x contributes 1/2 to Ann's payoff. Thus Ann's payoff equals 1+(1/2)·(d(x)-n(x,y))+(1/4)·n(x,y) = 1+(1/2)·d(x)-(1/4)·n(x,y) and Beth's payoff is 1+(1/2)·(d(y)-n(x,y))+(1/4)·n(x,y) = 1+(1/2)·d(y)-(1/4)·n(x,y)
• If the restaurants are placed in different but adjacent villages x and y, then Ann gets 1 from x, 1/4 from each one of the n(x,y) villages adjacent to both x and y, and 1/2 from each other neighbor of x except y. Therefore Ann's payoff equals 1+(1/2)·(d(x)-1-n(x,y))+(1/4)·n(x,y) = (1/2)+(1/2)·d(x)-(1/4)·n(x,y) and Beth's payoff equals 1+(1/2)·(d(y)-1-n(x,y))+(1/4)·n(x,y) = (1/2)+(1/2)·d(y)-(1/4)·n(x,y)

Doing all these computations, we arrive at the following payoff bimatrix:

	1	2	3	4	5	6	7
1	5/4, 5/4	7/4, 7/4	7/4, 7/4	2, 3/2	2, 2	9/4, 7/4	9/4, 7/4
2	7/4, 7/4	5/4, 5/4	7/4, 7/4	9/4, 7/4	9/4, 9/4	9/4, 7/4	2, 3/2
3	7/4, 7/4	7/4, 7/4	5/4, 5/4	2, 3/2	2, 2	5/2, 2	9/4, 7/4
4	3/2, 2	7/4, 9/4	3/2, 2	1, 1	3/2, 2	7/4, 7/4	2, 2
5	2, 2	9/4, 9/4	2, 2	2, 3/2	5/4, 5/4	2, 3/2	9/4, 7/4
6	7/4, 9/4	7/4, 9/4	2, 5/2	7/4, 7/4	3/2, 2	1, 1	3/2, 3/2
7	7/4, 9/4	3/2, 2	7/4, 9/4	2, 2	7/4, 9/4	3/2, 3/2	1, 1

The Maximin moves for both players are 1, 2, 3, and 5, exactly the vertices with three neighbors. The Security Level achieved by these moves is 5/4.

There are four Nash equilibria, which are shaded in the table. Two of them are shown below, the other two are obtained by interchanging Ann's and Beth's move.

For these graph they are the only outcomes where every village is adjacent to some restaurant, but of course this is not true in general. Still it may seem that the Nash equlibria are also good for the society insofar as they give a distribution that reaches as many people as possible. In the example, the four Nash equilibria are the only outcomes where the sum of the payoffs reaches the maximum occuring value of 9/2. Are these observations true in general?

Play the game here on Graph 1.

	1	2	3	4	5	6	7
1	5/4, 5/4	7/4, 7/4	2, 2	2, 2	7/4, 9/4	2, 2	9/4, 9/4
2	7/4, 7/4	5/4, 5/4	9/4, 9/4	2, 2	7/4, 9/4	2, 2	2, 2
3	2, 2	9/4, 9/4	5/4, 5/4	2, 2	7/4, 9/4	2, 2	2, 2
4	2, 2	2, 2	2, 2	5/4, 5/4	2, 5/2	7/4, 7/4	2, 2
5	9/4, 7/4	9/4, 7/4	9/4, 7/4	5/2, 2	3/2, 3/2	5/2, 2	9/4, 7/4
6	2, 2	2, 2	2, 2	7/4, 7/4	2, 5/2	5/4, 5/4	2, 2
7	9/4, 9/4	2, 2	2, 2	2, 2	7/4, 9/4	2, 2	5/4, 5/4

This game has eight pure Nash equilibria, colored in the bimatrix above. Again four of them are shown below, the other four are just obtained by interchanging the moves of the players.

The conjecture about the Nash equilibria being the only outcomes maximizing the sum of the payoffs of the two players (and thereby also maximizing the number of villagers reached) is also true in this example.

Variants of the games are obtained by considering graphs with different weights of the vertices--- meaning that the villages have no longer equal but varying population. In Graph 3, for instance, vertices 4, 7, and 10 have double weight.

• if x=y, both get the payoff of w(x)/2+d(x)/4.
• if x and y are different and nonadjacent, then Ann's payoff equals w(x) + d(x)/2-n(x,y)/4, and Beth's payoff is w(y)+d(y)/2-n(x,y)/4.
• if x and y are different and adjacent, then Ann's payoff equals w(x)+(1/2)·(d(x)-w(y)-n(x,y))+(1/4)·n(x,y) = w(x)+d(x)/2-w(y)/2-n(x,y)/4, and Beth's payoff equals w(y)+d(y)/2-w(x)/2-n(x,y)/4.

Every one-restaurant location game, even when played with weights, has the following properties:

• For every option x there is some value f(x), and
• for all pairs of options x and y there is some value g(x,y) = g(y,x), such that
• if Ann chooses option x and Beth option y, then Ann's payoff equals A(x,y) = f(x)-g(x,y) and Beth's payoff B(x,y) = f(y)-g(x,y).

In the restaurant location game with one restaurant to choose for each player, f(x) is the payoff Ann would get from the restaurant in x in the absence of Beth. using the notations d(x) and n(x,y) described above, f(x)=w(x)+d(x)/2. The symmetric value g(x,y)=g(y,x) is the amount that has to be subtracted form this ideal maximum possible payoff f(x) when placing at x, due to the sharing of some possible customers. It equals

• g(x,x)= w(x)/2+d(x)/4
• g(x,y)= n(x,y)/4 if x and y are distinct and nonadjacent.
• g(x,y)= w(y)/2 + n(x,y)/4 if x and y are distinct and adjacent.

We could also play variants where two restaurant chains place not only one but several restaurants each. The

Let us discuss what can happen at the example of Graph 10. ..........

To the right is parth of the condensed best response digraph. Obviously dominated moves, like placing both restaurant in the same village, are eliminated, Furthermore all moves that are not best responses of another move are eliminated. Those moves that are not best response of a best response of a best reponse ... of a move, with arbitrary length of this sequence, are displayed in light bold. In the remaining part, many cycles can be observed, but no cycles of length 2 or 1, thus there is no pure Nash equilibrium.

More links

• ...

Exercises

1. ...
   
   Show/Hide solution
   ...........
2. ...
   
   Show/Hide solution
   ...
3. .....
   
   Show/Hide solution
   ...
4. .....
   
   Show/Hide solution
   ...
5. .....
   
   Show/Hide solution
   ...

Projects

1. Project: RESEARCH: Compute all Nash equilibria of the Restaurant Location Game for several graphs, and test whether they all maximize the sum of the payoffs of the two players.
   If it is true for all examples, does it make the general conjecture any truer? And what if it is not true for some example?
   
   
   Show/Hide solution
   ...
2. .....
   
   Show/Hide solution
   ...
3. .....
   
   Show/Hide solution
   ...
4. .....
   
   Show/Hide solution
   ...
5. .....
   
   Show/Hide solution
   ...