Modeling and Optimization: Theory and Applications

Conference program

Wednesday 16th of August 2017

7:30 8:15 Registration and breakfast
8:15 8:30 Welcome
8:30 9:30 Plenary talk
 Simple Reduction of Lemke's Solvable Linear Complementarity Problems to Bimatrix Games Ilan Adler abstract Simple Reduction of Lemke's Solvable Linear Complementarity Problems to Bimatrix Games Ilan Adler 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 PPADcomplete. 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.
9:30 9:45 Coffee break
9:45 11:15 Parallel technical sessions