Return to search

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.

Identiferoai:union.ndltd.org:columbia.edu/oai:academiccommons.columbia.edu:10.7916/xg48-wn33
Date January 2023
CreatorsJin, Yaonan
Source SetsColumbia University
LanguageEnglish
Detected LanguageEnglish
TypeTheses

Page generated in 0.0021 seconds