Speeding Up Gradient-Based Algorithms for Sequential Games

First-order (i. e. , gradient-based) methods for solving two-personzero-sum sequential games of imperfect information have recentlybecome important tools in the construction of game theory-basedagents. The computation time per iteration is typically dominatedby matrix-vector product operations involving the payoff matrix$A$. In this paper, we describe two techniques for scaling up thisoperation. The first is a randomized sampling technique that approximates $A$ with a sparser matrix $\tilde{A}$. Then an approximate equilibrium for the original game is found by finding an approximateequilibrium of the sampled game. The second technique involvesthe development of an algorithm and system for performing thematrix-vector product on a cache-coherent Non-Uniform MemoryAccess (ccNUMA) architecture. The two techniques can be appliedtogether or separately, and they each lead to an algorithm that significantly outperforms the fastest prior gradient-based method.

Authors

• Andrew Gilpin Tuomas Sandholm
• Tuomas Sandholm Carnegie Mellon University, Computer Science Department, Pittsburgh, USA Strategy Robot, Inc. Strategic Machine, Inc. Optimized Markets, Inc.

Keywords

• Equilibrium finding
• automated abstraction
• computational game theory
• sequential games of imperfect information