Abstract

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.
Original languageEnglish
Article number103491
Number of pages15
JournalJournal of Computer and System Sciences
Volume140
Early online date28 Oct 2023
DOIs
Publication statusPublished - 31 Mar 2024

Data Availability Statement

No data was used for the research described in the article.

Fingerprint

Dive into the research topics of 'Bounded incentives in manipulating the probabilistic serial rule'. Together they form a unique fingerprint.

Cite this