Skip to main content
Erschienen in: Theory of Computing Systems 1/2013

01.07.2013

Mixing Time and Stationary Expected Social Welfare of Logit Dynamics

verfasst von: Vincenzo Auletta, Diodato Ferraioli, Francesco Pasquale, Giuseppe Persiano

Erschienen in: Theory of Computing Systems | Ausgabe 1/2013

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We study logit dynamics (Blume in Games Econ. Behav. 5:387–424, 1993) for strategic games. This dynamics works as follows: at every stage of the game a player is selected uniformly at random and she plays according to a noisy best-response where the noise level is tuned by a parameter β. Such a dynamics defines a family of ergodic Markov chains, indexed by β, over the set of strategy profiles. We believe that the stationary distribution of these Markov chains gives a meaningful description of the long-term behavior for systems whose agents are not completely rational.
Our aim is twofold: On the one hand, we are interested in evaluating the performance of the game at equilibrium, i.e. the expected social welfare when the strategy profiles are random according to the stationary distribution. On the other hand, we want to estimate how long it takes, for a system starting at an arbitrary profile and running the logit dynamics, to get close to its stationary distribution; i.e., the mixing time of the chain.
In this paper we study the stationary expected social welfare for the 3-player CK game (Christodoulou and Koutsoupias in Proc. of the 37th Annual ACM Symposium on Theory of Computing (STOC’05), pp. 67–73, ACM, New York, 2005), for 2-player coordination games, and for two simple n-player games. For all these games, we also give almost tight upper and lower bounds on the mixing time of logit dynamics. Our results show two different behaviors: in some games the mixing time depends exponentially on β, while for other games it can be upper bounded by a function independent of β.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Fußnoten
1
Roughly speaking, a finite-state Markov chain is irreducible and aperiodic if there is a time t such that, for all pairs of states x,y, the probability to be in y after t steps, starting from x, is positive.
 
2
This is the same coupling used in the analysis of the lazy random walk on the hypercube (e.g. see Sect. 5.3.3 in [18]), the only difference being that the probability of choosing 0 or 1 is not 1/2, 1/2 but 1/(1+e β ), 1/(1+e β ).
 
Literatur
1.
Zurück zum Zitat Anshelevich, E., Dasgupta, A., Kleinberg, J.M., Tardos, É., Wexler, T., Roughgarden, T.: The price of stability for network design with fair cost allocation. SIAM J. Comput. 38(4), 1602–1623 (2008). Preliminary version in FOCS’04 MathSciNetMATHCrossRef Anshelevich, E., Dasgupta, A., Kleinberg, J.M., Tardos, É., Wexler, T., Roughgarden, T.: The price of stability for network design with fair cost allocation. SIAM J. Comput. 38(4), 1602–1623 (2008). Preliminary version in FOCS’04 MathSciNetMATHCrossRef
2.
Zurück zum Zitat Asadpour, A., Saberi, A.: On the inefficiency ratio of stable equilibria in congestion games. In: Proc. of the 5th International Workshop on Internet and Network Economics (WINE’09). Lecture Notes in Computer Science, vol. 5929, pp. 545–552. Springer, Berlin (2009) CrossRef Asadpour, A., Saberi, A.: On the inefficiency ratio of stable equilibria in congestion games. In: Proc. of the 5th International Workshop on Internet and Network Economics (WINE’09). Lecture Notes in Computer Science, vol. 5929, pp. 545–552. Springer, Berlin (2009) CrossRef
3.
Zurück zum Zitat Auletta, V., Ferraioli, D., Pasquale, F., Penna, P., Persiano, G.: Convergence to equilibrium of logit dynamics for strategic games. In: Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA’11), pp. 197–206. ACM, New York (2011) CrossRef Auletta, V., Ferraioli, D., Pasquale, F., Penna, P., Persiano, G.: Convergence to equilibrium of logit dynamics for strategic games. In: Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA’11), pp. 197–206. ACM, New York (2011) CrossRef
4.
Zurück zum Zitat Auletta, V., Ferraioli, D., Pasquale, F., Persiano, G.: Metastability of logit dynamics for coordination games. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’12), pp. 1006–1024. SIAM, Philadelphia (2012) Auletta, V., Ferraioli, D., Pasquale, F., Persiano, G.: Metastability of logit dynamics for coordination games. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’12), pp. 1006–1024. SIAM, Philadelphia (2012)
6.
Zurück zum Zitat Bubley, R., Dyer, M.: Path coupling: a technique for proving rapid mixing in Markov chains. In: Proceedings of the 38th Annual Symposium on Foundations of Computer Science, p. 223. IEEE Computer Society, Washington (1997) CrossRef Bubley, R., Dyer, M.: Path coupling: a technique for proving rapid mixing in Markov chains. In: Proceedings of the 38th Annual Symposium on Foundations of Computer Science, p. 223. IEEE Computer Society, Washington (1997) CrossRef
7.
Zurück zum Zitat Chen, X., Deng, X., Teng, S.-H.: Settling the complexity of computing two-player Nash equilibria. J. ACM 56(3) (2009) Chen, X., Deng, X., Teng, S.-H.: Settling the complexity of computing two-player Nash equilibria. J. ACM 56(3) (2009)
8.
Zurück zum Zitat Christodoulou, G., Koutsoupias, E.: The price of anarchy of finite congestion games. In: Proc. of the 37th Annual ACM Symposium on Theory of Computing (STOC’05), pp. 67–73. ACM, New York (2005) Christodoulou, G., Koutsoupias, E.: The price of anarchy of finite congestion games. In: Proc. of the 37th Annual ACM Symposium on Theory of Computing (STOC’05), pp. 67–73. ACM, New York (2005)
9.
Zurück zum Zitat Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a Nash equilibrium. SIAM J. Comput. 39(1), 195–259 (2009) MathSciNetMATHCrossRef Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a Nash equilibrium. SIAM J. Comput. 39(1), 195–259 (2009) MathSciNetMATHCrossRef
11.
Zurück zum Zitat Fabrikant, A., Papadimitriou, C.H.: The complexity of game dynamics: Bgp oscillations, sink equilibria, and beyond. In: Proc. of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’08), pp. 844–853. ACM, New York (2008) Fabrikant, A., Papadimitriou, C.H.: The complexity of game dynamics: Bgp oscillations, sink equilibria, and beyond. In: Proc. of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’08), pp. 844–853. ACM, New York (2008)
12.
13.
Zurück zum Zitat Fudenberg, D., Levine, D.K.: The Theory of Learning in Games. MIT Press, Cambridge (1998) MATH Fudenberg, D., Levine, D.K.: The Theory of Learning in Games. MIT Press, Cambridge (1998) MATH
14.
Zurück zum Zitat Goemans, M., Mirrokni, V., Vetta, A.: Sink equilibria and convergence. In: Proc. of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05), pp. 142–154. IEEE Press, New York (2005) CrossRef Goemans, M., Mirrokni, V., Vetta, A.: Sink equilibria and convergence. In: Proc. of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05), pp. 142–154. IEEE Press, New York (2005) CrossRef
15.
Zurück zum Zitat Harsanyi, J.C., Selton, R.: A General Theory of Equilibrium Selection in Games. MIT Press, Cambridge (1988) MATH Harsanyi, J.C., Selton, R.: A General Theory of Equilibrium Selection in Games. MIT Press, Cambridge (1988) MATH
16.
Zurück zum Zitat Hart, S., Mas-Colell, A.: A simple adaptive procedure leading to correlated equilibrium. Econometrica 68(5), 1127–1150 (2000) MathSciNetMATHCrossRef Hart, S., Mas-Colell, A.: A simple adaptive procedure leading to correlated equilibrium. Econometrica 68(5), 1127–1150 (2000) MathSciNetMATHCrossRef
17.
Zurück zum Zitat Koutsoupias, E., Papadimitriou, C.H.: Worst-case equilibria. Comput. Sci. Rev. 3(2), 65–69 (2009). Preliminary version in STACS 1999 CrossRef Koutsoupias, E., Papadimitriou, C.H.: Worst-case equilibria. Comput. Sci. Rev. 3(2), 65–69 (2009). Preliminary version in STACS 1999 CrossRef
18.
Zurück zum Zitat Levin, D., Peres, Y., Wilmer, E.L.: Markov Chains and Mixing Times. Am. Math. Soc., Providence (2008) Levin, D., Peres, Y., Wilmer, E.L.: Markov Chains and Mixing Times. Am. Math. Soc., Providence (2008)
19.
Zurück zum Zitat Montanari, A., Saberi, A.: Convergence to equilibrium in local interaction games. In: Proc. of the 50th Annual Symposium on Foundations of Computer Science (FOCS’09). IEEE Press, New York (2009) Montanari, A., Saberi, A.: Convergence to equilibrium in local interaction games. In: Proc. of the 50th Annual Symposium on Foundations of Computer Science (FOCS’09). IEEE Press, New York (2009)
20.
Zurück zum Zitat Rosenthal, R.W.: A class of games possessing pure-strategy Nash equilibria. Int. J. Game Theory 2(1), 65–67 (1973) MATHCrossRef Rosenthal, R.W.: A class of games possessing pure-strategy Nash equilibria. Int. J. Game Theory 2(1), 65–67 (1973) MATHCrossRef
21.
Zurück zum Zitat Roth, A., Balcan, N., Kalai, A., Mansour, Y.: On the equilibria of alternating move games. In: Proc. of ACM-SIAM Symposium on Discrete Algorithms (SODA’10) (2010) Roth, A., Balcan, N., Kalai, A., Mansour, Y.: On the equilibria of alternating move games. In: Proc. of ACM-SIAM Symposium on Discrete Algorithms (SODA’10) (2010)
22.
Zurück zum Zitat Sandholm, W.H.: Population Games and Evolutionary Dynamics. MIT Press, Cambridge (2010) MATH Sandholm, W.H.: Population Games and Evolutionary Dynamics. MIT Press, Cambridge (2010) MATH
23.
Zurück zum Zitat Young, H.P.: Individual Strategy and Social Structure: An Evolutionary Theory of Institutions. Princeton University Press, Princeton (1998) Young, H.P.: Individual Strategy and Social Structure: An Evolutionary Theory of Institutions. Princeton University Press, Princeton (1998)
24.
Zurück zum Zitat Young, H.O.: The diffusion of innovations in social networks. Economics Working Paper Archive number 437, Johns Hopkins University, Department of Economics (2000) Young, H.O.: The diffusion of innovations in social networks. Economics Working Paper Archive number 437, Johns Hopkins University, Department of Economics (2000)
Metadaten
Titel
Mixing Time and Stationary Expected Social Welfare of Logit Dynamics
verfasst von
Vincenzo Auletta
Diodato Ferraioli
Francesco Pasquale
Giuseppe Persiano
Publikationsdatum
01.07.2013
Verlag
Springer-Verlag
Erschienen in
Theory of Computing Systems / Ausgabe 1/2013
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI
https://doi.org/10.1007/s00224-013-9458-z

Weitere Artikel der Ausgabe 1/2013

Theory of Computing Systems 1/2013 Zur Ausgabe