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