| paper | d4-conf-aaai-2026-0245 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable: construction takes time \(\operatorname{poly}(m,\tau,R,L)\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given rational type masses \(\mu_t\), additive utility vectors \(u_t\in\mathbb{Q}_{\ge 0}^m\), and rational per-capita supplies \(q_g\ge 0\), consider ordered profiles \(f:[0,1]\to T\) encoded as \(R\) rational rank intervals, with each type appearing on mass \(\mu_t\). Can one construct a scale-invariant polynomial-time rule, with running time measured in \(m,\tau,R,L\), that maps each \(f\) to a rank-indexed allocation \(B_f(r)\in\mathbb{Z}_{\ge 0}^m\), satisfies \(\int_0^1 B_{f,g}(r)\,dr=q_g\) for every good class \(g\), and gives EF1 for almost every pair of ranks? Require also PEF1 across every pair \(f,f'\) with the same type masses: for every type-preserving measure-preserving bijection \(\phi\) between their rank spaces, almost every rank \(r\) must satisfy the PEF1 comparison between \(B_f(r)\) and \(B_{f'}(\phi(r))\), using utility \(u_{f(r)}\) and removal of one good.
A continuum of agents with type masses \(\mu_t\), finite additive utility vectors, and per-capita supplies of equivalent goods. Each agent receives an integral bundle; the aggregate allocation is a measurable rank-indexed assignment whose mass averages meet supply. The mechanism sees the ordered type profile, not the identity-to-rank correspondence, and must preserve EF1 within each ordering and PEF1 for the same identity across orderings.
An arbitrary \(R\)-interval rank profile can encode nearly individual-level ordering detail, so the high-multiplicity representation may provide little compression.
fatal: False
Covers Theorem 3's polynomial-time, scale-invariant PEF1 and EF1 guarantee in a continuous cohort model. It leaves the two-agent MNW and adjusted-winner results, and the analyses of round-robin and envy-cycle mechanisms, unmirrored.
The strongest mirror is Theorem 3, proved in this paper. It says that for agents with nonnegative additive utilities over indivisible goods, there is a scale-invariant, polynomial-time mechanism that satisfies PEF1 for every profile and pair of agent orderings, while always producing an EF1 allocation. The authors prove it using repeated maximum-weight matchings. This is the paper’s clearest named computational anchor for a many-agent setting.
I would place it in a large course-allocation system: many students, a relatively small number \(\tau\) of distinct additive preference vectors over \(m\) course-seat classes, and a priority order that can change. Think thousands or more students but tens or hundreds of preference types. Each seat remains indivisible for the student who receives it. As enrollment grows, seat supply grows with it, so the natural continuous input records seats per student. This is a regime for the paper’s actual concern—how priority affects a person’s allocation—not a claim that course outcomes are already continuous.
Here is the continuous problem I would hand to a prover. Call it Continuous PEF1–EF1 Cohort Allocation. The input has rational type masses \(\mu_t\), with \(\sum_{t=1}^{\tau}\mu_t=1\); rational additive utility vectors \(u_t\in\mathbb Q_{\ge0}^m\); and rational per-capita supplies \(q_g\) for the \(m\) seat classes, with \(\sum_g q_g=K\) for an integer \(K\). A person’s bundle is still integral: a count vector \(b\in\mathbb Z_{\ge0}^m\) with \(\sum_g b_g=K\). The co-modification is that each class has many equivalent physical copies, supplied in proportion to the population. A mass of students may receive any given bundle, so aggregate amounts are fractional even though every student receives whole seats.
Represent the students of type \(t\) by an identity interval of length \(\mu_t\). An ordering is a measure-preserving assignment of those identities to ranks \(r\in[0,1]\); the ordered profile \(f(r)\) records the type at each rank. The mechanism sees \(f\), not the identity-to-rank correspondence. It outputs a rank-indexed bundle assignment \(B_f(r)\). Feasibility requires that each person receives an integral bundle and that the mass-weighted use of each seat class equals its supply \(q_g\). For computational input, take \(f\) to be explicitly encoded—for example, as \(R\) rational rank intervals labelled by type—and measure running time in \(m,\tau,K,R\), and the rational bit length \(L\).
The requested solution is one polynomial-time rule for these inputs, invariant when a type’s utilities are scaled by a positive constant. For every ordering, it must make the allocation EF1: for each student and each other student, removing one seat from the other’s bundle eliminates envy. Across every pair of orderings, it must make the allocation PEF1 for the *same identity*: that student’s bundle under the first ordering must be at least as valuable as their bundle under the second ordering after removing one seat. There is no welfare-maximization objective here; the task is to construct a feasible mechanism with those guarantees.
I expect this mirror to be Class A. Theorem 3 already gives a round-by-round construction, and in the continuous version each round suggests a transportation or maximum-cost-flow problem over types, rank intervals, and seat classes. A mass assignment can split students across seat classes while assigning each individual a whole seat; after \(K\) rounds, each student has an integral bundle. The paper’s central fairness requirements remain intact, and per-capita supply is precisely the co-modification that makes the large-population allocation meaningful.
The serious proof obligation is to preserve PEF1. The paper compares the bundles of one individual across orderings. An aggregate table \(x_{t,B}\) stating how much of each type receives each bundle does not by itself track that individual or certify the cross-order comparison. The continuous mechanism needs a rank-based allocation rule with a consistent identity-level interpretation, not merely a type-average relaxation. The paper’s use of ordered profiles while hiding the identity-to-position map gives authors a clear reason to recognize this as their problem, but extending their matching argument to an atomless population is real work.
I would keep the scope to Theorem 3. Theorem 8 also gives a polynomial-time mechanism, but fixes \(n=2\), which is a poor anchor for a many-agent population limit. The paper mentions NP- and APX-hardness of computing MNW allocations, but cites those results from elsewhere; they are not a numbered hardness result proved here, so I would not use them as anchors. A natural next question is whether the continuous mechanism can also guarantee Pareto optimality, echoing the paper’s open question for general \(n\). The weakest point remains the identity-level PEF1 condition: if it cannot be maintained under mass aggregation, the proposed tractability route could fail.
Theorem 3 is the only strong anchor, and it is a real computational result: a polynomial-time mechanism with PEF1 and EF1 guarantees. So the case against cannot start by saying the paper has no complexity result. Nor does the divisible-goods literature on meta-envy-freeness dispose of it: that changes the outcome space, not the population.
The best objection is that the proposed continuous input is doing more work than the type distribution suggests. The population measure \(\mu\) records how much mass has each utility vector, but PEF1 compares the bundles of the same person under different orderings. To state that comparison, the proposal adds a rank profile \(f\) and a correspondence between ranks and identities. With unrestricted orderings, even a population with few types can have arbitrarily intricate interleavings of those types; the number \(R\) of rank intervals need not be small relative to the population. A type-to-bundle mass table is more compressed, but it cannot certify the same-person comparisons. Thus the proposed mirror has not shown that the high-multiplicity representation retains the paper’s central guarantee at lower input complexity.
That is a serious formulation and compression concern, but the better mirror can address it: define rank-indexed allocations of integral bundles and require PEF1 almost everywhere under every type-preserving coupling between orderings. This avoids named identities while retaining the same fairness question. It also makes the task a computational problem over an explicitly encoded rank profile, with complexity measured in \(R\). That encoding may offer little compression for arbitrary priority orders, but the question remains coherent; a low-complexity ordering regime could also be meaningful. The theorem’s matching argument gives a plausible starting point for such a model.
So the strongest negative case is that the proposed mirror has not yet demonstrated a high-multiplicity computational gain: the ordering structure and identity comparison may carry the input complexity the type masses were meant to remove. I do not think this defeats the anchor universally. A continuous PEF1–EF1 cohort problem remains a plausible, author-recognizable mirror of Theorem 3, and I cannot honestly make the case that no scenario is worth the programme’s time.
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.