Why Your Phone Signal Won a Nobel Prize

IN 2020, Paul Milgrom won a Nobel Prize for inventing a new kind of auction. He’d already used it to help the US government raise $19.8 billion for the radio airwaves your phone signal runs on. He’s now designing an auction to help save a disappearing lake in Utah. He is also the Shirley and Leonard Ely Professor of Humanities and Sciences at Stanford.

We recently had the pleasure of interviewing him for The Confluence Journal.

The Confluence: Are there things you think should not be allocated by auctions or prices at all, even where a market would be efficient? Where do you draw that line?

Dr. Milgrom: In market design, there are lots of allocations where there are reasons not to use prices. We have kidney exchange, but the world is mostly unanimous that we don’t sell organs, giving highest priority to the kidney patients who can pay most. We don’t use money to assign students to oversubscribed courses, and mostly we don’t use money to allocate students among schools. We don’t use money to allocate food donations among food banks or to prioritize adoptions of children. Social norms that hopefully reflect sound human values determine the lines that we draw.

The Confluence: The FCC incentive auction had to buy spectrum back from broadcasters and sell it to mobile carriers at the same time. What was the hardest part of making that work in practice, as opposed to on paper?

Dr. Milgrom: Really, there were three things that were most challenging: two technical and one human.

The math problem:

On the technical side, the resource allocation had to satisfy 2.7 million constraints, which needed to be checked in real-time during the auction. A typical constraint would be “Don’t assign station X to channel A and station Y to channel B” (because their broadcast signals would interfere). We needed to check the possibility of assigning the given set of channels to whatever stations wanted to remain on-air. Verifying the possibility of that assignment is an NP-complete problem, so no algorithm exists that always gives a yes-or-no answer in any reasonable amount of time.

What made it “NP-complete”?

A problem is NP-complete when checking whether even one valid solution exists gets exponentially harder as the problem grows, which means that no algorithm can guarantee a fast yes-or-no answer. With 2.7 million interference constraints, brute-force checking wasn’t an option; Milgrom’s team had to build shortcuts that worked in practice, even without a guarantee they’d always work.

We created new algorithms and heuristics that could solve most of the problems we encountered within 60 seconds.

Also on the technical side, we needed to decide how many channels to try to clear, which depended both on what TV broadcasters demanded and on what mobile broadband providers were willing to pay. We had a new algorithm for that, too.

The human problem:

With such complex software running in the background processing bids and offers, how could anybody know how to bid? We needed an economic algorithm that made that feasible, which led eventually to Shengwu Li’s work about “obviously strategy-proof” mechanisms. The process needed to make it obvious to bidders, and we accomplished that.

What’s an “obviously strategy-proof” mechanism?

A market design where bidding honestly is not just the smart move, but visibly the smart move, which means a participant doesn’t need knowledge of game theory to work out that lying or gaming the system won’t help them. If bidders can’t tell what’s in their own interest, the auction fails regardless of how elegant its math is.

The Confluence: If you were asked to design a way to allocate a scarce public resource outside telecoms, such as carbon emission permits, water rights, or airport landing slots, which would you choose, and what would the main design challenge be?

Dr. Milgrom: I’m currently hoping to contribute an auction design to lease water rights to rescue the Great Salt Lake in Utah. Just as radio interference constraints made the purchase of TV broadcast rights challenging, hydrological constraints threaten to do the same in Utah. A farmer who fallows a field 100 miles from the Great Salt Lake does not supply the same amount of water as one who fallows a similar field 10 miles from the lake. Leakage, seepage, and evaporation all play roles, and water that seeps down into an aquifer in the basin is not necessarily lost in the same sense as water that evaporates.

I see my contribution as explaining to people that potentially very complex constraints can all be handled “under the hood” without adding any complexity for the participants. That is what it takes to make such an auction practical.

Why the Great Salt Lake?

Utah’s Great Salt Lake has lost roughly two-thirds of its surface area since the 1980s, mostly to upstream water diversion for farming. A shrinking lake exposes toxic dust on its dried bed and threatens the ecosystem millions of migratory birds depend on. An auction that pays farmers to leave water in the rivers can help us solve the worsening problem.

The Confluence: For a high school student who is curious about economics, what is one idea from auction theory or market design that you think everyone should understand?

Dr. Milgrom: After the basics of supply and demand, the next thing to understand is incentives. When you change the rules of a marketplace, you change behavior. Analyses that ignore that routinely make big mistakes leading to distorted, unfair, inefficient allocations.