TRANSMISSION // 2611.22216v1
How Hard Is Equilibrium in a Seller Network?
Source published
The authors report hardness results for approximate equilibrium, an efficient scheme under specific bounds, and finite representations for exact equilibria.

In this pricing game, each seller sets one price for captive buyers and shared markets with neighboring sellers. The authors ask how hard it is to compute an equilibrium—and whether exact equilibria can be described with finitely many price intervals.
A pricing game on a network
In the Bertrand network game, sellers share some markets with neighboring sellers, while they may also have captive buyers. Each seller posts a single price across these settings and cannot set separate prices for different markets. The paper studies the existence, computation and representation of equilibria in this mathematical game.
A Nash equilibrium is a set of strategies in which no participant can improve its payoff by changing strategy alone, given the others’ choices. Earlier work, as summarized by the authors, established equilibrium existence and polynomial-time algorithms for trees. Whether efficient algorithms could compute equilibria for general graphs remained open.
Hardness and a restricted-case algorithm
MohammadTaghi Hajiaghayi and Suho Shin report that computing any constant-error approximate Nash equilibrium is PPAD-complete. The abstract does not specify the error measure, so this result should be understood using the paper’s formal definition rather than a particular interpretation of “constant error.” PPAD is a complexity class used in classifying problems where a solution is guaranteed to exist; the abstract reports the classification but does not explain its formal definition.
The hardness holds even for sparse bipartite graphs with maximum degree five and constant integer market weights. This is a result under the stated restrictions. The abstract does not spell out all the formal conditions or proof details, so it does not support a broader claim about the difficulty of every possible network or implementation.
The authors also present an efficient polynomial-time approximation scheme (EPTAS) when both maximum degree and the number of sellers with captive buyers are bounded. This is a result for networks satisfying those bounds, not a guarantee covering every network. The abstract does not provide practical running times for particular instances.
Finite descriptions of exact equilibria
A separate part of the paper considers how exact equilibria can be represented. Such equilibria may involve sellers randomizing prices over continuous intervals. The authors ask whether an exact equilibrium can nevertheless be described using finitely many price intervals, a measure they call structural complexity.
They report that every achievable equilibrium revenue profile can be realized by an equilibrium with structural complexity O(2ⁿ). The abstract does not define n, so its meaning and the scale of this bound should be checked in the full paper before interpreting it more specifically. The authors say the bound yields an exact algorithm with doubly exponential running time. This establishes a theoretical route to an exact solution, not that the algorithm is practical for large instances.
The abstract also reports that there exist instances where the unique equilibrium realizing the target revenue profiles has structural complexity Ω(2ⁿ). This statement concerns those instances and equilibria realizing those profiles; it does not establish uniqueness of equilibrium overall.
What the evidence supports
These are theoretical results about a specified game, not evidence about prices or behavior in observed markets. The supplied evidence is the paper’s abstract, which gives the headline claims but not enough detail to explain the proofs, the precise error definition, or how the algorithms perform on particular instances. That is a limitation of the material available for this account, not a conclusion about what the full paper contains.
The source is an arXiv preprint, and the supplied material does not establish its peer-review status. Accordingly, the results here are presented as the authors’ reported contributions, not as independently verified findings. The central distinction is between finding an approximate equilibrium—which the authors classify as PPAD-complete under stated conditions—and representing exact equilibria, for which they report finite bounds that can grow exponentially.
- Bertrand network game
- Nash equilibrium
- algorithmic game theory
- PPAD-completeness
- pricing networks
Related reading
Automatically matched by shared topic keywords. These links do not imply that the sources agree or establish a consensus.
Bounding Solver Variables Speeds Up a Three-Player Poker Equilibrium Search
Source published
Shared keywords: nash equilibrium
When opposites become the same game
Source published
Shared keywords: nash equilibrium
Why sharing resources can benefit the whole but fail the individual
Source published
Shared keywords: nash equilibrium
A new route to stable strategies in Colonel Blotto games
Source published
Shared keywords: nash equilibrium
What a memory network can teach us about strategic choices
Source published
Shared keywords: nash equilibrium