5 - Example: Restaurant Location Games

Summary

Prerequisites: Chapters 1 and 2.

As in in the previous chapter we discuss games on graphs. Their most interesting feature is that they always have pure Nash equilibria.

Let us repeat the definition of an undirected graph, given in Chapter 4. Undirected graphs have vertices, displayed by small circles. Some pairs of vertices are connected by undirected edges. They are drawn as curves connecting the two vertices. Vertices connected by an edge are called adjacent. Adjacent vertices are also called neighbors.

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

Restaurant Location Game On a small island are towns, all having the same number of residents. The towns 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:

• People with a sushi restaurant in their home town would on average eat sushi once a year. They would not visit sushi restaurants outside their home town. If both sushi restaurants were in the home town, residents would randomly choose either, or alternate their choices.

• A person with no sushi restaurant in the home town, but with a restaurant in an adjacent town, would on average eat sushi once in two years. If more than one sushi restaurants were in a town adjacent to the person's home town, the person would randomly choose either, or alternate choices.

• Nobody would go to a sushi restaurant that is not in the home town or an adjacent town.

In the simultaneous version of the game, both Ann and Beth simultaneously submit a proposal for the location of their restaurants. The payoffs for the players are the expected numbers of customers per year. What location should the players choose?