Resource-Aware Cost-Sharing Methods for Scheduling Games

References

• Abed F, Huang CC (2012) Preemptive coordination mechanisms for unrelated machines. Epstein L, Ferragina P, eds. Algorithms—ESA 2012. Lecture Notes in Computer Science, vol. 7501 (Springer, Berlin), 12–23.Google Scholar
• Anshelevich E, Dasgupta A, Kleinberg J, Tardos E, 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
• Awerbuch B, Azar Y, Epstein A (2013) The price of routing unsplittable flow. SIAM J. Comput. 42(1):160–177.Google Scholar
• Azar Y, Fleischer L, Jain K, Mirrokni VS, Svitkina Z (2015) Optimal coordination mechanisms for unrelated machine scheduling. Oper. Res. 63(3):489–500.Link, Google Scholar
• Bhattacharya S, Im S, Kulkarni J, Munagala K (2014) Coordination mechanisms from (almost) all scheduling policies. Naor M, ed. Proc. Fifth Conf. Innovations Theoret. Comput. Sci. (Association for Computing Machinery, New York), 121–134.Google Scholar
• Bhawalkar K, Gairing M, Roughgarden T (2014) Weighted congestion games: Price of anarchy, universal worst-case examples, and tightness. ACM Trans. Econom. Comput. 2(4):14.Google Scholar
• Caragiannis I (2013) Efficient coordination mechanisms for unrelated machine scheduling. Algorithmica 66(3):512–540.Crossref, Google Scholar
• Caragiannis I, Gkatzelis V, Vinci C (2017) Coordination mechanisms, cost-sharing, and approximation algorithms for scheduling. Web and Internet Economics. Lecture Notes in Computer Science, vol. 10660 (Springer, Cham, Switzerland), 74–87.Google Scholar
• Chen HL, Roughgarden T, Valiant G (2010) Designing network protocols for good equilibria. SIAM J. Comput. 39(5):1799–1832.Crossref, Google Scholar
• Christodoulou G, Sgouritsa A (2019) Designing networks with good equilibria under uncertainty. SIAM J. Comput. 48(4):1364–1396.Crossref, Google Scholar
• Christodoulou G, Gkatzelis V, Sgouritsa A (2017) Cost-sharing methods for scheduling games under uncertainty. Daskalakis C, Babaioff M, Moulin H, eds. Proc. 2017 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 441–458.Google Scholar
• Christodoulou G, Koutsoupias E, Nanavati A (2009) Coordination mechanisms. Theoret. Comput. Sci. 410(36):3327–3336.Crossref, Google Scholar
• Christodoulou G, Leonardi S, Sgouritsa A (2016) Designing cost-sharing methods for Bayesian games. Gairing M, Savani R, eds. Algorithmic Game Theory. Lecture Notes in Computer Science, vol. 9928 (Springer, Berlin), 327–339.Crossref, Google Scholar
• Christodoulou G, Mehlhorn K, Pyrga E (2014) Improving the price of anarchy for selfish routing via coordination mechanisms. Algorithmica 69(3):619–640.Crossref, Google Scholar
• Christodoulou G, Gkatzelis V, Latifian M, Sgouritsa A (2020) Resource-aware protocols for network cost-sharing games. Biró P, Hartline J, Ostrovsky M, Procaccia AD, eds. Proc. 21st ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 81–107.Google Scholar
• Cole R, Correa JR, Gkatzelis V, Mirrokni VS, Olver N (2015) Decentralized utilitarian mechanisms for scheduling games. Games Econom. Behav. 92:306–326.Crossref, Google Scholar
• Fotakis D, Spirakis PG (2008) Cost-balancing tolls for atomic network congestion games. Internet Math. 5(4):343–363.Crossref, Google Scholar
• Gairing M, Schoppmann F (2007) Total latency in singleton congestion games. Deng X, Graham FC, eds. Internet and Network Economics. Lecture Notes in Computer Science, vol 4858 (Springer, Berlin), 381–387.Crossref, Google Scholar
• Gkatzelis V, Kollias K, Roughgarden T (2014) Optimal cost-sharing in weighted congestion games. Liu TY, Qi Q, Ye Y, eds. Web and Internet Economics. Lecture Notes in Computer Science, vol 8877 (Springer, Cham, Switzerland), 72–88.Crossref, Google Scholar
• Gkatzelis V, Kollias K, Roughgarden T (2016) Optimal cost-sharing in general resource selection games. Oper. Res. 64(6):1230–1238.Link, Google Scholar
• Gkatzelis V, Pountourakis E, Sgouritsa A (2021) Resource-aware cost-sharing mechanisms with priors. Biró P, Chawla S, Echenique F, eds. Proc. 22nd ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 541–559.Google Scholar
• Gkatzelis V, Kollias K, Sgouritsa A, Tan X (2022) Improved price of anarchy via predictions. Pennock DM, Segal I, Seuken S, eds. Proc. 23rd ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 529–557.Google Scholar
• 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
• Harks T, Klimm M (2012) On the existence of pure Nash equilibria in weighted congestion games. Math. Oper. Res. 37(3):419–436.Link, Google Scholar
• Harks T, Miller K (2011) The worst-case efficiency of cost sharing methods in resource allocation games. Oper. Res. 59(6):1491–1503.Link, Google Scholar
• Harks T, Klimm M, Möhring RH (2011) Characterizing the existence of potential functions in weighted congestion games. Theory Comput. Systems 49(1):46–70.Crossref, Google Scholar
• Harks T, Hoefer M, Huber A, Surek M (2018) Efficient black-box reductions for separable cost sharing. Chatzigiannakis I, Kaklamanis C, Marx D, Sannella D, eds. Proc. 45th Internat. Colloquium Automata, Languages, Programming. Leibniz International Proceedings in Informatics, vol. 107 (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Wadern, Germany), 154:1–154:15.Google Scholar
• Immorlica N, Li LE, Mirrokni VS, Schulz AS (2009) Coordination mechanisms for selfish scheduling. Theoret. Comput. Sci. 410(17):1589–1598.Crossref, Google Scholar
• Klimm M, Schmand D (2015) Sharing non-anonymous costs of multiple resources optimally. Paschos V, Widmayer P, eds. Algorithms and Complexity. Lecture Notes in Computer Science, vol. 9079 (Springer, Cham, Switzerland), 274–287.Crossref, Google Scholar
• Kollias K (2013) Nonpreemptive coordination mechanisms for identical machines. Theory Comput. Systems 53(3):424–440.Crossref, Google Scholar
• Kollias K, Roughgarden T (2015) Restoring pure equilibria to weighted congestion games. ACM Trans. Econom. Comput. 3(4):13–46.Google Scholar
• Koutsoupias E, Papadimitriou C (2009) Worst-case equilibria. Comput. Sci. Rev. 3(2):65–69.Crossref, Google Scholar
• Marden JR, Wierman A (2013) Distributed welfare games. Oper. Res. 61(1):155–168.Link, Google Scholar
• Milchtaich I (1996) Congestion games with player-specific payoff functions. Games Econom. Behav. 13(1):111–124.Crossref, Google Scholar
• Monderer D, Shapley LS (1996) Potential games. Games Econom. Behav. 14(1):124–143.Crossref, Google Scholar
• Mosk-Aoyama D, Roughgarden T (2009) Worst-case efficiency analysis of queueing disciplines. Albers S, Marchetti-Spaccamela A, Matias Y, Nikoletseas S, Thomas W, eds. Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 5556 (Springer, Berlin), 546–557.Crossref, Google Scholar
• Moulin H (1999) Incremental cost sharing: Characterization by coalition strategy-proofness. Social Choice Welfare 16(2):279–320.Crossref, Google Scholar
• Moulin H (2008) The price of anarchy of serial, average and incremental cost sharing. Econom. Theory 36(3):379–405.Crossref, Google Scholar
• Moulin H, Shenker SJ (2001) Strategyproof sharing of submodular costs: Budget balance vs. efficiency. Econom. Theory 18(3):511–533.Crossref, Google Scholar
• Rosenthal RW (1973) The network equilibrium problem in integers. Networks 3(1):53–59.Crossref, Google Scholar
• von Falkenhausen P, Harks T (2013) Optimal cost sharing for resource selection games. Math. Oper. Res. 38(1):184–208.Link, Google Scholar