In the equilibrium problems we have discussed so far, each variable and each constraint was owned by a single agent. In this section we relax the assumption that each constraint has to be controlled by a single agent and introduce shared constraints. Shared constraints are constraints that appear in the problems of several agents. They are mainly used to model resources shared among agents. Note that the examples in this section are from Kim & Ferris (2017) [108].
Consider the following example:
\begin{equation} \tag {14} \begin{array}{lll} \textrm{Find} & (x_{1}^{*}, \dots , x_{N}^{*}) & \textrm{satisfying} \\ x_{i}^{*} \, \in \,&\textrm{arg min}_{x_i} & f_i(x_i, x_{-i}^{*}) \\ & \textrm{s.t.} & g_i(x_i, x^{*}_{-i}) \leq 0 \\ & & h(x_i, x^{*}_{-i}) \leq 0, \qquad \textrm{for} \; i = 1, \dots , N. \\ \end{array} \end{equation}
The constraints \(g_i\) are owned by agent \(i\), while the constraint \(h\) is shared by all agents. This example can be reformulated in two different ways, each with its own EMP annotations and resulting MCP. However, both share the model formulation below:
variables obj(i), x(i);
equations deff(i), defg(i), defh;
model sharedc / deff, defg, defh /;
Observe that the equation defh implementing the shared constraint \(h(x) \leq 0\) is not indexed: it is exists once, not once per agent. The first way to write the EMP annotations is as follows:
file empinfo / '%emp.info%' /;
put empinfo 'equilibrium' /;
loop(i,
put 'min', obj(i), x(i), deff(i), defg(i), defh; /;
);
putclose empinfo;
Here the equation defh appears in the minimization problem of each agent. As the equation defh is not indexed by agent and appears in the problem of each agent, it is easy to see that it is a shared constraint. Given these annotations, the EMP framework aggregates the FOC for each agent to create the following MCP:
\begin{equation} \tag {15} \begin{array}{ll} F(z) = ((F_i(z)^T)_{i=1}^N)^T, & z = ((z_{i}^{T})_{i=1}^{N})^T , \\ F_i(z) = \begin{bmatrix} \bigtriangledown_{x_i}f_i(x) - \bigtriangledown_{x_i}g_i(x) \lambda_i - \bigtriangledown_{x_i}h(x) \mu_i \\ g_i(x) \\ h(x) \\ \end{bmatrix}, & z_i = \begin{bmatrix} x_i \\ \lambda_i \leq 0 \\ \mu_i \leq 0 \\ \end{bmatrix}, \quad \textrm{for} \; i=1, \dots , N. \end{array} \end{equation}
Note that the equation \(h(\cdot)\) is replicated for each agent and each agent is assigned a separate multiplier \(\mu_i\).
- Attention
- By default, the solver JAMS does not allow shared constraints. The option
SharedEquneeds to be specified in the option filejams.optif shared constraints are intended, otherwise an error is reported when they are detected. This cautious default helps minimize the number of surprising results.
A full model including the JAMS option file is given below.
The second way to write the EMP annotations uses the EMP keyword VIsol to specify that a variational equilibrium be computed, i.e. a solution where the multipliers \(\mu_i\) are all equal. The VIsol keyword should appear after the EMP keyword equilibrium and before the descriptions of agent models.
put / 'VIsol defh';
The multipliers to make equal (or, equivalently, the constraints not to replicate) are indicated by the equation name(s) following the keyword VIsol. These constraints appear once in the resulting MCP, not once per agent. The EMP tool creates the following MCP:
\begin{equation} \tag {16} \begin{array}{ll} F(z) = ((F_i(z)^T)_{i=1}^N, F_h(z)^T)^T, & z = ((z_{i}^{T})_{i=1}^{N}, z_h^T)^T , \\ F_i(z) = \begin{bmatrix} \bigtriangledown_{x_i}f_i(x) - \bigtriangledown_{x_i}g_i(x) \lambda_i - \bigtriangledown_{x_i}h(x) \mu \\ g_i(x) \\ \end{bmatrix}, & z_i = \begin{bmatrix} x_i \\ \lambda_i \leq 0 \\ \end{bmatrix}, \quad \textrm{for} \; i=1, \dots , N, \\ F_h(z) = \begin{bmatrix} h(x) \\ \end{bmatrix}, & z_h = \begin{bmatrix} \mu\leq 0 \\ \end{bmatrix}. \end{array} \end{equation}
If there are no constraints \(g_i(x)\), then - assuming a constraint qualification - the equilibrium problem with the shared constraint corresponds exactly to the variational inequality \(VI(F,X)\), where the set \(X=\{x \, | \, h(x) \leq 0\}\) and \(F(x) = ((\bigtriangledown_{x_i}f_i(x)^T)_{i=1}^N)^T \). This corresponds in turn to the solution of the first MCP (with the replicated shared constraints) in case that solution has the property that the multipliers \(\mu_i\) are all equal. This is what gives the latter solution its name variational equilibrium. If the equilibrium problem with the shared constraint has a unique solution, both MCP reformulations will have the same solution. Otherwise, the two MCPs that correspond to the two different EMP annotations may have different solutions.
An example for shared constraints is the pollution of a river basin in Haurie & Krawczyk (1997) [95] and Krawczyk & Uryasev (2000) [110], where the total amount of pollutants that may be dumped in a river is restricted. This implies that the environmental constraints of some pollutant-producing agents are shared. This example can be formulated as follows, where \(i\) is the agent index and \(m\) denotes the number of shared constraints.
\begin{equation} \tag {17} \begin{array}{lll} \textrm{Find} & (x_{1}^{*}, x_{2}^{*}, x_{3}^{*}) & \textrm{satisfying} \\ x_{i}^{*} \, \in \,&\textrm{arg min}_{x_i} & (c_{1i} + c_{2i} x_i) \, x_i - \Big ( d_1 - d_2 \Big ( \sum_{j=1, \, j \neq i}^{3} x^{*}_{j} + x_i \Big ) \Big ) \, x_i \\ & \textrm{s.t.} & \sum_{j=1, \, j \neq i}^{3} x^{*}_{j} (u_{jm} e_j x_j^*) + u_{im} e_i x_i \leq K_m, \\ & & \textrm{for} \; i = 1, 2, 3, \; m =1,2, \\ &\textrm{where} & (c,d,e,u,K) \; \textrm{is the problem data}.\\ \end{array} \end{equation}
Here three agents produce some commodities and aim to maximize their profit. The term \((c_{1i} + c_{2i} x_i) \, x_i\) denotes the total cost for each agent \(i\) and the term \( ( d_1 - d_2 ( \sum_{j=1, \, j \neq i}^{3} x^{*}_{j} + x_i )) \, x_i\) represents the revenue for each agent. The amount of pollutants each agent dumps in the river is limited by the two shared constraints. This problem can be implemented in GAMS with EMP as follows:
Sets i / 1*3 /
m / 1*2 / ;
alias(i,j) ;
Variable obj(i) ;
Positive Variable x(i) ;
Parameters K(m) / 1 100, 2 100 /
d1 / 3 /
d2 / 0.01 /
e(i) / 1 0.5, 2 0.25, 3 0.75 / ;
Table c(m,i)
1 2 3
1 0.1 0.12 0.15
2 0.01 0.05 0.01 ;
Table u(i,m)
1 2
1 6.5 4.583
2 5.0 6.250
3 5.5 3.750 ;
Equations objdef(i)
cons(m) ;
objdef(i).. obj(i) =e= (c('1',i) + c('2',i)*x(i))*x(i) - (d1 - d2*sum(j, x(j)))*x(i);
cons(m).. sum(i, u(i,m)*e(i)*x(i)) =l= K(m);
Model m_shared / objdef, cons /;
File empinfo / '%emp.info%' /;
put empinfo 'equilibrium' /;
put 'VIsol cons' /;
loop(i,
put 'min', obj(i), x(i), objdef(i), 'cons' /;
);
putclose empinfo;
$echo SharedEqu > jams.opt
m_shared.optfile = 1;
solve m_shared using emp;
display x.l, cons.m;
Note that the shared environmental constraints are expressed with the equation cons. In the EMP annotations, we have chosen the formulation with the EMP keyword VIsol. It leads to the solution \(x^*=(21.145, 16.028, 2.726)\). Alternatively, we could delete the line with the EMP keyword VIsol and thus prompt the framework to compute the MCP in (15), resulting in the solution \(x^*=(0, 6.473, 22.281)\).