Research map / Learning theory and algorithms / Submodular and game algorithms

Cost Minimization for Equilibrium Transition

AAAI 2024 · Learning theory and algorithms › Submodular and game algorithms · approach: Correlated equilibria in sequential games · 1 citations (OpenAlex)

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.

Studies how a mediator can pay minimal monetary rewards to move a row player and k column players step by step from an initial Nash equilibrium to a more desirable one, giving complexity results and approximation/tractability results.

Problem

Computing the minimum total monetary reward needed to move players over multiple rounds from an initial pure Nash equilibrium to a more favorable target equilibrium in a game with one row player and k column players.

Approach

Models equilibrium transition as a shortest-path problem over strategy profiles with edge weights equal to the reward of a length-2 alternating path; shows NP-completeness and APX-hardness, gives slicewise polynomial algorithms, an ILP-rounding additive-error approximation, and a polynomial algorithm for single-peaked/exact-distance payoffs.

Key results

• Deciding whether the minimum transition reward is zero (TRANSITION(k,m,n,0)) is NP-complete, implying OPT TRANSITION is APX-hard and no multiplicative approximation is possible.
• Optimal reward scheme is computable in O(m^2 n^{2k}) time for fixed k, and in O(m^2 k^{2n}) time for fixed n.
• An approximation algorithm achieves additive error 2m(2||R||_{1,1}+||C||_{1,1}), independent of k; under single-peaked payoffs and exact-distance row payoffs the optimum is polynomial-time computable.

Surprising findings

• Even with only two row strategies (m=2), the transition problem is NP-complete.

Limitations

• Only one row player and identical column players with pure strategies considered.
• Approximation error is additive and not multiplicative; no multiplicative approximation possible unless P=NP.
• Hardness holds even for m=2, limiting tractability of general cases.

Experimental setup

Builds on: k-implementation best response dynamics

Closest papers by meaning

• Constrained Phi-Equilibria (ICML 2023 · similarity 0.89)
• Minimally Modifying a Markov Game to Achieve Any Nash Equilibrium and Value (ICML 2024 · similarity 0.88)
• Exclusion Method for Finding Nash Equilibrium in Multiplayer Games (AAAI 2017 · similarity 0.88)
• Efficient Regret Minimization Algorithm for Extensive-Form Correlated Equilibrium (NeurIPS 2019 · similarity 0.88)
• The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games (NeurIPS 2025 · similarity 0.87)
• Anytime-Constrained Equilibria in Polynomial Time (ICML 2025 · similarity 0.86)