Games of fixed rank: A hierarchy of bimatrix games

Details Games of fixed rank: A hierarchy of bimatrix games Games of fixed rank: A hierarchy of bimatrix games

2005-11-04

arxiv.org/abs/cs/0511021v1

Computer Science

Computer Science and Game Theory

13 pages

Scientific paper

We propose a new hierarchical approach to understand the complexity of the open problem of computing a Nash equilibrium in a bimatrix game. Specifically, we investigate a hierarchy of bimatrix games $(A,B)$ which results from restricting the rank of the matrix $A+B$ to be of fixed rank at most $k$. For every fixed $k$, this class strictly generalizes the class of zero-sum games, but is a very special case of general bimatrix games. We show that even for $k=1$ the set of Nash equilibria of these games can consist of an arbitrarily large number of connected components. While the question of exact polynomial time algorithms to find a Nash equilibrium remains open for games of fixed rank, we can provide polynomial time algorithms for finding an $\epsilon$-approximation.

Affiliated with

Also associated with

No associations

Rating

Games of fixed rank: A hierarchy of bimatrix games 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 Games of fixed rank: A hierarchy of bimatrix games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Games of fixed rank: A hierarchy of bimatrix games will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-57839