Return to Colloquia & Seminar listing
A simple reduction of wide range of optimization, engineering and economics problems to Bimatrix Games.
Mathematics of Data & Decisions| Speaker: | Ilan Adler, UC Berkeley |
| Related Webpage: | https://ieor.berkeley.edu/people/faculty/adler |
| Location: | 1147 MSB |
| Start time: | Tue, Jan 29 2019, 4:10PM |
It is well known that many optimization problems, ranging from linear programming to hard combinatorial problems, as well as many engineering and economics problems, can be formulated as linear complementarity problems (LCP).
One particular LCP, finding a Nash equilibrium of a bimatrix game (2-NASH), motivated the development of the elegant Simplex-like Lemke’s algorithm which is guaranteed to terminate in a finite number of iterations but not necessarily with a solution (or a certificate that no solution exists). Over the years, many subclasses of LCP, covering a variety of optimization problems, were proven to be solvable by Lemke’s algorithm.
It turned out that, in general, Lemke solvable LCPs belong to the complexity class PPAD (Polynomial-time Parity Argument Directed) and that, quite surprisingly, 2 NASH is PPAD-complete. Thus, Lemke solvable LCPs can be formulated as 2 NASH. While of great theoretical value, the ingeniously constructed reduction (which is designed for all PPAD problem) is very complicated, difficult to implement, and not readily available for potential insights.
In this talk, I’ll present and discuss a simple reduction of Lemke-solvable LCPs to bimatrix games that is easy to implement and have the potential to gain additional insights to problems (including several models of market equilibrium) for which the reduction is applicable.