Existence and solution methods for equilibria
Giancarlo Bigi, Marco Castellani, Massimo Pappalardo and Mauro Passacantando
Summary
In scientific contexts the term "equilibrium" has been widely used at least in physics, chemistry, engineering and economics within different frameworks,
relying on different mathematical models. For instance, it may refer to physical or mechanical structures, chemical processes, the distribution of traffic over
computer and telecommunication networks or over public roads. In economics it often refers to production competition or the dynamics of offer and demand,
exploiting the mathematical model of noncooperative games and the corresponding equilibrium concept by Nash.
This survey paper deals with those equilibrium problems which are relevant in operations research and mathematical programming. Many problems
involving equilibria can be modeled in this framework through different mathematical models such as optimization, variational inequalities and
noncooperative games among others. In turn, these mathematical models share an underlying common structure which allows to conveniently formulate
them in a unique format. Therefore, theoretical developments and algorithms developed for one of these models can be generally modified to cope with
the others through the common format in a unifying language.
This format was named "equilibrium problem" by Blum and Oettli (Math. Student 1994), who stressed this unifying feature and provided a thorough
investigation of its theoretical properties. Until then, this format did not actually receive much attention: Nikaido and Isoda characterized Nash
equilibria as the solutions of the equiliberium problem for an appropriate auxiliary bifunction (Pacific J. Math 1955) but they did not consider the problem
itself in an independent fashion; Gwinner introduced it just as a tool to develop a unified treatment of penalization techniques for optimization and variational
inequalities (Lecture Notes in Pure and Appl. Math. 1983); Antipin first formulated an inverse optimization problem as a noncooperative game and therefore in this
general format via the Nikaido-Isoda bifunction (Lecture Notes in Control and Inform. Sci. 1990), and afterwards provided a solution method for the general
problem (Comput. Math. Math. Phys. 1995, 1997).
Indeed, equilibrium problems in the above format started to gain real interest only after the publication of the seminal paper of Blum and Oettli.
Actually, the possibility to exploit results and algorithms developed for one class of problems in another framework was not a novelty at all: this
kind of bridge already finds roots in the analytical development of variational inequalities through the connection with optimization via
complementarity problems. Anyway, a large number of applications has been described successfully via the concept of equilibrium solution and therefore
many researchers devoted their efforts to study the equilibrium problem. In fact, nowadays there is a good theory for equilibria and a rapidly increasing
number of algorithms for finding them.
In this paper we aim at reviewing two core issues up to the state of the art: the existence of equilibria and the solution methods. In order to make the paper
as readable as possible, instead of presenting all the technical details of the results, we propose a structured overview with different levels. In particular,
the existence results are divided into groups according to the required assumptions, while the solution methods are classified depending on the kind of problems
which are solved at each iteration.
A Technical Report version is available
here (gzipped .pdf file).
My Home Page