A stable marriage requires communication (d4-journals-geb-2019-0040)

Given finite woman-type and man-type sets \(A\) and \(B\), rational masses \(\mu\) and \(\nu\), and strict rankings of opposite-side types, find a nonnegative mass matching \(x=(x_{ab})\) with \(\sum_b x_{ab}=\mu_a\) and \(\sum_a x_{ab}=\nu_b\) whose type-level blocking pairs are absent, or whose aggregate divorce distance \(d_\infty(x)=1-\max_{y\in\mathcal S}\sum_{a,b}\min\{x_{ab},y_{ab}\}\) is at most fixed \(\varepsilon<\tfrac12\).

Let \(A,B\) be nonempty finite sets of woman-types and man-types, each with a strict complete ranking of opposite-side types; all partners are acceptable.
A society is given by its support: the list of its \(\tau=|A|+|B|\) positive-mass types, each with its mass as a binary rational. Require \(\sum_a\mu_a=\sum_b\nu_b=1\); let \(m=\max\{|A|,|B|\}\) and let \(L\) be the total input bit length. State running times in \(m,\tau,L\).
A mass matching is a nonnegative matrix satisfying \(\sum_bx_{ab}=\mu_a\) and \(\sum_ax_{ab}=\nu_b\).
A pair \((a,b)\) blocks \(x\) precisely when \(\sum_{b':\,b\succ_a b'}x_{ab'}>0\) and \(\sum_{a':\,a\succ_b a'}x_{a'b}>0\). Let \(\mathcal S\) be the set of mass matchings without blocking pairs.
For fixed \(0\leq\varepsilon<\tfrac12\), construct a rational mass matching satisfying \(d_\infty(x)=1-\max_{y\in\mathcal S}\sum_{a,b}\min\{x_{ab},y_{ab}\}\leq\varepsilon\); exact stability is the case \(\varepsilon=0\).

Is this construction problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?

Discrete: finding an approximately stable marriage requires \(\Omega(n^2)\) separate-side Boolean queries, including for randomized algorithms; this is a query lower bound, not NP-hardness. [Source](https://arxiv.org/html/1405.7709).
Continuous: Baïou–Balinski give a strongly polynomial algorithm for stable allocations under this blocking definition, covering the stated normalized complete market. Consequently, this construction target is already settled in polynomial time. [Source](https://pubsonline.informs.org/doi/pdf/10.1287/moor.27.4.662.302).

Conclusion

The construction problem is polynomial-time solvable, including exact stability. We can construct a rational stable mass matching and therefore satisfy the approximation requirement for every permitted \(\varepsilon\).

Write \(p=|A|\), \(q=|B|\), and \(E=pq\). A conservative implementation bound is \(O(E^2\tau)\) arithmetic operations and
\(O(\tau L^2+E^2\tau L)\) bit operations. Since \(E\leq m^2\), this is at most \(O(\tau L^2+m^4\tau L)\).

1. The stable-allocation theorem

We use the following known result.

Baïou–Balinski stable-allocation theorem. Given finite row and column sets, strict preferences, positive quotas \(s_a,d_b\), and nonnegative entry capacities \(c_{ab}\), their inductive algorithm constructs an allocation \(z\) satisfying
\(\sum_b z_{ab}\leq s_a\), \(\sum_a z_{ab}\leq d_b\), and \(0\leq z_{ab}\leq c_{ab}\), with the stability condition
\[ z_{ab}<c_{ab} \quad\Longrightarrow\quad \sum_{b'\succeq_a b}z_{ab'}=s_a \ \text{or}\ \sum_{a'\succeq_b a}z_{a'b}=d_b. \]
Here weak preference means strict preference or equality. The algorithm is strongly polynomial; Theorem 2 bounds its allocation changes by \(3E+q\). [Baïou–Balinski, corrected paper, §2 and Theorem 2](https://pubsonline.informs.org/doi/pdf/10.1287/moor.27.4.662.302).

Apply this theorem with row set \(A\), column set \(B\), quotas \(s_a=\mu_a\), \(d_b=\nu_b\), and capacities \(c_{ab}=2\). All hypotheses hold: the sets are finite, quotas are positive, preferences are strict and complete, and capacities are positive.

2. Every returned allocation exhausts all masses

Let \(z\) be the stable allocation returned by the theorem, and define \(T=\sum_{a,b}z_{ab}\). Its quota inequalities imply \(T\leq1\).

Suppose \(T<1\). Since both sides have total quota \(1\), some row \(a\) and some column \(b\) have deficits:
\(\sum_{b'}z_{ab'}<\mu_a\) and \(\sum_{a'}z_{a'b}<\nu_b\).

Consequently,
\(\sum_{b'\succeq_a b}z_{ab'}<\mu_a\) and
\(\sum_{a'\succeq_b a}z_{a'b}<\nu_b\).
Moreover, \(z_{ab}\leq T<1<2=c_{ab}\). These three inequalities contradict the theorem’s stability condition. Therefore \(T=1\).

Each row deficit is nonnegative, and their sum is
\(\sum_a\mu_a-T=0\); hence every row deficit is zero. The identical argument applies to columns. Thus
\(\sum_bz_{ab}=\mu_a\) and \(\sum_az_{ab}=\nu_b\):
the returned allocation is a mass matching.

3. Its stability is exactly the requested stability

Because \(z_{ab}\leq T=1<2\), the theorem’s stability implication applies to every pair.

Using the row equality,
\(\mu_a-\sum_{b'\succeq_a b}z_{ab'} =\sum_{b':\,b\succ_a b'}z_{ab'}\).
Similarly,
\(\nu_b-\sum_{a'\succeq_b a}z_{a'b} =\sum_{a':\,a\succ_b a'}z_{a'b}\).

The theorem therefore says that, for every pair \((a,b)\), at least one of these two worse-partner sums equals zero. They can never both be positive. This is precisely the absence of blocking pairs in the question, so \(z\in\mathcal S\).

Output \(x=z\). Choosing \(y=x\) gives
\(\sum_{a,b}\min\{x_{ab},y_{ab}\}=\sum_{a,b}x_{ab}=1\).
For every mass matching \(y\), the overlap is at most \(\sum_{a,b}x_{ab}=1\). Hence the maximum equals \(1\), and \(d_\infty(x)=0\leq\varepsilon\).

4. Rational output and bit complexity

Write the input masses as binary-encoded fractions, and let \(Q\) be the product of their denominators. Its binary length is \(O(L)\). Multiply every quota and capacity by \(Q\), giving integer quotas and capacities \(2Q\).

The inductive algorithm’s numerical operations are additions, subtractions, comparisons, and minima, so integer input produces integer allocations. Its updates preserve feasibility. [Baïou–Balinski, §2](https://pubsonline.informs.org/doi/pdf/10.1287/moor.27.4.662.302). Dividing its output by \(Q\) therefore gives rational entries with \(O(L)\) bits each.

For completeness, a conservative implementation bound follows from the algorithm’s structure. Between allocation changes, its alternating sequence has distinct rows and columns, hence length \(O(\tau)\). Each extension can be implemented by scanning the matrix and recomputing preference-prefix sums in \(O(E)\) operations. Together with \(O(E)\) allocation changes and the row initialization, this gives \(O(E^2\tau)\) arithmetic operations.

After scaling, feasible entries and quota sums are bounded by \(Q\), and capacities by \(2Q\). The auxiliary differences and sums consequently have \(O(L)\) bits. Each addition, subtraction, or comparison costs \(O(L)\) bit operations. Computing \(Q\) and converting the quotas costs at most \(O(\tau L^2)\) using elementary integer arithmetic.

Thus construction takes \(O(\tau L^2+E^2\tau L)\) bit operations, with output length \(O(EL)\). No expansion into individual agents is required.

5. The discrete query lower bound

The cited \(\Omega(n^2)\) lower bound concerns separate-side Boolean queries, including randomized algorithms. It does not establish NP-hardness and is compatible with polynomial-time construction from explicitly supplied preferences. [Gonczarowski–Nisan–Ostrovsky–Rosenbaum](https://arxiv.org/html/1405.7709).

⟨structured verdict parsed — rendered above⟩

The prover resolves the assigned construction problem. The theorem application, exhaustion argument, stability translation, and rational bit-complexity analysis are valid. I found no major or minor mathematical issues.

1. The cited theorem is applicable

The stated stability condition agrees with equation (4) of the corrected Baïou–Balinski paper. Its model permits positive real quotas, nonnegative entry capacities, and strict preferences. Theorem 2 gives the stated bound of \(3E+q\) allocations generated by the inductive algorithm. [Corrected paper, §§1–2](https://pubsonline.informs.org/doi/pdf/10.1287/moor.27.4.662.302).

The specialization satisfies every hypothesis:

• Both sets are finite and nonempty.
• Every quota is positive because the input lists positive-mass types.
• Preferences are strict and complete.
• Every capacity is the positive rational number \(2\).

No integrality, unequal-total-mass, or nondegeneracy assumption is required. In particular, equal total quotas do not obstruct this theorem.

2. Exhaustion of all masses is proved correctly

Nonnegativity and the quota inequalities give \(T\leq1\).

If \(T<1\), the sum of row deficits and the sum of column deficits both equal \(1-T>0\). Thus a deficient row and a deficient column exist simultaneously. For their intersection, each preference-prefix sum is bounded above by its deficient full row or column sum, so both prefix inequalities are strict.

Also, \(z_{ab}\leq T<1<2\), which activates the theorem’s stability implication. Neither alternative in that implication holds, yielding the claimed contradiction.

After establishing \(T=1\), the nonnegative row deficits sum to zero, so every row is exhausted. The column argument is identical. This establishes all required marginal equalities.

3. The stability translation is exact

Every entry satisfies \(z_{ab}\leq1<2\). Consequently, capacity saturation never exempts a pair from the theorem’s stability condition.

Because the rankings are strict and complete, the opposite-side types partition into those weakly preferred to the proposed partner and those strictly worse. The prover’s two subtraction identities therefore hold exactly.

With exhausted quotas, the theorem’s prefix equality on either side is equivalent to that side’s worse-partner sum being zero. The two worse-partner sums cannot both be positive. This is precisely the blocking definition in USER_TASK.

The subsection establishes the claimed equivalence without changing the task’s stability notion.

4. Exact stability satisfies the approximation target

The output \(x=z\) belongs to \(\mathcal S\). Choosing \(y=x\) gives overlap \(1\).

For every mass matching \(y\), entrywise overlap is bounded by the corresponding entry of \(x\), so its total is at most \(1\). Thus the maximum is attained at \(y=x\), and \(d_\infty(x)=0\).

This addresses every permitted fixed \(\varepsilon\), including \(\varepsilon=0\). No representation or computation of \(\varepsilon\) is needed.

5. Rational output and numerical sizes

The product \(Q\) of the input denominators has bit length bounded by their total encoded length, hence \(O(L)\). Every scaled quota is an integer, and every scaled capacity equals \(2Q\).

The cited inductive algorithm uses the numerical operations identified by the prover; these preserve integrality. Its feasibility guarantees also support the claimed bounds on entries and quota sums. Dividing by \(Q\) restores the original quotas and capacities and preserves the stability equalities and inequalities.

Consequently, each output rational has \(O(L)\) bits, and the matrix has total numerical encoding length \(O(EL)\). There is no expansion proportional to the numerical value of \(Q\).

6. Running-time bounds

The algorithm’s retained alternating sequence has distinct row indices and distinct column indices. A terminal extension can close a cycle, but this does not change its \(O(\tau)\) length bound. The cited algorithm also supports scanning entries and recomputing preference-prefix sums within \(O(E)\) arithmetic operations per extension. [Corrected paper, §2](https://pubsonline.informs.org/doi/pdf/10.1287/moor.27.4.662.302).

Since the sets are nonempty, \(q\leq E\), so the allocation-change bound is \(O(E)\). The resulting conservative bound \(O(E^2\tau)\) accommodates sequence construction, updates, and initialization.

Scaled arithmetic has \(O(L)\)-bit operands. Elementary denominator-product and quota-conversion work fits within \(O(\tau L^2)\). Therefore the claimed bit bound
\(O(\tau L^2+E^2\tau L)\) is valid. Substituting \(E\leq m^2\) gives the stated \(O(\tau L^2+m^4\tau L)\).

7. The discrete lower bound is characterized correctly

Corollary 3.1 states the separate-side Boolean-query lower bound for fixed \(0\leq\varepsilon<\tfrac12\), including randomized algorithms. The prover correctly distinguishes this from NP-hardness and from computation using explicitly supplied preferences. [Discrete source, Corollary 3.1](https://arxiv.org/html/1405.7709).

No repair or additional mathematical clarification is required.

⟨structured verdict parsed — rendered above⟩