Best response adaptation under dominance solvability

Kukushkin, Nikolai S. (2008): Best response adaptation under dominance solvability.

Abstract

Two new properties of a finite strategic game, strong and weak BR-dominance solvability, are introduced. The first property holds, e.g., if the game is strongly dominance solvable or if it is weakly dominance solvable and all best responses are unique. It ensures that every simultaneous best response adjustment path, as well as every non-discriminatory individual best response improvement path, reaches a Nash equilibrium in a finite number of steps. The second property holds, e.g., if the game is weakly dominance solvable; it ensures that every strategy profile can be connected to a Nash equilibrium with a simultaneous best response path and with an individual best response path (if there are more than two players, switches from one best response to another may be needed). In a two person game, weak BR-dominance solvability is necessary for the acyclicity of simultaneous best response adjustment paths; if the set of Nash equilibria is rectangular, it is also necessary for the acyclicity of best response mprovement paths.

• Item Type: MPRA Paper
• Institution: Russian Academy of Sciences, Dorodnicyn Computing Center
• Language: English
• Keywords: Dominance solvability; Best response dynamics; Potential game
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C72 - Noncooperative Games; C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C73 - Stochastic and Dynamic Games ; Evolutionary Games ; Repeated Games

References

Bernheim, B.D., 1984. Rationalizable strategic behavior. Econometrica 52, 1007--1028.

Borges, T., 1993. Pure strategy dominance. Econometrica 61, 423--430.

Dufwenberg, M., and M. Stegeman, 2002. Existence and uniqueness of maximal reductions under iterated strict dominance. Econometrica 70, 2007--2023.

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

Fudenberg, D., and D.K. Levine, 1998. The Theory of Learning in Games. The MIT Press, Cambridge, Mass.

Gilboa, I., E. Kalai, and E. Zemel, 1990. On the order of eliminating dominated strategies. Operations Research Letters 9, 85--89.

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.

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

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

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

Luce, R.D., and H. Raiffa, 1957. Games and Decisions. Wiley, New York.

Marx, L.M., and J.M. Swinkels, 1997. Order independence for iterated weak dominance. Games and Economic Behavior 18, 219--245.

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

Milgrom, P., and J. Roberts, 1990. Rationalizability, learning, and equilibrium in games with strategic complementarities. Econometrica 58, 1255--1277.

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

Moulin, H., 1979. Dominance solvable voting schemes. Econometrica 47, 1337--1351.

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

Moulin, H., 1986. Game Theory for the Social Sciences. New York University Press, New York.

Pearce, D., 1984. Rationalizable strategic behavior and the problem of perfection. Econometrica 52, 1029--1050.

Samuelson, L., 1992. Dominated strategies and common knowledge. Games and Economic Behavior 4, 284--313.

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

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.