Hypergraph conditions for the solvability of the ergodic equation for zero-sum games

Marianne Akian; Stéphane Gaubert; Antoine Hochart

doi:10.1109/CDC.2015.7403138

Hypergraph conditions for the solvability of the ergodic equation for zero-sum games

Marianne Akian
, Stéphane Gaubert
, Antoine Hochart

Ecole polytechnique

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

The ergodic equation is a basic tool in the study of mean-payoff stochastic games. Its solvability entails that the mean payoff is independent of the initial state. Moreover, optimal stationary strategies are readily obtained from its solution. In this paper, we give a general sufficient condition for the solvability of the ergodic equation, for a game with finite state space but arbitrary action spaces. This condition involves a pair of directed hypergraphs depending only on the growth at infinity of the Shapley operator of the game. This refines a recent result of the authors which only applied to games with bounded payments, as well as earlier nonlinear fixed point results for order preserving maps, involving graph conditions.

Original language	English
Title of host publication	54rd IEEE Conference on Decision and Control,CDC 2015
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	5845-5850
Number of pages	6
ISBN (Electronic)	9781479978861
DOIs	https://doi.org/10.1109/CDC.2015.7403138
Publication status	Published - 8 Feb 2015
Event	54th IEEE Conference on Decision and Control, CDC 2015 - Osaka, Japan Duration: 15 Dec 2015 → 18 Dec 2015

Publication series

Name	Proceedings of the IEEE Conference on Decision and Control
ISSN (Print)	0743-1546
ISSN (Electronic)	2576-2370

Conference

Conference	54th IEEE Conference on Decision and Control, CDC 2015
Country/Territory	Japan
City	Osaka
Period	15/12/15 → 18/12/15

Keywords

Zero-sum games
computational methods
directed hypergraphs
ergodic control
nonlinear consensus
risk-sensitive control
stochastic control

Access to Document

10.1109/CDC.2015.7403138

Cite this

Akian, M., Gaubert, S., & Hochart, A. (2015). Hypergraph conditions for the solvability of the ergodic equation for zero-sum games. In 54rd IEEE Conference on Decision and Control,CDC 2015 (pp. 5845-5850). Article 7403138 (Proceedings of the IEEE Conference on Decision and Control). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CDC.2015.7403138

@inproceedings{53a5de90c4c64e2db075cd67910b786f,

title = "Hypergraph conditions for the solvability of the ergodic equation for zero-sum games",

abstract = "The ergodic equation is a basic tool in the study of mean-payoff stochastic games. Its solvability entails that the mean payoff is independent of the initial state. Moreover, optimal stationary strategies are readily obtained from its solution. In this paper, we give a general sufficient condition for the solvability of the ergodic equation, for a game with finite state space but arbitrary action spaces. This condition involves a pair of directed hypergraphs depending only on the growth at infinity of the Shapley operator of the game. This refines a recent result of the authors which only applied to games with bounded payments, as well as earlier nonlinear fixed point results for order preserving maps, involving graph conditions.",

keywords = "Zero-sum games, computational methods, directed hypergraphs, ergodic control, nonlinear consensus, risk-sensitive control, stochastic control",

author = "Marianne Akian and St{\'e}phane Gaubert and Antoine Hochart",

note = "Publisher Copyright: {\textcopyright} 2015 IEEE.; 54th IEEE Conference on Decision and Control, CDC 2015 ; Conference date: 15-12-2015 Through 18-12-2015",

year = "2015",

month = feb,

day = "8",

doi = "10.1109/CDC.2015.7403138",

language = "English",

series = "Proceedings of the IEEE Conference on Decision and Control",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "5845--5850",

booktitle = "54rd IEEE Conference on Decision and Control,CDC 2015",

}

Akian, M , Gaubert, S & Hochart, A 2015, Hypergraph conditions for the solvability of the ergodic equation for zero-sum games. in 54rd IEEE Conference on Decision and Control,CDC 2015., 7403138, Proceedings of the IEEE Conference on Decision and Control, Institute of Electrical and Electronics Engineers Inc., pp. 5845-5850, 54th IEEE Conference on Decision and Control, CDC 2015, Osaka, Japan, 15/12/15. https://doi.org/10.1109/CDC.2015.7403138

Hypergraph conditions for the solvability of the ergodic equation for zero-sum games. / Akian, Marianne ; Gaubert, Stéphane; Hochart, Antoine.
54rd IEEE Conference on Decision and Control,CDC 2015. Institute of Electrical and Electronics Engineers Inc., 2015. p. 5845-5850 7403138 (Proceedings of the IEEE Conference on Decision and Control).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Hypergraph conditions for the solvability of the ergodic equation for zero-sum games

AU - Akian, Marianne

AU - Gaubert, Stéphane

AU - Hochart, Antoine

PY - 2015/2/8

Y1 - 2015/2/8

N2 - The ergodic equation is a basic tool in the study of mean-payoff stochastic games. Its solvability entails that the mean payoff is independent of the initial state. Moreover, optimal stationary strategies are readily obtained from its solution. In this paper, we give a general sufficient condition for the solvability of the ergodic equation, for a game with finite state space but arbitrary action spaces. This condition involves a pair of directed hypergraphs depending only on the growth at infinity of the Shapley operator of the game. This refines a recent result of the authors which only applied to games with bounded payments, as well as earlier nonlinear fixed point results for order preserving maps, involving graph conditions.

AB - The ergodic equation is a basic tool in the study of mean-payoff stochastic games. Its solvability entails that the mean payoff is independent of the initial state. Moreover, optimal stationary strategies are readily obtained from its solution. In this paper, we give a general sufficient condition for the solvability of the ergodic equation, for a game with finite state space but arbitrary action spaces. This condition involves a pair of directed hypergraphs depending only on the growth at infinity of the Shapley operator of the game. This refines a recent result of the authors which only applied to games with bounded payments, as well as earlier nonlinear fixed point results for order preserving maps, involving graph conditions.

KW - Zero-sum games

KW - computational methods

KW - directed hypergraphs

KW - ergodic control

KW - nonlinear consensus

KW - risk-sensitive control

KW - stochastic control

U2 - 10.1109/CDC.2015.7403138

DO - 10.1109/CDC.2015.7403138

M3 - Conference contribution

AN - SCOPUS:84962010435

T3 - Proceedings of the IEEE Conference on Decision and Control

SP - 5845

EP - 5850

BT - 54rd IEEE Conference on Decision and Control,CDC 2015

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 54th IEEE Conference on Decision and Control, CDC 2015

Y2 - 15 December 2015 through 18 December 2015

ER -

Hypergraph conditions for the solvability of the ergodic equation for zero-sum games

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this