| paper | d4-conf-ijcai-2020-0684 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | low |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete, hence \(\mathrm{NP}\)-hard; hardness holds already with \(d=1\) and guaranteed feasibility. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite type support \(T\), rational masses \(\mu_\theta>0\) summing to \(1\), attribute vectors \(a_\theta\), and each type’s preferences over acceptable colleges, decide whether there exists a mass assignment \(x_{\theta,w}\ge 0\) satisfying \(\sum_w x_{\theta,w}\le\mu_\theta\), each college’s per-capita capacity \(q_w\), and attribute quota shares \(\ell_{wz}\le\sum_\theta a_\theta[z]x_{\theta,w}\le u_{wz}\), with no positive-mass blocking opportunity. Such an opportunity exists if, for some type \(\theta\), college \(w\), and current destination \(k\in W\cup\{\perp\}\), \(x_{\theta,k}>0\) and \(\theta\) prefers \(w\) to \(k\), and some \(\delta>0\) of that mass can enter \(w\) by removing masses \(0\le y_s\le x_{s,w}\) only from types \(s\) that \(w\) ranks strictly below \(\theta\), while satisfying \(w\)’s capacity and quota constraints after the change. As in the paper’s local blocking convention, feasibility at the source college is not checked.
A repeated-type admissions market with rational population masses, overlapping binary attributes, type-level college preferences and priorities, per-capita capacities and quota shares, and mass assignments describing cohorts whose members each receive one college. Stability rules out any positive mass of a type moving to a preferred college when that college can accommodate it by removing only lower-priority mass while meeting its own constraints.
The mirror covers Theorem 1’s stable-existence question and Proposition 1’s stability-audit question; it leaves the paper’s other complexity classifications and parameterized algorithms aside.
There is a credible mirror here, strongest for the paper’s central question: whether a diverse, stable matching exists. I would frame it as a high-multiplicity extension of the paper’s model, rather than claim that its hardness theorem automatically transfers.
The main anchor is Theorem 1, proved in this paper: \(\textsc{SMTI-Diverse}\) is \(\Sigma^P_2\)-complete, and remains \(\Sigma^P_2\)-hard when preferences have no ties, feasible matchings always exist, there are exactly four colleges, and the maximum upper quota is \(3\). That is a particularly good anchor because the result concerns the existence of a stable matching with overlapping diversity constraints, not just a special encoding or an algorithmic side condition.
A plausible regime is a large centralized college-admissions market: millions of applicants, but far fewer distinct combinations of college preferences, overlapping demographic or socioeconomic attributes, and college priority tiers. Each such combination is a complete student type. Colleges rank these types, with ties among applicants in the same priority tier. The number of people \(N\) is much larger than the support size \(\tau\). Capacities and quota bounds are expressed as shares of the applicant population, so they remain meaningful as the market grows.
I would call the resulting problem Stable Diverse Mass Matching. An instance gives supported types \(T\), rational masses \(\mu_t>0\) summing to \(1\), and for each type \(t\), an attribute vector \(a_t\in\{0,1\}^d\) and a preference order \(\succ_t\) over acceptable colleges. Each college \(w\) has a weak priority order over types, a per-capita capacity \(q_w\), and lower and upper quota shares \(\ell_{wz},u_{wz}\) for every attribute \(z\in[d]\). College priorities are part of the complete type information: applicants grouped into one type are interchangeable in every respect the problem uses.
A candidate solution is a mass-assignment matrix \(x_{t,w}\ge 0\), with any unassigned mass left unmatched. It is feasible when
\[
\sum_w x_{t,w}\le \mu_t,\qquad
\sum_t x_{t,w}\le q_w,\qquad
\ell_{wz}\le\sum_t a_t[z]x_{t,w}\le u_{wz}
\]
for every type, college, and attribute.
The stability test keeps the paper’s pairwise blocking idea and its local feasibility convention. A type \(t\), college \(w\), and current destination \(k\in W\cup\{\perp\}\) form a mass-blocking opportunity if \(x_{t,k}>0\), type \(t\) prefers \(w\) to \(k\), and some \(\delta>0\) of that mass can enter \(w\), while the college removes mass \(y_s\) only from types it ranks below \(t\), so that \(w\)’s new capacity and quotas are satisfied. As in the paper, this test checks feasibility at the deviating college; it does not add a new check on the college from which the incoming mass departs. A stable mass matching is a feasible \(x\) with no such opportunity.
The mass matrix does not give any applicant a fractional assignment: it describes how a nonatomic cohort is divided among colleges, with each person assigned to one college. Positive-mass deviations are the natural extension of the paper’s individual blocking pair once a single person has zero mass and cannot change a quota. That extension should be stated plainly; it is part of the model, not a consequence of Theorem 1.
For this existence problem, my tentative expectation is continuum-specific difficulty (Class C), but with low confidence. For a fixed \(x\), each proposed block can be checked by a linear program over \(\delta\) and the removable masses \(y_s\). The harder question is choosing one global \(x\) that satisfies all quotas and defeats every possible block. Overlapping quotas and the stability constraints leave room for hard interactions there. But I would not claim hardness transfer: the theorem’s reduction uses discrete matching choices, and allowing each type’s mass to split may destroy its logical gadgets. Nor would I rule out a tractable formulation.
A second, cleanly separate anchor is Proposition 1, proved in this paper: deciding whether a given feasible matching has no blocking pairs, or has no \(d\)-blocking pairs, is coNP-hard. The corresponding continuous question is Stable Mass Audit: given rational instance data and a feasible rational assignment \(x\), decide whether \(x\) is stable under the mass-blocking definition above. This one has an expected Class A answer. For every relevant type, college, and source destination, maximize \(\delta\) subject to the college’s capacity and quota constraints and the bounds on removable lower-priority mass. These are rational linear programs. A positive optimum is a block; if every such program has no positive feasible \(\delta\), the assignment is stable. There are only polynomially many such checks in \(m\) and \(\tau\), with the LP size polynomial in the input dimensions. This would be a concrete case where the discrete subset search behind a blocking witness becomes a continuous optimization problem.
The mirror’s weakest point is the gap between those two versions of stability. In the paper, a blocking witness is a subset of named students; here it is a removable vector of type mass. The theorem’s \(\Sigma^P_2\)-hardness does not survive that change automatically. A decisive follow-up is to establish a finite-to-continuous dictionary: when does a stable mass matching correspond to a high-multiplicity finite matching, and when does mass splitting create a stable solution absent from every integral clone instance? Any claim of transferred hardness or tractability should settle that fractional escape route. A bit-model classification should also say whether a yes instance always has a polynomial-size rational assignment.
This case covers Theorem 1’s stable-existence question and Proposition 1’s stability-checking result. The authors should recognize the first as their core diverse-and-stable matching question in a repeated-type market, while recognizing that the positive-mass blocking rule is an explicit continuum extension. It does not try to mirror the paper’s entire complexity table.
The strongest case against the proposed mirror is that Theorem 1’s hardness is tied to atomic choices. Its reduction encodes assignments by choosing which named literal students go to a college, then uses a possible blocking subset to represent the universal quantifier. In a mass assignment, a type can split across colleges, and blocking witnesses become fractional removal vectors. The theorem therefore supplies no discrete-to-continuous correspondence, and the resulting existence problem may be a new stability model rather than a limit of the paper’s problem. Whether that new model has a simple algorithm or hard global interactions is open.
That objection weakens further against the proponents’ better scenario. Complete types can include college-priority tiers, so a large applicant pool with repeated attributes, preferences, and priority tiers is a credible high-multiplicity regime. Requiring tiers means the mirror does not retain the theorem’s no-ties restriction, but ties are allowed in the paper’s general problem. Fractional splitting and the need for a finite-to-continuous dictionary are research questions, not reasons to dismiss the mirror under the programme’s criteria.
Proposition 1 is harder to defeat. The paper proves that auditing a given feasible matching for stability is coNP-hard. For a rational mass assignment, a proposed block can be checked by an LP: bound incoming mass by the available mass of the type, allow removal only of lower-priority mass, and enforce the receiving college’s capacity and quota constraints. There are finitely many type–college–source combinations. This is a precise computational question with a plausible repeated-type setting, and it mirrors the paper’s stability audit. Calling it a verifier rather than a full matching algorithm does not dispose of it: checking stability is exactly the proposition’s task.
So the negative case can show that Theorem 1’s \(\Sigma^P_2\)-hardness does not automatically transfer and that the stable-existence mirror needs careful modeling. It cannot honestly eliminate Proposition 1’s mass-audit mirror. Given the instruction that one surviving anchor is enough, I do not see a sound basis for claiming that no worthwhile continuous mirror exists in any scenario.
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.