Today I'll share a bit about a paper which is very close to my heart, having recently revised the paper and posted it to the arxiv: https://arxiv.org/abs/2105.07329
Title: Dynamic Spatial Matching
Abstract: Motivated by a variety of online matching platforms, we consider demand and supply units which are located i.i.d. in [0,1]^d, and each demand unit needs to be matched with a supply unit. The goal is to minimize the expected average distance between matched pairs (the "cost"). We model dynamic arrivals of one or both of demand and supply with uncertain locations of future arrivals, and characterize the scaling behavior of the achievable cost in terms of system size (number of supply units), as a function of the dimension d. Our achievability results are backed by concrete matching algorithms. Across cases, we find that the platform can achieve cost (nearly) as low as that achievable if the locations of future arrivals had been known beforehand. Furthermore, in all cases except one, cost nearly as low in terms of scaling as the expected distance to the nearest neighboring supply unit is achievable, i.e., the matching constraint does not cause an increase in cost either. The aberrant case is where only demand arrivals are dynamic, and d=1; excess supply significantly reduces cost in this case.
The goal of the paper is to establish technical foundations for dynamic matching and resource allocation, where demand and supply live in d-dimensional space, and there are many types. My motivation for establishing such a foundation comes loosely from ridehailing, matching platforms, and network revenue management with many types. And of course, it was an opportunity to introduce a new, fundamental model and say something about it :) Motivating literatures include those for static random spatial matching (including Ajtai, Komlos and Tusnady '84, Peter Shor's thesis work, and Talagrand's work), and work on stochastic bin packing.
From a personal perspective, there's a few things which have been special about this project for me. For one, this is my first single author paper in more than 10 years. Why? Well, I tend to write papers with others since I like collaborating with good and friendly people, and learning from them. It's nice to have somebody to talk to about the research, and also the publication process, disseminating the work, and what not. Even with this particular project, I interacted with many folks about it over months and years including multiple PhD students, several colleagues, and the reputed mathematician Michel Talagrand (which was a special experience in itself!). In fact, the idea for the key Hierarchical Greedy algorithm which facilitates my analysis and hence the main results in the paper came out of a conversation with Michel, in the context of his epic latest book: https://link.springer.com/book/10.1007/978-3-030-82595-9. Nevertheless, none of these interactions developed into a full blown collaboration, and I ended up doing this paper myself. Writing it alone has been a great reminder of the fact that writing one of these papers is hard, and takes a lot out of you. And yet, producing research like this is exactly why I'm in the profession in the first place, so no complaints :)
A second, related, special thing about this project is that it connects up conceptually with an exploratory project I was a part of way back in 2011, on Distributed Storage for Intermittent Energy Sources, with Andrea Montanari, David Tse and Baosen Zhang. There's something truly beautiful about wandering off in one's research for years, while something "old" continues to gestate at the fringes of one's interests, and eventually coming back to a topic after a decade or more with a new angle to move the needle. That's exactly what happened here.
A third special experience with this paper has been that with the referee who reviewed my paper for the Annals of Applied Probability. This is perhaps my best referee experience to date, and I'm super grateful. The referee found an intricate bug in the proof of the easier of my results, and went on to construct a detailed fix for the bug, which would have taken me multiple days (at least) to come up with myself! So the bug was short lived. In addition, the referee suggested a very simple way to obtain my results for all d>=3 via a very elegant analysis indeed. I've included the insight in my paper. Many thanks to the anonymous referee, and here's hoping that I have the fortune to encounter more such brilliant, dedicated and helpful referees in future.
