Safe Equilibrium
This addresses a foundational issue in game theory for researchers and practitioners by offering a more robust equilibrium concept, though it is incremental as it builds on existing Nash and maximin frameworks.
The paper tackles the problem of Nash equilibrium's vulnerability to irrational opponents and maximin strategies' excessive conservatism by introducing a new solution concept called safe equilibrium, which models opponents as rational with a specified probability and arbitrary otherwise, and provides existence proofs, hardness results, and algorithms for computation.
The standard game-theoretic solution concept, Nash equilibrium, assumes that all players behave rationally. If we follow a Nash equilibrium and opponents are irrational (or follow strategies from a different Nash equilibrium), then we may obtain an extremely low payoff. On the other hand, a maximin strategy assumes that all opposing agents are playing to minimize our payoff (even if it is not in their best interest), and ensures the maximal possible worst-case payoff, but results in exceedingly conservative play. We propose a new solution concept called safe equilibrium that models opponents as behaving rationally with a specified probability and behaving potentially arbitrarily with the remaining probability. We prove that a safe equilibrium exists in all strategic-form games (for all possible values of the rationality parameters), and prove that its computation is PPAD-hard. We present exact algorithms for computing a safe equilibrium in both 2 and $n$-player games, as well as scalable approximation algorithms.