Fair cost-sharing methods for scheduling jobs on parallel machines

N. Andelman, Y. Azar, M. Sorani, Truthful approximation mechanisms for scheduling selfish related machines, in: 22nd Annual Symposium on Theoretical Aspects of Computer Science, 2005, pp. 69–82 Archer, 2004, Approximation and collusion in multicast cost sharing, Games and Economic Behaviour, 47, 36, 10.1016/S0899-8256(03)00176-3 A. Archer, E. Tardos, Truthful mechanisms for one-parameter agents, in: Proceedings of the 42th IEEE Symposium on Foundations of Computer Science, 2001, pp. 482–491 V. Auletta, R. De Prisco, P. Penna, G. Persiano, C. Ventre, New constructions of mechanisms with verification, in: Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, LNCS, vol. 4051, 2006, pp. 596–607 V. Auletta, R. De Prisco, P. Penna, P. Persiano, The power of verification for one-parameter agents, in: Proceedings of the 31st International Colloquium on Automata, Languages and Programming, in: LNCS, vol. 3142, 2004, pp. 171–182 L. Becchetti, J. Könemann, S. Leonardi, M. Pál, Sharing the cost more efficiently: improved approximation for multicommodity rent-or-buy, in: Proceedings of the 16th Annual ACM–SIAM Symposium on Discrete Algorithms, 2005, pp. 375–384 G. Christodoulou, E. Koutsoupias, A. Vidali, A lower bound for scheduling mechanisms, in: Proceedings of the 18th Annual ACM–SIAM Symposium on Discrete Algorithms, 2007, in press A. Czumaj, Selfish routing on the Internet, in: Handbook of Scheduling: Algorithms, Models, and Performance Analysis, 2004 (Chapter 42) N. Devanur, M. Mihail, V. Vazirani, Strategyproof cost sharing mechanisms for set cover and facility location problems, in: Proceedings of ACM Conference on Electronic Commerce, 2003, pp. 108–114 Feigenbaum, 2003, Hardness results for multicast cost sharing, Theoretical Computer Science, 304, 215, 10.1016/S0304-3975(03)00085-9 Feigenbaum, 2001, Sharing the cost of multicast transmissions, Journal of Computer and System Sciences, 63, 21, 10.1006/jcss.2001.1754 D. Fotakis, S. Kontogiannis, E. Koutsoupias, M. Mavronicolas, P. Spirakis, The structure and complexity of Nash equilibria for a selfish routing game, in: Proceedings of the 29th Int. Colloquium on Automata, Languages, and Programming, in: LNCS, vol. 2380, 2002, pp. 123–134 Friesen, 1984, Tighter bounds for the multifit processor scheduling algorithm, SIAM Journal on Computing, 13, 170, 10.1137/0213013 Friesen, 1987, Tighter bounds for LPT scheduling on uniform processors, SIAM Journal on Computing, 16, 554, 10.1137/0216037 Friesen, 1983, Bounds for multifit scheduling on uniform processors, SIAM Journal on Computing, 12, 60, 10.1137/0212004 M. Gairing, T. Lücking, B. Monien, K. Tiemann, Nash equilibria, the price of anarchy and the fully mixed Nash equilibrium conjecture, in: Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, in: LNCS, vol. 3580, 2005, pp. 51–65 Graham, 1969, Bounds on multiprocessing timing anomalies, SIAM Journal of Applied Mathematics, 17, 416, 10.1137/0117039 A. Gupta, A. Srinivasan, E. Tardos, Cost-sharing mechanisms for network design, in: Proceedings of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, vol. 3122, 2004, pp. 139–152 Hochbaum, 1987, Using dual approximation algorithms for scheduling problems: Theoretical and practical results, Journal of the ACM, 34, 144, 10.1145/7531.7535 Hochbaum, 1988, A polynomial approximation scheme for scheduling on uniform processors: Using the dual approximation approach, SIAM Journal on Computing, 17, 539, 10.1137/0217033 N. Immorlica, M. Mahdian, V. Mirrokni, Limitations of cross-monotonic cost sharing schemes, in: Proceedings of the 16th Annual ACM–SIAM Symposium on Discrete Algorithms, 2005, pp. 602–611 K. Jain, V. Vazirani, Applications of approximate algorithms to cooperative games, in: Proceedings of the 33th Annual ACM Symposium on Theory of Computing, 2001, pp. 364–372 K. Kent, D. Skorin-Kapov, Population monotonic cost allocation on msts, in: Operational Research Proceedings KOI, 1996, pp. 43–48 J. Könemann, S. Leonardi, G. Schäfer, A group-strategyproof mechanism for steiner forests, in: Proceedings of the 16th Annual ACM–SIAM Symposium on Discrete Algorithms, 2005, pp. 612–619 J. Könemann, S. Leonardi, G. Schäfer, S. van Zwam, From primal-dual to cost shares and back: A stronger LP relaxation for the steiner forest problem, in: Proceedings of the 32th Int. Colloquium on Automata, Languages, and Programming, 2005, pp. 930–942 S. Leonardi, G. Schäfer, Cross-monotonic cost-sharing methods for connected facility location games, in: ACM Conference on Electronic Commerce, 2004, pp. 224–243 Moulin, 1999, Incremental cost sharing: Characterization by coalition strategy-proofness, Social Choice and Welfare, 16, 279, 10.1007/s003550050145 Nisan, 2001, Algorithmic mechanism design, Games and Economic Behaviour, 35, 166, 10.1006/game.1999.0790 M. Pál, E. Tardos, Group strategyproof mechanisms via primal-dual algorithms, in: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, 2003, pp. 584–593 P. Penna, C. Ventre, More powerful and simpler cost-sharing methods, in: Proceedings of the Second Workshop on Approximation and Online Algorithms, LNCS, vol. 3351, 2005, pp. 97–110 P. Penna, C. Ventre, The algorithmic structure of group strategyproof budget-balanced cost-sharing mechanisms, in: Proceedings of the 23rd International Symposium on Theoretical Aspects of Computer Science, 2006, pp. 337–348 Shapley, 1967, On balanced sets and cores, Naval Research Logistics Quarterly, 14, 453, 10.1002/nav.3800140404