Random Assignment with Optional Participation

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. General Terms Economics, Theory

Authors

• Florian Brandl TU München
• Felix Brandt Technical University of Munich
• Johannes Hofbauer Technical University of Munich

Keywords

• random assignment
• random serial dictatorship
• probabilistic serial rule
• Boston mechanism
• popular random assignments
• participation
• no-show paradox
• stochastic dominance