Table of Contents
While optimization problems have one decision maker that controls all decison variables, equilibrium problems are a collection of optimization problems and variational inequalities, each controlled by a different agent. We typically assume that each variable and each equation is controlled by or belongs to exactly one agent. Variables that are controlled by one agent but appear in the equations of a second agent are regarded as fixed or exogenous variables by that second agent: when taking first-order conditions, the second agent won't take derivatives wrt these exogenous variables. Later we will relax this assumption and introduce equilibrium problems with shared constraints and shared variables. Note that in this section we will discuss equilibrium problems of the Nash type, i.e. where all agents are on the same level, each assuming the decisions or strategies of the other agents are known and fixed. Equilibrium problems of the Stackelberg type, where there are leaders and followers, are covered in section Bilevel Programs.
We start with the mathematical formulation of an equilibrium problem, next present two examples, and conclude with a description of the EMP annotations for equilibrium problems.
Equilibrium Problems: Mathematical Formulation
Consider the following equilibrium problem with \(N\) agents solving minimization problems and one agent solving a variational inequality:
\begin{equation} \begin{array}{ll} \textrm{Find} & (x_{1}^{*}, \dots, x_{N}^{*}, p^{*}) \; \textrm{satisfying} \\ x_{i}^{*} \, \in \,&\textrm{arg min}_{x_i} \, f_i(x_i,x^{*}_{-i}) \\ & \textrm{s.t.} \quad \quad \quad g_i(x_i,x^{*}_{-i}) \leq 0, \; \textrm{for} \; i=1, \dots, N, \\ p^* \, \in &\textrm{SOL} \, (H(p,x^*), K(x^*)), \\ &\textrm{where} \; K(x^*) = \{p \, | \, w(p,x^*) \leq 0 \}. \tag {10} \\ \end{array} \end{equation}
Note that \(f_i(x_i,x_{-i})\) denotes the objective function of the problem of agent \(i\), \(g_i(x_i,x_{-i})\) are the constraints relating to this optimization problem and \(x_{-i}=(x_1, \dots , x_{i-1}, x_{i+1}, \dots , x_N)\) denotes the decisions of the other agents. Further, \(\textrm{SOL} \, (H,K)\) represents the solution set of the variational inequality \(VI(H,K)\).
This problem can be implemented with EMP as follows:
Set i ;
Variables obj(i), x(i), p;
Equations deff(i), defg(i), defH, defw;
*Definitions of equations are omitted
Model equil / deff, defg, defH, defw /;
File myinfo /'%emp.info%'/;
put myinfo 'equilibrium';
loop(i,
put / 'min', obj(i), x(i), deff(i), defg(i);
);
put 'vi defH p defw' /;
putclose myinfo;
solve equil using EMP;
Note that the GAMS variable obj(i) holds the value of \(f_i(x)\), x(i) represents the variable \(x_i\) and p denotes the variable \(p\), of course. The equations deff(i) and defg(i) are closed-form definitions of the objective function \(f_i(x)\) and the constraint \(g_i(x)\) respectively. The equation defH defines the variational inequality function \(H\) and the equation defw defines the set \(K\). The EMP annotations found in the file emp.info specify the equilibrium structure of the model:
equilibrium
min obj('1') x('1') deff('1') defg('1')
...
min obj('N') x('N') deff('N') defg('N')
vi defH p defw
The EMP keyword equilibrium indicates that the annotations are for an equilibrium problem. Each of the EMP keywords min begins a new optimization problem (owned by a new agent), where each problem has its own objective variable, decision variables, and equations / constraints. For example, the first agent minimizes obj('1'), controls or owns x('1'), and is subject to the constraints deff('1') and defg('1'). If other variables like x('2') and x('3') appear in deff('1') and defg('1'), they will be treated as exogenous by the first agent. This specification is consistent with the formulation above in (9). Each agent's optimization problem can be easily (re)constructed given the EMP annotations. Following the optimization problems of the \(N\) agents we have the VI specification for agent \(p\). The EMP keyword vi is followed by the equation-variable pair defH p defining the VI function \(H\) and the equation defw that defines the feasible set \(K\).
Note that the short form of the solve statement is used for equilibrium problems. Objective variables (if and when they exist) belong to individual agents, not to the model as a whole.
Equilibrium Problems with EMP: A Simple Example
Consider the following example from Kim & Ferris (2017) [108]. In this economic equilibrium problem there are three agents: one profit-maximizing producer, one utility-maximizing consumer and a market that determines the price of three commodities based on production and demand. The problem data include a technology matrix \(A\), where the entry \(a_{ij} > 0\) denotes the output of the commodity \(i\) for each unit of activity of producer \(j\) and \(a_{ij} < 0\) denotes the respective input. Further, an initial endowment \(b\) and the demand function \(d(p)\) is given, where \(p\) is the price. The consumer maximizes her utility within her budget, which depends on the price \(p\) and the initial endowment \(b\). Let \(y\) represent the activity of the producer, \(x\) represent the demand of the consumer and \(p\) represent the prices of commodities. Then \((y^{*},x^{*}, p^{*})\) is a general equilibrium if it satisfies the following:
\begin{equation} \begin{array}{rll} -A^T p^* & \geq 0 & \textrm{No positive profit for each activity} \\ b+Ay^*-d(p^*) & \geq 0 & \textrm{No excess demand} \\ p^* \geq 0, \, y^* & \geq 0 & \textrm{Nonnegativity} \\ -A^T p^* & \perp y^* & \textrm{No activity for earning negative profit and positive activity implies balanced profit}\\ b+Ay^* - d(p^*) & \perp p^{*} & \textrm{Zero price for excess supply and market clearance for positive price} \\ \end{array} \end{equation}
The code for the respective model is given below. Note that instead of using the consumer demand function \(d(p)\) in its explicit form, we introduce a utility-maximizing consumer with demand \(x\).
set i 'commodities' / 1*3 /;
variable u 'consumer utility';
positive variables
y 'activity of the producer'
x(i) 'Marshallian demand of the consumer'
p(i) 'prices'
;
parameters
A(i) 'technology matrix' / 1 1, 2 -1, 3 -1 /
s(i) 'budget share' / 1 0.9, 2 0.1, 3 0 /
b(i) 'endowment' / 1 0, 2 5, 3 3 /
;
equations
profit 'profit of activity'
mkt(i) 'constraint on excess demand'
udef 'Cobb-Douglas utility function'
budget 'budget constraint'
;
profit.. -sum(i, A(i)*p(i)) =g= 0;
mkt(i).. b(i) + A(i)*y - x(i) =g= 0;
udef.. u =e= sum(i, s(i)*log(x(i)));
budget.. sum(i, p(i)*x(i)) =l= sum(i, p(i)*b(i));
model m / mkt, profit, udef, budget /;
file empinfo /'%emp.info%'/; putclose empinfo
'equilibrium' /
' max', u, 'x', udef, budget /
' vi profit y' /
' vi mkt p' /
;
* the second commodity is used as a numeraire
p.fx('2') = 1;
x.l(i) = 1;
solve m using EMP;
Observe that in the EMP annotations the problems of the three agents are specified after the EMP keyword equilibrium: the consumer solves a maximization problem (where the utility u is maximized) and the activities of the producer and the price-setting market are expressed as VI. As there are three commodities, the first VI actually generates three VI functions, one for each commodity. Thus there are three agents and four VI functions in the equilibrium problem. This is reflected in the EMP Summary in the listing file:
--- EMP Summary
...
VI Functions = 4
Equilibrium Agent = 3
...
In the GAMS EMP Library there are several models that have a similar form, e.g. Scarf's activity analysis model [SCARFEMP-DEM] and the simple equilibrium problem [SIMPEQUIL]. The latter demonstrates that there are equilibrium problems where the optimization problems of the individual agents are solvable, but the overall equilibrium problem does not have a solution.
Equilibrium Problems with EMP: Example with Dual Variables
In many applications equilibrium problems come with a twist: the dual variable associated with a constraint in the problem of one agent appears exogenously in the problem of another agent. The following simple example with two agents is from model [DUALVAR] in the GAMS EMP Library.
\begin{equation} \tag {11} \begin{array}{ll} \textrm{Problem of the first agent:} \textrm{Min}_{(v,w)} & z = v+w \\ \textrm{s.t.} & \sqrt{v+1} + 2w \geq 2 \qquad (\perp \; u \geq 0) \\ & v, w \geq 0 \\ \\ \textrm{Problem of the second agent:} VI: & F(y) := y-4u + 1 \quad \; (\perp \, y \; \textrm{free}) \\ \end{array} \end{equation}
N.B.: the variable \(u\) that appears in the problem of the second agent is the dual multiplier (aka shadow price) of the first agent's constraint. This equilibrium problem can be modeled in GAMS with EMP as follows:
positive variables
v 'belongs to min agent'
w 'belongs to min agent'
u 'dual of min constraint'
;
free variables
y 'belongs to VI agent'
z 'objective var'
;
equations
defz 'objective def'
g 'constraint for min agent'
Fy 'VI function'
;
defz.. v + w =e= z;
g.. sqrt(v+1) + 2*w =g= 2;
Fy.. y - 4*u + 1 =n= 0;
Model opt 'min agent and VI agent' / defz, g, Fy /;
File empinfo / '%emp.info%' /; putclose empinfo
'equilibrium' /
' min z v w defz g' /
' vi Fy y' /
' dualvar u g' /
;
defz.m = -1;
g.m = 0.5; Fy.m = 1;
v.l = 0; w.l = 0.5;
y.l = 1; u.l = 0.5;
solve opt using emp;
The EMP info file contains the EMP keyword equilibrium followed by the specifications for the two agents: a minimization problem for the first agent and a VI for the second agent. The special relationship between the variable u and the equation g is declared via the EMP keyword dualvar followed by the respective variable-equation pair. Recall our usual assumption that each variable and each equation is owned or controlled by exactly one agent. Since variable u is tied to equation g and g is owned by the first agent, variable u is owned by the first agent also.
Besides the number of equilibrium agents and the number of VI functions, the EMP Summary lists the number of dual variable maps:
--- EMP Summary
...
Dual Variable Maps = 1
...
VI Functions = 1
Equilibrium Agent = 2
...
- Note
- Although the example above contained an optimizing agent and a VI agent, dual variables most often occur in equilibrium problems with several optimizing agents.
Other examples with dual variables in the GAMS EMP Library include a formulation of the well-known transportation model as an equilibrium problem [TRANSEQL], Scarf's activity analysis model [SCARFEMP-PRIMAL] and the general equilibrium model [TWO3EMP].
EMP Syntax for Equilibrium Problems
The EMP framework provides the following general syntax to specify equilibrium problems:
Equilibrium
{VIsol {equ}}
{Implicit {var equ}}
{MAX|MIN obj {var|*} {[-] equ}}
{VI {var|*} {[-] equ var} {[-] equ}}
{DualVar {var [-] equ}}
The EMP keyword Equilibrium indicates that the specifications that follow define the structure of an equilibrium problem. The MAX, MIN, and VI keywords specify agents in the problem, while the rest of the keywords are optional modifiers used to adjust the structure of the agent models or the meaning of the equations they contain.
- Note
- An equilibrium problem must contain at least one agent, i.e must contain one of the keywords
MAX,MIN, orVI.
The EMP keyword VIsol identifies a shared constraint(s) and specifies the MCP reformulation to use for it: see section Equilibrium Problems with Shared Constraints below for details. The keyword Implicit identifies a shared variable and its defining constraint: see section Equilibrium Problems with Shared Variables below for details. The keywords MAX and MIN each begin the specification of an optimization agent and are followed by the objective variable obj and the other variables and equations owned by the agent, as described in the formulation and example above. The keyword VI begins the specification of a VI agent: see the section on VI above for details. Finally, the EMP keyword DualVar specifies that the variable var is the Lagrange multiplier for the equation equ. For examples, see sections Equilibrium Problems with EMP: Example with Dual Variables and Embedded Complementarity Systems.
The symbol '*' specifies that the default or automatic assignment of variables to this agent be used, i.e. the set of variables used in the equations owned by this agent but not explicitly or otherwise assigned to another agent. Note that if a variable occurs in equations owned by multiple agents and is not explicitly assigned to any agent, the default assignment is not well defined and using it will be flagged as an error. To avoid confusion and promote clarity, we recommend that modelers use explicit variable lists and avoid the '*' symbol.
The "-" sign in the syntax above is used to flip (i.e. to reorient or negate) the marked equation, e.g. so that x**1.5 =L= y becomes y =G= x**1.5. Flipped equations in EMP behave in the same way as flipped equations in MCP.
- Note
- When the EMP keyword
equilibriumappears in the EMP annotations, the solve statement takes the short form also used for complementarity problems in GAMS.