{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T06:10:14Z","timestamp":1768889414140,"version":"3.49.0"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2011,2,17]],"date-time":"2011-02-17T00:00:00Z","timestamp":1297900800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2011,7]]},"DOI":"10.1007\/s00224-011-9316-9","type":"journal-article","created":{"date-parts":[[2011,2,16]],"date-time":"2011-02-16T15:56:11Z","timestamp":1297871771000},"page":"3-23","source":"Crossref","is-referenced-by-count":22,"title":["Non-clairvoyant Scheduling Games"],"prefix":"10.1007","volume":"49","author":[{"given":"Johanne","family":"Cohen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christoph","family":"D\u00fcrr","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thang","family":"Nguyen\u00a0Kim","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,2,17]]},"reference":[{"key":"9316_CR1","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/j.tcs.2006.07.057","volume":"369","author":"E. Angel","year":"2006","unstructured":"Angel, E., Bampis, E., Pascual, F.: Truthful algorithms for scheduling selfish tasks on parallel machines. Theor. Comput. Sci. 369, 157\u2013168 (2006)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9316_CR2","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1145\/258128.258201","volume":"44","author":"J. Aspnes","year":"1997","unstructured":"Aspnes, J., Azar, Y., Fiat, A., Plotkin, S.A., Waarts, O.: On-line routing of virtual circuits with applications to load balancing and machine scheduling. J. ACM 44(3), 486\u2013504 (1997)","journal-title":"J. ACM"},{"key":"9316_CR3","series-title":"Contributions to the Theory of Games IV, Annals of Math. Study","volume-title":"Acceptable Points in General Cooperative n-Person Games","author":"R.J. Aumann","year":"1959","unstructured":"Aumann, R.J.: Acceptable Points in General Cooperative n-Person Games. Contributions to the Theory of Games IV, Annals of Math. Study (1959)"},{"issue":"2\u20133","key":"9316_CR4","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1016\/j.tcs.2006.05.010","volume":"361","author":"B. Awerbuch","year":"2006","unstructured":"Awerbuch, B., Azar, Y., Richter, Y., Tsur, D.: Tradeoffs in worst-case equilibria. Theor. Comput. Sci. 361(2\u20133), 200\u2013209 (2006)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9316_CR5","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1006\/jagm.1995.1008","volume":"18","author":"Y. Azar","year":"1995","unstructured":"Azar, Y., Naor, J., Rom, R.: The competitiveness of on-line assignments. J. Algorithms 18(2), 221\u2013237 (1995)","journal-title":"J. Algorithms"},{"key":"9316_CR6","first-page":"323","volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Y. Azar","year":"2008","unstructured":"Azar, Y., Jain, K., Mirrokni, V.S.: (Almost) optimal coordination mechanisms for unrelated machine scheduling. In: Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 323\u2013332 (2008)"},{"key":"9316_CR7","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04550-3","volume-title":"Scheduling Algorithms","author":"P. Brucker","year":"2001","unstructured":"Brucker, P.: Scheduling Algorithms, 3rd edn. Springer, Berlin (2001)","edition":"3"},{"key":"9316_CR8","doi-asserted-by":"crossref","first-page":"815","DOI":"10.1137\/1.9781611973068.89","volume-title":"Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"I. Caragiannis","year":"2009","unstructured":"Caragiannis, I.: Efficient coordination mechanisms for unrelated machine scheduling. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 815\u2013824 (2009)"},{"key":"9316_CR9","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1137\/0209007","volume":"9","author":"Y. Cho","year":"1980","unstructured":"Cho, Y., Sahni, S.: Bounds for list schedules on uniform processors. SIAM J. Comput. 9, 91\u2013103 (1980)","journal-title":"SIAM J. Comput."},{"key":"9316_CR10","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/978-3-540-27836-8_31","volume-title":"Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP)","author":"G. Christodoulou","year":"2004","unstructured":"Christodoulou, G., Koutsoupias, E., Nanavati, A.: Coordination mechanisms. In: Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP), pp. 345\u2013357 (2004)"},{"key":"9316_CR11","first-page":"413","volume-title":"Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"A. Czumaj","year":"2002","unstructured":"Czumaj, A., V\u00f6cking, B.: Tight bounds for worst-case equilibria. In: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 413\u2013420 (2002)"},{"key":"9316_CR12","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1137\/0213044","volume":"13","author":"G. Dobson","year":"1984","unstructured":"Dobson, G.: Scheduling independent tasks on uniform processors. SIAM J. Comput. 13, 721\u2013716 (1984)","journal-title":"SIAM J. Comput."},{"key":"9316_CR13","first-page":"179","volume-title":"Proceedings of the 31st ACM Symposium on Theory of Computing (STOC)","author":"J. Edmonds","year":"1999","unstructured":"Edmonds, J.: Scheduling in the dark. In: Proceedings of the 31st ACM Symposium on Theory of Computing (STOC), pp. 179\u2013188 (1999)"},{"issue":"3","key":"9316_CR14","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1145\/1273340.1273348","volume":"3","author":"E. Even-Dar","year":"2007","unstructured":"Even-Dar, E., Kesselman, A., Mansour, Y.: Convergence time to Nash equilibrium in load balancing. ACM Trans. Algorithms 3(3), 32 (2007)","journal-title":"ACM Trans. Algorithms"},{"key":"9316_CR15","doi-asserted-by":"crossref","first-page":"608","DOI":"10.1007\/11786986_53","volume-title":"Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP)","author":"A. Fiat","year":"2006","unstructured":"Fiat, A., Kaplan, H., Levy, M., Olonetsky, S., Shabo, R.: On the price of stability for designing undirected networks with fair cost allocations. In: Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP), pp. 608\u2013618 (2006)"},{"key":"9316_CR16","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1007\/978-3-540-73420-8_51","volume-title":"Proceedings of the 34th International Colloquium on Automata, Languages and Programming","author":"A. Fiat","year":"2007","unstructured":"Fiat, A., Kaplan, H., Levy, M., Olonetsky, S.: Strong price of anarchy for machine load balancing. In: Proceedings of the 34th International Colloquium on Automata, Languages and Programming, pp.\u00a0583\u2013594 (2007)"},{"key":"9316_CR17","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1007\/BF01930985","volume":"19","author":"G. Finn","year":"1979","unstructured":"Finn, G., Horowitz, E.: A linear time approximation algorithm for multiprocessor scheduling. BIT 19, 312\u2013320 (1979)","journal-title":"BIT"},{"key":"9316_CR18","doi-asserted-by":"crossref","first-page":"554","DOI":"10.1137\/0216037","volume":"16","author":"D.K. Friesen","year":"1987","unstructured":"Friesen, D.K.: Tighter bounds for LPT scheduling on uniform processors. SIAM J. Comput. 16, 554\u2013560 (1987)","journal-title":"SIAM J. Comput."},{"key":"9316_CR19","first-page":"613","volume-title":"Proceedings of the 36th ACM Symposium on Theory of Computing (STOC)","author":"M. Gairing","year":"2004","unstructured":"Gairing, M., L\u00fccking, T., Mavronicolas, M., Monien, B.: Computing Nash equilibria for scheduling on restricted parallel links. In: Proceedings of the 36th ACM Symposium on Theory of Computing (STOC), pp. 613\u2013622 (2004)"},{"key":"9316_CR20","volume-title":"Computers and Intractability; A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1990","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness. Freeman, New York (1990)"},{"key":"9316_CR21","doi-asserted-by":"crossref","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"R.L. Graham","year":"1966","unstructured":"Graham, R.L.: Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45, 1563\u20131581 (1966)","journal-title":"Bell Syst. Tech. J."},{"key":"9316_CR22","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1137\/0117039","volume":"45","author":"R.L. Graham","year":"1969","unstructured":"Graham, R.L.: Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 45, 416\u2013429 (1969)","journal-title":"SIAM J. Appl. Math."},{"key":"9316_CR23","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1145\/322003.322011","volume":"24","author":"O.H. Ibarra","year":"1977","unstructured":"Ibarra, O.H., Kim, C.E.: Heuristic algorithms for scheduling independent tasks on nonidentical processors. J. ACM 24, 280\u2013289 (1977)","journal-title":"J. ACM"},{"key":"9316_CR24","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/11600930_7","volume-title":"Proceedings of the 1st International Workshop on Internet and Network Economics (WINE)","author":"N. Immorlica","year":"2005","unstructured":"Immorlica, N., Li, L., Mirrokni, V.S., Schulz, A.: Coordination mechanisms for selfish scheduling. In: Proceedings of the 1st International Workshop on Internet and Network Economics (WINE), pp.\u00a055\u201369 (2005)"},{"issue":"2","key":"9316_CR25","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/j.cosrev.2009.04.003","volume":"3","author":"E. Koutsoupias","year":"2009","unstructured":"Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. Comput. Sci. Rev. 3(2), 65\u201369 (2009)","journal-title":"Comput. Sci. Rev."},{"key":"9316_CR26","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1006\/game.1996.0044","volume":"14","author":"D. Monderer","year":"1996","unstructured":"Monderer, D., Shapley, L.S.: Potential games. Games Econ. Behav. 14, 124\u2013143 (1996)","journal-title":"Games Econ. Behav."},{"issue":"2","key":"9316_CR27","doi-asserted-by":"crossref","first-page":"286","DOI":"10.2307\/1969529","volume":"54","author":"J. Nash","year":"1951","unstructured":"Nash, J.: Non-cooperative games. Ann. Math. 54(2), 286\u2013295 (1951)","journal-title":"Ann. Math."},{"key":"9316_CR28","unstructured":"Nguyen Kim, T.: Pure equilibria: existence and inefficiency & online auction. PhD thesis, Ecole Polytechnique, France (2009)"},{"issue":"1","key":"9316_CR29","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1287\/ijoc.1050.0152","volume":"361","author":"P. Schuurman","year":"2007","unstructured":"Schuurman, P., Vredeveld, T.: Performance guarantees of local search for multiprocessor scheduling. INFORMS J. Comput. 361(1), 52\u201363 (2007)","journal-title":"INFORMS J. Comput."},{"key":"9316_CR30","unstructured":"Vredeveld, T.: Combinatorial approximation algorithms: guaranteed versus experimental performance. PhD thesis, Technische Universiteit Eindhoven, The Netherlands (2002)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-011-9316-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-011-9316-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-011-9316-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T07:54:22Z","timestamp":1558684462000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-011-9316-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,2,17]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,7]]}},"alternative-id":["9316"],"URL":"https:\/\/doi.org\/10.1007\/s00224-011-9316-9","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,2,17]]}}}