| paper | d4-conf-ecai-2016-0168 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-hard}\) · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 6
statement extracted from the paper’s text layer
Given a finite set of student types \(T\), rational masses \(\mu_t\) summing to \(1\), seat types \(G\), a strict ranking and nonnegative rational additive utilities \(v_{tg}\) for each \(t\), rational per-student supplies \(s_g\) with \(\sum_{g\in G}s_g=R\) for an integer \(R\), and a rational threshold \(w\), does there exist a policy of \(R\) measurable measure-preserving orderings of an atomless unit population such that, in every round, each student takes their highest-ranked seat type still available and almost every student receives total utility at least \(w\)? Supplies are consumed by the induced mass-flow, while each individual receives an integral bundle.
A unit-mass atomless population is partitioned into finitely many types with rational masses \(\mu_t\); type \(t\) has a fixed ranking and utility vector. The chair chooses measurable orderings for \(R\) sequential rounds, seat supplies \(s_g\) scale per student, and each individual still receives one indivisible seat in each round. The decision objective is whether the essential minimum welfare reaches \(w\).
The proposed policy ranges over measurable schedules, and the proponent does not provide a finite normal form for them; that leaves an algorithmic representation problem even though the decision question is specified over finite rational inputs.
fatal: False
The mirror covers the possible egalitarian welfare result in Theorem 6; it leaves the theorem's other welfare questions and the paper's results for other policy classes untreated.
The strongest mirror is the paper’s policy-control question under recursively balanced policies. A plausible setting is a large course-allocation system: many students, relatively few distinct utility and ranking profiles, and course-seat supplies that grow with enrollment. Students of the same type have the same complete utility vector and ranking over course types. Mass \(\mu_t\) is the fraction of students of type \(t\); each student still receives an integral bundle of indivisible seats, while seat supply is specified per student and scales with the population.
My anchor is Theorem 6, proved in this paper. It states that, for recursively balanced policies, Possible Egalitarian Welfare and Possible Utilitarian Welfare are NP-complete, while Necessary Egalitarian Welfare and Necessary Utilitarian Welfare are coNP-complete. The paper’s proof reduces from the corresponding top-\(k\) possible or necessary set problems. For its Possible Egalitarian Welfare reduction, one agent values each of their top \(k\) items at \(k^2\) and all other items at zero; the remaining agents value every item at least \(k^3\). Reaching egalitarian welfare \(k^3\) is then equivalent to making the designated agent receive their top \(k\) items.
The continuous problem I would put to a prover is RB-Continuous Possible Egalitarian Welfare. An instance has a finite set \(T\) of student types, rational masses \(\mu_t\) summing to \(1\), and a finite set \(G\) of seat types. Each \(t\) has a strict ranking and nonnegative rational additive utilities \(v_{tg}\) over \(G\). Each seat type \(g\) has rational per-student supply \(s_g\), with \(\sum_g s_g=R\) for an integer \(R\). The population is an atomless unit interval with type masses \(\mu_t\). A policy is a sequence of \(R\) measurable, measure-preserving schedules: in each round every student gets exactly one turn, and at that turn picks their highest-ranked seat type with remaining supply. Given a rational threshold \(w\), ask whether there is such a policy under which almost every student receives total utility at least \(w\). A solution is the policy schedule and its induced picks. This keeps the paper’s chair, sequential sincere picking, additive welfare, and recursive balance; it changes population and seat supplies together so that the limit is defined.
I would expect the unrestricted version to be continuum-specifically hard (Class C), with a plausible tractable fixed-\(R\) boundary. Atomless scheduling lets the chair split a type’s mass across turn positions, so the discrete top-\(k\) hardness does not automatically transfer. But students still receive integral bundles, and the schedule must make those bundles reachable through sequential picks. A configuration formulation would need to handle both constraints; its pricing problem over safe bundles and reachable round-by-round histories may remain hard. The paper’s theorem gives a concrete reason to ask whether that hardness survives, while the continuous model makes fractional population scheduling and configuration optimization available as tools. Further questions are whether schedules admit a finite rational normal form, whether fixed \(R\) yields a flow or configuration-LP algorithm, and whether hardness returns when \(R\) is part of the input.
My weakest point is that the anchor’s reduction singles out one agent. In a continuum, a positive-mass cohort is not one designated person, and extra scheduling freedom may erase the reduction’s obstacle. The mirror is credible as the paper’s same welfare-control problem in a high-multiplicity regime; I would not claim Theorem 6’s hardness already applies to it. The paper’s results about expected welfare under a random policy do not collide with this mirror: they keep the society finite and make policy choice stochastic.
Theorem 6 is a genuine computational anchor, so the case against cannot rest on the absence of a result to mirror. Its weakness is in the particular source of its hardness: the reduction makes one designated agent’s top-\(k\) picks determine whether the egalitarian threshold is met. In an atomless population, a single agent has zero mass. Replicating that agent into a positive-mass cohort changes the question: now every member of the cohort must meet the threshold, and seat supplies must scale with the cohort. The paper’s reduction does not establish hardness for that problem.
There is a more basic gap in the proposed formulation. A policy is an arbitrary measurable schedule, but the paper’s decision problems have finite witnesses. Before this is a computational problem, one needs to show that schedules can be represented by finite certificates—or that unrestricted measurable schedules give the same answer as some finitely described class. The proponent identifies a finite rational normal form as an open question. That is a real obstacle to treating Theorem 6 as an established mirror, though not proof that such a normal form cannot be found.
Those objections do not defeat the stronger version of the mirror. A large course-allocation system with repeated student profiles and seat supplies that scale with enrollment is a plausible high-multiplicity regime. Requiring almost every student to receive an integral bundle above a welfare threshold preserves the paper’s welfare-control question. Whether the resulting scheduling problem has a finite normal form, admits an efficient configuration formulation, or remains hard is itself a well-posed computational question once the representation is supplied.
So the negative case is weak. The paper’s hardness proof does not carry over as written, and the proposed schedule model needs a finite computational representation. But neither point shows that every sensible continuous-population mirror fails; the cohort-and-seat-supply model remains credible and worth investigating.
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.