Weitere Kapitel dieses Buchs durch Wischen aufrufen
Game Theory is the main tool used to model the behavior of agents that are guided by their own objective in contexts where their gains depend also on the choices made by neighboring agents. Game theoretic approaches have been often proposed for modeling phenomena in a complex social network, such as the formation of the social network itself. We are interested in the dynamics that govern such phenomena. In this paper, we study a specific class of randomized update rules called the logit choice function which can be coupled with different selection rules so to give different dynamics. We study how the logit choice function behave in an extreme case of concurrency.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten
Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:
C. Alós-Ferrer and N. Netzer, “The logit-response dynamics”, Games and Economic Behavior68 (2) (2010), 413–427.
E. Anshelevich, A. Dasgupta, É. Tardos, and T. Wexler, “Near-optimal network design with selfish agents”, Theory of Computing4 (1) (2008), 77–109.
A. Asadpour and A. Saberi, “On the inefficiency ratio of stable equilibria in congestion games”, Proc. of the 5-th Int. Workshop on Internet and Network Economics (WINE’09), volume 5929 of Lecture Notes in Computer Science, 545–552. Springer, 2009.
V. Auletta, D. Ferraioli, F. Pasquale, P. Penna, and G. Persiano, “Convergence to equilibrium of logit dynamics for strategic games”, Proc. of the 23-rd ACM Symp. on Parallelism in Algorithms and Architectures (SPAA’11) (2011), 197–206.
V. Auletta, D. Ferraioli, F. Pasquale, and G. Persiano, “Metastability of logit dynamics for coordination games”, Proc. of the ACM-SIAM Symp. on Discrete Algorithms (SODA’12) (2012), 1006–1024.
V. Bala and S. Goyal, “A noncooperative model of network formation”, Econometrica68 (5) (2000), 1181–1229.
N. Berger, Cl. Kenyon, E. Mossel, and Y. Peres, “Glauber dynamics on trees and hyperbolic graphs”, Probability Theory and Related Fields131 (2005), 311–340; preliminary version in FOCS 01.
D. Bindel, J.M. Kleinberg, and S. Oren, “How bad is forming your own opinion?”, Proc. of the 52-nd IEEE Annual Symposium on Foundations of Computer Science (FOCS’11) (2011), 57–66.
L.E. Blume, “The statistical mechanics of strategic interaction”, Games and Economic Behavior5 (3) (1993), 387–424.
C. Borgs, J.T. Chayes, J. Ding, and B. Lucier, “The hitchhiker’s guide to affiliation networks: a game-theoretic approach”, Proc. of the 2-nd Symposium on Innovation in Computer Science (ICS’11), 389–400; Tsinghua University Press, 2011.
C. Borgs, J.T. Chayes, B. Karrer, B. Meeder, R. Ravi, R. Reagans, and A. Sayedi, “Game-theoretic models of information overload in social networks”, Proc. of the 7-th Workshop on Algorithms and Models for the Web Graph (WAW’10), 146–161, 2010.
J. Corbo and D.C. Parkes, “The price of selfish behavior in bilateral network formation”, Proc. of the 24-th Annual ACM Symposium on Principles of Distributed Computing (PODC’05), 99–107, 2005.
A.A. Cournot, “Recherches sur le principes mathematiques de la theorie des richesses”, L. Hachette, 1838.
Gl. Ellison, “Learning, local interaction, and coordination”, Econometrica61 (5) (1993), 1047–1071.
A. Fabrikant, A. Luthra, E.N. Maneva, C.H. Papadimitriou, and S. Shenker, “On a network creation game”, Proc. of the 22-nd Annual ACM Symposium on Principles of Distributed Computing (PODC’03) (2003), 347–351.
D. Ferraioli, P. Goldberg, and C. Ventre, “Decentralized dynamics for finite opinion games”, Proc. of the 5-th Int. Symp. on Algorithmic Game Theory (SAGT’12), 144–155; Springer Berlin Heidelberg, 2012.
D. Fudenberg and D.K. Levine, “The theory of learning in games”, MIT Press, 1998.
Dr. Fudenberg and J. Tirole, “Game theory”, MIT Press, 1992.
J.C. Harsanyi and R. Selten, “A general theory of equilibrium selection in games”, MIT Press, 1988.
S. Hart and A. Mas-Colell, “A general class of adaptive procedures”, Journal of Economic Theory98 (1) (2001), 26–54.
M.O. Jackson and A. Wolinsky, “A strategic model of social and economic networks”, Journal of Economic Theory71 (1) (1996), 44–74.
J.M. Kleinberg and S. Oren, “Mechanisms for (mis)allocating scientific credit”, Proc. of the 43-rd ACM Symposium on Theory of Computing (STOC’11) (2011), 529–538.
F. Martinelli, “Lectures on glauber dynamics for discrete spin models”, Lectures on Probability Theory and Statistics, volume 1717 of Lecture Notes in Mathematics, 93–191; Springer Berlin Heidelberg, 1999.
D.L. McFadden, “Conditional logit analysis of qualitative choice behavior”, Frontiers in Econometrics, 105–142; Academic Press, 1974.
A. Montanari and A. Saberi, “Convergence to equilibrium in local interaction games”, Proc. of 50-th Annual IEEE Symposium on Foundations of Computer Science (FOCS’09) (2009), 303–312.
S. Morris, “Contagion”, Review of Economic Studies67 (1) (2000), 57–78.
H. Peyton Young, “Individual strategy and social structure: an evolutionary theory of institutions”, Princeton University Press, 1998.
H. Peyton Young, “The diffusion of innovations in social networks”, in L.E. Blume and S.N. Durlauf, editors, The Economy as a Complex Evolving System, vol. III. Oxford University Press, 2003.
W.H. Sandholm, “Population games and evolutionary dynamics”, MIT Press, 2010.
DH. Wolpert, “Information theory – the bridge connecting bounded rational game theory and statistical physics”, Complex Engineered Systems, 14, 262–290; Springer Berlin / Heidelberg, 2006.
- Logit Dynamics with Concurrent Updates for Local Interaction Games
Neuer Inhalt/© ITandMEDIA, Product Lifecycle Management/© Eisenhans | vege | Fotolia