Research map / Multi-agent systems and games / Games and equilibria
Paths to Equilibrium in Games
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves that every finite n-player normal-form game has the satisficing paths property: from any initial strategy profile there is a satisficing path to a Nash equilibrium, constructed by growing the set of unsatisfied players.
Problem
Whether, for a given normal-form game and initial strategy profile, a satisficing path (where satisfied best-responding players must not switch) always exists that terminates at a Nash equilibrium; this underlies convergence guarantees for satisficing-based MARL algorithms.
Approach
Construct the path by repeatedly switching strategies of unsatisfied players so that the set of unsatisfied players strictly grows (even if rewards deteriorate), until either no one is satisfied or no accessible move grows the unsatisfied set; then use a continuity/limit-point argument with fixed-game Nash equilibria on the boundary of a strategy subset to reach an equilibrium in one step.
Key results
- Theorem 1: every finite n-player normal-form game has the satisficing paths property; the constructed path has length at most n (T(x1) <= n).
- The path construction increases the number of unsatisfied players at each step, so reward-deteriorating updates are key to reaching equilibrium.
- Proof uses a lemma (limit point of NoBetter set) whose proof relies on a polynomial indifference argument in the mixing parameter lambda.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| allow unsatisfied players to explore arbitrary strategies while satisfied players stay fixed | satisficing paths in finite normal-form games · finite n-player normal-form games | existence of a path to Nash equilibrium | Helped |
| use suboptimal, potentially reward-deteriorating updates that increase the number of unsatisfied players | the constructed satisficing path · finite n-player normal-form games | ability to reach Nash equilibrium along a satisficing path | Helped |
Surprising findings
- Reward-deteriorating strategic updates, which increase the number of unsatisfied players, are key to driving play to equilibrium along a satisficing path.
- Satisficing paths to equilibrium exist for all finite normal-form games, even though best response paths may cycle and fail to reach equilibrium.
Limitations
- Result is for stateless normal-form games; extension to multi-state Markov games is not fully established because the indifference argument does not transfer.
- Existence result is analytical and semi-constructive; the path-selecting step (Nash equilibrium in one step) is computationally prohibitive, and the result is not a learning algorithm.
- Unclear whether the result holds for epsilon-best response satisficing with epsilon > 0, and it assumes unrestricted strategy sets for unsatisfied players.
Experimental setup
Builds on: best response dynamics regret testing win-stay lose-shift
Closest papers by meaning
- Foundations of Multi-Agent Learning in Dynamic Environments: Where Reinforcement Learning Meets Strategic Decision-Making (AAAI 2025 · similarity 0.87)
- Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem (NeurIPS 2024 · similarity 0.87)
- Mimicking To Dominate: Imitation Learning Strategies for Success in Multiagent Games (NeurIPS 2024 · similarity 0.86)
- Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraints (ICML 2024 · similarity 0.86)
- Asymptotic Extinction in Large Coordination Games (AAAI 2025 · similarity 0.86)
- Decomposing Temporal Equilibrium Strategy for Coordinated Distributed Multi-Agent Reinforcement Learning (AAAI 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.