Optimal Cost-Sharing in General Resource Selection Games

References

• Abed F, Huang C-C (2012) Preemptive coordination mechanisms for unrelated machines. Epstein L, Ferragina P, eds. Proc. 20th Eur. Sympos. Algorithms (Springer, Berlin), 12–23.Crossref, Google Scholar
• 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
• Awerbuch B, Azar Y, Epstein A (2005) The price of routing unsplittable flow. Gabow HN, Fagin R, ed. Proc. 37th ACM Sympos. Theory Comput., STOC ’05 (ACM, New York), 57–66.Crossref, 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. Proc. 5th Conf. Innovations Theoret. Comput. Sci., ITCS ’14 (ACM, New York), 121–134.Crossref, Google Scholar
• Bhawalkar K, Roughgarden T (2012) Simultaneous single-item auctions. Goldberg P, eds. Internet and Network Economics (Springer, Berlin), 337–349.Crossref, 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
• 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, Koutsoupias E, Nanavati A (2009) Coordination mechanisms. Theoret. Comput. Sci. 410(36):3327–3336.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
• Coffman Jr EG, Mitrani I (1980) A characterization of waiting time performance realizable by single-server queues. Oper. Res. 28(3):810–821.Link, 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
• Cominetti R, Correa JR, Stier Moses NE (2009) The impact of oligopolistic competition in networks. Oper. Res. 57(6):1421–1437.Link, 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 Chung F, eds. Internet and Network Economics (Springer, Berlin), 381–387.Crossref, Google Scholar
• Gkatzelis V, Kollias K, Roughgarden T (2014) Optimal cost-sharing in weighted congestion games. Liu T-Y, Qi Q, Ye Y, eds. Proc. 10th Internat. Conf. Web and Internet Econom., WINE ’14 (Springer International, Cham, Switzerland), 72–88.Crossref, Google Scholar
• Goemans M, Mirrokni VS, Vetta A (2005) Sink equilibria and convergence. Proc. 46th IEEE Sympos. Foundations Comput. Sci., FOCS ’05 (IEEE Computer Society, Washington, DC), 142–151.Crossref, 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, 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, Miller K (2011) The worst-case efficiency of cost sharing methods in resource allocation games. Oper. Res. 59(6):1491–1503.Link, Google Scholar
• Haviv M, Roughgarden T (2007) The price of anarchy in an exponential multi-server. Oper. Res. Lett. 35(4):421–426.Crossref, 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
• 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
• Lucier B, Borodin A (2010) Price of anarchy for greedy auctions. Charikar M, ed. Proc. Twenty-First Annual ACM-SIAM Sympos. Discrete Algorithms, SODA ’10 (SIAM, Philadelphia), 537–553.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. Proc. 36th Internat. Colloquium on Automata, Languages and Programming (Springer, Berlin), 546–557.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 versus efficiency. Econom. Theory 18(3):511–533.Crossref, Google Scholar
• Osborne MJ, Rubinstein A (1994) A Course in Game Theory (MIT Press, Cambridge, MA).Google Scholar
• Rosenthal RW (1973a) A class of games possessing pure-strategy Nash equilibria. Internat. J. Game Theory 2(1):65–67.Crossref, Google Scholar
• Rosenthal RW (1973b) The network equilibrium problem in integers. Networks 3(1):53–59.Crossref, Google Scholar
• Roughgarden T (2009) Intrinsic robustness of the price of anarchy. Mitzenmacher M, ed. Proc. 41st ACM Sympos. Theory Comput., STOC ’09 (ACM, New York), 513–522.Crossref, Google Scholar
• Roughgarden T, Tardos É (2002) How bad is selfish routing? J. ACM 49(2):236–259.Crossref, Google Scholar
• Shapley LS (1953) Additive and Non-Additive Set Functions (Princeton University, Princeton, NJ).Google Scholar
• Shenker SJ (1995) Making greed work in networks: A game-theoretic analysis of switch service disciplines. IEEE/ACM Trans. Networking 3(6):819–831.Crossref, Google Scholar
• Syrgkanis V, Tardos É (2013) Composable and efficient mechanisms. Proc. 45th ACM Sympos. Theory Comput., STOC ’13 (ACM, New York), 211–220.Crossref, Google Scholar
• von Falkenhausen P, Harks T (2013) Optimal cost sharing protocols for scheduling games. Math. Oper. Res. 38(1):184–208.Link, Google Scholar