On Multi-Dimensional Envy-Free Mechanisms
- Creators
- Mu'alem, Ahuva
Abstract
Traditional performance analysis of approximation algorithms considers overall performance, while economic fairness analysis focuses on the individual performance each user receives. In this paper we formulate the problem of fairness design in the context of resource allocation scenarios. The fair design problem is the design of computationallyefficient individually-fair mechanism to approximate a global goal. We present the first polynomial-communication profit-maximizing combinatorial auction for general bidders in an envy-free manner. Additionally, we study the canonical makespan-minimizing scheduling problem of unrelated machines and show upper and lower bounds. For the related machines model we show that tight algorithmic bounds can be achieved. Furthermore, using a shifting procedure we show how an interesting special case of post-auction resales can be prevented in quasi-polynomial time.
Additional Information
© 2009 Springer. I would like to thank anonymous referees, Liad Blumrosen, Federico Echenique, David Kempe, John Ledyard, Debasis Mishra, Mohamed Mostagir, Mahyar Salek and Michael Schapira for helpful discussions.Additional details
- Eprint ID
- 18117
- DOI
- 10.1007/978-3-642-04428-1_11
- Resolver ID
- CaltechAUTHORS:20100503-150511845
- Created
-
2010-05-12Created from EPrint's datestamp field
- Updated
-
2023-03-16Created from EPrint's last_modified field