nach oben

Theory and Decision

Erschienen in:

01.04.2015

A classification of weakly acyclic games

verfasst von: Krzysztof R. Apt, Sunil Simon

Erschienen in: Theory and Decision | Ausgabe 4/2015

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Weakly acyclic games form a natural generalization of the class of games that have the finite improvement property (FIP). In such games one stipulates that from any initial joint strategy some finite improvement path exists. We classify weakly acyclic games using the concept of a scheduler introduced in Simon and Apt (Choosing products in social networks, 2012). We also show that finite games that can be solved by the iterated elimination of never best response strategies are weakly acyclic. Finally, we explain how the schedulers allow us to improve the bounds on finding a Nash equilibrium in a weakly acyclic game.

Nächster Artikel Reconciling cost-effectiveness with the rule of rescue: the institutional division of moral labour

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!

Jetzt informieren

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!

Jetzt informieren

Apt, K.R. (2005). Order independence and rationalizability. In Proceedings 10th Conference on Theoretical Aspects of Reasoning about Knowledge (TARK ’05) (pp. 22–38). The ACM Digital Library. Available from http://portal.acm.org

Apt, K.R., & Simon, S. (2012). A classification of weakly acyclic games. In Proceedings 5th International Symposium on Algorithmic Game Theory (SAGT12), volume 7615 of Lecture Notes in Computer Science (pp. 1–12). Springer.

Bernheim, B. D. (1984). Rationalizable strategic behavior. Econometrica, 52(4), 1007–1028.CrossRef

Brokkelkamp, K.R., & Vries, M.J. (2012). Convergence of ordered paths in generalized congestion games. In Proceedings 5th International Symposium on Algorithmic Game Theory (SAGT12), volume 7615 of Lecture Notes in Computer Science (pp. 61–711). Springer.

Engelberg, R., & Schapira, M. (2011). Weakly-acyclic (internet) routing games. In Proceedings 4th International Symposium on Algorithmic Game Theory (SAGT11), volume 6982 of Lecture Notes in Computer Science (pp. 290–301). Springer.

Fabrikant, A., Jaggard, A., & Schapira, M. (2010). On the structure of weakly acyclic games. In Proceedings of the Third International Symposium on Algorithmic Game Theory (SAGT 2010), volume 6386 of Lecture Notes in Computer Science, (pp. 126–137). Springer.

Fabrikant, A., Luthra, A., Maneva, E., Papadimitriou, C., & Shenker, S. (2003). On a network creation game. In Proceedings of the 22nd annual Symposium on Principles of Distributed Computing (PODC’03) (pp. 347–351). ACM.

Grädel, E. (2011). Lectures in game theory for computer scientists. In K. R. Apt & E. Grädel (Eds.), Back and forth between logic and games. (pp. 99–145). Cambridge: Cambridge University Press.

Kawald, B., & Lenzner, P. (2013). On dynamics in selfish network creation. In Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures (pp. 83–92). ACM.

König, D. (1927). Über eine Schlußweise aus dem Endlichen ins Unendliche. Acta Litterarum ac Scientiarum, 3, 121–130.

Marden, J., Arslan, G., & Shamma, J. (2007). Regret based dynamics: convergence in weakly acyclic games. In Proceedings of the Sixth International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2007) (pp. 194–201). IFAAMAS.

Milchtaich, I. (1996). Congestion games with player-specific payoff functions. Games and Economic Behaviour, 13, 111–124.CrossRef

Monderer, D., & Shapley, L. S. (1996). Potential games. Games and Economic. Behaviour, 14, 124–143.

Moulin, H. (1986). Game Theory for the Social Sciences. NYU Press, New York, second, revised edition.

Simon, S., & Apt, K.R. (2012). Choosing products in social networks. In Proceedings 8th International Workshop on Internet and Network Economics (WINE), volume 7695 of Lecture Notes in Computer Science (pp. 100–113). Liverpool, UK: Springer.

Young, H. P. (1993). The evolution of conventions. Econometrica, 61(1), 57–84.CrossRef

Titel: A classification of weakly acyclic games
verfasst von: Krzysztof R. Apt
Sunil Simon
Publikationsdatum: 01.04.2015
Verlag: Springer US
Erschienen in: Theory and Decision / Ausgabe 4/2015
Print ISSN: 0040-5833
Elektronische ISSN: 1573-7187
DOI: https://doi.org/10.1007/s11238-014-9436-1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 4/2015

Minimax and the value of information

Rationalizing epistemic bounded rationality

Reconciling cost-effectiveness with the rule of rescue: the institutional division of moral labour

Temptation, horizontal differentiation and monopoly pricing

Is the newcomer more aggressive when the incumbent is granted a Right-of-First-Refusal in a procurement auction? Experimental Evidence

Strategically equivalent contests