{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T22:34:57Z","timestamp":1781908497006,"version":"3.54.5"},"reference-count":102,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2018,2,27]],"date-time":"2018-02-27T00:00:00Z","timestamp":1519689600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["PE 514\/22-1"],"award-info":[{"award-number":["PE 514\/22-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["OR Spectrum"],"published-print":{"date-parts":[[2018,7]]},"DOI":"10.1007\/s00291-018-0512-8","type":"journal-article","created":{"date-parts":[[2018,2,27]],"date-time":"2018-02-27T10:18:29Z","timestamp":1519726709000},"page":"583-611","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":20,"title":["Mechanism design for machine scheduling problems: classification and literature overview"],"prefix":"10.1007","volume":"40","author":[{"given":"Dominik","family":"Kress","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sebastian","family":"Meiswinkel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Erwin","family":"Pesch","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2018,2,27]]},"reference":[{"issue":"3","key":"512_CR1","doi-asserted-by":"publisher","first-page":"985","DOI":"10.1016\/j.ejor.2006.06.060","volume":"187","author":"A Allahverdi","year":"2008","unstructured":"Allahverdi A, Ng CT, Cheng TCE, Kovalyov MY (2008) A survey of scheduling problems with setup times or costs. Eur J Oper Res 187(3):985\u20131032","journal-title":"Eur J Oper Res"},{"key":"512_CR2","doi-asserted-by":"crossref","unstructured":"Ambrosio P, Auletta V (2005) Deterministic monotone algorithms for scheduling on related machines. In: Persiano G, Solis-Oba R (eds) Approximation and online algorithms, 2nd international workshop, WAOA 2004, revised selected papers, Springer, Berlin, pp 267\u2013280","DOI":"10.1007\/978-3-540-31833-0_22"},{"issue":"3","key":"512_CR3","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/j.tcs.2008.06.050","volume":"406","author":"P Ambrosio","year":"2008","unstructured":"Ambrosio P, Auletta V (2008) Deterministic monotone algorithms for scheduling on related machines. Theor Comput Sci 406(3):173\u2013186","journal-title":"Theor Comput Sci"},{"key":"512_CR4","doi-asserted-by":"crossref","unstructured":"Andelman N, Azar Y, Sorani M (2005) Truthful approximation mechanisms for scheduling selfish related machines. In: Diekert V, Durand B (eds) STACS 2005, 22nd annual symposium on theoretical aspects of computer science, Springer, Berlin, pp 69\u201382","DOI":"10.1007\/978-3-540-31856-9_6"},{"issue":"4","key":"512_CR5","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1007\/s00224-006-1316-9","volume":"40","author":"N Andelman","year":"2007","unstructured":"Andelman N, Azar Y, Sorani M (2007) Truthful approximation mechanisms for scheduling selfish related machines. Theor Comput Syst 40(4):423\u2013436","journal-title":"Theor Comput Syst"},{"key":"512_CR6","doi-asserted-by":"crossref","unstructured":"Angel E, Bampis E, Pascual F (2005) Truthful algorithms for scheduling selfish tasks on parallel machines. In: Deng X, Ye Y (eds) Internet and network economics, first international workshop, WINE 2005, proceedings, Springer, Berlin","DOI":"10.1007\/11600930_70"},{"issue":"1\u20133","key":"512_CR7","doi-asserted-by":"publisher","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 (2006) Truthful algorithms for scheduling selfish tasks on parallel machines. Theor Comput Sci 369(1\u20133):157\u2013168","journal-title":"Theor Comput Sci"},{"issue":"5","key":"512_CR8","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/s10951-009-0118-8","volume":"12","author":"E Angel","year":"2009","unstructured":"Angel E, Bampis E, Pascual F, Tchetgnia AA (2009) On truthfulness and approximation for scheduling selfish tasks. J Sched 12(5):437\u2013445","journal-title":"J Sched"},{"key":"512_CR9","doi-asserted-by":"crossref","unstructured":"Angel E, Bampis E, Thibault N (2010) Randomized truthful algorithms for scheduling selfish tasks on parallel machines. In: L\u00f3pez-Ortiz A (ed) LATIN 2010: theoretical informatics, 9th latin american symposium, proceedings, Springer, Berlin","DOI":"10.1007\/978-3-642-12200-2_5"},{"issue":"1","key":"512_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2011.10.006","volume":"414","author":"E Angel","year":"2012","unstructured":"Angel E, Bampis E, Thibault N (2012) Randomized truthful algorithms for scheduling selfish tasks on parallel machines. Theor Comput Sci 414(1):1\u20138","journal-title":"Theor Comput Sci"},{"key":"512_CR11","unstructured":"Archer A (2004) Mechanisms for discrete optimization with rational agents. PhD thesis, Cornell University"},{"key":"512_CR12","doi-asserted-by":"crossref","unstructured":"Archer A, Tardos \u00c9 (2001) Truthful mechanisms for one-parameter agents. In: Proceedings of the 42nd IEEE symposium on foundations of computer science, IEEE, FOCS \u201901, pp 482\u2013491","DOI":"10.1109\/SFCS.2001.959924"},{"key":"512_CR13","doi-asserted-by":"crossref","unstructured":"Ashlagi I, Dobzinski S, Lavi R (2009) An optimal lower bound for anonymous scheduling mechanisms. In: Proceedings of the 10th ACM conference on electronic commerce, ACM, EC \u201909, pp 169\u2013176","DOI":"10.1145\/1566374.1566399"},{"issue":"2","key":"512_CR14","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1287\/moor.1110.0534","volume":"37","author":"I Ashlagi","year":"2012","unstructured":"Ashlagi I, Dobzinski S, Lavi R (2012) Optimal lower bounds for anonymous scheduling mechanisms. Math Oper Res 37(2):244\u2013258","journal-title":"Math Oper Res"},{"key":"512_CR15","doi-asserted-by":"crossref","unstructured":"Auletta V, De\u00a0Prisco R, Penna P, Persiano G (2004) Deterministic truthful approximation mechanisms for scheduling related machines. In: Diekert V, Habib M (eds) STACS 2004, 21st annual symposium on theoretical aspects of computer science, proceedings, Springer, Berlin, pp 608\u2013619","DOI":"10.1007\/978-3-540-24749-4_53"},{"key":"512_CR16","doi-asserted-by":"crossref","unstructured":"Auletta V, Christodoulou G, Penna P (2012) Mechanisms for scheduling with single-bit private values. In: Serna M (ed) Algorithmic game theory, 5th international symposium, SAGT 2012, proceedings, Springer, Berlin, pp 25\u201336","DOI":"10.1007\/978-3-642-33996-7_3"},{"issue":"3","key":"512_CR17","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1007\/s00224-015-9625-5","volume":"57","author":"V Auletta","year":"2015","unstructured":"Auletta V, Christodoulou G, Penna P (2015) Mechanisms for scheduling with single-bit private values. Theor Comput Syst 57(3):523\u2013548","journal-title":"Theor Comput Syst"},{"key":"512_CR18","doi-asserted-by":"crossref","unstructured":"Azar Y, Hoefer M, Maor I, Reiffenh\u00e4user R, V\u00f6cking B (2015) Truthful mechanism design via correlated tree rounding. In: Proceedings of the 16th ACM conference on economics and computation, ACM, EC \u201915, pp 415\u2013432","DOI":"10.1145\/2764468.2764503"},{"issue":"1\u20132","key":"512_CR19","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1007\/s10107-016-1068-5","volume":"163","author":"Y Azar","year":"2017","unstructured":"Azar Y, Hoefer M, Maor I, Reiffenh\u00e4user R, V\u00f6cking B (2017) Truthful mechanism design via correlated tree rounding. Math Program 163(1\u20132):445\u2013469","journal-title":"Math Program"},{"key":"512_CR20","volume-title":"Handbook on scheduling: from theory to applications","author":"J B\u0142a\u017cewicz","year":"2007","unstructured":"B\u0142a\u017cewicz J, Ecker KH, Pesch E, Schmidt G, W\u0119glarz J (2007) Handbook on scheduling: from theory to applications. Springer, Berlin"},{"issue":"6","key":"512_CR21","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1016\/j.omega.2009.10.008","volume":"38","author":"N Boysen","year":"2010","unstructured":"Boysen N, Fliedner M (2010) Cross dock scheduling: classification, literature review and research agenda. Omega 38(6):413\u2013422","journal-title":"Omega"},{"issue":"2","key":"512_CR22","doi-asserted-by":"publisher","first-page":"674","DOI":"10.1016\/j.ejor.2006.10.010","volume":"183","author":"N Boysen","year":"2007","unstructured":"Boysen N, Fliedner M, Scholl A (2007) A classification of assembly line balancing problems. Eur J Oper Res 183(2):674\u2013693","journal-title":"Eur J Oper Res"},{"issue":"2","key":"512_CR23","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1016\/j.ejor.2007.09.013","volume":"192","author":"N Boysen","year":"2009","unstructured":"Boysen N, Fliedner M, Scholl A (2009) Sequencing mixed-model assembly lines: survey, classification and model critique. Eur J Oper Res 192(2):349\u2013373","journal-title":"Eur J Oper Res"},{"issue":"1","key":"512_CR24","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0377-2217(98)00204-5","volume":"112","author":"P Brucker","year":"1999","unstructured":"Brucker P, Drexl A, M\u00f6hring R, Neumann K, Pesch E (1999) Resource-constrained project scheduling: notation, classification, models, and methods. Eur J Oper Res 112(1):3\u201341","journal-title":"Eur J Oper Res"},{"key":"512_CR25","doi-asserted-by":"crossref","unstructured":"Chawla S, Hartline JD, Malec D, Sivan B (2013) Prior-independent mechanisms for scheduling. In: Proceedings of the 45th annual ACM symposium on theory of computing, ACM, STOC \u201913, pp 51\u201360","DOI":"10.1145\/2488608.2488616"},{"key":"512_CR26","doi-asserted-by":"crossref","unstructured":"Chen X, Du D, Zuluaga LF (2013) Copula-based randomized mechanisms for truthful scheduling on two unrelated machines. In: V\u00f6cking B (ed) Algorithmic game theory, 6th international symposium, SAGT 2013, proceedings, Springer, Berlin, pp 231\u2013242","DOI":"10.1007\/978-3-642-41392-6_20"},{"issue":"3","key":"512_CR27","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1007\/s00224-014-9601-5","volume":"57","author":"X Chen","year":"2015","unstructured":"Chen X, Du D, Zuluaga LF (2015) Copula-based randomized mechanisms for truthful scheduling on two unrelated machines. Theor Comput Syst 57(3):753\u2013781","journal-title":"Theor Comput Syst"},{"key":"512_CR28","first-page":"40","volume":"97","author":"G Christodoulou","year":"2009","unstructured":"Christodoulou G, Koutsoupias E (2009) Mechanism design for scheduling. Bull EATCS 97:40\u201359","journal-title":"Bull EATCS"},{"key":"512_CR29","doi-asserted-by":"crossref","unstructured":"Christodoulou G, Kov\u00e1cs A (2010) A deterministic truthful PTAS for scheduling related machines. In: Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, SIAM, SODA \u201910, pp 1005\u20131016","DOI":"10.1137\/1.9781611973075.81"},{"key":"512_CR30","doi-asserted-by":"crossref","unstructured":"Christodoulou G, Kov\u00e1cs A (2011) A global characterization of envy-free truthful scheduling of two tasks. In: Chen N, Elkind E, Koutsoupias E (eds) Internet and network economics, 7th international workshop, WINE 2011, proceedings, Springer, Berlin, pp 84\u201396","DOI":"10.1007\/978-3-642-25510-6_8"},{"issue":"4","key":"512_CR31","doi-asserted-by":"publisher","first-page":"1572","DOI":"10.1137\/120866038","volume":"42","author":"G Christodoulou","year":"2013","unstructured":"Christodoulou G, Kov\u00e1cs A (2013) A deterministic truthful PTAS for scheduling related machines. SIAM J Comput 42(4):1572\u20131595","journal-title":"SIAM J Comput"},{"key":"512_CR32","doi-asserted-by":"crossref","unstructured":"Christodoulou G, Gourv\u00e8s L, Pascual F (2007a) Scheduling selfish tasks: about the performance of truthful algorithms. In: Lin G (ed) Computing and combinatorics, 13th annual international conference, COCOON 2007, proceedings, Springer, Berlin, pp 187\u2013197","DOI":"10.1007\/978-3-540-73545-8_20"},{"key":"512_CR33","doi-asserted-by":"crossref","unstructured":"Christodoulou G, Koutsoupias E, Kov\u00e1cs A (2007b) Mechanism design for fractional scheduling on unrelated machines. In: Arge L, Cachin C, Jurdzi\u0144ski T, Tarlecki A (eds) Automata, languages and programming, 34th international colloquium, ICALP 2007, proceedings, Springer, Berlin, pp 40\u201352","DOI":"10.1007\/978-3-540-73420-8_6"},{"key":"512_CR34","unstructured":"Christodoulou G, Koutsoupias E, Vidali A (2007c) A lower bound for scheduling mechanisms. In: Proceedings of the 18th annual ACM-SIAM symposium on discrete algorithms, ACM, SODA \u201907, pp 1163\u20131170"},{"key":"512_CR35","doi-asserted-by":"crossref","unstructured":"Christodoulou G, Koutsoupias E, Vidali A (2008) A characterization of 2-player mechanisms for scheduling. In: Halperin D, Mehlhorn K (eds) Algorithms\u2014ESA 2008, 16th annual European symposium, proceedings, Springer, Berlin, pp 297\u2013307","DOI":"10.1007\/978-3-540-87744-8_25"},{"issue":"36","key":"512_CR36","doi-asserted-by":"publisher","first-page":"3327","DOI":"10.1016\/j.tcs.2009.01.005","volume":"410","author":"G Christodoulou","year":"2009","unstructured":"Christodoulou G, Koutsoupias E, Nanavati A (2009a) Coordination mechanisms. Theor Comput Sci 410(36):3327\u20133336","journal-title":"Theor Comput Sci"},{"issue":"4","key":"512_CR37","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1007\/s00453-008-9165-3","volume":"55","author":"G Christodoulou","year":"2009","unstructured":"Christodoulou G, Koutsoupias E, Vidali A (2009b) A lower bound for scheduling mechanisms. Algorithmica 55(4):729\u2013740","journal-title":"Algorithmica"},{"issue":"2","key":"512_CR38","doi-asserted-by":"publisher","first-page":"38:1","DOI":"10.1145\/1721837.1721854","volume":"6","author":"G Christodoulou","year":"2010","unstructured":"Christodoulou G, Koutsoupias E, Kov\u00e1cs A (2010) Mechanism design for fractional scheduling on unrelated machines. ACM Trans Algorithms 6(2):38:1\u201338:18","journal-title":"ACM Trans Algorithms"},{"issue":"1","key":"512_CR39","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/BF01726210","volume":"11","author":"EH Clarke","year":"1971","unstructured":"Clarke EH (1971) Multipart pricing of public goods. Public Choice 11(1):17\u201333","journal-title":"Public Choice"},{"key":"512_CR40","doi-asserted-by":"crossref","unstructured":"Daskalakis C, Weinberg SM (2015) Bayesian truthful mechanisms for job scheduling from bi-criterion approximation algorithms. In: Proceedings of the 26th annual ACM-SIAM symposium on discrete algorithms, ACM, SODA \u201915, pp 1934\u20131952","DOI":"10.1137\/1.9781611973730.130"},{"issue":"2","key":"512_CR41","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/s00199-016-0983-2","volume":"64","author":"P De","year":"2017","unstructured":"De P, Mitra M (2017) Incentives and justice for sequencing problems. Econ Theory 64(2):239\u2013264","journal-title":"Econ Theory"},{"key":"512_CR42","doi-asserted-by":"crossref","unstructured":"Dhangwatnotai P, Dobzinski S, Dughmi S, Roughgarden T (2008) Truthful approximation schemes for single-parameter agents. In: Proceedings of the 49th annual IEEE symposium on foundations of computer science, IEEE, FOCS \u201908, pp 15\u201324","DOI":"10.1109\/FOCS.2008.71"},{"issue":"3","key":"512_CR43","doi-asserted-by":"publisher","first-page":"915","DOI":"10.1137\/080744992","volume":"40","author":"P Dhangwatnotai","year":"2011","unstructured":"Dhangwatnotai P, Dobzinski S, Dughmi S, Roughgarden T (2011) Truthful approximation schemes for single-parameter agents. SIAM J Comput 40(3):915\u2013933","journal-title":"SIAM J Comput"},{"issue":"6","key":"512_CR44","doi-asserted-by":"publisher","first-page":"2287","DOI":"10.1137\/090780146","volume":"42","author":"S Dobzinski","year":"2013","unstructured":"Dobzinski S, Dughmi S (2013) On the power of randomization in algorithmic mechanism design. SIAM J Comput 42(6):2287\u20132304","journal-title":"SIAM J Comput"},{"key":"512_CR45","doi-asserted-by":"crossref","unstructured":"Dobzinski S, Sundararajan M (2008) On characterizations of truthful mechanisms for combinatorial auctions and scheduling. In: Proceedings of the 9th ACM conference on electronic commerce, ACM, EC \u201908, pp 38\u201347","DOI":"10.1145\/1386790.1386798"},{"issue":"1","key":"512_CR46","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/s10951-014-0378-9","volume":"18","author":"J Duives","year":"2015","unstructured":"Duives J, Heydenreich B, Mishra D, M\u00fcller R, Uetz M (2015) On optimal mechanism design for a sequencing problem. J Sched 18(1):45\u201359","journal-title":"J Sched"},{"key":"512_CR47","doi-asserted-by":"crossref","unstructured":"Epstein L, van Stee R (2008) Maximizing the minimum load for selfish agents. In: Laber ES, Bornstein C, Nogueira LT, Faria L (eds) LATIN 2008: theoretical informatics, 8th latin american symposium, proceedings, Springer, Berlin, pp 264\u2013275","DOI":"10.1007\/978-3-540-78773-0_23"},{"issue":"1","key":"512_CR48","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1016\/j.tcs.2009.08.032","volume":"411","author":"L Epstein","year":"2010","unstructured":"Epstein L, van Stee R (2010) Maximizing the minimum load for selfish agents. Theor Comput Sci 411(1):44\u201357","journal-title":"Theor Comput Sci"},{"key":"512_CR49","doi-asserted-by":"crossref","unstructured":"Epstein L, Levin A, van Stee R (2013) A unified approach to truthful scheduling on related machines. In: Proceedings of the 24th annual ACM-SIAM symposium on discrete algorithms, ACM, SODA \u201913, pp 1243\u20131252","DOI":"10.1137\/1.9781611973105.90"},{"issue":"1","key":"512_CR50","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1287\/moor.2015.0730","volume":"41","author":"L Epstein","year":"2015","unstructured":"Epstein L, Levin A, van Stee R (2015) A unified approach to truthful scheduling on related machines. Math Oper Res 41(1):332\u2013351","journal-title":"Math Oper Res"},{"issue":"8","key":"512_CR51","doi-asserted-by":"publisher","first-page":"886","DOI":"10.1016\/j.tcs.2008.12.024","volume":"410","author":"A Ferrante","year":"2009","unstructured":"Ferrante A, Parlato G, Sorrentino F, Ventre C (2009) Fast payment schemes for truthful mechanisms with verification. Theor Comput Sci 410(8):886\u2013899","journal-title":"Theor Comput Sci"},{"key":"512_CR52","volume-title":"Game theory","author":"D Fudenberg","year":"1991","unstructured":"Fudenberg D, Tirole J (1991) Game theory. MIT Press, Cambridge"},{"key":"512_CR53","doi-asserted-by":"crossref","unstructured":"Giannakopoulos Y, Kyropoulou M (2015) The VCG mechanism for Bayesian scheduling. In: Markakis E, Sch\u00e4fer G (eds) Web and internet economics, 11th international conference, WINE 2015, proceedings, Springer, Berlin, pp 343\u2013356","DOI":"10.1007\/978-3-662-48995-6_25"},{"key":"512_CR54","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"RL Graham","year":"1979","unstructured":"Graham RL, Lawler EL, Lenstra JK, Rinnooy Kan AHG (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discrete Math 5:287\u2013326","journal-title":"Ann Discrete Math"},{"issue":"4","key":"512_CR55","doi-asserted-by":"publisher","first-page":"617","DOI":"10.2307\/1914085","volume":"41","author":"T Groves","year":"1973","unstructured":"Groves T (1973) Incentives in teams. Econometrica 41(4):617\u2013631","journal-title":"Econometrica"},{"issue":"2","key":"512_CR56","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1016\/j.geb.2003.09.005","volume":"48","author":"R Hain","year":"2004","unstructured":"Hain R, Mitra M (2004) Simple sequencing problems with interdependent costs. Game Econ Behav 48(2):271\u2013291","journal-title":"Game Econ Behav"},{"issue":"3","key":"512_CR57","doi-asserted-by":"publisher","first-page":"678","DOI":"10.1016\/S0377-2217(98)00355-5","volume":"119","author":"H Hamers","year":"1999","unstructured":"Hamers H, Klijn F, Suijs J (1999) On the balancedness of multiple machine sequencing games. Eur J Oper Res 119(3):678\u2013691","journal-title":"Eur J Oper Res"},{"issue":"1","key":"512_CR58","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1007\/s00224-011-9315-x","volume":"49","author":"T Harks","year":"2011","unstructured":"Harks T, Klimm M, M\u00f6hring RH (2011) Characterizing the existence of potential functions in weighted congestion games. Theor Comput Syst 49(1):46\u201370","journal-title":"Theor Comput Syst"},{"key":"512_CR59","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1017\/CBO9780511800481.015","volume-title":"Algorithmic game theory","author":"JD Hartline","year":"2007","unstructured":"Hartline JD, Karlin AR (2007) Profit maximization in mechanism design. In: Nisan N, Roughgarden T, Tardos E, Vazirani VV (eds) Algorithmic game theory. Cambridge University Press, Cambridge, pp 331\u2013361"},{"issue":"3","key":"512_CR60","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1007\/s00355-011-0540-7","volume":"38","author":"K Hashimoto","year":"2012","unstructured":"Hashimoto K, Saitoh H (2012) Strategy-proof and anonymous rule in queueing problems: a relationship between equity and efficiency. Soc Choice Welf 38(3):473\u2013480","journal-title":"Soc Choice Welf"},{"issue":"4","key":"512_CR61","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1111\/j.1937-5956.2007.tb00271.x","volume":"16","author":"B Heydenreich","year":"2007","unstructured":"Heydenreich B, M\u00fcller R, Uetz M (2007) Games and mechanism design in machine scheduling\u2014an introduction. Prod Oper Manag 16(4):437\u2013454","journal-title":"Prod Oper Manag"},{"key":"512_CR62","doi-asserted-by":"crossref","unstructured":"Heydenreich B, Mishra D, M\u00fcller R, Uetz M (2008) Optimal mechanisms for single machine scheduling. In: Papadimitriou C, Zhang S (eds) Internet and network economics, 4th international workshop, WINE 2008, proceedings, Springer, Berlin, pp 414\u2013425","DOI":"10.1007\/978-3-540-92185-1_47"},{"key":"512_CR63","doi-asserted-by":"crossref","unstructured":"Hoeksma R, Uetz M (2013) Two dimensional optimal mechanism design for a sequencing problem. In: Goemans M, Correa J (eds) Integer programming and combinatorial optimization, 16th international conference, IPCO 2013, proceedings, Springer, Berlin, pp 242\u2013253","DOI":"10.1007\/978-3-642-36694-9_21"},{"issue":"17","key":"512_CR64","doi-asserted-by":"publisher","first-page":"1589","DOI":"10.1016\/j.tcs.2008.12.032","volume":"410","author":"N Immorlica","year":"2009","unstructured":"Immorlica N, Li EL, Mirrokni VS, Schulz AS (2009) Coordination mechanisms for selfish scheduling. Theor Comput Sci 410(17):1589\u20131598","journal-title":"Theor Comput Sci"},{"issue":"1","key":"512_CR65","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/j.geb.2009.07.003","volume":"68","author":"\u00c7 Kay\u0131","year":"2010","unstructured":"Kay\u0131 \u00c7, Ramaekers E (2010) Characterizations of Pareto-efficient, fair, and strategy-proof allocation rules in queueing problems. Game Econ Behav 68(1):220\u2013232","journal-title":"Game Econ Behav"},{"key":"512_CR66","doi-asserted-by":"publisher","unstructured":"Kay\u0131 \u00c7, Ramaekers E (2015) Corrigendum to characterizations of Pareto-efficient, fair, and strategy-proof allocation rules in queueing problems [Games Econ Behav 68(1) (2010) 220\u2013232]. Game Econ Behav https:\/\/doi.org\/10.1016\/j.geb.2015.01.006","DOI":"10.1016\/j.geb.2015.01.006"},{"key":"512_CR67","doi-asserted-by":"crossref","unstructured":"Koutsoupias E (2011) Scheduling without payments. In: Persiano G (ed) Algorithmic game theory, 4th international symposium, SAGT 2011, proceedings, Springer, Berlin, pp 143\u2013153","DOI":"10.1007\/978-3-642-24829-0_14"},{"issue":"3","key":"512_CR68","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/s00224-013-9473-0","volume":"54","author":"E Koutsoupias","year":"2014","unstructured":"Koutsoupias E (2014) Scheduling without payments. Theor Comput Syst 54(3):375\u2013387","journal-title":"Theor Comput Syst"},{"key":"512_CR69","unstructured":"Koutsoupias E, Vidali A (2007) A lower bound of 1+ $$\\varphi $$ \u03c6 for truthful scheduling mechanisms. In: Ku\u010dera L, Ku\u010dera A (eds) Mathematical foundations of computer science 2007, 32nd international symposium, MFCS 2007, proceedings, Springer, Berlin, pp 454\u2013464"},{"issue":"1","key":"512_CR70","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/s00453-012-9634-6","volume":"66","author":"E Koutsoupias","year":"2013","unstructured":"Koutsoupias E, Vidali A (2013) A lower bound of $$1+ \\varphi $$ 1 + \u03c6 for truthful scheduling mechanisms. Algorithmica 66(1):211\u2013223","journal-title":"Algorithmica"},{"key":"512_CR71","doi-asserted-by":"crossref","unstructured":"Kov\u00e1cs A (2005) Fast monotone 3-approximation algorithm for scheduling related machines. In: Brodal GS, Leonardi S (eds) Algorithms\u2014ESA 2005, 13th annual European symposium, proceedings, Springer, Berlin, pp 616\u2013627","DOI":"10.1007\/11561071_55"},{"key":"512_CR72","doi-asserted-by":"crossref","unstructured":"Kov\u00e1cs A (2006) Tighter approximation bounds for LPT scheduling in two special cases. In: Calamoneri T, Finocchi I, Italiano GF (eds) Algorithms and complexity, 6th Italian conference, CIAC 2006, proceedings, Springer, Berlin, pp 187\u2013198","DOI":"10.1007\/11758471_20"},{"issue":"3","key":"512_CR73","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/j.jda.2008.11.004","volume":"7","author":"A Kov\u00e1cs","year":"2009","unstructured":"Kov\u00e1cs A (2009) Tighter approximation bounds for LPT scheduling in two special cases. J Discrete Algorithms 7(3):327\u2013340","journal-title":"J Discrete Algorithms"},{"key":"512_CR74","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1016\/j.omega.2013.11.001","volume":"44","author":"MY Kovalyov","year":"2014","unstructured":"Kovalyov MY, Pesch E (2014) A game mechanism for single machine sequencing with zero risk. Omega 44:104\u2013110","journal-title":"Omega"},{"key":"512_CR75","unstructured":"Kovalyov MY, Kress D, Meiswinkel S, Pesch E (2016) A parallel machine schedule updating game with compensations and zero risk. Working Paper, National Academy of Sciences of Belarus and University of Siegen"},{"key":"512_CR76","doi-asserted-by":"publisher","unstructured":"Kress D, Meiswinkel S, Pesch E (2017) Incentive compatible mechanisms for scheduling two-parameter job agents on parallel identical machines to minimize the weighted number of late jobs. Discrete Appl Math. https:\/\/doi.org\/10.1016\/j.dam.2017.08.026","DOI":"10.1016\/j.dam.2017.08.026"},{"key":"512_CR77","volume-title":"Auction theory","author":"V Krishna","year":"2010","unstructured":"Krishna V (2010) Auction theory, 2nd edn. Academic Press, Amsterdam","edition":"2"},{"key":"512_CR78","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1017\/CBO9780511800481.014","volume-title":"Algorithmic game theory","author":"R Lavi","year":"2007","unstructured":"Lavi R (2007) Computationally efficient approximation mechanisms. In: Nisan N, Roughgarden T, Tardos E, Vazirani VV (eds) Algorithmic game theory. Cambridge University Press, Cambridge, pp 301\u2013329"},{"key":"512_CR79","doi-asserted-by":"crossref","unstructured":"Lavi R, Swamy C (2007) Truthful mechanism design for multidimensional scheduling via cycle monotonicity. In: Proceedings of the 8th ACM conference on electronic commerce, ACM, EC \u201907, pp 252\u2013261","DOI":"10.1145\/1250910.1250947"},{"issue":"1","key":"512_CR80","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/j.geb.2008.08.001","volume":"67","author":"R Lavi","year":"2009","unstructured":"Lavi R, Swamy C (2009) Truthful mechanism design for multidimensional scheduling via cycle monotonicity. Game Econ Behav 67(1):99\u2013124","journal-title":"Game Econ Behav"},{"key":"512_CR81","volume-title":"Handbook of scheduling: algorithms, models, and performance analysis","year":"2004","unstructured":"Leung JYT (ed) (2004) Handbook of scheduling: algorithms, models, and performance analysis. CRC Press, Boca Raton"},{"issue":"2","key":"512_CR82","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/j.ijpe.2008.09.003","volume":"116","author":"JYT Leung","year":"2008","unstructured":"Leung JYT, Li CL (2008) Scheduling with processing set restrictions: a survey. Int J Prod Econ 116(2):251\u2013262","journal-title":"Int J Prod Econ"},{"key":"512_CR83","unstructured":"Lu P, Yu C (2008a) An improved randomized truthful mechanism for scheduling unrelated machines. In: Proceedings of the 25th international symposium on theoretical aspects of computer science, IBFI Schloss Dagstuhl, STACS \u201908, pp 527\u2013538"},{"key":"512_CR84","doi-asserted-by":"crossref","unstructured":"Lu P, Yu C (2008b) Randomized truthful mechanisms for scheduling unrelated machines. In: Papadimitriou C, Zhang S (eds) Internet and network economics, 4th international workshop, WINE 2008, proceedings, Springer, pp 402\u2013413","DOI":"10.1007\/978-3-540-92185-1_46"},{"issue":"2","key":"512_CR85","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/PL00004107","volume":"17","author":"M Mitra","year":"2001","unstructured":"Mitra M (2001) Mechanism design in queueing problems. Econ Theory 17(2):277\u2013305","journal-title":"Econ Theory"},{"issue":"1","key":"512_CR86","first-page":"75","volume":"7","author":"M Mitra","year":"2002","unstructured":"Mitra M (2002) Achieving the first best in sequencing problems. Rev Econ Des 7(1):75\u201391","journal-title":"Rev Econ Des"},{"issue":"1","key":"512_CR87","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/j.ejor.2003.10.050","volume":"165","author":"M Mitra","year":"2005","unstructured":"Mitra M (2005) Incomplete information and multiple machine queueing problems. Eur J Oper Res 165(1):251\u2013266","journal-title":"Eur J Oper Res"},{"key":"512_CR88","unstructured":"Mu\u2019alem A, Schapira M (2007) Setting lower bounds on truthfulness: extended abstract. In: Proceedings of the 18th annual ACM-SIAM symposium on discrete algorithms, ACM, SODA \u201907, pp 1143\u20131152"},{"key":"512_CR89","doi-asserted-by":"crossref","unstructured":"Mu\u2019alem A, Schapira M (2017) Setting lower bounds on truthfulness. Working Paper","DOI":"10.1016\/j.geb.2018.02.001"},{"key":"512_CR90","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1017\/CBO9780511800481.011","volume-title":"Algorithmic game theory","author":"N Nisan","year":"2007","unstructured":"Nisan N (2007) Introduction to mechanism design (for computer scientists). In: Nisan N, Roughgarden T, Tardos E, Vazirani VV (eds) Algorithmic game theory. Cambridge University Press, Cambridge, pp 209\u2013241"},{"key":"512_CR91","doi-asserted-by":"crossref","unstructured":"Nisan N, Ronen A (1999) Algorithmic mechanism design (extended abstract). In: Proceedings of the 31st annual ACM symposium on theory of computing, ACM, STOC \u201999, pp 129\u2013140","DOI":"10.1145\/301250.301287"},{"issue":"1\u20132","key":"512_CR92","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1006\/game.1999.0790","volume":"35","author":"N Nisan","year":"2001","unstructured":"Nisan N, Ronen A (2001) Algorithmic mechanism design. Game Econ Behav 35(1\u20132):166\u2013196","journal-title":"Game Econ Behav"},{"key":"512_CR93","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511800481","volume-title":"Algorithmic game theory","author":"N Nisan","year":"2007","unstructured":"Nisan N, Roughgarden T, Tardos E, Vazirani VV (2007) Algorithmic game theory. Cambridge University Press, Cambridge"},{"issue":"2","key":"512_CR94","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1016\/S0377-2217(99)00153-8","volume":"120","author":"CN Potts","year":"2000","unstructured":"Potts CN, Kovalyov MY (2000) Scheduling with batching: a review. Eur J Oper Res 120(2):228\u2013249","journal-title":"Eur J Oper Res"},{"key":"512_CR95","doi-asserted-by":"crossref","unstructured":"Procaccia AD, Tennenholtz M (2009) Approximate mechanism design without money. In: Proceedings of the 10th ACM conference on electronic commerce, ACM, EC \u201909, pp 177\u2013186","DOI":"10.1145\/1566374.1566401"},{"key":"512_CR96","first-page":"321","volume-title":"Aggregation and revelation of preferences","author":"K Roberts","year":"1979","unstructured":"Roberts K (1979) The characterization of implementable choice rules. In: Laffont JJ (ed) Aggregation and revelation of preferences. North-Holland, Amsterdam, pp 321\u2013348"},{"issue":"1","key":"512_CR97","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/BF01737559","volume":"2","author":"RW Rosenthal","year":"1973","unstructured":"Rosenthal RW (1973) A class of games possessing pure-strategy Nash equilibria. Int J Game Theory 2(1):65\u201367","journal-title":"Int J Game Theory"},{"key":"512_CR98","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1017\/CBO9780511800481.019","volume-title":"Algorithmic game theory","author":"T Roughgarden","year":"2007","unstructured":"Roughgarden T, Tardos E (2007) Introduction to the inefficiency of equilibria. In: Nisan N, Roughgarden T, Tardos E, Vazirani VV (eds) Algorithmic game theory. Cambridge University Press, Cambridge, pp 443\u2013459"},{"key":"512_CR99","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1017\/CBO9780511800481.012","volume-title":"Algorithmic game theory","author":"J Schummer","year":"2007","unstructured":"Schummer J, Vohra RV (2007) Mechanism design without money. In: Nisan N, Roughgarden T, Tardos E, Vazirani VV (eds) Algorithmic game theory. Cambridge University Press, Cambridge, pp 243\u2013265"},{"issue":"1","key":"512_CR100","first-page":"193","volume":"2","author":"J Suijs","year":"1996","unstructured":"Suijs J (1996) On incentive compatibility and budget balancedness in public decision making. Econ Des 2(1):193\u2013209","journal-title":"Econ Des"},{"issue":"1","key":"512_CR101","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1111\/j.1540-6261.1961.tb02789.x","volume":"16","author":"W Vickrey","year":"1961","unstructured":"Vickrey W (1961) Counterspeculation, auctions, and competitive sealed tenders. J Finance 16(1):8\u201337","journal-title":"J Finance"},{"key":"512_CR102","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1017\/CBO9780511800481.022","volume-title":"Algorithmic game theory","author":"B V\u00f6cking","year":"2007","unstructured":"V\u00f6cking B (2007) Selfish load balancing. In: Nisan N, Roughgarden T, Tardos E, Vazirani VV (eds) Algorithmic game theory. Cambridge University Press, Cambridge, pp 517\u2013542"}],"container-title":["OR Spectrum"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00291-018-0512-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00291-018-0512-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00291-018-0512-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,11]],"date-time":"2019-10-11T19:43:30Z","timestamp":1570823010000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00291-018-0512-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2,27]]},"references-count":102,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,7]]}},"alternative-id":["512"],"URL":"https:\/\/doi.org\/10.1007\/s00291-018-0512-8","relation":{},"ISSN":["0171-6468","1436-6304"],"issn-type":[{"value":"0171-6468","type":"print"},{"value":"1436-6304","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,2,27]]},"assertion":[{"value":"13 December 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 February 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 February 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}