Sampling from the Gibbs Distribution in Congestion Games

References

• [1] Ackermann H, Röglin H (2008) On the convergence time of the best response dynamics in player-specific congestion games. Preprint, submitted May 8, https://arxiv.org/abs/0805.1130.Google Scholar
• [2] Ackermann H, Röglin H, Vöcking B (2008) On the impact of combinatorial structure on congestion games. J. ACM 55(6):1–22.Google Scholar
• [3] Anari N, Gharan SO, Vinzant C (2018) Log-concave polynomials, entropy, and a deterministic approximation algorithm for counting bases of matroids. Proc. 59th Annual Sympos. Foundations Comput. Sci., 35–46.Google Scholar
• [4] Anari N, Liu K, Gharan SO, Vinzant C (2018) Log-concave polynomials III: Mason’s ultra-log-concavity conjecture for independent sets of matroids. Preprint, submitted July 2, https://arxiv.org/abs/1807.00929.Google Scholar
• [5] Anari N, Liu K, Gharan SO, Vinzant C (2019) Log-concave polynomials II: High-dimensional walks and an FPRAS for counting bases of a matroid. Proc. 51st Annual ACM SIGACT Sympos. Theory Comput., 1–12.Google Scholar
• [6] Anari N, Liu K, Gharan SO, Vinzant C, Vuong TD (2021) Log-concave polynomials IV: Approximate exchange, tight mixing times, and near-optimal sampling of forests. Proc. 53rd Annual ACM SIGACT Sympos. Theory Comput., 408–420.Google Scholar
• [7] Arman A, Gao P, Wormald N (2019) Fast uniform generation of random graphs with given degree sequences. Proc. 60th Annual Sympos. Foundations Comput. Sci., 1371–1379.Google Scholar
• [8] Asadpour A, Saberi A (2009) On the inefficiency ratio of stable equilibria in congestion games. Internet and Network Economics, 545–552.Crossref, Google Scholar
• [9] Auletta V, Ferraioli D, Pasquale F, Persiano G (2013) Mixing time and stationary expected social welfare of logit dynamics. Theory Comput. Systems 53(1):3–40.Crossref, Google Scholar
• [10] Auletta V, Ferraioli D, Pasquale F, Persiano G (2018) Metastability of logit dynamics for coordination games. Algorithmica 80(11):3078–3131.Crossref, Google Scholar
• [11] Auletta V, Ferraioli D, Pasquale F, Penna P, Persiano G (2015) Logit dynamics with concurrent updates for local interaction potential games. Algorithmica 73(3):511–546.Crossref, Google Scholar
• [12] Auletta V, Ferraioli D, Pasquale F, Penna P, Persiano G (2016) Convergence to equilibrium of logit dynamics for strategic games. Algorithmica 76(1):110–142.Crossref, Google Scholar
• [13] Bezáková I, Bhatnagar N, Vigoda E (2007) Sampling binary contingency tables with a greedy start. Random Structures Algorithms 30(1–2):168–205.Crossref, Google Scholar
• [14] Blume LE (1993) The statistical mechanics of strategic interaction. Games Econom. Behav. 5(3):387–424.Crossref, Google Scholar
• [15] Bobkov SG, Tetali P (2006) Modified logarithmic Sobolev inequalities in discrete settings. J. Theoretical Probab. 19(2):289–336.Crossref, Google Scholar
• [16] Brändén P, Huh J (2018) Hodge-Riemann relations for Potts model partition functions. Preprint, submitted November 5, https://arxiv.org/abs/1811.01696.Google Scholar
• [17] Brändén P, Huh J (2020) Lorentzian polynomials. Ann. Math. 192(3):821–891.Crossref, Google Scholar
• [18] Camerer CF (2010) Behavioural game theory. Behavioural and Experimental Economics, 42–50.Google Scholar
• [19] Chien S, Sinclair A (2011) Convergence to approximate Nash equilibria in congestion games. Games Econom. Behav. 71(2):315–327.Crossref, Google Scholar
• [20] Cryan M, Guo H, Mousa G (2019) Modified log-Sobolev inequalities for strongly log-concave distributions. Proc. 60th Annual Sympos. Foundations Comput. Sci., 1358–1370.Google Scholar
• [21] Del Pia A, Ferris M, Michini C (2017) Totally unimodular congestion games. Proc. 28th Annual ACM-SIAM Sympos. Discrete Algorithms, 577–588.Google Scholar
• [22] Diaconis P, Saloff-Coste L (1996) Logarithmic Sobolev inequalities for finite Markov chains. Ann. Appl. Probab. 6(3):695–750.Crossref, Google Scholar
• [23] Dyer M, Greenhill C, Kleer P, Ross J, Stougie L (2021) Sampling hypergraphs with given degrees. Discrete Math. 344(11):112566.Crossref, Google Scholar
• [24] Even-Dar E, Kesselman A, Mansour Y (2007) Convergence time to Nash equilibrium in load balancing. ACM Trans. Algorithms 3(3):32.Crossref, Google Scholar
• [25] Fabrikant A, Papadimitriou C, Talwar K (2004) The complexity of pure Nash equilibria. Proc. 36th Annual ACM Sympos. Theory Comput., 604–612.Google Scholar
• [26] Fanelli A, Moscardelli L (2011) On best response dynamics in weighted congestion games with polynomial delays. Distributed Comput. 24(5):245–254.Crossref, Google Scholar
• [27] Feder T, Mihail M (1992) Balanced matroids. Proc. 24th Annual ACM Sympos. Theory Comput., 26–38.Google Scholar
• [28] Ferraioli D (2013) Logit dynamics: A model for bounded rationality. ACM SIGecom Exchanges 12(1):34–37.Crossref, Google Scholar
• [29] Fotakis D (2010) Congestion games with linearly independent paths: Convergence time and price of anarchy. Theory Comput. Systems 47(1):113–136.Crossref, Google Scholar
• [30] Fujishige S, Goemans M, Harks T, Peis B, Zenklusen R (2015) Congestion games viewed from m-convexity. Oper. Res. Lett. 43(3):329–333.Crossref, Google Scholar
• [31] Garey MR, Johnson DS (1990) Computers and Intractability: A Guide to the Theory of NP-Completeness (W.H. Freeman & Co., New York).Google Scholar
• [32] Goel S (2004) Modified logarithmic Sobolev inequalities for some models of random walk. Stochastic Processes Appl. 114(1):51–79.Crossref, Google Scholar
• [33] Gourvès L, Monnot J (2009) On strong equilibria in the max cut game. Proc. Fifth Internat. Workshop Internet Network Econom., 608–615.Google Scholar
• [34] Gurvits L (2010) On multivariate Newton-like inequalities. Advances in Combinatorial Mathematics, 61–78.Google Scholar
• [35] Helgason T (1974) Aspects of the theory of hypermatroids. Hypergraph Seminar (Springer, Berlin/Heidelberg), 191–213.Google Scholar
• [36] Hermon J, Salez J (2019) Modified log-Sobolev inequalities for strong-Rayleigh measures. Preprint, submitted February 7, https://arxiv.org/abs/1902.02775.Google Scholar
• [37] Holzman R, Law-Yone N (1997) Strong equilibrium in congestion games. Games Econom. Behav. 21(1–2):85–101.Crossref, Google Scholar
• [38] Ieong S, McGrew R, Nudelman E, Shoham Y, Sun Q (2005) Fast and compact: A simple class of congestion games. Proc. 20th Natl. Conf. Artificial Intelligence, 489–494.Google Scholar
• [39] Jerrum M, Sinclair A (1993) Polynomial-time approximation algorithms for the Ising model. SIAM J. Comput. 22(5):1087–1116.Crossref, Google Scholar
• [40] Jerrum M, Sinclair A, Vigoda E (2004) A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. J. ACM 51(4):671–697.Crossref, Google Scholar
• [41] Jerrum M, Son JB, Tetali P, Vigoda E (2004) Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains. Ann. Appl. Probab. 14(4):1741–1765.Crossref, Google Scholar
• [42] Kleer P (2021) Sampling from the Gibbs distribution in congestion games. Proc. 22nd ACM Conf. Econom. Comput., 679–680.Google Scholar
• [43] Kleer P, Schäfer G (2017) Potential function minimizers of combinatorial congestion games: Efficiency and computation. Proc. 18th ACM Conf. Econom. Comput., 223–240.Google Scholar
• [44] Levin DA, Luczak MJ, Peres Y (2010) Glauber dynamics for the mean-field Ising model: Cut-off, critical power law, and metastability. Probab. Theory Related Fields 146(1–2):223–265.Crossref, Google Scholar
• [45] Mamageishvili A, Penna P (2016) Tighter bounds on the inefficiency ratio of stable equilibria in load balancing games. Oper. Res. Lett. 44(5):645–648.Crossref, Google Scholar
• [46] Martin RA, Randall D (2000) Sampling adsorbing staircase walks using a new Markov chain decomposition method. Proc. 41st Annual Sympos. Foundations Comput. Sci., 492–502.Google Scholar
• [47] Mäs M, Nax HH (2016) A behavioral study of “noise” in coordination games. J. Econom. Theory 162:195–208.Crossref, Google Scholar
• [48] McFadden D (1973) Conditional logit analysis of qualitative choice behavior. Frontiers in Econometrics, 105–142.Google Scholar
• [49] McKay BD (1984) Asymptotics for 0-1 matrices with prescribed line sums. Enumeration and Design (Academic Press, Cambridge, MA), 225–238.Google Scholar
• [50] Mihail M, Vazirani U (1989) On the expansion of 0-1 polytopes. J. Combin. Theory Ser. BGoogle Scholar
• [51] Murota K (1998) Discrete convex analysis. Math. Programming 83(1–3):313–371.Crossref, Google Scholar
• [52] Murota K (2003) Discrete convex analysis. SIAM Monograph on Discrete Mathematics and Applications (Society for Industrial and Applied Mathematics).Crossref, Google Scholar
• [53] Murota K (2009) Recent developments in discrete convex analysis. Research Trends in Combinatorial Optimization, 219–260.Google Scholar
• [54] Penna P (2018) The price of anarchy and stability in general noisy best-response dynamics. Internat. J. Game Theory 47(3):839–855.Crossref, Google Scholar
• [55] Rosenthal RW (1973) A class of games possessing pure-strategy Nash equilibria. Internat. J. Game Theory 2:65–67.Crossref, Google Scholar
• [56] Sandholm WH (2010) Population Games and Evolutionary Dynamics (MIT Press, Cambridge, MA).Google Scholar
• [57] Schrijver A (2003) Combinatorial optimization: Polyhedra and efficiency. Matroids, Trees, Stable Sets, vol. B, Algorithms and Combinatorics (Springer-Verlag, Berlin).Google Scholar
• [58] Sinclair A (1992) Improved bounds for mixing rates of Markov chains and multicommodity flow. Combin. Probab. Comput. 1(4):351–370.Crossref, Google Scholar
• [59] Skopalik A, Vöcking B (2008) Inapproximability of pure Nash equilibria. Proc. 40th Annual ACM Sympos. Theory Comput., 355–364.Google Scholar