Theses Doctoral

Bayesian Auction Design and Approximation

Jin, Yaonan

We study two classes of problems within Algorithmic Economics: revenue guarantees of simple mechanisms, and social welfare guarantees of auctions. We develop new structural and algorithmic tools for addressing these problems, and obtain the following results:

In the ๐‘˜-unit model, four canonical mechanisms can be classified as: (i) the discriminating group, including Myerson Auction and Sequential Posted-Pricing, and (ii) the anonymous group, including Anonymous Reserve and Anonymous Pricing. We prove that any two mechanisms from the same group have an asymptotically tight revenue gap of 1 + ฮธ(1 /โˆš๐‘˜), while any two mechanisms from the different groups have an asymptotically tight revenue gap of ฮธ(log ๐‘˜).

In the single-item model, we prove a nearly-tight sample complexity of Anonymous Reserve for every value distribution family investigated in the literature: [0, 1]-bounded, [1, ๐ป]-bounded, regular, and monotone hazard rate (MHR).

Remarkably, the setting-specific sample complexity poly(๐œ–โปยน) depends on the precision ๐œ– โˆˆ (0, 1), but not on the number of bidders ๐‘› โ‰ฅ 1. Further, in the two bounded-support settings, our algorithm allows correlated value distributions. These are in sharp contrast to the previous (nearly-tight) sample complexity results on Myerson Auction.

In the single-item model, we prove that the tight Price of Anarchy/Stability for First Price Auctions are both PoA = PoS = 1 - 1/๐œ–ยฒ โ‰ˆ 0.8647.


  • thumnail for Jin_columbia_0054D_17876.pdf Jin_columbia_0054D_17876.pdf application/pdf 4.56 MB Download File

More About This Work

Academic Units
Computer Science
Thesis Advisors
Chen, Xi
Servedio, Rocco Anthony
Ph.D., Columbia University
Published Here
June 28, 2023