Achieving Envy-freeness and Equitability with Monetary Transfers
Keywords:Fair Division, Social Choice / Voting
AbstractWhen allocating indivisible resources or tasks, an envy-free allocation or equitable allocation may not exist. We present a sufficient condition and an algorithm to achieve envy-freeness and equitability when monetary transfers are allowed. The approach works for any agent valuation functions (positive or negative) as long as they satisfy superadditivity. For the case of additive utilities, we present a characterization of allocations that can simultaneously be made equitable and envy-free via payments. Our study shows that superadditive valuations constitute the largest class of valuations for which an envy-free and equitable outcome exists for all instances. We then present a distributed algorithm to compute an approximately envy-free outcome for any class of valuations.
How to Cite
Aziz, H. (2021). Achieving Envy-freeness and Equitability with Monetary Transfers. Proceedings of the AAAI Conference on Artificial Intelligence, 35(6), 5102-5109. https://doi.org/10.1609/aaai.v35i6.16645
AAAI Technical Track on Game Theory and Economic Paradigms