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.
| Identifer | oai:union.ndltd.org:columbia.edu/oai:academiccommons.columbia.edu:10.7916/xg48-wn33 |
| Date | January 2023 |
| Creators | Jin, Yaonan |
| Source Sets | Columbia University |
| Language | English |
| Detected Language | English |
| Type | Theses |
Page generated in 0.0021 seconds