| paper | Coalitional Permutation Manipulations in the Gale-Shapley Algorithm |
| authors | Weiran Shen, Yuan Deng, Ping-Zhong Tang |
| venue | ATAL 2018 |
| filed under | coalition · matching |
| judged by | gpt-5.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}\)-hard · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 8
statement extracted from the paper’s text layer
Given finite man types \(A\) and woman types \(B\), rational masses \(\lambda_a\) and \(\mu_b\), strict true rankings, and a coalition \(B_L\), each manipulator type chooses one reported permutation of \(A\) shared by its mass. Run mass Gale–Shapley to obtain truthful and manipulated matching matrices \(X^0\) and \(X\). Decide whether reports exist such that, for every \(b\in B_L\) with \(\mu_b>0\), \(X\) strictly improves on \(X^0\) under a coupling that assigns every manipulated partner type \(a'\) to a truthful partner type \(a\) with \(a'\succ_b a\).
A high-multiplicity, policy-block version of permutation manipulation: types carry mass, reports are common permutations per manipulator type, matching is a mass-flow matrix, and welfare is strict stochastic improvement under a coupling.
The common-report requirement and the coupling-based strict-improvement criterion are substantive type-level modeling choices, and exact equivalence with Gale–Shapley on named replicated agents depends on how within-type priorities are represented.
fatal: False
The mirror covers the strict all-manipulators improvement problem in Theorem 8. It leaves the counting result in Theorem 9 and the rotation-based algorithmic, equilibrium, inconspicuousness, and many-to-one results unmirrored.
The strongest honest case is to anchor on Theorem 8 and propose a high-multiplicity version of exactly its strict-improvement manipulation problem. I would not anchor on Theorem 9: counting a continuum of fractional matchings has no canonical \(\#\mathrm P\) interpretation without adding an artificial discretization.
Theorem 8, proved in this paper rather than cited, states that it is NP-complete to find a permutation strategy profile for the coalition \(L\) of women such that the Gale–Shapley induced matching makes every manipulator strictly better off according to her true preference list. The input has complete strict preferences for all men and women; men report truthfully, every woman in \(L\) may report any permutation of her complete list, and the question is whether some report profile improves every woman in \(L\) over the truthful Gale–Shapley outcome. Membership in NP follows by guessing the reported lists and running Gale–Shapley. The paper proves hardness by reducing from 3-SAT. Each variable gadget forces a binary choice: \(w_{x_i}^{+_2}\) may improve to \(m_{x_i}^{+_1}\) or \(m_{x_i}^{-_3}\), while the symmetric negative-side manipulator has the analogous choices, but the two satisfying branches cannot occur simultaneously. A clause manipulator \(w_{c_j}^r\) improves exactly when at least one of the three literal gadgets takes the branch corresponding to a satisfying literal. Thus all manipulators can improve if and only if the formula is satisfiable. Lemma 16 additionally shows that, in the constructed instances, an all-improving induced matching is stable with respect to the true preferences.
Here is the continuous mirror I would put to the authors.
Call it Continuous Strict-Improvement Permutation Manipulation. There are finite sets \(A\) of man types and \(B\) of woman types. Type \(a\in A\) has a strict ranking \(\succ_a\) over \(B\); type \(b\in B\) has a true strict ranking \(\succ_b\) over \(A\). The instance gives rational masses \(\lambda_a\) and \(\mu_b\), with \(\sum_a\lambda_a=\sum_b\mu_b=1\). A woman type also specifies whether it belongs to the manipulating coalition \(B_L\subseteq B\). A type is complete: its ranking, coalition status, and all other parameters are shared by every member of its mass.
The action is a permutation \(\widehat{\succ}_b\) of \(A\) for each \(b\in B_L\); all mass of that type follows the same reported ranking. This is the natural policy-block regime for the paper’s admissions motivation: identical programme or university slots use one common priority rule or score-bonus policy. Non-manipulator types report their true rankings.
Given the reported rankings, run the men-proposing Gale–Shapley process on masses. An amount of mass of type \(a\) proposes down \(\succ_a\); each woman type retains up to \(\mu_b\) mass of the best proposals under \(\widehat{\succ}_b\), rejecting the rest. The resulting type-level matching is a matrix \(X=(x_{ab})\) with row sums \(\lambda_a\) and column sums \(\mu_b\). The matrix is fractional only because it records what fractions of a type’s population receive each partner type: every individual still receives one integral partner.
Let \(X^0\) be the truthful Gale–Shapley matching and \(X^{\widehat{\succ}}\) the matching under the reported rankings. For each woman type \(b\), compare its truthful and manipulated partner distributions using a coupling. The manipulation strictly improves type \(b\) if there is a coupling between its mass in \(X^0\) and its mass in \(X^{\widehat{\succ}}\) such that every coupled manipulated partner \(a'\) satisfies \(a'\succ_b a\), where \(a\) is the corresponding truthful partner. Equivalently, every infinitesimal member of \(b\) can be reassigned to a strictly preferred partner. The decision problem asks whether there exists a report profile \((\widehat{\succ}_b)_{b\in B_L}\) for which this holds for every positive-mass manipulator type.
This is a genuine population continuization, not outcome-space fractionalization. The society consists of masses of applicants and positions, while matching remains one-to-one at the individual level. A natural regime is a large annual admissions or internship market with many repeated applicant and position profiles: \(\rho\) copies of each role type, with \(N=\rho |A|\) agents per side but only \(|A|+|B|\) distinct types, where \(\rho\) is very large. The type count is determined by preference and policy profiles, not by the number of people. The paper’s Chinese admissions setting makes the common-report assumption especially plausible for groups of institutions or identical programme slots governed by a shared recruitment rule.
There is an exact high-multiplicity bridge in this regime. Rational masses can be expanded into finite numbers of clones, while a finite market with repeated preference profiles compresses to the corresponding type distribution. In particular, the paper’s 3-SAT construction can be replicated \(\rho\) times per role. The variable and clause gadgets remain the same at type level; replication merely scales all masses. The binary choice is made by the report of a role type, not by the identity of one particular person.
I therefore expect this mirror to lie in Class B: hardness transfers. The reduction’s combinatorics live in the variable and clause gadgets, hence in the number of distinct preference types and manipulable policy blocks, not in the number of named agents. If Continuous Strict-Improvement Permutation Manipulation were polynomial in \(|A|+|B|\) and the input bit length, the replicated type-level construction would yield a polynomial algorithm for 3-SAT. Continuization may remove dependence on the huge multiplicity \(\rho\), but it does not remove the underlying Boolean structure.
The weakest point is the uniform-report assumption. A more permissive continuum model could let a positive-mass woman type split among several reported permutations, using variables \(y_{b,\pi}\) for the mass assigned to each report \(\pi\). That relaxation might convexify the paper’s binary gadgets and could become tractable, or it might retain hardness for a subtler reason. It is therefore an important follow-up rather than something I would silently identify with the lead mirror. The proposed policy-block model is still a credible continuous analogue because common ranking policies are institution-level decisions in the motivating application, and the paper itself studies settings where copies of a woman must share a preference list.
Further questions are whether hardness survives the fully split-report model, whether quotas and the paper’s many-to-one extension admit a configuration-LP formulation, and whether the problem is fixed-parameter tractable in the number of woman or man types even though it is NP-hard when that number grows.
The strongest case against the proposed mirror is that Theorem 8’s combinatorics belong to a finite coalition of distinct institutions, not to a population. In the paper’s motivating application, the manipulators are universities. The large population is the student side, while the universities—the agents who act, have quotas, and evaluate whether they are better off—are few and individually identified. Replacing students by masses while retaining named universities does not continuize the manipulation problem. Replacing each university by \(\rho\) identical copies creates a different institutional environment.
That objection becomes sharper because the reduction’s gadgets are not merely preference types; they are distinct strategic roles. A variable gadget, its opposite literal, and a clause gadget must make separate decisions. Replicating each one \(\rho\) times and requiring all copies to submit the same permutation turns each gadget into a policy bloc. The resulting question is whether a mass of identical institutions can adopt one common ranking and improve in aggregate. That is a sensible new matching problem, but it is not obviously the high-multiplicity version of the paper’s coalition game. The paper permits each named woman to choose her own permutation; the proposed mirror imposes a common action precisely because the agents have been merged.
The proposed strict-improvement condition also needs a substantive replacement. In the paper, woman \(w\) has one partner, so “strictly better off” is pointwise. In the continuum, a woman type may receive a distribution of partner types, and the coupling condition compares two distributions by strict stochastic dominance. That is defensible, but it is a new welfare criterion. If instead one lets a type split its mass among several reported permutations \(y_{b,\pi}\), the model becomes a fractional or randomized policy-manipulation problem, again not the paper’s strategic game. Thus the two most natural repairs move in opposite directions: common reports impose an extra collective constraint, while split reports change the action space.
There is also a technical modelling choice hidden in the alleged exact bridge. The paper has strict rankings over named agents. A type-level market has strict rankings over types, but no canonical priority order among individuals of the same type. If within-type tie-breaking is retained, it is additional identity data and can destroy the claimed compression. If it is erased, one has defined a fluid deferred-acceptance model rather than directly replicated Gale–Shapley. That model may be worthwhile, but the reduction does not establish that its outcome or improvement condition is exactly Theorem 8’s.
This is the best negative case, but it is not strong enough to support the universal conclusion requested here. A plausible alternative scenario exists: many repeated programmes or campuses, with identical priority policies and quotas, facing repeated applicant types. In that regime, common reports are genuinely institutional decisions, the matching can be represented by mass flows, and the coupling definition is natural. Replicating the paper’s gadgets then plausibly gives a Class B problem whose hardness lives in the number of distinct types rather than in the replication factor \(\rho\).
The programme explicitly treats such high-multiplicity hardness as a worthwhile outcome, and it forbids objecting merely that the answer remains hard. Nor is there a continuous-population treatment already present in the paper. Consequently, the naturalness and exactness concerns above should be recorded, but they do not defeat the anchor. I could not honestly maintain that no worthwhile continuous mirror exists in any scenario; Theorem 8 remains a credible mirror.
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.