×

Graphical potential games. (English) Zbl 1369.91033

Summary: We study the class of potential games that are also graphical games with respect to a given graph \(G\) of connections between the players. We show that, up to strategic equivalence, this class of games can be identified with the set of Markov random fields on \(G\). From this characterization, and from the Hammersley-Clifford theorem, it follows that the potentials of such games can be decomposed into local potentials.

MSC:

91A43 Games involving graphs
91A10 Noncooperative games
60G60 Random fields
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Auletta, Vincenzo; Ferraioli, Diodato; Pasquale, Francesco; Penna, Paolo; Persiano, Giuseppe, Convergence to equilibrium of logit dynamics for strategic games, (Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures (2011)), 197-206 · Zbl 1349.91041
[2] Babichenko, Yakov; Tamuz, Omer, Graphical potential games (2014) · Zbl 1369.91033
[3] Bilò, Vittorio; Fanelli, Angelo; Flammini, Michele; Moscardelli, Luca, Graphical congestion games, Algorithmica, 61, 2, 274-297 (2011) · Zbl 1229.91078
[4] Bimpikis, Kostas; Ilkilic, Rahmi; Shayan, Ehsani, Cournot competition in networked markets, (Proceedings of the 15th ACM Conference of Economics and Coputation (2014))
[5] Bramoullé, Yann; Kranton, Rachel; D’amours, Martin, Strategic interaction and networks, Am. Econ. Rev., 104, 3, 898-930 (2014)
[6] Daskalakis, Constantinos; Papadimitriou, Christos H., Computing pure Nash equilibria in graphical games via Markov random fields, (Proceedings of the 7th ACM Conference on Electronic Commerce (2006)), 91-99
[7] Grimmett, Geoffrey R., A theorem about random fields, Bull. Lond. Math. Soc., 5, 1, 81-84 (1973) · Zbl 0261.60043
[9] Jackson, Matthew O.; Zenou, Yves, Games on networks (2012), Technical Report 9127, C.E.P.R. Discussion Papers
[10] Kakade, Sham; Kearns, Michael; Langford, John; Ortiz, Luis, Correlated equilibria in graphical games, (Proceedings of the 4th ACM Conference on Electronic Commerce (2003)), 42-47
[11] Kearns, Michael; Littman, Michael L.; Singh, Satinder, Graphical models for game theory, (Proceedings of the Seventeenth Conference on Uncertainty in Artificial Intelligence (2001)), 253-260
[12] Monderer, Dov; Shapley, Lloyd S., Potential games, Games Econ. Behav., 14, 1, 124-143 (1996) · Zbl 0862.90137
[13] Nisan, Noam, Algorithmic Game Theory (2007), Cambridge University Press · Zbl 1130.91005
[14] Ortiz, Luis E., Graphical potential games (2015), arXiv preprint
[15] Preston, C. J., Generalized Gibbs states and Markov random fields, Adv. Appl. Probab., 242-261 (1973) · Zbl 0318.60085
[16] Rosenthal, Robert W., A class of games possessing pure-strategy Nash equilibria, Int. J. Game Theory, 2, 1, 65-67 (1973) · Zbl 0259.90059
[17] Sherman, S., Markov random fields and Gibbs random fields, Isr. J. Math., 14, 1, 92-103 (1973) · Zbl 0255.60047
[18] Victor, David G.; Jaffe, Amy M.; Hayes, Mark H., Natural Gas and Geopolitics: From 1970 to 2040 (2006), Cambridge University Press
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.