Colonel Blotto 博弈中的高效均衡计算
Efficient Equilibrium Computation in Colonel Blotto Games
Martin Bichler, Abheek Ghosh
AI 速读 基于摘要
作者提出一个全多项式时间近似方案，用于计算经典连续版 Colonel Blotto 博弈的 ε-Nash 均衡。
cs.GT · cs.DS · econ.TH
查看原文摘要
Colonel Blotto is a fundamental resource-allocation game in which two players divide their budgets across battlefields, and the higher allocation on each battlefield wins its value. The problem of computing an equilibrium efficiently has remained unresolved for its classical continuous version with arbitrary budgets and with values that may vary across battlefields but are the same for both players. We give a fully polynomial-time approximation scheme that computes an $\varepsilon$-Nash equilibrium in time polynomial in the input length and $1/\varepsilon$, and nearly linear in the input length for fixed $\varepsilon$. For sufficiently balanced budgets and battlefield values, we also compute exact equilibria in linear time.