4 · 协作的信息论：协调需要多少比特#
第 2 章算出了不能商量的代价：两个基站各看一个噪声观测、目标完全一致，最优的分散式方案比集中式差 3.02%（\(\eta^2=0.5,c=0.1\)）或 8.00%（\(\eta=1,c=1\)）。第 3 章回答了能不能解：回传时延 \(d\) 不超过耦合时标 \(p\)，协作控制器综合就是凸的（命题 3.8）；超过，就掉出可解区。
这两章都把"能说多少话"当成 0/1 的开关：要么共享，要么不共享。本章把它变成一个连续的变量，并问那个自然的下一个问题：
要商量，最少说多少话？
这个问题看着简单，其实一开口就分叉。"多少话"至少有三种互不相同的问法，每一种都有一门成熟的理论：
- 目标是一个分布：让几个节点的动作在统计上服从某个联合分布（例如"两个基站每个时隙恰好开一个"），每个时隙平均要多少比特？这是协调容量（coordination capacity，Cuff–Permuter–Cover 2010 [1]）。
- 目标是一个函数或一个解概念：让所有人算对某个东西（例如"找到一个纯 Nash 均衡"），最坏情形一共要多少比特？这是通信复杂度（communication complexity，Yao 一脉；均衡版是 Hart–Mansour 2010 [2]、Conitzer–Sandholm 2004 [4]）。
- 在开口之前，已经共同知道多少：哪一部分是免费的？这是公共信息（common information，Gács–Körner 1973 [6]、Wyner 1975 [7]）。
三门理论的答案单位不一样：第一门给"比特每符号"的渐近速率，第二门给"总比特数"的最坏情形，第三门给"零率就能提取的熵"。本章会反复强调这一点。把它们混在一栏里比大小，是这一章最容易犯、也最难被发现的硬伤。
本章要立的东西有三样：
- 一条能算到底的协调价签曲线（命题 4.4）：两基站错开发射的最小速率是 \(1-h(\epsilon)\)，它的反函数告诉我们多花一个比特能少浪费多少时隙。
- 一张分栏的话费表（4.8 节，本站提法）。
- 一条多方版的猜想（猜想 4.13），它是第 9 章"协商的最小话费"那条缺失定理的第一块砖。
本章预备知识
需要：熵、条件熵、互信息、数据处理不等式、联合典型性与随机码本论证（预备篇 4.1–4.5）；率失真函数的定义（预备篇 4.9）；二元熵函数 \(h(\epsilon)=-\epsilon\log_2\epsilon-(1-\epsilon)\log_2(1-\epsilon)\)。不需要博弈论基础。第 4.5 节用到的均衡概念会在那里现给定义，完整的均衡阶梯留到第 6 章。
用到的站内内容：
- 划分之交与 Gács–Körner、Wyner 公共信息的口径：第二部第 3 章的备注（"格的交是划分，GK 公共信息是它的熵——一个是集合，一个是数"）。
- Yao 双方模型、黑板 vs coordinator 的分离、两小区最小 CSI 交换 \(C(\varepsilon)\lesssim56\) 比特：第三部第 6 章。
- 信息的价值曲线 \(V(I)\)（单调不减、凹、小 \(I\) 处极陡）：第三部第 5 章。
- 分散化代价与嵌套亏损猜想 2.6：第 2 章；嵌套亏欠 \(\nu\)（链路数，定义 3.4）：第 3 章。
本部统一符号：\(N\) = 玩家 / 决策者数，\(m\) = 动作数。文献里 Hart–Mansour 用 \(n\) 记玩家数、Conitzer–Sandholm 用 \(n\) 记动作数，本章一律改写为 \(N\) 与 \(m\)，引用时会点明。
4.1 两个基站想错开：不商量能不能做到#
两个共信道的小基站挨得很近，同时发射就互相打架。理想的做法是错开：这个时隙我开你关，下个时隙我关你开。
先问一个幼稚的问题：不商量能做到吗？
如果两个基站各自掷一枚公平硬币决定开还是关，每个时隙有四种结果，各占 \(1/4\)：（开，关）、（关，开）是好的，（开，开）撞车，（关，关）浪费。一半的时隙是坏的。
要把坏时隙压到零，就必须让两个动作反相关。独立的随机源做不出反相关，这是概率论的常识，也是本章全部内容的起点：
相关性不能凭空产生。要让两个分开的随机变量不独立，中间必须流过信息。
流多少？最粗暴的做法是：基站 1 每个时隙用 1 比特告诉基站 2"我这一时隙开还是关"，基站 2 取反。这样坏时隙率是 0，话费是 1 比特/时隙。
这个数字对吗？直觉上应该是对的：要让对方精确知道你的一个二元决定，就得给他 1 比特。但"精确知道"不是我们真正需要的。我们需要的只是"两人的动作合起来看上去像是从某个联合分布里抽的"。这个要求弱得多，而弱要求应该更便宜。
便宜多少？如果允许 10% 的坏时隙呢？
本章第一个定量结果是：允许 10% 的坏时隙，话费从 1 比特降到 0.531 比特/时隙，省了将近一半。允许 1%，话费是 0.919 比特。这条曲线（图见 4.3 节）就是"协调的价签"。
直觉：为什么"看起来像"比"知道"便宜
"让基站 2 知道基站 1 的决定"是一个逐时隙的要求：每一个时隙都必须对。"让两人的动作服从某个联合分布"是一个统计的要求：只要长期的经验频率对就行。
统计要求给了编码器很大的自由度。它可以在很多个时隙上一起编码，把那些"反正对结果影响不大"的时隙拿去补贴关键的时隙。这就是信源编码的全部魔法：整块处理比逐个处理便宜。所以协调容量的答案里必然出现"\(n\to\infty\)"和"每符号速率"，而不是"每个时隙固定几比特"。
这也是本章第一个量纲警告的来源。协调容量给的是速率，通信复杂度给的是一次性的总比特数。同一个"话费"两种记账，不能相加，也不能比大小。
顺着这条直觉往下走，还有第二个分叉。"看上去像"到底有多像？
- 版本一：经验频率像。数一数这 \(n\) 个时隙里（开，关）出现了多少次、（开，开）多少次，四个频率接近目标分布就算成功。
- 版本二：整条序列的分布像。把 \((P_1^n,P_2^n)\) 这个 \(4^n\) 个点上的分布拿来，与目标的 \(n\) 重乘积分布做总变差（total variation，衡量两个分布差多远的一个数，定义 4.2 给出）比较，要求趋于零。
版本二严格更强。经验频率对，不代表序列的联合分布对。例如"前一半全是（开，关）、后一半全是（关，开）"，经验频率完美，但它显然不像 i.i.d.。
Cuff–Permuter–Cover [1] 把这两个版本分别叫经验协调（empirical coordination）与强协调（strong coordination），并证明：强协调要额外买一样东西，也就是公共随机性；经验协调不用。这是本章的第一个"分级"，4.2 节展开。
到此为止我们得到了什么
- 要让两个分开的决策者的动作相关，中间必须流过信息。
- "精确告知"要 1 比特/时隙，而"统计上看起来像"应该更便宜。
- "像"到什么程度，本身还要分成经验协调与强协调两级，后者要额外的资源。
4.2 把"协调"写成定义：经验协调、强协调与两节点定理#
4.2.1 模型与三个定义#
我们只处理本章需要的最简拓扑：两节点，单向链路。
节点 1（下称"信源节点"，对应基站 1）不做任何决策，它的动作序列 \(X^n=(X_1,\dots,X_n)\) 由自然按 \(p(x)\) 独立同分布给定。可以读成"基站 1 的业务需求决定了它这一时隙要不要发"。
节点 2 收到一条消息后产生自己的动作序列 \(Y^n\)。目标是一个给定的联合分布 \(p(x,y)\)，其 \(x\) 边缘必须与自然给的 \(p(x)\) 一致。
定义 4.1（速率 \(R\) 的协调码）
一个块长 \(n\)、速率 \(R\) 的协调码由一对映射构成：
- 编码器 \(f_n:\mathcal{X}^n\to\{1,\dots,2^{nR}\}\)，把 \(X^n\) 映成一个消息指标 \(M=f_n(X^n)\)；
- 解码器 \(g_n:\{1,\dots,2^{nR}\}\to\mathcal{Y}^n\)，把 \(M\) 映成动作序列 \(Y^n=g_n(M)\)。
若允许两端共享一个与 \(X^n\) 独立的随机变量 \(W\)（公共随机性，common randomness，速率 \(R_0\) 表示 \(W\) 需要 \(nR_0\) 比特描述），则 \(f_n,g_n\) 可以额外依赖 \(W\)。
记号解释
- \(M\) 是"说的话"，\(2^{nR}\) 是话的总数。\(n\) 个符号一共说 \(nR\) 比特，所以速率是每符号 \(R\) 比特。
- \(W\) 是"事先约好的一本共用密码本 / 一串共用随机数"。它不携带关于 \(X^n\) 的任何信息，但两边看到的是同一份。
定义 4.2（经验协调）
记 \((X^n,Y^n)\) 的经验联合分布（joint type）为
称速率 \(R\) 对目标 \(p(x,y)\) 可达经验协调，若存在一列协调码使 \(\hat{P}_{X^nY^n}\to p\) 依概率收敛。等价地，对任意 \(\epsilon>0\)，\(\Pr\big[\|\hat{P}_{X^nY^n}-p\|_{\mathrm{TV}}>\epsilon\big]\to0\)。
白话说：不要求每次运行都数得准，只要求"直方图偏离目标超过任一给定容差"这件坏事的概率随块长 \(n\) 增大趋于零。这里的 \(\epsilon\) 只是容差，与 4.3 节算例 4.1 里的坏时隙率 \(\epsilon\) 无关。
这个定义在说什么
只数频率，不管顺序。\(\hat{P}\) 是把 \(n\) 个时隙的 \((X_i,Y_i)\) 对丢进四个（一般是 \(|\mathcal{X}||\mathcal{Y}|\) 个）格子里数出来的直方图，要求它长得像目标 \(p\)。
总变差取半 \(L_1\) 约定：\(\|P-Q\|_{\mathrm{TV}}=\tfrac12\|P-Q\|_1=\tfrac12\sum_z|P(z)-Q(z)|\in[0,1]\)。这与第二部第 1 章定义 1.3 相同，第 5 章也用它。
总变差等于"任取一个事件 \(A\)，两个分布给 \(A\) 的概率最多差多少"，即 \(\max_A|P(A)-Q(A)|\)。例如 \(P=(0.5,0.5)\)、\(Q=(0.6,0.4)\) 时 \(\|P-Q\|_{\mathrm{TV}}=\tfrac12(0.1+0.1)=0.1\)。
先验各半时，任何检验猜对"样本来自 \(P\) 还是 \(Q\)"的概率至多 \((1+\|P-Q\|_{\mathrm{TV}})/2\)。所以总变差趋于零，就是"任何检验都只能瞎猜"。定义 4.3 就是这样用它的。
定义 4.3（强协调）
称速率对 \((R,R_0)\) 对目标 \(p(x,y)\) 可达强协调，若存在一列协调码使
这个定义在说什么
它不数频率，而是把整条长度 \(n\) 的序列对的真实分布，与"独立同分布地按 \(p(x,y)\) 抽 \(n\) 次"得到的分布放在一起，做总变差比较。它要求一个统计学家即使拿到整条序列、做任意检验，也分辨不出这是编出来的还是真抽的。
陷阱：两个定义差的不是精度，是"顺序里的信息"
经验协调只约束一阶经验统计量；强协调约束整个 \(n\) 维分布。前面举的例子（前一半全（开，关）、后一半全（关，开））经验频率完美，强协调意义下却与 i.i.d. 相差极远。
工程上的差别很实在。如果协调结果还要喂给第三方做统计推断，经验协调不够，因为它允许序列里存在可被识别的结构。例如一个基于时隙占用序列做异常检测的运维模块，就属于这种情况。
如果只是要长期吞吐或干扰的平均值对，经验协调足够。
4.2.2 两节点定理#
定理 4.1（Cuff–Permuter–Cover 2010，定理 3：两节点经验协调容量）【已解决】
在上述两节点模型中（\(X^n\) 由自然按 \(p(x)\) i.i.d. 给出，单向链路速率 \(R\)），目标 \(p(x,y)\) 可经验协调当且仅当
其中互信息按目标联合分布 \(p(x,y)\) 计算。可达域是 \(\{(R,p):R>I(X;Y)\}\) [1]。
边界 \(R=I(X;Y)\) 的归属按原文取开集。本章后文写"最小速率 \(R^\star=I(X;Y)\)"时，指的是这个开区域的下确界。
证明思路（可达性：随机码本 + 覆盖引理）
分四步，每一步都只用到率失真编码的标准工具。
第 1 步：造码本。 固定目标 \(p(x,y)\)，取其 \(y\) 边缘 \(p(y)\)。独立地生成 \(2^{nR}\) 条码字 \(Y^n(m)\)，\(m=1,\dots,2^{nR}\)，每条的每个符号按 \(p(y)\) 独立抽。
码本对编解码双方公开。它是确定性的一张表，事先约定好，不是公共随机性（见定理 4.2）。
第 2 步：编码，就是找一条与 \(X^n\) 联合典型的码字。 编码器拿到 \(X^n\) 后，在码本里搜索一个 \(m\) 使 \((X^n,Y^n(m))\) 关于 \(p(x,y)\) 联合典型。找到就发这个 \(m\)，找不到就发 \(m=1\)。
联合典型（jointly typical）的白话是：把这对序列逐时隙配对，数出的经验联合分布（即定义 4.2 的 \(\hat P\)）与 \(p(x,y)\) 足够接近。预备篇 4.5"典型序列与随机编码"用它做过信道译码，这里把同一个工具用在信源一侧"找搭档"。
第 3 步：覆盖引理保证找得到。 这一步是率失真编码可达性的标准结论：随机生成的码本以高概率"覆盖"典型的 \(X^n\)，只要码本足够大，即
这个门槛可以数出来，这就是覆盖引理（covering lemma）的内容：码字撒得够多，几乎每个典型的 \(X^n\) 都会有一条与它联合典型的码字。
- 固定一条典型的 \(x^n\)。与它联合典型的 \(y^n\) 约有 \(2^{nH(Y\mid X)}\) 条，它们都是 \(Y\) 的典型序列。一条按 \(p(y)\) 独立抽出的码字取到其中任意指定一条的概率约为 \(2^{-nH(Y)}\)。两者相乘，一条码字与 \(x^n\) 联合典型的概率约为 \(2^{-n[H(Y)-H(Y\mid X)]}=2^{-nI(X;Y)}\)。
- \(2^{nR}\) 条码字彼此独立，全部落空的概率约为 \(\big(1-2^{-nI}\big)^{2^{nR}}\le\exp\big(-2^{nR}\cdot2^{-nI}\big)=\exp\big(-2^{n(R-I)}\big)\)，这一步用了 \(1-u\le e^{-u}\)。\(R>I\) 时 \(2^{n(R-I)}\) 随 \(n\) 指数增长，落空概率以"指数的指数"速度趋于零。
- 再加上 \(X^n\) 本身以趋于 1 的概率是典型的（预备篇 4.5 的 AEP），"找不到"的总概率 \(\to0\)。
第 4 步：联合典型 \(\Longrightarrow\) 经验分布对。 联合典型的定义本身就是"经验联合分布接近 \(p(x,y)\)"。所以只要第 3 步成功，定义 4.2 的要求自动满足。\(\square\)
证明思路（逆定理：数据处理 + 互信息的凸性）
设某个码达到了经验协调，则
逐步说明
- 第一个不等号：\(nR\) 比特最多携带 \(nR\) 比特的熵。
- 第二个不等号：熵的非负性，\(I(X^n;M)=H(M)-H(M\mid X^n)\le H(M)\)。
- 第三个不等号：数据处理不等式。\(Y^n\) 是 \(M\) 的函数，\(X^n\to M\to Y^n\) 成马氏链（预备篇 4.3）。
- 第一个等号：互信息定义。
- 第二个等号：\(X^n\) 独立同分布。
- 最后一个不等号分两步。先用链式法则（预备篇 4.2）把 \(H(X^n\mid Y^n)\) 逐个拆开，再在每一项里扔掉多余的条件。条件作用减少熵，扔掉条件只会让熵变大：
其中 \(X^{i-1}=(X_1,\dots,X_{i-1})\)，第 \(i\) 项的条件从"\(X^{i-1}\) 与整条 \(Y^n\)"缩成只剩 \(Y_i\)。
最后一步把逐分量的互信息合成一个。
为什么需要这一步：上面的链条给出的是 \(n\) 个时隙各自互信息之和，而各时隙的联合分布可以各不相同。经验协调约束的却只是所有时隙平均起来的联合分布。所以必须把"各时隙互信息的平均"与"平均分布的互信息"连起来，而且方向必须是前者 \(\ge\) 后者，链条才接得上。
记第 \(i\) 个时隙的条件分布为 \(q_i(y\mid x):=\Pr(Y_i=y\mid X_i=x)\)，其平均 \(\bar q=\frac1n\sum_iq_i\)。每个 \(X_i\) 的分布都是同一个 \(p_X\)。
互信息在固定输入分布下对信道是凸的。 Jensen 不等式说，凸函数"先平均再取值"不超过"先取值再平均"（预备篇 7.2）。于是得
凸性本身有一个两行的证明。让时隙编号 \(J\) 在 \(\{1,\dots,n\}\) 上均匀、与 \(X\sim p_X\) 独立，给定 \(J=i\) 时 \(Y\) 过信道 \(q_i\)。这时 \(X\) 到 \(Y\) 的信道恰是 \(\bar q\)，于是
这里用了"多看一个 \(J\) 不会让信息变少"和 \(I(X;J)=0\)。直观地说，几条信道混着用又不告诉接收方用的是哪条，只会丢掉相关性。
极端例子：\(p_X\) 均匀，两个时隙分别用"原样照抄"与"取反"，各自的互信息都是 1 比特，平均信道却让输出与输入独立，\(I(p_X,\bar q)=0\)。
剩下是把 \((p_X,\bar q)\) 与目标对上。经验联合分布的期望是
它恰是 \((p_X,\bar q)\) 诱导的联合分布。经验协调要求 \(\hat P\to p\) 依概率，而 \(\hat P\) 的每个分量都在 \([0,1]\) 内，所以它的期望也趋于 \(p(x,y)\)。互信息在分布上连续，于是 \(R\ge I(X;Y)-o(1)\)。\(\blacksquare\)
物理意义
可达性说"要造出多少相关性，就得付多少互信息"，逆定理说"付的钱一分不能少"。在协调问题里，互信息度量的是"两个动作有多相关"，价签就按它计。
这是 Cuff 等人这篇论文最漂亮的地方：同一个 \(I(X;Y)\)，在信道编码里是"能传多快"，在率失真里是"能压多小"，在协调问题里是"能有多默契"。
行为分析
下面看四个极限。
- 完全独立（\(p(x,y)=p(x)p(y)\)）：\(I=0\)，\(R^\star=0\)。不需要说一句话，各掷各的骰子就行。
- 完全确定（\(Y=f(X)\)）：\(I=H(Y)\)，\(R^\star=H(Y)\)。这时协调退化成"把 \(Y\) 告诉对方"，价签就是 \(Y\) 的熵，与 4.1 节那个幼稚协议一致（\(Y\) 为均匀二元时 \(H(Y)=1\) 比特）。
- 中间地带：\(0<I<H(Y)\)，这就是协调比"告知"便宜的区间，4.3 节量化。
- \(Y\) 的字母表变大：\(R^\star=I(X;Y)\le\min\{H(X),H(Y)\}\)，所以价签永远不超过两端各自的熵。协调再复杂，也不会比"把两边的决定都说一遍"更贵。
4.2.3 分级：经验协调不用买公共随机性，强协调要买#
定理 4.2（Cuff–Permuter–Cover 2010，定理 2：公共随机性对经验协调无用）【已解决】
任何经验协调可达的速率–分布对 \((R,p)\)，都可以用确定性的编码器与解码器（不使用任何公共随机性 \(W\)）达到。等价地，允许随机化的协调码不能改进经验协调容量域 [1]。
物理意义
经验协调只看频率直方图，而直方图是一个"平均量"。随机化只能在平均量周围制造抖动，不能把平均量搬到别处，所以它买不到任何东西。
定理 4.1 的可达性证明本身就印证了这一点。随机码本只是证明手法（概率方法）。一旦证明存在一个好码本，就把它固定下来当成公开的表用，全程不需要在线的随机性。
定理 4.3（Cuff–Permuter–Cover 2010，定理 9、10：强协调与公共随机率）【已解决】
（i）无通信、只有公共随机性的三节点情形（定理 9）：让三个节点的动作服从给定的联合分布所需的最小公共随机率，等于 Wyner 公共信息向三方的推广，即在"给定 \(W\) 时三者条件独立"的约束下最小化 \(I(X,Y,Z;W)\)。Wyner 公共信息的两变量版本见 4.6 节定义 4.6，它是能把变量之间全部相关性解释掉的最省公共起因。
作者自评这是"对一组随机变量之间公共信息的一个建议度量" [1]。
（ii）两节点强协调（定理 10）：记公共随机率为 \(R_0\)。
- 没有公共随机性（\(R_0=0\)）时，容量域是 \(R\ge C_{\mathrm{Wyner}}(X;Y)\)，门槛就是 4.6 节定义 4.6 的 Wyner 公共信息。
- 当且仅当 \(R_0\ge\Gamma\) 时，容量域退化为与经验协调相同的 \(R\ge I(X;Y)\)。\(R_0<\Gamma\) 时门槛严格高于 \(I(X;Y)\) [1]。
这里的 \(\Gamma\) 是原文所称的"必要条件熵"（necessary conditional entropy，原文记作 \(H(Y\dagger X)\)）：
极小化取遍使 \(X-f(Y)-Y\) 成马氏链的函数 \(f\)。原文指出，对许多联合分布 \(\Gamma\) 就等于 \(H(Y\mid X)\)。\(R_0\) 介于 \(0\) 与 \(\Gamma\) 之间时的完整速率域，原文引向 Cuff 2008 年的 ISIT 论文，本章不展开。
物理意义
强协调要求"整条序列都像真的随机抽的"。如果解码器是确定性的，\(2^{nR}\) 条消息只能索引出 \(2^{nR}\) 条确定的输出序列，也就是一个只有 \(2^{nR}\) 个支撑点的分布。这样的分布在总变差意义下逼近不了一个典型支撑点约有 \(2^{nH(Y)}\) 个的分布，除非 \(R\ge H(Y)\)。
要绕开这个障碍，输出必须真的带上随机性。解码器自己掷骰子（私有随机性）能把门槛从 \(H(Y)\) 往下降，但这份随机性对方不知道，造不出与 \(X\) 的额外相关。要一路降到经验协调的 \(I(X;Y)\)，还得让两边共享同一份随机性。这就是公共随机性出场的原因：它是"两人共有的骰子"。
没有公共随机性时，门槛的精确形式是 Wyner 公共信息 \(C_{\mathrm{Wyner}}(X;Y)\)（原文定理 10）。它介于 \(I(X;Y)\) 与 \(H(Y)\) 之间：下界见 4.6 节命题 4.10，上界取 \(W=Y\) 即得。
行为分析
把这条定理读成资源清单：
| 目标 | 需要的资源 | 说明 |
|---|---|---|
| 经验协调 | 只需通信速率 \(R>I(X;Y)\) | 定理 4.1 + 定理 4.2 |
| 强协调，公共随机充足（\(R_0>\Gamma\)） | \(R>I(X;Y)\)，另加 \(R_0\) 比特/符号的共用随机数 | 定理 4.3(ii) |
| 强协调，无公共随机（\(R_0=0\)） | \(R\ge C_{\mathrm{Wyner}}(X;Y)\)，一般严格大于 \(I(X;Y)\) | 定理 4.3(ii)（原文定理 10） |
工程读法
公共随机性在无线里是便宜的。两端共享一个伪随机序列种子几乎不花在线带宽，加扰、跳频、导频序列的日常做法就是如此。所以"强协调贵在哪"，在无线里的答案往往是：贵在你必须先建立起那个共享的种子。这是一次性的开销，不是每符号的速率。
这一点会在第 5 章变成"共享什么，决定省多少"的第一级阶梯。那里还会引出 Newman 1991 [5] 的定理：公共随机性相对于私有随机性最多只值 \(O(\log n)\) 比特，也就是这层资源便宜得几乎白送。
到此为止我们得到了什么
- 协调的三个定义（协调码、经验协调、强协调）与两节点的完整答案。
- 经验协调的最小速率是目标联合分布的互信息 \(I(X;Y)\)。可达性用随机码本 + 覆盖引理，逆定理用数据处理 + 互信息凸性。
- 经验协调不需要公共随机性（定理 4.2），强协调需要（定理 4.3）。后者是本章的第一条"目标越强、资源清单越长"的分级。
4.3 算例：两基站错开发射的协调价签#
现在把定理 4.1 用在 4.1 节那个例子上，算到底。
4.3.1 算例 4.1：错开发射的价签#
算例 4.1（两基站错开发射的协调价签）【本站演算】
场景。 两个共信道小基站，每个时隙各自决定"开"或"关"。基站 1 的决定 \(P_1\) 由自身业务给定，取"开"与"关"各 \(1/2\)。这是自然给的 \(p(x)\)，基站 1 不为协调而改变它。基站 2 要配合。目标联合分布取
其中 \(\epsilon\in[0,1/2]\) 是允许的坏时隙率：（开，开）是撞车（互相干扰），（关，关）是双双空闲（浪费时隙），两者合起来的概率恰是 \(\epsilon\)。
第 1 步：核对边缘分布。 \(\Pr(P_1=\text{开})=\frac{1-\epsilon}{2}+\frac{\epsilon}{2}=\frac12\) ✓。这与自然给的 \(p(x)\) 一致，是定理 4.1 的前提。同理 \(\Pr(P_2=\text{开})=\frac12\)。
第 2 步：算条件熵。 给定 \(P_1=\text{开}\)，\(P_2\) 取"关"的概率是 \(\frac{(1-\epsilon)/2}{1/2}=1-\epsilon\)，取"开"的概率是 \(\epsilon\)。所以
对 \(P_1=\text{关}\) 同理。于是 \(H(P_2\mid P_1)=h(\epsilon)\)。
第 3 步：算互信息。
第 4 步：代入定理 4.1。 经验协调所需的最小速率
第 5 步：代数字。
| 允许的坏时隙率 \(\epsilon\) | \(h(\epsilon)\) | 协调价签 \(R^\star=1-h(\epsilon)\)（比特/时隙） | 相对"直接告知"（1 比特）省下 |
|---|---|---|---|
| 0（完全错开） | 0 | 1.000 | 0% |
| 0.01 | 0.080793 | 0.919 | 8.1% |
| 0.05 | 0.286397 | 0.714 | 28.6% |
| 0.10 | 0.468996 | 0.531 | 46.9% |
| 0.20 | 0.721928 | 0.278 | 72.2% |
| 0.30 | 0.881291 | 0.119 | 88.1% |
| 0.40 | 0.970951 | 0.029 | 97.1% |
| 0.50（独立） | 1 | 0.000 | 100% |
校验（三条独立途径）
-
换一个恒等式算同一个数。 途径一（上面）用 \(I=H(P_2)-H(P_2\mid P_1)\)，途径二用 \(I=H(P_1)+H(P_2)-H(P_1,P_2)\)。
联合熵为
\[ H(P_1,P_2)=-2\cdot\frac{1-\epsilon}{2}\log_2\frac{1-\epsilon}{2}-2\cdot\frac{\epsilon}{2}\log_2\frac{\epsilon}{2}=1+h(\epsilon) \]推导时把 \(\log_2\frac{u}{2}=\log_2u-1\) 代入，四项的 \(-1\) 合起来给出 \(+1\)。于是 \(I=1+1-(1+h(\epsilon))=1-h(\epsilon)\)，与途径一相同 ✓。
-
数值复核 \(h(0.1)\)。 \(-0.1\log_20.1-0.9\log_20.9=0.1\times3.321928+0.9\times0.152003=0.332193+0.136803=0.468996\)，故 \(R^\star=0.531004\)，与第 5 步表中 \(\epsilon=0.10\) 一行的 0.531 相符 ✓。
- 两个极限退化到已知答案。
- \(\epsilon=1/2\)：目标分布变成两个独立均匀比特的乘积，\(R^\star=0\)。不需要说任何话，各掷各的硬币即可，与 4.1 节的幼稚计算（独立时坏时隙率恰好 \(1/2\)）严丝合缝 ✓。
- \(\epsilon=0\)：目标是 \(P_2=\overline{P_1}\)，\(R^\star=1=H(P_2)\)。这退化为"把决定原样告知"，与定理 4.1 行为分析里的"完全确定"情形一致 ✓。
把这条曲线画出来。
怎么读这张图
- 下面那条是算例 4.1 第 5 步表格的 \(R^\star=1-h(\epsilon)\)，上面那条水平线是"每时隙直接告知对方我的决定"这个幼稚协议的 1 比特/时隙。
- 两条线只在 \(\epsilon=0\) 处相接。要求完全错开，协调就退化成告知，一分钱都省不下。一旦松一点点（\(\epsilon=0.01\)）就省下 8.1%，松到 \(\epsilon=0.1\) 省下将近一半。
- 曲线在 \(\epsilon=0\) 处是竖直的（\(\mathrm{d}h/\mathrm{d}\epsilon\to\infty\)），意思是最后那一点点完美主义最贵。数据点全部由 \(1-h(\epsilon)\) 直接代入得到。
4.3.2 命题 4.4：由回传预算反推坏时隙率#
这条曲线可以反过来读，那才是工程师真正要的形式：我有 \(R\) 比特/时隙的回传预算，能把坏时隙率压到多低？
命题 4.4（两基站错开发射的协调价签曲线）【本站演算：两条经典定理的合成】
设 \(P_1\sim\mathrm{Bern}(1/2)\) 由业务给定，节点 2 经速率 \(R\) 比特/时隙的单向链路产生 \(P_2^n\)，"坏时隙"定义为 \(\{P_1=P_2\}\)。则在经验协调意义下可达的最小坏时隙率是
其中 \(h^{-1}:[0,1]\to[0,1/2]\) 是二元熵函数在 \([0,1/2]\) 上的反函数；\(R\ge1\) 时 \(\epsilon^\star=0\)。等价地，达到坏时隙率 \(\epsilon\) 的最小速率是 \(R^\star(\epsilon)=1-h(\epsilon)\)。
证明
分三步。
第 1 步：由定理 4.1，问题化为一个约束极小化。 给定预算 \(R\)，可达的目标分布恰是那些满足 \(I(P_1;P_2)<R\) 的联合分布（\(P_1\) 边缘固定为均匀）。所以
第 2 步：这是二元均匀信源在汉明失真下的率失真问题。 令 \(\tilde P_2:=\overline{P_2}\)（把节点 2 的动作取反），则 \(\{P_1=P_2\}=\{P_1\ne\tilde P_2\}\)，而取反是一一映射、不改变互信息。于是上式等价于"以汉明失真 \(d(x,\tilde y)=\mathbf{1}\{x\ne\tilde y\}\) 度量、失真不超过 \(\epsilon\) 时的最小互信息"，即率失真函数 \(R(D)\) 在 \(D=\epsilon\) 处的值。
第 3 步：代入经典结论 \(R(D)=1-h(D)\)（\(0\le D\le1/2\)）。 其逆定理只有两行：
逐个看这几个符号：
- 第一个等号：互信息定义。
- 第二个等号：给定 \(\tilde P_2\) 时，知道 \(P_1\) 与知道 \(P_1\oplus\tilde P_2\) 是一回事。
- 第一个不等号：去掉条件增加熵。
- 第二个不等号：用 \(\Pr[P_1\oplus\tilde P_2=1]\le D\le1/2\) 与 \(h\) 在 \([0,1/2]\) 上单调增。
可达性取对称测试信道 \(\tilde P_2=P_1\oplus Z\)，\(Z\sim\mathrm{Bern}(D)\) 且与 \(P_1\) 独立。两个不等号此时都取等：
- 因为 \(P_1\) 均匀，\(\Pr(\tilde P_2=b,Z=z)=\Pr(P_1=b\oplus z)\Pr(Z=z)=\tfrac12\Pr(Z=z)\)，所以 \(Z=P_1\oplus\tilde P_2\) 与 \(\tilde P_2\) 独立，去掉条件不损失任何东西。
- \(\Pr[Z=1]=D\) 恰好用满失真预算。
于是 \(I=1-h(D)\)。把 \(R=1-h(\epsilon)\) 反解即得 \(\epsilon^\star(R)=h^{-1}(1-R)\)。\(\blacksquare\)
物理意义
这条曲线是"话费—浪费"的兑换率：横轴是每时隙肯花多少比特在回传上，纵轴是因此浪费掉的时隙比例。它是一条凸减曲线：第一批比特买到的改善最大，后面越来越不划算。
这与第三部第 5 章的 \(V(I)\) "在小 \(I\) 处极陡"是同一个现象的两次出现：信息的边际价值递减，而且在零点附近陡到发散。
4.3.3 话费—代价曲线的形状#
行为分析
代数字（\(\epsilon^\star(R)=h^{-1}(1-R)\)）：
| 回传预算 \(R\)（比特/时隙） | 0 | 0.1 | 0.2 | 0.4 | 0.6 | 0.8 | 0.9 | 1.0 |
|---|---|---|---|---|---|---|---|---|
| 最小坏时隙率 \(\epsilon^\star\) | 0.500 | 0.316 | 0.243 | 0.146 | 0.079 | 0.031 | 0.013 | 0 |
- 第一个 0.1 比特把坏时隙率从 0.500 降到 0.316，一口气吃掉全部可改善量的 \((0.500-0.316)/0.500=36.8\%\)。
- 最后一个 0.1 比特（\(R\) 从 0.9 到 1.0）只买到 \(0.013/0.500=2.6\%\)。
- 两者相差 14 倍。用无线的话说：回传给协调的第一根管子价值极高，把管子加粗到"完美"则极不划算。
- 边界斜率可以算准：\(\mathrm{d}\epsilon^\star/\mathrm{d}R=-1/h'(\epsilon^\star)\)，而 \(h'(x)=\log_2\frac{1-x}{x}\)。\(R\to0\) 时 \(\epsilon^\star\to1/2\)、\(h'\to0\)，斜率 \(\to-\infty\)（无穷陡）；\(R\to1\) 时 \(\epsilon^\star\to0\)、\(h'\to+\infty\)，斜率 \(\to0\)（完全平）。
怎么读这张图
- 下面那条是命题 4.4 的 \(\epsilon^\star(R)=h^{-1}(1-R)\)，上面那条直线是"每花一分钱买到等量改善"的线性参照。
- 真实曲线整条压在参照线下方，说明它是凸减的：便宜的前半段买走了绝大部分改善。
- \(R=0.2\) 处真实值 0.243 对参照值 0.4：花两成的钱买到五成的效果（坏时隙率从 0.5 降到 0.243，改善 \(0.257/0.5=51.4\%\)）。花到四成（\(R=0.4\)，\(\epsilon^\star=0.146\)）就买到七成（70.8%）。
- 数据点由 \(h^{-1}(1-R)\) 数值求根得到（在 \([0,1/2]\) 上对 \(h\) 求逆）。
到此为止我们得到了什么
- 一条能算到底的协调价签：两基站错开发射的最小速率是 \(1-h(\epsilon)\) 比特/时隙（\(\epsilon=0.1\) 时 0.531，\(\epsilon=0.01\) 时 0.919，完全错开时 1）。
- 反过来读，得到话费—代价曲线 \(\epsilon^\star(R)=h^{-1}(1-R)\)。它凸减，在 \(R=0\) 处无穷陡，第一个 0.1 比特买走 36.8% 的改善，最后一个只买 2.6%。
- 这条曲线是定理 4.1 与二元率失真定理的合成，两端点都能独立复核。
4.4 拓扑一变，答案就未知#
两节点的答案干净得像教科书习题。三节点开始，就不再是了。这一节要老实交代协调容量这门理论的边界在哪。本站后面要在这条边界上立猜想，边界画错了，猜想就没有意义。
定理 4.5（Cuff–Permuter–Cover 2010，定理 4、5：另外两个精确刻画的拓扑）【已解决】
（i）孤立节点（原文 Fig. 7）：节点 1 观测 \(X^n\) 并向节点 2 发消息，节点 3 收不到任何消息但自己有动作 \(Z\)，联合分布满足 \(p(x,y,z)=p(x)p(z)p(y\mid x,z)\)。经验协调的容量域是
（ii）级联（定理 5，\(X\to Y\to Z\)，两段链路速率 \(R_1,R_2\)）：容量域由
给出，且该域达到割集界（cut-set bound），这是原文在定理 5 之后的讨论里点明的 [1]。
物理意义
（i）说的是：协调目标里多了一个不收任何消息的第三方 \(Z\)。经验协调只看频率，\(Z\) 的动作序列可以事先约定好、写进码本，节点 2 事先就知道。于是节点 2 的输出不但要跟 \(X\) 配合，还要跟 \(Z\) 的节奏对上，价签变成 \(I(X;Y\mid Z)\)。
在本定理的模型里 \(X\) 与 \(Z\) 独立，由链式法则 \(I(X;Y,Z)=I(X;Z)+I(X;Y\mid Z)\) 且 \(I(X;Z)=0\)，得 \(I(X;Y\mid Z)=I(X;Y,Z)\ge I(X;Y)\)。多照顾一个人，只会更贵或持平。
（ii）说的是级联的两段各自要付什么：第一段要为"下游两个人加起来的行为"付钱，第二段只为最末端付钱。
行为分析
一般情况下，条件互信息 \(I(X;Y\mid Z)\) 可以比 \(I(X;Y)\) 大，也可以比它小，这是信息论的老陷阱。若 \(Z\) 与 \(X\) 相关、又能被节点 2 用上（类似 Wyner–Ziv 问题里的边信息），它能替消息解释掉一部分相关性，协调会变便宜。若 \(Z\) 与 \(X\) 独立，如本定理，它只是一项额外要求，协调只会更贵。
无线读法：共享的导频、时间戳这类与业务无关的公共序列，对经验协调并不省话费（定理 4.2 已说明公共随机性对经验协调无用）。能省话费的是与待协调的量相关的共享测量，例如双方都测到的同一个干扰。
只有节点 2 拿得到这份测量 \(Z\) 时，最小速率已有单字母刻画（Raginsky [11] 定理 2）：
下确界取遍满足马氏链 \(Z-X-U\)、且节点 2 用 \((Z,U)\) 的函数产生动作的辅助变量 \(U\)，形式上就是 Wyner–Ziv 率失真函数。取 \(U=Y\) 可见它不超过 \(I(X;Y)-I(Z;Y)\)，边信息确实让协调变便宜。
这一点与第二部第 7 章收尾的第一块警示牌（信息多不一定好）是同一族现象。
陷阱：广播与干扰型拓扑的协调容量，一般情形是开放问题
原文的定理 7、8 处理广播型与更一般的网络拓扑，但给出的是内界与外界（inner and outer bounds），不是精确刻画。原文自己写的是"对许多分布，定理 7 的界是紧的" [1]。
因此不得写成"协调容量已解决"。精确刻画目前只覆盖：两节点、孤立节点、级联，以及若干退化信源情形。
广播拓扑在一般情形下【开放】。一个基站同时协调多个基站，恰恰是无线最自然的拓扑。
这条边界对本站有直接后果：4.9 节的两基站命题必须建在两节点定理 4.1 上。要扩到三个及以上基站，只能说"落在定理 7 的内外界之间"，不能报一个确切的价签。
原文还留了一个明确的开放方向：定理 4.3(i) 处理的是"所有节点共享同一个公共随机源"，而每个子集各有自己独立的公共随机源的更丰富版本，作者列为 interesting open direction [1]。这在无线里不是纸上谈兵：簇内共享一个种子、簇间共享另一个种子，正是分层网络的日常结构。
工程落点：这条边界卡住了什么
- CoMP 簇内协调调度：三个及以上基站要"联合服从一个调度分布"，其最小回传速率没有闭式。工程上现有的做法（半静态资源划分、集中式调度器）都在回避这个问题。回避的方式是把拓扑强行退化成级联或星形（经协调器），而那恰好是有答案的两种拓扑之一。这不是巧合：能算的拓扑，正是工程上被选中的拓扑。
- ISAC 组网感知：多站协同照射一个目标，各站的波形/时隙选择要服从一个联合分布（避免互相致盲、同时保证覆盖）。三站以上同样落在开放区。
- 多智能体 LLM：\(K\) 个 agent 要"共同表现得像在执行同一个计划"，这是一个广播型协调问题（一个协调者对多个执行者）。速率口径的下界目前不存在。
到此为止我们得到了什么
- 协调容量这门理论的真实边界：精确刻画只有两节点、孤立节点、级联三类。
- 广播与一般网络只有内外界，一般情形【开放】。
- 因此本站的无线命题必须建在两节点定理上，三基站及以上只能说落在内外界之间。这条纪律决定了 4.9 节猜想的措辞。
4.5 换一个口径：到达一个均衡要多少比特#
到此为止的"目标"都是一个分布。工程和博弈里更常见的目标是一个函数或一个解概念，例如"算出最优功率"、"找到一个纯 Nash 均衡"、"达成一致"。这类目标的记账方式完全不同：每符号速率不再适用，要算的是一次性的总比特数，而且看最坏情形。
这是 Yao 1979 开创的通信复杂度（第三部第 6 章第一课已经完整教过双方模型）。本节只做一件事：把它用在均衡上，看会得到什么结果。
4.5.1 非耦合均衡程序#
定义 4.4（非耦合均衡程序与其通信复杂度，Hart–Mansour 2010 [2] 的口径，符号已改写）
\(N\) 名玩家，玩家 \(i\) 的动作集 \(A_i\)，\(|A_i|\le m\)。非耦合（uncoupled）指：玩家 \(i\) 初始时只知道自己的支付函数 \(u_i:\prod_jA_j\to\mathbb{R}\)，对别人的支付一无所知。
一个均衡程序是一个通信协议（谁在什么时候说什么，由已经说过的话与自己的私有输入决定），结束时所有玩家共同确定一个满足给定解概念的结果。其通信复杂度 \(\mathrm{CC}\) 是最坏输入下交换的总比特数；时间复杂度 \(\mathrm{tCC}\) 是轮数（每轮所有人可以同时各说一些话）。
这个定义在说什么
把"多个基站互相试探、逐步收敛到一个稳定工作点"这件事，抽象成"两个人各拿半张表、要一起指出表上的某一格"。它不对算法作任何假设。梯度、拍卖、强化学习、大模型对话，只要信息是这样分布的，下界一律适用。
三个解概念（速览，供没有博弈论基础的读者）
以两个基站各选一档功率为例，玩家 \(i\) 的支付 \(u_i(a_1,\dots,a_N)\) 是它自己的效用（速率减功耗）。
- 纯 Nash 均衡：一个确定的动作组合 \((a_1^\star,\dots,a_N^\star)\)，没有任何一个玩家能靠单方面改动作让自己的支付变好。它是第 2 章"人各最优"在目标不一致时的名字（定义 2.2 后的对照表）。有的博弈没有纯 Nash（如"石头剪刀布"）。
- 混合 Nash 均衡：允许每个玩家按一个概率分布随机选动作，各自独立抽签；要求没有人能靠单方面换分布提高期望支付。Nash 定理保证有限博弈一定有混合 Nash。
- 相关均衡（correlated equilibrium）：允许一个中立的"协调者"先按一个联合分布抽出一组建议 \((a_1,\dots,a_N)\)，把 \(a_i\) 私下告诉玩家 \(i\)；要求每个玩家在只知道自己那条建议的情况下，都不愿偏离它。混合 Nash 是相关均衡的特例（联合分布恰为乘积分布），所以相关均衡的集合更大、更容易"谈妥"。这就是下面定理 4.6 与 4.7 之间那个指数—多项式落差的直觉来源。
"解概念"就是"我们同意管什么叫谈妥了"。第 6 章会把它们连同粗相关均衡（CCE）排成一条阶梯。
4.5.2 三条定理#
定理 4.6（Hart–Mansour 2010：到纯 / 混合 Nash 需指数比特）【已解决】
记 \(\Gamma^N_m\) 为 \(N\) 人、每人至多 \(m\) 个动作的博弈族。这个 \(\Gamma\) 沿用 Hart–Mansour 的记法，与定理 4.3 的"必要条件熵"\(\Gamma\) 无关。则：
-
（原文定理 3）对每个 \(m\ge2\)，任何纯 Nash 均衡程序满足
\[ \mathrm{CC}(\mathrm{PURE},\Gamma^N_m)\ \ge\ \mathrm{CC}(\mathrm{PURE},\Gamma^N_2)\ =\ \Omega(2^N). \]指数是对玩家数 \(N\) 而言，动作数固定为 2 即可。证明由集合不交问题 \(\mathrm{DISJ}\) 归约得到。
集合不交（set disjointness）是通信复杂度里最基本的难题：两人各持全集 \(S\) 的一个子集 \(A\)、\(B\)，要判定 \(A\cap B\) 是否为空。原文定理 1 说 \(\mathrm{CC}(\mathrm{DISJ}_S)=|S|\)，即最坏情形下差不多只能把自己的子集逐元素（每元素 1 比特）告诉对方。
"归约"是把任一 DISJ 实例改写成一个博弈，使得找到纯 Nash 就能回答 DISJ，所以找纯 Nash 至少与 DISJ 一样贵。此处取 \(S=\{0,1\}^N\)（全部 \(2^N\) 个动作组合），\(|S|=2^N\)，指数由此而来。
-
（原文命题 2 + 定理 3）轮数口径：每轮最多传 \(O(N)\) 比特，故 \(\mathrm{tCC}(\mathrm{PURE},\Gamma^N_2)=\Omega(2^N/N)\)。
-
（原文定理 4）即使把博弈族限制到保证存在纯 Nash 的有限改进性质（finite improvement property，FIP）类 \(\mathrm{FIP}^N_m\)（\(m\ge4\)），仍有 \(\Omega(2^{N/2})\)。
FIP 指：任何一串"某个玩家单方面换动作并严格获益"的改进步都在有限步内停下。停下之处没人能再改进，就是纯 Nash（有限势博弈是典型例子）。
-
（原文定理 7）存在博弈上的概率分布使任何纯 Nash 程序的期望通信复杂度也是 \(\Omega(2^N)\)。指数不是靠罕见的坏例撑起来的。
-
（原文定理 10）混合 Nash 同样指数：存在二元动作博弈族 \(U^N\subset\Gamma^N_2\)（编码 1 比特、magnitude \(O(N)\) 比特）使任何混合 Nash 程序满足 \(\mathrm{CC}(\mathrm{MIXED},U^N)=\Omega(2^N)\)。
定理 4.7（Hart–Mansour 2010，定理 17：相关均衡有多项式程序）【已解决（上界）】
令 \(U^N_u\subset\Gamma^N_2\) 为 \(N\) 人二元动作、整数支付且 magnitude 至多 \(u\) 比特的博弈族（每个支付值都是能用 \(u\) 个二进制位写下的整数）。则存在一个相关均衡程序 \(\Pi_{\mathrm{CORR}}\) 使
构造是把 Papadimitriou 2005 的椭球算法跑在 Hart–Schmeidler 框架里，每一步只需各玩家广播自己的期望支付 [2]。
陷阱：这是"下界 vs 上界"的对照，不是两个下界
定理 4.6 给的是下界（任何程序都要这么多），定理 4.7 给的是上界（存在一个程序只要这么多），而且是有前提的上界：整数支付、magnitude 有界、二元动作。原文没有给出多项式的显式次数。
因此：
- 可以写"存在多项式的相关均衡程序"；
- 不可以写"相关均衡的通信复杂度是多项式"（那把上界当成了紧界）；
- 不可以写 \(O(N^3)\) 之类的具体次数（原文没给）。
本部后面各章引用这条对照时都按这个措辞。
【本站提法】解概念决定话费的量级——但这是对原文的重述，不是本站的发现
把定理 4.6 与定理 4.7 并排读：同一批玩家、同一个博弈族，只因为要的"解"换了一个名字，最坏话费从指数掉到多项式。输入的规模没变，玩家的知识没变，变的只是"我们同意管什么叫谈妥了"。
这句话本站叫作"解概念决定话费的量级"，并在第 9 章把它列为"协商的最小话费"那条缺失定理的第一条相变。但必须写明学术产权：Hart 与 Mansour 自己就是这样解读的。原文明确写道，纯 / 混合 Nash 的指数性"is a result of the equilibrium notion"（是解概念造成的），并且特意先反驳了"输入本来就指数大所以不奇怪"这个直觉 [2]。本站做的是把它翻译到无线资源分配的语境，不是重新发现它。
这条相变还会在第 6 章从另一头再出现一次：no-regret 学习的时间平均收敛到粗相关均衡（CCE），而不是 Nash。便宜的均衡，恰好就是学习动力学自然到达的均衡。话费与可学性指向同一个解概念，这不是巧合。
4.5.3 双人多动作：另一个方向的爆炸#
Hart–Mansour 的指数是对玩家数的。玩家只有两个、但动作很多时，爆炸换了个方向。
定理 4.8（Conitzer–Sandholm 2004：双人 \(m\times m\) 博弈）【已解决】
双人博弈，各有 \(m\) 个动作，合作式通信模型（双方只想尽快算出解，无策略性）。则纯 Nash 的通信复杂度是
确定性上界 \(O(m^2)\)（原文定理 2）、非确定性下界 \(\Omega(m^2)\)（原文定理 3，即使支付只取 0/1）。
非确定性通信复杂度允许一个全知的"证明者"把答案连同证据递给双方，双方只需核验，证据长度计入话费。它永远不超过确定性复杂度，所以非确定性下界比确定性下界更强。
此外：若承诺均衡唯一，降到 \(\Theta(m\log m)\)（定理 4、5）；迭代严格 / 弱劣势剔除也是 \(\Theta(m\log m)\) 量级（定理 6–10）[4]。
原文用 \(n\) 记动作数，本部统一改写为 \(m\)。
物理意义
\(\Theta(m^2)\) 是把整张支付矩阵说一遍的量级。这意味着在最坏情形下，"找一个纯 Nash"没有任何可压缩性：没法用一个聪明的协议先算出"重要的那几行"。
相比之下，"唯一均衡"或"迭代劣势剔除"这类有额外结构的问题降到 \(\Theta(m\log m)\)，也就是"说 \(m\) 个动作的名字"的量级。结构值一个 \(m/\log m\) 的因子。
推论 4.9（通信比特 ⟹ 学习轮数，Conitzer–Sandholm 2004 [4]）【已解决】
在重复博弈的学习框架里，每一轮玩家从对方那里看到的只是"选了哪个动作"，至多 \(\log_2m\) 比特（双方合计 \(2\log_2m\)）。因此若某解概念的通信复杂度下界为 \(\Omega(f(m))\) 比特，则任何学习算法在最坏情形下需要
代入定理 4.8 的纯 Nash：\(T=\Omega(m^2/\log m)\)。若每轮的最小损失为 \(\mu\)，则累积代价下界 \(\Omega(\mu f(m)/\log m)\)；若只有 \(m_0<m\) 个"不至于太贵"的动作可用，分母换成 \(\log m_0\)。
物理意义
这是本部唯一一条不对学习算法的具体形式作假设的下界，原文自称"arguably the only truly universal lower bound"。它不问你用的是虚拟对策、乘性权重、Q-learning 还是一个大模型：只要每轮流过去的信息只有"你选了哪个动作"，轮数就被通信复杂度除以每轮容量卡死。
关于随机化学习过程的适用范围
严格说，推论 4.9 直接覆盖确定性的学习过程。原文对随机化只在第 3 节括注一句：愚弄集方法给出的下界对非确定性通信复杂度成立，因而对随机化通信复杂度也成立。
这对不许出错的随机化协议是对的。若允许以小概率出错，非确定性下界一般不能直接搬用：对 \(n\) 比特输入的相等函数，愚弄集给出 \(n\) 比特下界，允许出错的随机化协议却只需 \(O(\log n)\) 比特。这时要另证随机化下界。
算例 4.2（八档功率的两基站：找一个纯 Nash 要说多少话、要试多少轮）【本站演算】
场景。 两个基站，各有 \(m=8\) 档发射功率（例如 \(\{0,3,6,\dots,21\}\) dBm）。每个基站的效用是自己的速率减去功率开销，取值先粗量化成 0/1（"这一格我能不能接受"）。两站互不知道对方的效用表（非耦合），要共同找出一个纯 Nash 功率对。
第 1 步：下界。 由定理 4.8，最坏情形需 \(\Omega(m^2)=\Omega(64)\) 比特。取下界中的常数为 1 作为"量级读数"：约 64 比特。
第 2 步：上界（构造一个协议）。 基站 1 把自己整张 0/1 效用表发出去：\(m^2=64\) 比特。基站 2 现在两张表都有，本地算出一个纯 Nash（计算在 Yao 模型里免费），再广播它是哪一格：\(\lceil\log_2 64\rceil=6\) 比特。总计 70 比特。
第 3 步：轮数。 每轮双方各暴露一个动作，合计 \(2\log_28=6\) 比特。由推论 4.9，
第 4 步：换个规模看趋势。
| 功率档数 \(m\) | 比特下界量级 \(m^2\) | 构造协议 \(m^2+\lceil2\log_2m\rceil\) | 每轮比特 \(2\log_2m\) | 轮数量级 \(m^2/(2\log_2m)\) |
|---|---|---|---|---|
| 2 | 4 | 6 | 2 | 2.0 |
| 4 | 16 | 20 | 4 | 4.0 |
| 8 | 64 | 70 | 6 | 10.7 |
| 16 | 256 | 264 | 8 | 32.0 |
| 32 | 1024 | 1034 | 10 | 102.4 |
第 5 步：与第三部的 56 比特对照，但要小心。 第三部第 6 章算出两小区功控解到 \(\varepsilon=0.01\) bit/s/Hz 精度需 \(C(\varepsilon)\lesssim56\) 比特。这里的 64–70 比特看着同量级，但两者问的不是同一件事：
- \(C(\varepsilon)\) 是团队问题（目标一致，求 \(\varepsilon\)-最优），话费随精度按 \(\log(1/\varepsilon)\) 增长。
- 定理 4.8 是博弈问题（目标冲突，求一个均衡），话费随动作数按 \(m^2\) 增长。
同量级是巧合，趋势完全不同：把功率档数从 8 加到 32，Nash 的话费涨 16 倍；把精度从 \(10^{-2}\) 提到 \(10^{-4}\)，\(C(\varepsilon)\) 的上界只从 56 涨到 84 比特。第三部的表达式是 \(4\lceil\log_2(2\times1.33\times60/\varepsilon)\rceil\)，精度每提高 100 倍多付 \(4\log_2100\approx27\) 比特。
校验（三条）
- 上下界夹逼自洽。 下界 \(c\cdot64\)、上界 70，两者同为 \(\Theta(m^2)\)。比值 \(70/64=1.094\)，即构造协议只比"说完整张表"多 9.4%（那 6 比特是宣布答案的开销）✓。
- 轮数与比特互为倒算。 \(11\ \text{轮}\times6\ \text{比特/轮}=66\) 比特，与第 1 步的 64 比特一致，差的 2 比特来自向上取整。把轮数乘回每轮容量应当回到比特下界，这是推论 4.9 的定义式，所以自洽 ✓。
- 极限退化。
- \(m=2\)：4 比特下界、6 比特协议、2 轮。\(2\times2\) 博弈只有四格，"说清两张 \(2\times2\) 的 0/1 表"确实是常数比特，与"\(\Theta(m^2)\) 在 \(m=2\) 处退化为常数"一致 ✓。
- \(m\to\infty\)：\(m^2/(2\log_2m)\to\infty\)，但比 \(m^2\) 慢。把 \(m\) 翻倍，比特涨 4 倍，轮数涨 \(4\log_2m/\log_2(2m)\) 倍；\(m=8\to16\) 给 \(32/10.67=3.0\)，而 \(4\times3/4=3.0\) ✓。
行为分析（把 Hart–Mansour 的指数代成工程数字）
\(N\) 个小区、每个小区两档功率（开/关），非耦合，要一个纯 Nash：
| 小区数 \(N\) | 比特量级 \(2^N\) | 轮数量级 \(2^N/N\) | 在 100 Mb/s 回传上耗时 |
|---|---|---|---|
| 10 | \(1.02\times10^{3}\) | 102 | 10 μs |
| 20 | \(1.05\times10^{6}\) | \(5.2\times10^{4}\) | 10.5 ms |
| 30 | \(1.07\times10^{9}\) | \(3.6\times10^{7}\) | 10.7 s |
| 40 | \(1.10\times10^{12}\) | \(2.8\times10^{10}\) | 3.1 小时 |
每多 10 个小区，话费乘 1024。20 个小区已经吃掉一个 10 ms 级的控制环，30 个小区就彻底不可能。
作为对照，若相关均衡程序的多项式次数是 3（原文未给次数，此处仅作量级示意），\(N=40\) 时是 \(40^3=6.4\times10^4\) 比特 \(=0.64\) ms。同一个网络，换一个解概念，从三小时变成半毫秒。
到此为止我们得到了什么
- 非耦合地到达纯或混合 Nash，在最坏情形要指数于玩家数的总比特（定理 4.6）。到达相关均衡存在多项式程序（定理 4.7，只有上界且有前提）。
- 双人 \(m\times m\) 的纯 Nash 是 \(\Theta(m^2)\) 比特（定理 4.8），并可换算成 \(\Omega(m^2/\log m)\) 的学习轮数下界（推论 4.9），这是唯一一条不对算法作假设的下界。
- 8 档功率的两基站要约 64–70 比特、\(\gtrsim11\) 轮，而 \(N=30\) 个小区的纯 Nash 在 100 Mb/s 回传上要 10.7 秒。
4.6 开口之前已经共同知道多少：Gács–Körner 与 Wyner#
前两节都在算"要说多少"。这一节问一个更早的问题：有没有一部分是不用说的？
生活里的例子：两个人约在"老地方"见面。如果"老地方"是双方都已经知道的同一个概念，这三个字就够了；如果不是，就得从头描述地址。双方已经共同知道的那部分，传输价格是零。
信息论把"共同知道"做成了两个互不相同的量。第二部第 3 章已经给过口径，这里原样沿用并补上算例。
4.6.1 两个定义与三个量的排序#
定义 4.5（Gács–Körner 公共信息，[6]）
设 \((X,Y)\sim p(x,y)\)。称 \((f,g)\) 是一对公共函数，若 \(f(X)=g(Y)\) 几乎必然成立。Gács–Körner 公共信息定义为
怎么算
在 \(\mathcal{X}\times\mathcal{Y}\) 上画一张二部图，\(x\) 与 \(y\) 之间有边当且仅当 \(p(x,y)>0\)。\(f(X)=g(Y)\) 的最细公共函数就是连通分量的编号。
理由有两层。若 \(p(x,y)>0\) 而 \(f(x)\ne g(y)\)，事件 \(f(X)\ne g(Y)\) 就有正概率，违反"几乎必然相等"。所以每条边两端的取值相同，沿边传下去，同一连通分量里 \(f\)、\(g\) 取同一个值。反过来，"所在分量的编号"本身就是一对合法的公共函数，再把分量合并只会让熵变小。
于是 \(K_{\mathrm{GK}}\) 等于这个连通分量标签的熵。
与第二部的接口
按第二部的口径，两个决策者的公共知识是各自划分之交，那是一个划分（集合）。\(K_{\mathrm{GK}}\) 是这个划分的熵（一个数）。二者是两个不同的对象，不要写成等式。
定义 4.6（Wyner 公共信息，[7]）
极小化取遍所有使 \(X\) 与 \(Y\) 在给定 \(W\) 时条件独立的辅助变量 \(W\)。
怎么读
\(W\) 是一个"解释变量"，也就是能把 \(X\) 与 \(Y\) 之间全部相关性解释干净的公共起因。Wyner 公共信息是最省的那个解释要花多少比特。
注意 \(W\) 一般不是样本空间上的函数（不像 GK 那样必须能从两边各自算出来），所以它不是格运算。
命题 4.10（三个量的排序）【已解决（经典）】
对任意 \((X,Y)\)，
且两个不等号一般都是严格的 [6][7]。
证明思路（两行）
左边：取达到最大的公共函数 \(V=f(X)=g(Y)\)。因为 \(V=g(Y)\)，\(X\to Y\to V\) 成马氏链，数据处理给出 \(I(X;Y)\ge I(X;V)\)。又因为 \(V=f(X)\)，\(H(V\mid X)=0\)，所以 \(I(X;V)=H(V)-H(V\mid X)=H(V)=K_{\mathrm{GK}}\)。
右边：对任何满足 \(X-W-Y\) 的 \(W\)，
- 第一个不等号：链式法则 \(I(X,Y;W)=I(X;W)+I(Y;W\mid X)\) 加上后一项非负。
- 第二个不等号：又是数据处理，马氏链 \(X-W-Y\) 给出 \(I(X;Y)\le I(X;W)\)。
对所有这样的 \(W\) 取下确界即得。\(\blacksquare\)
物理意义
三个量是同一件事的三种口径：
- \(K_{\mathrm{GK}}\)：两边各自能独立算出来的那一部分，也就是零通信、零误差就已经共享的公共知识。
- \(I(X;Y)\)：统计上的相关量。协调容量（定理 4.1）用的就是它。
- \(C_{\mathrm{Wyner}}\)：要从零造出这份相关性，需要广播多少比特。这是一个"生成侧"的价格。
Cuff 的定理 4.3(i)（无通信、只靠公共随机性协调三个节点）用的是 Wyner 公共信息的三方推广，这不是巧合：Wyner 问题的操作意义，就是"从公共随机源造相关性"。
4.6.2 算例 4.3：相关但没有公共部分#
算例 4.3（同一个 \(2\times2\) 分布上的三个量：相关但没有公共部分）【本站演算】
仍取算例 4.1 的目标分布（\(P_1\) 均匀，\(\Pr(P_1\ne P_2)=1-\epsilon\)，\(\Pr(P_1=P_2)=\epsilon\)）。把 \(P_2\) 取反后它就是标准的二元对称相关源（DSBS），交叉概率 \(\epsilon\)；三个量都不受这个一一映射影响。
（a）Gács–Körner。 当 \(0<\epsilon<1\) 时，四个格子 \((\text{开},\text{开}),(\text{开},\text{关}),(\text{关},\text{开}),(\text{关},\text{关})\) 全部有正概率，所以定义 4.5 那张二部图是连通的（\(P_1=\text{开}\) 与 \(P_1=\text{关}\) 通过任意一个 \(P_2\) 取值相连）。连通图只有一个分量，公共函数只能取常数，于是
而 \(\epsilon=0\) 时只有两个格子有正概率，图断成两个分量，\(K_{\mathrm{GK}}=H(\mathrm{Bern}(1/2))=1\) 比特。\(K_{\mathrm{GK}}\) 在 \(\epsilon=0\) 处从 1 跳到 0，这是 Gács–Körner 1973 那篇论文的核心现象：公共信息对分布不连续。
（b）互信息。 算例 4.1 已给：\(I=1-h(\epsilon)\)。
（c）Wyner。 取 \(W\sim\mathrm{Bern}(1/2)\)，\(X=W\oplus N_1\)、\(\tilde Y=W\oplus N_2\)，\(N_1,N_2\sim\mathrm{Bern}(a)\) 独立（\(\tilde Y\) 是取反后的 \(P_2\)）。这样构造的 \(W\) 自动满足 \(X-W-\tilde Y\)。两步：
-
定 \(a\)。 \(X\oplus\tilde Y=N_1\oplus N_2\)，其为 1 的概率是 \(2a(1-a)\)，必须等于 \(\epsilon\)。解 \(2a^2-2a+\epsilon=0\) 取小根：
\[ a=\frac{1-\sqrt{1-2\epsilon}}{2}. \] -
算 \(I(X,\tilde Y;W)\)。 \(I=H(X,\tilde Y)-H(X,\tilde Y\mid W)\)。前项 \(H(X,\tilde Y)=H(X)+H(\tilde Y\mid X)=1+h(\epsilon)\)。后项因给定 \(W\) 时 \(X,\tilde Y\) 条件独立、各自是 \(W\) 过一个 \(\mathrm{Bern}(a)\) 翻转，故 \(=2h(a)\)。于是
\[ C_{\mathrm{Wyner}}\ \le\ 1+h(\epsilon)-2h(a),\qquad a=\frac{1-\sqrt{1-2\epsilon}}{2}. \]
这是本站构造给出的上界。Wyner 1975 [7] 对二元对称相关源证明了它就是最小值，即 \(C_{\mathrm{Wyner}}=1+h(\epsilon)-2h(a)\)（\(0\le\epsilon\le1/2\)）【二手已核：据 Yu 2024 对 Wyner 结果的转述（arXiv:2407.06132），本站未读 Wyner 原文】。
数字
| \(\epsilon\) | \(K_{\mathrm{GK}}\) | \(I(P_1;P_2)\) | \(a\) | \(C_{\mathrm{Wyner}}\) |
|---|---|---|---|---|
| 0 | 1.000 | 1.000 | 0 | 1.000 |
| 0.001 | 0 | 0.988592 | 0.000500 | 0.998994 |
| 0.01 | 0 | 0.919207 | 0.005025 | 0.989578 |
| 0.1 | 0 | 0.531004 | 0.052786 | 0.872761 |
| 0.2 | 0 | 0.278072 | 0.112702 | 0.705905 |
| 0.3 | 0 | 0.118709 | 0.183772 | 0.504771 |
| 0.5 | 0 | 0 | 0.5 | 0 |
读法
\(\epsilon=0.1\) 那一行最能说明问题：两个基站的决策高度相关（互信息 0.531 比特），却没有任何一个非平凡的公共函数（\(K_{\mathrm{GK}}=0\)）。而要从一个公共随机源把这份相关性造出来，得花 0.873 比特。三个数一个比一个大，中间隔着 0.531 与 0.873 这样的鸿沟。
校验（四条）
- 构造自洽。 \(a=0.052786\) 代回 \(2a(1-a)=2\times0.052786\times0.947214=0.100000=\epsilon\) ✓。
- 不等式链逐行成立。 \(\epsilon=0.1\)：\(0\le0.531004\le0.872761\) ✓；\(\epsilon=0.3\)：\(0\le0.118709\le0.504771\) ✓（命题 4.10）。
- 两个极限。
- \(\epsilon=0\)：\(a=0\)，\(C_{\mathrm{Wyner}}=1+0-0=1\)，同时 \(I=1\)、\(K_{\mathrm{GK}}=1\)。三个量重合于 \(H(P_1)=1\) 比特，正确（\(P_2\) 完全由 \(P_1\) 决定，公共部分就是全部）✓。
- \(\epsilon=1/2\)：\(a=1/2\)，\(C_{\mathrm{Wyner}}=1+1-2=0\)，\(I=0\)，\(K_{\mathrm{GK}}=0\)。三个量全零，正确（独立）✓。
- 数值复核一个中间值。 \(\epsilon=0.1\)：\(h(0.1)=0.468996\)，\(h(0.052786)=0.298117\)，\(1+0.468996-2\times0.298117=1.468996-0.596234=0.872762\)，与表中 0.872761 在第六位一致（舍入）✓。
4.6.3 工程含义：两张信道知识地图#
工程含义：地图里"已经共同知道"的那部分是免费的
把 \(X,Y\) 换成两个基站各自的信道知识地图（第一部第 7 章的 CKM），三个量分别回答：
- \(K_{\mathrm{GK}}\)：两边不用通信就已经一致的那部分，例如同一份 3GPP 定义的码本索引、同一张标准化的地形/建筑物栅格、同一个公开的时间基准。这部分零话费。
- \(I\)：两张地图的统计重叠。协调的价签就按它计（定理 4.1）。
- \(C_{\mathrm{Wyner}}\)：要用一个中心节点广播出这份一致性，得播多少。
算例 4.3 给出的警告很硬：\(K_{\mathrm{GK}}\) 在 \(\epsilon>0\) 时塌到零。两张地图哪怕只有千分之一的概率不一致（\(\epsilon=0.001\)），"零通信就共享的部分"也从 1 比特变成 0，而互信息还有 0.989 比特。"几乎共同知道"在 GK 的意义下等于"完全不共同知道"。
这是 3GPP 讨论"两侧模型互操作"时的真实困难。两端各自训练出来的 CSI 编解码器几乎一致，但那个"几乎"让它们没有可零率同步的公共部分，必须真的花比特去对齐。
第三部第 6 章把这件事读成"建立公共知识的通信复杂度问题"，本章补上它的信息论侧解释：公共信息对分布不连续，所以"对齐"不能靠"差不多"。
到此为止我们得到了什么
- 开口之前的三个量：\(K_{\mathrm{GK}}\)（零率就共享的部分）、\(I\)（协调价签的计价基准）、\(C_{\mathrm{Wyner}}\)（从公共随机源造出相关性的价格）。排序是 \(K_{\mathrm{GK}}\le I\le C_{\mathrm{Wyner}}\)。
- 在算例 4.1 的同一个分布上，三者是 \(0\le0.531\le0.873\)（\(\epsilon=0.1\)）。
- \(K_{\mathrm{GK}}\) 在 \(\epsilon=0\) 处从 1 跳到 0："几乎共同知道"在 GK 意义下等于"完全不知道"。
4.7 多方：广播是资源，不是负担#
前面三节都是两个人（加上一个孤立的旁观者）。真实网络是 \(K\) 个小区。多方通信复杂度里，消息怎么送本身就改变答案。
第三部第 6 章已经完整立过这条分离，本章只做回链与确认，不重复展开：
定理 4.11（黑板 vs coordinator 的分离；第三部第 6 章已立，此处回链）【已解决】
\(k\) 方 number-in-hand 集合不交问题 \(\mathrm{DISJ}_{n,k}\)（各方持 \(X_i\subseteq[n]\)，判定 \(\bigcap_iX_i\) 是否为空）满足
前者见 Phillips–Verbin–Zhang 2012 [9]，后者的紧界见 Braverman 等 2013 [10]。
记号提醒
- 这里的 \(R\) 是随机化通信复杂度（允许以小概率出错时的最坏总比特数），不是 4.2 节的协调速率 \(R\)；\(n\) 是全集大小，不是块长。
- number-in-hand 指每一方只看得到自己的 \(X_i\)。黑板模型里每条消息所有人可见，coordinator 模型里各方只能与一个中心节点点对点通话。
- \(k=2\) 时就是定理 4.6 里的 \(\mathrm{DISJ}\)。
物理意义（沿用第三部口径）
点对点世界里，一条信息要让 \(k\) 个人知道就得说 \(k\) 遍，公共知识按人头计费；黑板世界里说一遍就够。无线的广播介质天然是黑板，这是无线相对于有线分布式系统的结构性优势，而且它是定理，不是口号。
行为分析
\(k=100\) 个小区：coordinator 模型话费 \(\sim100n\)，黑板模型 \(\sim n\log_2100\approx6.6n\)，差十五倍。
第三部留下的钉子在这里原样保留：没有人把无线资源分配问题归约到多方 \(\mathrm{DISJ}\) 上，所以这个 \(\Theta(k/\log k)\) 的分离在无线语境里还没有兑现【开放，第三部与本部共有的钉子】。
一条给第 5 章的伏笔：共享随机性只值 \(O(\log n)\)
通信复杂度还有第三个坐标：两端有没有共享的随机比特。Newman 1991 [5] 的定理（标准教科书形式）说
\(n\) 为输入比特长度；\(R^{\mathrm{priv}}\)、\(R^{\mathrm{pub}}\) 分别是只用私有随机比特、允许公共随机比特时的随机化通信复杂度，下标是允许的出错概率（改用私有随机性后，出错概率从 \(\varepsilon\) 放宽到 \(\varepsilon+\delta\)）。
这是后来教科书的写法。Newman 原文的定理 1.1 写成
其中复杂度按最坏输入上的期望比特数计，出错概率按乘性放宽，公共比特的话费外面还套着一个常数因子，但"只差对数项"的结论相同。
读法
公共随机性最多帮你省 \(O(\log n)\) 比特。它便宜得几乎白送，也就意味着它作为一种"共享资源"几乎不值钱。
第 5 章会把这条负面结果当作阶梯的第一级，再问：如果两端共享的是一个生成模型，而不是随机数，那一级值多少？（那里的硬锚点是推测解码的接受率 \(\alpha=1-\mathrm{TV}(p,q)\)。）
还有一条更深的伏笔：Braverman–Rao 的信息复杂度 \(\mathrm{IC}(f,\mu)\) 本身就以一个共享先验 \(\mu\) 为参数，并满足"信息 = 摊销通信"\(\mathrm{IC}(f,\mu)=\lim_{n\to\infty}D_\mu(f^{\otimes n})/n\) [8]。"相对于共享模型来度量通信"，信息论里早有成熟框架。第 5 章的三级阶梯必须诚实地建在它上面，不能假装从零发明。
到此为止我们得到了什么
- 多方口径的一条已证分离：黑板（广播）与 coordinator（点对点）在 \(k\) 方集合不交上差 \(\Theta(k/\log k)\)，广播介质因此是资源，不是负担。
- 一条待兑现的钉子：把无线资源分配归约到多方 DISJ 仍是开放的。
- 两条给第 5 章的伏笔：公共随机性最多值 \(O(\log n)\)（Newman）；"相对于共享先验度量通信"已有信息复杂度这一成熟框架（Braverman–Rao）。
4.8 三个切面一张表：量纲必须分栏#
现在可以把三门理论摆在一起了。但摆之前先立一条纪律。
4.8.1 三种比特与分栏话费表#
陷阱（本章最容易犯的硬伤）：三种"比特"不是同一种比特
- Cuff 的 \(R\) 是每信源符号的渐近速率（\(n\to\infty\)，块编码，平均意义）。单位：比特/符号。
- Hart–Mansour 与 Conitzer–Sandholm 的是一次性的总比特数，最坏情形，有限。单位：比特。
- 第三部第 6 章的 \(C(\varepsilon)\lesssim56\) 比特属于后者。
- \(K_{\mathrm{GK}}\) 是熵，是"零率可提取"的渐近速率，又是另一种记账。
把 \(I(X;Y)=0.531\) 与 \(56\) 比特并排比大小，是量纲错误。下面的表因此必须分栏写清"口径 / 渐近方式 / 最坏还是平均"。
【本站提法】协商话费表：三个切面，三种记账
| 协调容量（Cuff 等 [1]） | 通信复杂度（Hart–Mansour [2]、Conitzer–Sandholm [4]） | 公共信息（GK [6]、Wyner [7]） | |
|---|---|---|---|
| 要达成什么 | 动作服从给定联合分布 | 算对一个函数 / 解概念 | ——（是"已有的"而非"要达成的"） |
| 单位（口径） | 比特 / 符号（速率） | 总比特数 | 比特（熵，零率可提取） |
| 渐近方式 | 块长 \(n\to\infty\) | 有限、一次性 | 块长 \(n\to\infty\)（零误差可提取） |
| 最坏还是平均 | 平均（依概率 / 总变差） | 最坏情形 | 依分布定义 |
| 两方的答案 | \(R^\star=I(X;Y)\)（定理 4.1） | 纯 Nash：\(\Theta(m^2)\) 比特（定理 4.8） | \(K_{\mathrm{GK}}\) = 连通分量标签的熵 |
| 多方的答案 | 只有内外界，一般【开放】 | 纯 Nash \(\Omega(2^N)\)；相关均衡有 poly 上界（定理 4.6、4.7） | 三方推广见定理 4.3(i) |
| 无线里的实例 | 两基站错开发射：\(1-h(\epsilon)\)（算例 4.1） | 8 档功率找 Nash：约 64–70 比特（算例 4.2） | 标准化码本 / 公共时基（算例 4.3 的讨论） |
| 本站已有的锚 | 命题 4.4 的价签曲线 | 第三部 \(C(\varepsilon)\lesssim56\) 比特（同为总比特口径） | 第二部第 3 章"格的交是划分、GK 是它的熵" |
| 回答不了什么 | 广播 / 干扰拓扑；有限块长 | 常常太松（最坏情形）；相关均衡侧只有上界且无显式次数 | 对分布不连续；"几乎共享"不算共享 |
注意第一列与第二列的最后一行不能对减。\(C(\varepsilon)=56\) 比特与 \(R^\star=0.531\) 比特/时隙如果一定要放在一起看，唯一合法的读法是：56 比特是一次性建立共识的开销，0.531 比特/时隙是此后每时隙维持默契的开销。一个是安装费，一个是月租费。
本站把这个区分写成一句话：建立公共知识按次收费，维持协调按时收费。【本站提法】
4.8.2 三问顺序#
这张表还可以读成一个决策顺序。
flowchart TD
A["$$N$$ 个节点要协同行动"] --> B{{"第一问<br/>开口之前已经共同知道多少？"}}
B --> C["Gács–Körner 公共信息<br/>零率就能同步的那部分<br/>注意它对分布不连续<br/>几乎一致 = 完全不一致"]
C --> D{{"第二问<br/>目标是一个分布，<br/>还是一个函数 / 解概念？"}}
D -->|"分布：每时隙的联合行为"| E["协调容量<br/>单位 比特每符号，<br/>块长趋于无穷，平均意义<br/>两节点 $$R$$ 大于 $$I(X;Y)$$"]
D -->|"函数或均衡：一次性算对"| F["通信复杂度<br/>单位 总比特，有限，最坏情形<br/>纯 Nash 指数<br/>相关均衡有多项式上界"]
E --> G{{"第三问<br/>还要多强？经验协调够不够？"}}
G -->|"经验频率对就行"| H["不需要公共随机性，定理 4.2"]
G -->|"整条序列都要像"| I["要买公共随机性，定理 4.3"]
F --> J{{"第三问<br/>广播还是点对点？"}}
H --> J
I --> J
J -->|"广播 黑板"| K["$$k$$ 方 DISJ 下界<br/>约 $$n\log k$$ 加 $$k$$"]
J -->|"点对点 coordinator"| L["$$k$$ 方 DISJ 下界 约 $$nk$$，<br/>贵 $$\Theta(k/\log k)$$ 倍"]怎么读这张图
- 这是本站给"协商要花多少钱"设计的三问顺序，图上每个方框都对应本章一条有编号的定理或定义。
- 分布目标那一支走协调容量与经验/强协调的分级，函数或解概念目标那一支走通信复杂度。两支在第三问（介质是广播还是点对点）汇合，因为介质的影响与目标类型无关。
- 图是叙事脉络，不是数值。三支的比特单位互不相同，见上表的分栏。
为什么三问的顺序不能换
- 第一问必须在最前：\(K_{\mathrm{GK}}\) 是免费的部分，不先扣掉它，后面两问的答案都会高估。
- 第二问决定用哪套记账（速率还是总比特），换了就会写出量纲错误的表。
- 第三问只影响常数与 \(k\) 的因子，所以放最后。
到此为止我们得到了什么
- 一张分栏的协商话费表与一条三问顺序。三门理论各答一个切面，但单位、渐近方式与最坏/平均口径三者全不相同，不能混栏比较。
- 本站把 \(C(\varepsilon)\) 与协调速率的关系读成"建立公共知识按次收费、维持协调按时收费"。
4.9 从话费到代价：协调价签接回团队问题#
第 2 章的猜想 2.6 问的是：多花 \(\nu_{\mathrm{b}}\) 比特能省下多少团队代价？
那里两端已知：\(\nu_{\mathrm{b}}=0\) 由 Ho–Chu 定理 2.5 给出，\(\nu_{\mathrm{b}}=\infty\) 由算例 2.2 的闭式给出 8.00%。中段形状未知，猜想那条曲线是凹增，且在零点附近线性。
命题 4.4 给出了这个问句的第一个能算到底的实例。把它按猜想 2.6 的参数化重写一遍。
4.9.1 命题 4.12：价签曲线的形状#
命题 4.12（协调价签曲线的形状：对猜想 2.6 细则的一个可算样本）【本站演算】
在算例 4.1 的两基站错开模型中，把"团队代价"取为坏时隙率、把"嵌套亏损"\(\nu_{\mathrm{b}}\) 取为"离完全协调还差多少比特/时隙"，即 \(\nu_{\mathrm{b}}=1-R\)。则代价缺口
满足：\(g(0)=0\)、\(g(1)=1/2\)、\(g\) 单调增且凸，且
证明
\(g=h^{-1}\) 在 \([0,1]\to[0,1/2]\) 上是 \(h|_{[0,1/2]}\) 的反函数。\(h\) 在 \([0,1/2]\) 上严格增且凹（\(h''(x)=-\frac{1}{x(1-x)\ln2}<0\)），故其反函数严格增且凸。
理由看导数：反函数求导给 \(g'(\nu)=1/h'(g(\nu))\)，其中 \(h'(x)=\log_2\frac{1-x}{x}\)。\(\nu\) 增大时 \(g(\nu)\) 增大，而 \(h\) 凹意味着 \(h'\) 递减，于是 \(h'(g(\nu))\) 递减、\(g'(\nu)\) 递增，导数递增就是凸。
同一个导数式还给出零点斜率：\(\nu\to0^+\) 时 \(g(\nu)\to0\)、\(h'\to+\infty\)，故 \(g'\to0\)。\(\blacksquare\)
物理意义
翻译成工程语言："最后一个比特"买到的改善极小，"第一个比特"买到的改善极大。具体地：
- \(\nu_{\mathrm{b}}=0.0114\)（离完美只差 1.1% 的比特）时，代价只有 \(g=0.001\)。
- \(\nu_{\mathrm{b}}=0.469\)（差 47%）时，代价 \(g=0.1\)。
前者的"比特换代价"兑换率是 \(0.001/0.0114=0.088\)，后者是 \(0.1/0.469=0.213\)。离完美越近，省下的每一比特造成的损失越小。
行为分析（与猜想 2.6 的关系，必须说清楚）
猜想 2.6 猜的是 \(g\) 凹增且 \(g(\nu_{\mathrm{b}})=\Theta(\nu_{\mathrm{b}})\)（\(\nu_{\mathrm{b}}\to0\)）。命题 4.12 给出的实例两条都不满足：\(g\) 是凸的，且在零点附近是 \(o(\nu_{\mathrm{b}})\) 而非 \(\Theta(\nu_{\mathrm{b}})\)。
这不构成对猜想 2.6 的反例。猜想 2.6 明确限定在 LQG 动态团队（二次代价、高斯噪声、连续动作），而本例是二元动作、0-1 型代价的协调问题，模型类不同。但它给出两条真实的教训：
- "凹增"不是这类问题的普遍规律。 猜想 2.6 若要成立，必须把模型类写死在 LQG 上，不能当成一条关于"比特换协调"的一般直觉。
-
零点附近的斜率恰恰是最需要小心的地方。 在本例里，把"差一点点"补齐几乎不要钱（\(g'(0^+)=0\)）；而在 第 2 章2.7 节的另一端（部分嵌套的 0/1 判据），"差一条链路"与"不差"之间是跳变。
这两种极端之间，\(g\) 的真实形状取决于代价函数是二次的还是 0-1 的。这本身就是一条值得单列的开放问题（见章末第 3 条）。
把命题 4.4 与第 2 章、第 3 章接上，本部的"话费—代价"链条现在有了三个刻度：
| 章 | 问的是 | 自变量 | 因变量 | 状态 |
|---|---|---|---|---|
| 第 2 章 | 完全不能商量要付多少 | 0/1（能否共享） | 分散化代价 3.02% / 8.00% | 【已解决】闭式 |
| 第 3 章 | 结构够不够让问题可解 | 嵌套亏欠 \(\nu\)（链路数）、\(d/p\) | 凸 / 非凸 | 【部分结果】相图 |
| 本章 | 每时隙花 \(R\) 比特能买回多少 | \(R\)（比特/时隙） | 坏时隙率 \(h^{-1}(1-R)\) | 【本站演算】闭式（二元模型） |
三行连起来，就是第 3 章3.8 节写下的那条组织性等式的展开：
- 结构决定可不可解（第 3 章）；
- 话费决定解得多贵（本章）；
- 代价决定值不值（第 2 章）。
4.9.2 猜想 4.13：多方分布版#
最后，把这条能算的两方结果推到多方，就是本部要立的第二条缺失定理的第一块砖。
猜想 4.13（协商的最小话费：多方分布版）【开放·本站提法】
考虑 \(K\) 个共信道小区，每个小区每时隙做一个二元发射决策 \(A_i\in\{0,1\}\)，目标是一个给定的联合分布 \(p(a_1,\dots,a_K)\)（例如"每个干扰簇内至多一个开、且长期公平"）。记
- \(R_{\mathrm{bb}}(K)\)：**广播（黑板）**介质下达到经验协调的最小总速率（比特/时隙，所有链路合计）；
- \(R_{\mathrm{cd}}(K)\)：**点对点（coordinator）**介质下的同一量。
猜想：存在一族目标分布 \(p\)（由干扰图生成）使
已知的边界
- （i）\(K=2\) 时两种介质无差别，速率由定理 4.1 精确给出 \(I(A_1;A_2)\)（命题 4.4 是它的一个显式族）。
- （ii）\(\Theta(k/\log k)\) 的分离在一次性总比特口径下已证（定理 4.11，[9][10]）。
- （iii）广播拓扑的协调容量在一般情形只有内外界（定理 4.5 后的说明），所以 \(R_{\mathrm{bb}}(K)\) 本身目前没有闭式。
猜想说的到底是什么
它主张那个已在"总比特/最坏情形"口径下证明的分离，在"速率/平均"口径下也成立。这不是自动的：两种口径之间没有一般的转换定理（4.8 节的分栏表就是为了讲清这一点），而广播协调容量的开放性恰恰卡在中间。
可证伪的第一步
取 \(K=3\)，干扰图为一条链（小区 2 同时干扰 1 和 3，1 与 3 互不干扰），目标分布为"2 开时 1、3 必关"。这个拓扑落在 Cuff 定理 7 的内外界之间。先把内外界在这个具体分布上算成两个数，看它们是否已经把 \(\Theta(K/\log K)\) 的形状夹住。
若内外界在 \(K=3\) 上就相差一个 \(K\) 的因子，猜想的形状就无法在这条路上验证，得换工具。例如先走第三部第 6 章留下的 \(\mathrm{DISJ}\) 归约，再把一次性下界摊销成速率。
它是谁的第一步
第 9 章"协商的最小话费"那条缺失定理；它同时是第三部 \(C(\varepsilon)\) 从两小区升级到多方的分布版本。
到此为止我们得到了什么
- 把协调价签接回团队代价。命题 4.12 给出"比特换代价"曲线的第一个可算实例，其形状（凸增、零点处 \(o(\nu_{\mathrm{b}})\)）与猜想 2.6 的猜测相反，说明那条猜想必须把模型类写死。
- 三章连成"结构—话费—代价"三个刻度。
- 猜想 4.13 把两方的确切答案推成多方的介质分离猜想，并给出 \(K=3\) 的可证伪第一步。
4.10 场景与方法盘点：谁解决了什么，谁答不上来#
4.10.1 四个当代场景#
（一）AI 空口的两侧模型对齐
3GPP TR 38.843 的 CSI 压缩用例里，终端侧编码器与基站侧解码器是两个决策者。算例 4.3 的教训在这里最刺眼：两端模型"几乎一致"时 \(K_{\mathrm{GK}}\) 已经塌到 0，可零率同步的公共部分为零，所以对齐必须真的花比特。这是第三部第 6 章"两侧模型互操作 = 建立公共知识的通信复杂度问题"的信息论侧解释。
按 4.8 节的口径，它是一次性安装费（总比特），不是月租费（速率）。
（二）ISAC 组网感知的波形协调
多站协同照射同一目标时，各站的时隙/波形选择要服从一个联合分布（避免互相致盲、保证覆盖）。两站可用定理 4.1 定价；三站及以上落在定理 4.5 之后的开放区，没有闭式价签。
这是"缺失定理"在 ISAC 上的一个具体落点：现在的组网感知方案只能给出可行的协议，给不出"最少要多少回传"的下界。
（三）边缘推理的特征传输
多个边缘设备把特征送到同一个推理节点，目标不是"复原特征"，而是"让联合决策服从某个分布"。这是协调容量的问句形式，不是率失真的问句形式。
但拓扑是多对一的广播/汇聚型，同样落在开放区。目前工程上的做法（各自率失真编码后简单拼接）在协调的口径下必然次优。次优多少，没有理论。
（四）多智能体 LLM 的对话轮数
推论 4.9 是这里最有力的工具：只要每轮流过去的信息量有限，轮数就被通信复杂度除以每轮容量卡死，与用什么模型无关。把"两个 agent 在 \(m\times m\) 的联合方案表上找一个双方都接受的方案"当成模型，纯 Nash 型目标给 \(\Omega(m^2/\log m)\) 轮。
这条界的价值不在数字，而在它不可绕过：再强的模型也不能凭空制造出没有流过去的比特。
2025–2026 有大量工作报告多智能体框架的 token 削减比例（有的降到原来的四分之一量级），也开始出现信息论口径的 token 下界【预印本·未评审，本站未逐篇核实，不引用具体百分比】。它们要成为真正的下界，缺的是"把任务的通信复杂度算清楚"这一步。
4.10.2 方法盘点#
| 方法谱系 | 解决了什么 | 回答不了什么 | 缺的定理落在哪 |
|---|---|---|---|
| 协调容量（Cuff 等 [1]，一般字母表的推广见 Raginsky [11]） | 把"协作"重新定义成"合成一个联合分布"，并给出两节点、级联、孤立节点的精确价签；区分经验/强协调两级与各自的资源清单 | 广播与干扰型拓扑只有内外界（一般情形【开放】）；有限块长没有刻画；不处理"目标是一个函数"的情形 | 猜想 4.13；第 9 章缺失定理二 |
| 均衡的通信复杂度（Hart–Mansour [2][3]、Conitzer–Sandholm [4]） | 给出不依赖算法的下界：纯/混合 Nash 指数于玩家数、\(\Theta(m^2)\) 于动作数；把比特下界换算成学习轮数下界（推论 4.9） | 最坏情形常常太松（真实网络的支付表有大量结构）；相关均衡侧只有上界且无显式次数；不给"平均情形"或"典型无线信道下"的答案 | 平均情形与结构化博弈族的通信复杂度【开放】 |
| 公共信息（GK [6]、Wyner [7]） | 说清"哪一部分不用说"；给出三量排序；解释"几乎一致 \(\neq\) 一致"这个反直觉现象 | \(K_{\mathrm{GK}}\) 对分布不连续、有限块长几乎不可提取；不给"近似公共信息"的可操作版本 | 第二部第 3 章 Q3.6（格的交的可操作提取）【开放】 |
| 多方通信复杂度 / 黑板分离（[9][10]，第三部第 6 章） | 证明广播介质省 \(\Theta(k/\log k)\)；把"广播是资源"变成定理 | 还没有把无线资源分配归约到多方 DISJ 上，所以分离在无线里未兑现 | 第三部与本部共有的 \(\mathrm{DISJ}\) 归约钉子【开放】 |
| 学到的通信协议（MARL 的可微通信、emergent communication，综述见 Lazaridou–Baroni [12]） | 在仿真里能涌现出可用的协议，不需要人工设计消息格式；对非结构化观测有效 | 没有任何下界保证：学到的协议长度与任务的 \(R^{\mathrm{pub}}/R^{\mathrm{priv}}\) 下界之间没有定量对照；也说不清它逼近的是经验协调还是强协调 | "学到的协议 vs 通信复杂度下界"的定量对照【开放·据本站检索未见先例；第 5 章会把它落到一个可算的任务上】 |
| 工程做法（半静态资源划分、集中调度器、标准化码本） | 能跑、可互操作；把拓扑强行退化成"有答案的那几种"（星形/级联） | 不知道自己付的话费离最优有多远；换拓扑就得重来 | 广播协调容量【开放】 |
六行读下来是同一句话：两个人的时候我们知道价签，三个人的时候就不知道了；要一个分布的时候我们知道怎么记账，要一个均衡的时候记账方式就换了一套。本部要补的东西正在这两条缝里。
协调要花多少比特：五十年的路标
| 年份 | 路标 |
|---|---|
| 1973 | Gács–Körner 公共信息远小于互信息，且对分布不连续 |
| 1975 | Wyner 第二种公共信息，最小的解释变量 |
| 1979 | Yao 通信复杂度模型，把"算一个函数要说多少话"变成可证问题 |
| 2004 | Conitzer–Sandholm 双人 \(m\times m\) 纯 Nash 需 \(\Theta(m^2)\) 比特，并把比特下界换算成学习轮数 |
| 2010 | Cuff–Permuter–Cover 协调容量，两节点经验协调的最小速率是互信息；Hart–Mansour 非耦合到纯 Nash 指数比特，到相关均衡存在多项式程序 |
| 2011–2014 | Braverman–Rao 信息复杂度等于摊销通信复杂度，度量以共享先验为参数 |
| 2012–2013 | Phillips 等；Braverman 等 多方黑板与 coordinator 的严格分离 |
| 2013 | Raginsky 经验协调推广到一般字母表 |
| 2026 | 本站第四部 三个切面并成一张分栏的话费表，接上两小区的团队代价与相图 |
怎么读这张表
- 上半段（1973–1979）是两条独立的线：公共信息（信息论）与通信复杂度（理论计算机），各自在自己的学科里成形。
- 中段（2004–2013）三件事同时发生：博弈论把通信复杂度用在均衡上，信息论把协作重新定义成合成分布，理论计算机把多方模型分离开。
- 本站在最后一行做的，是把三条线并成一张分栏的表并接到无线上，不是新定理。
- 数据来自本章参考文献的年份与题目。
到此为止我们得到了什么
- 四个当代场景的落点：两侧模型对齐是安装费，ISAC 与边缘推理都卡在广播拓扑的开放区，多智能体 LLM 的轮数被推论 4.9 卡死。
- 一张六行方法表。缺口集中在两处：从两方到多方（拓扑），以及从分布目标到函数目标（记账方式）。
开放问题#
-
广播与干扰型拓扑的协调容量【开放】。 Cuff 等的定理 7、8 只给内外界 [1]，而广播恰是无线最自然的拓扑。最小的非平凡实例：一个基站同时协调两个基站（\(1\to\{2,3\}\)），目标分布由干扰图给定。第一步：把内外界在 4.9 节猜想 4.13 的 \(K=3\) 链式实例上算成两个显式数字，看间隙有多大。
-
多方协调话费的介质分离【开放·本站提法】（猜想 4.13）。 已证的 \(\Theta(k/\log k)\) 分离在"一次性总比特/最坏情形"口径下 [9][10]；速率口径下是否成立没有定理。障碍是第 1 条：广播侧的量本身还没有闭式。
-
"比特换代价"曲线的形状与代价函数的关系【开放】。 命题 4.12 在二元 0-1 模型上给出凸增且 \(g'(0^+)=0\)；第 2 章猜想 2.6 在 LQG 上猜凹增且零点线性。两者都可能对，因为代价函数不同。
开放问题是：\(g\) 的形状与代价函数（0-1 / 二次 / 一般凸）之间有没有一条一般规律？
第一步可证引理：在算例 2.2 的两成员高斯二次模型上把 \(y_1\) 量化成 \(R\) 比特转发，算出 \(J^\star(R)\) 的闭式并判其凹凸（这条引理第 2 章也点名要它）。
-
有限块长的协调【开放】。 定理 4.1 是渐近的。真实调度环的块长是几十到几百个时隙，\(n=100\) 时"\(R^\star=I(X;Y)\)"这句话要打多少折扣？信道编码有成熟的有限块长理论（正规逼近），协调问题的对应物本站未取得。
这条对工程最重要：一个只在 \(n\to\infty\) 成立的价签，工程师有权怀疑。
-
相关均衡程序的多项式次数【开放】。 定理 4.7 只给"poly\((N,u)\)"，原文未给显式次数 [2]。次数是 2 还是 6，决定"解概念决定话费量级"这句话在 \(N=50\) 的网络里是不是真的可用。
-
近似公共信息【开放】。 \(K_{\mathrm{GK}}\) 对分布不连续（算例 4.3：\(\epsilon\) 从 0 变到 0.001，公共信息从 1 掉到 0），这让它在工程上几乎不可用。是否存在一个"\(\delta\)-近似公共信息"，连续、可算、且有操作意义（例如"允许 \(\delta\) 概率不一致时可零率同步的最大熵"）？与第二部第 3 章 Q3.6 是同一问题的两端。
注意第二部第 2 章 2.6 节的反例：Le Cam 亏格不满足共同后处理单调（对两个实验做同一次后处理，亏格可能反而变大），所以不能天真地把单决策者的松弛工具搬过来。
-
学到的通信协议与下界的定量对照【开放·本站提法】。 emergent communication 的文献以度量协议性质（组合性、拓扑相似度、消息熵）为主 [12]，本站检索未见把学到的协议长度与某个任务的通信复杂度下界做定量对照的工作。
要让这句话可证伪，必须把任务钉死在一个下界已知的问题上。推论 4.9 与定理 4.8（双人 \(m\times m\) 找纯 Nash，\(\Theta(m^2)\) 比特、\(\Omega(m^2/\log m)\) 轮）正是现成的模板。第 5 章会接手这一条。
参考文献#
- P. Cuff, H. Permuter, T. M. Cover, 《Coordination Capacity》, IEEE Transactions on Information Theory, 56(9):4181–4206, 2010. https://www.ee.bgu.ac.il/~haimp/Coordination_capacity_journal_thomas_cover_paul_cuff_permuter.pdf
- S. Hart, Y. Mansour, 《How long to equilibrium? The communication complexity of uncoupled equilibrium procedures》, Games and Economic Behavior, 69(1):107–126, 2010. https://math.huji.ac.il/hart/papers/comcom.pdf
- S. Hart, Y. Mansour, 《The communication complexity of uncoupled Nash equilibrium procedures》, Proc. ACM STOC, 2007. http://www.math.tau.ac.il/~mansour/papers/07-stoc.pdf
- V. Conitzer, T. Sandholm, 《Communication complexity as a lower bound for learning in games》, Proc. ICML, 2004. https://www.cs.cmu.edu/~sandholm/communication.icml04.pdf
- I. Newman, 《Private vs. common random bits in communication complexity》, Information Processing Letters, 39(2):67–71, 1991. https://doi.org/10.1016/0020-0190(91)90157-D
- P. Gács, J. Körner, 《Common information is far less than mutual information》, Problems of Control and Information Theory, 2(2):149–162, 1973.
- A. D. Wyner, 《The common information of two dependent random variables》, IEEE Transactions on Information Theory, 21(2):163–179, 1975.
- M. Braverman, A. Rao, 《Information equals amortized communication》, Proc. IEEE FOCS, 2011；IEEE Transactions on Information Theory, 60(10):6058–6069, 2014. https://arxiv.org/pdf/1106.3595
- J. M. Phillips, E. Verbin, Q. Zhang, 《Lower bounds for number-in-hand multiparty communication complexity, made easy》, Proc. ACM-SIAM SODA, 2012. https://arxiv.org/abs/1107.2559
- M. Braverman, F. Ellen, R. Oshman, T. Pitassi, V. Vaikuntanathan, 《A tight bound for set disjointness in the message-passing model》, Proc. IEEE FOCS, 2013. https://arxiv.org/abs/1305.4696
- M. Raginsky, 《Empirical processes, typical sequences, and coordinated actions in standard Borel spaces》, IEEE Transactions on Information Theory, 2013. https://maxim.ece.illinois.edu/pubs/raginsky_IEEE-IT13.pdf
- A. Lazaridou, M. Baroni, 《Emergent multi-agent communication in the deep learning era》, arXiv:2006.02419, 2020. https://arxiv.org/abs/2006.02419