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

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

一句话总结¶

提出首个隐私保护的蛋糕切割协议 PP_CC_puv，基于秘密共享和安全多方计算（MPC）技术改造 Chen et al. 的策略防操纵算法，在保持无嫉妒、Pareto 最优和策略防操纵性质的同时防止任何参与方获知他人偏好信息。

研究背景与动机¶

领域现状：蛋糕切割问题是公平分配理论的经典问题——如何将连续资源（建模为 \([0,1]\) 区间）公平分配给 \(n\) 个代理。过去二十年在公平性方面取得了很大进展，Chen et al. (2010) 提出了同时满足无嫉妒（envy-free）和策略防操纵（strategyproof）的确定性算法 CC_puv（适用于分段均匀估值函数）。

现有痛点：策略防操纵只能解决"说谎无利可图"的问题，但代理可能出于隐私顾虑不愿如实报告偏好——即使不说谎比说谎好，他们也害怕暴露偏好。例如：电信公司竞拍频谱时，公开偏好会暴露未来战略方向；广告时间分配中，偏好可能泄露产品上市计划；数据保护法规也可能限制偏好公开。

核心矛盾：现有算法要求代理向中央协调者或其他参与方公开估值函数，但公开偏好可能带来隐私风险。策略防操纵和隐私保护是两个正交的需求维度。

本文目标 设计一个同时满足公平性（envy-free）、效率性（Pareto-optimal）、策略防操纵（strategyproof）和隐私保护（privacy-preserving）的蛋糕切割协议。

切入角度：将 CC_puv 算法的集中式计算替换为基于 Shamir 秘密共享和安全多方计算的分布式协议，使代理可以在不暴露偏好的情况下完成分配。

核心 idea：用密码学的秘密共享和安全多方计算技术将已有的策略防操纵蛋糕切割算法"私有化"，使代理既没动机说谎也不会暴露偏好。

方法详解¶

整体框架¶

协议 PP_CC_puv 忠实模拟原始 CC_puv 算法的逻辑，但所有计算都在秘密共享的数值上进行。整体分为五个阶段：（1）代理秘密共享各自的分段均匀估值函数；（2）将蛋糕分割成区间集合 \(\mathcal{W}\)；（3）用二值向量编码哪些区间被哪些代理"渴望"；（4）迭代地选择具有最小平均需求的代理子集并分配；（5）最终将区间分配结果（以秘密共享形式）揭示给各代理。

关键设计¶

估值函数的秘密共享（SharingPrivateValuations）:
- 功能：将每个代理的分段均匀估值函数转为 \((t,n)\)-秘密共享
- 核心思路：每个代理的估值由 \(\ell\) 个区间端点 \((a_{i,j}, b_{i,j})\) 描述。首先代理协商一个足够大的整数 \(Q = 10^d\) 将实数端点离散化为整数（无损），然后每个代理将 \(2\ell\) 个端点用 Shamir 的 \((t,n)\)-门限秘密共享分发。为防止作弊，协议包含完整性检查机制。共享门限设为 \(t = \lfloor(n+1)/2\rfloor\)，保证诚实多数即可保护秘密
- 设计动机：直接使用标准密码学会泄露区间数量等侧信道信息；通过将所有代理填充到相同数量 \(\ell\) 的区间并用空区间 \([1,1)\) 补齐，消除了这一泄露通道
固定图结构的遗忘式最大流（AssignCakeToSelectedAgents）:
- 功能：在不泄露图结构的情况下完成区间到代理的公平分配
- 核心思路：原始 CC_puv 在每轮迭代中构建不同的有向图并求最大流。但动态图的结构会泄露哪些代理渴望哪些区间。PP_CC_puv 用一个固定的全量图替代动态图，边权通过密码学计算得出：不相关的边权值设为 0 的秘密共享，分配通过 MPC 进行。这样协议对图结构保持"遗忘"（oblivious）
- 设计动机：确保协议执行过程中不会因图结构变化而泄露代理偏好与区间之间的关联
安全基本运算的组合:
- 功能：提供完整的安全计算原语集合以支持协议运行
- 核心思路：在秘密共享上实现仿射组合（零通信开销）、乘法（DN07 协议）、比较（\([[1_{u<v}]]\)）、相等测试（\([[1_{u=0}]]\)）、最小值、OR 运算和除法。这些原语按需组合实现排序、区间编码、需求计算等高层操作
- 设计动机：所有中间值——代理需求、区间选择、流计算——都以秘密共享形式存在，任何单一方无法获取明文信息

损失函数 / 训练策略¶

本文为理论密码学协议，无训练过程。计算开销为：原始算法复杂度的 \(\mathcal{O}(1)\) 倍计算开销 + 最多 \(\mathcal{O}(n^2)\) 额外通信代价。安全性基于信息论保证（非计算假设），在半诚实模型下成立，需要诚实多数。

实验关键数据¶

主实验¶

本文为理论工作，实验以形式化证明为主。核心结果是定理证明：

性质	CC_puv (原)	PP_CC_puv (本文)	说明
无嫉妒 (Envy-free)	✓	✓	完整保持
Pareto 最优	✓	✓	完整保持
策略防操纵	✓	✓	完整保持
隐私保护	✗	✓	新增——信息论安全
去中心化	✗	✓	新增——无需可信第三方

消融实验¶

协议组件	计算开销	通信开销	安全保证
秘密共享估值	\(\mathcal{O}(n\ell)\)	\(\mathcal{O}(n^2\ell)\)	隐藏估值+区间数
安全排序(分割区间)	\(\mathcal{O}(m \log m)\) MPC轮	\(\mathcal{O}(m^2)\)	隐藏端点排列
遗忘式最大流	\(\mathcal{O}(1)\) 相对原算法	\(\mathcal{O}(n^2)\) 每轮	隐藏图结构
最终分配揭示	\(\mathcal{O}(m)\)	\(\mathcal{O}(nm)\)	可选全公开/仅自己

关键发现¶

隐私保护不需要牺牲公平性或效率性——所有原算法的保证完整保留
最大的技术挑战是将动态图替换为固定图以防止结构泄露，这需要根本性的算法重构而非简单的"插入加密"
通信复杂度主要瓶颈在安全排序和最大流计算环节
协议支持两种揭示模式：全局可见（所有人看到完整分配）和受限可见（每人仅看到自己的份额）

亮点与洞察¶

首个隐私保护蛋糕切割协议：打通了公平分配理论与密码学之间的桥梁，将"不想说谎"和"不怕暴露"合二为一
固定图遗忘式最大流：用固定结构图+密码学边权替代动态图，避免结构泄露。这一技巧可推广到任何需要在秘密数据上执行图算法的场景
去中心化副产品：隐私协议的一个意外好处是消除了对中央协调者的需求，代理可自行执行协议——适用于没有可信基础设施的临时场景

局限与展望¶

仅处理分段均匀估值函数（piecewise uniform），尚不支持更一般的分段线性或任意估值函数
安全模型假设半诚实（semi-honest）——代理遵循协议但尝试推断他人信息。恶意对手模型下需要额外保障
需要诚实多数假设（>50% 诚实参与方），不满足时安全性失效
通信复杂度 \(\mathcal{O}(n^2)\) 在大规模参与方时可能成为瓶颈
作者指出将技术扩展到通用蛋糕切割算法（如支持任意估值函数的 Aziz-Mackenzie 协议）是自然方向

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首个隐私保护蛋糕切割协议，理论贡献突出
实验充分度: ⭐⭐⭐ 理论工作以证明为主，无实际运行时间对比
写作质量: ⭐⭐⭐⭐ 密码学和公平分配理论都讲解清楚，适合跨领域读者
价值: ⭐⭐⭐⭐ 在隐私日趋重要的时代，为公平分配理论开辟了新方向