Approximate Well-supported Nash Equilibria below Two-thirds

Details Approximate Well-supported Nash Equilibria below Two-thirds Approximate Well-supported Nash Equilibria below Two-thirds

2012-04-03

arxiv.org/abs/1204.0707v1

Computer Science

Computer Science and Game Theory

Scientific paper

In an epsilon-Nash equilibrium, a player can gain at most epsilon by changing his behaviour. Recent work has addressed the question of how best to compute epsilon-Nash equilibria, and for what values of epsilon a polynomial-time algorithm exists. An epsilon-well-supported Nash equilibrium (epsilon-WSNE) has the additional requirement that any strategy that is used with non-zero probability by a player must have payoff at most epsilon less than the best response. A recent algorithm of Kontogiannis and Spirakis shows how to compute a 2/3-WSNE in polynomial time, for bimatrix games. Here we introduce a new technique that leads to an improvement to the worst-case approximation guarantee.

Affiliated with

Also associated with

No associations

Rating

Approximate Well-supported Nash Equilibria below Two-thirds 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 Approximate Well-supported Nash Equilibria below Two-thirds, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximate Well-supported Nash Equilibria below Two-thirds will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-355118