Theory Seminar

Online markets and platforms have drastically shaped the algorithmic landscape into a complex ecosystem of strategic or self-interested entities. Hence, it is important to design algorithmic systems that are robust to strategic behavior and other informational uncertainties in order to guarantee desirable outcomes. In this talk, I will focus on my recent work that tackles three important challenges—uncertain decision making, strategic behavior, and interdependence—by using approximation algorithms to go beyond standard assumptions on information structures.

Divyarthi Mohan is a postdoctoral researcher in the Faculty of Computing & Data Sciences at Boston University. Her research broadly lies at the intersection of computer science and economics, with a focus on algorithmic mechanisms design and the interplay of incentives and information. She obtained her PhD in Computer Science at Princeton University, advised by Matt Weinberg, and was previously a postdoctoral fellow at Tel Aviv University hosted by Michal Feldman. Her research has been recognized with the Simons-Berkeley Research Fellowship for Fall 2022, the class of 2021 Siebel Scholarship, and 2019 SEAS award of excellence at Princeton University, and her work was invited to the Highlights Beyond EC 2024.

Many of the most important optimization problems in practice are massive in scale, mathematically complex, and involve numerous unknown parameters. Machine learning offers a powerful way to address these challenges by uncovering hidden structure and improving decision quality, but integrating predictions into algorithms raises fundamental questions: which architectures align with combinatorial structure, and how can we ensure robustness to error? This talk presents two case studies. First, we show how graph neural networks can approximate the optimal dynamic program for online matching, yielding algorithms that generalize across graph sizes and achieve strong empirical performance. Second, we introduce calibration as a principled interface between machine learning and decision-making, demonstrating through rent-or-buy and job scheduling problems that calibrated predictions yield both theoretical guarantees and practical improvements. Together, these results illustrate how learning can meaningfully augment algorithm design while retaining rigorous performance guarantees. This is joint work with Alexandre Hayderi, Amin Saberi, Anders Wikum, and Judy Hanwen Shen.

Ellen Vitercik is an Assistant Professor at Stanford University with a joint appointment between the Management Science & Engineering department and the Computer Science department. Her research interests include machine learning, algorithm design, discrete and combinatorial optimization, and the interface between economics and computation. Before joining Stanford, she spent a year as a Miller Postdoctoral Fellow at UC Berkeley and received a PhD in Computer Science from Carnegie Mellon University. Her research has been recognized with a Schmidt Sciences AI2050 Early Career Fellowship, an NSF CAREER award, the SIGecom Doctoral Dissertation Award, and the CMU School of Computer Science Distinguished Dissertation Award, among other honors.

Over the past decade, machine learning has achieved remarkable progress across a wide range of applications. This success is largely attributable to the paradigm of training machine learning systems by minimizing a single loss function using gradient-descent-based optimization algorithms. However, the landscape is shifting, and many of the outstanding challenges in machine learning now lie at its intersection with game theory. These challenges arise either from explicitly strategic environments—such as multi-agent reinforcement learning systems, autobidding in auctions, and algorithmic pricing—or from problems that can be implicitly modeled as games, such as robustifying models against adversarial attacks, training generative models, and alignment.

These emerging problems present new challenges for both machine learning and game theory. On the one hand, it remains unclear what types of optimization algorithms are effective in these game-theoretic settings. On the other hand, the games arising from machine learning problems often involve non-concave utilities, whereas traditional game theory has largely focused on games with (quasi)-concave utilities. In this talk, we will discuss recent progress in tackling these challenges and explore the obstacles and opportunities that lie ahead for both machine learning and game theory.

Yang Cai is a Professor of Computer Science and Economics (secondary appointment) at Yale University. He finished his Ph.D. at MIT in Computer Science under the supervision of Costis Daskalakis and received his B.Sc. in EECS at Peking University. His research interests lie in theoretical computer science and its interface with economics, optimization, and machine learning. His work has been recognized with the COLT Best Paper Award, the FOCS Test of Time Award, the Sloan Research Fellowship, the NSF CAREER Award, the William Dawson Scholarship, and the Simons-Berkeley Research Fellowship.

We consider the problem of dynamically allocating a reusable resource to strategic agents under long-term budget constraints, so that we simultaneously (i) maximize social welfare, (ii) satisfy multi-dimensional long-term cost constraints, and (iii) incentivize truthful reporting. Finding that primal-dual methods, widely used in constrained online optimization, are highly fragile in strategic settings, we develop an incentive-aware primal-dual framework achiving \(\tilde O(\sqrt T)\) social welfare regret – matching the non-strategic lower bound – while being robust to strategic agents and adhering to all constraints. Technically, our primal side design features epoch-based lazy updates, dual-adjusted pricing rule, and randomized exploration rounds to fix agents’ expectations about future and discourage misreporting. On the dual side, we carefully design a novel online learning technique – which can be of independent interest – to efficiently learn optimal duals despite lazy updates and strategic agents.

Yan Dai is a 2nd-year PhD student in Operations Research at MIT, co-advised by Prof. Patrick Jaillet and Prof. Negin Golrezaei. His research focuses on developing robust mechanisms for strategic economic systems under incomplete information via an online learning toolbox. He also works on online learning topics like bandits or reinforcement learning. He belongs to the COLT, ICML, and NeurIPS community, and was recognized by a Best Paper award at SIGMETRICS 2025.

Motivated by our collaboration with a major refugee resettlement agency in the U.S., we study a dynamic matching problem where each new arrival (a refugee case) must be matched immediately and irrevocably to one of the static resources (a location with a fixed annual quota). In addition to consuming the static resource, each case requires post-allocation services from a server, such as a translator. Given the uncertainty in service time, a server may not be available at a given time, thus we refer to it as a dynamic resource. Upon matching, the case will wait to avail service in a first-come-first-serve manner. Bursty matching to a location may result in undesirable congestion at its corresponding server. Consequently, the central planner (the agency) faces a dynamic matching problem with an objective that combines the matching reward (captured by pair-specific employment outcomes) with the cost for congestion for dynamic resources and over-allocation for the static ones. Motivated by the observed fluctuations in the composition of refugee pools across the years, we aim to design algorithms that do not rely on distributional knowledge. We develop learning-based algorithms that are asymptotically optimal in certain regimes, easy to interpret, and computationally fast. Our design is based on learning the dual variables of the underlying optimization problem; however, the main challenge lies in the time-varying nature of the dual variables associated with dynamic resources. Our theoretical development brings together techniques from Lyapunov analysis, adversarial online learning, and stochastic optimization. On the application side, when tested on real data from our partner agency and incorporating practical considerations, our method outperforms existing ones making it a viable candidate for replacing the current practice upon experimentation.

Online decision-making is one of the most active research areas in computer science and operations research - these problems show up everywhere, and thanks to the ever present “curse-of-dimensionality”, enable a constant stream of work on new models, algorithms, and performance metrics. The huge diversity in methodologies, however, means that these policies are hard to understand and compare. In practice, we would ideally like a policy that does as well as possible for our given setting; but is this possible?

In this talk, I will try and present two case-studies based on my research that offers hope towards this goal. First, for a large class of “exchangeable action” problems (which includes several widely-studied settings including online resource-allocation, dynamic pricing, generalized assignment and online bin packing), I will present a class of simple greedy policies that, under stochastic inputs, get constant regret, i.e., have additive loss compared to the optimal solution in hindsight which is independent of the horizon and state-space. One downside of these policies is that their performance can be bad under certain adversarial inputs. To this end, for the simpler “online learning” setting (i.e., repeated decision-making problems with no intertemporal constraints and additive rewards), I will present a policy that in every instance can match (up to constant factors) the regret of both the above greedy policies as well as the minimax optimal policy, whichever is better for that given instance. In both cases, the resulting policies are surprisingly simple, despite beating the performance of complex state-of-the-art algorithms for widely studied problems. The magic behind this is in the use of new sample-path coupling approaches, and I will try to give examples in each case to illustrate these techniques.

Sid Banerjee is an associate professor in the School of Operations Research at Cornell, working on topics at the intersection of data-driven decision-making, network algorithms and market design. His research is supported by grants from the NSF (including an NSF CAREER award), ARO, and AFOSR, and has received multiple awards including the INFORMS Applied Probability Society Best Publication award in 2021 and the Erlang Prize in 2022. He completed his PhD from the ECE Department at UT Austin, and was a postdoctoral researcher in the Social Algorithms Lab at Stanford. He also served as a technical consultant with the research science group at Lyft from 2014-18.

We give a reduction from \((1+\epsilon)\)-approximate Earth Mover’s Distance (EMD) to \((1+\epsilon)\)-approximate Closest Pair. As a consequence, we improve the fastest known approximation algorithm for high-dimensional EMD. Here, given \(p\in [1, 2]\) and two sets of \(n\) points \(X,Y \subset (\R^d,\ell_p)\), their EMD is the minimum cost of a perfect matching between \(X\) and \(Y\), where the cost of matching two vectors is their \(\ell_p\) distance. Further, Closest Pair is the basic problem of finding a pair of points realizing \(\min_{x \in X, y\in Y} \Vert x-y \Vert_p\).

TBA

TBA

TBA

TBA

TBA

TBA

TBA

TBA

We consider a class of optimization problems over stochastic variables where the algorithm can learn information about the value of any variable through a series of costly steps; we model this information acquisition process as a Markov Decision Process (MDP). The algorithm’s goal is to maximize the value of its solution minus the cost of information acquisition under a selection constraint. Such bandit superprocesses have been studied previously but solutions are known only for fairly restrictive special cases and the problem is computationally challenging in general.

To address this challenge, previous approaches have turned to approximation algorithms by considering a restricted class of committing policies that simplify the decision-making aspects of the problem and allow for efficient optimization. This motivates the question of bounding the commitment gap, measuring the worst case ratio in the performance of the optimal committing policy and the overall optimal.

In this talk, we provide a unified framework for bounding the commitment gap by developing a bound on the utility of the overall optimal through a novel cost amortization technique. We then proceed to develop two different approaches for exploiting that bound. The first one is a local approximation condition that is established individually for each MDP and then composes into a (global) bound on the commitment gap. The second one relies on an ex ante relaxation of the objective and provides MDP-invariant bounds on the commitment gap that are related to the correlation gap of the underlying selection constraint. Both techniques provide improved bounds on the commitment gap and approximately optimal solutions to many costly information models, including different variants of the Pandora’s Box problem.

Dimitrios (aka Dimitris) Christou is a 5th year Computer Science PhD student at UT Austin. He is fortunate to be advised by Prof. Shuchi Chawla. Prior to joining UT Austin, he received a Diploma in Electrical and Computer Engineering from the National Technical University of Athens. His research focuses on optimisation in uncertain environments and spans many areas, including the design of online algorithms, online-learning algorithms and data-driven algorithmic design. Recently, he has worked in problems in the intersection of Computer Science, Operations Research and Economics such as revenue maximization in online markets and costly-information models like bandit superprocesses.