Determination of Sequential Best Replies in N-player Games by Genetic Algorithms
An iterative algorithm is proposed and tested in Cournot Game models, which is based on the convergence of sequential best responses and the utilization of a genetic algorithm for determining each player-s best response to a given strategy profile of its opponents. An extra outer loop is used, to address the problem of finite accuracy, which is inherent in genetic algorithms, since the set of feasible values in such an algorithm is finite. The algorithm is tested in five Cournot models, three of which have convergent best replies sequence, one with divergent sequential best replies and one with “local NE traps"[14], where classical local search algorithms fail to identify the Nash Equilibrium. After a series of simulations, we conclude that the algorithm proposed converges to the Nash Equilibrium, with any level of accuracy needed, in all but the case where the sequential best replies process diverges.
[1] F. Alkemade, H. La Poutre and H. Amman, "On Social Learning
and Robust Evolutionary Algorithm Design in the Cournot Oligopoly
Game", Computational Intelligence, vol. 23, 2007, pp. 162-175.
[2] J. Arifovic,"Genetic Algorithm Learning and the Cobweb Model",
Journal of Economic Dynamics and Control, vol. 18, 1994, pp. 3-28.
[3] R. Amir, "Cournot oligopoly and the theory of supermodular games",
Games and Economic Behavior, vol. 15, 1996, pp. 132-148.
[4] J.I. Bulow, J.D. Geanakoplos and P.D. Klemperer, "Multimarket
oligopoly: strategic substitutes and complements", Journal of Political
Economy, vol. 93, 1985, pp. 488-511.
[5] A.A. Cournot, Recherches sur les principes mathematiques de la theorie
des richesses (Researches into the Mathematical Principles of the
Theory of Wealth), English translation by N.T. Bacon, 1897.
[6] P. Dubey,O. Haimanko and A. Zapechelnyuk, "Strategic Complements
and Substitutes and Potential Games", Games and Economic Behavior,
vol. 54, 2006, pp. 77-94.
[7] D. Fundenberg and J. Tirole, Game Theory, The MIT Press, Cambridge
MA, 1991.
[8] D.E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine
Learning, Addison-Wesley, Reading, MA, 1998.
[9] B.F. Hobbs, C.F. Metzler and J.S. Pang, "Strategic gaming analysis for
electric power systems: An MPEC approach", IEEE Transactions on
Power Systems, vol. 15, 2000, pp. 638-645.
[10] N.S. Kukushkin, "A fixed-point theorem for decreasing mappings",
Economic Letters, vol. 46, 1994, pp. 23-26.
[11] C.E. Lemke and J.T. Howson, "Equilibrium points of bimatrix games",
Journal of the Society for Industrial and Applied Mathematics, vol. 12,
1964, pp. 413-423.
[12] P. Milgrom and J. Roberts, "Rationalizability, learning, and equilibrium
in games with strategic complementarities", Econometrica, vol. 58,
1990, pp. 1255-1277.
[13] M. Protopapas and E. Kosmatopoulos, "Two Genetic Algorithms yielding
Nash Equilibrium in Cournot Games", Technical University of Crete
Working Paper 29-01-2008.
[14] Y.S. Son and R. Baldick, "Hybrid Coevolutionary Programming for
Nash Equilibrium Search in Games with Local Optima", IEEE Transactions
on Evolutionary Computation, 2004, vol. 8, pp. 305-315.
[15] M. Voorneveld, "Best-response potential games, Economic Letters,
2000, vol. 66, pp. 289-295.
[16] N. Vriend, "An Illustration of the Essential Difference between Individual
and Social Learning, and its Consequences for Computational
Analyses", Journal of Economic Dynamics and Control, 2000, vol. 24,
pp. 1-19.
[17] J.D. Weber and T.J. Overbye, "A two-level optimization problem
for analysis of market bidding strategies",. In Proceedings of Power
Engineering Society Summer Meeting, 1999, vol. 2, pp. 846-851.
[1] F. Alkemade, H. La Poutre and H. Amman, "On Social Learning
and Robust Evolutionary Algorithm Design in the Cournot Oligopoly
Game", Computational Intelligence, vol. 23, 2007, pp. 162-175.
[2] J. Arifovic,"Genetic Algorithm Learning and the Cobweb Model",
Journal of Economic Dynamics and Control, vol. 18, 1994, pp. 3-28.
[3] R. Amir, "Cournot oligopoly and the theory of supermodular games",
Games and Economic Behavior, vol. 15, 1996, pp. 132-148.
[4] J.I. Bulow, J.D. Geanakoplos and P.D. Klemperer, "Multimarket
oligopoly: strategic substitutes and complements", Journal of Political
Economy, vol. 93, 1985, pp. 488-511.
[5] A.A. Cournot, Recherches sur les principes mathematiques de la theorie
des richesses (Researches into the Mathematical Principles of the
Theory of Wealth), English translation by N.T. Bacon, 1897.
[6] P. Dubey,O. Haimanko and A. Zapechelnyuk, "Strategic Complements
and Substitutes and Potential Games", Games and Economic Behavior,
vol. 54, 2006, pp. 77-94.
[7] D. Fundenberg and J. Tirole, Game Theory, The MIT Press, Cambridge
MA, 1991.
[8] D.E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine
Learning, Addison-Wesley, Reading, MA, 1998.
[9] B.F. Hobbs, C.F. Metzler and J.S. Pang, "Strategic gaming analysis for
electric power systems: An MPEC approach", IEEE Transactions on
Power Systems, vol. 15, 2000, pp. 638-645.
[10] N.S. Kukushkin, "A fixed-point theorem for decreasing mappings",
Economic Letters, vol. 46, 1994, pp. 23-26.
[11] C.E. Lemke and J.T. Howson, "Equilibrium points of bimatrix games",
Journal of the Society for Industrial and Applied Mathematics, vol. 12,
1964, pp. 413-423.
[12] P. Milgrom and J. Roberts, "Rationalizability, learning, and equilibrium
in games with strategic complementarities", Econometrica, vol. 58,
1990, pp. 1255-1277.
[13] M. Protopapas and E. Kosmatopoulos, "Two Genetic Algorithms yielding
Nash Equilibrium in Cournot Games", Technical University of Crete
Working Paper 29-01-2008.
[14] Y.S. Son and R. Baldick, "Hybrid Coevolutionary Programming for
Nash Equilibrium Search in Games with Local Optima", IEEE Transactions
on Evolutionary Computation, 2004, vol. 8, pp. 305-315.
[15] M. Voorneveld, "Best-response potential games, Economic Letters,
2000, vol. 66, pp. 289-295.
[16] N. Vriend, "An Illustration of the Essential Difference between Individual
and Social Learning, and its Consequences for Computational
Analyses", Journal of Economic Dynamics and Control, 2000, vol. 24,
pp. 1-19.
[17] J.D. Weber and T.J. Overbye, "A two-level optimization problem
for analysis of market bidding strategies",. In Proceedings of Power
Engineering Society Summer Meeting, 1999, vol. 2, pp. 846-851.
@article{"International Journal of Information, Control and Computer Sciences:59788", author = "Mattheos K. Protopapas and Elias B. Kosmatopoulos", title = "Determination of Sequential Best Replies in N-player Games by Genetic Algorithms", abstract = "An iterative algorithm is proposed and tested in Cournot Game models, which is based on the convergence of sequential best responses and the utilization of a genetic algorithm for determining each player-s best response to a given strategy profile of its opponents. An extra outer loop is used, to address the problem of finite accuracy, which is inherent in genetic algorithms, since the set of feasible values in such an algorithm is finite. The algorithm is tested in five Cournot models, three of which have convergent best replies sequence, one with divergent sequential best replies and one with “local NE traps"[14], where classical local search algorithms fail to identify the Nash Equilibrium. After a series of simulations, we conclude that the algorithm proposed converges to the Nash Equilibrium, with any level of accuracy needed, in all but the case where the sequential best replies process diverges.
", keywords = "Best response, Cournot oligopoly, genetic algorithms, Nash equilibrium.", volume = "3", number = "9", pages = "2270-6", }
