An Algorithmic Solution to the Blotto Game using Multi-marginal Couplings
An Algorithmic Solution to the Blotto Game using Multi-marginal Couplings
复制标题
DOI：
10.1145/3490486.3538240
复制
发表时间：
2022-02
期刊：
影响因子：
--
通讯作者：
Vianney Perchet;P. Rigollet;Thibaut Le Gouic
中科院分区：
文献类型：
--
作者：
Vianney Perchet;P. Rigollet;Thibaut Le Gouic
一个世纪前，埃米尔·博雷尔发表了他的开创性论文，关于游戏理论和具有反对称核的积分方程[1]。博雷尔描述了现在被称为Blotto游戏的游戏：一种资源分配游戏，其中两个玩家通过同时向每个战场分配资源来争夺n个不同的战场。以下两个额外的特点可能是Blotto游戏最显著的特点：赢家通吃：在每个战场上，分配最多资源的玩家赢得战场。固定预算：每个参与者都有一个固定的-确定的-预算，混合策略几乎肯定会满足这个预算。尽管存在了一个世纪之久，但Blotto博弈的纳什均衡只有在对问题的主要参数的各种限制下才知道：每个玩家的预算和每个战场的价值。此外，以前的解决方案，两个球员的游戏，包括在建设明确的解决方案。由于预算约束，这些策略可以分解为两部分：边际分布，表明在每个战场上使用哪种（随机）策略;以及耦合，以确保几乎肯定满足预算约束的方式将边际策略关联起来。第一部分可以独立于第二部分进行研究，考虑所谓的（一般）乐透游戏。在这个博弈中，预算约束只需要在期望中强制执行混合策略的随机化。虽然这种设置缺乏Blotto游戏的定义特征（固定预算），但它具有更适合计算的优势。事实上，与Blotto博弈不同，最近在[2]中提出了Lotto博弈的完整解决方案，其中作者描述了最一般情况下的显式纳什均衡：非对称预算，非对称和异质价值。鉴于这一进展，一个自然的问题是，在[2]中发现的边际解是否可以以几乎肯定满足预算约束的方式耦合。我们通过引用联合可混性理论的一个已有结果[5]，对这个问题给出了肯定的回答。混合性提出了以下问题：n个随机变量X1，...，Xn与规定的边际分布Xi ~ Pi以var（X1+ ··· + Xn）=0的方式耦合。联合可混性正是从Lotto解到Blotto解所需的步骤，通过以满足预算约束的方式耦合Lotto解的边缘。在本文中，我们利用联合可混性和多边缘耦合理论之间的一个简单的连接。我们提出了一种算法解决方案，有效地构建一个耦合，满足预算约束几乎肯定，可以很容易地采样的Blotto问题。我们的构造依赖于三个关键步骤：首先，我们将问题减少到少量的边缘以绕过多边缘问题的固有NP-困难，其次，我们将边缘离散化，最后，我们采用Sinkhorn算法的多边缘版本[3，4]来构造离散边缘的耦合。该过程输出具有连续边缘的耦合，其接近于[2]的Lotto解决方案所规定的边缘，并且可以直接从中进行采样。此外，我们量化的离散化误差和Sinkhorn算法对游戏的价值的综合影响，有效地导致一个近似的纳什均衡，甚至在对称值的情况下近似最优解。对于对称的战场价值和不对称的预算，Blotto博弈是常数和的，因此存在最优解，并且我们的算法在时间上从ε-最优解中采样，而与预算和战场价值无关。在不对称值的情况下，最优解不需要存在，但纳什均衡做，我们的算法样本从ε-纳什均衡具有类似的复杂性，但隐式常数取决于各种参数的游戏，如战场值。全文可在以下网址查阅：https://arxiv.org/abs/2202.07318。
A century ago, Emile Borel published his seminal paper on the theory of play and integral equations with skew-symmetric kernels[1]. Borel describes what is now called the Blotto game: a resource-allocation game in which two players compete for over n different battlefields by simultaneously allocating resources to each battlefield. The following two additional characteristics are perhaps the most salient features of the Blotto game: Winner-takes-all: For each battlefield, the player allocating the most resources to a given battlefield wins the battlefield. Fixed budget: each player is subject to a fixed---and deterministic---budget that mixed strategies should satisfy almost surely. Despite its century-long existence, Nash equilibria for the Blotto game are only known under various restrictions on the main parameters of the problem: the budget of each player and the value given to each battlefield. Moreover, previous solutions for two-player games have consisted in constructing explicit solutions. Because of the budget constraints, these strategies can be decomposed into two parts: marginal distributions that indicate which (random) strategy to play on each battlefield and a coupling that correlates the marginal strategies in such a way to ensure that the budget constraint is satisfied almost surely. The first part may be studied independently of the second by considering what is known as the (General) Lotto game. In this game, the budget constraint needs only be enforced in expectation with respect to the randomization of the mixed strategies. While this setup lacks a defining characteristic of the Blotto game (fixed budget), it has the advantage of lending itself to more amenable computations. Indeed, unlike the Blotto game, a complete solution to the Lotto game was recently proposed in [2] where the authors describe an explicit Nash equilibrium in the most general case: asymmetric budget, asymmetric and heterogeneous values. In light of this progress, a natural question is whether the marginal solutions discovered in [2] could be coupled in such a way that the budget constraint is satisfied almost surely. We provide a positive answer to this question by appealing to an existing result from the theory of joint mixability [5]. Mixability asks the following question: Can n random variables X1, ..., Xn with prescribed marginal distributions Xi ~ Pi, be coupled in such a way that var(X1+ ··· + Xn)=0. Joint mixability is precisely the step required to go from a Lotto solution to a Blotto one by coupling the marginals of the Lotto solution in such a way that the budget constraint is satisfied. In this paper, we exploit a simple connection between joint mixability and the theory of multi-marginal couplings. We propose an algorithmic solution to the Blotto problem by efficiently constructing a coupling that satisfies the budget constraint almost surely and can be easily sampled from. Our construction relies on three key steps: first, we reduce the problem to a small number of marginals to bypass the inherent NP-hardness of multi-marginal problems, second, we discretize the marginals and finally, we employ a multi-marginal version of the Sinkhorn algorithm [3,4] to construct a coupling of the discretized marginals. This procedure outputs a coupling with continuous marginals that are close to the ones prescribed by the Lotto solutions of [2] and from which it is straightforward to sample. Furthermore, we quantify the combined effect of discretization error and of the Sinkhorn algorithm on the value of the game, effectively leading to an approximate Nash equilibrium and even to an approximately optimal solution in the case of symmetric values. For symmetric battlefield values and asymmetric budget, the Blotto game is constant-sum so optimal solutions exist, and our algorithm samples from an ε-optimal solution in time Õ(n2 + ε-4), independently of budgets and battlefield values. In the case of asymmetric values where optimal solutions need not exist but Nash equilibria do, our algorithm samples from an ε-Nash equilibrium with similar complexity but where implicit constants depend on various parameters of the game such as battlefield values. The full paper is available at: https://arxiv.org/abs/2202.07318.