Finding EFL and EQL Allocations of Indivisible Goods
Wei Huang, Wen Ming Huang, Dong Cai · 2020
Fair resource allocation has become an emerging research topic in Computer Science and Artificial Intelligence. We can judge whether the allocation is “fair” from two aspects. First, if each agent prefers his own set of bundle, that is, envy-free, then we say that the allocation is fair; If each agent's valuation of his own item set is equal to other agents' valuation of its own item-equitability (EQ), then we also say that this allocation is fair. Solving the problem of envy-free (EF) or equitability (EQ) fair allocation is proved to be NP-hard, so this paper mainly studies the problem of approximate fair allocation i.e., approximate envy-free and approximate equitability. Our contribution are as follows. 1. We proved that equitable up to one less-preferred good (EQL) allocation always exists and can be found in polynomial time; 2. We proved that the allocation that satisfies both equitable up to one less-preferred good (EQL) and Pareto optimality (PO) exists and provides a pseudo-polynomial time algorithm that can find the allocation when the valuation function is additive with strictly positive; 3. We proved that when the allocation with specific valuation that satisfies equitable up to one less-preferred good (EQL), envy-free up to one less-preferred good (EFL) and Pareto optimality (PO) exists then it can be found in polynomial time.