×

On discrete preferences and coordination. (English) Zbl 1408.91041

Summary: An active line of research has considered games played on networks in which payoffs depend on both a player’s individual decision and the decisions of her neighbors. A basic question that has remained largely open is to consider games where the players’ strategies come from a fixed, discrete set, and where players may have different preferences among the possible strategies. We develop a set of techniques for analyzing this class of games, which we refer to as discrete preference games. We parametrize the games by the relative extent to which a player takes into account the effect of her preferred strategy and the effect of her neighbors’ strategies, allowing us to interpolate between network coordination games and unilateral decision-making. We focus on the efficiency of the best Nash equilibrium and provide conditions on when the optimal solution is also a Nash equilibrium.

MSC:

91A43 Games involving graphs
91A35 Decision theory for games
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bindel, David; Kleinberg, Jon; Oren, Sigal, How bad is forming your own opinion?, (Proc. 52nd IEEE Symposium on Foundations of Computer Science (2011)) · Zbl 1292.91148
[2] Blume, Larry, The statistical mechanics of strategic interaction, Games Econ. Behav., 5, 387-424 (1993) · Zbl 0797.90123
[3] Boykov, Yuri; Veksler, Olga; Zabih, Ramin, Fast approximate energy minimization via graph cuts, (Proc. 7th International Conference on Computer Vision (1999)), 377-384
[4] Ellison, Glenn, Learning, local interaction, and coordination, Econometrica, 61, 1047-1071 (1993) · Zbl 0802.90143
[5] Ferraioli, Diodato; Goldberg, Paul W.; Ventre, Carmine, Decentralized dynamics for finite opinion games, (Proceedings of the Algorithmic Game Theory: 5th International Symposium. Proceedings of the Algorithmic Game Theory: 5th International Symposium, SAGT 2012, Barcelona, Spain, October 22-23, 2012, vol. 7615 (2012), Springer), 144 · Zbl 1284.91019
[6] Friedkin, Noah E.; Johnsen, Eugene C., Social influence and opinions, J. Math. Sociol., 15, 3-4, 193-205 (1990) · Zbl 0712.92025
[7] Gavish, Bezalel; Sridhar, Suresh, Computing the 2-median on tree networks in \(o(n \lg n)\) time, Networks, 26, 305-317 (1995) · Zbl 0856.90065
[8] Goldman, A. J., Optimal center location in simple networks, Transp. Sci., 5, 212-221 (1971)
[9] Gottlob, Georg; Greco, Gianluigi; Scarcello, Francesco, Pure Nash equilibria: hard and easy games, J. Artif. Intell. Res., 357-406 (2005) · Zbl 1134.91312
[10] Jackson, Matthew O., Social and Economic Networks (2008), Princeton University Press · Zbl 1149.91051
[11] Kariv, Oded; Hakimi, S. Louis, An algorithmic approach to network location problems. II: the p-medians, SIAM J. Appl. Math., 37, 3, 539-560 (1979) · Zbl 0432.90075
[12] Kleinberg, Jon M.; Tardos, Éva, Approximation algorithms for classification problems with pairwise relationships: metric labeling and Markov random fields, J. ACM, 49, 5, 616-639 (2002) · Zbl 1326.68336
[13] Monderer, Dov; Shapley, Lloyd S., Potential games, Games Econ. Behav., 14, 124-143 (1996) · Zbl 0862.90137
[14] Contagion, Stephen Morris, Rev. Econ. Stud., 67, 57-78 (2000)
[15] Nisan, Noam; Roughgarden, Tim; Tardos, Eva; Vazirani, Vijay V., Algorithmic Game Theory (2007), Cambridge University Press: Cambridge University Press New York, NY, USA · Zbl 1130.91005
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.