Computer science tackles 30-year-old economics problem

June 25, 2012, Massachusetts Institute of Technology
Computer science tackles 30-year-old economics problem
In economists' jargon, an "auction" is any market that involves a single seller and a group of buyers. In some auctions, the seller has information about the populations from which the buyers are drawn — as at a movie theater, which can ask its customers to produce student IDs or senior-citizen cards.

In 2007, the University of Chicago's Roger Myerson won the Nobel Memorial Prize in Economic Sciences — in part for research he had published, in 1981, on auction design. Using the tools of game theory, Myerson showed how to structure an auction for a single item such that if all the bidders adopted the bidding strategies in their best interest, the auctioneer would realize the greatest profit.

Myerson's work immediately raised a related question: What's the best way to organize an auction in which bidders are competing for multiple items? That question has stood for 30 years, but MIT computer scientists believe that they have now answered it. In a pair of recent papers, Constantinos Daskalakis, the X-Window Consortium Assistant Professor of Computer Science and Engineering at MIT, and his students Yang Cai and Matthew Weinberg describe an algorithm for finding an almost-perfect approximation of the optimal design of a multi-item auction. The first of the papers was presented at the Association for Computing Machinery's 44th Symposium on Theory of Computing in May; the second is yet unpublished but has been posted online.

In economists' jargon, an auction is any market that involves a single seller and a group of buyers. An art auction at Christie's counts as an auction, but so does the sale of tickets at a movie theater. The movie theater just happens to be running a particular kind of auction called a fixed-price auction.

At a Christie's auction, the auctioneer may not know much about individual bidders: The guy in jeans and a T-shirt could be the agent of a billionaire. But in other types of auctions, the seller has information about the populations from which buyers are drawn. The movie theater, for instance, could check customers for student IDs or senior-citizen cards before offering them a discounted rate. Figuring out how to extract the maximum amount of money from people with differing abilities to pay is one of the things that makes auction analysis so complex.

According to Daskalakis, the difficulty of finding the optimal multi-item auction suggests that it "has such large complexity that there's no succinct description that gives you the optimal outcome." To maximize revenue, the auctioneer might have to agree to sell an item at some fraction of the highest bid, a fraction that could depend on a host of factors: the difference between the top two bids, the final price of the previous item on the docket, the populations from which the bidders are drawn. "Maybe it's a long laundry list of allocation rules of what you have to do for every possible set of bids," Daskalakis says.

The solution

But the MIT researchers were able to show that while the optimal auction might be enormously complicated, it can be described as a probabilistic combination of simple auctions. To explain the basic idea, Daskalakis draws the analogy of three points that define an equilateral triangle. A point in the center of the triangle, Daskalakis says, could be thought of as 33 percent the point at the top of the triangle, 33 percent the bottom right corner and 33 percent the bottom left corner.

"Our result basically hinges on the fact that we view this auction-design problem as a geometric problem," Daskalakis says. "And our auctions lie inside complicated shapes whose corners are simple things." In particular, the "corners" are so-called Vickrey–Clarke–Groves (VCG) auctions, one of whose inventors, William Vickrey, won the Nobel Prize 11 years before Myerson did.

What that means in practice, however, is that the auctioneer doesn't have to keep track of a complicated set of rules. After the bidders have submitted their bids, the auctioneer randomly chooses one of the VCG auctions — the "corners" — and uses its relatively simple rules to allocate the items in the docket.

"Every randomized algorithm is by definition a distribution over deterministic algorithms, so the crucial thing here is not that," Daskalakis says. "The crucial thing is understanding what deterministic algorithms are in this decomposition. And the important aspect of the result is that the algorithms in this decomposition happen to be of a very simple form — VCG auctions." When the MIT researchers began their analysis, they had no idea what those algorithms would turn out to be. "It is remarkable that they are of this type," Daskalakis says.

In the type of VCG auctions the researchers use, bids are modified according to the populations from which the bidders are drawn: Affluent bidders might see their bids cut in half; middle-income bidders might see theirs boosted by 20 percent. The items in the docket are then allocated according to the modified bids — not the actual bids. The difference between the VCG auctions in one of the researchers' decompositions is simply the numerical values of the modifications.

Lose to win

It may seem counterintuitive that awarding an item to the lower bidder — as could happen with modified bids — will increase the auctioneer's revenue, but the movie-theater example helps explain why. A movie theater that sells student tickets for $5 and nonstudent tickets for $10 is, in effect, modifying its customers' bids according to their ability to pay — boosting the students' $5 bids so that they're commensurate with the nonstudents' $10 bids. But the theater's motives aren't altruistic: By using a tiered pricing model, it makes more money. It may lose the business of a couple nonstudents who would have been happy to pay $5 — or $8 — but not $10, and it may undercharge a few students who would have been happy to pay $10. But overall, it does better business than it would if it had charged everyone the same flat rate.

Technically, Daskalakis and his students' recent research is in the field of mechanism design. A single-item auction is an example of what's called a single-dimension mechanism; a multi-item , on the other hand, is a multidimensional mechanism. "Multidimensional mechanism design is accepted to be the big open problem of the whole mechanism-design community, in both computer science and economics," says Éva Tardos, the Jacob Gould Schurman Professor of Computer Science at Cornell University and the most recent recipient of the Gödel Prize for theoretical . "This sequence of papers by Costis and his students is making one of the biggest contributions — or maybe the biggest contribution — in a long, long time."

In the traditional theoretical framework for multi-item auctions, "When there are N bidders involved, and they all can possibly have high or low values or maybe multiple kinds of different values, then you end up with a variable for every possible combination of which bidder has which kind of value," Tardos explains. "Because of the number of variables involved, the size of these programs, it was not usable at all. And they turn it into a usable framework, which is very beautiful."

Explore further: eBay Mind Games

Related Stories

eBay Mind Games

December 11, 2009

Psychologists have long known that when two people haggle over a price, it pays for the seller to start high.

You can look -- but don't touch

January 7, 2009

Consumers are often told that if they break an item, they buy it. But a new study suggests that if they just touch an item for more than a few seconds, they may also end up buying it.

Icahn, Dish, debtholders vie for Blockbuster

April 5, 2011

(AP) -- Billionaire investor Carl Icahn, Dish Network and a group of debtholders are the three remaining bidders for movie-rental chain Blockbuster in an auction Tuesday at U.S. Bankruptcy Court in New York.

Recommended for you

Oldest evidence for animals found

October 15, 2018

Researchers at the University of California, Riverside, have found the oldest clue yet of animal life, dating back at least 100 million years before the famous Cambrian explosion of animal fossils.


Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.