| paper | d4-conf-atal-2020-0291 |
| 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}$-complete · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4.4
statement extracted from the paper’s text layer
Given rational masses \(\mu_t\) over applicant types, type preferences, project priorities over types, project capacities, supervisor budgets, and the supervisor-project incidence structure, decide whether there are assignment masses \(x_{t,r}\) for \(r\in P\cup\{\bot\}\) and a feasible funding allocation such that no type \(t\) with positive mass at a source \(r\) has a preferred blocking project \(p\) for which all types assigned to \(p\) have at least as high a priority as \(t\), and some positive mass \(\varepsilon\leq x_{t,r}\) can move from \(r\) to \(p\) while preserving feasibility after funding is reallocated.
Use a finite set of complete applicant types, each carrying mass \(\mu_t\); type members share acceptable-project rankings, funding requirements, and project priority classes. Decision variables are assignment masses \(x_{t,p}\) and funding masses \(z_{s,p}\). Project capacities and supervisor budgets are per-capita quantities, and a blocking deviation moves positive mass from one assignment to a preferred project, testing feasibility after funding is reallocated.
Positive-mass blocking is a cohort-level deviation rather than the paper's single-applicant test, and the paper does not establish whether its authors would adopt that stability notion; the proposed market and explicit definition make it a plausible extension.
fatal: False
The mirror covers Theorem 4.4's strong-stability existence problem only; it leaves the weak-stability algorithm and the fair funding-allocation result unaddressed.
The strongest mirror is to continuize the applicant population in the paper’s strongly stable matching problem. The paper already makes supervisor funding divisible; that is not the continuization. In the mirror, assignments, project capacities, and supervisor budgets are measured per unit of population, while each individual still receives one whole project or remains unmatched.
A plausible regime is a large internship or hiring clearinghouse with thousands of applicants and a much smaller set of recurring applicant profiles. A type records an applicant’s complete acceptable-project set and ranking, funding requirement, and priority class at every project. Applicants within a type are indistinguishable on all those attributes. For instance, a market with tens of thousands of applicants might have a few dozen or a few hundred supported profiles. Project priorities are strict between types, with applicants in the same type treated as tied. Capacities and supervisor endowments scale with the market: if an original market has \(N\) applicants, a capacity \(c_p\) becomes \(c_p/N\), and an endowment \(q_s\) becomes \(q_s/N\). This is the natural version for a high-multiplicity market whose supply of positions and funding grows with its applicant pool.
My anchor is Theorem 4.4, proved in this paper. It says that deciding whether a strongly stable matching exists is NP-complete, even when every supervisor has capacity one and each supervisor is responsible for at most two distinct projects. The authors prove the result here by reducing from a restricted MAX-SMTI problem cited as [21]. This is the paper’s strongest anchor for the continuization programme: it makes the central downstream question whether applicant multiplicity is responsible for the hardness, or whether a mass model retains it.
I would call the mirror Mass Strong Stability Existence. An instance has finite applicant types \(T\), projects \(P\), and supervisors \(S\). It gives rational type masses \(\mu_t\), summing to one; a strict acceptable-project ranking for each type; project capacities \(\bar c_p\); per-capita supervisor budgets \(\bar q_s\); and the supervisor-project incidence structure. Each project also ranks the types it accepts. All numeric inputs are binary rationals.
A candidate solution gives assignment masses \(x_{t,p}\geq 0\) and \(x_{t,\bot}\geq 0\), where \(\bot\) denotes unmatched. They must satisfy
\[
x_{t,\bot}+\sum_{p\in P}x_{t,p}=\mu_t,\qquad
\sum_{t\in T}x_{t,p}\leq \bar c_p.
\]
Only acceptable type-project pairs may receive positive mass. The interpretation is that each individual gets an integral assignment, but members of a type may be divided across projects in the aggregate. A feasible funding allocation \(z_{s,p}\geq 0\) must also exist, with \(z_{s,p}=0\) when supervisor \(s\) does not supervise \(p\), and
\[
\sum_{s:\,p\in P_s}z_{s,p}=\sum_{t\in T}x_{t,p},\qquad
\sum_{p\in P_s}z_{s,p}\leq \bar q_s.
\]
Thus every unit of assigned applicant mass receives one unit of funding, just as in the paper.
For stability, consider a type \(t\), a source assignment \(r\in P\cup\{\bot\}\) with \(x_{t,r}>0\), and a project \(p\) that \(t\) prefers to \(r\). This is a blocking move if \(p\) has spare capacity or strictly prefers \(t\) to a type currently assigned there. Extend the paper’s strong-stability condition to these moves: every type currently assigned to \(p\) must be at least as high in \(p\)’s priority order as \(t\), and moving any positive mass \(\varepsilon\leq x_{t,r}\) from \(r\) to \(p\) must make the resulting assignment infeasible, even after reallocating supervisor funding. The question is whether a strongly stable mass assignment exists. A yes-solution is the assignment masses and funding allocation; the finitely many possible mass transfers can be checked with linear feasibility tests.
For this mirror, my working prediction is tractability in the intended low-support regime, rather than automatic transfer of Theorem 4.4’s NP-hardness. Atomless cohorts can split, so the all-or-nothing choices in the discrete reduction may no longer work. That makes an algorithm polynomial in the number of projects, supported types, and input bit length a sensible target, likely requiring more than a direct LP because stability introduces choices about which moves are blocked. The classification should test whether fractional splitting removes the reduction’s hardness; if hardness survives, one must identify whether it comes from the growing preference structure or from genuinely continuous feasibility.
The mirror covers only Theorem 4.4’s existence problem for strong stability. It does not claim to continuize the paper’s weak-stability algorithm or fair funding-allocation result.
The main weakness is the type restriction. The paper gives projects preference lists over named applicants, often with strict orders; repeated complete priority profiles are then uncommon. A high-multiplicity version needs applicants in a type to share a priority class, which introduces ties within a class. That is a real co-modification. I think it remains a credible mirror because it preserves the paper’s matching, budget, capacity, and blocking concepts while making the population genuinely continuous. The mirror should be judged on that explicit cohort regime, not on whether every arbitrary named-applicant instance can be grouped into a few types.
Theorem 4.4 is the right anchor: the paper proves a named computational result, and a large internship or hiring market with repeated applicant profiles is a plausible high-multiplicity setting. Types could include preferences, funding needs, and priority classes; capacities and budgets could scale per capita. The proponent has addressed the obvious grouping objection.
The harder problem is the theorem’s definition of strong stability. It tests whether adding one applicant to a project and removing that applicant’s old match makes the matching infeasible. In a nonatomic population, one person has zero mass. Changing that person’s assignment leaves the aggregate assignment and funding constraints unchanged, so the feasibility test cannot register the deviation. Under that interpretation, strong stability loses the role funding constraints play in Theorem 4.4.
The proposed repair—test whether *any positive mass* can move—does produce a coherent question, but it changes the unit of deviation from an applicant to a cohort. Its result can depend on whether there is any slack at all: a continuous cohort can use arbitrarily small positive slack, while a finite market can use slack only if it covers at least one applicant. For example, if a project has per-capita slack \(\delta>0\), the continuous test allows a move of some \(\varepsilon\leq\delta\); in a market with \(N\) applicants, an individual move needs slack of at least \(1/N\). A fixed minimum cohort size would avoid that threshold, but adds a parameter the paper’s problem does not have.
So the obstacle is not that the hardness answer might change. It is that preserving individual blocking makes the feasibility condition vacuous in the limit, while preserving feasibility effects requires a new collective-blocking notion and a choice of deviation scale. The paper does not supply a canonical choice, and changing the type space cannot remove that issue.
This is a case against treating Theorem 4.4 as a ready continuous mirror, not proof that the mass-blocking problem lacks value. If the authors regard positive-mass blocking as their problem, it could be worth studying. The material here does not establish that they would reject it, so the negative case remains weaker than the proponent’s explicit, plausible formulation.
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.