Complexity of the Existence of Constrained Secure Equilibria in Multi-Player Games
By: Hiroki Mizuno, Yoshiaki Takata, Hiroyuki Seki
Potential Business Impact:
Finds fair ways for players to win games.
We consider a multi-player non-zero-sum turn-based game (abbreviated as multi-player game) on a finite directed graph. A secure equilibrium (SE) is a strategy profile in which no player has the incentive to deviate from the strategy because no player can increase her own payoff or lower the payoff of another player. SE is a promising refinement of Nash equilibrium in which a player does not care the payoff of another player. In this paper, we discuss the decidability and complexity of the problem of deciding whether a secure equilibrium with constraints (a payoff profile specifying which players must win) exists for a given multi-player game.
Similar Papers
ε-Stationary Nash Equilibria in Multi-player Stochastic Graph Games
CS and Game Theory
Finds near-perfect game strategies when perfect ones are too hard.
On characterization and existence of a constrained correlated equilibria in Markov games
CS and Game Theory
Helps smart systems make fair group decisions.
Finding equilibria: simpler for pessimists, simplest for optimists
CS and Game Theory
Helps games find fair outcomes for players.