Restaurant Location Games

Prerequisites: Chapters 1, and 2.

As in in the doctor location games page we discuss games on graphs. Here the most interesting features are existence or nonexistence of pure Nash equilibria. The corresponding sequential versions will be discussed later.

• 1. A first Graph (Graph 6)
• 2. A second Graph (Graph 1)
• 3. Weights
• 4. Existence of pure Nash Equilibria
• 5. More than one restaurant

Let us briefly repeat the definition of an undirected graph, given in the sibling chapter. Undirected graphs have vertices, displayed by small circles. Some pairs of vertices are connected by undirected edges. They are visualized by curves connecting the two vertices. Vertices connected by an edge are called adjacent.

As in the doctor location chapter we use graphs for modeling islands. The vertices represent the villages, and the edges the roads between the villages.

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. Actually, if the graph is large enough, then this is probably what would happen. The restaurants would find their own niches far apart, and there would not be much competition between them. This is different to what happens in the doctor location game. The game gets more interesting if the graph is smaller, and there must be some competition between the restaurants.

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 the restaurant location model we consider here, we will see that the invisible hand works at least for the examples we look at.

Let me explain how the payoffs are computed in these three cases where the restaurants are placed in the same village, or in adjacent villages, or farer apart.. 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. Remember that we are still playing a simultaneous game, all location decisions are made simultanously by the two players. It is not at all obvious how to handle ties, for instance where one vertex is adjacent to one of Ann's restaurants and two of Beth's restaurants. Half of the population of that village go to a restaurant, but will one third of them go to Ann's restaurnt and two thirds to Beth's restaurants? Or. and this is the point of view we take, does half of them go to Ann's restaurant, and half to Beth's restaurants? This point of view could be justifies if the population has a very slight bias, half of them towards Ann's and the other half towards Beth's restaurants, so slight that they always go to the closer one no matter what brand, but in case of a tie of distance, they go to their preferred brand.

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

To the right is part 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
   ...