Table of Contents
In the last section, we relaxed the restriction that each constraint has to be controlled by a single agent and introduced shared constraints. In this section, we go a step further and allow shared variables. Note that the content of this section is adapted from Kim & Ferris (2017) [108].
First, we introduce the notion of implicit variables. In mathematical terms, a variable
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
Note that there are
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:
Note that in this MCP the constraint 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:
Observe that in this MCP, the defining constraint 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
The size of this MCP is
The size of this MCP is
Strategy | Size of the MCP |
---|---|
Replication | |
Switching | |
Substitution (implicit) | |
Substitution (explicit) |
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 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] .