Computing a proper equilibrium of a bimatrix game

We provide the first pivoting-type algorithm that computes an exact proper equilibrium of a bimatrix game. This is achieved by using Lemke's algorithm to solve a linear complementarity problem (LCP) of polynomial size. This also proves that computing a simple refinement of proper equilibria for bimatrix game is PPAD-complete. The algorithm also computes a witness in the form of a parameterized strategy that is an epsilon-proper equilibrium for any given sufficiently small epsilon, allowing polynomial-time verification of the properties of the refined equilibrium. The same technique can be applied to matrix games (two-player zero-sum), thereby computing a parameterized epsilon-proper strategy in polynomial time using linear programming.