| paper | Computing Efficient Envy-Free Partial Allocations of Indivisible Goods |
| authors | — |
| venue | AAMAS 2025 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 4.1
statement extracted from the paper’s text layer
Given a finite type set \(\Theta\) with rational masses \(\mu_\theta\), a finite catalogue \(R\) with rational per-capita supplies \(q_r\) of indivisible copies, binary liked sets \(L_\theta\), and \(t\in\mathbb{N}\), decide whether there exist \(x_{\theta r}\ge0\) such that \(x_{\theta r}=0\) for \(r\notin L_\theta\), \(\sum_{r\in L_\theta}x_{\theta r}=t\mu_\theta\) for every \(\theta\), and \(\sum_\theta x_{\theta r}\le q_r\) for every \(r\); equivalently, does an envy-free mass allocation of whole bundles exist in which every agent receives utility at least \(t\)?
Types are complete binary liked-resource sets with masses \(\mu_\theta\); decision variables \(x_{\theta r}\) represent mass receiving indivisible copies, supplies are \(q_r\), and the objective is feasibility at egalitarian threshold \(t\).
The mirror scales resource-copy supplies \(q_r\) with the population, so it is not a population-only limit of the paper's fixed-inventory instances; the finite denominator-clearing bridge also lacks explicit size and bit-complexity bounds.
fatal: False
The mirror covers only Theorem 4.1's \(0/1\)-utility egalitarian result; it leaves the utilitarian, size, min-cardinality, identical-utility, and ternary-utility results untreated.
The strongest honest case is a Class A mirror of the paper’s binary-utility egalitarian result. I would make this the lead.
The anchor is Theorem 4.1, proved in this paper: “For \(0/1\)-utilities esw-EF-PA is solvable in \(O(m^{2.5})\) time.” I am not claiming that theorem is cited from elsewhere; its matching reduction is proved here.
The natural regime is a large cohort of students, employees, or residents competing for many indivisible copies of a finite catalogue of goods: course seats, licenses, laptops, or placements. An agent type \(\theta\) is its complete \(\{0,1\}\)-utility vector over the catalogue: equivalently, its liked-resource set \(L_\theta\). The population is represented by rational masses \(\mu_\theta\), with \(\sum_\theta\mu_\theta=1\), where \(\tau=|\Theta|\) is small compared with the number \(N\) of agents. Resource \(r\) has a rational supply density \(q_r\), meaning that a finite expansion with scale \(N\) contains \(Nq_r\) distinct copies of \(r\). Thus the goods remain indivisible; only the population and repeated-copy counts are represented compactly.
I would call the problem \(\mathrm{ESW\text{-}EF\text{-}PA}_\infty\). Its input is
\[ (\Theta,\mu,R,q,(L_\theta)_{\theta\in\Theta},t), \]
where \(t\in\mathbb N\). A solution is a census \(z_{\theta,B}\) assigning mass of type \(\theta\) to whole indivisible bundles \(B\), satisfying
\[ \sum_B z_{\theta,B}=\mu_\theta \]
for every type, and
\[ \sum_{\theta,B} b_r(B)z_{\theta,B}\le q_r \]
for every resource \(r\), where \(b_r(B)\) is the number of copies of \(r\) in \(B\). It must be envy-free in the exact type-level sense: whenever \(z_{\theta,B}>0\) and \(z_{\theta',B'}>0\),
\[ u_\theta(B)\ge u_\theta(B'). \]
The question is whether there is such an allocation with
\[ \operatorname{esw}_\infty(z) =\inf_{\theta,B:z_{\theta,B}>0}u_\theta(B)\ge t. \]
This is recognisably the paper’s esw-EF-PA question: partial allocation is allowed, utilities are additive, goods are indivisible, and every agent must reach the same egalitarian threshold.
For \(\{0,1\}\)-utilities, the problem has a particularly clean normal form. If every agent gets utility at least \(t\), trim each bundle to exactly \(t\) liked copies. The resulting allocation remains envy-free, because every agent values its own bundle at \(t\), while every other bundle contains exactly \(t\) goods and therefore has value at most \(t\). Consequently the continuous problem is equivalent to the following capacitated flow problem:
\[ \sum_{r\in L_\theta}x_{\theta r}=t\mu_\theta \qquad\text{for every }\theta, \]
\[ \sum_{\theta}x_{\theta r}\le q_r \qquad\text{for every }r, \]
with \(x_{\theta r}\ge0\) and \(x_{\theta r}=0\) whenever \(r\notin L_\theta\).
A feasible \(x\) is a solution: it records the mass of type-\(\theta\) agents receiving copies of resource \(r\). It can be decomposed into a distribution over whole \(t\)-copy bundles, and clearing denominators produces an ordinary finite allocation. Conversely, every finite high-multiplicity allocation normalizes to such an \(x\). Hence this has the required two-way bridge, not merely an analogy.
The algorithm is a maximum-flow computation on \(\tau\) type nodes and \(m\) resource nodes, with demand \(t\mu_\theta\) and capacities \(q_r\). It is polynomial in \(\tau\), \(m\), and the encoding length of the rational data. I therefore expect \(\mathrm{ESW\text{-}EF\text{-}PA}_\infty\) to be Class A. The continuous formulation gives the authors’ matching insight in the regime where millions of agents share a small number of utility types; it does not need to enumerate those agents individually.
The mirror is an extension rather than a literal fixed-inventory limit. To keep a positive per-agent threshold as the population grows, goods must scale with the population. Holding a finite set of goods fixed would make the egalitarian requirement vacuous or impossible. This is the weakest point. The defence is that the resource copies remain atoms in every finite realization: \(z_{\theta,B}\) is a census of whole bundles, not a fractional good assigned to a fractional agent. The additional assumption is specifically a repeated-indivisible-goods regime, which is a sensible high-multiplicity scenario for the paper’s allocation problem.
I would not stretch this case to Theorem 5.2. Its ternary-utility hardness gadgets may not survive type aggregation without a separate proof, and claiming that they do would confuse a plausible mirror with an established hardness transfer. The present case covers only Theorem 4.1, but it covers that result exactly and concretely. The natural follow-up questions are whether the same flow/configuration method survives ternary utilities, whether other efficiency measures admit compact type-level formulations, and what rounding guarantees hold when the rational masses are expanded to a finite cohort.
The strongest negative case is a scope objection to Theorem 4.1. It is the only genuine computational anchor raised.
The theorem concerns \(n\) agents competing for a fixed set of \(m\) indivisible resources, with every agent required to obtain utility at least \(t\). If only the population is continuized while the resource set remains fixed, then for binary utilities and \(t\ge1\), every agent needs at least \(t\) distinct resources. Thus any feasible allocation satisfies
\[ nt\le m. \]
As \(n\) grows, the egalitarian requirement becomes impossible; setting \(t=0\) makes the empty allocation trivially feasible. Renormalizing utilities does not repair this: a positive threshold still requires every agent to receive a liked resource. Replacing the minimum by an aggregate or positive-mass requirement would be a different problem.
The proponent’s \(q_r\)-repair avoids this collapse only by introducing a second high-multiplicity axis: resources themselves are replicated in per-capita supply. That is no longer merely a continuous population version of the paper’s fixed-inventory problem; it is a new repeated-indivisible-goods model. The flow formulation also forgets the original resource identities and replaces the allocation problem by capacitated transportation. Finally, denominator clearing establishes finite realizability only existentially: a rational mass solution may require exponentially many cloned agents and goods, so a genuine finite-instance bridge needs support and bit-complexity bounds.
Those objections are real, but they do not defeat the best version of the mirror. Repeated course seats, licences, laptops, or placement slots are a plausible high-multiplicity regime. Agents with the same liked-resource set are complete interchangeable types, and the goods remain indivisible copies rather than fractional goods. For binary utilities, trimming every bundle to \(t\) liked copies makes envy-freeness equivalent to
\[ \sum_{r\in L_\theta}x_{\theta r}=t\mu_\theta, \qquad \sum_\theta x_{\theta r}\le q_r, \qquad x_{\theta r}\ge0, \]
which is an exact capacitated-flow formulation. Integral flow after denominator expansion supplies the finite clone correspondence.
So the honest negative conclusion is narrow: under a strict population-only, fixed-resource interpretation, Theorem 4.1 degenerates. But once the natural repeated-inventory regime is admitted, the anchor survives. I cannot defend the universal claim that no worthwhile mirror exists; the proponent’s repaired Class A formulation is author-recognizable and computationally meaningful.
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.