TR-2017-02

Possible and necessary allocations under serial dictatorship with incomplete preference lists

Katarína Cechlárová, Tamás Fleiner, Ildikó Schlotter



Abstract

We study assignment problems in a model where agents have strict preferences over objects, allowing preference lists to be incomplete. We investigate the questions whether an agent can obtain or necessarily obtains a given object under serial dictatorship. We prove that both problems are computationally hard even if agents have preference lists of length at most 3; by contrast, we give linear-time algorithms for the case where preference lists are of length at most 2. We also study a capacitated version of these problems where objects come in several copies.


Bibtex entry:

@techreport{egres-17-02,
AUTHOR = {Cechl{\'a}rov{\'a}, Katar{\'i}na and Fleiner, Tam{\'a}s and Schlotter, Ildik{\'o}},
TITLE = {Possible and necessary allocations under serial dictatorship with incomplete preference lists},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2017},
NUMBER = {TR-2017-02}
}


Last modification: 21.9.2017. Please email your comments to Tamás Király!