论文标题
操纵概率序列规则时有界的激励措施
Bounded Incentives in Manipulating the Probabilistic Serial Rule
论文作者
论文摘要
概率序列机制以其理想的公平性和效率特性而闻名。它是随机分配问题最突出的协议之一。但是，概率连续序列不兼容，因此这些理想的属性仅适用于代理人所宣布的偏好，而不是其真正的偏好。通过战略行为获得的大量实用性将触发自私的药物来操纵机制，并颠覆实践中采用该机制的基础。在本文中，我们表征了单个代理可以通过战略操纵来增加其效用的程度。我们表明该机制的激励比为$ \ frac {3} {2} $。也就是说，没有任何代理商会误导其偏好，从而使其效用变成了实际报告时的偏好超过1.5倍。通过允许代理商获得有关其他代理报告的完整信息，并确定最佳响应策略，即使它在计算上很棘手，该比率是最坏的保证。为了补充这项最糟糕的研究，我们通过实验平均进一步评估了代理商的效用增益。实验表明，操纵该规则的代理动机非常有限。这些结果阐明了概率序列反对战略操纵的鲁棒性，这比知道这不是激励兼容的范围更进一步。
The Probabilistic Serial mechanism is well-known for its desirable fairness and efficiency properties. It is one of the most prominent protocols for the random assignment problem. However, Probabilistic Serial is not incentive-compatible, thereby these desirable properties only hold for the agents' declared preferences, rather than their genuine preferences. A substantial utility gain through strategic behaviors would trigger self-interested agents to manipulate the mechanism and would subvert the very foundation of adopting the mechanism in practice. In this paper, we characterize the extent to which an individual agent can increase its utility by strategic manipulation. We show that the incentive ratio of the mechanism is $\frac{3}{2}$. That is, no agent can misreport its preferences such that its utility becomes more than 1.5 times of what it is when reports truthfully. This ratio is a worst-case guarantee by allowing an agent to have complete information about other agents' reports and to figure out the best response strategy even if it is computationally intractable in general. To complement this worst-case study, we further evaluate an agent's utility gain on average by experiments. The experiments show that an agent' incentive in manipulating the rule is very limited. These results shed some light on the robustness of Probabilistic Serial against strategic manipulation, which is one step further than knowing that it is not incentive-compatible.
