Combining Compact Representation and Incremental Generation in Large Games with Sequential Strategies

Authors

  • Branislav Bosansky Aarhus University
  • Albert Xin Jiang Trinity University
  • Milind Tambe University of Southern California
  • Christopher Kiekintveld University of Texas at El Paso

DOI:

https://doi.org/10.1609/aaai.v29i1.9319

Keywords:

normal-form games with sequential strategies, incremental strategy generation, zero-sum games

Abstract

Many search and security games played on a graph can be modeled as normal-form zero-sum games with strategies consisting of sequences of actions. The size of the strategy space provides a computational challenge when solving these games. This complexity is tackled either by using the compact representation of sequential strategies and linear programming, or by incremental strategy generation of iterative double-oracle methods. In this paper, we present novel hybrid of these two approaches: compact-strategy double-oracle (CS-DO) algorithm that combines the advantages of the compact representation with incremental strategy generation. We experimentally compare CS-DO with the standard approaches and analyze the impact of the size of the support on the performance of the algorithms. Results show that CS-DO dramatically improves the convergence rate in games with non-trivial support

Downloads

Published

2015-02-16

How to Cite

Bosansky, B., Jiang, A. X., Tambe, M., & Kiekintveld, C. (2015). Combining Compact Representation and Incremental Generation in Large Games with Sequential Strategies. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1). https://doi.org/10.1609/aaai.v29i1.9319

Issue

Section

AAAI Technical Track: Game Theory and Economic Paradigms