Pure Strategy Nash Equilibria Refinement in Bimatrix Games by Using Domination Efficiency along with Maximin and the Superoptimality Rule
DOI:
https://doi.org/10.20535/1810-0546.2018.3.123853Keywords:
Bimatrix game, Nash equilibria, Refinement, Domination efficiency, Maximin, Superoptimality ruleAbstract
Background. Multiple Nash equilibria bring a new problem of selecting amongst them but this problem is solved by refining the equilibria. However, none of the existing refinements can guarantee a single refined Nash equilibrium. In some games, Nash equilibria are nonrefinable.
Objective. For solving the nonrefinability problem of pure strategy Nash equilibria in bimatrix games, the goal is to develop an algorithm which could facilitate in refining the equilibria as much further as possible.
Methods. A Nash equilibria refinement is suggested, which is based on the classical refinement by selecting only efficient equilibria that dominate by their payoffs. The suggested refinement exploits maximin subsequently. The superoptimality rule is involved if maximin fails to produce just a single refined equilibrium.
Results. An algorithm of using domination efficiency along with maximin and the superoptimality rule has been developed for refining Nash equilibria in bimatrix games. The algorithm has 10 definite steps at which the refinement is progressively accomplished. The developed concept of the equilibria refinement does not concern games with payoff symmetry and mirror-like symmetry.
Conclusions. The suggested pure strategy Nash equilibria refinement is a contribution to the equilibria refinement game theory field. The developed algorithm allows selecting amongst nonrefinable Nash equilibria in bimatrix games. It partially removes the uncertainty of equilibria, without going into mixed strategies. There are only two negative cases when the refinement fails. For a case when more than a single refined equilibrium is produced, the superoptimality rule may be used for a player having multiple refined equilibrium strategies but the other player has just a single refined equilibrium strategy.References
N.N. Vorob’yov, Game Theory Fundamentals. Noncooperative Games. Moscow, SU: Nauka, 1984, 496 p.
V.V. Romanuke, “Pure strategies Pareto efficient situations versus pure strategies Nash equilibrium situations by their stochastically constrained payoffs in dyadic game modeling of resources rational usage with alternative choice of action”, Herald of Khmelnytskyi National University. Tech. Sci., no. 6, pp. 140–143, 2014.
D. Friedman, “On economic applications of evolutionary game theory”, J. Evolution. Economics, vol. 8, iss. 1, pp. 15–43, 1998. doi: 10.1007/s001910050054
V.V. Romanuke, “Environment guard model as dyadic three-person game with the generalized fine for the reservoir pollution”, Ecological Safety and Nature Management, iss. 6, pp. 77–94, 2010.
V.V. Romanuke and V.G. Kamburg, “Approximation of isomorphic infinite two-person noncooperative games via variously sampling the players’ payoff functions and reshaping payoff matrices into bimatrix game”, Appl. Comp. Syst. vol. 20, pp. 5–14, 2016. doi: 10.1515/acss-2016-0009
V.V. Romanuke, “Approximation of unit-hypercubic infinite two-sided noncooperative game via dimension-dependent irregular samplings and reshaping the multidimensional payoff matrices into flat matrices for solving the corresponding bimatrix game”, Computer Modelling and New Technologies, vol. 19, no. 3A, pp. 7–16, 2015.
V.V. Romanuke, “Uniform sampling of the infinite noncooperative game on unit hypercube and reshaping ultimately multidimensional matrices of players’ payoff values”, Electrical, Control and Communication Engineering, vol. 8, pp. 13–19, 2015. doi: 10.1515/ecce-2015-0002
S.-C. Suh, “An algorithm for verifying double implementability in Nash and strong Nash equilibria”, Math. Social Sci., vol. 41, iss. 1, pp. 103–110, 2001. doi: 10.1016/S0165-4896(99)00057-8
G. Tian, “Implementation of balanced linear cost share equilibrium solution in Nash and strong Nash equilibria”, J. Public Economics, vol. 76, iss. 2, pp. 239–261, 2000. doi: 10.1016/S0047-2727(99)00041-9
E. Kohlberg and J.-F. Mertens, “On the strategic stability of equilibria”, Econometrica, vol. 54, no. 5, pp. 1003–1037, 1986. doi: 10.2307/1912320
R. Selten, “Reexamination of the perfectness concept for equilibrium points in extensive games”, Int. J. Game Theory, vol. 4, iss. 1, pp. 25–55, 1975. doi: 10.1007/BF01766400
R.B. Myerson, “Refinements of the Nash equilibrium concept”, Int. J. Game Theory, vol. 7, iss. 2, pp. 73–80, 1978. doi: 10.1007/BF01753236
E. van Damme, “A relation between perfect equilibria in extensive form games and proper equilibria in normal form games”, Int. J. Game Theory, vol. 13, iss. 1, pp. 1–13, 1984. doi: 10.1007/BF01769861
D. Fudenberg and J. Tirole, “Perfect Bayesian equilibrium and sequential equilibrium”, J. Economic Theory, vol. 53, iss. 2, pp. 236–260, 1991. doi: 10.1016/0022-0531(91)90155-W
D. Gerardi and R.B. Myerson, “Sequential equilibria in Bayesian games with communication”, Games and Economic Behavior, vol. 60, iss. 1, pp. 104–134, 2007. doi: 10.1016/j.geb.2006.09.006
J.-F. Mertens, “Two examples of strategic equilibrium”, Games and Economic Behavior, vol. 8, iss. 2, pp. 378–388, 1995. doi: 10.1016/S0899-8256(05)80007-7
E. Bajoori et al., “Perfect equilibrium in games with compact action spaces”, Games and Economic Behavior, vol. 82, pp. 490–502, 2013. doi: 10.1016/j.geb.2013.08.002
V.V. Romanuke, “Recommendations on transacting the finite noncooperative game with invisible horizon of plays by NE-strategy”, Science and Economics, iss. 2 (18), pp. 255–262, 2010.
V.V. Romanuke, “Convergence and estimation of the process of computer implementation of the optimality principle in matrix games with apparent play horizon”, J. Automation Inform. Sci.s, vol. 45, iss. 10, pp. 49–56, 2013. doi: 10.1615/JAutomatInfScien.v45.i10.70
V.V. Romanuke, “The tactics of the pure strategies selecting as a theoretic groundwork for investigating the efficiency of diverse ways of the optimal mixed strategies realization”, Naukovi Visti NTUU KPI, no. 3, pp. 61–68, 2008.
V.V. Romanuke, “Formulation of an optimality principle in the elementary antagonistic game without saddle point by incomplete realization of optimal mixed strategies”, Herald of Khmelnytskyi National University. Tech. Sci., no. 2, vol. 2, pp. 218–222, 2007.
J.C. Harsanyi and R. Selten, A General Theory of Equilibrium Selection in Games. Cambridge, UK: The MIT Press, 1988, 365 p.
V.V. Romanuke, “Finite approximation of unit-hypercubic infinite noncooperative game via dimension-dependent irregular samplings and reshaping the player’s payoffs into line array for simplification and speedup”, Visnyk of Zaporizhzhya National University. Phys. Math. Sci., no. 2, pp. 201–221, 2015.
V. Scalzo, “Pareto efficient Nash equilibria in discontinuous games”, Economics Lett., vol. 107, iss. 3, pp. 364–365, 2010. doi: 10.1016/j.econlet.2010.03.010
T. Kumano, “Nash implementation of constrained efficient stable matchings under weak priorities”, Games and Economic Behavior, vol. 104, pp. 230–240, 2017. doi: 10.1016/j.geb.2017.04.003
W.J. Luhan et al., “Real-time tacit bargaining, payoff focality, and coordination complexity: Experimental evidence”, Games and Economic Behavior, vol. 102, pp. 687–699, 2017. doi: 10.1016/j.geb.2017.02.016
I. Guo and M. Rutkowski, “Discrete time stochastic multi-player competitive games with affine payoffs”, Stochastic Processes and their Applications, vol. 126, iss. 1, pp. 1–32, 2016. doi: 10.1016/j.spa.2015.07.013
V.V. Romanuke, “Determining and applying the set of superoptimal pure strategies in some antagonistic games with nonempty set of saddle points in pure strategies”, Visnyk of Zaporizhzhya National University. Phys. Math. Sci., no. 2, pp. 120–125, 2010.
V.V. Romanuke, “Superoptimal mixed strategies in antagonistic games as the advantaged subset of the optimal mixed strategies set”, Bulletin of Donetsk National University. Ser. А. Natural Sci., no. 2, pp. 289–298, 2010.
P. Prokopovych and N.C. Yannelis, “On the existence of mixed strategy Nash equilibria”, J. Math. Economics, vol. 52, pp. 87–97, 2014. doi: 10.1016/j.jmateco.2014.04.002
J.R. Marden, “Selecting efficient correlated equilibria through distributed learning”, Games and Economic Behavior, vol. 106, pp. 114–133, 2017. doi: 10.1016/j.geb.2017.09.007
A. Koh, “An evolutionary algorithm based on Nash dominance for equilibrium problems with equilibrium constraints”, Appl. Soft Computing, vol. 12, iss. 1, pp. 161–173, 2012. doi: 10.1016/j.asoc.2011.08.056
P. Barelli and J. Duggan, “Purification of Bayes Nash equilibrium with correlated types and interdependent payoffs”, Games and Economic Behavior, vol. 94, pp. 1–14, 2015. doi: 10.1016/j.geb.2015.08.005
B.S.R. Pradelski and H. Peyton Young, “Learning efficient Nash equilibria in distributed systems”, Games and Economic Behavior, vol. 75, iss. 2, pp. 882–897, 2012. doi: 10.1016/j.geb.2012.02.017
E. Boros et al., “Nash-solvable two-person symmetric cycle game forms”, Discrete Appl. Math., vol. 159, iss. 15, pp. 1461–1487, 2011. doi: 10.1016/j.dam.2011.05.011
V.V. Romanuke, “Sampling individually fundamental simplexes as sets of players’ mixed strategies in finite noncooperative game for applicable approximate Nash equilibrium situations with possible concessions”, J. Inform. Organizational Sci., vol. 40, no. 1, pp. 105–143, 2016.
P. Bouyer et al., “Nash equilibria in symmetric graph games with partial observation”, Information and Computation, vol. 254, p. 2, pp. 238–258, 2017. doi: 10.1016/j.ic.2016.10.010
M. Bravo and P. Mertikopoulos, “On the robustness of learning in games with stochastically perturbed payoff observations”, Games and Economic Behavior, vol. 103, pp. 41–66, 2017. doi: 10.1016/j.geb.2016.06.004
S. Rachmilevitch, “Approximate equilibria in strongly symmetric games”, J. Math. Economics, vol. 66, pp. 52–57, 2016. doi: 10.1016/j.jmateco.2016.07.003
M. Fey, “Symmetric games with only asymmetric equilibria”, Games and Economic Behavior, vol. 75, iss. 1, pp. 424–427, 2012. doi: 10.1016/j.geb.2011.09.008
I. Heloulou et al., “Automatic multi-objective clustering based on game theory”, Expert Systems with Applications, vol. 67, pp. 32–48, 2017. doi: 10.1016/j.eswa.2016.09.008
W. Grauberger and A. Kimms, “Computing approximate Nash equilibria in general network revenue management games”, Eur. J. Operational Res., vol. 237, iss. 3, pp. 1008–1020, 2014. doi: 10.1016/j.ejor.2014.02.045
V.V. Romanuke, “Approximate equilibrium situations with possible concessions in finite noncooperative game by sampling irregularly fundamental simplexes as sets of players’ mixed strategies”, J. Uncertain Systems, vol. 10, no. 4, pp. 269–281, 2016.
C. Daskalakis et al., “A note on approximate Nash equilibria”, Theor. Comp. Sci., vol. 410, iss. 17, pp. 1581–1588, 2009. doi: 10.1016/j.tcs.2008.12.031
C. Daskalakis and C. H. Papadimitriou, “Approximate Nash equilibria in anonymous games”, J. Economic Theory, vol. 156, pp. 207–245, 2015. doi: 10.1016/j.jet.2014.02.002
Downloads
Published
Issue
Section
License
Copyright (c) 2018 Igor Sikorsky Kyiv Polytechnic Institute
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under CC BY 4.0 that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work
