The SODALab consists of undergraduate and graduate students committed to developing algorithmic tools for decision-making under uncertainty. Some members focus on advancing the general theory in this area—primarily through the lens of online and randomized algorithms, algorithmic game theory / mechanism design, and reinforcement / online learning. Others tackle societal challenges involving complex resource allocation, scheduling, and matching problems across domains such as Internet advertising, cloud computing, shared mobility, and electrical grids. For more details, explore examples of our recent projects below.
Online Algorithms: Markets & Platforms
Research in online algorithms focuses on a subset of optimization and decision-making problems where (i) data are incrementally revealed over time, and (ii) decisions need to be made sequentially (oftentimes also irrevocably). This differs from offline optimization, where all the data is available upfront, and the algorithm can optimize the solution with complete knowledge of the future. Online algorithms have diverse applications, including Internet advertising, recommendation systems, financial trading, and revenue management, etc.
Our research in this area broadly focuses on online algorithms and their implications for the design and operation of online markets and platforms in domains such as Internet advertising, cloud computing, and ridesharing.
Recent Work
Abstract
This paper addresses the online k-selection problem with diseconomies of scale (OSDoS), where a seller seeks to maximize social welfare by optimally pricing items for sequentially arriving buyers, accounting for increasing marginal production costs. Previous studies have investigated deterministic dynamic pricing mechanisms for such settings. However, significant challenges remain, particularly in achieving optimality with small or finite inventories and developing effective randomized posted price mechanisms. To bridge this gap, we propose a novel randomized dynamic pricing mechanism for OSDoS, providing a tighter lower bound on the competitive ratio compared to prior work. Our approach ensures optimal performance in small inventory settings (i.e., whenis small) and surpasses existing online mechanisms in large inventory settings (i.e., whenis large), leading to the best-known posted price mechanism for optimizing online selection and allocation with diseconomies of scale across varying inventory sizes.
Abstract
This paper provides threshold policies with tight guarantees for online selection with convex cost (OSCC). In OSCC, a seller wants to sell some asset to a sequence of buyers with the goal of maximizing his/her profit. The seller can produce additional units of the asset, but at non-decreasing marginal costs. At each time, a buyer arrives and offers a price, and the seller must make an immediate and irrevocable decision in terms of whether to accept the offer and produce/sell one unit of the asset to this buyer. The goal is to develop an online algorithm that selects a subset of buyers to maximize the seller’s profit, namely, the total selling revenue minus the total production cost. Our main result is the development of a class of simple threshold policies that are logistically-simple and easy to implement, but have provable optimality guarantees among all deterministic algorithms. We also derive a lower bound on competitive ratios of randomized algorithms, and prove that the competitive ratio of our threshold policy asymptotically converges to this lower bound when the total production output is sufficiently large. Our results generalize and unify various online search, pricing, and auction problems, and provide a new perspective on the impact of non-decreasing marginal costs on real-world online resource allocation problems.
Algorithmic Fairness: Dynamics & Uncertainty
Fairness is a difficult topic to talk about, as perspectives on fairness often vary across individuals and depend on the context. Nevertheless, addressing fairness in algorithmic decision-making has far-reaching implications, including promoting equitable access to limited public resources and reducing biases in critical domains such as healthcare, hiring, and education. Fairness can be conceptualized through various notions, including envy-freeness, proportionality, and maximin share, among others. Although these concepts have been extensively studied in offline settings, they present significant new challenges in dynamic and uncertain environments with sequential agent arrivals.
Our research in this area focuses on developing fair algorithms for sequential decision-making under various forms of arrival uncertainty (e.g., adversarial, stochastic, and learning-augmented settings). Specifically, our recent work has focused on group fairness and time fairness in online allocation and selection, aiming to design algorithms that treat sequentially arriving agents fairly across groups while ensuring high efficiency, consistency, and explainability over time.
Recent Work
Abstract
We introduce and study a multi-class online resource allocation problem with group fairness guarantees. The problem involves allocating a fixed amount of resources to a sequence of agents, each belonging to a specific group. The primary objective is to ensure fairness across different groups in an online setting. We focus on three fairness notions: one based on quantity and two based on utility. To achieve fair allocations, we develop two threshold-based online algorithms, proving their optimality under two fairness notions and near-optimality for the more challenging one. Additionally, we demonstrate a fundamental trade-off between group fairness and individual welfare using a novel representative function-based approach. To address this trade-off, we propose a set-aside multi-threshold algorithm that reserves a portion of the resource to ensure fairness across groups while utilizing the remaining resource to optimize efficiency under utility-based fairness notions. This algorithm is proven to achieve the Pareto-optimal trade-off. We also demonstrate that our problem can model a wide range of real-world applications, including network caching and cloud computing, and empirically evaluate our proposed algorithms in the network caching problem using real datasets.
Abstract
This paper studies an online selection problem, where a seller seeks to sequentially sell multiple copies of an item to arriving buyers. We consider an adversarial setting, making no modeling assumptions about buyers’ valuations for the items except acknowledging a finite support. In this paper, we focus on a class of static pricing algorithms that sample a price from a pre-determined distribution and sell items to buyers whose valuations exceed the sampled price. Such algorithms are of practical interests due to their advantageous properties, such as ease of implementation and non-discrimination over prices. Our work shows that the simple static pricing strategy can achieve strong guarantees comparable to the best known dynamic pricing algorithms. Particularly, we design the optimal static pricing algorithms for the adversarial online selection problem and its two important variants: the online assignment problem and the online selection with convex cost. The static pricing algorithms can even attain the optimal competitive ratios among all online algorithms for the online selection problem and the online assignment problem. To achieve these results, we propose an economics-based approach in the competitive analysis of static pricing algorithms, and develop a novel representative function-based approach to derive the lower bounds. We expect these approaches will be useful in related problems such as online matching.
Learning-Augmented Algorithms: Theory & Applications
Learning-augmented algorithms, also known as algorithms with predictions, represent a recent paradigm that integrates machine-learned predictions into classical algorithmic frameworks to enhance practical performance while retaining provable worst-case guarantees. Unlike purely data-driven methods, these algorithms incorporate predictions to guide decision-making, yet are explicitly designed to remain robust even when predictions are highly inaccurate. This paradigm bridges the gap between worst-case analysis and empirical performance, combining the reliability of traditional algorithm design with the adaptability of machine learning.
Our research in this area investigates how predictions can be leveraged to surpass the worst-case guarantees of conventional algorithm design, particularly in online settings, with respect to metrics such as efficiency, fairness, and risk. We adopt both theoretical and applied perspectives, with applications ranging from electric vehicle charging and cloud computing to network caching and other decision-making problems under uncertainty.
Recent Work
Abstract
We study the ordinal secretary problem, where a sequence of candidates arrives in uniformly random order, and the goal is to select the best candidate using only pairwise comparisons. We consider a learning-augmented setting that incorporates potentially erroneous predictions about the best candidate’s position. Our goal is to design online algorithms that balance robustness against poor predictions while having high performance when predictions are accurate. Using an optimization-based framework, we develop deterministic and randomized algorithms that extend classical strategies and explicitly model the trade-off between consistency and robustness. Also, we show the flexibility of our approach by applying it to multiple secretary problem variants, including multiple-choice and rehiring.
Abstract
We study the online multi-class selection problem with group fairness guarantees, where limited resources must be allocated to sequentially arriving agents. Our work addresses two key limitations in the existing literature. First, we introduce a novel lossless rounding scheme that ensures the integral algorithm achieves the same expected performance as any fractional solution. Second, we explicitly address the challenges introduced by agents who belong to multiple classes. To this end, we develop a randomized algorithm based on a relax-and-round framework. The algorithm first computes a fractional solution using a resource reservation approach---referred to as the extit{set-aside} mechanism---to enforce fairness across classes. The subsequent rounding step preserves these fairness guarantees without degrading performance. Additionally, we propose a learning-augmented variant that incorporates untrusted machine-learned predictions to better balance fairness and efficiency in practical settings.
Energy Sustainability: Incentives & Computation
Markets and economic incentives are powerful tools for influencing behavior and outcomes in modern infrastructure systems, particularly in the energy sector. As global demand for reliable and low-carbon energy grows, there is an urgent need for systems that align individual decisions with broader environmental and social sustainability objectives. In this context, designing effective market mechanisms and incentive structures for pricing, allocation, and coordination is critical to supporting an efficient transition toward a sustainable energy future.
Our research in this area integrates tools from optimization, game theory, and machine learning to develop algorithmic and economic solutions that foster collective action toward energy and carbon sustainability. We particularly focus on applications involving power systems with distributed energy resources, electric mobility, and data centers—domains where incentives and computation are tightly coupled.
Recent Work
Abstract
This paper introduces a novel mechanism for online allocation with multi-phase, non-separable regularizers, termed Cap-and-Penalize (CnP), inspired by real-world applications such as cap-and-tax policies in carbon pricing. The CnP regularizer models a multi-phase cost structure, imposing a monotone convex penalty when total allocation exceeds a predefined level (soft cap) and enforcing a strict limit (hard cap) beyond which allocation is prohibited. Our contributions are twofold: (1) we propose an online mechanism for CnP-regularized allocation without per-step resource constraints, which operates as a simple and intuitive posted-price mechanism, but achieves the best-possible guarantee among all possible online algorithms; (2) we tackle the more complex setting with per-step resource constraints by decomposing the regularizer into local components, yielding a similar mechanism with time-dependent marginal pricing functions. To establish the tightness of our results in both settings, we introduce a representative function-based approach that transforms the lower-bound proof into the problem of solving an ordinary differential equation with boundary conditions. We believe that this technique has the potential to be applied to other similar online optimization problems.
Abstract
Virtual power plants (VPP) can increase reliability and efficiency of power systems with a high share of renewables. However, their adoption largely depends on their profitability, which is difficult to maximize due to the heterogeneity of their components, different sources of uncertainty and potential profit streams. This paper proposes two profit-maximizing operating strategies for a VPP that aggregates solar systems and electric vehicle (EV) chargers with vehicle-to-grid (V2G) support, and generates profit by trading energy in day-ahead and imbalance electricity markets. Both strategies solve a two-stage stochastic optimization problem. In the first stage, energy bids are placed by solving a sequence of linear programs, each formulated for a specific forecast scenario. In the second stage, given the day-ahead commitments and real-time measurements, the decisions with respect to charging or discharging EVs are made sequentially for every hour and adjustments to the day-ahead commitments are settled in the imbalance market. The two strategies differ in how they solve the sequential decision making problem in the second stage. But, they both foresee the effect of their current (dis)charge decisions on the feasibility of fulfilling the EV charging demands using a one-step lookahead technique. The first strategy employs a heuristic algorithm to find a feasible charging schedule for every EV that is connected to a charger. The second one utilizes a soft actor-critic reinforcement learning method with a differentiable projection layer that enforces constraint satisfaction. We empirically evaluate the proposed operating strategies using real market prices, solar traces, and EV charging sessions obtained from a network of chargers in the Netherlands, and analyze how the uptake of V2G could affect profitability of this VPP.