d4-conf-atal-2013-0207 (d4-conf-atal-2013-0207)

Given applicant types \(I\) and slot types \(J\), rational masses \(\mu_i,\nu_j\) summing to one on each side, and weak rankings over opposite-side types and being single, decide whether there is a nonnegative matching-mass matrix \(x\) with \(\sum_j x_{ij}\le\mu_i\) and \(\sum_i x_{ij}\le\nu_j\) such that no positive-mass agent can strictly improve by becoming single or switching to an unmatched opposite-side type, and no unmatched agent can strictly improve by pairing with an unmatched opposite-side type.

Let \(I\) and \(J\) be nonempty, disjoint sets of applicant and slot types. Each type has a complete weak ranking over opposite-side types and the single status \(\bot\); partners may rank below, equal to, or above being single. Only opposite-side pairs are allowed.
A society is given by its support: its list of types with positive mass, each mass a binary rational. Let \(\tau=|I|+|J|\) be the total support size, \(m=|J|\), and \(L\) the total input bit length; support size counts listed types, not all possible rankings. Masses satisfy \(\sum_i\mu_i=\sum_j\nu_j=1\).
A matching is a real matrix \(x\geq0\) with \(\sum_jx_{ij}\leq\mu_i\) and \(\sum_ix_{ij}\leq\nu_j\). Write \(s_i=\mu_i-\sum_jx_{ij}\) and \(t_j=\nu_j-\sum_ix_{ij}\). Entries describe masses of actual pairs, not lotteries evaluated by expected utility.
Call \(x\) Nash stable if every positive matched mass weakly prefers its partner to being single and to every opposite-side type with positive unmatched mass. Every positive unmatched mass must weakly prefer being single to every opposite-side type with positive unmatched mass. These conditions apply separately on both sides.
A deviation requires a strict improvement only for its initiator: neither the abandoned partner nor the approached unmatched partner has a veto. Ties do not create deviations; fully matched types cannot be approached.

Is deciding whether such a Nash-stable matching exists in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?

For finite marriage games with ties and unacceptable partners, Nash-stable matching existence is \(\mathrm{NP}\)-complete; when every opposite-side partner is acceptable, existence is guaranteed and a matching can be computed in \(O(n^2)\) time for \(n\) agents. [Aziz (2013)](https://www.ifaamas.org/Proceedings/aamas2013/docs/p287.pdf)
No result settling this exact mass formulation was located in the literature search.

Result

The decision problem is \(\mathrm{NP}\)-complete. Hardness holds even when every listed type has the same dyadic mass.

The essential point is that, with equal masses, fractional Nash-stable matchings can be rounded to integral matchings without destroying stability.

1. A rounding lemma

Lemma. Let \(A,B\) be finite disjoint sets, and let \(y\) be a nonnegative matrix satisfying

\(\sum_{b\in B}y_{ab}\leq 1\) for every \(a\in A\), and \(\sum_{a\in A}y_{ab}\leq 1\) for every \(b\in B\).

There exists a matrix \(z\) with entries in \(\{0,1\}\) such that:

• Every row and column of \(z\) sums to at most \(1\).
• If \(z_{ab}=1\), then \(y_{ab}>0\).
• Every row or column whose sum in \(y\) is \(1\) also has sum \(1\) in \(z\).

Proof. Define the saturated sets

\(S=\{a\in A:\sum_b y_{ab}=1\}\), and \(T=\{b\in B:\sum_a y_{ab}=1\}\).

Consider the polytope \(P\) defined by nonnegativity, row and column sums at most \(1\), and the additional constraints

\(z_{ab}=0\) whenever \(y_{ab}=0\),

\(\sum_b z_{ab}=1\) for \(a\in S\), and \(\sum_a z_{ab}=1\) for \(b\in T\).

It is nonempty because \(y\in P\). It is bounded because each coordinate lies between \(0\) and \(1\). Consequently, it has an extreme point \(z\).

Suppose some coordinate of \(z\) lies strictly between \(0\) and \(1\). Form the bipartite graph \(H\) whose edges are exactly these fractional coordinates.

Any vertex incident to a fractional edge cannot also be incident to an edge of value \(1\), because its total incident mass is at most \(1\). Therefore, if a vertex of \(H\) has degree one, its row or column sum is strictly below \(1\).

There are two cases.

• \(H\) contains a cycle. The cycle has even length because \(H\) is bipartite. Alternately add and subtract a sufficiently small positive \(\varepsilon\) around its edges. Both choices of sign preserve every row and column sum and keep all entries nonnegative. They give distinct points \(z^+,z^-\in P\) with \(z=(z^++z^-)/2\), contradicting extremality.

• \(H\) contains no cycle. Choose a component containing an edge. It is a finite tree, so it has a path between two leaves. Alternately add and subtract \(\varepsilon\) along this path. Internal vertex sums remain unchanged. Both endpoint sums are strictly below \(1\), so sufficiently small \(\varepsilon\) makes both perturbations feasible. The endpoints cannot belong to \(S\cup T\), since those vertices have sum \(1\). Again, \(z\) is the midpoint of two distinct points of \(P\), contradicting extremality.

Thus every coordinate of \(z\) is integral. Its defining constraints establish all three conclusions. \(\square\)

2. Rounding preserves Nash stability

Temporarily give every type capacity \(1\). For a feasible matrix \(y\), define its unmatched-type sets by

\(U_y=\{a\in A:\sum_b y_{ab}<1\}\), and \(V_y=\{b\in B:\sum_a y_{ab}<1\}\).

Corollary. If \(y\) is Nash stable, the integral matrix \(z\) supplied by the lemma is also Nash stable.

Proof. Preservation of saturated rows and columns gives

\(U_z\subseteq U_y\), and \(V_z\subseteq V_y\).

If \(z_{ab}=1\), then \(y_{ab}>0\). Stability of \(y\) therefore says that each endpoint weakly prefers this partner to being single and to every opposite-side type in the corresponding unmatched set of \(y\). These comparisons continue to hold against the smaller unmatched sets of \(z\).

If \(a\in U_z\), then \(a\in U_y\). Stability of the unmatched mass of \(a\) in \(y\) gives \(\bot\succeq_a b\) for every \(b\in V_y\), hence for every \(b\in V_z\). The same argument applies to unmatched slot types.

These are precisely all the required stability conditions for \(z\). \(\square\)

This argument uses the stipulated requirement that stability hold for every positive matched entry.

3. Polynomial reduction proving hardness

We use Aziz’s established theorem: deciding whether a finite marriage game with weak preferences and unacceptable partners admits a Nash-stable matching is \(\mathrm{NP}\)-complete. [Aziz (2013), Theorem 1](https://www.ifaamas.org/Proceedings/aamas2013/docs/p287.pdf).

Its deviation rule agrees with the present rule on integral matchings. Becoming single enforces individual rationality; an initiator can approach an opposite-side single agent without that agent’s consent. Joining an existing pair creates an unacceptable larger coalition and cannot improve an individually rational outcome.

Take an instance of this finite problem with sides \(A_0,B_0\). Choose \(N=2^q\) to be the least power of two satisfying

\(N\geq\max\{|A_0|,|B_0|,1\}\).

Pad each side to size \(N\) using dummy agents. Preserve every original preference comparison, and arrange that:

• Every original agent ranks every opposite-side dummy strictly below \(\bot\).
• Every dummy ranks every opposite-side agent strictly below \(\bot\).

These specifications extend to complete weak rankings. Any originally omitted unacceptable partners can likewise be placed below \(\bot\).

Every dummy must remain single in an individually rational matching. Moreover, neither an original agent nor a dummy can profitably approach a dummy. Thus the padded finite instance has a Nash-stable matching exactly when the original instance does.

Now regard each padded agent as one listed type and give every type mass

\(\mu_a=\nu_b=1/N=2^{-q}\).

Both side totals are \(1\), and every mass is a positive dyadic rational.

Forward implication. Given a Nash-stable finite matching in the padded instance, assign mass \(1/N\) to each matched pair and zero to every other pair. The resulting mass matching has exactly the same unmatched types and preference comparisons, so it is Nash stable.

Reverse implication. Suppose the mass instance has a Nash-stable matching \(x\). Set \(y=Nx\). This gives unit capacities, and multiplication by a positive scalar preserves the positive-entry and unmatched-type sets. Thus \(y\) is Nash stable.

By the corollary, \(y\) can be rounded to an integral Nash-stable matrix \(z\). Its positive entries define a Nash-stable finite matching in the padded instance. Removing the necessarily single dummies gives a Nash-stable matching in the original instance.

Hence the original finite instance is a yes-instance if and only if the constructed mass instance is a yes-instance.

The construction is polynomial: \(N\) is at most twice the larger original side size, the output contains \(2N\) listed types, their complete rankings have polynomial length, and each mass has \(O(\log N)\) bits. In particular, \(m=N\), \(\tau=2N\), and the output length \(L\) are all polynomial in the source-instance length. This proves \(\mathrm{NP}\)-hardness.

4. Membership in \(\mathrm{NP}\)

We give a polynomial verifier that does not require guessing real numbers.

Guess subsets \(U\subseteq I\) and \(V\subseteq J\). They represent sets containing all actually unmatched types; types in these guessed sets are permitted to turn out fully matched.

First check, for every \((i,j)\in U\times V\), that

\(\bot\succeq_i j\), and \(\bot\succeq_j i\).

Next define \(E(U,V)\) to consist of the pairs \((i,j)\) satisfying all four requirements:

• \(j\succeq_i\bot\).
• \(i\succeq_j\bot\).
• \(j\succeq_i v\) for every \(v\in V\).
• \(i\succeq_j u\) for every \(u\in U\).

Test feasibility of the following rational linear system:

• \(x_{ij}\geq 0\) for all pairs, and \(x_{ij}=0\) outside \(E(U,V)\).
• \(\sum_j x_{ij}\leq\mu_i\) for every \(i\), with equality whenever \(i\notin U\).
• \(\sum_i x_{ij}\leq\nu_j\) for every \(j\), with equality whenever \(j\notin V\).

Rational linear-program feasibility is decidable in time polynomial in the number of variables, constraints, and their binary encoding length. Here there are at most \(m(\tau-m)\) variables, polynomially many constraints, and coefficients consisting of the input masses and \(0,1\). Constructing \(E(U,V)\) also requires only polynomially many preference comparisons. The guessed subsets use \(\tau\) bits.

Completeness. If a Nash-stable matching exists, choose \(U,V\) to be its exact unmatched-type sets. Stability gives the initial comparisons and ensures that every positive entry belongs to \(E(U,V)\). The matching itself satisfies the linear system.

Soundness. Suppose a guess passes the initial check and the linear system is feasible. For any feasible solution, its actual unmatched-type sets \(U_x,V_x\) satisfy

\(U_x\subseteq U\), and \(V_x\subseteq V\).

Every positive pair belongs to \(E(U,V)\), so both endpoints weakly prefer their partner to being single and to every actual unmatched opposite-side type. The initial comparisons on \(U\times V\) also hold on \(U_x\times V_x\), establishing the required conditions for unmatched mass. Thus the solution is Nash stable.

This proves membership in \(\mathrm{NP}\). Together with the reduction, it proves \(\mathrm{NP}\)-completeness; a running time polynomial in \(m,\tau,L\) therefore exists only if \(\mathrm{P}=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

The prover’s claim is proved. The rounding lemma, stability preservation, polynomial reduction, and membership argument are correct. I found no major or minor issue requiring repair.

• The rounding lemma is valid.

The polytope \(P\) contains \(y\), so it is nonempty. Its nonnegative coordinates and row bounds imply that every coordinate is at most \(1\), so it is bounded. A nonempty bounded polytope has an extreme point.

The fractional-edge argument correctly establishes integrality of that extreme point:

• A vertex incident to a fractional edge cannot have an incident entry equal to \(1\), because the incident sum is at most \(1\).
• Consequently, a degree-one vertex in the fractional-edge graph has total incident mass strictly below \(1\): its only positive incident entry is the fractional edge.
• On a cycle, bipartiteness ensures even length. Alternating perturbations preserve every incident sum. Choosing the perturbation smaller than the affected positive entries preserves nonnegativity in both directions.
• In an acyclic component containing an edge, a path between two leaves exists. Alternating perturbations preserve internal sums. Both endpoints have strictly positive slack below \(1\), so both perturbation directions can satisfy the upper bounds.
• Those endpoints cannot have a prescribed saturation equality, because their sums are strictly below \(1\).

Both perturbations retain all prescribed zero coordinates and saturation equalities. Their midpoint is the original extreme point, giving the stated contradiction.

If there are no fractional coordinates, the conclusion already holds. Empty row or column index sets also cause no difficulty. Thus all three conclusions of the lemma follow.

• Rounding preserves exactly the stability conditions in the task.

Preserving every saturated row and column gives
\[ U_z\subseteq U_y,\qquad V_z\subseteq V_y. \]
The direction of these inclusions is correct: rounding can fully match a formerly partially unmatched type, but cannot leave a formerly fully matched type unmatched.

Every positive entry of \(z\) was positive in \(y\). Therefore, each retained pair inherits both endpoints’ individual rationality and all required comparisons with unmatched opposite-side types. Restricting those comparisons to smaller unmatched sets preserves them.

Every unmatched type in \(z\) had positive unmatched mass in \(y\). Its comparisons between being single and unmatched opposite-side types therefore also persist.

This covers both matched and unmatched mass, separately on both sides. The argument correctly uses entrywise stability rather than preferences over an average allocation.

• The cited finite-game theorem applies.

[Aziz’s Theorem 1](https://www.ifaamas.org/Proceedings/aamas2013/docs/p287.pdf) states that deciding whether a marriage game admits a Nash-stable matching is \(\mathrm{NP}\)-complete. Its definitions allow weak preferences and unacceptable partners. Nash deviations require improvement by the moving player without consent from the destination coalition.

The prover correctly identifies the correspondence with the task. Departing to become single enforces individual rationality. Approaching a singleton is precisely approaching an unmatched agent. Same-side pairs and coalitions of size at least three are unacceptable in the cited model, so neither supplies a profitable deviation from an individually rational matching.

Thus the external theorem has the required hypotheses and deviation semantics.

• Padding preserves existence.

The specified preference extensions preserve every original comparison. All pairs involving a dummy are strictly unacceptable to both relevant endpoints, so no individually rational matching can contain such a pair.

In a Nash-stable matching, all dummies therefore remain single. Their presence introduces no profitable deviation: originals rank opposite-side dummies below being single, and dummies rank every opposite-side agent below being single.

Conversely, removing these single dummies changes neither original matches nor the availability of original unmatched agents. The claimed equivalence between the original and padded finite instances is justified.

Completing omitted unacceptable partners below \(\bot\) is also harmless: such partners cannot occur in an individually rational matching or provide a profitable destination from an individually rational current outcome.

• Both directions of the mass reduction are correct.

The padded instance has \(N\) agents on each side. Giving each listed type mass \(1/N=2^{-q}\) yields strictly positive dyadic masses and side totals equal to \(1\).

In the forward direction, replacing each finite pair by mass \(1/N\) preserves precisely the matched pairs and unmatched types. All stability comparisons remain identical.

In the reverse direction, scaling by \(N\) gives unit capacities. In particular,
\[ \sum_b y_{ab}<1 \quad\Longleftrightarrow\quad \sum_b x_{ab}<1/N, \]
with the analogous equivalence for columns. Positive entries are also preserved. Thus scaling preserves stability.

The rounding corollary then supplies an integral stable matching. Its row and column bounds ensure that it represents a finite matching. Removing the single dummies recovers a stable matching in the source instance.

Treating agents as separately listed types is compatible with the task’s support-based input description; the construction does not enumerate all possible rankings.

• The reduction has polynomial size.

For nonempty source instances, the least power of two \(N\) satisfies
\[ N<2\max\{|A_0|,|B_0|\}. \]
Hence padding creates only linearly many listed types. Their complete rankings require polynomial space, and each mass requires \(O(\log N)\) bits.

The resulting parameters \(m=N\), \(\tau=2N\), and \(L\) are polynomially bounded in the source input length. This establishes the claimed polynomial reduction and \(\mathrm{NP}\)-hardness, including the equal-dyadic-mass restriction.

• The membership-in-\(\mathrm{NP}\) argument is valid.

Guessing \(U,V\) requires \(\tau\) bits. Their interpretation as supersets of the actual unmatched sets is consistent throughout the verifier.

The preliminary comparisons correctly enforce the unmatched-mass conditions on \(U\times V\). The four requirements defining \(E(U,V)\) correctly enforce both endpoints’ individual rationality and comparisons against all guessed unmatched types.

The linear system forces every type outside the guessed unmatched sets to be saturated. Consequently, every feasible solution satisfies
\[ U_x\subseteq U,\qquad V_x\subseteq V. \]

Completeness: Choosing the exact unmatched sets of a stable matching satisfies the preliminary comparisons, places every positive entry inside \(E(U,V)\), and satisfies the saturation constraints.

Soundness: Every positive entry of a feasible solution satisfies the required comparisons against the actual unmatched sets, since these are subsets of the guessed sets. The preliminary comparisons likewise apply to every actually unmatched pair.

The invoked polynomial-time theorem for rational linear-program feasibility applies: there are polynomially many explicitly represented variables and constraints, and all coefficients and right-hand sides have polynomial binary encoding length. It decides real feasibility, so the verifier does not need a guessed real-valued matching.

Therefore the proposed certificate and verifier establish membership in \(\mathrm{NP}\).

The output resolves the requested complexity classification. No additional clarification or mathematical repair is needed.

⟨structured verdict parsed — rendered above⟩