| paper | d4-conf-sagt-2015-0009 |
| 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: \(\mathrm{P}\) · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Corollary 4
Given a fixed course set \(C\), a finite set \(T\) of applicant types, rational type masses \(\mu_t\) summing to \(1\), and per-capita course capacities \(\kappa_c\), each type specifying a complete course preference ordering with ties and an individual quota, take as input a feasible allocation \(x_{t,S}\) of each type’s mass to acceptable, quota-feasible integral bundles \(S\). Is there a reassignment that preserves each type’s mass, respects every course capacity, gives each reassigned mass a bundle weakly preferred to its current bundle, and gives a positive mass a strictly preferred bundle?
Represent reassignment by \(z_{t,S,U}\), the mass of type \(t\) moved from bundle \(S\) to bundle \(U\). Maximize \(\sum_{t,S,U:\,U\succ_t S} z_{t,S,U}\), subject to \(\sum_U z_{t,S,U}=x_{t,S}\), \(z_{t,S,U}=0\) unless \(U\succeq_t S\), and total mass assigned each course \(c\) at most \(\kappa_c\). The allocation is Pareto optimal exactly when the optimum is zero.
The allocation input may have large support \(R\), so compression to the preference-type support \(\tau\) depends on the number of distinct type-bundle assignments also being manageable.
fatal: False
The mirror covers the Pareto-optimality recognition problem anchored by Corollary 4. It does not establish continuous counterparts of the extended envy graph characterization, GSDT’s generation results, or the truthfulness results.
The strongest anchor is Corollary 4, proved in this paper: given a many-to-many course-allocation instance \(I\) and a matching \(\mu\), one can decide in polynomial time whether \(\mu\) is Pareto optimal. The paper gets there through Theorem 3: \(\mu\) is Pareto optimal exactly when its extended envy graph has no negative-cost cycle. The paper gives no comparable hardness result, so this is the algorithmic anchor to use.
A direct population mirror is Type-Mass Pareto-Efficiency Recognition. Take a fixed finite course catalogue \(C\) and a finite support \(T\) of applicant types. A type specifies an applicant’s complete preference ordering, including ties, over courses and her course quota. Let \(\mu_t\) be the fraction of applicants of type \(t\). Course capacity is given per capita, so \(\kappa_c\) is the amount of course \(c\)’s capacity per unit of population. Each person still receives an integral bundle of distinct acceptable courses; only the mass of people receiving each bundle can be fractional.
The input includes a feasible allocation \(x_{t,S}\): the mass of type \(t\) receiving each bundle \(S\). Thus \(\sum_S x_{t,S}=\mu_t\), and total mass assigned course \(c\) is at most \(\kappa_c\). The question is whether this allocation is Pareto optimal: can some mass be reassigned so that nobody receives a less-preferred bundle and positive mass receives a strictly preferred one?
Precisely, let \(z_{t,S,U}\) be the mass currently receiving \(S\) who would receive \(U\) after the change. Require \(\sum_U z_{t,S,U}=x_{t,S}\); allow \(z_{t,S,U}>0\) only when \(U\) is an acceptable, quota-feasible bundle with \(U\succeq_t S\); and require the total mass receiving each course \(c\) afterward to be at most \(\kappa_c\). Maximize \(\sum_{t,S,U:\,U\succ_t S}z_{t,S,U}\). The allocation is Pareto optimal exactly when this optimum is zero. A positive value supplies a witness improvement; an optimum of zero certifies that none exists.
This is a credible large-market regime for course allocation at a large university or consortium: many students share standardized preference templates and schedule quotas, while the course catalogue stays fixed and capacities grow with enrollment. The types must be complete in the paper’s sense: students grouped together have the same preferences and quota. The intended regime has \(N\gg\tau\), not merely a large institution with mostly unique preferences. This keeps the problem recognizably about the paper’s many-to-many assignments, ties, quotas, and Pareto efficiency. Per-capita course supplies and fractional type-level masses are the co-modification that makes the population continuous; bundles remain integral for each person.
I would expect this mirror to be Class A, though that is a conjecture to prove. The LP has exponentially many possible destination bundles \(U\), but its pricing question appears manageable. For a fixed source bundle \(S\), dual course prices give additive values for selecting courses; the destination must also be lexicographically no worse than \(S\). Split that condition by the first tie class where \(U\) improves, or by the case where all tie counts stay equal. In each case, the quota and tie-class counts allow a polynomial dynamic program to find the best bundle. If that pricing oracle is polynomial, ellipsoid or column-generation methods should give a running time polynomial in the number of courses \(m\), support size \(\tau\), the number of input bundle types \(R\), and rational input length \(L\).
The scope is Corollary 4’s recognition problem, with Theorem 3’s negative-cycle characterization as motivation. This does not claim to mirror GSDT’s generation results or Theorem 14’s strategy-proofness impossibility; those need separate continuous definitions.
The weak point is the change in feasible Pareto improvements. A continuum can split a type cohort into arbitrarily small masses, so an improvement may move less than one person in a finite enrollment. A discrete matching embeds as a rational mass allocation, but its Pareto-optimality status need not be preserved at finite \(N\). Establishing when the continuous test approximates or agrees with high-multiplicity discrete instances is therefore an important follow-up, and the main qualification on this mirror.
The case against has to rest on Corollary 4: this paper does state a computational problem, and Theorems 2–3 give its characterization. So “there is no result to mirror” does not work.
The strongest objection is that the proposed mirror needs a second input beyond the type masses: an allocation \(x_{t,S}\) describing which bundles each type currently receives. With heterogeneous allocations within a type, that table can have many bundle entries. The attractive compression from a large applicant population to a small type support \(\tau\) then depends on the allocation also having small support \(R\). Restricting to one bundle per type would keep the input compact, but would fail to represent many ordinary high-multiplicity matchings in which otherwise identical applicants receive different bundles. This makes the proposed mirror less uniformly compact than the paper’s recognition problem.
That is a limitation on the promised high-multiplicity payoff, not a decisive objection to asking the question. \(R\) is part of a legitimate input description, and the paper’s problem can still have a meaningful continuous version when \(R\) is moderate. The proposed regime—large cohorts sharing preference and quota templates, with per-capita course capacities—is coherent; applicant identity carries no extra information once those details are included in the type.
There is also a real bridge issue: the continuous test treats a positive mass as enough for a Pareto improvement, while the finite problem requires at least one applicant. A very small improvement may therefore be absent at a particular population size. But with rational masses and allocations, fixed instances can be replicated at a common denominator, so this does not defeat the high-multiplicity connection; it calls for a careful statement of it.
I cannot make an honest case that no worthwhile mirror exists in any scenario. The best negative case is that the compression may be limited by allocation support and that the Pareto notion needs a precise finite-to-continuous bridge. Neither defeats the proposed recognition mirror for the programme’s purposes.
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.