Answer: Polynomial-time solvable; every valid instance admits a strong equilibrium.
Theorem 3.4 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateEvery single source fair connection game on a series-parallel graph possesses a strong equilibrium.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a directed series-parallel graph with common source \(s\), rational edge costs, and rational masses on finitely many sink types, does there exist a path-mass assignment with no positive-mass measurable coalition whose members can all reroute to strictly lower their costs?
An instance consists of a two-terminal directed series-parallel graph \(G=(V,E)\), oriented from its source \(s\) to its terminal \(t\), with nonnegative rational edge costs \(c_e\); type destinations may be internal vertices.
A society is given by its support: the list of \(\tau\) distinct sink types \(t_i\in V\), each with positive mass \(a_i\) as a binary rational, with \(\sum_i a_i=1\). Here \(\tau\) is the support size, not the number of possible types. Put \(m=|V|+|E|\), and let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
Represent type \(i\) by an atomless interval of Lebesgue measure \(a_i\). A path-mass assignment is a measurable assignment of one directed \(s\)-to-\(t_i\) path to each individual; arbitrary real path masses and splitting of each type among paths are allowed. All such paths are available; the empty path is allowed when \(t_i=s\).
If \(x_e\) is the total mass using edge \(e\), an individual using path \(P\) incurs cost \(C(P,x)=\sum_{e\in P}c_e/x_e\). At zero load, an edge contributes \(+\infty\) if \(c_e>0\), and zero if \(c_e=0\).
A profitable deviation is a measurable coalition of positive mass measurably assigning its members new paths to their original destinations, while outsiders retain their paths, such that almost every coalition member has strictly lower cost at the resulting loads. A strong equilibrium admits no profitable deviation; assignments are identified up to null sets.
Is deciding whether such a path-mass assignment exists solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finitely many indivisible players, single-source fair connection games on directed series-parallel graphs always admit a strong equilibrium ([Epstein–Feldman–Mansour](https://cs.tau.ac.il/~mfeldman/papers/EFMj07.pdf)).
This discrete existence guarantee extends to arbitrary nonincreasing per-user edge costs ([Holzman–Monderer](https://holzman.technion.ac.il/files/2015/08/strongeq.pdf)). No result settling the exact atomless decision problem above was located.
Every instance in the question admits a strong equilibrium. Consequently, the existence decision problem is polynomial-time solvable: on the specified domain, the algorithm always returns YES.
The proof transfers the finite-player existence theorem to the atomless model by compactness. The essential step is to show that a profitable coalition in a limiting assignment would yield a profitable coalition in sufficiently fine finite-player approximations.
We use the following established result:
Finite-player existence theorem. Every finite single-source fair connection game on a directed series-parallel graph, with nonnegative edge costs and all source-to-destination paths available, has a strong equilibrium. Destinations may be internal vertices. This is Theorem 3.4 of [Epstein–Feldman–Mansour](https://cs.tau.ac.il/~mfeldman/papers/EFMj07.pdf).
The graph and path-availability hypotheses are exactly those in the question. We will apply this theorem with finitely many players having the prescribed destinations and appropriately scaled edge costs.
A type whose destination is the source has only the empty path, because the graph is acyclic. Such individuals always pay zero and cannot strictly improve. Corresponding finite players can therefore be omitted when applying the theorem and added back afterward. If every destination is the source, the all-empty assignment already proves the result.
For each type \(i\), let \(\mathcal P_i\) be the set of directed paths from \(s\) to \(t_i\), including the empty path when appropriate. These sets are nonempty and finite: every vertex of the given graph is reachable from its source, and the graph is finite and acyclic.
Represent an assignment by its path masses \(z_{iP}\), satisfying
\(z_{iP}\geq 0,\qquad \sum_{P\in\mathcal P_i}z_{iP}=a_i.\)
Every such vector is realizable by a measurable assignment: partition the interval representing type \(i\) into subintervals of these measures and assign the corresponding paths.
Its edge loads are
\(x_e(z)=\sum_i\sum_{P\in\mathcal P_i:\,e\in P}z_{iP}.\)
Write \(C(P,x)\) for the path cost under the convention in the question. If \(z_{iP}>0\), then every edge of \(P\) has load at least \(z_{iP}\). Hence \(C(P,x(z))\) is finite. Since there are finitely many paths, almost every individual in any assignment has finite cost.
A measurable coalition and its reassignment can be described by finitely many numbers
\(b_{iPQ}\geq 0,\qquad P,Q\in\mathcal P_i,\)
where \(b_{iPQ}\) is the mass of type \(i\) coalition members whose original path is \(P\) and whose new path is \(Q\). Put
\(B_{iP}=\sum_{Q\in\mathcal P_i}b_{iPQ}.\)
These numbers necessarily satisfy
\(B_{iP}\leq z_{iP}.\)
Conversely, these inequalities suffice to realize the specified reassignment: atomlessness allows the individuals originally assigned \(P\) to be partitioned into measurable subsets of the required measures.
The resulting edge loads are
\(y_e=x_e(z)+\sum_i\sum_{P,Q\in\mathcal P_i}b_{iPQ}\bigl(\mathbf 1_{\{e\in Q\}}-\mathbf 1_{\{e\in P\}}\bigr).\)
Equivalently, these loads consist of the nonnegative outsider loads plus the coalition’s new loads. In particular, if \(b_{iPQ}>0\), then
\(x_e(z)\geq z_{iP}>0\quad\text{for every }e\in P,\)
and
\(y_e\geq b_{iPQ}>0\quad\text{for every }e\in Q.\)
Thus both the old and new costs of every positive-mass path pair are finite.
A profitable coalition has positive total mass and satisfies
\(C(Q,y)<C(P,x(z))\qquad\text{whenever }b_{iPQ}>0.\)
Indeed, all individuals in a given path pair have the same old and new costs. If that pair had positive mass and failed this inequality, profitability almost everywhere would fail.
Because the masses are rational, choose a positive integer \(D\) such that \(Da_i\) is an integer for every type. For each positive integer \(k\), set \(N_k=kD\).
Construct a finite fair connection game with \(N_ka_i\) players of type \(i\), each choosing a path in \(\mathcal P_i\), and edge costs
\(\widehat c_e^{(k)}=N_kc_e.\)
For bookkeeping, give each finite player mass \(1/N_k\). If \(n_e\) finite players use edge \(e\), their empirical load is \(x_e=n_e/N_k\). A player using that edge pays
\(\dfrac{\widehat c_e^{(k)}}{n_e}=\dfrac{N_kc_e}{n_e}=\dfrac{c_e}{x_e}.\)
Consequently, finite-player costs agree exactly with the costs evaluated at empirical loads. This equality holds both before and after every finite coalition deviation.
All hypotheses of the finite-player theorem hold: the graph and available paths are unchanged, all players share the source, and the scaled edge costs are nonnegative. Choose a finite strong equilibrium and denote its normalized path masses by \(z^{(k)}\). Each coordinate is an integer multiple of \(1/N_k\), and
\(\sum_{P\in\mathcal P_i}z^{(k)}_{iP}=a_i.\)
The feasible path-mass vectors form the compact, finite-dimensional set
\(\mathcal Z=\prod_{i=1}^{\tau}\left\{(z_{iP})_{P\in\mathcal P_i}:z_{iP}\geq0,\ \sum_{P\in\mathcal P_i}z_{iP}=a_i\right\}.\)
Pass to a convergent subsequence and relabel it, retaining \(N_k\to\infty\). Thus
\(z^{(k)}\longrightarrow z\in\mathcal Z.\)
We prove that a measurable assignment realizing \(z\) is a strong equilibrium.
Suppose, for contradiction, that such an assignment admits a profitable coalition. Let \(b_{iPQ}\), \(B_{iP}\), and \(y\) describe it as above.
The initial finite equilibrium may have slightly less mass on a particular path than the limit does. To respect every available supply, define
\(\alpha_k=\min\left(\{1\}\cup\left\{\dfrac{z^{(k)}_{iP}}{B_{iP}}:B_{iP}>0\right\}\right).\)
The coalition has positive mass, so there is at least one positive \(B_{iP}\). For each such row,
\(\dfrac{z^{(k)}_{iP}}{B_{iP}}\longrightarrow\dfrac{z_{iP}}{B_{iP}}\geq1.\)
There are finitely many rows. Therefore \(0\leq\alpha_k\leq1\) and \(\alpha_k\to1\).
Define integer numbers of deviating players by
\(q^{(k)}_{iPQ}=\left\lfloor N_k\alpha_kb_{iPQ}\right\rfloor,\)
and normalized reassignment masses by
\(b^{(k)}_{iPQ}=q^{(k)}_{iPQ}/N_k.\)
For every original type-path pair,
\(\sum_Qq^{(k)}_{iPQ}\leq N_k\alpha_kB_{iP}\leq N_kz^{(k)}_{iP}.\)
The right-hand side is exactly the number of available finite players of that type using that path. Thus we can select disjoint groups of the prescribed sizes, reassign each group to its specified new path, and leave all other players fixed.
Moreover,
\(0\leq\alpha_kb_{iPQ}-b^{(k)}_{iPQ}<1/N_k,\)
so \(b^{(k)}_{iPQ}\to b_{iPQ}\) for every pair. A zero limiting pair never recruits players. Every positive limiting pair recruits at least one player for all sufficiently large \(k\). In particular, the resulting finite coalition is eventually nonempty.
Let \(x^{(k)}=x(z^{(k)})\), and let \(y^{(k)}\) be the empirical loads after the constructed finite deviation. Their load formulas give
\(x^{(k)}\longrightarrow x(z),\qquad y^{(k)}\longrightarrow y.\)
Fix a pair with \(b_{iPQ}>0\). As established in Section 2, every edge of \(P\) has positive limiting old load, and every edge of \(Q\) has positive limiting new load.
For an edge of positive cost, the function \(u\mapsto c_e/u\) is continuous at every positive load. For an edge of zero cost, its contribution is identically zero, including at zero load. Hence
\(C(P,x^{(k)})\longrightarrow C(P,x(z)),\)
and
\(C(Q,y^{(k)})\longrightarrow C(Q,y).\)
The limiting inequality is strict:
\(C(Q,y)<C(P,x(z)).\)
It follows that, for all sufficiently large \(k\),
\(C(Q,y^{(k)})<C(P,x^{(k)}).\)
There are only finitely many positive-mass pairs, so one sufficiently large \(k\) makes these inequalities hold simultaneously for every pair that recruits players.
Every member of the constructed finite coalition therefore strictly improves. The equality between finite costs and empirical-load costs proved in Section 3 makes this a profitable deviation in the finite fair connection game. This contradicts the choice of its initial profile as a strong equilibrium.
The contradiction proves that \(z\) admits no profitable atomless coalition. Its measurable realization is the required strong equilibrium.
All valid instances are therefore YES instances. Under the stated instance promise, returning YES takes \(O(1)\) time, independently of \(m,\tau,L\); reading the entire encoding first takes \(O(L)\) time.
The potentially large denominator, the number of paths, and the limiting sequence are used only in the existence proof. The decision algorithm does not construct them.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output establishes that every valid instance admits a strong equilibrium, so the promised existence decision problem is polynomial-time solvable. I found no mathematical errors or gaps requiring clarification.
The citation is accurate. Theorem 3.4 states existence of strong equilibria for single-source fair connection games on directed series-parallel graphs. The paper’s definitions allow nonnegative finite edge costs, include all source-to-destination paths, and impose no requirement that each player’s destination be the graph’s terminal. Its series-composition proof explicitly treats destinations inside the components. The graph definition matches the task’s directed two-terminal series-parallel graph. [Epstein–Feldman–Mansour, Sections 2.2–2.3 and Theorem 3.4](https://cs.tau.ac.il/~mfeldman/papers/EFMj07.pdf).
The application therefore satisfies the stated hypotheses:
The treatment of destination \(s\) is correct. Acyclicity leaves only the empty path; those players contribute no edge load, pay zero, and cannot strictly improve. Omitting them and adding them back does not affect equilibrium. The all-empty case is also correctly handled.
Every vertex is reachable from \(s\), and the graph is finite and acyclic. Thus each \(\mathcal P_i\) is nonempty and finite. Consequently, the path-mass representation has finitely many coordinates.
The constraints
\[
z_{iP}\geq 0,\qquad \sum_{P\in\mathcal P_i}z_{iP}=a_i
\]
correctly characterize feasible assignments. Partitioning each type interval realizes any such vector measurably.
The edge-load formula is correct. If \(z_{iP}>0\), every edge on \(P\) has load at least \(z_{iP}\), so its path cost is finite. Individuals on zero-mass paths form a null set because there are only finitely many paths. The assertion of finite cost almost everywhere follows.
The quantities \(b_{iPQ}\) correctly record coalition mass by type, original path, and new path. The supply constraints
\[
\sum_Q b_{iPQ}\leq z_{iP}
\]
are necessary and sufficient: each original-path population is a measurable subset of an atomless interval and can be measurably subdivided into the specified finite collection of masses.
The post-deviation load formula correctly subtracts coalition members’ original usage and adds their new usage. Its alternative interpretation as outsider loads plus new coalition loads ensures nonnegativity.
For every positive-mass pair, the claimed lower bounds hold:
\[
x_e(z)\geq z_{iP}>0\quad(e\in P),\qquad
y_e\geq b_{iPQ}>0\quad(e\in Q).
\]
Both compared costs are therefore finite.
Profitability almost everywhere is correctly translated into a strict inequality for each positive-mass pair. Within any pair, all members have identical old and new costs. A failed inequality on a positive-mass pair would contradict the definition of a profitable coalition. Zero-mass pairs have no effect on loads or profitability.
Rational masses admit a common positive denominator \(D\). Thus \(N_ka_i\) is an integer for every type when \(N_k=kD\), and the total number of players is \(N_k\).
The scaling computation is exact:
\[
\frac{N_kc_e}{n_e}=\frac{c_e}{n_e/N_k}.
\]
It applies to every edge used by a finite player, both before and after a deviation, since such an edge has \(n_e\geq 1\). Unused edges require no evaluation in that player’s cost.
The normalized finite profiles satisfy the required type totals. The feasible set is a finite product of closed, bounded simplices and is compact. Passing to a convergent subsequence is justified; the corresponding denominators still tend to infinity. Exponentially many paths cause no difficulty for this existence argument.
The definition of \(\alpha_k\) is well-defined because it divides only by positive \(B_{iP}\). For every such row,
\[
\frac{z^{(k)}_{iP}}{B_{iP}}\longrightarrow
\frac{z_{iP}}{B_{iP}}\geq 1.
\]
There are finitely many rows, so the minimum with \(1\) tends to \(1\). Early values of \(\alpha_k\) may be zero without affecting the eventual argument.
The floor construction produces nonnegative integer coalition sizes. Its supply bound is correct:
\[
\sum_Q q^{(k)}_{iPQ}
\leq N_k\alpha_kB_{iP}
\leq N_kz^{(k)}_{iP}.
\]
The final quantity is exactly the available number of finite players in that row. Disjoint groups of the specified sizes can therefore be selected.
The rounding bound
\[
0\leq\alpha_kb_{iPQ}-b^{(k)}_{iPQ}<\frac1{N_k}
\]
implies coordinatewise convergence to \(b\). A zero limiting pair recruits no players. Every positive limiting pair eventually recruits players because \(N_k\alpha_kb_{iPQ}\) tends to infinity. The constructed coalition is eventually nonempty.
Both old and new load vectors converge, since their formulas are finite linear combinations of convergent coordinates.
The continuity argument addresses the zero-load singularity correctly. Every edge whose cost is evaluated for a positive-mass pair has positive limiting load in the relevant profile. Positive-cost edge contributions are continuous there; zero-cost contributions are identically zero under the task’s convention.
Thus both path costs converge to finite limits. Each strict limiting improvement persists for sufficiently large \(k\). Since there are finitely many positive-mass pairs, one sufficiently large index works for all recruited groups simultaneously.
Every selected finite player strictly improves. This contradicts finite strong equilibrium using exactly the cost correspondence established earlier. Hence the limiting assignment admits no profitable measurable coalition.
The conclusion resolves the requested existence decision problem. Under the valid-instance promise, an algorithm returning YES takes \(O(1)\) time in \(m,\tau,L\); reading the input first takes \(O(L)\). No equilibrium construction is required by the task, so the nonconstructive compactness argument is sufficient.
Actionable feedback: No repair or additional mathematical clarification 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.