Skip to main content

TS

Manipulating the probabilistic serial rule

Authors

Haris Aziz, Serge Gaspers, Simon Mackenzie, Nicholas Mattei, Nina Narodytska and Toby Walsh

NICTA

UNSW

University of Toronto

Abstract

The probabilistic serial (PS) rule is one of the most prominent randomized rules for the assignment problem. It is well-known for its superior fairness and welfare properties. However, PS is not immune to manipulative behaviour by the agents. We initiate the study of the computational complexity of an agent manipulating the PS rule. We show that computing an expected utility better response is NP-hard. On the other hand, we present a polynomial-time algorithm to compute a lexicographic best response. For the case of two agents, we show that even an expected utility best response can be computed in polynomial time. Our result for the case of two agents relies on an interesting connection with sequential allocation of discrete objects.

BibTeX Entry

  @inproceedings{Aziz_GMMNW_15,
    author           = {Aziz, Haris and Gaspers, Serge and Mackenzie, Simon and Mattei, Nicholas and Narodytska, Nina and
                        Walsh, Toby},
    month            = may,
    year             = {2015},
    keywords         = {assignment problem, probabilistic serial mechanism, fair allocation},
    title            = {Manipulating the Probabilistic Serial Rule},
    booktitle        = {International Conference on Autonomous Agents and Multiagent Systems},
    address          = {Istanbul, Turkey}
  }

Download

Served by Apache on Linux on seL4.