betaFeedback

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 boundh=1h = 1h=2h = 2h=3h = 3h≥4h \ge4
r≤3r \le3PPPP
r=4r = 4PPPHard
r=5r = 5PPHardHard
r≥6r \ge6PHardHardHard

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 rr be a bound on demand degree and hh 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 ε\varepsilon equilibrium is a feasible pure quantity profile at which no firm can improve its profit by more than ε\varepsilon 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(L,b)(L,b) time for additive accuracy 2−b2^{-b}, where LL 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 Si=∑jqijS_i = \sum_j q_{ij}? 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 ii has a convex polynomial cost Ci(Si)C_i(S_i), and each inverse demand is a nonincreasing concave polynomial on its feasible interval. Demands may be firm-specific. For every b≥1b \ge1, a rational feasible additive 2−b2^{-b} pure equilibrium can be computed deterministically in poly⁡(L,b)\operatorname{poly}(\mathcal{L},b) 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 ZZ-function and MM-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 E⊆N×ME \subseteq N \times M, with n=∣N∣n = |N| firms and m=∣M∣m = |M| markets. Write EiE_i for the markets accessible to firm ii and NjN_j for the firms incident to market jj. Firm ii chooses a vector in

Ki={qi∈R≥0Ei:∑j∈Eiqij≤Di},Di∈Q≥0.K_i = \left\{q_i \in\mathbb{R}_{\ge0}^{E_i} : \sum_{j \in E_i} q_{ij} \le D_i\right\}, \qquad D_i \in\mathbb{Q}_{\ge0}.

Let K=∏iKiK = \prod_i K_i, d=∣E∣d = |E|, Qj=∑i∈NjqijQ_j = \sum_{i \in N_j} q_{ij}, and Si=∑j∈EiqijS_i = \sum_{j \in E_i} q_{ij}. The common-demand model has profit

πi(q)=∑j∈Eiqijpj(Qj)−Ci(qi).(1)\pi_i(q) = \sum_{j \in E_i} q_{ij}p_j(Q_j) - C_i(q_i). \tag*{(1)}

Here pjp_j is nonincreasing and concave on [0,Bj][0, B_j], where Bj=∑i∈NjDiB_j = \sum_{i \in N_j} D_i, and CiC_i is convex on KiK_i. The polynomial-time algorithm for total-production costs also permits firm-specific demands pijp_{ij} and uses costs Ci(Si)C_i(S_i).

Each profit is concave in its own strategy: a market contribution has own second derivative 2pj′(Qj)+qijpj′′(Qj)≤02p'_j(Q_j) + q_{ij}p''_j(Q_j) \le0, 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

Reg⁡i(q)=max⁡zi∈Ki(πi(zi,q−i)−πi(q)).(2)\operatorname{Reg}_i(q) = \max_{z_i \in K_i} \left(\pi_i(z_i,q_{-i}) - \pi_i(q)\right). \tag*{(2)}

An additive ε\varepsilon equilibrium has Reg⁡i(q)≤ε\operatorname{Reg}_{i}(q) \le\varepsilon 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 L\mathcal{L} includes the graph and these descriptions. Accuracy is specified as 2−b2^{-b}, 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 qiq_i, since its marginal revenue is p(Q)+qip′(Q)p(Q) + q_i p'(Q). We need a bound that holds for every division of total output among the firms.

Write t=−p′t=-p'. For Q>0Q>0 with t(Q)>0t(Q)>0, measure the change in slope by Qt′(Q)/t(Q)Qt'(Q)/t(Q). We start by comparing the endpoint value of t′t' with its average on [0,Q][0,Q], since t(Q)=t(0)+∫0Qt′(u) dut(Q)=t(0)+\int_0^Q t'(u)\,\mathrm{d}u and t(0)≥0t(0)\ge0. For a quartic demand, for instance, t′t' 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 2−b2^{-b}.

Lemma 3.1 (Endpoint bounds). Let ff be a polynomial nonnegative on [0,1][0,1]. If its degree is at most one, two, or three, respectively, then

f(1)≤c∫01f(x) dx,c=2, 4, 6,f(1) \le c \int_0^1 f(x)\,\mathrm{d}x,\qquad c=2,\ 4,\ 6,

respectively. Each constant is sharp.

Proof. For the three degree bounds, respectively, exact integration gives

2∫01f(x) dx=f(0)+f(1),4∫01f(x) dx=3f(1/3)+f(1),6∫01f(x) dx=f(0)+4f(1/2)+f(1).\begin{aligned} 2\int_0^1 f(x)\,\mathrm{d}x &= f(0)+f(1),\\ 4\int_0^1 f(x)\,\mathrm{d}x &= 3f(1/3)+f(1),\\ 6\int_0^1 f(x)\,\mathrm{d}x &= f(0)+4f(1/2)+f(1). \end{aligned}

Each identity follows by checking the monomials up to its stated degree. All terms on the right are nonnegative, giving the desired bounds on f(1)f(1). Equality is attained by xx, (3x−1)2(3x-1)^2, and x(2x−1)2x(2x-1)^2, respectively. □\square

Corollary 3.2 (Curvature of low-degree demands). Let pp be nonincreasing and concave on [0,B][0,B]. If its degree is at most three, four, or five, then, wherever Q>0Q>0 and −p′(Q)>0-p'(Q)>0,

0≤Q(−p′′(Q))−p′(Q)≤2, 4, 6,0 \le\frac{Q(-p''(Q))}{-p'(Q)} \le2,\ 4,\ 6,

respectively.

Proof. Put t=−p′≥0t=-p'\ge0 and f=t′≥0f=t'\ge0. If ff is zero the result is immediate. Otherwise t(Q)=t(0)+∫0Qf(x) dx≥∫0Qf(x) dxt(Q)=t(0)+\int_0^Q f(x)\,\mathrm{d}x\ge\int_0^Q f(x)\,\mathrm{d}x. Applying Lemma 3.1 to f(Qx)f(Qx) bounds Qf(Q)/t(Q)Qf(Q)/t(Q) by the corresponding constant.

To apply the curvature bound, consider a simultaneous change dd in the firms’ deliveries. If JJ is the Jacobian of negative marginal revenues, monotonicity requires dTJd≥0d^{\mathsf T}Jd\ge0 along feasible directions. Since dTJd=dT(J+JT)d/2d^{\mathsf T}Jd=d^{\mathsf T}(J+J^{\mathsf T})d/2, it suffices to check the symmetric part. Write wi=qi/Qw_i=q_i/Q for firm ii’s share and κ=Qt′(Q)/t(Q)\kappa=Qt'(Q)/t(Q). Dividing the symmetric part by t(Q)>0t(Q)>0 gives the matrix Sh(w,κ)S_h(w,\kappa) below.

Lemma 3.3 (Market-size criterion). For h≥2h\ge2 and κ≥0\kappa\ge0, the matrix

Sh(w,κ)=I+11T+κ2(w1T+1wT)S_h(w,\kappa)=I+11^{\mathsf T}+\frac{\kappa}{2}(w1^{\mathsf T}+1w^{\mathsf T})

is positive semidefinite for every probability vector w∈R≥0hw\in\mathbb{R}_{\ge0}^h if and only if κ≤2(h+1)/(h−1)\kappa\le2(h+1)/(h-1).

Proof. The matrix depends affinely on ww, and the positive semidefinite cone is convex. It suffices to check the simplex vertices. By symmetry take w=e1w=e_1. 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 e1e_1 and (0,1,…,1)/h−1(0,1,\ldots,1)/\sqrt{h-1}. On this subspace the matrix is

(2+κ(1+κ/2)h−1(1+κ/2)h−1h).\begin{pmatrix} 2+\kappa& (1+\kappa/2)\sqrt{h-1}\\ (1+\kappa/2)\sqrt{h-1} & h \end{pmatrix}.

The diagonal entries are positive, and the determinant equals

h−14(κ+2)(2(h+1)h−1−κ).\frac{h-1}{4}(\kappa+2)\left(\frac{2(h+1)}{h-1}-\kappa\right).

This proves both directions.

We now compare the curvature bounds 2,4,62,4,6 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 PP entries of Table 1 admit a rational additive 2−b2^{-b} equilibrium in poly⁡(L,b)\operatorname{poly}(L,b) time, with no restriction on local strategy dimension.

Proof. Let G(q)=(−∇qiπi(q))iG(q)=(-\nabla_{q_i}\pi_i(q))_i. Fix a market with demand pp, total output QQ, and hh firms, and put t=−p′t=-p'. The negative marginal revenue of firm ii is −p(Q)+qit(Q)-p(Q)+q_i t(Q). Its derivative with respect to qℓq_\ell is (1+1{i=ℓ})t(Q)+qit′(Q)(1+1_{\{i=\ell\}})t(Q)+q_i t'(Q). Thus, for Q>0Q>0 and t(Q)>0t(Q)>0, the symmetric part of the market Jacobian is

t(Q)Sh(w,Qt′(Q)t(Q)),wi=qi/Q.t(Q)S_h\left(w,\frac{Qt'(Q)}{t(Q)}\right),\qquad w_i=q_i/Q.

The cutoff in Lemma 3.3 is 2+4/(h−1)2 + 4/(h - 1). It equals six for two firms, four for three firms, and exceeds two for every finite h≥2h \ge2. 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 10/310/3, 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 2t(Q)+Qt′(Q)2t(Q) + Qt'(Q) for every degree. At Q=0Q = 0, all deliveries vanish and the unscaled matrix is t(0)(I+11T)t(0)(I + 11^{\mathsf{T}}). If Q>0Q > 0 and t(Q)=0t(Q) = 0, the nonnegative, nondecreasing polynomial tt vanishes on [0,Q][0, Q], so its derivative there is also zero. Convex costs add positive semidefinite Hessians. Integrating along line segments in KK proves that GG 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 qq such that

G(q)T(z−q)≥−2−b(z∈K).(3)G(q)^{\mathsf{T}}(z - q) \ge-2^{-b} \qquad(z \in K). \tag*{(3)}

The following facts verify the computational assumptions. The map GG 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 KK 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 UU on its absolute value, reducing the bracket width to 2−b/(1+U)2^{-b}/(1 + U) bounds the profit gap by 2−b2^{-b}. We may therefore suppose d≥2d \ge2 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 qij=Dixijq_{ij} = D_i x_{ij}. If firm ii has did_i coordinates, translate its unit-capacity simplex by the vector with all entries 1/(di+1)1/(d_i + 1). Scale the product by d2(d+1)d^2(d + 1). The transformed domain contains the Euclidean unit ball and lies in a ball of radius d2(d+1)d^2(d + 1). Indeed, before scaling its inner radius is at least 1/((d+1)d)1/((d + 1)\sqrt{d}) and its outer radius is at most d\sqrt{d}. Writing the inverse coordinate change as q=Ay+b0q = Ay + b_0, use G~(y)=ATG(Ay+b0)\widetilde{G}(y) = A^{\mathsf{T}}G(Ay + b_0). 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 zz differ from qq only in firm ii’s coordinates. Concavity of that firm’s profit gives

πi(zi,q−i)−πi(q)≤∇qiπi(q)T(zi−qi)≤2−b.\pi_i(z_i, q_{-i}) - \pi_i(q) \le\nabla_{q_i}\pi_i(q)^{\mathsf{T}}(z_i - q_i) \le2^{-b}.

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 1/201/20-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 1/201/20 gives the corresponding firm a unilateral deviation worth more than the Cournot regret tolerance.

Consider a payoff entry that contributes −Lxy-Lxy to the receiver when the receiver and sender play the corresponding actions with probabilities xx and yy. Holding yy fixed, an increase of Δx\Delta x costs the receiver Ly ΔxLy\,\Delta x, regardless of its initial xx. 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 yy while keeping the receiver’s own payoff curvature and the influence in the opposite direction bounded. Each shared market has one high-output and ss low-output firms. For s=1,2,3s=1,2,3 we use degrees 6, 5, 4, respectively.

Theorem 4.1 (Fixed-demand hardness). There is a universal rational ε0>0\varepsilon_0>0 with the following property. For each (r,h)∈{(6,2),(5,3),(4,4)}(r,h)\in\{(6,2),(5,3),(4,4)\} there is one fixed rational polynomial prp_r, nonincreasing and concave on R≥0\mathbb{R}_{\geq0}, for which computing an additive ε0\varepsilon_0 pure Nash equilibrium is PPAD-hard. Every market uses prp_r, 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 hh firms per market and at most 24(h−1)+224(h-1)+2 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 [0,1][0,1]. Computing a 1/201/20-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 [0,1][0,1]. The losses must preserve the payoff difference between the player’s two actions against any fixed profile of its neighbors. Write xiax_{ia} for the probability of action aa. We seek directed loss matrices Lij∈[0,1]2×2L^{ij}\in[0,1]^{2\times2} giving payoffs of the form

uiloss(x)=−∑j∈N(i)∑a,b∈{0,1}Labijxiaxjb.(4)u_i^{\mathrm{loss}}(x)=-\sum_{j\in N(i)}\sum_{a,b\in\{0,1\}}L_{ab}^{ij}x_{ia}x_{jb}. \tag*{(4)}

To choose the entries, write player ii’s action-one minus action-zero payoff difference as ci+∑jdijxj1∈[−1,1]c_i+\sum_j d_{ij}x_{j1}\in[-1,1]. For each nonisolated ii, choose cijc_{ij} summing to cic_i in the intervals

−1−min⁡{dij,0}≤cij≤1−max⁡{dij,0}.-1-\min\{d_{ij},0\}\leq c_{ij}\leq1-\max\{d_{ij},0\}.

These intervals are nonempty because ∣dij∣≤2|d_{ij}|\leq2. Their summed endpoints contain cic_i, by minimizing and maximizing the payoff difference over the neighbor cube. A greedy interval allocation therefore finds rational cijc_{ij} in polynomial time. Set Dij(b)=cij+dijbD_{ij}(b)=c_{ij}+d_{ij}b, L0bij=(Dij(b))+L_{0b}^{ij}=(D_{ij}(b))_+, and L1bij=(−Dij(b))+L_{1b}^{ij}=(-D_{ij}(b))_+. Then L0bij−L1bij=Dij(b)L_{0b}^{ij}-L_{1b}^{ij}=D_{ij}(b). 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 JJ be a fixed polynomial satisfying J(0)=J′(0)=0J(0)=J^{\prime}(0)=0, J′(1)=1J^{\prime}(1)=1, 0<J(1)<10<J(1)<1, and J′′(1)=κ>0J^{\prime\prime}(1)=\kappa>0. Use the inverse demand p(Q)=A−J(Q)p(Q)=A-J(Q). We will choose the price level AA when we specify the costs. Choose 0<β<1/(s+1)0<\beta<1/(s+1) and 0<ϑ<20<\vartheta<2, and baseline quantities

βR=1−sβ,βL=β,\beta_R=1-s\beta,\qquad\beta_L=\beta,

so that one high-output firm and ss low-output firms supply total quantity one. A high firm’s signal changes its quantity by −δϑz-\delta\vartheta z, and a low firm’s signal changes its quantity by δz\delta z. Define

a=1+κβR,b=1+κβ,R0=a+1,S0=b+1,d0=R0ϑ2+sS0,α=R0ϑ2+s,γ=sb,D=α+sγ,A0=saϑ,B0=sbϑ.(5)\begin{aligned} a&=1+\kappa\beta_R, & b&=1+\kappa\beta, & R_0&=a+1, & S_0&=b+1,\\ d_0&=R_0\vartheta^2+sS_0, & \alpha&=R_0\vartheta^2+s, & \gamma&=sb,\\ D&=\alpha+s\gamma, & A_0&=sa\vartheta, & B_0&=sb\vartheta. \tag*{(5)} \end{aligned}

At the limiting baseline β=0\beta=0, the expression A0+B0−D=(κ+2)(sϑ−ϑ2)−s−s2A_0+B_0-D=(\kappa+2)(s\vartheta-\vartheta^2)-s-s^2 is maximized at ϑ=s/2\vartheta=s/2. Substitution gives

A0+B0−D=s4(sκ−2s−4).A_0+B_0-D=\frac{s}{4}(s\kappa-2s-4).

Thus at this limiting choice A0+B0>DA_0+B_0>D holds exactly when κ>2+4/s\kappa>2+4/s. Since a shared market has h=s+1h=s+1 firms, the right-hand side is the monotonicity cutoff from Lemma 3.3. If also A0>B0A_0>B_0 and D>2A0B0D>2\sqrt{A_0B_0}, this inequality puts A0A_0 above the larger root of x2−Dx+A0B0x^2-Dx+A_0B_0, producing a growing forward transfer along the chain. Our positive baseline β\beta preserves this strict gap. The constants will satisfy

d0<20,α>3,D−2A0B0>3/2,(A0/2+2B0)/D<5/6,A0<23,B0<5,A0B0<102,B0/A0<1/3,a/b<10,R0ϑ2<14,sS0<7.(6)\begin{aligned} d_0&<20,\quad\alpha>3,\quad D-2\sqrt{A_0B_0}>3/2,\quad(A_0/2+2B_0)/D<5/6,\\ A_0&<23,\quad B_0<5,\quad A_0B_0<102,\quad B_0/A_0<1/3,\quad a/b<10,\\ R_0\vartheta^2&<14,\quad sS_0<7. \tag*{(6)} \end{aligned}

For an integer k≥2k\ge2, let TkT_k be the tridiagonal matrix with diagonal DD, subdiagonal −A0-A_0, and superdiagonal −B0-B_0. With θj=det⁡Tj\theta_j=\det T_j and θ0=1\theta_0=1, put

K=A0k+1θk,K−=B0k+1θk,E=A0B0θk−1θk.(7)K=\frac{A_0^{k+1}}{\theta_k},\qquad K_-=\frac{B_0^{k+1}}{\theta_k},\qquad E=\frac{A_0B_0\theta_{k-1}}{\theta_k}. \tag*{(7)}

We choose a fixed chain length kk in § 4.6 to satisfy

241<K<2k+8,K−<1,0<E<100.(8)2^{41}<K<2^{k+8},\qquad K_-<1,\qquad0<E<100. \tag*{(8)}

Thus KK is a large forward gain, K−K_- a small reverse gain, and EE a bounded feedback coefficient. There are ss scalar relay players in each of kk layers. Their strategy interval is [−H,H][-H,H], where H=2k+4H=2^{k+4}. Let M\mathcal{M} have diagonal blocks αIs+γ11T\alpha I_s+\gamma\mathbf{1}\mathbf{1}^{\mathsf{T}}, subdiagonal blocks −aϑ11T-a\vartheta\mathbf{1}\mathbf{1}^{\mathsf{T}}, and superdiagonal blocks −bϑ11T-b\vartheta\mathbf{1}\mathbf{1}^{\mathsf{T}}. Each own diagonal entry is d0d_0. For endpoint signals u,v∈[−1/2,1/2]u,v\in[-1/2,1/2] and a loss L∈[0,1]L\in[0,1], the vector of derivatives of the relays’ payoffs with respect to their own signals is f−Mzf-\mathcal{M}z, where ff is uniform within the first and last layers. The first-layer entry is (A0/s)u(A_0/s)u, the last-layer entry is −B0Lv-B_0Lv, and all others are zero.

Lemma 4.2 (Stable amplification). The unique unconstrained relay solution is uniform in each layer, zℓh∗=yℓ∗z_{\ell h}^{*}=y_{\ell}^{*}, lies in the interior of [−H,H]sk[-H,H]^{sk}, and satisfies

Tky∗=(A0/s)ue1−B0Lvek,yk∗=KsA0u−EA0Lv,y1∗=EsB0u−KB0Lv.(9)T_k y^{*}=(A_0/s)u e_1-B_0Lv e_k, \qquad y_k^{*}=\frac{K}{sA_0}u-\frac{E}{A_0}Lv, \qquad y_1^{*}=\frac{E}{sB_0}u-\frac{K}{B_0}Lv. \tag*{(9)}

If each relay has regret at most ξ\xi, then

∥z−z∗∥∞≤60k 10kξ.(10)\lVert z-z^{*}\rVert_{\infty}\le\sqrt{60k\,10^k\xi}. \tag*{(10)}

The parameters will make this bound less than 1/10001/1000.

Proof. In the weighted maximum norm ∥y∥w=max⁡ℓ∣yℓ∣/2ℓ\lVert y\rVert_w=\max_{\ell}|y_{\ell}|/2^{\ell}, the nonnegative matrix I−Tk/DI-T_k/D has norm below 5/65/6. Hence TkT_k is invertible, its inverse is nonnegative, and ∥Tk−1∥w<6/D\lVert T_k^{-1}\rVert_w<6/D. The forcing in the first line of Eq. (9) has weighted norm at most max⁡{A0/(4s),B0/2k+1}\max\{A_0/(4s),B_0/2^{k+1}\}. The resulting solution obeys ∣yℓ∗∣<4⋅2ℓ≤H/4|y_{\ell}^{*}|<4\cdot2^{\ell}\le H/4. Tridiagonal cofactor expansion gives

(Tk−1)k1=A0k−1/θk,(Tk−1)1k=B0k−1/θk,(Tk−1)11=(Tk−1)kk=θk−1/θk,(T_k^{-1})_{k1}=A_0^{k-1}/\theta_k,\qquad (T_k^{-1})_{1k}=B_0^{k-1}/\theta_k,\qquad (T_k^{-1})_{11}=(T_k^{-1})_{kk}=\theta_{k-1}/\theta_k,

which proves the boundary identities.

For stability, use layer weights ωℓ=(b/a)ℓ−1\omega_{\ell}=(b/a)^{\ell-1} and W=diag⁡(ω1Is,…,ωkIs)W=\operatorname{diag}(\omega_1 I_s,\ldots,\omega_k I_s). The layer weights balance each pair of opposite coefficients, so WMWM is symmetric. To bound its quadratic form relative to the weighted norm, put S=W1/2MW−1/2S=W^{1/2}MW^{-1/2}. This symmetric matrix has eigenvalue α\alpha on each within-layer difference subspace. On the uniform-layer subspace it has diagonal DD and off-diagonal −A0B0-\sqrt{A_0B_0}. Its least eigenvalue there is at least D−2A0B0>3/2D-2\sqrt{A_0B_0}>3/2. Applying these bounds to W1/2zW^{1/2}z gives

zTWMz≥32∥z∥W2,min⁡ℓωℓ>10−k.z^{\mathsf T}WMz\ge\frac{3}{2}\lVert z\rVert_W^2,\qquad\min_{\ell}\omega_{\ell}>10^{-k}.

This also proves uniqueness of the full linear solution and its uniformity within layers.

Put Δ=z−z∗\Delta=z-z^{*}. Relay ii may unilaterally move one tenth of the way toward zi∗z_i^{*}. Its improvement is

110Δi(MΔ)i−d0200Δi2.\frac{1}{10}\Delta_i(M\Delta)_i-\frac{d_0}{200}\Delta_i^2.

The move is feasible even if ziz_i is on the boundary. Multiply these individual regret inequalities by WiW_i and sum. Since s≤3s\le3,

3kξ≥∑iWiξ≥(320−20200)∥Δ∥W2=120∥Δ∥W2.3k\xi\ge\sum_i W_i\xi\ge\left(\frac{3}{20}-\frac{20}{200}\right)\lVert\Delta\rVert_W^2=\frac{1}{20}\lVert\Delta\rVert_W^2.

The lower bound on the weights proves (10). In particular, this argument neither assumes interiority of the approximate profile nor permits a coordinated deviation. □\square

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 s+1s+1 firms, the next relay responds to the combined deliveries of ss predecessors. All these markets use the same demand curve. To encode a particular loss LL, we vary the receiver’s delivery with LL and add a linear cost. We can then isolate the multiple of LL in the receiver’s marginal payoff and bound the other terms across its incident chains.

For each directed interaction i←ji \leftarrow j and action pair (a,b)(a,b), make a fresh relay chain and set

L=Labij,u=xjb−1/2,v=xia−1/2.L = L^{ij}_{ab}, \qquad u = x_{jb} - 1/2, \qquad v = x_{ia} - 1/2.

For every relay hh of layer ℓ≥2\ell\ge2, create one market whose high firm is that relay and whose ss low firms are the previous layer. Their canonical quantities are

qR=βR−δϑzℓh,qL,t=β+δzℓ−1,t.(11)q_R = \beta_R - \delta\vartheta z_{\ell h}, \qquad q_{L,t} = \beta+ \delta z_{\ell-1,t}. \tag*{(11)}

At the first layer, one low firm is source firm jj, supplying β+δu\beta+ \delta u; the other s−1s - 1 low firms are fresh dummies, each with canonical quantity β\beta. This creates ss first-layer markets and never places a firm in two roles in one market. At the last boundary, make ss separate markets whose high firm is source firm ii and whose low firms are all last-layer relays, with

qR=βR+δϑLv,qL,t=β+δzkt.(12)q_R = \beta_R + \delta\vartheta L v, \qquad q_{L,t} = \beta+ \delta z_{kt}. \tag*{(12)}

Every relay is high in one market and low in ss markets. Figure 1 shows the incidence between layers.

The relay construction, shown schematically

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 βe\beta_e for a firm’s baseline delivery in a shared market. For raw demand −J-J, subtract the linear cost ℓeqe\ell_e q_e with

ℓe=−J(1)−βe.(13)\ell_e = -J(1) - \beta_e. \tag*{(13)}

Since J′(1)=1J'(1) = 1, this cancels the own first derivative of −qeJ(Q)-q_e J(Q) at the baseline. The own second derivative is −2−κβe-2 - \kappa\beta_e and each cross derivative of own marginal revenue is −1−κβe-1 - \kappa\beta_e. Consider relay hh in an interior layer ℓ\ell. It is high in one market, with signal coefficient −ϑ-\vartheta, and low in ss markets, with coefficient 11, in units of δ\delta. Its normalized quadratic payoff has derivative

−d0zℓh−sb∑t≠hzℓt+aϑ∑tzℓ−1,t+bϑ∑tzℓ+1,t.-d_0 z_{\ell h} - sb \sum_{t \ne h} z_{\ell t} + a\vartheta\sum_t z_{\ell-1,t} + b\vartheta\sum_t z_{\ell+1,t}.

Indeed, its own coefficient is −R0ϑ2−sS0=−d0-R_0\vartheta^2 - sS_0 = -d_0. Each other same-layer relay shares its ss outgoing markets. At the first boundary the preceding-layer sum is uu, and at the last boundary the next-layer sum is −sLv-sLv. Since d0=α+γd_0 = \alpha+ \gamma and γ=sb\gamma= sb, these derivatives are the entries of −Mz+f-Mz + f in Lemma 4.2.

Let zˉℓ=s−1∑hzℓh\bar{z}_{\ell}=s^{-1}\sum_h z_{\ell h}. Add a linear source cost (K/2)Lxia(K/2)Lx_{ia} in the normalized quadratic game. For one chain the source receiver’s quadratic contribution is

−sR0ϑ2L22v2−sA0Lzˉk−(K/2)Lxia,-\frac{sR_0\vartheta^2L^2}{2}v^2-sA_0L\bar{z}_k-(K/2)Lx_{ia},

and the source sender’s is

−sS02u2+B0uzˉ1.-\frac{sS_0}{2}u^2+B_0u\bar{z}_1.

The normalized quadratic game sums these endpoint payoffs over incident chains. Each source firm chooses the pair (xi0,xi1)(x_{i0},x_{i1}) in the probability simplex, and each relay chooses its own coordinate in [−H,H][-H,H].

Lemma 4.3 (Source regret in the quadratic game). Assume (6) and (8). Let 0<ξ≤10<\xi\leq1 satisfy 60k 10kξ<1/1000\sqrt{60k\,10^k\xi}<1/1000. At any ξ\xi-equilibrium of the normalized quadratic game, the source profile satisfies

Reg⁡isource(x)≤ξ+5000K<1/20for every source player i.(14)\operatorname{Reg}^{\mathrm{source}}_i(x)\leq\frac{\xi+5000}{K}<1/20\qquad\text{for every source player }i. \tag*{(14)}

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,

−KLxjb+s(E−R0ϑ2)L2v−sA0L(zˉk−yk∗),-KLx_{jb}+s(E-R_0\vartheta^2)L^2v-sA_0L(\bar{z}_k-y_k^*),
(E/s−sS0)u−K−Lv+B0(zˉ1−y1∗).(15)(E/s-sS_0)u-K-Lv+B_0(\bar{z}_1-y_1^*). \tag*{(15)}

For one incoming chain, the difference from the target derivative −KLxjb-KLx_{jb} is at most 3(100+14)/2+3⋅23/1000<1723(100+14)/2+3\cdot23/1000<172. For one outgoing chain the absolute derivative is at most (100+7)/2+1/2+5/1000<55(100+7)/2+1/2+5/1000<55. Here we used ∣u∣,∣v∣≤1/2|u|,|v|\leq1/2, 0≤L≤10\leq L\leq1, 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 KK times the derivative of (4) by at most 6(172+55)<20006(172+55)<2000.

With all relays held fixed, a source firm’s own quadratic Hessian is diagonal and has entries of absolute value below 6sR0ϑ2+6sS0<3006sR_0\vartheta^2+6sS_0<300. 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 ℓ1\ell_1 distance at most two and squared ℓ2\ell_2 distance at most two. Hence the gradient error costs at most 2000⋅22000\cdot2 in the gain from this move. The firm’s own quadratic term costs at most 12⋅300⋅2\frac{1}{2}\cdot300\cdot2 more. Taking g=Reg⁡source(x)g=\operatorname{Reg}^{\mathrm{source}}(x), this feasible unilateral move gains at least Kg−4300Kg-4300 and at most ξ\xi. Equation (14) follows from K>241K>2^{41}. □

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 ria=δxiar_{ia}=\delta x_{ia}, and those of a relay are ri0=δ(zi+H)r_{i0}=\delta(z_i+H) and ri1=δ(H−zi)r_{i1}=\delta(H-z_i). The required signal sums are Disig=δxiaD_i^{\mathrm{sig}}=\delta x_{ia} and 2H2H, respectively. For such a firm each shared canonical quantity has the form βe+δz\beta_e+\delta z, where z=xia−1/2z=x_{ia}-1/2 for a source action and z=ziz=z_i for a relay. Put T=1/2T=1/2 or T=HT=H, respectively. The firm’s two private coordinates are δ(T+z)\delta(T+z) and δ(T−z)\delta(T-z), up to ordering. For d≥0d \ge0 use r=δ(T−z)r=\delta(T-z), and for d<0d<0 use r=δ(T+z)r=\delta(T+z). In both cases βe+δdz=(βe+δ∣d∣T)−∣d∣r\beta e+\delta dz=(\beta e+\delta|d|T)-|d|r. Since ∣d∣≤max⁡{1,ϑ}<2|d|\le\max\{1,\vartheta\}<2 and 2δH<β/22\delta H<\beta/2, the resulting rows satisfy

qie=hie−cieri,a(i,e),0<cie<2,0<hie<2.(16)q_{ie}=h_{ie}-c_{ie}r_{i,a(i,e)},\qquad0<c_{ie}<2,\quad0<h_{ie}<2. \tag*{(16)}

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 {β}\{\beta\}. 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

Φi=((ri0+ri1)/δ−Disig)2+∑e(qie+cieri,a(i,e)−hie)2.(17)\Phi_i=\left((r_{i0}+r_{i1})/\delta-D_i^{\mathrm{sig}}\right)^2+\sum_e\left(q_{ie}+c_{ie}r_{i,a(i,e)}-h_{ie}\right)^2. \tag*{(17)}

A dummy has one coordinate and penalty (qi−β)2(q_i-\beta)^2. Give source private coordinate aa the nonnegative linear coefficient

via=δK2∑j,bLabij.(18)v_{ia}=\frac{\delta K}{2}\sum_{j,b}L_{ab}^{ij}. \tag*{(18)}

Other private coefficients are zero. Our parameters ensure via≤3v_{ia}\le3. Every market, including each private market, uses p(Q)=A−J(Q)p(Q)=A-J(Q), and the cost is

Ci(qi)=A∑eqie+∑e sharedℓeqie+∑aviaria+M(Φi(qi)−Φi(0)).(19)C_i(q_i)=A\sum_e q_{ie}+\sum_{e\ \mathrm{shared}}\ell_e q_{ie}+\sum_a v_{ia}r_{ia}+M\left(\Phi_i(q_i)-\Phi_i(0)\right). \tag*{(19)}

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−2−4MA-2-4M. A private partial is at least A−4MH/δ−576MA-4MH/\delta-576M: there are at most 72 shared coordinates and each row has coefficient and intercept below two. Choosing

A>2+4MH/δ+576M(20)A>2+4MH/\delta+576M \tag*{(20)}

makes every cost globally coordinatewise nondecreasing. The dummy partial has the same shared-coordinate bound. The subtraction of MΦi(0)M\Phi_i(0) gives Ci(0)=0C_i(0)=0.

All canonical shared quantities are strictly positive, since 2δH<β/22\delta H<\beta/2. 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 24s24s shared markets and two private markets. A relay uses s+1s+1 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 12s(s+1)12s(s+1) distinct opponents: an outgoing chain has s2s^2 first-layer opponents, an incoming chain has ss 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 RR on the capacity box, and every partial derivative with respect to an own coordinate or an incident opponent coordinate has absolute value at most L0L_0. Let M=3R/ρ2M=3R/\rho^2, 0<ρ<10<\rho<1, and 0<ε∗<R0<\varepsilon_*<R. Every actual ε∗\varepsilon_*-equilibrium decodes in polynomial time to a canonical profile with raw canonical regret at most

ε∗+1600L0ρ.(21)\varepsilon_*+1600L_0\rho. \tag*{(21)}

Proof. Comparison with any canonical zero-penalty strategy gives MΦi≤2R+ϵ∗<3RM\Phi_i \le2R+\epsilon_*<3R; hence Φi≤ρ2\Phi_i\le\rho^2. For a non-dummy firm, normalize its private pair to the required sum:

r^ia=δDisigriari0+ri1.\widehat r_{ia}=\frac{\delta D_i^{\mathrm{sig}}r_{ia}}{r_{i0}+r_{i1}}.

The denominator is positive because its distance from δDisig\delta D_i^{\mathrm{sig}} is at most δρ<δDisig\delta\rho<\delta D_i^{\mathrm{sig}}. The private ℓ1\ell_1 error is at most δρ\delta\rho and each shared coordinate error is at most ρ+2δρ≤3ρ\rho+2\delta\rho\le3\rho. A dummy is decoded to β\beta, with error at most ρ\rho.

The total own-coordinate error is at most 217ρ217\rho. Each of at most 72 incident markets has at most three opponents, so the relevant opponent-coordinate error is at most 648ρ648\rho. For a canonical unilateral deviation, the actual equilibrium inequality bounds its raw gain by ϵ∗−MΦi(qi)≤ϵ∗\epsilon_*-M\Phi_i(q_i)\le\epsilon_*. Replacing the current profile by its canonical decoding changes the current raw payoff by at most (217+648)L0ρ(217+648)L_0\rho, and replacing only the opponents in the deviating payoff changes that payoff by at most 648L0ρ648L_0\rho. Their sum is less than 1600L0ρ1600L_0\rho. 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 δ2\delta^2, and for a fixed chain the Taylor remainder scales as δ3\delta^3. We choose δ\delta small enough that the error after division by δ2\delta^2 fits within the relay tolerance.

Proof of Theorem 4.1. First omit the strongly convex perturbation below. Let qq be any ϵ∗\epsilon_*-equilibrium and let q^\widehat q be the canonical profile given by Lemma 4.4. We compare the raw gain from any canonical unilateral deviation at q^\widehat q with its normalized quadratic gain.

Every canonical displacement of a shared quantity from its baseline has magnitude at most 2δH2\delta H. There are at most four firms in a market. Suppose every third partial derivative of qi[−J(∑jqj)]q_i[-J(\sum_j q_j)] on [0,2]4[0,2]^4 has magnitude at most 2222^{22}. Taylor’s theorem bounds a unilateral payoff-difference remainder in one shared market by at most 2⋅222(8δH)32\cdot2^{22}(8\delta H)^3. Summing at most 72 such remainders gives less than 239δ3H32^{39}\delta^3H^3. If 0≤J(t)≤32t20\le J(t)\le32t^2 for 0≤t≤10\le t\le1, the two private revenues contribute at most 210δ3H32^{10}\delta^3H^3 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

240δH3.(22)2^{40}\delta H^3. \tag*{(22)}

Choose the accuracy parameters to satisfy

ϵ∗+1600L0ρδ2+240δH3<ξ,60k 10kξ<1/1000.(23)\frac{\epsilon_*+1600L_0\rho}{\delta^2}+2^{40}\delta H^3<\xi, \qquad \sqrt{60k\,10^k\xi}<1/1000. \tag*{(23)}

By (21) and (22), the first expression in (23) bounds every quadratic unilateral gain at the decoded profile. Thus this profile is a ξ\xi-equilibrium of the quadratic game. Lemma 4.3 gives the claimed source regret for the choice ξ≤1\xi\le1 in § 4.6.

Finally add λ∥qi∥22\lambda\lVert q_i\rVert_2^2 to every cost, where λ=ϵ∗/(4⋅10002)\lambda=\epsilon_*/(4\cdot1000^2), and set ϵ0=ϵ∗/2\epsilon_0=\epsilon_*/2. The old regret of an ϵ0\epsilon_0-equilibrium in the perturbed game is at most ϵ0+λ10002=3ϵ∗/4<ϵ∗\epsilon_0+\lambda1000^2=3\epsilon_*/4<\epsilon_*. The Hessian is now at least 2λI2\lambda I, 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 (r,h)(r,h), 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 pr(Q)=A−Jr(Q)p_r(Q)=A-J_r(Q), where

J4(Q)=34Q4−Q3+12Q2,J5(Q)=65Q5−2Q4+Q3,J6(Q)=103Q6−8Q5+7Q4−83Q3+12Q2.\begin{aligned} J_4(Q)&=\frac{3}{4}Q^4-Q^3+\frac{1}{2}Q^2,\\ J_5(Q)&=\frac{6}{5}Q^5-2Q^4+Q^3,\\ J_6(Q)&=\frac{10}{3}Q^6-8Q^5+7Q^4-\frac{8}{3}Q^3+\frac{1}{2}Q^2. \end{aligned}

Their first derivatives vanish at zero and equal one at one; their values at one are Jr(1)=1/rJ_r(1)=1/r. Their second derivatives are

J4′′(Q)=(3Q−1)2,J5′′(Q)=6Q(2Q−1)2,J6′′(Q)=(10Q2−8Q+1)2.J_4''(Q)=(3Q-1)^2,\qquad J_5''(Q)=6Q(2Q-1)^2,\qquad J_6''(Q)=(10Q^2-8Q+1)^2.

They are nonnegative on the entire nonnegative half-line, so all three final demands are decreasing and concave there. Use

(s,r,κ)∈{(1,6,9),(2,5,6),(3,4,4)},β=1/10000,ϑ=s/2.(s,r,\kappa)\in\{(1,6,9),(2,5,6),(3,4,4)\},\qquad\beta=1/10000,\qquad\vartheta=s/2.

The relay coefficients are the following exact rationals, written as terminating decimals:

ssA0A_0B0B_0DDd0d_0
14.999550.500454.7506754.750675
213.99762.001214.001212
322.49464.501825.500919.4985

Table 1 (PDF p. 15).

These entries verify [6] by rational comparison. For the spectral gaps, use A0B0<2.51,29,102A_0B_0<2.51,29,102 and D>4.75,14,25D>4.75,14,25, respectively. The first gap is greater than 4.75−2(1.6)>3/24.75-2(1.6)>3/2; the other two exceed three.

To verify the gain bounds, let λ±\lambda_{\pm} be the two roots of x2−Dx+A0B0x^2-Dx+A_0B_0. They are positive and λ+−λ−>1\lambda_+-\lambda_->1. Evaluation at (49/50)A0>D/2(49/50)A_0>D/2 shows λ+<(49/50)A0\lambda_+<(49/50)A_0: after division by A0A_0 the polynomial value is

(2401/2500)A0−(49/50)D+B0>0.(2401/2500)A_0-(49/50)D+B_0>0.

For the three rows, it suffices to use the rational bounds A0>4.99A_0>4.99, D<4.76D<4.76, B0>0.5B_0>0.5 for s=1s=1; A0>13.9A_0>13.9, D<14.1D<14.1, B0>2B_0>2 for s=2s=2; and A0>22.4A_0>22.4, D<25.6D<25.6, B0>4.5B_0>4.5 for s=3s=3. The determinant recurrence gives

θk=λ+k+1−λ−k+1λ+−λ−,K>(50/49)k+1.\theta_k=\frac{\lambda_+^{k+1}-\lambda_-^{k+1}}{\lambda_+-\lambda_-},\qquad K>(50/49)^{k+1}.

Set k=2048k=2048. Since (50/49)49>2(50/49)^{49}>2, this implies K>241K>2^{41}. The weighted inverse bound applied to Tky=A0e1T_k y=A_0e_1 gives yk<6⋅2ky_k<6\cdot2^k and therefore K=A0yk<2k+8K=A_0y_k<2^{k+8}. Then K−=K(B0/A0)k+1<1K_-=K(B_0/A_0)^{k+1}<1. The symmetric matrix similar to TkT_k has smallest eigenvalue greater than 3/23/2, so each inverse diagonal is at most 2/32/3; these diagonal entries are unchanged by diagonal similarity. Consequently E<(2/3) 102<100E < (2/3)\,10^2 < 100.

With the chain length fixed, choose the remaining constants as follows.

H=2k+4,ξ=2−30k−100,δ=ξ250H3,R=L0=2100,ρ=δ2ξ10000L0,M=3Rρ2,ε∗=δ2ξ8,V=290,A=V+10+8MHδ+1000M.(24)\begin{aligned} H &= 2^{k+4}, \qquad\xi= 2^{-30k-100}, \qquad\delta= \frac{\xi}{2^{50}H^3}, \qquad R = L_0 = 2^{100},\\ \rho&= \frac{\delta^2\xi}{10000L_0}, \qquad M = \frac{3R}{\rho^2}, \qquad\varepsilon_* = \frac{\delta^2\xi}{8},\\ V &= 2^{90}, \qquad A = V + 10 + \frac{8MH}{\delta} + 1000M. \tag*{(24)} \end{aligned}

They give 2δH<β/22\delta H < \beta/2, δK<1\delta K < 1, and (20). Since 60k<2k60k < 2^k and 10k<24k10^k < 2^{4k}, the relay error is less than 23kξ<1/10002^{3k}\sqrt{\xi} < 1/1000. The other inequality in (23) follows from the explicit budget

18ξ+160010000ξ+11024ξ<ξ.\frac{1}{8}\xi+ \frac{1600}{10000}\xi+ \frac{1}{1024}\xi< \xi.

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 Jr(Q)≤32Q6J_r(Q) \le32Q^6 and ∣Jr′(Q)∣≤100Q5|J'_r(Q)| \le100Q^5 for Q≥1Q \ge1 give Jr(Q)<VJ_r(Q) < V on this range; hence the final prices are positive. They also bound each firm’s raw payoff in absolute value by 1000(32⋅40006+5)<21001000(32\cdot4000^6+5) < 2^{100}, and each relevant partial by 32⋅40006+100000⋅40005+5<210032\cdot4000^6+100000\cdot4000^5+5 < 2^{100}. The same bounds for Q<1Q<1 follow by summing coefficient magnitudes. For 0≤t≤10\le t\le1, that sum gives 0≤Jr(t)≤32t20\le J_r(t)\le32t^2. Finally, a third partial of qi[−Jr(Q)]q_i[-J_r(Q)] has magnitude at most 3∣Jr′′(Q)∣+2∣Jr′′′(Q)∣3|J''_r(Q)|+2|J'''_r(Q)| on [0,2]4[0,2]^4. For 0≤Q≤80\le Q\le8, the displayed derivative formulas bound this quantity by 2222^{22} for every rr. For the largest case, r=6r=6, put h(Q)=10Q2−8Q+1h(Q)=10Q^2-8Q+1. The bounds ∣h(Q)∣<210|h(Q)|<2^{10} and ∣h′(Q)∣<28|h'(Q)|<2^8 give 3∣J6′′∣+2∣J6′′′∣<3⋅220+2⋅219=2223|J_6''|+2|J_6'''|<3\cdot2^{20}+2\cdot2^{19}=2^{22}; 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 Ci(Si)C_i(S_i) on its total output. Shifting a unit between two markets leaves its production cost unchanged. To exploit this in Theorem 1.2, give firm ii a charge λi\lambda_i 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 λi\lambda_i 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 pijp_{ij} may depend on the firm as well as the market. Write rr for the largest demand degree and B=∑iDiB=\sum_i D_i for total capacity.

Normalization of marginal costs. We may assume that every cost is nondecreasing. Indeed, for

c=max⁡{0,−min⁡iCi′(0)},c=\max\{0,-\min_i C_i'(0)\},

replace pij(Q)p_{ij}(Q) by pij(Q)+cp_{ij}(Q)+c and Ci(s)C_i(s) by Ci(s)+csC_i(s)+cs. Convexity makes the new costs nondecreasing, and every firm’s profit is unchanged. Henceforth use the shifted functions and set

P=max⁡{1,max⁡(i,j)∈Epij(0)}.P=\max\{1,\max_{(i,j)\in E}p_{ij}(0)\}.

Market and supply responses at fixed charges

Fix the charges and consider a trial total output QQ on one market. For each active firm, equating marginal revenue to its charge determines its delivery at that QQ. We seek the value of QQ at which these deliveries sum to QQ 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 τ\tau and replace the demands and costs by

pˉij(Q)=pij(Q)−τQ,Cˉi(s)=Ci(s)+τs2.(25)\bar{p}_{ij}(Q)=p_{ij}(Q)-\tau Q,\qquad\bar{C}_i(s)=C_i(s)+\tau s^2. \tag*{(25)}

Extend pˉij\bar{p}_{ij} beyond BjB_j by its tangent line at BjB_j. The extension is continuously differentiable, concave, and has slope at most −τ-\tau. It is used only by the auxiliary oracles; it changes no feasible payoff. On feasible profiles the regularization changes each profit by at most 2τB22\tau B^2. Consequently a regret guarantee transfers back to the original game with loss at most 4τB24\tau B^2.

For charges λ∈[0,P]n\lambda\in[0,P]^n, put

tij(Q)=−pˉij′(Q),aij(Q,λi)=(pˉij(Q)−λi)+tij(Q).(26)t_{ij}(Q)=-\bar{p}_{ij}'(Q),\qquad a_{ij}(Q,\lambda_i)=\frac{(\bar{p}_{ij}(Q)-\lambda_i)_+}{t_{ij}(Q)}. \tag*{(26)}

Here tij≥τt_{ij}\ge\tau, and tijt_{ij} is nondecreasing. Market jj has an aggregate response Qj(λ)Q_j(\lambda) defined by

∑i:(i,j)∈Eaij(Qj,λi)=Qj,qij(λ)=aij(Qj,λi).(27)\sum_{i:(i,j)\in E}a_{ij}(Q_j,\lambda_i)=Q_j,\qquad q_{ij}(\lambda)=a_{ij}(Q_j,\lambda_i). \tag*{(27)}

Lemma 5.1 (Scalar market response). Equation (27) has a unique nonnegative root in [0,P/τ][0,P/\tau]. The response is continuous in λ\lambda, and

pˉij(Qj)+qijpˉij′(Qj)=λi(qij>0),pˉij(Qj)≤λi(qij=0).(28)\bar{p}_{ij}(Q_j)+q_{ij}\bar{p}_{ij}'(Q_j)=\lambda_i\quad(q_{ij}>0),\qquad\bar{p}_{ij}(Q_j)\le\lambda_i\quad(q_{ij}=0). \tag*{(28)}

At rational trial points, the scalar equation can be evaluated exactly using rational arithmetic.

Proof. On an interval where aij>0a_{ij}>0,

∂aij∂Q=−1−aijtij′tij≤−1.\frac{\partial a_{ij}}{\partial Q}=-1-a_{ij}\frac{t_{ij}'}{t_{ij}}\le-1.

The function is zero otherwise. Therefore Ψj(Q)=∑iaij(Q,λi)−Q\Psi_j(Q)=\sum_i a_{ij}(Q,\lambda_i)-Q is continuous and strictly decreasing, with rate at least one. It is nonnegative at zero. Since pˉij(Q)≤P−τQ\bar{p}_{ij}(Q)\le P-\tau Q, all its positive-part terms vanish at P/τP/\tau. 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

σi(λi)=argmax⁡0≤s≤Di{λis−Cˉi(s)}.(29)\sigma_i(\lambda_i)=\underset{0\le s\le D_i}{\operatorname{argmax}}\{\lambda_i s-\bar{C}_i(s)\}. \tag*{(29)}

It is single-valued, nondecreasing, and 1/(2τ)1/(2\tau)-Lipschitz. It equals zero below Cˉi′(0)\bar{C}'_i(0), equals DiD_i above Cˉi′(Di)\bar{C}'_i(D_i), and is otherwise the unique root of Cˉi′(s)=λi\bar{C}'_i(s)=\lambda_i. Thus it too is evaluated by scalar bisection. Define the residual

Fi(λ)=σi(λi)−Si(λ),Si(λ)=∑jqij(λ).(30)F_i(\lambda)=\sigma_i(\lambda_i)-S_i(\lambda),\qquad S_i(\lambda)=\sum_j q_{ij}(\lambda). \tag*{(30)}

Our invariant will be F≥0F\ge0. Under this invariant the auxiliary quantities are already feasible, since Si≤σi≤DiS_i\le\sigma_i\le D_i. At λ=P1\lambda=P\mathbf{1} every market response is zero, so the invariant holds initially.

Relative column dominance of the residual map

Suppose we lower only λi\lambda_i. We need a quantitative comparison between the decrease in firm ii’s residual and the increases in its rivals’ residuals. Read these effects down column ii of the Jacobian of FF. The diagonal entry measures the response of firm ii 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

Qtij′(Q)tij(Q)≤K(Q>0)(31)\frac{Qt'_{ij}(Q)}{t_{ij}(Q)}\le K\qquad(Q>0) \tag*{(31)}

on every continued demand curve. Put γ=1/(n+K)\gamma=1/(n+K). Along every coordinate segment,

∂iFi≥0,∂iFk≤0 (k≠i),∑k≠i(−∂iFk)≤(1−γ)∂iFi.(32)\partial_iF_i\ge0,\qquad\partial_iF_k\le0\ (k\ne i),\qquad\sum_{k\ne i}(-\partial_iF_k)\le(1-\gamma)\partial_iF_i. \tag*{(32)}

These inequalities are understood on smooth portions and remain valid after integration. Also FiF_i is (m+1)/τ(m+1)/\tau-Lipschitz in its own charge.

Proof. Fix one market with positive aggregate QQ and active firms AA. For i∈Ai\in A, write

hi=1/ti(Q),wi=1+qiti′(Q)/ti(Q),Z=1+∑i∈Awi.h_i=1/t_i(Q),\qquad w_i=1+q_i t'_i(Q)/t_i(Q),\qquad Z=1+\sum_{i\in A}w_i.

Differentiating its scalar equation with respect to an active firm’s charge λℓ\lambda_\ell gives

∂λℓQ=−hℓ/Z,∂λℓqi=−hi1{i=ℓ}+wihℓ/Z.(33)\partial_{\lambda_\ell}Q=-h_\ell/Z,\qquad\partial_{\lambda_\ell}q_i=-h_i\mathbf{1}_{\{i=\ell\}}+w_i h_\ell/Z. \tag*{(33)}

An inactive charge has derivative zero. In column ℓ\ell of the derivative of −q-q, the diagonal is hℓ(Z−wℓ)/Zh_\ell(Z-w_\ell)/Z, the sum of the absolute off-diagonal entries is hℓ(Z−1−wℓ)/Zh_\ell(Z-1-w_\ell)/Z, and their difference is hℓ/Zh_\ell/Z. Moreover,

Z−wℓ=∣A∣+∑i∈A∖{ℓ}Qti′(Q)ti(Q)qiQ≤n+K.Z-w_\ell=|A|+\sum_{i\in A\setminus\{\ell\}}\frac{Qt'_i(Q)}{t_i(Q)}\frac{q_i}{Q}\le n+K.

This proves the relative inequality for one market. Summing over markets and adding the nonnegative supply derivative proves (32). Every market contributes at most 1/τ1/\tau to the diagonal; supply contributes at most 1/(2τ)1/(2\tau). 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 λ′\lambda' obtained by lowering λi\lambda_i,

0≤∑k≠i(Fk(λ′)−Fk(λ))≤(1−γ)(Fi(λ)−Fi(λ′)).0 \le\sum_{k \ne i}\left(F_k(\lambda')-F_k(\lambda)\right) \le(1-\gamma)\left(F_i(\lambda)-F_i(\lambda')\right).

For global polynomials, KK has a bound independent of coefficient magnitudes. In fact, we may take

K=2max⁡{r−1,0}2.(34)K = 2\max\{r-1,0\}^2. \tag*{(34)}

To see this, g=−pˉijg=-\bar{p}_{ij} is a positive nondecreasing polynomial of degree at most d=max⁡{r−1,0}d=\max\{r-1,0\} on [0,Bj][0,B_j]. On [0,Q][0,Q], its maximum is g(Q)g(Q). Markov’s polynomial inequality [7] therefore gives Qg′(Q)≤2d2g(Q)Qg'(Q)\le2d^2g(Q). Beyond BjB_j the slope is constant. Thus the fraction γ\gamma in the update bound depends only on nn 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 U≥Qj(λ)U\ge Q_j(\lambda) of the bracket. Since each firm’s delivery is nonincreasing in total output, aij(U,λi)≤qij(λ)a_{ij}(U,\lambda_i)\le q_{ij}(\lambda). To choose the bracket width, bound the sum of the delivery errors. For every Q≥Qj(λ)Q\ge Q_j(\lambda),

∑iaij(Q,λi)≤Qj(λ)≤Q.\sum_i a_{ij}(Q,\lambda_i)\le Q_j(\lambda)\le Q.

Consequently, on smooth intervals,

−ddQ∑iaij(Q,λi)≤n+K∑iaij(Q,λi)Q≤n+K.-\frac{d}{dQ}\sum_i a_{ij}(Q,\lambda_i)\le n+K\frac{\sum_i a_{ij}(Q,\lambda_i)}{Q}\le n+K.

Integration proves

∑i(qij(λ)−aij(U,λi))≤(n+K)(U−Qj(λ)).(35)\sum_i\left(q_{ij}(\lambda)-a_{ij}(U,\lambda_i)\right)\le(n+K)\left(U-Q_j(\lambda)\right). \tag*{(35)}

If the root is zero then all responses vanish, and the same conclusion holds directly. Algorithm 1 returns rational yy satisfying

0≤y≤q(λ),∥q(λ)−y∥1≤δ.(36)0\le y\le q(\lambda),\qquad\lVert q(\lambda)-y\rVert_1\le\delta. \tag*{(36)}

This holds even when the auxiliary response is infeasible. The tangent extension in (25) is therefore used during trial evaluations.

To implement Residual(λ,ν)(\lambda,\nu), first compute y=LowerResponse⁡(λ,ν/2)y=\operatorname{LowerResponse}(\lambda,\nu/2). For each firm, compute a supply estimate σ~i\tilde{\sigma}_i to error at most ν/2\nu/2. The clipping cases in (29) are tested exactly; in the interior, bisect [0,Di][0,D_i] until its width is at most ν\nu and return its midpoint. Set

vi=σ~i−∑jyij.v_i=\tilde{\sigma}_i-\sum_j y_{ij}.

Algorithm 1. LowerResponse(λ,δ)(\lambda,\delta)

Input: rational λ∈[0,P]n\lambda\in[0,P]^n and δ>0\delta> 0.

  1. For each market jj, perform the following steps. (a) Set L=0L=0 and U=P/τU=P/\tau. (b) While U−L>δ/[m(n+K)]U-L>\delta/[m(n+K)], set x=(L+U)/2x=(L+U)/2 and evaluate z=∑i:(i,j)∈Eaij(x,λi)−xz=\sum_{i:(i,j)\in E}a_{ij}(x,\lambda_i)-x. If z>0z>0, set L=xL=x; otherwise set U=xU=x. (c) Set yij=aij(U,λi)y_{ij}=a_{ij}(U,\lambda_i) for every incident firm ii.

  2. Return yy.

Then ∣vi−Fi(λ)∣≤ν|v_i-F_i(\lambda)|\leq\nu 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 λi\lambda_i 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 a>0a>0 be the desired residual bound and put ν=a/33\nu=a/33. In Algorithm 2, λ(i←x)\lambda^{(i\leftarrow x)} denotes λ\lambda with coordinate ii replaced by xx.

Lemma 5.3 (Feasibility and contraction). Every accepted iterate satisfies F≥0F\geq0. At termination, max⁡iFi≤a\max_i F_i\leq a. If R=∑iFiR=\sum_i F_i, each nonterminal update satisfies

Rnew≤(1−13n(n+K))R.(37)R_{\mathrm{new}}\leq\left(1-\frac{1}{3n(n+K)}\right)R. \tag*{(37)}

There are O(n(n+K)(1+log⁡+(B/a)))O(n(n+K)(1+\log_+(B/a))) accepted updates, where log⁡+x=max⁡{0,log⁡x}\log_+x=\max\{0,\log x\}.

Algorithm 2. Descending marginal charges

Input: regularization τ>0\tau> 0, residual target a>0a > 0, and output accuracy η>0\eta> 0.

  1. Set λ=P1\lambda= P\mathbf{1} and ν=a/33\nu= a/33.

  2. Compute v=Residual⁡(λ,ν)v = \operatorname{Residual}(\lambda,\nu) and choose i∈arg⁡max⁡kvki \in\arg\max_k v_k.

  3. If vi≤32νv_i \le32\nu, return LowerResponse⁡(λ,η)\operatorname{LowerResponse}(\lambda,\eta).

  4. Set v∗=viv_* = v_i, L=0L = 0, and U=λiU = \lambda_i.

  5. Set x=(L+U)/2x = (L+U)/2 and compute w=Residual⁡(λ(i←x),ν)iw = \operatorname{Residual}(\lambda^{(i\leftarrow x)},\nu)_i.

  6. If ∣w−v∗/2∣≤v∗/16\lvert w-v_*/2\rvert\le v_*/16, set λi=x\lambda_i=x and return to Step 2.

  7. If w>v∗/2w>v_*/2, set U=xU=x; otherwise set L=xL=x. Return to Step 5.

Proof. The initial invariant was established above. In a nonterminal iteration v∗>32νv_* > 32\nu. The selected old residual is at least v∗−ν>31v∗/32v_*-\nu> 31v_*/32, whereas setting its charge to zero gives Fi≤0F_i \le0, since σi(0)=0\sigma_i(0)=0. Thus the target v∗/2v_*/2 is bracketed. A failed acceptance test has the correct sign: v∗/16>νv_*/16>\nu.

At acceptance, the new true residual lies in [13v∗/32,19v∗/32]⊆[3v∗/8,5v∗/8][13v_*/32,19v_*/32] \subseteq[3v_*/8,5v_*/8]. It is positive; all other residuals weakly increase when λi\lambda_i decreases. The entire accepted coordinate segment therefore keeps F≥0F \ge0. Let Δ=Fiold−Fi\Delta=F_i^{\mathrm{old}}-F_i. Every old residual is at most v∗+ν<33v∗/32v_*+\nu<33v_*/32, so

Δ≥11v∗32≥R3n.\Delta\ge\frac{11v_*}{32} \ge\frac{R}{3n}.

The integrated column inequality bounds the total increase of all other residuals by (1−γ)Δ(1-\gamma)\Delta. Thus the total residual decreases by at least γΔ\gamma\Delta, proving (37).

The selected-coordinate Lipschitz bound is M=(m+1)/τ\mathcal{M}=(m+1)/\tau. Once the inner interval has width at most v∗/(32M)v_*/(32\mathcal{M}), its midpoint has true target error at most v∗/64v_*/64. Adding the oracle error ν<v∗/32\nu<v_*/32 makes the acceptance test succeed. Hence every inner search terminates.

At stopping, Fk≤vi+ν≤33ν=aF_k\le v_i+\nu\le33\nu=a. Initially R≤∑iDi=BR\le\sum_i D_i=B, and the stopping test must succeed once R≤31νR\le31\nu. 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 F≥0F\ge0, its exact auxiliary response is feasible and has regularized-game regret at most PFiPF_i for firm ii.

Proof. For fixed opponents, the function

zi↦∑jzijpˉij(Q−i,j+zij)−λi∑jzijz_i \mapsto\sum_j z_{ij}\bar{p}_{ij}(Q_{-i,j}+z_{ij})-\lambda_i\sum_j z_{ij}

is concave. By (28), its gradient at qiq_i is zero on positive coordinates and nonpositive on zero coordinates. Thus qiq_i maximizes this function over feasible deviations. Restoring the production cost bounds the gain from any deviation by

[λiσi−Cˉi(σi)]−[λiSi−Cˉi(Si)].[\lambda_i\sigma_i-\bar{C}_i(\sigma_i)]-[\lambda_iS_i-\bar{C}_i(S_i)].

Since Si≤σiS_i\le\sigma_i, nondecreasing cost bounds this difference by λi(σi−Si)≤PFi\lambda_i(\sigma_i-S_i)\le PF_i.

Lemma 5.5 (Downward rounding). For any feasible 0≤y≤q0\le y\le q, nonincreasing demands bounded above by PP and nondecreasing total costs satisfy

Reg⁡i(y)≤Reg⁡i(q)+P∥q−y∥1.(38)\operatorname{Reg}_i(y)\le\operatorname{Reg}_i(q)+P\lVert q-y\rVert_1. \tag*{(38)}

Proof. Fix a deviation ziz_i against y−iy_{-i} and put δj=Q−i,j(q)−Q−i,j(y)≥0\delta_j=Q_{-i,j}(q)-Q_{-i,j}(y)\ge0 and zij′=(zij−δj)+z'_{ij}=(z_{ij}-\delta_j)_+. This is a feasible deviation against q−iq_{-i}. When zij≥δjz_{ij}\ge\delta_j, the two deviations face the same aggregate and their revenues differ by at most PδjP\delta_j. When zij<δjz_{ij}<\delta_j, the comparison deviation is zero and the same upper bound holds. Its cost is no larger. Hence the best-response value against y−iy_{-i} exceeds that against q−iq_{-i} by at most P∑jδjP\sum_j\delta_j.

For the current payoffs, decreasing quantities raises market prices and lowers production cost. Consequently πi(q)−πi(y)≤P∑j(qij−yij)\pi_i(q)-\pi_i(y)\le P\sum_j(q_{ij}-y_{ij}). Adding the two inequalities proves (38). The argument also permits negative prices.

The returned yy is componentwise below the feasible response at termination and is therefore feasible. Combining the last two lemmas, (36), and regularization gives

Reg⁡i(y)≤Pa+Pη+4τB2.(39)\operatorname{Reg}_i(y)\le Pa+P\eta+4\tau B^2. \tag*{(39)}

For a target 0<ε≤10<\varepsilon\le1, choose the precisions so that each of the three terms in (39) is at most ε/4\varepsilon/4. Set

τ=ε16(1+B)2,a=η=ε4P,ν=a33,K=2max⁡{r−1,0}2.(40)\tau=\frac{\varepsilon}{16(1+B)^2},\qquad a=\eta=\frac{\varepsilon}{4P},\qquad\nu=\frac{a}{33},\qquad K=2\max\{r-1,0\}^2. \tag*{(40)}

Then 4τB2≤ε/44\tau B^2\le\varepsilon/4 and P(a+η)=ε/2P(a+\eta)=\varepsilon/2. Equation (39) therefore gives regret at most 3ε/4<ε3\varepsilon/4<\varepsilon.

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 δ\delta uses

O(1+log⁡+m(n+K)Pτδ)O\left(1+\log_+\frac{m(n+K)P}{\tau\delta}\right)

iterations. A supply bisection to error δ\delta uses O(1+log⁡+(B/δ))O(1+\log_+(B/\delta)) iterations. Since every nonterminal selected estimate exceeds 32ν32\nu, an inner coordinate search uses

O(1+log⁡+P(m+1)τa)O\left(1+\log_+\frac{P(m+1)}{\tau a}\right)

residual evaluations. Lemma 5.3 bounds the accepted updates by

O(n(n+r2)(1+log⁡+PBε)).(41)O\left(n(n+r^2)\left(1+\log_+\frac{PB}{\varepsilon}\right)\right). \tag*{(41)}

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 PP times a dyadic rational; its denominator exponent increases by at most the number of inner bisections. Market trial points are dyadic multiples of P/τP/\tau, and supply trial points are dyadic multiples of DiD_i. 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 bb.

Proof of Theorem 1.2. Take ε=2−b\varepsilon=2^{-b} and choose the parameters in (40). Lemma 5.3 gives a feasible terminal response with max⁡iFi≤a\max_i F_i \le a. Algorithm 1 returns a feasible rational profile below this response with total rounding error at most η\eta. Lemmas 5.4 and 5.5, followed by the regularization bound, give original-game regret at most P(a+η)+4τB2≤3ε/4P(a+\eta)+4\tau B^2 \le3\varepsilon/4. The operation and bit bounds above are polynomial in LL and bb. 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 k0,r0k_0, r_0. A firm has at most k0k_0 quantity coordinates, demands have degree at most r0r_0, costs are convex quadratic polynomials, and capacities and coefficients are rational. The shape conditions are input promises. In particular, our hard classes have k0≤74k_0 \le74 and r0≤6r_0 \le6.

Let dd be the total number of quantity coordinates, remove zero-capacity coordinates, and write X=∏iXiX = \prod_i X_i for the product of capacity simplexes. The case d=0d = 0 is trivial; assume d≥1d \ge1. Define

gi(q)=∇qiπi(q),Fi(q)=proj⁡Xi(qi+gi(q)).g_i(q) = \nabla_{q_i} \pi_i(q), \qquad F_i(q) = \operatorname{proj}_{X_i}(q_i + g_i(q)).

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 D,G,H≥1D,G,H \ge1 with D≥max⁡iDiD \ge\max_i D_i, ∣gij∣≤G|g_{ij}| \le G, and every derivative of gg bounded by HH on XX. Their encoding lengths are polynomial in the input length, and FF is Lipschitz in the maximum norm with constant Λ=d(1+dH)\Lambda= d(1+dH). 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 ri=Fi(q)−qir_i = F_i(q)-q_i. The projection inequality and concavity of own profit give, for every zi∈Xiz_i \in X_i,

πi(zi,q−i)−πi(q)≤gi(q)T(zi−qi)≤∥ri∥2(2Di+∥gi(q)∥2).\pi_i(z_i,q_{-i})-\pi_i(q) \le g_i(q)^{\mathsf{T}}(z_i-q_i) \le\lVert r_i\rVert_2(2D_i+\lVert g_i(q)\rVert_2).

Thus regret is at most d(2D+dG)∥F(q)−q∥∞d(2D+dG)\lVert F(q)-q\rVert_\infty. Let

η=min⁡{1,ε}d(2D+dG),2−t≤η2(1+Λ),\eta= \frac{\min\{1,\varepsilon\}}{d(2D+dG)}, \qquad2^{-t} \le\frac{\eta}{2(1+\Lambda)},

with tt the least nonnegative integer satisfying the inequality. Request residual at most η/2\eta/2 and round every coordinate down to a multiple of 2−t2^{-t}. Feasibility is preserved and the new residual is at most η\eta. We restrict outputs to rational profiles of total encoding length at most

d(2t+⌈log⁡2(1+D)⌉+10).d(2t+\lceil\log_2(1+D)\rceil+10).

This is an explicit polynomial bound.

For such an output qq, a violation of firm ii’s regret condition is the existence of zi∈Xiz_i \in X_i for which πi(zi,q−i)−πi(q)>ε\pi_i(z_i,q_{-i})-\pi_i(q)>\varepsilon. There are at most k0k_0 variables, one for each market accessible to firm ii. Revenue has degree at most r0+1r_0+1 and cost has degree at most two, so the violation polynomial has degree at most max⁡{r0+1,2}\max\{r_0+1,2\}. 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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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

Paper details

vlnc:W_w8djmhbw
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents