| paper | Strategic Aspects of Stable Matching Markets: A Survey |
| authors | Hadi Hosseini, Shraddha Pathak |
| venue | IJCAI 2024 |
| filed under | coalition · matching |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
The survey has no numbered Theorem, Lemma, Corollary, or Proposition asserting a complexity or algorithmic result; its numbered items are Open Problems, while the algorithmic claims are unnumbered summaries of cited work. Thus bit (a) fails independently of whether the proposed typed mass model is a sensible extension. The opponent wins clearly on this objective criterion, although its identity-versus-mass objection is not needed to reject the paper.
fails bit a — no named computational result to mirror
The only proposed anchor is an unnumbered report of Shen et al.'s external algorithm, so it fails the paper-level anchor rule.
fatal: True
The proposed mirror covers only coalitional permutation manipulation under men-proposing DA; it leaves truncation, dropping, accomplice, one-for-all, two-for-one, bribery, control, manipulation games, fairness, domain restrictions, approximation, and experimental results untouched.
Strictly, this paper contains no eligible anchor under your rule. It has no numbered Theorem, Lemma, Corollary, or Proposition; the numbered items are Open Problems. Its computational claims are unnumbered summaries of results proved elsewhere. I therefore cannot honestly quote a theorem number or claim that any complexity result is proved here.
The strongest salvage is a conditional anchor: Section 3.1 reports that Shen et al. [2021] give a polynomial-time algorithm for optimal coalitional permutation manipulation of the men-proposing DA mechanism. This is cited from elsewhere, not proved in the survey, and has no number in the paper.
My lead mirror would be Continuum Coalitional Permutation Manipulation for DA.
There are finite sets \(P\) and \(Q\) of man-types and woman-types. A type includes the agent’s complete ranking over types on the other side, together with every other parameter relevant to the mechanism. The two populations have mass distributions \(\mu\in\mathbb{Q}_{\ge 0}^{P}\) and \(\nu\in\mathbb{Q}_{\ge 0}^{Q}\), each summing to \(1\). The typed men-proposing DA algorithm returns a mass matching \(x_{pq}\), where \(x_{pq}\) is the mass of type-\(p\) men matched to type-\(q\) women.
Choose a set \(S\subseteq Q\) of manipulating woman-types. Each type \(q\in S\) may replace its truthful ranking by a reported permutation \(r_q\). Running typed DA on these reports produces \(x^{R}\), where \(R=(r_q)_{q\in S}\). The manipulation is feasible if:
The computational task is to find a Pareto-maximal feasible report vector \(R\), or to decide whether a prescribed collection of partner-mass thresholds is attainable. A solution consists of the reports \(R\), the resulting mass matching \(x^{R}\), and verification of the no-regret, improvement, and truthful-stability conditions.
This is a genuine high-multiplicity version of the paper’s coalitional manipulation problem. The relevant regime is, for example, national residency or school choice: many thousands of applicants and positions, but relatively few recurring preference and priority types. A type may represent a large cohort of applicants with the same ranking, eligibility constraints, and reporting costs. The continuous object is the applicant and position populations themselves, not merely the fractional matching outcome. Rational masses recover ordinary markets by replication: \(N\mu_p\) and \(N\nu_q\) agents of each type.
I would expect this mirror to be Class A, although that is a conjecture rather than a theorem. The anchor’s polynomial algorithm relies on structural properties of DA manipulation—coalitional reports can be reduced to controlled, inconspicuous changes, and stable outcomes form a lattice. In the typed setting, individual counts become mass variables, and rejection chains should become finite linear or flow constraints over types. That suggests a column-generation or network-flow formulation rather than a fundamentally new combinatorial problem.
The main further questions are whether an optimal mass manipulation always has an inconspicuous type-level representative, whether arbitrary splitting of one true type across several reports changes tractability, and whether the algorithm is polynomial in \(|P|+|Q|\) and the encoding length of \(\mu,\nu\). If report permutations create an uncontrolled pricing problem, this could instead become continuum-specifically hard.
The weakest point is unavoidable: the paper’s result concerns coalitions of named agents, whereas the mirror replaces them by positive-mass type blocks. That changes the strategic unit, and the survey does not establish that its polynomial algorithm survives this passage. Still, the change is exactly the high-multiplicity move: identical agents are grouped because the problem treats them identically. I would therefore defend this as a plausible continuous research problem, while reporting formally that the paper itself supplies no numbered computational anchor.
The decisive negative point is that this survey supplies no eligible computational anchor. It contains no numbered theorem, lemma, corollary, or proposition asserting a complexity or algorithmic result. The numbered items are Open Problems. The claimed polynomial-time algorithm is merely an unnumbered report of Shen et al.’s external result. The proponent’s threshold-attainment problem and “Pareto-maximal report vector” are newly invented computational tasks, not problems formulated or solved by this paper.
Even setting that source objection aside, the proposed mirror does not preserve the paper’s strategic object. In the paper, a manipulation is performed by a set \(A\) of named agents for a set \(B\) of named beneficiaries. Its success is pointwise: every \(i\in B\) must weakly prefer the new individual partner, with at least one strict improvement. A matching \(x_{pq}\) between types records only aggregate mass. It cannot say which woman received which man, or whether the particular agents in \(A\) and \(B\) improved.
This is not repaired by saying that a type includes all relevant information. If two women have the same preference type but only one manipulates, manipulator status is itself a relevant parameter, so they are different types for this problem. A finite instance with \(k\) otherwise identical women can contain any subset of them in \(A\) or \(B\); a fixed type-mass description cannot recover those choices. If one refines types into “truthful,” “manipulating,” and “beneficiary” cohorts, the type space depends on the selected coalition. If instead a fraction of one type may report differently, the model has changed the strategic action from an individual coalition to a divisible mass coalition.
The rational-clone test exposes the mismatch. Clearing denominators in a mass instance produces clones in which an entire type block submits the same report. It does not recover the original problem where an arbitrary subset of named clones manipulates. Conversely, encoding every possible subset requires identity- or coalition-dependent type refinement, defeating the fixed finite type regime. The proponent’s proposed stochastic-dominance condition over partner distributions is also new: original agents receive individual partners, not lotteries over partner types.
The best repair would be a genuinely anonymous continuum matching model: preference types rank counterpart types, DA is defined on matching measures, and one optimizes the mass of agents improved by a coordinated report flow. That could be an interesting new mean-field or high-multiplicity matching problem. But it is an extension or re-modelling, not a continuous mirror of Shen et al.’s coalitional permutation manipulation. Its algorithmic structure is not supplied by the cited polynomial algorithm: the latter’s inconspicuousness and lattice arguments concern selected named agents and individual preference permutations, whereas report splitting, measure-valued matching, and stochastic welfare introduce new objects.
I would not object to the residency or school-choice story itself. Large matching markets can plainly have repeated preference and priority types, and existing large-market work supports that regime. The objection is narrower: the paper’s strategic predicate is identity-sensitive, while its proposed continuum forgets exactly the identities that determine manipulation. Thus the paper should fail ChoCo’s anchor test, although the stronger universal claim that no worthwhile continuous matching problem could ever be built from this area would be overstated.
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.