Answer: The exact resulting circulation is computable in time polynomial in \(m,\tau,Q,L\).
Corollary 10 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateSingle-Serial-IR rules can be efficiently implemented through their alternative definition. The runtime is bounded by O(n6 Q ).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set of types \(T\), rational masses \(\mu_t>0\) summing to \(1\), integer capacities \(q_t\), rankings \(\succ_t\) of good types, and a schedule containing each type \(t\) exactly \(q_t\) times, compute the resulting type-level circulation. At each scheduled phase for type \(t\), assign mass \(\mu_t\) one unit of acceptable goods per unit of agent mass, choosing the lexicographically best assignment in \(\succ_t\) among those that leave an individually rational completion for all remaining mass. Each good type \(u\) supplies \(q_u\mu_u\); the final allocation must use all supplies and leave every type with an acceptable bundle.
A society is given by its support: a list \(T\) of \(\tau\geq2\) types with positive binary-rational masses \(\mu_t\) summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
Each type owns its own good type, so the number of good types is \(m=\tau\). Input includes binary-encoded capacities \(q_t\in\mathbb Z_{\geq0}\), strict complete rankings \(\succ_t\) of \(T\), and an explicitly listed schedule \(\pi\) containing each \(t\) exactly \(q_t\) times; let \(Q=\sum_tq_t\) and let \(L\) be the total input bit length.
Good \(u\) is acceptable to \(t\) exactly when \(u=t\) or \(u\succ_t t\). Goods are divisible; an acceptable bundle contains no positive quantity of an unacceptable good.
A type-level circulation is a nonnegative matrix \(X\) with \(\sum_uX_{tu}=q_t\mu_t\), \(\sum_tX_{tu}=q_u\mu_u\), and \(X_{tu}=0\) whenever \(u\) is unacceptable to \(t\). A partial allocation \(x\) has an individually rational completion when such an \(X\) exists with \(X\geq x\) coordinatewise.
Start with \(x=0\). At each scheduled occurrence of \(t\), choose a nonnegative increment \(z\) with \(\sum_uz_u=\mu_t\), supported on acceptable goods, such that adding \(z\) to row \(t\) leaves an individually rational completion. Choose the lexicographically greatest \(z\), with coordinates ordered by \(\succ_t\), and retain all earlier assignments. Output the final matrix exactly, as binary rationals.
Can this resulting circulation be computed in time polynomial in \(m,\tau,Q,L\), or is its computation NP-hard?
For discrete agents with indivisible goods and an explicitly listed schedule, Single-Serial-IR outcomes can be computed in \(O(n^6Q)\) time, where \(n\) is the number of agents and \(Q\) the schedule length. [Source](https://doi.org/10.1016/j.geb.2022.10.006). This result concerns indivisible unit choices and does not establish the complexity of the mass-valued phases defined here.
The resulting circulation can be computed exactly in time polynomial in \(m,\tau,Q,L\). The key is that each phase is a transportation problem, and all lexicographic optima remain integral after scaling by a single common denominator.
If \(Q=0\), the output is the zero matrix. Henceforth assume \(Q>0\).
Write each input mass as \(\mu_t=p_t/d_t\), with positive integers \(p_t,d_t\), and set
\(D=\prod_{t\in T}d_t,\qquad a_t=D\mu_t.\)
Then every \(a_t\) is a positive integer, and \(\sum_t a_t=D\). The binary length of \(D\) is \(O(L)\), because the sum of the binary lengths of the input denominators is at most \(L\). If “binary rational” means dyadic rational, \(D\) is also a power of two.
We work in units of \(1/D\). Thus the prescribed total for row and column \(t\) is \(q_ta_t\), and an occurrence of type \(t\) assigns exactly \(a_t\) scaled units.
Let \(b=Dx\) denote the scaled partial allocation. We will prove inductively that \(b\) remains integral.
Suppose the next scheduled type is \(t\), and define the residual row and column totals by
\(R_s=q_sa_s-\sum_u b_{su},\qquad C_u=q_ua_u-\sum_s b_{su}.\)
The induction invariant is that \(b\) has an acceptable completion with the prescribed totals. In particular, all these residual totals are nonnegative.
If \(t\) has already occurred \(k_t\) times, then its row has received exactly \(k_ta_t\) scaled units. Because another occurrence remains,
\(R_t=(q_t-k_t)a_t\geq a_t.\)
Construct a transportation problem with:
Both rows associated with \(t\) have edges precisely to goods acceptable to \(t\). Every other row has edges precisely to goods acceptable to its type. Variables on allowed edges are nonnegative.
Let \(w_u\) be the amount sent from the current row to column \(u\). The feasible vectors \(w\) are exactly the scaled feasible increments in the question.
Indeed, given such a transportation flow, combine the current and future rows of \(t\), and add all residual assignments to \(b\). This yields an acceptable completion containing \(b+w\).
Conversely, suppose \(b+w\) has a scaled completion \(F\). Use \(w\) as the current row, \(F_{tu}-b_{tu}-w_u\) as the future row, and \(F_{su}-b_{su}\) for every other row. These quantities are nonnegative and have exactly the required supplies and demands.
The transportation problem is feasible: take any residual completion of \(b\), and split \(a_t\) units from its row \(t\) into the current row. Divisibility and \(R_t\geq a_t\) permit this split.
Its feasible set is compact, since each variable is nonnegative and bounded by the total residual supply. Consequently, each successive coordinate maximum needed for lexicographic optimization exists.
We use the following lemma, including its proof to address exactness.
Lemma. Consider a feasible transportation problem on any finite bipartite graph, with nonnegative integer row supplies and column demands. Every linear objective has an integral optimal solution.
Proof. The feasible set is compact, so an optimum exists. Among all optimal solutions, choose one with the fewest positive variables.
Suppose its positive-support graph contains a cycle. A bipartite cycle has even length. Alternately add and subtract a sufficiently small quantity along its edges. Both signs of this perturbation preserve all row and column totals and remain nonnegative.
If the objective changes under this perturbation, one sign improves it, contradicting optimality. Therefore the objective is unchanged. Choose the perturbation magnitude so that an edge being decreased reaches zero. This preserves optimality and strictly reduces the number of positive variables, another contradiction.
Thus the positive-support graph is a forest. At a leaf, the value of its sole positive incident edge equals that vertex’s remaining supply or demand, which is an integer. Remove this edge and leaf, and subtract its integer value from the neighboring vertex’s remaining total. Repeating this process shows that every positive variable is integral. \(\square\)
Now consider a phase in which some current-row coordinates have already been fixed to integer values. Fixing such an edge to value \(v\) is equivalent to deleting the edge and subtracting \(v\) from its row supply and column demand. Hence the remaining problem is again a transportation problem with integer margins.
Applying the lemma to the next current-row coordinate proves that its maximum is an integer. Inducting over the ranking proves that the entire lexicographically greatest vector \(w\) is integral.
This applies to the optimization over all real feasible flows, so restricting the coordinate search to integers does not change the specified outcome.
Process acceptable goods in the order specified by \(\succ_t\). Unacceptable coordinates are identically zero.
Suppose earlier current-row coordinates have been fixed, and the next coordinate is \(w_j\). Its maximum lies in the integer interval \([0,a_t]\), by the preceding lemma.
For an integer \(h\) in this interval, test whether there is a feasible transportation flow satisfying the fixed coordinates and \(w_j\geq h\):
For the last step, add a source with an edge to each row, whose capacity is that row’s supply. Add an edge from each column to a sink, whose capacity is that column’s demand. Every allowed row-column edge receives capacity
\(N=\sum_s q_sa_s\leq QD.\)
This bound cannot exclude any feasible transportation flow, since every edge carries at most the total supply. The problem is feasible exactly when a maximum flow saturates all source-row edges: total row supply equals total column demand, so such saturation also forces every column demand to be met.
The feasibility predicate is monotone in \(h\). Binary search therefore finds the largest feasible integer \(h\). Since the real coordinate optimum is integral, this is its exact maximum. Fix that value and continue.
After every current-row coordinate has been fixed, their sum is \(a_t\), because the remaining constraints are feasible. Update
\(b_{tu}\leftarrow b_{tu}+w_u.\)
The updated matrix is integral and has an acceptable completion, establishing the induction invariant for the next phase.
Sequential coordinate maximization is precisely lexicographic maximization: every coordinate is maximized subject to the already optimal values of all preceding coordinates. Thus the computed increment agrees with the rule in the question.
Initially, the diagonal matrix with entries \(q_ta_t\) is an acceptable completion of \(b=0\), since every type accepts its own good.
The preceding construction therefore applies inductively to every occurrence in the schedule.
At the end, each type \(t\) has received exactly \(q_ta_t\) scaled units. Let \(F\geq b\) be an acceptable completion guaranteed by the invariant. For every row \(t\),
\(\sum_u(F_{tu}-b_{tu})=q_ta_t-q_ta_t=0.\)
All differences are nonnegative, so they are all zero. Hence \(F=b\): the final matrix itself has the prescribed column totals and is an acceptable circulation.
Returning \(b/D\) therefore gives exactly the requested outcome.
Each feasibility network has at most \(2\tau+3\) vertices and \(O(\tau^2)\) edges. All capacities are integers at most \(QD\), with binary length
\(O(L+\log(Q+1)).\)
The shortest-augmenting-path maximum-flow algorithm uses \(O(VE^2)\) elementary operations independently of capacity magnitudes. Thus each feasibility test uses \(O(\tau^5)\) operations on integers of the above bit length. [Edmonds and Karp](https://ftp.eecs.umich.edu/~pettie/matching/Edmonds-Karp-network-flow.pdf)
There are at most \(m=\tau\) optimized coordinates per occurrence. Each binary search uses \(O(1+\log(D+1))=O(L+1)\) feasibility tests. Across the explicit schedule, this gives
\(O\!\left(Q\tau^6(L+1)\right)\)
elementary flow operations, in addition to polynomial preprocessing. Accounting for integer arithmetic still gives polynomial bit complexity in \(m,\tau,Q,L\).
Finally, each output entry is \(b_{tu}/D\), with \(0\leq b_{tu}\leq QD\). Thus every entry has polynomial encoding length. Exact reduction of the fractions, if desired, also takes polynomial time.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The transportation formulation represents precisely the permitted continuous increments, the integrality argument justifies exact integer searches after scaling, and the running time is polynomial in the stated parameters. I found no major or minor issues requiring repair.
With explicitly binary-encoded rational masses, the product \(D=\prod_t d_t\) has bit length at most the sum of the denominator bit lengths, hence \(O(L)\). Each \(a_t=D\mu_t\) is a positive integer, and \(\sum_t a_t=D\).
Scaling by the positive constant \(D\) preserves feasibility, coordinatewise containment, and lexicographic comparisons. Thus computing the scaled increments suffices to compute the specified outcome. If the input rationals are dyadic, the product denominator is also dyadic, as stated.
An acceptable completion containing \(b\) implies that every residual row and column margin is nonnegative. Their total sums agree because both prescribed total sums are \(\sum_t q_ta_t\), and both subtract the total already allocated.
Before a scheduled occurrence of \(t\), the schedule guarantees \(k_t<q_t\). The earlier occurrences assigned exactly \(k_ta_t\) to its row, so the stated identity
\(R_t=(q_t-k_t)a_t\geq a_t\)
is correct.
The split into a current row of supply \(a_t\) and a future row of supply \(R_t-a_t\) preserves the residual total supply. Both rows use exactly the acceptable edges.
From a feasible transportation flow, combining the two rows and adding the residual assignments to \(b\) gives an acceptable completion containing the proposed increment.
Conversely, from a completion \(F\geq b+w\), the quantities specified in the output are nonnegative, have the required row totals, and reproduce the residual column demands. Therefore the projected feasible current-row vectors are exactly the increments permitted by the task.
The feasibility argument using a split of an existing residual completion is valid because goods are divisible. The feasible set is closed and bounded in finite dimension, so the compactness and existence claims are correct.
The lemma’s hypotheses are sufficient: a finite bipartite graph, nonnegative integer margins, and a nonempty feasible set.
Choosing an optimum with the fewest positive variables is legitimate because the number of positive variables takes values in a finite set of integers. On a positive-support cycle, sufficiently small perturbations in either alternating direction preserve feasibility. A nonzero objective change would allow improvement in one direction, contradicting optimality.
If the objective change is zero, increasing the perturbation until a decreased edge reaches zero preserves optimality and reduces support. No previously zero edge becomes positive because all perturbed edges belong to the positive-support cycle. This establishes that the selected support is a forest.
The leaf-removal argument correctly establishes integrality: each removed edge equals the leaf’s remaining integer margin, and subtracting its value preserves integer margins at the neighboring vertex. Isolated vertices and zero margins cause no difficulty.
Fixing an allowed edge to an integer value is equivalent to removing it and subtracting that value from its two incident margins. Since the fixed values arise from feasible optima, the resulting transportation problem remains feasible with nonnegative integer margins.
The lemma therefore applies at every coordinate optimization. It guarantees an integral optimal flow, so the maximum value of the selected coordinate is an integer even though optimization permits arbitrary real flows.
This establishes the necessary induction over coordinates without assuming integrality of the continuous rule in advance.
Reserving \(h\) units on the tested edge and retaining that edge correctly implements a lower bound rather than an equality. Removing previously fixed edges correctly implements their equalities.
Subtracting each reserved or fixed value from one row margin and one column margin preserves equality of total supply and demand. Negative margins correctly imply infeasibility.
The capacity \(N=\sum_s q_sa_s\leq QD\) on allowed row-column edges is sufficient: no residual edge can carry more than the original total supply. Saturating all source-row edges is equivalent to satisfying every row and column margin because total supply equals total demand.
The predicate is monotone in \(h\), and the coordinate optimum lies in \([0,a_t]\). Its proved integrality makes the largest feasible integer threshold its exact real optimum.
Skipping unacceptable coordinates is valid because they are identically zero. After all acceptable coordinates are fixed, feasibility forces their sum to equal \(a_t\). Sequential maximization therefore yields precisely the lexicographically greatest increment.
The diagonal matrix is a valid initial completion because each type accepts its own good.
Every computed increment preserves the completion invariant and adds exactly the required phase mass. At termination, all row totals equal their prescribed totals. For any completion \(F\geq b\), every row of \(F-b\) is nonnegative and sums to zero, forcing every entry to vanish.
Consequently, \(F=b\), so the final matrix itself satisfies the column totals and acceptability constraints. Returning \(b/D\) gives the exact requested outcome.
There are \(\tau+1\) transportation rows, \(\tau\) columns, and two additional network vertices, giving \(2\tau+3\) vertices and \(O(\tau^2)\) edges. All capacities have bit length \(O(L+\log(Q+1))\).
The stated Edmonds–Karp bound is applicable to these finite networks with nonnegative integer capacities: shortest augmenting paths give \(O(VE^2)\) arithmetic operations independently of capacity magnitudes. This standard bound is also documented in [MIT’s algorithm notes](https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2015/ba74f89434fc261d9366ebf136c04b52_MIT6_046JS15_Recitation7.pdf).
Substitution gives \(O(\tau^5)\) operations per feasibility test. Since \(a_t\leq D\), binary search uses \(O(1+\log(D+1))=O(L+1)\) tests per coordinate. Across at most \(\tau\) coordinates per occurrence and \(Q\) occurrences, the claimed \(O(Q\tau^6(L+1))\) flow-operation bound follows.
Arithmetic on the stated bit lengths, preprocessing, and fraction reduction all take polynomial time. Each output numerator is at most \(QD\), and the denominator has \(O(L)\) bits, so exact output has polynomial encoding length.
The case \(Q=0\) is correctly handled by the zero matrix. Types with \(q_t=0\), zero residual margins, and a zero-supply future row are all permitted by the construction and lemma.
The argument directly addresses the continuous, mass-valued phases and does not rely on the supplied indivisible-agent result. 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.