Decentralized utilitarian mechanisms for scheduling games

Abed, 2012, Preemptive coordination mechanisms for unrelated machines, 12 Aspnes, 1997, On-line routing of virtual circuits with applications to load balancing and machine scheduling, J. ACM, 44, 486, 10.1145/258128.258201 Awerbuch, 2005, The price of routing unsplittable flow, 57 Awerbuch, 2008, Fast convergence to nearly optimal solutions in potential games, 264 Awerbuch, 2006, Tradeoffs in worst-case equilibria, Theor. Comp. Sci., 361, 200, 10.1016/j.tcs.2006.05.010 Azar, 2008, (Almost) optimal coordination mechanisms for unrelated machine scheduling, 323 Azar, 1995, The competitiveness of on-line assignments, J. Algorithms, 18, 221, 10.1006/jagm.1995.1008 Bagchi, 1984 Beckman, 1956 Borodin, 2003, (Incremental) priority algorithms, Algorithmica, 37, 295, 10.1007/s00453-003-1036-3 Bruno, 1974, Scheduling independent tasks to reduce mean finishing time, Commun. ACM, 17, 382, 10.1145/361011.361064 Caragiannis, 2012, Efficient coordination mechanisms for unrelated machine scheduling, Algorithmica, 1 Caragiannis, 2011, Tight bounds for selfish and greedy load balancing, Algorithmica, 61, 606, 10.1007/s00453-010-9427-8 Caragiannis, 2010, Taxes for linear atomic congestion games, ACM Trans. Algorithms, 7, 13, 10.1145/1868237.1868251 Chevaleyre, 2006, Issues in multiagent resource allocation, Informatica (Slovenia), 30, 3 Chien, 2011, Convergence to approximate Nash equilibria in congestion games, Games Econ. Behav., 71, 315, 10.1016/j.geb.2009.05.004 Choi, 1983, Tricks or treats with the Hilbert matrix, Amer. Math. Mon., 90, 301, 10.1080/00029890.1983.11971218 Christodoulou, 2005, The price of anarchy of finite congestion games, 67 Christodoulou, 2009, Coordination mechanisms, Theor. Comp. Sci., 410, 3327, 10.1016/j.tcs.2009.01.005 Chung, 1988, Self-organizing sequential search and Hilbert's inequalities, J. Comput. Syst. Sci., 36, 148, 10.1016/0022-0000(88)90025-6 Cole, 2006, How much can taxes help selfish routing?, J. Comput. Syst. Sci., 72, 444, 10.1016/j.jcss.2005.09.010 Cominetti, 2011, Existence and uniqueness of equilibria for flows over time, 552 Conway, 1967 Correa, 2012, Efficiency of equilibria in restricted uniform machine scheduling with total weighted completion time as social cost, Nav. Res. Logist., 59, 384, 10.1002/nav.21497 Czumaj, 2007, Tight bounds for worst-case equilibria, ACM Trans. Algorithms, 3, 1, 10.1145/1186810.1186814 Davis, 1981, Algorithms for scheduling tasks on unrelated processors, J. ACM, 28, 721, 10.1145/322276.322284 Dürr, 2009, Non-clairvoyant scheduling games, 135 Even-Dar, 2007, Convergence time to Nash equilibrium in load balancing, ACM Trans. Algorithms, 3, 10.1145/1273340.1273348 Farzad, 2008, A priority-based model of routing, Chic. J. Theor. Comput. Sci, 10.4086/cjtcs.2008.001 Finn, 1979, A linear time approximation algorithm for multiprocessor scheduling, BIT, 19, 312, 10.1007/BF01930985 Fleischer, 2004, Tolls for heterogeneous selfish users in multicommodity networks and generalized congestion games, 277 Fleischer, 2010, Preference-constrained oriented matching, 56 Foster, 1998 Gairing, 2010, Computing Nash equilibria for scheduling on restricted parallel links, Theory Comput. Syst., 47, 405, 10.1007/s00224-009-9191-9 Gonnet, 1981, Exegesis of self-organizing linear search, SIAM J. Comput., 10, 613, 10.1137/0210046 Hall, 1997, Scheduling to minimize average completion time: Off-line and on-line approximation algorithms, Math. Oper. Res., 22, 513, 10.1287/moor.22.3.513 Hartline, 2008, Optimal mechanism design and money burning, 75 Hoefer, 2011, Competitive routing over time, Theor. Comp. Sci., 412, 5420, 10.1016/j.tcs.2011.05.055 Hoeksma, 2011, The price of anarchy for minsum related machine scheduling, 261 Hoogeveen, 2001, Non-approximability results for scheduling problems with minsum criteria, INFORMS J. Comput., 13, 157, 10.1287/ijoc.13.2.157.10520 Horn, 1973, Minimizing average flow time with parallel machines, Oper. Res., 21, 846, 10.1287/opre.21.3.846 Ibarra, 1977, Heuristic algorithms for scheduling independent tasks on nonidentical processors, J. ACM, 24, 280, 10.1145/322003.322011 Immorlica, 2009, Coordination mechanisms for selfish scheduling, Theor. Comp. Sci., 410, 1589, 10.1016/j.tcs.2008.12.032 Koch, 2011, Nash equilibria and the price of anarchy for flows over time, Theory Comput. Syst., 49, 71, 10.1007/s00224-010-9299-y Korilis, 1997, Achieving network optima using Stackelberg routing strategies, IEEE/ACM Trans. Netw., 5, 161, 10.1109/90.554730 Koutsoupias, 2009, Worst-case equilibria, Comput. Sci. Rev., 3, 65, 10.1016/j.cosrev.2009.04.003 Lenstra, 1977, Complexity of machine scheduling problems, Ann. Discrete Math., 4, 281 Peterson, 2003, A blueprint for introducing disruptive technology into the internet, Comput. Commun. Rev., 33, 59, 10.1145/774763.774772 Pinedo, 2008 Roughgarden, 2004, Stackelberg scheduling strategies, SIAM J. Comput., 33, 332, 10.1137/S0097539701397059 Roughgarden, 2009, Intrinsic robustness of the price of anarchy, 513 Sahni, 1980, Bounds for list schedules on uniform processors, SIAM J. Comput., 9, 91, 10.1137/0209007 Schulz, 2002, Scheduling unrelated machines by randomized rounding, SIAM J. Discrete Math., 15, 450, 10.1137/S0895480199357078 Schuurman, 2007, Performance guarantees of local search for multiprocessor scheduling, INFORMS J. Comput., 19, 52, 10.1287/ijoc.1050.0152 Sethuraman, 1999, Optimal scheduling of multiclass parallel machines, 963 Shoham, 2008 Skutella, 2001, Convex quadratic and semidefinite programming relaxations in scheduling, J. ACM, 48, 206, 10.1145/375827.375840 Skutella, 2000, A PTAS for minimizing the total weighted completion time on identical parallel machines, Math. Oper. Res., 25, 63, 10.1287/moor.25.1.63.15212 Smith, 1956, Various optimizers for single stage production, Nav. Res. Logist. Quart., 3, 59, 10.1002/nav.3800030106 von Stackelberg, 1934 Vredeveld, 2002