Answer: \(\mathrm{NP}\)-hard
Theorem 8 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateIt is NP-complete to find a strategy profile, the induced matching of which is strictly better off for all manipulators.
statement extracted from the paper’s text layer; consult the paper for the exact wording
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\).
Let \(A\) and \(B\) be nonempty finite sets of man and woman types, with positive rational masses satisfying \(\sum_{a\in A}\lambda_a=\sum_{b\in B}\mu_b=1\). Each type has a complete strict true ranking of the opposite side; every partner is acceptable.
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. Here \(\tau=|A|+|B|\) is the support size, not the number of possible types. Put \(m=\max\{|A|,|B|\}\), let \(L\) be the input bit length, and let \(k=|B_L|\) for a specified nonempty coalition \(B_L\subseteq B\). State running times in \(m,\tau,L,k\).
Each coalition type reports one complete permutation of \(A\), shared by its entire mass. Men and women outside the coalition report truthfully.
Mass deferred acceptance is men-proposing: initially all man mass is free; in synchronous rounds, each free portion proposes to its highest-ranked woman type that has not rejected that portion. Each woman type retains up to its mass of the best man types among its held and incoming proposals, according to its reported ranking, and rejects the remainder. A cutoff type may be split; portions of the same type are interchangeable. Rejected portions advance in the next round. Stop when no further proposals are possible.
Write \(X^0\) and \(X\) for the truthful and reported outcomes, where \(X_{ab}\) is matched mass, \(\sum_bX_{ab}=\lambda_a\), and \(\sum_aX_{ab}=\mu_b\).
Strict improvement for \(b\) means there exists \(C^b\in\mathbb R_{\geq0}^{A\times A}\) with \(\sum_{a'}C^b_{aa'}=X^0_{ab}\), \(\sum_aC^b_{aa'}=X_{a'b}\), and \(C^b_{aa'}=0\) unless \(a'\succ_b a\). The decision problem asks whether reports exist giving strict improvement to every coalition type.
Is this continuous coalitional permutation-manipulation decision problem in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?
For finite individual agents with complete strict rankings, deciding whether permutation reports make every coalition woman strictly better off under men-proposing Gale–Shapley is \(\mathrm{NP}\)-complete ([Shen, Deng and Tang](https://www.weiran-shen.info/page_files/coalitional_permutation_manipulations_in_the_gale_shapley_algorithm_aij.pdf)). No result settling exactly the mass problem defined above was identified in the literature search.
Result. The decision problem is \(\mathrm{NP}\)-hard, already when both sides have equally many types and every type has the same mass. The key is that equal masses prevent splitting throughout deferred acceptance, under every permitted report profile.
1. The finite source problem. We use the following known theorem: given equally sized sets of individual men and women, complete strict true rankings, and a specified coalition of women, deciding whether coalition permutation reports make every coalition member strictly better off under men-proposing deferred acceptance is \(\mathrm{NP}\)-complete. These are precisely the hypotheses of Theorem 8 of [Shen, Deng and Tang](https://www.weiran-shen.info/page_files/coalitional_permutation_manipulations_in_the_gale_shapley_algorithm_aij.pdf); their hardness construction has equally many men and women and a nonempty coalition.
We first give a preprocessing construction ensuring that all true rankings on each side are distinct. This makes the reduction valid even if “type” means a preference ranking rather than a labeled category.
Let the source instance have men \(a_1,\ldots,a_n\), women \(b_1,\ldots,b_n\), and coalition \(S\). Add dummy men \(d_1,\ldots,d_n\) and dummy women \(e_1,\ldots,e_n\). Define true rankings as follows:
The cyclic suffixes distinguish all original rankings on the same side. Dummy rankings are mutually distinct because their first choices differ, and differ from original rankings because their first choices are dummy agents.
We claim that this augmentation preserves the answer for every coalition report profile, including reports interspersing dummy and original men.
In the first round, each dummy man proposes to his designated dummy woman. She retains him permanently because he is her first choice. Thus no dummy man ever proposes to an original woman.
No original man can exhaust all original women. Indeed, after an original woman rejects him, she holds an original man and thereafter remains occupied by an original man: she never receives a dummy proposal, and held men do not voluntarily leave. If an original man had been rejected by all \(n\) original women, those women would hold \(n\) distinct other original men, although only \(n-1\) exist. This is impossible.
Consequently, original men never propose to dummy women. For each coalition woman, only the restriction of her report to original men affects the execution. The original agents therefore execute exactly the source deferred-acceptance algorithm with those restricted reports. Conversely, every source report extends to a report in the augmented instance. The truthful outcome also restricts to the source truthful outcome, and true comparisons between original men are preserved. Hence the augmented and source instances have the same answer.
2. Equal masses force unsplit deferred acceptance. Let \(N=2n\) be the number of agents on each side after preprocessing. Turn each agent into one type and assign every type mass \(c=1/N\). Thus
\(\lambda_a=\mu_b=c\)
for every man type \(a\) and woman type \(b\). Each side’s masses sum to one.
Fix any permitted report profile. We prove by induction over synchronous rounds that each man type is either wholly free or wholly held by one woman type, and each woman type holds either nothing or exactly one whole man type.
Initially all man types are wholly free, so the claim holds. Suppose it holds before a round. Each free man type proposes its entire mass \(c\) to one woman type. At any woman, the held and incoming candidates are distinct whole man types, each of mass \(c\). Her capacity is exactly \(c\). With a strict reported ranking, she therefore retains the entire best candidate and rejects every other candidate entirely. No cutoff splits a type. This proves the induction step.
Moreover, the identity of every proposing, retained, and rejected type is exactly that of the corresponding individual agent in synchronous finite deferred acceptance. Thus, writing \(M\) for that finite matching, the mass outcome satisfies
\(X_{ab}=c\) if \(M(b)=a\), and \(X_{ab}=0\) otherwise.
Complete rankings and equal side sizes ensure that the finite matching is perfect: an unmatched man who exhausted every woman would imply that every woman holds another man, contradicting the number of men. Therefore the displayed outcome has all required marginals.
This correspondence applies both to truthful reports and to every coalition report profile.
3. The coupling condition becomes strict partner improvement. Fix a coalition woman type \(b\). Let \(a_0\) be her truthful finite partner and \(a_1\) her reported finite partner. By the preceding argument, her truthful column has mass \(c\) only at \(a_0\), and her reported column has mass \(c\) only at \(a_1\).
Any nonnegative matrix satisfying the prescribed row sums must have every row other than \(a_0\) equal to zero. Likewise, its prescribed column sums force every column other than \(a_1\) to be zero. Hence the only possible coupling is
\(C^b_{a_0a_1}=c\),
with every other entry zero.
Since \(c>0\), this coupling satisfies the required support restriction if and only if \(a_1\succ_b a_0\). Conversely, when \(a_1\succ_b a_0\), the displayed coupling witnesses strict improvement.
Thus the mass problem’s strict improvement condition is exactly the finite problem’s strictly better partner condition on the constructed instances.
4. Reduction correctness and running times. Reports correspond by restricting or extending the original women’s permutations, and the two preceding arguments show that outcomes and strict improvement correspond. Therefore
\(I\text{ is a yes-instance of the finite problem}\ \Longleftrightarrow\ R(I)\text{ is a yes-instance of the mass problem}.\)
All constructed types have positive rational mass, distinct complete strict true rankings, and complete acceptability. Reports remain one permutation per coalition type, shared by its entire mass.
For a source instance of bit length \(\ell\) with \(n\) agents on each side, the construction satisfies
\(m=2n,\qquad \tau=4n=2m,\qquad k=|S|.\)
Its output length and construction time are \(O(\ell+n^2\log(n+1))\), equivalently \(O(\ell+m\tau\log(m+1))\). Each mass \(1/(2n)\) uses \(O(\log(n+1))\) bits.
On this equal-mass subclass, a report certificate uses \(O(km\log(m+1))\) bits. After rank-table preprocessing, truthful and reported deferred acceptance together require \(O(m^2)\) proposal operations, and all coalition improvements require \(O(k)\) comparisons. A conservative bit-time bound for certificate verification is \(O(L+m^2\log(m+1))\).
Consequently, the equal-mass subclass is itself \(\mathrm{NP}\)-complete, and the full rational-mass problem is \(\mathrm{NP}\)-hard. A polynomial-time algorithm in the stated input parameters would therefore imply \(\mathrm P=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The proof resolves the assigned problem: the continuous decision problem is \(\mathrm{NP}\)-hard, and its balanced equal-mass subclass is \(\mathrm{NP}\)-complete. I found no major or minor mathematical issues.
The prover states the source problem precisely: complete strict rankings, men-proposing deferred acceptance, permutation reports by a specified coalition of women, and strict improvement for every coalition member.
This matches Theorem 8 in the cited paper, interpreted under its definitions of the manipulation game and permutation manipulation. Appendix F.1 constructs equally sized sets of men and women, each containing \(6n+2m\) agents, with a specified coalition that is nonempty on the nontrivial source instances used for hardness. Thus the balance, completeness, strictness, and coalition requirements needed by the reduction are satisfied. [Shen, Deng and Tang, preliminaries, Theorem 8, and Appendix F.1](https://www.weiran-shen.info/page_files/coalitional_permutation_manipulations_in_the_gale_shapley_algorithm_aij.pdf).
No additional requirement concerning stability under true preferences is imposed on the source decision problem invoked here.
Every constructed ranking is complete and strict. Original agents retain their original comparisons, and the cyclic dummy suffix distinguishes original agents whose original rankings coincide. Dummy agents have distinct designated first choices. Their first choices also distinguish their rankings from all original rankings on the same side.
The claimed preservation under arbitrary coalition permutations is justified:
The counting argument remains valid with synchronous rounds: at the end of the round containing the last such rejection, every original woman is occupied, and the rejected man is held by none of them.
Therefore original men never reach the dummy suffix of their lists. Restricting coalition reports to original men preserves every relevant comparison and the entire original execution. Conversely, extending a source permutation to a complete augmented permutation is always possible.
The truthful baseline and true comparisons between attainable partners are preserved. Hence preprocessing preserves both yes-instances and no-instances. No gap occurs at \(n=1\); distinctions among multiple original agents are then vacuous.
The induction invariant is strong enough: each man type is wholly free or wholly held by exactly one woman type, and every occupied woman holds one whole man type.
Initially it holds. Under the invariant, every incoming proposal has mass \(c\). A held candidate and incoming candidates are distinct types, since a wholly held type cannot simultaneously be free and propose elsewhere.
A woman with capacity \(c\) and a strict reported ranking retains exactly the whole best candidate whenever candidates exist. Every other candidate is rejected wholly. If no candidate exists, she remains empty. Thus the invariant survives every round, under every permitted report profile.
This establishes the correspondence with synchronous individual deferred acceptance round by round, including proposal histories and rejections. There are at most \(N^2\) proposals, so termination is also ensured.
The perfect-matching argument is valid: an unmatched man at termination would have exhausted all women, each of whom would then hold a distinct other man. Equal side sizes make that impossible. Therefore the displayed mass outcome has the required marginals.
For a coalition type, the truthful column is supported only at \(a_0\), and the reported column only at \(a_1\).
Nonnegativity and the prescribed zero row sums force every other row of the coupling to vanish. The zero column sums similarly force every other column to vanish. The remaining entry must equal \(c\).
Since \(c>0\), the support condition holds precisely when \(a_1\succ_b a_0\). In particular, retaining the same partner fails strict improvement, as required. The proof correctly handles this edge case without replacing strict improvement by weak improvement.
The two report mappings give both directions of the stated equivalence. Crucially, the reverse direction covers all target reports, including permutations that intersperse dummy and original men.
The parameter counts are correct:
\[ m=2n,\qquad \tau=4n=2m,\qquad k=|S|. \]
The augmented rankings contain \(O(n^2)\) entries, each representable using \(O(\log(n+1))\) bits. The masses have the same logarithmic encoding bound. Consequently, the stated construction time and output-length bounds are polynomial and consistent with these parameter identities.
The certificate bound \(O(km\log(m+1))\) is correct. On the balanced equal-mass subclass, verification uses ordinary individual deferred acceptance; the proof does not need to establish a polynomial simulation for arbitrary rational masses.
After preprocessing ranks, the two executions use \(O(m^2)\) total proposal operations, and coalition improvement checks use \(O(k)\) rank comparisons. The stated conservative verification bound \(O(L+m^2\log(m+1))\) accommodates reading and validating the certificate because \(k\leq m\).
Thus membership in \(\mathrm{NP}\) for the stated restricted subclass, together with the reduction, supports its \(\mathrm{NP}\)-completeness. Hardness of that subclass establishes hardness of the full problem.
None. The proof establishes the claimed hardness classification. It does not claim membership in \(\mathrm{NP}\) for unrestricted rational masses, and no such claim is needed to resolve the assigned question.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.