## 斯特罗姆奎斯特走刀法（Stromquist Moving‑Knife Procedure） > **场景**：三个人分一块“口味不均匀”的蛋糕，每个人对不同位置的价值感觉都不一样；想要做到 **“无嫉妒（Envy‑free）”**，并且只用一把刀一次性切到底。 --- ## 1 ▪ 问题再描述 - **目标**：让 A、B、C 三人最后各拿到 1/3 的份额，并且**谁也不眼红别人**。 - **难点**：传统“一刀三断”做不到无嫉妒；常见算法要么多刀多次投票，要么允许微调重新分配。 斯特罗姆奎斯特（Walter Stromquist, 1980）给出一个只需要“**一把刀连续移动**”就能当场停下并完成分配的方案。 --- ## 2 ▪ 规则（通俗版剧本） 1. **蛋糕按从左到右铺开**，大家心里都有自己的“甜度地图”。 2. **裁判**拿着一把刀，**从左端缓慢匀速往右推**。 3. **每人同时拿一根标尺**，在刀移动的任何时刻，可以把标尺的“指针”放在蛋糕上方，代表“若现在停刀，我想要的 1/3 起点”。 - 换句话说，你在脑海里把剩下部分再分成三等，指针指向你认为自己的那一份左端。 4. **同步移动**：刀在前方匀速走，每人的指针跟着各自的价值函数同步滑动（可以快慢不同，但始终保持“指到自己那一份的左边界”）。 5. **停刀规则**（关键） - 当三根指针第一次在蛋糕上的**空间顺序发生改变**（即指针从“刀‑A‑B‑C”变成“刀‑B‑A‑C”之类）时，马上喊停！ - 令此刻**最左边**的那位得“刀到他指针之间的区块”。 - 其余两人继续用同样方法在剩下蛋糕里二分钱（可以用简单的“切一半，让对方选”），无嫉妒可保证。 > 直观理解： > > - 每人指针始终代表“我心中恰好 1/3 的左端”。 > > - 当顺序改变时，意味着有两人的“1/3 起点”交叉——此刻抓住交叉点切掉最左段，就能保证被切到的人觉得自己拿满 1/3，而别人由于指针还在右侧也不嫉妒。 > --- ## 3 ▪ 为什么无嫉妒？ - **得到切块的人**：他在喊停瞬间就确定“从刀到指针”正好是自己价值 = 1/3 → 不嫉妒。 - **另外两人**：他们的指针都在切块右边，说明切块对他们价值 < 1/3；剩余蛋糕 ≥ 2/3，对两人用二分钱算法也能各得 ≥ 1/3 → 不嫉妒。 - 整个过程中刀“单调”移动，指针各自单调，因此第一次交叉必然在所有人满意的时刻出现。 --- ## 4 ▪ 亮点与局限 |亮点|说明| |---|---| |**只用一把刀**|全程连续移动，一旦停下只切一次。| |**实时可执行**|不需要事先知道彼此价值函数；只要同步移动标尺即可。| |**保证无嫉妒**|三人都认为自己得到的至少与别人相等。| |局限|说明| |---|---| |仅适用于 **三人**|四人及以上到目前为止不存在已知的“单刀连续走”算法。| |需 **同步、实时**|所有人必须持续观察并移动指针，在现实操作中略麻烦。| |对 **测量误差敏感**|价值判断需即时精确，否则停刀点可能偏离理论交叉点。| --- ## 5 ▪ 与其它著名分割算法对比 |算法|参与人数|刀数 / 轮数|无嫉妒?|备注| |---|---|---|---|---| |“我切你选”|2|1 刀|✔|切的人最糟=1/2| |**Stromquist**|3|1 刀 (走刀)|✔|需同步移动| |Selfridge‑Conway|3|≤5 刀|✔|离线分几轮| |Brams‑Taylor (BT)|n|有限次|✔|算法极长，实际难操作| |Aziz‑Mackenzie|n|离散循环|EF1（近似无嫉妒）|允许微量剩余| --- ### 小结 - **斯特罗姆奎斯特走刀法**：三人公平分蛋糕的“单刀实时”方案；核心是“刀‑指针顺序首次交叉即切”。 - 它证明了：对三人而言，无嫉妒分割**不必**多轮、也不必多刀，只要大家同时更新“我想要的 1/3 起点”即可。 - 对更多人如何做到“单刀无嫉妒”，仍是公平分割研究的开放难题。