Finite uniform approximation of zero-sum games defined on a product of staircase-function continuous spaces

Vadim Romanuke


A method of finite approximation of zero-sum games defined on a product of staircase-function continuous spaces is presented. The method consists in uniformly sampling the player’s pure strategy value set, solving “smaller” matrix games, each defined on a subinterval where the pure strategy value is constant, and stacking their solutions if they are consistent. The stack of the “smaller” matrix game solutions is an approximate solution to the initial staircase game. The (weak) consistency, equivalent to the approxi-mate solution acceptability, is studied by how much the payoff and optimal situation change as the sampling density minimally increases. The consistency is decomposed into the payoff, optimal strategy support cardinality, optimal strategy sampling density, and support probability consistency. The most important parts are the payoff consistency and optimal strategy support cardinality (weak) consistency. However, it is practically reasonable to consider a relaxed payoff consistency, by which the game optimal value change in an appropriate approximation may grow at most by epsilon as the sampling density minimally increases. The weak consistency itself is a relaxation to the consistency, where the minimal decrement of the sampling density is ignored.

Full Text:



J.H. Dshalalow, On multivariate antagonistic marked point processes, Mathematical and Computer Modelling 49 (2009), no. 3-4, 432-452. DOI: 10.1016/j.mcm.2008.07.029

D. Friedman, On economic applications of evolutionary game theory, Journal of Evolutionary Economics 8 (1998), no. 1, 15-43. DOI: 10.1007/s001910050054

M. C. Gelhausen, P. Berster, and D. Wilken, Airport Capacity Constraints and Strategies for Mitigation, Cambridge, Massachusetts, USA, Academic Press, 2019.

C.E. Lemke and J.T. Howson, Equilibrium points of bimatrix games, SIAM Journal on Applied Mathematics 12 (1964), no. 2, 413-423. 10.1137/0112033

F. Loesche and T. Ionescu, Mindset and Einstellung E_ect. In: Encyclopedia of Creativity, Academic Press (2020), 174-178.

S. Mannor and N. Shimkin, Regret minimization in repeated matrix games with variable stage duration, Games and Economic Behavior 63 (2008), no. 1, 227-258. DOI:10.1016/j.geb.2007.07.006

A. Neme and L. Quintas, Nash equilibrium strategies in repeated games with and without cost of implementation, Operations Research Letters 12 (1992), no. 2, 111-115. DOI: 10.1016/0167-6377(92)90072-B

N. Nisan, T. Roughgarden, _E. Tardos, and V. V. Vazirani, Algorithmic Game Theory, Cambridge, UK, Cambridge University Press, 2007.

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

T. Parthasarathy, On games over the unit square, SIAM Journal on Applied Mathematics 19 (1970), no. 2, 473-476. DOI: 10.1137/0119047

V.V. Romanuke, Theory of Antagonistic Games, Lviv, New World - 2000, 2010.

V.V. Romanuke, Approximation of unit-hypercubic infinite antagonistic game via dimension-dependent irregular samplings and reshaping the payoffs into at matrix wherewith to solve the matrix game, Journal of Information and Organizational Sciences 38 (2014), no. 2, 125-143.

V.V. Romanuke, Discretization of continuum antagonistic game on unit hypercube and transformation of multidimensional matrix for solving of the corresponding matrix game, Journal of Automation and Information Sciences 47 (2015), no. 2, 77-86. DOI: 10.1615/JAutomatInf-Scien.v47.i2.80

V.V. Romanuke, Finite approximation of continuous noncooperative two-person games on a product of linear strategy functional spaces, Journal of Mathematics and Applications 43 (2020), 123-138. DOI: 10.7862/rf.2020.9

J. Tanimoto and H. Sagara, A study on emergence of alternating reciprocity in a 2x2 game with 2-length memory strategy, Biosystems 90 (2007), no. 3, 728-737. DOI: 10.1016/j.biosystems.2007.03.001

N. N. Vorob'yov, Foundations of Game Theory. Noncooperative Games, Moscow, Nauka, 1984.

N. N. Vorob'yov, Game Theory for Economists-Cyberneticists, Moscow, Nauka, 1985.

A. Wolitzky, Indeterminacy of reputation e_ects in repeated games with contracts, Games and Economic Behavior 73 (2011), no. 2, 595-607. DOI: 10.1016/j.geb.2011.02.009

J. Yang, Y.-S. Chen, Y. Sun, H.-X. Yang, and Y. Liu, Group formation in the spatial public goods game with continuous strategies, Physica A: Statistical Mechanics and its Applications 505 (2018), 737-743. DOI: 10.1016/j.physa.2018.03.057

E. B. Yanovskaya, Minimax theorems for games on the unit square, Probability theory and its applications 9 (1964), no. 3, 554-555.

E. B. Yanovskaya, Antagonistic games played in function spaces, Lithuanian Mathematical Bulletin 3 (1967), 547-557.

Z. Zhou and Z. Jin, Optimal equilibrium barrier strategies for time-inconsistent dividend problems in discrete time, Insurance: Mathematics and Economics 94 (2020), 100-108. DOI: 10.1016/j.insmatheco.2020.06.011