First, we introduce the notion of implicit variables. In mathematical terms, a variable \(y\) is called an implicit variable if for each value of \(x\) there is at most one value of \(y\) satisfying \((y,x) \in X\). For such implicit variables there exists one and only one function \(g(\cdot)\) such that \((g(x),x) \in X\), where \(g\) is defined over the set \(\{x \, | \, \exists \, y \; \textrm{such that} \; (y,x) \in X \} \). The set \(X\) is called the defining constraint of the variable \(y\): the value of \(y\) is implicitly defined by the value of \(x\) via the defining constraint. In the current implementation, the defining constraint may only be represented as a system of equations and implicit variables must be free variables in GAMS.

Shared variables in equilibrium problems are implicit variables that have the same defining constraint for all agents that share the variable. Hence, the defining constraint becomes a shared constraint. Consider the following equilibrium problem with the shared decision variable \(y\) and its defining constraint \(X = \{(y,x) \, | \, H(y,x) = 0 \}\):

\begin{equation} \tag {18} \begin{array}{lll} \textrm{Find} & (y^*, x_{1}^{*}, \dots, x_{N}^{*}) & \textrm{satisfying} \\ (y^*,x_{i}^{*}) \, \in \,&\textrm{arg min}_{y, x_i} & f_i(y, x_i, x^{*}_{-i}) \\ & \textrm{s.t.} & H(y, x_i, x^{*}_{-i}) = 0, \quad \textrm{for} \; i = 1, \dots , N, \\ &\textrm{where} & H: \mathbb{R}^{m+n} \rightarrow \mathbb{R}^m, \; y \in \mathbb{R}^m\\ \end{array} \end{equation}

Note that there are \(N\) agents, \(m\) is the dimension of the variable \(y\) and \(n = \sum_i n_i\), where \(n_i\) is the dimension of \(x_i\). Assuming we have 4 agents, this example can be implemented in GAMS EMP as follows:

Set       i / 1*4/;
Variables obj(i), x(i), y;

Equations deff(i), defH;

Model     sharedv / deff, defH /;

File empinfo / '%emp.info%' /;
put empinfo 'equilibrium' /;
put 'implicit y defH' /;
loop (i,
   put 'min', obj(i), x(i), y, deff(i) /;
);
putclose empinfo;

solve sharedv using EMP;

In the EMP annotations, the EMP keyword implicit is used to declare the implicit variable y and its defining constraint defH. Note that the keyword implicit must be followed by variable-constraint pairs. If multiple pairs are specified with a single keyword implicit, they will be augmented to form a single vector of implicit variables and its defining constraint.

Note: Implicit variables are declared before the agent problems are defined.

Observe that the shared variable y appears in the problem specification for each agent. However, the defining equation defH does not appear in each problem specification, since it is assumed to be part of the implicit variable.

Reformulation Strategies for Equilibrium Problems with Shared Variables

Like other equilibrium problems, equilibrium problems with shared variables are reformulated as MCPs by the EMP tool. Users can choose between three different reformulation strategies if shared decision variables are involved. In the first strategy, the shared variables are replicated for each agent and the respective KKT conditions are computed, resulting in the following MCP:

\begin{equation} \tag {19} \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,y) - (\bigtriangledown_{x_i} H(y,x)) \mu_i \\ \bigtriangledown_{y_i}f_i(x,y) - (\bigtriangledown_{y_i} H(y,x)) \mu_i \\ H(y_i,x)\\ \end{bmatrix}, & z_i = \begin{bmatrix} x_i \\ y_i \\ \mu_i \\ \end{bmatrix}. \\ \end{array} \end{equation}

Note that in this MCP the constraint \(H\) and the variable \(y\) are replicated \(N\) times. The size of the MCP is \((n + 2mN)\). This reformulation is obtained by specifying the option ImplVarModel=replication in the JAMS options file.

The second reformulation strategy involves switching each shared variable with the multiplier associated with its defining equation. This technique can be applied if all of the following three conditions are met:

The defining constraint is given as an equation.
The dimension of the range of the defining constraint equals the dimension of the shared variable.
The shared variable is a free (unbounded) variable.

The switching strategy uses the fact that in an MCP, the matching between free variables and equations is somewhat arbitrary: it can be re-assigned without changing the solution. Applying this technique, we obtain the following MCP:

\begin{equation} \tag {20} \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,y) - (\bigtriangledown_{x_i} H(y,x)) \mu_i \\ \bigtriangledown_{y_i}f_i(x,y) - (\bigtriangledown_{y_i} H(y,x)) \mu_i \\ \end{bmatrix}, & z_i = \begin{bmatrix} x_i \\ \mu_i \\ \end{bmatrix}\\ F_h(z) = \begin{bmatrix} H(y,x) \\ \end{bmatrix}, & z_h = \begin{bmatrix} y \\ \end{bmatrix}.\\ \end{array} \end{equation}

Observe that in this MCP, the defining constraint \(H\) and the shared variable \(y\) appear only once. Thus the size of the problem is reduced to \((n + mN + m)\). The EMP framework will use this reformulation if the option ImplVarModel=switching is specified in the JAMS option file. This is currently the default strategy used.

The third strategy is selected by specifying option ImplVarModel=substitution in the JAMS option file. It uses the implicit function theorem to substitute the multipliers \( \mu_i \) by new variables \( \Lambda_i \), where \( \Lambda_i = \bigtriangledown_{x_i} H(\bigtriangledown_y H)^{-1} \). This technique may be applied when the three conditions of the switching strategy are satisfied, and in addition, the implicit function theorem holds for the defining constraints. The basic idea is to regard the shared variable \(y\) as a function of other non-shared variables and apply the derivative. At each solution to the problem \((y^*,x^*)\), there exists a locally defined implicit function \(h_{x^*}(x)\) such that \( y^* = h_{x^*}(x^*)\) and \(H(h_{x^*} (x),x)=0\) for each \(x\) in some neighborhood of \(x^*\). It can be shown that given the implications of the implicit function theorem and the new variables \( \Lambda_i \), the equilibrium problem can be reformulated as the MCP that follows. However, we omit a step-by-step mathematical derivation here, it is given in Kim & Ferris (2017) [108].

\begin{equation} \tag {21} \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,y) - (\bigtriangledown_{y_i} f_i(x,y)) \Lambda_i \\ \bigtriangledown_{y} H(y,x) \Lambda_i - (\bigtriangledown_{x_i} H(y,x)) \\ \end{bmatrix}, & z_i = \begin{bmatrix} x_i \\ \Lambda_i \\ \end{bmatrix}\\ F_h(z) = \begin{bmatrix} H(y,x) \\ \end{bmatrix}, & z_h = \begin{bmatrix} y \\ \end{bmatrix}.\\ \end{array} \end{equation}

The size of this MCP is \((n+mn+m)\). It can be significantly reduced if the shared variable is explicitly defined, for example, \( H(y,x) = y-h(x) \). In this case, \((\bigtriangledown_y H)^{-1}\) is the identity matrix, therefore it is not neccessary to introduce the variables \(\Lambda_i\) and the MCP takes the following form:

\begin{equation} \tag {22} \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,y) - \bigtriangledown_{x_i}H(y,x) \bigtriangledown_y f_i(x,y) \\ \end{bmatrix}, & z_i = \begin{bmatrix} x_i \\ \end{bmatrix}\\ F_h(z) = \begin{bmatrix} H(y,x) \\ \end{bmatrix}, & z_h = \begin{bmatrix} y \\ \end{bmatrix}.\\ \end{array} \end{equation}

The size of this MCP is \( (n+m) \), which is a huge decrease compared to the other formulations. Note that the EMP framework detects automatically if the shared variable is explicitly defined and exploits this fact. In the following table an overview of the size of the MCP for the different reformulation techniques is given.

Strategy	Size of the MCP
Replication	\((n+2mN)\)
Switching	\((n+mN+m)\)
Substitution (implicit)	\((n+mn+m)\)
Substitution (explicit)	\((n+m)\)

Table 2: Size of the Reformulated MCP For Different Reformulation Techniques

Equilibrium Problems with Shared Variables: A Simple Example

The following simple example computes a saddle point of the Lagrangian associated with a minimization over \(x\) subject to a single equality constraint with dual multiplier \(y\). The GAMS EMP implementation is from Youngdae Kim. The primal (minimizing) and dual (maximizing) agents share the variable L containing the value of the Lagrangian, as well as its defining equation defL:

set i / 1*2 /;
variables
  L    'Lagrangian function: f(x) - y * h(x)'
  x(i) 'primal variables'
  y    'dual variable'
  ;
equation defL;
defL..
   L =e= sum{i, sqr(x(i)-1)} - y*(sum{i, x(i)} - 4);

model m / defL /;
file empinfo / '%emp.info%' /; putclose empinfo
  'equilibrium' /
  'implicit L defL' /
  '  min L x' /
  '  max L y' /
  ;

solve m using emp;

Note that the variable L is not indexed and it appears in the optimization problem of each agent. It is declared to be an implicit variable (using the keyword implicit) in the first line following the equilibrium keyword. Its defining constraint defL is listed only once, in this same line: it does not appear in the problem specification of each agent. By modeling the Lagrangian as a shared variable, its defining equation does not have to be replicated for each agent.

For other, more complex examples, both with shared decision variables and with a shared objective variable, see Kim & Ferris 2017 [108] .

Table of Contents

Reformulation Strategies for Equilibrium Problems with Shared Variables

Equilibrium Problems with Shared Variables: A Simple Example