Three-Dimensional Popular Matching with Cyclic Preferences

The positive case I would actually defend is a mirror of the paper’s verification problem, anchored on Theorem 4.2, proved in this paper:

It is NP-complete to decide whether a given \(3dpmvi\) instance with a matching \(M\) admits a matching more popular than \(M\), even when preferences are derived from a \(1\)-master list.

I would use no second anchor. Theorem 4.2 is especially valuable because its continuous version has a clear interpretation and a credible algorithmic fate.

Consider a large three-sided service market: users, data sources, and servers, as in the paper’s networking applications. There may be millions of agents in each class but only finitely many operational types: service profile, compatibility requirements, priority template, and so on. A type is a complete preference and acceptability profile over partner types. Let the three type sets be \(\mathcal A,\mathcal B,\mathcal C\), with rational masses \(\mu^A,\mu^B,\mu^C\), each summing to \(1\). Preferences remain cyclic: \(A\)-types rank \(B\)-types, \(B\)-types rank \(C\)-types, and \(C\)-types rank \(A\)-types.

A mass matching is a measurable assignment of population mass to acceptable triples. A matching may split a type across several partner types, since a nonatomic population can be partitioned into subcohorts. This is not a lottery: every infinitesimal agent receives one definite triple.

The precise continuous problem is:

Mass-\(3d\)-Cyclic Popularity Verification. The input consists of the type sets, masses, cyclic preference lists, and a reference mass matching \(M\). The matching \(M\) is represented by finitely many current-partner cells. For example, an \(A\)-cell \(p\) has mass \(r_p\), preference type \(a(p)\), and current \(B\)-partner type \(b^0(p)\), or \(\bot\) if unmatched. Analogous cells \(q\) and \(r\) are supplied for \(B\) and \(C\).

The question is whether there exists another mass matching \(M'\) such that the total mass preferring \(M'\) exceeds the total mass preferring \(M\).

For a type \(x\), define

\[ v_x(z,z_0)= \begin{cases} 1 & \text{if } z\succ_x z_0,\\ 0 & \text{if } z=z_0,\\ -1 & \text{if } z_0\succ_x z. \end{cases} \]

Let \(y_{pqr}\) be the mass of alternative triples formed from \(A\)-cell \(p\), \(B\)-cell \(q\), and \(C\)-cell \(r\). The variables satisfy the mass constraints

\[ \sum_{q,r}y_{pqr}\le r_p,\qquad \sum_{p,r}y_{pqr}\le r_q,\qquad \sum_{p,q}y_{pqr}\le r_r, \]

and \(y_{pqr}=0\) whenever the corresponding type triple is unacceptable.

The vote margin is the linear expression

\[ \Delta(M',M) = K(M)+ \sum_{p,q,r} y_{pqr} \left[ \begin{aligned} &v_{a(p)}(b(q),b^0(p))-v_{a(p)}(\bot,b^0(p))\\ +{}&v_{b(q)}(c(r),c^0(q))-v_{b(q)}(\bot,c^0(q))\\ +{}&v_{c(r)}(a(p),a^0(r))-v_{c(r)}(\bot,a^0(r)) \end{aligned} \right], \]

where \(K(M)\) accounts for agents left unmatched in \(M'\). The answer is YES precisely when the maximum of \(\Delta(M',M)\) is positive.

This is recognisably the paper’s question: same three populations, same cyclic acceptability, same partner-based votes, and the same head-to-head notion of popularity. The only change is that unit agents become divisible mass. In a discrete election with \(N\) agents, a winning margin of \(k\) becomes a mass margin \(k/N>0\).

I expect this continuous problem to be Class A. Once the reference matching is fixed, every agent’s current partner is known. The best defeating alternative is therefore a finite packing/transportation LP with linear objective and linear mass constraints. The number of variables is polynomial in the number of supplied type cells, and exact rational LP methods decide whether the optimum is positive. Thus the NP-complete discrete search for a defeating integral 3-dimensional matching plausibly dissolves into fractional mass transport.

The high-multiplicity regime is credible rather than ornamental. A recurring batch of network requests, data sources, and server slots can contain millions of agents with a small catalogue of repeated service profiles. The paper itself points to networking and resource-allocation applications, and its master-list restrictions strengthen this interpretation: common priority templates are natural in pooled service systems. The relevant object is a fraction of a batch receiving each service pattern, not the identity of the \(437{,}291\)-st request.

This mirror deliberately covers only Theorem 4.2. I would not yet claim that the paper’s existence result, Theorem 4.1, has the same fate. There the reference matching is itself variable, so one must choose \(M\) while ensuring that no alternative mass matching defeats it. That introduces a nontrivial \(\exists M\,\forall M'\) condition, and the resulting problem could be tractable, continuum-specifically hard, or retain discrete hardness. It is an excellent follow-up question, but not needed to establish a credible mirror.

The weakest point is that popularity compares agents with their own current partners. If one retained only aggregate type-to-type mass and discarded the reference-partner cells, popularity would become underdefined once a type is split across several partners. The cell refinement is therefore essential. An opponent could argue that it enriches the state beyond the paper’s bare population profile. My answer is that it records the supplied matching \(M\), exactly as Theorem 4.2 does; it does not introduce idiosyncratic prices or named-agent structure. Agents in the same preference type and current-partner cell remain completely interchangeable.

The natural next questions are whether Theorem 4.1’s existence problem admits a polynomial formulation, whether discrete popularity can be recovered from the LP with useful additive guarantees, and whether hardness returns when mass splitting is forbidden or when preference types are given only through a succinct pricing oracle.