| paper | d4-conf-atal-2022-0160 |
| 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 in \(m,\tau,|E|,L\) by assigning each edge, in priority order, the minimum of its residual student, project, and grant capacities. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given finite student types \(U\) with rational masses \(\mu_a\), project types \(V\) with rational slot masses \(q_b\), admissible type pairs \(E\), a per-capita grant limit \(\kappa\), and a strict priority order on \(E\), compute a feasible assignment \(x_{ab}\geq 0\) that lexicographically maximizes the masses assigned to type pairs in priority order, subject to student, project, and grant capacities.
A mass matching between student and project types: \(x_{ab}\) is the mass assigned on an admissible pair, each student type supplies at most \(\mu_a\), each project type receives at most \(q_b\), and total assigned mass is at most \(\kappa\). Each individual receives one project or none; fractional values describe assignments across the mass of a type.
The paper’s strict order can distinguish named student-project pairs, so a small-support mirror requires the committee to treat members of each type-pair block as interchangeable; the paper’s individual-pair setting does not establish that this fits its motivating schemes.
fatal: False
The mirror covers Theorem 1’s lexicographic-optimality result for Greedy in a repeated-types, block-priority regime. It leaves the paper’s stability, strategyproofness, dynamic monotonicity, and comparisons among mechanisms unaddressed.
The paper gives no named NP-hardness result, and it does not explicitly classify a problem as being in P. Its strongest computational anchor is Theorem 1, proved in this paper: *Greedy outputs a lexicographically optimal matching.* In full, Greedy scans the master list in order, adds a pair whenever both its student and project are unmatched, and stops when it reaches the grant limit or exhausts the list. The theorem proves that this procedure returns the unique matching that is lexicographically optimal under the committee’s master-list ordering. Since the algorithm scans the list once, this is a polynomial-time tractability result.
A credible high-multiplicity setting would be a large, multi-institutional doctoral funding round with many applicants and replicated project slots. A student type records the applicant’s complete project ranking, acceptable projects, and any committee-relevant attributes; a project type records the relevant project or supervisor profile. The committee orders *type-pair blocks* by priority, with any tie-breaking among individual pairs inside a block affecting only otherwise indistinguishable applicants and slots. There can be many more applicants and slots than distinct student and project types. This is a regime for such a scheme, not a claim that a small department’s annual round is already a continuum.
I would hand the authors this lead problem, Type-Lex-Mass Matching. An instance has finite sets of student types \(U\) and project types \(V\), rational student masses \(\mu_a\) with \(\sum_{a\in U}\mu_a=1\), rational project-slot masses \(q_b\), a per-capita grant limit \(\kappa\), an admissible set \(E\subseteq U\times V\), and a strict committee order on \(E\). For each \((a,b)\in E\), choose \(x_{ab}\geq 0\), the mass of type-\(a\) students assigned to type-\(b\) slots, subject to \(\sum_b x_{ab}\leq\mu_a\), \(\sum_a x_{ab}\leq q_b\), and \(\sum_{(a,b)\in E}x_{ab}\leq\kappa\). The task is to return a feasible \(x\) that lexicographically maximizes its coordinates in committee order. Unassigned mass is \(\mu_a-\sum_bx_{ab}\). Each individual in the continuum still receives one project or none; fractional values describe how much mass of a type receives each project.
This preserves the theorem’s object and priority rule: the committee’s lexicographic choice among one-to-one assignments. The co-modification is that repeated project slots and the grant limit scale with the population, so their capacities become masses. With integer clone counts and capacities, the corresponding bipartite flow has an integral realization; under the stated block-order and clone-symmetry assumptions, its aggregate type-pair totals are the continuous counterpart of the discrete Greedy outcome. For Type-Lex-Mass Matching I expect Class A, tractable: process the type-pair blocks in order, assigning each as much remaining student and project mass as possible, up to the remaining grant capacity. The relevant size parameters are the numbers of supported types, admissible type-pairs, and the rational input bit length.
The authors should recognize this as their lexicographic matching question with repeated, indistinguishable applicants and slots: it keeps the master list, admissibility, one-assignment constraints, grant cap, and committee objective. The scope is deliberately just Theorem 1. Further questions include whether continuum versions of stability and student-optimality capture the paper’s other mechanisms, and whether dynamic monotonicity can be defined when a positive mass of one type withdraws or raises its acceptance threshold.
The weak point is that the paper’s result is already easy to compute on its explicit discrete input; this mirror does not show discrete hardness dissolving, and it assumes priorities can be organized into clone-symmetric type-pair blocks. That limits its value as a continuization result. It still makes a respectable positive case: it names a plausible large-market regime and carries the paper’s actual lexicographic objective into a continuous matching problem without turning assignments into fractional bundles.
The only plausible anchor is Theorem 1: Greedy returns the lexicographically optimal matching. Its weakness as a computational result is that the paper gives the algorithm itself—a scan down the finite master list—and proves its correctness. The theorem does not identify a complexity boundary or an algorithmic bottleneck; it establishes a property of this particular mechanism.
The stronger objection is that the proposed mass model changes what the master list means. In the paper, \(L\) is a strict order over individual student-project pairs, and that order is central: it can distinguish two applicants even when their preferences and admissible projects are identical. To preserve that distinction in a type, the committee priority must be part of the type. Then applicants at different positions in \(L\) are different types, and the proposed high-multiplicity regime may disappear.
Type-Lex-Mass Matching avoids that problem by giving every pair in a type-pair block the same priority. That is coherent, and scaling project slots and grants with the population is an allowed co-modification. But it replaces the paper’s order over named pairs with an order over categories. Lexicographically maximizing the mass assigned to each category does not preserve the committee’s exact pair-by-pair choice when its ordering distinguishes or interleaves individuals. The resulting model is a plausible tier-priority matching problem; it is not simply Theorem 1 with more students.
This objection is strongest in the paper’s stated setting, where each project is a particular funded position and the committee evaluates particular student-project fits. A large recurring scheme with repeated applicant and project types could make the category version natural, but it would need the committee to treat type-pair members as genuinely interchangeable. The proponent has supplied a possible scenario, not evidence that this assumption fits the mechanism studied.
The negative case is therefore limited. Theorem 1 does have an algorithmic content, and a large market with repeated types and block priorities could yield a sensible continuous version. I cannot honestly rule that version out as unworthy; the case against is that the paper’s actual result depends on individual-pair priority, while the proposed mirror obtains a clean continuum by changing that priority structure.
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.