Bilinear games: Polynomial time algorithms for rank based subclasses

Jugal Garg, Albert Xin Jiang, Ruta Mehta

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

Abstract

Motivated by the sequence form formulation of Koller et al. [16], this paper considers bilinear games, represented by two payoff matrices (A,B) and compact polytopal strategy sets. Bilinear games are very general and capture many interesting classes of games including bimatrix games, two player Bayesian games, polymatrix games, and two-player extensive form games with perfect recall as special cases, and hence are hard to solve in general. For a bilinear game, we define its best response polytopes (BRPs) and characterize its Nash equilibria as the fully-labeled pairs of the BRPs. Rank of a game (A,B) is defined as rank(A+B). In this paper, we give polynomial-time algorithms for computing Nash equilibria of (i) rank-1 games, (ii) FPTAS for constant-rank games, and (iii) when rank(A) or rank(B) is constant.

Original languageEnglish (US)
Title of host publicationInternet and Network Economics - 7th International Workshop, WINE 2011, Proceedings
PublisherSpringer-Verlag Berlin Heidelberg
Pages399-407
Number of pages9
ISBN (Print)9783642255090
DOIs
StatePublished - 2011
Externally publishedYes
Event7th International Workshop on Internet and Network Economics, WINE 2011 - Singapore, Singapore
Duration: Dec 11 2011Dec 14 2011

Publication series

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

Other

Other7th International Workshop on Internet and Network Economics, WINE 2011
CountrySingapore
CitySingapore
Period12/11/1112/14/11

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Bilinear games: Polynomial time algorithms for rank based subclasses'. Together they form a unique fingerprint.

Cite this