Thorben Tröbst, a student of Vijay Vazirani at UC Irvine, passed his Ph.D. defense today. Thorben joined UCI in 2019, already very knowledgeable about linear programming and related topics through a master’s degree at the University of Bonn. His doctoral research includes work from five of his papers related to matching, especially focusing on matching problems that pair up agents (with preferences) and goods (without) but that do not involve payments. Examples of problems like this include some systems for assigning donated organs to patients in need of a transplant, assigning students to schools in large school systems, or matching would-be visitors to open time slots in oversubscribed public parks. These systems are often either randomized, or produce fractional matchings, as this is required for fairness. (How else could you fairly assign even one thing to multiple people requesting it?)

The papers he incorporated into his thesis (to which I’ve added likely-inaccurate summaries) are:

  • “One-Sided Matching Markets with Endowments: Equilibria and Algorithms”, Garg, Tröbst, and Vazirani, arXiv:2009.10320, Autonomous Agents and Multi-Agent Systems 2024. This concerns exchange markets, where the agents come into the system with goods to share and seek a re-allocation of the goods that maximizes their utility. Although these are difficult in general, and may not have exact equilibria, the authors approximate equilibria for linear utilities, satisfying approximate versions of the nice properties you would want an equilibrium to have (Pareto-optimality and envy-freeness), and an efficient solution for the special case of \(\{0,1\}\)-valued utilities.

  • “Cardinal-Utility Matching Markets: The Quest for Envy-Freeness, Pareto-Optimality, and Efficient Computability”, Tröbst and Vazirani, arXiv:2402.08851, EC 2024. It was known that the Hylland and Zeckhauser mechanism for fractional matching (in which agents are given equal assignments of play money and then find a market equilibrium) is Pareto-optimal and envy-free, but hard (PPAD-complete) to compute or even to approximate. It is not the only Pareto-optimal and envy-free solution, but this paper rules out others by showing that if you could find them, you could also accurately approximate the Hylland and Zeckhauser solution. Nevertheless, it is possible to find in polynomial time a solution that approximates both the Pareto-optimal and envy-free properties to within a factor of two.

  • “Time-Efficient Algorithms for Nash-Bargaining-Based Matching Market Models”, Panageas, Tröbst, and Vazirani, arXiv:2106.02024, WINE 2024. I think the main result here is to replace algorithms for certain kinds of market equilibrium based on convex programming, by simpler and faster combinatorial algorithms based on the multiplicative weight update method. There are also some more approximation results related to those of the previous paper.

  • “Online Matching with High Probability”, Mihail and Tröbst, arXiv:2112.07228, SAGT 2024. This is on a different problem, online matching, in which one side of a bipartite graph is known, the rest becomes available one vertex neighborhood at a time, and whenever each vertex becomes available one must either match it to a neighbor or fail to match it, permanently. This models certain problems of matching online ads to viewers, riders to vehicles in ride-sharing systems, etc. A randomized algorithm by Karp, Vazirani, and Vazirani from 1990 gets within a \(1-\tfrac1e\) factor of the maximum matching, in expectation; this is optimal for randomized algorithms and significantly better than the \(\tfrac12\) factor that is best possible for deterministic algorithms. This paper shows more strongly that it is very likely to get a matching that is nearly this good: the probability of getting a matching within a factor of \(1-\tfrac1e-\alpha\) of optimal is at least \(1-e^{-2\alpha^2n}\). Although Tröbst spent most of the time at his defense talking about his results on market-based matching, he saved a few minutes at the end to include this more briefly.

  • “Almost Tight Bounds for Online Hypergraph Matching”, Tröbst and Udwani, arXiv:2402.08775, Oper. Res. Lett. 2024. Thorben didn’t have time to speak about this in the defense so I don’t have as much of an idea what it is about, but it appears to be on hypergraph generalizations of the same sort of online matching problem, in which one gets a hyperedge at a time instead of a vertex neighborhood at a time.

Unfortunately for academia, but maybe fortunately for Thorben, he is moving to e-commerce. His next destination is London, where he will be working with Optiver.

Congratulations, Thorben!

(Discuss on Mastodon)