ISyE Seminar Series: Paul Milgrom

"Long-run Performance of Approximation Algorithms"

Presentation by Paul Milgrom
Shirley and Leonard Ely Professor of Humanities and Sciences
Department of Economics, Stanford University, Palo Alto

3:30 pm - Seminar
4:30 pm - Reception, snacks and beverages

About the seminar:

We 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. We introduce a new FPTAS for the knapsack problem that has no such negative externalities, so it is high-performing with and without investments.

Bio:

Paul Milgrom is the Ely Professor of Humanities and Sciences in the Department of Economics at Stanford University and 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.” Paul 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.