Bounded Incentives in Manipulating the Probabilistic Serial Rule

The Probabilistic Serial mechanism is valued for its fairness and efficiency in addressing the random assignment problem. However, it lacks truthfulness, meaning it works well only when agents' stated preferences match their true ones. Significant utility gains from strategic actions may lead s...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computer and system sciences 2024-03, Vol.140, p.103491, Article 103491
Main Authors: Huang, Haoqiang, Wang, Zihe, Wei, Zhide, Zhang, Jie
Format: Article
Language:English
Subjects:
Incentive ratio
manipulation
probabilistic serial mechanism
random assignment
resource allocation
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The Probabilistic Serial mechanism is valued for its fairness and efficiency in addressing the random assignment problem. However, it lacks truthfulness, meaning it works well only when agents' stated preferences match their true ones. Significant utility gains from strategic actions may lead self-interested agents to manipulate the mechanism, undermining its practical adoption. To gauge the potential for manipulation, we explore an extreme scenario where a manipulator has complete knowledge of other agents' reports and unlimited computational resources to find their best strategy. We establish tight incentive ratio bounds of the mechanism. Furthermore, we complement these worst-case guarantees by conducting experiments to assess an agent's average utility gain through manipulation. The findings reveal that the incentive for manipulation is very small. These results offer insights into the mechanism's resilience against strategic manipulation, moving beyond the recognition of its lack of incentive compatibility.
ISSN:0022-0000
1090-2724
DOI:10.1016/j.jcss.2023.103491