OPIM Professor Robert Day’s Combinatorial Auction Algorithm Employed Throughout Europe, Canada in Billion-Dollar Bidding Deals
When the Canadian government wanted to apportion mobile broadband services in February 2014—so that there would be plenty of cell-phone coverage, competitive prices and more provider options nationwide—it used an algorithm devised by UConn Business Professor Bob Day and his colleagues.
Day, a professor of Operations and Information Management in the School of Business, is an expert in combinatorial auctions. His services have been called upon by the governments in Canada and England, who have collected over $8 billion in auction revenues for just two projects he worked on in 2013 and 2014.
Combinatorial auctions are different from traditional auctions in which a single item is auctioned to the highest bidder. During combinatorial auctions, bidders are allowed to bid on a combination of items, such as telecommunications rights in multiple regions or multiple frequency ranges. In these auctions, some items are substitutes and some are complementary, and the combinations of interest may change during the course of a multi-tiered process.
By allowing bidders to state their preferences for combinations, it allows them to more accurately express their preferred packages. But, as the number of items for auction increase, the number of combinations for which people can bid also increases exponentially, causing a computational problem for the auctioneer, who has a tremendous amount of data to process. And that’s where Day’s algorithmic expertise comes into play.
In the past, the bidders were limited in the number of bundles they could bid on or were forced to bid on items individually. But Day and his colleagues looked at the problems from a different viewpoint, devising bidding systems in which bidders can submit bids detailing their preferences over potentially any bundle. Day helped to establish a multi-stage auction, including a multi-round ascending auction to enhance price-discovery, followed by two sealed-bid phases used to determine the winning amounts and specific assignment of winners to frequencies.
One big issue is trying to get people to tell the truth about what packages they want and what they’ll be willing to pay. While it is impossible to devise a system that cannot be manipulated, Day and his research co-authors, including S. Raghavan and Peter Cramton, of the University of Maryland, and Paul Milgrom of Stanford University, were able to create a system to minimize the effect of strategic manipulation, such as bid reduction, collusive bidding, or false-name bidding.
In a single-item auction, the winning bidder could be asked to pay the price submitted by the runner up, leaving her no strategy better than telling the truth. But adapting this idea for auctions with bids on combinations proved tricky, and it took years of research to come up with rules that made sense and algorithms to support the rules. The result is what is now known as a “core-selecting” combinatorial auction, which is part of the larger framework called the “combinatorial clock auction.”
Many industries, including electricity and telecommunications, now use combinatorial auctions involving the sale of assets or contracts worth billions of dollars.
“It’s a cutting-edge way for governments to interact with business,” said Day, who has been fascinated by this field since he wrote his dissertation on it 11 years ago. “You can’t have a free-for-all with everyone grabbing for the spectrum they want. We were able to regulate good outcomes and at the smallest rates possible to keep everyone happy. Importantly, we were able to use the auction mechanism to ensure an adequate number of winners in a region. So, in all but the most desolate part of Canada, for example, consumers will have four different choices for cell-phone coverage. At the same time, one company was able to win a large swath of prime spectrum across the nation, allowing that company to roll out a plan to stream hockey games to customers’ phones. Both the big guys and the small guys came away feeling like winners.”
While Day himself has only been an adviser for a few countries, the idea has taken off worldwide, with core-selecting auction rules used in recent auctions in the United Kingdom, the Netherlands, Denmark, Ireland, Switzerland, Australia, Austria, Slovenia, Canada and Slovakia. The auctions are vast, with revenues totaling around $19.5 billion for auctions conducted in 2012 through 2014 alone.
“I’ve gotten invited by governments to do these,” Day said. “The pricing we do is a safety feature that keeps auction revenue from going too low. Discounts from the bid amounts are used to encourage truthful bidding, but without the safety net of core-constraints, the prices could get absurdly low.”
“We also limited the size that the big guys could win. Then the market decides who can buy and at what price,” he said. “We were able to help the governments get what they want, and the algorithms we developed were faster and more precise than any predecessor. It’s something I’m proud of, to be one of the many people who helped resolve these issues and thus to impact the lives of so many.”
