prev

next

out of 38

View

216Download

0

Embed Size (px)

8/2/2019 Vickrey Auctions

1/38

This work is distributed as a Discussion Paper by the

STANFORD INSTITUTE FOR ECONOMIC POLICY RESEARCH

SIEPR Discussion Paper No. 03-36

The Lovely but Lonely Vickrey Auction

By

Lawrence M. Ausubel

University of Maryland

And

Paul Milgrom

Stanford University

August 2004

Stanford Institute for Economic Policy ResearchStanford University

Stanford, CA 94305(650) 725-1874

The Stanford Institute for Economic Policy Research at Stanford University supports research bearing on

economic and public policy issues. The SIEPR Discussion Paper Series reports on research and policy

analysis conducted by researchers affiliated with the Institute. Working papers in this series reflect the views

of the authors and not necessarily those of the Stanford Institute for Economic Policy Research or StanfordUniversity.

8/2/2019 Vickrey Auctions

2/38

1

The Lovely but Lonely Vickrey Auction

Lawrence M. Ausubel and Paul Milgrom

1. Introduction

William Vickreys (1961) inquiry into auctions and counterspeculation marked the

first serious attempt by an economist to analyze the details of market rules and to design

new rules to achieve superior performance. He demonstrated that a particular pricing rule

makes it a dominant strategy for bidders to report their values truthfully, even when they

know that their reported values will be used to allocate goods efficiently. Vickreys

discovery was largely ignored for a decade, but the floodgates have since opened. Dozens

of studies have extended his design to new environments, developed his associated theory

of bidding in auctions, and tested its implications using laboratory experiments and field

data.

Despite the enthusiasm that the Vickrey mechanism and its extensions generate

among economists, practical applications of Vickreys design are rare at best. The classic

English auction of Sothebys and Christies, in which bidders iteratively submit

successively higher bids and the final bidder wins the item in return for a payment

equaling his final bid, is closely related to Vickreys second-price sealed-bid auction, but

long predates it. Online auctions such as eBay, in which bidders commonly utilize proxy

bids authorizing the auctioneer to bid up to specified prices on their behalf, more nearly

resemble the Vickrey design for a single item; however, these remain true dynamic

auctions, as online bidders who submit proxy bids generally retain the ability to raise

their proxy bids later. The most general and novel version of Vickreys design, which

8/2/2019 Vickrey Auctions

3/38

2

applies to sales in which different bidders may want multiple units of homogeneous

goodsor packages of heterogeneous goodsremains largely unused.

Why is the Vickrey auction design, which is so lovely in theory, so lonely in practice?

The answer, we believe, is a cautionary tale that emphasizes the importance of analyzing

practical designs from many perspectives. Vickreys design has some impressive

theoretical virtues, but it also suffers from weaknesses that are frequently decisive. This

chapter reviews the theoretical pluses and minuses of the Vickrey design, highlighting

issues that cannot be ignored in developing practical auction designs.

2. Description of the general Vickrey (VCG) design

Vickreys original inquiry treated both auctions of a single item and auctions of

multiple identical items, providing a mechanism in which it is a dominant strategy for

bidders to report their values truthfully and in which outcomes are efficient. For a single

item, the mechanism is often referred to as the second-price sealed-bid auction, or simply

the Vickrey auction. Bidders simultaneously submit sealed bids for the item. The highest

bidder wins the item, but (unlike standard sealed-bid tenders) the winner pays the amount

of the second-highest bid. For example, if the winning bidder bids 10 and the highest

losing bid is 8, the winner pays 8. With these rules, a winning bidder can never affect the

price it pays, so there is no incentive for any bidder to misrepresent his value. From

bidderns perspective, the amount he bids determines only whether he wins, and only by

bidding his true value can he be sure to win exactly when he is willing to pay the price.

In Vickreys original treatment of multiple units of a homogeneous good, which may

be available in either continuous or discrete quantities, each bidder is assumed to have

monotonically nonincreasing marginal values for the good. The bidders simultaneously

8/2/2019 Vickrey Auctions

4/38

3

submit sealed bids comprising demand curves. The seller combines the individual

demand curves in the usual way to determine an aggregate demand curve and a clearing

price forS units. Each bidder wins the quantity he demanded at the clearing price.

However, rather than paying the prices he bid or the clearing price for his units, a

winning bidder pays the opportunity costfor the units won.

In the case of discrete units, an equivalent way to describe the multi-unit Vickrey

auction is that each bidder submits a number of separate bids, each representing an offer

to buy one unit. These individual bids describe the bidders demand curve. The

auctioneer accepts the S highest bids. If biddern wins Kunits, then he pays the sum of

the Khighest rejected bids by other bidders. For example, if a bidder wins 2 units and the

highest rejected bids by his competitors are 12 and 11, then the bidder pays 23 for his two

units.

Another way to describe the rule is that the price a bidder pays for his rth unit is the

clearing price that would have resulted if biddern had restricted his demand to runits (all

other bidders behaviors held fixed). This equivalent description makes clear the

opportunity-cost interpretation of the winners payments. The total payment for biddern

is computed by summing this payment over all items won, in the case of discrete units, or

by integrating this payment from 0 to the quantity won, in the case of continuous units.

The mechanism can be used as either a mechanism to sell (a standard auction) or as a

mechanism to buy (a reverse auction). Described as a standard auction, the buyers

generally pay a discount as compared to the clearing price. Described as a reverse

auction, the sellers generally receive a premium as compared to the clearing price.

Indeed, the main point of Vickreys seminal article was that the government cannot

8/2/2019 Vickrey Auctions

5/38

4

establish a marketing agency to implement a dominant-strategy mechanism in two-sided

markets without providing a subsidy: The basic drawback to this scheme is, of course,

that the marketing agency will be required to make payments to suppliers in an amount

that exceeds, in the aggregate, the receipts from purchasers (Vickrey 1961, p. 13).

Since Vickreys original contribution, his auction design has been melded with the

Clarke-Groves design for public goods problems.1 The resulting auction design works for

heterogeneous goods as well as homogeneous goods and does not require that bidders

have nonincreasing marginal values. As with Vickreys original design, this mechanism

still assigns goods efficiently and still charges bidders the opportunity cost of the items

they win. The main difference is that the amounts paid cannot generally be expressed as

the sums of bids for individual items. The extended Vickrey mechanism goes by various

names. Here, we call it the Vickrey-Clarke-Groves orVCG mechanism.

Formally, the VCG mechanism is described as follows. Let x be a vector of goods

that a seller has on offer and let ( )n n

v x denote bidderns value for any nonnegative

vector nx . Each bidder 1,...,n N= reports a value function nv to the auctioneer. The

auctioneer then computes a value-maximizing allocation:1

*

,...,arg max ( )

Nx x n nnx v x

subject to nnx x . The price paid by a biddern is then* ( )n n m mm np v x = , where

{ }max ( ) |n m m mm n m nv x x x = . Notice that n depends only on the value reports

of the other bidders and not on what biddern reports.

1 The Clarke-Groves design was introduced in Clarke (1971) and Groves (1973).

8/2/2019 Vickrey Auctions

6/38

5

To illustrate the VCG mechanism, suppose that there are two items for sale (A and B)

and two bidders. Each biddern = 1,2 submits bids: (A)n

v for item A; (B)n

v for item B;

and (AB)n

v for the two items together. Assume without loss of generality that

1 2 (AB) (AB)v v and 1 2 1 2 (A) (B) (B) (A)v v v v+ + . If 1 1 2 (AB) (A) (B)v v v> + , then the

outcome is that bidder 1 wins both items. Applying the formula, his payment is 2 (AB)v .

However, if 1 1 2 (AB) (A) (B)v v v< + , then the outcome is that bidder 1 wins item A (with

an associated payment of 2 2 (AB) (B)v v ) and bidder 2 wins items B (with an associated

payment of1 1

(AB) (A)v v ). In each case, the winner pays the opportunity cost of the

items won, and his payment depends only on his opponents reports.

The first theorem confirms that the general VCG mechanism still has the properties

that it is a dominant strategy for each bidder to report its values truthfully and that t