TY - GEN
T1 - Bilinear games
T2 - 7th International Workshop on Internet and Network Economics, WINE 2011
AU - Garg, Jugal
AU - Jiang, Albert Xin
AU - Mehta, Ruta
PY - 2011
Y1 - 2011
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=82955184506&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=82955184506&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-25510-6_35
DO - 10.1007/978-3-642-25510-6_35
M3 - Conference contribution
AN - SCOPUS:82955184506
SN - 9783642255090
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 399
EP - 407
BT - Internet and Network Economics - 7th International Workshop, WINE 2011, Proceedings
PB - Springer
Y2 - 11 December 2011 through 14 December 2011
ER -