Answer: Polynomial-time solvable in \(m,\tau,L\), independently of \(1/\epsilon\). A stable exact unequal-division allocation always exists.
Theorem 7 — class: algorithmic
Given worker types \(A\), employer-seat types \(B\), rational masses \(\mu_t>0\) summing to one, and a compatibility graph \(H\), where every member of a type has the same compatible types, values \(w_{ab}\in(0,1]\), and bargaining shares \(r_{ab},r_{ba}>0\) with \(r_{ab}+r_{ba}=1\), find a stable \(\epsilon\)-UD allocation or certify that none exists. Represent matched mass on each compatible pair \((a,b)\) by a finite rational measure \(\pi_{ab}\) over earnings pairs \((x,y)\), with \(x+y=w_{ab}\), and require total incident matched mass at each type \(t\) to be at most \(\mu_t\); unmatched mass earns zero. Let \(\ell_t\) be the lowest earnings in the resulting earnings support and set \(\beta_t=\max_{u\in N(t)}(w_{tu}-\ell_u)^+\), or zero if \(t\) has no compatible types. Require \(\ell_a+\ell_b\ge w_{ab}\) for every compatible pair and, for \(\pi_{ab}\)-almost every matched earnings pair, \(\left|x-\beta_a-r_{ab}(w_{ab}-\beta_a-\beta_b)\right|\le\epsilon\).
Let \(A\) and \(B\) be disjoint worker and employer-seat type sets, with a simple bipartite compatibility graph \(H=(A\cup B,E)\); write \(m=|E|\). Each individual can participate in at most one match. A society is given by its support: the list of its \(\tau=|A\cup B|\) positive-mass types, each with binary rational mass \(\mu_t>0\), with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Each edge \((a,b)\) has binary rational value \(w_{ab}\in(0,1]\) and shares \(r_{ab},r_{ba}>0\) satisfying \(r_{ab}+r_{ba}=1\). The error tolerance \(\epsilon>0\) is binary rational; \(L\) is the total input bit length.
An allocation specifies, for every edge, a finitely supported nonnegative measure \(\pi_{ab}\), encoded by rational atom masses and rational earnings pairs \((x,y)\in\mathbb{Q}_{\ge0}^2\) with \(x+y=w_{ab}\). Total incident matched mass at type \(t\) is at most \(\mu_t\); the remainder is unmatched and earns zero.
Let \(\ell_t\) be the minimum earnings among positive-mass atoms incident to \(t\), also including zero whenever unmatched mass at \(t\) is positive. Set \(\beta_t=\max_{u\in N_H(t)}(w_{tu}-\ell_u)^+\), with an empty maximum equal to zero. Alternatives include other individuals of the current partner's type.
The allocation is stable if \(\ell_a+\ell_b\ge w_{ab}\) for every edge, and satisfies \(\epsilon\)-unequal division if every positive-mass atom on \((a,b)\) satisfies \(\left|x-\beta_a-r_{ab}(w_{ab}-\beta_a-\beta_b)\right|\le\epsilon\).
Does finding such a stable \(\epsilon\)-unequal-division allocation, or certifying nonexistence, admit an algorithm polynomial in \(m,\tau,L,1/\epsilon\), or is this approximation problem NP-hard even when \(1/\epsilon\) is polynomially bounded in the input length?
For finite agent networks with values bounded by one, a stable \(\epsilon\)-unequal-division outcome can be found, or nonexistence certified, in time polynomial in the input and \(1/\epsilon\); outside alternatives exclude the particular matched individual ([Kanoria](https://arxiv.org/abs/1008.0212)). No result settling the mass problem defined above was identified in the literature search.
The problem admits an exact polynomial-time algorithm in \(m,\tau,L\), independently of \(1/\epsilon\). A stable allocation always exists, and every stable allocation satisfies exact unequal division under the stated definition of alternatives.
The decisive feature is that alternatives include the current partner’s type. This makes the bargaining surplus on every used edge zero.
Fix a stable allocation. Call an edge *used* if its measure has positive total mass.
Consider any positive-mass atom \((x,y)\) on a used edge \((a,b)\). By the definition of minimum earnings,
\(x\ge \ell_a,\qquad y\ge \ell_b.\)
Feasibility and stability give
\(w_{ab}=x+y\ge \ell_a+\ell_b\ge w_{ab}.\)
Consequently, all these inequalities are equalities. In particular,
\(x=\ell_a,\qquad y=\ell_b,\qquad \ell_a+\ell_b=w_{ab}.\)
Thus all matched individuals of a given type receive the same earnings, and every used edge is tight for the stability inequalities. This applies to every atom, regardless of how many atoms the allocation initially contains.
For every type \(t\) and neighbor \(u\), stability implies
\(w_{tu}-\ell_u\le \ell_t.\)
Because \(\ell_t\ge 0\), taking positive parts and then the maximum gives
\(\beta_t\le \ell_t.\)
If type \(t\) has positive matched mass, it is incident to a used edge \((t,u)\). Section 1 gives
\(w_{tu}-\ell_u=\ell_t.\)
This neighbor is included in the maximum defining \(\beta_t\), so \(\beta_t\ge\ell_t\). Hence \(\beta_t=\ell_t\).
If type \(t\) has no matched mass, its positive mass \(\mu_t\) is entirely unmatched. Thus \(\ell_t=0\), and the inequality \(\beta_t\le\ell_t\) again gives \(\beta_t=\ell_t\).
We have proved, for every type,
\(\beta_t=\ell_t.\)
Now consider an atom \((x,y)\) on a used edge \((a,b)\). Section 1 implies
\(w_{ab}-\beta_a-\beta_b=w_{ab}-\ell_a-\ell_b=0.\)
Therefore,
\(x-\beta_a-r_{ab}(w_{ab}-\beta_a-\beta_b)=\ell_a-\ell_a-r_{ab}\cdot 0=0.\)
This proves exact unequal division. The shares may be arbitrary subject to the stated assumptions; their values do not affect this conclusion.
We construct one using a pair of linear programs.
For each edge \((a,b)\), let \(q_{ab}\ge 0\) denote its matched mass. Write
\(d_t=\sum_{e\ni t}q_e.\)
The primal linear program maximizes total match value:
\(\displaystyle \text{maximize }\sum_{(a,b)\in E}w_{ab}q_{ab}\)
subject to
\(d_t\le\mu_t\quad\text{for every }t,\qquad q_{ab}\ge 0\quad\text{for every }(a,b)\in E.\)
Its dual has one variable \(p_t\) per type:
\(\displaystyle \text{minimize }\sum_t\mu_t p_t\)
subject to
\(p_a+p_b\ge w_{ab}\quad\text{for every }(a,b)\in E,\qquad p_t\ge 0\quad\text{for every }t.\)
The primal is feasible by taking all \(q_{ab}=0\). Its objective is bounded: each edge mass is counted twice in the incident totals, so
\(\displaystyle 2\sum_{(a,b)\in E}q_{ab}=\sum_t d_t\le\sum_t\mu_t=1.\)
Since \(w_{ab}\le 1\), the primal objective is at most \(1/2\). The dual is feasible, for example by taking every \(p_t=1\).
Finite-dimensional linear programming strong duality therefore supplies optimal primal and dual solutions \(q,p\) with equal objectives. Their objective difference can be written explicitly as
\(\displaystyle 0=\sum_t p_t(\mu_t-d_t)+\sum_{(a,b)\in E}q_{ab}(p_a+p_b-w_{ab}).\)
Every summand is nonnegative by primal and dual feasibility. Consequently,
\(d_t<\mu_t\ \Longrightarrow\ p_t=0,\)
and
\(q_{ab}>0\ \Longrightarrow\ p_a+p_b=w_{ab}.\)
Choose rational optimal solutions, whose polynomial encoding bounds are justified below. For each edge with \(q_{ab}>0\), put one atom of mass \(q_{ab}\) at the earnings pair \((p_a,p_b)\). Give every other edge the zero measure. Leave mass \(\mu_t-d_t\) unmatched at type \(t\).
The capacity constraints hold by primal feasibility. Each atom has nonnegative earnings summing to \(w_{ab}\), by the implication for positive \(q_{ab}\).
We next verify that the resulting allocation has \(\ell_t=p_t\):
Dual feasibility now gives
\(\ell_a+\ell_b=p_a+p_b\ge w_{ab}\)
on every edge. Thus the constructed allocation is stable. Section 2 proves that it satisfies exact unequal division.
This argument also covers isolated types and the case \(E=\varnothing\).
We use the standard exact rational linear programming theorem: a linear program with rational coefficients encoded in binary can be solved, including production of a rational optimal solution when an optimum exists, in time polynomial in its dimensions and total coefficient encoding length. The returned solution has polynomial encoding length.
Here the primal has \(m\) variables and \(\tau\) capacity constraints; the dual has \(\tau\) variables and \(m\) edge constraints. Apart from zero and unit coefficients, their coefficients are the input masses and edge values. Their total encoding length is polynomial in \(m,\tau,L\). The feasibility and boundedness hypotheses were verified in Section 3.
Solving both programs therefore takes polynomial time in \(m,\tau,L\). The allocation has at most one atom per edge, so at most \(m\) atoms in total, with rational masses and earnings of polynomial encoding length.
Neither \(\epsilon\) nor the shares enter the algorithm. Every valid instance receives a stable exact unequal-division allocation, which also satisfies its requested \(\epsilon\)-unequal-division inequalities. Thus nonexistence never occurs under the given assumptions.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem correctly. The construction yields a rational stable allocation in polynomial time, and the argument that every stable allocation satisfies exact unequal division is valid. No major or minor issues were found.
Primal feasibility, primal boundedness, and dual feasibility are all verified. The identity \(2\sum_e q_e=\sum_t d_t\) correctly counts each edge mass twice, yielding the stated objective bound. These facts satisfy the hypotheses for finite-dimensional LP strong duality and optimal attainment.
Isolated types and the empty-edge case are covered: their incident matched mass is zero, so the unsaturated-type argument applies.
No additional clarification or repair is needed.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.