d4-conf-aaai-2018-0246

There is one credible, narrow mirror, anchored on Theorem 7 (proved here). Given a strong Nash equilibrium report profile \(P'(L)\) and its Gale–Shapley outcome \(\mu\), the theorem says it is super-strong exactly when, for every manipulator \(w\) and every man \(m\) whom \(w\) truly prefers to \(\mu(w)\), some manipulator becomes unmatched after this test deviation: \(w\) truncates her report below \(m\), and every other manipulator who ranks \(m\) above \(w\) removes \(m\). The paper then gives a polynomial algorithm: compute the strong equilibrium, enumerate \(O(n^2)\) pairs \((w,m)\), and run Gale–Shapley in \(O(n^2)\) time for each, for total time \(O(n^4)\). This is the paper’s relevant computational anchor; it has no comparable named hardness result.

My mirror is Continuous Super-strong Manipulation Check for Deferred Acceptance. Consider a large two-sided clearinghouse—say, a labor or residency market—with many applicants and many position units. Each side is a distribution over finitely many types, where a type includes a strict ranking of the opposite-side types and all other attributes the market uses. Members of a type are interchangeable for the matching problem. If \(\mu_a\) and \(\nu_b\) are the rational masses of the two sides’ types, a matching is a mass flow \(x_{ab}\geq 0\), with \(\sum_b x_{ab}\leq\mu_a\) and \(\sum_a x_{ab}\leq\nu_b\); unused mass is unmatched. A mass version of men-proposing deferred acceptance has proposer types apply down their reported rankings, while receiver types retain their preferred offers up to their capacity, splitting mass at a cutoff when necessary.

The problem’s input is those masses and rankings, a set \(K\) of manipulable types on the women’s side, and a candidate report for each type in \(K\). As in Theorem 7, the candidate profile is promised to be a strong equilibrium. The question is whether it is super-strong: can any coalition of positive mass change reports so that every member is weakly better off and positive mass is strictly better off? A deviation may split a type into reported subgroups. To keep the comparison ordinal, certify its benefit by a coupling from deviators’ old partner types to their new ones: no mass may move to a less-preferred type, and positive mass must move to a strictly preferred one. A “no” solution gives the deviating report masses, resulting mass-DA assignment, and such a coupling; a “yes” solution rules out all such deviations. The natural parameters are the number of populated types, ranking length, and bit length of the rational masses.

I expect this question to be tractable, if a finite certificate analogous to Theorem 7’s pair tests survives fractional matching. Mass-DA works over finitely many types, and a deviation is represented by finite report masses and assignment flows; the research task is to show that checking incentives can be compressed to polynomially many tests, or to find the optimization subproblem that prevents it. The main follow-up questions are whether Theorem 7’s certificate extends when a type can split its mass, and whether the rational-mass problem has a clean discrete high-multiplicity dictionary.

This covers only the paper’s result on checking whether a strong equilibrium is super-strong. The authors could plausibly recognize the mirror: it keeps their central objects—deferred acceptance, strategic reports by the women’s side, and coalitional incentives—while asking the same check in a high-multiplicity market with fractional mass assignments. The regime is credible when large cohorts really do share rankings over counterpart types; the number of agents can then be large while the support stays moderate.

The weak point is that Theorem 7’s test depends on individual women and their single W-optimal partners. In the mirror, types can receive distributions over counterpart types, and a deviating coalition can select only part of a type. The certificate may therefore need new ideas, and ranking people by type can erase meaningful individual distinctions. That is a real co-modification of the matching model, but it is also what makes population mass and finite support meaningful here. The proposed problem keeps the incentive question explicit instead of assuming the discrete proof carries over.