Truth, Justice, and Secrecy: Cake Cutting Under Privacy Constraints¶

会议: AAAI 2026
arXiv: 2511.09882
代码: 无
领域: AI Safety / 公平分配
关键词: 蛋糕切割, 隐私保护, 策略防谋, 安全多方计算, 无嫉妒分配

一句话总结¶

首个隐私保护蛋糕切割协议，在保持无嫉妒性和策略防谋性的同时，通过秘密共享和安全多方计算（MPC）技术确保参与者的估值函数不被泄露。

研究背景与动机¶

领域现状：蛋糕切割问题（即连续资源公平分配）在过去二十年取得了显著进展。Chen et al. (2010) 提出了针对分段均匀估值的确定性、策略防谋且无嫉妒的分配算法 CC_puv。
现有痛点：即使算法具备策略防谋性（即参与者没有激励去虚报偏好），参与者仍然可能因隐私顾虑而拒绝如实汇报。例如广告时间分配中，透露偏好可能暴露营销策略；频谱竞拍中，出价可能泄露公司未来规划。
核心矛盾：策略防谋解决了"谎报无益"的问题，但无法解决"如实汇报会暴露隐私"的问题。参与者可能宁愿牺牲算法保证也不愿泄露真实偏好。
本文要解决什么？ 设计一个同时满足公平性（无嫉妒）、策略防谋性和隐私保护性的蛋糕切割协议。
切入角度：将 Chen et al. 的集中式算法改造为基于密码学技术的分布式隐私保护协议，以秘密共享替代明文计算。
核心idea一句话：用 Shamir 秘密共享 + 安全多方计算重新实现 CC_puv 算法的每一步，使得任何参与者都无法获知他人偏好，同时保留原算法的所有公平性保证。

方法详解¶

整体框架¶

提出 PP_CC_puv 协议（Privacy-Preserving Cake Cutting for piecewise uniform valuations），是对 CC_puv 算法的隐私保护变体。协议分为三大阶段：

准备阶段：参与者通过秘密共享分发估值函数，将蛋糕划分为区间集合 W
迭代分配阶段：在秘密共享的状态下，迭代地选择最小平均需求子集并进行公平分配
最终分配阶段：扫描所有区间并分配给相应参与者

关键设计¶

秘密共享估值函数（SharingPrivateValuations）：每个参与者将其分段均匀估值的端点离散化为整数，然后通过 Shamir (t,n)-门限秘密共享方案分发给所有参与者。协议统一了区间数量上界 ℓ（通过安全最大值计算），不足的用空区间 [1,1) 填充，防止区间数量泄露信息。此外嵌入完整性检查，防止不诚实参与者提交非法估值。
固定图替代动态图（MaxFlow 改造）：原算法 CC_puv 在每轮迭代中根据当前参与者-区间关系构建不同的有向图并计算最大流。但图的结构变化可能泄露敏感信息。PP_CC_puv 将动态图替换为跨所有迭代共用的固定图，边权通过密码学方式计算。这是协议设计中的核心难点和创新，需要保证图的结构不泄露任何关于参与者偏好的信息（即"遗忘式"选择）。
遗忘式迭代分配（IterativeAllocation）：每轮需要选出平均需求最小的参与者子集 S'，但协议必须在不知道哪些参与者已被服务、哪些区间仍可用的情况下完成选择。通过维护秘密共享的状态位（IntervalAvailable、IntervalDesired 等），所有操作均在密文上进行，确保迭代过程的遗忘性。
安全子协议工具箱：利用 MPC 文献中的基本安全操作——加法/仿射组合（无需通信）、乘法（DN07/Chida18）、比较（NO07）、相等测试（KoganTG23）、最小值、OR、除法——组合实现复杂的分配逻辑。

损失函数 / 训练策略¶

本文不涉及机器学习训练。协议的计算开销为 O(1) 额外计算，至多 O(n²) 额外通信代价。安全模型为半诚实（semi-honest）模型，要求诚实多数（>n/2 的参与者诚实）。协议提供信息论级别的隐私保证：任何参与者既不能获知他人的估值函数，也不能获知中间计算结果。

实验关键数据¶

主实验¶

本文为理论密码学工作，以定理证明而非实验为主。核心理论结果：

性质	CC_puv (原算法)	PP_CC_puv (本文)
无嫉妒 (Envy-free)	✓	✓
Pareto 最优	✓	✓
策略防谋	✓	✓
隐私保护	✗	✓
需要中心协调者	✓	✗
额外计算开销	—	O(1)
额外通信开销	—	O(n²)

消融实验¶

无传统消融。但协议支持两种可见性模式： - 受限可见性：每个参与者仅知道自己分到的部分 - 完全可见性：所有参与者可见完整分配方案

关键发现¶

首个同时满足无嫉妒、策略防谋和隐私保护三重性质的蛋糕切割协议
固定图替代动态图的设计是保证隐私的关键创新，需要对原算法进行非平凡的结构性改造
协议消除了对中心可信方的依赖，参与者可以自行运行协议

亮点与洞察¶

将隐私作为资源分配算法的核心需求提出，而非仅关注公平性和策略防谋性。这一视角在实际应用中非常重要
不是简单地将标准密码学替换插入原算法，而是需要对算法本身进行重构（如固定图设计），体现了密码学与经济学算法深度融合的技术贡献
即使参与者不具有策略性（non-strategic agents），隐私保护仍然有价值——解决了"虽然不想骗但也不想被看到"的现实顾虑

局限性 / 可改进方向¶

仅适用于分段均匀估值（piecewise uniform valuations），不支持分段线性、分段常数或更一般的估值函数类
安全模型假设半诚实（semi-honest），不能抵抗恶意参与者的主动攻击（如发送错误共享值）
通信复杂度为 O(n²)，在参与者数量很大时可能成为瓶颈
未来可将隐私保护技术推广到更广泛的蛋糕切割算法族

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首个隐私保护蛋糕切割协议，开辟了新方向
实验充分度: ⭐⭐⭐ 理论工作，无实验验证效率
写作质量: ⭐⭐⭐⭐ 结构清晰，密码学和公平分配两个方向的背景都交代到位
价值: ⭐⭐⭐⭐ 理论意义强，但实际适用场景受限于估值函数类型