Rank-1 Bi-matrix Games: A Homeomorphism and a Polynomial Time Algorithm

Details Rank-1 Bi-matrix Games: A Homeomorphism and a Polynomial Time Algorithm Rank-1 Bi-matrix Games: A Homeomorphism and a Polynomial Time Algorithm

2010-10-15

arxiv.org/abs/1010.3083v2

Computer Science

Computer Science and Game Theory

Scientific paper

Given a rank-1 bimatrix game (A,B), i.e., where rank(A+B)=1, we construct a suitable linear subspace of the rank-1 game space and show that this subspace is homeomorphic to its Nash equilibrium correspondence. Using this homeomorphism, we give the first polynomial time algorithm for computing an exact Nash equilibrium of a rank-1 bimatrix game. This settles an open question posed in Kannan and Theobald (SODA 2007) and Theobald (2007). In addition, we give a novel algorithm to enumerate all the Nash equilibria of a rank-1 game and show that a similar technique may also be applied for finding a Nash equilibrium of any bimatrix game. This technique also proves the existence, oddness and the index theorem of Nash equilibria in a bimatrix game. Further, we extend the rank-1 homeomorphism result to a fixed rank game space, and give a fixed point formulation on $[0,1]^k$ for solving a rank-k game. The homeomorphism and the fixed point formulation are piece-wise linear and considerably simpler than the classical constructions.

Affiliated with

Also associated with

No associations

Rating

Rank-1 Bi-matrix Games: A Homeomorphism and a Polynomial Time Algorithm does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Rank-1 Bi-matrix Games: A Homeomorphism and a Polynomial Time Algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rank-1 Bi-matrix Games: A Homeomorphism and a Polynomial Time Algorithm will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-203479