ISYE Seminar Series with Paul Milgrom (Economics, Stanford)

Long-run Performance of Approximation Algorithms

Professor Milgrom and his team study investment incentives created by truthful mechanisms that allocate resources using approximation algorithms. Even for some high-performing ("FPTAS") approximation algorithms, when a bidder can invest before participating, its investment incentives may be so distorted that the net welfare performance is arbitrarily bad. An algorithm’s worst-case allocation and investment performance coincide if and only if a particular kind of externality is sufficiently small. The researchers introduce a new FPTAS for the knapsack problem that has no such negative externalities, so it is high-performing with and without investments.

About the Paul Milgrom
Paul Milgrom is the Ely Professor of Humanities and Sciences in the Department of Economics at Stanford University. He is the recipient of numerous awards, including the 2020 Sveriges Riksbank Prize, in Memory of Alfred Nobel, for “improvements to auction theory and invention of new auction methods.”

Milgrom is the author of two books about auction design, and his scholarly publications have more than 100,000 Google Scholar citations. He co-invented the two auction formats most commonly used for selling radio spectrum licenses in North America, Europe, Asia, and Australia, and the Auctionomics team that designed the U.S. Incentive Auction process which reallocated UHF-TV channels for use in mobile broadband.