d4-conf-wine-2014-0010

The strongest mirror I see is Mass Reachability in Correlated Stable Matching. Consider a large two-sided market—say, recurring cohorts of researchers and potential collaborators—where agents fall into a modest number of role and preference types. Every agent in a type has the same preferences over counterpart types, and the value of a match is shared by both sides. That common compatibility score makes the paper’s correlated-preference model plausible. The number of agents can be very large while the number of types, \(\tau\), stays modest.

Here is the continuous problem. Let \(A\) and \(B\) be the types on the two sides, with rational masses \(\mu_a,\nu_b\) summing to \(1\). Let \(E\subseteq A\times B\) be the allowed matches, and let each \((a,b)\in E\) have a positive rational common benefit \(w_{ab}\). Agents rank counterpart types by this benefit, with ties when benefits are equal. A mass matching is a matrix \(x\geq 0\) satisfying \(\sum_b x_{ab}\leq\mu_a\) and \(\sum_a x_{ab}\leq\nu_b\). Each individual still has at most one partner; \(x_{ab}\) is the mass of agents paired across those two types.

The instance also gives an initial mass matching \(x^0\) and a stable target \(x^\star\). At a state \(x\), the mass of type \(a\) willing to match with \(b\) is
\[ W_a(b;x)=\mu_a-\sum_{b':\,w_{ab'}\geq w_{ab}}x_{ab'}. \]
This counts agents who are unmatched or currently matched to a strictly less preferred type. Define \(W_b(a;x)\) symmetrically. The target is stable when no allowed pair has positive willing mass on both sides.

A legal step chooses \((a,b)\) with \(W_a(b;x)>0\) and \(W_b(a;x)>0\), selects the same positive rational mass \(\delta\) from each willing pool, breaks their old matches, and matches that mass across \((a,b)\). The question is whether a finite sequence of such steps takes \(x^0\) exactly to \(x^\star\). Its computational complexity is measured in \(|A|+|B|\), \(|E|\), and the input bit length \(L\). This keeps the paper’s discrete blocking-pair dynamics and specified-target question. Only the population becomes continuous; fractional edge mass records many individually integral matches.

My anchor is Theorem 3, item 4, proved in this paper. It says that, for ordinary bipartite stable matching with correlated preferences and ties, it is NP-complete to decide whether a sequence of improvement steps leads from a given initial matching \(M_0\) to a given stable matching \(M^\star\). The authors prove this via their reduction in Appendix A.5; Theorem 2 supplies the polynomial-size reachability certificate used for membership in NP. The correlated scores and ties make this a particularly apt anchor: they let a cohort share one preference description without pretending its members have distinct identities.

I would expect the unrestricted mass-reachability problem to be hard for continuum-specific reasons, though that is a conjecture, not a hardness transfer from Theorem 3. The target still imposes an exact endpoint, and the order in which type-pair masses are released and matched may preserve difficult sequencing choices. The paper’s discrete reduction does not establish this: fractional moves could split the mass in its gadgets and create paths absent from the finite instance. Fixed or modest \(\tau\) may well be tractable, which makes the dependence on support size a natural follow-up.

The scope is deliberately narrow: this mirrors the paper’s ordinary bipartite stable-matching reachability result, not its convergence theorems for constrained games or all its preference settings. The weakest point is the gap between the reduction’s individually specified agents and a society of interchangeable cohorts. The scenario makes the high-multiplicity regime credible, but it remains to show whether any meaningful complexity survives aggregation and mass splitting. That gap is the research question, rather than a reason to dismiss the mirror.