量子算法首次实现高效计算多方博弈的近似相关均衡
Near-Optimal Quantum Algorithms for Computing (Coarse) Correlated Equilibria of General-Sum Games
- 用量子改进的乘法权重更新法求解相关均衡
- 对多玩家博弈，查询复杂度达近似最优水平
- 适合研究量子博弈与优化的学者参考
计算零和博弈的纳什均衡在经典与量子领域已广泛研究。对于一般和博弈，计算纳什均衡是PPAD难问题，而更广义的相关均衡（CE）和粗相关均衡（CCE）在博弈论中被广泛探讨。本文首次研究多玩家标准形式博弈中ε-近似相关均衡（CE）与粗相关均衡（CCE）的量子算法。我们利用量子化多尺度乘法权重更新（MWU）方法计算CE，实现固定ε下的查询复杂度为$ ilde{O}(meginfty{n})$；针对CCE，将零和博弈的量子算法技术扩展至多玩家场景，获得$ ilde{O}(m inity{n}/\varepsilon^{2.5})$的查询复杂度。两种算法在玩家数$m$与行动数$n$上均达到近似最优，经量子查询下界验证。
原文摘要 · Abstract (English)
Computing Nash equilibria of zero-sum games in classical and quantum settings is extensively studied. For general-sum games, computing Nash equilibria is PPAD-hard and the computing of a more general concept called correlated equilibria has been widely explored in game theory. In this paper, we initiate the study of quantum algorithms for computing $\varepsilon$-approximate correlated equilibria (CE) and coarse correlated equilibria (CCE) in multi-player normal-form games. Our approach utilizes quantum improvements to the multi-scale Multiplicative Weight Update (MWU) method for CE calculations, achieving a query complexity of $\tilde{O}(m\sqrt{n})$ for fixed $\varepsilon$. For CCE, we extend techniques from quantum algorithms for zero-sum games to multi-player settings, achieving query complexity $\tilde{O}(m\sqrt{n}/\varepsilon^{2.5})$. Both algorithms demonstrate a near-optimal scaling in the number of players $m$ and actions $n$, as confirmed by our quantum query lower bounds.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。