{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T11:36:27Z","timestamp":1770896187677,"version":"3.50.1"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,11,30]],"date-time":"2017-11-30T00:00:00Z","timestamp":1512000000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2017,11,30]]},"abstract":"<jats:p>\n            We study the problem of scheduling\n            <jats:italic>m<\/jats:italic>\n            tasks to\n            <jats:italic>n<\/jats:italic>\n            selfish, unrelated machines in order to minimize the makespan, in which the execution times are independent random variables, identical across machines. We show that the VCG mechanism, which myopically allocates each task to its best machine, achieves an approximation ratio of\n            <jats:italic>O<\/jats:italic>\n            (ln\n            <jats:italic>n<\/jats:italic>\n            ln \/ ln\n            <jats:italic>n<\/jats:italic>\n            ). This improves significantly on the previously best known bound of\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            \/\n            <jats:italic>n<\/jats:italic>\n            ) for prior-independent mechanisms, given by Chawla et al. [7] under the additional assumption of Monotone Hazard Rate (MHR) distributions. Although we demonstrate that this is tight in general, if we do maintain the MHR assumption, then we get improved, (small) constant bounds for\n            <jats:italic>m<\/jats:italic>\n            \u2265\n            <jats:italic>n<\/jats:italic>\n            ln\n            <jats:italic>n<\/jats:italic>\n            i.i.d. tasks. We also identify a sufficient condition on the distribution that yields a constant approximation ratio regardless of the number of tasks.\n          <\/jats:p>","DOI":"10.1145\/3105968","type":"journal-article","created":{"date-parts":[[2017,12,15]],"date-time":"2017-12-15T13:39:24Z","timestamp":1513345164000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["The VCG Mechanism for Bayesian Scheduling"],"prefix":"10.1145","volume":"5","author":[{"given":"Yiannis","family":"Giannakopoulos","sequence":"first","affiliation":[{"name":"University of Liverpool"}]},{"given":"Maria","family":"Kyropoulou","sequence":"additional","affiliation":[{"name":"University of Oxford"}]}],"member":"320","published-online":{"date-parts":[[2017,12,14]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Aaron Archer and \u00c9va Tardos. 2001. Truthful mechanisms for one-parameter agents. In FOCS. 482--491.   Aaron Archer and \u00c9va Tardos. 2001. Truthful mechanisms for one-parameter agents. In FOCS. 482--491.","DOI":"10.1109\/SFCS.2001.959924"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1110.0534"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.2307\/3213876"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201914)","author":"Azar Pablo D."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177704147"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.09.023"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488616"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214019"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1668926.1668927"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/120866038"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01726210"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Constantinos Daskalakis and S. Matthew Weinberg. 2015. Bayesian truthful mechanisms for job scheduling from bi-criterion approximation algorithms. In SODA. 1934--1952.   Constantinos Daskalakis and S. Matthew Weinberg. 2015. Bayesian truthful mechanisms for job scheduling from bi-criterion approximation algorithms. In SODA. 1934--1952.","DOI":"10.1137\/1.9781611973730.130"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25510-6_11"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/080744992"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2014.03.011"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a005"},{"key":"e_1_2_1_17_1","first-page":"1243","article-title":"A unified approach to truthful scheduling on related machines","volume":"41","author":"Epstein L.","year":"2013","journal-title":"Mathematics of Operations Research"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48995-6_25"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-54110-4_12"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.2307\/1914085"},{"key":"e_1_2_1_21_1","volume-title":"Approximation Algorithms for NP-hard Problems, Dorit S","author":"Hall Leslie A."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1566374.1566407"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9634-6"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2008.08.001"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585745"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10841-9_5"},{"key":"e_1_2_1_27_1","unstructured":"Pinyan Lu and Changyuan Yu. 2008. An improved randomized truthful mechanism for scheduling unrelated machines. In STACS. 527--538.  Pinyan Lu and Changyuan Yu. 2008. An improved randomized truthful mechanism for scheduling unrelated machines. In STACS. 527--538."},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Rajeev Motwani and Prabhakar Raghavan. 1995. Randomized Algorithms. Cambridge University Press New York NY.   Rajeev Motwani and Prabhakar Raghavan. 1995. Randomized Algorithms. Cambridge University Press New York NY.","DOI":"10.1017\/CBO9780511814075"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"N. Nisan and A. Ronen. 2001. Algorithmic mechanism design. Games and Economic Behavior 35 1\/2 166--196.  N. Nisan and A. Ronen. 2001. Algorithmic mechanism design. Games and Economic Behavior 35 1\/2 166--196.","DOI":"10.1006\/game.1999.0790"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622606.1622608"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Martin Raab and Angelika Steger. 1998. \u201cBalls into Bins\u201d - A simple and tight analysis. In RANDOM. 159--170.   Martin Raab and Angelika Steger. 1998. \u201cBalls into Bins\u201d - A simple and tight analysis. In RANDOM. 159--170.","DOI":"10.1007\/3-540-49543-6_13"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229077"},{"key":"e_1_2_1_33_1","unstructured":"Balasubramanian Sivan. 2013. Prior Robust Optimization. Ph.D. Dissertation. University of Wisconsin-Madison.   Balasubramanian Sivan. 2013. Prior Robust Optimization. Ph.D. Dissertation. University of Wisconsin-Madison."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1540-6261.1961.tb02789.x"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.02.001"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3105968","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3105968","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:04Z","timestamp":1750217404000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3105968"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,11,30]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,11,30]]}},"alternative-id":["10.1145\/3105968"],"URL":"https:\/\/doi.org\/10.1145\/3105968","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"value":"2167-8375","type":"print"},{"value":"2167-8383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,11,30]]},"assertion":[{"value":"2016-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-12-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}