IDEAS home Printed from https://ideas.repec.org/p/huj/dispap/dp539.html

Envy-Free Makespan Approximation

Author

Listed:
  • Edith Cohen
  • Michal Feldman
  • Amos Fiat
  • Haim Kaplan
  • Svetlana Olonetsky

Abstract

We study envy-free mechanisms for scheduling tasks on unrelated machines (agents) that approximately minimize the makespan. For indivisible tasks, we put forward an envy-free poly-time mechanism that approximates the minimal makespan to within a factor of O(logm), where m is the number of machines. We also show a lower bound of Omega(log m/log logm). This improves the recent result of Mu™alem [22] who give 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.

Suggested Citation

  • Edith Cohen & Michal Feldman & Amos Fiat & Haim Kaplan & Svetlana Olonetsky, 2010. "Envy-Free Makespan Approximation," Discussion Paper Series dp539, The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem.
    • Handle: RePEc:huj:dispap:dp539
    as

    Download full text from publisher

    File URL: http://ratio.huji.ac.il/sites/default/files/publications/dp539.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Claus-Jochen Haake & Matthias G. Raith & Francis Edward Su, 2002. "Bidding for envy-freeness: A procedural approach to n-player fair-division problems," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 19(4), pages 723-749.
    2. Herve Moulin, 2004. "Fair Division and Collective Welfare," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262633116, December.
    3. Nisan, Noam & Ronen, Amir, 2001. "Algorithmic Mechanism Design," Games and Economic Behavior, Elsevier, vol. 35(1-2), pages 166-196, April.
    4. Barbanel,Julius B. Introduction by-Name:Taylor,Alan D., 2005. "The Geometry of Efficient Fair Division," Cambridge Books, Cambridge University Press, number 9780521842488, November.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Vito Fragnelli & Maria Erminia Marina, 2009. "Strategic Manipulations and Collusions in Knaster Procedure," Czech Economic Review, Charles University Prague, Faculty of Social Sciences, Institute of Economic Studies, vol. 3(2), pages 143-153, July.
    2. Edith Cohen & Michal Feldman & Amos Fiat & Haim Kaplan & Svetlana Olonetsky, 2010. "Truth and Envy in Capacitated Allocation Games," Discussion Paper Series dp540, The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem.
    3. Mu'alem, Ahuva, 2014. "Fair by design: Multidimensional envy-free mechanisms," Games and Economic Behavior, Elsevier, vol. 88(C), pages 29-46.
    4. Josué Ortega & Erel Segal-Halevi, 2022. "Obvious manipulations in cake-cutting," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 59(4), pages 969-988, November.
    5. Jens Gudmundsson & Jens Leth Hougaard & Erik Ansink, 2024. "Towards fully decentralized environmental regulation," Tinbergen Institute Discussion Papers 24-035/VIII, Tinbergen Institute.
    6. Sridhar Mandyam & Usha Sridhar, 2017. "DON and Shapley Value for Allocation among Cooperating Agents in a Network: Conditions for Equivalence," Studies in Microeconomics, , vol. 5(2), pages 143-161, December.
    7. Xiayan Cheng & Rongheng Li & Yunxia Zhou, 0. "Tighter price of anarchy for selfish task allocation on selfish machines," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-32.
    8. Levin, Hagay & Schapira, Michael & Zohar, Aviv, 2006. "The Strategic Justification for BGP," MPRA Paper 2110, University Library of Munich, Germany.
    9. Chen, Violet Xinying & Hooker, J.N., 2022. "Combining leximax fairness and efficiency in a mathematical programming model," European Journal of Operational Research, Elsevier, vol. 299(1), pages 235-248.
    10. Barbanel, Julius B. & Brams, Steven J. & Stromquist, Walter, 2008. "Cutting a pie is not a piece of cake," MPRA Paper 12772, University Library of Munich, Germany.
    11. Bettina Klaus & Flip Klijn, 2006. "Procedurally fair and stable matching," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 27(2), pages 431-447, January.
    12. Markus K. Brunnermeier & Michael Sockin & Wei Xiong, 2020. "China’s Model of Managing the Financial System," Working Papers 2020-45, Princeton University. Economics Department..
    13. Shahar Dobzinski & Noam Nisan & Michael Schapira, 2005. "Truthful Randomized Mechanisms for Combinatorial Auctions," Discussion Paper Series dp408, The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem.
    14. Marco LiCalzi & Antonio Nicolò, 2009. "Efficient egalitarian equivalent allocations over a single good," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 40(1), pages 27-45, July.
    15. M. Y. Jumba & Y. S. Haruna & U. O. Aliyu & A. L. Amao, 2024. "Application of Games Theory in Modelling of Nigerian Electricity Market," International Journal of Research and Scientific Innovation, International Journal of Research and Scientific Innovation (IJRSI), vol. 11(5), pages 1129-1140, May.
    16. Yoav Kolumbus & Joe Halpern & 'Eva Tardos, 2024. "Games with Payments between Learning Agents," Papers 2405.20880, arXiv.org, revised Feb 2026.
    17. Aziz, Haris & Chan, Hau & Lee, Barton E. & Parkes, David C., 2020. "The capacity constrained facility location problem," Games and Economic Behavior, Elsevier, vol. 124(C), pages 478-490.
    18. Rachel R. Chen & Robin O. Roundy & Rachel Q. Zhang & Ganesh Janakiraman, 2005. "Efficient Auction Mechanisms for Supply Chain Procurement," Management Science, INFORMS, vol. 51(3), pages 467-482, March.
    19. Zhiling Guo & Gary J. Koehler & Andrew B. Whinston, 2012. "A Computational Analysis of Bundle Trading Markets Design for Distributed Resource Allocation," Information Systems Research, INFORMS, vol. 23(3-part-1), pages 823-843, September.
    20. Konstantin Chatziathanasiou & Svenja Hippel & Michael Kurschilgen, 2020. "Property, Redistribution, and the Status Quo," Munich Papers in Political Economy 02, Munich School of Politics and Public Policy and the School of Management at the Technical University of Munich.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:huj:dispap:dp539. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Michael Simkin (email available below). General contact details of provider: https://edirc.repec.org/data/crihuil.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.