Using Linear Programming and Divide and Conquer to Solve Large Games of Imperfect Information

Solving games of imperfect information with linear programming took a significant leap forward when Koller, Megiddo, and Stengel (KMS) proposed an exponentially more compact way to represent two-player games of imperfect information as linear programs. Despite this substantial advancement many recent works on solving these games rely on Counter Factual Regret Minimization (CFR) as opposed to linear programming. One reason CFR became a standard approach is that CFR is easily parallelizable whereas the linear program defined by KMS's technique is difficult to solve in parallel. Convenient parallelism made CFR more amenable to multi-core computing environments and large games. This paper presents a method to parallelize the linear programing techniques of KMS. The proposed iterative method divides a potentially intractable linear program representing a large game of imperfect information into many smaller linear programs. Each of the smaller LPs can be processed independently and in parallel. It is shown that the solutions to the smaller LPs interact together over multiple iterations of this algorithm to produce a strategy pair that converges to the Nash Equilibrium solution to the original undivided problem. This is the first work to propose a Dantzig-Wolfe style decomposition for solving two-player games of imperfect information.