猜测排名游戏
有 \(n\) 名玩家参与一个猜测排名游戏。首先，玩家 \(i\) 获得一个独立同分布于 \(U(0, 1)\) 的随机数 \(X_i\)，该随机数不公开。随后进行若干轮：
- 玩家 \(i\) 依次猜测自己得到的随机数 \(X_i\) 的大小在所有玩家中的排名，并公开（每轮猜测的排名可以不同）。
若存在至少两个玩家猜测的排名相同，则进入下一轮，否则结束所有轮次。最后，公开所有 \(X_i\)，在最后轮次中所有猜测排名正确的玩家获得奖励。
在合作博弈假设下，每个玩家都希望所有玩家能够获得奖励。所有玩家在游戏开始前可以商议一个策略。在必胜的前提下，试提出一个策略，最大化每轮立即结束的概率。
扩展：
- 推广到任意连续非均匀概率分布，例如 \(N(0,1)\)
- 推广到任意离散概率分布（当有复数个玩家获得相同随机数时，他们的排名猜测连续即算猜测正确）
解答
规定“第 \(1\) 名”表示随机数最小者；若排名方向相反，只需把名次编号反过来。
这个策略整体上可以概括为：等分概率分布区间，每位玩家根据自己的随机数报出自己位于第几个区间，然后递归地等分尚未区分的玩家组。
具体地，第一轮，把区间 \([0,1]\) 等分成 \(n\) 个半开区间：
\[ I_k=\left[\frac{k-1}{n},\frac{k}{n}\right),\qquad k=1,\dots,n. \]
若玩家 \(i\) 的 \(X_i\in I_k\)，则猜自己是第 \(k\) 名。如果所有人的猜测互不相同，那么每个小区间恰好有一名玩家。小区间从左到右排列，因此这些玩家的真实排名正好分别是 \(1,\dots,n\)，所以一旦本轮结束，所有人必然都猜对。
如果第一轮有人猜重，则根据第一轮结果，把玩家分组。记某个小区间中有 \(m\) 名玩家。由于其他小区间中的人数已经公开，这 \(m\) 名玩家在总排名中必然占据某个连续名次块 \(s+1,s+2,\dots,s+m\)，其中 \(s\) 是所有更靠左区间中的玩家总数。现在把该组所在的区间继续等分成 \(m\) 个等长子区间 \(J_1,\dots,J_m\)。若该组某玩家的 \(X_i\in J_j\)，则下一轮猜 \(s+j\)。已经成为单人组的玩家，其真实排名已经确定，以后每轮都猜这个确定的排名。
每轮结束后，同一子区间中的玩家继续构成一个未区分组。落入不同子区间的玩家之间的先后顺序已经确定，重新计算每个组对应的连续名次块，然后递归等分。
可以发现，如果某个组尚未完全区分，那么至少有两个玩家落入同一子区间并猜同一名次，游戏就不会错误地结束，因此该策略是必胜的。
设某轮开始时，尚未区分的各组大小为 \(m_1,m_2,\dots,m_g\)，满足 \(\sum_{j=1}^g m_j=n\)，其中单人组允许 \(m_j=1\)。对于一个大小为 \(m\) 的组，\(m\) 名玩家独立均匀地落入 \(m\) 个等长子区间。该组在本轮被完全区分的概率为 \(\frac{m!}{m^m}\)，不同组条件独立。因此，在当前公开历史条件下，本轮立即结束的概率是 \(\prod_{j=1}^g\frac{m_j!}{m_j^{m_j}}\)。特别地，第一轮只有一个大小为 \(n\) 的组，所以概率为 \(\frac{n!}{n^n}\)。
下面证明这个策略可以使上述概率最大化。
考虑一个当前大小为 \(m\) 的未区分组。条件于已有公开信息，这 \(m\) 名玩家的数仍然独立均匀地分布在同一个区间内。固定一种可能的真实次序，例如 \(x_{\pi(1)}<x_{\pi(2)}<\cdots<x_{\pi(m)}\)。
如果本轮以这一真实次序正确结束，那么各玩家公开的猜测已经唯一确定：玩家 \(\pi(j)\) 必须猜该名次块中的第 \(j\) 个名次。
即使玩家依次猜测，对于这一固定的公开猜测序列，每名玩家是否作出指定猜测只取决于自己的数以及已经固定的先前公开信息。因此，对应的成功集合是一个笛卡尔积集合
\[ A_1\times A_2\times\cdots\times A_m, \]
并且由于该策略是必胜的，因此该笛卡尔积必须完全位于相应的有序区域中，于是这些集合必须按数轴先后分离。设每个集合的长度分别为 \(a_1,\dots,a_m\)，则
\[ a_1+\cdots+a_m\le 1. \]
可知，当前随机数分配取到这个笛卡尔积集合，即使用该策略可以直接结束的概率为 \(a_1a_2\cdots a_m\)。由算术—几何平均不等式，它满足
\[ a_1a_2\cdots a_m \le \left(\frac{a_1+\cdots+a_m}{m}\right)^m \le \frac1{m^m}. \]
所以，对于每一种指定的真实次序，正确结束的概率至多是 \(1/m^m\)。共有 \(m!\) 种次序，故一个大小为 \(m\) 的组在本轮完全解决的概率至多为 \(\frac{m!}{m^m}\)。多个组必须同时解决，故总概率至多为 \(\prod_{j=1}^g\frac{m_j!}{m_j^{m_j}}\)。递归等分策略恰好达到这个上界，因此它在每一个公开历史之后，都最大化了下一轮立即结束的条件概率。
扩展：非均匀分布
设 \(X_i\) 独立同分布，累积分布函数为 \(F(x)=\Pr(X_i\le x)\)，并假设 \(F\) 连续。令 \(U_i=F(X_i)\)，由概率积分变换，\(U_i\overset{\mathrm{iid}}{\sim}U(0,1)\)，而且除零概率事件外，\(X_i<X_j\iff U_i<U_j\)，因此可以直接在 \(U_i\) 上运行均匀分布情形的策略。
具体地，第一轮，取分位点
\[ q_k=F^{-1}\left(\frac{k}{n}\right), \qquad k=0,1,\dots,n, \]
其中广义逆定义为
\[ F^{-1}(u)=\inf\{x:F(x)\ge u\}. \]
玩家观察到 \(X_i\in(q_{k-1},q_k]\) 时，猜自己是第 \(k\) 名。每个分位区间的概率都是 \(1/n\)，所以第一轮结束的概率仍为 \({\frac{n!}{n^n}}\)。一旦所有猜测不同，每个分位区间恰好有一名玩家，分位区间的顺序与真实数值顺序相同，因此所有猜测都正确。若发生碰撞，后续轮次同理，不再赘述。
由于变换 \(U=F(X)\) 把问题等价地化为均匀分布问题，原来的最优性证明完全适用。
扩展：离散分布
现在设 \(X_i\) 取值于一个有序的可数集合，记 \(p_x=\Pr(X_i=x)\)，\(F(x^-)=\Pr(X_i<x)\)，由于 \(F(X_i)\) 不再服从均匀分布，需要使用“随机化概率积分变换”。
让每名玩家额外使用一个相互独立的私人随机数 \(V_i\sim U(0,1)\)，并令
\[ Y_i=F(X_i^-)+p_{x}V_i. \]
那么可以证明 \({Y_i\overset{\mathrm{iid}}{\sim}U(0,1)}\)。且：
- 若 \(X_i<X_j\)，则必有 \(Y_i<Y_j\)；
- 若 \(X_i=X_j=x\)，则 \(Y_i,Y_j\) 都位于原子 \(x\) 对应的区间 \(\bigl(F(x^-),F(x)\bigr)\)，它们的先后顺序只是在相同数值内部作随机排列。因此，按 \(Y_i\) 的排名猜测即可。
假设恰有 \(m\) 名玩家获得相同值 \(x\)，且有 \(s\) 名玩家的值严格小于 \(x\)。那么这 \(m\) 名玩家对应的 \(Y_i\) 全部满足 \(F(x^-)<Y_i<F(x)\)，而所有更小的 \(X\) 对应更小的 \(Y\)，所有更大的 \(X\) 对应更大的 \(Y\)。所以这 \(m\) 名并列玩家按 \(Y\) 排序后，获得的名次恰好是 \(s+1,s+2,\dots,s+m\)，即一组连续名次，正好满足题目对并列者的判定规则。于是，可以在 \(Y_i\) 上完整地运行原来的递归等分策略。
然而，对于离散分布而言，这一策略不一定是最优策略，某些分布通过精心构造可以获得更优的结果，即单轮结束概率大于 \({\frac{n!}{n^n}}\)。例如，对于退化分布 \(\Pr(X_i=c) = 1\)，只需规定第 \(i\) 个玩家猜测第 \(i\) 名即可，从而第一轮必然结束。而使用上述随机化概率积分变换则仍可能发生“碰撞”，进而需要更多轮次才能结束。
轮数期望的渐近分析
使用以上递归策略，记总结束轮数为 \(T_n\)，那么可以证明
\[ E(T_n) = \log_2 n + O(1). \]