Answer: Polynomial-time solvable.
Lemma 2 — class: algorithmic
Given a finite resource set \(Q\) and a support \(\mathcal T\) of \(\tau\) types, where type \(t\) has mass \(\mu_t\in\mathbb Q_{>0}\), peak \(p_t\), and eligible sources \(N_t\subseteq Q\), and each source \(r\) has rational supply \(\omega_r\) per unit of normalized population, compute the unique weighted analogue of Lemma 2’s partition \((\mathcal T_+,\mathcal T_0,\mathcal T_-;Q_+,Q_0,Q_-)\) in time polynomial in the input size and rational bit length \(L\). Define \(P(S)=\sum_{t\in S}\mu_t p_t\), \(\Omega(R)=\sum_{r\in R}\omega_r\), \(f(S)=\bigcup_{t\in S}N_t\), and \(g(R)=\{t:N_t\cap R\ne\varnothing\}\). The partition must satisfy \(E(\mathcal T_-,Q_0\cup Q_-)=E(\mathcal T_0,Q_-)=\varnothing\), \(P(S)<\Omega(f(S)\cap Q_-)\) for each nonempty \(S\subseteq\mathcal T_+\), and \(\Omega(R)<P(g(R)\cap\mathcal T_-)\) for each nonempty \(R\subseteq Q_+\); the balanced component must admit flows \(y_{tr}\ge0\) on eligible edges in \(\mathcal T_0\times Q_0\) with \(\sum_r y_{tr}=\mu_t p_t\) and \(\sum_t y_{tr}=\omega_r\).
A society is given by its support: a list \(\mathcal T\) of \(\tau\) types with positive binary rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types. Each type has a finite peak \(p_t\in\mathbb Q_{\ge0}\) per individual and eligible sources \(N_t\subseteq Q\); the nonempty resource set has size \(m=|Q|\) and supplies \(\omega_r\in\mathbb Q_{>0}\) per unit population. Let \(L\) be the total binary input length.
The explicitly given bipartite eligibility graph \(E=\{(t,r):r\in N_t\}\) is connected. Transfers are divisible, nonnegative, and have no edge capacities; all supply must be allocated. Write \(E(S,R)=E\cap(S\times R)\), \(P(S)=\sum_{t\in S}\mu_tp_t\), \(\Omega(R)=\sum_{r\in R}\omega_r\), \(f(S)=\bigcup_{t\in S}N_t\), and \(g(R)=\{t:N_t\cap R\ne\varnothing\}\).
Compute the canonical partitions \((\mathcal T_+,\mathcal T_0,\mathcal T_-;Q_+,Q_0,Q_-)\), allowing empty parts, satisfying:
\(E(\mathcal T_-,Q_0\cup Q_-)=E(\mathcal T_0,Q_-)=\varnothing\), and \(p_t>0\) for every \(t\in\mathcal T_-\).
\(P(S)<\Omega(f(S)\cap Q_-)\) for every nonempty \(S\subseteq\mathcal T_+\), and \(\Omega(R)<P(g(R)\cap\mathcal T_-)\) for every nonempty \(R\subseteq Q_+\).
The balanced component admits transfers \(y_{tr}\ge0\), zero off eligible edges in \(\mathcal T_0\times Q_0\), with \(\sum_{r\in Q_0}y_{tr}=\mu_tp_t\) and \(\sum_{t\in\mathcal T_0}y_{tr}=\omega_r\). The positive-peak convention for \(\mathcal T_-\) resolves the otherwise ambiguous placement of zero-peak types.
Is computing this canonical partition solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For the finite-agent analogue, existence of a canonical partition and computation in polynomial time in the number of graph vertices are asserted in [Bochet, İlkılıç, and Moulin (2013)](https://yoksis.bilkent.edu.tr/pdf/files/10.1016-j.jet.2012.09.016.pdf). That assertion already allows real-valued peaks and supplies, but does not explicitly state a binary bit-complexity bound; no separate result for the normalized distribution formulation was verified.
The canonical partition is computable in polynomial time in \(m,\tau,L\). One maximum-flow computation, followed by two residual-graph searches, suffices.
The finite-agent decomposition appears in Lemma 2 of [Bochet, İlkılıç, and Moulin (2013)](https://yoksis.bilkent.edu.tr/pdf/files/10.1016-j.jet.2012.09.016.pdf). Below is a direct proof for the support representation, including uniqueness, zero-peak types, and binary bit complexity.
For each type, define its aggregate peak demand by \(d_t=\mu_t p_t\). Since \(\mu_t>0\), we have \(d_t>0\) exactly when \(p_t>0\). Moreover, \(P(S)=\sum_{t\in S}d_t\).
Construct a directed network with source \(s\), sink \(z\), resource vertices \(Q\), and type vertices \(\mathcal T\). Its arcs and capacities are:
| Arc | Capacity |
|---|---|
| \(s\to r\), for \(r\in Q\) | \(\omega_r\) |
| \(r\to t\), for \((t,r)\in E\) | \(M\) |
| \(t\to z\), for \(t\in\mathcal T\) | \(d_t\) |
Choose \(M=1+\Omega(Q)+P(\mathcal T)\).
Compute any maximum flow. Write \(x_{rt}\) for its flow on \(r\to t\), and put \(u_r=\sum_t x_{rt}\) and \(v_t=\sum_r x_{rt}\). Thus \(u_r\leq\omega_r\) and \(v_t\leq d_t\).
The flow value is at most \(\Omega(Q)<M\). Consequently, every eligibility arc \(r\to t\) has strictly positive forward residual capacity. Its reverse arc \(t\to r\) has positive residual capacity exactly when \(x_{rt}>0\).
In the residual graph, let:
Maximality of the flow implies \(A\cap B=\varnothing\). Define
\( \mathcal T_+=A\cap\mathcal T,\qquad Q_-=A\cap Q, \)
\( \mathcal T_-=B\cap\mathcal T,\qquad Q_+=B\cap Q, \)
and let \(\mathcal T_0\) and \(Q_0\) contain the remaining type and resource vertices.
We prove that these are exactly the required canonical partitions.
If \(r\in Q_-\), every eligible neighbor \(t\) is reachable from \(s\), because \(r\to t\) has positive residual capacity. Hence \(g(Q_-)\subseteq\mathcal T_+\).
If \(t\in\mathcal T_-\), every eligible resource \(r\) can reach \(z\) through \(r\to t\). Hence \(f(\mathcal T_-)\subseteq Q_+\).
These inclusions give all required edge restrictions:
\(E(\mathcal T_-,Q_0\cup Q_-)=E(\mathcal T_0,Q_-)=\varnothing.\)
Two further consequences of reverse residual arcs will be useful:
Together with the eligibility restrictions, these imply that every positive \(x_{rt}\) belongs to one of the three blocks \(\mathcal T_+\times Q_-\), \(\mathcal T_0\times Q_0\), or \(\mathcal T_-\times Q_+\).
Every \(t\in\mathcal T_+\) satisfies \(v_t=d_t\). Otherwise \(t\to z\) would have positive residual capacity, yielding an augmenting path from \(s\) to \(z\).
Every \(r\in Q_+\) satisfies \(u_r=\omega_r\). Otherwise \(s\to r\), followed by a residual path from \(r\) to \(z\), would be an augmenting path.
Also, every \(t\in\mathcal T_0\) satisfies \(v_t=d_t\): an unsaturated \(t\to z\) would place \(t\) in \(B\). Similarly, every \(r\in Q_0\) satisfies \(u_r=\omega_r\): an unsaturated \(s\to r\) would place \(r\) in \(A\).
Finally, suppose \(d_t=0\). Then \(v_t=0\), so all \(x_{rt}=0\). The type vertex \(t\) has no outgoing residual arc: neither \(t\to z\) nor any reverse arc \(t\to r\) has positive residual capacity. Therefore \(t\notin B\). Thus \(p_t>0\) for every \(t\in\mathcal T_-\), as required.
Restrict the flow to the middle block and define \(y_{tr}=x_{rt}\) there, with zero transfers elsewhere.
The block property and saturation established above give
\(\sum_{r\in Q_0}y_{tr}=d_t=\mu_t p_t\) for every \(t\in\mathcal T_0\),
and
\(\sum_{t\in\mathcal T_0}y_{tr}=\omega_r\) for every \(r\in Q_0\).
Thus the balanced component has the required transfers.
Take a nonempty \(S\subseteq\mathcal T_+\), and set \(H=f(S)\cap Q_-\).
All demand of \(S\) is met by resources in \(H\). Flow conservation therefore gives
\(\Omega(H)-P(S)=\sum_{r\in H}(\omega_r-u_r)+\sum_{r\in H,\ t\notin S}x_{rt}\geq 0.\)
Suppose equality held. Every term on the right would vanish. Thus all resources in \(H\) would be saturated, and no positive flow from \(H\) would go to a type outside \(S\).
Consider the residual graph restricted to \(A\), and let \(U=H\cup S\). There is no residual arc entering \(U\) from \(A\setminus U\):
These exhaust the possible incoming residual arcs. Since \(s\notin U\), no vertex of \(U\) could be reachable from \(s\). This contradicts the nonempty inclusion \(S\subseteq A\).
Consequently, \(P(S)<\Omega(f(S)\cap Q_-)\).
Take a nonempty \(R\subseteq Q_+\), and set \(H=g(R)\cap\mathcal T_-\).
All resources in \(R\) are saturated and send their flow only to \(H\). Hence
\(P(H)-\Omega(R)=\sum_{t\in H}(d_t-v_t)+\sum_{t\in H,\ r\notin R}x_{rt}\geq 0.\)
Suppose equality held. Then all types in \(H\) would be saturated, and no positive flow into \(H\) would come from outside \(R\).
In the residual graph restricted to \(B\), let \(U=R\cup H\). There is no residual arc leaving \(U\) for \(B\setminus U\):
Since \(z\notin U\), no resource in \(R\) could reach \(z\). This contradicts \(R\subseteq B\).
Therefore, \(\Omega(R)<P(g(R)\cap\mathcal T_-)\).
This proves existence of a partition satisfying every condition in the question.
We first establish that residual reachability does not depend on the chosen maximum flow, and then show that every partition satisfying the stated conditions has the same reachability sets.
For any source–sink cut with source side \(X\), flow conservation gives
\(\operatorname{cap}(X)-F=\sum_{a\text{ leaving }X}(c_a-f_a)+\sum_{a\text{ entering }X}f_a,\)
where \(F\) is the maximum-flow value.
All terms are nonnegative. By the max-flow/min-cut theorem, \(X\) is the source side of a minimum cut exactly when there is no positive-capacity residual arc leaving \(X\).
It follows that:
For the second statement, a vertex outside \(B\) cannot have a residual arc to a vertex in \(B\); and a minimum-cut source side cannot contain a vertex with a residual path to \(z\).
Thus \(A\) is the intersection of all minimum-cut source sides, while the complement of \(B\) is their union. Both are determined by the network, independently of the maximum flow.
For a bipartite graph with resource capacities \(a_r\) and type capacities \(b_t\), nonnegative eligible transfers can:
Here “saturate” means equality at the specified vertices and no capacity violation at the other vertices.
Necessity follows by summing transfers. For sufficiency, use the network from Section 1 with middle-arc capacity exceeding both total capacities. A cut crossing a middle arc already exceeds either target flow value. Any other cut, containing resource subset \(R_X\) and type subset \(T_X\) on its source side, satisfies \(g(R_X)\subseteq T_X\) and has capacity
\(\sum_{r\notin R_X}a_r+\sum_{t\in T_X}b_t.\)
The first Hall condition, applied to the types outside \(T_X\), makes this at least \(\sum_t b_t\). The second, applied to \(R_X\), makes it at least \(\sum_r a_r\). The max-flow/min-cut theorem proves both assertions.
Consider any other partition satisfying the question’s conditions. Denote it by hats.
The Hall lemma supplies a flow in \(\widehat{\mathcal T}_+\times\widehat Q_-\) saturating all type demands, because strict underdemand implies the corresponding non-strict Hall inequalities.
It also supplies a flow in \(\widehat{\mathcal T}_-\times\widehat Q_+\) saturating all resource supplies, because strict overdemand implies the other Hall inequalities. Use the stipulated balanced transfers in \(\widehat{\mathcal T}_0\times\widehat Q_0\).
Combining these three flows, with zero flow between blocks, gives a feasible flow in the auxiliary network.
Any residual path starting at \(s\) remains within \(\{s\}\cup\widehat Q_-\cup\widehat{\mathcal T}_+\): only resources in \(\widehat Q_-\) can have unsaturated source arcs; their eligible neighbors lie in \(\widehat{\mathcal T}_+\); these types have saturated sink arcs; and positive reverse arcs remain in the same block. Hence there is no augmenting path, so this flow is maximum.
Likewise, vertices that can reach \(z\) lie within \(\{z\}\cup\widehat{\mathcal T}_-\cup\widehat Q_+\).
We now prove that these containments are equalities.
Let \(S\) be the types in \(\widehat{\mathcal T}_+\) not reachable from \(s\), and let \(W\) be the resources in \(\widehat Q_-\) not reachable from \(s\).
Every resource in \(W\) is saturated. It sends no positive flow to a reachable type, because the resulting reverse arc would make that resource reachable. Therefore \(\Omega(W)\leq P(S)\). Moreover, \(f(S)\cap\widehat Q_-\subseteq W\), since every forward eligibility arc is residual.
If \(S\ne\varnothing\), strict underdemand gives the contradiction
\(P(S)<\Omega(f(S)\cap\widehat Q_-)\leq\Omega(W)\leq P(S).\)
Thus \(S=\varnothing\), and then \(\Omega(W)\leq 0\) forces \(W=\varnothing\), because supplies are positive.
For the other component, let \(U\) be the types in \(\widehat{\mathcal T}_-\) that cannot reach \(z\), and let \(R\) be the resources in \(\widehat Q_+\) that cannot reach \(z\).
Every type in \(U\) is saturated. It receives no positive flow from a resource that can reach \(z\), since the reverse arc would let that type reach \(z\). Consequently, \(P(U)\leq\Omega(R)\). Also, \(g(R)\cap\widehat{\mathcal T}_-\subseteq U\).
If \(R\ne\varnothing\), strict overdemand yields
\(\Omega(R)<P(g(R)\cap\widehat{\mathcal T}_-)\leq P(U)\leq\Omega(R),\)
a contradiction. Thus \(R=\varnothing\), and \(P(U)\leq 0\) forces \(U=\varnothing\), because every type in \(\widehat{\mathcal T}_-\) has positive peak and positive mass.
The residual sets of this maximum flow therefore identify precisely the hatted components. Their invariance proves that the hatted partition equals the partition computed in Section 1. Uniqueness follows.
The network has \(n=m+\tau+2\) vertices and \(a=m+\tau+|E|\) arcs. Because the eligibility graph is explicitly given, these quantities are polynomially bounded by the stated input parameters.
Write the input rationals with integer numerators and positive integer denominators. Let \(D\) be the product of the denominators of all masses, peaks, and supplies.
The binary length of \(D\) is \(O(L)\). Also, \(D\omega_r\) and \(D\mu_t p_t\) are integers: the denominator product defining \(D\) includes both denominators in each \(\mu_t p_t\).
Multiplying every network capacity by \(D\) therefore gives an integer-capacity network with middle capacity
\(DM=D+\sum_r D\omega_r+\sum_t D\mu_t p_t.\)
All capacities have \(O(L+\log(m+\tau))\) bits. Computing them takes polynomial time.
The Edmonds–Karp algorithm computes a maximum flow in a directed network with nonnegative integer capacities using \(O(na^2)\) arithmetic operations, independently of the numerical magnitudes of the capacities. Its hypotheses hold here. Flow values and residual capacities have polynomially many bits, so its arithmetic operations take polynomial bit time. The two residual-graph searches take \(O(n+a)\) time.
Finally, positive scaling preserves maximum flows after rescaling and preserves which residual capacities are positive. Thus the integer network produces exactly the desired rational-input partition.
No population expansion is needed: each supported type contributes one vertex. This establishes polynomial-time computation in \(m,\tau,L\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The argument establishes existence and uniqueness of the specified partition and gives a polynomial-time algorithm under the stated binary rational encoding. I found no major or minor mathematical issues.
The substitution \(d_t=\mu_t p_t\) exactly represents the aggregate peak demand in the task. Positivity of \(\mu_t\) justifies the equivalence \(d_t>0\) if and only if \(p_t>0\).
All network capacities are finite and nonnegative. The choice \(M=1+\Omega(Q)+P(\mathcal T)\) is sufficient: every eligibility-arc flow is at most the total flow value, which is at most \(\Omega(Q)<M\). Thus every forward eligibility arc has strictly positive residual capacity, regardless of the chosen maximum flow.
The residual sets \(A\) and \(B\) are disjoint: a vertex in their intersection would produce a residual source-to-sink path, contradicting maximum-flow optimality. Consequently, the proposed definitions give genuine partitions.
Finding: Correct.
Both eligibility inclusions follow directly from positive forward residual capacities:
They imply exactly the prohibited-edge conditions in the task.
The two implications involving positive reverse residual arcs are also correct. Combined with the eligibility restrictions, they exclude positive flow between different proposed blocks.
Each saturation claim uses the appropriate residual implication:
The zero-peak argument is valid. If \(d_t=0\), nonnegativity and conservation force every incoming eligibility-arc flow to vanish. Neither the sink arc nor any reverse eligibility arc then provides an outgoing residual arc from \(t\). Therefore such a type cannot belong to \(B\).
Restricting the flow to the middle block gives the required balanced transfers because middle vertices are saturated and no positive flow crosses between blocks.
Finding: Correct, including the positive-peak convention.
For every nonempty \(S\subseteq\mathcal T_+\), the displayed identity correctly accounts for the supply of \(H=f(S)\cap Q_-\):
\(\Omega(H)-P(S)\) equals unused supply in \(H\), plus flow from \(H\) to types outside \(S\).
All these terms are nonnegative. Equality therefore forces every resource in \(H\) to be saturated and every indicated outgoing flow to vanish.
The subsequent residual-graph argument is complete. Within \(A\), the listed arc categories exhaust possible arcs entering \(H\cup S\). In particular, \(z\notin A\), so reverse sink arcs introduce no omitted incoming case. A path witnessing reachability of a vertex in \(A\) remains entirely within \(A\).
Thus equality contradicts reachability of the nonempty set \(S\). The reasoning also covers \(H=\varnothing\).
Finding: The required strict inequality holds for every quantified nonempty subset.
The second displayed identity is likewise correct:
\(P(H)-\Omega(R)\), for \(H=g(R)\cap\mathcal T_-\), equals unused type capacity in \(H\), plus flow into \(H\) from resources outside \(R\).
Equality gives exactly the saturation and zero-flow conclusions used afterward.
The listed outgoing residual-arc cases exhaust those possible within \(B\). Here \(s\notin B\), so reverse source arcs do not create an omitted case. Every vertex on a residual path to \(z\) belongs to \(B\).
Consequently, the asserted absence of outgoing residual arcs prevents the nonempty set \(R\) from reaching \(z\), a contradiction.
Finding: The required strict inequality holds for every quantified nonempty subset.
The cut identity has the correct signs and accounts for both forward and reverse residual arcs across the cut.
Its application of the max-flow/min-cut theorem is justified: for a maximum flow, a source–sink cut has minimum capacity exactly when every residual capacity leaving its source side is zero.
The argument correctly identifies:
Both sets therefore depend only on the network.
Finding: Correct; the output partition is independent of algorithmic choices.
The lemma states both saturation criteria precisely, including the capacity restrictions on the opposite side. Necessity follows from summing feasible transfers.
For sufficiency, the cut calculation is correct. A cut crossing a middle arc exceeds either target flow value. Otherwise, its source-side resource and type subsets satisfy \(g(R_X)\subseteq T_X\), and its capacity is the stated sum.
The first Hall condition applies to types outside \(T_X\), whose eligible resources necessarily lie outside \(R_X\). The second applies directly to \(R_X\). These applications justify the respective lower bounds on every cut.
All applications later in the proof use nonnegative capacities and finite bipartite graphs. Empty subsets impose only the valid inequality \(0\leq0\).
Finding: Correct and sufficiently justified.
For an arbitrary admissible hatted partition, the Hall lemma supplies the two outer-block flows, while the task supplies the balanced flow. Their combination is feasible.
The residual containment arguments correctly use the prohibited edges, blockwise positive flow, and saturation. They establish maximum-flow optimality before invoking residual-set invariance.
Both subsequent contradiction chains are valid:
The strict subset inequalities force the exceptional type or resource sets to be empty. Strictly positive supplies eliminate the remaining underdemanded resource set. Strictly positive masses and the positive-peak convention eliminate the remaining overdemanded type set.
These arguments cover empty partition parts without assuming their nonemptiness.
Finding: Uniqueness is established.
The network size bounds are correct for an explicitly listed eligibility graph.
The denominator product \(D\) has binary length \(O(L)\). Including the denominator of each input occurrence ensures that both \(D\omega_r\) and \(D\mu_t p_t\) are integers, including when a mass and peak have common denominator factors.
The scaled middle capacity is computed correctly. Products and sums retain polynomial binary length, and their construction takes polynomial time.
The stated Edmonds–Karp bound applies to this finite directed integer-capacity network and is independent of capacity magnitudes. Flows and residual capacities have polynomial binary length, so the arithmetic-operation bound yields polynomial bit complexity. Residual searches add only polynomial work.
Positive scaling preserves flow optimality and residual positivity, so integer scaling does not change the computed partition.
Finding: Polynomial time in \(m,\tau,L\) is established.
The auxiliary maximum flow need not allocate all supplies: its purpose is to identify the partition. The requested balanced transfers are nevertheless fully supplied, and every partition condition is proved.
The contextual attribution to Lemma 2 is accurate: it states the finite-agent decomposition in the cited [Bochet, İlkılıç, and Moulin paper](https://yoksis.bilkent.edu.tr/pdf/files/10.1016-j.jet.2012.09.016.pdf). The submitted proof independently establishes the support formulation and binary complexity bound.
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.