IDEAS home Printed from https://ideas.repec.org/p/huj/dispap/dp539.html
   My bibliography  Save this paper

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. Herve Moulin, 2004. "Fair Division and Collective Welfare," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262633116, December.
    2. Nisan, Noam & Ronen, Amir, 2001. "Algorithmic Mechanism Design," Games and Economic Behavior, Elsevier, vol. 35(1-2), pages 166-196, April.
    3. Barbanel,Julius B. Introduction by-Name:Taylor,Alan D., 2005. "The Geometry of Efficient Fair Division," Cambridge Books, Cambridge University Press, number 9780521842488.
    4. 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.
    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. Ehtamo, Harri & Kettunen, Eero & Hamalainen, Raimo P., 2001. "Searching for joint gains in multi-party negotiations," European Journal of Operational Research, Elsevier, vol. 130(1), pages 54-69, April.
    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. García-Martínez, Jose A. & Mayor-Serra, Antonio J. & Meca, Ana, 2020. "Efficient Effort Equilibrium in Cooperation with Pairwise Cost Reduction," MPRA Paper 105604, University Library of Munich, Germany.
    9. Alessandra Casella & Sébastien Turban & Gregory Wawro, 2017. "Storable votes and judicial nominations in the US Senate," Journal of Theoretical Politics, , vol. 29(2), pages 243-272, April.
    10. de Marti, Joan & Zenou, Yves, 2009. "Social Networks," Working Paper Series 816, Research Institute of Industrial Economics.
    11. Levin, Hagay & Schapira, Michael & Zohar, Aviv, 2006. "The Strategic Justification for BGP," MPRA Paper 2110, University Library of Munich, Germany.
    12. 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.
    13. 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.
    14. 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.
    15. Markus K. Brunnermeier & Michael Sockin & Wei Xiong, 2020. "China’s Model of Managing the Financial System," Working Papers 2020-45, Princeton University. Economics Department..
    16. Tommy ANDERSSON & Lars EHLERS, 2013. "An Algorithm for Identifying Agent-k-Linked Allocations in Economies with Indivisibilities," Cahiers de recherche 17-2013, Centre interuniversitaire de recherche en économie quantitative, CIREQ.
    17. Mark Schneider & Jonathan W. Leland, 2021. "Salience and social choice," Experimental Economics, Springer;Economic Science Association, vol. 24(4), pages 1215-1241, December.
    18. 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.
    19. 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.
    20. William Thomson, 2007. "Children Crying at Birthday Parties. Why?," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 31(3), pages 501-521, June.

    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.