第六章一把公平的尺子

上一章的例子太小，两边共同的只有公园一种。现在回到标准签盒，删掉电影那一条。

删前两条都在，就是那一盒：电影院 $5$ 张，公园 $3$ 张，图书馆 $2$ 张。删后只剩“不喜欢太吵的地方”。我们假设，这时从头再问助手，签盒变成电影院 $2$ 张、公园 $5$ 张、图书馆 $3$ 张。约定没了，电影院只是普通的一个选择，公园和图书馆跟着多了。游乐场两边都是 $0$ 张，因为“怕吵”还在；它不影响下面的计算，表里就不写了。

去掉去处的名字，两张表就是两行数。为了说起来方便，删前那一行叫 $p$，删后那一行叫 $q$。括号里写哪种回答，就表示那种回答的机会：$p(\text{甲})$ 是“删前表里甲的机会”，也就是删前去电影院的机会，这里等于 $\frac{5}{10}$。

最多能有多少相同

祺乐照着删后那一行又写了十张纸条，电影院 $2$ 张、公园 $5$ 张、图书馆 $3$ 张，装进盒盖上写着“只剩怕吵”的那个签盒。然后把两盒签都倒在桌上，摆成两排，上排是删前，下排是删后。

祺乐先把能对上的上下对齐：电影院对电影院两张，公园对公园三张，图书馆对图书馆两张。最后剩下三列，上面是三张电影院，下面是公园、公园、图书馆。

韵吉问：“剩下这三列，还能再少吗？”

“少不了。上面的电影院比下面多三张。”

把这件事换成机会来说。两栏都是甲，最多能占多少机会？删前甲有 $\frac{5}{10}$，删后甲只有 $\frac{2}{10}$，所以“两栏都是甲”最多 $\frac{2}{10}$，再多删后那一栏就不够用了。同样，“两栏都是乙”最多 $\frac{3}{10}$，“两栏都是丙”最多 $\frac{2}{10}$。

每种回答取两边较小的那个，加起来： $$\frac{2}{10}+\frac{3}{10}+\frac{2}{10}=\frac{7}{10}$$ 两栏相同的机会最多 $\frac{7}{10}$，所以不同的机会至少 $\frac{3}{10}$。

这个下限做得到，桌上那两排纸签就是做法。先把能重合的部分都重合：甲甲 $\frac{2}{10}$，乙乙 $\frac{3}{10}$，丙丙 $\frac{2}{10}$。剩下的是删前多出来的甲 $\frac{3}{10}$，和删后多出来的乙 $\frac{2}{10}$、丙 $\frac{1}{10}$。把它们配成“甲乙”$\frac{2}{10}$ 和“甲丙”$\frac{1}{10}$，正是桌上剩下的那三列。

整张签表就填完了：

表里每一格是“删前是这一行、删后是这一列”的机会。每一行加起来是删前的分布，每一列加起来是删后的分布，两边都没动。两栏不同的格子在对角线以外，加起来正好 $\frac{3}{10}$。

这种把“相同”做到最大的耦合，叫最大耦合。

全变差距离

刚才那个 $\frac{3}{10}$ 还有另一种算法。把两张表在每种回答上的差取绝对值：甲差 $\frac{3}{10}$，乙差 $\frac{2}{10}$，丙差 $\frac{1}{10}$。加起来是 $\frac{6}{10}$，再除以 $2$，正好 $\frac{3}{10}$。

这个数叫两个分布的全变差距离，英文缩写是 TV。名字里的“变差”可以理解成差别，“全”是说每种回答上的差别都算进去。写成式子是 $$\mathrm{TV}(p,q)=\frac{1}{2}\sum _a|p(a)-q(a)|$$ 竖线是绝对值，只看差的大小；$\sum$ 读作“求和”，意思是把每种回答 $a$ 都算进去再加起来。

韵吉看着式子问：“为什么要除以 $2$？”

祺乐指着桌上剩下的三列：上面多出来的三张电影院，和下面多出来的两张公园、一张图书馆，是同一批要挪动的机会。一个在原来的地方多了，一个在新的地方多了，同一笔账算了两次。

也可以直接写成“$1$ 减去每种回答上两边较小者的和”。两种算法总是得到同一个数，你可以拿上面的例子验证一下。

为什么说它公平

两张表本身不同，就一定有一部分变化躲不掉，不管怎样安排都要发生。全变差距离量出的正是这部分躲不掉的变化。如果我们的安排让变化的机会恰好等于它，就说明一点多余的变化都没有。

所以以后我们问的是，比起单独协调时本来能做到的最好成绩，多付出了多少。

回到周末。删掉电影那一条，最好的两栏签只让 $\frac{3}{10}$ 的机会换地方，换掉的全是原来的电影院：$\frac{2}{10}$ 改去公园，$\frac{1}{10}$ 改去图书馆。原来抽到公园或图书馆的，一个都不用动。这 $\frac{3}{10}$ 省不掉，因为签盒里的电影院确实少了三张。只有这一种删除要照顾的时候，助手可以做到一点不多换。

我们把两排纸签收回各自的签盒。