MAT109 · Erich Prisner · Franklin College · 2007-2011

Restaurant Location Games

Prerequisites: Chapters 1, and 2.

As in the previous page we discuss games on graphs. The most interesting feature of these games is that they always have pure Nash equilibria.

  • References
  • Exercises and Projects
    • Note to the Teacher: ............
    Excel File

    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.

    Again we use graphs to model islands. The vertices represent the villages, and the edges the roads between the villages.

    Restaurant Location Game: On a small island, the different villages are connected by a system of streets. Two Sushi restaurants, Ann's and Beth's, are about to open. Both have the same quality and price level, and are almost indistinguishable. Market research shows the following: In the simultaneous version of the game, both Ann and Beth are forced by the island government to simultaneously submit a proposal for the location of their restaurant. We assume that all villages have about the same size. The payoffs for the players are the expected numbers of customers per year. What location should the players choose?

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

    Graph 1: Only one Nash: 5 versus 5.
    Graph 2: Only one Nash: 2 versus 2.
    Graph 4: Everyone of 1,2,3,4 versus everyone of 1,2,3,4.
    Graph 5:

    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 the restaurants might 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, in which case some competition between the restaurants is unavoidable.

    Adam Smith coined the phrase "the invisible hand" in his book "The Wealth of Nations". 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 seen in the Doctor Location Chapter 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 seems to work, maybe not perfect but all right, at least in the examples we look at.

    How are the payoffs computed in the three cases where the restaurants are placed in the same village, or in adjacent villages, or in nonadjacent villages? It turns out that they only depend on three quantities: 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.

    1. A first Graph (Graph 6)

    Look at the graph displayed to the right. Again you can play Restaurant placement on this graph . Let me explain in three examples how the payoff matrix of the game is derived.

    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, the four Nash equilibria are the only outcomes where the sum of the payoffs reaches the maximum occurring value of 9/2.

    2. A second Graph (Graph 11)

    Play the game here on Graph 11.

    Gr2     1    2    3    4    5    6    7    8
    1   3/2, 3/2     9/4, 7/4     5/2, 2     9/4, 5/4     2, 5/2     2, 2     5/2, 2     3, 2  
    2   7/4, 9/4     5/4, 5/4     7/4, 7/4     9/4, 7/4     3/2, 5/2     2, 5/2     9/4, 9/4     9/4, 7/4  
    3   2, 5/2     7/4, 7/4     5/4, 5/4     5/2, 2     7/4, 11/4     9/4, 11/4     2, 2     2, 3/2  
    4   5/4, 9/4     7/4, 9/4     2, 5/2     1, 1     3/2, 3     5/4, 9/4     7/4, 9/4     2, 2  
    5   5/2, 2     5/2, 3/2     11/4, 7/4     3, 3/2     7/4, 7/4     5/2, 2     11/4, 7/4     3, 3/2  
    6   2, 2     5/2, 2     11/4, 9/4     9/4, 5/4     2, 5/2     3/2, 3/2     9/4, 7/4     11/4, 7/4  
    7   2, 5/2     9/4, 9/4     2, 2     9/4, 7/4     7/4, 11/4     7/4, 9/4     5/4, 5/4     2, 3/2  
    8   2, 3     7/4, 9/4     3/2, 2     2, 2     3/2, 3     7/4, 11/4     3/2, 2     1, 1  

    This game has four pure Nash equilibria, colored in the bimatrix above. In both these cases, the sum of payoffs of both players equals 9/2. However the combination of one restaurant in village 1 and the other one in village 8 serves the community better, since the sum of payoffs is 5 in this case. This combination maximizes the number of villagers reached.

    Move number 5 is the only Maximin move, with a security level of 7/4. The maximum degree of the graph equals Δ = 5. Again vertex 5 is the vertex whose degree equals the maximum degree Δ. This is not a coincidence:

    Theorem: For every graph, the maximin moves are locations on vertices with maximum degree d(x)=Δ. The security level equals 1/2 + Δ/4.

    Why? If Ann plays vertex x, the worst that could happen to Ann is when Beth also places her restaurant on vertex x, since both payoffs then are 1/2 + d(x)/4, which is always lower or equal to the Ann's payoffs 1+ d(x)/2 - n(x,y)/4 respectively 1/2 + d(x)/2 - n(x,y)/4 when Beth places her restaurant somewhere else (since n(x,y) ≤ d(x)). Thus in row x, the minimum value for Ann is 1/2 + d(x)/4. This value is maximized for x with maximal d(x).

    3. Existence of Pure Nash Equilibria

    For every vertex x, the payoff Ann would get from the restaurant in x in the absence of Beth, or if Beth places her restaurant far away is 1+d(x)/2. Of course, the same is true for Beth, if she places her restaurant at y and Ann places far away, Beth's payoff is 1+d(y)/2. But if the locations x and y are closer together, both payoffs are reduced. Moreover, and this is the important part, both payoffs are reduced by the same amount. This amount equals

    Theorem [P 2011]: All simultaneous restaurant location games with one restaurant for each player have at least one Nash equilibrium in pure strategies.

    We can even describe how to find a Nash equilibrium. Starting with any vertex, we proceed to one of its best responses, and from that vertex to one of its best responses, and so on. In other words, we start with any vertex and move along arcs of the best response digraph. Eventually we must visit a vertex that we have seen already in the sequence. In other words, we will find a directed cycle in the best response digraph. We will only discuss one special case, but the others can be treated similarly.

    The special case is where the cycle consists of four different vertices x, y, z, and w, i.e. where y is a best response to x, z a best response to y, w is a best response to z, and x is a best response to w. Since y is the best response to x, and therefore at least as good a response as w, we get

    1+d(y)/2 - g(y,x) ≥ 1+d(w)/2 - g(w,x).
    In the same way, we can conclude
    1+d(z)/2 - g(z,y) ≥ 1+d(x)/2 - g(x,y),
    1+d(w)/2 - g(w,z) ≥ 1+d(y)/2 - g(y,z),
    1+d(x)/2 - g(x,w) ≥ 1+d(z)/2 - g(z,w),
    We have four inequalities, with the left sides always greater or equal to the right side. Then the sum of these four left sides must be greater or equal to the sum of the four right sides.
    1+d(y)/2 - g(y,x) + 1+d(z)/2 - g(z,y) + 1+d(w)/2 - g(w,z) + 1+d(x)/2 - g(x,w) ≥ 1+d(w)/2 - g(w,x) + 1+d(x)/2 - g(x,y) + 1+d(y)/2 - g(y,z) + 1+d(z)/2 - g(z,w).
    But since g(x,y)=g(y,x), and so on, the expressions on the left are exactly the ones on the right, so we have equality. That means that there must have been equality in all the four inequalities above. Equality in the first one implies that both w and y are best responses to x, and since x is also a best response to w we have a Nash equilibrium x versus w. The other three equations would imply three more pairs of Nash equilibria--- x versus y, y versus z, and z versus w. So we have found Nash equilibria.

    4. More than one restaurant (optional)

    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 simultaneously by the two players. If a village hosts no restaurant, but two restaurants from Ann's chain and one from Beth's chain are adjacent, then still half of the population would go to a restaurant, one fourth to to one from Ann's chain and one fourth to Beth's restaurant. Thus they would not visit every adjacent restaurant with the same frequency. This could be explained by 50% of the population of every village having a very slight preference towards Ann's chain, and 50% towards Beth's chain, so slight that they would always go to the closer one no matter what brand, but in case of a tie of distance, they would go to their preferred brand.

    Let us discuss what can happen at the example of Graph 10. Note that, since you cannot click simultaneously with one mouse, in this applet you have to press the button "Seq Ann---Beth", and then select Ann's first restaurant, Beth's first restaurant, Ann's second restaurant, and Beth's second restaurant, in this order.

    Let us abbreviate a move where a player places her two restaurants at vertices x and y as {x,y}. Since there every player has the 9 moves {1,1}, ... {9,9}, and also the 36 moves {x,y} with x and y different (note that {x,y} and {y,x} are the same), each player has 45 possible moves, so the payoff bimatrix would have dimensions 45 × 45--- a little too large for us to display and discuss.

    Still we can check that the method of finding Nash equilibria inside directed cycles of the best response digraph for restaurant location games with one restaurant each fails. Assume Blue places her restaurant on 4 and 6, i.e. chooses move {4,6}. Confirm that one of Beth's best responses to that would be {2,5} (the other best response would be {1,2}). Ann's best response to {2,5} is {1,9} (or {4,9}). Beth's best response to {1,9} is {4,6}. So we have a directed cycle of length 3 in the best response digraph, but different to the one restaurant case, the reverse arcs are absent in the best response digraph: {1,9} is not a best response to {4,6}, {2,5} is not a best response to {1,9}, and {4,6} is not a best response to {2,5}.

    In fact, looking at the whole best response digraph, one can confirm that this simultaneous game has no pure Nash equilibria.

    More links

    Exercises

    1. Look at a simultaneous restaurant location game with two restaurants for each player. Find moves {x,z} for Ann and {y,w} for Beth where the difference between Ann's actual payoff and the payoff she would get if both of Beth's restaurant where far away is different to the difference between Beth's actual payoff and the payoff she would get if both of Ann's restaurant where far away. Remember that in the 1-restaurant case, both these numbers must be equal (denoted g(x,y) above).
      ...........
    2. Look at a variant of the 1-restaurant location game where every villagers goes to some restaurant if there is some in the same village, half of the villagers go to a restaurant if the closest one is in a neighbor village, and one fourth of the villagers go to some restaurant if the closest one is in a neighbor village of a neighbor village of that village.
      Look at moves 7 and 8 in Graph 10 above. Calculate the payoffs for the players for that case. What would the payoffs be if the placement of the other player were far away, assuming that the play graph were much larger than Graph 10? Which one of the players is hurt more by the placement of the other player?
      ...
    3. .....
      ...

    4. ...


      ...

    5. .....
      ...

    Projects

    1. Research Project: Use this Excel File to compute all Nash equilibria of the Restaurant Location Game for several graphs, and test how many of them maximize the sum of the payoffs of the two players.
      If they don't, what is the worst ratio of sum of player's payoffs in a Nash equilibrium and the maximum possible sum of player's payoffs.

      ...
    2. .....
      ...
    3. .....
      ...
    4. .....
      ...
    5. .....
      ...

    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 response ... 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.