Blotto Game

Here are 10 castles, numbered 1, 2, 3, ... , 10, and worth 1, 2, 3, ... , 10 points respectively. You have 100 soldiers, which you can allocate between the castles however you wish. Your opponent also (independently) does the same. The number of soldiers on each castle is then compared, and for each castle, whoever has the most soldiers on that castle wins its points. Additionally, you lose 0.2 points for each "extra" soldier that you have, in excess of your opponent's army size, at each castle that you win. You still need to deploy all 100 soldiers. In the case of a tie, no one gets points for that castle.

See example below:

Blotto Example

In this match, Alice wins castles 2, 4, 6, 9 and takes a 6-point penalty, for a total of 15 points, and Carol wins castles 1, 8, 10 and takes a 6-point penalty, for a total of 13 points (no one wins castles 3, 5, 7).

We're going to play a tournament. You get one entry and your final score is the average (mean) of your scores against all the other entries from applicants. An entry should be submitted as a list of 10 non-negative integers, adding up to 100, where the nth element is the number of soldiers being sent to castle n.

What's your entry?

写一个遗传算法在整个行动空间玩大逃杀应该可以得到一个还不错的解．然而在这之外，这个空间上还有没有什么有趣的性质呢？

让我们把问题简化，它本质上是某种剪刀石头布的超级增强版：对于任何一个元素 $a$，都可以从行动空间上选择另一个元素 $b$ 使 $a < b$ （我们用 $<$ $>$ $=$ 分别表示负，胜，平）．

那么再向剪刀石头布中加入一个新的元素呢？胜负可能会变成这样：

尽管每一个元素都会败给另外一个元素，但如果双方随机选择元素，那么有两个元素的胜率是 $\frac{1}{2}$，另外两个元素胜率只有 $\frac{1}{4}$，存在一些元素具有“相对优势”．的确如此，若把胜负表当作一张有向图的话，有一些节点的出度大于入度，这些节点面对随机出手的对手胜率更高．

Remark 1: 虽然行动空间上可以允许存在 $a, b$ 使 $S(a, b) = S(b, a)$，但在 Blotto Game 中，「平局」并不能构成等价关系． 例如我们假设有三座城堡，得分分别为 $1, 2, 3$，两人各有 100 兵力．那么 $[33,33,34] = [40,50,10]$, $[33,33,34] = [50,40,10]$，然而 $[40,50,10] \neq [50,40,10]$，这个关系缺少传递性．太无趣了！

向问题的行动空间中中加入实数那么多个元素，让可以选择的兵力分布可以是任意的呢？

我们考虑这样一个更一般的情况：两方各拥有 $1$ 个单位的士兵资源，在每个城堡可以摆放的士兵数量是 $[0, 1]$ 间的一个实数，那么我们就得到了一个连续的 Blotto Game.

假设我方和对方分别从 $\Delta_n$ 上选择 $\alpha$ 和 $\beta$ 两点，得分函数 $S(\alpha, \beta)$ 和相对得分 $R(\alpha, \beta)$ 定义为

其中 $w_i \gt 0$ 是城堡 $i$ 的得分， $P$ 是兵力超出的惩罚函数，比如 $P(\delta) = 20\delta$.

那么，在对方完全随机选择兵力分布的情况（$\Delta_n$ 上的均匀分布）下，是否有一些点，比其他的点「胜率」更高？我们如何找到这些点？

Theroem 1: Win chance $W$ is continous on $\Delta_n$ for all finite $n \geq 1$, where $f(u)$ is the probability density function of uniform distribution on $\Delta_n$, $P(\delta)$ is continuous and $P(0)=0$.

Note 1: 我们略微滥用一下记号，$R(\mathbf{p}, \mathbf{u})>0$ 指集合 $\{\mathbf{u} \mid R(\mathbf{p}, \mathbf{u})>0, \mathbf{u} \in \Delta_n\}$，即 $\mathbf{p}$ 相对 $\mathbf{u}$ 得分大于 $0$ 的区域；$d\mathbf{u}=du_1du_2...du_n$.

Note 2: 并且「连续」还不能保证 $w_i - P(\epsilon_i)$ 大于 0，这会给分析问题带来诸多困难．下文我们假设选择的 $\boldsymbol{\epsilon}$ 足够小，额外满足 $P(\epsilon_i)<w_i$ 来保证 $S_i$ 符号不会改变，由于 $P$ 连续，这总是可行的．

任取一点 $\mathbf{p} \in \Delta_n$，我们需要证明 $\forall \delta > 0\text{, }\exists\boldsymbol{\epsilon}\text{, }|W(\mathbf{p}+\boldsymbol{\epsilon}) - W(\mathbf{p})| < \delta$.

这实际上有些困难，对于每一点 $\mathbf{p}$ 来说，积分区域都不相同，那些美丽的定理离我们远去．由于 $\mathbf{p}$ 在 $\Delta_n$ 上， $\boldsymbol{\epsilon}$ 需要满足额外的条件：

并且相对得分 $R(\mathbf{p}+\boldsymbol{\epsilon}, \mathbf{p})$ 在 $\mathbf{p}$ 的邻域内是不连续的：

即使我们有假设 $P(\boldsymbol{\epsilon})$ 在 $\boldsymbol{\epsilon} \rightarrow 0$ 时连续且 $P(\boldsymbol{\epsilon}) \rightarrow 0$，$R$ 在 $\mathbf{p}$ 附近的取值也取决于每个 $\epsilon_i$ 的符号．

我画了一个 $\Delta_3$ 上 $R(\mathbf{p}+\boldsymbol\epsilon, \mathbf{p})$ 的示意图，可以看到沿着不同方向，得分会跳变．

一开始我也认为为胜率或许并不连续，不过一天多之后我找到了证明思路．要证明胜率变化的连续性，其实我们只需要关注获胜区域的变化，也就是与 $\mathbf{p}$ 相比，$\mathbf{p}+\boldsymbol{\epsilon}$ 会获胜的“面积”的变化．

接下来我要宣称，从 $\mathbf{p}$ 到 $\mathbf{p}+\boldsymbol{\epsilon}$，胜负会变化的点，全部落在某个特定区域内．

让我们固定其他分量，只看某一个维度的变化．我们将 $\mathbf{p}$ 点所有会获胜的区域投影到第 $i$ 轴，它可能长这样：

• 对于 $\inf \alpha_i \gt \max(p_i, p_i+\epsilon_i)$ 的区域来说，第 $i$ 轴增加的一点并不足以让 $\mathbf{p}$ 获胜拿到得分 $w_i$
• 对于 $\sup \beta_i \lt \min(p_i, p_i+\epsilon_i)$ 的区域来说，第 $i$ 轴本身就会拿到对应的得分 $w_i$，也不会影响胜负

实际上如果 $\epsilon_i>0$，那么当 $\mathbf{p}$ 的分量 $p_i$ 增加到 $p_i + \epsilon_i$ 时，只有那些在 $[p_i, p_i + \epsilon_i]$ 区域内的点才有可能由扭负为正（或者平局），增加胜利区域的大小．同样地，若 $\epsilon_i<0$，那么只有 $[p_i - \epsilon_i, p_i]$ 区域内的点才可能减少胜利区域．

Proposition 1: If $R(\mathbf{p}, \mathbf{u}) \neq R(\mathbf{p}+\boldsymbol{\epsilon}, \mathbf{u})$ for a fixed $\mathbf{p}$ and $P(\epsilon_i)<w_i$, then $\mathbf{u} \in \prod_{i=1}^n [p_i, p_i+\epsilon_i)$.

我们记

• $I^+ = \{i \mid \epsilon_i > 0\}$ 为所有 $\epsilon_i$ 大于 0 的下标 $i$ 的集合
• $I^- = \{i \mid \epsilon_i < 0\}$ 为所有 $\epsilon_i$ 小于 0 的下标 $i$ 的集合
• $\mathcal{V}_p = \{\mathbf{u} \mid R(\mathbf{p}, \mathbf{u})>0\}$ 为 $\mathbf{p}$ 会获胜的集合
• $\mathcal{V}_{p+\epsilon} = \{\mathbf{u} \mid R(\mathbf{p+\boldsymbol\epsilon}, \mathbf{u})>0\}$ 为 $\mathbf{p}+\boldsymbol{\epsilon}$ 会获胜的集合
• $\mathcal{V}_i^+ = \Delta_n \cap (\mathbb{R}^{i-1} \times [p_i, p_i + \epsilon_i) \times \mathbb{R}^{n-i-1}), i \in I^+$ 为新增的获胜的点一定会落在的区域
• $\mathcal{V}_i^- = \Delta_n \cap (\mathbb{R}^{i-1} \times (p_i + \epsilon_i, p_i] \times \mathbb{R}^{n-i-1}), i \in I^-$ 为减少的获胜的点一定会落在的区域

那么获胜概率的变化为：

$(2)$ 由积分的可数可加性，即对互不相交的一族集合 $S_i$ 有 $\int_{\bigcup S_i} f d\mu = \sum \int_{S_i} f d\mu$ 和一个简单的事实 $X = (X \setminus Y) \cup (X \cap Y)$.

$(3)$ 由 $(2)$ 消去 $\mathcal{V}_p$ 与 $\mathcal{V}_{p+\epsilon}$ 相交的部分，即胜负没有发生变化的区域．这基本是在说，胜利区域的变化 = 新增的胜利区域 - 减少的胜利区域．

$(4)$ 由 Proposition 1，胜负会变化的点一定落在这些区域内．并且我们已知，这两个区域不相交．

我们来单独看其中一部分：

$(5)$ 再次使用积分的可数可加性．

$(6)$ 我们对积分进行一个缩放，由于 $f(\mathbf{u}) \geq 0$，这个不等式自然成立．

$(7)$ 由 $f(\mathbf{u}) = {1}/{\mathrm{Vol}(\Delta_n)}$ 是 $\Delta_n$ 上的均匀分布，其中 $\mathrm{Vol}(\Delta_n)$ 为 n 维单位单纯形 $\Delta_n$ 的体积．

$(8)$ 由 $\mathcal{V}_i^+ = \Delta_n \cap (\mathbb{R}^{i-1} \times [p_i, p_i + \epsilon_i) \times \mathbb{R}^{n-i})$，它是一个 $n$ 维超“三棱台”（等腰梯形、等腰三棱台、等腰四面体台...），而它的上下底正是分量之合分别为 $p_i$ 和 $p_i+\epsilon_i$ 的 $n-1$ 单纯形．

$(9)$ 提取出常量 $\mathrm{Vol}(\Delta_{n-1})$. $(10)$ 简单的积分．

同理我们有

并且由于 $|a-b| \leq |a|+|b|$，我们可以得到胜率变化的上界

右侧是一个关于 $p_i$ 和 $\epsilon_i$ 的多项式，在 $\boldsymbol\epsilon \rightarrow 0$ 时也收敛于 $0$

由于 $\mathbf{p}$ 是 $\Delta_n$ 上任意一点，$W$ 在 $\Delta_n$ 上连续，Q.E.D..

至此我们已经证明了对任意有限 $n$ 和随机选择布置兵力的对手，连续 Blotto Game 的胜率函数都是连续的．注意 $n = \infty$ 的情况并不成立，因为无穷维上的均匀分布并不是良好定义的，并且也没有非平凡的 Lebesgue 测度．

当然这个结论对任意可以对有界 PDF 有效，只需要在证明过程保留 $f(\mathbf{u})$ 并且令 $f(\mathbf{u}) = 0 \text{ when } \mathbf{u} \notin \mathrm{dom}f$.

那么原本的题目 (离散 Blotto Game) 呢？直觉上来说我们只需要将总兵力作为单位 $1$，在连续 Blotto Game 上寻找极值点，然后再取整到附近的数字，应该就可以得到一个胜率相对较高的解．由上面的不等式可知，对 $\epsilon_i \leq 0.005$，

你的不等式十分紧致，但是又相当松弛．

私密马赛，我们还得找到一个更精细的上界．问题出在 $|a-b| \leq |a|+|b|$ 上，这个不等式过于松弛，让我们回到把绝对值加到每一项上之前的状态：

这里有一个直观的意义：$-{(1-p)^{10}} \big\vert_{p_i}^{p_i+\epsilon_i}$ 是 $f(x)=\frac{(1-x)^{11}}{11}$ 在 $x=p_i$ 到 $x=p_i+\epsilon_i$ 的斜率．如果这个函数二阶导数为 $0$，那么绝对值内部的每一项都会抵消，因为 $\sum_{i=1}^{10} \epsilon_i = 0$．而这个函数是凸的，左侧的斜率小于右侧，求和的绝对值才不为 $0$．

计算一下每一项对 $p_i$ 的导数：

符号与 $\epsilon_i$ 有关．也就是说要让不等式右边绝对值内的求和最大，$i \in I^+$ 的 $p_i$ 要尽可能小，$i \in I^-$ 的 $p_i$ 要尽可能大．我们取最极端的情况，$p_i = 0, i \in I^+$ 和 $\sum_{i \in I^-} p_i = 1$.

而 $\epsilon_i$ 这边只需要绝对值越大越好（$p_i + \epsilon_i$ 离 $p_i$ 越远则斜率越大），但要同时满足 $\sum_{i=1}^{10} \epsilon_i = 0$，其实我们只有 $5$ 个 $0.005$ + $5$ 个 $-0.005$ 这个选择．于是估计的一个更准确的胜率变化上界是 $\approx 20.75\%$．此时 $\mathbf{p} = [0,0,0,0,0,0.2,0.2,0.2,0.2,0.2]$，$\boldsymbol{\epsilon} = [0.05,0.05,0.05,0.05,0.05,-0.05,-0.05,-0.05,-0.05,-0.05]$.

不过「胜率最高点」附近的胜率变化可能不会如此陡峭，在 $\mathbf{p} = [0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1]$ 附近，胜率变化的上界 $\approx 1.04\%$，直接取整带来的胜率变化并不如在边界那么明显（因为 $n$ 维球的体积主要集中在边界上），朝不同方向多次取整取胜率最大值或许还能让胜率变化更小一点，这个计算方式应该还是相对安全的(roughly)．

不过这是一个博弈，我们还需要估计对手类型的分布．我们可以很容易得到胜率的链式法则：

Theorem 2: For a two-player continuous blotto game with bounded probability density function $f$ of opponent, the win chance $W_f$ against $f$ satisfies chain rule $W_{\mathbf{p}\circ(f_1,...f_n)}(\mathbf{u}) = \sum_{i=1}^{n} p_i W_{f_i}(\mathbf{u})$ for all $\mathbf{p} \in \Delta_n$.

Proof:

$(16)$ The interchange of integral and sum holds due to Tonelli's theorem.

Remark 2: It applies to discrete and mixed distributions as we change the integral to sum.

比如我们可以假设有 50% 的人会靠直觉在每个城堡都布置一点兵力，兵力分布与城堡分数正相关；30% 的人会考虑到第一层，利用某种算法得到胜率的一些极值点附近的区域；15% 的人会考虑到有聪明的对手和不太聪明的对手；还有 5% 的人会或许会出奇招梭哈赌一把．最终面对所有对手的胜率会是单独面对各类对手的胜率的简单线性组合．

那么期望得分呢？

我们有 $\forall w_i > 0\text{, }\exists\boldsymbol{\epsilon}\text{, } P(\epsilon_i) < w_i$ 且

$(22)$ 由 Proposition 1 $\Delta_n\setminus\big(\prod_{i=1}^n [p_i, p_i+\epsilon_i)\big)$ 区域中得分不会发生改变，即 $S(\mathbf{p}+\boldsymbol\epsilon, \mathbf{u})-S(\mathbf{p}, \mathbf{u}) = 0$. 而 $\mathrm{max}S$ 的存在性由 $S_i$ 的连续性+极值定理保证．

当然也是连续的．美丽！

“色魔啊色魔，你又作伪证了！”色魔刚把文章发出来，所有喝酒的人便都看著他笑． 色魔瞪大眼睛：“你怎么这样凭空污人清白！”“什么清白？我亲眼见你在 $\mathbb{R}^n$ 上算 Lebesgue 积分不考虑 well-definess，被人吊着打．”色魔便涨红了脸，额上的青筋条条绽出，争辩道：“显然可积…… 显然！…… 证明的大厦已经建成，只差一朵乌云飘在空中”又突然若有所悟，露出阴怨的神色：“你好狠毒的心……”

Indeed，我们需要证明，对任意 $\mathbf{p} \in \Delta_n$，$\mathcal{V}^+=\{\mathbf{u} \mid R(\mathbf{p}, \mathbf{u})>0, \mathbf{u} \in \Delta_n\}$ 是 Lebesgue measurable 的．否则分球悖论的幽灵在集合中徘徊，前面的东西都白证了（Though 我们没有使用选择公理构造这个集合）．

我们还是把 $\mathcal{V}^+$ 投射到每个分量单独处理．在没有惩罚函数（i.e. $P(\delta) = 0$） 的情况下，第 $i$ 个城堡得分只有两种可能，即

• $p_i>u_i, R_i>0$
• $p_i \leq u_i, R_i=0$

对每个分量 $i$ 构造一个超平面将 $\Delta_n$ 划分成两个区域 $p_i>u_i$ 和 $p_i \leq u_i$，那么至多会划分出 $2^n$ 个区域，每个区域都是可测的（可数个可测集的笛卡尔积也是可测集，证明略），而获胜的区域是其中一部分的并，自然也是可测的．

在有惩罚函数的情况下，情况似乎会复杂一些．即使 $p_i>u_i$，$R_i = S_i(\mathbf{p}, \mathbf{u}) - S_i(\mathbf{u}, \mathbf{p})$ $=sgn(p_i-u_i)\left(w_i - P(p_i-u_i)\right)$ 也可能会 $\leq0$.

但我们有假设 $P(\delta)$ 连续，这意味着 $R_i$ 也是连续的．Recall that, a function between topological spaces is continuous iff the preimage of an open set is an open set. 开集 $(0,\infty)$ 的原像 $R_i^{-1}(\mathbf{p}, \mathbf{u})$ 也是开集¹．Lebesgue 可测有许多等价定义，我们选择用开集逼近：

A set $E \subseteq \mathbb{R}^n$ is Lebesgue measurable if for every $\epsilon > 0$, there exists an open set $O$ such that:

$$E \subseteq O \quad \text{and} \quad m^*(O \setminus E) < \epsilon$$

where $m^*$ denotes the Lebesgue outer measure.

因为，平凡地，$\mathbb{R}^n$ 上的任何开集可测．只需要选择开集 $O=E$，Lebesgue 外测度 $m^*(O \setminus E) = m^*(\emptyset) = 0 < \epsilon$ ²．

接下来同样的，可数个可测集的笛卡尔积 $\prod_{i=1}^n R_i^{-1}(\mathbf{p}, \mathbf{u})$ 仍然可测．$\mathcal{V}^+$ is Lebesgue measurable, as required.