| paper | d4-conf-atal-2021-0265 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper presents an executable EEF framework and empirical solver results, but contains no numbered Theorem, Lemma, Corollary, or Proposition stating a computational result. Its fixed-parameter and completeness claims are attributed to earlier work, and its own performance claims are empirical, so the proposed typed-population EEF problem is a plausible extension rather than a continuous analogue of a qualifying result in this paper.
fails bit a — no named computational result to mirror
The typed-population EEF question is plausible, but its computational complexity is a new question rather than a result established by this paper.
fatal: True
The proposed extension concerns EEF existence only; it leaves the paper's solver engineering, experiments, trading-cycle explanations, fairness relaxations, and social-welfare objectives outside the mirror.
I can’t honestly supply the requested theorem-anchored case: the supplied paper has no numbered Theorem, Lemma, Corollary, or Proposition of its own that classifies a problem as hard, tractable, or fixed-parameter tractable. Its \(\Sigma_2^P\)-completeness claim points to [11], and its FPT claim to [2]. The closest numbered statement is [2, Lemma 10(3)], which the paper cites: any allocation that is Pareto-dominated has a dominating allocation within an \(\ell_1\)-distance bounded by a computable function of the number of agents and maximum utility. That is a structural proximity result from earlier work, not a complexity classification proved here. The article’s own contributions are algorithm engineering and experiments.
There is still a credible positive case at the problem level. The strongest candidate is a continuous-population version of the paper’s central EEF–Allocation question. Call it Bounded-Bundle EEF–Allocation\(_\infty\). An instance gives a finite set \(J\) of item types, integer utilities \(u_a(j)\) for each of finitely many complete agent types \(a\in T\), rational masses \(\mu_a\) summing to \(1\), and rational per-capita supplies \(q_j\). It also gives a per-person cap \(h_j\) for each item type, so the allowed integral bundles are \(B=\prod_{j\in J}\{0,\ldots,h_j\}\). The question is whether there is an allocation, and the solution is a list of masses \(\lambda_{a,b}\ge0\): the mass of type \(a\) receiving bundle \(b\). Require \(\sum_b\lambda_{a,b}=\mu_a\) and \(\sum_{a,b}\lambda_{a,b}b_j\le q_j\).
The allocation is envy-free when, for every type \(a\), every bundle \(b\) receiving positive mass of type \(a\), and every bundle \(b'\) receiving positive mass in the society, \(u_a\cdot b\ge u_a\cdot b'\). It is Pareto-efficient when there is no reassignment of the same population within the bundle caps that weakly improves every person’s utility and strictly improves a positive mass. Since there are finitely many types and bundles, this can be checked by a finite coupling \(\pi_{a,b,b'}\) between each type’s current and replacement bundles: it must preserve the current mass at each \(b\), use at most \(q_j\) units of each item per capita, and only pair \(b\) with \(b'\) when \(u_a\cdot b'\ge u_a\cdot b\). A positive mass of strictly improving pairs would witness a Pareto improvement. The task is to return such a \(\lambda\), or report that none exists.
A plausible regime is a large workforce or public programme distributing standardized, indivisible benefits. Millions of people may share a modest number \(\tau\) of complete utility types, with inventory scaling in proportion to population; entitlement rules can impose the per-person caps. Here \(N\) can be very large while \(\tau\) and the number of item types stay moderate. This keeps the paper’s additive utilities, envy-freeness, Pareto efficiency, and integral individual bundles, while making the population the continuous object. The paper’s central question is therefore recognizable to its authors, though their own high-multiplicity setting scales the goods and keeps the agent set small. Their cited work on few agent types in fair allocation [15] is useful evidence that this population regime is a sensible one.
My tentative expectation is Class C, continuum-specifically hard: continuous masses may remove some indivisibility tied to the number of agents, but selecting bundle supports and ruling out Pareto improvements still couple the item types and utility types. That is a conjectural starting point, not a result of this paper. The next questions are whether fixed \(\tau\), bounded utilities, or a pricing formulation make the problem tractable; and whether discrete EEF instances admit a meaningful limit or approximation relationship to this mass model.
The weak point is substantial: this is not an anchor-backed claim, and the per-person caps narrow the original allocation problem. They fit settings with entitlement limits, but the paper does not impose them. So this is the strongest honest mirror I see in the paper’s problem setting, but it cannot satisfy the requested numbered-result requirement. It covers only EEF existence, not the paper’s trading-cycle explanations, social-welfare objectives, or fairness relaxations.
The strongest case against a mirror is that this article gives no theorem-level computational result of its own to continuize. Its \(\Sigma_2^P\)-completeness and fixed-parameter tractability claims are attributed to earlier work, [11] and [2]. This paper’s contributions are algorithm engineering, a flexible solver framework, and empirical findings on finite instances. The proposed Bounded-Bundle EEF–Allocation\(_\infty\) is a new problem-level direction; it is not a continuous version of a complexity result established here. The paper’s evidence is also tied to small Spliddit instances, with 3–15 agents and usually one copy of each item type.
That leaves a real gap in the negative case. A large allocation programme could have many people drawn from a modest set of complete utility types, with item supplies scaling per person. Each person could still receive an integral bundle, while the mass assigned to each type and bundle is fractional. Envy-freeness and Pareto efficiency remain meaningful under that model, and checking improvements through type-preserving couplings gives it genuine computational structure. The bundle caps may narrow the proposed formulation, but finite per-capita supplies already bound the bundles, so this can be repaired without losing the core question. Prior high-multiplicity work supports the plausibility of this regime.
So the paper-specific objection is strong: the proposed anchor does not mirror a named complexity result from this article. But I cannot honestly turn that into the universal claim that no worthwhile continuous mirror exists. The mass version of EEF–Allocation survives as a plausible research question, even if it is better described as an extension of the paper’s central problem than as a continuization of one of its own theorem-level results.
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.