Settling the Efficiency of the First-Price Auction

Speaker 

Dr. Pinyan Lu is a professor and the founding director of Institute for Theoretical Computer Science at Shanghai University of Finance and Economics (ITCS@SUFE).

Before joining SUFE, he spent seven years as a researcher at Microsoft Research. He studied in Tsinghua University (BS (2005) and PhD (2009) both in Computer Science).

He is interested in theoretical computer science, including complexity theory, algorithms design and algorithmic game theory. Currently, his research is mainly focused on complexity and approximability of counting problems, and algorithmic mechanism design.

Pinyan Lu is the recipient of a number of awards including ICCM Silver Medal of Mathematics, Distinguished Membership of ACM and CCF, CCF Young Scientist award, Best Paper Award from ICALP 2007, FAW 2010, ISAAC 2010 and so on. He is the PC chairs for FAW-AAIM 2012, WINE 2017, FAW 2018, ISAAC 2019 and so on, and PC members for STOC, FOCS, SODA and a dozen of international conferences. He is an Editorial Board Member of the “Information and Computation” and "Theoretical Computer Science".

Abstract

First-price auction is one of the most widely used auction format. However, the efficiency of its equilibria has been a long-standing open question since Nobel Laureate Vickrey initiated auction theory in 1961. In this talk, I will report our recent work which settles this open question. In particular, we prove a tight price of anarchy (PoA) of 1-1/e^2 for first-price auction.