Envy-Free Makespan Approximation

Edith Cohen, Michal Feldman, Amos Fiat, Haim Kaplan and Svetlana Olonetsky

Discussion Paper Series from The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem

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.

Pages: 14 pages
Date: 2010-02
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://ratio.huji.ac.il/sites/default/files/publications/dp539.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 404 Not Found (http://ratio.huji.ac.il/sites/default/files/publications/dp539.pdf [302 Moved Temporarily]--> https://ratio.huji.ac.il/sites/default/files/publications/dp539.pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:huj:dispap:dp539

Access Statistics for this paper

More papers in Discussion Paper Series from The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem Contact information at EDIRC.
Bibliographic data for series maintained by Michael Simkin ().