?
A convex programming-based algorithm for mean payoff stochastic games with perfect information
Optimization Letters. 2017. Vol. 11. No. 8. P. 1499–1512.
Boros E., Elbassioni K., Gurvich V., Makino K.
We consider two-person zero-sum stochastic mean payoff games with perfect information, or BWR-games, given by a digraph (Formula presented.), with local rewards (Formula presented.), and three types of positions: black (Formula presented.), white (Formula presented.), and random (Formula presented.) forming a partition of V. It is a long-standing open question whether a polynomial time algorithm for BWR-games exists, even when (Formula presented.). In fact, a pseudo-polynomial algorithm for BWR-games would already imply their polynomial solvability. In this short note, we show that BWR-games can be solved via convex programming in pseudo-polynomial time if the number of random positions is a constant.
Keywords: Stochastic gamesmean payoffConvex programmingPerfect informationPseudo-polynomial algorithm
Publication based on the results of:
Gurvich V., Naumova M., Annals of Operations Research 2023 No. 336 P. 1905–1927
Added: August 7, 2024
Zuazo-Garin P., Journal of Mathematical Economics 2017 Vol. 71 P. 135–151
In everyday economic interactions, it is not clear whether each agent’s sequential choices are visible to other participants or not: agents might be deluded about others’ ability to acquire, interpret or keep track of data. Following this idea, this paper introduces uncertainty about players’ ability to observe each others’ past choices in extensive-form games. In ...
Added: September 14, 2020
Averboukh Y., SIAM Journal on Control and Optimization 2016 Vol. 54 No. 5 P. 2629–2649
The paper is concerned with a zero-sum continuous-time stochastic differential game with a dynamics controlled by a Markov process and a terminal payoff. The value function of the original game is estimated using the value function of a model game. The dynamics of the model game differs from the original one. The general result applied ...
Added: April 17, 2020
Shvedov A. S., Mathematical notes 2020 Vol. 107 No. 4 P. 679–686
Noncooperative discounted stochastic n-person games are considered; the payoffs at each step are represented by trapezoidal fuzzy numbers. The existence of stationary Nash equilibrium strategies is proved. ...
Added: April 9, 2020
Shvedov A. S., Математические заметки 2020 Т. 107 № 4 С. 623–632
Рассматриваются некооперативные дисконтированные стохастические игры с n участниками, при этом выигрыши на каждом шаге представляются трапецоидальными нечеткими числами. Доказывается существование стационарных равновесных по Нэшу стратегий. ...
Added: April 9, 2020
Boros E., Elbassioni K., Gurvich V. et al., Information and Computation 2019 Vol. 267 P. 74–95
We consider two-person zero-sum stochastic mean payoff games with perfect information, or BWR-games, given by a digraph G=(V,E), with local rewards r:E→Z, and three types of positions: black VB, white VW, and random VR forming a partition of V. It is a long-standing open question whether a polynomial time algorithm for BWR-games exists, or not, even when |VR|=0. In fact, a pseudo-polynomial algorithm for BWR-games ...
Added: December 9, 2019
Gurvich V., Boros E., Milanič M. et al., Discrete Applied Mathematics 2018 Vol. 243 P. 21–38
We give an example of a three-person deterministic graphical game that has no Nash equilibrium in pure stationary strategies. The game has seven positions, four outcomes (a unique cycle and three terminal positions), and its normal form is of size 2×2×4 only. Thus, the example strengthens significantly the one obtained in 2014 by Gurvich and Oudalov; the ...
Added: October 10, 2018
Levando D. V., / NRU Higher School of Economics. Series WP BRP "Economics/EC". 2017. No. WP BRP 157/EC/2017.
The paper defines a family of nested non-cooperative simultaneous finite games to study coalition structure formation with intra and inter-coalition externalities. The novelties of the paper are: a definition of every games embeds a coalition structure formation mechanism. Every game has two outcomes - an allocation of players over coalitions and a payoff profile for ...
Added: February 3, 2017
Gurvich V., Boros E., Elbassioni K. et al., , in: Combinatorial Optimization and Applications - 8th International Conference, COCOA 2014, Wailea, Maui, HI, USA, December 19-21, 2014, Proceedings.: Springer, 2014. P. 694–709.
We suggest a new algorithm for two-person zero-sum undiscounted stochastic games focusing on stationary strategies. Given a positive real ϵϵ, let us call a stochastic game ϵϵ-ergodic, if its values from any two initial positions differ by at most ϵϵ. The proposed new algorithm outputs for every ϵ>0ϵ>0 in finite time either a pair of stationary strategies for the two ...
Added: October 22, 2016
Gurvich V., Boros E., Elbassioni K. et al., , in: 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), Leibniz International Proceedings in Informatics (LIPIcs)Vol. 30.: Dagstuhl: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2015. P. 103–115.
We consider finite Markov decision processes (MDPs) with undiscounted total effective payoff. We show that there exist uniformly optimal pure stationary strategies that can be computed by solving a polynomial number of linear programs. We apply this result to two-player zero-sum stochastic games with perfect information and undiscounted total effective payoff, and derive the existence ...
Added: October 22, 2016
Gurvich V., Oudalov V., Discrete Applied Mathematics 2014 Vol. 167 P. 131–143
We study existence of Nash equilibria (NE) in pure stationary strategies in n-person positional games with no moves of chance, with perfect information, and with the mean or total effective cost function.
We construct a NE-free three-person game with positive local costs, thus disproving the conjecture suggested in Boros and Gurvich (2003). Still, the following four problems ...
Added: October 22, 2016