A Vickrey auction is a type of sealed-bid auction, where bidders submit written bids without knowing the bid of the other people in the auction, and in which the highest bidder wins, but the price paid is the second-highest bid. The auction was created by Columbia University professor William Vickrey. This type of auction is strategically similar to an English auction, and gives bidders an incentive to bid their true value.

Vickrey's original paper considered only auctions where a single, indivisible good is being sold. In this case, the terms Vickrey auction and second-price sealed-bid auction are equivalent, and are used interchangeably. However, when either a divisible good or multiple identical goods are sold in a single auction, these terms are used differently.

The most obvious generalization to multiple or divisible goods is to have all winning bidders pay the amount of the highest non-winning bid. This is known as a uniform price auction. The uniform-price auction does not, however, result in bidders bidding their true valuations as they do in a second-price auction unless each bidder has demand for only a single unit. A generalization of the Vickrey auction that maintains the incentive to bid truthfully is known as the Vickrey–Clarke–Groves (VCG) mechanism. The idea in VCG is that items are assigned to maximize the sum of utilities; then each bidder pays the "opportunity cost" that their presence introduces to all the other players. This opportunity cost for a bidder is defined as the total bids of all the other bidders that would have won if the first bidder didn't bid, minus the total bids of all the other actual winning bidders.

For example, suppose two apples are being auctioned among three bidders.

• Bidder A wants one apple and bids $5 for that apple.
• Bidder B wants one apple and is willing to pay $2 for it.
• Bidder C wants two apples and is willing to pay $6 to have both of them but is uninterested in buying only one without the other.

First, the outcome of the auction is determined by maximizing bids: the apples go to bidder A and bidder B. Next, the formula for deciding payments gives:

• A: B and C have total utility $2 (the amount they pay together: $2 + $0) - if A were removed, the optimal allocation would give B and C total utility $6 ($0 + $6). So A pays $4 ($6 − $2).
• B: A and C have total utility $5 ($5 + $0) - if B were removed, the optimal allocation would give A and C total utility $(0 + 6). So B pays $1 ($6 − $5).
• similarly, C pays $0 (5 + 2) − (5 + 2) = $0.

Vickrey auctions are much studied in economic literature, but are not particularly common in practice. One market in which they have been used is stamp collecting. eBay's system of proxy bidding is similar, but not identical, to a Vickrey auction. A slight generalized variant of a Vickrey auction, named generalized second-price auction, which is different from the VCG mechanism, is known to be used in Google's and Yahoo!'s online advertisement programmes.^[1][2] NYU Law School uses an iterated version of the Vickrey auction model for its course registration lottery.^[3]

Properties[link]

Self-revelation/incentive compatibility[link]

In a Vickrey auction with independent private values (IPV) each bidder maximizes his or her expected utility by bidding (revealing) his or her true valuation.

Ex-post efficiency[link]

A Vickrey auction is decision efficient (the winner is the bidder with the highest valuation) under the most general circumstances; it thus provides a baseline model against which the efficiency properties of other types of auctions can be posited. It is only ex-post efficient (sum of transfers equal to zero) if the seller is included as "player zero," whose transfer equals the negative of the sum of the other players' transfers (i.e. the bids).

Weaknesses[link]

Despite the Vickrey auction's strengths, it has shortcomings:

• It does not allow for price discovery, that is, discovery of the market price if the buyers are unsure of their own valuations, without sequential auctions.
• Sellers may use shill bids to increase profit.

The Vickrey–Clarke–Groves (VCG) mechanism has the additional shortcomings:

• It is vulnerable to bidder collusion. If all bidders in Vickrey auction reveal their valuations to each other, they can lower some or all of their valuations, while preserving who wins the auction. [1]
• It is vulnerable to shill bidding with respect to the buyers.^[vague]
• It does not necessarily maximize seller revenues; seller revenues may even be zero in VCG auctions. If the purpose of holding the auction is to maximize profit for the seller rather than just allocate resources among buyers, then VCG may be a poor choice.
• The seller's revenues are non-monotonic with regard to the sets of bidders and offers.

The non-monotonicity of seller's revenues with respect to bids can be shown by the following example. Consider 3 bidders A, B, and C, and two homogeneous items bid upon, Y and Z.

• A wants both items and bids $2 for the package of Y and Z.
• B and C both bid $2 each for a single item (bid $2 for Y or Z), as they really want one item but don't care if they have the second.

Now, Y and Z are allocated to B and C, but the price is $0, as can be found by removing either B or C respectively. If C bid $0 instead of $2, then the seller would make $2 instead of $0. Because the seller's revenue can also go up when bids are increased, the seller's revenues are non-monotonic with respect to bids.

Proof of dominance of truthful bidding[link]

The dominant strategy in a Vickrey auction with a single, indivisible item is for each bidder to bid their true value of the item.^[4]

Let Failed to parse (Missing texvc executable; please see math/README to configure.): v_i

be bidder i's value for the item. Let Failed to parse (Missing texvc executable; please see math/README to configure.): b_i
be bidder i's bid for the item. 

The payoff for bidder i is Failed to parse (Missing texvc executable; please see math/README to configure.): \begin{cases} v_i-\max_{j\neq i} b_j & \text{if } b_i > \max_{j\neq i} b_j \\ 0 & \text{otherwise} \end{cases}

The strategy of overbidding is dominated by bidding truthfully. Assume that bidder i bids Failed to parse (Missing texvc executable; please see math/README to configure.): b_i > v_i .

If Failed to parse (Missing texvc executable; please see math/README to configure.): \max_{j\neq i} b_j < v_i

then the bidder would win the item with a truthful bid as well as an overbid. The bid's amount does not change the payoff so the two strategies have equal payoffs in this case. 

If Failed to parse (Missing texvc executable; please see math/README to configure.): \max_{j\neq i} b_j > b_i

then the bidder would lose the item either way so the strategies have equal payoffs in this case. 

If Failed to parse (Missing texvc executable; please see math/README to configure.): v_i < \max_{j\neq i} b_j < b_i

then only the strategy of overbidding would win the auction. The payoff would be negative for the strategy of overbidding because they paid more than their value of the item, while the payoff for a truthful bid would be zero. Thus the strategy of bidding higher than one's true valuation is dominated by the strategy of truthfully bidding.

The strategy of underbidding is dominated by bidding truthfully. Assume that bidder i bids Failed to parse (Missing texvc executable; please see math/README to configure.): b_i < v_i .

If Failed to parse (Missing texvc executable; please see math/README to configure.): \max_{j\neq i} b_j > v_i

then the bidder would lose the item with a truthful bid as well as an underbid, so the strategies have equal payoffs for this case. 

If Failed to parse (Missing texvc executable; please see math/README to configure.): \max_{j\neq i} b_j < b_i

then the bidder would win the item either way so the strategies have equal payoffs in this case. 

If Failed to parse (Missing texvc executable; please see math/README to configure.): b_i < \max_{j\neq i} b_j < v_i

then only the strategy of truthfully bidding would win the auction. The payoff for the truthful strategy would be positive as they paid less than their value of the item, while the payoff for an underbid bid would be zero. Thus the strategy of underbidding is dominated by the strategy of truthfully bidding.

Truthful bidding dominates the other possible strategies (underbidding and overbidding) so it is an optimal strategy.

Use in network routing[link]

This section needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. (May 2009)

In network routing, VCG mechanisms are a family of payment schemes based on the added value concept. The basic idea of a VCG mechanism in network routing is to pay the owner of each link or node (depending on the network model) that is part of the solution, its declared cost plus its added value. In many routing problems, this mechanism is not only strategyproof, but also the minimum among all strategyproof mechanisms.

In the case of network flows, Unicast or Multicast, a minimum cost flow (MCF) in graph G is calculated based on the declared costs d_k of each of the links and payment is calculated as follows:

Each link (or node) Failed to parse (Missing texvc executable; please see math/README to configure.): \scriptstyle e_k

in the MCF is paid

Failed to parse (Missing texvc executable; please see math/README to configure.): p_k = d_k + MCF(G - e_k) - MCF(G)

,

where MCF(G) indicates the cost of the minimum cost flow in graph G and G − e_k indicates graph G without the link e_k. Links not in the MCF are paid nothing. This routing problem is one of the cases for which VCG is strategyproof and minimum.

In 2004, it was shown that the expected VCG overpayment of an Erdős–Renyi random graph with n nodes and edge probability p, Failed to parse (Missing texvc executable; please see math/README to configure.): \scriptstyle G \in G(n, p)

approaches

Failed to parse (Missing texvc executable; please see math/README to configure.): \frac{p}{2-p}

as n, approaches Failed to parse (Missing texvc executable; please see math/README to configure.): \scriptstyle \infty , for Failed to parse (Missing texvc executable; please see math/README to configure.): n p = \omega(\sqrt{n \log n}) . Prior to this result, it was known that VCG overpayment in G(n, p) is

Failed to parse (Missing texvc executable; please see math/README to configure.): \Omega\left(\frac{1}{np}\right)

and

Failed to parse (Missing texvc executable; please see math/README to configure.): O(1)\,

with high probability given

Failed to parse (Missing texvc executable; please see math/README to configure.): np=\omega(\log n).\,

References[link]

• Vijay Krishna, Auction Theory, Academic Press, 2002.
• Peter Cramton, Yoav Shoham, Richard Steinberg (Eds), Combinatorial Auctions, MIT Press, 2006, Chapter 1. ISBN 0-262-03342-9.
• Paul Milgrom, Putting Auction Theory to Work, Cambridge University Press, 2004.
• Tech Ho, "Consumption and Production" UC Berkeley, Haas Class of 2010.

External links[link]

• Paper on the history of Vickrey auctions in stamp collecting

Notes[link]

1. ^ Benjamin Edelman, Michael Ostrovsky, and Michael Schwarz: "Internet Advertising and the Generalized Second-Price Auction: Selling Billions of Dollars Worth of Keywords". American Economic Review 97(1), 2007 pp 242–259.
2. ^ Hal R. Varian: "Position Auctions". International Journal of Industrial Organization, 2006, doi:10.1016/j.ijindorg.2006.10.002 .
3. ^ Memorandum from the Office of the Vice Dean of NYU School of Law. http://www.law.nyu.edu/ecm_dlv/groups/public/@nyu_law_website__academics/documents/web_copytext/ecm_pro_061262.pdf
4. ^ von Ahn, Luis (2008-09-30). "Auctions" (PDF). 15–396: Science of the Web Course Notes. Carnegie Mellon University. http://www.scienceoftheweb.org/15-396/lectures/lecture09.pdf. Retrieved 2008-11-06. 

Robert Remsen Vickrey (August 26, 1926 – April 17, 2011)^[1] was a Massachusetts-based artist and author who specialized in the ancient medium of egg tempera. His paintings are surreal dreamlike visions of sunset shadows of bicycles, nuns in front of mural-painted brick walls, and children playing.

Born in Manhattan in 1926, Robert Vickrey graduated from the Pomfret School, then studied at Wesleyan University, received a Bachelor of Arts degree from Yale University in 1947 and a Bachelor of Fine Arts degree from the Yale School of Fine Arts in 1950.^[2] His works are in the collections of the Metropolitan Museum of Art, the Whitney Museum of American Art, the Brooklyn Museum in New York, the Corcoran Gallery of Art, and The Museum of Modern Art, Rio de Janeiro.

Vickrey received the Gerard Manley Hopkins Award for Excellence in the Arts from Fairfield University and the Regina A. Quick Center for the Arts in March 2009 where a retrospective exhibition of Vickrey's paintings from 1951-2007 was held at the Thomas J. Walsh Art Gallery. The award and exhibition coincided with the publication of "Robert Vickrey: The Magic of Realism," written by Dr. Philip Eliasoph, a Fairfield University professor of art history.^[3] Vickrey died in Naples, Florida on April 17, 2011. He was 84.

Sources[link]

• Robert Vickrey and Diane Cochran, New Techniques in Egg Tempera, Watson Guptill Publications, New York 1973. ISBN 0-8230-3170-5
• Philip Eliasoph, Robert Vickrey: The Magic of Realism, Hudson Hills Press (February 2009). ISBN 978-1-55595-292-1

See also[link]

• Andrew Wyeth
• Egg Tempera

References[link]

This article about a painter from the United States born in the 1920s is a stub. You can help Wikipedia by expanding it. v t e

This Massachusetts-related article is a stub. You can help Wikipedia by expanding it. v t e

Paul Robert Milgrom (born April 20, 1948 in Detroit, Michigan) is an American economist. He is the Shirley and Leonard Ely Professor of Humanities and Sciences at Stanford University, a position he has held since 1987. Dr. Milgrom is an expert in game theory, specifically auction theory and pricing strategies. He is also the co-creator of the no-trade theorem with Nancy Stokey, and the co-founder of several companies, the most recent of which, Auctionomics^[1], provides software and services that create efficient markets for complex commercial auctions and exchanges.

Biography[link]

Paul Milgrom^[2] was born on April 20, 1948 in Detroit, Michigan. He graduated from the University of Michigan in 1970 with an A.B. with high honors in mathematics. In 1975 he enrolled for graduate studies at Stanford University, where he earned an M.S. in statistics in 1978 and a Ph.D. in business in 1979. His thesis advisor, Robert B. Wilson, would later become his collaborator in designing the spectrum auction used by the Federal Communications Commission.

After earning his Ph.D., Milgrom went to teach at Northwestern University, where he stayed from 1979 to 1983. From 1982 to 1987 he was a professor of economics and management at Yale University. In 1987 Milgrom returned as an economics professor to his alma mater, Stanford University, where he is currently the Shirley and Leonard Ely Professor of Humanities and Sciences. He was the doctoral thesis advisor for several students, notably John Bates Clark Medal winner Susan Athey.

Paul Milgrom held editorial positions at various prestigious journals, including the American Economic Review, Econometrica and the Journal of Economic Theory, and has been a fellow of the Econometric Society since 1984. In 1996, he gave the Nobel Prize memorial lecture^[3] honoring Nobel prize in economics laureate William Vickrey, who had died three days after the prize announcement. In 2006, Milgrom was elected in the National Academy of Sciences.

Paul Milgrom won the Erwin Plein Nemmers Prize in Economics in 2008. He won that prize "for contributions dramatically expanding the understanding of the role of information and incentives in a variety of settings, including auctions, the theory of the firm, and oligopolistic markets."

He is married to Eva Meyersson Milgrom and has two children, Josh Thurston-Milgrom and Elana Thurston-Milgrom.

Selected publications[link]

• Milgrom, Paul (1979). The Structure of Information in Competitive Bidding. New York: Garland Press.  (Ph.D. Dissertation)
• Milgrom, Paul (1979). "A Convergence Theorem for Competitive Bidding with Differential Information". Econometrica (Econometrica, Vol. 47, No. 3) 47 (3): 679–88. DOI:10.2307/1910414. JSTOR 1910414. 
• Milgrom, Paul (1981). "Good News and Bad News: Representation Theorems and Applications". Bell Journal of Economics (The Bell Journal of Economics, Vol. 12, No. 2) 12 (2): 380–91. DOI:10.2307/3003562. JSTOR 3003562. 
• Milgrom, Paul and John Roberts (1982). "Limit Pricing and Entry Under Incomplete Information: An Equilibrium Analysis". Econometrica (Econometrica, Vol. 50, No. 2) 50 (2): 443–59. DOI:10.2307/1912637. JSTOR 1912637. 
• Milgrom, Paul and John Roberts (1982). "Predation, Reputation, and Entry Deterrence". Journal of Economic Theory 27 (2): 280–312. DOI:10.1016/0022-0531(82)90031-X. 
• Milgrom, Paul and John Roberts (1990). "The Economics of Modern Manufacturing: Technology, Strategy and Organization". American Economic Review 80 (3): 511–28. 
• Milgrom, Paul and Nancy Stokey (1982). "Information, Trade and Common Knowledge". Journal of Economic Theory 26: 17–27. DOI:10.1016/0022-0531(82)90046-1. 
• Milgrom, Paul and Robert Weber (1982). "The Value of Information in a Sealed Bid Auction". Journal of Mathematical Economics 10: 105–14. DOI:10.1016/0304-4068(82)90008-8. 
• Milgrom, Paul and Robert Weber (1982). "A Theory of Auctions and Competitive Bidding". Econometrica (Econometrica, Vol. 50, No. 5) 50 (5): 1089–1122. DOI:10.2307/1911865. JSTOR 1911865. 
• Milgrom, Paul and Robert Weber (1985). "Distributional Strategies for Games with Incomplete Information". Mathematics of Operations Research 10 (4): 619–32. DOI:10.1287/moor.10.4.619. 
• Milgrom, Paul (2004). Putting Auction Theory to Work. Cambridge University Press. ISBN 0-521-53672-3. 

References[link]

1. ^ Auctionomics
2. ^ Curriculum Vitae
3. ^ Procuring Universal Service: Putting Auction Theory to Work, in Le Prix Nobel: The Nobel Prizes, 1996, Nobel Foundation, 1997, 382-392

External links[link]

• Personal web page