Loading...
Please wait, while we are loading the content...
Similar Documents
CS364A: Algorithmic Game Theory Lecture #6: Simple Near-Optimal Auctions∗ (2013)
| Content Provider | CiteSeerX |
|---|---|
| Author | Roughgarden, Tim |
| Abstract | Last lecture we proved some of the most fundamental results in auction theory. To reiterate, for every DSIC auction (x,p) for a single-parameter environment with valuation distributions F1,..., Fn, the expected revenue equals the expected virtual welfare: Ev n∑ i=1 pi(v) = Ev n∑ i=1 ϕi(vi) · xi(v). (1) Define the virtual welfare-maximizing allocation rule as the one that sets x(v): = argmax X n∑ i=1 ϕi(vi)xi(v) for each input v. If every Fi is regular, meaning that the corresponding virtual valuation function ϕi(vi) = vi − 1−Fi(vi)fi(vi) is strictly increasing, then the virtual welfare-maximizing allocation rule is monotone and, after we define suitable payments, maximizes expected revenue over all DSIC auctions. This characterization of optimal auctions can be extended to irregular distributions, but this extension requires more work (see [3, Chapter 3]). As a corollary of this general characterization, we noted that the optimal single-item auction with i.i.d. bidders and a regular distribution F is shockingly simple: it is simply the Vickrey auction, augmented with the reserve price ϕ−1(0). This is a true “killer application” of auction theory — it gives crisp, conceptually clean, and practically useful guidance to auction design. |
| File Format | |
| Publisher Date | 2013-01-01 |
| Access Restriction | Open |
| Content Type | Text |
