Multiple Item Auctions
A team of researchers from MIT recently published their findings on the 30 year old problem of how to conduct a multiple item auction in a way that maximized the auctioneer’s profits. Multiple item auctions are especially tricky compared to single item auctions, in that there can be multiple winners. In a standard multiple item auction, the top n bidders, where n is the number of items being auctioned, pay x for each item, where x is the lowest bid among the top n bidders. In the case that there is a tie between two or more people who bid exactly x, people who bid earlier win. So if there are three items and the bids are (in order) 1, 1, 1, and 4, the first two people and the last person would be the winners, and they would each pay 1.
Until Constantinos Daskalakis, a professor at MIT, and his two students Yang Cai and Matthew Weinberg published their study on multiple item auctions, it was unknown what the optimal strategy for multiple item auctions was from the auctioneer’s perspective. As it turns out, the dominant strategy depends on a huge number of variables. Early models were absurdly complex due to the high number of variables, to the point where they were unusable. To determine the optimal strategy, the researchers from MIT constructed a model based on a probabilistic combination of simple auctions, including some of the same simple, one item auctions that were covered in class. They then applied a geometric approach to finding the solution to their system, in which different variables lead to different shapes with corners corresponding to different weights. More specifically, the corners of the complicated shapes are actually VCG auctions. VCG auctions are a bit complicated, but in practice they are rather similar to the second price auctions discussed in class, except they are then applied to multiple items at once.
Although dealing optimizing multiple VCG auctions is not easy, it is a welcome alternative to the incredibly complex algorithms that were in place before. Essentially what happens, is each bidder’s bid is modified based on several criteria. The most important of these criteria is the wealth of the bidders. Wealthier bidders have their bids modified to count for less, whereas those with less money have their bids modified to count for more. The winners of the auction are then determined by the modified values.
This seems a bit confusing, and perhaps counterintuitive, but it works well in practice. Consider one of the most common type of multiple item auction: ticket sales. Ticket sales are a fixed price auction, in that the seller sets the price which the buyer then accepts or rejects depending on the buyer’s valuation of the item. Although these seem different than the auctions covered in class, they behave in a similar manner. Movie theaters will often offer tickets for different prices to different people.
This follows the strategy detailed by the MIT researchers. Everyone is technically bidding for the same item, a movie ticket. People with less disposable income are charged less money for the same item everyone else is paying for. If done correctly, decreasing the cost for a select group of people will increase the number of tickets sold without decreasing the perceived value of the item for the general public, which in turn leads to increased profits for the theater.
Constantinos Daskalakis continues to study how to maximize revenue in multiple item markets, and his newest study was published today, September 16, 2014. It can be accessed here: http://arxiv.org/pdf/1409.4150.pdf
Original article describing multiple item markets: http://newsoffice.mit.edu/2012/comp-sci-econ-0625