Envy-Free Auctions for Digital Goods

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.