Online Resource Allocation

Talk Abstracts:

Sahil Singla

Title: Online Resource Allocation with Large Budgets

Abstract: The online resource allocation problem is central to many areas of Computer Science, Operations Research, and Economics. In this problem, n requests arrive sequentially for m limited resources. Each request can be satisfied in multiple ways, consuming different amounts of resources and generating varying values, and the objective is to maximize the total value without exceeding resource budgets. Applications of this problem include online advertisement, online routing, packing LPs, ridesharing platforms, and online auctions. 

In this tutorial, we will begin with an overview of the online resource allocation problem. We will then focus on designing (1+ϵ)-approximation algorithms when each resource has a large budget. We will start by achieving this guarantee for known distributions, then extend it to unknown i.i.d. distributions, and finally to unknown non-identical distributions. Our approach involves using no-regret online learning algorithms to present each incoming request with resource prices, enabling the request to make a value-maximizing decision. This method immediately results in fast and incentive-compatible algorithms.

Andrés Cristi

Title: Online Combinatorial Allocations and Auctions

Abstract: In an online combinatorial auction, n agents arrive sequentially, and we have to allocate m different items among them. Their preferences are expressed as a value for each possible subset of the items, and we want to design an online algorithm to allocate the items, maximizing the social welfare.

In this tutorial, we will present the basic model of online combinatorial auctions and focus on the bayesian case, where the valuations are drawn independently from known distributions. We will introduce two important techniques for this model: balanced prices and using samples to protect items. We will prove two recent results using these techniques regarding valuations with bounded demand size and sub additive valuations. Finally, we will discuss open directions in the area.

Anupam Gupta

Title: Robust Algorithms for Secretary Problems

Abstract: The secretary problem in online optimization assumes a probabilistic model on the inputs (that items are presented in uniformly random order), and existing algorithms achieve near-optimal performance when the data conforms to the model. However, these algorithms performs poorly when the data can be slightly corrupted by an adversary. In this talk, we discuss how to model adversarial corruptions, and how to get good algorithms that are robust to them. The talk is based on work with C.J. Argue, Domagoj Bradac, Marco Molinaro, Sahil Singla, and Goran Zuzic.

Víctor Verdugo

Title: Online Combinatorial Assignment in Independence Systems

Abstract: In the online combinatorial assignment problem, we are given an independence system over a ground set of elements and agents that arrive online one by one. Upon arrival, each agent reveals a weight function over the elements of the ground set. If the independence system is given by the matchings of a hypergraph we recover the combinatorial auction problem, where every node represents an item to be sold, and every edge represents a bundle of items. Using linear programming techniques, we provide improved guarantees for the k-bounded online combinatorial auction problem (i.e., bundles of size at most k): We show a (1−exp(−k))/k-competitive algorithm in the prophet IID model, a 1/(k+1)-competitive algorithm in the prophet-secretary model, and a k^{-k/(k−1)}-competitive algorithm in the secretary model. Our algorithms run in polynomial time and work in more general independence systems where the offline combinatorial assignment problem admits the existence of a polynomial-time randomized algorithm that we call certificate sampler. In terms of upper bounds, we also show that the competitiveness of any online combinatorial auction algorithm in the prophet IID setting is upper bounded by O(log(k)/k), and O(log(n)/sqrt(n)), where k is the maximum bundle size and n is the number of items. Joint work with Javier Marinkovic (UChile) and José A. Soto (UChile).

Yifeng Teng

Title: Pricing for Online Resource Allocation: Intervals and Paths

Abstract: We present pricing mechanisms for several online resource allocation problems which obtain tight or nearly tight approximations to social welfare. In our settings, buyers arrive online and purchase bundles of items. Motivated by applications to cloud economics, we consider two kinds of buyer preferences. In the first, items correspond to different units of time at which a resource is available; the items are arranged in a total order and buyers desire intervals of items. The second generalizes the first and corresponds to bandwidth allocation over a graph network; the items are edges in the network and buyers desire paths. We discuss the performance of different pricing algorithms for these buyer preferences in both Bayesian settings and single-minded settings.

Rebecca Reiffenhäuser

Title: Combinatorial Single-Sample Prophet Inequalities

Abstract: In Prophet Inequalities, the impossibility of obtaining online algorithms with nontrivial competitive ratios is circumvented by assuming knowledge of all value distributions beforehand. However, much less is actually needed to achieve this: in fact, for the classic problem, Rubinstein, Wang and Weinberg showed the famous optimal ratio of ½ can still be obtained when prior knowledge is restricted to a single sample from each value distribution. Constant competitive ratios with just a single sample have by now also been obtained for a large number of combinatorial problems. The talk introduces central techniques as well as new results for XOS combinatorial allocations. 

Based on joint work with Constantine Caramanis, Paul Dütting, Matthew Faw, Federico Fusco, Philip Lazos, Stefano Leonardi, Orestis Papadigenopoulos, Emmanouil Pountourakis, and joint work with Paul Dütting, Thomas Kesselheim, Brendan Lucier and Sahil Singla.

Balasubramanian Sivan

Title: Robust Budget Pacing with a Single Sample

Abstract:  Major Internet advertising platforms offer budget pacing tools as a standard service for advertisers to manage their ad campaigns. Given the inherent non-stationarity in an advertiser's value and also competing advertisers' values over time, a commonly used approach is to learn a target expenditure plan that specifies a target spend as a function of time, and then run a controller that tracks this plan. This raises the question: how many historical samples are required to learn a good expenditure plan? We study this question by considering an advertiser repeatedly participating in $T$ second-price auctions, where the tuple of her value and the highest competing bid is drawn from an unknown time-varying distribution. The advertiser seeks to maximize her total utility subject to her budget constraint. Prior work has shown the sufficiency of $T\log T$ samples per distribution to achieve the optimal $O(\sqrt{T})$-regret. We dramatically improve this state-of-the-art and show that \emph{just one sample per distribution} is enough to achieve the near-optimal $\tilde O(\sqrt{T})$-regret, while still being robust to noise in the sampling distributions.

Based on joint work with Santiago Balseiro, Rachitesh Kumar, Vahab Mirrokni and Di Wang. Appeared in ICML'23.

Mahsa Derakhshan

Title: Max-Weight Online Stochastic Matching: Improved Approximations Against the Online Benchmark

Abstract: We study max-weight stochastic matchings on online bipartite graphs under both vertex and edge arrivals. We focus on designing polynomial time approximation algorithms with respect to the online benchmark, which was first considered by Papadimitriou, Pollner, Saberi, and Wajc [EC'21]. 

In the vertex arrival version of the problem, the goal is to find an approximate max-weight matching of a given bipartite graph when the vertices in one part of the graph arrive online in a fixed order with independent chances of failure. Whenever a vertex arrives we should decide, irrevocably, whether to match it with one of its unmatched neighbors or leave it unmatched forever. There has been a long line of work designing approximation algorithms for different variants of this problem with respect to the offline benchmark (prophet). Papadimitriou et al., however, propose the alternative online benchmark and show that considering this new benchmark allows them to improve the 0.5 approximation ratio, which is the best ratio achievable with respect to the offline benchmark. They provide a 0.51-approximation algorithm which was later improved to 0.526 by Saberi and Wajc [ICALP'21]. The main contribution of this paper is designing a simple algorithm with a significantly improved approximation ratio of (1-1/e) for this problem. 

We also consider the edge arrival version in which, instead of vertices, edges of the graph arrive in an online fashion with independent chances of failure. Designing approximation algorithms for this problem has also been studied extensively with the best approximation ratio being 0.337 with respect to the offline benchmark. This paper, however, is the first to consider the online benchmark for the edge arrival version of the problem. For this problem, we provide a simple algorithm with an approximation ratio of 0.5 with respect to the online benchmark.