d4-journals-geb-2024-0100 (d4-journals-geb-2024-0100)

Let \(T\) be a finite set of agent types, each with side, weight \(w_t\), compatible opposite-side types, and a strict ranking \(\succ_t\) over those types; let \(X_t\) be an atomless cohort of rational mass \(\mu_t\), with \(\sum_t\mu_t=1\). Copies of the same partner type are tied. A feasible matching \(\pi\) is a measurable one-to-one pairing of compatible agents, with unmatched agents allowed; write \(r_t^\pi(z)\) for the type of \(z\)’s partner, or \(\bot\) if unmatched, with \(\bot\) ranked last. Define \(\Delta(\pi,\pi')=\sum_{t\in T}\int_{X_t}w_t\bigl(\mathbf{1}[r_t^\pi(z)\succ_t r_t^{\pi'}(z)]-\mathbf{1}[r_t^{\pi'}(z)\succ_t r_t^\pi(z)]\bigr)\,d\lambda(z)\). Given the type graph and masses, does there exist a feasible \(\pi\) such that \(\Delta(\pi,\pi')\ge0\) for every feasible matching \(\pi'\)?

Fix a rational constant \(1<c\leq2\). The input is a simple bipartite compatibility graph \(G=(T_A\cup T_B,E)\); each type strictly ranks its neighbors, with voting weight \(w_t=c\) on \(T_A\) and \(w_t=1\) on \(T_B\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types. Let \(m=|E|\) and \(L\) be the total input bit length; state running times in \(m,\tau,L\).
Represent each cohort by a disjoint copy \(X_t\) of \([0,\mu_t)\) with Lebesgue measure \(\lambda\). A feasible matching is a measurable, measure-preserving bijection between measurable subsets of the two sides, pairing only compatible types; agents outside these subsets are unmatched. Matchings are identified up to null sets.
Let \(r_t^\pi(z)\) be the partner type of \(z\in X_t\), or \(\bot\) when unmatched. All compatible types rank above \(\bot\); copies of the same partner type are tied.
Define \(\Delta(\pi,\pi')=\sum_t\int_{X_t}w_t\bigl(\mathbf{1}[r_t^\pi(z)\succ_t r_t^{\pi'}(z)]-\mathbf{1}[r_t^{\pi'}(z)\succ_t r_t^\pi(z)]\bigr)\,d\lambda(z)\). A matching \(\pi\) is popular if \(\Delta(\pi,\pi')\geq0\) for every feasible \(\pi'\), comparing the same agents across matchings.

For each fixed rational \(1<c\leq2\), is deciding whether this society admits a popular matching in \(\mathsf{P}\), or is it \(\mathsf{NP}\)-hard?

The finite-agent existence problem with these side weights and strict preferences is \(\mathsf{NP}\)-complete. [Heeger–Cseh](https://arxiv.org/html/2110.05901v2)
Popular mixed matchings with unit voting weights can be computed in polynomial time under expected-vote comparisons of lotteries; that comparison differs from the agentwise comparison above. [Huang–Kavitha](https://www.di.ens.fr/~cchuang/work/mixed_popular.pdf)
No result settling this exact atomless existence problem was located.

Result

For every fixed rational \(1<c\leq 2\), the problem is \(\mathsf{NP}\)-hard, even when all positive masses are equal and dyadic.

The key is an equivalence: an equal-mass atomless society admits a popular matching if and only if its finite type graph admits a popular matching. The reverse implication requires allowing the atomless incumbent to split each type among several partner types.

1. Definitions and two preliminary facts

For partner types \(p,q\), including \(\bot\), define the weighted vote
\[ \text{} \]
\( \displaystyle v_t(p,q)=w_t\bigl(\mathbf{1}[p\succ_t q]-\mathbf{1}[q\succ_t p]\bigr). \)

For finite matchings \(M,N\) on the type graph, let
\( \displaystyle D(N,M)=\sum_t v_t(N(t),M(t)). \)
Thus \(M\) is popular precisely when \(D(N,M)\leq 0\) for every finite matching \(N\). Likewise, by antisymmetry of the given comparison, an atomless matching \(\pi\) is popular precisely when \(\Delta(\pi',\pi)\leq 0\) for every feasible \(\pi'\).

We use the following facts.

Bipartite matching integrality. For a finite bipartite graph, the polytope
\( \displaystyle P(G)=\left\{z\in\mathbb{R}_{\geq 0}^{E}: \sum_{e\ni t}z_e\leq 1\ \text{for every }t\right\} \)
is the convex hull of the incidence vectors of finite matchings.

For completeness, orient every edge from the first side to the second. The oriented vertex-edge incidence matrix is totally unimodular: in any square submatrix, a column with at most one nonzero entry permits induction by determinant expansion; otherwise every column has two opposite entries, so the row sum is zero and the determinant vanishes. Changing the signs of the first-side rows gives the unsigned incidence matrix. Appending unit rows preserves total unimodularity. Consequently, every vertex of \(P(G)\), whose constraint right-hand sides are integral, is integral. Its integral points are exactly matching incidence vectors. Since \(P(G)\) is bounded, the stated convex-hull conclusion follows.

Atomless measure-space facts. A measurable subset of a finite interval has measurable subsets of every measure between zero and its own measure. Also, two such sets of equal positive Lebesgue measure admit a measurable, measure-preserving bijection modulo null sets.

The first assertion follows from continuity of the cumulative measure function. The second is the standard isomorphism theorem for atomless standard finite measure spaces: measurable subsets of intervals, after replacing them by Borel representatives modulo null sets, satisfy its hypotheses. These facts apply to every cohort subset used below. Working modulo null sets agrees with the problem’s convention.

2. Equal-mass equivalence: finite to atomless

Suppose every type has mass \(\delta=1/\tau\), and let \(M\) be a popular finite matching.

Construct \(\pi_M\) by matching entire cohorts along the edges of \(M\), using the identity between their interval coordinates. Leave the other cohorts unmatched. Every agent of type \(t\) then has incumbent partner type \(M(t)\).

Consider any feasible atomless challenger \(\pi'\). For each edge \(\{a,b\}\), let \(y_{ab}\) be the mass matched between its two endpoint types under \(\pi'\). Measure preservation makes this mass the same at both endpoints. Therefore
\( \displaystyle z_{ab}=\frac{y_{ab}}{\delta} \)
belongs to \(P(G)\).

Set \(h_t(p)=v_t(p,M(t))\), and define the affine function
\( \displaystyle F_M(z)= \sum_{\{a,b\}\in E}z_{ab}\bigl(h_a(b)+h_b(a)\bigr) + \sum_t\left(1-\sum_{e\ni t}z_e\right)h_t(\bot). \)

Because the incumbent partner type is constant throughout each cohort,
\( \displaystyle \Delta(\pi',\pi_M)=\delta F_M(z). \)

For every finite matching \(N\),
\( \displaystyle F_M(\mathbf{1}_N)=D(N,M)\leq 0. \)
By bipartite matching integrality, \(z\) is a convex combination of matching incidence vectors. Affineness therefore gives \(F_M(z)\leq 0\). Hence \(\pi_M\) is popular.

3. Equal-mass equivalence: atomless to finite

Now let \(\pi\) be any popular atomless matching with cohort masses \(\delta\). No homogeneity assumption is imposed on \(\pi\).

Write \(x_{ab}\) for its mass on edge \(\{a,b\}\), and write
\( \displaystyle u_t=\delta-\sum_{e\ni t}x_e \)
for the unmatched mass of type \(t\). Again, measure preservation gives consistent edge masses at both endpoints.

The vector \(z=x/\delta\) lies in \(P(G)\). Consequently,
\( \displaystyle z=\sum_{i=1}^{k}\theta_i\mathbf{1}_{M_i}, \qquad \theta_i>0,\qquad \sum_i\theta_i=1, \)
for finite matchings \(M_i\).

Two consequences of this decomposition are essential:

• If \(x_e=0\), then no \(M_i\) contains \(e\), because every summand is nonnegative.
• If \(u_t=0\), then every \(M_i\) matches \(t\). Indeed,

\( \displaystyle 1=\sum_i\theta_i\mathbf{1}[t\text{ is matched in }M_i], \)
and every indicator on the right is at most one.

Choose any one of these matchings, denoted \(M\). Thus every edge of \(M\) carries positive incumbent mass, and every type unmatched in \(M\) has positive incumbent unmatched mass.

We prove that \(M\) is popular by embedding each finite challenge into the same agents of the atomless incumbent.

Choose \(\varepsilon>0\) no larger than all the numbers
\( \displaystyle \{x_e:e\in M\}\ \cup\ \{u_t:t\text{ is unmatched in }M\}. \)
This is a nonempty finite collection of positive numbers, since \(\tau\geq 1\).

For each edge \(\{a,b\}\in M\), select a measurable subset of mass \(\varepsilon\) from the type-\(a\) agents whom \(\pi\) matches to type \(b\), and select their corresponding partners under \(\pi\). These partners also have mass \(\varepsilon\). For each type unmatched in \(M\), select mass \(\varepsilon\) from its incumbent unmatched agents.

Denote the resulting selected subset of cohort \(t\) by \(U_t\). The construction has three properties:

• Every \(U_t\) has measure \(\varepsilon\).
• Every selected agent has incumbent partner type \(M(t)\).
• Every incumbent pair containing a selected agent has both endpoints selected.

Let \(N\) be an arbitrary finite matching. Construct an atomless challenger \(\pi_N\) as follows. For each edge \(\{a,b\}\in N\), pair \(U_a\) and \(U_b\) by a measurable, measure-preserving bijection. Leave the other selected sets unmatched, and retain \(\pi\) on all unselected agents.

Equal selected masses provide the required bijections. Property 3 ensures that retaining the incumbent outside the selected sets creates no conflict. Thus \(\pi_N\) is feasible.

Only selected agents change partner types, and their votes give exactly
\( \displaystyle \Delta(\pi_N,\pi) = \varepsilon\sum_t v_t(N(t),M(t)) = \varepsilon D(N,M). \)

Popularity of \(\pi\) implies that this quantity is nonpositive. Since \(\varepsilon>0\) and \(N\) was arbitrary, \(M\) is a popular finite matching.

We have therefore proved
\( \displaystyle G\text{ admits a popular finite matching} \quad\Longleftrightarrow\quad \text{its equal-mass atomless society admits a popular matching}. \)

The embedded challenge compares the same selected agents across the two matchings, exactly as required by the question.

4. Hardness reduction and input size

For every fixed \(1<c\leq 2\), Heeger–Cseh’s Theorem 9 establishes that finite popular-matching existence is \(\mathsf{NP}\)-complete for strict bipartite preferences with weight \(c\) on one side and weight \(1\) on the other. [Heeger–Cseh, Theorem 9](https://arxiv.org/html/2110.05901v2)

Take such a finite instance with \(n\geq 1\) vertices. Add isolated vertices until the number of vertices is
\( \displaystyle \tau=2^{\lceil\log_2 n\rceil}. \)
Isolated vertices are unmatched in every finite matching and contribute zero to every comparison, so this padding preserves popular-matching existence.

Make each vertex a positive-mass type, retain all edges, rankings, and side weights, and assign
\( \displaystyle \mu_t=\frac1\tau \)
to every type. These masses are dyadic and sum to one. By the equivalence proved above, the resulting society admits a popular matching exactly when the original finite instance does.

The construction keeps \(m\) unchanged and has \(\tau<2n\) unless \(n\) already is a power of two. If the finite source has bit length \(L_{\mathrm{fin}}\), the resulting society has
\( \displaystyle L=O(L_{\mathrm{fin}}+\tau\log\tau). \)
The reduction uses \(O(m+\tau)\) graph operations and \(O(L_{\mathrm{fin}}+\tau\log\tau)\) bit operations, hence polynomial time in \(m,\tau,L\).

This proves the requested \(\mathsf{NP}\)-hardness. Moreover, the equal-mass restriction is itself \(\mathsf{NP}\)-complete: its equivalence with the finite problem also supplies membership in \(\mathsf{NP}\).

⟨structured verdict parsed — rendered above⟩

The prover resolves the task. The equal-mass equivalence is valid, including the direction starting from an incumbent that splits cohorts among several partner types. The cited finite hardness theorem applies with the required preferences and weights. I found no mathematical gaps requiring repair.

• Definitions and comparison signs.

The definition of \(v_t(p,q)\) correctly includes voting weights, ties between identical partner types, and the unmatched option. The finite comparison \(D(N,M)\) measures the challenger’s advantage. Thus popularity requires \(D(N,M)\leq 0\).

The atomless criterion \(\Delta(\pi',\pi)\leq 0\) follows correctly from antisymmetry. The signs remain consistent throughout both implications.

• Bipartite matching integrality.

The stated polytope is the correct fractional matching polytope with unmatched vertices allowed.

The determinant argument establishes total unimodularity of the oriented incidence matrix: expansion handles columns with at most one nonzero entry; otherwise each column has two opposite entries, giving a linear dependence among rows. Row sign changes preserve total unimodularity, as does adjoining the signed unit rows needed for nonnegativity.

Integral right-hand sides therefore yield integral vertices. Nonnegative integral edge vectors satisfying the degree constraints are precisely matching incidence vectors. Boundedness supplies the claimed convex-hull representation. This also covers isolated vertices and the graph with no edges.

• Measure-space facts.

Both facts are stated sufficiently precisely for their uses. The cumulative-measure argument permits selecting subsets of any prescribed admissible mass. The measure-space isomorphism theorem supplies measure-preserving bijections modulo null sets between equal-measure subsets.

Passing to Borel representatives modulo null sets addresses the measurable-subset hypothesis. The problem explicitly identifies matchings modulo null sets, so these bijections provide the required feasible matchings.

• Finite popularity implies atomless popularity.

Matching whole equal-mass cohorts along a finite matching is feasible. Every incumbent partner type is then constant on its cohort.

For any atomless challenger, measure preservation gives consistent edge masses at both endpoints. Dividing by \(\delta\) produces a vector in \(P(G)\).

The displayed affine function correctly counts both matched and unmatched challenger agents. In particular,
\(\Delta(\pi',\pi_M)=\delta F_M(z)\).
At a matching incidence vector, it equals the finite challenger’s vote:
\(F_M(\mathbf{1}_N)=D(N,M)\).

Convex decomposition and affineness therefore transfer the nonpositive finite comparisons to every atomless challenger. This implication is rigorous.

• Atomless popularity implies finite popularity.

This is the central step, and the argument handles heterogeneous incumbents correctly.

The incumbent edge masses again yield \(z\in P(G)\). A finite convex decomposition can be taken with all retained coefficients positive. Nonnegativity then ensures that each edge in any retained matching has positive incumbent mass. Likewise, if a type has zero incumbent unmatched mass, every retained matching must match it.

Consequently, for the chosen \(M\), every quantity used to bound \(\varepsilon\) is positive. The collection is nonempty: either \(M\) has an edge, or its nonempty vertex set contains an unmatched vertex. A positive common \(\varepsilon\) therefore exists.

Selecting both endpoints of each incumbent pair on an edge of \(M\) is essential and correctly executed. Since \(M\) is a matching, these selections do not conflict. The resulting \(U_t\) all have mass \(\varepsilon\), have incumbent partner type \(M(t)\), and are closed under incumbent pairing.

For each arbitrary finite challenger \(N\), the proposed replacement matching is measurable and measure preserving. Closure under incumbent pairing ensures that retaining the incumbent outside the selected sets leaves no crossing pairs or conflicts.

Every selected agent receives challenger partner type \(N(t)\), including \(\bot\) when appropriate. Every unselected agent retains its partner. Hence the exact identity
\[ \Delta(\pi_N,\pi)=\varepsilon D(N,M) \]
is valid. Popularity of \(\pi\), positivity of \(\varepsilon\), and arbitrariness of \(N\) establish popularity of \(M\). The construction compares the same agents across matchings, as required.

• External hardness theorem.

The cited theorem is correctly identified. Heeger–Cseh’s Theorem 9 states finite \(\mathsf{NP}\)-completeness for every constant \(1<c\leq 2\), with weight \(c\) throughout one side and weight \(1\) throughout the other. Their underlying input model uses simple bipartite graphs, strict neighbor preferences, and every neighbor preferred to being unmatched. All hypotheses match the reduction. See [Heeger–Cseh, Section 4.2, Theorem 9](https://arxiv.org/html/2110.05901v2).

• Padding, encoding, and complexity.

Adding isolated vertices preserves finite popularity because these vertices remain unmatched under every matching and always contribute zero votes. They can be placed on either side without changing this argument.

The padded support size is a power of two, so the equal masses are positive dyadic rationals summing to one. The equivalence therefore applies directly.

The padding adds fewer than \(n\) vertices. Edges and rankings are retained, and each mass needs \(O(\log\tau)\) bits. The stated output-length and reduction-time bounds are consistent with explicit graph and binary-rational encodings and are polynomial in \(m,\tau,L\).

The additional \(\mathsf{NP}\)-completeness claim for the equal-mass restriction also follows: its equivalence with the finite problem supplies finite matching certificates with polynomial verification. The prover does not claim membership in \(\mathsf{NP}\) for arbitrary unequal masses.

No additional mathematical clarification is needed.

⟨structured verdict parsed — rendered above⟩