| paper | Computing Envy-Freeable Allocations with Limited Subsidies |
| authors | I. Caragiannis, S. Ioannidis |
| venue | WINE 2021 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-hard}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 6
statement extracted from the paper’s text layer
Given finite item types \(G\), valuation types \(\Theta\), rational masses \(\mu\) with \(\sum_{\theta}\mu_\theta=1\), rational per-capita supplies \(\beta_g\), and additive valuations \(v_\theta\), compute nonnegative masses \(\lambda_{\theta,B}\) for integral bundles \(B\subseteq G\) satisfying \(\sum_B\lambda_{\theta,B}=\mu_\theta\) and \(\sum_{\theta,B:g\in B}\lambda_{\theta,B}=\beta_g\), together with subsidies \(p_{\theta,B}\ge0\) satisfying \(v_\theta(B)+p_{\theta,B}\ge v_{\theta'}(B')+p_{\theta',B'}\) for all occupied pairs, minimizing \(\chi_\infty=\sum_{\theta,B}\lambda_{\theta,B}p_{\theta,B}\); in particular, determine whether one can distinguish \(\chi_\infty\le a\) from \(\chi_\infty\ge a+3\cdot10^{-4}V\), where \(V=\sum_\theta\mu_\theta v_\theta(G)\).
A high-multiplicity SMEF model with finite valuation types \(\Theta\), item types \(G\), rational society masses \(\mu\), and per-capita supplies \(\beta\); individuals receive integral bundles, while \(\lambda_{\theta,B}\) records population mass and \(p_{\theta,B}\) records subsidies, with objective \(\chi_\infty=\sum_{\theta,B}\lambda_{\theta,B}p_{\theta,B}\).
The MAX-3DM-2 gap may be driven by a growing catalogue of gadget-specific valuation and item types rather than by population multiplicity, so the prediction that fixed-type mass splitting yields Class \(A\) remains unproved.
fatal: False
The mirror directly covers Theorem 6 and its approximation-gap question. It leaves Theorem 5's constant-agent dynamic-programming guarantee and the paper's intermediate structural lemmas without a faithful continuous counterpart.
The strongest positive case is a high-multiplicity version of SMEF itself, with indivisible bundles preserved at the individual level.
Let \(G=\{g_1,\ldots,g_m\}\) be item types and let \(\Theta\) be a finite set of complete valuation types. A type \(\theta\) is an additive valuation vector \(v_\theta:G\to\mathbb Q_{\ge 0}\). The society is a mass distribution \(\mu\in\mathbb Q_{\ge0}^{\Theta}\), with \(\sum_\theta\mu_\theta=1\). Item supplies are also scaled per capita: \(\beta_g\) is the number of copies of item type \(g\) per unit population.
The crucial point is that individual bundles remain integral. A bundle is \(B\subseteq G\), not a fractional bundle. The variable
\[ \lambda_{\theta,B} \]
is the mass of type-\(\theta\) agents receiving \(B\). Thus
\[ \sum_B\lambda_{\theta,B}=\mu_\theta \]
and
\[ \sum_{\theta,B:g\in B}\lambda_{\theta,B}=\beta_g. \]
For every occupied pair \((\theta,B)\), let \(p_{\theta,B}\ge0\) be the subsidy paid to those agents. Envy-freeness requires
\[ v_\theta(B)+p_{\theta,B} \ge v_\theta(B')+p_{\theta',B'} \]
whenever both \((\theta,B)\) and \((\theta',B')\) have positive mass. The objective is
\[ \sum_{\theta,B}\lambda_{\theta,B}p_{\theta,B}. \]
Call the optimum \(\chi_\infty\). This is not continuity of the outcome space: every individual receives an integral bundle, while \(\lambda\) records only the population proportions receiving each bundle.
This is a credible high-multiplicity regime. Think of a national-scale allocation of standardized benefit packages or household goods. There may be millions of agents but only a small number \(\tau=|\Theta|\) of valuation profiles, because profiles encode all relevant preferences and economic parameters. Item supplies scale with population, so a finite realization has \(N\mu_\theta\) agents of type \(\theta\) and \(N\beta_g\) copies of item \(g\). For rational data, finite allocations and mass allocations translate into one another after taking a sufficiently large common denominator; total subsidies scale by \(N\). Thus this is a genuine high-multiplicity relaxation rather than an unrelated fractional-allocation problem.
My lead anchor is Theorem 6, proved in this paper. It states that approximating SMEF within an additive term \(3\cdot10^{-4}\sumv{v}\) is NP-hard, where \(\sumv{v}=\sum_i v_i(M)\). The number of agents is part of the input, and the hardness is stronger than the basic NP-hardness of exact SMEF.
The proof reduces from MAX-3DM-2, where every element occurs in exactly two triples. If \(L\) is the maximum matching size and \(K\) is the threshold in the gap instance, the constructed SMEF instance has optimum subsidy
\[ \chi\bigl(1+\max\{K-L,0\}\bigr) \]
in the \(\chi>0\) construction. The reduction ensures \(\sumv{v}<30n\chi\), while the MAX-3DM gap gives a subsidy gap of at least \(0.01n\chi\), yielding the stated additive inapproximability. The paper also gives a \(\chi=0\) modification whose optimum is \(\max\{K-L,0\}\). The theorem is proved here, although it uses the external MAX-3DM-2 gap of \(\mathrm{CC06}\).
The corresponding continuous question is:
\[ \text{$\mathrm{C\text{-}SMEF}_{\mathrm{gap}}$:} \]
Given \((G,\Theta,\mu,\beta,v)\), compute an integral-bundle mass allocation \(\lambda\) and nonnegative subsidies \(p\) satisfying the supply and envy-freeness constraints, minimizing total subsidy. In particular, determine whether one can distinguish
\[ \chi_\infty\le a \qquad\text{from}\qquad \chi_\infty\ge a+3\cdot10^{-4}V, \]
where
\[ V=\sum_{\theta}\mu_\theta v_\theta(G) \]
is the per-capita analogue of \(\sumv{v}\).
This is recognizably the authors’ problem: the valuation model, indivisible bundles, envy-freeness with nonnegative subsidies, and minimum total subsidy are unchanged. Only named agents have been replaced by masses of indistinguishable valuation types, and item supplies have been replicated so that the limit is meaningful.
I expect the MAX-3DM hardness gap to dissolve in the intended fixed-\(\tau\) high-multiplicity regime, at least approximately. The discrete reduction uses a different triplet-specific agent type and a carefully linked collection of unique items for essentially every gadget. Once those agents and items are replicated, the continuum can mix masses among configurations, potentially converting the integral matching structure into a configuration LP or a fractional matching problem. That would make this a Class A problem in the low-type regime. If \(\tau\) is allowed to grow with the triplet structure, hardness may survive; that would be hardness transfer or a boundary result, not evidence that the continuous mirror is illegitimate.
A secondary anchor is Theorem 5, also proved here. It says that, for a constant number \(n\) of agents, the paper’s algorithm runs in time
\[ \bigO\!\left((m/\epsilon)^{n^2+2}\right) \]
and returns an envy-freeable allocation using at most
\[ \chi+\epsilon\max v \]
in total subsidies, where \(\chi\) is the optimum and \(\max v=\max_i v_i(M)\). The proof discretizes valuations, classifies allocations by valuation signatures, uses dynamic programming to find representatives, and then solves the subsidy LP.
Its continuous analogue is the bounded-type problem
\[ \text{$\mathrm{C\text{-}SMEF}_{\mathrm{PTAS}}$:} \]
Given a fixed number \(\tau\) of valuation types, rational \(\mu\) and \(\beta\), and \(\epsilon>0\), output an integral-bundle mass allocation and subsidies with total cost at most
\[ \chi_\infty+\epsilon V_{\max}, \qquad V_{\max}=\max_{\theta\in\Theta}v_\theta(G). \]
The expected direction here is tractability. The paper’s valuation-signature dynamic program suggests a configuration formulation in which the \(\lambda_{\theta,B}\) variables are handled by column generation or separation. With \(\tau\) fixed, the relevant value profiles have bounded dimension, and the continuous model exposes precisely the optimization machinery—configuration LPs, convex relaxations, and approximation schemes—that the discrete presentation obscures. Exact optimization may still depend on a nontrivial pricing problem, so a continuum-specific hardness result remains possible when item types or valuation dimensions grow.
The weakest point is that neither theorem itself is a high-multiplicity theorem. Theorem 6’s reduction has many distinct valuation types tied to unique gadget items, while Theorem 5 concerns a constant number of named agents rather than a large repeated population. Consequently, I cannot honestly claim that the paper already contains the continuous result, or that its hardness gap automatically transfers. What the paper supplies is the right underlying optimization problem and two sharply contrasting computational anchors. The proposed mirror asks whether the hardness is caused by population multiplicity—or instead by the item-and-type combinatorics that survive continuization. That is exactly the computational question the programme is meant to expose.
The best negative case is that Theorem 5 does not actually support the proposed mirror. Its parameter \(n\) is the number of named agents, held constant—not the number of repeated valuation types. The dynamic program tracks an \(n\times n\) matrix of values of particular agents for particular bundles. Replacing those agents by masses produces a configuration-allocation problem with variables \(\lambda_{\theta,B}\), not a continuous version of the theorem’s algorithm. Conversely, merely duplicating the finitely many agents makes the optimum and subsidy total scale predictably; it adds no substantive population question.
Theorem 6 is a stronger but still vulnerable anchor. Its reduction is built from one-off identities: every \(J_r(t)\) has a triplet-specific valuation pattern, and the \(A_i,B_i,\Gamma_i,\Delta_t,Z_t,\Theta_t\) items encode a particular MAX-3DM instance. If the item set is kept fixed while the population grows, almost all agents must receive empty bundles and the limit degenerates. If only agents are copied, the same scarce items remain the bottleneck. If the items are copied as well, the model has changed to a standardized-goods economy in which the matching gadget can be split across masses.
The only way to preserve the reduction’s combinatorics is to let the valuation and item-type spaces grow with the encoded MAX-3DM instance. Then the “continuum” merely repeats one-off gadget types with rational multiplicities; the hardness is not population-driven. That is a legitimate high-multiplicity encoding, but a weak mirror of the paper’s contribution: the continuous variable contributes compression of repeated copies, while the entire computational content remains in the growing catalogue of types and goods.
This does not, however, establish the requested universal negative. The repaired standardized-benefit-package model is genuinely natural, preserves integral individual bundles, and has an exact rational finite-realization interpretation. Its possible configuration-LP or pricing theory is a real computational question, even if it ultimately proves easy or hard. Thus Theorem 5 can be rejected as a faithful anchor, but Theorem 6 cannot honestly be defeated: the proponent’s continuous SMEF is a worthwhile mirror.
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.