| paper | d4-journals-mss-2026-0031 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 2
statement extracted from the paper’s text layer
Given two atomless preference cohorts \(X_1,X_2\) of rational masses \(\mu_1,\mu_2>0\) summing to \(1\), ranked object classes \(J\) with rational supplies \(q_j>0\) summing to \(1\), and rational type-level marginals \(p_{tj}\), assume \(\sum_j p_{tj}=1\), \(\sum_t\mu_t p_{tj}=q_j\), and SD-EF for every ranking prefix. Can one compute in time polynomial in \(|J|\) and the input bit length a finite lottery over deterministic allocations, represented by finite interval partitions of each cohort, such that every outcome assigns each agent one whole class and allocates mass \(q_j\) of each class, every agent \(x\in X_t\) receives class \(j\) with probability \(p_{tj}\), and for every distinct pair \(x\in X_t,y\), the probability that \(x\)'s assigned class is preferred to \(y\)'s is at most \(1/2\)?
Two atomless cohorts \(X_1,X_2\) carry mass \(\mu_1,\mu_2\) and have strict rankings over interchangeable object classes \(J\) with atomless supplies \(q_j\). Each outcome is an identity-resolved measurable allocation assigning every agent one whole class and matching each supply; a finite lottery over interval-partition allocations must give each agent the input marginal \(p_{tj}\) and keep envy probability at most \(1/2\) for every distinct pair. For rational data, expanding each class into copies and each cohort into equal-mass cells gives an existence lift from Theorem 2; polynomial time and output size in the input bit length are the open computational question.
The proposed mass table controls only average sampled-pair envy; preserving the guarantee for every fixed pair requires identity-resolved allocations, and the denominator expansion does not provide a polynomial-size representation in the input bit length.
fatal: False
The mirror covers Theorem 2 and the two-preference-type part of Corollary 1 for PS outputs. It does not cover Theorem 1 for instances with three distinct preferences, the general envy bounds in Propositions 2 and 3, or the RP result.
The strongest honest anchor is Theorem 2, proved in this paper. It says that in every finite assignment instance with at most two distinct preference rankings, every SD-EF assignment matrix admits a decomposition satisfying Dec-EF. The proof gives a construction: for preference-type populations of sizes \(r\) and \(s\), it produces a decomposition with at most \(4rs(n+1)\) positive-probability assignments. The paper does not state a formal “in P” result; this is a constructive algorithmic theorem, whose explicit-\(n\) procedure can be implemented using supported perfect matchings and rational arithmetic.
Here is the continuous problem I would put to a prover: Two-Type Continuous Dec-EF Decomposition. There is a unit-mass population with two complete preference types, of masses \(\mu_1=\alpha\) and \(\mu_2=1-\alpha\), where \(0<\alpha<1\). There are finitely many strictly ranked object classes \(J\), each with an atomless supply \(q_j\), where \(\sum_{j\in J}q_j=1\). A class represents interchangeable copies of an object; in every realized allocation, each individual receives one class, and its total allocated mass is \(q_j\).
An instance gives rational masses and supplies, the two rankings, and a rational assignment matrix \(p\), where \(p_{tj}\) is the probability that an agent of type \(t\) receives class \(j\). Require \(\sum_j p_{tj}=1\), \(\sum_t\mu_t p_{tj}=q_j\), and SD-EF: for each type \(t\), each prefix \(B\) of its ranking, and the other type \(t'\),
\[
\sum_{j\in B}p_{tj}\ \ge\ \sum_{j\in B}p_{t'j}.
\]
The task is to output a finite lottery \((\lambda_\ell,z^\ell)\). Each outcome \(z^\ell_{tj}\) is the mass of type \(t\) assigned class \(j\), with row sums \(\mu_t\) and column sums \(q_j\); its expectation must recover the input, \(\sum_\ell\lambda_\ell z^\ell_{tj}=\mu_t p_{tj}\). It must also satisfy, for every ordered type pair \(t,t'\),
\[
\sum_\ell \lambda_\ell\frac{1}{\mu_t\mu_{t'}}
\sum_{\substack{a,b\in J\\ o_b\succ_t o_a}}
z^\ell_{t,a}z^\ell_{t',b}\ \le\ \frac12.
\]
This is the probability that a uniformly sampled type-\(t\) agent envies a uniformly sampled type-\(t'\) agent, with distinct agents sampled when \(t=t'\). Each table is realizable by partitioning the type populations into groups that receive whole object classes; fractional entries describe mass, not fractional bundles.
The regime is a large assignment market—say, public housing or standardized job placements—with millions of applicants, object supplies growing in proportion to the population, and two large cohorts sharing the same ranking within each cohort. The number of agents greatly exceeds the number of preference types: \(N\gg\tau=2\). Treating copies within a class as interchangeable and scaling their supply with population is the co-modification that makes the continuum model coherent.
I expect this problem to be tractable, in Class A. Theorem 2’s type symmetry and support-reduction construction are unusually good evidence for that expectation. More concretely, rational instances can be scaled to finite populations and object copies, lifted to SD-EF matrices with block-ordered copies, and passed through Theorem 2; collapsing copies back to classes gives the mass-allocation structure above. This supports existence in the continuous model. It does not by itself give a polynomial-time algorithm in the compact input length \(L\): scaling denominators can make the explicit finite population large. The computational question is whether the construction can be compressed to run in \(\operatorname{poly}(|J|,L)\) time and return a polynomial-size lottery.
This case covers Theorem 2’s two-preference-types result, and the corresponding two-type part of Corollary 1 for PS outputs. It does not mirror the paper’s \(n\le3\) result, its general \(n\)-agent envy bounds, or its RP observation. Further questions are whether a compact algorithm exists, whether the guarantee extends to three or more preference types, and whether stronger envy bounds can hold for particular assignment rules.
The weakest point is the semantic passage from distinct, strictly ranked objects and envy between every named pair to interchangeable object classes and envy for sampled pairs from nonatomic cohorts. In applications such as seats in the same program, that abstraction is natural; it also removes object distinctions and the individual-level quantifier that the original paper emphasizes. That is a real modeling cost. Still, the mirror preserves the paper’s central object—a lottery over integral assignments—and its exact SD-EF-to-Dec-EF question, in a genuinely high-multiplicity regime.
Theorem 2 is the strongest anchor, but the proposed mirror changes what its guarantee means. The theorem concerns a lottery over assignments to named agents and requires the envy probability to be at most \(1/2\) for every ordered pair. The proposed mass-table model instead bounds envy for a pair sampled uniformly from two cohorts. That controls average pairwise envy; it does not rule out particular agents being treated badly almost every time.
The mass table \(z\) records how much of each preference type receives each object class. It does not record which identities receive those shares or how identities’ assignments are correlated across lottery outcomes. So it can calculate the sampled-pair statistic, but it cannot by itself recover the paper’s all-pairs guarantee. To preserve that guarantee, one would need an identity-resolved random allocation or a precise exchangeable-limit model. The former loses the compact type-level description; the latter needs justification beyond the proposed table formulation.
There is a cost on the object side too. Keeping the paper’s distinct, strictly ranked objects preserves its envy comparisons, but leaves an explicit \(n\times n\) assignment matrix. The construction in Theorem 2 has support at most \(4rs(n+1)\), hence at most \(O(n^3)\), and appears implementable with polynomial work in that explicit input size. Compressing many objects into a few interchangeable classes can make the input smaller, but it replaces strict rankings over distinct objects with a model that treats copies as equivalent. That may be a good allocation model; it is not automatically the same Dec-EF problem.
These objections do not defeat the best repair. A large market with interchangeable seats or positions is plausible, and an exchangeable limit could make sampled-pair envy the right population-level analogue. The paper’s two-preference-type result makes that regime especially natural. So the negative case is weak: it exposes a real gap between the proposed mass statistic and the paper’s pairwise guarantee, but it cannot honestly rule out a worthwhile continuous mirror once the authors accept the sampled-pair or exchangeable-limit formulation.
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.