A convex programming-based algorithm for mean payoff stochastic games with perfect information

Boros E.; Elbassioni K.; V. Gurvich; Makino K.

doi:10.1007/s11590-017-1140-y

Публикации

?

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., Гурвич В. А., 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.

Язык: английский

DOI

Ключевые слова: Stochastic games mean payoff Convex programming Perfect information Pseudo-polynomial algorithm

ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА:

Теоретическая информатика (2017)

On Nash-solvability of n-person graphical games under Markov and a-priori realizations

Гурвич В. А., Naumova M., Annals of Operations Research 2023 No. 336 P. 1905–1927

Добавлено: 7 августа 2024 г.

Uncertain Information Structures and Backward Induction

Суасо Гарин П., Journal of Mathematical Economics 2017 Vol. 71 P. 135–151

Добавлено: 14 сентября 2020 г.

Approximate Solutions of Continuous-Time Stochastic Games

Авербух Ю. В., SIAM Journal on Control and Optimization 2016 Vol. 54 No. 5 P. 2629–2649

Добавлено: 17 апреля 2020 г.

Existence of Equilibrium Strategies in Fuzzy Stochastic Games with Finite Sets of States and Decisions

Шведов А. С., Mathematical notes 2020 Vol. 107 No. 4 P. 679–686

Добавлено: 9 апреля 2020 г.

Существование равновесных стратегий в нечетких стохастических играх с конечными множествами состояний и действий

Шведов А. С., Математические заметки 2020 Т. 107 № 4 С. 623–632

Рассматриваются некооперативные дисконтированные стохастические игры с n участниками, при этом выигрыши на каждом шаге представляются трапецоидальными нечеткими числами. Доказывается существование стационарных равновесных по Нэшу стратегий. ...

Добавлено: 9 апреля 2020 г.

A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions

Boros E., Elbassioni K., Гурвич В. А. и др., Information and Computation 2019 Vol. 267 P. 74–95

Добавлено: 9 декабря 2019 г.

A three-person deterministic graphical game without Nash equilibria

Гурвич В. А., Boros E., Milanič M. и др., Discrete Applied Mathematics 2018 Vol. 243 P. 21–38

Добавлено: 10 октября 2018 г.

Formation of Coalition Structures As a Non-Cooperative Game

Левандо Д. В., / NRU Higher School of Economics. Series WP BRP "Economics/EC". 2017. No. WP BRP 157/EC/2017.

Для изучения коалиционных структур с внутри- и меж-коалиционными экстерналиями в статье вводится семейство вложенных некооперативных одновременных конечных игр . Определение каждой игры включает в себя механизм разрешения конфликтов или механизм формирования коалиционных структур. Каждый исход каждой игры имеет два результата - профиль платежей и размещение игроков по коалициям. Семейство игр параметризовано максимальным размером коалиции для коалиционных структур ...

Добавлено: 3 февраля 2017 г.

A Potential Reduction Algorithm for Ergodic Two-Person Zero-Sum Limiting Average Payoff Stochastic Games

Гурвич В. А., Boros E., Elbassioni K. и др., , in: Combinatorial Optimization and Applications - 8th International Conference, COCOA 2014, Wailea, Maui, HI, USA, December 19-21, 2014, Proceedings.: Springer, 2014. P. 694–709.

Добавлено: 22 октября 2016 г.

Markov Decision Processes and Stochastic Games with Total Effective Payoff

Гурвич В. А., Boros E., Elbassioni K. и др., , 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.

Добавлено: 22 октября 2016 г.

On Nash-solvability in pure stationary strategies of the deterministic n-person games with perfect information and mean or total effective cost

Гурвич В. А., Oudalov V., Discrete Applied Mathematics 2014 Vol. 167 P. 131–143

Добавлено: 22 октября 2016 г.