Non-Obvious Manipulability in Extensive-Form Mechanisms: The Revelation Principle for Single-Parameter Agents
Non-Obvious Manipulability in Extensive-Form Mechanisms: The Revelation Principle for Single-Parameter Agents
复制标题
扩展形式机制中的非明显可操作性：单参数智能体的揭示原理
DOI：
10.24963/ijcai.2023/278
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Carmine Ventre
中科院分区：
文献类型：
--
作者：
T. Archbold;B. D. Keijzer;Carmine Ventre
最近的工作在算法机制设计的重点是设计机制的代理有限理性，修改必须满足的约束，以实现激励相容性。从李鸿章对防策略性的强化开始，明显防策略性（OSP）要求说真话比不诚实更“明显”，大致意思是说真话的最坏结果必须不比不诚实的最好结果差。优势策略激励相容机制的一个著名结果，允许我们将注意力限制在直接机制上，称为启示原则，并不适用于OSP：实施细节对机制的明显激励属性很重要。在研究现实机制中的代理策略时，Troyan和莫里尔引入了一种被称为非明显可操作性的防策略性的放松，它只需要比较代理效用函数的某些极值，以便使机制与激励相容。具体来说，如果诚实行为的最佳和最差结果并不比不诚实行为的最佳和最差结果更差，则机制不是明显可操纵的（NOM）。在这项工作中，我们首先扩展了直接启示NOM机制设计的循环单调性框架，间接机制。然后，我们将其应用到两个设置，单参数代理和两个代理的机制，其中一个有一个两值域，并表明，在这些模型的启示原则持有：直接机制是一样强大的间接的。
Recent work in algorithmic mechanism design focuses on designing mechanisms for agents with bounded rationality, modifying the constraints that must be satisfied in order to achieve incentive compatibility. Starting with Li's strengthening of strategyproofness, obvious strategyproofness (OSP) requires truthtelling to be "obvious" over dishonesty, roughly meaning that the worst outcome from truthful actions must be no worse than the best outcome for dishonest ones. A celebrated result for dominant-strategy incentive-compatible mechanisms that allows us to restrict attention to direct mechanisms, known as the revelation principle, does not hold for OSP: the implementation details matter for the obvious incentive properties of the mechanism. Studying agent strategies in real-life mechanisms, Troyan and Morrill introduce a relaxation of strategyproofness known as non-obvious manipulability, which only requires comparing certain extrema of the agents' utility functions in order for a mechanism to be incentive-compatible. Specifically a mechanism is not obviously manipulable (NOM) if the best and worst outcomes when acting truthfully are no worse than the best and worst outcomes when acting dishonestly. In this work we first extend the cycle monotonicity framework for direct-revelation NOM mechanism design to indirect mechanisms. We then apply this to two settings, single-parameter agents and mechanisms for two agents in which one has a two-value domain, and show that under these models the revelation principle holds: direct mechanisms are just as powerful as indirect ones.
公平高效的分配，没有明显的操纵
DOI：
--
发表时间：
2022
期刊：
Advances in neural information processing systems
影响因子：
--
作者：
Psomas, Alexandros;Verma, Paritosh
通讯作者：
Verma, Paritosh
OSP机制的近似保证：以机器调度和设施选址为例
影响因子：
1.1
作者：
Ferraioli D
通讯作者：
Ferraioli D