Favoring Eagerness for Remaining Items: Designing Efficient, Fair, and Strategyproof Mechanisms
This addresses the problem of efficiently and fairly assigning items to agents with ordinal preferences in a strategyproof manner, representing an incremental advance in mechanism design.
The paper tackled the assignment problem by proposing a new efficiency property called favoring-eagerness-for-remaining-items (FERI), which ensures first-choice maximality, and designed mechanisms that satisfy FERI along with fairness and strategyproofness properties, while also exploring impossibility results for stronger guarantees.
In the assignment problem, the goal is to assign indivisible items to agents who have ordinal preferences, efficiently and fairly, in a strategyproof manner. In practice, first-choice maximality, i.e., assigning a maximal number of agents their top items, is often identified as an important efficiency criterion and measure of agents' satisfaction. In this paper, we propose a natural and intuitive efficiency property, favoring-eagerness-for-remaining-items (FERI), which requires that each item is allocated to an agent who ranks it highest among remaining items, thereby implying first-choice maximality. Using FERI as a heuristic, we design mechanisms that satisfy ex-post or ex-ante variants of FERI together with combinations of other desirable properties of efficiency (Pareto-efficiency), fairness (strong equal treatment of equals and sd-weak-envy-freeness), and strategyproofness (sd-weak-strategyproofness). We also explore the limits of FERI mechanisms in providing stronger efficiency, fairness, or strategyproofness guarantees through impossibility results.