AAAI Publications, Thirty-First AAAI Conference on Artificial Intelligence

Font Size: 
Resource Graph Games: A Compact Representation for Games with Structured Strategy Spaces
Albert Xin Jiang, Hau Chan, Kevin Leyton-Brown

Last modified: 2017-02-10

Abstract


In many real-world systems, strategic agents' decisions can be understood as complex - i.e., consisting of multiple sub-decisions - and hence can give rise to an exponential number of pure strategies. Examples include network congestion games, simultaneous auctions, and security games. However, agents' sets of strategies are often structured, allowing them to be represented compactly. There currently exists no general modeling language that captures a wide range of commonly seen strategy structure and utility structure. We propose Resource Graph Games (RGGs), the first general compact representation for games with structured strategy spaces, which is able to represent a wide range of games studied in literature. We leverage recent results about multilinearity, a key property of games that allows us to represent the mixed strategies compactly, and, as a result, to compute various equilibrium concepts efficiently. While not all RGGs are multilinear, we provide a general method of converting RGGs to those that are multilinear, and identify subclasses of RGGs whose converted version allow efficient computation.

Keywords


Games; Compact representation; Action graph; multilinear; mixed strategies; computation; examples; structured space; structured utility; Nash equilibrium; coarse correlated equilibrium; modeling

Full Text: PDF