DIMACS
DIMACS REU 2022

General Information I

me
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. The motivation for our project is that these optimal auctions are weird in the following sense: their prices for items are super-additive (i.e., the price of buying an apple and a pear together is greater than the price of buying an apple and a pear separately). We study Buy-k mechanisms, which restricts the mechanism to have the property that any buyer prefers buying one menu item than any k other menu items. Previous work has shown that for k=n, this is sufficient to avoid the infinite revenue gap in the case of additive buyers. We will extend upon this work.

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 2:
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.
Week 3:
For the unit-demand setting, we proved that optimal Buy-n mechanisms have finite revenue; this is in contrast to optimal Buy-1 mechanisms, which have been shown to obtain infinite revenue for some cases. When we assume there is a total ordering over the item valuations (i.e., everyone agrees that item i is worth more than item j for i > j), we can show that bundling obtains a O(n^2)-approximation. This total ordering assumption is natural in a few cases: for example, a large drink is always worth more than a medium drink, and a medium drink is always worth more than a small drink. When we don't assume a total ordering, the previous result directly implies that we have a O(n! * n^2)-approximation, since there are n! possible total orderings. With being a little bit more clever, we can actually show that the approximation factor is O(2^n * n^2). The natural thing to try is to show that this can be improved to a polynomial approximation, but I have a feeling the current technique can't obtain such a guarantee.
Week 4:
This week was primarily spent on typing up our proof from last week that optimal Buy-n mechanisms have finite revenue for all valuation distributions. We also spent a considerable time thinking about how to improve the upper bound from O(2^n) down to a polynomial, with little luck. We've decided to turn away from this problem for the time being, and consider another direction related to revenue monotonicity and revenue continuity in Buy-n mechanisms.
Week 5:
Vikram wrote a program to find the optimal Buy-2 mechanism given some distribution, and found an example of a distribution for which the revenue of the optimal Buy-2 mechanism on 2 items is strictly better than the optimal Buy-3 mechanism, hence showing our conjecture that there is a strict gap between optimal Buy-n mechanisms and optimal Buy-Many mechanisms. We are trying to understand this example better in order to construct a family of distributions for each n. The case we currently have only works for n=2. Also, I showed that the lower bound ideas for the additive case can be adapted for the unit-demand case to show that for k \le n^{1/2-\epsilon}, there is an exponential gap between the optimal Buy-k mechanism and optimal Buy-1 mechanism.
Week 6:
In the beginning of this week, I was feeling relatively unmotivated due to being stuck on the ideas we were working on for quite a while. But then, we decided to submit our work to SODA 2023. Suddenly, I had a moment of inspiration. I felt like the proof we had for the unit-demand case could be generalized to apply to buyers with arbitrary (monotone) valuation functions. With some work, I wrote up this proof. It later turned out that we didn't submit to SODA 2023 since the deadline was too close and we didn't want to stress ourselves with writing the paper.
Week 7:
With the adrenaline of the SODA 2023 deadline cooling off, a group of us went to New York over the weekend and largely procrastinated making the final presentation and writing up all of our work for the final paper. Luckily for me (and Vikram), our mentor Ariel had already made slides for a presentation about our work so we simply took a subset of his slides to use for our final presentation. As a result, we did essentially nothing this week besides procrastinate :). Of course, I made sure to make fun of everyone else about having to stress. I also got to listen to Abby + Kabir's presentation 3 times this week, which was fun.

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.

DIMACS
DIMACS REU 2023

General Information II

me
Student: George Z. Li
Mentor: Zihan Tan
School: University of Maryland
E-mail: gzli929 (@) umd (dot) edu
Project: Exact Planar Emulators/Composable Coresets for MSTs

Project Description

Given n points in a weighted planar graph G and k chosen points called terminals, we wish to output a new weighted planar graph H containing the terminals such that the pairwise shortest path distances between terminals are preserved exactly. We would like to study the minimal numbers of nodes needed in H in order to achieve such a guarantee on the pairwise distances. When we instead want to preserve pairwise distances up to a 1+\eps approximation factor, my mentor and others proved in their STOC 2022 paper that nearly linear (in k) number of nodes is sufficient. When all nodes lie on the same face of the planar graph, it is known that O(k^2) nodes is sufficient. There are also lower bounds showing that Omega(k^2) nodes is necessary in general. We believe that O(k^2) is the correct answer, and showing this will be the goal for my REU. More realistically, we will show that O(k^2) nodes is achievable when all terminals lie on a constant number of faces.

Weekly Log

Week 1:
I started the project when I received my offer in February, so I'll discuss here some things I had done during that time as well. I've understood the problem generally, and read through the paper which constructed an exact planar emulator of size O(k^2) when all nodes lie on a single face. Our goal in the past few months has been to extend this construction to the case where all terminals lie on two faces. We almost are done with this extension, and before arriving at the REU, I finished a 5 page writeup on a subset of this proof. There are a few more details here that we are stuck on though. I had also been informed about the other project (coresets for MSTs) and was told that that project would be somewhat of a back-up in case I was dumb (he didn't say this) and couldn't solve the planar emulators problem.
Week 2:
This week I discovered a very difficult case for a sub-sub-sub-problem of the 2-face case which we were stuck on for a while. I also requested this week that Zihan tell me more about the coresets problem because I liked having two problems to think about at the same time (so that if I was too stuck on one, I would just think about the other one). At the end of this week, we resolved the hard case (basically by ignoring it) and I spent the rest of the week formalizing the remainder of the proof for the 2-face case. I also worked on the MST problem a bit in the midst of this.
Week 3:
This week was the Modern Techniques in Graph Algorithms workshop, organized by my mentor along with Nicole and Prantar. I spent most of the week just attending this workshop, which was surprisingly energy consuming. I also got sick right after the workshop, so I did not achieve much in terms of REU research this week. There was a lot of free food, and I finished formalizing the entire 2-face case proof (basically). So finally, after 4 ****ing months of work, we finished the 2-face case and can finally think about the exciting ... 3-face case. Fortunately, I think the techniques that'll work for 3-face case should quickly extend to the constant-faced case. I also met Quanquan during this workshop, which was very exciting.
Week 4:
I was sick this week (maybe because the workshop was too much information for my body to process), so I didn't make much progress this week. Also, Zihan went to STOC (and to vacation) so he was not here either.
Week 5:
For some time this week, I read Arora's PTAS for Euclidean steiner tree among other problems and tried to use it to give a PTAS for our problem of finding the optimal coreset for MST. Unfortunately, it doesn't seem to work: the coreset problem is a maximization problem and a lot of the tricks used in Arora's work seems to be primarily for minimization problems. I also continued thinking about the structure for the 3-face case. I finally understood some of the things Zihan mentioned to me like 10 weeks ago: he was like "by the way, here are some ideas which may be useful at some point in this project" when I was still thinking about 2-face case. He was right ... they were indeed useful.
Week 6:
I continued staring at my little piece of paper for the entire week. Fortunately, progress was made. The structure for the 3- (and more generally) f-face case became clear to me finally (note that it was clear to Zihan probably since the beginning of the project ...). And we have began trying to set the edge weights of this emulator such that the shortest paths are actually preserved. I had my first non-trivial contribution here: there seems to be a way to simplify the edge-weight setting significantly here by assuming some nodes are contracted in the emulator. This will also decrease the total number of nodes in the emulator, which could help improve upon the O(k^4) folklore upper bound. Zihan seemed excited about it, so I assumed it was good.
Week 7:
I went to EC 2023 this week to present my work from the 2022 REU. Zihan gave me a goal of talking to 2 professors and 3 PhD students during the conference, which caused me way too much stress. Fortunately, Matt introduced me to a bunch of PhD students at Princeton which helped me accomplish the PhD student part of my "requirements." In fact, I ended up meeting 10 or so PhD students (who were far less scary). For professors, I talked to Will and Shuchi; it took so much out of me to get myself to talk to them ... I probably lost 2 months of my life due to the amount of stress it caused. I also talked to Yifeng, and joined a follow-up project on my REU project from last year. Hopefully it's not too much.
Week 8:
I continued to work on the edge-weight setting this week. In my previous genius observation, I was able to set the edge weights of all pairs of "critical paths" whose endpoints lay on 3 different faces. I realized this week that my idea for setting the edge weights for 4-face case didn't seem to work ... this was a very sad experience. As a result, I couldn't claim in my presentation that I had solved the problem already. It was nice to see the presentations of all the other students this week, and I was again impressed by how much us little kids can do over the summer. Finally, on Friday, we (a subset of us) left for Prague.
Weeks 9 and 10:
I finished the final write-up for the REU during this time and attended the midsummer combinatorial workshop in Prague.

Acknowledgements

I am incredibly grateful to Zihan Tan for his mentorship and useful discussions. This work was carried out while I was a participant in the 2023 DIMACS REU program at Rutgers University, supported by NSF grants CCF-1836666 and CNS-2150186.