Random assignment with optional participation

Florian Brandl, Felix Brandt, Johannes Hofbauer

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

7 Scopus citations

Abstract

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 arc. 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 uno-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.

Original languageEnglish
Title of host publication16th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2017
EditorsEdmund Durfee, Sanmay Das, Kate Larson, Michael Winikoff
PublisherInternational Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Pages326-334
Number of pages9
ISBN (Electronic)9781510855076
StatePublished - 2017
Event16th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2017 - Sao Paulo, Brazil
Duration: 8 May 201712 May 2017

Publication series

NameProceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
Volume1
ISSN (Print)1548-8403
ISSN (Electronic)1558-2914

Conference

Conference16th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2017
Country/TerritoryBrazil
CitySao Paulo
Period8/05/1712/05/17

Keywords

  • Boston mechanism
  • No-show paradox
  • Participation
  • Popular random assignments
  • Probabilistic serial rule
  • Random assignment
  • Random serial dictatorship
  • Stochastic dominance

Fingerprint

Dive into the research topics of 'Random assignment with optional participation'. Together they form a unique fingerprint.

Cite this