Optimal Allocations under Strongly Pigou-Dalton Criteria: Hidden Layer Structure & Efficient Combinatorial Approach
We investigate optimal social welfare allocations of $m$ items to $n$ agents with binary additive or submodular valuations. For binary additive valuations, we prove that the set of optimal allocations coincides with the set of so-called \emph{stable allocations}, as long as the employed criterion for evaluating social welfare is strongly Pigou-Dalton (SPD) and symmetric. Many common criteria are SPD and symmetric, such as Nash social welfare, leximax, leximin, Gini index, entropy, and envy sum. We also design efficient algorithms for finding a stable allocation, including an $O(m^2n)$ time algorithm for the case of indivisible items, and an $O(m^2n^5)$ time one for the case of divisible items. The first is faster than the existing algorithms or has a simpler analysis. The latter is the first combinatorial algorithm for that problem. It utilizes a hidden layer partition of items and agents admitted by all stable allocations, and cleverly reduces the case of divisible items to the case of indivisible items.In addition, we show that the profiles of different optimal allocations have a small Chebyshev distance, which is 0 for the case of divisible items under binary additive valuations, and is at most 1 for the case of indivisible items under binary submodular valuations.