| paper | d4-conf-aaai-2026-2425 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Every instance admits a finite-support rational EFX+PO allocation. Existence is in \(\mathrm P\), and for \(m=2\) an allocation with at most \(\tau+2\) positive-mass cohorts can be computed in time polynomial in \(m,\tau,L\). · discrete side: polynomial · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
Given a finite set of valuation types \(T\u005c), positive rational masses \(\mu_t\u005c) summing to \(1\u005c), positive rational valuations \(v_t=(1,r_t)\u005c), and rational per-capita supplies \(q_1,q_2\in\mathbb{Q}_{\ge 0}\u005c), does there always exist, and can one compute in time polynomial in \(\tau\u005c) and input bit length \(L\u005c), a finite-support allocation \(\lambda_{t,a,b}\ge 0\u005c) of type-\(t\u005c) mass to integral bundles \((a,b)\in\mathbb{Z}_{\ge0}^2\u005c), with type masses and aggregate supplies matching the input, that is EFX across every pair of positive-mass type-and-bundle cohorts and Pareto optimal? For Pareto optimality, compare feasible allocations through type-by-type couplings of old and new bundles: no such coupling may make almost every agent weakly better off and a positive mass strictly better off.
A continuum population has rational masses \(\mu_t\u005c) of valuation types \(v_t=(1,r_t)\u005c) and per-capita supplies \(q_1,q_2\u005c). Decision variables \(\lambda_{t,a,b}\u005c) assign mass to integral bundles, subject to type-mass and supply constraints; find an allocation satisfying EFX across positive-mass cohorts and Pareto optimality under type-preserving couplings.
Support-sensitive EFX means every positive-mass cohort constrains the allocation, so Theorem 5’s pivot structure gives no evidence for a \(\operatorname{poly}(\tau,L)\u005c) algorithm; this is a real open challenge, not a defect in the formulation.
fatal: False
The mirror covers the central two-good, positive-valuation EFX+PO existence and computation result of Theorem 5; it leaves Theorems 1–4’s discrete structural results and the EFX+fPO incompatibility claim outside its scope.
My lead is a high-multiplicity version of the paper’s two-good EFX+PO allocation problem. It preserves indivisible bundles for every recipient while making the population and aggregate supplies continuous.
Take a finite set of agent types \(T\), with rational masses \(\mu_t>0\) summing to \(1\). A type is the agent’s additive valuation on the two goods, normalized to \(v_t=(1,r_t)\) with rational \(r_t>0\); the normalization is valid because multiplying one agent’s utilities by a positive constant does not change EFX or Pareto comparisons. The instance also gives rational per-capita supplies \(q_1,q_2\) of the two goods.
A solution is a finite list of rational masses \(\lambda_{t,a,b}\): the mass of type-\(t\) agents receiving the integral bundle \((a,b)\in\mathbb Z_{\ge0}^2\). It must satisfy
\[
\sum_{a,b}\lambda_{t,a,b}=\mu_t,\qquad
\sum_{t,a,b}a\lambda_{t,a,b}=q_1,\qquad
\sum_{t,a,b}b\lambda_{t,a,b}=q_2.
\]
Thus fractional mass can be assigned to a bundle, but no individual receives a fractional bundle.
Require EFX across every pair of positive-mass bundle cohorts: for cohorts \((t,(a,b))\) and \((s,(c,d))\), and each good \(j\) present in \((c,d)\), the type-\(t\) agent’s utility for \((a,b)\) must be at least their utility for \((c,d)\) after removing one \(j\)-good. Require Pareto optimality against all other feasible mass allocations of integral bundles: there must be no reassignment that can pair each type’s original and new bundles so that every agent is weakly better off and a positive mass is strictly better off. The question is whether, for every such rational instance, one can compute such an allocation in time polynomial in \(\tau\) and the input bit length \(L\). Call this Two-Good EFX+PO Mass Allocation.
The anchor is Theorem 5, proved in this paper: given the paper’s preprocessed input, it finds an EFX+PO allocation in \(O(\log n+\log m)\) time. The input is a two-good instance with positive valuations, normalized so \(v_{i,1}=1\), with the \(v_{i,2}\) values sorted and agents divided at \(v_{i,2}=1\) into groups of sizes \(n_1,n_2\). After the paper’s allowed relabeling of goods and groups, the conditions include \(m_1/n_1\ge m_2/n_2\), \(m_2>0\), \(n_2>0\), and \(m_1+m_2\ge n\). The theorem gives an allocation, not just an existence result. The paper also says its algorithm takes \(O(n\log n+\log m)\) on general input and \(O(\log n+\log m)\) when agents are already ordered. Theorem 5 is an algorithmic anchor; the paper gives no comparable numbered hardness result for this exact two-good EFX+PO problem. Its introductory citation for NP-completeness concerns exact envy-freeness, a different question.
A plausible regime is a large relief programme distributing two standardized kinds of aid parcels among many households. Households with the same relative valuation for the two kinds form a type; there might be millions of recipients but only tens or hundreds of recurring profiles. The mass \(\mu_t\) is their population share. This is a credible high-multiplicity scenario, though it describes a standardized population rather than all real allocation settings.
The authors should recognize this as their problem’s continuous-population analogue: agents still receive integral bundles, the fairness test is still EFX between agents, and the efficiency test is still Pareto optimality. The mass representation only allows the supply and the number of recipients of each bundle to be fractional in aggregate. That is the co-modification needed to describe a population continuously; it does not replace the population question with divisible outcomes.
I expect Class A, tractable, but this is a prediction, not a transfer of Theorem 5. Its algorithm sorts agents by valuation ratio and returns only a few bundle patterns, which suggests a compressed version could work on type masses rather than an explicit list of people. The central follow-up is whether one can find that allocation in \(\operatorname{poly}(\tau,L)\) time while maintaining exact EFX and Pareto optimality. Related questions include whether the output always has a compact rational representation, how to round it for a finite population, and whether the method extends beyond two goods.
The weakest point is the paper’s use of a particular individual as a split point: in a continuum, one household has zero mass. Replacing that pivot with a positive mass assigned among neighboring integral bundles may change the EFX or Pareto arguments. The continuous question therefore needs its own proof. That difficulty is also exactly where this mirror tests whether the theorem’s construction survives removal of one-person granularity.
The strongest objection is that Theorem 5 is an algorithm for an explicitly listed population, and its construction turns on an individual split point \(t\). Its constant-time EFX checks exploit a small number of bundles shared by contiguous blocks of sorted agents; its final reallocation then uses integer counts around that pivot. The theorem does not give an algorithm parameterized by the number of distinct valuation types, and the pivot has no direct counterpart as a positive-mass cohort. So the proposed polynomial-time result in \((\tau,L)\) needs new arguments; it is not a translation of Theorem 5.
That exposes a real difficulty, but the stronger mass-over-integral-bundles formulation handles it coherently. EFX can be required between every pair of positive-mass cohorts, and Pareto comparisons can preserve each recipient’s integral bundle. EFX is sensitive to support: a cohort of tiny positive mass still imposes comparisons, while a cohort that vanishes in a limit imposes none. That makes a limit argument unreliable, but it does not make the continuous question ill-posed. A large standardized distribution of aid among households with recurring valuation profiles is a plausible high-multiplicity setting.
The best case against its value is that the problem has only two good types and the discrete construction already compresses allocations into a small number of bundle patterns. A weighted version might reduce to searches over type masses and integer breakpoints, making the continuous algorithm a modest extension of the existing structure. But that is a conjecture about how hard the missing proof will be, not evidence that the question lacks value; the individual pivot and support-sensitive EFX are precisely where that extension could fail.
I can’t honestly defeat this anchor. Theorem 5 is a named computational result, and the proposed mirror keeps the population continuous while giving recipients integral bundles. The negative case establishes that the theorem does not automatically transfer; it does not establish that no worthwhile mirror exists. On the material here, this is a strong surviving anchor.
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.