Fair and Efficient Allocations under Subadditive Valuations (d4-conf-aaai-2021-0883)

Given \(\tau\) monotone normalized subadditive valuation types \(v_t:2^{[m]}\to\mathbb{Q}_{\ge 0}\), rational type masses \(\mu_t\) with \(\sum_t\mu_t=1\), rational per-capita supplies \(\rho_g\), \(p\in(-\infty,1]\), and \(\epsilon>0\), compute a polynomial-support allocation of masses \(x_{t,S}\ge 0\) of type-\(t\) agents receiving integral bundles \(S\subseteq[m]\), satisfying \(\sum_Sx_{t,S}=\mu_t\) and \(\sum_{t,S:g\in S}x_{t,S}=\rho_g\). Require \(v_t(S)\ge(1/2-\epsilon)v_t(R\setminus\{g\})\) whenever \(x_{t,S}>0\), \(x_{u,R}>0\), and \(g\in R\); achieve \(M_p(x)\ge\frac{1-2\epsilon}{8(\tau+1)}\operatorname{OPT}_p\), with the standard \(p=0\) and \(p=-\infty\) interpretations.

There are \(\tau\) types with rational masses \(\mu_t\) summing to \(1\). Type \(t\) has a monotone, normalized, subadditive valuation \(v_t:2^{[m]}\to\mathbb Q_{\ge0}\), accessed by value oracle. Each good \(g\) has rational per-capita supply \(\rho_g\).
An allocation assigns mass \(x_{t,S}\ge0\) to each type–bundle pair, with \(\sum_Sx_{t,S}=\mu_t\) and \(\sum_{t,S:g\in S}x_{t,S}=\rho_g\). Its support consists of pairs with \(x_{t,S}>0\).
For \(p\ne0,-\infty\), let \(M_p(x)=(\sum_{t,S}x_{t,S}v_t(S)^p)^{1/p}\); use the weighted geometric mean for \(p=0\) and the minimum value on the support for \(p=-\infty\), with welfare zero if positive mass receives value zero. Let \(\operatorname{OPT}_p\) maximize \(M_p\) over feasible allocations.
Given rational \(\epsilon>0\) and rational \(p\le1\) or \(p=-\infty\), the requested output has polynomial support, satisfies \(v_t(S)\ge(1/2-\epsilon)v_t(R\setminus\{g\})\) for every supported \((t,S),(u,R)\) and \(g\in R\), and achieves \(M_p(x)\ge\frac{1-2\epsilon}{8(\tau+1)}\operatorname{OPT}_p\).
Is this continuous allocation problem solvable in polynomial time, or is it NP-hard?
For \(n\) discrete agents, a polynomial-time algorithm finds a complete \((1/2-\epsilon)\)-EFX allocation with \(p\)-mean welfare at least \(\frac{1-2\epsilon}{8(n+1)}\) times optimum. That guarantee does not address type masses or prescribed per-capita supplies.

The required allocation need not exist, even for one type with an additive valuation. Thus no algorithm can satisfy the requested guarantee on every stated input, regardless of running time.

Take \(\tau=1\), \(\mu_1=1\), two goods \(\{a,b\}\), and parameters
\[ \rho_a=1,\qquad \rho_b=\frac12,\qquad \epsilon=\frac14,\qquad p=1. \]
Define
\[ v(S)=\mathbf 1_{\{a\in S\}}+8\mathbf 1_{\{b\in S\}}. \]
This valuation is rational, nonnegative, normalized, and monotone. It is subadditive because, for all bundles \(A,B\),
\[ v(A)+v(B)=v(A\cup B)+v(A\cap B)\ge v(A\cup B). \]

Write \(x_S=x_{1,S}\). The total-mass and supply constraints for good \(a\) give
\[ \sum_{S\subseteq\{a,b\}}x_S=1, \qquad \sum_{S:a\in S}x_S=1. \]
Subtracting shows that \(\sum_{S:a\notin S}x_S=0\). Nonnegativity therefore forces
\[ x_{\varnothing}=x_{\{b\}}=0. \]
The supply constraint for good \(b\) then forces \(x_{\{a,b\}}=\frac12\), and the total-mass constraint forces \(x_{\{a\}}=\frac12\). Consequently, the unique feasible allocation has support
\[ \bigl\{(1,\{a\}),(1,\{a,b\})\bigr\}. \]

Apply the requested fairness inequality to the supported bundles \(S=\{a\}\), \(R=\{a,b\}\), and the good \(g=a\). It requires
\[ 1=v(\{a\}) \ge \left(\frac12-\frac14\right)v(\{b\}) =\frac14\cdot8 =2, \]
which is false.

The supply constraints themselves are feasible, and the unique feasible allocation has welfare
\[ \operatorname{OPT}_1=\frac12\cdot1+\frac12\cdot9=5. \]
Thus the obstruction is specifically the fairness requirement, independently of the welfare approximation or polynomial-support condition.

This settles the stated universal output requirement by counterexample. It does not establish NP-hardness of a separate feasibility decision problem or of a search problem restricted to instances admitting the required output. Such a restriction would change the question.

⟨structured verdict parsed — rendered above⟩

The prover’s counterexample is correct and resolves the universal output requirement: an admissible instance has a feasible allocation, but no feasible allocation satisfies the required fairness condition. This establishes nonexistence on some inputs, rather than a polynomial-time algorithm or an NP-hardness result.

• The instance meets all input assumptions. There is one type with rational mass \(\mu_1=1\). Both supplies are rational and lie in \([0,1]\). The parameters \(\epsilon=\frac14>0\) and \(p=1\) are permitted. The valuation assigns nonnegative rational weights \(1\) and \(8\) to the two goods, so it is normalized and monotone. The displayed identity proving subadditivity is valid for this additive valuation. Its values can also be supplied by a value oracle.

• The feasible allocation is uniquely determined. Subtracting the supply equation for \(a\) from the total-mass equation gives

\(\sum_{S:a\notin S}x_S=0\).
Nonnegativity forces both \(x_{\varnothing}=0\) and \(x_{\{b\}}=0\). The supply equation for \(b\) therefore gives \(x_{\{a,b\}}=\frac12\), and total mass gives \(x_{\{a\}}=\frac12\). These masses satisfy every constraint, proving both feasibility and uniqueness. Both identified support pairs have strictly positive mass.

• The fairness violation uses exactly the required quantifiers. The requirement applies to every pair of supported type–bundle pairs, including two distinct bundles belonging to the same type. Thus \(S=\{a\}\) and \(R=\{a,b\}\) are valid choices. The selected good \(g=a\) belongs to \(R\); the task does not require \(g\) to lie outside \(S\). The resulting inequality is \(1\ge\frac14\cdot8=2\), which is false. Since the feasible allocation is unique, no feasible fair allocation exists.

• The welfare calculation is correct. At \(p=1\), welfare is the weighted arithmetic mean. The unique feasible allocation has welfare \(\frac12\cdot1+\frac12\cdot9=5\), so \(\operatorname{OPT}_1=5\). Its support has size two. Consequently, neither welfare maximization nor support size causes the failure; fairness alone makes the requested output impossible.

• The conclusion has the appropriate scope. One admissible counterexample suffices to disprove an algorithmic guarantee asserted for every stated input. The prover correctly avoids inferring NP-hardness from nonexistence. A complexity classification for a modified feasibility problem or a restricted search problem would require a separate argument.

No unjustified steps, missing hypotheses, computational errors, or substantive ambiguities were found. No additional clarification is needed.

⟨structured verdict parsed — rendered above⟩