{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:56Z","timestamp":1740109316509,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2021,1,18]],"date-time":"2021-01-18T00:00:00Z","timestamp":1610928000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,1,18]],"date-time":"2021-01-18T00:00:00Z","timestamp":1610928000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000275","name":"Leverhulme Trust","doi-asserted-by":"publisher","award":["RPG-2020-351"],"award-info":[{"award-number":["RPG-2020-351"]}],"id":[{"id":"10.13039\/501100000275","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Apart from the principles and methodologies inherited from Economics and Game Theory, the studies in Algorithmic Mechanism Design typically employ the<jats:italic>worst-case analysis<\/jats:italic>and design of<jats:italic>approximation schemes<\/jats:italic>of Theoretical Computer Science. For instance, the<jats:italic>approximation ratio<\/jats:italic>, which is the canonical measure of evaluating how well an incentive-compatible mechanism approximately optimizes the objective, is defined in the worst-case sense. It compares the performance of the optimal mechanism against the performance of a truthful mechanism, for all possible inputs. In this paper, we take the<jats:italic>average-case analysis<\/jats:italic>approach, and tackle one of the primary motivating problems in Algorithmic Mechanism Design\u2014the scheduling problem\u00a0(Nisan and Ronen, in: Proceedings of the 31st annual ACM symposium on theory of computing (STOC), 1999). One version of this problem, which includes a verification component, is studied by Koutsoupias (Theory Comput Syst 54(3):375\u2013387, 2014). It was shown that the problem has a tight approximation ratio bound of<jats:inline-formula><jats:alternatives><jats:tex-math>$$(n+1)\/2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mo>(<\/mml:mo><mml:mi>n<\/mml:mi><mml:mo>+<\/mml:mo><mml:mn>1<\/mml:mn><mml:mo>)<\/mml:mo><mml:mo>\/<\/mml:mo><mml:mn>2<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>for the single-task setting, where<jats:italic>n<\/jats:italic>is the number of machines. We show, however, when the costs of the machines to executing the task follow<jats:italic>any<\/jats:italic>independent and identical distribution, the<jats:italic>average-case approximation ratio<\/jats:italic>of the mechanism given by Koutsoupias (Theory Comput Syst 54(3):375\u2013387, 2014) is upper bounded by a constant. This positive result asymptotically separates the average-case ratio from the worst-case ratio. It indicates that the optimal mechanism devised for a worst-case guarantee works well on average.<\/jats:p>","DOI":"10.1007\/s00453-020-00796-2","type":"journal-article","created":{"date-parts":[[2021,1,18]],"date-time":"2021-01-18T13:03:00Z","timestamp":1610974980000},"page":"1638-1652","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Average-Case Approximation Ratio of Scheduling without Payments"],"prefix":"10.1007","volume":"83","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5348-7671","authenticated-orcid":false,"given":"Jie","family":"Zhang","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,1,18]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Archer, A., Tardos, \u00c9.: Truthful mechanisms for one-parameter agents. In: 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14\u201317 October 2001, Nevada, USA, pp. 482\u2013491. IEEE Computer Society, Las Vegas (2001)","key":"796_CR1","DOI":"10.1109\/SFCS.2001.959924"},{"doi-asserted-by":"crossref","unstructured":"Arlitt M.F., Williamson C.L.: Web server workload characterization: The search for invariants. In: Proceedings of the ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, pp. 126\u2013137 (1996)","key":"796_CR2","DOI":"10.1145\/233008.233034"},{"issue":"2","key":"796_CR3","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.: Optimal lower bounds for anonymous scheduling mechanisms. Math. Oper. Res. 37(2), 244\u2013258 (2012)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"796_CR4","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1016\/j.jcss.2008.10.001","volume":"75","author":"V Auletta","year":"2009","unstructured":"Auletta, V., Prisco, R.D., Penna, P., Persiano, G.: The power of verification for one-parameter agents. J. Comput. Syst. Sci. 75(3), 190\u2013211 (2009)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"796_CR5","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1145\/2692375.2692378","volume":"13","author":"S Chawla","year":"2014","unstructured":"Chawla, S., Sivan, B.: Bayesian algorithmic mechanism design. SIGecom Exch. 13(1), 5\u201349 (2014)","journal-title":"SIGecom Exch."},{"doi-asserted-by":"crossref","unstructured":"Conitzer, V., Vidali, A.: Mechanism design for scheduling with uncertain execution time. In: Proceedings of the 28th AAAI Conference on Artificial Intelligence, pp. 623\u2013629 (2014)","key":"796_CR6","DOI":"10.1609\/aaai.v28i1.8793"},{"unstructured":"Deng, X., Gao, Y., Zhang, J.: Smoothed and average-case approximation ratios of mechanisms: beyond the worst-case analysis. In: 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017, pp. 16:1\u201316:15 (2017)","key":"796_CR7"},{"key":"796_CR8","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1016\/j.tcs.2012.11.036","volume":"472","author":"D Fotakis","year":"2013","unstructured":"Fotakis, D., Tzamos, C.: Winner-imposing strategyproof mechanisms for multiple facility location games. Theor. Comput. Sci. 472, 90\u2013103 (2013)","journal-title":"Theor. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Gao, Y., Zhang, J.: Average-case analysis of the assignment problem with independent preferences. In: Kraus S (ed) Proceedings of the 28th International Joint Conference on Artificial Intelligence, IJCAI 2019, ijcai.org, pp. 287\u2013293 (2019)","key":"796_CR9","DOI":"10.24963\/ijcai.2019\/41"},{"doi-asserted-by":"crossref","unstructured":"Hartline, JD., Lucier, B.: Bayesian algorithmic mechanism design. In: Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, pp. 301\u2013310 (2010)","key":"796_CR10","DOI":"10.1145\/1806689.1806732"},{"issue":"3","key":"796_CR11","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/s00224-013-9473-0","volume":"54","author":"E Koutsoupias","year":"2014","unstructured":"Koutsoupias, E.: Scheduling without payments. Theory Comput. Syst. 54(3), 375\u2013387 (2014)","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"796_CR12","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.: A lower bound of $$1+\\varphi$$ for truthful scheduling mechanisms. Algorithmica 66(1), 211\u2013223 (2013)","journal-title":"Algorithmica"},{"unstructured":"Kov\u00e1cs, A., Vidali, A.: A characterization of n-player strongly monotone scheduling mechanisms. In: Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI), pp. 568\u2013574 (2015)","key":"796_CR13"},{"doi-asserted-by":"crossref","unstructured":"Kov\u00e1cs, A., Meyer, U., Ventre, C.: Mechanisms with monitoring for truthful RAM allocation. In: Web and Internet Economics\u201411th International Conference, WINE 2015, Amsterdam, The Netherlands, December 9\u201312, 2015, Proceedings, pp. 398\u2013412 (2015)","key":"796_CR14","DOI":"10.1007\/978-3-662-48995-6_29"},{"issue":"1","key":"796_CR15","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.: Truthful mechanism design for multidimensional scheduling via cycle monotonicity. Games Econ. Behav. 67(1), 99\u2013124 (2009)","journal-title":"Games Econ. Behav."},{"unstructured":"Lu, P.: On 2-player randomized mechanisms for scheduling. In: Leonardi S (ed) Internet and Network Economics, 5th International Workshop, WINE 2009, Rome, Italy, December 14\u201318, 2009. Proceedings, Lecture Notes in Computer Science, vol. 5929, pp. 30\u201341. Springer (2009)","key":"796_CR16"},{"unstructured":"Lu, P., Yu, C.: An improved randomized truthful mechanism for scheduling unrelated machines. In: Albers, S., Weil, P. (eds.) STACS 2008, 25th Annual Symposium on Theoretical Aspects of Computer Science, Bordeaux, France, February 21\u201323, 2008, Proceedings, LIPIcs, vol. 1, pp. 527\u2013538. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Germany (2008)","key":"796_CR17"},{"unstructured":"Mu\u2019alem, A., Schapira, M.: Setting lower bounds on truthfulness: extended abstract. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 1143\u20131152 (2007)","key":"796_CR18"},{"doi-asserted-by":"crossref","unstructured":"Nisan, N., Ronen, A.: Algorithmic mechanism design (extended abstract). In: Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC), pp. 129\u2013140 (1999)","key":"796_CR19","DOI":"10.1145\/301250.301287"},{"key":"796_CR20","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, V.V.: Algorithmic Game Theory. Cambridge University Press, New York (2007)"},{"key":"796_CR21","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1016\/j.geb.2012.09.002","volume":"86","author":"P Penna","year":"2014","unstructured":"Penna, P., Ventre, C.: Optimal collusion-resistant mechanisms with verification. Games Econ Behav 86, 491\u2013509 (2014)","journal-title":"Games Econ Behav"},{"doi-asserted-by":"crossref","unstructured":"Procaccia, AD., Tennenholtz, M.: Approximate mechanism design without money. In: Proceedings of the 10th ACM Conference on Electronic Commerce, ACM, pp. 177\u2013186 (2009)","key":"796_CR22","DOI":"10.1145\/1566374.1566401"},{"issue":"8","key":"796_CR23","doi-asserted-by":"publisher","first-page":"1733","DOI":"10.1081\/STA-120037438","volume":"33","author":"WJ Reed","year":"2004","unstructured":"Reed, W.J., Jorgensen, M.: The double pareto-lognormal distribution\u2013a new parametric model for size distributions. Commun. Stat. Theory Methods 33(8), 1733\u20131753 (2004)","journal-title":"Commun. Stat. Theory Methods"},{"key":"796_CR24","first-page":"26","volume":"62","author":"H Robbins","year":"1955","unstructured":"Robbins, H.: A remark on stirling\u2019s formula. Am. Math. Montly. 62, 26\u201329 (1955)","journal-title":"Am. Math. Montly."},{"issue":"21\u201323","key":"796_CR25","doi-asserted-by":"publisher","first-page":"2196","DOI":"10.1016\/j.tcs.2009.02.001","volume":"410","author":"C Yu","year":"2009","unstructured":"Yu, C.: Truthful mechanisms for two-range-values variant of unrelated scheduling. Theor. Comput. Sci. 410(21\u201323), 2196\u20132206 (2009)","journal-title":"Theor. Comput. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00796-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00796-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00796-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,12]],"date-time":"2022-12-12T01:14:16Z","timestamp":1670807656000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00796-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,18]]},"references-count":25,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["796"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00796-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2021,1,18]]},"assertion":[{"value":"21 July 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 December 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 January 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}