Favoring Eagerness for Remaining Items: Achieving Efficient and Fair Assignments

In the assignment problem, items must be assigned to agents who have unit demands, based on agents' ordinal preferences. Often the goal is to design a mechanism that is both fair and efficient. In this paper, we first prove that, unfortunately, the desirable efficiency notions rank-maximality, ex-post favoring-higher-ranks, and ex-ante favoring-higher-ranks, which aim to allocate each item to agents who rank it highest over all the items, are incompatible with the desirable fairness notions strong equal treatment of equals (SETE) and sd-weak-envy-freeness (sd-WEF) simultaneously. In light of this, we propose novel properties of efficiency based on a subtly different notion to favoring higher ranks, by favoring "eagerness" for remaining items and aiming to guarantee that each item is allocated to agents who rank it highest among remaining items. We prove that the eager Boston mechanism satisfies ep-FERI and sd-WSP, and that the uniform probabilistic respecting eagerness mechanism satisfies ea-FERI. We also prove that both mechanisms satisfy SETE and sd-WEF, and show that no mechanism can satisfy stronger versions of envyfreeness and strategyproofness while simultaneously maintaining SETE, and either ep-FERI or ea-FERI. X. Guo and Y. Cao are with Key Laboratory of High Confidence Software Technologies (MOE), Department of Computer Science and Technology, Peking University, Beijing 100871, China (e-mail: guoxiaoxi@pku.edu.cn; S. Sikdar is with Department of Computer Science, Binghamton University (email: ssikdar@binghamton.edu). H. Wang is with School of Computer Science and Cyber Engineering, Guangzhou University, China, and Key Laboratory of High Confidence Software Technologies (MOE), Department of Computer Science and Technology, Peking University, Beijing 100871, China (whpxhy@pku.edu.cn). This serves as a useful model for a variety of problems where the items may be either indivisible such as houses (Shapley and Scarf, 1974), dormitory rooms (Chen and Sönmez, 2002), and school choice without priorities (Miralles, 2009); or divisible such as natural resources like land and water (Segal-Halevi, 2016), and computational resources in cloud computing (Ghodsi et al., 2011, 2012; Grandl et al., 2014).