Thirteen Reasons Why the Vickrey-Clarke-Groves Process is Not Practical April 17, 2007
Posted by Michael Trick in : Auctions 2007 , trackbackIn the March - April 2007 issue of Operations Research, Michael Rothkopf of Rutgers University argues that the well-known Vickrey-Clarke-Groves process for auctions is not practical. The abstract reads:
In theory, the mathematically elegant Vickrey-Clarke-Groves process offers perfect efficiency with dominant truth-revealing strategies. However, it has many serious practical problems. This paper describes these problems and argues that research that aims to maintain the dominant truth-revealing strategies while compromising on the other practical issues is of limited practical value.
Rothkopf goes on to discuss thirteen reasons for this limited value. These are
- the fact that the dominant strategy equilibrium is a weak equilibrium and there may exist alternative weak equilibria,
- the nonexistence of dominant strategy equilibria in models that include reasonable bid preparation costs,
- the exponential growth of effort related to bid preparation and bid communication,
- the NP completeness of the winner determination problem,
- problems related to capital limited bidders,
- problems associated with the disclosure of valuable confidential information,
- problems associated with various kinds of cheating including
- false bids by the bid taker,
- conspiracies by competing bidders,
- conspiracies in two-sided markets between bidders offering to sell and those offering to buy,
- and the use of false name bids by single bidders,
- the fact that strategies in sequences of strategy-proof auctions may not be strategy-proof,
- and the fact that the process can be revenue deficient.
You can find the entire article here.
The editors of Operations Research have invited three researchers to provide commentary on this paper:
- John Ledyard of California Institute of Technology. John O. Ledyard is Alan and Lenabelle Davis Professor of Economics and Social Sciences at Caltech. He has been a Fellow of the Econometric Society since 1977, a Fellow of the American Academy of Arts and Sciences since 1999, and a Fellow of the Public Choice Society since 2004. His research is in mechanism design with applications in the development of computer-assisted markets for trading pollution rights, managing resources for spacecraft and instrument design, acquiring logistics contracts, swapping portfolios of thinly traded securities, and prediction markets. In his commentary, John writes:
It is good to see a significant expansion of the few issues that Ted Groves tried to raise in 1977 about what are now known as VCG mechanisms. My comments here are intended to reinforce Professor Rothkopf’s point that “research that aims to maintain the dominant truth-revealing strategies while compromising on the other practical issues is of limited practical value” and to challenge the computer science community to redirect its focus to tackle a deeper problem.
It is, or should be, well-known that VCG mechanisms are at most second-best mechanisms. Ted Groves and I emphasized this, in the context of mechanisms for public good allocations, by pointing out that even though majority rule often produces inefficient allocations, everyone could still better off than if a VCG mechanism were used because the private good was not wasted under majority rule. When VCG is used for auctions, this feature can produce significantly low revenues – reason 13, revenue deficiency, in the article. It is theoretically impossible to use a VCG mechanism and get a first-best allocation. We need to give up the search for the impossible, by relaxing the requirement of dominant strategies and turning to finding the best of the possible.
See Prof. Ledyard’s full commentary.
- P.J. Healy of the Ohio State University. Paul J. Healy is an assistant professor of economics in the Department of Economics at the Ohio State University and in the Tepper School of Business at Carnegie Mellon University. His research interests include game theory, microeconomic theory, mechanism design, predictions markets, and public goods problems, and he specializes in both theoretical and experimental methodologies. He has published (or has forthcoming papers) in The American Economic Review, Journal of Economic Theory, Journal of Economic Behavior & Organization, and Experimental Economics. In his commentary, P.J. writes:
Whenever a research topic which has developed in one field spreads to new disciplines, there is the potential benefit of new perspectives and new tools opening unexplored avenues, and there is the potential danger of re-learning the old lessons of the originating discipline. The spread of auction theory and, more generally, mechanism design to computer science, operations research, and related fields is certainly no exception.
On one hand, important practical issues such as the computability of equilibria have long been ignored by the economics profession. On the other hand, computer scientists and operations researchers have focused almost exclusively on the dominant strategy mechanisms developed in the 1970s with no attention to the vast and elegant implementation literature of the 1980s and 1990s, much of which was developed with the
focus of finding continually better mechanisms. Fortunately, cross-disciplinary discussions such as this can help both sides reap the benefits of progress without incurring the costs of repetition. My hope is that Michael Rothkopf’s critique of the VCG mechanism will lead non-economists interested in mechanism design to explore the implementation literature and to use new tools to generate additional useful insights.See Prof. Healy’s full commentary.
- Karla Hoffman of George Mason University. Karla L. Hoffman is a Professor in the Systems Engineering and Operations Research Department of the School of Information Technology and Engineering of George Mason University where she had been Chair for five years ending in 2001. In 1984, she was awarded the Applied Research Award of the National Bureau of Standards for her research in solving large combinatorial optimization problems. The same year, she received the Commerce Department Silver Medal Award for meritorious service. Dr. Hoffman was President of the Institute for Operations Research and the Management Sciences (INFORMS) in 1999. She consultants to the FCC on auction design and testing for package-bidding auctions. Her research focuses on the development of new algorithms for solving large modeling problems arising in industry. In her commentary, Prof. Hoffman writes:
The use of auctions to trade goods and services is pervasive and growing. With the need to handle the complex problem of selling or buying multiple items simultaneously, the study of combinatorial auction designs has became a thriving research area for experimental economists, optimizers, game theorists, psychologists, and sociologists. The mathematically elegant Vickrey-Clark-Groves design has been at the heart of this research. However, as Rothkopf states, the VCG design has rarely been used. Rothkopf describes why the design is impractical and argues that “research that aims to maintain the dominant truth-telling strategies while compromising on the other practical issues is of limited practical value”. I agree with Rothkopf that participants in auctions have conflicting goals, and it is sometimes impossible to develop an auction design that can achieve all of these goals simultaneously. Tradeoffs must therefore be made in the choice of a design based on the characteristics that are best for the given situation. Auction design choices are likely to be application-specific, based on market competition, the type of bidders who will be participating , the likelihood that the auction will repeat periodically, the value of the goods being offered, and many other factors.
In this short comment I would like to expand on Rothkopf’s discussion by listing a collection of goals that we seek to achieve with combinatorial auctions and then list some of the auction design choices that can impact the auction’s performance. I encourage others to add to these lists, as I am certain that I have overlooked important issues.
See Prof. Hoffman’s full commentary.
Professor Rothkopf has provided an initial response to the comment of Profs. Healy and Ledyard.
First of all, I want to thank both John Ledyard and Paul Healy for the kind comments they have made about the paper. I appreciate that both of them realized that, in spite of my not being explicit about, it my paper was talking about Vickrey-Clarke-Grove auctions, and not necessarily broader uses of the process. I also thank both of them for pointing out additional references on related topics that may be of interest to readers of the original paper and for enriching the paper’s discussion of the auction theory literature in economics. Professor Healy’s discussion of experimental economics is welcome. In addition to laboratory experiments, he might have mentioned field experiments such as Lucking-Reiley 1999, which can shed light on revenue, if not efficiency, in real markets.
I am unconvinced by Professor Healy’s suggestion that the presence of alternative equilibria to the dominant, but weak, equilibrium of the Vickrey-Clarke-Groves process is not usually important because in laboratory experiments when bidders used alternative strategies the resulting allocation of goods was usually the efficient allocation. The reason I am unconvinced is that these alternative bids can lead to much lower revenue for the bid taker. Their presence contributes to bid takers’ reluctance to use the process.
I agree with Professor Healy that there are both potential benefits and potential dangers when a research topic that has developed in one field spreads to other disciplines. However, unlike computer science, operations research is not a newcomer to the study of auctions. As far as I know, the first academic paper on auctions is Friedman 1956, based upon the work in the first doctoral dissertation in operations research, Friedman 1957. The first common value models were published in Management Science (Rothkopf 1969 and Wilson 1969), and the winner’s curse is first discussed in the academic literature by Capen et al, 1971, not by an economist.It is good to see that both Professor Healy and, particularly, Professor Ledyard see moving auction theory towards practicality as a worthwhile goal. It is a goal that I believe to be important and one I have been arguing for explicitly for a long time (Rothkopf, Teisberg and Kahn 1990, Rothkopf 1991, Rothkopf and Harstad 1994). In my view, much recent work in microeconomics is driven by the theoretical power and beauty of game theory to the exclusion of practical concerns, and this is detrimental to it. Some economists see this as a serious issue. For example, in his entry in Who’s Who in Economics, Robert Wilson wrote, “The fine structure of markets is poorly modeled in my view, and the theory barely conveys the richness of practice; this would be fine if the theory captured the main features but actually it misses essentials. The challenge is more often the right formulation than the analysis. … The reliance of game theory on assumed common knowledge and perfect ‘rationality’ is an analytic strength and a practical deficiency.”
References
Capen, Edward, Robert Clapp and William Campbell, 1971, “Competitive Bidding in High Risk Situations,” Journal of Petroleum Technology 23, pp. 641-653.
Friedman, Lawrence, 1956, “A Competitive Bidding Strategy,” Operations Research 4, pp. 104-112.
Friedman, Lawrence, 1957, “Competitive Bidding Strategies,” PhD Dissertation, Case Institute of Technology, Cleveland Ohio.
Lucking-Reiley, David, “Using Field Experiments to Test Equivalence Between Auction Formats: Magic on the Internet” American Economic Review 89, December 1999, pp.1063-1080.
Rothkopf, Michael H., 1969, “A Model of Rational Competitive Bidding,” Management Science 15, pp. 362-373.
Rothkopf, Michael H., 1991, “On Auctions with Withdrawable Winning Bids,” Marketing Science 10, pp. 40-57.
Rothkopf, Michael H., 1994, and Ronald Harstad, “Modeling Competitive Bidding: A Critical Essay,” Management Science 40, pp. 364-384.
Rothkopf, Michael H., Thomas J. Teisberg and Edward P. Kahn, 1990, “Why Are Vickrey Auctions Rare?,” Journal of Political Economy 98, pp. 94-109.
Wilson, Robert B., 1969, “Competitive Bidding with Disparate Information,” Management Science 15, pp. 446-448.
Wilson, Robert B, 1999, in Who’s Who in Economics, 3rd edition, M. Blaug, ed., Edward Elgar, p. 1178.
Regarding the commentary from Prof. Hoffman (received after the other two commentaries), Prof Rothkopf agrees with her focus, and notes that the papers Rothkopf and Park, “An Elementary Introduction to Auctions”, Interfaces, 31(6), pp 83-97 (2001) and Pekec and Rothkopf, “Combinatorial Auction Design”, Management Science, 49, pp 1485-1503 (2003) are relevant in developing a list of issues to consider in auction design.
We now welcome more general comments on the paper, the commentary, and the general issue of auctions. Follow or add to the discussion!
Comments
Professor Rothkopf is correct; other Nash equilibria of the VCG auction, though still efficient, can lead to different revenue levels for the seller. For an efficiency-minded economist it doesn’t matter who pays what to whom, as long as the object goes to the bidder with the highest value. But to a seller choosing the auction format, expected revenue is obviously a big deal, and this will impact the choice of auction format.
Note, however, that revenue may go either way here: there are also Nash equilibria that lead to higher revenues than the dominant strategy equilibrium (for example, the high-value bidder bids his value v and everyone else bids a penny less than v; also, see Andreas Blume’s papers characterizing all Nash equilibria of VCG auctions). So, we’re back to the age-old equilibrium selection problem, and running experiments (laboratory or field) seems to be the sensible approach to figure out what revenue sellers should really expect.