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 will appear at the IEEE Symposium on Foundations of Computer Science in October.
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 auction, 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 computer science. "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."
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 will appear at the IEEE Symposium on Foundations of Computer Science in October.
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 auction, 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 computer science. "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."
