The Buck-Passing Game

References

• [1] Aldous D, Fill JA (2002) Reversible Markov chains and random walks on graphs, unfinished monograph, recompiled 2014. Accessed August 9, 2018, http://www.stat.berkeley.edu/ aldous/RWG/book.html.Google Scholar
• [2] Anantharam V, Tsoucas P (1989) A proof of the Markov chain tree theorem. Statist. Probab. Lett. 8(2):189–192.Crossref, Google Scholar
• [3] Andersen R, Chung F, Lang K (2008) Local partitioning for directed graphs using PageRank. Internet Math. 5(1–2):3–22.Crossref, Google Scholar
• [4] Anshelevich E, Dasgupta A, Kleinberg J, Tardos É, Wexler T, Roughgarden T (2008) The price of stability for network design with fair cost allocation. SIAM J. Comput. 38(4):1602–1623.Crossref, Google Scholar
• [5] Avis D, Iwama K, Paku D (2014) Reputation games for undirected graphs. Discrete Appl. Math. 166:1–13.Crossref, Google Scholar
• [6] Avrachenkov K, Litvak N (2004) Decomposition of the Google PageRank and optimal linking strategy. Technical report, INRIA. Accessed August 9, 2018, https://hal.inria.fr/inria-00071482/document.Google Scholar
• [7] Avrachenkov K, Litvak N (2006) The effect of new links on Google PageRank. Stochastic Models 22(2):319–331.Crossref, Google Scholar
• [8] Avrachenkov K, Litvak N, Son Pham K (2008) A singular perturbation approach for choosing the PageRank damping factor. Internet Math. 5(1–2):47–69.Crossref, Google Scholar
• [9] Bogomolnaia A, Moulin H, Sandomirskiy F (2021) On the fair division of a random object. Management Sci. Forthcoming.Google Scholar
• [10] Borkar VS, Ejov V, Filar JA (2004) Directed graphs, Hamiltonicity and doubly stochastic matrices. Random Structures Algorithms 25(4):376–395.Crossref, Google Scholar
• [11] Borkar VS, Ejov V, Filar JA (2009) On the Hamiltonicity gap and doubly stochastic matrices. Random Structures Algorithms 34(4):502–519.Crossref, Google Scholar
• [12] Borkar VS, Ejov V, Filar JA, Nguyen GT (2012) Hamiltonian Cycle Problem and Markov Chains (Springer, New York).Crossref, Google Scholar
• [13] Brin S, Page L (1998) The anatomy of a large-scale hypertextual web search engine. Comput. Newtorks ISDN Systems 30(1–7):107–117.Google Scholar
• [14] Candogan O, Menache I, Ozdaglar A, Parrilo PA (2011) Flows and decompositions of games: Harmonic and potential games. Math. Oper. Res. 36(3):474–503.Link, Google Scholar
• [15] Caputo P, Quattropani M (2021) Mixing time of PageRank surfers on sparse random digraphs. Random Structures Algorithms 59(3):376–406.Crossref, Google Scholar
• [16] Castaldo M, Catalano C, Como G, Fagnani F (2020) On a centrality maximization game. IFAC-PapersOnLine 53(2):2844–2849.Crossref, Google Scholar
• [17] Chen N, Litvak N, Olvera-Cravioto M (2017) Generalized PageRank on directed configuration networks. Random Structures Algorithms 51(2):237–274.Crossref, Google Scholar
• [18] Chen W, Teng SH, Wang Y, Zhou Y (2009) On the α-sensitivity of Nash equilibria in PageRank-based network reputation games. Deng X, Hopcroft JE, Xue J, eds. Frontiers in Algorithmics (Springer, Berlin, Heidelberg), 63–73.Crossref, Google Scholar
• [19] de Kerchove C, Ninove L, van Dooren P (2008) Maximizing PageRank via outlinks. Linear Algebra Appl. 429(5–6):1254–1276.Crossref, Google Scholar
• [20] Ejov V, Filar JA, Nguyen MT (2004) Hamiltonian cycles and singularly perturbed Markov chains. Math. Oper. Res. 29(1):114–131.Link, Google Scholar
• [21] Ejov V, Filar JA, Murray W, Nguyen GT (2008) Determinants and longest cycles of graphs. SIAM J. Discrete Math. 22(3):1215–1225.Crossref, Google Scholar
• [22] Ejov V, Litvak N, Nguyen GT, Taylor PG (2011) Proof of the Hamiltonicity-trace conjecture for singularly perturbed Markov chains. J. Appl. Probab. 48(4):901–910.Crossref, Google Scholar
• [23] Filar JA (2006) Controlled Markov chains, graphs, and Hamiltonicity. Foundations Trends Stochastic Systems 1(2):77–162.Crossref, Google Scholar
• [24] Filar JA, Krass D (1994) Hamiltonian cycles and Markov chains. Math. Oper. Res. 19(1):223–237.Link, Google Scholar
• [25] Fournier G, Scarsini M (2019) Location games on networks: Existence and efficiency of equilibria. Math. Oper. Res. 44(1):212–235.Abstract, Google Scholar
• [26] Galeotti A, Goyal S, Jackson MO, Vega-Redondo F, Yariv L (2010) Network games. Rev. Econom. Stud. 77(1):218–244.Crossref, Google Scholar
• [27] Garavaglia A, van der Hofstad R, Litvak N (2020) Local weak convergence for PageRank. Ann. Appl. Probab. 30(1):40–79.Crossref, Google Scholar
• [28] Gopalakrishnan R, Marden JR, Wierman A (2014) Potential games are necessary to ensure pure Nash equilibria in cost sharing games. Math. Oper. Res. 39(4):1252–1296.Link, Google Scholar
• [29] Hopcroft J, Sheldon D (2008) Manipulation-resistant reputations using hitting time. Internet Math. 5(1–2):71–90.Crossref, Google Scholar
• [30] Hopcroft J, Sheldon D (2008) Network reputation games. Cornell University, Computing and Information Science Technical Reports.Google Scholar
• [31] Jeh G, Widom J (2003) Scaling personalized web wearch. Hencsey G, White B, eds. Proc. 12th Internat. Conf. World Wide Web (ACM, New York), 271–279.Google Scholar
• [32] Kearns MJ, Littman ML, Singh SP (2001) Graphical models for game theory. Breese JS, Koller D, eds. Proc. 17th Conf. Uncertainty Artificial Intelligence.Google Scholar
• [33] Kouroupas G, Markakis E, Papadimitriou C, Rigas V, Sideri M (2015) The web graph as an equilibrium. Hoefer M, ed. Algorithmic Game Theory (Springer, Heidelberg), 203–215.Crossref, Google Scholar
• [34] Koutsoupias E, Papadimitriou CH (1999) Worst-case equilibria. Meinel C, Tison S, eds. Proc. 16th Annual Sympo. Theoretical Aspects Comput. Sci.Google Scholar
• [35] Koutsoupias E, Papadimitriou C (2009) Worst-case equilibria. Comput. Sci. Rev. 3(2):65–69.Crossref, Google Scholar
• [36] Lã QD, Chew Y, Soong BH (2016) Potential Game Theory Applications in Radio Resource Allocation (Springer, Cham, Switzerland).Google Scholar
• [37] Lee J, Olvera-Cravioto M (2020) PageRank on inhomogeneous random digraphs. Stochastic Processes Their Appl. 130(4):2312–2348.Crossref, Google Scholar
• [38] Leighton F, Rivest R (1986) Estimating a probability using finite memory. IEEE Trans. Inform. Theory 32(6):733–742.Crossref, Google Scholar
• [39] Levin DA, Peres Y (2017) Markov Chains and Mixing Times (American Mathematical Society, Providence, RI).Crossref, Google Scholar
• [40] Litvak N, Ejov V (2009) Markov chains and optimality of the Hamiltonian cycle. Math. Oper. Res. 34(1):71–82.Link, Google Scholar
• [41] Mavronicolas M, Monien B, Papadopoulou VG, Schoppmann F (2008) Voronoi games on cycle graphs. Ochmanski E, TyskKiewicz J, eds. Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, vol. 5162 (Springer, Berlin), 503–514.Google Scholar
• [42] Monderer D, Shapley LS (1996) Potential games. Games Econom. Behav. 14(1):124–143.Crossref, Google Scholar
• [43] Moulin H (2019) Fair division in the internet age. Annual Rev. Econom. 11(1):407–441.Crossref, Google Scholar
• [44] Norris JR (1998) Markov Chains (Cambridge University Press, Cambridge, MA).Google Scholar
• [45] Papadimitriou CH (2001) Algorithms, games, and the internet. Vitter JS, Spirakis P, Yannakakis M, eds. Proc. 33rd Annual ACM Sympos. Theory Comput.Google Scholar
• [46] Parise F, Ozdaglar A (2019) A variational inequality framework for network games: Existence, uniqueness, convergence and sensitivity analysis. Games Econom. Behav. 114:47–82.Crossref, Google Scholar
• [47] Rawls J (2009) A Theory of Justice, rev. ed. (Harvard University Press, Cambridge, MA).Google Scholar
• [48] Rosenthal RW (1973) A class of games possessing pure-strategy Nash equilibria. Internat. J. Game Theory 2:65–67.Crossref, Google Scholar
• [49] Schulz AS, Stier Moses N (2003) On the performance of user equilibria in traffic networks. Proc. 14th Annual ACM-SIAM Sympos. Discrete Algorithms (ACM, New York), 86–87.Google Scholar
• [50] Ventcel′ AD, Freĭdlin MI (1970) Small random perturbations of dynamical systems. Russian Math. Surveys 25(1):1–55.Crossref, Google Scholar
• [51] Vetta A (2002) Nash equilibria in competitive societies with applications to facility location, traffic routing and auctions. Proc. 43rd Sympos. Foundations Comput. Sci. (IEEE Computer Society, Washington, DC), 416–425.Google Scholar
• [52] Voorneveld M, Norde H (1997) A characterization of ordinal potential games. Games Econom. Behav. 19(2):235–242.Crossref, Google Scholar