| paper | d4-conf-ecai-2024-0289 |
| 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}\text{-hard}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2
Given finite applicant and position category sets \(I\) and \(J\), rational distributions over applicant types \(t=(i,j_0,\pi)\) and position types \(u=(j,i_0,\rho)\), and a stable incumbent mass coupling \(\kappa\) with those marginals supported only where \(j=j_0\) and \(i=i_0\), may the preference rankings be changed so that the blocking-pair density reaches \(\beta\) within swap budget \(\varepsilon\)? An edit transfers mass only between types with the same own category and incumbent partner category; its cost is transferred mass times Kendall swap distance between rankings, summed over both sides. For edited distributions \(\nu,\omega\), the blocking-pair density is \(B(\nu,\omega)=\sum_{t,u}\nu_t\omega_u\,\mathbf{1}[\operatorname{rk}_{\pi_t}(j)<\operatorname{rk}_{\pi_t}(j_0)\ \wedge\ \operatorname{rk}_{\rho_u}(i)<\operatorname{rk}_{\rho_u}(i_0)]\); the decision question is whether feasible edits of total cost at most \(\varepsilon\) yield \(B(\nu,\omega)\ge\beta\).
A two-sided nonatomic placement market given by rational masses of applicant and position types, where each type records its category, incumbent partner category, and ranking of opposite-side categories. The incumbent matching is a compatible stable mass coupling; edit variables transfer mass between rankings while preserving categories, cost is total mass-weighted Kendall distance, and the objective is the density of mutually blocking applicant-position pairs.
Category-level swaps do not have a canonical cost-preserving translation to swaps among named individuals, and blocking density replaces the paper’s individual pair count.
fatal: False
The mirror covers the worst-case swap question of creating many blocking pairs under a budget; it leaves deletion, pair and agent variants, counting hardness, approximation results, and experiments aside.
The strongest mirror I see is the swap part of Theorem 2, proved in this paper. The theorem says that both Blocking Pairs-Swap-Robustness and Blocking Pairs-Delete-Robustness are NP-complete: given a stable-marriage instance, a matching \(M\), a change budget \(\ell\), and a threshold \(b\), decide whether changes within budget can make at least \(b\) pairs block \(M\). The paper also states that the hardness holds when asking for exactly \(b\) blocking pairs. Its swap reduction is from Clique; its deletion reduction is from Independent Set. I would anchor only on the swap result.
A plausible high-multiplicity setting is a large internship or placement market: many applicants and positions, but only a modest number of recurring applicant and position categories. Members of each category share the preferences and other attributes relevant to the model. For example, an applicant type could include its category, its ranking of position categories, and the category of its partner in the incumbent matching. A market with tens or hundreds of thousands of agents and hundreds or a few thousand such types has many agents per type. Rankings over categories, rather than named individuals, are a genuine co-modification: members of a category are interchangeable for this problem.
Here is the continuous problem I would hand to a prover: Mass-Blocking Robustness under Swaps (lead). Let \(I\) and \(J\) be finite sets of applicant and position categories. A type on either side records its own category, the category of its partner in a given incumbent matching \(M\), and a strict ranking of the opposite-side categories. The instance gives rational type masses \(\mu^M,\mu^W\), each summing to \(1\), and an incumbent matching represented by a mass coupling of those types. Require \(M\) to be stable under the category rankings.
The remaining inputs are a swap budget \(\varepsilon\in\mathbb Q_{\ge0}\) and a target \(\beta\in[0,1]\cap\mathbb Q\). A solution is a mass-transfer plan that changes agents’ rankings by adjacent swaps of categories, preserves each agent’s own category and incumbent partner category, and has total mass-weighted swap cost at most \(\varepsilon\). For resulting type distributions \(\nu^M,\nu^W\), define the blocking-pair density as
\[
B(\nu^M,\nu^W)
=
\sum_{\substack{t=(i,q,\pi),\,u=(j,r,\rho):\\
\pi\text{ ranks }j\text{ above }q,\;
\rho\text{ ranks }i\text{ above }r}}
\nu^M_t\nu^W_u.
\]
This is the fraction of applicant–position pairs that would block \(M\) when one agent is sampled from each population. The question is whether a feasible transfer plan can achieve \(B(\nu^M,\nu^W)\ge\beta\). Its finite high-multiplicity interpretation is a budget of roughly \(\varepsilon n\) swaps and a target of roughly \(\beta n^2\) blocking pairs in a market with \(n\) agents on each side.
This is recognizably the paper’s problem: the incumbent matching stays fixed, an adversary changes preferences, and the objective is to cause instability. The co-modification replaces preferences over named individuals with preferences over interchangeable categories; it does not replace the continuous population with a continuous outcome or a noise model. The mirror covers the paper’s worst-case question about creating many blocking pairs under swaps. It does not claim to mirror the deletion branch, the pair and agent variants, or the paper’s counting and average-case results.
For the unrestricted version, where the category sets are part of the input, my provisional expectation is Class C: continuum-specifically hard. The blocking-density objective is quadratic in the edited masses, so fractional mass changes create a nonconvex optimization problem of their own. Theorem 2’s Clique gadget is a reason to look for hardness, but its discrete NP-completeness does not itself prove hardness here: fractional edits may split the mass that the reduction treats as a choice. A central follow-up is whether that gadget can be made to survive fractional mass, or whether an alternative blocking-mass formulation yields a tractable convex problem. The discrete-to-continuous approximation dictionary is another natural question.
The weakest point is the category-level preference model. The paper uses strict rankings of named agents and counts blocking pairs individually; this mirror ranks categories and measures their pair density. In a replicated finite market, category members are interchangeable, so this amounts to indifference within categories and to swaps between categories as the relevant edit. That is a meaningful high-multiplicity model, but it is a real model change. The case stands if the authors and a referee accept robustness of an aggregate placement as their question; it weakens if swaps between particular named agents are essential to the application.
Theorem 2’s swap result is a real computational result, so the objection cannot be that there is nothing to mirror. The difficulty is that, in the paper’s model, the objects being ranked are the other individual agents. A type must capture everything relevant to whether an edit creates a blocking pair, including how its members rank the named alternatives and how those alternatives compare with their assigned partners. For a complete incumbent matching, each agent has a different partner. In the exact model, that makes the matching itself distinguish agents even when their preference lists look alike; the population does not compress into a fixed set of types with many members each.
The proposed category model avoids that problem by changing what agents rank. But the change reaches into the operation and the objective. Swapping two category labels is one edit to an aggregate ranking; in a finite market, moving two whole blocks of counterpart identities past each other can take many individual swaps, with the cost depending on the block sizes and internal orders. And a block of category pairs contributes a density of blocking pairs, whereas the theorem counts individual blocking pairs. Those are sensible quantities for a new category-level matching market, but there is no canonical high-multiplicity translation that preserves the paper’s swap cost and blocking-pair count.
The strongest setting for that alternative is a labor market with large cohorts of interchangeable employers and workers, each ranking counterpart categories. It is plausible, and may be worth studying in its own right. But it turns on category preferences and cohort-level interventions. The paper’s motivating settings—dating, student placement, and daycare—do not supply that structure automatically, and the employer/worker scenario would need a case that the authors see as their robustness problem rather than a related model. The proponent’s formulation establishes coherence; it does not establish that this paper’s result has a worthwhile continuous mirror.
That is the best negative case I can make, and it is weak at the universal claim. If the authors accept type-level preferences and swaps as the right way to model a large placement market, their Mass-Blocking Robustness question survives. The case against it rests on the gap between that coherent co-modification and the paper’s identity-based intervention—not on a reason the resulting computational question cannot be worthwhile.
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.