Computing Market Equilibria

Motivation: an algorithmic theory of markets

Thinkers have pondered markets and money through the ages; the credit for initiating formal mathematical modelling is generally given to the nineteenth-century economist Léon Walras (1874). The overwhelming importance given to this study within mathematical economics has a lot to do with the fact that Western economies are capitalistic — essentially, our most critical decision-making is relegated to pricing mechanisms. Prices determine the relative worth of goods and services, ensure the economy is efficient in that goods reach the entities producing what is most in demand, and ensure stable operation.

ImportantThe central tenet, and the celebrated theorem

A central tenet of pricing mechanisms is that prices be such that demand equals supply — the economy should operate at equilibrium. Unsurprisingly, the most celebrated theorem of general equilibrium theory, the Arrow–Debreu theorem (1954), establishes precisely the existence of such prices under a very general model. The First Welfare Theorem, showing Pareto optimality of equilibrium allocations, provides the social justification.

Historically: Walras (1874) posed the system; Wald (1936) gave the first existence proof under severe restrictions; Arrow and Debreu proved existence under much milder assumptions. The proofs are fixed-point arguments, via Brouwer or Kakutani depending on the setting.

WarningThe shortcoming

Although general equilibrium theory enjoyed the status of crown jewel within mathematical economics, it suffers from a serious defect: other than a few isolated results — some of them real gems, such as Eisenberg–Gale (1959) and Scarf (1973) — it was essentially a nonalgorithmic theory.

From the 1960s, Scarf and coauthors exploited the fixed-point connection computationally, using path-following techniques: decompose the price simplex into many small regions and construct a path that terminates near a fixed point. The fixpoint theorems guarantee termination, but the worst-case running time is exponential.

IntuitionWhy this matters now

With the emergence of new markets on the Internet — already an important part of today’s economy and projected to grow — and massive computational power available to run them centrally or distributedly, the need for an algorithmic theory of markets is apparent. Such algorithms are also a tool for understanding the repercussions of technological advances, new goods, or tax changes on existing prices, production and consumption.

A good beginning has been made, but given that markets were studied for over a century within mathematical economics, it is safe to say we have only scratched the surface.

NoteThe two approaches, and how this note is organized

Two lines of attack have emerged, both covered here:

Approach	Technique	Model treated
Combinatorial	primal-dual schema	Fisher, linear utilities
Combinatorial	auction-based	Arrow–Debreu, linear utilities
Convex programming	Eisenberg’s program	Fisher, homogeneous utilities
Convex programming	discrete tâtonnement	exchange economies satisfying WGS
Convex programming	convex feasibility	linear and CES exchange, production

The primal-dual algorithm is notable for extending the primal-dual schema from its usual setting of solving linear programs to exactly solving a nonlinear convex program.

The two models

DefinitionFisher’s model (linear case)

A set $B$ of buyers and a set $A$ of divisible goods, $|A| = n$ , $|B| = n'$ . Buyer $i$ has money $e_i$ ; good $j$ is available in amount $b_j$ . Utilities are linear: if $u_{ij}$ is the utility $i$ derives per unit of good $j$ , then on receiving $x_{ij}$ units of each good her happiness is $\sum_j u_{ij}x_{ij}$ .

Prices $p_1,\ldots,p_n$ are market clearing if, after each buyer is assigned an optimal basket, there is no surplus or deficiency of any good.

NoteNormalizations

WLOG each $b_j$ is unit (scale the $u_{ij}$ ), and the $u_{ij}$ and $e_i$ are integral (scale again, since they are rational). We make the mild assumption that each good has a potential buyer — someone deriving nonzero utility from it — under which market clearing prices exist.

DefinitionArrow–Debreu (exchange, Walrasian) model

A set $A$ of $m$ agents and $G$ of $n$ goods. Agent $i$ arrives with an initial endowment $e_i = (e_{i1},\ldots,e_{in})$ ; WLOG the total amount of each good is unit, $\sum_i e_{ij} = 1$ . Utilities are linear as above.

Find prices so that if each agent sells her endowment at these prices and buys her optimal bundle, the market clears. An agent may have several optimal bundles; we are free to hand her any one of them to meet the clearing condition.

ImportantFisher reduces to Arrow–Debreu

A Fisher market with $n$ goods and $m$ buyers becomes an Arrow–Debreu market with $n+1$ goods and $m+1$ agents: money is the $(n{+}1)$ st good. The first $m$ agents are the buyers, endowed with the money they bring and having the Fisher utilities (and no utility for money); the $(m{+}1)$ st agent is endowed with all $n$ goods and has utility for money only.

Equivalently, in the general exchange model, Fisher is the special case of proportional endowments $w_i = \delta_i w$ — so that relative incomes are independent of prices.

DefinitionThe exchange model in general

Trader $i$ has a concave utility $u_i : \mathbb{R}^n_+\to\mathbb{R}_+$ and endowment $w_i$ , with $u_i$ nonsatiable (for any $x$ there is $y$ with $u_i(y) > u_i(x)$ ) and monotone ( $y\ge x \Rightarrow u_i(y)\ge u_i(x)$ ), and $w_{ij}>0$ for at least one $j$ . At prices $\pi$ trader $i$ sells her endowment and demands the $x_i$ maximizing $u_i(x)$ subject to $\pi\cdot x\le\pi\cdot w_i$ .

An equilibrium is $\pi$ at which there exist bundles $\bar x_i$ such that each $\bar x_i$ maximizes $u_i$ under the budget constraint, and $\sum_i\bar x_{ij}\le\sum_i w_{ij}$ for each good.

DefinitionDemand, excess demand, Walras’ Law

$x_i(\pi)$ is a demand of trader $i$ at $\pi$ ; there is at least one and possibly several. We usually assume exactly one — a demand function — which holds under strict quasi-concavity; for linear utilities the demand is a correspondence, not a function.

$z_i(\pi) = x_i(\pi) - w_i$ is the individual excess demand, $X^k(\pi) = \sum_i x_{ik}(\pi)$ the market demand, and $Z^k(\pi) = X^k(\pi) - \sum_i w_{ik}$ the market excess demand.

The economy satisfies positive homogeneity, $Z(\pi) = Z(\lambda\pi)$ , and since $\pi\cdot x_i(\pi) = \pi\cdot w_i$ , it satisfies Walras’ Law:

$\pi\cdot Z(\pi) = 0$

Equivalently, an equilibrium is a $\pi$ with $Z^j(\pi)\le0$ for every $j$ .

NoteTâtonnement

The model predicts no dynamics leading to equilibrium, though it conveys the intuition that a disequilibrium price must rise if demand exceeds supply. Walras introduced a price-adjustment mechanism — tâtonnement — inspired by the Paris stock exchange: a fictitious auctioneer announces prices, agents report demands, the auctioneer adjusts prices in proportion to aggregate demand, and the process repeats. In continuous form,

$\frac{d\pi_k}{dt} = G_k\big(Z_k(\pi)\big)$

for continuous, differentiable, sign-preserving $G_k$ .

Utility functions and approximation

Family	Form	Note
Linear	$u_i(x) = \sum_j a_{ij}x_{ij}$	perfect substitutes
Cobb–Douglas	$u_i(x) = \prod_j x_{ij}^{a_{ij}}$ , $\sum_j a_{ij}=1$	spends a fixed fraction of income on each good
Leontief (fixed-proportions)	$u_i(x) = \min_j a_{ij}x_{ij}$	perfect complements
CES	$u(x) = \big(\sum_i \alpha_i x_i^\rho\big)^{1/\rho}$ , $-\infty<\rho<1$ , $\rho\ne0$	elasticity of substitution $1/(1-\rho)$

IntuitionCES interpolates all three

As $\rho\to1$ , CES becomes linear — perfect substitutes, no preference for variety. For $\rho>0$ the goods are partial substitutes, with $\rho$ expressing the degree of preference for variety. As $\rho\to0$ it becomes Cobb–Douglas, a perfect balance of substitution and complementarity. For $\rho<0$ it models significant complementarity, reaching perfect complementarity — Leontief — as $\rho\to-\infty$ .

A utility is homogeneous if $u(\alpha x) = \alpha u(x)$ , and log-homogeneous if $u(\alpha x) = \log\alpha + u(x)$ .

DefinitionApproximate equilibria

$x_i$ is a $\mu$ -approximate demand ( $\mu\ge1$ ) if $u_i(x_i)\ge\frac1\mu u^*$ and $\pi\cdot x_i\le\mu\,\pi\cdot w_i$ , where $u^*$ is the optimal utility under the budget.

$\pi$ is a strong $\mu$ -approximate equilibrium if there are bundles that are exact demands with $\sum_i x_{ij}\le\mu\sum_i w_{ij}$ ; it is weak if the bundles need only be $\mu$ -approximate demands.

An algorithm running in time polynomial in the input and $1/\epsilon$ is a polynomial time approximation scheme; polynomial in $\log(1/\epsilon)$ makes it a polynomial time algorithm.

NoteWhy approximation is usually unavoidable

A rational equilibrium price vector exists only in very special cases, so most algorithms compute an approximate equilibrium. The linear cases below are among the exceptions.

Gross substitutability

DefinitionGS and WGS

Market excess demand satisfies gross substitutability (resp. weak gross substitutability, WGS) if for prices $\pi,\pi'$ with $0<\pi_j\le\pi'_j$ for all $j$ and strict for some $j$ , then $\pi_k = \pi'_k$ implies $Z^k(\pi) < Z^k(\pi')$ (resp. $\le$ ).

In words: raising the price of some goods while keeping others fixed can only increase demand for the fixed-price goods.

ImportantWhat WGS buys

WGS implies equilibrium prices are unique up to scaling, and market excess demand satisfies WGS whenever each individual excess demand does.

WGS is also exactly what makes the ascending-price strategy of The main algorithm work: on raising one good’s price, no other good’s demand falls, so the need to decrease a price never arises.

WarningIn general, equilibria need not even be connected

Not only are equilibria not unique; the equilibrium set may be disconnected. Economists have therefore sought realistic restrictions under which the problem has structure — uniqueness or convexity — either at the level of individuals (restricting utilities or endowments) or of the aggregate market. See Limitations of convex programming.

The Eisenberg–Gale convex program

The problem. For the linear case of Fisher’s model, equilibrium allocations are captured as optimal solutions to a remarkable convex program. Before stating it, it is instructive to ask what such a program must look like.

IntuitionDeriving the objective function

The constraints must be the packing constraints on the $x_{ij}$ . The objective, maximizing utilities derived, should satisfy two conditions:

Scale invariance: if one buyer’s utilities are scaled by a constant, the optimal allocation is unchanged.
Splitting: if buyer $b$ ‘s money is split between two new buyers with $b$ ‘s utility function, the sum of their optimal allocations should be optimal for $b$ .

The money-weighted geometric mean of buyers’ utilities satisfies both: $\max\big(\prod_i u_i^{e_i}\big)^{1/\sum_i e_i}$ , equivalently $\max\prod_i u_i^{e_i}$ . Taking its log gives the program.

FormulaThe Eisenberg–Gale program

$\text{maximize}\quad \sum_{i=1}^{n'} e_i\log u_i$ $\text{s.t.}\quad u_i = \sum_{j=1}^n u_{ij}x_{ij}\ \ \forall i\in B, \qquad \sum_{i=1}^{n'} x_{ij}\le 1\ \ \forall j\in A, \qquad x_{ij}\ge0$

Interpreting the Lagrangian variables $p_j$ of the second constraint set as prices, the KKT conditions are

$\forall j: p_j \ge 0$
$\forall j: p_j > 0 \Rightarrow \sum_i x_{ij} = 1$
$\forall i,j: \dfrac{u_{ij}}{p_j} \le \dfrac{\sum_{j'}u_{ij'}x_{ij'}}{e_i}$
$\forall i,j: x_{ij}>0 \Rightarrow \dfrac{u_{ij}}{p_j} = \dfrac{\sum_{j'}u_{ij'}x_{ij'}}{e_i}$

TheoremProperties of Fisher equilibria, linear case

If each good has a potential buyer, equilibrium exists.
The set of equilibrium allocations is convex.
Equilibrium utilities and prices are unique.
If all $u_{ij}$ and $e_i$ are rational, equilibrium allocations and prices are rational, writable in polynomially many bits.

ProofAll four claims from the KKT conditions

Existence. For good $j$ there is a buyer with $u_{ij}>0$ , so by KKT (3), $p_j \ge e_iu_{ij}/\sum_{j'}u_{ij'}x_{ij'} > 0$ — all prices are positive, and by KKT (2) all goods are fully sold.

Conditions (3) and (4) say that if buyer $i$ gets good $j$ , then $j$ is among the goods giving her maximum utility per unit money — so each buyer receives an optimal bundle. Condition (4) is equivalent to $e_iu_{ij}x_{ij}/\sum_{j'}u_{ij'}x_{ij'} = p_jx_{ij}$ ; summing over $j$ gives $e_i = \sum_j p_jx_{ij}$ — every buyer’s money is fully spent. Together these establish equilibrium.

Convexity. Each equilibrium allocation is an optimal solution to a convex program, so the set of them is convex.

Uniqueness. $\log$ is strictly concave, so if there is more than one equilibrium, each buyer’s utility is the same in all of them; with (4), prices are then unique too.

Rationality. Equilibrium allocations and prices solve a linear system. Introduce $q_j = 1/p_j$ and let $k$ be the number of nonzero $x_{ij}$ : the system has $k+n$ unknowns (the $q_j$ and the nonzero $x_{ij}$ ) and $k+n$ equations — the equality of KKT (2) per good, and of KKT (4) per nonzero $x_{ij}$ .

∎

NoteEisenberg’s generalization

Eisenberg (1961) extends the program to Fisher markets with any homogeneous utilities, maximizing $\sum_i e_i\log u_i(x_i)$ subject to $\sum_i x_{ij}\le q_j$ . He proves an arguably stronger result: with $\sum_i e_i = 1$ , the social utility function $u(s) = \max\{\prod_i u_i(x_i)^{e_i} : \sum_i x_i\le s\}$ is homogeneous and concave, and the market demand of the whole Fisher economy equals the demand of a single trader with utility $u$ and income 1. See Convex programming for the Fisher model for the proof of optimality.

NoteNegishi’s characterization

More generally, Negishi (1960) showed equilibrium allocations of an exchange economy solve a convex program with unknown welfare weights: there exist $\alpha_i>0$ such that maximizing $\sum_i\alpha_iu_i(x_i)$ subject to $\sum_ix_{ij}\le\sum_iw_{ij}$ yields equilibrium allocations, with prices coming from the KKT dual variables. For log-homogeneous utilities KKT forces $\alpha_i = \pi\cdot\bar x_i$ , so at equilibrium $\alpha_i = \pi\cdot w_i$ .

The combinatorial algorithm for Fisher’s linear case

Checking whether given prices are equilibrium prices

DefinitionBang per buck and the equality subgraph

At prices $p$ , buyer $i$ gets $u_{ij}/p_j$ utility per unit money spent on good $j$ ; her bang per buck is $\alpha_i = \max_j\{u_{ij}/p_j\}$ . Always $\alpha_i\ge u_{ij}/p_j$ , with equality only for her bang-per-buck goods — among which she is equally happy with any combination.

The equality subgraph $G$ is bipartite on $(A,B)$ with edge $(i,j)$ iff $\alpha_i = u_{ij}/p_j$ .

DefinitionThe network $N(p)$

Direct the equality-subgraph edges from $A$ to $B$ with infinite capacity; add source $s$ with an edge to each good $j$ of capacity $p_j$ , and sink $t$ with an edge from each buyer $i$ of capacity $e_i$ . If edge $(j,i)$ carries flow $f(j,i)$ , buyer $i$ receives $f(j,i)/p_j$ units of good $j$ .

flowchart LR
  s((s)) -->|p_1| g1["good 1"]
  s -->|p_2| g2["good 2"]
  g1 -->|infinite| b1["buyer 1"]
  g1 -->|infinite| b2["buyer 2"]
  g2 -->|infinite| b2
  b1 -->|e_1| t((t))
  b2 -->|e_2| t

LemmaEquilibrium test by one max-flow

$p$ are equilibrium prices iff in $N(p)$ both cuts $(s, A\cup B\cup t)$ and $(s\cup A\cup B, t)$ are min-cuts. If so, allocations corresponding to any max-flow are equilibrium allocations.

IntuitionWhat each cut being min means

The first says all goods can be sold; the second says all money is spent. The algorithm will maintain the first as an invariant and drive toward the second.

The two crucial ingredients

The algorithm starts with prices guaranteed below equilibrium, so buyers have surplus money, and raises prices iteratively to reduce the surplus; when the surplus vanishes it terminates. This raises two questions, whose answers are the two key notions.

Question	Answer
How do we ensure no good’s equilibrium price is exceeded?	Tight sets
How do we ensure the surplus falls fast enough for polynomial time?	Balanced flows

ImportantWhy the primal-dual schema needs enhancing

The fundamental difference between complementary slackness for LPs and KKT conditions for nonlinear convex programs: the former do not involve primal and dual variables simultaneously in an equality constraint; the latter do. The repercussions are visible in the structure of the algorithm.

The dual growth process here is greedy — as in all known primal-dual algorithms, with the single exception of Edmonds’ maximum weight matching. The disadvantage of greed is that a raised dual may turn out to “obstruct” others, and only later in the run does this become clear. More sophisticated dual growth makes primal objects go tight and loose, requiring an accounting of the reversals; matching’s impeccable combinatorial structure supports such accounting, but attempts elsewhere have failed.

Here, even though growth is greedy, the complex nature of KKT conditions makes equality-subgraph edges appear and disappear as the algorithm proceeds — so we are forced into that difficult accounting anyway.

FormulaWhich KKT conditions are relaxed

Conditions (1) and (2) are enforced throughout — via a max-flow in $N(p)$ , all goods can always be sold. Buyers may have surplus. With $m_i$ the money buyer $i$ spends under a balanced flow, her surplus is $\gamma_i = e_i - m_i$ , and conditions (3) and (4) are relaxed to

$\frac{u_{ij}}{p_j}\le\frac{\sum_{j'}u_{ij'}x_{ij'}}{m_i}, \qquad x_{ij}>0\Rightarrow\frac{u_{ij}}{p_j} = \frac{\sum_{j'}u_{ij'}x_{ij'}}{m_i}$

The potential function is $\Phi = \gamma_1^2+\cdots+\gamma_{n'}^2$ ; when it drops to zero, all KKT conditions hold exactly.

NoteContinuous rather than discrete satisfaction

Primal-dual algorithms for LPs satisfy complementary conditions in discrete steps — each iteration satisfies at least one new condition — so strongly polynomial iterations give a strongly polynomial algorithm. This algorithm satisfies KKT conditions continuously: as it proceeds, each buyer’s conditions are satisfied to a greater extent. Since $\Phi$ ‘s initial value depends on the money possessed by buyers, and hence on the input length, the algorithm is polynomial but not strongly polynomial even though each phase is.

Tight sets and the Invariant

DefinitionTight set

For $S\subseteq A$ let $p(S)$ be the total price of goods in $S$ , for $T\subseteq B$ let $m(T) = \sum_{i\in T}e_i$ , and let $\Gamma(S)$ be $S$ ‘s neighbourhood in $N(p)$ — the buyers currently interested in goods in $S$ . Then $S$ is tight if $p(S) = m(\Gamma(S))$ .

Under this circumstance, raising prices in $S$ may exceed some good’s equilibrium price, so the algorithm freezes the prices of all goods in $S$ . (When new edges enter the equality subgraph, frozen goods may be unfrozen.)

ImportantThe Invariant

The prices $p$ are such that $(s, A\cup B\cup t)$ is a min-cut in $N(p)$ .

LemmaCharacterization of the Invariant

$N(p)$ satisfies the Invariant iff $\forall S\subseteq A: p(S)\le m(\Gamma(S))$ .

ProofMove

A_1

and its neighbourhood across the cut

Forward is trivial: under a max-flow of value $p(A)$ , every $S$ must send $p(S)$ into its neighbourhood.

Reverse: let $(s\cup A_1\cup B_1, A_2\cup B_2\cup t)$ be a min-cut, of capacity $p(A_2) + m(B_1)$ . Necessarily $\Gamma(A_1)\subseteq B_1$ , else the cut is infinite. Moving $A_1$ and $\Gamma(A_1)$ to the $t$ side gives another cut, and by hypothesis $p(A_1)\le m(\Gamma(A_1))$ , so its capacity is no larger — hence it too is a min-cut, and the Invariant holds.

∎

Balanced flows

DefinitionBalanced flow

Given a feasible flow $f$ in $N$ , the surplus $\gamma_i(N,f)$ of buyer $i$ is the residual capacity of edge $(i,t)$ — her money minus what she spends. A balanced flow minimizes $\lVert\gamma(N,f)\rVert$ , the $\ell_2$ norm of the surplus vector.

A balanced flow must be a max-flow, since augmenting can only decrease the norm.

LemmaUniqueness of the surplus vector

All balanced flows in $N$ have the same surplus vector.

ProofConvexity plus strict convexity of the objective

If $\gamma_1,\gamma_2$ are surplus vectors of $f_1,f_2$ then $(\gamma_1+\gamma_2)/2$ is that of $(f_1+f_2)/2$ ; since feasible flows form a convex region, so do feasible surplus vectors. Minimizing a strictly convex function over a convex set gives a unique optimum.

∎

ImportantProperty 1 — the property used critically throughout

If $\gamma_j(N,f) < \gamma_i(N,f)$ then there is no path from $j$ to $i$ in $R(f)-\{s,t\}$ . A max-flow is balanced iff it satisfies Property 1.

ProofBoth directions, via circulations

Balanced $\Rightarrow$ Property 1. Suppose $\gamma_i > \gamma_j$ yet a path $j\to i$ exists in $R(f)-\{s,t\}$ . In $N$ the only edge out of $j$ is $(j,t)$ , so the path must start with a different positive-capacity edge; by flow conservation $(t,j)$ has positive residual capacity. Since $\gamma_i>0$ , so does $(i,t)$ . Concatenating $(t,j)$ , the path, and $(i,t)$ gives a positive-capacity cycle; pushing a circulation around it raises $j$ ‘s surplus slightly and lowers $i$ ‘s — a more balanced flow, contradiction.

Property 1 $\Rightarrow$ balanced. A max-flow satisfying Property 1 is locally optimal with respect to changes in pairs of surplus components, since any circulation in $R(f)$ can only move flow from a high-surplus buyer to a low-surplus one, making things less balanced. As the $\ell_2$ norm is strictly convex, local optimality implies global.

∎

AlgorithmFinding a balanced flow by divide and conquer

Assume $N$ satisfies the Invariant. Continuously reduce the capacities of all edges from $B$ to $t$ (excepting those hitting zero) until the capacity of $(\{s\}\cup A\cup B,\{t\})$ equals that of $(\{s\}, A\cup B\cup\{t\})$ . Call the result $N'$ , let $f'$ be a max-flow in it, and find a maximal $s$ – $t$ min-cut $(S,T)$ .

Case 1: $T = \{t\}$ . Output a max-flow in $N'$ — this is balanced in $N$ .
Case 2: otherwise let $N_1,N_2$ be the subnetworks of $N$ induced by $S\cup\{t\}$ and $T\cup\{s\}$ — inheriting original capacities from $N$ , not the reduced ones from $N'$ . Recursively find balanced $f_1,f_2$ and output $f = f_1\cup f_2$ .

Proof

f

is a max-flow

Case 1: the output saturates $(\{s\}\cup A\cup B,\{t\})$ , whose capacity in $N'$ equals that of $(\{s\},A\cup B\cup\{t\})$ ; by the Invariant it is a max-flow in $N$ .

Case 2: $N_1,N_2$ are edge-disjoint so $f$ is feasible; we show it saturates all edges from $s$ to $A$ . Let $g$ be a max-flow in $N$ . Neither $N'$ nor $N$ has edges from $A_1$ to $B_2$ , so all of $g$ ‘s flow into $A_1$ exits via $B_1$ ; hence $g$ restricted to $N_1$ saturates $s\to A_1$ , and so must the max-flow $f_1$ . Since $(S,T)$ is a min-cut in $N'$ , $f'$ saturates $s\to A_2$ and all that flow exits via $B_2$ , so $f'$ restricted is feasible in $N_2$ and the max-flow $f_2$ also saturates $s\to A_2$ .

∎

Proof

f

is balanced

By induction on recursion depth. Base case ( $T=\{t\}$ ): the surplus vector is precisely the amounts subtracted from the $B\to t$ capacities, which makes the components as equal as possible and hence minimizes the norm.

Inductive step. $f$ is a max-flow; we verify Property 1. By hypothesis it holds within $N_1$ and $N_2$ , so only cross paths matter. There are no edges $A_1\to B_2$ in $N$ , hence no residual paths $B_1\to B_2$ . For paths $B_2\to B_1$ , we show $\gamma_i < \gamma_j$ for $i\in B_1$ , $j\in B_2$ .

By maximality of the min-cut in $N'$ , every node of $B_2$ has positive surplus under $f'$ (zero-surplus nodes are all in $B_1$ ), so the same amount $X$ was subtracted from each edge $(i,t)$ , $i\in B_2$ . Let $L$ be the minimum-surplus vertices of $B_2$ and $K$ the vertices of $A_2$ reachable from $L$ in $R$ ; then $\Gamma(K) = L$ , else there is a residual path from $L$ to $B_2 - L$ violating Property 1. All edges $s\to K$ are saturated in $f'$ and that flow leaves via $L$ , so $c'(L) > c(K)$ ; and $c(L) = c'(L) + |L|X$ . Hence the total surplus on $E_L$ is $c(L)-c(K) > |L|X$ , and since all these edges have equal surplus, each exceeds $X$ . Symmetrically each $i\in B_1$ has surplus below $X$ .

∎

TheoremComputing a balanced flow

The above computes a balanced flow using at most $n$ max-flow computations: the biggest piece shrinks by at least one good per iteration, and $N_1, N_2$ are vertex-disjoint apart from $s,t$ , so the work per level is bounded by one max-flow in $N$ .

The main algorithm

NoteInitialization

Two conditions guarantee the Invariant at the start:

Prices low enough that each buyer can afford all goods — $1/n$ suffices, since the goods cost one unit together and the $e_i$ are integral.
Each good has an incident equality edge; if good $j$ has none, reduce its price to $p_j = \max_i\{u_{ij}/\alpha_i\}$ .

WarningThe naive approach fails

Under the Invariant there is a unique maximal tight set $S$ , whose prices cannot be raised. One could raise all prices in $A - S$ — but no way is known to bound the running time of such an algorithm, and it seems it can be forced to take many steps making very little progress, hence superpolynomial time.

The fix: always raise prices of goods desired by buyers with a lot of surplus. When a subset of these goes tight, the surplus of some of those buyers vanishes — substantial progress. Property 1 is what lets the algorithm keep working with a high-surplus set even as $N(p)$ changes.

AlgorithmThe main loop

A run is partitioned into phases, each ending with a new tight set; phases are partitioned into iterations.

A phase begins by computing a balanced flow $f$ . If the balanced-flow algorithm terminates in Case 1, the current prices and allocations are an equilibrium — halt. Otherwise let $\delta$ be the maximum surplus, $I$ the buyers achieving it, and $J$ the goods with edges to $I$ ; the network induced by $I\cup J$ is the active subgraph.

Step: multiply the prices of goods in $J$ by a variable $x$ , initialized to 1, and raise $x$ continuously. (Raising all of $J$ by the same factor keeps the ratio of any two prices fixed, so each buyer in $I$ keeps the same favourite set — all within $J$ . As soon as $x>1$ , buyers in $B-I$ lose interest in $J$ and those edges leave the equality subgraph.)

Event 1: a subset $S\subseteq J$ goes tight — the phase ends.
Event 2: an edge $(i,j)$ with $i\in I$ , $j\in A-J$ enters the equality subgraph, as goods outside $J$ become relatively more desirable. Add $(j,i)$ to $N(p)$ and recompute a balanced flow. (If that terminates in Case 1, halt.) Otherwise update $I$ to be all buyers with residual paths to the current $I$ — which certainly contains the old $I$ — update $J$ accordingly, and return to Step.

Compute the smallest $x$ at which each event occurs and take the smaller.

IntuitionThe primal-dual reading

The primal variables are the flows in $N(p)$ and the dual variables the current prices. The current flow suggests how to improve the prices, and vice versa.

Finding tight sets

Let $p$ be the current prices (at $x=1$ ). WLOG the tight set at $p$ is empty, since we can restrict attention to the active subgraph. Define

$x^* = \min_{\emptyset\ne S\subseteq A}\frac{m(\Gamma(S))}{m(S)}$

the value of $x$ at which a nonempty set goes tight, with $S^*$ the tight set at $x^*p$ .

LemmaHow the min-cut changes with $x$

W.r.t. prices $x\cdot p$ : if $x\le x^*$ then $(s,A\cup B\cup t)$ is a min-cut; if $x>x^*$ it is not, and moreover any min-cut $(s\cup A_1\cup B_1, A_2\cup B_2\cup t)$ has $S^*\subseteq A_1$ .

ProofBoth cases

$x\le x^*$ : by definition $x\cdot m(S)\le m(\Gamma(S))$ for all $S$ , so the Invariant holds.

$x>x^*$ : since $x\cdot m(S^*) > x^*m(S^*) = m(\Gamma(S^*))$ , the cut $(s\cup S^*\cup\Gamma(S^*), t)$ is strictly smaller than $(s\cup A\cup B,t)$ , so the latter is not min.

For the second claim, let $S_2 = S^*\cap A_2$ and $S_1 = S^*-S_2$ , and suppose $S_2\ne\emptyset$ . Certainly $\Gamma(S_1)\subseteq B_1$ . If $m(\Gamma(S_2)\cap B_2) < x\cdot m(S_2)$ we could move $S_2$ and $\Gamma(S_2)$ to the $s$ side and get a smaller cut; in particular $m(\Gamma(S^*)\cap B_2)\le m(\Gamma(S^*)) = x^*m(S^*) < x\cdot m(S^*)$ , so $S_2\ne S^*$ and $S_1\ne\emptyset$ . Then $m(\Gamma(S_2)\cap B_2)\ge x\cdot m(S_2) > x^*m(S_2)$ while $m(\Gamma(S_2)\cap B_2)+m(\Gamma(S_1))\le x^*(m(S_2)+m(S_1))$ , giving $m(\Gamma(S_1))/m(S_1) < x^*$ — contradicting the definition of $x^*$ .

∎

LemmaRecursing on a smaller graph

With $x = m(B)/m(A)$ , if $x>x^*$ and $(s\cup A_1\cup B_1, A_2\cup B_2\cup t)$ is a min-cut in $N(xp)$ , then $A_1$ is a proper subset of $A$ .

(If $A_1 = A$ then $B_1 = B$ and $(s\cup A\cup B,t)$ is a min-cut; but at this $x$ that cut has the same capacity as $(s,A\cup B\cup t)$ , which is not min since $x>x^*$ .)

LemmaFinding $x^*$ and $S^*$

Both can be found using $n$ max-flow computations: set $x = m(B)/m(A)\ge x^*$ ; if $(s,A\cup B\cup t)$ is a min-cut then $x^* = x$ and $S^* = A$ ; otherwise $S^*\subseteq A_1\subset A$ and we recurse on $(A_1,\Gamma(A_1))$ .

Running time

Let $U = \max_{i,j}u_{ij}$ and $\Delta = nU^n$ .

LemmaPrices of newly tight goods are nicely rational

At the end of a phase, the prices of goods in the newly tight set are rational with denominator $\le\Delta$ .

ProofAlternating products along a path

Let $S$ be the newly tight set; assume the equality subgraph on $(S,\Gamma(S))$ is connected (else argue per component). Pick $j\in S$ and a subgraph in which $j$ reaches every other $j'\in S$ — at most $2|S|\le2n$ edges. If $j$ reaches $j'$ by a path of length $2l$ then $p_{j'} = ap_j/b$ where $a,b$ are products of $l$ utility parameters each, since alternate edges of the path contribute to $a$ and to $b$ . Hence $m(S) = p_jc/d$ with $c\le\Delta$ , and $p_j = m(\Gamma(S))d/c$ .

∎

LemmaPrices jump by a definite amount

If good $j$ lies in the newly tight set at the end of two phases $P$ and $P'$ (not necessarily consecutive), the price increase between them is $\ge 1/\Delta^2$ — since with $p/q$ and $r/s$ the two prices and $q,s\le\Delta$ , $r/s - p/q \ge 1/\Delta^2$ .

LemmaIterations per phase

At most $n$ . Each Event-2 iteration brings at least one new good into the active subgraph, and there is at least one there to begin with, so at most $n-1$ of those; the last iteration of each phase is Event 1.

LemmaThe surplus norm drops

If $f$ is feasible and $f^*$ balanced in $N(p)$ with $\gamma_i(p,f^*) = \gamma_i(p,f)-\delta$ for some $i$ and $\delta>0$ , then $\lVert\gamma(p,f^*)\rVert^2 \le \lVert\gamma(p,f)\rVert^2 - \delta^2$ .

ProofDecompose

f^* - f

and keep only the paths through

(i,t)

Augment $f$ by only those flow paths and circulations of $f^*-f$ that go through $(i,t)$ , getting $f'$ . These are paths $s\to i\to t$ or circulations $i\to t\to i_l\to i$ . Then $\gamma_i(f') = \gamma_i(f^*) = \gamma_i(f)-\delta$ and $\gamma_{i_l}(f') = \gamma_{i_l}(f)+\delta_l$ with $\sum_l\delta_l\le\delta$ ; moreover each $i_l$ is reachable from $i$ in $R(p,f^*)$ , so by Property 1, $\gamma_i(f')= \gamma_i(f^*)\ge\gamma_{i_l}(f^*)\ge\gamma_{i_l}(f')$ .

The elementary inequality $\lVert(a,b_1,\ldots,b_n)\rVert^2 \le \lVert(a+\delta, b_1-\delta_1,\ldots,b_n-\delta_n)\rVert^2 - \delta^2$ (for $a\ge b_i\ge0$ , $\sum_j\delta_j\le\delta$ ) then gives $\lVert\gamma(p,f')\rVert^2\le\lVert\gamma(p,f)\rVert^2-\delta^2$ , and since $f^*$ is balanced, $\lVert\gamma(p,f^*)\rVert\le\lVert\gamma(p,f')\rVert$ .

∎

LemmaMonotonicity across iterations

A balanced flow $f_t$ at the end of iteration $t$ is feasible in $N_{t+1}$ — both raising prices in $J$ and adding an Event-2 edge can only support an augmented max-flow — so $\lVert\gamma(N_t)\rVert$ is monotonically decreasing. Moreover if the minimum active surplus $\delta_t$ strictly drops, some buyer’s surplus drops by at least $\delta_t - \delta_{t+1}$ , whence $\lVert\gamma(N_t)\rVert^2 - \lVert\gamma(N_{t+1})\rVert^2 \ge (\delta_t-\delta_{t+1})^2$ .

LemmaProgress per phase

In a phase, $\lVert\gamma\rVert^2$ drops by a factor $\big(1 - \tfrac{1}{n^2}\big)$ .

ProofTelescope, then use

\delta_0 = \delta

\delta_k = 0

The difference $\lVert\gamma(N_0)\rVert^2 - \lVert\gamma(N_k)\rVert^2$ telescopes into nonnegative terms; keeping only those with $\delta_t>\delta_{t+1}$ , the sum is minimized when all the differences are equal, giving $\ge\delta^2/k\ge\delta^2/n$ since $k\le n$ . With $\lVert\gamma(N_0)\rVert^2\le n\delta^2$ the claim follows.

∎

TheoremRunning time

The algorithm finds equilibrium prices and allocations for Fisher’s linear case using $O\big(n^4(\log n + n\log U + \log M)\big)$ max-flow computations.

ProofMultiply the three bounds

The squared surplus halves every $O(n^2)$ phases; it starts at most $M^2$ and the algorithm is done once it drops below $1/\Delta^4$ (by the two price lemmas), so the number of phases is $O(n^2\log(\Delta^4M^2)) = O(n^2(\log n + n\log U + \log M))$ . Each phase has $n$ iterations and each iteration $n$ max-flows.

∎

Auction-based algorithm for Arrow–Debreu

The target. For any fixed $\epsilon>0$ , find prices such that the market clears and each agent gets a bundle worth at least $(1-\epsilon)^2$ times the utility of her optimal bundle.

AlgorithmThe auction

Initialize every price to 1, compute the worth of each agent’s endowment, and give her that money; all goods are unsold. As prices change, endowment worths and agents’ money are recomputed. Initially the total surplus is $n$ .

At any point part of good $j$ is sold at $p_j$ and part at $(1+\epsilon)p_j$ . The run splits into iterations, each ending when some price rises by a factor $(1+\epsilon)$ ; iterations split into rounds, in which agents are considered in a fixed order.

For agent $i$ with surplus, find her bang-per-buck optimal good $j$ and execute outbid: buy back $j$ from agents holding it at price $p_j$ and sell it to $i$ at $(1+\epsilon)p_j$ . This ends either when

$i$ ‘s surplus is exhausted — move to the next agent; or
no agent holds $j$ at price $p_j$ — raise $p_j$ to $(1+\epsilon)p_j$ , ending the iteration and updating all agents’ money.

After each round, if the total surplus is at most $\epsilon\cdot a_{\min}$ , halt; at termination give unsold goods to an arbitrary agent so the market clears.

(Notation: $a_i = \sum_j e_{ij}$ , $a_{\min} = \min_i a_i$ , $p_{\max}$ the largest price assigned, $v_{\min}, v_{\max}$ the extreme utility values.)

LemmaRounds per iteration

$O\big(\tfrac1\epsilon\log\tfrac{np_{\max}}{\epsilon a_{\min}}\big)$ .

Why: outbid buys at $p_j$ and sells at $(1+\epsilon)p_j$ , so each fully completed round reduces total surplus by a factor $(1+\epsilon)$ . Surplus starts at most $np_{\max}$ and the algorithm stops at $\epsilon a_{\min}$ .

LemmaTotal iterations

$O\big(\tfrac n\epsilon\log p_{\max}\big)$ , since each iteration raises some price by $(1+\epsilon)$ .

LemmaApproximation quality

Each agent gets utility at least $(1-\epsilon)^2$ times her optimum.

ProofTwo sources of loss

The algorithm always sells an agent her optimal goods at current prices (charging $(1+\epsilon)p_j$ ). First, some of her money may remain unspent: with $M$ her endowment’s terminating worth and $M_1$ what she spent, the total surplus at termination is at most $\epsilon a_{\min}$ , so $M_1\ge(1-\epsilon)M$ . Second, she paid $(1+\epsilon)p_j$ for part of good $j$ though the announced price is $p_j$ — equivalently she gets optimal goods at prices $p$ for

$\frac{M_1}{1+\epsilon}\ge\frac{(1-\epsilon)M}{1+\epsilon}\ge(1-\epsilon)^2M$

of her money.

∎

TheoremRunning time

$O\left(\frac{mn}{\epsilon^2}\log\frac{nv_{\max}}{\epsilon a_{\min}v_{\min}}\log\frac{v_{\max}}{v_{\min}}\right)$

ProofBound

p_{\max}

, then apply the two lemmas

Every good whose price exceeds 1 is fully sold. Since the agents’ total money is the total worth of all goods, the surplus condition must be reached before all prices exceed 1 — so at termination some good still has price 1, and the ratio of max to min price is bounded by $v_{\max}/v_{\min}$ , hence so is $p_{\max}$ . Each round takes $O(m)$ time.

∎

Kelly’s resource allocation markets

ImportantWhere this came from

In a different context — modelling and understanding TCP congestion control — Kelly (1997) defined a class of resource allocation markets and gave a convex program for their equilibria. Kelly’s program has the same structure as Eisenberg–Gale.

Kelly’s object was to explain the unprecedented success of TCP and Jacobson’s congestion avoidance protocol, which played a crucial role in the Internet’s growth. Fairness is a key desired property, and Jacobson’s protocol seems to ensure it. Recent results show that with Jacobson’s protocol at end-nodes and Floyd–Jacobson at buffer queues, traffic flows converge in the limit to an optimal solution of Kelly’s program — i.e. to equilibrium allocations. Kelly used the formulation to prove equilibrium allocations are proportionally fair, formally ratifying the protocol.

DefinitionKelly’s model

Resources $R$ with capacities $c : R\to\mathbb{Z}_+$ , agents $A = \{a_1,\ldots,a_n\}$ with money $m_i$ . Each agent wants to build as many objects as possible from resources; agent $a_i$ can use any of the subsets $S_{i1},\ldots,S_{ik_i}\subseteq R$ . With $x_{ij}$ the (not necessarily integral) number of objects built from $S_{ij}$ and $f_i = \sum_j x_{ij}$ the total, the program is

$\text{maximize}\ \sum_i m_i\log f_i \quad\text{s.t.}\quad f_i = \sum_{j=1}^{k_i}x_{ij},\quad \sum_{(ij):r\in S_{ij}}x_{ij}\le c(r),\quad x_{ij}\ge0$

FormulaProportional fairness

An optimal $f^*$ satisfies, for every feasible $f$ ,

$\sum_{i=1}^n \frac{f_i - f_i^*}{f_i^*} \le 0$

Intuitively: the only way to make one agent 5% happier is to make others unhappy by at least 5% in total.

NoteEquilibrium conditions, and uniqueness

KKT gives Lagrangian variables $p_r$ interpreted as resource prices, with (i) a resource has positive price only if used to capacity; (ii) each agent uses only the cheapest sets; (iii) each agent’s money is fully used. Since the objective is strictly concave, the vector $f_1,\ldots,f_n$ is unique at optimality — and hence in every equilibrium.

Market	Resources	Agents	Objects
1: flow market	edges of a directed or undirected $G$	source–sink pairs $(s_i,t_i)$	$s_i$ – $t_i$ paths
2	edges of a directed $G$	$A\subseteq V$	branchings rooted at $s$ spanning $V$
3	edges of an undirected $G$	$A\subseteq V$	spanning trees

NoteThe flow market and the question that motivated this line

The flow market is of special significance: find equilibrium flows and edge prices (in the TCP reading, drop rates at links). Continuous-time algorithms, though not polynomial, were given by Kelly et al. Kelly and Vazirani observed that Kelly’s model essentially generalizes Fisher’s linear case, and asked: “Continuous time algorithms similar to TCP are known, but insights from discrete algorithms may be provocative.” The next section answers a special case.

Single-source multiple-sink flow markets

Setup. A directed $G = (V,E)$ with edge capacities, source $s$ , sinks $T = \{t_1,\ldots,t_r\}$ with money $m_i$ . (Undirected graphs reduce by replacing each edge with two directed edges of the same capacity.)

ExampleA small instance worth simulating

$V = \{s,a,b,c,d\}$ ; sinks $b$ and $d$ with $120 and $10. Edges $(s,a)$ and $(s,c)$ of capacity 2, $(a,b)$ of capacity 1, and $(a,d),(c,d),(c,b)$ of capacity 10. The unique equilibrium prices are $p_{(s,a)} = \text{\textdollar}10$ , $p_{(a,b)}= \text{\textdollar}30$ , $p_{(s,c)}= \text{\textdollar}40$ , with the rest zero; the flows are 1 on $s,a,d$ , 1 on $s,a,b$ , and 2 on $s,c,b$ . Simulating the algorithm reveals the complex sequence of cuts needed.

ImportantThe algorithm as an ascending-price auction

Buyers are sinks, sellers are edges. Buyers have fixed budgets and want maximum flow; sellers want the highest price. The deviation from a usual auction: the sellers act in a highly coordinated manner — at any point, all edges of one particular cut raise their prices simultaneously while the rest stay fixed.

Prices start at zero. The first cut considered is the unique maximal min-cut separating all sinks from $s$ .

Let $\text{rate}(t_i)$ be the cost of the cheapest $s$ – $t_i$ path at current prices; sink $t_i$ demands $m_i/\text{rate}(t_i)$ flow — infinite at the start, when all prices are zero. Indeed no feasible flow satisfies all demands at any intermediate point: some cuts must be oversaturated.

The price of the current cut $(S,\bar S)$ rises as long as demand across it exceeds supply. When does the cut realize it must sell itself? As soon as there is a cut $(U,\bar U)$ with $S\subset U$ whose capacity differs from $(S,\bar S)$ ‘s by exactly the flow demanded by sinks in $S - U$ . Take $(U,\bar U)$ maximal (it is unique). If $U = V$ , halt; otherwise $(U,\bar U)$ is oversaturated, becomes the new $(S,\bar S)$ , and the next iteration begins.

An edge in several such cuts is priced at the sum of the assigned prices.

IntuitionWhy the cut stops there

From the edges’ own viewpoint: raise prices any further and demand would fall below supply — the cut would be under-saturated, and then these edges would have to be priced at zero.

ProofCorrectness

Suppose $k$ iterations, with cuts $(S_i,\bar S_i)$ and $S_0\subset S_1\subset\cdots\subset S_k = V$ , $T_i$ the terminals in $S_i - S_{i-1}$ , and $p_i$ the price assigned to the edges of cut $c_i$ . Then $\text{rate}(t) = p_0+\cdots+p_{i-1}$ for $t\in T_i$ .

Form $G'$ by adding a sink $t$ and edges $(t_i,t)$ of capacity $m_i/\text{rate}(t_i)$ . Each cut $(S_i, \bar S_i\cup\{t\})$ has the same capacity, and all $k+1$ are minimum $s$ – $t$ cuts in $G'$ . Take a max-flow $f'$ in $G'$ and let $f$ ignore the flow into $t$ ; then $f$ sends $m_i/\text{rate}(t_i)$ to each sink.

All three KKT conditions hold: each $c_i$ is saturated by $f$ , so priced edges are used to capacity; every flow to $t'\in T_i$ uses a path of cost $\text{rate}(t')$ ; and since the flow to $t'$ is $m_i/\text{rate}(t')$ , each terminal’s money is fully spent.

∎

AlgorithmFinding the next cut

Let $(S,\bar S)$ be the current cut with edge set $c$ and capacity $f$ , $T'$ the sinks in $\bar S$ , $p'$ the sum of prices assigned so far, and $p$ the price on $c$ . Define $G'$ by adding $t$ and edges $(t_i,t)$ of capacity $m_i/(p'+p)$ .

Let $\text{cap}_p(C)$ be a cut’s capacity assuming price $p$ on $c$ ; $\text{cut}(p)$ the maximal $s$ – $t$ min-cut in $G'$ at that price; and $\text{price}(A,\bar A\cup\{t\})$ the smallest price making that cut minimum ( $\infty$ if impossible) — found by solving one equation in $p$ . Then:

$C\leftarrow(V,t)$
$p\leftarrow\text{price}(C)$
While $\text{cut}(p)\ne C$ : set $C\leftarrow\text{cut}(p)$ and $p\leftarrow\text{price}(C)$
Output $(C,p)$

LemmaThe search shrinks monotonically

Suppose $p>p^*$ , $\text{cut}(p) = (A,\bar A\cup\{t\})$ with $A\ne U$ , $q = \text{price}(A,\bar A\cup\{t\})$ and $\text{cut}(q) = (B,\bar B\cup\{t\})$ . Then $B\subset A$ .

ProofSubmodularity rules out crossing

Since $A\ne U$ , $\text{cap}_p(A,\bar A\cup\{t\})>f$ , so $q<p$ . With $c_A,c_B$ the capacities at $p=0$ and $m_A,m_B$ the money of sinks in $A-S$ , $B-S$ : minimality of $A$ at $p$ gives $c_A + m_A/p < c_B + m_B/p$ , and of $B$ at $q$ gives $c_B+m_B/q < c_A+m_A/q$ , whence

$\frac{m_B-m_A}{q} < c_A - c_B < \frac{m_B-m_A}{p}$

If $A\subset B$ then $m_A\le m_B$ , contradicting this since $q<p$ . If $A,B$ cross, there is $q<r<p$ with $\text{cap}_r(A,\cdot) = \text{cap}_r(B,\cdot) = g$ ; by submodularity either $\text{cap}_r(A\cap B,\cdot)\le g$ — and since the money in $(A\cap B)-S$ is at most $m_B$ , at price $q$ this beats $B$ , contradiction — or $\text{cap}_r(A\cup B,\cdot)\le g$ — and since the money in $(A\cup B)-S$ is at least $m_A$ , at price $p$ this beats $A$ , contradiction.

∎

TheoremRunning time

The algorithm finds equilibrium edge prices and flows using $O(r^2)$ max-flow computations, $r$ the number of sinks: the subroutine takes $r$ max-flows (it keeps finding cuts with fewer sinks on the $s$ side), and the number of trapped sinks increases each iteration so $k\le r$ .

Convex programming for the Fisher model

FormulaEisenberg’s program

With homogeneous utilities,

$\text{maximize}\ \sum_i e_i\log u_i(x_i)\quad\text{s.t.}\quad \sum_i x_{ij}\le q_j$

Notice the program has no price variables. The optimal allocations are exactly the individual demands at prices given by the Lagrangian duals.

ProofOptimality, for differentiable utilities

Let $\bar x$ be optimal; note $u_i(\bar x_i)>0$ . KKT gives $\pi_j\ge0$ and $\lambda_{ij}\ge0$ with

$\pi_j\Big(\sum_i x_{ij}-q_j\Big) = 0, \qquad \lambda_{ij}x_{ij} = 0, \qquad \frac{e_i}{u_i(\bar x_i)}\times\frac{\partial u_i(\bar x_i)}{\partial x_{ij}} = \pi_j - \lambda_{ij}$

Budget exhaustion. Multiply the third by $\bar x_{ij}$ and sum over $j$ ; using the second and Euler’s identity $u_i(x_i) = \sum_j x_{ij}\partial u_i/\partial x_{ij}$ for homogeneous $u_i$ , this collapses to $e_i = \sum_j\pi_j\bar x_{ij}$ .

Optimality of the bundle. Let $y_i\ge0$ with $\pi\cdot y_i\le e_i$ . By concavity,

$u_i(y_i)-u_i(\bar x_i) \le \nabla u(\bar x_i)\cdot(y_i-\bar x_i) = \frac{u_i(\bar x_i)}{e_i}\sum_j(\pi_j-\lambda_{ij})(y_{ij}-\bar x_{ij}) = \frac{u_i(\bar x_i)}{e_i}\Big(\sum_j(\pi_jy_{ij}-\lambda_{ij}y_{ij}) - e_i\Big) \le 0$

Market clearance. The first KKT condition gives $\sum_i\bar x_{ij} = q_j$ whenever $\pi_j>0$ ; for goods with $\pi_j = 0$ , allocate the excess to trader 1 — which keeps her bundle a demand, since the new goods are free and adding positive quantities cannot decrease $u_1$ .

∎

Exchange economies satisfying WGS

LemmaThe separating hyperplane

Let $\hat\pi$ be an equilibrium price vector for an exchange economy satisfying gross substitutability, and $\pi$ any nonequilibrium price vector. Then

$\hat\pi\cdot Z(\pi) > 0$

ImportantWhy this is the whole story for WGS

The lemma says the set of equilibrium prices is convex, by exhibiting for any non-equilibrium $\pi$ a hyperplane separating it from that set — namely $\{x : x\cdot Z(\pi) = 0\}$ , since $\hat\pi\cdot Z(\pi)>0$ while $\pi\cdot Z(\pi) = 0$ by Walras’ Law. To compute the hyperplane we need only the demands at $\pi$ .

It also says: if we start at $\pi$ and move in the direction $Z(\pi)$ , the Euclidean distance to equilibrium decreases — the crux of the proof that tâtonnement converges.

Two transformations

DerivationNormalizing total supply, then adding a Cobb–Douglas trader

Transformation 1 ( $M\to M'$ ): make the total amount of each good 1. Set $u_i'(x) = u_i(W_1x_1,\ldots,W_nx_n)$ with $W_j = \sum_i w_{ij}$ , and $w_{ij}' = w_{ij}/W_j$ ; then $W_j' = 1$ . Concavity and WGS are preserved, and $\mu$ -approximate demands and weak $\mu$ -approximate equilibria correspond under the rescaling $\pi_j\leftrightarrow\pi_j/W_j$ .

Transformation 2 ( $M'\to\hat M$ ): fix $0<\eta\le1$ and add one extra trader with endowment $\hat w_{m+1} = (\eta,\ldots,\eta)$ and the Cobb–Douglas utility $\prod_j x_{m+1,j}^{1/n}$ — so she spends exactly $1/n$ of her budget on each good: $\pi_jx_{m+1,j}(\pi) = \pi\cdot\hat w_{m+1}/n$ . Now $\hat W_j = 1+\eta$ .

LemmaProperties of $\hat M$

(1) $\hat M$ has an equilibrium. (2) Every equilibrium satisfies $\frac{\max_j\pi_j}{\min_j\pi_j}\le 2n/\eta$ . (3) A weak $\mu$ -approximate equilibrium for $\hat M$ is a weak $\mu(1+\eta)$ -approximate equilibrium for $M'$ . (4) $\hat M$ satisfies WGS if $M'$ does.

IntuitionWhat the extra trader is for

Existence follows from standard microeconomic theory: a quasi-equilibrium always exists, and at it the extra trader’s income is strictly positive, forcing $\pi_j>0$ for every good — which upgrades the quasi-equilibrium to an equilibrium. Property (2) — bounding the spread of prices — is the other crucial role she plays, and it is what makes the price region compact.

DefinitionThe price regions

$\Pi = \{\pi\ge0 : \eta/2n\le\pi_j\le1\}$ , which contains an equilibrium of $\hat M$ ; and $\Pi^+ = \{\pi\ge0:\eta/4n\le\pi_j\le1+\eta/4n\}$ , on which $\frac{\max_j\pi_j}{\min_j\pi_j}\le\frac{1+\eta/4n}{\eta/4n}\le\frac{5n}{\eta}$ .

The discrete tâtonnement process

AlgorithmDiscrete tâtonnement

Assume an oracle computing the excess demand of $\hat M$ at any $\pi\in\Pi^+$ (readily built from one for $M$ ). Start at any $\pi^0\in\Pi$ . Given $\pi^0,\ldots,\pi^{i-1}$ :

If $\pi^{i-1}\notin\Pi^+$ , let $\pi^i$ be the point of $\Pi$ closest to $\pi^{i-1}$ (clamp each coordinate into $[\eta/2n, 1]$ ).
Otherwise, $\displaystyle \pi^i = \pi^{i-1} + \frac{\delta}{(12n^2/\eta)^2}Z(\pi^{i-1})$ .

LemmaQuantitative separation

Let $\pi\in\Pi^+$ fail to be a weak $(1+\epsilon)$ -approximate equilibrium for $\hat M$ . Then for any equilibrium $\hat\pi\in\Pi$ , $\hat\pi\cdot Z(\pi)\ge\delta>0$ where $1/\delta$ is polynomial in $n$ , $1/\epsilon$ , $1/\eta$ .

ProofA telescoping path of price vectors, with WGS applied at each step

Order the goods so $\hat\pi_1/\pi_1\le\cdots\le\hat\pi_n/\pi_n$ and write $\alpha_s = \hat\pi_s/\pi_s$ . Let $q^s = \min\{\alpha_s\hat\pi, \pi\}$ componentwise, i.e. $q^s = (\pi_1,\ldots,\pi_{s-1},\alpha_s\hat\pi_s,\ldots,\alpha_s\hat\pi_n)$ — so $q^1$ is an equilibrium price vector (a scaling of $\hat\pi$ ) and $q^n = \pi$ . Let $G_s^h = \{1,\ldots,s\}$ (prices fixed during step $s$ ) and $G_s^t = \{s+1,\ldots,n\}$ .

By Walras’ Law at both ends, $0 = q^{s+1}\cdot Z(q^{s+1}) - q^s\cdot Z(q^s)$ ; expanding and applying WGS twice — to $(q^s, \alpha_s\hat\pi)$ giving $Z_j(q^s)\le0$ for $j\in G_s^t$ , and to $(q^s,q^{s+1})$ giving $Z_j(q^{s+1})\ge Z_j(q^s)$ for $j\in G_s^h$ — yields

$\hat\pi\cdot\big(Z(q^{s+1})-Z(q^s)\big) \ge \Big(1-\frac{\alpha_s}{\alpha_{s+1}}\Big)\sum_{j\in G_s^h}\hat\pi_j\big(Z_j(q^{s+1})-Z_j(q^s)\big) \ge 0$

Since $\pi$ is not an approximate equilibrium, $\alpha_n/\alpha_1\ge1+\epsilon/3$ , so some $k$ has $\alpha_{k+1}/\alpha_k\ge1+\epsilon/6n$ and hence $1-\alpha_k/\alpha_{k+1}\ge\epsilon/12n$ .

Here the extra trader earns her keep. Her income rises by at least $(\alpha_{k+1}-\alpha_k)\hat\pi_n\hat w_{m+1,n}\ge\frac{\epsilon\alpha_k}{6n}\hat\pi_n\hat w_{m+1,n}$ , and since she spends $1/n$ of income on each good, $x_{m+1,1}(q^{k+1}) - x_{m+1,1}(q^k)\ge\frac{\epsilon\alpha_k\hat\pi_n\hat w_{m+1,n}}{6n^2\pi_1}$ . The other traders satisfy WGS and $1\in G^h_s$ , so their demand for good 1 does not fall. Substituting into the displayed inequality and adding the nonnegative terms for $s\ne k$ ,

$\hat\pi\cdot Z(\pi) \ge \frac{\epsilon^2\alpha_k\hat\pi_n\hat w_{m+1,n}}{72n^3\pi_1} = \delta$

∎

LemmaBounded step length

For any $\pi\in\Pi^+$ , $\lVert Z(\pi)\rVert_2 \le 12n^2/\eta$ — bound $\sum_j|Z_j|$ by $\sum_jX_j + \sum_j\hat W_j$ , use $\frac{\max_k\pi_k}{\min_k\pi_k}\le5n/\eta$ on $\Pi^+$ and $\hat W_j\le2$ .

TheoremConvergence

With $\mu = \min\{\tfrac{\delta^2}{(12n^2/\eta)^2}, (\eta/4n)^2\}$ , within $n/\mu$ iterations the algorithm computes a price in $\Pi^+$ that is a weak $(1+\epsilon)$ -approximate equilibrium for $\hat M$ .

ProofEach iteration cuts the distance to a fixed equilibrium

Fix an equilibrium $\pi^*\in\Pi$ . If $\pi^{i-1}\notin\Pi^+$ , clamping moves no coordinate away from $\pi^*$ and moves some coordinate at least $\eta/4n$ toward it, so $\lVert\pi^*-\pi^{i-1}\rVert^2 - \lVert\pi^*-\pi^i\rVert^2\ge(\eta/4n)^2$ .

If $\pi^{i-1}\in\Pi^+$ and is not approximately optimal, the separation lemma gives $\pi^*\cdot Z(\pi^{i-1})\ge\delta$ , and Walras’ Law gives $(\pi^*-\pi^{i-1})\cdot Z(\pi^{i-1})\ge\delta$ . With $q = \pi^i-\pi^{i-1} = \frac{\delta}{(12n^2/\eta)^2}Z(\pi^{i-1})$ , the step-length bound gives $(\pi^*-\pi^{i-1}-q)\cdot q\ge0$ , whence

$\lVert\pi^*-\pi^{i-1}\rVert^2 - \lVert\pi^*-\pi^i\rVert^2 \ge (\pi^*-\pi^{i-1})\cdot q \ge \frac{\delta^2}{(12n^2/\eta)^2}$

Summing over $k$ iterations gives $k\mu\le\lVert\pi^*-\pi^0\rVert^2\le n$ .

∎

TheoremMain WGS result

For an exchange market $M$ satisfying WGS and equipped with an excess-demand oracle, the tâtonnement-based algorithm computes in time polynomial in the input and $1/\epsilon$ a sequence of prices, one of which is a weak $(1+\epsilon)$ -approximate equilibrium.

NotePicking the right one out of the sequence

We need an algorithm that recognizes an approximate equilibrium — it suffices that it assert a weak $(1+2\epsilon)$ -approximation whenever given a weak $(1+\epsilon)$ one. Since recognizing is an explicitly presented convex program, this is generally easy. Using the separation lemma with the ellipsoid method instead makes the dependence on $1/\epsilon$ polynomial in $\log(1/\epsilon)$ .

Convex programs for specific utilities

FormulaLinear exchange economies

With $u_i(x) = \sum_j a_{ij}x_{ij}$ and $w_{ij}>0$ , find $\psi_j$ and $x_{ij}\ge0$ with

$\sum_k a_{ik}x_{ik} \ge a_{ij}\sum_k w_{ik}e^{\psi_k-\psi_j} \quad\forall i,j, \qquad \sum_i x_i = \sum_i w_i$

Solutions correspond exactly to equilibria via $\pi_j = e^{\psi_j}$ , in both directions.

NoteExact solutions for linear utilities

For linear utilities an equilibrium price vector with small rational components exists. Jain exploits this in an ellipsoid variant using the above separating hyperplane to compute the equilibrium exactly in polynomial time; Ye gives an interior-point algorithm doing the same.

FormulaCES demand

For $u_i(x) = \big(\sum_j\alpha_{ij}x_{ij}^{\rho_i}\big)^{1/\rho_i}$ with $\alpha_{ij},w_{ij}>0$ and $-\infty<\rho_i<1$ , $\rho_i\ne0$ (and $u_i := 0$ if some $x_{ij}=0$ when $\rho_i<0$ , ensuring continuity), the demand is unique and

$x_{ij}(\pi) = \frac{\alpha_{ij}^{1/(1-\rho_i)}}{\pi_j^{1/(1-\rho_i)}}\times\frac{\sum_k\pi_kw_{ik}}{\sum_k\alpha_{ik}^{1/(1-\rho_i)}\pi_k^{-\rho_i/(1-\rho_i)}}$

TheoremCES with $-1\le\rho_i<0$ is a convex feasibility problem

Set $\rho = -1\le\rho_i$ , $f_{ij}(\pi) = \pi_j x_{ij}(\pi)$ and $\sigma_j = \pi_j^{1/(1-\rho)}$ . Equilibria are the $\sigma\in\mathbb{R}^n_{++}$ with $\sum_i f_{ij}(\sigma)\le\sigma_j\sum_i w_{ij}$ for each good — and each $f_{ij}$ is convex, so the right side being linear makes this a convex feasibility program.

ProofConvexity of

f_{ij}

It suffices that $f_{ij}\le t$ define a convex set for $t>0$ . Using the demand formula, rewriting and raising to the power $1/(1-\rho)$ , the constraint becomes

$\alpha_{ij}^{\frac{1}{1-\rho}}\Big(\sum_k\sigma_k^{1-\rho}w_{ik}\Big)^{\frac{1}{1-\rho}} \le t^{\frac{1}{1-\rho}}\,\sigma_j^{\frac{\rho_i-\rho}{(1-\rho)(1-\rho_i)}}\,v_i^{\frac{-\rho_i}{(1-\rho_i)(1-\rho)}}, \qquad v_i = \Big(\sum_k\alpha_{ik}^{\frac{1}{1-\rho_i}}\sigma_k^{\frac{-\rho_i(1-\rho)}{1-\rho_i}}\Big)^{\frac{-\rho_i(1-\rho)}{1-\rho_i}}$

The left side is convex; the right side is concave and nondecreasing in $t,\sigma_j,v_i$ , since the exponents are nonnegative and add up to one. Since $0<\frac{-\rho_i(1-\rho)}{1-\rho_i}\le1$ , the expression for $v_i$ is itself concave (a CES function), so substituting it keeps the right side concave.

∎

NoteAn unexpected corollary

The demand of such an economy need not satisfy WGS, so the connectedness of the equilibria implied by this convex formulation is a genuinely new consequence.

Limitations of convex programming

WarningDisconnected equilibria for CES with $\rho<-1$

Two traders, two goods. Trader 1 has $w_1 = (1,0)$ and $u_1(x,y) = ((ax)^\rho + y^\rho)^{1/\rho}$ ; trader 2 has $w_2 = (0,1)$ and $u_2(x,y) = ((x/a)^\rho+y^\rho)^{1/\rho}$ . For each $\rho<-1$ there is a sufficiently small $a$ for which

$(1/2,1/2)$ is an equilibrium price, and
$(p,1-p)$ is an equilibrium for some $p<1/2$ , while $(q,1-q)$ is not for any $p<q<1/2$ .

So the equilibria are multiple and disconnected. This economy therefore admits no convex programming formulation in terms of any “relative” of the prices — such a formulation would force every intermediate $p_3$ between two equilibrium prices to be one too. It is unlikely the CES results above extend past $\rho = -1$ .

ImportantLeontief exchange economies are PPAD-hard

Equilibrium computation belongs in TFNP, the class of total search problems: Nash’s theorem makes finding a Nash equilibrium total, and Arrow–Debreu gives sufficient conditions making market equilibrium total. The relevant subclass is PPAD.

The game–market correspondence. Take a bimatrix game $(A,B)$ with positive entries, $A$ of size $n\times m$ . Build a Leontief exchange economy with $n+m$ traders and $n+m$ goods: trader $i$ is endowed with one unit of good $i$ ; traders $j\in\{1,\ldots,n\}$ derive utility only from goods $\{n+1,\ldots,n+m\}$ , in proportions given by row $j$ of $B$ ; traders $j\in\{n+1,\ldots,n+m\}$ derive utility only from goods $\{1,\ldots,n\}$ , in proportions given by column $j$ of $A$ . The traders split into two groups bringing disjoint goods and interested only in the other group’s goods.

The Nash equilibria of $(A,B)$ are in one-to-one, polynomial-time computable correspondence with the market equilibria of this economy. (For this we must drop the convention of considering only positive-price equilibria; only then does the economy capture the complexity of bimatrix games.)

Combined with the PPAD-completeness of bimatrix Nash, computing a market equilibrium is PPAD-complete even for this restricted family of Leontief economies.

Models with production

Setup. A constant returns economy adds producers to the exchange model. Producer $k$ can make good $o_k$ from the $n$ goods via a concave, degree-1 homogeneous $f_k : \mathbb{R}^n_+\to\mathbb{R}_+$ : inputs $z_j$ produce up to $f_k(z_1,\ldots,z_n)$ units of $o_k$ .

ImportantProfit maximization is well defined only at zero profit

If some feasible plan makes strictly positive profit $\pi_{o_k}f_k(z) - \sum_j\pi_jz_j > 0$ , then scaling inputs by $\alpha>1$ scales the profit by $\alpha$ — so no profit-maximizing plan exists. A maximizing plan exists iff no feasible plan makes positive profit, in which case a maximizing plan makes zero profit, and the trivial plan $z=0$ always qualifies.

In terms of the unit cost function $c_k(\pi) = \min\{\sum_j\pi_jz_j : z\ge0,\ f_k(z)\ge1\}$ : if $\pi_{o_k}>c_k(\pi)$ maximization is undefined; if $\pi_{o_k}<c_k(\pi)$ only the trivial plan maximizes; if $\pi_{o_k} = c_k(\pi)$ , the trivial plan and any $z$ with $f_k(z)c_k(\pi) = \sum_j\pi_jz_j$ all maximize.

DefinitionEquilibrium with production

Prices $\pi$ , consumer bundles $x_i$ and producer input bundles $z_k$ with output $q_{ko_k} = f_k(z_k)$ , such that (i) profit maximization is well defined at $\pi$ and each plan is profit-maximizing; (ii) each $x_i$ is consumer $i$ ‘s demand; and (iii) the market clears: $\sum_ix_{ij}+\sum_kz_{kj}\le\sum_iw_{ij}+\sum_{k:j=o_k}q_{kj}$ .

Requirement (i) rules out the trivial approach of ignoring the production units and computing an exchange equilibrium.

DerivationTransforming to a market with trivial consumption

Transform $M$ into $M'$ with $m$ consumers, $n+m$ goods and $l+m$ producers. Add a good $n+i$ per consumer, and set $u_i'(x) = x_{n+i}$ — consumer $i$ now wants only good $n+i$ . Endowments are unchanged on the first $n$ goods and zero after. The first $l$ producers are unchanged; the $(l+i)$ th produces good $n+i$ with technology $f'_{l+i}(z) = u_i(z_1,\ldots,z_n)$ . There is a one-to-one correspondence between equilibria of $M$ and $M'$ , and the simplicity of $M'$ ‘s consumption side is what makes the characterization tractable.

FormulaInequalities characterizing equilibrium of $M'$

In variables $\pi_j\ge0$ , consumer demands $x_{i,n+i}$ , producer inputs $z_k$ and outputs $q_{ko_k}$ :

$\pi_{n+i}x_{i,n+i}\ \ge\ \sum_{j=1}^n\pi_jw_{ij}\tag{a}$ $q_{ko_k}\ \le\ f_k(z_k)\tag{b}$ $\pi_{o_k}\ \le\ c_k(\pi_1,\ldots,\pi_n)\tag{c}$ $\sum_kz_{kj}\ \le\ \sum_iw_{ij}+\sum_{k:o_k=j}q_{kj}\tag{d}$ $x_{i,n+i}\ \le\ q_{l+i,n+i}\tag{e}$

ProofWhy any feasible solution is an equilibrium

Evidently every equilibrium is feasible. Conversely, (b) and (c) imply no producer makes positive profit: $\sum_{j\le n}\pi_jz_{kj}\ge\pi_{o_k}q_{ko_k}$ . Adding these and (a) shows the cost of consumer and producer demands is at least the cost of endowments and outputs; multiplying (d) and (e) by prices and adding shows it is at most that. Hence the two are equal, forcing $\sum_{j\le n}\pi_jz_{kj} = \pi_{o_k}q_{ko_k}$ — every plan makes exactly zero profit and, by (c), is optimal — and forcing equality in (a), so $x_{i,n+i}$ is the demand. Conservation follows from (d) and (e).

∎

ImportantThe substitution that convexifies everything

Put $\pi_j = e^{\psi_j}$ . All constraints become convex except possibly (c). For a CES production function with $0<\rho<1$ the unit cost is $c_k(\pi) = \big(\sum_ja_{kj}^\sigma\pi_j^{1-\sigma}\big)^{1/(1-\sigma)}$ with $\sigma = 1/(1-\rho)$ ; raising both sides to the power $1-\sigma<0$ turns (c) into

$\pi_{o_k}^{1-\sigma} \ge \sum_j a_{kj}^\sigma\pi_j^{1-\sigma}$

which the substitution makes convex. The same holds for linear and Cobb–Douglas production.

So we obtain convex programs for constant-returns economies whose utility and production functions are linear, Cobb–Douglas, or CES with $\rho>0$ — and for a family of nested CES functions. Interestingly, using production technologies to simplify the consumption side is also the key to convex programs for pure exchange economies with nested CES utilities.

Discussion and open problems

WarningLinear utilities are easy but unrealistic

Linear functions gave us the easiest algorithmic questions with which to commence the study — but they are much too restrictive to be useful. Concave utilities are considered especially useful in economics because they model decreasing marginal utilities. If strictly concave, each agent has a unique optimal bundle at any prices, which yields a remarkable communication-complexity fact: it suffices to announce equilibrium prices — all agents can then individually compute and buy their optimal bundles and the market clears.

ImportantWhy concavity breaks the ascending-price approach

The approach of starting at very low prices and raising them is made possible by weak gross substitutability: raising one good’s price never lowers another’s demand, so the need to decrease a price never arises. Concave utility functions do not satisfy WGS.

Open: does the piecewise-linear-concave approach yield an efficient algorithm, exactly or approximately? If so, general concave functions could be handled by approximation. Alternatively, can one show finding an equilibrium for such utilities is PPAD-hard?

NoteOther open problems

Given the properties in the Fisher-equilibria theorem, can equilibrium allocations for the linear Fisher case be captured by a linear program? Resolving this either way seems exciting.
Is there a strongly polynomial algorithm for the linear Fisher case? The dependence on the buyers’ money in the potential function is what currently blocks this.
Numerous questions remain for a deeper algorithmic understanding of Eisenberg–Gale markets generally.

Quick reference

Object	Statement
Fisher model	buyers with money $e_i$ , linear utilities $u_{ij}$ ; find market-clearing prices
Arrow–Debreu	agents with endowments $e_i$ ; sell, then buy optimal bundles
Fisher $\subset$ Arrow–Debreu	money as the $(n{+}1)$ st good, plus one agent endowed with all goods
Walras’ Law	$\pi\cdot Z(\pi) = 0$
WGS	raising some prices cannot lower demand for the fixed-price goods $\Rightarrow$ equilibrium unique up to scaling
Eisenberg–Gale	$\max\sum_i e_i\log u_i$ s.t. packing constraints; duals are prices
Fisher linear equilibria	exist, form a convex set, have unique utilities and prices, and are rational
Bang per buck	$\alpha_i = \max_j u_{ij}/p_j$ ; equality subgraph has edge $(i,j)$ iff attained
Equilibrium test	both $(s,A\cup B\cup t)$ and $(s\cup A\cup B,t)$ min-cuts in $N(p)$
Invariant	$(s,A\cup B\cup t)$ is a min-cut $\iff \forall S: p(S)\le m(\Gamma(S))$
Tight set	$p(S) = m(\Gamma(S))$ ; freeze its prices
Balanced flow	minimizes $\lVert\gamma\rVert_2$ ; unique surplus vector; Property 1
Primal-dual running time	$O(n^4(\log n + n\log U + \log M))$ max-flows
Auction (Arrow–Debreu)	$(1-\epsilon)^2$ -optimal bundles; $O\big(\frac{mn}{\epsilon^2}\log\frac{nv_{\max}}{\epsilon a_{\min}v_{\min}}\log\frac{v_{\max}}{v_{\min}}\big)$
Kelly’s program	$\max\sum_i m_i\log f_i$ s.t. capacities; proportionally fair
Single-source flow market	$O(r^2)$ max-flows, $r$ = number of sinks — strongly polynomial
WGS separation	$\hat\pi\cdot Z(\pi)>0$ for non-equilibrium $\pi$
Discrete tâtonnement	weak $(1+\epsilon)$ -approximate equilibrium in poly $(n,1/\epsilon,1/\eta)$
Linear exchange	convex feasibility in $\psi_j = \log\pi_j$ ; exact solution in poly time
CES, $-1\le\rho_i<0$	convex feasibility in $\sigma_j = \pi_j^{1/(1-\rho)}$
CES, $\rho<-1$	multiple disconnected equilibria — no convex formulation
Leontief exchange	PPAD-complete, via the bimatrix game–market correspondence
Production, CES $\rho>0$	convex after $\pi_j = e^{\psi_j}$ ; also linear and Cobb–Douglas

Facts to keep to hand:

Both combinatorial algorithms are ascending price — and that is legitimate only because linear utilities satisfy WGS, so no price ever needs to come back down.
The primal-dual algorithm’s two inventions answer two separate needs: tight sets stop prices overshooting, balanced flows guarantee fast surplus reduction.
KKT conditions mix primal and dual variables, unlike LP complementary slackness — which is why the equality subgraph churns and why the algorithm satisfies conditions continuously rather than in discrete steps.
The algorithm is polynomial but not strongly polynomial, because $\Phi$ ‘s starting value depends on the buyers’ money and hence on the input length.
Eisenberg–Gale’s objective is forced by two requirements: scale invariance and splitting, which the money-weighted geometric mean uniquely satisfies.
Kelly’s resource allocation program has the same structure as Eisenberg–Gale, which is how TCP congestion control connects to market equilibrium.
In the WGS analysis, the added Cobb–Douglas trader does two jobs: forces all prices positive (existence) and bounds the price spread (compactness).
The convexity frontier sits at CES $\rho = -1$ : above it convex feasibility works; below it equilibria disconnect, and at the Leontief extreme the problem is PPAD-complete.

References

Nisan, Roughgarden, Tardos & Vazirani, Algorithmic Game Theory — chapters 5 (Vazirani) and 6 (Codenotti & Varadarajan)

Related

Motivation: an algorithmic theory of markets

The two models

Utility functions and approximation

Gross substitutability

The Eisenberg–Gale convex program

The combinatorial algorithm for Fisher’s linear case

Checking whether given prices are equilibrium prices

The two crucial ingredients

Tight sets and the Invariant

Balanced flows

The main algorithm

Finding tight sets

Running time

Auction-based algorithm for Arrow–Debreu

Kelly’s resource allocation markets

Single-source multiple-sink flow markets

Convex programming for the Fisher model

Exchange economies satisfying WGS

Two transformations

The discrete tâtonnement process

Convex programs for specific utilities

Limitations of convex programming

Models with production

Discussion and open problems

Quick reference

References

Mentioned in