SCIENCE@home

Majority Graphs of Assignment Problems and Properties of Popular Random Assignments

F. Brandt,Johannes Hofbauer,Martin Suderland

Published 2017 in Adaptive Agents and Multi-Agent Systems

ABSTRACT

Randomized mechanisms for assigning objects to individual agents have received increasing attention by computer scientists as well as economists. In this paper, we study a property of random assignments, called popularity, which corresponds to the well-known notion of Condorcet-consistency in social choice theory. Our contribution is threefold. First, we define a simple condition that characterizes whether two assignment problems induce the same majority graph and which can be checked in polynomial time. Secondly, we analytically and experimentally investigate the uniqueness of popular random assignments. Finally, we prove that popularity is incompatible with very weak notions of both strategyproofness and envy-freeness. This settles two open problems by Aziz et al. (2013) and reveals an interesting tradeoff between social and individual goals in random assignment.

PUBLICATION RECORD

  • Publication year

    2017

  • Venue

    Adaptive Agents and Multi-Agent Systems

  • Publication date

    2017-05-08

  • Fields of study

    Mathematics, Computer Science, Economics

  • Identifiers
    DOI 10.5555/3091125.3091178
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-38 of 38 references · Page 1 of 1

CITED BY

Showing 1-14 of 14 citing papers · Page 1 of 1