Research map / Learning theory and algorithms / Submodular and game algorithms
The Complexity of Computing Robust Mediated Equilibria in Ordinal 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.
Defines robust mediated equilibria for ordinal games (robust to all cardinal utilities consistent with given ordinal preferences) and gives LP-based algorithms and complexity results for finding them, with coNP-hardness for preference-CNF type spaces.
Problem
Computing equilibria in ordinal games where players know only ordinal preferences over outcomes, so mixed strategies cannot be evaluated without cardinal utilities; the goal is equilibria robust to all consistent cardinal utilities.
Approach
Uses folk-theorem-style mediated equilibria in which an on-path distribution p and punishment distributions q_{-i} must satisfy incentive constraints for every utility function consistent with the ordinal preferences; this reduces to LPs whose separation oracles are max-flow or LP problems depending on the order structure.
Key results
- Ordinal games with total orders: EORE, SIRE, AARE, and OMIRE solvable by a single polynomial-size LP with O(|O| * sum_i |A_i|) constraints.
- Ordinal games with partial orders over pure outcomes: solvable via a single LP with a max-flow separation oracle.
- With two players and preference-CNF type spaces for player 1, EORE, SIRE, AARE and OMIRE are coNP-hard.
Surprising findings
- Some ordinal games (even with total orders) have no robust equilibrium, e.g. a matching-pennies-style game.
- In repeated games with observable actions and persistent types, punishment strategies conditioning on history can beat the stationary robust punishment, so the concept is not without loss of generality.
Limitations
- Robust equilibria do not always exist, even with total orders.
- Hardness result for richer preference-CNF constraints.
- Equivalence to repeated/mediated settings holds only under assumptions; history-dependent punishment can help when actions are observable and types persist.
Experimental setup
Builds on: mediated equilibrium pre-Bayesian games folk theorem program equilibrium
Closest papers by meaning
- Robust Equilibria in Continuous Games: From Strategic to Dynamic Robustness (NeurIPS 2025 · similarity 0.89)
- On the Interplay between Social Welfare and Tractability of Equilibria (NeurIPS 2023 · similarity 0.89)
- Perturbing Best Responses in Zero-Sum Games (AAAI 2026 · similarity 0.88)
- Constrained Pure Nash Equilibria in Polymatrix Games (AAAI 2017 · similarity 0.88)
- Certifying Concavity and Monotonicity in Games via Sum-of-Squares Hierarchies (NeurIPS 2025 · similarity 0.87)
- Roping in Uncertainty: Robustness and Regularization in Markov Games (ICML 2024 · similarity 0.87)
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.