{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:24:57Z","timestamp":1787340297253,"version":"build-2736575974"},"reference-count":31,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p>We study envy-free mechanisms for assigning tasks to agents, where every task may take a different amount of time to perform by each agent, and the goal is to get all the tasks done as soon as possible (i.e., minimize the makespan). For indivisible tasks, we put forward an envy-free polynomial mechanism that approximates the minimal makespan to within a factor of $O(\\log m)$, where m is the number of machines. This bound is almost tight, as we also show that no envy-free mechanism can achieve a better bound than $\\Omega(\\log m \/ \\log\\log m)$. This improves the recent result of Mu'alem [On multi-dimensional envy-free mechanisms, in Proceedings of the First International Conference on Algorithmic Decision Theory, F. Rossi and A. Tsoukias, eds., Lecture Notes in Comput. Sci. 5783, Springer, Berlin, 2009, pp. 120\u2013131] who introduced the model and gave an upper bound of $(m+1)\/2$ and a lower bound of $2-1\/m$. For divisible tasks, we show that there always exists an envy-free poly-time mechanism with optimal makespan. Finally, we demonstrate how our mechanism for envy-free makespan minimization can be interpreted as a market clearing problem.<\/jats:p>","DOI":"10.1137\/100801597","type":"journal-article","created":{"date-parts":[[2012,1,3]],"date-time":"2012-01-03T21:04:15Z","timestamp":1325624655000},"page":"12-25","source":"Crossref","is-referenced-by-count":5,"title":["Envy-Free Makespan Approximation"],"prefix":"10.1137","volume":"41","author":[{"given":"Edith","family":"Cohen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michal","family":"Feldman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Amos","family":"Fiat","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Haim","family":"Kaplan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Svetlana","family":"Olonetsky","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,1,3]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"I. Ashlagi, S. Dobzinski, and R. Lavi,\n                      An optimal lower bound for anonymous scheduling mechanisms\n                      , in Proceedings of the 10th ACM Conference on Electronic Commerce, ACM, New York, 2009, pp. 169\u2013176.","DOI":"10.1145\/1566374.1566399"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"N. Bansal, N. Chen, N. Cherniavsky, A. Rudra, B. Schieber, and M. Sviridenko,\n                      Dynamic pricing for impatient bidders\n                      , ACM Trans. Algorithms, 6 (2010), art. 35.","DOI":"10.1145\/1721837.1721851"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"S. J. Brams and A. D. Taylor,\n                      Fair Division: From Cake-Cutting to Dispute Resolution\n                      , Cambridge University Press, Cambridge, UK, 1996.","DOI":"10.1017\/CBO9780511598975"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"P. Briest,\n                      Uniform budgets and the envy-free pricing problem\n                      , in Proceedings of the 35th International Colloquium on Automata, Languages and Programming, Part 1 (ICALP), L. Aceto, I. Damg\u00e5rd, L. A. Goldberg, M. M. Halld\u00f3rsson, A. Ing\u00f3lfsd\u00f3ttir, and I. Walukiewicz, eds., Lecture Notes in Comput. Sci. 5125, Springer, Berlin, New York, 2008, pp. 808\u2013819.","DOI":"10.1007\/978-3-540-70575-8_66"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"N. Chen, A. Ghosh, and S. Vassilvitskii,\n                      Optimal envy-free pricing with metric substitutability\n                      , in Proceedings of the ACM Conference on Electronic Commerce, L. Fortnow, J. Riedl, and T. Sandholm, eds., ACM, New York, 2008, pp. 60\u201369.","DOI":"10.1145\/1386790.1386803"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"G. Christodoulou, E. Koutsoupias, and A. Kov\u00e1cs,\n                      Mechanism design for fractional scheduling on unrelated machines\n                      , ACM Trans. Algorithms, 6 (2010), art. 38.","DOI":"10.1145\/1721837.1721854"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"G. Christodoulou, E. Koutsoupias, and A. Vidali,\n                      A characterization of 2-player mechanisms for scheduling\n                      , in Proceedings of the 16th Annual European Symposium on Algorithms, Springer, Berlin, 2008, pp. 297\u2013307.","DOI":"10.1007\/978-3-540-87744-8_25"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/060656048"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1961.11989615"},{"key":"R10","first-page":"45","volume":"7","author":"Foley D.","year":"1967","journal-title":"Yale Economic Essays"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"H. Gabow, ed.\n                      Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA),\n                      New Orleans, LA, SIAM, Philadelphia, ACM, New York, 2007.","DOI":"10.1137\/1.9780898716245"},{"key":"R12","unstructured":"M. Gardner,\n                      Aha! Insight\n                      , W.H. Freeman, San Francisco, 1978."},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70356-X"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1006\/jeth.1999.2531"},{"key":"R15","unstructured":"V. Guruswami, J. D. Hartline, A. R. Karlin, D. Kempe, C. Kenyon, and F. McSherry,\n                      On profit-maximizing envy-free pricing\n                      , in Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, ACM, New York, 2005, pp. 1164\u20131173."},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1007\/s003550100149"},{"key":"R17","unstructured":"A. D. T. Julius and B. Barbanel,\n                      The Geometry of Efficient Fair Division\n                      , Cambridge University Press, Cambridge, UK, 2005."},{"key":"R18","doi-asserted-by":"crossref","unstructured":"D. Kempe, A. Mu'alem, and M. Salek,\n                      Envy-free allocations for budgeted bidders\n                      , in Proceedings of the 5th International Workshop on Internet and Network Economics, Springer-Verlag, Heidelberg, 2009, pp. 537\u2013544.","DOI":"10.1007\/978-3-642-10841-9_53"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"E. Koutsoupias and A. Vidali,\n                      A lower bound of $1+{\\phi}$ for truthful scheduling mechanisms\n                      , In Proceedings of the 32nd International Symposium on Mathematical Foundations of Computer Science (MFCS), L. Ku$\\check{\\rm c}$era and A. Ku$\\check{\\rm c}$era, eds., Lecture Notes in Comput. Sci. 4708, Springer, Berlin, 2007, pp. 454\u2013464.","DOI":"10.1007\/978-3-540-74456-6_41"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800020109"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"R. Lavi and C. Swamy,\n                      Truthful mechanism design for multi-dimensional scheduling via cycle monotonicity\n                      , in Proceedings 8th ACM Conference on Electronic Commerce (EC-2007), San Diego, CA, J. K. MacKie-Mason, D. C. Parkes, and P. Resnick, eds., ACM, New York, 2007, pp. 252\u2013261.","DOI":"10.1145\/1250910.1250947"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585745"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"H. Moulin,\n                      Fair Division and Collective Welfare\n                      , MIT Press, Cambridge, MA, 2004.","DOI":"10.7551\/mitpress\/2954.001.0001"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"A. Mu'alem,\n                      On multi-dimensional envy-free mechanisms\n                      , in Proceedings of the First International Conference on Algorithmic Decision Theory, F. Rossi and A. Tsoukias, eds., Lecture Notes in Comput. Sci. 5783, Springer, Berlin, 2009, pp. 120\u2013131.","DOI":"10.1007\/978-3-642-04428-1_11"},{"key":"R25","unstructured":"A. Mu'alem and M. Schapira,\n                      Setting lower bounds on truthfulness (extended abstract)\n                      , in Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), New Orleans, LA, H. Gabow, ed., SIAM, Philadelphia, ACM, New York, 2007, pp. 1143\u20131152."},{"key":"R26","doi-asserted-by":"crossref","unstructured":"N. Nisan and A. Ronen,\n                      Algorithmic mechanism design (extended abstract)\n                      , in Proceedings of the 31st Symposium on Theory of Computing (STOC), ACM, New York, 1999, pp. 129\u2013140.","DOI":"10.1145\/301250.301287"},{"key":"R27","unstructured":"J. Rawls,\n                      A Theory of Justice\n                      , Harvard University Press, Cambridge, MA, 2005."},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1145\/1012888.1005704"},{"key":"R29","first-page":"101","volume":"16","author":"Steinhaus H.","year":"1948","journal-title":"Econometrica","ISSN":"https:\/\/id.crossref.org\/issn\/0012-9682","issn-type":"print"},{"key":"R30","unstructured":"H. Steinhaus,\n                      Mathematical Snapshots\n                      , Oxford University Press, Oxford, UK, 1951."},{"key":"R31","unstructured":"H. P. Young,\n                      Equity: In Theory and Practice\n                      , Princeton University Press, Princeton, NJ, 1995."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/100801597","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:28:51Z","timestamp":1787336931000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/100801597"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1137\/100801597"],"URL":"https:\/\/doi.org\/10.1137\/100801597","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1]]}}}