| paper | d4-conf-sagt-2022-0007 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: \(\mathrm{P}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
For the men-side variant, fix \(k\), all matching agents’ preferences other than \(\hat m\)'s, a target \(w^\star\), and an honest-mass distribution \(\mu\) over rankings \(\pi \in \mathcal R(W)\) with total mass \(1-\rho\) and support size \(\tau\), where \(\rho \in (0,1]\). Does there exist a report-mass distribution \(x_\pi \ge 0\), with \(\sum_{\pi \in \mathcal R(W)} x_\pi = \rho\), such that the Borda scores \(S(c)=\sum_{\pi \in \mathcal R(W)}(\mu_\pi+x_\pi)(k-\operatorname{pos}_\pi(c))\), ordered using the paper’s lexicographic tie-break, give \(\hat m\) the match \(w^\star\) under men-proposing Gale–Shapley?
The team’s voters are ranking types \(\pi \in \mathcal R(W)\). Honest voters carry mass \(\mu_\pi\); the coalition chooses report masses \(x_\pi\) totaling \(\rho\). Their combined Borda scores determine \(\hat m\)'s preference order, which feeds into Gale–Shapley with all other preferences fixed. The decision question is whether some feasible \(x\) yields the target match.
The mirror covers the coalitional hardness questions in Theorems 3 and 6; it leaves the single-manipulator algorithms in Theorems 2 and 5 and the additive guarantees in Theorems 4 and 7 aside.
The cleanest mirror sits inside the team: make the team’s voter population continuous while leaving its matching role intact. A type is a member’s complete ranking of the possible partners. This fits the paper’s setup directly: members already vote over partners, Borda turns their ballots into the team’s ranking, and that ranking feeds into Gale–Shapley.
For a concrete regime, take a large student cohort or professional consortium that is treated as one matching agent and matched to one of \(k\) counterparties. Suppose many members share rankings because they belong to the same study tracks or professional groups. If the team has \(N\) members and only \(\tau\) distinct rankings, with \(\tau \ll N\), its ballot profile is naturally a distribution over ranking types. A coalition united around one desired match has mass \(\rho\), rather than a list of individually counted voters. This makes the population inside one team continuous; it does not make the matching agents, bundles, or outcomes fractional.
My lead anchor is Theorem 3, proved in this paper. It says that coalitional MnM-m is NP-complete, even with two manipulators: given a man \(\hat m\), the honest voters’ ballots \(L\) for his team, the preferences of the other men and all women, a coalition \(R\), and a target woman \(w^\star\), decide whether the coalition can report ballots \(L_R\) so that Borda’s team ranking and the M-proposing Gale–Shapley algorithm match \(\hat m\) with \(w^\star\). The proof reduces from Permutation Sum, whose NP-completeness the paper attributes to [24]. The construction makes the two manipulators’ Borda position scores encode permutations whose coordinatewise sums must equal the given integers.
The corresponding continuous question is Continuous Men-side Team Coalition Manipulation (C-MnM-m). Let \(\mathcal R(W)\) be the strict rankings of the \(k\) women. Its input consists of \(k\); the preferences of all matching agents other than \(\hat m\); a rational honest-mass distribution \(\mu\) over \(\mathcal R(W)\), with total mass \(1-\rho\) and support size \(\tau\); a rational coalition mass \(\rho>0\); and a target \(w^\star\). Choose nonnegative report masses \(x_\pi\), one for each \(\pi\in\mathcal R(W)\), satisfying \(\sum_\pi x_\pi=\rho\). The resulting Borda score of woman \(c\) is
\[
S(c)=\sum_{\pi\in\mathcal R(W)}(\mu_\pi+x_\pi)\bigl(k-\operatorname{pos}_\pi(c)\bigr),
\]
with the paper’s lexicographic tie-breaking rule. The question is whether some such \(x\) makes the resulting M-proposing Gale–Shapley outcome match \(\hat m\) with \(w^\star\). A solution is the reported mass distribution \(x\). In a finite team of size \(N\), the analogous coalition has \(\rho=|R|/N\). By the dimension of the Borda score vectors, a successful report distribution can be represented using at most \(k\) distinct rankings.
I would expect C-MnM-m to be tractable (Class A), though that is a conjecture about the mirror, not a result of the paper. Continuous coalition mass replaces a pair of indivisible ballots with a convex mixture of rankings. Borda scores are linear in that mass, and linear optimization over rankings has an efficient pricing step: a weighted ranking can be found by sorting candidates by their coefficients. If the GS condition for reaching \(w^\star\) can be expressed through a polynomial-size set of score-order constraints, the mirror becomes an LP with column generation. Establishing that compact description is the prover’s main task.
A second, distinct anchor is Theorem 6, also proved in the paper. It says that coalitional MnM-w is NP-complete, even with two manipulators: given a woman \(\hat w\), the honest ballots \(L\) of her team, the preferences of all men and the other women, a coalition \(R\), and a target man \(m^\star\), decide whether coalition reports can make the M-proposing Gale–Shapley outcome match \(\hat w\) with \(m^\star\). The paper again reduces from Permutation Sum, constructing two manipulative rankings whose position scores encode the required pair of permutations.
Its mirror is Continuous Women-side Team Coalition Manipulation (C-MnM-w). The input and requested report masses are the analogous ones over \(\mathcal R(M)\); the fixed preferences are those of all men and all women except \(\hat w\); and the question is whether some mass distribution of total \(\rho\) makes \(\hat w\)’s Borda-generated ranking yield \(m^\star\) under the same M-proposing Gale–Shapley algorithm. I also expect this version to be tractable, but less confidently: the paper’s own women-side analysis must account for which men propose to \(\hat w\). A promising route is to use the second-best proposer \(m_{nd}\) from Algorithm 3 as a finite case split, then seek linear constraints for each case and a polynomial pricing oracle.
These two anchors cover the paper’s coalitional-manipulation hardness results on both sides of the matching market. They do not claim a mirror for the single-manipulator algorithms or the additive guarantees in Theorems 4 and 7.
The weakest point is that the paper proves hardness for two indivisible manipulator ballots, while the mirror permits arbitrary fractional mass across rankings. Its reduction encodes Permutation Sum in the fact that each manipulator contributes a permutation of position scores; the continuous reports can mix rankings and need not preserve that structure. So the hardness does not transfer automatically. That is also why the mirror is a substantive computational question rather than a restatement: does convexification remove the reduction’s integrality, or does the interaction between Borda’s induced order and Gale–Shapley retain a hard core? If a compact set of GS-relevant order constraints cannot be found, continuum-specific hardness remains possible.
Further questions are to characterize those target-reaching constraints for each proposing side; establish the exact complexity in \(k,\tau\), and the input bit length; and give a discrete-to-continuous dictionary describing when a fractional successful coalition can be rounded to a finite coalition, and what extra mass rounding requires.
The strongest objection is a scaling mismatch. Theorems 3 and 6 establish NP-completeness even with two manipulators. If a team grows while its coalition stays at two people, the coalition’s mass tends to zero, so that limit does not preserve the manipulation problem’s effect. A continuous version with fixed positive coalition mass instead represents a coalition whose size grows with the team. That is a different regime, and the paper’s reductions do not show that its complexity carries over.
That objection does not defeat either mirror. Large associations or consortia could plausibly act as one matching agent while many members vote over its possible partners. Their rankings are natural types, and a coalition with mass \(\rho\) can report rankings to pursue a shared match. The men-side question in Theorem 3 and the women-side question in Theorem 6 both remain meaningful in that setting; the difference in how Gale–Shapley uses each ranking does not make either population incoherent.
Nor does the paper already answer these continuous questions: its voters cast discrete ballots, and its complexity results concern finite coalitions. The convexification may erase the Permutation Sum construction, but that would be a valuable outcome under this programme. Conversely, the proponent’s proposed LP route is only a conjecture: sorting gives a pricing step for Borda scores, but it does not by itself give a compact description of the rankings that lead Gale–Shapley to the target match.
So the negative case is weak. It identifies a real gap between hardness for two manipulators and a positive-mass coalition, but the larger-team scenario supplies a sensible continuous version of both anchors. I cannot honestly rule out a worthwhile mirror for Theorem 3 or Theorem 6.
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.