2020/07/09 by Rupert Freeman, Nisarg Shah, Rohit Vaish · 2 citations
Economics, Econometrics and Finance · Decision Sciences · Social Sciences · #Game Theory and Voting Systems #Auction Theory and Applications #Experimental Behavioral Economics Studies
paper · doi:10.1145/3391403.3399537
openalex publication_date 2020/07/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
We study the problem of allocating indivisible goods among agents. When randomization is allowed, it is possible to achieve compelling fairness guarantees such as envy-freeness (Foley, 1967), which states that no agent should (in expectation) prefer any other agent's allocation to her own. For instance, we can simply allocate each good, independently of the other goods, to an agent chosen uniformly at random. However, while this scheme is fair ex-ante, it may produce outcomes that are very unfair ex-post, such as by chance assigning all the goods to a single agent. On the other hand, in the absence of randomization, some amount of ex-post unfairness is unavoidable. Nevertheless, it is possible to guarantee relaxations of envy-freeness that bound the maximum level of envy. One popular relaxation is envy-freeness up to one good (Lipton et al., 2004; Budish, 2011), which requires that the envy of any agent toward another agent can be removed by the elimination of at most one good from the envied agent's bundle.