1 Introduction↩︎

Walrasian economies, introduced by French economist Léon Walras in 1874, are a broad mathematical framework for modeling any economic system governed by supply and demand [1]. A Walrasian economy consists of a finite set of commodities, characterized by an excess demand function that maps values for commodities, called , to positive (resp. negative) quantities of each commodity demanded (resp. supplied) in excess. Walras proposed a steady-state solution of his economy namely a collection of per-commodity prices which is , i.e., there is no excess demand for any commodity, and for which holds, i.e., the value of the excess demand is equal to 0. We call such a solution a Walrasian (or competitive) equilibrium.

Walras did not establish conditions ensuring the existence of an equilibrium, leaving the question unresolved until the 1950s [2], but argued that his economy would settle at a Walrasian equilibrium via a (i.e., any process that generates a sequence of prices based on prior prices and associated excess demands), known as , which mimics the behavior of the , updating prices at a rate equal to the excess demand [1], [3], [4]. To motivate the relevance of tâtonnement to real-world economies, Walras argued that tâtonnement is a price-adjustment process, in the following sense: if each commodity is owned by a different seller, then each seller can update the price of its commodity, using only information about the excess demand of its commodity, without coordinating with other sellers. It is thus plausible that tâtonnement could explain the movement of prices in real-world economies.

Nearly half a century after Walras’ initial foray into general equilibrium analysis, a group of academics brought together by the Cowles Commission in 1939 reinitiated a study of Walras’ economic model with the aim of bringing rigorous mathematics to the analysis of markets. One of the earliest and most important outputs of this collaborative effort was the introduction of a broad and well-justified class of Walrasian economies known as [2], for which the existence of Walrasian equilibrium was established by a novel application of fixed point theorems to economics. With the question of existence thus resolved, the field subsequently turned its focus to questions on the of Walrasian equilibrium, i.e., which price-adjustment processes can settle at a Walrasian equilibrium and under which assumptions [3]–[12]?

Most relevant work on stability has been concerned with the convergence properties of tâtonnement. Beyond Walras’ justification for tâtonnement’s relevance to real-world economies, research on tâtonnement in the post-World-War-II economics literature is motivated by the fact that it can be understood as a plausible explanation of how prices move in real-world markets [13]. Hence, if one could prove that tâtonnement is a price-adjustment process, i.e., one that converges to a Walrasian equilibrium in all competitive economies, then perhaps it would be justifiable to claim real-world economies would also eventually settle at a Walrasian equilibrium.

In 1958, [4] established the convergence of a continuous-time variant of tâtonnement in Walrasian economies with an excess demand function satisfying the weak axiom of revealed preferences (WARP) [14], which among others, includes Walrasian economies satisfying (i.e., the excess demand of any commodity can only increase when the price of another commodity increases, fixing all other prices) [15], [16]. This result was complemented by [17]’s ([17]) result on the convergence of a discrete-time variant of tâtonnement in Walrasian economies satisfying WARP—albeit without any non-asymptotic convergence guarantees. These initial results sparked hopes that tâtonnement could be a universal price-adjustment process.

Furthermore, as Walrasian equilibria in general cannot be expressed in closed form, these results ignited further interest in discovering algorithms to compute a Walrasian equilibrium, as tâtonnement could be implemented on a computer to obtain numerical approximations of Walrasian equilibria in Walrasian economies. Indeed, these early results on the stability of tâtonnement inspired a new line of work on [18]–[21] initiated by Herbert Scarf [22], whose goal was to establish “a general method for the explicit numerical solution of the neoclassical [Walrasian economy] model” [20]. The motivation behind this research agenda was a desire to predict the impact of economic policy on an economy by estimating the parameters of a parametric Walrasian economy from empirical data, and then running a comparative static analysis to compare the numerical solution of the Walrasian economy before and after the implementation of the policy.

Soon after this research agenda was initiated, Scarf dashed all hopes that tâtonnement could be a universal price-adjustment process by exhibiting a competitive economy with only three commodities and an excess demand function generated by three consumers with Leontief preferences, i.e., , for which the sequence of prices generated by a continuous-time variant of tâtonnement cycles ad infinitum around the unique Walrasian equilibrium [23]. Even more disheartening, the prices generated by discrete-time variants of tâtonnement, when applied to the Scarf economy, spiral farther and farther away from the Walrasian equilibrium.

Scarf’s negative result seems to have discouraged further research by economists on the stability of Walrasian equilibrium [24]. Despite research on this question coming to a near halt, one positive outcome was achieved, on the convergence of a non-tâtonnement update rule known as [25]–[28], which updates prices at the rate of the product of the excess demand and the inverse of its Jacobian, to a Walrasian equilibrium in competitive economies that have an excess demand with a non-singular Jacobian, including Scarf economies. Unfortunately, this convergence result for Smale’s process comes with two caveats: 1) Smale’s process is not a “natural" price-adjustment process, as it updates the price of each commodity using information not only about the excess demand of the commodity but also the derivative of the excess demand function with respect to each commodity in the economy, 2) convergence of discrete time-variants of Smale’s process requires the excess demand to satisfy the law of supply and demand, which even Walrasian economies that satisfy the GS or WARP conditions need not satisfy.

Nearly half a century after these seminal analyses of competitive economies, research on the stability and efficient computation of Walrasian equilibrium is once again coming to the fore, motivated by applications of algorithms to compute Walrasian equilibrium in dynamic stochastic general equilibrium models in macroeconomics [29]–[32], and the use of algorithms such as tâtonnement to solve models of transactions on crypotocurrency blockchains [33]–[35] and load balancing over networks [36]. In contrast to the prior literature on the stability of tâtonnement, which was primarily concerned with proving asymptotic convergence of price-adjustment processes to Walrasian equilibria, this line of work is also concerned with obtaining non-asymptotic convergence rates, and hence computing approximate Walrasian equilibria in polynomial time.

The first result on this question is due to [10], who introduced a discrete-time version of tâtonnement, and showed that in exchange economies that satisfy (i.e., the excess demand of any commodity weakly increases if the price of any other commodity increases, fixing all other prices), the tâtonnement process converges to an approximate Walrasian equilibrium in a number of steps polynomial in the inverse of the approximation factor and the size of the problem. Soon after this positive result appeared, [37] argued that no natural (i.e., decentralized)¹ price-adjustment process based on excess demand can converge to a Walrasian equilibrium in polynomial time in general in competitive economies, thus ruling out the possibility of Smale’s process (and many others) justifying the notion of Walrasian equilibrium. Nonetheless, further study of the convergence of price-adjustment processes such as tâtonnement under stronger assumptions, or in simpler models than full-blown Arrow-Debreu competitive economies, continued, as these processes are being deployed in practice [33]–[36].²

1.1 A Tractable Variational Inequality Framework for Walrasian Economies↩︎

The intent of this paper is to bridge the gap between the practical relevance of tâtonnement and [37]’ [37] impossibility result. To do so, we employ the variational inequality (VI) optimization framework [38], exploiting a well-known connection between (Walrasian) VIs and Walrasian economies, namely that the set of Walrasian equilibria of any Walrasian economy can be characterized as the solution set of an associated complementarity problem (i.e., a VI where the constraint set is the positive orthant) [39]. Within the VI framework, we study the class of algorithms [40],³ which is known [41] to converge in polynomial time to a strong solution in VIs that satisfy a computational tractability condition known as the Minty condition [42] and a generalization of Lipschitz continuity known as Bregman (or relative [43]) continuity. Applied to Walrasian VIs, mirror extragradient corresponds to a novel, natural price-adjustment process we call .

Our focus in this paper is on , a class of Walrasian economies that includes among others Arrow and Debreu’s competitive economies [2]. In a balanced economy, excess demand is a homogeneous correspondence of degree \(0\), and weak Walras’ Law is satisfied (i.e., the value of the excess demand is less than or equal to \(0\)). While it is known [39] that the set of Walrasian equilibria of balanced economies is equal to the set of strong solutions of the \((\R_+^\numgoods,-\excessset)\), where \(\numgoods\) is the number of goods and \(\excessset\) is the excess demand correspondence, we observe that this connection extends to the modified Walrasian VI \(([0,1]^\numgoods, -\excessset)\), which we call the , and to the modified Walrasian VI \((\simplex[\numgoods], -\excessset)\), which we call the . [37] restrict their attention to price-adjustment processes that generate prices in the unit simplex. The simplex VI, however, can fail to satisfy the Minty condition, and accordingly, can be computationally intractable. On the other hand, by relaxing this requirement, so that prices instead lie in the unit box, the Minty condition is satisfied, with \(\zeros[m]\) as the Minty solution. Consequently, if the excess demand correspondence can be shown to satisfy something like Bregman continuity, we can apply mirror extratâtonnement to solve it.

This observation suggests a plan of attack by which to overcome [37]’ impossibility result, and instead allow for the efficient computation of Walrasian equilibrium, at least in practice. The reader might wonder what we mean by “in practice”.

As it turns out, the box VI is Bregman discontinuous at one point in its search space, namely the Minty solution, i.e., when all prices are \(0\). It is thus impossible to simultaneously ensure both the Minty condition and Bregman continuity of excess demand on the unit box in general. Moreover, the only balanced economies with Lipschitz-continuous excess demand on the unit box are those with a constant excess demand. It is therefore not possible to obtain any meaningful polynomial-time convergence results for mirror extratâtonnement applied to the box VI without further assumptions. Nevertheless, in our experiments, we observe the fast convergence of mirror extratâtonnement in a large class of competitive economies, including very large instances with Leontief consumers, for which the computation of a Walrasian equilibrium is known to be PPAD-complete [11], [44]. To explain this empirical observation, we introduce a assumption, which requires Bregman-continuous excess demand only along the sequence of prices generated by mirror extratâtonnement. We prove that this condition is sufficient to guarantee polynomial-time convergence to a Walrasian equilibrium in balanced and thus also competitive economies.

In [chap:vis], after reviewing background material on variational inequalities, we introduce two new types of methods with polynomial-time convergence guarantees.

The first type of methods is a family of first-order methods known as the mirror extragradient method. We prove that this method converges to a strong solution of any variational inequality for which a weak solution exists. Furthermore, in the absence of a weak solution, we establish local convergence to a strong solution when the algorithm’s first iterate is initialized sufficiently close to a local weak solution. Since first-order methods are not guaranteed to converge beyond settings where a (local) weak solution exists, we then turn our attention to a class of second-order methods known as merit function methods. In particular, we introduce the primal mirror descent, which we show is guaranteed to converge to a local minimum of the regularized primal gap function of any Lipschitz-smooth variational inequality.

In [chap:walrasian_economies], after reviewing background material on Walrasian economies, we demonstrate that the set of Walrasian equilibria of any Walrasian economy is equivalent to the set of strong solutions of an associated variational inequality. Additionally, we show that applying the gradient method to this variational inequality corresponds to solving the Walrasian economy through a well-known price-adjustment process known as tâtonnement. Extending this analysis, we introduce a new family of price-adjustment processes, termed the mirror extratâtonnement process, by applying the mirror extragradient method to the variational inequality formulation. Leveraging results from the prior section, we establish that this process converges to a Walrasian equilibrium in all Walrasian economies whose excess demand satisfies the Weak Axiom of Revealed Preferences (WARP).

As neither tâtonnement nor extratâtonnement processes are guaranteed to converge beyond this class of Walrasian economies, we introduce a class of merit function methods tailored for Walrasian economies with a Lipschitz-smooth excess demand. These methods are guaranteed to converge to a local minimum of the regularized primal gap function of any Lipschitz-smooth variational inequality. Our approach provides a novel perspective on Walrasian equilibria through the lens of variational inequalities, enabling the design of price-adjustment processes with strong theoretical guarantees. Additionally, we validate our framework through numerical experiments on large Arrow-Debreu economies with Cobb-Douglas, Leontief, and CES consumers, as well as the Scarf economy, demonstrating robust convergence in all cases. These results suggest that the computational intractability of general equilibrium models primarily arises from discontinuities rather than fundamental algorithmic limitations, addressing a long-standing challenge posed by Herbert Scarf regarding the explicit numerical solution of neoclassical equilibrium models.

1.2 Technical Contributions↩︎

1.2.0.1 Variational Inequalities

Our first contribution is an analysis of the class of constrained mirror extragradient algorithms, a generalization of Korpelevich’s extragradient method [45] for solving VIs. For VIs that satisfy the Minty condition and are Bregman continuous, we establish best-iterate convergence to an \(\varepsilon\)-strong solution in \(O(\frac{1}{\varepsilon^2})\) evaluations of the VI’s optimality operator ([thm:mirror95extragradient95global95convergence]). Our result generalizes the results and proof techniques of [46] for the extragradient method, and extends the convergence results of [41] for the unconstrained mirror extragradient method to constrained domains. In addition, we establish suitable conditions for the local convergence of the mirror extragradient algorithm to an \(\varepsilon\)-strong solution of any Bregman-continuous VI that does not satisfy the Minty condition—to the best of our knowledge, the first result of its kind ([thm:vi95mirror95extragrad95local]).

1.2.0.2 Walrasian Economies

It is known that the set of Walrasian equilibria of any Walrasian economy can be characterized as the solution set of an associated complementarity problem (i.e., a VI where the constraint set is the positive orthant) [39]. For balanced economies, however, we provide the first computationally tractable characterization of Walrasian equilibria as the set of scalar multiples (\(\geq 1\)) of the set of strong solutions of a box VI. As the box trivially satisfies the Minty condition, we apply the mirror extragradient method to obtain a novel natural price-adjustment process we call mirror extratâtonnement (5), and establish its polynomial-time convergence in all balanced economies that satisfy pathwise Bregman continuity (2).

Next, we apply these insights to the Scarf economy. First, we observe that the Scarf economy is balanced (7). Then, we prove polynomial-time convergence of mirror extratâtonnement to the unique Walrasian equilibrium of the Scarf economy ([thm:scarf95convergence]). As such, the mirror extratâtonnement process is the first discrete-time natural price-adjustment process known to converge in the Scarf economy.

While the pathwise Bregman continuity assumption provides intuition for the fast convergence of mirror extratâtonnement in practice, it is hard to verify this assumption analytically, in advance of running the process. We obtain stronger theoretical results by restricting our attention to competitive economies with (i.e., the change in excess demand as prices change is bounded across all price changes) that are [47] on the unit simplex (i.e., simplex VIs for which the Minty condition holds) . We show that under these assumptions, the excess demand is Bregman continuous, thus providing the first polynomial-time convergence result for a natural price-adjustment process in this broad class of Walrasian economies, which includes economies that satisfy weak GS , and more generally, WARP.

We then restrict our attention to competitive economies, the special case of balanced economies that are variationally stable on the unit simplex. We establish polynomial-time convergence of mirror extratâtonnement in all such economies assuming bounded elasticity of excess demand, bounded aggregate demand, and bounded aggregate supply (3). This convergence result provides the first polynomial-time convergence result for price-adjustment processes in WARP economies with bounded elasticity of excess demand, thereby generalizing the well-known tâtonnement convergence result in weak GS [10] to such economies.

Finally, we run experiments (5) which demonstrate that mirror extratâtonnement converges to a Walrasian equilibrium in a variety of large (600, 800, or 1000 consumers and 500 or 1000 commodities) competitive economies, including some of which are known to be PPAD-complete (e.g., Leontief economies). The convergence rate matches our theory because we first conduct a search for an appropriate step size, meaning one that ensures pathwise Bregman continuity. In particular, convergence is fast in all economies except those with linear consumers, where our convergence bounds are weak due to the magnitude of the pathwise Bregman continuity coefficient. We conclude with an additional set of experiments using step sizes that violate pathwise Bregman continuity, but we nonetheless observe a similar pattern of convergence.

2 Preliminaries↩︎

2.0.0.1 Notation.

We use caligraphic uppercase letters to denote sets (e.g., \(\calX\)), bold uppercase letters to denote matrices (e.g., \(\allocation\)), bold lowercase letters to denote vectors (e.g., \(\price\)), lowercase letters to denote scalar quantities (e.g., \(x\)). We denote the \(i\)th row vector of a matrix (e.g., \(\allocation\)) by the corresponding bold lowercase letter with subscript \(i\) (e.g., \(\allocation[\buyer])\). Similarly, we denote the \(j\)th entry of a vector (e.g., \(\price\) or \(\allocation[\buyer]\)) by the corresponding lowercase letter with subscript \(j\) (e.g., \(\price[\good]\) or \(\allocation[\buyer][\good]\)). We denote functions by a letter determined by the value of the function, e.g., \(f\) if the mapping is scalar valued, \(\f\) if the mapping is vector valued, and \(\calF\) if the mapping is set valued (i.e., \(\calF\) is a correspondence). If a correspondence \(\calF\) happens to be singleton valued, we overload notation and denote it by \(\f\). We denote the set \(\left\{1, \ldots, n\right\}\) by \([n]\), the set of natural numbers by \(\N\), and the set of real numbers by \(\R\). We denote the positive and strictly positive elements of a set using a \(+\) or \(++\) subscript, respectively (e.g., \(\R_+\) and \(\R_{++}\)).

For any \(n \in \N\), we denote the \(n\)-dimensional vector of zeros and ones by \(\zeros[n]\) and \(\ones[n]\), respectively, and the \(i^{th}\) basis vector in \(\R^n\) by \(\basis[i]\). We let \(\simplex[n] = \{\x \in \R_+^n \mid \sum_{i = 1}^n x_i = 1 \}\) denote the unit simplex in \(\R^n\). Unless otherwise noted, the norm notation denotes the 2-norm, i.e., \(\| \cdot \| \doteq \| \cdot \|_2\), and we denote the Euclidean projection operator onto a set \(C\) by \(\project[C]\), i.e., \(\project[C](\x) \doteq \argmin_{\y \in C} \left\|\x - \y \right\|^2\). Given a metric space \((\metricspace, \metric)\) and \(\varepsilon \geq 0\), we write \(\closedball[\varepsilon][\var] = \{ \var[\prime] \in \metricspace \mid \metric(\var, \var[\prime]) \leq \varepsilon \}\) to denote the closed \(\varepsilon\)-ball centered at \(\var \in \metricspace\). The multiplication of a scalar and a set is defined as the Minkowksi product, i.e., for all \(a \in \R\) and \(\set \subseteq \R^\numgoods\), we define \(a \set \doteq \{a \vartuple \mid \vartuple \in \set \}\).

2.0.0.2 Functions.

Given a Euclidean vector space \(\set \subseteq \R^n\), we define its dual space \(\set^*\) as the set of all linear maps \(\vioper: \set \to \R^d\). Let \((\set, \norm_{\set})\) and \((\otherset, \norm_{\otherset})\) be normed spaces. A function \(\vioper: \set \to \otherset\) is if for all sequences \(\left\{ \var[(n)] \right\}_{n \in \N}\) s.t.\(\var[(n)] \to \var \in \set\), it holds that \(\obj(\var[(n)]) \to \obj(\var)\). Given \(\lipschitz \geq 0\), \(\vioper\) is said to be \(\lipschitz\)- on \(\calA \subseteq \set\) iff for all \(\x_1, \x_2 \in \calA, \left\| \obj(\x_1) - \obj(\x_2) \right\|_{\otherset} \leq \lipschitz \left\| \x_1 - \x_2 \right\|_{\set}\). If \(f\) is differentiable, then it is \(\lipschitz\)- if its gradient is \(\lipschitz\)-Lipschitz continuous. A function \(\obj: \set \to \R\) is iff for all \(\lambda \in [0,1]\) and \(\vartuple, \vartuple[][\prime] \in \set\), \(\obj (\lambda \vartuple + (1-\lambda) \vartuple[][\prime]) \leq \lambda \obj(\vartuple) + (1-\lambda) \obj(\vartuple[][\prime]) \enspace .\) Given \(\sconvex \geq 0\), \(\obj\) is \(\sconvex\)-strongly-convex iff \(\vartuple \mapsto \obj(\vartuple) - \frac{\sconvex}{2}\| \vartuple\|^2\) is convex.

2.0.0.3 Correspondences.

Let \((\set, \innerprod)\) be an inner product space. A correspondence \(\relation: \set \rightrightarrows \set^*\) is said to be if for any sequence \(\{(\var[(n)], y^{(n)}) \}_{n \in \N} \subset \set \times \set^*\) that converges to \((\var, y)\) with \(y^{(n)} \in \relation(\var[(n)])\), for all \(n \in \N\), it also holds that \(y \in \relation(\var)\). \(\relation\) is if for any sequence \(\left\{ \var[(n)] \right\}_{n \in \N} \subset \set\) that converges to \(\var\) it also holds that \(\relation(\var[(n)]) \to \relation(\var)\). \(\relation\) is said to be (resp. / / ) iff for all \(\var \in \set\), \(\relation(\var)\) is closed (resp.compact / convex / a singleton). \(\relation\) is iff for all \(\var, \var[\prime] \in \set\) and \(\othervar \in \relation(\var), \othervar[\prime] \in \relation(\var[\prime])\), \(\left< \othervar[\prime] - \othervar, \var[\prime] - \var \right> \geq 0.\) \(\relation\) is iff for all \(\var, \var[\prime] \in \set\), \(\othervar \in \relation(\var)\), and \(\othervar[\prime] \in \relation(\var[\prime])\), \(\left< \othervar, \var[\prime] - \var \right> \geq 0 \, \text{ implies } \left< \othervar[\prime], \var[\prime] - \var \right> \geq 0\). \(\relation\) is iff for all \(\var, \var[\prime] \in \set\), \(\othervar \in \relation(\var)\), and \(\othervar[\prime] \in \relation(\var[\prime])\), \(\left< \othervar, \var[\prime] - \var \right> > 0 \, \text{ implies } \left< \othervar[\prime], \var[\prime] - \var \right> \geq 0\). We note the following relationship between these notions of monotonicity: \(\mathrm{monotone} \implies \mathrm{pseudomonotone} \implies \mathrm{quasimonotone}\).

2.0.0.4 Bregman divergence

Given a set \(\set\) and a \(\kernel: \set \to \R\), the \(\divergence[\kernel]: \set \times \set \to \R\) associated with \(\kernel\) is defined as \(\divergence[\kernel](\vartuple, \othervartuple) \doteq \kernel(\vartuple) - \kernel(\othervartuple) - \innerprod[{\grad \kernel(\othervartuple)}][{\vartuple - \othervartuple}].\) If \(\kernel\) is convex, then the Bregman divergence is non-negative. If \(\kernel\) is strictly convex, then \(\divergence[\kernel](\vartuple, \othervartuple) = 0\) iff \(\vartuple = \othervartuple\). If \(\kernel\) is \(\sconvex\)-strongly convex, then for all \(\vartuple, \othervartuple \in \set\), we have \(\divergence[\kernel](\vartuple, \othervartuple) \geq \frac{\sconvex}{2} \| \vartuple - \othervartuple\|^2\). When the kernel function is chosen s.t.\(\kernel(\vartuple) \doteq \frac{1}{2}\norm[\vartuple]^2\), then the Bregman divergence corresponds to Euclidean square distance, i.e., \(\divergence[\kernel][\vartuple][{\othervartuple}] \doteq \frac{1}{2} \norm[{\vartuple - \othervartuple}]^2\). Given a modulus of continuity \(\lsmooth \geq 0\) and a kernel function \(\kernel\), a function \(\vioper: \set \to \otherset\) is said to be (or relatively continuous [43]) on \(\calA \subseteq \set\) iff for all \(\vartuple, \othervartuple \in \calA\), \(\frac{1}{2} \norm[\vioper(\vartuple) - \vioper(\othervartuple)]^2 \leq \lsmooth^2 \divergence[\kernel][{\vartuple}][{\othervartuple}]\).

3 Variational Inequalities↩︎

Consider an inner product space \((\universe, \innerprod)\). A , denoted \((\set, \vioperset)\), comprises a \(\set \subseteq \universe\) and an \(\vioperset: \universe \rightrightarrows \universe^*\). For notational convenience, for any \(\vartuple \in \set\), we denote any arbitrary element of \(\vioperset(\vartuple)\) by \(\vioper(\vartuple)\), and denote the variational inequality by \((\set, \vioper)\) when \(\vioperset\) is singleton-valued.⁴

Any VI \((\set, \vioperset)\) defines a problem known as the [38]: \[\begin{align} &\text{Find } \vartuple[][*] \in \set \text{ such that } &\innerprod[{\vioper(\vartuple[][*])}][{\vartuple - \vartuple[][*]}] \geq 0 && \text{for all } \vartuple \in \set\\ &\text{and for some } &\vioper(\vartuple[][*]) \in \vioperset(\vartuple[][*]) \end{align}\]

3.0.1 Solution Concepts↩︎

A solution to a SVI is called a of the variational inequality \((\set, \vioperset)\). Just like in convex optimization settings (see Section 1.1.2 of [48]), in practice, it is not possible to compute an exact strong solution to a VI \((\set, \vioperset)\), and as such we have to resort to approximate solutions which we call the \(\vepsilon\)-strong solution. Note that in the following definition, in line with the literature (see, for instance Section 1.2 of [49]), the inequality is negated (and as such inverted).

3.1 Solution Concepts and their Properties↩︎

The canonical solution concept for VIs is the strong, or [38], solution. In practice, it is not possible to compute an exact strong solution to an arbitrary VI \((\set, \vioperset)\),⁵ so we resort to an approximate solution. Given an \(\vepsilon \geq 0\), an \(\vepsilon\)- (or \(\vepsilon\)-) of the VI \((\set, \vioperset)\) is an \(\vartuple[][*] \in \set\) s.t.for all \(\vartuple \in \set\), there exists an \(\vioper(\vartuple[][*]) \in \vioperset(\vartuple[][*])\) s.t.\(\innerprod[{\vioper(\vartuple[][*])}][{\vartuple[][*] - \vartuple }] \leq \vepsilon\). A \(0\)-strong solution is simply called a . We denote the set of \(\varepsilon\)-strong (resp.the set of strong) solutions of a VI \((\set, \vioperset)\) by \(\svi[\varepsilon](\set, \vioperset)\) (resp.\(\svi(\set, \vioperset)\)).

Strong solutions are known to exist in a broad of class of VIs known as continuous. A VI is a VI \((\set, \vioperset)\) s.t.\(\set\) is non-empty, compact, and convex and \(\vioperset\) is upper hemicontinuous, non-empty-, compact-, and convex-valued. One can establish the existence of a strong solution in a continuous VI by defining a mapping whose fixed points correspond to the strong solutions of the VI, and then invoking the Glicksberg-Kakutani fixed point theorem. We refer the reader to Theorem 2.2.1 of [51].

An alternative but related solution to a VI is the weak (or Minty) solution [42], for which we can once again define an approximate variant for computational purposes. Given a VI \((\set, \vioperset)\) and an \(\vepsilon \geq 0\), an is an \(\vartuple[][*] \in \set\) s.t.for all \(\vartuple \in \set, \vioper(\vartuple) \in \vioperset(\vartuple)\), it holds that \(\innerprod[{\vioper(\vartuple)}][{\vartuple[][*] - \vartuple}] \leq \vepsilon\). A \(0\)-weak solution to the VI is simply called a . We denote the set of \(\varepsilon\)-weak (resp.the set of weak) solutions a VI \((\set, \vioperset)\) by \(\mvi[\varepsilon](\set, \vioperset)\) (resp.\(\mvi(\set, \vioperset)\)).

In continuous VIs, \(\svi\) is a refinement of \(\mvi\), so that any weak solution is also strong. Surprisingly, an \(\vepsilon\)-weak-solution is not guaranteed to be \(\vepsilon\)-strong. If the optimality operator \(\vioperset\) is monotone though, the set of strong and weak solutions coincide. Moreover, any \(\vepsilon\)-strong solution is also \(\vepsilon\)-weak, but not vice versa.

A VI \((\set, \vioperset)\) is { , , } iff the optimality operator \(\vioperset\) is { monotone, pseudomonotone, quasimonotone }.

Unlike strong solutions, the existence of weak solutions is not guaranteed in continuous VIs. A VI \((\set, \vioperset)\) is said to satisfy the iff the set of weak solutions is non-empty, i.e., \(\mvi(\set, \vioperset) \neq \emptyset\). With these definitions in place, we summarize the following known properties of the solution sets of VIs.

Note that while it has become common place to use the Minty condition in the analysis of VIs as it is much more general (see, for instance, [53]), the Minty condition can at the cost of generality be replaced by the assumption that the VI \((\set, \vioperset)\) is quasimonotone with \(\set\) non-empty, and compact by Lemma 3.1 and Proposition 3.1 of [52].

3.2 First-Order Methods↩︎

We now turn our attention to the computation of solutions to variational inequalities. For simplicity, we restrict our attention to VIs \((\set, \vioperset)\) in which \(\vioperset\) is singleton-valued, which we denote as \((\set, \vioper)\). In future work, analogous results to those described here could be developed for the more general non-singleton-valued VI setting.

We consider first-order methods for computing strong solutions of VIs. Given a VI \((\set, \vioper)\), and an initial iterate \(\vartuple[][][0] \in \set\), a \(\kordermethod: \bigcup_{\numhorizons \geq 1} (\set \times \set^*)^{\numhorizons} \to \set\) consists of an update function that generates the sequence of iterates \(\left\{ \vartuple[][][\numhorizon] \right\}_{\numhorizon \in \N}\), given by \(\vartuple[][][\numhorizon + 1] \doteq \kordermethod \left( \left\{ (\vartuple[][][i], \vioper(\vartuple[][][i])) \right\}_{i=0}^{\numhorizon} \right)\). When \(\kordermethod\) depends solely on the last item in the sequence, we simply write \(\vartuple[][][\numhorizon + 1] = \kordermethod(\vartuple[][][\numhorizon], \vioper(\vartuple[][][\numhorizon]))\).

A common assumption that is used to establish polynomial-time convergence to strong solutions of VIs is Lipschitz continuity. Given a modulus of continuity \(\lsmooth \geq 0\), a \(\lsmooth\)- VI is a VI \((\set, \vioper)\) s.t. \(\set\) is non-empty, compact, and convex and \(\vioper\) is \(\lsmooth\)-Lipschitz-continuous. As is standard in the literature (see, for instance, [54]), the computational complexity measures in this section consider the number of evaluations of the optimality operator \(\vioper\) as the unit of account.

3.2.1 Mirror Gradient Algorithm↩︎

The canonical class of first-order methods for VIs is the class of [55]. These algorithms are parameterized by a kernel function \(\kernel: \set \to \R\), which induces a Bregman divergence \(\divergence[\kernel]: \set \times \set \to \R\) that in turn defines the update function \(\kordermethod^{\mathrm{MG}}(\othervartuple, \vioper(\othervartuple)) \doteq \argmin\limits_{\vartuple \in \set} \left\{ \innerprod[{\vioper(\othervartuple)}][{ \vartuple - \othervartuple}] + \frac{1}{2 \learnrate[][ ]} \divergence[\kernel][\vartuple][{\othervartuple}]\right\}\). When the kernel function is chosen s.t.\(\kernel(\vartuple) \doteq \frac{1}{2}\norm[\vartuple]^2\), the mirror gradient method \(\kordermethod^{\mathrm{MG}}\) reduces to the well-known method \(\kordermethod^{\mathrm{PG}}\) [56], i.e., \(\kordermethod^{\mathrm{PG}}(\othervartuple, \vioper(\othervartuple)) \doteq \proj[\outerset] \left[ \othervartuple - \learnrate[ ][ ] \vioper(\othervartuple) \right]\).

, the Bregman divergence corresponds to the Euclidean square norm, i.e., \(\divergence[\kernel][\vartuple][{\othervartuple}] \doteq \norm[{\vartuple - \othervartuple}]^2\), in which case

The average of the iterates of the mirror gradient method converges asymptotically to a strong solution in monotone and Lipschitz-continuous VIs [55]. In general, however, it is only possible to prove polynomial-time (i.e., non-asymptotic) computation of an \(\varepsilon\)-weak solution in such VIs, which does not necessarily imply convergence to an \(\varepsilon\)-strong solution (see, for instance, Proposition 8 and Appendix D of [57]). Even more troublesome, the sequence of iterates generated by the mirror gradient method is not guaranteed to converge at all, nor does averaging the iterates imply polynomial-time computation of an \(\varepsilon\)-strong solution, as shown by 1 in Appendix 10.

3.2.2 Global Convergence of the Mirror Extragradient Algorithm↩︎

Mirror extragradient (3, [40]) generalizes the well-known extragradient algorithm [45], which is known to asymptotically converge to a strong solution under reasonable assumptions⁶ [58], and allows for the polynomial-time computation of an \(\varepsilon\)-strong solution [40], [54], [59]. Similar to the class of mirror gradient methods, these algorithms are parameterized by a kernel function \(\kernel: \set \to \R\), which induces a Bregman divergence \(\divergence[\kernel]: \set \times \set \to \R\) that defines the update function \(\kordermethod^{\mathrm{MEG}}(\othervartuple, \vioper(\othervartuple)) \doteq \kordermethod^{\mathrm{MG}}\left(\othervartuple, \vioper(\kordermethod^{\mathrm{MG}}( \othervartuple, \vioper(\othervartuple)))\right)\). Moreover, when the kernel function for mirror extragradient is chosen s.t.\(\kernel(\vartuple) \doteq \frac{1}{2}\norm[\vartuple]^2\), it reduces to Korpelevich’s projected extragradient algorithm [45].

A seminal result by [40] shows that the average of the iterates output by the extragradient algorithm is an \(\varepsilon\)-strong solution for any monotone VI with a Lipschitz-continuous optimality operator when the algorithm is run for \(O(\frac{1}{\varepsilon})\) iterations. In the same setting, [59] and [54] show best-iterate convergence to an \(\varepsilon\)-strong solution in \(O(\frac{1}{\varepsilon^2})\) iterations. Later, [46] extended this polynomial-time computation result to VIs which satisfy the weaker Minty condition rather than the monotonicity assumption.

We extend [46]’s result to mirror extragradient algorithm with the following theorem. Our result states that an \(\varepsilon\)-strong solution of a VI \((\set, \vioper)\) can be found in polynomial time if \((\set, \vioper)\) satisfies the Minty condition and is over the outputs of the mirror extragradient method \(\left\{ \vartuple[][][\numhorizon + 0.5], \vartuple[][][\numhorizon] \right\}_{\numhorizon \in [\numhorizons]}\), i.e., there exists \(\lsmooth \geq 0\), s.t.for all \(\numhorizon \in [\numhorizons]\), \(\frac{1}{2} \norm[\vioper({\vartuple[][][t+0.5]}) - \vioper({\vartuple[][][t]})]^2 \leq \lsmooth^2 \divergence[\kernel][{\vartuple[][][t+0.5]}][{\vartuple[][][t]}]\). As we show in 4, this weaker pathwise Bregman continuity condition can be useful in the analysis of price-adjustment processes, and has indeed found such applications in the past (see, for example, [8]).⁷

3.2.3 Local Convergence of the Mirror Extragradient Algorithm↩︎

Beyond VIs for which the Minty condition holds, it seems unlikely that we can devise a first-order method which, given an arbitrary initial iterate, converges to a strong solution, as the computation of an \(\vepsilon\)-strong solution for Lipschitz-continuous VIs is in general a PPAD-complete problem [60].⁹ As a result, we investigate the conditions that guarantee local convergence of mirror extragradient to a (global) strong solution.

Given a VI \((\set, \vioperset)\), and a \(\vdelta \geq 0\), a of the VI is an \(\vartuple[][*] \in \set\) s.t.for all \(\vartuple \in \set \cap \closedball[\vdelta][{\vartuple[][*]}]\) and \(\vioper(\vartuple) \in \vioperset(\vartuple)\), it holds that \(\innerprod[{\vioper(\vartuple[][])}][{\vartuple - \vartuple[][*]}] \leq 0\) [61] We denote the set of \(\vdelta\)-local weak solutions of a VI \((\set, \vioperset)\) by \(\lmvi[][\vdelta] (\set, \vioperset)\). With these definitions in place, we now show that we can guarantee local convergence by assuming the algorithm is initialized close enough to a local weak (or Minty) solution. As we will not be applying this result in this paper, for simplicity, we present it under the assumption of Lipschitz continuity.

We now turn our attention to an application of Theorem [thm:mirror95extragradient95global95convergence] to Walrasian economies.

4 Walrasian economies↩︎

A \((\numgoods, \excessset)\) consists of \(\numgoods \in \N\) ,¹⁰ with any quantity of each commodity being exchangeable for a quantity of another. The exchange process is governed by a valuation system called , modeled as a vector \(\price \in \R^\numgoods_+\) s.t.\(\price[\good] \geq 0\) is the price of commodity \(\good \in \goods\). Prices \(\price \in \R^\numgoods_+\) allow the exchange of \(x \in \R_+\) units of any commodity \(\good \in \goods\) for \(x \left( \frac{\price[\good]}{\price[k]} \right)\) units of some other commodity \(k \in \goods\). For example, if \(j\) represents apples whose price is $1 and \(k\) represents bananas whose price is $2, then one apple can be exchanged for half of a banana.

A Walrasian economy is characterized by an \(\excessset: \R^\numgoods_+ \rightrightarrows \R^\numgoods\), which, for any price vector \(\price \in \R^\numgoods_+\) outputs a set of \(\excessset(\price) \subseteq \R^\numgoods\), with each excess demand denoted by \(\excess(\price) \in \excessset(\price)\). That is, \(\excess[\good](\price) > 0\) denotes the number of units of commodity \(\good \in \goods\) (i.e., more units of \(\good\) are bought than sold), while \(\excess[\good](\price) < 0\) denotes the number of units of commodity \(\good \in \goods\) (i.e., more units of \(\good\) are sold than bought).

A price vector \(\price \in \R^\numgoods_+\) is said to be iff there exists a \(\excess(\price) \in \excessset(\price)\) s.t.for all commodities \(\good \in \goods\), \(\excess[\good](\price) \leq 0\). Similarly, a price vector \(\price \in \R^\numgoods_+\) satisfies iff there exists a \(\excess(\price) \in \excessset(\price)\) s.t.\(\price \cdot \excess(\price) = 0\).

The canonical solution concept for Walrasian economies is the Walrasian equilibrium [1]. Given an approximation parameter \(\varepsilon \geq 0\), we say that a price vector \(\price[][][*] \in \R^\numgoods_+\) is an \(\varepsilon\)- iff there exists an excess demand \(\excess(\price[][][*]) \in \excessset(\price[][][*])\) s.t. for all commodities \(\good \in \goods\), it holds that \(\excess[\good](\price[][][*]) \leq \varepsilon\) and \(\price[][][*] \cdot \excess(\price[][][*]) \in [-\varepsilon, \varepsilon]\) . We denote the set of \(\varepsilon\)-Walrasian equilibria of a Walrasian economy \((\numgoods, \excessset)\) by \(\we[\varepsilon](\numgoods, \excessset)\). A \(0\)-Walrasian equilibrium, i.e., one that is (\(0\)-)feasible and satisfies (\(0\)-)Walras Law, is simply called a , and denoted by \(\we(\numgoods, \excessset)\).

Seen otherwise, a Walrasian equilibrium \(\price[][][*] \in \R^\numgoods_+\) is a price vector s.t. for all commodities \(\good \in \goods\), \(\price[\good][][*] > 0 \implies \excess[\good](\price[][][*]) = 0\) and \(\price[\good][][*] = 0 \implies \excess[\good](\price[][][*]) \leq 0\). Intuitively, a Walrasian equilibrium is a price vector which ensures that the exchange of any commodity with another can be implemented. On the one hand, if the price of a commodity \(\good \in \goods\) is strictly positive, then the exchange system dictates that \(\good\) can be exchanged for a strictly positive quantity of some other commodity \(k \in \goods\); in other words, at a Walrasian equilibrium commodity \(\good\) will always find a buyer since its excess demand is zero. On the other hand, if the price of commodity \(\good\) is zero, then the price system dictates that the commodity \(\good\) cannot be exchanged for any othercommodity; in other words, at a Walrasian equilibrium the commodity might not find a buyer.

4.1 Walrasian Economies and Variational Inequalities↩︎

With these definitions in place, we now present the fundamental relationship between Walrasian economies and VIs. The following theorem, due to [39], is to the best of our knowledge the first result exposing the connection between VIs and Walrasian equilibria.¹¹ It states that the problem of computing a Walrasian equilibrium is equivalent to the problem of computing a strong solution of the Walrasian VI, whose constraint set is given by the positive orthant, an instance of the class of VIs known as [63]. For completeness, we include its proof, as well as all other omitted proofs of results in this section in Appendix 12.

By 2, we can view any Walrasian equilibrium computation problem as a strong VI computation problem. Nevertheless, because the domain of prices is unbounded (i.e., \(\R^\numgoods_+\)), and because we seek existence and convergence results, we restrict the class of Walrasian economies we study. To this end, we introduce two important classes of Walrasian economies. The first of these is balanced economies; and the second, a further restriction, we call competitive economies.

4.1.1 Balanced Economies↩︎

A is a Walrasian economy \((\numgoods, \excessset)\) whose excess demand correspondence satisfies for all \(\lambda >0\), \(\excessset(\lambda \price) = \excessset(\price)\) and for all \(\price \in \R^\numgoods_+\) and \(\excess(\price) \in \excessset(\price)\), \(\price \cdot \excess(\price) \leq 0\). Intuitively, homogeneity requires that commodity prices have no absolute meaning of their own, but meaning only relative to the prices of other commodities, while weak Walras’ law requires budget balance (demand expenditure does not exceed supply revenue). While homogeneity of degree 0 is a standard assumption, weak Walras’ law is significantly weaker than standard assumptions in the literature [4], [64].

We now provide a novel characterization of Walrasian equilibrium prices in balanced economies as the , defined over \([0, 1]^\numgoods\) rather than \(\R^\numgoods_+\), which facilitates polynomial-time computation of Walrasian equilibria. The computational guarantees of our algorithms depend on the diameter of the constraint set of the VIs, which is hereby made finite.

In the sequel, we make use of the following lemma.

We now turn our attention to the question of existence of a Walrasian equilibrium. In balanced economies, the existence of Walrasian equilibrium follows as a corollary of the existence of strong solutions to continuous VIs (Theorem 2.2.1 of [51]), under the assumption that the excess demand correspondence \(\excessset\) is non-empty-, compact-, convex-valued, and upper hemicontinuous on \([0,1]^\numgoods\). ¹² This Walrasian equilibrium can be trivial, however, i.e., \(\price[][][*] = \zeros[\numgoods]\) is an equilibrium. To establish the existence of a non-trivial Walrasian equilibrium, we further restrict our attention to a subset of balanced Walrasian economies. We choose to study a canonical subset [64], [65], which we call .

4.1.2 Competitive Economies↩︎

A is a balanced economy \((\numgoods, \excessset)\) whose excess demand correspondence satisfies , which we define as follows: for all \(\price \in \R^\numgoods_+\) and \(\excess(\price) \in \excessset(\price)\), \(\excess(\price) \leq \zeros[\numgoods]\) implies \(\price \cdot \excess(\price) = 0\). Intuitively, this condition requires that whenever all commodities are supplied in excess, it must be that the economy has exhausted its purchasing power. As such, the excess demand is non-satiated, in the sense that the economy cannot demand more of any commodity, not because its supply is insufficient, but rather because it cannot afford it. The canonical example of a competitive economy is the [2] (see, 8, Appendix 13).

In competitive economies, we can alternatively characterize the set of Walrasian equilibria as the Walrasian VI with constraint set \(\simplex[\numgoods]\), yielding the . This VI is better suited to proving existence, because it is not necessary to rule out the trivial equilibrium.

To establish the existence of a Walrasian equilibrium in competitive economies, we assume continuity of the excess demand, which necessitates the following definition. A is a Walrasian economy \((\numgoods, \excessset)\) whose excess demand correspondence \(\excessset\) is upper hemicontinuous on \(\simplex[\numgoods]\), non-empty-, compact-, and convex-valued. Requiring upper hemicontinuity on \(\simplex[\numgoods]\) only is motivated as before. Intuitively, continuous economies are those economies in which relative changes in prices lead to well-behaved changes in excess demands.

Next, we leverage the fact that a strong solution is guaranteed to exist in continuous VIs (see [remark:sol95set95propert]) to establish the existence of a Walrasian equilibrium in continuous competitive economies. We use this fact to provide an alterative proof—one that is consistent with our theory—of the existence of a Walrasian equilibrium in Arrow-Debreu competitive economies, as they are indeed continuous competitive economies (see Appendix 13, 8).

With our characterization of Walrasian equilibria as strong solutions of VIs complete, we now turn our attention to solving the Walrasian, box, and simplex VIs.

4.2 Price Adjustment Processes for Walrasian Equilibrium↩︎

In this section, we develop algorithms with polynomial-time convergence guarantees. Specifically, we consider (first-order) price-adjustment processes, as defined by [37]. Unless otherwise noted, we assume the excess demand correspondence is singleton-valued.

Given a Walrasian economy \((\numgoods, \excess)\) and an initial iterate \(\price[][0] \in \R^\numgoods_+\), a \(\priceupdate\) consists of an update function \(\priceupdate: \bigcup_{\numhorizons \geq 1} (\R^\numgoods_+ \times \R^\numgoods)^{\numhorizons} \to \R^\numgoods_+\) that generates the sequence of iterates \(\left\{ \price[][\numhorizon] \right\}_{\numhorizon \in \N}\) given by \(\price[][\numhorizon + 1] \doteq \priceupdate \left( \left\{ (\price[][i], \excess(\price[][i])) \right\}_{i=0}^{\numhorizon} \right)\). As is standard in the literature (see, for instance, [37]), the computational complexity measures in this section consider the number of evaluations of the excess demand \(\excess\) as the unit of account.

An important class of price-adjustment processes are price-adjustment processes. These are processes where the price of each commodity is updated using only information about the past prices of the commodity itself and its excess demand. They are natural in the following sense: if each commodity is sold by exactly one fictional seller,¹³ that seller can update the price of her commodity in a decentralized fashion, that is, without having to coordinate with other sellers.

Formally, given a Walrasian economy \((\numgoods, \excess)\) and an initial price vector \(\price[][0] \in \R^\numgoods_+\), a price-adjustment process \(\priceupdate\) is said to be if it can be written as as \(\priceupdate \doteq (\priceupdate[1], \ldots, \priceupdate[\numgoods])\), where, for all commodities \(\good \in \goods\), \(\priceupdate[\good]: \bigcup_{\numhorizons \geq 1} (\R_+ \times \R)^{\numhorizons} \to \R_+\) is given by, for all \(\numhorizon = 0, 1, \ldots\), \(\price[\good][\numhorizon + 1] \doteq \priceupdate[\good] \left( \left\{ \price[\good][k], \excess[\good] (\price[][k]) \right\}_{k = 0}^{\numhorizon} \right)\). The canonical natural price-adjustment processes are tâtonnement processes [1], [4], i.e., processes \(\priceupdate \doteq (\priceupdate[1], \ldots, \priceupdate[\numgoods])\) s.t.for all \(\good \in \goods\) and \(\numhorizon \in \N_{++}\), there exists a function \(g: \R_+ \times \R \to \R\) that satisfies \(\priceupdate[\good]\left( \left\{\price[\good][k], \excess[\good] (\price[][k])\right\}_{k = 0}^{\numhorizon} \right) \doteq g(\price[\good][\numhorizon], \excess[\good] (\price[][\numhorizon]))\).¹⁴ Observe that \(\priceupdate[\good]\) depends only on commodity \(j\)’s price \(\price[\good]\) and excess demand \(\excess[\good]\), not on \(\price\) and \(\excess\).¹⁵

4.2.1 Variationally Stable Walrasian Economies↩︎

To characterize the class of Walrasian economies for which a Walrasian equilibrium can be computed using our VI characterizations, we now introduce the class of variationally stable economies. A Walrasian economy \((\numgoods, \excessset)\), is said to be [47] on a general price space \(\pricespace \subseteq \R^\numgoods_+\) iff there exists a \(\price[][][*] \in \pricespace\) s.t.for all prices \(\price \in \pricespace\) and \(\excess(\price) \in \excessset(\price)\), \(\innerprod[{ \excess(\price)}][{\price[][][*] - \price}] \geq 0\). In other words, a Walrasian economy \((\numgoods, \excessset)\) is variationally stable on \(\pricespace\) iff the VI \((\pricespace, -\excessset)\) satisfies the Minty condition. The next lemma is key to our story: the box VI \(([0, 1]^\numgoods, -\excessset)\) associated with balanced economy \((\numgoods, \excessset)\) satisfies the Minty condition, i.e., any balanced economy is variationally stable on \([0, 1]^\numgoods\).

While [lemma:balanced95is95minty] may seem trivial, it suggests that in balanced economies, which include among others Arrow-Debreu competitive economies, first-order methods for the box VI \(([0, 1]^\numgoods, -\excessset)\) are guaranteed to converge to a strong solution under suitable continuity assumptions—possibly even one that is not the zero-price vector.

4.2.2 Mirror Extratâtonnement Process in Balanced Economies↩︎

We now turn our attention to solving the box VI \(([0, 1]^\numgoods, -\excessset)\)—or rather, the box VI \(([0, 1]^\numgoods, -\excess)\), since we assume for our algorithms that the excess demand is singleton-valued—and hence computing a Walrasian equilibrium with the mirror extragradient method. Solving the VI \((\pricespace, -\excess)\) for a general price space \(\pricespace\) with the mirror extragradient method gives rise to a family of price-adjustment processes parameterized by a kernel function \(\kernel\), which we call (5). The name is justified because, as we show next, these processes are natural.¹⁶

With the mirror extratâtonnement process and [lemma:balanced95is95minty] in hand, we apply [thm:mirror95extragradient95global95convergence] to characterize the convergence of the mirror extratâtonnement process (5).

The convergence guarantee provided by [thm:mirror95extra95tatonn95convergence] requires pathwise Bregman continuity over price trajectories generated by the mirror extratâtonnement process. This statement is purposeful, as it is not possible to guarantee Bregman continuity of an excess demand function that is homogeneous of degree \(\alpha > 0\), unless this excess demand is constant and thus trivially Bregman continuous for any Bregman divergence \(\divergence[\kernel]\).¹⁷ Moreover, pathwise Bregman continuity is achievable by mirror extratâtonnement, as we empirically verify for all Walrasian economies simulated in the experiments reported in 5.

For choices of kernel functions \(\kernel\) s.t.the associated Bregman divergence \(\divergence[\kernel]\) is not homogeneous of degree \(\alpha > 0\) (i.e., for all \(\price, \otherprice \in \R^\numgoods_+\) and \(\alpha, \lambda > 0\), \(\divergence[\kernel] (\lambda \price, \lambda\otherprice) \neq \lambda^\alpha \divergence[\kernel] (\price, \otherprice)\)), we define a novel class of economies, which seems likely to capture a broader family of Walrasian economies.¹⁸ Given a modulus of continuity \(\lsmooth > 0\) and a kernel function \(\kernel: \pricespace \to \R\), a on \(\pricespace \subseteq \R^\numgoods_+\) is a Walrasian economy \((\numgoods, \excess)\) whose excess demand \(\excess\) is \((\lsmooth, \kernel)\)-Bregman-continuous on \(\pricespace\).¹⁹ We now note the following corollary of [thm:mirror95extra95tatonn95convergence].

4.2.3 Mirror Extratâtonnement Process in Elastic Economies↩︎

While the convergence result established in 2 seems promising, it is not immediately clear what types of excess demand functions satisfy Bregman continuity. To characterize the Bregman continuity properties of Walrasian economies, we introduce additional economic parameters, which have been used extensively in the analysis of algorithms for computing Walrasian equilibria (e.g., [6]).

Given \(\lelastic \geq 0\), an economy \((\numgoods, \demandfunc, \supplyfunc)\) is said to be if it is a Walrasian economy \((\numgoods, \excess)\) with an \(\demandfunc: \R^\numgoods_+ \to \R^\numgoods_+\) and \(\supplyfunc: \R^\numgoods_+ \to \R^\numgoods_+\) s.t.\(\excess(\price) \doteq \demandfunc(\price) - \supplyfunc(\price)\), for which the following two bounds hold: \[\begin{align} &\frac{\norm[\demandfunc(\otherprice)-\demandfunc(\price)]}{\norm[\demandfunc(\price)]} \leq \lelastic \, \frac{\norm[\otherprice-\price]}{\norm[\price]_\infty} \quad \quad \quad \frac{\norm[\supplyfunc(\otherprice)-\supplyfunc(\price)]}{\norm[\supplyfunc(\price)]} \leq \lelastic \, \frac{\norm[\otherprice-\price]}{\norm[\price]_\infty}. \end{align}\]

The next lemma provides conditions that ensure that an \(\lelastic\)-economy satisfies Bregman continuity.

2 suggests that upper bounding the excess demand and lower bounding prices away from \(\zeros[\numgoods]\) is sufficient to ensure the \((\lsmooth, \kernel)\)-Bregman continuity of the excess demand, assuming a non-zero and finite Bregman constant \(\lsmooth\).

While it is not possible to ensure that prices remain bounded away from \(\zeros[\numgoods]\) when running the mirror extratâtonnement process with price space \([0, 1]^\numgoods\), we can instead choose the price space \(\simplex[\numgoods]\), in which case we can obtain a Bregman continuity bound from 2. The price space \(\simplex[\numgoods]\), however, does not include the zero vector \(\zeros[\numgoods]\), which trivially ensures that balanced economies are variationally stable on \([0, 1]^\numgoods\). In this sense, the restriction of the price space to \(\simplex[\numgoods]\) can effectively destabilize an economy, potentially making the computation of a Walrasian equilibrium intractable. To overcome this challenge, we focus our attention on the class of competitive economies that are indeed variationally stable on \(\simplex[\numgoods]\). This class includes among others Walrasian economies whose excess demand satisfies the weak axiom of revealed preferences (WARP) (10, Appendix 14), the weak gross substitutes (WGS) condition (9, Appendix 14), and the law of supply and demand (8, Appendix 14).

For balanced economies, by weak Walras’ law a sufficient condition for the economy to be variationally stable on \(\simplex[\numgoods]\) is the existence of \(\price[][][*] \in \simplex[\numgoods]\) s.t.for all prices \(\price \in \simplex[\numgoods]\), \(\excess(\price) \in \excessset(\price)\), \(\innerprod[{ \excess(\price)}][{\price[][][*]}] \geq 0\). Now, suppose that there exists a commodity \(\good \in \goods\) which is (weakly) demanded in excess for all \(\price \in \simplex[\numgoods]\), i.e., \(\excess[\good] (\price) \geq 0\). Then, setting \(\price[][][*] = \basis[\good]\), we have \(\innerprod[{ \excess(\price)}][{\price[][][*]}] = \innerprod[{ \excess(\price)}][{\basis[\good]}] = \excess[\good] (\price) \geq 0\). Hence, if there is a good which is never supplied in excess the economy is variationally stable.

Alternatively, a balanced economy is variationally stable on \(\simplex[\numgoods]\) whenever there exists two commodities \(\good, k \in \goods\), whose excess demands are negatively proportional for all prices, i.e., \(\exists \alpha > 0\), s.t.\(\excess[\good] (\price) \geq -\alpha \excess[k] (\price)\), Then, setting \(\price[][][*] = \frac{1}{1 + \alpha}\basis[\good] + \frac{\alpha}{(1+\alpha)} \basis[k]\), we have \(\innerprod[{ \excess(\price)}][{\price[][][*]}] = \frac{1}{1 + \alpha}\excess[\good] (\price) + \frac{\alpha}{(1+\alpha)} \excess[k] (\price) \geq \frac{-\alpha}{1 + \alpha}\excess[k] (\price) + \frac{\alpha}{(1+\alpha)} \excess[k] (\price) = 0\). In light of this observation, the variational stability assumption on \(\simplex[\numgoods]\) can be seen as a rather mild assumption, as commodities whose excess demands are negatively correlated are abundant in the real world. For instance, airplane tickets and airplanes, whenever the excess demand for airline tickets is positive, this must mean that there are not enough airplanes, that is the excess demand for planes is negative.

To use 2, we also have to ensure that the excess demand of the economy is bounded, which we achieve by bounding each consumer’s consumption space for a commodity by the maximum aggregate supply of that commodity. Formally, given \(\lbounded \geq 0\), a \((\numgoods, \demandfunc, \supplyfunc)\) is a Walrasian economy \((\numgoods, \excess)\) that consists of an \(\demandfunc: \R^\numgoods_+ \to \R^\numgoods_+\) and an \(\supplyfunc: \R^\numgoods_+ \to \R^\numgoods_+\) s.t.\(\excess(\price) \doteq \demandfunc(\price) - \supplyfunc(\price)\), \(\|\demandfunc\|_\infty \leq \lbounded\), and \(\|\supplyfunc\|_\infty \leq \lbounded\). In 8 (Appendix 13), we prove that any Arrow-Debreu competitive economy [2] can be represented as a bounded continuous competitive economy; as such, this assumption is mild.

With these definitions in place, we can finally apply 2 to derive polynomial-time convergence of the mirror extratâtonnement process as a reinterpretation of [thm:mirror95extra95tatonn95convergence].

Going beyond variationally stable competitive economies on \(\simplex[\numgoods]\), the local convergence behavior of mirror extratâtonnement can similarly be obtained by applying [thm:vi95mirror95extragrad95local], i.e., replacing the assumption that the competitive economy is variationally stable with the assumption that the initial price iterate starts close enough to a local weak solution of the simplex VI \((\simplex[\numgoods], -\excess)\).

With this theorem in hand, we make the following remarks before turning our attention to second order price-adjustment processes.

4.2.4 Mirror Extratâtonnement in Scarf Economies↩︎

One of the earliest negative results in the literature is the example of a Walrasian economy provided by Herbert Scarf, in which continuous-time tâtonnement cycles around the unique Walrasian equilibrium, while discrete-time variants spiral away from the equilibrium from any initial non-equilibrium price vector [23]—this, all when the algorithm is run on the simplex. Formally, a is a Walrasian economy \((3, \excess^{\mathrm{scarf}})\) with three goods, for which the excess demand is the following singleton-valued function: \[\begin{align} \excess^{\mathrm{scarf}}(\price) \doteq \left( \frac{\price[1]}{\price[1] + \price[2]} + \frac{\price[3]}{\price[1] + \price[3]} - 1, \frac{\price[1]}{\price[1] + \price[2]} + \frac{\price[2]}{\price[2] + \price[3]} - 1, \frac{\price[2]}{\price[2] + \price[3]} + \frac{\price[3]}{\price[1] + \price[3]} - 1 \right) \enspace. \end{align}\]

As we show in [lemma:scarf95var95stable95breg95cont] (Appendix 12), the Scarf economy is Bregman-continuous on any price space bounded away from \(0\) in every coordinate. We thus obtain the following result.

5 Experiments↩︎

We describe two sets of experiments in this section. First, we run mirror tâtonnement and extratâtonnement, both with kernel function \(\kernel(\price) \doteq \frac{1}{2} \norm[\price]^2\) in an attempt to solve the Scarf economy. The goal is to illustrate the differing convergence behavior between these two price-adjustment processes. Second, we run mirror extratâtonnement, again with kernel function \(\kernel(\price) \doteq \frac{1}{2} \norm[\price]^2\), on various Arrow-Debreu exchange economies [2]. This time, the goal is to demonstrate that extratâtonnement can efficiently solve reasonably large Walrasian economies in practice.

In 6, we visualize the trajectories generated by the tâtonnement and extratâtonnement processes on the Scarf economy. As is well established

[13], the sequence of prices generated by tâtonnement, even when initialized very close to the equilibrium prices \((\frac{1}{3}, \frac{1}{3}, \frac{1}{3})\) spirals away from these prices and ultimately lands at \((0, 0, 1)\), which is not a Walrasian equilibrium.²⁰ In contrast, the prices generated by the mirror extratâtonnement process spiral inwards towards the equilibrium prices, even when initialized far away from them. An informal rationale for this behavior is as follows: The continuous-time variant of tâtonnement is known to cycle around the equilibrium prices [23]. If we interpret the discrete-time tâtonnement (resp. mirror extratâtonnement) process as an explicit (resp. implicit) discretization [66] of the continuous-time tâtonnement dynamics, it is well understood that explicit (resp.implicit) discretization methods tend to be unstable (resp.stable) when continuous-time dynamics cycle.

An Arrow-Debreu exchange economy \((\numbuyers, \numcommods, \consumptions, \consendow, \util)\) comprises \(\numcommods \in \N\) commodities and \(\numbuyers \in \N\) consumers, each \(\consumer \in [\numconsumers]\) with a consumption space \(\consumptions[\buyer]\), an endowment of commodities \(\consendow[\consumer] \in \R^\numcommods_+\), and a utility function \(\util[\consumer]: \consumptions[\buyer] \to \R\). Such an economy can be represented as a bounded continuous competitive economy \((\numgoods, \excessset)\) where the excess demand correspondence is given by \(\excessset(\price) \doteq \sum_{\player \in \players} \argmax\limits_{\consumption[\consumer] \in \consumptions[\consumer]: \consumption[\consumer] \cdot \price \leq \consendow[\consumer] \cdot \price} \util[\consumer](\consumption[\consumer]) - \sum_{\consumer \in \consumers} \consendow[\consumer]\).²¹

In our second set of experiments, we run extratâtonnement on Arrow-Debreu exchange economies, using the following utility function classes: 1. linear: \(\util[\buyer](\allocation[\buyer]) = \sum_{\good \in \goods} \valuation[\buyer][\good] \allocation[\buyer][\good]\); 2. Cobb-Douglas: \(\util[\buyer](\allocation[\buyer]) = \prod_{\good \in \goods} \allocation[\buyer][\good][][{\valuation[\buyer][\good]}]\); 3. Leontief: \(\util[\buyer](\allocation[\buyer]) = \min_{\good \in \goods} \left\{ \frac{\allocation[\buyer][\good]}{\valuation[\buyer][\good]}\right\}\); and 4. CES: \(\util[\buyer](\allocation[\buyer]) = \sqrt[{\rho_\buyer}]{ \sum_{\good \in \goods} \valuation[\buyer][\good] \allocation[\buyer][\good][][{\rho_\buyer}]}\), with each utility function parameterized by \(\valuation[\buyer] \in \mathbb{R}_+^{\numbuyers}\), where every \(\valuation[\buyer][\good]\) quantifies the value of commodity \(\good\) to consumer \(\consumer\). These values are drawn randomly from a uniform distribution.

We study seven different reasonably-sized Arrow-Debreu exchange economies, with 500 or 1000 commodities, and 600, 800, or 1000 consumers. Their precise makeup is shown in ¿tbl:table:exp95summary?.²²\(^,\)²³

7 depicts the convergence of extratâtonnement in all seven economies. Moreover, the convergence rates (loosely; explanation forthcoming) respect our bounds (see ¿tbl:table:convergence95bounds95alt?). Polynomial-time convergence is perhaps surprising, in light of [37]’s observation that solving Arrow-Debreu economies is PPAD-complete ([37]). But we are not contradicting their claim. For one thing, the space of prices we consider is the unit box, not the unit simplex as in [37]; thus, Minty is necessarily satisfied. Additionally, we achieve our results by searching for a suitable step size, in consideration of pathwise Bregman continuity.

Specifically, we conduct a grid search over the step-size parameter for each economy to find appropriate settings, by uniformly discretizing an interval \([\eta_{\text{min}}, \eta_{\text{max}}]\) into 200 grid points. We then record the best-iterate Walrasian deviation \((\varepsilon)\) for each of these points and the maximum Lipschitz coefficient (see ¿tbl:table:convergence95bounds95alt?, columns 2 and 3). The results of these grid searches for all seven economies are shown in 8. In all cases, the minimum, best-iterate Walrasian deviation (indicated by a red X) was achieved at a step size at which pathwise Bregman continuity does not hold.²⁴ The shaded regions of these plots indicate step sizes where pathwise Bregman continuity does hold, as does a loose upper bound on the best-iterate Walrasian deviation (described below).

For our first set experiments with Arrow-Debreu exchange economies, we choose as our step size that for which the best-iterate Walrasian deviation is minimized, among step sizes at which pathwise Bregman continuity is satisfied—points marked by blue circles in the plots. This choice ensures that our theory applies. Having taken this choice, 7 depicts the progression of the Walrasian deviations at prices generated during each iteration of extratâtonnement in all seven Arrow-Debreu economies. We observe rapid convergence in those economies that lack linear consumers (1-4 and 7); but in economies with linear consumers (5 and 6), where results in the literature attest to the difficulty of convergence [67], convergence is notably slower. To nonetheless claim convergence in economies with linear consumers, we use [thm:mirror95extragradient95global95convergence] to compute a loose upper bound on the best-iterate Walrasian deviations. As we do not know \(x^*\), we replace the divergence from \(x^*\) to \(x^{(0)}\) with the maximal distance from \(x^{(0)}\) to any point in the price space. Since our price space is a box, this maximal distance is achieved by picking the farthest corner of the box from \(x^{(0)}\). This upper bound is looser than the one presented in [thm:mirror95extragradient95global95convergence]; hence, violating this upper bound would certainly imply non-convergence. The results presented in ¿tbl:table:convergence95bounds95alt? (column 1) show that no such violations are encountered, even in economies inhabited by linear consumers.

¿tbl:table:convergence95bounds95alt? (column 4) also lists the step sizes used in each experiment. It is interesting to note the relationship between the choice of step size and the reported deviations. For example, in economy 3 (CES with \(\rho \in (0,1)\), where the step size is very small, convergence is likewise slower. On the other hand, in economy 1 (Leontief), where the step size is large, convergence is fast.

Finally, going beyond our theory, we run an additional set of experiments on the same seven Arrow-Debreu economies, but this time using step sizes that minimize the best-iterate Walrasian deviation, although pathwise Bregman continuity is not in fact satisfied. (I.e., We choose as the step sizes the points indicated by red Xs on the plots in 8.) Although our theory no longer applies, we find that these convergence plots (see Appendix 16) follow similar trajectories to those shown in 7. These experiments suggest that pathwise Bregman continuity, a condition that can only be verified post hoc, may be too restrictive. We leave as future work the search for a weaker, preferably ex-ante verifiable, convergence condition. We also leave as future work the search for theoretical last-iterate guarantees that reflect what we observe in our convergence plots.

We observe that in all our experiments except 5 and 6—which include linear consumers and as such are not covered by our theory, because ²⁵—the mirror extratâtonnement process converges to an \(\varepsilon\)-Walrasian equilibrium.

Finally, while our experiments obey our theory which suggests a best-iterate convergence to an \(\varepsilon\)-Walrasian equilibrium in \(O \left( \frac{1}{\varepsilon^2} \right)\) time steps, we observe that last-iterate convergence occurs only in economy 4, corresponding to the case of Cobb-Douglas consumers, for which even tâtonnement is known to converge in last iterates. These findings suggest that achieving convergence in last iterates might not be possible with the mirror extratâtonnement process.

6 Discussion↩︎

A recent paper by [68], revisits the stability of tâtonnement from a complementary but distinct angle. Rather than working within the classical Walrasian framework, they embed a static general equilibrium model into an intertemporal setting with forward-looking monopolistic and monopsonistic price setters subject to pricing frictions, and derive tâtonnement-like price dynamics endogenously from agents’ optimizing behavior. Their central stability results rest on two properties of this intertemporal environment: first, forward-looking households use savings to smooth anticipated price changes;

Our results differ from those of Lorenzoni and Werning along several important dimensions. First, our convergence guarantees are stronger. They are non-asymptotic—we provide explicit polynomial-time rates of convergence to an approximate Walrasian equilibrium—and global, while their stability analysis is local, relying on a linearization of the excess demand function around equilibrium. Second, our framework requires no additional structure beyond the classical Walrasian setting—we work directly with competitive price-taking agents, without imposing monopolistic market power, pricing frictions, or rational expectations dynamics. Third, our treatment of the Scarf economy does not rely on eliminating income effects through an intertemporal structure: we prove polynomial-time convergence of mirror extratâtonnement to the unique Walrasian equilibrium of the Scarf economy directly, working with its standard Leontief preferences and Walrasian excess demand. More broadly, Lorenzoni and Werning recover stability as a consequence of specific microfoundational assumptions on price setters’ behavior. In contrast, our results establish stability as a property of the excess demand structure of the Walrasian economy itself, which can be viewed as a more fundamental statement. We note that the two approaches are not in conflict: they address adjacent questions and the findings are complementary.

7 Conclusion↩︎

In this work, we analyze the mirror extragradient method, and show that it is a powerful computational tool for solving variational inequalities, extending existing results to establish polynomial-time convergence under suitable conditions. Then, by leveraging this framework, we provide the first computationally tractable characterization of Walrasian equilibrium in balanced economies. Specifically, we introduce the mirror extratâtonnement process, and show that it converges efficiently even in challenging cases like the Scarf economy. Our theoretical insights and empirical validation suggest that computational intractability in general equilibrium is largely a consequence of Bregman discontinuities, rather than fundamental hardness, offering a new perspective on Scarf’s long-standing challenge in applied general equilibrium theory.

8 Acknowledgments↩︎

Denizalp Goktas was supported by a JP Morgan AI Fellowship. This work was further supported by the Office of Naval Research (ONR) grant N00014-24-1-2657.

9 Related Work↩︎

9.0.0.1 Algorithms for Walrasian Economies

A detailed inquiry into the computational properties of market equilibria was initiated by [69], who studied a special case of the Arrow-Debreu competitive economy known as the [70]. This model, for which Irving Fisher computed equilibrium prices using a hydraulic machine in the 1890s, is essentially the Arrow-Debreu model of a competitive economy, but there are no firms, and buyers are endowed with only one type of commodity—hereafter good²⁶—an artificial currency [70], [71]. [72] exploited a connection first made by [73] between the and Walrasian equilibrium to solve Fisher markets assuming buyers with linear utility functions, thereby providing a (centralized) polynomial-time algorithm for equilibrium computation in these markets [69], [72]. Their work was built upon by [9], who extended the Eisenberg-Gale program to all Fisher markets in which buyers have utility functions, and proved that the equilibrium of Fisher markets with such buyers can be computed in polynomial time by interior point methods.

Concurrent with this line of work on computing Walrasian equilibrium using centralized methods, a line of work on devising and proving convergence guarantees for price-adjustment processes (i.e., iterative algorithms that update prices according to a predetermined update rule) developed. This literature has focused on devising natural price-adjustment processes, like tâtonnement, which might explain or imitate the movement of prices in real-world markets. In addition to imitating the law of supply and demand, tâtonnement has been observed to replicate the movement of prices in lab experiments, where participants are given endowments and asked to trade with one another [13]. Perhaps more importantly, the main premise of research on the stability of Walrasian equilibrium in computer science is that for Walrasian equilibrium to be justified, not only should it be backed by a natural price-adjustment process as economists have long argued, but it should also be computationally efficient [71].

Another line of work considers price-adjustment processes in variants of Fisher markets. [6] analyzed tâtonnement in a real-world-like model satisfying WGS called the ongoing market model. In this model, tâtonnement once-again converges in polynomial-time [6], [74], and it has the advantage that it can be seen as an abstraction for market processes. [6]’s results were later extended by [75] to ongoing markets with , i.e., the excess demand of any commodity weakly increases if the price of any other commodity weakly decreases, fixing all other prices, and ongoing markets with a mix of WGC and WGS commodities. The ongoing market model these two papers study contains as a special case the Fisher market; however [6] assume bounded own-price elasticity of Marshallian demand, and bounded income elasticity of Marshallian demand, while [75] assume, in addition to [6]’s assumptions, bounded adversarial market elasticity, which can be seen as a variant of bounded cross-price elasticity of Marshallian demand, from below. With these assumptions, these results cover Fisher markets with a small range of the well-known CES utilities, including CES Fisher markets with \(\rho \in [0, 1)\) and WGC Fisher markets with \(\rho \in (- 1, 0]\). [8] built on this work by establishing the convergence of tâtonnement in polynomial time in nested CES Fisher markets, excluding the limiting cases of linear and Leontief markets, but nonetheless extending polynomial-time convergence guarantees for tâtonnement to Leontief Fisher markets as well. More recently, [76] showed that [8]’s [[8]] result extends to an asynchronous version of tâtonnement, in which good prices are updated during different time periods. In a similar vein, [77] analyzed tâtonnement in online Fisher markets, determining that tâtonnement tracks Walrasian equilibrium prices closely provided the market changes slowly.

Another price-adjustment process that has been shown to converge to market equilibria in Fisher markets is , first introduced by [78] for linear utilities; then expanded upon and shown to converge by [79] for all CES utilities; and very recently shown to converge in Arrow-Debreu exchange economies with linear and CES (\(\rho \in [0,1)\)) utilities by [80]. The study of the proportional response process was proven fundamental when [8] noticed its relationship to gradient descent. This discovery opened up a new realm of possibilities in analyzing the convergence of market equilibrium processes. For example, it allowed [7] to generalize the convergence results of proportional response dynamics to Fisher markets for buyers with mixed CES utilities. This same idea was applied by [8] to prove the convergence of tâtonnement in Leontief Fisher markets, using the equivalence between mirror descent [81] on the dual of the Eisenberg-Gale program and tâtonnement, first observed by [69]. More recently, [82] developed methods to solve the Eisenberg-Gale convex program in the case of linear, quasi-linear, and Leontief Fisher markets.

An alternative to the (global) competitive economy model, in which an agent’s trading partners are unconstrained, is the [83] model of a graphical economies. This model features local markets, in which each agent can set its own prices for purchase only by neighboring agents, and likewise can purchase only from neighboring agents. Auction-like price-adjustment processes have been shown to converge in variants of this model assuming WGS [84].

9.0.0.2 Algorithms for Variational Inequalities

Variational inequalities [51] are a mathematical modeling framework whose study dates back to the early 1960s [38], [85]–[88]. Their utility lies in their very broad mathematical formulation which allows one to solve other mathematical modeling problems using the tools of functional analysis. They have found a great number of applications to problems in engineering and finance [51] over the years, and have seen an increased interest due to their novel applications in machine learning, to problems ranging from the training of generative adversarial neural networks [89] to robust optimization [90].

Historically, the goal of the literature on solution methods for VIs has been to devise algorithms which are asymptotically guaranteed to converge to a strong or weak solution [91]. An overwhelming majority of these works have focused on first-order methods for computing solutions of VIs, with higher order methods having been considered only in recent years (see, for instance, [53], [92]) While a strong solution of a VI is guaranteed to exist in continuous VIs, most results on the computational complexity of strong solutions, concerns the class of monotone VIs (see, for instance [54]) with a few works focusing on VIs that satisfy the Minty condition (see, for instance, [49]).

The canonical algorithm to solve VIs is the projected gradient method [48], [56] ( subgradient, gradient descent ascent and Arrow-Hurwicz-Uzawa [4], [93]). While asymptotic convergence of the projected gradient method to a solution can be shown for a subset of monotone VIs known as strongly monotone VIs²⁷, in general monotone VIs, only ergodic asymptotic convergence (i.e., asymptotic convergence of the averaged iterates) to a strong solution can be guaranteed. The earliest known algorithm with asymptotic convergence guarantees to a solution of a monotone VI, is the extragradient method, attributed to [45]. Following this earlier success, [58] introduced a closely related algorithm called the optimistic gradient method which he also showed to converge to a solution. These initial extragradient and optimistic gradient algorithms would eventually become much more sophisticated with a large body of work appearing on asymptotic convergence guarantees for variants of these earlier methods (e.g., [94]) of the optimality operator

More recently, the literature has turned its attention to algorithms with non-asymptotic guarantees, and in particular to ones that are guaranteed to compute a \(\vepsilon\)-strong or \(\vepsilon\)-weak solution of a VI in polynomial-time, i.e., in a number of evaluations of the optimality operator \(\vioperset\) which is polynomial in the inverse of the approximation parameter \(\frac{1}{\vepsilon}\), the dimensionality \(\spacedim\) of the constraint set, and other relevant assumption specific parameters such as an upper bound on all of the values of the optimality operator. One of the earliest results in this direction was given by [40], who introduced the conceptual mirror-Prox Method, an elegant generalization of the extragradient Method, and established that \(\vepsilon\)-strong and \(\vepsilon\)-weak solutions can be computed in \(O(\frac{1}{\vepsilon})\) operations by averaging the iterates of the algorithm under the assumption that the the VI is monotone, and the optimality operator is Lipschitz-continuous. [40]’s work was subsequently followed by a large body of work on more sophisticated algorithms (e.g., [49], [95]) for monotone VIs, and better computational results for the projection method [96], the extragradient method [54], [97], [98] and the optimistic gradient method [99].

More recently, a number of works have considered first-order methods to compute a strong solution (e.g., [49], [53], [100]) in VIs or a stationary point of the VI²⁸ (e.g., [57]) that satisfy the Minty condition. The first-order methods considered by this more recent line of work on non-monotone variational inequalities include the extragradient method (e.g., [101], [102]), Tseng’s method (e.g., [103]–[107]), and the optimistic gradient method (e.g., [108]) and its variants.

[57] consider a very large class of continuous VIs in which the optimality operator satisfies weak-monotonicity, and provide non-asymptotic polynomial-time convergence bounds for the , an iterative algorithm which at each iteration solves a regularized version of the VI until converence. While these results are positive, at a high-level, the authors’ non-asymptotic convergence is not to a \(\vepsilon\)-strong or \(\vepsilon\)-weak solution of the VI, but rather, either 1) to a , i.e., a point \(\vartuple[][*] \in \set\) s.t. for some \(\vdelta \geq 0\) there exists \(\vartuple \in \ball[\vdelta][{\vartuple[][*]}]\) and \(\vartuple\) is a \(\vepsilon\)-strong solution, or 2) to a distribution over the constraint set \(\set\) that in expectation that is a \(\vepsilon\)-strong solution. Unfortunately, this computational complexity result can not be translated to a polynomial-time convergence to a \(\vepsilon\)-strong or \(\vepsilon\)-weak solution.

10 Omitted Examples from Section 3↩︎

11 Omitted Proofs for Section 3↩︎

Before we start our analysis of the mirror extragradient method (3), we first prove the following technical lemma on Bregman divergences.

11.1 Global Convergence of the Mirror Extragradient Algorithm↩︎

With the above technical lemma in hand, we are now ready to prove a progress lemma for the mirror extragradient method, which describes how the algorithm progresses from one iteration to another. Note that under the Minty condition, the following lemma implies convergence to a weak solution since setting \(\vartuple \doteq \vartuple[][*] \in \mvi(\set, \vioper)\), we obtain \(\divergence[\kernel][{\vartuple[][*]}][{\vartuple[][][k]}] > \divergence[\kernel][{\vartuple[][*]}][{\vartuple[][][k + 1]}]\) for all \(k \in [\numhorizons]\) (i.e., the distance to the weak solution \(\vartuple[][*]\) is strictly decreasing). In addition, note that under the assumptions of the lemma, the VI \((\set, \vioper)\) is continuous, hence also implying convergence to a strong solution since any weak solution is also a strong solution in continuous VIs; see [remark:sol95set95propert].

While as previously noted, the above lemma implies asymptotic convergence to a strong solution, to show polynomial-time computation of an \(\varepsilon\)-strong solution, we have to bound the progress of the intermediate iterates \(\divergence[\kernel][{\vartuple[][][k+0.5]}][{\vartuple[][][k]}]\) as a function of the time horizon algorithm. In the proof of the following theorem, we show that we can bound this quantity, assuming that the kernel function is, in addition to being 1-strongly-convex, also \(\kernelsmooth\)-Lipschitz-smooth.

11.2 Local Convergence of the Mirror Extragradient Algorithm↩︎

To understand how a local weak solution can provide us with local convergence, recall by 4 the iterates of the mirror extragradient algorithm satisfy the following for all \(\numhorizon \in \N\): \[\begin{align} \divergence[\kernel][{\vartuple}][{\vartuple[][][k]}] - \divergence[\kernel][{\vartuple}][{\vartuple[][][k+1]}] \geq \learnrate[ ][ ]\langle \vioper(\vartuple[][][k+0.5]),\vartuple[][][k+0.5] - \vartuple \rangle + \left( 1 - (\learnrate[ ][ ]\lsmooth)^2 \right)\divergence[\kernel][{\vartuple[][][k+0.5]}][{\vartuple[][][k]}]. \end{align}\]

Suppose that the kernel function \(\kernel\) is strictly convex, and that the algorithm has not yet converged, i.e., \(\vartuple[][][k+0.5] \neq \vartuple[][][k]\), then \(\divergence[\kernel][{\vartuple[][][k+0.5]}][{\vartuple[][][k]}] > 0\), and we can drop the term. Re-organizing the expressions, we then have: \[\begin{align} \divergence[\kernel][{\vartuple}][{\vartuple[][][k]}] > \divergence[\kernel][{\vartuple}][{\vartuple[][][k+1]}] + \learnrate[ ][ ] \langle \vioper(\vartuple[][][k+0.5]),\vartuple[][][k+0.5] - \vartuple \rangle \end{align}\]

Now, notice that if we can ensure that for all \(k \in [\numhorizons]_+\), there exists an \(\vartuple[][*] \in \svi(\set, \vioper)\) s.t. \(\langle \vioper(\vartuple[][][k+0.5]),\vartuple[][][k+0.5] - \vartuple[][*] \rangle \geq 0\), then we have: \(\divergence[\kernel][{\vartuple[][*]}][{\vartuple[][][k]}] > \divergence[\kernel][{\vartuple[][*]}][{\vartuple[][][k+1]}]\), implying that \(\vartuple[][][k] \to \vartuple[][*]\), i.e., convergence to a strong solution. Since we cannot assume the existence of a weak solution (i.e., the Minty condition), the next best way to ensure that there exists an \(\vartuple[][*] \in \svi(\set, \vioper)\) s.t. \(\langle \vioper(\vartuple[][][k+0.5]),\vartuple[][][k+0.5] - \vartuple[][*] \rangle \geq 0\) is to initialize the algorithm with an initial iterate \(\vartuple[][][0] \in \set\) which is \(O(\delta)\)-close to a \(\delta\)-local weak solution \(\vartuple[][*] \in \lmvi[][\vdelta](\set, \vioper)\)²⁹ for some \(\delta \geq 0\), and ensure that all subsequent intermediary iterates \(\left\{\vartuple[][][k + 0.5]\right\}_{k \in [\numhorizons]_{+}}\) remain \(\delta\)-close to \(\vartuple[][*]\).

To ensure this, we have to first bound the distance between the intermediary \(\left\{\vartuple[][][k + 0.5]\right\}_{k \in [\numhorizons]_{+}}\) and terminal \(\left\{\vartuple[][][k]\right\}_{k \in [\numhorizons]_{+}}\) iterates. The following lemma provides us with such a bound.

With 5

in hand, we can show that if the initial iterate starts close enough to some local weak solution, then the intermediate iterates will remain within this \(\vdelta\)-ball for the remainder of the algorithm for an appropriate choice of step size.

With 6 in hand, modifying the proof of [thm:mirror95extragradient95global95convergence] slightly, we can show local convergence to a strong solution when the initial iterate of the algorithm is initialized close enough to a local solution.

12 Omitted Proofs for Section 4↩︎

12.1 Walrasian Economies and Variational Inequalities↩︎

12.2 Results for Balanced Economies↩︎

12.3 Results for Variationally Stable Economies↩︎

12.4 The Scarf Economy↩︎

The following lemma states that any Scarf economy is a balanced economy.

13 Arrow-Debreu Competitive Economies as Competitive Walrasian Economies↩︎

An \((\numbuyers, \numcommods, \consumptions, \consendow, \util)\), denoted \((\consumptions, \consendow, \util)\) when clear from context, comprises a finite set of \(\numcommods \in \N_+\) divisible and \(\numconsumers \in \N_+\) . Each consumer \(\consumer \in \consumers\) is characterized by a \(\consumptions[\consumer] \subseteq \R^{\numcommods}\), an of commodities \(\consendow[\consumer] = \left(\consendow[\consumer][1], \dots, \consendow[\consumer][\numcommods] \right) \in \R^\numconsumers\), and a \(\util[\consumer]: \R^{\numcommods} \to \mathbb{R}\) which for any \(\consumption[\consumer] \in \consumptions[\consumer]\) describes the utility \(\util[\consumer](\consumption[\consumer])\) consumer \(\consumer\) derives.³⁰ We define any collection of per-consumer consumptions \(\consumption \doteq (\consumption[1], \ldots, \consumption[\numconsumers]) \in \consumptions\) a , where \(\consumptions \doteq \bigtimes_{\consumer \in \consumers} \consumptions[\consumer]\) is the , and any collection of per-consumer endowments an \(\consendow \doteq \left(\consendow[1], \ldots, \consendow[\numbuyers] \right) \in \R^{\numconsumers \numcommods}\).

From the proof of Theorem 1 of [2], we can infer that any Walrasian equilibrium \(\price[][][*] \in \simplex[\numgoods]\) of the Walrasian Arrow-Debreu competitive economy \((\numcommods, \excessset)\) is an Arrow-Debreu equilibrium price of \((\numconsumers, \numcommods, \consumptions, \consendow, \util)\). Further, as shown in the following lemma, the economy \((\numcommods, \excessset)\), as the name suggests, gives rise to a Walrasian competitive economy.

14 Classes of Variationally Stable Economies on \(\simplex[\numgoods]\)↩︎

We now discuss some important classes of Walrasian economies which are variationally stable on \(\simplex[\numgoods]\). The most basic class of Walrasian economies which are variationally stable on \(\simplex[\numgoods]\) are those which satisfy the law of supply and demand. Intuitively, these Walrasian economies are those for which the excess demand is downward sloping.

We note that the excess demand of a Walrasian economy satisfies the law of supply and demand iff \(-\excessset\) is monotone. This implies that \(-\excessset\) is quasimonotone, and hence for any non-empty and compact price space \(\pricespace \subseteq \R^\numgoods_+\) the VI \((\pricespace, -\excessset)\) satisfies the Minty condition (see Lemma 3.1 of [52]), meaning that any Walrasian economy which satisfies the law of supply and demand is variationally stable on \(\pricespace\).

Another important class of Walrasian economies which are variationally stable on \(\simplex[\numgoods]\) is the class of Walrasian economies which satisfy the weak gross substitutes condition. Intuitively, these are Walrasian economies for which the excess demand for a given good only increases when the price of some other good increases. While we omit the proof as it is involved, we note that any continuous balanced weak gross substitutes Walrasian economy \((\numgoods, \excessset)\) which satisfies Walras’ law, i.e., (for all \(\price \in \R^\numgoods_+, \excess(\price) \in \excessset(\price)\), \(\price \cdot \excess(\price)=0\)) is a subset of the class of variationally stable economies on \(\pricespace \subseteq \R^\numgoods_+\) for any non-empty and compact price space \(\pricespace\) (see, for instance Lemma 5 of [15]).

Going further, we can show that any Walrasian economy which satisfies the well-known weak axiom of revealed preferences [4], [14] is variationally stable on \(\simplex[\numgoods]\) (and more generally on any non-empty and compact price space \(\pricespace \subseteq \R^\numgoods\)). To this end, let us first define the weak axiom of revealed preferences for balanced economies.

As we show next, WARP implies that \(-\excessset\) is pseudomonotone in balanced economies.³¹

An important consequence of 10 is that since \(-\excessset\) is pseudomonotone, for any non-empty and compact price space \(\pricespace \subseteq \R^\numgoods_+\) the VI \((\pricespace, -\excessset)\) satisfies the Minty condition (see Lemma 3.1 of [52]). As such, we have the following corollary of 10.

15 Experiment Details↩︎

15.0.0.1 Computational Resources

.

15.0.0.2 Programming Languages, Packages, and Licensing

We ran our experiments in Python 3.12.12 [114] , using NumPy [115], Jax [116], and JaxOPT [117]. All figures were graphed using Matplotlib [118].

Python software and documentation are licensed under the PSF License Agreement. Numpy is distributed under a liberal BSD license. Pandas is distributed under a new BSD license. Matplotlib only uses BSD compatible code, and its license is based on the PSF license.

15.0.0.3 Experimental Setup Details

Each economy is initialized using a random seed to ensure reproducibility. Each consumer is assigned an initial endowment, drawn from a uniform distribution: \(\consendow[][][][\prime] \sim \mathrm{Unif}(10^{-6}, 1), \quad \forall \consumer \in [\numconsumers], \good \in [\numgoods].\) For numerical stability, we restrict the total economy-wide aggregate supply of each commodity to remain fixed at \(10\)³², to this end we normalize the endowments of consumers for all \(\good \in \goods\), \(\consumer \in \consumers\) to obtain their final endowment: \[\consendow[\consumer][\good] \doteq \frac{10 \consendow[\consumer][\good][][\prime]}{\sum_{\consumer \in \consumers} \consendow[\consumer][\good][][\prime]}.\]

Each consumer’s valuation of each commodity is drawn from a uniform distribution, i.e., for all \(\good \in \goods\), \(\consumer \in \consumers\): \[\valuation[\consumer][\good] \sim \mathrm{Unif}(0, 1) .\]

For any CES consumer \(\consumer \in \consumers\), the elasticity of substitution parameter \(\rho_\consumer\), is drawn as follows from the uniform distribution for substitutes and complements consumers respectively: \[\begin{align} &\rho_\consumer^{\text{substitutes}} \sim \mathrm{Unif}(0.6, 0.9) \; &\rho_\consumer^{\text{complements}} &\sim \mathrm{Unif}(-1000, -1) \end{align}\]

The initial price vector \(\price[][0]\) for the algorithms is drawn from a uniform distribution s.t. for all \(\good \in \goods\): \[\price[\good][0] \sim \mathrm{Unif}(1, 10) .\] We note that while we initialize the prices between \(1\) and \(10\) for numerical stability, this choice is without loss of generality since the excess demand is homogeneous of degree \(0\).

To summarize. Given a random seed, the initialization process consists of: 1) Sampling endowments from a uniform distribution and normalizing them to ensure total supply constraints; 2) sampling valuations from a uniform distribution; 3) sampling substitution parameters for CES consumers, 4) generating an initial price vector.

15.0.0.4 Pathwise Bregman Continuity

The pathwise Bregman continuity is verified for every experiment. For the choice of kernel function \(\kernel(\price) \doteq \frac{1}{2}\|\price\|^2\), Bregman divergence corresponds to half of Euclidean distance, therefore Bregman continuity becomes: \[\begin{align} \frac{1}{2} \norm[\vioper({\vartuple[][][k+0.5]}) - \vioper({\vartuple[][][k])}]^2 &\leq \lsmooth^2 \frac{1}{2}\norm[{\vartuple[][][k+0.5]} - {\vartuple[][][k]}]^2 \\ \frac{\norm[\vioper({\vartuple[][][k+0.5]}) - \vioper({\vartuple[][][k])}]^2}{\norm[{\vartuple[][][k+0.5]} - {\vartuple[][][k]}]^2} &\leq \lsmooth^2 \\ \frac{\norm[\vioper({\vartuple[][][k+0.5]}) - \vioper({\vartuple[][][k])}]}{\norm[{\vartuple[][][k+0.5]} - {\vartuple[][][k]}]} &\leq \lsmooth. \end{align}\]

Because Theorem [thm:mirror95extragradient95global95convergence] relies on the existence of a \(\lsmooth \in (0, \frac{1}{\sqrt{2}\learnrate[ ][ ]}]\), we have: \[\begin{align} \frac{\norm[\vioper({\vartuple[][][k+0.5]}) - \vioper({\vartuple[][][k])}]}{\norm[{\vartuple[][][k+0.5]} - {\vartuple[][][k]}]} &\leq \lsmooth \leq \frac{1}{\sqrt{2}\learnrate[ ][ ]} \\ \frac{\norm[\vioper({\vartuple[][][k+0.5]}) - \vioper({\vartuple[][][k])}]}{\norm[{\vartuple[][][k+0.5]} - {\vartuple[][][k]}]} &\leq \frac{1}{\sqrt{2}\learnrate[ ][ ]}. \end{align}\]

For every experiment, the value of the left hand-side term (the Lipschitz coefficient) is recorded at each iteration of the extratâtonnement algorithm. The maximum value among these recorded Lipschitz coefficients is then checked to be less than \(\frac{1}{\sqrt{2}\learnrate[ ][ ]}\), which is sufficient to show that the Bregman continuity is satisfied. This empirically verifies that excess demand is pathwise Bregman-continuous during the experiments.

15.0.0.5 Grid Search Experiments

We performed a grid search for a suitable step size for our experiments with Arrow-Debreu economies. To do so, we discretized an interval into 200 equally-spaced step sizes. Table ¿tbl:table:grid95intervals? lists the intervals that were used for each economy.

16 Additional Experiments with Arrow-Debreu Economies↩︎

In 10, we plot the Walrasian deviations at prices generated by each step of extratâtonnement in our seven Arrow-Debreu exchange economies, using step sizes that correspond to the (global) minimum best-iterate Walrasian deviation without satisfying pathwise Bregman continuity (See ¿tbl:table:ad95grid95search95step95sizes?). Similar to the convergence plots in 7, which use the step sizes that correspond to the minimum best-iterate Walrasian deviation while satisfying pathwise Bregman continuity, we observe fast convergence in all markets that are not inhabited by any linear consumers (economies 1–4 and 7); otherwise, convergence is slower.

The results presented in ¿tbl:table:convergence95bounds95opt? show that the minimum and final deviation values during these experiments also fall under the established loose upper bound, providing evidence of convergence for extratâtonnement when pathwise Bregman continuity is satisfied, as established by our theory.

References↩︎

---

1. [37] deemed a price-adjustment process “natural" if the update to commodity \(\good\)’s price depends only on the history of commodity \(\good\)’s prices and excess demands, but not on the prices or excess demands of any other commodities.↩︎

2. We refer the reader to 9 for additional related work on algorithms for Walrasian Economies and VIs.↩︎

3. While [40] introduced this algorithm as the “prox-method,” the name “mirror extragradient” is synonymous.↩︎

4. In the literature, a nomenclatural distinction is sometimes made between a where the optimality operator is a function and a , where it is a correspondence. Since we make this distinction through our choice of notation, we forego the “generalized” nomenclature.↩︎

5. The exact strong solution may be irrational, which is computationally intractable (see [50]).↩︎

6. A closed convex constraint set, \(L\)-Lipschitzness of the operator, and a non-empty set of strong solutions.↩︎

7. All proofs omitted from this section can be found in Appendix 11.↩︎

8. The assumption that \(\kernel\) is \(1\)-strongly-convex is without loss of generality since any \(\mu\)-strongly-convex kernel \(\kernel^\prime\) can be converted to a \(1\)-strongly-convex kernel \(\frac{1}{\mu} \kernel^\prime\).↩︎

9. See also 2 in Appendix 10 for an example involving a strictly concave function, for which both the mirror gradient and mirror extragradient methods diverge to infinity when initialized at a negative-valued point.↩︎

10. The “commodity” terminology is used here in the tradition of [2], and refers to any raw, intermediate, or finished products, as well as labor and services.↩︎

11. [62] enhance this formulation by incorporating Lagrange multipliers for budget constraints, thereby facilitating equilibrium existence proofs for a broader class of economies.↩︎

12. In more stylized applications such as Arrow-Debreu competitive economies [2], the excess demand correspondence is defined so as to be continuous only on the interior of the unit simplex, as the excess demand for a commodity can be infinite if its price is 0. An alternative modeling choice, which also does not modify the set of Walrasian equilibria, is to restrict the excess demand for a commodity to be bounded by the total amount of the commodity that can be ever supplied in the economy. [2] take exactly this approach in Section 3 of their paper when proving their seminal Walrasian equilibrium existence result, and it is also the approach we take in 8 (Appendix 13) to prove that any Arrow-Debreu competitive economy can be represented as a continuous competitive economy with bounded excess demand.↩︎

13. All commodities are assumed to be unique in some way.↩︎

14. Traditionally , the function \(\tatonnfunc\) is further restricted to be sign preserving, i.e., for all \(\price[ ] \in \R_+\) and \(\excess[ ] \in \R\), \(\sign(g(\price[ ], \excess[ ])) = \sign(\excess[ ])\). With this restriction in place, a tâtonnement process can be seen a mathematical model of the law supply and demand, which stipulates that the price of any commodity that is demanded (resp.supplied) in excess will increase (resp.decrease) [1], [4].↩︎

15. As \(\excess\) is a function of \(\price\), there is an indirect coupling of commodity prices, in spite of the informational restrictions of natural price-adjustment processes.↩︎

16. A similar observation was previously made by [8] for a smaller class of Walrasian economies known as convex potential markets.↩︎

17. Suppose that \(\excess\) is \(\lsmooth\)-Lipschitz-continuous on \([0, 1]^\numgoods\). By homogeneity of degree \(0\), we have, for all \(\alpha > 0\) and \(\price, \otherprice \in [0, 1]^\numgoods\), \(\norm[{\excess(\price) - \excess(\otherprice)}] = \norm[{\excess(\alpha\price) - \excess(\alpha \otherprice)}] \leq \lambda \alpha \norm[{\price - \otherprice}]\). Hence, taking \(\alpha \to 0\), we have, for all \(\price, \otherprice \in [0, 1]^\numgoods\), \(\excess(\otherprice) = \excess(\price)\).↩︎

18. We leave this question open for future work.↩︎

19. Bregman-continuous functions have been introduced in recent years in the optimization literature and have been shown to contain a large number of important function classes which are not continuous (see, for instance, [43]). Note that when the kernel function \(\kernel\) is chosen to be \(\kernel(\price) \doteq \frac{1}{2}\|\price\|^2\), \(\lsmooth\)-Bregman continuity reduces to \(\lsmooth\)-Lipschitz continuity. Further, the literature on algorithmic general equilibrium theory has considered variants of Bregman continuity to prove the polynomial-time convergence of the mirror tâtonnement process to Walrasian equilibria in restricted classes of Walrasian economies (see, for instance [8] and [7]). As such, Bregman continuity seems a natural assumption to prove the convergence of algorithms to a Walrasian equilibrium.↩︎

20. Prices do not converge here in the technical sense. Rather, further updates attempt to move prices outside the simplex, after which they are repeatedly projected back to this point.↩︎

21. We refer the reader to Appendix 13 on additional background and definitions on Arrow-Debreu exchange economies.↩︎

22. For reproducibility, our code is available and ready to run on . In addition, we include all details of our experimental setup in Appendix 15.↩︎

23. Among these utility functions, linear and Leontief utilities could cause the demand of a consumer of one or more commodities to approach \(\infty\) when the prices of these commodities approach \(0\). We thus bound the per-consumer per-commodity demand to be between 0 and the maximum supply of each commodity. Bounding the consumer demand in this manner does not modify the set of Walrasian equillibria [2].↩︎

24. We tested for pathwise-Bregman continuity using a fixed horizon, namely \(500\) for economy 1, and \(2000\) for economies 2 through 7. It is conceivable that the property in fact holds for an alternative choice of \(\tau\).↩︎

25. In our experiments, we choose to break ties “evenly," i.e., if there are multiple bang-per-buck goods, all of them are demanded in equal amounts.↩︎

26. In the context of Fisher markets, commodities are typically referred to as goods [8], as Fisher markets are often analyzed for a single time period only. More generally, in Arrow-Debreu markets, where commodities vary by time, location, or state of the world, "an apple today" may be different than "an apple tomorrow". For consistency with the literature, we refer to commodities as goods.↩︎

27. Recall that for monotone VIs, the set of strong and weak solutions are equal, as such here “solution” refers to both strong and weak solutions.↩︎

28. A \((\varepsilon, \delta)\) stationary point of a VI \((\set, \vioperset)\) is a point \(\vartuple[][*] \in \set\) s.t. for some \(\vdelta \geq 0\) there exists \(\vartuple \in \ball[\vdelta][{\vartuple[][*]}]\) and \(\vartuple\) is a \(\vepsilon\)-strong solution. Convergence to this weaker solution concept is necessary for VIs in which \(\vioperset\) is not singleton-valued for technical reasons, and any future work that seeks to generalize the results in this section should adopt this weaker definition to prove their convergence results.↩︎

29. Note that a local weak solution is guaranteed to be strong solution by Proposition 3.1 of [61].↩︎

30. In line with the literature (see, for instance, [111]), the value of this utility function should not be interpreted to have any meaning, and the utility function \(\util[\consumer]\) should be understood to represent a preference relation \(\prefer[\consumer]\) on the space of consumptions \(\consumptions[\consumer]\) so that for any two consumptions \(\consumption[\consumer], \consumption[\consumer][][][\prime] \in \consumptions\), \(\util[\consumer](\consumption[\consumer]) \geq \util[\consumer](\consumption[\consumer][][][\prime]) \implies \consumption[\consumer] \prefer[\consumer] \consumption[\consumer][][][\prime]\).↩︎

31. To be more precise, we note that an excess demand function satisfies WARP iff is strictly pseudomonotone. However, as this result will not be used we present the more general result.↩︎

32. This is without loss of generality since commodities are divisible.↩︎