The reduction of PPAD linear complementarity problems to bimatrix games
Ilan Adler
Professor, Department of Industrial Engineering and Operations Research
University of California at Berkeley
Wednesday, April 24
4:15 - 5:15 PM
Y2E2, Room 101
Abstract:
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 problem, finding a Nash equilibrium of a bimatrix game (2 NASH), which can be formulated as LCP, motivated the development of the elegant Lemke algorithm to solve LCPs. While the algorithm always terminates, it can generate either a solution or a so-called ‘secondary ray’. We say that the algorithm process a given LCP if a secondary ray can be used to certify, in polynomial time, that no solution exists. It turned out that in general, Lemke-processable LCPs belong to the complexity class PPAD and that, quite surprisingly, 2 NASH is PPAD-complete. Thus, Lemke-processable LCPs can be formulated as 2 NASH. However, the known formulation (which is designed for any 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 (and easy to implement) reduction to 2 NASH of what we call Lemke-LCP, where the goal is to obtain either a solution or a secondary ray of a given LCP. As a consequence, this reduction leads to simple reduction to 2 NASH of a large class of PPAD LCPs, including several models of market equilibrium.
Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html