Acyclic-and-Asymmetric Payoff Triplet Refinement of Pure Strategy Efficient Nash Equilibria in Trimatrix Games by Maximinimin and Superoptimality
DOI:
https://doi.org/10.20535/1810-0546.2018.4.131696Keywords:
Trimatrix game, Efficient Nash equilibria, Refinement, Maximinimin, Superoptimality ruleAbstract
Background. A problem of selecting amongst efficient Nash equilibria is solved by refining them. The existing approaches to refining do not guarantee that the refined efficient Nash equilibrium will be single. Nevertheless, a novel approach to refining pure strategy efficient Nash equilibria in bimatrix games suggested before exploits the maximin and superoptimality rule that, at least partially, remove the uncertainty of the equilibria.
Objective. The goal of the article is to develop the bimatrix game approach expanding it over trimatrix games for refining efficient Nash equilibria as much further as possible.
Methods. An efficient Nash equilibria refinement is suggested for trimatrix games, which is based on expanding the refinement approach for bimatrix games, exploiting the maximinimin and superoptimality. Games with acyclic-and-asymmetric payoff triplets are only considered.
Results. Series of trimatrix game simulations allow concluding on that whereas the refinement is needed in about between 33 % and 65 % of trimatrix games where players possess between 4 to 12 pure strategies (this rate increases as the game size increases), it is perfectly accomplished to a single metaequilibrium in roughly between 46 % and 52 % of those cases (this rate decreases as the game size increases), using maximinimin only, without the superoptimality rule. Exploiting the maximin, expanded to the maximinimin principle, and superoptimality using now double-summing, the main work for the refinement is off the maximinimin principle.
Conclusions. An algorithm for the developed approach refinement in trimatrix games is very simple. It consists of four generalized items. Although a total fail of the refinement is not excluded, the aggregate efficiency of removing the uncertainty of equilibria by the maximinimin principle and superoptimality rule seems satisfactory.References
[1] J. C. Harsanyi and R. Selten, A general theory of equilibrium selection in games, Cambridge, The MIT Press, 1988, 365 p.
[2] R. B. Myerson, “Refinements of the Nash equilibrium concept”, International Journal of Game Theory, vol. 7, iss. 2, pp. 73 — 80, 1978.
https://doi.org/10.1007/BF01753236
[3] S. Belhaiza et al., “On proper refinement of Nash equilibria for bimatrix games”, Automatica, vol. 48, iss. 2, pp. 297 — 303, 2012.
https://doi.org/10.1016/j.automatica.2011.07.013
[4] C. Meroni and C. Pimienta, “The structure of Nash equilibria in Poisson games”, Journal of Economic Theory, vol. 169, pp. 128 — 144, 2017.
https://doi.org/10.1016/j.jet.2017.02.003
[5] D. Fudenberg and J. Tirole, “Perfect Bayesian equilibrium and sequential equilibrium”, Journal of Economic Theory, vol. 53, iss. 2, pp. 236 — 260, 1991.
https://doi.org/10.1016/0022-0531(91)90155-W
[6] 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.
https://doi.org/10.1016/j.geb.2006.09.006
[7] V. V.Romanuke, “Pure strategy Nash equilibria refinement in bimatrix games by using domination efficiency along with maximin and the superoptimality rule”, Research Bulletin of the National Technical University of Ukraine “Kyiv Polytechnic Institute”. — 2018. — № 2. — С. ХХ —ХХ.
[8] M. Fey, “Symmetric games with only asymmetric equilibria”, Games and Economic Behavior, vol. 75, iss. 1, pp. 424 — 427, 2012.
https://doi.org/10.1016/j.geb.2011.09.008
[9] G. Nöldeke and J. Peña, “The symmetric equilibria of symmetric voter participation games with complete information”, Games and Economic Behavior, vol. 99, pp. 71 — 81, 2016.
https://doi.org/10.1016/j.geb.2016.06.016
[10] W. Leinfellner and E. Köhler, Game theory, experience, rationality. foundations of social sciences, economics and ethics in honor of John C. Harsanyi, Springer, Netherlands, 1998, 461 p.
https://doi.org/10.1007/978-94-017-1654-3
[11] N. N. Vorob’yov, Game theory fundamentals. Noncooperative games, Moscow, Nauka, 1984, 496 p.
[12] 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 ZaporizhzhyaNational University. Physical and Mathematical Sciences, no. 2, pp. 120 — 125, 2010.
[13] V. V. Romanuke,“Superoptimal mixed strategies in antagonistic games as the advantaged subset of the optimal mixed strategies set”, Bulletin of Donetsk National University. Series А. Natural Sciences, no. 2, pp. 289 — 298, 2010.
[14] R. Selten, “Reexamination of the perfectness concept for equilibrium points in extensive games”, International Journal of Game Theory, vol. 4, iss. 1, pp. 25 — 55, 1975.
https://doi.org/10.1007/BF01766400
[15] 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. Technical sciences,no. 6, pp. 140 — 143, 2014.
[16] T. Kumano, “Nash implementation of constrained efficient stable matchings under weak priorities”, Games and Economic Behavior, vol. 104, pp. 230 — 240, 2017.
https://doi.org/10.1016/j.geb.2017.04.003
[17] V. Scalzo, “Pareto efficient Nash equilibria in discontinuous games”, Economics Letters, vol. 107, iss. 3, pp. 364 — 365, 2010.
https://doi.org/10.1016/j.econlet.2010.03.010
[18] J. R. Marden, “Selecting efficient correlated equilibria through distributed learning”, Games and Economic Behavior, vol. 106, pp. 114 — 133, 2017.
https://doi.org/10.1016/j.geb.2017.09.007
[19] 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.
https://doi.org/10.1016/j.geb.2012.02.017
[20] S. Rachmilevitch, “Approximate equilibria in strongly symmetric games”, Journal of Mathematical Economics, vol. 66, pp. 52 — 57, 2016.
https://doi.org/10.1016/j.jmateco.2016.07.003
[21] V. V. Romanuke,“Approximate equilibrium situations with possible concessions in finite noncooperative game by samplingirregularly fundamental simplexes as sets of players’ mixed strategies”,Journal of Uncertain Systems, vol. 10, no. 4, pp. 269 — 281, 2016.
[22] 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.
[23] E. Boros et al., “Nash-solvable two-person symmetric cycle game forms”, Discrete Applied Mathematics, vol. 159, iss. 15, pp. 1461 — 1487, 2011.
https://doi.org/10.1016/j.dam.2011.05.011
[24] P. Bouyer et al., “Nash equilibria in symmetric graph games with partial observation”, Information and Computation, vol. 254, p. 2, pp. 238 — 258, 2017.
https://doi.org/10.1016/j.ic.2016.10.010
[25] V. V. Romanuke, “Minimaximax approach for finding optimal decisions’ subset regarding changes of the loss function”,Bulletin of V. Karazin Kharkiv National University. Series “Mathematical Modelling. Information Technology. Automated Control Systems”, iss. 33, pp. 81 — 89, 2017.
[26] V. V. Romanuke, “Finding an optimal decisions’ subset by minimaximax regret criterion regarding instability of the decision function”,Research Bulletin of the National Technical University of Ukraine “Kyiv Polytechnic Institute”, no.5,pp. 35 — 40, 2017.
https://doi.org/10.20535/1810-0546.2017.5.105535
[27]V. V. Romanuke, “Formulation of an optimality principle in the elementary antagonistic game without saddle point by incomplete realization of optimal mixed strategies”, HeraldofKhmelnytskyinationaluniversity. Technicalsciences, no. 2, vol. 2, pp. 218 — 222, 2007.
[28] 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.
https://doi.org/10.1016/j.geb.2015.08.005
[29] W. Grauberger and A. Kimms, “Computing approximate Nash equilibria in general network revenue management games”, European Journal of Operational Research, vol. 237, iss. 3, pp. 1008 — 1020, 2014.
https://doi.org/10.1016/j.ejor.2014.02.045
[30] P. Prokopovych and N. C. Yannelis, “On the existence of mixed strategy Nash equilibria”, Journal of Mathematical Economics, vol. 52, pp. 87 — 97, 2014.
https://doi.org/10.1016/j.jmateco.2014.04.002
[31] 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.
https://doi.org/10.1016/j.geb.2016.06.004
[32] 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”, Journal of Information and Organizational Sciences, vol. 40, no. 1, pp. 105 — 143, 2016.
[33]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”, NaukoviVisti NTUU “KPI”, no. 3, pp. 61 — 68, 2008.
[34] C. Daskalakis et al., “A note on approximate Nash equilibria”, Theoretical Computer Science, vol. 410, iss. 17, pp. 1581 — 1588, 2009.
https://doi.org/10.1016/j.tcs.2008.12.031
[35] C. Daskalakis and C. H. Papadimitriou, “Approximate Nash equilibria in anonymous games”, Journal of Economic Theory, vol. 156, pp. 207 — 245, 2015.
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
