Strategy Purification

There has been significant recent interest in computing good strategies for large games. Most prior work involves computing an approximate equilibrium strategy in a smaller abstract game, then playing this strategy in the full game. In this paper, we present a modification of this approach that works by constructing a deterministic strategy in the full game from the solution to the abstract game; we refer to this procedure as purification. We show that purification, and its generalization which we call thresholding, lead to significantly stronger play than the standard approach in a wide variety of experimental domains. One can view these approaches as ways of achieving robustness against one's own lossy abstraction.

Authors

• Sam Ganzfried
• Tuomas Sandholm Carnegie Mellon University, Computer Science Department, Pittsburgh, USA Strategy Robot, Inc. Strategic Machine, Inc. Optimized Markets, Inc.
• Kevin Waugh

Keywords

• Game theory