Equitability and Welfare Maximization for Allocating Indivisible Items

We study fair allocations of indivisible goods and chores in conjunction with system efficiency, measured by two social welfare functions, namely utilitarian and egalitarian welfare. To model preference, each agent is associated with a cardinal and additive valuation function. The fairness criteria we are concerned with are equitability up to any item (EQX) and equitability up to one item (EQ1). For the trade-off between fairness and efficiency, we investigate efficiency loss under these fairness constraints and establish the price of fairness. From the computational perspective, we provide an almost complete picture of the computational complexity of (i) deciding the existence of an EQX/EQ1 and welfare-maximizing allocation; (ii) computing a welfare maximizer among all EQX/EQ1 allocations.

Authors

• Ankang Sun School of Computer Science and Technology, Shandong University
• Bo Chen Middle Tennessee State University
• Xuan Vinh Doan

Keywords

• Fair division
• Equitability
• Indivisible items
• Price of Fairness