- Series
- ACO Colloquium
- Time
- Thursday, March 27, 2014 - 3:00pm for 1 hour (actually 50 minutes)
- Location
- Skiles 268
- Speaker
- Ilan Adler – University of California, Berkeley
- Organizer
- Robin Thomas

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
elegant Lemke algorithm to solve LCPs. While the algorithm always
terminates, it can generates either a solution
or a so-called ‘secondary ray’. We say that the algorithm resolves
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-resolvable LCPs belong to the complexity class
PPAD and that, quite surprisingly, 2 NASH is PPAD-complete. Thus,
Lemke-resolvable 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
reduction of Lemke-resolvable 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.