d4-conf-sagt-2016-0021

The strongest mirror I can defend is Stable Roommates with Ties at Continuum, based on Theorem 12, proved in this paper. The theorem says that deciding whether an instance of \(3\)-srti has a stable matching is NP-complete, even when every preference list has length at most \(3\). The authors prove it by reduction from \((2,2)\)-e3-SAT. In full, the discrete problem takes an undirected acceptability graph and, for each agent, an incomplete preference list of at most three acceptable agents, with ties allowed; it asks whether there is a matching with no blocking edge.

Here is a continuous version of that question. Let \(T\) be a finite set of agent types. A type records the features relevant to pairing and gives a weak ranking of at most three acceptable partner types. Compatibility is symmetric. The society is specified by rational masses \(\mu_t\geq 0\), with \(\sum_{t\in T}\mu_t=1\). Let \(q_{tu}=q_{ut}\geq 0\) be the mass of type \(t\) paired with type \(u\), for each compatible pair. Require \(\sum_{u:\{t,u\}\text{ compatible}}q_{tu}\leq\mu_t\); the remaining mass is unmatched.

For a compatible pair \(t,u\), let
\[ B_t(u)=\mu_t-\sum_{v:\,v\succeq_t u}q_{tv}, \]
where \(v\succeq_t u\) means type \(t\) ranks \(v\) at least as highly as \(u\). Thus \(B_t(u)\) is the mass of type \(t\) that is unmatched or strictly prefers \(u\) to its current partner type. Call \(q\) stable if, for every compatible pair, \(B_t(u)=0\) or \(B_u(t)=0\). This rules out a positive mass on both sides that would strictly prefer to pair with one another. The continuous problem asks whether such a stable mass assignment exists. A solution is the table \(q\). The input and running time are naturally described by the support size \(\tau=|T|\) and the bit length \(L\) of the masses.

A plausible high-multiplicity setting is a large seasonal workforce or intern cohort housed in pairs. Many people share standardized profiles—such as shift, language, and sleep schedule—and rank at most three compatible profiles. There may be tens of thousands of people but only dozens of profiles. Every unit of mass still represents people being paired one-to-one; it is the population that is continuous, not the set of outcomes. Since the paper’s problem already allows ties, treating members of a type as interchangeable and ranking partner types is a natural high-multiplicity interpretation. The preference-list bound and the mutual-improvement definition of stability both remain central to the question.

My tentative forecast is Class B: hardness transfers. The SAT choices in the paper’s reduction are encoded in the compatibility and preference structure, so they appear to live in the type graph rather than in the number of repeated copies of an agent. But Theorem 12 does not prove hardness for this mirror: its gadget vertices are distinct, and continuous mass assignments can split a type across several partner types. Showing that such splitting cannot wash out the SAT choices—or finding a gap-preserving transfer argument—is a central follow-up question. Related questions are whether stable mass assignments always exist at degree \(2\), whether feasibility is polynomial-time solvable or hard in \(\tau\) at degree \(3\), and when a mass solution corresponds to a discrete stable matching of cloned agents.

The weakest point is the aggregation itself. The mirror ranks partner *types*, with members of each class interchangeable; the paper ranks named agents in a graph that can have arbitrary individual-level structure. The workforce scenario makes that aggregation plausible, and the tie variant gives the authors a natural language for it, but it does not make the paper’s reduction carry over automatically. This case covers only Theorem 12’s stable-matching existence question; it does not claim a mirror for egalitarian costs or most-stable matching.