Cost Minimization for Equilibrium Transition

In this paper, we delve into the problem of using monetary incentives to encourage players to shift from an initial Nash equilibrium to a more favorable one within a game. Our main focus revolves around computing the minimum reward required to facilitate this equilibrium transition. The game involves a single row player who possesses m strategies and k column players, each endowed with n strategies. Our findings reveal that determining whether the minimum reward is zero is NP-complete, and computing the minimum reward becomes APX-hard. Nonetheless, we bring some positive news, as this problem can be efficiently handled if either k or n is a fixed constant. Furthermore, we have devised an approximation algorithm with an additive error that runs in polynomial time. Lastly, we explore a specific case wherein the utility functions exhibit single-peaked characteristics, and we successfully demonstrate that the optimal reward can be computed in polynomial time.

Authors

• Haoqiang Huang Hong Kong University of Science and Technology
• Zihe Wang Renmin University of China
• Zhide Wei Peking University
• Jie Zhang University of Bath

Keywords

• GTEP: Equilibrium
• GTEP: Game Theory
• GTEP: Other Foundations of Game Theory & Economic Paradigms