Fractional Assignment with $\ell_1$ Preferences

Abstract

We study a fractional assignment setting where $n$ objects are to be assigned to $n$ agents with unit capacity, and each agent specifies an ideal distribution over the objects. Unlike in classic random assignment, these ideal distributions are not necessarily degenerate, as agents may prefer a mixture of objects rather than any single object. We assume that agents seek to minimize the $\ell_1$ distance between their ideal distribution and the distribution they receive, which is equivalent to maximizing the overlap between the two distributions. We propose two mechanisms, one based on water filling (WF) and the other on quadratic programming (QP), and show that both mechanisms are utilitarian-optimal (and hence Pareto efficient), envy-free, strategyproof, and satisfy equal treatment of equals. Moreover, we highlight a distinct advantage of each mechanism: while the WF mechanism satisfies the stronger property of group-strategyproofness, the QP mechanism is more robust in terms of egalitarian overlap welfare.