ICS Theory Group

ICS 269, Fall 2003: Theory Seminar

07 Nov 2003:
Envy-Free Auctions for Digital Goods
authored by J. Hartline and A. Goldberg

In: Proc. 4th ACM Conf. on Electronic Commerce, 2003.

presented by Matt Nguyen

The authors study auctions in unlimited supply. They show that no constant-competitive truthful auction is envy-free. They also show that by relaxing the problem to instead being truthful with small probability of being envy-free, or vice versa, auctions can be competitive.


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