- Costis Daskalakis, Maxwell Fishelson, Brendan Lucier, Vasilis Syrgkanis and Santhoshini Velusamy. Simple, Credible, and Approximately-Optimal Auctions. EC20 [paper] [talk]
- Fishelson, M., Gunby, B. Generalized Pattern Avoidance via Hypergraph Containers. Engineering and Applied Sciences: Combinatorics, ISSN Online: 2575-1468
Accepted to the twenty-first ACM conference on Economics and Computation (EC20), this work establishes that a large class of multi-item auctions achieve a constant factor of the optimal revenue. Notably, we demonstrate the first revenue bounds for many common non-truthful auctions in the multi-item setting, settling an open problem in the literature. For the first time ever, we have guarantees that first-price-type auctions perform well. These are the most common auctions in practice, and until now, there was no certainty of their performance. We also establish the first approximately optimal static auction that is credible. What this means is that, the auctioneer cannot profitably deceive the bidders. A second price auction, for example, is not credible. Say 2 guys bid in a second price auction $100 and $50 respectively. As the auctioneer, I can lie to the $100 guy and tell him the other guy bid $99. This bidder would get charged $99 as he can’t disprove my claim. However, in the first price auction, you know you are paying your bid and there is no room for deception. We also obtain mechanisms with fixed entry fees that are amenable to tuning via online learning techniques.
The story behind this project is pretty crazy. It started as a final project in the graduate course Algorithmic Game Theory taught by Professor Costis Daskalakis and Vasilis Syrgkanis. I took it during the spring semester of my junior year of undergrad. I was absolutely obsessed with the class; it offered some of the coolest, most fascinating lectures I’d ever attended. I really wanted to do research with the professors. So, I decided to take on this really ambitious project. Here’s a video of Vasilis laughing at me for attempting the problem in a lecture hall of 50+ students.
My project partner Santhoshini Velusamy and I worked pretty hard at the problem for what remained of the semester. We ultimately produced a result on multi-item revenue optimality, but one that relied on bidder value distributions having a monotone hazard rate, an assumption often too strong in practice.
Flash forward to September: T minus 3 months till grad school apps were due. The safe thing to do was to try to squeeze out a new project in the time that remained, as this auction research was already in a decent place for undergraduate work. However, the mysteries of the problem still lingered in my mind, even after months of hiatus. So, I decided to contact Santhoshini and restart work on it. We had one final idea that we didn’t explore during the semester: an alternate formulation of multidimensional virtual value. It ended up being the crucial first step to the proof.
With this insight, the problem boiled down to one thing: bounding the welfare loss of the first price auction. As a non-truthful auction, first price is not always welfare optimal; sometimes the bidder that wants the item the most doesn’t win. However, we needed to demonstrate that this lost welfare (Wel(OPT)-Wel(FP)) was at most a constant factor of the revenue of Myerson’s auction. This puzzle turned from a fascination to an obsession. It seemed impossible to find a counter example, and yet the proof continued to allude me. I would spend 14 hour days thinking about it, wholly neglecting my homework and even my grad school apps.
Exactly 6 days before the apps were due, it finally clicked. It was a moment of pure joy followed by a moment of manically rewriting all of my apps to reflect the result. A pretty unforgettable way to finish off undergrad and the best 4 years of my life (so far).
Published in the journal of Engineering and Applied Sciences, this work was a generalization of the Stanley-Wilf conjecture. The statement of the conjecture is as follows. There are n! (roughly (n/e)^n) ways to permute the numbers 1 to n. However, if we say that we only want to count permutations that avoid a particular subsequence pattern, then the total will only be singly exponential (roughly c^n for some constant c). For example, the number of permutations that do not contain increasing subsequences of length 3 is C_n, the nth Catalan number (roughly 4^n). The conjecture states that, no matter how crazy and convoluted the pattern is, we will always observe this singly exponential behavior.
The conjecture was settled in 2004 by Marcus and Tardos. The goal of this research was to generalize this result, where we only necessitate that the pattern be avoided at specific indices.
This project was the first serious research I ever did, and it came about from somewhat humorous circumstances. It all started when I emailed Professor Asaf Ferber to complain that he gave me a B in his class Algebraic Combinatorics. He essentially responded with a challenge, “Do a research project with me next semester and prove to me you deserved an A.”
We met one on one a number of times that following semester, where he introduced me to the problem and the Hypergraph Containers method. I was working on the setting where the indices at which the pattern must be avoided are chosen randomly. Later, Asaf introduced me to Benjamin Gunby, a graduate student at Harvard who was working on the deterministic version of the problem. We came together and wrote a joint paper of our findings.
I never did end up getting my grade changed to an A, but looking back I realize that that B did more for me than any A ever could.