Random Assignment with Optional Participation

With F. Brandt and J. Hofbauer
In Proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 326–334. IFAAMAS, 2017

A central problem in multiagent systems concerns the fair assignment of objects to agents. We initiate the study of randomized assignment rules with optional participation and investigate whether agents always benefit from participating in the assignment mechanism. Our results are largely positive, irrespective of the strategyproofness of the considered rules. In particular, random serial dictatorship, the probabilistic serial rule, and the Boston mechanism strictly incentivize single agents to participate, no matter what their underlying utility functions are. Random serial dictatorship and the probabilistic serial rule also cannot be manipulated by groups of agents who abstain strategically. These results stand in contrast to results for the more general domain of voting where many rules suffer from the so-called “no-show paradox”. We also show that rules that return popular random assignments may disincentivize participation for some (but never all) utility representations consistent with the agents’ ordinal preferences.