| paper | (Almost Full) EFX for Three (and More) Types of Agents |
| authors | Pratik Ghosal, Vishwa Prakash HV, Prajakta Nimbhorkar, Nithin Varma |
| venue | AAAI 2025 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper’s numbered contributions are existence theorems and contain no qualifying computational result. Mass-EFX is a coherent high-multiplicity extension of Theorem 1, but it is a newly posed computational problem rather than a mirror of a computational result from the paper. Therefore bit (a) fails and the grade is red.
fails bit a — no named computational result to mirror
Support-wise EFX is discontinuous when configurations lose all mass, and the normalized k−2 waste guarantee becomes asymptotically vacuous; these limit fidelity but do not make the high-multiplicity question incoherent.
fatal: False
The proposed mirror covers Theorem 1’s k-valuation-type regime; Corollary 1 is only a special case, while Theorem 2’s two-outlier result and auxiliary existence lemmas are not covered.
Under ChoCo’s strict anchor rule, this paper has no qualifying computational anchor. Its named results are existence theorems, not results saying that a problem is in P, NP-hard, FPT, or otherwise computationally classified:
The paper calls its proofs constructive, but gives no polynomial-time bound for the overall procedures. It would therefore be wrong to present Theorem 1 or Theorem 2 as an “in P” result. The strongest positive case is consequently a proposed extension around Theorem 1, not a source-anchored computational verdict.
My lead question would be Mass-EFX for replicated indivisible goods with \(k\) valuation types.
Take \(k\) additive valuation types \(t\in[k]\), with rational population masses \(\mu_t\) summing to one. Let there be finitely many good kinds \(j\in[r]\), with rational per-capita supplies \(q_j\); physically, these are many repeated indivisible copies of each good kind. Type \(t\) values one copy of kind \(j\) at \(w_{tj}\), so an indivisible bundle \(b\in\mathbb Z_{\ge0}^r\) has value
\[ v_t(b)=\sum_j w_{tj}b_j. \]
A solution is a mass allocation \(x_{t,b}\ge0\), where \(x_{t,b}\) is the fraction of type \(t\) receiving the whole bundle \(b\). Thus
\[ \sum_b x_{t,b}=\mu_t,\qquad \sum_{t,b} b_jx_{t,b}\le q_j. \]
The individual bundle remains indivisible; \(x\) is fractional only because it describes many clones.
The allocation is EFX if, whenever \(x_{t,b}>0\) and \(x_{t',b'}>0\),
\[ v_t(b)\ge v_t(b'-e_j) \]
for every good kind \(j\) occurring in \(b'\). Let \(u\) be the residual supply. The optimization version minimizes \(\sum_j u_j\), optionally subject to no supported agent type envying the residual bundle. The zero-waste limit asks whether the optimum is \(0\).
This is the high-multiplicity interpretation of Theorem 1: at scale \(N\), take \(N\mu_t\) agents and \(Nq_j\) indivisible copies. A rational mass allocation can be denominator-cleared into an ordinary allocation of clones. The theorem’s \(k-2\) leftover goods then becomes normalized waste at most \((k-2)/N\), which tends to zero. The direct analogue is therefore complete EFX in the replicated, atomless limit, with the finite-scale \(k-2\) bound as its quantitative approximation.
A plausible scenario is a large annual cohort of workers or households receiving repeated packages of indivisible equipment, office modules, housing slots, or computing resources. A small number of standardized roles produces \(k\) valuation types, while the number of agents and resource copies is large. This is much more convincing than applying the mirror to a seven-person committee: the paper itself already organizes its proof around groups of agents with identical valuations, leading agents, and the number \(k\) of types.
I would expect the bounded replicated-good regime to be a Class-A candidate: with fixed \(k\), fixed good kinds, and an explicit bounded configuration set, the mass formulation becomes a finite configuration-feasibility or optimization problem. Removing the configuration bound is the real research question; its pricing problem may be hard because it still contains bundle-selection and partition structure. That hardness could transfer from the indivisible allocation problem rather than arise from population continuity.
Theorem 2 is a weaker possible extension. Replacing the two named outliers by two positive-mass outlier types changes the statement substantially: the theorem proves a result for exactly two outlier agents, not for arbitrarily many agents of two outlier types. Retaining two literal outlier atoms alongside a continuous majority would be a mixed discrete–continuous model, not the programme’s clean population distribution. I would not use it as a second anchor.
The weakest point is fundamental: EFX is about individual bundles and the effect of removing one particular good. If one simply replaces bundles by fractional allocations or checks only average utilities, the result becomes a different divisible-goods problem and leaves the paper’s question. If goods are not scaled with the population, a continuous population is also impossible or vacuous. The proposed mirror survives only by using many repeated indivisible goods and treating mass as a distribution over whole-bundle assignments.
So the honest conclusion is: this paper supplies a very natural high-multiplicity *subject* for ChoCo—especially Theorem 1’s \(k\)-valuation-type regime—but no named computational result to anchor a formal positive verdict. The appropriate follow-up is to turn Mass-EFX into a genuine complexity question and determine whether its configuration/pricing problem is tractable, discrete-hard, or continuum-specifically hard.
The negative case is decisive at the programme’s first gate: this paper has no qualifying computational anchor. Theorem 1, Corollary 1, and Theorem 2 are existence statements. Calling the proofs “constructive” does not make them polynomial-time algorithms: termination is obtained from finiteness or a strictly increasing potential, with no complexity bound, input encoding, or valuation-access model. The MMS-feasible and nice-cancelable cases are not even given a computational representation. Thus there is no named complexity, approximation, query, or parameterized result here to continuize.
The proposed Mass-EFX problem is consequently a newly invented problem, not a continuous version of a computational result in the paper. It adds repeated good kinds, per-capita supplies, a distribution over whole-bundle configurations, residual-waste minimization, and a zero-waste objective. Those may define an interesting fair-division project, but inspiration from Theorem 1 is not an anchor under ChoCo’s rule.
The rational-clone argument also exposes a degeneracy. At scale \(N\), Theorem 1 already gives at most \(k-2\) unallocated goods. After normalizing resources by \(N\), the residual is at most \((k-2)/N\), hence tends automatically to zero. The proposed zero-waste limit therefore captures only the disappearance of a finite additive remainder. If one retains the unnormalized number of leftover goods, that quantity has no continuous limit. Either way, the paper’s actual quantitative content is lost rather than transformed into a new computational question.
More seriously, exact EFX is not naturally a property of an atomless allocation measure. EFX quantifies over every agent, every other agent’s bundle, and every good in that bundle. A cohort of mass \(\varepsilon\) can invalidate EFX just as decisively as a cohort of mass \(1/2\). As \(\varepsilon\to0\), that cohort disappears from the limiting measure. “EFX almost everywhere” therefore changes the fairness notion; retaining the proponent’s support-wise condition \(x_{t,b}>0\) makes feasibility depend discontinuously on whether a configuration has any mass at all. Keeping named agents to preserve exact EFX gives a mixed individual/continuum model, not a population represented by types and masses.
The proponent’s support-wise configuration formulation is the strongest repair, and it is mathematically coherent. But then all the fairness content remains in a finite-support combinatorial configuration problem; population mass merely balances resource capacity. Bounding the configuration set makes the model an additional restricted clone-commodity problem. Removing the bound introduces a new bundle-selection or pricing problem that the paper neither states nor analyzes. Neither version is a computational mirror of the paper’s results.
Theorem 2 cannot provide a second anchor. It concerns exactly two literal outlier agents. Giving two outlier valuation types positive mass creates arbitrarily many outliers and a genuinely different three-type EFX problem. Keeping two exceptional agents as measure-zero atoms yields a hybrid model; ignoring them under almost-everywhere semantics destroys the theorem’s exceptional-agent structure. The proponent’s own refusal to use Theorem 2 is therefore correct.
There is a credible high-multiplicity story for fair division—large cohorts receiving repeated standardized equipment or resource packages—and I would not reject it merely because agents share valuation types. A separate Mass-EFX paper could be worthwhile. But that concession does not rescue this paper for ChoCo: its named contributions are noncomputational, its proposed mirror changes the problem and invents the objective, and its most natural continuous limit erases the only quantitative guarantee. I would therefore reject it as a worthwhile continuous mirror of this paper.
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.