Geodesic
Best Response Digraphs for Two Location Games on Graphs
Contributions to game theory and management, Tome 4 (2011), pp. 378-388.

Voir la notice de l'article provenant de la source Math-Net.Ru

We investigate two classes of location games on undirected graphs, where two players simultaneously place one facility each on a vertex. In the first class, called ‘Voronoi games’, the payoff for a player is the number of vertices closer to that player's facility than to the other one, plus half of the number of vertices with equal distance. For the other class, called ‘restaurant location games’, the payoff for a player equals 1 plus $\kappa$ times the number of private neighbors plus $\kappa /2$ times the number of common neighbors, if both locations are different, and 1/2 plus $\kappa /2$ times the number of common neighbors provided both locations are identical, for some constant $\kappa$. For both classes the question of the existence of pure Nash equilibria is investigated. Although Voronoi games, which are obviously constant-sum games, do not need to have pure Nash equilibria, Nash equilibria exist if the play graphs are trees. Restaurant location games have always at least one pure Nash equilibrium. We also try to express these Nash equilibria in graph-theoretical terms, and investigate the structure of so-called best response digraphs for the games in relation to the structure of the underlying play graph.
Keywords: simultaneous games, graphs, best response digraph, pure Nash equilibria. 
@article{CGTM_2011_4_a28,
     author = {Erich Prisner},
     title = {Best {Response} {Digraphs} for {Two} {Location} {Games} on {Graphs}},
     journal = {Contributions to game theory and management},
     pages = {378--388},
     publisher = {mathdoc},
     volume = {4},
     year = {2011},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CGTM_2011_4_a28/}
}
TY  - JOUR
AU  - Erich Prisner
TI  - Best Response Digraphs for Two Location Games on Graphs
JO  - Contributions to game theory and management
PY  - 2011
SP  - 378
EP  - 388
VL  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CGTM_2011_4_a28/
LA  - en
ID  - CGTM_2011_4_a28
ER  - 
%0 Journal Article
%A Erich Prisner
%T Best Response Digraphs for Two Location Games on Graphs
%J Contributions to game theory and management
%D 2011
%P 378-388
%V 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CGTM_2011_4_a28/
%G en
%F CGTM_2011_4_a28
Erich Prisner. Best Response Digraphs for Two Location Games on Graphs. Contributions to game theory and management, Tome 4 (2011), pp. 378-388. http://geodesic.mathdoc.fr/item/CGTM_2011_4_a28/

[1] Hotelling H., “Stability in competition”, Economic Journal, 39 (1929), 41–57 | DOI

[2] Knoblauch V., “Generalizing Location Games to a Graph”, Journal of Industrial Economics, 34 (1991)

[3] Knoblauch V., “Geometric versions of finite games: Prisoner's dilemma, entry deterrence and a cyclical majority paradox”, International Journal of Game Theory, 24 (1995), 165–177 | DOI | Zbl

[4] Buneman P., “A characterization on rigid circuit graphs”, Discrete Math., 9 (1974), 205–212 | DOI | Zbl

[5] Gavril F., “The intersection graphs of subtrees of a tree are exactly the chordal graphs”, J. Comb. Theory B, 16 (1974), 46–56 | DOI

[6] Walter J. R., “Representations of chordal graphs as subtrees of a tree”, J. Graph Th., 12 (1978), 265–267 | DOI

[7] Cheong O., Har-Peled S., Linial N., Matous̆ek J., “The one-round Voronoi game”, Discrete and Computational Geometry, 31 (2004), 125–138 | DOI | Zbl

[8] Teramoto S., Demaine E., Uehara R., “Voronoi game on graphs and its complexity”, CIG'06, Proceedings of the IEEE Symposium on Computational Intelligence and Games (2006), 265–271

[9] Dürr C., Nguyen Kim T., “Nash equilibria in Voronoi games on graphs”, ESA'07, Proceedings of the 15th Annual European Symposium on Algorithms (2007), 17–28

[10] Kariv O., Hakimi S. L., “An algorithmic approach to network location problems. II: The $p$-medians”, SIAM J. Applied Math., 37 (1979), 539–560 | DOI | Zbl