Author: Edward Rothberg, PhD
Date: 2/24/2021
You may have heard the news that two American economists – Paul Milgrom and Robert Wilson – recently won the 2020 Nobel Prize in Economic Sciences “for improvements to auction theory and inventions of new auction formats.” The prize committee highlighted the fact that their work has resulted in “practical applications, which have spread globally” and “benefitted sellers, buyers and taxpayers around the world.”
Indeed, Milgrom and Wilson’s work has spurred numerous real-world auction applications across various industries including telecommunications and media. Their “best-known contribution,” in the eyes of the prize committee, is the auction they designed in the early 1990s that enables the U.S. government’s Federal Communications Commission (FCC) to sell radio frequencies to telecom operators. This incredibly complex spectrum allocation auction can be classified as a “combinatorial auction” problem — and this type of problem is typically solved using mathematical optimization techniques and technologies.
This mathematical optimization-based approach to auctioning radio frequencies is now utilized around the world by the regulatory agencies of various countries and has had a tremendous economic impact. In 2016, for instance, the FCC (using Milgrom and Wilson’s framework) conducted a combinatorial auction, which deployed a mathematical optimization solver (my company’s Gurobi Optimizer) to determine the best way to repurpose radio spectrum from broadcast television to wireless internet and generated nearly $20 billion in revenue — $7.3 billion of which went to the U.S. Treasury to reduce the federal deficit.
As a mathematical optimization software developer, I am proud of the part that this AI technology played in Milgrom and Wilson’s Nobel Prize-winning work. And this is not the first time mathematical optimization has had a hand in winning this prestigious award. Leonid Kantorovich and Tjalling Koopmans, for example, shared the Nobel Prize in Economics in 1975 for their contributions to optimal resource allocation, and Harry Markowitz received the award in 1990 for his work on optimal financial portfolio design.
With a history stretching back over 70 years, mathematical optimization has proven to be very effective in addressing some of the most challenging, high-stakes problems in the business world.
In this article, I will take a closer look at the combinatorial auction problem and explain what makes it so complex before exploring how it appears in various industries.
Everyone is familiar with the format of a simple, standard auction: A group of buyers bids on a particular item that is listed by a seller at a certain starting price, and the buyer with the highest bid takes home the item.
But in a combinatorial auction, participants can bid on combinations or “packages” of interrelated items — and this is where the complexity comes in. As the number of items for sale increases, the number of possible combinations grows exponentially.
Let’s say, for example, you are tasked with auctioning off radio frequencies in different parts of a country. Even if you simplify the problem by putting a fixed price on each frequency (so that bidders just have to pick a set of frequencies to bid on), you are still faced with massive complexity. If you only have three radio frequencies, there are eight possible bidding combinations. If you have four radio frequencies, there are 16 possible combinations. By the time you reach 265 radio frequencies, the number of possible combinations is actually more than the number of atoms in the universe!
It’s impossible for the human brain to comb through the astronomical number of possible packages of items in a combinatorial auction and identify the best one. This problem (known as the “winner determination problem”) requires the power of a mathematical optimization solver to sift through all the possible allocations of items and figure out which combination of bids maximizes total revenue (while also meeting other business objectives).
Besides telecommunications, combinatorial auctions can be found in numerous other industries.
Perhaps the most common example is in industrial procurement. Many leading global corporations today – across various industries including manufacturing, construction and retail — employ a combinatorial auction approach (and deploy mathematical optimization technologies) to handle their procurement operations and drive their sourcing decisions.
Whenever a company puts out an RFP for a package of items (products or services), suppliers place bids on providing a combination of these items — and they can tailor their bid to take into account their capacity, supply, inventory and other constraints as well as economies of scale.
To evaluate all the possible combinations of bids and make the best sourcing decisions (while considering multiple factors besides price including quantity, technical specifications, lead times and location), the company putting out the RFP must be able to run a combinatorial auction (or, to be more precise, a reverse combinatorial auction). Using a mathematical optimization tool, they can determine which combination of bids and allocation of contracts will enable them to get the goods and services they need (when and where they need them) at the lowest possible cost.
Another established use case of combinatorial auctions is in the truck transport industry, where shippers forecast loads and invite carriers to bid for their business. The carriers submit bids on sets of routes, and the shippers figure out the best combination of bids (in terms of price, service levels, geographic areas and other factors) and award contracts accordingly.
It’s interesting to note that all the combinatorial auction examples highlighted above are ultimately “winner determination problems.” Mathematical optimization’s ability to tackle this and other problem types that crop up over and over again is one of the main reasons this AI technology is part and parcel of the business world.
Mathematical optimization’s role as a key technological tool that helped Milgrom and Wilson win this year’s Nobel Prize in Economics is proof of this profound and positive real-world impact.
This article was originally published on Forbes.com here.
GUROBI NEWSLETTER
Latest news and releases
Choose the evaluation license that fits you best, and start working with our Expert Team for technical guidance and support.
Request free trial hours, so you can see how quickly and easily a model can be solved on the cloud.