Uniform Sampling of the Infinite Noncooperative Game on Unit Hypercube and Reshaping Ultimately Multidimensional Matrices of Player’s Payoff Values

Vadim Romanuke

doi:10.1515/ecce-2015-0002

Uniform Sampling of the Infinite Noncooperative Game on Unit Hypercube and Reshaping Ultimately Multidimensional Matrices of Player’s Payoff Values

Authors

Vadim Romanuke Khmelnitskiy National University

DOI:

https://doi.org/10.1515/ecce-2015-0002

Keywords:

Systems, man, and cybernetics, Decision theory, Computational efficiency, Mathematical model

Abstract

The paper suggests a method of obtaining an approximate solution of the infinite noncooperative game on the unit hypercube. The method is based on sampling uniformly the players’ payoff functions with the constant step along each of the hypercube dimensions. The author states the conditions for a sufficiently accurate sampling and suggests the method of reshaping the multidimensional matrix of the player’s payoff values, being the former player’s payoff function before its sampling, into a matrix with minimally possible number of dimensions, where also maintenance of one-to-one indexing has been provided. Requirements for finite NE-strategy from NE (Nash equilibrium) solution of the finite game as the initial infinite game approximation are given as definitions of the approximate solution consistency. The approximate solution consistency ensures its relative independence upon the sampling step within its minimal neighborhood or the minimally decreased sampling step. The ultimate reshaping of multidimensional matrices of players’ payoff values to the minimal number of dimensions, being equal to the number of players, stimulates shortened computations.

References

M. J. Osborne, An introduction to game theory. Oxford: Oxford University Press, Incorporated, 2003.

J. C. Harsanyi and R. Selten, A General Theory of Equilibrium Selection in Games. Cambridge: The MIT Press, 1988.

V. G. Suzdal, Game theory for Fleet. Moscow: Voyenizdat, 1976 (in Russian).

R. Calvert, M. D. McCubbins, and B. R. Weingast, “A Theory of Political Control and Agency Discretion,” American J. of Political Science, vol. 33, no. 3, 1989, pp. 588–611. http://dx.doi.org/10.2307/2111064

D. Friedman, “On economic applications of evolutionary game theory,” J. of Evolutionary Economics, vol. 8, iss. 1, 1998, pp. 15–43. http://dx.doi.org/10.1007/s001910050054

N. N. Vorobyov, Game theory for economist-cyberneticians. Moscow: Nauka, 1985 (in Russian).

V. V. Romanuke, “A theorem on continuum of the projector optimal behaviors in antagonistic model of building resources distribution under segment uncertainties with incorrectly pre-evaluated one left and one right endpoints,” Problems of tribology, no. 4, 2011, pp. 52–55.

D. Gasior and M. Drwal, “Pareto-optimal Nash equilibrium in capacity allocation game for self-managed networks,” Computer Networks, vol. 57, iss. 14, 2013, pp. 2817–2832. http://dx.doi.org/10.1016/j.comnet.2013.06.012

M. Kucukmehmetoglu, “An integrative case study approach between game theory and Pareto frontier concepts for the transboundary water resources allocations,” J. of Hydrology, vol. 450–451, 2012, pp. 308–319.

N. N. Vorobyov, Game theory fundamentals. Noncooperative games. Moscow: Nauka, 1984 (in Russian).

G. Owen, Game theory. Philadelphia – London – Toronto: W. B. Saunders Company, 1968.

G. Stoltz and G. Lugosi, “Learning correlated equilibria in games with compact sets of strategies,” Games and Economic Behavior, vol. 59, iss. 1, 2007, pp. 187–208. http://dx.doi.org/10.1016/j.geb.2006.04.007

F. Tao et al., “CLPS-GA: A case library and Pareto solution-based hybrid genetic algorithm for energy-aware cloud service scheduling,” Applied Soft Computing, vol. 19, 2014, pp. 264–279. http://dx.doi.org/10.1016/j.asoc.2014.01.036

V. Scalzo, “Pareto efficient Nash equilibria in discontinuous games,” Economics Letters, vol. 107, iss. 3, 2010, pp. 364–365. http://dx.doi.org/10.1016/j.econlet.2010.03.010

E. Kohlberg and J.-F. Mertens, “On the Strategic Stability of Equilibria,” Econometrica, vol. 54, no. 5, 1986, pp. 1003–1037.

R. Selten, “Reexamination of the perfectness concept for equilibrium points in extensive games,” Int. J. of Game Theory, vol. 4, iss. 1, 1975, pp. 25–55. http://dx.doi.org/10.1007/BF01766400

R. B. Myerson, “Refinements of the Nash equilibrium concept,” Int. J. of Game Theory, vol. 7, iss. 2, 1978, pp. 73–80. http://dx.doi.org/10.1007/BF01753236

E. van Damme, “A relation between perfect equilibria in extensive form games and proper equilibria in normal form games,” Int. J. of Game Theory, vol. 13, iss. 1, 1984, pp. 1–13. http://dx.doi.org/10.1007/BF01769861

R. J. Aumann, “Subjectivity and correlation in randomized strategies,” J. of Mathematical Economics, vol. 1, iss. 1, 1974, pp. 67–96. http://dx.doi.org/10.1016/0304-4068(74)90037-8

D. Fudenberg and J. Tirole, “Perfect Bayesian equilibrium and sequential equilibrium,” J. of Economic Theory, vol. 53, iss. 2, 1991, pp. 236–260. http://dx.doi.org/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, 2007, pp. 104–134. http://dx.doi.org/10.1016/j.geb.2006.09.006

J.-F. Mertens, “Two examples of strategic equilibrium,” Games and Economic Behavior, vol. 8, iss. 2, 1995, pp. 378–388. http://dx.doi.org/10.1016/S0899-8256(05)80007-7

E. Bajoori, J. Flesch, and D. Vermeulen, “Perfect equilibrium in games with compact action spaces,” Games and Economic Behavior, vol. 82, 2013, pp. 490–502. http://dx.doi.org/10.1016/j.geb.2013.08.002

P. Battigalli, “Strategic Independence and Perfect Bayesian Equilibria,” J. of Economic Theory, vol. 70, iss. 1, 1996, pp. 201–234. http://dx.doi.org/10.1006/jeth.1996.0082

C. C. Moallemi, B. Park, and B. Van Roy, “Strategic execution in the presence of an uninformed arbitrageur,” J. of Financial Markets, vol. 15, iss. 4, 2012, pp. 361–391. http://dx.doi.org/10.1016/j.finmar.2011.11.002

B. W. Rogers, T. R. Palfrey, and C. F. Camerer, “Heterogeneous quantal response equilibrium and cognitive hierarchies,” J. of Economic Theory, vol. 144, iss. 4, 2009, pp. 1440–1467. http://dx.doi.org/10.1016/j.jet.2008.11.010

R. Golman, “Quantal response equilibria with heterogeneous agents,” J. of Economic Theory, vol. 146, iss. 5, 2011, pp. 2013–2028. http://dx.doi.org/10.1016/j.jet.2011.06.007

M. Shimoji, “Outcome-equivalence of self-confirming equilibrium and Nash equilibrium,” Games and Economic Behavior, vol. 75, iss. 1, 2012, pp. 441–447. http://dx.doi.org/10.1016/j.geb.2011.09.010

A. Gamba, “Learning and evolution of altruistic preferences in the Centipede Game,” J. of Economic Behavior & Organization, vol. 85, 2013, pp. 112–117. http://dx.doi.org/10.1016/j.jebo.2012.11.009

S.-C. Suh, “An algorithm for verifying double implementability in Nash and strong Nash equilibria,” Mathematical Social Sciences, vol. 41, iss. 1, 2001, pp. 103–110. http://dx.doi.org/10.1016/S0165-4896(99)00057-8

G. Tian, “Implementation of balanced linear cost share equilibrium solution in Nash and strong Nash equilibria,” J. of Public Economics, vol. 76, iss. 2, 2000, pp. 239–261. http://dx.doi.org/10.1016/S0047-2727(99)00041-9

S. Castro and A. Brandão, “Existence of a Markov perfect equilibrium in a third market model,” Economics Letters, vol. 66, iss. 3, 2000, pp. 297–301. http://dx.doi.org/10.1016/S0165-1765(99)00208-6

H. Haller and R. Lagunoff, “Markov Perfect equilibria in repeated asynchronous choice games,” J of Mathematical Economics, vol. 46, iss. 6, 2010, pp. 1103–1114. http://dx.doi.org/10.1016/j.jmateco.2009.09.003

D. Han et al., “An improved two-step method for solving generalized Nash equilibrium problems,” European J. of Operational Research, vol. 216, iss. 3, 2012, pp. 613–623. http://dx.doi.org/10.1016/j.ejor.2011.08.008

X. Chen and X. Deng, “Recent development in computational complexity characterization of Nash equilibrium,” Computer Science Review, vol. 1, iss. 2, 2007, pp. 88–99. http://dx.doi.org/10.1016/j.cosrev.2007.09.002

L. Browning and A. M. Colman, “Evolution of coordinated alternating reciprocity in repeated dyadic games,” J. of Theoretical Biology, vol. 229, iss. 4, 2004, pp. 549–557. http://dx.doi.org/10.1016/j.jtbi.2004.04.032

C. E. Lemke and J. T. Howson, “Equilibrium points of bimatrix games,” SIAM Journal on Applied Mathematics, vol. 12, no. 2, 1964, pp. 413–423. http://dx.doi.org/10.1137/0112033

N. Nisan et al., Algorithmic Game Theory. Cambridge: Cambridge University Press, 2007. http://dx.doi.org/10.1017/CBO9780511800481

A. S. Belenky, “A 3-person game on polyhedral sets,” Computers & Mathematics with Applications, vol. 28, iss. 5, 1994, pp. 53–56.

J. H. Dshalalow, “On multivariate antagonistic marked point processes,” Mathematical and Computer Modelling, vol. 49, iss. 3–4, 2009, pp. 432–452.

N. S. Kukushkin, “Nash equilibrium in compact-continuous games with a potential,” Int. J. of Game Theory, vol. 40, iss. 2, 2011, pp. 387–392. http://dx.doi.org/10.1007/s00182-010-0261-7

A. Meirowitz, “On the existence of equilibria to Bayesian games with non-finite type and action spaces,” Economics Letters, vol. 78, iss. 2, 2003, pp. 213–218. http://dx.doi.org/10.1016/S0165-1765(02)00216-1

H. W. Kuhn, “An algorithm for equilibrium points in bimatrix games,” in Proc. Nat. Acad. Sci., vol. 47, 1961, pp. 1657–1662. http://dx.doi.org/10.1073/pnas.47.10.1657

S. C. Kontogiannis, P. N. Panagopoulou, and P. G. Spirakis, “Polynomial algorithms for approximating Nash equilibria of bimatrix games,” Theoretical Computer Science, vol. 410, iss. 17, 2009, pp. 1599–1606. http://dx.doi.org/10.1016/j.tcs.2008.12.033

V. V. Romanuke, “The principle of optimality problem in the elementary matrix game with the finite number of plays,” Bulletin of Khmelnitskiy National University. Technical Sciences, no. 1, 2007, pp. 226–230.

V. V. Romanuke, “Method of realizing the optimal mixed strategies in the matrix game with the empty set of saddle points in pure strategies with the known number of the game plays,” Research bulletin of National Technical University of Ukraine “Kyiv Polytechnic Institute”, no. 2, 2009, pp. 45–52 (in Ukrainian).

V. V. Romanuke, “Method of practicing the optimal mixed strategy with innumerable set in its spectrum by unknown number of plays,” Measuring and Computing Devices in Technological Processes, no. 2, 2008, pp. 196–203.

V. V. Romanuke, “A program function representation for implementing the method of practicing the optimal mixed strategy with innumerable spectrum by unknown number of plays,” Optoelectronic Information-Power Technologies, no. 1, 2010, pp. 28–37.