- Exploring Fine-Grained Buy-Many Mechanisms
- Project Year:
2022
- REU Student (s):
Vikram Kher | University of Southern California CA
| George Li | University of Maryland-College Park MD
- Student 1 Institution:
University of Southern California
- Student 2 Institution:
University of Maryland-College Park
- Project Mentor:
Ariel Schvartzman
- Project Mentor Area:
DIMACS
- Project Abstract:
Multi-item revenue-optimal mechanisms are known to be extremely complex, often offering buyers randomized lotteries of goods. In the standard buy-one model it is known that optimal mechanisms can yield revenue infinitely higher than that of any "simple" mechanism, even for the case of just two items and a single buyer.We build off of the manuscript of Assadi and Schvartzman, who first defined the notion buy-$k$ mechanisms, which smoothly interpolate between the classical buy-one mechanisms and the recently studied buy-many mechanisms. Buy-$k$ mechanisms allow the buyer to buy up to $k$ many menu options. Our main results are that the revenue gap with respect to bundling, an extremely simple mechanism, is bounded by O(2n·n2) for any arbitrarily correlated distribution D over $n$ items for the case of buyer's with arbitrary monotone valuations. This is a generalization of the known O(n2) bound for additive valuations. In addition to this, we also conjecture that there exists a distribution D over two items such that Buy(k)Rev(D) > Buy(k+1)Rev(D). We make partial progress towards proving this conjecture by providing a candidate distribution D and a candidate optimal mechanism Mk which we believe witnesses such a gap.
