Andrew V. Goldberg and Jason D. Hartline
We study auctions for a commodity in unlimited supply, e.g., a digital good. In particular we consider three desirable properties for auctions: - Competitive: the auction achieves a constant fraction of the optimal revenue even on worst case inputs. - Truthful: any bidder's best strategy is to bid the maximum value they are willing to pay. - Envy-free: after the auction is run, no bidder would be happier with the outcome of another bidder (for unlimited supply auctions, this means that there is a single sale price and goods are allocated to all bidders willing to pay this price). Our main result is to show that no constant-competitive truthful auction is envy-free. We consider two relaxations of these requirements, allowing the auction to be untruthful with vanishingly small probability, and allowing the auction to give non-envy-free outcomes with vanishingly small probability. Under both of these relaxations we get competitive auctions.
|Published in||ACM Conference on Electronic Commerce (EC '03)|
|Address||San Diego, CA|
|Publisher||Association for Computing Machinery, Inc.|
Copyright © 2003 by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or email@example.com. The definitive version of this paper can be found at ACM’s Digital Library –http://www.acm.org/dl/.