| paper | Fair and Efficient Allocations under Subadditive Valuations |
| authors | B. Chaudhury, J. Garg, R. Mehta |
| venue | AAAI 2021 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→other discrete result → its continuous mirror
Answer: The required allocation need not exist; the universal output guarantee is impossible. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
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.
A high-multiplicity fair-division model with finite valuation types carrying masses, integral course bundles as configurations, per-capita indivisible supplies, support-level EFX constraints, and \(p\)-mean welfare induced by \(\sum_{t,S}x_{t,S}v_t(S)^p\).
The support-sensitive EFX condition makes the continuous feasible region nonconvex and unstable when a supported mass tends to zero, so the proposed \(\tau\)-dependent guarantee and configuration-LP approach are not inherited from Theorem 1.
fatal: False
The mirror covers the main algorithmic approximation result for the \((1/2-\epsilon)\)-EFX branch across the \(p\)-mean family; it leaves the bounded-charity branch, the finite proof, and the weighted-welfare remark as separate questions.
The strongest positive case is anchored in Theorem 1, proved in this paper. The paper has no comparable hardness theorem of its own; its APX-hardness remarks concern cited work, so they cannot serve as anchors here. Theorem 12 is essentially the runtime restatement of Theorem 1, not an independent anchor.
Theorem 1 states that, given \(n\) agents, \(m\) indivisible goods, monotone normalized subadditive valuations, \(p\in(-\infty,1]\), and \(\epsilon>0\), a polynomial-time algorithm finds either:
\[ (1/2-\epsilon)\text{-EFX} \]
allocation \(X\) with
\[ M_p(X)\ge \frac{1-2\epsilon}{8(n+1)}M_p(X^\ast), \]
or a partial \((1-\epsilon)\)-EFX allocation with bounded charity, meaning fewer than \(n\) unallocated goods \(P\), \(v_i(X_i)\ge v_i(P)\) for every agent, and
\[ M_p(X)\ge \frac{1-\epsilon}{4(n+1)}M_p(X^\ast). \]
Here \(X^\ast\) maximizes \(p\)-mean welfare. The theorem covers Nash welfare at \(p=0\), max-min welfare at \(p=-\infty\), and social welfare at \(p=1\). Theorem 12 confirms polynomial running time in \(n,m,1/\epsilon\).
My lead mirror would be Continuous Type-EFX-\(p\)-Mean Allocation.
Consider a large university allocating seats in \(m\) courses to \(N\) students. Students fall into \(\tau\) valuation types, where a type is a complete subadditive valuation \(v_t:2^{[m]}\to\mathbb{Q}_{\ge0}\). Let \(\mu_t\) be the fraction of students of type \(t\), with \(\sum_t\mu_t=1\). Course \(g\) has a per-capita capacity \(\rho_g\in\mathbb{Q}_{\ge0}\): in an \(N\)-student realization there are \(N\rho_g\) indistinguishable copies of course \(g\). Each student still receives an integral course bundle \(S\subseteq[m]\); only the population is continuous.
The decision variable is
\[ x_{t,S}\ge0, \]
the mass of type-\(t\) students receiving integral bundle \(S\). It must satisfy
\[ \sum_{S\subseteq[m]}x_{t,S}=\mu_t \]
for every type \(t\), and
\[ \sum_{t,S:g\in S}x_{t,S}=\rho_g \]
for every course \(g\). A solution is a polynomial-size list of nonzero type–bundle masses, or an equivalent configuration-LP certificate.
The allocation is \(\alpha\)-EFX if, whenever \(x_{t,S}>0\) and \(x_{u,R}>0\),
\[ v_t(S)\ge \alpha\,v_t(R\setminus\{g\}) \]
for every \(g\in R\). Thus EFX remains a pointwise condition between integral bundles; it is not replaced by average envy or fractional utility.
Its welfare is the population \(p\)-mean
\[ M_p(x)=\left(\sum_{t,S}x_{t,S}v_t(S)^p\right)^{1/p} \]
for \(p\neq0\), with the usual logarithmic definition at \(p=0\) and minimum-support value at \(p=-\infty\). Let \(\mathrm{OPT}_p\) be the maximum of this quantity over all feasible allocations, without an EFX requirement.
The concrete problem is:
Given \(\mu\), \(\rho\), the \(\tau\) subadditive valuation types, \(p\), and \(\epsilon\), output a \((1/2-\epsilon)\)-EFX allocation \(x\) satisfying
\[ > M_p(x)\ge \frac{1-2\epsilon}{8(\tau+1)}\mathrm{OPT}_p, > \]
in time polynomial in \(m,\tau\), the encoding length, and \(1/\epsilon\).
The replacement of \(n\) by \(\tau\) is the natural high-multiplicity target: the original guarantee becomes useless as the number of cloned students tends to infinity, whereas the continuous problem should depend on the number of distinct valuation types. This is a proposed research target, not a claim already proved by the paper.
The regime is credible. A university may have millions of students but only dozens or hundreds of recurring course-demand profiles. The students sharing a type have identical preferences over course bundles; they are not being treated as interchangeable merely because they are unnamed. Course capacities scale with the population, which is the natural co-modification forced by population continuization. Every individual outcome remains integral.
This is a genuine high-multiplicity bridge. For rational \(\mu\), \(\rho\), and \(x\), choose \(N\) clearing their denominators. Then \(N\mu_t\) students of type \(t\), \(N\rho_g\) course seats, and \(Nx_{t,S}\) students assigned bundle \(S\) produce an ordinary discrete instance. Conversely, large finite instances with repeated valuation types yield empirical masses. Slack in \(\epsilon\)-EFX can absorb rounding errors when passing between the two representations.
I would expect this problem to be a tentative Class A candidate. The welfare objective becomes linear in the configuration masses for fixed \(p\) after applying the relevant transformation, while the resource constraints are linear. The paper’s high-value-good matching and EFX-completion ideas also look batchable by type: instead of processing millions of identical students, one would process mass flows between types and integral bundle configurations. Configuration LPs, column generation, and type-level matching are exactly the continuous-optimization tools the paper’s finite formulation does not exploit.
The serious technical question is pricing: with unrestricted subadditive valuations, finding useful bundle configurations may itself be difficult. Exact welfare maximization, stronger fairness guarantees, and the \(1-\epsilon\)-EFX bounded-charity variant may therefore retain hardness. But that is a meaningful boundary question about the same allocation problem, not a retreat to a different outcome-space model.
The weakest point is the proposed \(\tau\)-dependent guarantee. The proof of Theorem 1 uses \(n\) structurally—for example, the \(n\) highest-valued goods and the bound on singleton bundles—so replacing \(n\) by \(\tau\) is not automatic. Moreover, splitting one valuation type across several bundles makes EFX a support-sensitive, nonconvex condition. A type-level algorithm with polynomial support may require genuinely new ideas.
That weakness does not undermine the mirror itself. The continuous problem preserves the paper’s exact objects—subadditive valuations, indivisible bundles, EFX, and \(p\)-mean welfare—while asking whether its finite algorithm can be compressed to a high-multiplicity population. The theorem supplies a clear algorithmic anchor; the continuous analogue supplies a substantive new complexity question rather than merely renaming a finite allocation.
The strongest negative case is that Theorem 1 does not survive population compression in the form the proponent proposes. Its \(n\)-dependence is not merely a loose bound caused by naming agents. The proof uses \(n\) structurally: each agent receives one high-valued good, the matching has \(n\) slots, and the argument controls the number of singleton bundles. Those objects do not collapse to the number \(\tau\) of valuation types.
If goods remain the paper’s original one-copy indivisible goods, the continuum degenerates immediately. As the population grows, almost all mass must receive the empty bundle, so both welfare and EFX become uninformative. The proposed repair—giving each good a per-capita supply \(\rho_g\)—is natural in a university setting, but it is a substantive multi-unit extension. The original problem has one copy of each named good; the repaired model has \(N\rho_g\) copies and a new assumption that bundles contain at most one copy of each course. That may be a good research problem, but it is not a high-multiplicity limit of the finite instances used by Theorem 1 in any literal sense.
More seriously, exact EFX does not aggregate cleanly. The proposed condition is
\[ x_{t,S}>0,\ x_{u,R}>0 \quad\Longrightarrow\quad v_t(S)\ge \alpha v_t(R\setminus\{g\}) \]
for every \(g\in R\). Thus feasibility depends on the support of the allocation, not on its aggregate masses. A tiny positive mass assigned to a bundle has exactly the same fairness consequences as a mass close to one. Conversely, when that mass tends to zero, all of its EFX constraints disappear. This makes the continuous formulation discontinuous with respect to the high-multiplicity limit: one exceptional finite agent still creates EFX constraints, while a measure-zero exceptional population does not.
The same issue defeats the claim that this is naturally a configuration LP. The resource constraints are linear, and the transformed \(p\)-mean objective can be linearized for fixed \(p\), but EFX produces a union of support-dependent polytopes. If one type is split among many bundles, every supported bundle becomes a distinct fairness class. The effective object is therefore not \(\tau\) valuation types but pairs \((t,S)\), potentially exponentially many in \(m\). If one forbids such splitting and gives each type a single bundle, the result is easier to represent but is no longer the paper’s allocation problem and may be infeasible under the capacity constraints.
A mass-weighted or average version of EFX could restore convexity, but then it no longer mirrors the paper’s central fairness guarantee. It would ignore small minorities precisely where individual EFX is strongest. The obstacle is therefore not a technical issue about strict inequalities or tie-breaking; it is that the theorem’s main fairness property is intrinsically support- and individual-sensitive.
The proposed \(\tau\)-dependent guarantee is consequently not a transfer of Theorem 1. It is a new conjectural theorem about a different multi-unit model. The fact that type-level matching and configuration methods might solve it is evidence that the new problem could be interesting, but not evidence that this paper supplies a worthwhile continuous mirror.
That said, the universal negative case is weak. A cleaned-up version with per-capita supplies, integral bundles, and pointwise EFX is mathematically coherent and has a plausible repeated-course or repeated-demand interpretation. The paper contains a genuine named algorithmic result, not merely axioms or distortion bounds. So I can defeat the submitted mirror as a faithful compression of Theorem 1, but I cannot honestly establish that no worthwhile continuous-population problem can be built from it. On the programme’s rules, the proponent’s anchor probably survives in that broader form.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.