Eric Xue will present his General Exam "Settling the competition complexity of additive buyers over independent items" on May 15th, 2024 at 1:30pm in Friend 005. Committee members: Mark Braverman ( adviser), Matt Weinberg, and Huacheng Yu Abstract: Settling the competition complexity of additive buyers over independent items Committee: Mark Braverman, Matt Weinberg, Huacheng Yu Abstract: Auction design studies how to sell items to bidders in a way that incentives truthful participation. The goal of revenue maximization—as its name suggests—is to extract as much revenue as possible while doing so. In single-dimensional settings, e.g., selling a single item to multiple bidders, the seminal work of Myerson completely characterizes the revenue optimal auction, showing that it is structurally quite simple. In stark contrast, the revenue optimal auction for selling multiple items remains elusive, and for the settings that the literature understands, it has been shown that the revenue optimal auction can be extremely complex and deeply unintuitive. To circumvent this barrier, the literature has adopted two main approaches. The first is to approximate the revenue of the optimal auction via a simple auction, such as selling each item separately or posting a price on each item. This line of work has been fruitful, but there are times in practice when approximate revenue guarantees are not enough or it is costly to know the prior—the distribution from which bidders come—so that an auction which achieves these approximations can be designed. The resource augmentation approach addresses these concerns: this approach seeks to sell items in a prior-independent way but guarantee as much revenue as the optimal auction for the original set of bidders by recruiting sufficiently many additional bidders so that economic competition itself drives up revenue. For a given auction environment, the minimum number of bidders needed to do so is termed its competition complexity. We show that the competition complexity of selling m independent items to n additive bidders when m < n is precisely \Theta(\sqrt{nm}). More specifically, prior work demonstrated an O(\sqrt{nm}) upper bound on the competition complexity for this setting. We prove a matching \Omega(\sqrt{nm}) lower bound by explicitly constructing a Bayesian incentive compatible auction for selling m items to n additive bidders with values drawn iid from the Equal Revenue distribution truncated at \sqrt{nm} that obtains at least as much revenue as optimally selling each item separately to n + \Omega(\sqrt{nm}) bidders. Abstract & Reading List: [ https://docs.google.com/document/d/1VQ9_0ffiQGxtun3CaG5tdDbH_A15IX_XLx-JVXA-... | https://docs.google.com/document/d/1VQ9_0ffiQGxtun3CaG5tdDbH_A15IX_XLx-JVXA-... ]