Spliddit: Unleashing Fair Division Algorithms

研究动机

• 理论与实践的鸿沟：公平分配（Fair Division）自 Hugo Steinhaus（1948）起已有七十余年的数学研究史，形成了覆盖经济学、数学、计算机科学和政治学的完整理论体系，但极少数方法真正面向公众开放。
• 现有工具的局限：仅有 Adjusted Winner Website（仅支持两人、受专利保护）和 Francis Su 的 Fair Division Calculator（Su 1999）等少数例外，覆盖场景有限、可用性较低。
• 核心 insight：可证明公平（provably fair） 才是关键——不是"看起来公平"，而是在最坏情况下仍有理论保证；同时将算法解释对公众透明，兼顾教育意义。

三大应用

房租分摊 物品分配 信用分享

1. 房租分摊（Splitting Rent）

问题设定：\(n\) 个室友，\(n\) 个房间，总租金 \(R\)。每人 \(i\) 对房间 \(j\) 的估值为 \(V_{ij}\)（满足 \(\sum_j V_{ij} = R\)），准线性效用为 \(V_{ij} - p_j\)。

算法：来自 Abdulkadiroğlu et al.（2004）的市场算法——迭代地以相同速率提高过需求房间的价格、降低其余房间的价格，直至达到均衡。

公平保证：无嫉妒（Envy-Free）分配，即对所有房间 \(j'\)： \[ V_{ij} - p_j \;\ge\; V_{ij'} - p_{j'} \] 在此域中无嫉妒等价于 Pareto 有效，且算法保证当非负价格的无嫉妒分配存在时输出非负价格。

实现细节：采用 Ünver（2007）基于 Gallai-Edmonds 分解引理的高效算法计算过需求房间集合。

2. 物品分配（Dividing Goods）

问题设定：\(n\) 个玩家，一组物品（可整体或可分割），加性估值 \(V_i(X) = \sum_{j \in X} V_{ij}\)。每人在 Spliddit 上用 1000 分分配给各物品。

三级公平性（由强到弱）：

1. 无嫉妒（Envy-Free）：\(V_i(A_i) \ge V_i(A_{i'})\) 对所有 \(i,i'\)——不可整除时常不可行。
2. 比例公平（Proportionality）：\(V_i(A_i) \ge V_i(G)/n\)——仍可能不可行。
3. Maximin Share（MMS）保证： \[ \text{MMS}(i) = \max_{X_1,\ldots,X_n} \min_j V_i(X_j) \] 即玩家 \(i\) 若自己划分后最后拿的那份的最大可能值。算法保证 \(V_i(A_i) \ge \text{MMS}(i)\)，退而求其次至少保证 \(\ge \tfrac{2}{3}\text{MMS}(i)\)（Procaccia & Wang 2014）。

算法策略：先找最高可行公平级别，再在该约束下最大化社会福利 \(\sum_i V_i(A_i)\)。用 IBM CPLEX 求解混合整数线性规划。

3. 信用分享（Sharing Credit）

问题设定：\(n\) 个参与者，每人 \(i\) 上报其余人的贡献比例（不含自己），最终分配 100% 信用。

算法：de Clippel et al.（2008）的规则族中的一个，具体使用算术平均作为聚合器（论文公式 17）。

关键保证：

• 公正性（Impartiality）：玩家的信用份额与其自身上报无关，无法通过操纵自己的报告影响自身份额。
• 共识性（Consensuality）：若存在所有人都同意的分配，则以该分配为结果。

约束：当 \(n=3\) 时，公正且共识的规则必然不精确（无法始终分配满 100%），因此 Spliddit 强制 \(n \ge 4\)。

算法详解与例子

1. 房租分摊算法（市场均衡迭代法）

核心思路：把找"无嫉妒价格"转化为找竞争均衡（Competitive Equilibrium）——价格向量 \(\mathbf{p}\) 使每个玩家在该价格下都恰好"愿意"拿被分配的房间，没有人宁愿换房。

算法步骤：

1. 初始化：各房间价格相等，\(p_j = R/n\)。
2. 每个玩家根据当前价格选择效用最高的房间（贪心）。
3. 找"过需求集"（Overdemanded Set）：某房间被多人同时首选 → 价格上涨；无人选 → 价格下降。两类价格以相同速率变化以保持 \(\sum p_j = R\)。
4. 重复直至每个房间恰好被一人首选（均衡）。

过需求集的高效计算依赖 Ünver（2007）基于 Gallai-Edmonds 分解引理（二部图最大匹配理论）的算法，避免暴力枚举所有子集。

具体例子：Alice、Bob、Carol 分 3 个房间，总租 $3000

每行之和均为 $3000（总租）

第 0 步：初始价格 \(p_{Big}=p_{Med}=p_{Sml}=\$1000\)。

• Alice 效用：Big=600, Med=100, Sml=−700 → 选 Big
• Bob 效用：Big=400, Med=200, Sml=−600 → 选 Big
• Carol 效用：Big=−100, Med=400, Sml=−300 → 选 Med

Big 被 Alice+Bob 同时选 → 过需求；Sml 无人选 → 欠需求。

迭代：令 \(p_{Big}\) 上升、\(p_{Sml}\) 下降（等速 \(\delta\)），\(p_{Med}\) 不变（只被一人选）。当 \(\delta = 200\) 时：

• \(p_{Big}=1200,\ p_{Med}=1000,\ p_{Sml}=800\)（仍满足总和 $3000）
• Alice 效用：Big=400, Med=100, Sml=−500 → 仍选 Big
• Bob 效用：Big=200, Med=200, Sml=−400 → Big 和 Med 并列
• Carol 效用：Big=−300, Med=400, Sml=−100 → 仍选 Med

Bob 现在可以移到 Med 解决冲突 → 分配：Alice=Big，Bob=Med，Carol=Sml... 但 Carol 不选 Sml！

继续迭代（实际算法更精细，这里简化说明）。最终均衡价格约为：

验证无嫉妒：

• Alice 不换：1100−1050=50 < 250 ✓；300−600=−300 < 250 ✓
• Bob 不换：1400−1350=50 < 150 ✓；400−600=−200 < 150 ✓
• Carol 不换：900−1350=−450 < 100 ✓；1400−1050=350 > 100 ✗

Carol 嫉妒 Bob！说明这不是真正的均衡价格，迭代需继续。这里仅演示流程，真实算法会精确收敛到无嫉妒点。关键结论是：只要无嫉妒分配（非负价格）存在，算法必然找到。

2. 物品分配算法（三级公平 + 社会福利最大化）

两阶段流程：

1. 阶段一：从强到弱依次检验：无嫉妒 → 比例公平 → 最大可行 α-MMS。每级都用线性规划或 MILP 判断可行性并求解。
2. 阶段二：在阶段一找到的公平约束下，最大化社会总福利 \(\sum_i V_i(A_i)\)（再次 MILP）。

MMS 计算（对每个玩家 \(i\) 分别求解）：

这是一个 NP-hard 的整数规划问题：把 \(|G|\) 件物品分成 \(n\) 堆，使最小堆的价值（按玩家 \(i\) 的估值）最大。Spliddit 用 CPLEX 直接暴力求解。

具体例子：Alice、Bob、Carol 分 4 件物品（各有 1000 点）

计算 MMS(Alice)：Alice 把 4 件物品分成 3 堆，最大化最小堆：

计算 MMS(Bob)：

计算 MMS(Carol)：

阶段一：检验无嫉妒。尝试 Alice=L+P，Bob=T，Carol=W：

• Alice 拿 {L,P}=800；是否嫉妒 Bob({T})？Alice 评价 T=150 < 800 ✓；嫉妒 Carol({W})？W=50 < 800 ✓
• Bob 拿 {T}=400；嫉妒 Alice({L,P})？Bob 评价 L+P=200+200=400 = 400，不嫉妒（≥）✓；嫉妒 Carol({W})？W=200 ≤ 400 ✓
• Carol 拿 {W}=500；嫉妒 Alice({L,P})？L+P=300+100=400 < 500 ✓；嫉妒 Bob({T})？T=100 < 500 ✓

→ 无嫉妒分配存在，进入阶段二最大化社会福利。

阶段二：当前分配社会福利 = 800+400+500 = 1700。检验其他可能：

3. 信用分享算法（公正同行评估）

核心设计难点：任何人不能通过"给自己打高分"来提升自身份额——即必须满足公正性（Impartiality）。解法：玩家 \(i\) 的份额完全不依赖于 \(i\) 自己的上报，只由其他人对 \(i\) 的评价决定。

de Clippel 规则（等差均值聚合，公式 17）的直觉：

1. 每人 \(i\) 上报对其余 \(n-1\) 人的贡献比例向量 \(\mathbf{r}_i\)（和为 1，不含自己）。
2. 对每个玩家 \(j\)，收集所有其他人对 \(j\) 的评价，取算术均值得到"原始份额" \(\hat{s}_j\)。
3. 由于原始份额之和不一定等于 1（\(n=3\) 时尤甚），用精确的线性修正使和恰好为 1（这正是 \(n \ge 4\) 时才完全精确的原因）。

具体例子：Alice、Bob、Carol、Dave 合写一篇论文

每人上报其余三人的贡献比例（自己除外）：

第一步：对每人求"他人评价均值"（公正性的来源：自评不计入）

第二步：归一化（精确性修正）

注意：这里展示的是"简单均值+归一化"版本，实际 de Clippel 公式（Eq. 17）略有不同——它通过更精巧的线性组合在 \(n \ge 4\) 时实现精确性（exactness）且同时满足共识性（consensuality），即若所有人报告一致时直接输出该报告。上述简单均值在 \(n \ge 4\) 时的近似行为与之相近。

验证公正性：假设 Alice 把自己的上报改为 Bob=0%, Carol=0%, Dave=100%（极端操纵）：

公平性保证对比

工程实现

flowchart LR
    U([用户浏览器]) -->|HTTP| RoR[Ruby on Rails\nWeb App]
    RoR -->|ActiveRecord ORM| RDS[(Amazon RDS\nPostgreSQL)]
    RoR -->|异步任务| DJ[Delayed Job\n后台队列]
    DJ -->|调用| JVM[Java 算法引擎]
    JVM -->|房租| Rent[Gallai-Edmonds\n市场算法]
    JVM -->|物品| CPLEX[IBM CPLEX\nMILP 求解器]
    JVM -->|信用| Credit[de Clippel 公式\n算术均值聚合]
    RoR -->|部署| EB[Elastic Beanstalk\n自动伸缩]
    RoR -->|邮件| SES[Amazon SES]
          

• 后端：Ruby on Rails，ActiveRecord 建模所有实体（应用实例、玩家、物品、估值、分配）。
• 前端：jQuery 构建交互界面（如竞价滑块）。
• 算法层：Java 独立服务，通过 Delayed Job 异步运行，避免阻塞 Web 服务器。
• 云服务：Amazon EC2（计算）+ Elastic Beanstalk（自动扩缩）+ RDS（数据库）+ SES（邮件通知）。
• MILP：IBM Concert Technology 建模，CPLEX 求解；MMS 计算本身也需要先解 MILP 再做分配优化。

局限与展望

• 物品分配的 MMS 不保证精确：Procaccia & Wang（2014）构造了 MMS 分配不存在的反例，因此 Spliddit 的最坏情形保证退至 \(\tfrac{2}{3}\) MMS；实践中几乎不会触发，但理论上存在缺口。
• 信用分享的 n=3 不可能性：impartial + consensual + exact 在三人情形下不可同时满足，强制 \(n \ge 4\) 是妥协而非理想解。
• 按信用份额排序作者名单：Berga & Gjorgjiev（2014）证明在强公正性下无法实现公正排序——玩家可通过贬低他人来提升自己在排名中的位置，即使无法改变自身份额比例。
• 偏好模型简化：假设加性估值（Goods）和准线性效用（Rent），无法捕捉互补性或负外部性。
• 实证研究潜力：作者将 Spliddit 定位为"真实价值、真实用户"的实验平台——可将用户随机分组使用不同算法，用幸福感调查衡量各公平性准则的实际影响，突破实验室研究中"虚拟物品无真实价值"的困境（Herreiner & Puppe 2009）。
• 研究趋势：Spliddit 属于算法博弈论（AGT）中"理论落地"运动的早期代表。后续工作在 MMS 近似比上已有改进（当时 2/3，后续达 3/4 乃至更高），且类似平台（如 Course-Match 选课机制）已在多所大学上线，标志着可证明公平机制正逐步走向实际部署。

算法对比：Spliddit vs 自创最高竞价算法

结论先行：不等价。自创算法在 \(n \ge 3\) 时不保证无嫉妒，且存在冲突未定义的情形。

1. Spliddit 实际算法（竞争均衡迭代法）

Spliddit 的前端（React/jQuery）只负责收集输入和展示结果，算法本体是服务端 Java，实现 Abdulkadiroğlu-Sönmez-Ünver (2004) 的市场均衡算法：

1. 初始化：令所有房间价格相等，\(p_j^{(0)} = R/n\)。
2. 需求计算：每个玩家 \(i\) 在当前价格下选"效用最大的房间"： \[ D_i(\mathbf{p}) = \arg\max_j \bigl(V_{ij} - p_j\bigr) \]
3. 过需求集检测（Gallai-Edmonds 分解）：找集合 \(T \subseteq \text{Rooms}\) 使得 \(|\{i : D_i \cap T \ne \emptyset\}| > |T|\)（想要 \(T\) 中房间的人比 \(T\) 中房间数多）。这是过需求（overdemanded）集。
4. 价格调整：以相同速率 \(\delta\) 提高所有过需求房间价格，降低所有欠需求房间价格，保持 \(\sum_j p_j = R\)。
5. 终止：当每个房间恰好被唯一一个玩家需求时停止。此时输出价格 \(\mathbf{p}^*\) 和对应分配 \(A^*\)。

数学保证：该算法输出唯一竞争均衡（Competitive Equilibrium from Equal Incomes, CEEI），满足：

即：任何玩家用自己的价格算，都不希望换到别人的房间。这就是无嫉妒（Envy-Free）。

2. 自创算法（最高竞价 + 比例返还）

形式化（设总租金为 \(R\)，每人估值 \(V_{ij}\) 满足 \(\sum_j V_{ij} = R\)）：

1. 房间 \(j\) 分给最高竞价者：\(w_j = \arg\max_i V_{ij}\)
2. 令 \(S = \sum_j \max_i V_{ij}\)。因为 \(\sum_j \max_i V_{ij} \ge \max_i \sum_j V_{ij} = R\)，所以 \(S \ge R\) 恒成立。
3. 超出量 \(E = S - R \ge 0\) 按竞价比例返还给各赢家。
4. 赢家 \(w_j\) 实际支付：\(p_j = V_{w_j,j} - \frac{V_{w_j,j}}{S} \cdot E = V_{w_j,j} \cdot \frac{R}{S}\)

化简后，自创算法给出的价格有一个极简闭合公式：

即：每间房的价格 = 总租 × 该房最高竞价 / 所有房最高竞价之和。所有价格按同一比例因子 \(R/S\) 缩放。

3. 失效情形一：同一玩家赢多间房（算法未定义）

自创算法没有规定"同一玩家赢多间房时怎么办"。这并非罕见边缘情形：

（总租 R=$1000，加粗为各房最高出价）

Spliddit 的迭代算法自然绕开此问题：价格调整使"过度竞争"的房间变贵，直到每间恰好一人"最愿意"住为止。

4. 失效情形二：产生有效分配但不满足无嫉妒（核心反例）

即使凑巧每人恰好赢得一间房，自创算法的价格也不保证无嫉妒。下面是具体反例：

（总租 R=$3000，加粗为各房最高竞价；每人竞价和恰好等于总租）

现在检验 Alice（住 A 房，付 $312.50）是否嫉妒 Bob（住 B 房，付 $1312.50）：

根本原因：自创算法价格 \(p_j \propto \max_i V_{ij}\)——谁赢了这间房价格就按他的出价来算。但 Alice 赢 A 房是"以很低出价（500）碰巧胜过其他人更低的出价"，A 房因此被定得很便宜（$312.50）。而 B 房因为 Bob 激烈竞价（2100）被定得较贵（$1312.50），但对 Alice 来说 B 房值 $2000，仍然划算——自创算法的价格没有在 A/B 之间建立正确的"价差壁垒"来阻止 Alice 觊觎 B。

Spliddit 为同一分配（A→Alice, B→Bob, C→Carol）找到满足无嫉妒的价格，例如：

注：Spliddit 的迭代市场算法会将价格收敛到"竞争均衡"，而不是手动枚举；上面只是展示满足无嫉妒的某个有效价格，实际输出由算法唯一确定。

5. 对比总结