We give envy-free mechanisms for parallel task scheduling on unrelated machines that approximates the minimal makespan to within a factor of O(log m). We also show a lower bound of Omega(log m / loglog m). This improves the recent result of Hartline et. al. who give an upper bound of (m+1)/2, and a lower bound of 2-1/m. We consider both envy freeness and incentive compatibility, give mechanisms for combinatorial auctions that are both, and characterize allocations with respect to the interaction between envy freeness and incentive compatibility.

Joint work with Edith Cohen, Michal Feldman, Haim Kaplan, Svetlana Olonetsky