Answer: Polynomial-time solvable: every instance admits a finite rational better-response sequence from its initial allocation to stability, constructible in polynomial binary time.
Theorem 6. — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor every real-valued allocation instance and given feasible allo- cation, there is a sequence of better responses leading to a stable allocation in O(|V |2|E|) time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a bipartite market with finite job and machine type sets \(J\) and \(M\), positive rational masses \(\mu_t\), common strict rankings within each type, per-capita quotas \(q_t\), pool quotas \(Q_t=\mu_tq_t\), pool-pair capacities \(K_{jm}\), and a feasible initial flow \(x^0\), compute a finite sequence of type-pool better-response reallocations ending at a stable allocation. Does every such instance admit such a sequence, and what running time suffices in the support size \(\tau=|J|+|M|\), the compatible-pair set \(E_T\), and the input bit length?
A society is given by its support: disjoint finite job and machine type sets \(J,M\), with each type's positive mass \(\mu_t\) encoded as a binary rational. Masses need not sum to one. Let \(\tau=|J|+|M|\) be the support size, not the number of possible types, and let \(m=|M|\).
The input includes compatible pairs \(E_T\subseteq J\times M\), nonnegative rational per-capita quotas \(q_t\), pool quotas \(Q_t=\mu_tq_t\), nonnegative rational pair capacities \(K_{jm}\), and a rational feasible initial allocation \(x^0\). Each type strictly ranks its compatible opposite types; all members share that ranking. Let \(L\) be the total binary input length.
An allocation assigns divisible quantities \(x_{jm}\geq0\), with \(x_{jm}\leq K_{jm}\) and \(x(t):=\sum_{e\ni t}x_e\leq Q_t\). These are pool constraints; no individual-level realization is required.
A pair \(jm\) blocks \(x\) when \(x_{jm}<K_{jm}\) and each endpoint \(t\in\{j,m\}\) either has \(x(t)<Q_t\) or ranks \(jm\) above some incident pair carrying positive allocation. Stability means absence of blocking pairs.
A type-pool better-response move chooses a blocking pair \(jm\), increases its allocation by a positive rational amount, and may decrease allocations only on incident pairs that the rejecting endpoint ranks below \(jm\). All other coordinates remain unchanged and the resulting allocation must be feasible. Refusals may exceed what is necessary to restore feasibility; jobs initiate moves.
Does every instance admit a finite better-response sequence from \(x^0\) to stability, and is constructing such a sequence polynomial-time in \(m,\tau,|E_T|,L\), or NP-hard?
Known results: finite-vertex stable allocation admits a better-response path from any feasible allocation in \(O(|V|^2|E|)\) arithmetic time, even with real quotas and capacities. The [later full version](https://real.mtak.hu/83554/1/MTDP1820.pdf) explicitly establishes polynomial-length paths of individual better-response moves.
Those results already encompass the pool allocation model defined above; a separate open continuous complexity target is therefore not established.
Every instance admits a finite rational better-response sequence from $x^0$ to stability, and such a sequence can be constructed in polynomial binary time in $m,\tau,|E_T|,L$.
The obstruction identified in the verifier report is real: the proposed cycle expansion need not reach the accelerated endpoint. We repair it by restoring the temporary refusal after completing the cycle. This restoration is itself a legal better-response move.
Construct the bipartite graph
$$
G=(J\cup M,E_T),
$$
with vertex quotas $Q_t=\mu_tq_t$, edge capacities $K_{jm}$, and the given strict preferences.
Its feasible allocations are exactly the allocations in the question. The blocking definitions also coincide: when a vertex has positive allocation, an edge is preferred to some positively allocated incident edge if and only if it is preferred to the worst such edge. When there is no positive incident allocation, that preference alternative is false in both definitions.
Consequently, one vertex per supported type gives an exact representation. No expansion according to the masses is necessary. The hypotheses of the supplied stable-allocation theorem hold: the graph is finite and bipartite, quotas and capacities are nonnegative, preferences are strict, and $x^0$ is feasible.
If $E_T$ is empty, the empty sequence suffices. Henceforth suppose it is nonempty.
We use the accelerated construction underlying the supplied theorem. With $n$ vertices and $h$ edges, it performs $O(nh)$ simultaneous augmentations along simple alternating paths or cycles. The first proposal blocks; every proposal is preferred at its active endpoint to its paired refusal, which is that endpoint’s worst positive edge. Proposals gain a common positive amount and refusals lose it. Paths can additionally reject worse edges at their starting passive vertex. Numerical operations are sums, differences, minima and maxima.
Its second phase adds a dummy job $d$, with
$$
Q_d=\sum_{m\in M}Q_m,\qquad
K_{dm}=\max_{m'\in M}Q_{m'},\qquad
x_{dm}=Q_m-x(m),
$$
ranks $d$ last at each machine, and swaps the active and passive sides. The final projection onto the original graph is stable. These are properties of the accelerated construction; we do not use its proposed individual cycle expansion. See Algorithm 2, Sections 5.1–5.2, and Theorem 8 of [Cseh–Skutella, *Paths to stable allocations*](https://real.mtak.hu/83554/1/MTDP1820.pdf).
We now prove that every simultaneous augmentation can be realized exactly by a short sequence of legal moves.
Lemma. Suppose $x$ and $z$ are feasible allocations, and their differences consist of:
Then $e$ blocks $x$, and the transition is a legal better-response move.
Proof. Since
$$
x_e<z_e\leq K_e,
$$
the edge is unsaturated before the transition.
Fix an endpoint $t$ of $e$. If $x(t)<Q_t$, its blocking condition holds through unused quota. Otherwise $x(t)=Q_t$. Feasibility of $z$ implies
$$
Q_t+\delta-
\sum_{\substack{f\ni t\\f\neq e}}(x_f-z_f)
=z(t)\leq Q_t.
$$
Thus the sum of decreases incident to $t$ is at least $\delta>0$. Some such edge $f$ decreases strictly. Since $z_f\geq0$, it previously had $x_f>0$; by hypothesis, $t$ prefers $e$ to $f$.
Both endpoints therefore satisfy the blocking condition. All other requirements of a move hold by hypothesis. $\square$
This proves the useful legality argument from the notes without relying on the disputed endpoint-constrained linear program.
For this section, write the bipartition as $U\cup V$, allowing either side to be designated active. Consider a simple alternating path
$$
v_1,u_1,v_2,u_2,\ldots,v_s,u_s,v_{s+1}.
$$
Set
$$
p_i=u_iv_i,\qquad r_i=u_iv_{i+1}.
$$
Suppose $p_1$ blocks the initial allocation $x$, and each $u_i$ prefers $p_i$ to $r_i$.
Let the simultaneous augmentation amount be $a>0$, satisfying
$$
a\leq x_{r_i},
\qquad
a\leq K_{p_i}-x_{p_i}
\quad\text{for every }i.
$$
Every $p_i$ gains $a$ and every $r_i$ loses $a$. At $v_1$, the augmentation additionally rejects amounts $b_f$ from edges ranked below $p_1$, where
$$
0\leq b_f\leq x_f,\qquad
\sum_f b_f=
\max\{0,a-(Q_{v_1}-x(v_1))\}.
$$
These rejection edges lie outside the path: its only edge incident to $v_1$ is $p_1$.
Perform the following $s$ transitions:
The first transition is feasible. At $u_1$, the increase and decrease cancel; at $v_1$, the additional rejections prevent quota violation. All remaining changes are decreases.
Before transition $i\geq2$, vertex $v_i$ has lost $a$ on $r_{i-1}$ and has received no increase. It therefore has at least $a$ unused quota. At $u_i$, the increase and decrease cancel, while any earlier additional rejection could only have lowered its total. Each $r_i$ still has its original allocation, because no additional rejection edge belongs to the path. Thus all transitions preserve nonnegativity, capacities and quotas.
Every decrease is authorized by an endpoint ranking the increased edge above the decreased edge. The lemma in Section 3 proves legality of every transition.
The resulting allocation is exactly the simultaneous path endpoint.
Consider a simple alternating cycle
$$
v_1,u_1,v_2,u_2,\ldots,v_s,u_s,v_1,
$$
where $s\geq2$. Define
$$
p_i=u_iv_i,\qquad r_i=u_iv_{i+1},
\qquad v_{s+1}=v_1.
$$
Again, $p_1$ blocks $x$, each $u_i$ prefers $p_i$ to $r_i$, and
$$
0<a\leq x_{r_i},\qquad
a\leq K_{p_i}-x_{p_i}.
$$
Let $y$ be the simultaneous endpoint:
$$
y_{p_i}=x_{p_i}+a,\qquad
y_{r_i}=x_{r_i}-a,
$$
with all other coordinates unchanged. This allocation is feasible: every cycle vertex receives and loses the same amount.
Put
$$
s_1=Q_{v_1}-x(v_1).
$$
If $s_1>0$, choose
$$
\varepsilon=\frac12\min\{a,s_1\},
$$
and make no temporary rejection at $v_1$.
If $s_1=0$, blocking of $p_1$ guarantees an incident edge $f$ with $x_f>0$ that $v_1$ ranks below $p_1$. Choose one and put
$$
\varepsilon=\frac12\min\{a,x_f\}.
$$
The only cycle edges incident to $v_1$ are $p_1$ and $r_s$. Consequently, either $f=r_s$ or $f$ is outside the cycle.
In both cases,
$$
0<\varepsilon<a.
$$
Make the first transition:
At $u_1$, the total decreases by $a-\varepsilon$. At $v_1$, either unused quota accommodates the increase or the decrease on $f$ offsets it. All other affected totals decrease. Coordinate bounds hold by the choice of $\varepsilon$.
The transition is therefore feasible, and every decrease is permitted. Section 3 proves its legality.
For $i=2,\ldots,s$, increase $p_i$ by $a$ and decrease $r_i$ by $a$, with one exception: if the initialization decreased $f=r_s$, the last transition decreases $r_s$ by only $a-\varepsilon$.
Before transition $i$, vertex $v_i$ has lost $a$ on $r_{i-1}$, so it has at least $a$ free quota. Each proposal has its original allocation before its increase, hence has enough residual capacity.
Normally the changes at $u_i$ cancel. If initialization decreased an external edge incident to $u_i$, that only gives additional slack. In the exceptional case $f=r_s$, vertex $u_s$ previously lost $\varepsilon$, and the last transition restores its total by adding $a$ and subtracting $a-\varepsilon$.
Each refusal has sufficient allocation: it is unchanged before its transition, except that $r_s$ may already have lost $\varepsilon$, leaving at least $a-\varepsilon$.
Thus every transition is feasible. All decreases are on the corresponding $r_i$, which its active endpoint ranks below $p_i$. Section 3 again proves legality.
Increase $p_1$ by $a-\varepsilon$, without any decrease.
Vertex $u_1$ has at least this much unused quota from initialization. At $v_1$, its current total is:
$$ x(v_1)+\varepsilon-a \quad\text{if initialization used unused quota}, $$
$$ x(v_1)-(a-\varepsilon) \quad\text{if initialization decreased }r_s, $$
or
$$ x(v_1)-a \quad\text{if initialization decreased an external }f. $$
In every case, $v_1$ has at least $a-\varepsilon$ free quota. The final value on $p_1$ is $x_{p_1}+a\leq K_{p_1}$. Hence this transition is feasible and legal.
If initialization used unused quota or decreased $r_s$, the allocation now equals $y$.
Otherwise it equals $y$ except that the external edge $f$ has allocation $y_f-\varepsilon$. Restore $f$ by increasing it by $\varepsilon$, with no decreases.
Both endpoints have totals exactly $\varepsilon$ below their totals in the feasible allocation $y$. They therefore each have at least $\varepsilon$ unused quota. The restoration also respects the capacity of $f$. It is feasible and, by Section 3, a legal better-response move.
We have reached exactly $y$ in at most $s+2$ individual moves.
In that example, choose $\varepsilon=\tfrac12$ and temporarily reject $\tfrac12$ from $j_3m_1$. The moves are:
Before the last move, both $j_3$ and $m_1$ have unused quota $\tfrac12$. The restoration therefore blocks and reaches the accelerated stable endpoint exactly.
The verifier correctly rejected the three-move order; the additional restoration repairs it.
In the first phase, Sections 4–5 apply directly.
For the auxiliary second phase, the dummy initialization is feasible:
$$
0\leq Q_m-x(m)\leq Q_m\leq K_{dm},
$$
and
$$
\sum_m x_{dm}\leq\sum_m Q_m=Q_d.
$$
It changes no original coordinate.
After the sides are swapped, machines are the active vertices. A proposal must be preferred by its active machine to its worst positively allocated edge. Since the dummy edge is ranked last, no dummy edge can be a proposal.
It follows that:
Dummy edges may decrease during a path expansion. Project each transition onto the original edges. Projection preserves feasibility, and every remaining decrease is permitted by the unchanged original preferences. Each projected transition still increases an original edge positively. Section 3 therefore proves that it is a legal move in the original instance.
The definition of a move is symmetric in its two endpoints apart from initiation. For every projected transition, designate the original job endpoint as the initiator.
Each expanded augmentation reaches its accelerated endpoint exactly. Consequently, the expansions concatenate without changing the subsequent accelerated computation. Its final projection is stable by the supplied constructive theorem.
This establishes a finite better-response path. We next establish polynomial binary complexity.
Computing $Q_t=\mu_tq_t$ preserves polynomial encoding length: multiplication adds the numerator and denominator bit lengths.
Let $D$ be the product of the denominators of all transformed quotas, capacities and initial allocation coordinates. Then
$$
\log_2 D=O(L),
$$
and all these quantities belong to $D^{-1}\mathbb Z$.
Set
$$
W=\max\bigl(\{1\}\cup\{Q_t:t\in J\cup M\}
\cup\{K_e:e\in E_T\}\bigr).
$$
Its binary magnitude satisfies $\log_2 W=O(L)$. Auxiliary edge capacities are at most $W$, and the dummy quota is at most $mW$.
The accelerated numerical operations preserve $D^{-1}\mathbb Z$. The additional path rejections can be computed by successively taking the minimum of the remaining rejection amount and the allocation on a permitted edge. These operations also preserve that lattice.
All allocation coordinates are bounded by their capacities. Sums used in quota and augmentation calculations are bounded by a polynomial in $\tau$ times $W$. Thus their integer numerators over denominator $D$ have
$$
O\bigl(L+\log(\tau+1)\bigr)
$$
bits.
Each cycle initialization chooses
$$
\varepsilon=\frac12\min\{a,s_1\}
\quad\text{or}\quad
\varepsilon=\frac12\min\{a,x_f\}.
$$
Thus its intermediate allocations and move quantities belong to $(2D)^{-1}\mathbb Z$.
Crucially, the repair reaches the exact accelerated endpoint, which belongs to $D^{-1}\mathbb Z$. The next augmentation starts on that original lattice. Successive cycle repairs therefore do not accumulate additional powers of two in their denominators.
Every output quantity consequently has polynomial binary encoding length.
The auxiliary graph has at most
$$
n'=\tau+1,\qquad h'=|E_T|+m
$$
vertices and edges, respectively. The known construction uses $O(n'h')$ augmentations. Each expansion uses $O(n')$ individual moves. Hence the total number of moves is
$$
O\!\left((\tau+1)^2(|E_T|+m)\right).
$$
The accelerated computation and the expansions require polynomially many arithmetic operations and comparisons on numbers of polynomial bit length. They therefore run in polynomial binary time. Outputting each increased edge, its increment, and the permitted decreases also takes polynomial time.
This proves polynomial-time construction of the requested rational sequence. The guarantee concerns a constructible path; it does not assert convergence under every possible choice of moves.
⟨structured verdict parsed — rendered above⟩
Assessment: proved with minor gaps. The output establishes the requested finite rational better-response sequence and polynomial binary-time construction. The cycle restoration is valid. I found no false central step or gap requiring new mathematics.
The remaining issues concern specifying the auxiliary preferences, matching path rejections to the cited algorithm, and supplying the data for the illustrative example.
The reduction is exact:
For a finite strictly ordered set of positively allocated incident edges, preferring an edge to some member is equivalent to preferring it to the worst member. The empty-set case is correctly distinguished.
Thus feasibility and blocking coincide with the finite stable-allocation model. No individual realization or expansion by mass is needed.
The hypotheses are satisfied, including nonnegative quotas and capacities. Zero quotas and zero capacities cause no exception: they cannot support the positive increases required by a blocking move. The case $E_T=\varnothing$ is correctly handled before the maximum defining dummy-edge capacity is used.
Finding: correct.
I checked the cited [Cseh–Skutella paper](https://real.mtak.hu/83554/1/MTDP1820.pdf). Section 5.1 and Algorithm 2 support the claimed proposal/refusal structure, augmentation formulas, and $O(nh)$ augmentation bound. Section 5.2 supports the dummy construction, side swap, and stability of the final projection. Theorem 8 states the resulting better-response guarantee.
The source’s stopping rules produce the simple paths and cycles used in Sections 4–5. Its numerical augmentation formulas use sums, differences, and minima, consistent with the later lattice argument.
Minor issue: the output does not assign a strict preference order to the dummy job. The auxiliary instance formally requires one.
Minimum clarification: state that the dummy job receives an arbitrary strict ordering of its incident edges.
The lemma correctly establishes blocking from feasibility and the permitted pattern of changes.
The positive increase gives
$$
x_e<z_e\leq K_e.
$$
At an endpoint already at quota, feasibility forces total incident decreases of at least $\delta$. A strictly decreased edge previously carried positive allocation and, by hypothesis, is ranked below the increased edge at its rejecting endpoint.
An endpoint below quota already satisfies its blocking condition. These alternatives cover both endpoints, including all zero-quota cases allowed by feasibility.
The conclusion concerns the stated move model, which permits refusals exceeding the amount needed for feasibility. It would not automatically apply to a more restrictive move definition, but that is not the assigned problem.
Finding: correct.
The first transition respects capacities and nonnegativity. Its paired changes cancel at $u_1$, and the additional rejections prevent a quota violation at $v_1$.
For every subsequent transition, the preceding refusal has freed $a$ units at $v_i$. Simplicity ensures that no intervening proposal has consumed that slack. Additional rejection edges are outside the path, so they do not reduce a later refusal coordinate. They can only create additional slack at active vertices.
All decreases have the required preference authorization. The legality lemma therefore applies to each transition.
Coordinatewise, the final changes are exactly the specified proposal increases, refusal decreases, and additional rejections.
Minor issue: exact concatenation requires the $b_f$ values to match the accelerated algorithm’s rejections. Algorithm 2 rejects from the starting vertex’s worst allocated edges. Section 7.1 instead describes successive minima on “a permitted edge,” without specifying this ordering. Arbitrary permitted choices need not reproduce that algorithm’s endpoint.
Minimum clarification: explicitly take the $b_f$ values from the cited augmentation, processing the starting vertex’s worst eligible edges first.
This is an implementation clarification; the expansion itself correctly realizes any specified admissible $b_f$ values.
Both definitions of $\varepsilon$ give
$$
0<\varepsilon<a.
$$
If $v_1$ has slack, its increase fits within that slack. Otherwise blocking supplies a positively allocated, worse incident edge $f$, and its temporary decrease offsets the increase.
The decrease of $r_1$ by $a$ is feasible. The edges $r_1$ and $f$ are distinct because the cycle is simple and $s\geq2$.
Finding: correct.
Before proposal $p_i$ increases, refusal $r_{i-1}$ has freed $a$ units at $v_i$. Each proposal still has its original coordinate value.
Normally the changes cancel at $u_i$. In the exceptional case $f=r_s$, initialization has already freed $\varepsilon$ at $u_s$, exactly accommodating the net increase in the last propagation transition.
The remaining allocation on $r_s$ is sufficient for its adjusted decrease of $a-\varepsilon$.
Finding: correct.
The displayed totals at $v_1$ are correct in all three cases. Each permits an additional increase of $a-\varepsilon$. Initialization also left that much slack at $u_1$.
The final proposal coordinate respects its capacity because its total increase is $a$.
Finding: correct.
After completing $p_1$, the allocation differs from $y$ only by the deficit $\varepsilon$ on $f$. Consequently, both endpoints of $f$ have totals $\varepsilon$ below their totals in feasible $y$.
They therefore have sufficient unused quota, and increasing $f$ to $y_f$ respects capacity. Both endpoints satisfy the slack alternative of blocking. No preference comparison is needed for this increase-only move.
The restoration reaches exactly $y$, and the count of at most $s+2$ moves is correct.
Finding: correct. The proposed restoration resolves the stated endpoint discrepancy.
Minor issue: Section 5.5 refers to “the verifier’s example,” but its quotas, capacities, initial allocation, and rankings are absent from the supplied inputs. Its numerical and preference claims cannot be independently checked.
Minimum clarification: supply the referenced instance data or remove this illustrative subsection. The general cycle proof does not depend on it.
The dummy initialization satisfies all edge and vertex bounds.
After swapping sides, every proposal must be preferred by its active machine to a positive refusal edge. A dummy edge, ranked last, cannot satisfy that requirement.
The consequences listed in Section 6 follow:
Projection preserves feasibility and every surviving refusal’s preference authorization. Each projected transition still has exactly one positive increase on an original edge. Applying the legality lemma after projection is valid.
Designating the original job endpoint as initiator satisfies the assigned move definition, whose remaining conditions are symmetric.
Exact endpoint agreement permits concatenation with the accelerated computation, subject to the minor path-rejection clarification above.
Finding: correct.
The binary complexity argument checks out.
Computing the products $Q_t=\mu_tq_t$ increases aggregate encoding length by only a constant factor. Therefore the product of all transformed denominators satisfies
$$
\log_2 D=O(L).
$$
The accelerated arithmetic preserves $D^{-1}\mathbb Z$. Capacities bound coordinates; the dummy quota and relevant sums have magnitude bounded by a polynomial in $\tau$ times $W$. Their numerators over denominator $D$ consequently have the asserted polynomial bit length.
A cycle repair introduces only the denominator factor $2$. Since it returns exactly to an accelerated endpoint on $D^{-1}\mathbb Z$, repeated repairs do not accumulate denominator factors.
The auxiliary graph bounds and move count are valid:
$$
n'\leq\tau+1,\qquad h'\leq|E_T|+m,
$$
$$
O\!\left((\tau+1)^2(|E_T|+m)\right).
$$
Each move changes only polynomially many coordinates, each of polynomial encoding length. The arithmetic, comparisons, and explicit output therefore take polynomial binary time.
Finding: correct. The result guarantees a constructible sequence, not convergence under every possible move choice.
⟨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.