Attaining Equilibria Using Control Sets

Attaining Equilibria Using Control Sets

연구 분야: Software Development

학회: International Conference on Combinatorial Optimization and Applications

Many interactions stabilise in a socially suboptimal equilibrium, or are in 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 are made to deviate to d, then d becomes a best response for everyone outside A. We prove that the direct control set optimisation problem is NP-hard, and inapproximable within factor , for any . 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. 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.