| paper | d4-conf-atal-2014-0155 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Polynomial-time solvable (\(\mathrm{P}\)). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given a finite school set \(C\), a listed family of regions \(R\subseteq 2^C\), and rational lower-quota fractions \(p_r\), does a nonatomic unit-mass population of one feasibility-relevant type admit an assignment to schools in which each individual receives one whole school place and every region \(r\) receives at least mass \(p_r\)?
One type \(t\) has mass \(\mu_t=1\). Variables \(x_{t,c}\ge 0\) denote mass assigned to school \(c\), with \(\sum_{c\in C}x_{t,c}=1\) and \(\sum_{c\in r}x_{t,c}\ge p_r\) for every \(r\in R\). The aggregate assignment is fractional, while every individual receives one indivisible school place.
The mirror covers Theorem 2's general-region feasibility result for minimum quotas. It leaves the hierarchical-region algorithm, the strategy-proof mechanisms, their fairness and wastefulness properties, and the simulation results aside.
The strongest mirror is the paper’s feasibility result, rather than its strategy-proof mechanisms. A plausible regime is a large school or hospital placement system checking whether its regional quota policy can accommodate an annual applicant cohort. For that feasibility question, the relevant type can be the single class of applicants who are all eligible for every school: preferences and priorities do not appear in the anchor’s input. The cohort may contain many thousands of people while having just one feasibility-relevant type.
My anchor is Theorem 2, proved in this paper. It says that, given \(S,C,R,p,q\), deciding whether a feasible matching exists is NP-complete even when the instance has only maximum quotas or only minimum quotas. The paper derives this from Theorem 1: it proves hardness for general quotas, then observes that a quota on a region can be represented by the opposite quota on its complement. I would mirror the “only minimum quotas” case, which is the paper’s direct regional-minimum setting.
Call the mirror General-Region Minimum-Quota Mass Feasibility. An instance gives a finite set of schools \(C\), an arbitrary listed family of regions \(R\subseteq 2^C\), a nonatomic applicant population of total mass \(1\), and rational per-capita lower quotas \(p_r\) for \(r\in R\). In the exact anchor’s feasibility model, all applicants are eligible for all schools and form one type. The question is whether the population can be assigned so every individual receives exactly one school and each region \(r\) receives at least mass \(p_r\).
A solution can be given as nonnegative masses \(x_{t,c}\), where \(x_{t,c}\) is the mass of type \(t\) assigned to school \(c\), satisfying
\[ \sum_{c\in C}x_{t,c}=\mu_t \quad\text{for each }t, \qquad \sum_t\sum_{c\in r}x_{t,c}\ge p_r \quad\text{for each }r\in R. \]
In the anchor’s exact version, \(\tau=1\) and \(\mu_1=1\). Because each type’s population is nonatomic, any such mass table can be realized by partitioning that population into groups; each person still gets one whole school place. The fractional quantities describe how much population goes to each school, not a fractional assignment for any individual.
I expect this mirror to be tractable: it is a rational linear-program feasibility problem with \(\tau |C|\) variables and a constraint for each type and region, so it is solvable in polynomial time in the listed input size and bit length. The discrete matching embeds into it by normalizing assignment counts by the cohort size. The reverse implication need not hold: the mass assignment may split a type in ways that no discrete assignment can. That gap is the point to investigate. Further questions include when the resulting polytope is integral, when a continuous feasible solution can be rounded while preserving quotas, and which region families make such recovery possible.
The authors should recognize this as their problem in a population regime: it asks the same question—whether a full assignment satisfies the stated regional quotas—with quota levels expressed per capita. The regime is credible for a large interchangeable cohort subject to administrative regional quotas, and Theorem 2 itself abstracts away student preferences and priorities. This case covers that feasibility result, not the paper’s DA mechanisms, strategy-proofness, or welfare comparisons.
The weakest point is that the continuous model permits a cohort to be divided across schools, so it can answer “yes” where the finite instance answers “no.” That is a real change from the discrete problem. But it is a clear population continuization of the same quota-feasibility question, and the resulting integrality gap is precisely what makes the mirror worth studying.
The only serious target is Theorem 2’s quota-feasibility result. Its input uses students only through their number: preferences, priorities, and welfare do not enter. The reduction’s combinatorics live in the school and region structure, while the students are interchangeable units used to satisfy quotas. That makes this a weak anchor for a programme about populations of agent types: enriching the type space with preferences or eligibility would change the question, while the theorem itself has only one feasibility-relevant type.
The strongest version of the objection is that the proposed mass model is therefore an anonymous fractional allocation problem, not a continuous version of the paper’s richer matching market. And its connection back to the discrete decision question is one-sided: an integral feasible matching gives a feasible mass allocation after normalization, but a feasible mass allocation need not round to a feasible matching. Since the theorem asks a yes-or-no question, an additive approximation to the relaxed answer does not by itself decide the original question. Recovering that connection would require studying integrality or rounding, which goes beyond the theorem’s stated result.
But this does not defeat the mirror. The paper’s theorem is itself an anonymous feasibility question, so a one-type population is faithful to its input. A large applicant cohort with per-capita regional quotas is plausible; each person can still receive one whole school place while the population is divided into measurable groups. Overlapping regional quotas are also part of the theorem’s explicit general case. The authors could reasonably recognize mass feasibility—and the gap between it and finite feasibility—as their problem.
So the negative case is weak. I can argue that this is the paper’s least representative result and that its link back to finite yes-or-no feasibility may be limited. I cannot honestly argue that no worthwhile continuous mirror exists: Theorem 2 survives as a well-posed population continuization, even though it says little about the paper’s mechanisms.
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.