First-Choice Maximality Meets Ex-ante and Ex-post Fairness
This work addresses fairness and efficiency in resource allocation for agents with preferences, offering incremental improvements by combining existing concepts like FCM and EF1 in new mechanisms.
The paper tackles the assignment problem with ordinal preferences by designing randomized mechanisms that maximize first-choice assignments while ensuring Pareto efficiency and providing both ex-ante and ex-post fairness guarantees, such as ex-post envy-freeness up to one item (EF1).
For the assignment problem where multiple indivisible items are allocated to a group of agents given their ordinal preferences, we design randomized mechanisms that satisfy first-choice maximality (FCM), i.e., maximizing the number of agents assigned their first choices, together with Pareto efficiency (PE). Our mechanisms also provide guarantees of ex-ante and ex-post fairness. The generalized eager Boston mechanism is ex-ante envy-free, and ex-post envy-free up to one item (EF1). The generalized probabilistic Boston mechanism is also ex-post EF1, and satisfies ex-ante efficiency instead of fairness. We also show that no strategyproof mechanism satisfies ex-post PE, EF1, and FCM simultaneously. In doing so, we expand the frontiers of simultaneously providing efficiency and both ex-ante and ex-post fairness guarantees for the assignment problem.