EFX의 비용: 일반화된 평균 복지 및 복잡성 이분법, 그리고 적은 수의 잉여 상품을 갖는 경우

The Cost of EFX: Generalized-Mean Welfare and Complexity Dichotomies with Few Surplus Items

분할 불가능한 자원을 할당할 때, '모든 사람에게 적합한 공정성(Envy-freeness up to any good, EFX)'은 중요한 공정성 개념이지만, 일반적으로 EFX의 존재 여부가 해결되지 않았습니다. 잉여 상품의 수가 적은 경우 (즉, 상품의 수가 에이전트 수보다 적은 상수, 최대 3개) EFX 할당은 반드시 존재하며, 이는 존재 문제를 효율성과 계산 문제로 전환시킵니다. 본 연구에서는 EFX가 일반적으로 연구되는 효용 극대화(p=1), 내쉬 균형(p=0), 그리고 평등(p → -∞) 목표를 포함하는 일반화된 평균($p$-mean) 복지와 어떻게 상호작용하는지 분석합니다. 우리는 $p=0$에서 명확한 복잡성 이분법을 제시합니다. 즉, $p$가 0과 1 사이의 고정된 값일 때, EFX가 전역적인 $p$-mean 최적값을 달성할 수 있는지 결정하는 문제, 그리고 $p$-mean 복지를 최대화하는 EFX 할당을 계산하는 문제는 최대 3개의 잉여 상품이 있는 경우에도 NP-hard입니다. 반면, $p extless= 0$인 경우, EFX 할당 공간 내에서 $p$-mean 복지를 최적화하고 EFX가 전역 최적을 달성하는지 효율적으로 확인하는 다항 시간 알고리즘을 제시합니다. 또한, '공정성의 가격' 프레임워크를 사용하여 EFX를 강제함으로써 발생하는 복지 손실을 정량화합니다. $p > 0$인 경우, 손실은 에이전트 수에 따라 선형적으로 증가할 수 있지만, $p extless= 0$인 경우, 손실은 잉여 상품에 따라 결정되는 상수로 제한되며, 내쉬 복지의 경우 무한대로 감소합니다. 마지막으로, EFX와 함께 파레토 최적성을 요구하는 경우, 이 문제는 NP-hard이며, EFX의 더 강력한 변형에서는 $Σ_2^P$-complete이 됩니다. 전반적으로, 본 연구는 잉여 상품의 수가 적은 경우, EFX가 언제 계산 비용이 많이 드는지, 그리고 언제 복지 극대화와 구조적으로 일치하는지를 명확히 규명합니다.

Envy-freeness up to any good (EFX) is a central fairness notion for allocating indivisible goods, yet its existence is unresolved in general. In the setting with few surplus items, where the number of goods exceeds the number of agents by a small constant (at most three), EFX allocations are guaranteed to exist, shifting the focus from existence to efficiency and computation. We study how EFX interacts with generalized-mean ($p$-mean) welfare, which subsumes commonly-studied utilitarian ($p=1$), Nash ($p=0$), and egalitarian ($p \rightarrow -\infty$) objectives. We establish sharp complexity dichotomies at $p=0$: for any fixed $p \in (0,1]$, both deciding whether EFX can attain the global $p$-mean optimum and computing an EFX allocation maximizing $p$-mean welfare are NP-hard, even with at most three surplus goods; in contrast, for any fixed $p \leq 0$, we give polynomial-time algorithms that optimize $p$-mean welfare within the space of EFX allocations and efficiently certify when EFX attains the global optimum. We further quantify the welfare loss of enforcing EFX via the price of fairness framework, showing that for $p > 0$, the loss can grow linearly with the number of agents, whereas for $p \leq 0$, it is bounded by a constant depending on the surplus (and for Nash welfare it vanishes asymptotically). Finally we show that requiring Pareto-optimality alongside EFX is NP-hard (and becomes $Σ_2^P$-complete for a stronger variant of EFX). Overall, our results delineate when EFX is computationally costly versus structurally aligned with welfare maximization in the setting with few surplus items.