|
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:
| 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 egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2017}, |
| NUMBER | = | {TR-2017-02} |