2025/09/02 by Hiroki Mizuno, Mizuno, Hiroki, Yoshiaki Takata +3
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Game Theory and Applications #Game Theory and Voting Systems #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2509.01870
openalex publication_date 2025/09/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.