Solving Deterministic and Stochastic Equilibrium Problems via Augmented Walrasian

Abstract

We described a method to solve deterministic and stochastic Walras equilibrium models based on associating with the given problem a bifunction whose maxinf-points turn out to be equilibrium points. The numerical procedure relies on an augmentation of this bifunction. Convergence of the proposed procedure is proved by relying on the relevant lopsided convergence. In the two-stage versions of our models, deterministic and stochastic, we are mostly concerned with models that equip the agents with a mechanism to transfer goods from one time period to the next, possibly simply savings, but also allows for the transformation of goods via production.

1 Introduction

The economic equilibrium model proposed by Arrow and Debreu (1954) for a competitive economy implicitly assumes that the entire economic activity will take place in a single time span, implicitly instantly. As soon as one includes the agent’s concerns about the future, one has to consider an inter-temporal component, intrinsically dynamic, and take into account the uncertainty about this future. Here, our primary goal is to design numerical procedures to solve (two-stage) stochastic Walras equilibrium models where goods get transferred from time 0 to time 1 via “home production;” clearly, this will usually include the possibility of retention.

The overall approach to this stochastic model is based on a fundamental decomposition-result that allows us obtain the overall equilibrium by spliting the calculation into one that deals with each state separately. Consequently, our first concern is with an algorithmic procedure that will deliver, rather efficiently, an equilibrium solution for a classical exchange model, i.e., in a static, deterministic environment. As a stepping stone to our stochastic model, we consider then, a two-stage (dynamic,deterministic) Walras model that allows for the transfer of goods between time 0 and time 1 via home production and we exploit its particular structure to streamline the computational procedure. We rely systematically on an augmentation method applied to what’s called the Walrasian: essentially, the function ‘supposedly solved’ by the Walrasian auctioneer and a maxmin characterization of an equilibrium point. The fact that the theory allows us to proceed, in the iterative process, with approximate equilibria turns out to be critical in the development of the overall numerical scheme.

Our approach deviates, even in the deterministic case, from the path-breaking methods suggested by Scarf and Hansen (1973), Eaves (2011), Brown et al. (1996), Saigal (1983), and other approximation strategies described in the books by Judd (1998), and Brown and Kubler (2008). These earlier methods are not efficient when the economies have a significant number of goods or agents, even for reaching approximate equilibria, as their solution strategies rely on an enumerative argument, and smoothness of the excess demand function. Moreover, in stochastic environments, these results are prohibitively time-expensive.

In this paper, we develop an approach based on an augmented Walrasian technique and a lopsided convergence approximation procedure, which allows us to cope with large equilibrium problems including uncertainty and heterogeneity on the agents. By using this approach we have designed a two-phase algorithm without computing derivatives of the demand function. We report several numerical experiments for equilibrium problems involving up to 5 agents, 7 goods and 10 stochastic scenarios, which can be easily expanded in the number of agents and goods. Finally, the procedure proposed in this paper might be parallelized in terms of agents and the multi-start strategy.

The paper is organized as follows. In Sect. 2 we review the general equilibrium problem for a pure-exchange economy, setting notation, and definitions. In Sect. 3, we provide the foundation of our new approach, stating the equilibrium problem as an optimization problem of the maxinf family, and developing the augmentation technique to construct a solution algorithm. This section ends with some numerical examples of pure-exchange economies. Section 4 is a stepping stone in the economies considered in this manuscript, where the agent problem is given by a two-stage deterministic optimization problem, with home production. In Sect. 5 we proposed our final economic model, a two-stage stochastic exchange economy, where agents face uncertainty about the second stage of the economy. We provide the maxinf characterization, as well as a solution algorithm based in the augmented Walrasian previously defined. Finally, Sect. 6 concludes and provides some remarks about the numerical performance of our algorithm, as well as some prospective future lines of research.

2 The Arrow–Debreu Model

To set the stage and fix terminology and notation, let’s start with the barter, or pure exchange model, of Debreu (1959). A finite number of (individual) agents $i\in \mathcal{I}$ with initial endowments , consisting of a finite number of goods, to be bartered so as to maximize, individually, their upper semicontinuous (usc) concave utility functions that depend on the level of the acquisitions of these goods, potentially for “consumption”; one refers to as the survival sets; note that the concavity of $u_i$ implies that the survival set $X_i$ is convex, typically unbounded. The value to assign to each good, in this trading process, depends on a market price system that will restrict each agent to limit the “market value” of its acquisitions to the “market value” of its endowment, i.e., $\langle p,x \rangle \le \langle p, e_i \rangle$; since these prices don’t necessarily reflect monetary prices, the “values” are often referred to as units of account. Given , each agent maximizes its utility subject to its budgetary constraint, i.e.,

For the market to be in equilibrium the total demand must not exceed total supply, i.e., with s designating the excess supply function,

$$\begin{aligned} s(p) = \sum _{i\in \mathcal{I}} (e_i - x_i(p)) \ge 0. \end{aligned}$$

Since, we haven’t ruled out the possibility that at equilibrium the prices of some goods might turn out to be 0, as for free disposal goods, one can also write this condition in terms of a geometric variational inequality:

where $N_C(p)$ denotes the normal cone of variational analyis Rockafellar and Wets (1998) to the set C at p, or still, must be solutions of the linear complementarity problem,

$$\begin{aligned} 0 \le p \perp \sum _{i\in \mathcal{I}} (e_i -d_i(p)) \ge 0. \end{aligned}$$

Since the budgetary constraints are positively homogeneous in the price p, and the price is not zero for every good, $p \ne 0$, no additional restriction is introduced by insisting that the price system should be scaled so that it lies in the unit simplex . This is often included in the formulation of the problem to enable appealing to a fixed point argument to establish existence or to provide boundedness in the design of a computational scheme.

Additionally, to maintain the boundedness of the agent utility maximization problem, we introduce a natural bound for each agent demand function $x_i(p)\le \sum _{i\in \mathcal{I}} e_i$ [see Debreu (1959, Ch.5)], i.e., no agent can demand more quantity of each good than the total resources of that good available in the economy. These bounds naturally provide a lower bound for the excess supply function, i.e. $s(p)>-\infty$.

3 Augmented Walrasian

3.1 Walrasian and the Equilibrum Problem

Our assumptions and notation introduced in the previous section follow those of the article “Continuity properties of Walras equilibrium points” Jofré and Wets (2002). This article provides a formulation of the equilibrium problem for an exchange economy as a maxinf optimization problem. It introduces the Walrasian bifunction associated with this problem

$$\begin{aligned} W(p,q) = \langle q,s(p) \rangle \;\,\;\hbox {on}\;\, \varDelta \times \varDelta \end{aligned}$$

where $p,q \in$ the (unit) price simplex , and s is the excess supply function as defined in the previous section. The first fundamental result that we consider [Jofré and Wets (2002, Theorem 14)] is related with the existence of maxinf points of W, and how they correspond to the solutions of the equilibrium problem. In our setting, considering excess supply instead of excess demand functions, it is given by the following lemma

Lemma 1

(Walras equilibrium prices and maxinf-points) The function W has a max-inf point $\bar{p}\in \varDelta$ such that

$$\begin{aligned} 0\le \inf _{q\in \varDelta }W(\bar{p},q)\,=\,\max _{p\in \varDelta }\inf _{q\in \varDelta } W(p,q), \end{aligned}$$

Moreover, every maxinf-point $\bar{p}$ of the Walrasian function is an equilibrium point, i.e. $s(\bar{p})\ge 0$.

Proof

The existence of max-inf points for the Walrasian function follows by applying the Ky-Fan inequality [Aubin and Ekeland (2006, Theorem 6.3.5)] to W. For this, it is easy to check that W is a Ky-Fan function: (1) Note that the upper-semicontinuity of the agents’ utility functions grants the upper-semi continuity of W in its first argument, (2) it is linear in its second argument, and (3) by Walras’ law, $W(p,p)\ge 0$.

If $\bar{p}$ is a maxinf-point of the Walrasian with $W(\bar{p},\cdot ) \ge 0$, it follows that for all unit vectors $e^j=(0,\ldots ,1,\ldots )$, the j-th entry is 1, $\langle e^j, s(\bar{p}) \rangle \ge 0$ which implies $s(\bar{p}) \ge 0$. $\square$

The condition of $W(\bar{p},\cdot ) \ge 0$ follows by the definition of W and noting that for every price $p\in \varDelta$, and under local nonsatiation preferences assumption, $W(p,p)=0$. Furthermore, the converse of Lemma (1) also holds, i.e., every equilibrium point is a maxinf-point of W [Jofré and Wets (2014, Prop. 2.4)].

The formulation of the equilibrium problem as an optimzation problem of finding the maxinf points of the Walrasian is closely related to the existence proof developed by in Arrow and Debreu (1954), Kirman (1998, Ch.1) where the existence of equilibrium points follows by the application of Kakutani’s fixed point theorem to a set-valued mapping, defined in the interior of the simplex, given in our setting as

$$\begin{aligned} p\in \varDelta \mapsto \phi (p)={\left\{ \begin{array}{ll}\big \lbrace \pi {\,\big \vert \,}\langle \pi ,\, s(p)\rangle = \inf _{q\in \varDelta } \langle q, s(p)\rangle \big \rbrace &{}\quad p\in \mathrm{int}\varDelta \\ \big \lbrace \pi {\,\big \vert \,}\langle \pi ,\, s(p)\rangle = 0\big \rbrace &{}\quad p\in \partial \varDelta \end{array}\right. } \end{aligned}$$

It is immediate that the definition of the Walrasian is intrinsically present in the original proofs. Moreover, one can associate the maxinf optimization problem as the one of the Walrasian auctioneer: first, the inf-problem identifies the market with the largest imbalance in supply/demand, and then, the max-problem adjust the prices in order to reduce it. Therefore, the saddle point reflects the equilibrium state of the market.

3.2 Non-Concave Duality and Augmentation

Since our basic approach, first suggested by Bagh (2002), is related to that for the augmented Lagrangian, it’s informative to consider the bifunction that might have led to the Walrasian in a standard non-convex duality scheme [Rockafellar and Wets (1998, §11.K)]. Let’s introduce a pre-Walrasian obtained as a restricted-partial conjugate, with respect to the q-variable, i.e., for all $p\in \varDelta$

$$\begin{aligned} V(p,u) = {\mathop {\hbox {sup}}\limits _{\;z\in \varDelta }}\,[\,\langle u,z\rangle - W(p,z)\,]. \end{aligned}$$

$V(p,\cdot )$ is clearly convex and one can think of the family of bifunctions as ‘perturbations’ of a ‘fundamental’ primal-problem

$$\begin{aligned} \,\;\hbox {find}\;\,\;\hat{p} \in {\mathop {\mathop {\mathrm{argmax}}\nolimits }\limits _{\;p\in \varDelta }}\,v(p) \,\quad \hbox {where}\quad \, v(p) = V(p,0) = -\inf _{\,q\in \varDelta }\,[\,W(p,q)\,]. \end{aligned}$$

By conjugacy, since the functions $q\mapsto W(p,q)$ on $\varDelta$ are proper, lower semicontinuous (lsc) and convex, so are the functions $u\mapsto V(p,u)$.

Note that $\min _{\,q\in \varDelta }\,\langle q,s(p) \rangle$ will yield the q that generates the smallest convex combination of the elements of s(p). So, if for any l, $s_l(p) <0$, it follows that $v(p) >0$. Thus, $\hat{p}$ will be such that an element of the vector $s(\hat{p})$ will be as negative as possible it will minimize the $\ell ^{\scriptscriptstyle \infty }$-norm of s(p).

The process of going from v to the collection is well-understood; it can be viewed as associating to a particular optimization problem, $\max \big \lbrace v(p) {\,\big \vert \,}p\in \varDelta \big \rbrace$, a perturbed collections that leads to the analysis of stability. But in our setting what is this particular optimization problem? It can be viewed as the Walrasian auctioneer’s problem. It’s easy to see that it’s optimal value is 0 which is attained when the Walrasian auctioneer has selected a price system that yields an equilibrium. Generally it’s not a concave as a function of p, and certainly not a strictly concave function, and thus one can’t expect a unique maximizer which highlights the well-known fact that, in general, Walras equilibrium points are not unique.

In order to compute equilibrium points for an economy, we propose a strategy to find a max-inf point of W by an approximating scheme. Our first goal is to build a family of approximating bifunctions by relying on an augmentation technique that skirts the lack of concavity [Rockafellar and Wets (1998, §11.K)]. Let be an augmenting function, i.e., it’s convex, $\mathrm{argmin}\,\sigma = \{0\}$ and $\min \sigma = 0$. Typically, $\sigma = |\cdot |$ is chosen to be a norm but depending on the application it could be quite different; recall that we can even choose $\sigma$ to take on the value $\infty$, for example, it could be a norm of some type restricted to a ball centered at 0, or even more exotic. In particular, the self-dual function, defined as $\sigma =\frac{1}{2}|\cdot |^2$, provides some computational advantages, as being a quadratic function, with the property that $\sigma ^*=\sigma$, its conjugate turns out to be the same function.

Given the augmenting function $\sigma$ and a scalar $r>0$, the augmented Walrasian, by definition, is

For a fixed p, considering the convexity of $V(p,\cdot )$ and $\sigma$, one can re-write the definition of $\widetilde{W}_r$ as a partial conjugate w.r.t the u-variable. Additionally, by the property of conjugation of a sum and the definition of the epi-sum (), we have the following chain of identities

where $\sigma ^*$ is the conjugate of $\sigma$, i.e., $\sigma ^*(v)=\sup _x\big \lbrace \langle v,x\rangle -\sigma (x) \big \rbrace$. Thus, the augmented Walrasian function in its final form is the infimum of a convex function, and depending of our choice of $\sigma$, possibly quadratic or linear.

Finally, for a given choice of augmenting function $\sigma$ and a sequence of scalars $\{r^\nu :\nu \in {IN}\}$, it is possible to define a sequence of augmented Walrasians, $\{W^\nu :\nu \in {IN}\}$. The next step is to study the approximation and convergence properties of this family, and how the computation of its associated sequence of maxinf points is related with the goal of finding an equilibrium price for the original economy.

3.3 Approximation and Lopsided Convergence

Before giving a notion of approximation for equilibrium problems, we first establish a definition for an approximating equilibrium point, given by a price such that the associated excess supply function is close to satisfying the market clearing condition.

Definition 1

(approximate maxinf-points). For $\epsilon \ge 0$, $p_\epsilon$ is said to be an approximate equilibrium point or approximate maxinf-point of W if $\inf W(p_\varepsilon ,\cdot ) \ge \sup \inf W-\varepsilon$, and the set of all such approximating maxinf-points is denoted by $\varepsilon \hbox {-}\mathrm{argmaxinf}\, W$.

Note that given an approximating equilibrium price, $p_\epsilon$, one can adjust the agents’ initial endowments by a fraction of $\epsilon$ and make $p_\epsilon$ and equilibrium price. In addition, note that the concept of an approximating equilibrium price is associated with the proximity of satisfying the market clearing condition, which is not necessarily related to proximity to an equilibrium point.

Considering the family of augmented Walrasian perturbations, and a sequence of their corresponding approximate max-inf points, one should be able to guarantee a convergence result of this sequence of points, given the convergence of the family of augmented functions. This condition can be obtained by appealing to lopsided convergence, or lop-convergence, of the augmented Walrasian to the Walrasian. Given the compactness of the domain, one doesn’t have to appeal to the (more comprehensive) definition of lopsided convergence it suffices to refer to a more restrictive version, namely tight lopsided convergence; for the general definition and further details, consult Jofré and Wets (2009, 2014).

Definition 2

(tight lopsided convergence) A sequence in finite-valued bivariate functions, fv-biv(), defined over a compact set $C\times D$, lop-converges tightly to a function , also in fv-biv(), if

• (a) for all $y\in D$, and all $(x^\nu \in C)\rightarrow x\in C$, there exists $(y^\nu \in D) \rightarrow y$ such that

  $$\begin{aligned} \limsup _\nu F^\nu (x^\nu ,y^\nu ) \le F(x,y), \end{aligned}$$

• (a−t) and for all $\epsilon >0$, there is a compact set $A_\epsilon$ such that for all $\nu$ large enough,

  $$\begin{aligned} \sup _{x\in C^\nu \cap A_\epsilon } \inf _{y\in D^\nu } F^\nu (x,y) \ge \sup _{x\in C^\nu } \inf _{y\in D^\nu } F^\nu (x,y)-\epsilon . \end{aligned}$$

• (b) For all $x\in C$, there exists $(x^\nu \in C) \rightarrow x$ such that given any $(y^\nu \in D) \rightarrow y\in D$,

  $$\begin{aligned} \liminf _\nu F^\nu (x^\nu ,y^\nu )\ge F(x,y), \end{aligned}$$

• (b−t) and for any $\epsilon >0$ and one can find a compact set $B_\epsilon \ne \emptyset$, possibly depending on $\big \lbrace x^\nu \rightarrow x\big \rbrace$, such that for all $\nu$ sufficiently large,

  $$\begin{aligned} \inf _{D^\nu \cap B_\epsilon } F^\nu (x^\nu ,\cdot ) \le \inf _{D^\nu } F^\nu (x^\nu ,\cdot )+\epsilon . \end{aligned}$$

The desired convergence result for the equilibrium points follows from adaptating the tight lop-convergence given by Jofré and Wets (2014, Theorem 3.2) to our case with compact (and invariant) domains.

Theorem 1

[convergence of maxinf-points, Jofré and Wets (2014, Theorem 3.2)] Let $C\times D$ be a compact subset of . When the bifunctions $\big \lbrace F^\nu \big \rbrace _{\nu \in {IN}}$ lop-converge tightly to F, all in fv-biv($C\times D$) with $\sup \inf F$ finite, and , then every cluster point $\bar{x}\in C$ of a sequence of $\epsilon ^\nu$-maxinf points of the bifunctions $F^\nu$ is an $\epsilon$-maxinf point of the limit function F.

In particular, this implies that in these circumstances, every cluster point of a sequence of maxinf-points of the bifunctions $F^\nu$ is a maxinf-point of the lop-limit function F.

In order to obtain our convergence result for approximating maxinf points, the following result is an application of the previous theorem in our framework. It tells us that tight lopsided convergence of the augmented Walrasian entails convergence of equilibrium points.

Theorem 2

(convergence of $\epsilon$-maxinf points) Suppose that $p \mapsto s(p)$ is usc on $\varDelta$. Consider the non-negative sequences $\big \lbrace r^\nu ,\, \nu \in {IN}\big \rbrace$ and $\big \lbrace \epsilon ^\nu ,\, \nu \in {IN}\big \rbrace$ such that , . Let $\big \lbrace W^{\nu },\, \nu \in {IN}\big \rbrace$ be a family of augmented Walrasian functions associated which each augmenting parameter $r^\nu$. Let $p^{\nu } \in \epsilon ^{\nu } \hbox {-}\mathrm{argmaxinf}\, W^{\nu }$ and $\bar{p}$ be any cluster point of $\big \lbrace p^{\nu },\,\nu \in {IN}\big \rbrace$. Then $\bar{p} \in \epsilon \hbox {-}\mathrm{argmaxinf}\, W$.

Proof

It suffices to show that $\big \lbrace W^\nu ,\, \nu \in {IN}\big \rbrace$ lop-converges tightly to W and conclude by Theorem (1) the convergence of a (sub)sequence of $\epsilon ^\nu$-maxinf points. In order to prove tight lopsided convergence, let $q\in \varDelta$, $\big \lbrace p^\nu ,\, \nu \in {IN}\big \rbrace \rightarrow p\in \varDelta$. Define $q^\nu \equiv q,\,\nu \in {IN}$. Then

and as the function $p \mapsto s(p)$ is usc,

$$\begin{aligned} \limsup W^\nu (p^\nu , q^\nu ) = \limsup W(p^\nu ,q) \le W(p,q). \end{aligned}$$

On the other hand, let $p\in \varDelta$ and $\big \lbrace q^\nu ,\, \nu \in {IN}\big \rbrace \rightarrow q$. By compactness of $\varDelta$, $q\in \varDelta$ and defining $p^\nu = p,\, \nu \in {IN}$, $W^\nu (p,q)$ is the inf-projection of the function $F^\nu (q,z) = W(p,q-z) + r^\nu *\sigma ^*(z)$ in the z-variable. Thus, $F^\nu$ is level bounded in z locally uniform in q and therefore $W^\nu (p,\cdot )$ is lsc by Rockafellar and Wets (1998, Theorem 1.17). Finally,

$$\begin{aligned} \liminf W^\nu (p^\nu ,q^\nu ) \ge W(p,q), \end{aligned}$$

since for any $q_0 \in \varDelta$, $W^{\nu }(p,q_0)\rightarrow W(p,q_0)$ as $\nu \rightarrow \infty$ and the conclusion follows from a standard diagonal argument. $\square$

The following inmediate corollary of this theorem, with $\epsilon = 0$, plays a pivotal role form a numerical viewpoint

Corollary 1

($\epsilon$-maxinf and equilibrium points) Let . Then, every cluster point of a sequence of $\epsilon ^\nu$-approximating equilibrium points of a sequence of augmented Walrasian functions is an equilibrium point for the original economy.

The major thrust of the eventual algorithmic procedures is to replace finding local near maxinf-points of W by finding a local saddle point of a $\widetilde{W}^\nu$ for $\nu$ large enough (but not too large to avoid numerical instabilities). Under this scheme, there are several options for choosing the augmenting function $\sigma$. For example, one can consider $\sigma =|\,\cdot \,|$ a norm whose dual norm will be denoted by $|\cdot |_o$, then one can express the augmented Walrasian as

$$\begin{aligned} \widetilde{W}^\nu (p,q) = \min _z \left[ \, W(p,z) {\,\Big \vert \,}z\in {IB}_0(q,r^\nu )\cap \varDelta \,\right] , \end{aligned}$$

where ${IB}_0(q,r^\nu )$ is the dual ball with center in q and radius $r^\nu$. Alternatively, for $\sigma$ be the self-dual function, i.e., $\sigma =\frac{1}{2}|\,\cdot \,|_2^2$, the augmented Walrasian takes the form

$$\begin{aligned} \widetilde{W}^\nu (p,q) = \min _z \left[ \, W(p,z)+\frac{1}{2r^\nu }|z-q|_2^2 \,{\,\Big \vert \,}z\in \varDelta \,\right] . \end{aligned}$$

There is quite a variety of procedures for finding these near local saddle-points. One possible procedure to solve the problem at hand is described next:

• At iteration $\nu +1$, given $(p^\nu ,q^\nu )$ with $r = r_{\nu +1}$ ($\ge r_ \nu$), the Phase I (or primal) consists in solving

  $$\begin{aligned}q^{\nu +1} \in {\mathop {\mathrm{argmin}}\limits _{q\in \varDelta }}\,\widetilde{W}^{\nu +1}(p^\nu ,q) \end{aligned}$$

  note that the ‘internal’ minimization is either that of a linear form on a ball, this seems to favor $|\cdot |_o$ as the $\ell ^{\scriptscriptstyle \infty }$-norm, or the self-dual augmenting function which yields an immediate solution.

• How to carry out the next step will depend on the ‘shape’ and the properties of the demand functions. For example, this turns out to be rather simple when the utility functions are of the Cobb–Douglas type, defining the Phase II (or dual) as finding

  $$\begin{aligned} p^{\nu +1} \in {\mathop {\mathrm{argmax}}\limits _{p\in \varDelta }} \,\widetilde{W}^{\nu +1}(p,q^{\nu +1})\, \end{aligned}$$

In virtue of the Corollary (1), we know that as , $p^\nu \rightarrow \bar{p}$ a maxinf-point of W, equivalently an equilibrium price system for Walras’ problem. The strategy for increasing $r^\nu$ should take into account (i) numerical stability, i.e., keep $r^\nu$ as small as possible and (ii) efficiency, i.e., increase $r^\nu$ sufficiently fast to guarantee accelerated convergence.

We appeal to this new formulation to highlight two major features of our approach. First, embedding the equilibrium problem into a family of perturbed optimization problem induces a notion of stability of each iteration, where the algorithm performs its iteration in a robust manner, and without jumping too far ahead of the current iteration point. Secondly, the optimization nature of the maxinf problem opens a wide variety of well-known and developed computational libraries that can solve the corresponding optimization problem for each phase of the algorithm.

3.4 Numerical Implementation for the Arrow–Debreu Model.

The proposed algorithm was implemented in Pyomo [Python Optimization Modeling Objects, Hart et al. (2012)], a mathematical programming language based on Python. The problems that we solve come with the following features:

• In order to describe the economy, we consider utility functions of Cobb–Douglas and Constant Elasticity of Substitution (CES) type, and strictly positive aggregated initial endowment for every good.

• For the selection of the augmenting function $\sigma$, we primarily considered the self-dual type, given by $\sigma =\frac{1}{2}|\cdot |_2^2$.

• For the agent problem, everyone has to maximize a concave utility function over a linear constrained set determined by budgetary constraint and nonegativity of the solution. This problem is solved using the interior point method, Ipopt, implemented by Wächter and Biegler (2006) (which gives satisfactory results for problems of this nature).

• Phase I consists of the minimization of a quadratic objective function over the simplex of prices. This is solved using Gurobi Optimization (2014), a state-of-the-art and efficient algorithm.

• Phase II is the critical step of the entire augmented Walrasian algorithmic framework. We need to overcome the (typical) lack of concavity of the objective function. Thus, the maximization is done without considering first order information and relying on BOBYQA algorithm Powell (2009). which performs a sequentially local quadratic fit of the objective functions, over box constraints, and solves it using a trust-region method.

All the examples were run on a 3.30 GHz Intel Core i3-3220 processor with 4 GB of RAM memory, under Ubuntu 12.04 operating system.

In what follows, a set of numerical examples is described. The first example corresponds to a toy model, which turns out to be useful in the general description of how the algorithm acts in every interation to get to an equilibrium price. The second one provides a direct benchmark for the performance of our algorithm applied to a classical example in the literature, provided by Scarf [Kirman (1998, Chapter 4)]. This section ends with an example of an exchange economy with symmetric agents and a large size of commodities reflecting the computational power of the augmented Walrasian approach.

Fig. 1

Homogeneus Agents (Example 1)

Example 1

(symmetric agents). To test the overall performance of the algorithm we start with a basic example. Consider an economy of three goods and two agents, with utility functions within the CES family, i.e.,

$$\begin{aligned} u_i(x)=\left( \sum _{j=1}^3 (a_{i,j})^{\frac{1}{b_i}}(x_j)^{\frac{b_i-1}{b_i}}\right) ^{\frac{b_i}{b_i-1}}, \end{aligned}$$

with survival sets $X_i=[10^{-3},\infty )^2$, for each agent.

Details In this first example, the agents are symmetric, i.e., their utility functions’ coefficients are equal, given by $a_{i,j}=\frac{1}{3}$, $i=1,2,\,j=1,2,3$ and $b_i=\frac{1}{2}$, $i=1,2$, as well as their initial endowments $e_{i,j}=1$, $j=1,2,3\,,i=1,2$. It is easy to see that, by symmetry of the agents, the equilibrium price for this economy is given by $p^*=(\frac{1}{3},\frac{1}{3},\frac{1}{3})$, and it is unique. Computationally, we initialize the algorithm at an arbitrary point of the simplex, in this case, $p^0=(0.12, 0.56, 0.32)$. The trajectory of prices $\{p^\nu \}$ and excess supply evaluations $\{s(p^\nu )\}$ performed by our algorithm are depicted in Fig. 1. The first graph describes the price evolution, where each good is represented by a line (prices are scaled by a factor of 100). The second graph depicts the behaviour of the corresponding excess supply function, where each good is again represented by a line. The adjustment process of the prices shows the Walrasian auctioneer’s problem, where in every iteration, the algorithm identifies the good of the excess supply function with the corresponding least value, and performs an iteration adjusting its price for the next period. As the algorithm progresses, it converges to the equilibrium price. $\square$

Table 1 Initial endowments for Example 2

Table 2 Utility parameters for Example 2

Example 2

(exchange economy; Scarf example). Consider the example described in Scarf in Kirman (1998, Chapter 4): exchange economy involving five type of consumers and ten comodities. The initial endowment for each agent is given by Table 1.

Details The utility functions correspond to the CES-type, for which the parameters $a_{ij}$ and $b_i$ for each consumer are described in Table 2.

The algorithm was set with the self-dual augmenting function, and the centroid of the simplex as the initial point. Additionally, the augmenting parameter was updated by a geometric progression $r^{\nu }=1.259^\nu$. The trajectory of prices $\{p^\nu \}$ and the corresponding sequence of excess supply evaluations are depicted in Fig. 2. In this example, the convergence to an approximate equilibrium point for $\epsilon =10^{-1}$ is obtained within 37 iterations, taking a machine time of 114 [min]; for $\epsilon =10^{-2}$, 53 iterations were required taking 179 [min]. The price is given by

$$\begin{aligned} p^*=\left( 18.4,\,11.0,\,9.9,\,4.4,\,12.5,\,7.7,\,11.7,\,10.2,\,9.9,\,4.3\right) \end{aligned}$$

As in the previous example, the price sequence describes a trajectory that can be associated with the Walrasian auctioneer’s problem. Note the stability of the performance: after few iterations, the algorithm reaches an approximating equilibrium. Similar results are obtained with different starting points, as well as different augmenting sequences, that are not included in this manuscript. $\square$

Fig. 2

Scarf’s example (Example 2)

Example 3

(large scale, symmetric agents economy). In this example, we consider a larger economy, with a total of 50 consumption goods and 10 agents with homogeneous CES utility functions defined over survival sets given by $[10^{-3},\infty )^{50}$.

Details The starting price is a random point in the simplex. As expected, the trajectory of the approximating prices $\{p^\nu \}$ converges to the unique equilibrium price system, in which every good has the same price, i.e., $p_g=\frac{1}{50},\,g=1,\ldots ,50$. The convergence of the sequence of prices, $\{p^\nu \}$ and the corresponding sequence of excess suppy functions $\{s(p^\nu )\}$ is illustrated in Fig. 3. $\square$

Fig. 3

Large scale, symmetric agents (Example 3)

From the examples previously described, a crucial observation can be made regarding the stability of the iterative process: the algorithm approaches an approximating equilibrum with about half of the total iterations. This behaviour is robust in every simulation performed, and one find a reason in the introduction of the augmenting function.

It’s noteworthy that, in all cases, after a few iteration, the procedure finds an approximate equilibrium which one should be able to exploit when dealing with equilibirum problems in a stochastic environment.

4 Two-Stage Deterministic Equilibrium Model

As a stepping stone to the solution of stochastic Walras equilibrium models, we are going to rely on solving, efficiently, deterministic two-stage versions of the Walras equilibrium model. This model includes an exchange economy with a deterministic two-stage structure, where agents make intertemporal consumption decisions, as well as an activity-level decision for their particular home-production plan. Equilibrium conditions and an approximation scheme via augmented Walrasian is provided. Finally, a solution strategy for the agents’ problems is provided, in order to solve them efficiently.

4.1 Agents’ Problem and Equilibrium Formulation

Given a price system $p = (p^0, p^1)$ with $p^t$ the price vector in vigor at time t, each agent $i\in \mathcal{I}$ determines its optimal consumption plan $\bar{x} = (\bar{x}_i^0, \bar{x}_i^1)$ as the solution of the following utility maximization problem,

$$\begin{aligned} \max _{x^0,y,x^1}\;&u_i^0(x^0) + u_i^1(x^1) \\ \hbox {so that}&\;\langle p^0, x^0 + T_i^0y\rangle \le \langle p^0, e_i^0 \rangle , \\&\langle p^1, x^1 \rangle \le \langle p^1, e_i^1 + T_i^1y\rangle , \\&\;\; x^0 \in X_i^0,\quad y\in Y_i, \quad x^1\in X_i^1, \end{aligned}$$

where $u_i^t, e_i^t$ and $X_i^t$ are the utility functions, the endowments and the survival sets for agent i at time $t = 0,1$. As in Sect. 2, the utility functions are assumed to be usc and concave, providing the closedness and convexity of the corresponding survivals sets.

Each agent has access to (their individual) technology to transform goods from the first stage to the second one. The technology for each agent is modeled by a given pair of matrices $T_i^0,T_ i^1$, and the agent’s decision is modeled by an activity-level variable y. Therefore, each agent determines a set of activities at time 0 that requires an input of goods $T_i^0y$ and produces a deterministic output $T_i^1y$ at time 1. The set of potential activities that are at the disposal of agent-i is determined by the closed convex cone ; in many instances, one would simply have but not necessarily in general. One can think of the pair of matrices $(T_i^0, T_i^1)$ as determining an input/output (home production) process that could simply be savings including enhancements or deterioration, or investment activities, retention, and so on. Of course, the agent chooses y so as to maximize its overall utility; note, $u_i^1$ could include a discount factor that doesn’t have to be made explicit here.

The excess supply function $s(p) = (s^0(p^0,p^1), s^1(p^0,p^1))$ is given as usual as the difference between the total amount of goods available in each time period and the total endowments adjusted by the goods used or generated by the input/output process, i.e.,

$$\begin{aligned} s^0(p)&= \sum \nolimits _{i\in \mathcal{I}}[\,e_i^0 - (x_i^0(p) + T_i^0 y_i(p))\,], \\ s^1(p)&= \sum \nolimits _{i\in \mathcal{I}}[\,(e_i^1+T_i^1 y_i(p)) - x_i^1(p)\,], \end{aligned}$$

where $(x_i^0(p),y_i(p), x_i^1(p))$ is the optimal solution for agent i of its utility maximization problem.

The Walrasian bifunction for this economy, is defined by

$$\begin{aligned}W(p,q) = \langle q,s(p) \rangle = \langle q^0, s^0(p^0,p^1) \rangle +\langle q^1, s^1(p^0,p^1) \rangle , \end{aligned}$$

where a price $\bar{p} = (\bar{p}^0, \bar{p}^1)$ is and equilibrium price system if $s(\bar{p}) \ge 0$. As in the static (one-stage) model, it can be shown that such a $\bar{p}$ is a maxinf-point of the Walrasian and its existence is provided as W is a Ky Fan function. One possible approach in finding such a maxinf-point is based on the Augmented Walrasian approach described in §3.

Theorem 3

(dynamic deterministic maxinf-points) Consider the Walrasian function W for the previous economy. Assuming local nonsatiation preferences, every maxinf-point $\bar{p}=(\bar{p}^0,\bar{p}^1)$ of W is an equilibrium point, i.e., $s^0(\bar{p})\ge 0$ and $s^1(\bar{p})\ge 0$.

Proof

Adapting the same pattern of proof as in Lemma 1, for every price system $p=(p^0,p^1)$, it is easy to check that $W(p,p)=0$, thus $\langle p^0, s^0(p)\rangle =0$ and $\langle p^1, s^1(p)\rangle =0$. Then, if $\bar{p}$ is a maxinf-point of W, $W(\bar{p},\cdot )\ge 0$. It follows that for vectors $q=(e^j,\bar{p}^1)$ defined for every unit vector $e^j$, $0\le \langle q, s(\bar{p}) \rangle =\langle e^j,s^0(\bar{p})\rangle +\langle \bar{p},s^1(\bar{p})\rangle$ which implies $s^0(\bar{p})\ge 0$. Analogously, taking $q=(\bar{p}^0,e^j)$ it follows that $s^1(\bar{p})\ge 0$. $\square$

Theorem 4

(convergence of $\epsilon$-maxinf points and equilibrium). Suppose that the function $p\mapsto s(p)$ is usc on $\varDelta ^2$. Consider the non-negative sequences $\big \lbrace r^\nu : \nu \in {IN}\big \rbrace$ and $\big \lbrace \epsilon ^\nu : \nu \in {IN}\big \rbrace$ such that , .¹ Let $\big \lbrace W^{\nu }: \nu \in {IN}\big \rbrace$ be a family of Augmented Walrasian functions associated which each augmenting parameter $r^\nu$. Let $p^{\nu } \in \epsilon ^{\nu } \hbox {-}\mathrm{argmaxinf}\, W^{\nu }$ and $\bar{p}$ be a cluster point of $\big \lbrace p^{\nu }:\nu \in {IN}\big \rbrace$. Then $\bar{p} \in \epsilon \hbox {-}\mathrm{argmaxinf}\, W$. In particular, when $\epsilon =0$, $\bar{p}$ is an equilibrium point.

Proof

The tight lop-convergence of the augmented Walrasian $\big \lbrace W^\nu : \nu \in {IN}\big \rbrace$ follows the same arguments as those in the proof of Theorem 2 and the conclusion follows from Theorem 1. $\square$

4.2 Two-Stage Deterministic Model: A Solution Strategy

A crucial observation on the structure of the two-stage deterministic problem help us design an efficient solution procedure for this type problem. After dropping reference to agent-i, for a fixed choice of activities y, the two-stage deterministic model is essentially just an extension of a one-stage problem. Let $y = \bar{y}\in Y$, then the problem reads:

$$\begin{aligned} \max _{(x^0,x^1)}\;&u^0(x^0) + u^1(x^1) \\ \hbox {so that}&\;\langle p^0, x^0 \rangle \le \langle p^0, e^0 - T^0 \bar{y}\rangle , \\&\langle p^1, x^1 \rangle \le \langle p^1, e^1 + T^1 \bar{y}\rangle , \\&\quad x^0 \in X^0, \quad x^1\in X^1. \end{aligned}$$

Considering a fixed $\bar{y}$, the agent’s problem become separable: notice that in each budget constraint, the terms $T^0\bar{y}$ and $T^1\bar{y}$ are constant terms, and therefore, one can think of having modified endowments $\tilde{e}^0=e^0-T^0\bar{y}$, and $\tilde{e}^1=e^1+T^1\bar{y}$. Thus, as the objective function is separable, and the constraints are decoupled, this problem can be solved by maximizing separately in the $x^0$ and $x^1$ variables:

$$\begin{aligned} \hbox {max}_{x^0\in X^0}\;&u^0(x^0)\; \hbox {so that}\; \langle p^0, x^0 \rangle \le \langle p^0, e^0 - T^0 \bar{y}\rangle , \\ \hbox {max}_{x^1\in X^1}\;&u^1(x^1)\, \hbox { such that }\; \langle p^1, x^1 \rangle \le \langle p^1, e^1 + T^1 \bar{y}\rangle . \end{aligned}$$

If these problems are of the Cobb–Douglas or CES-type, one can find (closed-form) explicit solutions to these problems at negligible computational cost, detailed in Sects. 4.2.1 and 4.2.2

The agent’s problem can now be seen as finding the best $y\in Y$ that will maximize the overall reward function r, defined as

$$\begin{aligned} r(y) =&\sup _{x^0\in X^0} \big \lbrace u^0(x^0) {\,\big \vert \,}\langle p^0, x^0 \rangle \le \langle p^0, e^0 - T^0 y\rangle \big \rbrace \\&+ \sup _{x^1\in X^1} \big \lbrace u^1(x^1) {\,\big \vert \,}\langle p^1, x^1 \rangle \le \langle p^1, e^1 + T^1 y\rangle \big \rbrace . \end{aligned}$$

The agent’s problem can be translated to:

$$\begin{aligned} \,\;\hbox {find}\;\,\; y^* \in \mathop {\mathrm{argmax}}\nolimits _{y\in Y} r(y). \end{aligned}$$

We refer to this reduction as the transfer-first approach and the algorithmic procedure to solve it (nonlinear convex optimization problem) very much depends on the properties of r. In the Cobb–Douglas or CES case, the function r is twice differentiable and one can find explicit expressions for the gradient and the Hessian of r. When , the problem boils down to maximizing a convex function on the non-negative orthant. Assuming further that r is differentiable, the optimality conditions read:

$$\begin{aligned} \,\;\hbox {for}\;\,\; k = 1,\dots , m, \quad y_k^*\ge 0, \quad \frac{\partial }{\partial y_k}r(y^*) \le 0, \quad y_k^* \frac{\partial }{\partial y_k}r(y^*) = 0. \end{aligned}$$

A number of specialized algorithmic procedures have been designed for precisely this problem-type.

4.2.1 The Cobb–Douglas Case

The utility function of agent-i takes the form

$$\begin{aligned} u_i(x) = \mathop {\prod }\nolimits _{j=1}^n x_j^{\beta _{i,j}} \quad \,\;\hbox {with}\;\, \mathop {\sum }\nolimits _{j=1}\beta _{i,j} = 1, \;\; \beta _{i,j} \ge 0. \end{aligned}$$

For any price $p\in \varDelta$ and assuming that the survival set , agent-i solution is

$$\begin{aligned} \,\;\hbox {for}\;\,\; j = 1,\dots , n, \quad \bar{x}_{i,j}(p) = \frac{\beta _{i,j}}{p_j} \mathop {\sum }\nolimits _{l=1}^n p_l e_{i,l}; \end{aligned}$$

the endowment of agent-i: $e_i = (e_{i,1}, \dots , e_{i,n})$ and the utility attached to this solution:

$$\begin{aligned} u_i(\bar{x}_i) = \alpha _i(p) \Big (\mathop {\sum }\nolimits _{l=1}^n p_l e_{i,l}\Big ) \quad \,\;\hbox {where}\;\,\; \alpha _i(p) = \mathop {\prod }\nolimits _{j=1}^N \Big (\frac{\beta _{i,j}}{p_j}\Big )^{\beta _{i,j}}. \end{aligned}$$

Given the dynamic model, once the activity levels $y \ge 0$ are fixed, the problem becomes separable (per-stage) and the solution takes the same form provided that y is chosen so that $e_i^0 - T_i^0 y$ remains non-negative, otherwise agent-i would enter the exchange market with a negative quantity of certain goods. It’s implicitly assumed that the technology matrices $T_i^0, T_i^1$ are non-negative: negative entries in $T_i^0$ would imply goods-production at time 0 and negative entries in $T_i^1$ would imply negative outputs would be generated by certain technologies at time 1. Hence, assuming that $T_i^0 y \le e_i^0$, the solutions (consumption vectors) that result from the choice of y and $p = (p^0,p^1)\in \varDelta \times \varDelta$ would be

$$\begin{aligned} \,\;\hbox {for}\;\,\; j = 1,\dots , n, \quad \bar{x}_{i,j}^0(p^0) = \frac{\beta _{i,j}^0}{p^0_j} \mathop {\sum }\nolimits _{l=1}^n p_l^0 (e_{i,l}^0-\langle T_{i,l}^0, y \rangle ); \end{aligned}$$

where $T_{i,l}^0$ is the lth row of $T_i^0$,

$$\begin{aligned} \,\;\hbox {for}\;\,\; j = 1,\dots , n, \quad \bar{x}_{i,j}^1(p^1) = \frac{\beta _{i,j}^1}{p^1_j} \mathop {\sum }\nolimits _{l=1}^n p_l^1 (e_{i,l}^1+\langle T_{i,l}^1, y \rangle ); \end{aligned}$$

and consequently,

$$\begin{aligned} r_i(y)&= u_i^0(\bar{x}^0) + u_i^1(\bar{x}^1) \\&= \alpha _i^0(p^0) \Big (\mathop {\sum }\nolimits _{l=1}^n p_l^0 (e_{i,l}^0 - \langle T_{i,l}^0, y \rangle )\Big ) + \alpha _i^1(p^1) \Big (\mathop {\sum }\nolimits _{l=1}^n p_l^1 (e_{i,l}^1 + \langle T_{i,l}^1, y \rangle )\Big ) \end{aligned}$$

As detailed in Sect. 4.1, the optimization problem for agent-i is reduced to

This is a linear programming problem whose feasible region is bounded and non-empty; $y = 0$ is always a feasible solution.

4.2.2 The Constant Elastiticity of Substitution (CES) Case

If the utility functions for agent i take the following form

$$\begin{aligned} u_i^0(x^0)= & {} \left( \sum _{j=1}^n ( a^0_{i,j} )^{\frac{1}{b_i^0}}(x^0_j)^{\frac{b_i^0-1}{b_i^0}} \right) ^{\frac{b_i^0}{b_i^0-1}}.\\ u_i^1(x^1)= & {} \left( \sum _{j=1}^n ( a^1_{i,j} )^{\frac{1}{b_i^1}}(x^1_j)^{\frac{b_i^1-1}{b_i^1}} \right) ^{\frac{b_i^1}{b_i^1-1}}. \end{aligned}$$

Then, the KKT optimality conditions Rockafellar and Wets (1998), are satisfied if, and only if, the budget constraint is active. On the other hand, each agent must satisfy the constraint for feasibility $T_i^0y\le e_i^0$. Then, for a given a feasible $y\in Y_i$, we can find an explicit solution, given by

$$\begin{aligned} \,\;\hbox {for}\;\,\; j = 1,\dots , n, \quad \bar{x}_{i,j}^0(p) = \frac{ a^0_{i,j} }{ ( p^0_j )^{ b_i^0 } \sum _{ k=1 }^n ( p^0_k )^{ 1-b_i^0 } a_{i,k}^0 } \sum _{l=1}^n p^0_l ( e_{i,l}^0- \langle T_{i,l}^0 , y \rangle ); \end{aligned}$$

where $T_{i,l}^0$ is the lth row of $T_i^0$,

$$\begin{aligned} \,\;\hbox {for}\;\,\; j = 1,\dots , n, \quad \bar{x}_{i,j}^1(p^1) = \frac{ a^1_{i,j} }{ ( p^1_j )^{ b_i^1 } \sum _{ k=1 }^n ( p^1_k )^{ 1-b_i^1 } a_{i,k}^1 } \sum _{l=1}^n p^1_k ( e_{i,l}^1 + \langle T_{i,l}^1 , y\rangle ); \end{aligned}$$

Defining for agent-i

$$\begin{aligned} \,\;\hbox {for}\;\,\; t = 1,2, \quad \theta _i^t(p) = \left( \sum _{j=1}^n ( a^t_{i,j} )^{ \frac{ 1 }{ b_i^t } } \left( \frac{ a_{i,j}^t }{ ( p^t_j )^{ b_i^t }} \frac{ 1 }{ \sum _{k=1}^n ( p^t_k )^{ 1-b_i^t }a_{i,k}^t } \right) ^{ \frac{ b_i^t-1 }{ b_i^t } } \right) ^{ \frac{ b_i^t }{ b_i^t-1 } }. \end{aligned}$$

consequently

$$\begin{aligned} r_i(y)&= u_i^0(\bar{x}^0) + u_i^1(\bar{x}^1) \\&= \theta _i^0(p^0) \left( \sum _{l=1}^n p_l^0 (e_{i,l}^0 - \langle T_{i,l}^0, y \rangle )\right) + \theta _i^1(p^1) \left( \sum _{l=1}^n p_l^1 (e_{i,l}^1 + \langle T_{i,l}^1, y \rangle )\right) \end{aligned}$$

This is again a linear function of y. Thus, if , the problem for each agent is given by

5 Stochastic Equilibrium

In Sect. 4 we introduced an intertemporal deterministic exchange economy. In this section, we enrich this model by incorporating uncertainty. This stochastic model reflects a more realistic approach to the economic activity, where agents face an intertemporal decision problem, and where the outcome in the second stage has multiple possibilities. This model is intrinsically dynamic, and the price adjustment procedure is uniquely driven by the market interaction between agents. Considering this modification, we analyze the agent’s problem, as well as proposing an equilibrium formulation and an augmenting Walrasian algorithm to solve this problem.

5.1 The Agent’s Problem

In an uncertain (stochastic) environment the agent’s decision strategy is modeled as a stochastic two-stage optimization problem, that can be formulated as follows:

where, the utility functions are usc, concave and the survival sets are convex and unbounded. Additionally, the uncertainty on the second stage is modeled by a finite number of possible states (scenarios), denoted by the set $\varXi$, and agent-i is calculating the expectation with respect to agent-ibeliefs, i.e., to each possible state $\xi \in \varXi$, agent-i assigns a probability $\pi _{i,\xi } \ge 0$ such that $\sum _{\xi \in \varXi } \pi _{i,\xi } = 1$. It’s possible, although unlikely, that all agents have the same information about the future in which case these probabilities wouldn’t depend on i. As before, the agents set up their trades in full knowledge of the suggested price system, eventually an equilibrium price system,

$$\begin{aligned} p = (p^0, (p_\xi ^1)_{\xi \in \varXi } ); \end{aligned}$$

in particular, $p_\xi ^1$ is known for every contingency $\xi \in \varXi$. Note that the goods required $T_i^0 y$ to carry out activities at level y are still well determined, the output at time 1 is now stochastic, namely $T_{i,\xi }^1y$. This reflects a more realistic view of the output process. Even in the simple case of savings via buying certificates of deposit, bonds or stocks, their value at time 1 can’t be known with certainty. This is even more so, if the activities are decisions involving manufacturing, the marketing or distribution of goods (perishable or not) and so on.

The agents’ problems are thus (two-stage) stochastic programs with recourse Birge and Louveaux (2011) with stochastic entries in the right-hand side $\langle p_{\xi }^1, e_{i,\xi }^1\rangle$, the so-called technology matrix $T_{i,\xi }^\top$ and the recourse matrix $p_{\xi }^1$; the recourse decisions are $x_{i,\xi }^1$. Under the ‘usual’ conditions that guarantee the existence of an equilibrium price system, recalled in Jofré and Wets (2002), Magill and Quinzii (2002), these stochastic programs are necessarily feasible; note however that straightforward feasibility of these stochastic programs doesn’t really require such stringent conditions, for example, one could rely on an adaptation of the ample survivability assumption introduced in Jofré et al. (2017). From the stochastic programming viewpoint, these conditions can be viewed as sufficient conditions to guarantee the relatively complete recourse property. For our problem, this can be stated as follows: for every agent, and for every possible state of nature, there exists a consumption plan and an activity-level decision that allows survivability of the agent. Mathematically, for every agent (dropping the dependence on i), for all $\xi \in \varXi$, there exists such that

$$\begin{aligned} e^0_l-\tilde{x}^0_l-(T^0\tilde{y})_l\ge & {} 0,\quad l=1,\ldots ,L\\ e^1_{l,\xi }-\tilde{x}^1_{l,\xi }+(T^1_\xi \tilde{y})_l\ge & {} 0,\quad l=1,\ldots ,L,\,\forall \xi \in \varXi \end{aligned}$$

From the economic perspective, this assumption is weaker than the usual survivability conditions, and can be interpreted as every agent being able to survive or participate in the economy, independently of the market prices.

5.2 Solving the Agent’s (Stochastic) Problem

There are many alternatives methods to solve stochastic programs with recourse, but in this setup the use of the Progressive Hedging algorithm Rockafellar and Wets (1991), Wets (1989) seems to have many advantages, in particular because solutions of the individual scenario subproblems are so readily available, cf. Sect. 4.2 with the transfer-first approach.

The approach is based on relaxing, at the outset, the non-anticipativity constraint, namely that the first stage variables aren’t allowed to depend on $\xi$, and then, progressively enforcing this requirement. For now let’s just limit ourselves to a description of the steps of the algorithm as it applies to the stochastic version of the (two-stage) agent’s problem in the Cobb–Douglas case, generated by the transfer-first approach described in Sect. 4.2.1.

Under the transfer-first setting, the only first stage decision variable is y, and the Progressive Hedging algorithm can be described as follows Step 0. Set $\nu =0$. Pick $\rho > 0$, $\bar{y}^0 = 0$, such that $E_i\{w_i^\nu (\varvec{\xi })\} = 0$.

Step 1. For all $\xi \in \varXi$, let

where

$$\begin{aligned} r_i^\nu (\xi ,y) =\,&\alpha _i^0(p^0) \Big (\mathop {\sum }\nolimits _{l=1}^n p_l^0 (e_{i,l}^0 - \langle T_{i,l}^0, y \rangle )\Big )\\&+\,\alpha _i^1(\xi ,p^1(\xi )) \Big (\mathop {\sum }\nolimits _{l=1}^n p_l^1(\xi ) (e_{i,l}^1(\xi ) + \langle T_{i,l}^1(\xi ), y \rangle )\Big ) \end{aligned}$$

and

$$\begin{aligned} \alpha _i^0(p^1) = \mathop {\prod }\nolimits _{j=1}^n \left( \frac{\beta _{i,j}^0}{p_j^0}\right) ^{\beta _{i,j}^0}, \qquad \alpha _i^1(\xi ,p^1(\xi )) = \mathop {\prod }\nolimits _{j=1}^n \left( \frac{\beta _{i,j}^1}{p_j^1(\xi )}\right) ^{\beta _{i,j}^1}. \end{aligned}$$

Step 2. If $\xi \mapsto y_i^\nu (\xi )$ is a constant function, stop. $y^\nu (\xi )$, for any $\xi$, of course, determines the optimal activity levels and the corresponding vector and function $[x_i^0, (x_i^1(\xi ), \xi \in \varXi )]$ determine the optimal consumption plans. Otherwise, set $\bar{y}_i^{\nu +1} = E\{y_i^{\nu +1}(\varvec{\xi })\}$,

$$\begin{aligned} w_i^{\nu +1}(\xi ) = w_i^\nu + \rho (y_i^{\nu +1}(\xi ) - \bar{y}_i^{\nu +1}), \end{aligned}$$

and return to Step 1 with $\nu = \nu +1$.

Note that the optimization problem in Step 1 is a quadratic program of a very simple nature since it’s completely separable. After carrying out some elementary calculations, it can be written in the form:

One could rely on general quadratic procedures to solve this particular problem, but a much more efficient procedure could be designed to deal with a problem of this particular type.

One final remark about this model is that it can be easily extended to the CES utility functions case, using the same transfer first approach of maximizing r function. In this situation, is easy to see that the only difference is the sustitution of the linear coefficientes $\alpha$ by the ones given by the CES parameters, $\theta$. Furthermore, one can solve the general agent problem, relaxing the dependence of $x^0$ and y on $\xi$, and apply the enforcing procedure to progressively converge to a deterministic solution.

5.3 Augmented Walrasian and the Approximating Scheme

In this section, we set the foundations of the augmentation techniques applied to the Two-stage Stochastic Equilibrium Model. A description of equilibrium points as maxinf points of the corresponding Walrasian, as well as the approximation scheme based in tight lopsided convergence of augmented Walrasian is provided. Finally, a general description of the computational implementation of the algorithm and numerical examples are analized.

As in the previous section, consider the stochastic equilibrium model, where given a price system $p=\left( p^0, (p_\xi ^1)_{\xi \in \varXi }\right)$, each agent i solves

which defines the individual demand function $x_{i}(p) = \left( x^0_{i}(p), (x_{i,\xi }^1(p))_{\xi \in \varXi }\right)$ and the individual transfer vector $y_i(p)$. Additionally, the excess supply function for this economy $s(p) = \left( s^0(p),(s_\xi ^1(p))_{\xi \in \varXi }\right)$ is defined as

$$\begin{aligned} s^0(p)= & {} \sum _{i\in \mathcal {I}} e_i^0-x_i^0(p)-T^0_iy_i(p)\\ s^1_\xi (p)= & {} \sum _{i\in \mathcal {I}} e_{i,\xi }^1-x_{i,\xi }^1(p)+T^1_{i,\xi }y_i(p), \quad \forall \,\xi \in \varXi \\ \end{aligned}$$

The Walrasian for this model is the function defined by

$$\begin{aligned} W(p,q) = \langle q^0, s^0(p)\rangle +\sum _{\xi \in \varXi } \langle q_\xi ^1, s_\xi ^1(p)\rangle \end{aligned}$$

A price system $\bar{p}=\left( \bar{p}^0, (\bar{p}_\xi ^1)_{\xi \in \varXi }\right)$ is an equilibrium price if $s(\bar{p})\ge 0$, i.e., $s^0(\bar{p})\ge 0$ and $s_\xi ^1({p})\ge 0$, for every possible state $\xi \in \varXi$. Then, a equilibrium point for the stochastic model can be described as a maxinf point of the Walrasian. Again, the existence is granted by noting that W turns out to be a Ky Fan function.

Theorem 5

(stochastic equilibrium prices and maxinf-points) Consider the Walrasian function W for the previous economy. Then, under local nonstatiation of preferences, every maxinf-point $\bar{p}=(\bar{p}^0,(\bar{p}_\xi ^1)_{\xi \in \varXi })$ of W is an equilibrium point, i.e., $s^0(\bar{p})\ge 0$ and $s_\xi ^1({p})\ge 0$, for every possible state $\xi \in \varXi$.

Proof

Considering that for every price system $p=(p^0,(p^1_\xi )_{\xi \in \varXi })$, under local nonsatiation preferences, the excess supply satisfies the Walras’ law for the first stage and for every possible state of the second stage, i.e.,$\langle p^0, s^0(p)\rangle =0$ and for every $\xi$, $\langle p^1_\xi , s^1_\xi (p)\rangle =0$. Thus, for $\bar{p}$ a maxinf point of W, $W(\bar{p},\cdot )\ge 0$. Considering $q=(e^j,(\bar{p}^1_\xi )_{\xi \in \varXi })$, $0\le \langle q, s(\bar{p})\rangle =\langle e^j,s^0(\bar{p})\rangle + \sum _{\xi \in \varXi }\langle \bar{p}^1_\xi ), s^1_\xi (\bar{p})\rangle$, which implies that $(s^0(\bar{p}))_j\ge 0$ for all j. For the second stage, given an scenario $\xi _0\in \varXi$, it suffices to take $q=(\bar{p}^0,(\bar{p}^1_1,\ldots ,\bar{p}^1_{\xi _0-1}, e^j, \bar{p}^1_{\xi _0+1},\ldots ,\bar{p}^1_{\varXi })$ and conclude by the same argument that $(s^1_{\xi _0}(\bar{p}))_j\ge 0$, for every good j and every state $\xi _0$. $\square$

For the problem of finding equilibrium points, we will follow the approximating technique described in Sect. 3, where for a given Walrasian function W for the stochastic economy, we consider the augmenting function $\sigma$, and an increasing sequence of positive scalars , for which we defined the family of augmented Walrasian bifunctions $W^\nu$ as follows

$$\begin{aligned} W^\nu (p,q) = \inf _{z\in \varDelta \times \varDelta ^{\varXi }}\big \lbrace W(p,z)+r^\nu *\sigma ^*(q-z)\big \rbrace , \end{aligned}$$

and the algorithmic procedure relies in the idea of finding approximating maxinf-points of this augmented Walrasian bifunctions for $\nu$ large enough. Finally, the following convergence result will guarantee the approximation to an equilibrium point for the initial economy.

Theorem 6

(convergence of dynamic stochastic $\epsilon$-maxinf points) Suppose that $p \mapsto s(p)$ is usc on $\varDelta$. Consider the non-negative sequences $\big \lbrace r^\nu : \nu \in {IN}\big \rbrace$ and $\big \lbrace \epsilon ^\nu : \nu \in {IN}\big \rbrace$ such that , , for $\epsilon \ge 0$. Let $\big \lbrace W^{\nu }: \nu \in {IN}\big \rbrace$ be a family of Augmented Walrasian functions associated wich each augmenting parameter $r^\nu$. Let $p^{\nu } \in \epsilon ^{\nu } \hbox {-}\mathrm{argmaxinf}\, W^{\nu }$ and $\bar{p}$ be a cluster point of $\big \lbrace p^{\nu }:\nu \in {IN}\big \rbrace$. Then $\bar{p} \in \epsilon \hbox {-}\mathrm{argmaxinf}\, W$. In particular, for $\epsilon =0$, $\bar{p}$ is an equilibrium point.

Proof

The proof follows from the application of the Theorem 1, as it was used in the convergence results of Sects.  3 and 4 (Theorems 2, 4). Finally, the tight lopsided convergence of the sequence $\big \lbrace W^\nu : \nu \in {IN}\big \rbrace$ follows from the same argument. $\square$

5.4 Numerical Implementation and Examples

Computationally, we proceed with a primal-dual iteration scheme as described in Sect. 3. Especial features for this type of economy are considered. In terms of the agent’s problem, we can adopt a strategy solving the problem directly or solving it through the maximization of the overall reward function r, coming from the transfer-first approach

On the other hand, the agent’s problem is now a stochastic program with relatively complete recourse, for which Progressive Hedging algorithm is implemented. Exploiting the structure of the agent’s problem given by the separability in terms of the different scenarios in the second stage, combined with the progressive hedging approach, we provide two strategies, one sequential and another one parallel. The efficiency of these strategies will be discussed later and will basically depend on the size of the economy considered as the total amount of goods available.

Finally, the global strategy of solution adopted can be summarized in the following scheme:

• Step 0 Set $\nu =0$. Pick an initial price $p^{(0)}$ (for example, the centroid of the simplex $\varDelta$ for each $\xi \in \varXi$), and an augmenting parameter $r^0>0$. Define an strategy for the agent’s problem, directly maximizing the utility function $u(x^0,y,(x^1_\xi )_{\xi \in \varXi })$, or indirectly maximizing the overall reward function r(y). Additionally, defined the procedure for the Progressive Hedging algorithm implementation, sequential or parallel.

• Step 1 For all $i\in \mathcal {I}$, compute $x_i^\nu (p^\nu )$ by applying Progresive Hedging algorithm to the agent’s problem with the proper choice of strategies. With this, compute $s^\nu (p^\nu )$, and solve the Phase I iteration for the primal-dual scheme:

  $$\begin{aligned} q^{\nu +1} \in \mathop {\mathrm{argmax}}\nolimits _q \big \lbrace W^\nu (p^\nu ,q){\,\big \vert \,}q\in \varDelta \times \varDelta ^{\varXi } \big \rbrace , \end{aligned}$$

  which is a linear problem.

• Step 2 Solve the Phase II, given by

  $$\begin{aligned} p^{\nu +1} \in \mathop {\mathrm{argmax}}\nolimits _p \big \lbrace W^\nu (p,q^{\nu +1}){\,\big \vert \,}p\in \varDelta \times \varDelta ^{\varXi } \big \rbrace . \end{aligned}$$

  Finally, check the optimality condition: if $\min s(p^{\nu +1})\ge - \varepsilon$, stop. Otherwise, set $r^{\nu +1}>r^\nu$ and return to Step 1 with $\nu = \nu +1$.

Finally, check the optimality condition: if $\min s(p^{\nu +1})\ge - \varepsilon$, stop. Otherwise, set $r^{\nu +1}>r^\nu$ and return to Step 1 with $\nu = \nu +1$.

5.5 Numerical Experimentation

Example 4

(main example). The main example for testing the numerical implementation of the augmented Walrasian algorithm is described for the following economy, consisting of seven goods: skilled job, unskilled job, leisure, consumption, risk free bond, and two stocks.

Details We considered an economy with 5 agents, with utility functions of CES type, and 9 posible scenarios in the second stage. On the other hand, the transformation matrices are the same for every agent at the first stage given by $T^0=\mathbf{I}$ and for the second stage are given by $T_{i,\xi }^1= \mathrm{diag}(d_{i,\xi })$ for each agent $i=1,\ldots \mathcal{I}$, with

$$\begin{aligned} d_{1,\xi }= & {} (0,0,1+3r/4,0.7,1+r,R^1_\xi ,R^2_\xi ),\\ d_{2,\xi }= & {} (0,0,1+r/2,0.8,1+r,R^1_\xi ,R^2_\xi ),\\ d_{3,\xi }= & {} (0,0,0,0.7,1+r,R^1_\xi ,R^2_\xi ),\\ d_{4,\xi }= & {} (0,0,1+r/2,0.9,1+r,R^1_\xi ,R^2_\xi ),\\ d_{5,\xi }= & {} (0,0,1+r/2,0.7,1+r,R^1_\xi ,R^2_\xi ). \end{aligned}$$

$\square$

where $r=3.25\%$ and $R^1_\xi$,$R^2_\xi$ are given and labeled by the following table

$\xi$		$R^2_{(+)}$	$R^2_{(=)}$	$R^2_{(-)}$
		1.10	1.00	0.95
$R^1_{(+)}$	1.20	1	2	3
$R^1_{(=)}$	1.00	4	5	6
$R^1_{(-)}$	0.85	7	8	9

Agents’ utility functions are CES type, with parameters can be found online,² as well as their initial endowments and survival sets. Additionally, we consider that every agent has the same beliefs over the scenarios on the second stage, given by $\pi _{i,\xi }=\frac{1}{9},\,i\in \mathcal{I},\, \xi \in \varXi$.

Fig. 4

Main example (Example 4), $\{p^\nu \}$ and $\{s(p^\nu )\}$

The algorithm is initialised with $p^{(0)}$ as the centroid of $\varDelta \times \varDelta ^\varXi$, the augmenting function is $\sigma =\frac{1}{2}|\cdot |^2$, and the augmenting sequence of parameters $r^\nu$ is given by $r^\nu =1.259^\nu$. The trajectory of the prices $\{p^\nu \}$ for every iteration and the corresponding excess supply function $\{s(p^\nu )\}$ are described in Fig. 4. The algorithm was set for direct solution for the agent’s problem and for Progressive Hedging, a sequential approach was considered. It finished after 62 iterations, with a total machine time of 28 h. $\square$

6 Conclusions

We introduced a new optimization methodology that allows the computation of equilibrium, demand, and prices for different economies. This new approach combines several elements of variational analysis, such as the notion of lopsided convergence and augmented Lagrangian technique for non-concave optimization problems.

Following Jofré and Wets (2002), we characterize equilibrium prices as maxinf points for the so-called Walrasian bifunction for an exchange economy. The novelty of our approach relies in the approximation of the Walrasian by augmented Walrasian. Then, the computation of equilibrium points follows from the convergence of the sequence of maxinf points for the approximated problems, granted by the lopsided convergence of the sequence of augmented Walrasians.

We use this methodology to solve, as a prelude, the classical Arrow–Debreu general equilibrium model and, then, two periods exchange economies with uncertainty. For both models we got convergence in every numerical example, including a large scale problem in the stochastic case. A robust performance of the algorithm is always obtained, and it can be interpreted as a direct result of the augmentation procedure. One can appreciate stability of the iterations: by about half of the total iterations required to get a high tolerance-level solution. Furthermore, different numerical scenarios were tested, varying the augmenting function $\sigma$ and the augmenting parameter r. The results observed in these variations were not considered significantly different. The most efficient variant relied on the self-dual augmenting function with exponential growth in the augmenting parameter. Finally, for the stochastic problem, we tested an implementation of the algorithm based on a parallel computation for the agent problem.

The augmented Walrasian algorithm introduced in this manuscript has a fundamental feature that helps it outperformed earlier methods: it does not rely on smoothness properties of the demand function. This fact becomes crucial when introducing stochastic environments. Instead, it relies on non-concave duality properties and lopsided approximation theory, both components that entail a robust and stable performance under given parameters. Theoretically, the efficiency of this algorithm can be measured by time efficiency, space efficiency, and complexity theory. However, these rigorous metrics are out of the scope of the present paper. Nevertheless, our efficiency claim is based on the theoretical foundation of our algorithm, as long as the usage of efficient tools for solving optimization problems that outperform fixed-point based methods. Finally, this algorithm provides a tool to solve problems from real-life applications, where other algorithms might fail Guo et al. (2016)

The usage of the augmented Walrasian approximation for the computation of equilibrium points can be extended for more sophisticated economic models, as the one presented in Jofré et al. (2017), Brown et al. (1996), where financial markets, collateral, and retention goods are considered. Additionally, considering the structure of the problems, computational strategies that consider an efficient use of a parallel algorithm should improve the overall time performance.