d4-conf-atal-2013-0207

The lead anchor is Theorem 1, proved in this paper: for marriage games, deciding whether a Nash-stable matching exists is NP-complete. A marriage game has two sides; each agent ranks the agents on the other side, and a matching leaves some agents single. The paper allows ties and unacceptable partners. Its proof reduces MinimumMaximalMatching to this existence question.

A plausible high-multiplicity setting is a large internship or residency placement market: many applicants and one-person placement slots, grouped by their complete preference profiles. Applicants in one type rank slot types the same way; slots in one type rank applicant types the same way. A type includes every feature that affects preferences, including acceptability. This is credible when \(N\), the number of agents, is very large while the number \(\tau\) of distinct types is much smaller. The paper itself points to resident–hospital matching as an application, though the mirror here keeps one-to-one slots.

I would ask the authors to consider Typed Continuum Nash-Stable Marriage Existence. An instance gives applicant types \(I\), slot types \(J\), rational masses \(\mu_i,\nu_j\ge 0\) with total mass \(1\), and each type’s weak ranking over opposite-side types and being single, denoted \(\bot\). A nonnegative matrix \(x_{ij}\) specifies the mass of type \(i\) matched to type \(j\), subject to \(\sum_j x_{ij}\le\mu_i\) and \(\sum_i x_{ij}\le\nu_j\). The residual masses are \(a_i=\mu_i-\sum_jx_{ij}\) and \(b_j=\nu_j-\sum_ix_{ij}\).

The question is whether there is such an \(x\) with no profitable unilateral deviation. In particular, a type-\(i\) applicant assigned positive mass to type \(j\) must not prefer being single or any type \(k\) with \(b_k>0\) to \(j\); the symmetric condition applies to slots. An unmatched applicant type \(i\) must not prefer any unmatched slot type to being single, and symmetrically for unmatched slots. These conditions preserve the paper’s Nash notion: the recipient need not consent, and the target must be unmatched because joining an already matched pair would make an infeasible three-person coalition. The problem is a feasibility decision, with \(x\) as its solution; there is no welfare objective in Theorem 1 to add.

This is a continuous-population question rather than a fractional-outcome question. The population is represented by masses, and the matching decision distributes those masses across type pairs. The individual deviation rule remains pointwise: whenever both the relevant matched mass and unmatched target mass are positive, an agent of the relevant type can make the deviation. For rational data, a feasible mass matrix can be taken rational. Scaling by a common denominator then gives an ordinary matching in a sufficiently large replicated population with the same type proportions; conversely, any matching in such a replication gives a feasible mass matrix. Thus “yes” means that some high-multiplicity replication admits a Nash-stable matching, not necessarily that the original finite electorate does.

For this mirror, I expect tractability parameterized by support size \(\tau\). Guess which types have positive unmatched mass. Once those sets are fixed, the stability rules forbid certain type-pair assignments, and the remaining mass-balance conditions are linear. Requiring each guessed unmatched mass to be positive can be handled by maximizing a common lower bound in an LP. Enumerating the unmatched-type sets gives a \(2^\tau\operatorname{poly}(\tau,L)\)-time algorithm, where \(L\) is the input bit length. That is polynomial when \(\tau\) is fixed and FPT in \(\tau\). I am not claiming polynomial time when \(\tau\) is unrestricted.

The discrete hardness does not automatically transfer. The paper’s reduction encodes a graph in individual preference lists, and fractional mass assignments may create stable allocations where no matching existed at the original population size. The reduction therefore does not by itself prove hardness for this mirror. Its graph structure may still yield hardness as \(\tau\) grows, which is a natural further question, alongside whether the exponential dependence on \(\tau\) can be removed and how the mass solution relates to finite instances at a fixed population size.

The weak point is that a referee could regard the ability to split a type’s mass across partners as a substantial change from the indivisible matching in Theorem 1. I think the mirror survives that objection because it asks the same existence question, with the same unilateral stability rule, for a plausible market in which agents of each type are genuinely exchangeable. The paper’s NP-hardness remains the anchor; determining whether its obstruction disappears under high multiplicity is exactly the question this mirror puts to a prover.