Answer: Polynomial-time solvable. The core is always nonempty, and maximum total payment is \(dD_{R_c}(s,t)\). An exact polynomial-size extended linear description exists, but payment-only linear descriptions can require exponentially many inequalities.
Theorem 3.1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateThe two constraint collections (C1) and (C2) de- scribe the same core. This theorem means that (C2) is equivalent to (C1). Next, we will prove theorem 3.1 from two aspects, necessity and sufficiency. Necessity is to prove (C1) ⇒(C2) and sufficiency is to prove (C2) ⇒(C1).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a directed network \(G=(V,E)\), source and sink, rational demand \(d\), and a distribution \(\mu\) over supplier types \(r=(e,c_r)\), each with unit capacity, let \(x^\star\) be an efficient flow with \(0\le x_r^\star\le\mu_r\). What exact core constraints characterize payments to the winning supplier mass, and does a polynomial-size analogue of the paper’s vertex-pair collection suffice to compute maximum total core payments or report that the core is empty?
Let \(G=(V,E)\) be directed, \(s\ne t\), \(m=|V|+|E|\), and let demand \(d>0\) be a binary rational. A society is given by its support: the list of \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. Types are \(r=(e_r,c_r)\), with \(e_r\in E\), positive binary-rational costs \(c_r\), and \(\sum_r\mu_r=1\).
Type \(r\) consists of an atomless mass \(\mu_r\) of suppliers, each owning one unit of capacity on \(e_r\). For available masses \(z\), let \(C(z)\) be the minimum cost of a demand-\(d\) flow using type capacities \(z_r\) and unit costs \(c_r\); set \(C(z)=+\infty\) when infeasible.
A rational efficient flow \(x^\star\), with \(0\le x_r^\star\le\mu_r\), is supplied and fixed, including any choice among tied optima. Its selected supplier mass of type \(r\) is \(x_r^\star\). Assume \(C(\mu-x^\star)<+\infty\), so the unselected suppliers can meet demand.
Each selected supplier of type \(r\) receives the same per-unit payment \(q_r\ge c_r\); unselected suppliers receive zero. Total payment is \(P=\sum_r x_r^\star q_r\), selected suppliers have utility density \(q_r-c_r\), and the auctioneer has utility \(-P\).
Coalitions may contain arbitrary measurable portions of selected and unselected suppliers. A coalition without the auctioneer has worth zero; one containing the auctioneer and supplier masses \(z\) has worth \(-C(z)\). Use the transferable-utility core for these measurable coalitions. Let \(L\) be the total binary input length, including \(x^\star\) and any payment threshold.
What exact constraints characterize this payment core, and does an analogue of the vertex-pair detour collection give a polynomial-size exact description?
Is computing maximum total core payment, or reporting an empty core, polynomial-time in \(m,\tau,L\), or is deciding whether a core payment with \(P\ge B\) exists NP-hard for binary-rational \(B\)?
For discrete single-edge suppliers and a winning shortest path \(H\) of \(k\) edges, individual rationality and at most \(k(k+1)/2\) detour constraints describe the core: \(\sum_{e\in H[a,b]}p_e\le D_{G\setminus H[a,b]}(a,b)\), where \(H[a,b]\) is the winning subpath and \(D\) denotes shortest-path cost; omit infinite bounds. This yields polynomial-time maximum-payment computation. [Discrete equivalence](https://ha0cheng.github.io/paper/aamas2018.pdf), [later algorithms](https://ha0cheng.github.io/paper/Cheng2020_Article_FastCorePricingAlgorithmsForPa.pdf).
Continuous-goods reverse auctions have core formulations and constraint-generation methods for finitely many bidders, rather than atomless supplier coalitions; this result does not settle the problem above. [Continuous-goods auctions](https://arxiv.org/pdf/1711.06774).
The maximum-payment problem is polynomial-time solvable. The core is always nonempty under the stated assumptions.
There is an exact linear description using \(O(|V|+\tau)\) variables and constraints, with vertex potentials as auxiliary variables. However, a polynomial-size collection of linear inequalities in the payment variables alone does not exist in general: the core can have exponentially many facets. This distinguishes the general flow setting from the [discrete winning-path detour description](https://ha0cheng.github.io/paper/aamas2018.pdf).
The maximum payment also has a shortest-path formula, proved below.
Write \(x=x^\star\), \(a=\mu-x\), \(u_r=q_r-c_r\), and \(C^\star=C(\mu)=\sum_r c_rx_r\). Thus \(P=C^\star+\sum_r x_ru_r\).
A coalition containing the auctioneer can include selected masses \(\alpha_r\in[0,x_r]\) and unselected masses \(\beta_r\in[0,a_r]\). Atomlessness permits every such choice. Its allocated utility is
\( -P+\sum_r\alpha_ru_r=-C^\star-\sum_r(x_r-\alpha_r)u_r. \)
Consequently, its core constraint is
\( C^\star+\sum_r(x_r-\alpha_r)u_r\le C(\alpha+\beta). \)
Put \(y=x-\alpha\). For fixed \(y\), the smallest right-hand side occurs when the coalition includes all unselected suppliers, because increasing available capacity cannot increase minimum cost. Its available capacity is then \(\mu-y\).
Therefore the exact coalition constraints are
\[ q_r\ge c_r\quad\text{for every }r,\qquad \sum_r y_r(q_r-c_r)\le C(\mu-y)-C^\star\quad\text{for every }0\le y\le x. \tag{1} \]
Constraints with infinite right-hand side are vacuous.
These conditions are also sufficient. Every auctioneer-containing coalition has available capacity at most \(\mu-y\), so its procurement cost is at least \(C(\mu-y)\). Coalitions without the auctioneer receive nonnegative utility, since \(u_r\ge0\). Finally, grand-coalition efficiency holds because
\( -P+\sum_r x_r(q_r-c_r)=-C^\star. \)
In particular, \(q_r=c_r\) always belongs to the core: every restricted-capacity cost is at least \(C^\star\). Thus an empty core cannot occur on an instance satisfying the premises.
Represent each type by a separate arc with the endpoints of \(e_r\). Let \(A\) be the incidence matrix using inflow minus outflow, and let \(b_s=-d\), \(b_t=d\), and \(b_v=0\) otherwise.
For a proposed \(q\ge c\), construct a network with two arcs per type:
Let its minimum demand-\(d\) flow cost be \(K(q)\). The flow using exactly all selected capacities and no unselected capacities is feasible and costs \(P\). Hence \(K(q)\le P\).
We now prove that
\[ q\text{ belongs to the core}\quad\Longleftrightarrow\quad K(q)=P. \tag{2} \]
For a fixed aggregate type flow \(f\), where \(Af=b\) and \(0\le f\le\mu\), its cheapest split between the two capacities uses selected capacity \((f_r-a_r)_+\). This follows from \(q_r\ge c_r\). Therefore
\[ K(q)=\min_{\substack{Af=b\\0\le f\le\mu}}\left[\sum_r c_rf_r+\sum_r u_r(f_r-a_r)_+\right]. \tag{3} \]
On the other hand, the minimum slack expression appearing in (1) is
\( \min_{0\le y\le x}\left[C(\mu-y)-\sum_r u_ry_r\right] =\min_{\substack{Af=b,\;f\ge0\\0\le y\le x,\;f+y\le\mu}}\left[\sum_r c_rf_r-\sum_r u_ry_r\right]. \)
The joint feasible set is nonempty and compact. For a fixed \(f\), nonnegativity of \(u\) permits choosing \(y_r=\min\{x_r,\mu_r-f_r\}\). The identity
\( \min\{x_r,\mu_r-f_r\}=x_r-(f_r-a_r)_+ \)
then gives, using (3),
\( \min_{0\le y\le x}\left[C(\mu-y)-\sum_r u_ry_r\right]=K(q)-\sum_r u_rx_r. \)
Thus (1) is equivalent to \(K(q)\ge C^\star+\sum_r u_rx_r=P\). Together with \(K(q)\le P\), this proves (2).
At the selected-only flow in the preceding network, the residual multigraph \(R(q)\) contains:
Its residual capacities are respectively \(a_r\) and \(x_r\).
The selected-only flow is optimal exactly when \(R(q)\) has no negative-cost directed cycle. Here is the justification in this particular network.
A negative residual cycle can be augmented by a positive amount no larger than its smallest residual capacity, producing a cheaper flow with the same demand. Conversely, the difference between any alternative feasible flow and the selected-only flow is a nonnegative residual circulation: it uses unselected arcs forward and selected arcs backward. Decomposing this circulation into directed cycles shows that a cheaper alternative requires a negative-cost cycle.
Combining this fact with (2) gives an exact family of linear inequalities in \(q\):
\[ \sum_{\substack{\text{selected reverse arcs}\\r\text{ on }\Gamma}}q_r \le \sum_{\substack{\text{unselected forward arcs}\\r\text{ on }\Gamma}}c_r \quad\text{for every directed simple cycle }\Gamma. \tag{4} \]
Together with \(q\ge c\), these inequalities characterize the core.
There is also a compact extended description. A finite weighted digraph has no negative cycle if and only if it admits vertex potentials \(\pi\) satisfying \(\pi_v-\pi_u\le w_{uv}\) on every arc \(u\to v\). To verify this equivalence, summing the inequalities around a cycle proves necessity of nonnegative cycle costs; for sufficiency, attach a new source with zero-cost arcs to all vertices and take shortest-path distances as potentials.
Applying this equivalence to \(R(q)\), the core consists exactly of the payment vectors admitting potentials with
\[ q_r\ge c_r\quad\text{for every }r, \tag{5a} \]
\[ q_r\le\pi_w-\pi_v\quad\text{if }e_r=(v,w)\text{ and }x_r>0, \tag{5b} \]
\[ \pi_w-\pi_v\le c_r\quad\text{if }e_r=(v,w)\text{ and }a_r>0. \tag{5c} \]
One may normalize \(\pi_s=0\). There are \(\tau+|V|\) variables and at most \(3\tau+1\) constraints.
For example, a partially selected type, with \(0<x_r<\mu_r\), must satisfy \(q_r=c_r\), because both (5b) and (5c) apply.
Define the fixed residual multigraph \(R_c=R(c)\): unselected arcs have cost \(c_r\), and selected reverse arcs have cost \(-c_r\). Let
\( D=D_{R_c}(s,t). \)
This distance is finite:
We claim that
\[ \boxed{P_{\max}=dD_{R_c}(s,t).} \tag{6} \]
Upper bound. Let \(q\) be a core payment and choose potentials satisfying (5). Since \(q_r\ge c_r\), those potentials satisfy the difference constraints on every arc of \(R_c\). Summing along a shortest \(s\)-to-\(t\) path gives \(\pi_t-\pi_s\le D\).
Using (5b) and flow conservation,
\[ P=\sum_r x_rq_r \le\sum_{r:e_r=(v,w)}x_r(\pi_w-\pi_v) =\pi^{\mathsf T}Ax =d(\pi_t-\pi_s) \le dD. \tag{7} \]
Attainment. Add to \(R_c\) an arc \(t\to s\) of cost \(-D\). The augmented graph has no negative cycle. Every simple cycle avoiding this arc is already nonnegative; a simple cycle using it consists of an original \(s\)-to-\(t\) path followed by the new arc, and has cost at least \(D-D=0\).
Hence the augmented graph admits feasible potentials. The original shortest-path constraints give \(\pi_t-\pi_s\le D\), while the added arc gives \(\pi_t-\pi_s\ge D\). Thus equality holds.
Set
\( q_r=\pi_w-\pi_v\quad\text{when }e_r=(v,w)\text{ and }x_r>0, \)
and set \(q_r=c_r\) when \(x_r=0\). The original selected reverse arcs ensure \(q_r\ge c_r\), and the unselected forward arcs ensure (5c). These payments therefore belong to the core, and their total is
\( P=\sum_{r:e_r=(v,w)}x_r(\pi_w-\pi_v)=d(\pi_t-\pi_s)=dD. \)
This proves (6), including attainment.
Although (5) is a polynomial-size extended description, exponentially many inequalities can be necessary when auxiliary variables are forbidden.
Fix an integer \(n\ge1\). Construct \(n\) diamonds in series, with junctions \(v_0=s,v_1,\ldots,v_n=t\). Diamond \(i\) has two intermediate vertices \(w_i^0,w_i^1\), and arcs
\( v_{i-1}\to w_i^b\to v_i,\qquad b\in\{0,1\}. \)
Add a direct arc \(s\to t\). Give every arc one type. Put
\( \varepsilon=\frac{1}{4n+2},\qquad d=2\varepsilon. \)
Each of the \(4n\) diamond types has mass \(\varepsilon\) and cost \(1\). The direct type has mass \(2\varepsilon\) and cost \(4n\). The masses sum to \(1\).
Choose \(x\) to use capacity \(\varepsilon\) on every diamond arc and zero on the direct arc. This is a feasible demand-\(d\) flow.
It is efficient. If a feasible flow sends amount \(g\) directly, its remaining amount \(d-g\) crosses all \(n\) diamonds, giving total cost
\( 2n(d-g)+4ng=2nd+2ng\ge2nd. \)
The chosen flow achieves \(2nd\). The unselected direct capacity alone also meets demand, so all required assumptions hold.
The residual graph contains the diamonds reversed, together with the forward direct arc. Every directed simple cycle consists of that direct arc followed by a reversed diamond path. There are \(2^n\) such paths. Consequently, after ignoring the irrelevant direct-type payment, the core is precisely
\[ q_e\ge1,\qquad \sum_{e\in H_\sigma}q_e\le4n \quad\text{for every }\sigma\in\{0,1\}^n, \tag{8} \]
where \(H_\sigma\) chooses one branch in each diamond.
Every path inequality in (8) defines a distinct facet. First, the polyhedron is full-dimensional: setting every payment to \(3/2\) makes all inequalities strict. For a fixed path \(H_\sigma\), set its arc payments to \(2\), and every other diamond-arc payment to \(3/2\). Then its path sum is \(4n\). Any other path differs in at least one diamond and has strictly smaller sum. Every lower bound is also strict.
Thus a neighborhood of this point within the hyperplane \(\sum_{e\in H_\sigma}q_e=4n\) remains feasible. Its face has dimension \(4n-1\), proving that it is a facet.
A full-dimensional polyhedron requires at least one defining halfspace for each distinct facet: at a relative interior point of a facet, some defining inequality must be active, and its boundary must coincide with that facet’s supporting hyperplane. Hence every exact linear description in these payment variables requires at least \(2^n\) inequalities.
Here \(|V|=3n+1\), \(|E|=4n+1\), \(\tau=4n+1\), and the binary input length is \(O(n\log n)\). Therefore the required number of inequalities is not polynomial in \(m,\tau,L\). Including the direct-type payment cannot avoid this bound, because fixing it to its cost recovers the same polyhedron.
So the analogue of a polynomial detour collection fails as a collection of linear inequalities in payments alone, while the potential formulation (5) remains compact and exact.
The formula supplies a direct algorithm:
The residual graph has at most \(2\tau\) arcs. Bellman–Ford uses polynomially many rational arithmetic operations. With no negative cycles, shortest paths can be chosen simple, so their costs, the resulting potentials, and the payments have polynomial binary encoding length. All positivity tests, arithmetic, and comparisons are therefore polynomial-time in \(m,\tau,L\).
In particular, a core payment satisfying \(P\ge B\) exists exactly when
\( dD_{R_c}(s,t)\ge B, \)
which can be decided by an exact rational comparison.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task. The measurable-coalition characterization, compact extended formulation, maximum-payment formula, and exponential lower bound for descriptions using only payment variables are correct. I found no major or minor issues.
The coalition parametrization is valid. Atomlessness allows independent choices of selected mass \(\alpha_r\in[0,x_r]\) and unselected mass \(\beta_r\in[0,\mu_r-x_r]\) for every type.
The allocated utility of an auctioneer-containing coalition is correctly computed as
\[
-P+\sum_r\alpha_r(q_r-c_r)
=-C^\star-\sum_r(x_r-\alpha_r)(q_r-c_r).
\]
Comparing this with the coalition’s worth gives the stated inequality with the correct direction.
For a fixed excluded selected mass \(y=x-\alpha\), including every unselected supplier minimizes procurement cost. Thus checking capacities \(\mu-y\) is both necessary and sufficient for checking all auctioneer-containing coalitions.
The remaining core requirements are also verified:
Consequently, (1) exactly characterizes the payment core, and the nonemptiness assertion follows.
The two-arc construction correctly represents the selected and unselected capacities. The selected-only flow is feasible and has cost \(P\), so \(K(q)\le P\).
For a fixed aggregate type flow \(f\), the cheapest split uses unselected capacity first because \(q_r\ge c_r\). The selected amount is therefore \((f_r-a_r)_+\), establishing (3), including the case \(q_r=c_r\).
The joint minimization over \(f\) and \(y\) correctly expresses the minimum coalition slack. Its feasible set is compact and nonempty. For each feasible \(f\), maximizing \(y_r\) minimizes the objective because \(u_r\ge0\). The identity
\[
\min\{x_r,\mu_r-f_r\}=x_r-(f_r-a_r)_+
\]
holds throughout \(0\le f_r\le\mu_r\).
Substitution gives exactly \(K(q)-\sum_r u_rx_r\). Hence the coalition constraints are equivalent to \(K(q)\ge P\); combined with \(K(q)\le P\), this proves (2).
The residual graph is correctly specified at the selected-only flow:
There are no additional residual arcs at this flow.
The optimality argument is sound in both directions. A negative cycle permits a strictly positive augmentation, since every retained residual arc has positive capacity. Conversely, an alternative feasible flow determines a nonnegative residual circulation. Its cycle decomposition shows that a strict cost improvement requires a negative cycle.
Thus (4) is an exact characterization together with \(q\ge c\). Restricting to simple cycles is sufficient because directed closed walks decompose into simple cycles.
The stated potential equivalence is precise and its hypotheses are satisfied: the graph is finite and its retained arc costs are finite. The artificial-source construction supplies finite shortest-path distances whenever there is no negative cycle.
The signs in (5b) and (5c) correctly follow from the residual arc directions. Normalizing \(\pi_s=0\) is valid because adding a constant to all potentials preserves every difference constraint. The variable and constraint counts are correct.
The consequence \(q_r=c_r\) for partially selected types follows immediately from both applicable potential bounds.
Both claims needed to define a finite distance \(D_{R_c}(s,t)\) are established.
First, a negative cycle in \(R_c\) would give a feasible cost-reducing modification of the supplied efficient flow. Second, feasibility using only unselected capacities forces an \(s\)-to-\(t\) path in their forward support. The reachability-cut argument correctly uses \(d>0\).
For the upper bound, core potentials satisfy every difference constraint of \(R_c\), since \(q_r\ge c_r\). Summing along a shortest path gives \(\pi_t-\pi_s\le D\). Flow conservation then gives
\[
\sum_r x_r(\pi_w-\pi_v)=d(\pi_t-\pi_s),
\]
so \(P\le dD\). Types with \(x_r=0\) contribute nothing.
The attainment argument is also complete. Adding the arc \(t\to s\) with cost \(-D\) creates no negative simple cycle: any simple cycle using it contains an original \(s\)-to-\(t\) path of cost at least \(D\). Therefore feasible potentials exist for the augmented graph, and its constraints force \(\pi_t-\pi_s=D\).
The constructed payments satisfy individual rationality and every constraint in (5). Their total equals \(dD\). Thus (6) proves an attained maximum, rather than merely a supremum.
The example satisfies all input assumptions.
The masses sum to
\[
(4n+2)\varepsilon=1.
\]
The chosen diamond flow has demand \(2\varepsilon\) and respects every capacity. The stated cost calculation proves its efficiency: sending amount \(g\) directly increases cost by \(2ng\). The unused direct capacity meets the entire demand.
The residual graph consists exactly of reversed diamond arcs and the forward direct arc. Each simple directed cycle uses the direct arc and one reversed diamond path, giving precisely the \(2^n\) path inequalities in (8).
The facet argument is valid:
These strict inequalities persist in a sufficiently small relative neighborhood within the tight hyperplane. The resulting face therefore has dimension \(4n-1\), proving that each path inequality defines a distinct facet.
The standard halfspace argument is supplied and correctly establishes that every finite exact linear description in the payment variables needs at least one inequality per facet. Fixing the unused direct-type payment to its cost preserves the lower bound.
The graph counts and input-length estimate are correct. Since \(2^n\) exceeds every polynomial in \(n\log n\), this disproves a general polynomial-size payment-only linear description. It does not conflict with the compact extended formulation.
The proposed algorithm operates on a graph with at most \(2\tau\) residual arcs and polynomially many vertices. Bellman–Ford applies despite negative arc costs because the proof establishes absence of negative cycles.
The bit-complexity justification is sufficient. Relevant shortest paths can be chosen simple, so their costs are sums of polynomially many input rationals. Distances, augmented-arc cost, potentials, payments, and the final product with \(d\) consequently have polynomial encoding length. Exact arithmetic and threshold comparison therefore take polynomial time in \(m,\tau,L\).
The output addresses every requested component: exact coalition constraints, the scope of a detour-style description, maximum-payment computation, nonemptiness, and threshold decision complexity. 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.