Multilinear games

Hau Chan, Albert Xin Jiang, Kevin Leyton-Brown, Ruta Mehta

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In many games, players’ decisions consist of multiple subdecisions, and hence can give rise to an exponential number of pure strategies. However, this set of pure strategies is often structured, allowing it to be represented compactly, as in network congestion games, security games, and extensive form games. Reduction to the standard normal form generally introduces exponential blow-up in the strategy space and therefore are inefficient for computation purposes. Although individual classes of such games have been studied, there currently exists no general purpose algorithms for computing solutions. equilibrium. To address this, we define multilinear games generalizing all. Informally, a game is multilinear if its utility functions are linear in each player’s strategy, while fixing other players’ strategies. Thus, if pure strategies, even if they are exponentially many, are vectors in polynomial dimension, then we show that mixed-strategies have an equivalent representation in terms of marginals forming a polytope in polynomial dimension. The canonical representation for multilinear games can still be exponential in the number of players, a typical obstacle in multi-player games. Therefore, it is necessary to assume additional structure that allows computation of certain sub-problems in polynomial time. Towards this, we identify two key subproblems: computation of utility gradients, and optimizing linear functions over strategy polytope. Given a multilinear game, with polynomial time subroutines for these two tasks, we show the following: (a) We can construct a polynomially computable and continuous fixed-point formulation, and show that its approximate fixed-points are approximate NE. This gives containment of approximate NE computation in PPAD, and settles its complexity to PPAD-complete. (b) Even though a coarse correlated equilibrium can potentially have exponential representation , through LP duality and a carefully designed separation oracle, we provide a polynomial-time algorithm to compute one with polynomial representation. (c) We show existence of an approximate NE with support-size logarithmic in the strategy polytope dimensions.

Original languageEnglish (US)
Title of host publicationWeb and Internet Economics - 12th International Conference, WINE 2016, Proceedings
EditorsAdrian Vetta, Yang Cai
PublisherSpringer-Verlag
Pages44-58
Number of pages15
ISBN (Print)9783662541098
DOIs
StatePublished - Jan 1 2016
Event12th International Conference on Web and Internet Economics, WINE 2016 - Montreal, Canada
Duration: Jun 11 2016Jul 14 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10123 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other12th International Conference on Web and Internet Economics, WINE 2016
CountryCanada
CityMontreal
Period6/11/167/14/16

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Multilinear games'. Together they form a unique fingerprint.

  • Cite this

    Chan, H., Jiang, A. X., Leyton-Brown, K., & Mehta, R. (2016). Multilinear games. In A. Vetta, & Y. Cai (Eds.), Web and Internet Economics - 12th International Conference, WINE 2016, Proceedings (pp. 44-58). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10123 LNCS). Springer-Verlag. https://doi.org/10.1007/978-3-662-54110-4_4