On the impact of fair best response dynamics

Angelo Fanelli*, Luca Moscardelli, Alexander Skopalik

*Corresponding author for this work

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    7 Citations (Scopus)

    Abstract

    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 linear congestion games and we show that (i) if each player is allowed to play at least once and at most β times in T best responses, states with approximation ratio O(β) times the price of anarchy are reached after T ⌈loglogn⌉ best responses, and that (ii) 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 β needed to fast obtain efficient states, left open by [10,11] and [3], in which fast convergence for constant β and very slow convergence for β = O(n) have been shown, respectively. Finally, we show that the structure of the game implicitly affects its performances. In particular, we prove 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. All the results extend to weighted congestion games.

    Original languageEnglish
    Title of host publicationMathematical Foundations of Computer Science 2012
    Subtitle of host publication37th International Symposium, MFCS 2012, Proceedings
    EditorsBranislav Rovan, Vladimiro Sassone, Peter Widmayer
    Pages360-371
    Number of pages12
    ISBN (Electronic)978-3-642-32589-2
    DOIs
    Publication statusPublished - 20 Aug 2012
    Event37th International Symposium on Mathematical Foundations of Computer Science, MFCS 2012 - Bratislava, Slovakia
    Duration: 27 Aug 201231 Aug 2012
    Conference number: 37

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume7464 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Conference

    Conference37th International Symposium on Mathematical Foundations of Computer Science, MFCS 2012
    Abbreviated titleMFCS
    CountrySlovakia
    CityBratislava
    Period27/08/1231/08/12

    Keywords

    • Best Response Dynamics
    • Congestion Games
    • Speed of Convergence

    Fingerprint Dive into the research topics of 'On the impact of fair best response dynamics'. Together they form a unique fingerprint.

  • Cite this

    Fanelli, A., Moscardelli, L., & Skopalik, A. (2012). On the impact of fair best response dynamics. In B. Rovan, V. Sassone, & P. Widmayer (Eds.), Mathematical Foundations of Computer Science 2012: 37th International Symposium, MFCS 2012, Proceedings (pp. 360-371). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7464 LNCS). https://doi.org/10.1007/978-3-642-32589-2_33