On the Impact of Fair Best Response Dynamics

Details On the Impact of Fair Best Response Dynamics On the Impact of Fair Best Response Dynamics

2011-04-29

arxiv.org/abs/1104.5642v1

Computer Science

Computer Science and Game Theory

Scientific paper

In this work we completely characterize how the frequency with which each player participates in the game dynamics affects the possibility of reaching efficient states, i.e., states with an approximation ratio within a constant factor from the price of anarchy, within a polynomially bounded number of best responses. We focus on the well known class of congestion games and we show that, if each player is allowed to play at least once and at most $\beta$ times any $T$ best responses, states with approximation ratio $O(\beta)$ times the price of anarchy are reached after $T \lceil \log \log n \rceil$ best responses, and that such a bound is essentially tight also after exponentially many ones. One important consequence of our result is that the fairness among players is a necessary and sufficient condition for guaranteeing a fast convergence to efficient states. This answers the important question of the maximum order of $\beta$ needed to fast obtain efficient states, left open by [9,10] and [3], in which fast convergence for constant $\beta$ and very slow convergence for $\beta=O(n)$ have been shown, respectively. Finally, we show that the structure of the game implicitly affects its performances. In particular, we show that in the symmetric setting, in which all players share the same set of strategies, the game always converges to an efficient state after a polynomial number of best responses, regardless of the frequency each player moves with.

Affiliated with

Also associated with

No associations

Rating

On the Impact of Fair Best Response Dynamics 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 On the Impact of Fair Best Response Dynamics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Impact of Fair Best Response Dynamics will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-17939