TY - JOUR AU - Aziz, Haris PY - 2021/05/18 Y2 - 2024/03/28 TI - Achieving Envy-freeness and Equitability with Monetary Transfers JF - Proceedings of the AAAI Conference on Artificial Intelligence JA - AAAI VL - 35 IS - 6 SE - AAAI Technical Track on Game Theory and Economic Paradigms DO - 10.1609/aaai.v35i6.16645 UR - https://ojs.aaai.org/index.php/AAAI/article/view/16645 SP - 5102-5109 AB - When 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. ER -