On the optimal mixing problem of approximate Nash equilibria in bimatrix games

作     者：Deng, Xiaotie Li, Dongchen Li, Hanyu 

作者机构：Peking Univ Sch Comp Sci CFCS 5 Yiheyuan Rd Beijing 100871 Peoples R China Univ Hong Kong Sch Comp Sci Pokfulam Rd Hong Kong 999077 Peoples R China 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (Theor Comput Sci)

年 卷 期：2025年第1031卷

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Natural Science Foundation of China 

主　　题：Approximate Nash equilibria Bimatrix games Optimal mixing Approximation algorithms Computational complexity 

摘      要：This paper introduces the optimal mixing problem, a natural extension of the computation of approximate Nash Equilibria (NE) in bimatrix games. The problem focuses on determining the optimal convex combination of given strategies that minimizes the approximation (i.e., regret) in NE computation. We develop algorithms for the exact and approximate optimal mixing problems and present new complexity results that bridge both practical and theoretical aspects of NE computation. Practically, our algorithms can be used to enhance and integrate arbitrary existing constant-approximate NE algorithms, offering a powerful tool for the design of approximate NE algorithms. Theoretically, these algorithms allow us to explore the implications of support restrictions on approximate NE and derive the upper-bound separations between approximate NE and exact NE. Consequently, this work contributes to theoretical understandings of the computational complexity of approximate NE under various constraints and practical improvements in multi- agent reinforcement learning (MARL) and other fields where NE computation is involved.