Thirteen Reasons Why the Vickrey-Clarke-Groves Process is Not Practical

In 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:

Rothkopf goes on to discuss thirteen reasons for this limited value. These are

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.

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.