Fair and efficient resource allocation problems occupy complex decision class
Fair and Efficient Allocations: Decision Problems in the Gap of Polynomial Hierarchy
Computer Science and Game Theory
Summary
This paper looks at how to fairly divide things that cannot be split, like indivisible items, among people so that no one envies another and the outcome is efficient. The authors study how hard it is to decide if a perfect division exists under different rules and conditions. They find that many of these problems are more complicated than typical computer problems, lying between well-known complexity levels, which means they are challenging to solve quickly. Their results also answer previously open questions about these difficulties in simpler situations with fewer people or restricted ways of valuing items.
What this means in practice
- •For market designers: Understand the computational limits of finding envy-free and efficient allocations for indivisible goods under different valuation models and numbers of agents.
- •For algorithm developers: Identify specific problem cases where fair and efficient allocation decision problems are computationally harder than NP or coNP, guiding algorithm focus and design.
A theory result. No direct application yet.
Authors
Xiaolin Bu, Biaoshuai Tao
Abstract
We consider the fair division problem with indivisible goods and study the following decision problem: given a fair division instance, does there exist an allocation that is envy-free and efficient? We consider two efficiency criteria: Pareto-optimality and social welfare optimality. We provide a complete landscape on the computational complexity of this decision problem, with the number of agents ranging from $2$ to $\infty$, both additive valuations and general valuations, and the more restricted class of $k$-ary valuation functions (where an item's marginal value is restricted to $\{0,1,\ldots,k-1\}$ for some constant $k\geq2$). One interesting observation is that many versions of the above-mentioned decision problems fall into the ``gap'' between the first and the second levels of the polynomial hierarchy. Specifically, assuming the polynomial hierarchy does not collapse to the first level (i.e., assuming $\text{NP}\neq\text{coNP}$), these problems are in $(Σ_2^{\text{p}}\capΠ_2^{\text{p}})\setminus(\text{NP}\cup\text{coNP})$. In particular, we provide a fine-grained complexity analysis across different parameter regimes, including the number of agents and the choice of valuation models. Depending on different parameters, many problems admit different complexity classifications, ranging from the intermediate classes $Θ_2^{\text{p}}$ and $Δ_2^{\text{p}}$ between the two levels to $Σ_2^{\text{p}}$-completeness. Finally, De Keijzer et al. show the $Σ_2^{\text{p}}$-completeness of the decision problem when considering Pareto-optimality as the efficiency criterion with additive valuations. Our main results extend this result to more restricted settings, such as instances with a constant number of agents or $3$-ary valuation functions, which resolves the open problem given by Bouveret and Lang.