About

Patrick Jaillet is the Dugald C. Jackson Professor in the Department of Electrical Engineering and Computer Science (EECS) at the Massachusetts Institute of Technology (MIT). He is also a faculty member and principal investigator at the Laboratory for Information and Decision Systems (LIDS) and a member of the Operations Research Center (ORC). His research focuses on online optimization and learning, sequential decision-making under uncertainty, and machine learning. His teaching interests include optimization, probability, machine learning, and network science, reflecting his expertise in these areas and his contributions to advancing knowledge in decision systems and data-driven methodologies.

Research topics

• Computer Science
• Machine Learning
• Artificial Intelligence
• Mathematical optimization
• Mathematics
• Psychology
• Telecommunications
• Philosophy
• Statistics
• Mathematical economics
• Computer network
• Combinatorics
• Operations research
• Transport engineering
• Economics
• Engineering

Selected publications

• Learning with Exact Invariances in Polynomial Time

  ArXiv.org · 2025-02-27

  preprintOpen accessSenior author

  We study the statistical-computational trade-offs for learning with exact invariances (or symmetries) using kernel regression. Traditional methods, such as data augmentation, group averaging, canonicalization, and frame-averaging, either fail to provide a polynomial-time solution or are not applicable in the kernel setting. However, with oracle access to the geometric properties of the input space, we propose a polynomial-time algorithm that learns a classifier with \emph{exact} invariances. Moreover, our approach achieves the same excess population risk (or generalization error) as the original kernel regression problem. To the best of our knowledge, this is the first polynomial-time algorithm to achieve exact (not approximate) invariances in this context. Our proof leverages tools from differential geometry, spectral theory, and optimization. A key result in our development is a new reformulation of the problem of learning under invariances as optimizing an infinite number of linearly constrained convex quadratic programs, which may be of independent interest.

  PublisherOA PDFDOI

• A Locational Demand Model for Bike-Sharing

  Manufacturing & Service Operations Management · 2025-03-31 · 3 citations

  articleSenior author

  Problem definition: Micromobility systems (bike-sharing or scooter-sharing) have been widely adopted across the globe as a sustainable mode of urban transportation. To efficiently plan, operate, and monitor such systems, it is crucial to understand the underlying rider demand—where riders come from and the rates of arrivals into the service area. They serve as key inputs for downstream decisions, including capacity planning, location optimization, and rebalancing. Estimating rider demand is nontrivial as most systems only keep track of trip data, which are a biased representation of the underlying demand. Methodology/results: We develop a locational demand model to estimate rider demand only using trip and vehicle status data. We establish conditions under which our model is identifiable. In addition, we devise an expectation-maximization (EM) algorithm for efficient estimation with closed-form updates on location weights. To scale the estimation procedures, this EM algorithm is complemented with a location-discovery procedure that gradually adds new locations in the service region with large improvements to the likelihood. Experiments using both synthetic data and real data from a dockless bike-sharing system in the Seattle area demonstrate the accuracy and scalability of the model and its estimation algorithm. Managerial implications: Our theoretical results shed light on the quality of the estimates and guide the practical usage of this locational demand model. The model and its estimation algorithm equip municipal agencies and fleet operators with tools to effectively monitor service levels using daily operational data and assess demand shifts because of capacity changes at specific locations. Funding: This work was supported by The Pacific Northwest Transportation Consortium (PacTrans) [Grant 69A3551747110]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/msom.2023.0306 .

  PublisherDOI

• Multi-drone rescue search in a large network

  European Journal of Operational Research · 2025-02-11 · 7 citations

  articleSenior author
  PublisherDOI

• Non-Monetary Mechanism Design without Distributional Information: Using Scarce Audits Wisely

  ArXiv.org · 2025-02-12

  preprintOpen accessSenior author

  We study a repeated resource allocation problem with strategic agents where monetary transfers are disallowed and the central planner has no prior information on agents' utility distributions. In light of Arrow's impossibility theorem, acquiring information about agent preferences through some form of feedback is necessary. We assume that the central planner can request powerful but expensive audits on the winner in any round, revealing the true utility of the winner in that round. We design a mechanism achieving $T$-independent $O(K^2)$ social welfare regret while only requesting $O(K^3 \log T)$ audits in expectation, where $K$ is the number of agents and $T$ is the number of rounds. We also show an $Ω(K)$ lower bound on the regret and an $Ω(1)$ lower bound on the number of audits when having low regret. Algorithmically, we show that incentive-compatibility can be mostly enforced via the imposition of adaptive future punishments, where the audit probability is inversely proportional to the winner's future winning probability. To accurately estimate such probabilities in presence of strategic agents, who may adversely react to any potential misestimate, we introduce a flagging component that allows agents to flag any biased estimate (we show that doing so aligns with individual incentives). On the technical side, without a unique and known distribution, one cannot apply the revelation principle and conclude that truthful reporting is exactly an equilibrium. Instead, we characterize the equilibrium via a reduction to a simpler auxiliary game, in which agents cannot strategize until close to the end of the game; we show equilibria in this game can induce equilibria in the actual, fully strategic game. The tools developed therein may be of independent interest for other mechanism design problems in which the revelation principle cannot be readily applied.

  PublisherOA PDFDOI

• Multi-Timescale Primal Dual Hybrid Gradient with Application to Distributed Optimization

  ArXiv.org · 2025-06-18

  preprintOpen accessSenior author

  We propose two variants of the Primal Dual Hybrid Gradient (PDHG) algorithm for saddle point problems with block decomposable duals, hereafter called Multi-Timescale PDHG (MT-PDHG) and its accelerated variant (AMT-PDHG). Through novel mixtures of Bregman divergence and multi-timescale extrapolations, our MT-PDHG and AMT-PDHG converge under arbitrary updating rates for different dual blocks while remaining fully deterministic and robust to extreme delays in dual updates. We further apply our (A)MT-PDHG, augmented with the gradient sliding techniques introduced in Lan et al. (2020), Lan (2016), to distributed optimization. The flexibility in choosing different updating rates for different blocks allows a more refined control over the communication rounds between different pairs of agents, thereby improving the efficiencies in settings with heterogeneity in local objectives and communication costs. Moreover, with careful choices of penalty levels, our algorithms show linear and thus optimal dependency on function similarities, a measure of how similar the gradients of local objectives are. This provides a positive answer to the open question whether such dependency is achievable for non-smooth objectives (Arjevani and Shamir 2015).

  PublisherOA PDFDOI

• Incentive-Aware Dynamic Resource Allocation under Long-Term Cost Constraints

  ArXiv.org · 2025-07-13

  preprintOpen accessSenior author

  Motivated by applications such as cloud platforms allocating GPUs to users or governments deploying mobile health units across competing regions, we study the dynamic allocation of a reusable resource to strategic agents with private valuations. Our objective is to simultaneously (i) maximize social welfare, (ii) satisfy multi-dimensional long-term cost constraints, and (iii) incentivize truthful reporting. We begin by numerically evaluating primal-dual methods widely used in constrained online optimization and find them to be highly fragile in strategic settings -- agents can easily manipulate their reports to distort future dual updates for future gain. To address this vulnerability, we develop an incentive-aware framework that makes primal-dual methods robust to strategic behavior. Our design combines epoch-based lazy updates -- where dual variables remain fixed within each epoch -- with randomized exploration rounds that extract approximately truthful signals for learning. Leveraging carefully designed online learning subroutines that can be of independent interest for dual updates, our mechanism achieves $\tilde{\mathcal{O}}(\sqrt{T})$ social welfare regret, satisfies all cost constraints, and ensures incentive alignment. This matches the performance of non-strategic allocation approaches while being robust to strategic agents.

  PublisherOA PDFDOI

• Market Design for Capacity Sharing in Networks

  ACM Transactions on Economics and Computation · 2025-11-21

  articleOpen access

  We study a market mechanism that sets edge prices to incentivize strategic agents to efficiently share limited network capacity. In this market, agents form coalitions, with each coalition sharing a unit capacity of a selected route and making payments to cover edge prices. Our focus is on the existence and computation of market equilibrium, where challenges arise from the interdependence between coalition formation among strategic agents with heterogeneous preferences and route selection that induces a network flow under integral capacity constraints. To address this interplay between coalition formation and network capacity utilization, we introduce a novel approach based on combinatorial auction theory and network flow theory. We establish sufficient conditions on the network topology and agents’ preferences that guarantee both the existence and polynomial-time computation of a market equilibrium. Additionally, we identify a particular market equilibrium that maximizes utilities for all agents and the outcome is equivalent to the classical Vickrey-Clarke-Groves mechanism. Furthermore, we extend our results to multi-period settings and general networks, showing that when the sufficient conditions are not met, an equilibrium may still exist but requires more complex, path-based pricing mechanisms that set differentiated prices based on agents’ preference parameters.

  PublisherDOI

• Online Scheduling for LLM Inference with KV Cache Constraints

  ArXiv.org · 2025-02-10 · 1 citations

  preprintOpen access1st authorCorresponding

  Large Language Model (LLM) inference, where a trained model generates text one word at a time in response to user prompts, is a computationally intensive process requiring efficient scheduling to optimize latency and resource utilization. A key challenge in LLM inference is the management of the Key-Value (KV) cache, which reduces redundant computations but introduces memory constraints. In this work, we model LLM inference with KV cache constraints theoretically and propose a novel batching and scheduling algorithm that minimizes inference latency while effectively managing the KV cache's memory. More specifically, we make the following contributions. First, to evaluate the performance of online algorithms for scheduling in LLM inference, we introduce a hindsight optimal benchmark, formulated as an integer program that computes the minimum total inference latency under full future information. Second, we prove that no deterministic online algorithm can achieve a constant competitive ratio when the arrival process is arbitrary. Third, motivated by the computational intractability of solving the integer program at scale, we propose a polynomial-time online scheduling algorithm and show that under certain conditions it can achieve a constant competitive ratio. We also demonstrate our algorithm's strong empirical performance by comparing it to the hindsight optimal in a synthetic dataset. Finally, we conduct empirical evaluations on a real-world public LLM inference dataset, simulating the Llama2-70B model on A100 GPUs, and show that our algorithm significantly outperforms the benchmark algorithms. Overall, our results offer a path toward more sustainable and cost-effective LLM deployment.

  PublisherOA PDFDOI

• Efficient Online Mirror Descent Stochastic Approximation for Multi-Stage Stochastic Programming

  ArXiv.org · 2025-06-18

  preprintOpen accessSenior author

  We study the unconstrained and the minimax saddle point variants of the convex multi-stage stochastic programming problem, where consecutive decisions are coupled through the objective functions, rather than through the constraints. We approach the problems from the infinite-dimensional policy perspective, but consider an online setting where only the policies corresponding to the actual realization of the underlying stochastic process is needed. This leads to a trackable formulation, where the dimension of the output is linear in the number of stages $T$. We propose hypothetical Mirror Descent Stochastic Approximation (MDSA) for the infinite dimensional policies using stochastic conditional gradients. By taking advantage of the decomposability of the updates across stages and realizations of the underlying stochastic process, we show that the proposed MDSA algorithms admit efficient online implementation, which achieves overall gradient complexity linear in $T$, improving exponentially over all existing algorithms.

  PublisherOA PDFDOI

• Near-Optimal Mechanisms for Resource Allocation Without Monetary Transfers

  arXiv (Cornell University) · 2024-08-19

  preprintOpen accessSenior author

  We study the problem in which a central planner sequentially allocates a single resource to multiple strategic agents using their utility reports at each round, but without using any monetary transfers. We consider general agent utility distributions and two standard settings: a finite horizon $T$ and an infinite horizon with $γ$ discounts. We provide general tools to characterize the convergence rate between the optimal mechanism for the central planner and the first-best allocation if true agent utilities were available. This heavily depends on the utility distributions, yielding rates anywhere between $1/\sqrt T$ and $1/T$ for the finite-horizon setting, and rates faster than $\sqrt{1-γ}$, including exponential rates for the infinite-horizon setting as agents are more patient $γ\to 1$. On the algorithmic side, we design mechanisms based on the promised-utility framework to achieve these rates and leverage structure on the utility distributions. Intuitively, the more flexibility the central planner has to reward or penalize any agent while incurring little social welfare cost, the faster the convergence rate. In particular, discrete utility distributions typically yield the slower rates $1/\sqrt T$ and $\sqrt{1-γ}$, while smooth distributions with density typically yield faster rates $1/T$ (up to logarithmic factors) and $1-γ$.

  PublisherOA PDFDOI

Recent grants

• Online Optimization for Dynamic Resource Allocation Problems

  NSF · $295k · 2010–2015

Frequent coauthors

• Bryan Kian Hsiang Low

  43 shared

• Arthur Flajolet

  33 shared

• Hani S. Mahmassani

  Northwestern University

  31 shared

• Sébastien Blandin

  27 shared

• Justin Dauwels

  24 shared

• Kian Hsiang Low

  24 shared

• Zhongxiang Dai

  23 shared

• Pradeep Varakantham

  21 shared

Education

• Ph.D., Civil Engineering

  Massachusetts Institute of Technology

  2003

• M.S., Civil Engineering

  Massachusetts Institute of Technology

  1999

• B.S., Civil Engineering

  Massachusetts Institute of Technology

  1998

Awards & honors

• French Foreign Ministry Fellowship (1981-1982)
• UPS/MIT Prize and Fellowship (1984-1985)
• ORSA/TSS (now INFORMS/TSL) 1985 Dissertation 1st Prize (1986…
• CNRS/NSF Research Award (1990)
• Fulbright (1990)