LIDS Seminar | Tim Roughgarden

"The Price of Anarchy in Markets for Lemons"

We study the worst-case equilibrium gains from trade in simple bilateral trade mechanisms with interdependent valuations. Equilibria in such settings are typically complex, as proposed prices can convey private information held by the proposer. Such equilibria suffer lost gains from trade both due to the inefficiency introduced by screening (as in independent private value settings) and due to adverse selection. We identify broad conditions under which, nevertheless, sequential equilibria are guaranteed to achieve a constant fraction of the first-best gains from trade. Our bounds quantify the central role of rare pessimistic seller signals and rare optimistic buyer signals. The results apply to seller-proposer, buyer-proposer, and random-proposer mechanisms. The key idea in our analysis is to reduce equilibrium gains from trade to proposer profits in an auxiliary market with independent private values.

Joint work with Naveen Durvasula.

Tim Roughgarden is a Professor in the School of Mathematics at the Institute for Advanced Study, on leave from the Computer Science Department at Columbia University. He is also the Founding Head of Research at a16z crypto. Prior to joining Columbia, he spent 15 years on the computer science faculty at Stanford, following a PhD at Cornell and a postdoc at UC Berkeley. His research interests include the many connections between computer science and economics, as well as the design, analysis, applications, and limitations of algorithms. For his research, he has been awarded the ACM Grace Murray Hopper Award, the Presidential Early Career Award for Scientists and Engineers (PECASE), the Kalai Prize in Computer Science and Game Theory, the Social Choice and Welfare Prize, the Mathematical Programming Society's Tucker Prize, the INFORMS Lanchester Prize, and the EATCS-SIGACT Gödel Prize. He was an invited speaker at the 2006 International Congress of Mathematicians and the Shapley Lecturer at the 2008 World Congress of the Game Theory Society. He is a Fellow of the Guggenheim Foundation, the ACM, the Game Theory Society, and the Society for the Advancement of Economic Theory, and a Member of the American Academy of Arts and Sciences. He has written or edited ten books and monographs, including Twenty Lectures on Algorithmic Game Theory (2016), Beyond the Worst-Case Analysis of Algorithms (2020), and the Algorithms Illuminated book series (2017-2022).