Fisher B, 9:00 AM - 12:00 PM
This workshop will cover recent developments in our understanding of the optimum online policy in online matching and allocation problems. In many online optimization problems, a natural benchmark to compare to is the optimal offline policy – for example, the EC community has long studied prophet inequalities, which have found myriad applications throughout economics and computer science. An equally natural benchmark in stochastic settings is the optimal online policy – although, as recently as 2016, Karlin and Koutsoupias (in Roughgarden's book on beyond worst-case analysis) observed that “we do not have many techniques for getting a handle” on it.
Nearly a decade later, we now possess such techniques, and understand some of their implications for algorithms in various economic contexts. This workshop will emphasize the variety of recent results from the EC community related to this benchmark, including approximation algorithms (i.e., philosopher inequalities), order-competitive ratio, dynamic allocation, learning, and mechanism design. An emphasis will be on future directions and applications of this line of work.
Tristan Pollner – Ph.D. student at Stanford University, supported by Dantzig-Liebermann Fellowship.
Amin Saberi – Professor at Stanford University and Director of the Stanford Center for Computational Market Design.
David Wajc – Senior lecturer (assistant professor) and Taub Fellow at the Technion — Israel Institute of Technology.
9:00-9:28 David Wajc Philosopher inequalities (based on works in EC'19, EC'21, EC'22, EC'23, SAGT'24, EC'24, SODA'25, SODA'25, STOC'25,...)
Abstract: In online Bayesian selection problems, a seller faces a stream of buyers arriving sequentially. Each arriving buyer makes, for each item on sale, a take-it-or-leave-it offer (drawn from a known distribution), which the seller must immediately either accept or decline. The objective is to maximize the expected welfare of the allocation. It is common to compare the seller's benefit to the optimal offline solution, obtained by a "prophet" who knows the future. However, the seller might not even be able to attain the value of the more "modest" benchmark of the optimal online algorithm: the latter may be computationally intractable to run. In this case the optimal online algorithm is obtained by a "philosopher" with sufficient time to think (compute). In this talk I will discuss some developments on this newly-named benchmark, and its (in)approximability by efficient online algorithms and mechanisms.
9:28-9:56 Amin Saberi Approximation Schemes for Online Matching (based on works in WINE'20, EC'20, EC'22, SODA'24, STOC'25, ...)
Abstract: I’ll begin with a quick overview of our latest line of work in designing online approximation algorithms for a variety of online optimization problems. Then I’ll dive into a continuous‑time, infinite‑horizon dynamic matching model inspired by applications such as deceased organ allocation and time-sensitive task assignments, where patients and workers exhibit limited patience and organs or tasks demand immediate pairing. I will show how we combined techniques from approximation algorithms, queueing theory, and MCMC to craft novel algorithms with substantially better approximation ratios.
9:56-10:14 Tristan Pollner Improved Approximations for Stationary Bipartite Matching: Beyond Probabilistic Independence
Abstract: We study stationary online bipartite matching, where both types of nodes--offline and online--arrive according to Poisson processes. Offline nodes wait to be matched for some random time, determined by an exponential distribution, while online nodes need to be matched immediately. This model captures scenarios such as deceased organ donation and time-sensitive task assignments, where there is an inflow of patients and workers (offline nodes) with limited patience, while organs and tasks (online nodes) must be assigned upon arrival.
We present an efficient online algorithm that achieves a (1-1/e+δ)-approximation to the optimal online policy's reward for a constant δ>0, simplifying and improving previous work by Aouad and Saritaç (2022). Our solution combines recent online matching techniques, particularly pivotal sampling, which enables correlated rounding of tighter linear programming approximations, and a greedy-like algorithm. A key technical component is the analysis of a stochastic process that exploits subtle correlations between offline nodes, using renewal theory. A byproduct of our result is an improvement to the best-known competitive ratio for this problem.
10:15-10:45 Coffee Break
10:45-11:03 Tomer Ezra “Who is Next in Line?” On the Significance of Knowing the Arrival Order in Bayesian Online Settings (SODA'23)
Abstract: We introduce a new measure for the performance of online algorithms in Bayesian settings, where the input is drawn from a known prior, but the realizations are revealed one-by-one in an online fashion. Our new measure is called order-competitive ratio. It is defined as the worst case (over all distribution sequences) ratio between the performance of the best order-unaware and order-aware algorithms, and quantifies the loss that is incurred due to lack of knowledge of the arrival order. Despite the growing interest in the role of the arrival order on the performance of online algorithms, this loss has been overlooked thus far.
We study the order-competitive ratio in the paradigmatic prophet inequality problem, for the two common objective functions of (i) maximizing the expected value, and (ii) maximizing the probability of obtaining the largest value; and with respect to two families of algorithms, namely (i) adaptive algorithms, and (ii) single-threshold algorithms. We provide tight bounds for all four combinations, with respect to deterministic algorithms. Our analysis requires new ideas and departs from standard techniques. In particular, our adaptive algorithms inevitably go beyond single-threshold algorithms. The results with respect to the order-competitive ratio measure capture the intuition that adaptive algorithms are stronger than single-threshold ones, and may lead to a better algorithmic advice than the classical competitive ratio measure.
11:03-11:21 Zhihao Gavin Tang Online Stochastic Matching with Unknown Arrival Order: Beating 0.5 against the Online Optimum (STOC'25)
Abstract: We study the online stochastic matching problem. Against the offline benchmark, Feldman, Gravin, and Lucier (SODA 2015) designed an optimal 0.5-competitive algorithm. A recent line of work, initiated by Papadimitriou, Pollner, Saberi, and Wajc (MOR 2024), focuses on designing approximation algorithms against the online optimum. The online benchmark allows positive results surpassing the 0.5 ratio.
In this work, adapting the order-competitive analysis by Ezra, Feldman, Gravin, and Tang (SODA 2023), we design a 0.5+Ω(1) order-competitive algorithm against the online benchmark with unknown arrival order. Our algorithm is significantly different from existing ones, as the known arrival order is crucial to the previous approximation algorithms.
11:21-11:39 Paul Dütting Prophet Secretary Against the Online Optimal (EC'23)
Abstract: We study the prophet secretary problem, a well-studied variant of the classic prophet inequality, where values are drawn from independent known distributions but arrive in uniformly random order. Upon seeing a value at each step, the decision-maker has to either select it and stop or irrevocably discard it. Traditionally, the chosen benchmark is the expected reward of the prophet, who knows all the values in advance and can always select the maximum one. In this work, we study the prophet secretary problem against a less pessimistic but equally well-motivated benchmark; the online optimal. Here, the main goal is to find polynomial-time algorithms that guarantee near-optimal expected reward. As a warm-up, we present a quasi-polynomial time approximation scheme (QPTAS) achieving a (1-eps)-approximation in O(n^{polylog n} * f(eps)) time through careful discretization and non-trivial bundling processes. Using the toolbox developed for the QPTAS, coupled with a novel frontloading technique that enables us to reduce the number of decisions we need to make, we are able to remove the dependence on n in the exponent and obtain a polynomial time approximation scheme (PTAS) for this problem.
11:39-11:57 Ellen Vitercik MAGNOLIA: Matching Algorithms via GNNs for Online Value-to-go Approximation (ICML'24)
Abstract: Online Bayesian bipartite matching is a central problem in digital marketplaces and exchanges, including advertising, crowdsourcing, ridesharing, and kidney exchange. We introduce a graph neural network (GNN) approach that emulates the problem's combinatorially-complex optimal online algorithm, which selects actions (e.g., which nodes to match) by computing each action's value-to-go (VTG) -- the expected weight of the final matching if the algorithm takes that action, then acts optimally in the future. We train a GNN to estimate VTG and show empirically that this GNN returns high-weight matchings across a variety of tasks. Moreover, we identify a common family of graph distributions in spatial crowdsourcing applications, such as rideshare, under which VTG can be efficiently approximated by aggregating information within local neighborhoods in the graphs. This structure matches the local behavior of GNNs, providing theoretical justification for our approach.