Approximate Pareto Set for Fair and Efficient Allocation: Few Agent Types or Few Resource Types

Approximate Pareto Set for Fair and Efficient Allocation: Few Agent Types or Few Resource Types

Trung Thanh Nguyen, Jörg Rothe

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence
Main track. Pages 290-296. https://doi.org/10.24963/ijcai.2020/41

In fair division of indivisible goods, finding an allocation that satisfies fairness and efficiency simultaneously is highly desired but computationally hard. We solve this problem approximately in polynomial time by modeling it as a bi-criteria optimization problem that can be solved efficiently by determining an approximate Pareto set of bounded size. We focus on two criteria: max-min fairness and utilitarian efficiency, and study this problem for the setting when there are only a few item types or a few agent types. We show in both cases that one can construct an approximate Pareto set in time polynomial in the input size, either by designing a dynamic programming scheme, or a linear-programming algorithm. Our techniques strengthen known methods and can be potentially applied to other notions of fairness and efficiency as well.
Keywords:
Agent-based and Multi-agent Systems: Computational Social Choice
Agent-based and Multi-agent Systems: Resource Allocation
Agent-based and Multi-agent Systems: Economic Paradigms, Auctions and Market-Based Systems