Names with clickable links indicate current/former lab members; * denotes equal contribution.
Preprints
Abstract
This paper investigates the online conversion problem, which involves sequentially trading a divisible resource (e.g., energy) under dynamically changing prices to maximize profit. A key challenge in online conversion is managing decisions under horizon uncertainty, where the duration of trading is either known, revealed partway, or entirely unknown. We propose a unified algorithm that achieves optimal competitive guarantees across these horizon models, accounting for practical constraints such as box constraints, which limit the maximum allowable trade per step. Additionally, we extend the algorithm to a learning-augmented version, leveraging horizon predictions to adaptively balance performance: achieving near-optimal results when predictions are accurate while maintaining strong guarantees when predictions are unreliable. These results advance the understanding of online conversion under various degrees of horizon uncertainty and provide more practical strategies to address real world constraints.
2025+
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
In the value-oblivious secretary problem, candidates come in a uniformly-random order, and the available information only includes comparisons between candidates, not their exact values. The goal is to maximize the probability of picking the best candidate. In this work, we consider the value-oblivious secretary problem with advice. The advice given is the coming-order position of the best candidate and possibly erroneous. We design randomized algorithms that leverage the famous wait-and-accept algorithm as subroutines, using a novel optimization-based framework. The framework models the consistency and robustness guarantees of designed algorithms as optimization objectives and constraints, and the performance of designed algorithm is optimized by solving the optimization problem. we show the flexibility of our framework on some variations of the secretary problem, including the multiple-choice secretary problem and the secretary problem with rehiring option.
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 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.
2024
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.
Abstract
We prove that single-parameter natural exponential families with subexponential tails are self-concordant with polynomial-sized parameters. For subgaussian natural exponential families we establish an exact characterization of the growth rate of the self-concordance parameter. Applying these findings to bandits allows us to fill gaps in the literature: We show that optimistic algorithms for generalized linear bandits enjoy regret bounds that are both second-order (scale with the variance of the optimal arm's reward distribution) and free of an exponential dependence on the bound of the problem parameter in the leading term. To the best of our knowledge, ours is the first regret bound for generalized linear bandits with subexponential tails, broadening the class of problems to include Poisson, exponential and gamma bandits.
ACM SIGMETRICS 2024 - Workshop on MAMA [PDF]Abstract
In this paper, we initiate the study of an online conversion problem incorporating group fairness guarantees. This problem aims to distribute a resource with fixed capacity to a sequence of buyers based on their offered prices. Each buyer can be categorized as a distinct group, and the objective is to maximize the revenue while maintaining fairness across groups, ensuring each group receives a predetermined quantity of resources. We propose a novel threshold-based online algorithm and prove that it attains the optimal competitive ratio with fairness guarantees.
Abstract
It has been known that a few bits of queries of the maximum price can break the lower bound of online conversion problem. We ask if a query only asks about the relationship of the future price and the current price plus a constant (k), will it also break the lower bound in the unknown horizon case? It turns out that when k=0, the query model is not helpful. We present a deterministic algorithm and a randomized algorithm to effectively utilize the prediction and break the lower bound when k>0.
2023
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.
Abstract
This paper studies an online path selection problem and proposes online mechanisms for a network operator to sequentially update link prices. The aim is to incentivize online-arriving agents to join the network and select paths in a manner that maximizes the social welfare, which comprises both system profit and the quality of service experienced by agents. Competitive analysis is adopted to analyze the performance of the proposed online mechanism. Sufficient and necessary conditions on a competitive mechanism are established. Moreover, the performance limit of the celebrated multiple-the-index pricing scheme is also analyzed.
Abstract
An electric vehicle based mobility-on-demand (EMoD) system provides shared transportation (e.g., car-sharing or ride-sharing) to satisfy customers’ individual mobility demands. It has been recognized as a vital alternative form of transportation between public and private transportations in future sustainable cities. Constrained by the long charging time and limited driving range of EVs, an operator of an EMoD system demands for decision-making models and algorithms to manage the mobility and energy of EVs to best serve customers with least costs. In this paper, we propose a stochastic dynamic program (DP) to model three operational decisions of the EMoD system: i) dispatching EVs to serve mobility demand from customers, ii) repositioning EVs to accommodate the unbalanced mobility demands between service regions, and iii) recharging EVs to maintain their sufficient state-of-charge levels. To handle this large-scale DP problem, we first observe and prove that it has a coordinate-wise concave value function. Based on this structural property, we propose to use a separable piecewise linear function to approximate the value function and design an approximation-based algorithm to efficiently derive the decision policy. Numerical tests show that our proposed algorithm significantly outperforms the existing model-free approaches (e.g., greedy heuristic and Q-learning) that fail to take into account the structural properties of the DP problem.
2022
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.
ACM SIGMETRICS 2022 - Workshop on MAMA [PDF] [Slides]Abstract
We study a novel online optimization problem, termed online selection with convex costs (OSCC). In OSCC, there is a sequence of items, each with a value that remains unknown before its arrival. At each step when there is a new arrival, we need to make an irrevocable decision in terms of whether to accept this item and take its value, or to reject it. The crux of OSCC is that we must pay for an increasing and convex cost associated with the number of items accepted, namely, it is increasingly more difficult to accommodate additional items. The goal is to develop an online algorithm that accepts/selects a subset of items, without any prior statistical knowledge of future arrival information, to maximize the social surplus, namely, the sum of the accepted items’ values minus the total cost. Our main result is the development of a threshold policy that is logistically-simple and easy to implement, but has provable optimality guarantees among all deterministic online algorithms.
2021-Selected publications before 2021 (Complete list: Google Scholar)
Abstract
Aggregation of demand-side flexibility plays a crucial role in helping improve the system-wide performance of power grids. However, less known is the potential negative impact of self-interested flexibility aggregators being strategic for their own benefits at the cost of other market participants and even system-wide performance. This paper aims to theoretically analyze this negative impact, as well as the corresponding mitigation method. Specifically, we consider a strategic aggregator derives the optimal bidding strategy of the flexibility bounds (for cumulative energy and instantaneous power consumption) and trades electricity in a pool. A multi-period bi-level program with a DC network setup is considered. The upper-level problem represents the aggregator’s cost minimization, and the lower-level problem represents the market clearing process. Based on this bi-level formulation, our theoretical analysis shows that the potential negative impacts of the strategic behavior on the system generation cost, the payments of the fixed loads and non-strategic aggregators depend on the bus locations of both the strategic and non-strategic aggregators. We propose to additionally charge the strategic aggregator for the newly introduced congestion so as to avoid the system performance degradation. The analytical results are validated via simulations.
Abstract
This paper concerns the mechanism design for online resource allocation in a strategic setting. In this setting, a single supplier allocates capacity-limited resources to requests that arrive in a sequential and arbitrary manner. Each request is associated with an agent who may act selfishly to misreport the requirement and valuation of her request. The supplier charges payment from agents whose requests are satisfied, but incurs a load-dependent supply cost. The goal is to design an incentive compatible online mechanism, which determines not only the resource allocation of each request, but also the payment of each agent, so as to (approximately) maximize the social welfare (i.e., aggregate valuations minus supply cost). We study this problem under the framework of competitive analysis. The major contribution of this paper is the development of a unified approach that achieves the best-possible competitive ratios for setups with different supply costs. Specifically, we show that when there is no supply cost or the supply cost function is linear, our model is essentially a standard 0-1 knapsack problem, for which our approach achieves logarithmic competitive ratios that match the state-of-the-art (which is optimal). For the more challenging setup when the supply cost is strictly-convex, we provide online mechanisms, for the first time, that lead to the optimal competitive ratios as well. To the best of our knowledge, this is the first approach that unifies the characterization of optimal competitive ratios in online resource allocation for different setups including zero, linear and strictly-convex supply costs.
Abstract
We study a general online combinatorial auction problem in algorithmic mechanism design. A provider allocates multiple types of capacity-limited resources to customers that arrive in a sequential and arbitrary manner. Each customer has a private valuation function on bundles of resources that she can purchase (e.g., a combination of different resources such as CPU and RAM in cloud computing). The provider charges payment from customers who purchase a bundle of resources and incurs an increasing supply cost with respect to the totality of resources allocated. The goal is to maximize the social welfare, namely, the total valuation of customers for their purchased bundles, minus the total supply cost of the provider for all the resources that have been allocated. We adopt the competitive analysis framework and provide posted-price mechanisms with optimal competitive ratios. Our pricing mechanism is optimal in the sense that no other online algorithms can achieve a better competitive ratio. We validate the theoretic results via empirical studies of online resource allocation in cloud computing. Our numerical results demonstrate that the proposed pricing mechanism is competitive and robust against system uncertainties and outperforms existing benchmarks.
Abstract
In this paper, we study a general transactive energy (TE) retailing problem in smart grids: a TE retailer (e.g., a utility company) publishes the energy price, which may vary over time. TE customers arrive in an arbitrary manner and may choose to either purchase a certain amount of energy based on the posted price, or leave without buying. Typical examples of such a setup include a transactive electric vehicle charging platform, or a general market-based demand-side management program, etc. We consider the setting where the customer arrival information is unknown (i.e., without prediction), and focus on maximizing the social welfare of the TE system through a posted-price mechanism (PPM) that runs in an online fashion with causal information only. We quantify the performance of the proposed PPM in the competitive analysis framework, and show that our proposed PPM is optimal in the sense that no other online mechanisms can achieve a better competitive ratio. We evaluate our theoretic results for the case of transactive electric vehicle charging. Our extensive experimental results show that the proposed PPM is competitive and robust against system uncertainties, and outperforms several existing benchmarks.
Abstract
Electric vehicles (EVs) have been well recognized as a deferrable load with the flexibility to shift their energy demands over time. Although this one-dimensional flexibility has been extensively investigated both by research and industrial implementations, the expanding energy demand and the associated uncertainties still make the integration of a large population of EVs into power system reliably and economically greatly challenging. In this paper, we design an auction scheme via mechanism design to elicit two additional flexibilities from EVs, namely energy flexibility and deadline flexibility. An offline mechanism is firstly designed as a benchmark based on the famous Vickrey–Clark– Groves mechanism. Then based on the primal-dual approach, we propose an online auction, in which all bids are truthful, the loss of social welfare is bounded by competitive ratio, and the mechanism can be implemented in polynomial time. By the numerical results, we quantitatively show that both the power system operators and individual EVs can benefit from the integration of the multi-dimensional flexibilities through our proposed mechanisms.
ACM SIGMETRICS 2019 - Workshop on MAMA [PDF]Abstract
We study a general online resource allocation problem, where a service provider sells multiple types of capacity-limited resources to heterogeneous customers that arrive in a sequential manner. The provider charges payment from customers who purchase the resource but must pay an increasing marginal supply cost with respect to the total resource allocated (e.g., production costs and/or operational costs). The goal is to maximize the social welfare, namely, the total valuation of customers minus the total supply cost of the provider. We adopt the standard competitive analysis framework and provide an optimal online posted-pricing mechanism. Our online mechanism is optimal in the sense that no other online algorithms can achieve a better competitive ratio.
Abstract
A battery swapping and charging station (BSCS) is an energy refueling station, where (i) electric vehicles (EVs) with depleted batteries (DBs) can swap their DBs for fully-charged ones, and (ii) the swapped DBs are then charged until they are fully-charged. Successful deployment of a BSCS system necessitates a careful planning of swapping- and chargingrelated infrastructures, and thus a comprehensive performance evaluation of the BSCS is becoming crucial. This paper studies such a performance evaluation problem with a novel mixed queueing network (MQN) model and validates this model with extensive numerical simulation. We adopt the EVs’ blocking probability as our quality-of-service measure and focus on studying the impact of the key parameters of the BSCS (e.g., the numbers of parking spaces, swapping islands, chargers, and batteries) on the blocking probability. We prove a necessary and sufficient condition for showing the ergodicity of the MQN when the number of batteries approaches infinity, and further prove that the blocking probability has two different types of asymptotic behaviors. Meanwhile, for each type of asymptotic behavior, we analytically derive the asymptotic lower bound of the blocking probability.
Abstract
This paper aims at quantifying the value of a lifetime-constrained battery energy storage system (BESS) operated by a consumer who faces fluctuating electricity prices. We define the lifetime of the BESS as the serving duration within which the BESSs capacity stays above a certain threshold of its initial capacity and define the value of the BESS as the total peakshaving value within its entire lifetime. Under the assumption that the price dynamics are Markovian, we show that maximizing the average value of the BESS can be formulated as a stochastic shortest path (SSP) problem, and the average lifetime corresponds to the average number of steps before being absorbed in the SSP problem. We propose an efficient parallel value iteration algorithm to solve the proposed SSP problem with guarantees of achieving optimality and a fast convergence. We also derive a closed form expression for the average lifetime based on the principle of an embedded absorbing Markov chain. We validate our model and algorithm on a practical BESS via real price data sets from two different markets. Comparison of the computational efficiency between the standard Gauss–Seidel value iteration and our parallel algorithm is also illustrated through extensive simulation.
Abstract
The optimal operation of a distributed battery energy storage system (BESS) for energy arbitrage under dynamic pricing is studied in this paper, and the Pareto optimal arbitrage policy that balances the economic value and lifetime tradeoff of the BESSis obtained. Specifically, the lifetime performance of the BESS is represented by its average lifetime, i.e., the average operational duration within which its capacity stays above a certain threshold, and the value performance of the BESS is defined as the total average arbitrage value within its entire lifetime. We propose a constrained stochastic shortest path (CSSP) model to characterize the optimal value-lifetime performance pair. By exploiting the hidden structure of this CSSP problem, an efficient parallel algorithm is proposed to compute the optimal policy. We further prove the condition under which the optimal policy is Pareto optimal. This implies that the achievable optimal value-lifetime performance pair is globally optimal as long as the system-wide utility is monotonically increasing in both the value performance and the lifetime performance. We validate our proposed model and algorithm via real battery specifications and electricity market data, and the results show promising insights for both infrastructure planning and operational management of BESSs in practice.