Acyclicity of improvements in finite game forms

Kukushkin, Nikolai S. (2008): Acyclicity of improvements in finite game forms.

Abstract

Game forms are studied where the acyclicity, in a stronger or weaker sense, of (coalition or individual) improvements is ensured in all derivative games. In every game form generated by an ``ordered voting'' procedure, individual improvements converge to Nash equilibria if the players restrict themselves to ``minimal'' strategy changes. A complete description of game forms where all coalition improvement paths lead to strong equilibria is obtained: they are either dictatorial, or voting (or rather lobbing) about two outcomes. The restriction to minimal strategy changes ensures the convergence of coalition improvements to strong equilibria in every game form generated by a ``voting by veto'' procedure.

• Item Type: MPRA Paper
• Language: English
• Keywords: Improvement dynamics; Game form; Perfect information game; Potential game; Voting by veto
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C72 - Noncooperative Games

References

Abdou, J., 1995. Nash and strongly consistent two-player game forms. International Journal of Game Theory 24, 345--356.

Abdou, J., 1998. Tight and effectively rectangular game forms: A Nash solvable class. Games and Economic Behavior 23, 1--11.

Abdou, J., and H. Keiding, 2003. On necessary and sufficient conditions for solvability of game forms. Mathematical Social Sciences 46, 243--260.

Boros, E., and V. Gurvich, 2003. On Nash-solvability in pure stationary strategies of finite games with perfect information which may have cycles. Mathematical Social Sciences 46, 207--241.

Boros, E., V. Gurvich, K. Makino, and W. Shao, 2007. Nash-solvable bidirected cyclic game forms. RUTCOR Research Report RRR 30-2007. Available at http://rutcor.rutgers.edu/pub/rrr/reports2007/30_2007.ps

Boros, E., V. Gurvich, K. Makino, and D. Papp, 2008a. On acyclic, or totally tight, two-person game forms. RUTCOR Research Report RRR 3-2008. Available at http://rutcor.rutgers.edu/pub/rrr/reports2008/03_2008.pdf

Boros, E., V. Gurvich, K. Makino, and D. Papp, 2008b. Acyclic, or totally tight, two-person game forms; characterization and main properties. RUTCOR Research Report RRR 6-2008. Available at http://rutcor.rutgers.edu/pub/rrr/reports2008/paper.pdf

Friedman, J.W., and C. Mezzetti, 2001. Learning in games by random sampling. Journal of Economic Theory 98, 55--84.

Germeier, Yu.B., and I.A. Vatel', 1974. On games with a hierarchical vector of interests. Izvestiya Akademii Nauk SSSR, Tekhnicheskaya Kibernetika, 3, 54--69 (in Russian; English translation in Engineering Cybernetics, V.12).

Gol'berg, A.I., and V.A. Gurvich, 1986. Collective choice based on the veto principle. VINITI Manuscript \#3182--V86 (in Russian).

Gurvich, V.A., 1975. Solvability of extensive games in pure strategies, Zhurnal Vychislitel'noi matematiki i matematicheskoi fiziki 15(2), 358--371 (in Russian; English translation in USSR Computational Mathematics and Mathematical Physics 15(2), 74--87).

Gurvich, V.A., 1988. Equilibrium in pure strategies. Doklady Akademii Nauk SSSR 303, 789--793 (in Russian; English translation in Soviet Mathematics. Doklady 38, 597--602).

Holzman, R., and N. Law-yone, 1997. Strong equilibrium in congestion games. Games and Economic Behavior 21, 85--101.

Kalai, E. and D. Schmeidler, 1977. An admissible set occurring in various bargaining situations. Journal of Economic Theory 14, 402--411.

Kandori, M., and R. Rob, 1995. Evolution of equilibria in the long run: A general theory and applications. Journal of Economic Theory 65, 383--414.

Konishi, H., M. Le Breton, and S. Weber, 1997. Equilibria in a model with partial rivalry. Journal of Economic Theory 72, 225--237.

Kreps, D.M., 1990. A Course in Microeconomic Theory. Princeton University Press, Princeton.

Kukushkin, N.S., 1995. Two-person game forms guaranteeing the stability against commitment and delaying tactics. International Journal of Game Theory 24, 37--48.

Kukushkin, N.S., 1999. Potential games: A purely ordinal approach. Economics Letters 64, 279--283.

Kukushkin, N.S., 2000. Potentials for Binary Relations and Systems of Reactions. Russian Academy of Sciences, Computing Center, Moscow.

Kukushkin, N.S., 2002a. Perfect information and potential games. Games and Economic Behavior 38, 306--317.

Kukushkin, N.S., 2002b. Unfocussed Nash Equilibria. Russian Academy of Sciences, Dorodnicyn Computing Center, Moscow. A revised version available at http://www.ccas.ru/mmes/mmeda/ququ/Unfocussed.pdf

Kukushkin, N.S., 2004. Best response dynamics in finite games with additive aggregation. Games and Economic Behavior 48, 94--110.

Kukushkin, N.S., 2004b. Acyclicity of Improvements in Games with Common Intermediate Objectives. Russian Academy of Sciences, Dorodnicyn Computing Center, Moscow. A revised version available at http://www.ccas.ru/mmes/mmeda/ququ/Common3.pdf

Kukushkin, N.S., 2006. Acyclicity and Aggregation in Strategic Games. Russian Academy of Sciences, Dorodnicyn Computing Center, Moscow. A version available at http://www.ccas.ru/mmes/mmeda/ququ/IntAA.pdf

Kukushkin, N.S., 2007a. Shapley's ``2 by 2'' theorem for game forms. Economics Bulletin 3, No.\,33, 1--5. Available at http://economicsbulletin.vanderbilt.edu/2007/volume3/EB-07C70017A.pdf; with a typo corrected, at http://www.ccas.ru/mmes/mmeda/ququ/Shapley.pdf

Kukushkin, N.S., 2007b. Congestion games revisited. International Journal of Game Theory 36, 57--83.

Kukushkin, N.S., 2007c. Aggregation and Acyclicity in Strategic Games. Russian Academy of Sciences, Dorodnicyn Computing Center, Moscow. A version available at http://www.ccas.ru/mmes/mmeda/ququ/AgrAcl.pdf

Kukushkin, N.S., S. Takahashi, and T. Yamamori, 2005. Improvement dynamics in games with strategic complementarities. International Journal of Game Theory 33, 229--238.

Mariotti, M., 2000. Maximum games, dominance solvability, and coordination. Games and Economic Behavior 31, 97--105.

Milchtaich, I., 1996. Congestion games with player-specific payoff functions. Games and Economic Behavior 13, 111--124.

Milgrom, P., and J. Roberts, 1991. Adaptive and sophisticated learning in normal form games. Games and Economic Behavior 3, 82--100.

Monderer, D., and L.S. Shapley, 1996. Potential games. Games and Economic Behavior 14, 124--143.

Moulin, H., 1976. Prolongements des jeux a deux joueurs de somme nulle. Bulletin de la Societe Mathematique de France, Supplementaire Memoire No.45.

Moulin, H., 1980. On strategy-proofness and single-peakedness. Public Choice 35, 437--455.

Moulin, H., 1983. The Strategy of Social Choice. North-Holland Publ., Amsterdam.

Moulin, H., 1984. Dominance solvability and Cournot stability. Mathematical Social Sciences 7, 83--102.

Mueller, D.C., 1978. Voting by veto. Journal of Public Economics 10, 57--75.

Peleg, B., 1978. Consistent voting systems. Econometrica 46, 153--161.

Rosenthal, R.W., 1973. A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory 2, 65--67.

Sela, A., 1992. Learning Processes in Games. M.Sc. Thesis. The Technion, Haifa (in Hebrew).

Topkis, D.M., 1979. Equilibrium points in nonzero-sum n-person submodular games. SIAM Journal on Control and Optimization 17, 773--787.

Topkis, D.M., 1998. Supermodularity and Complementarity. Princeton University Press, Princeton.

Vives, X., 1990. Nash equilibrium with strategic complementarities. Journal of Mathematical Economics 19, 305--321.

Young, H.P., 1993. The evolution of conventions. Econometrica 61, 57--84.