Attaining equilibria using control sets

Gleb Polevoy

doi:10.1016/j.tcs.2026.115790

Attaining equilibria using control sets

2026-02-01

0

PRE

AI

DOI：10.1016/j.tcs.2026.115790

Original

Original request for help

Save

Abstract

En 中文

Many interactions stabilise in a socially suboptimal equilibrium, or move through non-equilibrium states, from which arriving at the desired equilibrium through practical dynamics is either too lengthy or impossible. Thus, we formulate a new theoretically and practically interesting direct control set problem for the planner: Given a game, any profile s and any desired equilibrium d, find a minimum subset A of the players, such that if they deviate to d, then d becomes a best response for everyone outside A. We first show that if the desired equilibrium has certain direct control sets, then this equilibrium must be strong. We prove that the direct control set optimisation problem is NP-hard and inapproximable within factor n(1-& varepsilon;), for any & varepsilon; > 0. We then solve the problem for the particular case of the game graph being a tree, and approximate the solution within the number of players influencing another player's utility, using local ratio. We then study hardness and approximation systematically, considering potential and then harmonic games, which span the finite games. For potential games, finding a direct control set, even with a constant-factor approximation, is still NP-hard, but we solve this problem for singleton congestion games and closely treat specific potential games, such as coordination games on graphs and symmetric games. As for harmonic games, we solve the two-player games, and prove that for more players, the problem is almost as hard as for general games. Finally, we consider natural variations on the direct control set problem, paving the way to multiple future studies.

Keywords:

Equilibrium

Control set

Best response

Dynamic programming

Local ratio

Potential games

Harmonic games

Attaining equilibria using control sets

Abstract

Journal

Organization

Cited Papers