Abstract
A lot of effort has been dedicated by computer scientists and economists to designing Bayesian auctions that generate good revenue. In such auctions, the seller is assumed to know the players’ value distributions, and approximately optimal Bayesian mechanisms have been designed under this assumption. However, most existing studies do not consider the complexity for the seller to carry out the mechanism. It is implicitly assumed that the seller has access to “each single bit” of the distributions and is able to optimize perfectly based on the entire distributions, which may not be realistic when the value distributions have exponentially large supports or do not have succinct representations. In this work, we only allow the seller to have limited oracle accesses to the players’ value distributions, and consider the query complexity needed for a Bayesian mechanism to generate good revenue. For a large class of valuation functions, we prove logarithmic lower-bounds for the query complexity in order for any Bayesian mechanism to be a constant approximation to the optimal revenue. For single-good auctions, unit-demand auctions and additive auctions, we prove almost matching upper-bounds for the query complexity by constructing efficient Bayesian mechanisms.Time
2017-05-24 14:00 ~ 15:00Speaker
Jing Chen, Stony Brook UniversityRoom
Room 308,School of Information Management & Engineering, Shanghai University of Finance & Economics
