| paper | Bribery and Control in Stable Marriage |
| authors | N. Boehmer, Robert Bredereck, Klaus Heeger, R. Niedermeier |
| venue | SAGT 2020 |
| filed under | coalition · matching |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
parameterized→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete and \(\mathrm{W}[2]\)-hard parameterized by \(k\). It admits an XP algorithm, but no FPT algorithm unless \(\mathrm{FPT}=\mathrm{W}[2]\). · discrete side: parameterized · adjudication: proved
full proof & adversarial review →
Theorem 6
statement extracted from the paper’s text layer
Input finite male-type and female-type sets \(P\) and \(Q\), rational masses \(\mu^P\) and \(\mu^Q\) of equal total mass, strict rankings of opposite-side types, a target type matching \(\pi\) with \(\mu^P_p=\mu^Q_{\pi(p)}\), and budget \(B\). Choose female types \(S\subseteq Q\), paying \(\sum_{q\in S}\mu^Q_q\), and arbitrarily reorder every member of each selected type. Decide whether the target transport plan \(\nu^\star\), pairing all mass of \(p\) with \(\pi(p)\), is the unique stable transport plan, where stability forbids \(p,q\) with \(\sum_{q'\succ_p q}\nu_{p,q'}>0\) and \(\sum_{p'\succ_q p}\nu_{p',q}>0\).
An anonymous high-multiplicity stable-marriage market whose agents are recurring cohorts with masses, strict type rankings, and identical manipulation status. A feasible outcome is a mass transport \(\nu\), the target is \(\nu^\star\), and reordering a type costs its cohort mass; uniqueness is taken modulo permutations of indistinguishable individuals.
The strongest objection is that type-level uniqueness quotients individual permutations and whole-cohort reordering is a batch operation absent from the original theorem, so exact high-multiplicity equivalence is not automatic.
fatal: False
The mirror covers Theorem 6's \(\mathrm{W}[2]\)-hardness, stable-before-manipulation promise, and one-sided restriction; it leaves the paper's other goals, actions, algorithms, approximations, and hardness results unmirrored.
The strongest positive case is a cohort-level mirror of the paper’s Theorem 6, which I would treat as the lead anchor.
Theorem 6, proved in this paper, states that \(\exact-\uni-\reor\) is W[2]-hard parameterized by the budget \(\ell\). The result remains true even when the designated matching \(M^\star\) is already stable before manipulation and the manipulator may reorder preferences on only one side of the market. The reduction is from Hitting Set: each element \(z\) becomes an element pair \((m_z,w_z)\), each set \(F\) becomes a four-agent gadget \((m_F^1,m_F^2,w_F^1,w_F^2)\), and \(M^\star\) matches every pair internally. Reordering \(w_z\)'s preferences corresponds to selecting \(z\). The reordering makes \(M^\star\) unique exactly when the selected elements hit every set. If some \(F\) is unhit, its gadget can switch partners and remains stable.
A natural continuous version is:
\[ \textsc{C-Exact-Uni-Type-Reorder}. \]
There are male types \(P\) and female types \(Q\), with rational masses \(\mu^P_p\) and \(\mu^Q_q\). Each type is a complete cohort description: all members have the same strict ranking of opposite-side types, the same eligibility and manipulation status, and the same prescribed target partner type. Total male and female mass is equal. The instance also specifies a target type-level matching \(\pi\), with \(\mu^P_p=\mu^Q_{\pi(p)}\), and a mass budget \(B\).
A matching is a transport plan \(\nu\) between the two type populations. It is stable if there are no types \(p,q\) such that
\[ \sum_{q'\succ_p q}\nu_{p,q'}>0 \quad\text{and}\quad \sum_{p'\succ_q p}\nu_{p',q}>0. \]
Thus a blocking pair means that positive mass on both sides could move to one another and improve. The target matching \(\nu^\star\) assigns all mass of \(p\) to \(\pi(p)\).
The permitted manipulation is to choose female types \(S\subseteq Q\) and replace the preference order of every member of each selected type by an arbitrary order. The cost is the mass of the selected cohorts,
\[ \operatorname{cost}(S)=\sum_{q\in S}\mu^Q_q. \]
The question is whether some \(S\) with cost at most \(B\) makes \(\nu^\star\) the unique stable type-level matching.
This is a genuine population continuization. The agents are not named individuals but large recurring cohorts: for example, applicants in a national project or residency market who share the same preference template, eligibility profile, and manipulation policy. A cohort may contain thousands of agents, while the number of distinct preference types is moderate. The intervention is also plausible: an authority changes the submitted preference template for an entire cohort, perhaps through a common counselling or information campaign.
The discrete reduction lifts directly. Replace every agent in Theorem 6’s construction by a cohort of mass \(\rho\). For each element \(z\), use types \(m_z,w_z\); for each \(F\), use the four set-gadget types with the same rankings as in the paper:
\[ m_F^1:w_F^1\succ (w_z:z\in F)\succ w_F^2, \]
\[ m_F^2:w_F^2\succ w_F^1,\qquad w_F^1:m_F^2\succ m_F^1,\qquad w_F^2:m_F^1\succ m_F^2. \]
The target matching pairs corresponding types. Reordering the whole \(w_z\)-cohort moves the relevant \(m_F^1\)-types above \(m_z\). Selecting at most \(k\) cohorts makes the target matching unique exactly when the selected elements form a hitting set. If \(F\) is unhit, the positive mass in its gadget can switch partners, giving a second stable matching.
Hence I would expect hardness to transfer: this is a Class B mirror. The reduction’s combinatorics live in the incidence structure between element and set types, not in the number of individual agents. Blowing every type up from one agent to \(R\) interchangeable agents changes the population size from \(\tau\) to \(R\tau\), but it does not remove the Hitting Set structure.
The mirror is also faithful to the paper’s question. It retains external preference reordering, the one-sided restriction, the designated complete matching, and the requirement of unique stability. Only the population representation changes from individual agents to masses.
The weakest point is the whole-cohort restriction. If one instead allows arbitrary fractions of a type to be reordered at linear per-unit cost, the reduction may fail: an arbitrarily small positive mass of each \(w_z\)-type could potentially destroy every set gadget, defeating the \(k\)-element hitting-set correspondence. That fractional variant is an important follow-up question, but it does not invalidate the cohort-level mirror. In a high-multiplicity market where a preference template is changed administratively for an entire class, whole-cohort reordering is a sensible and recognizable analogue of the paper’s \(\reor\) operation.
The only serious anchor is Theorem 6, but its proposed lift does not survive as a faithful, non-degenerate continuization.
Theorem 6 concerns \(\exact-\uni-\reor\): a named complete matching \(M^\star\) must become the unique stable matching. That uniqueness is identity-sensitive. If every paper agent is replaced by a cohort of \(R\) interchangeable copies, then there are already many distinct individual matchings obtained by permuting partners within corresponding cohorts. Literal uniqueness therefore disappears. The proposed mirror repairs this by quotienting away identities and asking for a unique type-level transport plan. That is a reasonable new problem, but it is not the paper’s uniqueness objective; it changes precisely the feature Theorem 6 studies.
The intervention has the same problem. In the paper, one \(\reor\) operation changes one agent’s preference list. Under high multiplicity, the natural analogue is to reorder an arbitrary mass of a type at proportional cost. Let \(x_z\in[0,\rho]\) be the mass of the \(w_z\)-cohort whose preferences are changed. In the Hitting Set gadget, any \(x_z>0\) is enough: if \(z\in F\), the positive manipulated mass of \(w_z\) blocks the alternative rotation of gadget \(F\). Consequently, whenever a hitting set exists, assigning an arbitrarily small positive mass to each selected \(z\) makes the target type matching unique, with total cost arbitrarily close to zero. The optimum is not attained, and every positive budget collapses the quantitative problem to mere existence of a hitting set.
One can avoid that degeneration by imposing an all-or-nothing rule: changing a type means changing the preferences of its entire cohort. But then the continuous population is doing no computational work. The variables are binary cohort selections, the mass scale can be normalized away, and the construction is simply Hitting Set with every original agent renamed as a type. This is a plausible batch-campaign model, but it is a new collective manipulation primitive, not the high-multiplicity relaxation of the paper’s per-agent bribery.
Thus the anchor faces a forced choice. Preserve agent-level semantics and uniqueness, and multiplicity destroys the objective; use anonymous type-level uniqueness and fractional intervention, and the control problem degenerates; impose whole-cohort activation, and the “continuous” mirror is only a finite type-indexed restatement with a changed action model. A specially motivated cohort-campaign paper could still study that new model, but Theorem 6 does not provide a worthwhile continuous-population mirror of this paper. This negative case is not airtight—the batch intervention is defensible—but it is the strongest obstruction to the proposed anchor.
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.