WorksComputer Science
Sharp Complexity Thresholds for Network Cournot Competition
Abstract
We determine the approximation complexity of network Cournot equilibrium as a function of demand degree and the number of firms sharing a market. For common, nonincreasing concave polynomial inverse demands, convex quadratic costs of firms' allocation vectors, and rational total capacities, high-precision approximation is polynomial-time solvable for cubic demands, regardless of market size. Quartic demands remain tractable when each market has at most three firms, and quintic demands remain tractable with at most two. These thresholds are exact: approximation at a fixed positive profit-regret tolerance is PPAD-hard for quartic demands with four firms per market, quintic demands with three, and sextic demands with two. Each hardness result uses one fixed demand curve in every market, a constant number of markets per firm, and globally nondecreasing strongly convex quadratic costs. We also give a polynomial-time algorithm for arbitrary-degree nonincreasing concave polynomial demands when each firm's convex polynomial cost depends only on its total production. The algorithm applies to arbitrary access graphs and permits firm-specific inverse demands. Its running time is polynomial in the input size and the logarithm of the inverse accuracy. The algorithm assigns one marginal charge to each firm and adjusts the charges until each firm's total sales approximate the quantity it would produce at that charge.
Introduction
In network Cournot competition, a firm chooses how much to supply to each market it can access. A market’s price depends on its total supply, while a firm’s production cost couples its decisions across markets. Two firms can compete in one region and face different sets of competitors elsewhere.
Abolhassani, Bateni, Hajiaghayi, Mahini, and Sawant [1] developed an algorithmic treatment of this model. For affine inverse demands, they gave a potential function that represents all firms’ incentives in a single convex optimization problem. Nonlinear demand can destroy this potential structure. In that setting they used complementarity methods under additional monotonicity hypotheses.
Two questions arise. First, how much nonlinearity is needed before equilibrium computation becomes hard? Second, which forms of production cost preserve efficient computation beyond the affine case? Convexity alone does not answer either question. Each firm’s optimization problem is concave in its own quantities, but equilibrium requires solving these problems simultaneously. Even strongly concave polynomial games can be PPAD-hard to approximate at constant error [19]. The issue is whether the specific common-price structure of Cournot revenue prevents that hardness.
| Demand degree bound | ||||
| P | P | P | P | |
| P | P | P | Hard | |
| P | P | Hard | Hard | |
| P | Hard | Hard | Hard |
Table 1. The classification for common concave polynomial demands, convex quadratic allocation costs, and rational total capacities. P denotes polynomial time in input size and the logarithm of inverse accuracy; Hard denotes PPAD-hardness at a fixed positive error. Degree and participation are upper bounds on the input class.
We answer the first question by giving an exact classification in terms of two elementary parameters: the degree of the inverse-demand polynomials and the maximum number of firms sharing a market. We answer the second for costs of total production by a different algorithm, which works for every explicitly encoded polynomial degree. The distinction between total-production costs and general convex quadratic allocation costs is essential. A cost of total production couples markets only through one scalar; a quadratic cost of the full allocation vector can couple different market quantities separately.
Classification by demand degree and market size
Let be a bound on demand degree and a bound on the number of firms in each market. In this first result, every market has one inverse-demand function common to its participating firms. Firms have explicit rational total-production capacities and arbitrary convex quadratic costs of their own allocation vectors. The demand polynomials are nonincreasing and concave on the feasible intervals. An additive equilibrium is a feasible pure quantity profile at which no firm can improve its profit by more than through a unilateral deviation. A pure equilibrium exists throughout this class (§ 2). A hard entry in Table 1 concerns the search for an approximate equilibrium. PPAD-hardness means that a polynomial-time algorithm for this search would give polynomial-time algorithms for every problem in PPAD.
Theorem 1.1 (Classification). For the class above, the approximation complexity is given by Table 1. Each polynomial-time entry admits a deterministic algorithm running in poly time for additive accuracy , where is the input length. Each hard entry is PPAD-hard for a universal constant positive accuracy. Hardness already holds with one fixed identical demand polynomial in all markets, a constant number of markets per firm, and globally coordinatewise nondecreasing strongly convex quadratic costs. The fixed-degree, bounded-local-dimension rational-output versions defined in Appendix § 7 are PPAD-complete.
Thus the first hard degree is six when markets have at most two firms, five when they have at most three, and four when four or more firms are allowed. The classification is sharp unless PPAD search admits polynomial-time algorithms. With one firm per market there are no strategic interactions, and each firm’s problem is concave optimization for every degree.
In all three hard families, every market uses the same demand curve and every firm’s quadratic cost is strongly convex and nondecreasing on the entire nonnegative orthant. Each firm has at most 26, 50, or 74 quantity coordinates in the sextic, quintic, or quartic construction, respectively. All three constructions use the same fixed total capacity, and prices are positive throughout the feasible region.
We obtain both sides of the classification from the same curvature threshold. In Section 3 we bound how rapidly the slope of a low-degree demand can change. Up to the market-size cutoff, this bound makes the negative marginal-profit operator monotone [12], so we can approximate an equilibrium by solving a variational inequality [3]. In Section 4 we choose a demand above the cutoff and link markets in a chain. Along the chain we amplify one firm’s influence on another while keeping the reverse influence and the receiver’s own payoff curvature bounded. We use this asymmetry to encode a directed payoff interaction.
Costs of total production
The reduction couples individual deliveries through the firm’s cost. What if a firm pays the same production cost for any two allocations with the same total output ? Under this restriction we can compute an equilibrium at every demand degree.
Theorem 1.2 (Costs of total production). Consider an arbitrary firm–market access graph and rational total capacities. Suppose that firm has a convex polynomial cost , and each inverse demand is a nonincreasing concave polynomial on its feasible interval. Demands may be firm-specific. For every , a rational feasible additive pure equilibrium can be computed deterministically in time. Polynomial coefficients are rational and given by dense lists.
In Section 5 we give each firm a marginal charge for production and compute supply and sales separately at those charges. Whenever a firm would produce more than it would sell, we can lower its charge to bring those quantities closer together. To obtain a polynomial bound on the number of updates, we control how much this step widens the corresponding gaps for its rivals.
Related work
Networked quantity competition. Abolhassani et al. [1] introduced an algorithmic treatment of Cournot competition on a bipartite firm–market graph. Their affine-demand potential accommodates convex costs of each firm’s market-specific output vector; their nonlinear results use additional conditions on the induced complementarity problem. Bimpikis et al. [6] study how the network determines quantities, profits, and the effects of changes in market access. Their general model has common concave demands and convex costs of total output. Their Proposition 1 states uniqueness for strictly decreasing concave demands and convex increasing total costs; their more explicit network formulas specialize the economic primitives.
Harks and Timmermans [13, 15] compute equilibria exactly in polynomial time for rational atomic splittable singleton games with player-specific affine costs. An equilibrium-preserving reduction gives a multimarket Cournot application with firm-specific affine inverse demands and quadratic costs of total production. Their separate work on nonlinear convex-cost polymatroid games [14] gives a pseudo-polynomial algorithm and a nonlinear Cournot application. Bhaskar and Lolakapuri [5] study convex-cost atomic splittable routing and give parallel-link algorithms whose running times are exponential in the number of players or the number of links. Our total-cost theorem allows both quantities to vary and gives a running time polynomial in the input size and the logarithm of the inverse accuracy. Hota and Kapoor [16] give strongly polynomial equilibrium algorithms for a multiproduct Cournot model with substitutable goods and quadratic utilities.
Marginal-profit formulations and capacities. Alsabah et al. [2] analyze common concave inverse demands, linear production and transport costs, and firm capacities. They introduce a reduced game in marginal profits, prove uniqueness, and establish global convergence of simultaneous best responses in those variables. Caldentey and Haugh [8] characterize equilibria for heterogeneous resource-constrained firms; their main computational model has affine demand, and they also discuss nonlinear extensions. Guo, Wang, and Candogan [11] study production and shared transportation capacities with endogenous congestion prices. These models emphasize different ways in which resource constraints couple markets. Our nonlinear algorithm treats independent firm strategy sets and polynomial costs of total production, with an explicit high-precision running-time bound.
Marginal-cost coordinates and contraction arguments have older antecedents in Cournot and routing games [5, 18]. The sign structure of the reduced residual also relates to nonlinear -function and -function complementarity [21]. To obtain a running time polynomial in the input size and the requested precision, we bound the decrease in the total residual per update and the accuracy needed in each scalar market solve.
Monotonicity and hardness. Harks [12] gives curvature criteria for universal monotonicity in atomic splittable congestion games. We specialize the market criterion to common Cournot demand and identify which polynomial degrees satisfy it for each market size. For those degrees we apply the high-precision variational-inequality algorithm of Anagnostides et al. [3].
Hardness for strongly concave polynomial games is already known: Papadimitriou et al. [19] prove constant-error PPAD-hardness in that broader class. Our reductions impose the specific Cournot revenue form, common inverse demand within a market, convex nondecreasing quadratic production costs, and the small market sizes at the classification boundary. They start from the constant-error hardness of degree-three bipartite two-action polymatrix games proved by Deligkas et al. [9]. Klimm and Warode [17] establish PPAD-completeness for atomic splittable routing with player-specific affine costs on general networks. Such routing strategy spaces differ from the singleton structure underlying network Cournot games, so that result neither gives our restricted hardness instances nor conflicts with our positive results.
Model and equilibrium approximation
An access graph is a bipartite graph , with firms and markets. Write for the markets accessible to firm and for the firms incident to market . Firm chooses a vector in
Let , , , and . The common-demand model has profit
Here is nonincreasing and concave on , where , and is convex on . The polynomial-time algorithm for total-production costs also permits firm-specific demands and uses costs .
Each profit is concave in its own strategy: a market contribution has own second derivative , and the cost is convex. The feasible sets are compact and convex. These games therefore have pure equilibria by the standard existence theorem for concave games [20]. Define actual unilateral regret by
An additive equilibrium has for every firm. All approximation statements in this paper refer to this profit guarantee.
Rational coefficients and capacities are represented in binary; polynomial coefficient lists are dense. The input length includes the graph and these descriptions. Accuracy is specified as , and running times are measured in the standard rational-input model. Arbitrary positive rational accuracy is handled by a smaller dyadic target, including the supplied accuracy’s encoding in the input length. Convexity, monotonicity, and concavity are promises on the specified domains. Zero-capacity firms and isolated vertices are removed before running an algorithm. Their deliveries are restored as zeros. If no coordinates remain, the zero profile is an equilibrium.
For hardness, the reduction must decode any feasible profile that satisfies the regret bound, including one with real-valued deliveries. For PPAD membership we also need a finite output that can be checked in polynomial time. In Appendix § 7 we specify a polynomial encoding bound for rational outputs and verify the regret condition when degree and local dimension are fixed.
Polynomial-time regimes for allocation costs
To compute equilibria in the polynomial-time regimes of Table 1, we show that the firms’ negative marginal-profit map is monotone. Consider a single market. An increase in a rival’s output can lower the price and steepen the demand curve. The change in slope matters more to a firm with a large delivery , since its marginal revenue is . We need a bound that holds for every division of total output among the firms.
Write . For with , measure the change in slope by . We start by comparing the endpoint value of with its average on , since and . For a quartic demand, for instance, is a nonnegative quadratic. Its endpoint value is at most four times its average, so the ratio is at most four. We next determine how large a ratio each market size allows. With three suppliers the monotonicity cutoff is exactly four [12], so the quartic bound suffices. For each degree and market size that passes this test, we use monotonicity to compute a profile with profit regret at most .
Lemma 3.1 (Endpoint bounds). Let be a polynomial nonnegative on . If its degree is at most one, two, or three, respectively, then
respectively. Each constant is sharp.
Proof. For the three degree bounds, respectively, exact integration gives
Each identity follows by checking the monomials up to its stated degree. All terms on the right are nonnegative, giving the desired bounds on . Equality is attained by , , and , respectively.
Corollary 3.2 (Curvature of low-degree demands). Let be nonincreasing and concave on . If its degree is at most three, four, or five, then, wherever and ,
respectively.
Proof. Put and . If is zero the result is immediate. Otherwise . Applying Lemma 3.1 to bounds by the corresponding constant.
To apply the curvature bound, consider a simultaneous change in the firms’ deliveries. If is the Jacobian of negative marginal revenues, monotonicity requires along feasible directions. Since , it suffices to check the symmetric part. Write for firm ’s share and . Dividing the symmetric part by gives the matrix below.
Lemma 3.3 (Market-size criterion). For and , the matrix
is positive semidefinite for every probability vector if and only if .
Proof. The matrix depends affinely on , and the positive semidefinite cone is convex. It suffices to check the simplex vertices. By symmetry take . On vectors whose first coordinate and sum of remaining coordinates are zero, the matrix is the identity. An orthonormal basis for the remaining two directions is and . On this subspace the matrix is
The diagonal entries are positive, and the determinant equals
This proves both directions.
We now compare the curvature bounds with the cutoff for each market size. For the entries where the bounds meet the cutoff or fall below it, we assemble the market contributions and convex costs into a monotone variational inequality.
Proposition 3.4 (Polynomial-time upper bounds). The entries of Table 1 admit a rational additive equilibrium in time, with no restriction on local strategy dimension.
Proof. Let . Fix a market with demand , total output , and firms, and put . The negative marginal revenue of firm is . Its derivative with respect to is . Thus, for and , the symmetric part of the market Jacobian is
The cutoff in Lemma 3.3 is . It equals six for two firms, four for three firms, and exceeds two for every finite . Thus the curvature bounds 6, 4, 2 from Corollary 3.2 give the quintic, quartic and cubic entries, respectively. In particular, the quartic bound includes equality for three firms. With four firms the cutoff is , so the bound of four no longer suffices. The lower bound for that class is proved separately in § 4. With one firm, the contribution is the nonnegative scalar for every degree. At , all deliveries vanish and the unscaled matrix is . If and , the nonnegative, nondecreasing polynomial vanishes on , so its derivative there is also zero. Convex costs add positive semidefinite Hessians. Integrating along line segments in proves that is monotone.
We apply the polynomial-time variational-inequality algorithm of Anagnostides, Farina, Sandholm, and Zhang [3 Theorem 4.7]. For a monotone continuous map on a compact convex domain, a Stampacchia solution exists and is also a Minty solution. Their algorithm therefore returns a feasible rational such that
The following facts verify the computational assumptions. The map is an explicit polynomial. Coefficient absolute-value bounds on the capacity box bound its magnitude and Lipschitz constant by numbers whose logarithms are polynomial in the input length. Membership, separation, linear optimization, and Euclidean projection over are rational polynomial-time operations.
If only one delivery coordinate survives preprocessing, a scalar bisection suffices on its capacity interval. Own marginal profit is nonincreasing. Its signs at the endpoints either certify an optimal endpoint or bracket a zero. Given a coefficient bound on its absolute value, reducing the bracket width to bounds the profit gap by . We may therefore suppose in the ellipsoid construction.
The required well-bounded domain can be obtained by a rational affine change of variables. After removing zero-capacity coordinates, rescale . If firm has coordinates, translate its unit-capacity simplex by the vector with all entries . Scale the product by . The transformed domain contains the Euclidean unit ball and lies in a ball of radius . Indeed, before scaling its inner radius is at least and its outer radius is at most . Writing the inverse coordinate change as , use . This preserves the variational-inequality gap exactly, as well as monotonicity, while keeping all oracle descriptions and logarithmic bounds polynomial. Euclidean projection onto the transformed product of simplices is also rational and polynomial-time: sort coordinates and subtract a common threshold in each block. These are the well-bounded domain hypotheses used in [3].
Finally, in (3) let differ from only in firm ’s coordinates. Concavity of that firm’s profit gives
Thus the returned solution has the required actual regret. □
PPAD-hardness at the degree thresholds
At the first degree beyond each polynomial-time regime, we use the extra curvature to encode a two-action polymatrix game in a Cournot economy. Each source player becomes a firm whose deliveries to two private markets encode its action probabilities. We need to recover a -equilibrium of the source game from any sufficiently accurate equilibrium of the economy. To do so, we arrange that a source deviation worth more than gives the corresponding firm a unilateral deviation worth more than the Cournot regret tolerance.
Consider a payoff entry that contributes to the receiver when the receiver and sender play the corresponding actions with probabilities and . Holding fixed, an increase of costs the receiver , regardless of its initial . On a single shared market the sender can affect the price, but the receiver’s marginal revenue also falls as its own output rises. An interior quantity can therefore be optimal even when the source player strictly prefers a pure action. We insert relay firms between the sender and receiver to amplify the term proportional to while keeping the receiver’s own payoff curvature and the influence in the opposite direction bounded. Each shared market has one high-output and low-output firms. For we use degrees 6, 5, 4, respectively.
Theorem 4.1 (Fixed-demand hardness). There is a universal rational with the following property. For each there is one fixed rational polynomial , nonincreasing and concave on , for which computing an additive pure Nash equilibrium is PPAD-hard. Every market uses , every firm has total capacity 1000, and prices are positive on the feasible quantity range. Costs are strongly convex quadratics, are coordinatewise nondecreasing on the entire nonnegative orthant, and vanish at zero. There are at most firms per market and at most markets per firm. The bounded rational-output search relations specified in Appendix § 7 are PPAD-complete.
We build the reduction in two stages. First we work in an auxiliary quadratic game, where we can solve for the relay signals at fixed endpoint strategies. When we then measure a player’s gain from deviating, we hold those signals fixed because only that player can move. Second we implement the quadratic game with Cournot deliveries. We use costs to keep each firm’s deliveries consistent with a single strategy, and we choose the delivery scale so that the quadratic terms determine its incentives up to a small error.
Two-action polymatrix games
Take as input a bipartite polymatrix game of maximum degree three, with two actions per player and total payoffs normalized to . Computing a -Nash equilibrium for these games is PPAD-hard by Deligkas, Fearnley, Hollender, and Melissourgos [9, Theorem 4.4]. To assign one relay chain to each payoff entry, we express each player’s payoff as a sum of losses with coefficients in . The losses must preserve the payoff difference between the player’s two actions against any fixed profile of its neighbors. Write for the probability of action . We seek directed loss matrices giving payoffs of the form
To choose the entries, write player ’s action-one minus action-zero payoff difference as . For each nonisolated , choose summing to in the intervals
These intervals are nonempty because . Their summed endpoints contain , by minimizing and maximizing the payoff difference over the neighbor cube. A greedy interval allocation therefore finds rational in polynomial time. Set , , and . Then . Summing over neighbors gives the original difference between pure actions for every profile of the opponents. Affinity in the player’s own strategy gives equality of payoff differences for mixed deviations as well. Isolated players can be restored after decoding.
Equilibria of the quadratic relay game
Fix the strategies at the two ends of one chain. To find what signal reaches the receiver, give each relay a baseline with a large delivery on its incoming market and small deliveries on its outgoing markets. Its signal specifies a change from these quantities. A relay responds to its neighbors on both sides, so we solve for all signals simultaneously. Since we must decode approximate equilibria, we also bound how far the signals can stray from this solution when each relay has small regret.
Let be a fixed polynomial satisfying , , , and . Use the inverse demand . We will choose the price level when we specify the costs. Choose and , and baseline quantities
so that one high-output firm and low-output firms supply total quantity one. A high firm’s signal changes its quantity by , and a low firm’s signal changes its quantity by . Define
At the limiting baseline , the expression is maximized at . Substitution gives
Thus at this limiting choice holds exactly when . Since a shared market has firms, the right-hand side is the monotonicity cutoff from Lemma 3.3. If also and , this inequality puts above the larger root of , producing a growing forward transfer along the chain. Our positive baseline preserves this strict gap. The constants will satisfy
For an integer , let be the tridiagonal matrix with diagonal , subdiagonal , and superdiagonal . With and , put
We choose a fixed chain length in § 4.6 to satisfy
Thus is a large forward gain, a small reverse gain, and a bounded feedback coefficient. There are scalar relay players in each of layers. Their strategy interval is , where . Let have diagonal blocks , subdiagonal blocks , and superdiagonal blocks . Each own diagonal entry is . For endpoint signals and a loss , the vector of derivatives of the relays’ payoffs with respect to their own signals is , where is uniform within the first and last layers. The first-layer entry is , the last-layer entry is , and all others are zero.
Lemma 4.2 (Stable amplification). The unique unconstrained relay solution is uniform in each layer, , lies in the interior of , and satisfies
If each relay has regret at most , then
The parameters will make this bound less than .
Proof. In the weighted maximum norm , the nonnegative matrix has norm below . Hence is invertible, its inverse is nonnegative, and . The forcing in the first line of Eq. (9) has weighted norm at most . The resulting solution obeys . Tridiagonal cofactor expansion gives
which proves the boundary identities.
For stability, use layer weights and . The layer weights balance each pair of opposite coefficients, so is symmetric. To bound its quadratic form relative to the weighted norm, put . This symmetric matrix has eigenvalue on each within-layer difference subspace. On the uniform-layer subspace it has diagonal and off-diagonal . Its least eigenvalue there is at least . Applying these bounds to gives
This also proves uniqueness of the full linear solution and its uniformity within layers.
Put . Relay may unilaterally move one tenth of the way toward . Its improvement is
The move is feasible even if is on the boundary. Multiply these individual regret inequalities by and sum. Since ,
The lower bound on the weights proves (10). In particular, this argument neither assumes interiority of the approximate profile nor permits a coordinated deviation.
Market construction and source incentives
We now construct markets with the quadratic incentives just specified. With two firms per market, consecutive relays meet in pairs. One sells a small quantity on a market where the next sells a large quantity. A change in the price slope has a larger effect on the large seller’s marginal revenue, giving the link its direction. With firms, the next relay responds to the combined deliveries of predecessors. All these markets use the same demand curve. To encode a particular loss , we vary the receiver’s delivery with and add a linear cost. We can then isolate the multiple of in the receiver’s marginal payoff and bound the other terms across its incident chains.
For each directed interaction and action pair , make a fresh relay chain and set
For every relay of layer , create one market whose high firm is that relay and whose low firms are the previous layer. Their canonical quantities are
At the first layer, one low firm is source firm , supplying ; the other low firms are fresh dummies, each with canonical quantity . This creates first-layer markets and never places a firm in two roles in one market. At the last boundary, make separate markets whose high firm is source firm and whose low firms are all last-layer relays, with
Every relay is high in one market and low in markets. Figure 1 shows the incidence between layers.

Figure 1. The relay construction, shown schematically. Each block represents a layer of one, two, or three firms. Each internal arrow represents a typical adjacent-layer interaction; intervening layers are suppressed. A common Cournot market creates unequal local cross effects. Repetition amplifies forward influence while keeping the reverse endpoint effect bounded.
Write for a firm’s baseline delivery in a shared market. For raw demand , subtract the linear cost with
Since , this cancels the own first derivative of at the baseline. The own second derivative is and each cross derivative of own marginal revenue is . Consider relay in an interior layer . It is high in one market, with signal coefficient , and low in markets, with coefficient , in units of . Its normalized quadratic payoff has derivative
Indeed, its own coefficient is . Each other same-layer relay shares its outgoing markets. At the first boundary the preceding-layer sum is , and at the last boundary the next-layer sum is . Since and , these derivatives are the entries of in Lemma 4.2.
Let . Add a linear source cost in the normalized quadratic game. For one chain the source receiver’s quadratic contribution is
and the source sender’s is
The normalized quadratic game sums these endpoint payoffs over incident chains. Each source firm chooses the pair in the probability simplex, and each relay chooses its own coordinate in .
Lemma 4.3 (Source regret in the quadratic game). Assume (6) and (8). Let satisfy . At any -equilibrium of the normalized quadratic game, the source profile satisfies
Proof. Fix the profile and differentiate each endpoint payoff with the relays held fixed. Substituting (9) at this profile gives the receiver and sender derivatives, respectively,
For one incoming chain, the difference from the target derivative is at most . For one outgoing chain the absolute derivative is at most . Here we used , , and the relay error bound of Lemma 4.2. Each source action occurs in at most six chains in each direction, so its derivative differs from times the derivative of (4) by at most .
With all relays held fixed, a source firm’s own quadratic Hessian is diagonal and has entries of absolute value below . A best source deviation can be taken pure because the source payoff is affine in the player’s own probability. A deviation to a pure source action has distance at most two and squared distance at most two. Hence the gradient error costs at most in the gain from this move. The firm’s own quadratic term costs at most more. Taking , this feasible unilateral move gains at least and at most . Equation (14) follows from . □
Quadratic costs and consistency of deliveries
The quadratic game gives a source player one mixing probability for all its neighbors. In the Cournot economy the corresponding firm can choose a different delivery on every market. To make these choices encode one strategy, we record it in the firm’s private deliveries and penalize discrepancies between that record and its shared deliveries. We design the penalty so that the firm can eliminate it unilaterally by choosing any consistent strategy, including either pure action.
Each non-dummy firm serves two private markets. The canonical private deliveries of a source firm are , and those of a relay are and . The required signal sums are and , respectively. For such a firm each shared canonical quantity has the form , where for a source action and for a relay. Put or , respectively. The firm’s two private coordinates are and , up to ordering. For use , and for use . In both cases . Since and , the resulting rows satisfy
A canonical strategy consists of the private pair for an admissible source probability or relay signal and all its shared deliveries given by (16). A dummy’s canonical strategy is the singleton . Thus choosing a new signal changes only the corresponding firm’s delivery vector. The capacity bound below makes each such unilateral deviation feasible.
For non-dummy firms, set
A dummy has one coordinate and penalty . Give source private coordinate the nonnegative linear coefficient
Other private coefficients are zero. Our parameters ensure . Every market, including each private market, uses , and the cost is
The common affine shift cancels from the payoff. Because the rows in (17) have nonnegative coefficients, the quadratic Hessian is both positive semidefinite and entrywise nonnegative. A shared cost partial at zero is at least . A private partial is at least : there are at most 72 shared coordinates and each row has coefficient and intercept below two. Choosing
makes every cost globally coordinatewise nondecreasing. The dummy partial has the same shared-coordinate bound. The subtraction of gives .
All canonical shared quantities are strictly positive, since . A private coordinate can be zero, for example when its action has probability zero. Decoding uses the sum of the private pair, which is positive. A source uses at most shared markets and two private markets. A relay uses shared and two private markets; a dummy uses one market. Their canonical total quantities are below 145, hence feasible under capacity 1000. A source has at most distinct opponents: an outgoing chain has first-layer opponents, an incoming chain has last-layer opponents, and there are at most twelve chains of each kind.
Lemma 4.4 (Decoding arbitrary approximate profiles). Suppose raw payoffs before penalties and the cancelling shift have absolute value at most on the capacity box, and every partial derivative with respect to an own coordinate or an incident opponent coordinate has absolute value at most . Let , , and . Every actual -equilibrium decodes in polynomial time to a canonical profile with raw canonical regret at most
Proof. Comparison with any canonical zero-penalty strategy gives ; hence . For a non-dummy firm, normalize its private pair to the required sum:
The denominator is positive because its distance from is at most . The private error is at most and each shared coordinate error is at most . A dummy is decoded to , with error at most .
The total own-coordinate error is at most . Each of at most 72 incident markets has at most three opponents, so the relevant opponent-coordinate error is at most . For a canonical unilateral deviation, the actual equilibrium inequality bounds its raw gain by . Replacing the current profile by its canonical decoding changes the current raw payoff by at most , and replacing only the opponents in the deviating payoff changes that payoff by at most . Their sum is less than . All comparisons remain inside the capacity box. For dummies the canonical strategy set is a singleton. □
Regret transfer and completion of the reduction
Lemma 4.4 bounds the gain from changing a canonical delivery vector. To apply the source-regret bound, we must express that gain in the units of the quadratic game. The quadratic terms scale as , and for a fixed chain the Taylor remainder scales as . We choose small enough that the error after division by fits within the relay tolerance.
Proof of Theorem 4.1. First omit the strongly convex perturbation below. Let be any -equilibrium and let be the canonical profile given by Lemma 4.4. We compare the raw gain from any canonical unilateral deviation at with its normalized quadratic gain.
Every canonical displacement of a shared quantity from its baseline has magnitude at most . There are at most four firms in a market. Suppose every third partial derivative of on has magnitude at most . Taylor’s theorem bounds a unilateral payoff-difference remainder in one shared market by at most . Summing at most 72 such remainders gives less than . If for , the two private revenues contribute at most to a unilateral difference. The private revenue has no linear or quadratic term at zero, whereas the private linear bias is exact. The shared own-linear terms cancel by (13); opponent-only terms cancel in a unilateral comparison. Thus the total normalized error is at most
Choose the accuracy parameters to satisfy
By (21) and (22), the first expression in (23) bounds every quadratic unilateral gain at the decoded profile. Thus this profile is a -equilibrium of the quadratic game. Lemma 4.3 gives the claimed source regret for the choice in § 4.6.
Finally add to every cost, where , and set . The old regret of an -equilibrium in the perturbed game is at most . The Hessian is now at least , and global cost monotonicity and the zero-at-origin property are preserved. § 4.6 verifies all parameter inequalities with fixed rational constants. Each directed payoff entry uses a constant number of firms and markets. The cost coefficients are obtained from the rational losses by a bounded number of additions and multiplications per coefficient, and rational output profiles are decoded by normalizing each private pair. The construction and decoding therefore take polynomial time. The source hardness theorem gives PPAD-hardness, and Appendix A gives membership for the stated bounded rational-output relations.
Fixed demands and relay parameters
For each boundary pair , we must fix the demand and all reduction parameters independently of the source game. Start with a demand that is nonincreasing and concave on the entire nonnegative half-line and has enough curvature at output one to permit amplification. Its curvature fixes the relay coefficients. We can then choose the chain length for the required gain and the delivery scale and penalty for the required accuracy. For the three degrees, take , where
Their first derivatives vanish at zero and equal one at one; their values at one are . Their second derivatives are
They are nonnegative on the entire nonnegative half-line, so all three final demands are decreasing and concave there. Use
The relay coefficients are the following exact rationals, written as terminating decimals:
| 1 | 4.99955 | 0.50045 | 4.750675 | 4.750675 |
| 2 | 13.9976 | 2.0012 | 14.0012 | 12 |
| 3 | 22.4946 | 4.5018 | 25.5009 | 19.4985 |
Table 1 (PDF p. 15).
These entries verify [6] by rational comparison. For the spectral gaps, use and , respectively. The first gap is greater than ; the other two exceed three.
To verify the gain bounds, let be the two roots of . They are positive and . Evaluation at shows : after division by the polynomial value is
For the three rows, it suffices to use the rational bounds , , for ; , , for ; and , , for . The determinant recurrence gives
Set . Since , this implies . The weighted inverse bound applied to gives and therefore . Then . The symmetric matrix similar to has smallest eigenvalue greater than , so each inverse diagonal is at most ; these diagonal entries are unchanged by diagonal similarity. Consequently .
With the chain length fixed, choose the remaining constants as follows.
They give , , and (20). Since and , the relay error is less than . The other inequality in (23) follows from the explicit budget
To check the payoff and derivative bounds needed for decoding, observe that on the capacity box all market totals are at most 4000. The coefficient bounds and for give on this range; hence the final prices are positive. They also bound each firm’s raw payoff in absolute value by , and each relevant partial by . The same bounds for follow by summing coefficient magnitudes. For , that sum gives . Finally, a third partial of has magnitude at most on . For , the displayed derivative formulas bound this quantity by for every . For the largest case, , put . The bounds and give ; the quartic and quintic bounds are smaller. These choices satisfy the reduction bounds independently of the size and payoffs of the source game. We can now combine the three boundary families with the polynomial-time regimes.
Proof of Theorem 1.1. Proposition 3.4 proves every P entry of Table 1. Theorem 4.1 proves the three boundary hard entries. Since degree and market participation are upper bounds, each larger class contains the corresponding hard instances. Appendix § 7 supplies membership for the bounded-local-dimension search relations.
A marginal-charge algorithm for total-production costs
Now suppose that a firm pays on its total output. Shifting a unit between two markets leaves its production cost unchanged. To exploit this in Theorem 1.2, give firm a charge per unit sold, the same on all its markets. We can then solve each market separately for the quantities firms would sell if they paid these charges. On the production side, we ask each firm how much it would supply if it received per unit. We seek charges at which each firm’s total sales equal its supply. At such charges the two payments cancel in the firm’s profit.
Start with charges so high that sales are zero. Lower the charge of a firm whose supply exceeds its sales. Its desired production can fall and its sales can rise, displacing sales by its rivals. For the update to make progress, the selected firm’s gap must shrink by more than all the rivals’ gaps grow in total. We establish a bound on this difference, use it to reduce the sum of the gaps geometrically, and stop when the remaining gaps certify the requested profit regret after rounding.
Use the input and preprocessing conventions of § 2. Inverse demand may depend on the firm as well as the market. Write for the largest demand degree and for total capacity.
Normalization of marginal costs. We may assume that every cost is nondecreasing. Indeed, for
replace by and by . Convexity makes the new costs nondecreasing, and every firm’s profit is unchanged. Henceforth use the shifted functions and set
Market and supply responses at fixed charges
Fix the charges and consider a trial total output on one market. For each active firm, equating marginal revenue to its charge determines its delivery at that . We seek the value of at which these deliveries sum to itself. To give this equation a unique solution even for flat demand, and to make each firm’s supply single-valued, choose a positive rational and replace the demands and costs by
Extend beyond by its tangent line at . The extension is continuously differentiable, concave, and has slope at most . It is used only by the auxiliary oracles; it changes no feasible payoff. On feasible profiles the regularization changes each profit by at most . Consequently a regret guarantee transfers back to the original game with loss at most .
For charges , put
Here , and is nondecreasing. Market has an aggregate response defined by
Lemma 5.1 (Scalar market response). Equation (27) has a unique nonnegative root in . The response is continuous in , and
At rational trial points, the scalar equation can be evaluated exactly using rational arithmetic.
Proof. On an interval where ,
The function is zero otherwise. Therefore is continuous and strictly decreasing, with rate at least one. It is nonnegative at zero. Since , all its positive-part terms vanish at . This proves existence and uniqueness. The same strict slope bound gives continuity of the root in the charges; the remaining claims follow directly from the definitions.
The firm’s supply response is
It is single-valued, nondecreasing, and -Lipschitz. It equals zero below , equals above , and is otherwise the unique root of . Thus it too is evaluated by scalar bisection. Define the residual
Our invariant will be . Under this invariant the auxiliary quantities are already feasible, since . At every market response is zero, so the invariant holds initially.
Relative column dominance of the residual map
Suppose we lower only . We need a quantitative comparison between the decrease in firm ’s residual and the increases in its rivals’ residuals. Read these effects down column of the Jacobian of . The diagonal entry measures the response of firm and the other entries measure the responses of its rivals. We first compare them while the active firms stay fixed, then extend the bound across changes in market participation.
Lemma 5.2 (Relative column dominance). Suppose
on every continued demand curve. Put . Along every coordinate segment,
These inequalities are understood on smooth portions and remain valid after integration. Also is -Lipschitz in its own charge.
Proof. Fix one market with positive aggregate and active firms . For , write
Differentiating its scalar equation with respect to an active firm’s charge gives
An inactive charge has derivative zero. In column of the derivative of , the diagonal is , the sum of the absolute off-diagonal entries is , and their difference is . Moreover,
This proves the relative inequality for one market. Summing over markets and adding the nonnegative supply derivative proves (32). Every market contributes at most to the diagonal; supply contributes at most . To justify integration across changes of active set, decrease one charge while fixing the others. At the old aggregate the sum of the firms’ responses in (27) weakly increases, so the new market root is weakly larger. Each rival’s response at its fixed charge is nonincreasing in that root. The selected firm’s quantity, equal to the root minus the sum of rival quantities, is therefore nondecreasing. A rival can exit at most once and the selected firm can enter at most once. The aggregate can pass the tangent-extension boundary at most once, and the supply inverse has only two clipping thresholds. Integrating on these pieces and using continuity at their endpoints gives, for obtained by lowering ,
For global polynomials, has a bound independent of coefficient magnitudes. In fact, we may take
To see this, is a positive nondecreasing polynomial of degree at most on . On , its maximum is . Markov’s polynomial inequality [7] therefore gives . Beyond the slope is constant. Thus the fraction in the update bound depends only on and the demand degree.
Rational evaluation of responses and residuals
Even at rational charges the market root can be irrational. To return rational quantities within capacity, we will round each delivery down. Bisect the market equation and use the upper endpoint of the bracket. Since each firm’s delivery is nonincreasing in total output, . To choose the bracket width, bound the sum of the delivery errors. For every ,
Consequently, on smooth intervals,
Integration proves
If the root is zero then all responses vanish, and the same conclusion holds directly. Algorithm 1 returns rational satisfying
This holds even when the auxiliary response is infeasible. The tangent extension in (25) is therefore used during trial evaluations.
To implement Residual, first compute . For each firm, compute a supply estimate to error at most . The clipping cases in (29) are tested exactly; in the interior, bisect until its width is at most and return its midpoint. Set
Algorithm 1. LowerResponse
Input: rational and .
For each market , perform the following steps. (a) Set and . (b) While , set and evaluate . If , set ; otherwise set . (c) Set for every incident firm .
Return .
Then for every firm. All signs used by both bisections are signs of explicit rational numbers.
Feasibility and contraction of charge updates
Use the residual estimates to choose a firm with a largest gap. We lower its charge until the estimated gap is roughly half its old value (Figure 2). Aiming for half leaves room for estimation error while keeping the true residual positive. The other firms’ residuals can only grow during this update, so every firm stays within capacity. To bound the number of updates, we use Lemma 5.2 to limit how much of the selected decrease those increases can offset.
Figure 2. One coordinate update, with other charges fixed. The curves are schematic. Lowering brings the firm’s supply and allocated quantity closer while keeping their difference nonnegative. The column inequality bounds the resulting increase in other firms’ residuals.
Let be the desired residual bound and put . In Algorithm 2, denotes with coordinate replaced by .
Lemma 5.3 (Feasibility and contraction). Every accepted iterate satisfies . At termination, . If , each nonterminal update satisfies
There are accepted updates, where .
Algorithm 2. Descending marginal charges
Input: regularization , residual target , and output accuracy .
Set and .
Compute and choose .
If , return .
Set , , and .
Set and compute .
If , set and return to Step 2.
If , set ; otherwise set . Return to Step 5.
Proof. The initial invariant was established above. In a nonterminal iteration . The selected old residual is at least , whereas setting its charge to zero gives , since . Thus the target is bracketed. A failed acceptance test has the correct sign: .
At acceptance, the new true residual lies in . It is positive; all other residuals weakly increase when decreases. The entire accepted coordinate segment therefore keeps . Let . Every old residual is at most , so
The integrated column inequality bounds the total increase of all other residuals by . Thus the total residual decreases by at least , proving (37).
The selected-coordinate Lipschitz bound is . Once the inner interval has width at most , its midpoint has true target error at most . Adding the oracle error makes the acceptance test succeed. Hence every inner search terminates.
At stopping, . Initially , and the stopping test must succeed once . The iteration bound follows from the contraction. □
Profit regret after rounding
The stopping test controls a quantity gap. We need a bound on profit from any unilateral deviation, including one that changes total output. At the exact market response the firm already maximizes revenue less its charge against fixed rivals. We can therefore bound its gain by comparing two total outputs at that charge. We then account for the downward rounding of both its own deliveries and its rivals’ deliveries.
Lemma 5.4 (A one-dimensional regret certificate). At any charge vector with , its exact auxiliary response is feasible and has regularized-game regret at most for firm .
Proof. For fixed opponents, the function
is concave. By (28), its gradient at is zero on positive coordinates and nonpositive on zero coordinates. Thus maximizes this function over feasible deviations. Restoring the production cost bounds the gain from any deviation by
Since , nondecreasing cost bounds this difference by .
Lemma 5.5 (Downward rounding). For any feasible , nonincreasing demands bounded above by and nondecreasing total costs satisfy
Proof. Fix a deviation against and put and . This is a feasible deviation against . When , the two deviations face the same aggregate and their revenues differ by at most . When , the comparison deviation is zero and the same upper bound holds. Its cost is no larger. Hence the best-response value against exceeds that against by at most .
For the current payoffs, decreasing quantities raises market prices and lowers production cost. Consequently . Adding the two inequalities proves (38). The argument also permits negative prices.
The returned is componentwise below the feasible response at termination and is therefore feasible. Combining the last two lemmas, (36), and regularization gives
For a target , choose the precisions so that each of the three terms in (39) is at most . Set
Then and . Equation (39) therefore gives regret at most .
Running time
Each charge update calls a bisection that in turn evaluates market and supply responses. We count these nested calls, then bound the bit length of the rational numbers used in them, with the precisions chosen in (40).
Store the current charge vector and the residual estimates in arrays. At a midpoint of the inner search, evaluate the trial residual once and use the stored value for both the acceptance and sign tests. On acceptance, update the selected charge in the stored vector. Thus reading a later charge does not repeat the searches that produced earlier iterates. A market-root bisection with aggregate quantity error at most uses
iterations. A supply bisection to error uses iterations. Since every nonterminal selected estimate exceeds , an inner coordinate search uses
residual evaluations. Lemma 5.3 bounds the accepted updates by
Each oracle iteration evaluates explicitly represented polynomials and their derivatives, so its number of arithmetic operations is polynomial in the total coefficient count.
These operation bounds also give the claimed standard running time. Every updated charge is times a dyadic rational; its denominator exponent increases by at most the number of inner bisections. Market trial points are dyadic multiples of , and supply trial points are dyadic multiples of . All their encodings consequently have polynomial length. Exact polynomial evaluations and sums of polynomially many rational terms preserve this bound. Evaluated values are used for sign tests and output, not as new unconstrained endpoints in the nested bisections. Finally, all quantities in (40) have encoding length polynomial in the input length and .
Proof of Theorem 1.2. Take and choose the parameters in (40). Lemma 5.3 gives a feasible terminal response with . Algorithm 1 returns a feasible rational profile below this response with total rounding error at most . Lemmas 5.4 and 5.5, followed by the regularization bound, give original-game regret at most . The operation and bit bounds above are polynomial in and . Restoring the forced zero deliveries completes the construction. □
Open questions
Which ways of coupling a firm’s deliveries through its cost preserve tractability? A cost of total production permits high-precision approximation at every demand degree. A general convex quadratic cost can already give hardness at degree four when four firms share a market. Between these cases, can one characterize a larger family of allocation costs that still admits efficient equilibrium computation?
Even for costs of total production, the demand representation and the choice of adjustment rule raise distinct questions. Our running-time bound uses a polynomial on the entire feasible interval to control curvature. Can one obtain a comparable bound for succinctly represented piecewise polynomial demands? Our algorithm adjusts auxiliary marginal charges. How quickly can natural adjustment rules converge when firms update their quantities directly?
AI Use Statement. This work involved extensive, author-directed exchanges with OpenAI Astra, including suggestions and critical evaluation of its responses and the proposed ideas and arguments. OpenAI Astra also assisted in writing and revising the manuscript in response to detailed prompts. Gemini Argon assisted with parts of the work.
PPAD membership at fixed degree and local dimension
To place the bounded search problem in PPAD, we need a short rational delivery profile whose regret bound holds against every feasible real deviation. We first look for an approximate fixed point of a projected marginal-profit map and choose its accuracy so that the regret bound survives rounding. We then use the bounds on degree and local dimension to check the output by testing, one firm at a time, whether any deviation gains more than the regret tolerance.
Fix constants . A firm has at most quantity coordinates, demands have degree at most , costs are convex quadratic polynomials, and capacities and coefficients are rational. The shape conditions are input promises. In particular, our hard classes have and .
Let be the total number of quantity coordinates, remove zero-capacity coordinates, and write for the product of capacity simplexes. The case is trivial; assume . Define
Projection is rational and polynomial-time computable: take the positive part if its sum is within capacity; otherwise sort and subtract the unique common threshold whose positive parts sum to capacity. Coefficient bounds give rational with , , and every derivative of bounded by on . Their encoding lengths are polynomial in the input length, and is Lipschitz in the maximum norm with constant . The polynomially computable and polynomially continuous fixed-point framework of Etessami and Yannakakis [10 Proposition 2(2)] therefore computes a weak approximate fixed point through a PPAD reduction.
To obtain actual regret, put . The projection inequality and concavity of own profit give, for every ,
Thus regret is at most . Let
with the least nonnegative integer satisfying the inequality. Request residual at most and round every coordinate down to a multiple of . Feasibility is preserved and the new residual is at most . We restrict outputs to rational profiles of total encoding length at most
This is an explicit polynomial bound.
For such an output , a violation of firm ’s regret condition is the existence of for which . There are at most variables, one for each market accessible to firm . Revenue has degree at most and cost has degree at most two, so the violation polynomial has degree at most . The quadratic term can matter even under constant inverse demand. Fixed-dimensional real-algebraic decision [4] verifies this condition in polynomial time. The shape promises are also decidable in polynomial time in this fixed-degree, fixed-local-dimension class; invalid inputs may be assigned a distinguished trivial output. The relation is consequently total, polynomially balanced, and polynomial-time verifiable, and the weak fixed-point reduction places it in PPAD. The bounded local dimension is used for exact verification of the regret inequality; it is unnecessary for the fixed-point map itself.
References
- [1]M. Abolhassani, M. Bateni, M. Hajiaghayi, H. Mahini, and A. Sawant. Network Cournot competition. In Web and Internet Economics (WINE 2014), volume 8877 of Lecture Notes in Computer Science, pages 15–29. Springer, 2014. doi: 10.1007/978-3-319-13129-0_2. URL https://arxiv.org/abs/1405.1794.
- [2]H. Alsabah, B. Bernard, A. Capponi, G. Iyengar, and J. Sethuraman. Multiregional oligopoly with capacity constraints. Management Science, 67(8):4789–4808, 2021. doi: 10.1287/mnsc.202 0.3728. URL https://carlabernard.ch/beni/downloads/alsabah-bernard-capponi-iyengar-sethuraman-2019.pdf.
- [3]I. Anagnostides, G. Farina, T. Sandholm, and B. H. Zhang. A polynomial-time algorithm for variational inequalities under the Minty condition, 2026. URL https://arxiv.org/abs/2504.03432v4. Version 4, October 2026; first posted in 2025. To appear in FOCS 2026.
- [4]S. Basu, R. Pollack, and M.-F. Roy. On the combinatorial and algebraic complexity of quantifier elimination. Journal of the ACM, 43(6):1002–1045, 1996. doi: 10.1145/235809.235813. URL https://doi.org/10.1145/235809.235813.
- [5]U. Bhaskar and P. R. Lolakapuri. Equilibrium computation in atomic splittable routing games. In 26th Annual European Symposium on Algorithms (ESA 2018), volume 112 of Leibniz International Proceedings in Informatics, pages 58:1–58:14. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2018. doi: 10.4230/LIPIcs.ESA.2018.58. URL https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.58. The arXiv full version has the additional title phrase “with Convex Cost Functions”.DOI
- [6]K. Bimpikis, S. Ehsani, and R. Iiklič. Cournot competition in networked markets. Management Science, 65(6):2467–2481, 2019. doi: 10.1287/mnsc.2018.3061. URL https://web.stanford.edu/~kostasb/papers/networked_markets.pdf.DOI
- [7]P. Borwein and T. Erdélyi. Polynomials and Polynomial Inequalities, volume 161 of Graduate Texts in Mathematics. Springer, 1995. doi: 10.1007/978-1-4612-0793-1. URL https://link.springer.com/book/10.1007/978-1-4612-0793-1.DOI
- [8]R. Caldentey and M. B. Haugh. Technical note—multimarket Cournot equilibria with heterogeneous resource-constrained firms. Operations Research, 72(3):940–956, 2024. doi: 10.1287/opre.2022.0664. URL https://martin-haugh.github.io/files/Research/Cournot-Asymmetric_Final.pdf.DOI
- [9]A. Deligkas, J. Fearnley, A. Hollender, and T. Melissourgos. Pure-Circuit: Tight inapproximability for PPAD. Journal of the ACM, 71(5):31:1–31:48, 2024. doi: 10.1145/3678166. URL https://repository.essex.ac.uk/38497/1/Pure-Circuit_Tight_Inapproximability_for_PPAD.pdf.DOI
- [10]K. Etessami and M. Yannakakis. On the complexity of Nash equilibria and other fixed points. SIAM Journal on Computing, 39(6):2531–2597, 2010. doi: 10.1137/080720826. URL https://homepages.inf.ed.ac.uk/kousha/nash_focs07_full_j_spec_issue_sub.pdf.DOI
- [11]C. Guo, J. Wang, and O. Candogan. Networked markets with production and edge capacity constraints: From competitive equilibria to market entry. In ACM Conference on Economics and Computation (EC 2026), 2026. URL https://ec26.sigecom.org/program/accepted-papers/. Full manuscript circulated as “Networked Cournot Competition under Congestion,” SSRN 5558342.
- [12]T. Harks. Monotonicity, uniqueness and Frank–Wolfe dynamics in atomic splittable congestion games, 2026. URL https://arxiv.org/abs/2607.17684v2. Version 2, October 2026.
- [13]T. Harks and V. Tan-Timmermans. Correction to: Equilibrium computation in resource allocation games. Mathematical Programming, 194:35–40, 2022. doi: 10.1007/s10107-022-01813-8. URL https://link.springer.com/article/10.1007/s10107-022-01813-8.DOI
- [14]T. Harks and V. Timmermans. Computing equilibria in atomic splittable polymatroid congestion games with convex costs, 2018. URL https://arxiv.org/abs/1808.04712.
- [15]T. Harks and V. Timmermans. Equilibrium computation in resource allocation games. Mathematical Programming, 194:1–34, 2022. doi: 10.1007/s10107-020-01604-z. URL https://link.springer.com/article/10.1007/s10107-020-01604-z.DOI
- [16]M. Hota and S. Kapoor. Equilibrium and inefficiency in multi-product Cournot games. In Web and Internet Economics (WINE 2018), volume 11316 of Lecture Notes in Computer Science, pages 203–217. Springer, 2018. doi: 10.1007/978-3-030-04612-5_14. URL https://link.springer.com/chapter/10.1007/978-3-030-04612-5_14.DOI
- [17]M. Klimm and P. Warode. Complexity and parametric computation of equilibria in atomic splittable congestion games via weighted block laplacians. SIAM Journal on Computing, 54(5):1241–1293, 2025. doi: 10.1137/20M1361523. URL https://arxiv.org/abs/1811.08354.
- [18]N. V. Long and A. Soubeyran. Existence and uniqueness of Cournot equilibrium: A contraction mapping approach. Economics Letters, 67(3):345–348, 2000. doi: 10.1016/S0165-1765(00)00211-1. URL https://doi.org/10.1016/S0165-1765(00)00211-1.
- [19]C. Papadimitriou, E.-V. Vlata kis-Gkaragkounis, and M. Zampetakis. The computational complexity of multi-player concave games and Kakutani fixed points. In Proceedings of the 24th ACM Conference on Economics and Computation (EC 2023), page 1045. ACM, 2023. doi: 10.1145/3580507.3597812. URL https://arxiv.org/abs/2207.07557.
- [20]J. B. Rosen. Existence and uniqueness of equilibrium points for concave N-person games. Econometrica, 33(3):520–534, 1965. doi: 10.2307/1911749. URL https://www.jstor.org/stable/1911749.DOI
- [21]A. Tamir. Minimality and complementarity properties associated with Z-functions and M-functions. Mathematical Programming, 7:17–31, 1974. doi: 10.1007/BF01585501. URL https://www.math.tau.ac.il/~atamir/minimality_74.pdf.DOI
