Allocating Indivisible Goods: Fairness and Efficiency
Dr Jain, Sanjay, Provost'S Chair Professor, School of Computing
Dr Stephan, Frank Christian, Professor, School of Computing
COM1 Level 3
MR1, COM1-03-19
Abstract:
Allocating scarce resources is a perennial societal challenge. As fairness is often a central consideration in such decisions, the problem of fair division has been extensively studied by mathematicians, economists, and computer scientists alike. In particular, fair division of indivisible goods is a subtopic that has been gaining significant attention in recent years. Two main objectives in this problem are fairness and efficiency. One of the most prominent fairness notions is envy-freeness up to one good (EF1)—which means that if an agent envies another agent, this envy can be resolved by removing some good from the latter agent's bundle. On the other hand, efficiency is often measured via a welfare function such as utilitarian or egalitarian welfare. In this thesis, we investigate various methods for allocating indivisible goods, and analyze their fairness and efficiency guarantees.
We begin by exploring the trade-off between fairness and efficiency using the concept of price of fairness, which quantifies the welfare loss due to a specific fairness property. We evaluate the prices of several fairness notions—including EF1—where the welfare is defined by egalitarian welfare. We then examine three well-established methods for obtaining EF1 allocations: welfarist rules, picking sequences, and the envy cycle elimination (ECE) algorithm. Among the three, welfarist rules have the advantage of producing efficient allocations, since by definition, these rules always choose an allocation maximizing some welfare function. In particular, we study additive welfarist rules and determine which of them guarantee EF1 for certain subclasses of instances. Next, we consider picking sequences, wherein agents take turns picking their favorite goods that are available, according to a predetermined agent ordering. Recursively balanced picking sequences—where every agent picks exactly once in each round—yield EF1 allocations; a well-known example is the round-robin algorithm. We compare these sequences using different fairness benchmarks, and characterize the best and worst recursively balanced picking sequences according to each benchmark. Finally, we investigate the ECE algorithm—a versatile algorithm that works by alternating between allocating a good to an unenvied agent and resolving any resulting envy cycle. As the final allocation is always EF1 regardless of the ordering of allocated goods and receiving agents, this flexibility can be exploited to obtain additional guarantees. We study several heuristics for choosing the good and agent in each iteration of the ECE algorithm, and examine their efficiency guarantees in terms of both utilitarian and egalitarian welfare.