×

zbMATH — the first resource for mathematics

Decentralized dynamics for finite opinion games. (English) Zbl 1414.91072
Summary: Game theory studies situations in which strategic players can modify the state of a given system, in the absence of a central authority. Solution concepts, such as Nash equilibrium, have been defined in order to predict the outcome of such situations. In multi-player settings, it has been pointed out that to be realistic, a solution concept should be obtainable via processes that are decentralized and reasonably simple. Accordingly we look at the computation of solution concepts by means of decentralized dynamics. These are algorithms in which players move in turns to decrease their own cost and the hope is that the system reaches an “equilibrium” quickly.
We study these dynamics for the class of opinion games, recently introduced by D. Bindel et al. [in: Proceedings of the 2011 IEEE 52nd annual symposium on foundations of computer science – FOCS 2011, Palm Springs, CA, USA, October 22–25. Los Alamitos, CA: IEEE Computer Society. 57–66 (2011; Zbl 1292.91148)]. These are games, important in economics and sociology, that model the formation of an opinion in a social network. We study best-response dynamics and show upper and lower bounds on the convergence to Nash equilibria. We also study a noisy version of best-response dynamics, called logit dynamics, and prove a host of results about its convergence rate as the noise in the system varies. To get these results, we use a variety of techniques developed to bound the mixing time of Markov chains, including coupling, spectral characterizations and bottleneck ratio.

MSC:
91A43 Games involving graphs
91A06 \(n\)-person games, \(n>2\)
91D30 Social networks; opinion dynamics
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Acemoglu, D.; Ozdaglar, A., Opinion dynamics and learning in social networks, Dyn. Games Appl., 1, 1, 3-49, (2011) · Zbl 1214.91091
[2] Auletta, V.; Caragiannis, I.; Ferraioli, D.; Galdi, C.; Persiano, G., Minority becomes majority in social networks, (Proc. of International Workshop on Internet and Network Economics, WINE, (2015), Springer), 74-88 · Zbl 1406.91317
[3] V. Auletta, D. Ferraioli, F. Pasquale, P. Penna, G. Persiano, Convergence to equilibrium of logit dynamics for strategic games, Algorithmica, 1-33. · Zbl 1349.91041
[4] Auletta, V.; Ferraioli, D.; Pasquale, F.; Persiano, G., Metastability of logit dynamics for coordination games, (Proceedings of ACM-SIAM Symposium on Discrete Algorithms, SODA, (2012)), 1006-1024
[5] Auletta, V.; Ferraioli, D.; Pasquale, F.; Persiano, G., Mixing time and stationary expected social welfare of logit dynamics, Theory Comput. Syst., 1-38, (2013) · Zbl 1291.91026
[6] Balcan, M.; Blum, A.; Mansour, Y., Improved equilibria via public service advertising, (Proceedings of ACM-SIAM Symposium on Discrete Algorithms, SODA, (2009)), 728-737
[7] Berger, N.; Kenyon, C.; Mossel, E.; Peres, Y., Glauber dynamics on trees and hyperbolic graphs, Probab. Theory Related Fields, 131, 311-340, (2005) · Zbl 1075.60003
[8] Bhalgat, A.; Chakraborty, T.; Khanna, S., Approximating pure Nash equilibrium in cut, party affiliation, and satisfiability games, (Proc. of ACM Conference on Electronic Commerce, EC, (2010)), 73-82
[9] Bhawalkar, K.; Gollapudi, S.; Munagala, K., Coevolutionary opinion formation games, (Proc. of ACM symposium on Theory of Computing, STOC, (2013), ACM), 41-50 · Zbl 1293.91114
[10] Bindel, D.; Kleinberg, J. M.; Oren, S., How bad is forming your own opinion?, (Proc. of Symposium on Foundations of Computer Science, FOCS, (2011)), 57-66 · Zbl 1292.91148
[11] Blume, L. E., The statistical mechanics of strategic interaction, Games Econom. Behav., 5, 387-424, (1993) · Zbl 0797.90123
[12] Bubley, R.; Dyer Path, M. E., Coupling: a technique for proving rapid mixing in Markov chains, (Proc. of Symposium on Foundations of Computer Science, FOCS, (1997)), 223-231
[13] Chien, S.; Sinclair, A., Convergence to approximate Nash equilibria in congestion games, Games Econom. Behav., 71, 2, 315-327, (2011) · Zbl 1209.91020
[14] Chierichetti, F.; Kleinberg, J.; Oren, S., On discrete preferences and coordination, (Proc. of ACM Conference on Electronic Commerce, EC, (2013), ACM), 233-250
[15] DeGroot, M. H., Reaching a consensus, J. Amer. Statist. Assoc., 69, (1974) · Zbl 0282.92011
[16] DeMarzo, P. M.; Vayanos, D.; Zweibel, J., Persuasion bias, social influence, and unidimensional opinions, Quart. J. Econ., (2003) · Zbl 1069.91093
[17] Dyer, M.; Mohanaraj, V., Pairwise-interaction games, (Proc. of Automata, Languages and Programming, ICALP, (2011)), 159-170 · Zbl 1332.68071
[18] Easley, D.; Kleinberg, J., Networks, crowds, and markets: reasoning about a highly connected world, (2010), Cambridge University Press · Zbl 1205.91007
[19] Ellison, G., Learning, local interaction, and coordination, Econometrica, 61, 5, 1047-1071, (1993) · Zbl 0802.90143
[20] Escoffier, B.; Ferraioli, D.; Gourvès, L.; Moretti, S., Designing budget-balanced best-response mechanisms for network coordination games, (Proc. of International Symposium on Algorithmic Game Theory, SAGT, (2013)), 207-218 · Zbl 1319.91054
[21] Fabrikant, A.; Papadimitriou, C. H.; Talwar, K., The complexity of pure Nash equilibria, (Proc. of Symposium on the Theory of Computing, STOC, (2004)), 604-612 · Zbl 1192.91042
[22] Ferraioli, D.; Goldberg, P. W.; Ventre, C., Decentralized dynamics for finite opinion games, (Proc. of International Symposium on Algorithmic Game Theory, SAGT, (2012)), 144-155 · Zbl 1284.91019
[23] Ferraioli, D.; Gourvès, L.; Moretti, S.; Pascual, F.; Spanjaard, O., Combinatorial optimization with competing agents, 675-706, (2014), John Wiley & Sons, Inc.
[24] Ferraioli, D.; Ventre, C., Metastability of asymptotically well-behaved potential games - (extended abstract), (Proc. of Mathematical Foundations of Computer Science, MFCS, (2015)), 311-323 · Zbl 06482818
[25] Friedkin, N. E.; Johnsen, E. C., Social influence and opinions, J. Math. Sociol., 15, 3-4, (1990) · Zbl 0712.92025
[26] Ghaderi, J.; Srikant, R., Opinion dynamics in social networks: a local interaction game with stubborn agents, (American Control Conference, ACC, 2013, (2013), IEEE), 1982-1987
[27] Golub, B.; Jackson, M. O., Naive learning in social networks: convergence, influence and the wisdom of crowds, Amer. Econ. J. Microecon., 2, (2010)
[28] Jackson, M. O., Social and economic networks, (2008), Princeton University Press · Zbl 1149.91051
[29] Jerrum, M.; Sinclair, A., Approximating the permanent, SIAM J. Comput., 18, 6, 1149-1178, (1989) · Zbl 0723.05107
[30] Koutsoupias, E.; Papadimitriou, C. H., Worst-case equilibria, Comput. Sci. Rev., 3, 2, 65-69, (2009) · Zbl 1303.91012
[31] Levin, D.; Yuval, P.; Wilmer, E. L., Markov chains and mixing times, (2008), American Mathematical Society
[32] Monderer, D.; Shapley, L. S., Potential games, Games Econom. Behav., 14, 1, 124-143, (1996) · Zbl 0862.90137
[33] Montanari, A.; Saberi, A., Convergence to equilibrium in local interaction games, (Proc. of Symposium on Foundations of Computer Science, FOCS, (2009)) · Zbl 1292.91036
[34] Peyton Young, H., The diffusion of innovations in social networks, (Blume, Lawrence E.; Durlauf, Steven N., The Economy as a Complex Evolving System, vol. III, (2003), Oxford University Press)
[35] Rosenthal, R. W., A class of games possessing pure-strategy Nash equilibria, Internat. J. Game Theory, 2, 1, 65-67, (1973) · Zbl 0259.90059
[36] Thilikos, D. M.; Serna, M. J.; Bodlaender, H. L., Constructive linear time algorithms for small cutwidth and carving-width, (Proc. of International Symposium on Algorithms and Computation, ISAAC, (2000)), 192-203 · Zbl 1044.68709
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.