2023 Theses Doctoral

# Bayesian Auction Design and Approximation

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.

## Subjects

## Files

- 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
- Degree
- Ph.D., Columbia University
- Published Here
- June 28, 2023