General Information
| Student: | George Z. Li |
|---|---|
| Partner: | Vikram Kher |
| Mentor: | Ariel Schvartzman |
| School: | University of Maryland |
| E-mail: | gzli929 (@) umd (dot) edu |
| Project: | Fine Grained Buy Many Mechanisms |
Project Description
Designing simple and revenue-optimal auctions is known to be extremely complicated. Though simple and optimal auctions are known for the case of selling one item, the gap between simple and optimal auctions can be unbounded when selling just two items.
Weekly Log
- Week 1:
- For the first few days, Ariel gave all of his (6) students an introductory lecture on Mechanism Design to give us context for what our projects would contribute to. I had a bit of an idea what I was going to work on already, since I did some light reading before coming to the REU. In particular, we are working on a paper which Ariel and Sepehr have made a lot of progress on. I improved one of their approximation factors from O(n^3) to O(n^2) using some very trivial changes. This week, I also attended a talk on some obscure math thing which I understood very little of. On the brighter side, I joined the TCS reading group here and the paper discussed there made a lot more sense (it was on Kolmogorov Complexity, a topic I've wanted to learn about for quite a while now). A group of REU students also played Avalon essentially every night at 9pm, which was also very fun.
- Week 1:
- Through discussing with Ariel and Vikram, we've planned out some concrete directions to work on. One direction is to show a gap between optimal Buy-n and BuyMany mechanisms. For deterministic mechanisms, we proved that these two are equivalent; the same result is not known for randomized mechanisms (and we believe that the claim is incorrect). I've struggled this entire week to find a gap. This is an important result to prove since if it weren't true, some previous work would imply the result from Ariel's paper. We note that even if this is true, Ariel's paper still introduces interesting techniques for proving upper bounds for approximation. Another direction to work on is extending the current results to unit-demand buyers. Although in the past, unit-demand results are much easier to prove than the additive case; however, it seems that this is not true anymore for Buy-k mechanisms. We're struggling with this currently, but we're making a bit of progress.
Acknowledgements
I am incredibly grateful to Ariel Schvartzman for his mentorship and useful discussions. This work was carried out while I was a participant in the 2022 DIMACS REU program at Rutgers University, supported by NSF grant CCF-1852215.