随机占优策略的可证明性与次模性

《Mathematical Social Sciences》：Stochastic dominance strategyproofness and submodularity

　　•构建了选项集的随机对应形式。•从单代理视角为随机支配策略证明机制提供了新的刻画方式。•将随机机制设计与凸博弈联系起来。

引言
关于策略证明机制的研究催生了选项集这一概念（Barberà，1983；Hammond，1979）。
1. 策略证明机制能够激励代理真实报告其偏好。这一激励相容条件的一个关键含义是，每个代理都能获得其在自身能力范围内（考虑其他代理的偏好后）最偏好的选择；然而，她无法影响以此方式可获得的选项集合，因为那样做会给她提供虚假报告的动机。这类选项集合被称为选项集，代表着单个代理所面临的决策对象。
选项集已被广泛用于研究各种情境下的（联盟）策略证明性，包括集体决策（Barberà和Peleg，1990）、纯粹公共物品供给（Berga和Serizawa，2000）以及不可分割物品的分配（Pápai，2000）。本文旨在构建选项集的随机对应形式，期望以此推动对随机版本策略证明性相关研究的发展。
随机机制以代理报告的偏好排序作为输入，输出结果的概率分布。现有文献提出了多种随机激励相容概念，这些概念取决于代理如何评估此类概率分布。
2. 在这些概念中，我们重点研究随机支配策略证明性（sd-策略证明性），这一概念最早由Gibbard（1977）提出。该概念具有稳健性，即对于与代理的序数偏好排序一致的任何基数效用函数，真实报告都能使代理的预期效用最大化。它也非常适合那些难以获取基数效用信息的应用场景。
借助Gibbard（1977）的刻画方法，我们表明，一个满足sd-策略证明性的单代理机制可以表示为一个标准化、缩放后的、次模的且非递减的集合函数。
3. 这一结果揭示了机制设计与合作博弈论之间的有趣联系。通过对偶性，满足sd-策略证明性的单代理机制与具有单位大联盟价值的非递减凸博弈之间存在一一对应关系（Shapley，1971）。此外，用于刻画确定性策略证明性单代理机制的选项集所对应的集合函数，恰好是一致性博弈的对偶函数（Shapley，1953）。
4. 由于一致性博弈构成了特征函数向量空间的一组基，这种对应关系意味着每一个满足sd-策略证明性的单代理机制都可以表示为多个确定性策略证明性单代理机制的线性组合。
5. 这一发现进一步建立了确定性策略证明性单代理机制与其随机对应形式之间的联系，补充了Pycia和ünver（2015）从整数规划角度研究这一关系的成果。

本文其余结构如下：第2节介绍模型并回顾现有的刻画方法；第3节证明主要的刻画结果；第4节将这一结果与凸博弈联系起来，并探讨其对机制设计的意义；最后第5节对全文进行总结。

章节要点
单代理模型
本文聚焦于单代理模型。关于该模型与标准多代理模型之间的关联，可参见脚注7和9。
新的刻画方法
我们为sd-策略证明性提出了新的刻画方式。为此，我们首先介绍了集合函数及其性质。
凸博弈与sd-策略证明性的表示
我们通过重新审视合作博弈论中的经典结果，进一步研究了选项集的随机泛化形式。特别是，我们运用一致性博弈的标准基结果，得到了用选项集表示sd-策略证明性的方法。
在本节中，我们将X视为一组玩家，将每个子集A?X视为一個联盟。定义在X上的特征函数是一个标准化集合函数v:2X→R，即v0?=0。值vA被称为……
结论
我们在单代理框架下构建了选项集的随机泛化形式。我们证明了满足sd-策略证明性的单代理机制恰恰可以通过标准化、缩放后的、非递减的且次模的集合函数来刻画。通过对偶性，这些集合函数对应于具有单位大联盟价值的非递减凸博弈，而选项集对应的集合函数则与一致性博弈互为对偶。鉴于一致性博弈构成了特征函数向量空间的一组基，这一对应关系意味着每一个满足sd-策略证明性的单代理机制都可以表示为多个确定性策略证明性单代理机制的线性组合。
利益冲突声明
作者声明不存在任何可能影响本文研究工作的已知财务利益冲突或个人关系。
致谢
本研究未获得公共部门、商业机构或非营利组织方面的任何特定资助。
Ryo Tsukamoto