Motivated by the challenges in last-mile delivery operations, we consider a natural dynamic staffing problem in which a decision-maker sequentially hires staff over a finite time horizon to meet an unknown target demand at the end. The decision-maker also receives a sequence of predictions about the demand that become increasingly more accurate over time. Consequently, the decision-maker prefers to delay hiring decisions to avoid overstaffing. However, workers' availability decreases over time, resulting in a fundamental trade-off between securing staff early (thus risking overstaffing) versus hiring later based on more accurate predictions (but risking understaffing).

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, our method outperforms existing ones, making it a viable candidate for replacing the current practice upon experimentation.

Most of the literature on online algorithms and sequential decision-making focuses on settings with “irrevocable decisions” where the algorithm’s decision upon arrival of the new input is set in stone and can never change in the future. One canonical example is the classic prophet inequality problem, where realizations of a sequence of independent random variables X1, X2,… with known distributions are drawn one by one and a decision maker decides when to stop and accept the arriving random variable, with the goal of maximizing the expected value of their pick. We consider “prophet inequalities with recourse” in the linear buyback cost setting, where after accepting a variable Xi, we can still discard Xi later and accept another variable Xj, at a buyback cost of f × Xi. The goal is to maximize the expected net reward, which is the value of the final accepted variable minus the total buyback cost. Our first main result is an optimal prophet inequality in the regime of f ≥ 1, where we prove that we can achieve an expected reward 1+f/1+2f times the expected offline optimum. The problem is still open for 0<f<1 and we give some partial results in this regime. In particular, as our second main result, we characterize the asymptotic behavior of the competitive ratio for small f and provide almost matching upper and lower bounds that show a factor of 1−Θ(flog(1/f)). Our results are obtained by two fundamentally different approaches: One is inspired by various proofs of the classical prophet inequality, while the second is based on combinatorial optimization techniques involving LP duality, flows, and cuts.

Abstract. We construct explicit combinatorial Bernoulli factories for the following class of flow-based polytopes: integral 0/1-polytopes defined by a set of network flow constraints. This generalizes the results of Niazadeh et al. (who constructed an explicit factory for the specific case of bipartite perfect matchings) and provides novel exact sampling procedures for sampling paths, circulations, and [Formula: see text]-flows. In the process, we uncover new connections to algebraic combinatorics.

Experimentation is prevalent in online marketplaces and social networks to assess the effectiveness of new market intervention. In an experiment, the platform exposes a (randomized) group of targeted users to the new feature or, equivalently, assigns each user to either the treatment or the control group. The platform then uses the resulting outcomes to estimate the new feature's total market effect, i.e., the difference in total user outcomes if the feature is introduced to the entire market.

Motivated by applications in cloud computing spot markets and selling banner ads on popular websites, we study the online resource allocation problem with costly buyback. To model this problem, we consider the classic edge-weighted fractional online matching problem with a tweak, where the decision maker can recall (i.e., buyback) any fraction of an offline resource that is pre-allocated to an earlier online vertex; however, by doing so not only the decision maker loses the previously allocated reward (which equates the edge-weight), it also has to pay a non-negative constant factor f of this edge-weight as an extra penalty. Parameterizing the problem by the buyback factor f, our main result is obtaining optimal competitive algorithms for all possible values of f through a novel primal-dual family of algorithms. We establish the optimality of our results by obtaining separate lower-bounds for each of small and large buyback factor regimes, and showing how our primal-dual algorithm exactly matches this lower-bound by appropriately tuning a parameter as a function of f. The optimal competitive ratio Γgen(f) and the optimal competitive ratio Γdet-int(f) of deterministic integral algorithms are as follows,

We consider descending price auctions for selling m units of a good to unit demand i.i.d. buyers where there is an exogenous bound of k on the number of price levels the auction clock can take. The auctioneer's problem is to choose price levels p1 > p2 > ․․․ > pk for the auction clock such that auction expected revenue is maximized. The price levels are announced prior to the auction. We reduce this problem to a new variant of prophet inequality, which we call batched prophet inequality, where a decision-maker chooses k (decreasing) thresholds and then sequentially collects rewards (up to m) that are above the thresholds with ties broken uniformly at random. For the special case of m=1 (i.e., selling a single item), we show that the resulting descending auction with k price levels achieves 1- 1/ek of the unrestricted (without the bound of k) optimal revenue. That means a descending auction with just 4 price levels can achieve more than 98% of the optimal revenue. We then extend our results for m>1 and provide a closed-form bound on the competitive ratio of our auction as a function of the number of units m and the number of price levels k.

We introduce and study a variation of the submodular maximization problem motivated by applications in online retail. A platform displays a list of products to a user in response to a search query. The user inspects the first k items in the list for a k chosen at random from a given distribution, and decides whether to purchase an item from that set based on a choice model. The goal of the platform is to maximize the engagement of the shopper defined as the probability of purchase. This problem gives rise to a less-studied variation of submodular maximization in which we are asked to choose an ordering of a set of elements to maximize a linear combination of different submodular functions.

We study the classic online bipartite matching problem with a twist: offline nodes are reusable any number of times. Every offline node i becomes available d steps after it was assigned to. Nothing better than a 0.5-approximation, obtained by the trivial deterministic greedy algorithm, was known for this problem. We give the first approximation factor beating 0.5, namely a 0.505 approximation, by suitably adapting and interpreting the powerful technique of Online Correlated Selection.

Motivated by the applications of rental services in e-commerce, we consider revenue maximization in online assortment of reusable resources for a stream of arriving consumers with different types. We design competitive online algorithms with respect to the optimum online policy in the Bayesian setting, in which types are drawn independently from known heterogeneous distributions over time. In the regime where the minimum of initial inventories c_min is large, our main result is a near-optimal 1-min(1/2,√log(cmin)/cmin) competitive algorithm for the general case of reusable resources. Our algorithm relies on an expected LP benchmark for the problem, solves this LP, and simulates the solution through an independent randomized rounding. The main challenge is obtaining point-wise inventory feasibility in a computationally efficient fashion from these simulation-based algorithms. To this end, we use several technical ingredients to design discarding policies - one for each resource. These policies handle the trade-off between the inventory feasibility under reusability and the revenue loss of each of the resources. However, discarding a unit of a resource changes the future consumption of other resources. To handle this new challenge, we also introduce post-processing assortment procedures that help with designing and analyzing our discarding policies as they run in parallel, which might be of independent interest. We finally evaluate the performance of our algorithms using the numerical simulations on synthetic data.

In several applications of real-time matching of demand to supply in online marketplaces, the platform can allow for some latency to batch the demand and improve the matching’s efficiency. Motivated by these scenarios, we study the optimal trade-off between batching and inefficiency in online allocations. In particular, we consider K-stage variants of the classic vertex weighted bipartite b-matching and AdWords problems, where online vertices arrive in K batches. Our main result for both problems is an optimal (1-(1-1/K)^K)-competitive (fractional) matching algorithm, improving the classic (1-1/e) competitive ratios known for the online variant of these problems [Mehta et al., 2007; Aggarwal et al., 2011]. Our main technique is using a family of convex-programming based matchings that distribute the demand in a particularly balanced way among supply in different stages. More precisely, we identify a sequence of polynomials with decreasing degrees that can be used as strictly concave regularizers of the optimal matching linear program to form this family. By providing structural decompositions of the underlying graph using the optimal solutions of these convex programs, we develop a new multi-stage primal-dual framework to analyze the fractional multi-stage algorithm that returns the corresponding regularized optimal matching in each stage (by solving the stage’s convex program). We further show a matching upper-bound by providing an unweighted instance of the problem in which no online algorithm obtains a competitive ratio better than (1-(1-1/K)^K). We extend our results to integral allocations in the vertex weighted b-matching problem with large budgets, and in the AdWords problem with small bid over budget ratios.

We study the allocative challenges that governmental and nonprofit organizations face when tasked with equitable and efficient rationing of a social good among agents whose needs (demands) realize sequentially and are possibly correlated. As one example, early in the COVID-19 pandemic, the Federal Emergency Management Agency faced overwhelming, temporally scattered, a priori uncertain, and correlated demands for medical supplies from different states. In such contexts, social planners aim to maximize the minimum fill rate across sequentially arriving agents, where each agent's fill rate is determined by an irrevocable, one-time allocation. For an arbitrarily correlated sequence of demands, we establish upper bounds on the expected minimum fill rate (ex-post fairness) and the minimum expected fill rate (ex-ante fairness) achievable by any policy. Our upper bounds are parameterized by the number of agents and the expected demand-to-supply ratio, yet we design a simple adaptive policy called projected proportional allocation (PPA) that simultaneously achieves matching lower bounds for both objectives (ex-post and ex-ante fairness), for any set of parameters. Our PPA policy is transparent and easy to implement, as it does not rely on distributional information beyond the first conditional moments. Despite its simplicity, we demonstrate that the PPA policy provides significant improvement over the canonical class of non-adaptive target-fill-rate policies. We complement our theoretical developments with a numerical study motivated by the rationing of COVID-19 medical supplies based on a standard SEIR modeling approach that is commonly used to forecast pandemic trajectories. In such a setting, our PPA policy significantly outperforms its theoretical guarantee as well as the optimal target-fill-rate policy.

Motivated by online decision-making in time-varying combinatorial environments, we study the problem of transforming offline algorithms to their online counterparts. We focus on offline combinatorial problems that are amenable to a constant factor approximation using a greedy algorithm that is robust to local errors. For such problems, we provide a general framework that efficiently transforms offline robust greedy algorithms to online ones using Blackwell approachability.

We study a two-stage stochastic matching problem motivated in part by applications in online marketplaces used for ride hailing. Using a randomized primal-dual algorithm applied to a family of “balancing” convex programs, we obtain the optimal 3/4 competitive ratio against the optimum offline benchmark. These balancing convex programs offer a natural generalization of the matching skeleton by Goel et al. (2012) and may be of independent interest. Switching to the more precise benchmark of optimum online, we exploit connections to submodular optimization and use a factor-revealing program to improve the 3/4 ratio to (1 – 1/e + 1/e2) ≈ 0.767 for the unweighted and 0.761 for the weighted case. We also show it is NP-hard to obtain an FPTAS with respect to this benchmark.

A Bernoulli factory is an algorithmic procedure for exact sampling of certain random variables having only Bernoulli access to their parameters. Bernoulli access to a parameter p ∈ [0,1] means the algorithm does not know p, but has sample access to independent draws of a Bernoulli random variable with mean equal to p. In this paper, we study the problem of Bernoulli factories for polytopes: given Bernoulli access to a vector x∈ P for a given polytope P⊂ [0,1]n, output a randomized vertex such that the expected value of the i-th coordinate is exactly equal to xi. For example, for the special case of the perfect matching polytope, one is given Bernoulli access to the entries of a doubly stochastic matrix [xij] and asked to sample a matching such that the probability of each edge (i,j) be present in the matching is exactly equal to xij.

We provide a polynomial time reduction from Bayesian incentive compatible mechanism design to Bayesian algorithm design for welfare maximization problems. Unlike prior results, our reduction achieves exact incentive compatibility for problems with multi-dimensional and continuous type spaces. The key technical barrier preventing exact incentive compatibility in prior black-box reductions is that repairing violations of incentive constraints requires understanding the distribution of the mechanism’s output, which is typically #P-hard to compute. Reductions that instead estimate the output distribution by sampling inevitably suffer from sampling error, which typically precludes exact incentive compatibility. We overcome this barrier by employing and generalizing the computational model in the literature on Bernoulli Factories . In a Bernoulli factory problem, one is given a function mapping the bias of an “input coin” to that of an “output coin,” and the challenge is to efficiently simulate the output coin given only sample access to the input coin. This is the key ingredient in designing an incentive compatible mechanism for bipartite matching, which can be used to make the approximately incentive compatible reduction of Hartline et al. [18] exactly incentive compatible.

In this paper, a rather general online problem called \emph{dynamic resource allocation with capacity constraints (DRACC)} is introduced and studied in the realm of posted price mechanisms. This problem subsumes several applications of stateful pricing, including but not limited to posted prices for online job scheduling and matching over a dynamic bipartite graph. As the existing online learning techniques do not yield vanishing-regret mechanisms for this problem, we develop a novel online learning framework defined over deterministic Markov decision processes with \emph{dynamic} state transition and reward functions. We then prove that if the Markov decision process is guaranteed to admit an oracle that can simulate any given policy from any initial state with bounded loss --- a condition that is satisfied in the DRACC problem --- then the online learning problem can be solved with vanishing regret. Our proof technique is based on a reduction to online learning with \emph{switching cost}, in which an online decision maker incurs an extra cost every time she switches from one arm to another. We formally demonstrate this connection and further show how DRACC can be used in our proposed applications of stateful pricing.

In this paper we study the fundamental problems of maximizing a continuous non-monotone submodular function over the hypercube, both with and without coordinate-wise concavity. This family of optimization problems has several applications in machine learning, economics, and communication systems. Our main result is the first $\frac{1}{2}$-approximation algorithm for continuous submodular function maximization; this approximation factor of $\frac{1}{2}$ is the best possible for algorithms that only query the objective function at polynomially many points. For the special case of DR-submodular maximization, i.e. when the submodular function is also coordinate-wise concave along all coordinates, we provide a different $\frac{1}{2}$-approximation algorithm that runs in quasi-linear time. Both these results improve upon prior work (Bian et al. 2017; Soma and Yoshida, 2017). Our first algorithm uses novel ideas such as reducing the guaranteed approximation problem to analyzing a zero-sum game for each coordinate, and incorporates the geometry of this zero-sum game to fix the value at this coordinate. Our second algorithm exploits coordinate-wise concavity to identify a monotone equilibrium condition sufficient for getting the required approximation guarantee, and hunts for the equilibrium point using binary search. We further run experiments to verify the performance of our proposed algorithms in related machine learning applications.

Recent works on Hierarchical Clustering (HC), a well-studied problem in exploratory data analysis, have focused on optimizing various objective functions for this problem under arbitrary similarity measures. In this paper we take the first step and give novel scalable algorithms for this problem tailored to Euclidean data in R^d and under vector-based similarity measures, a prevalent model in several typical machine learning applications. We focus primarily on the popular Gaussian kernel and present our results through the lens of the objective introduced recently by [MW’17]. We show the approximation factor in [MW’17] can be improved for Euclidean data. We further demonstrate both theoretically and experimentally that our algorithms scale to very high dimension d, while outperforming average-linkage and showing competitive results against other less scalable approaches.

Hierarchical Clustering (HC) is a widely studied problem in exploratory data analysis, usually tackled by simple agglomerative procedures like average-linkage, single-linkage or complete-linkage. In this paper we focus on two objectives, introduced recently to give insight into the performance of average-linkage clustering: a similarity based HC objective proposed by [21] and a dissimilarity based HC objective proposed by [9]. In both cases, we present tight counterexamples showing that average-linkage cannot obtain better than ⅓ and ⅔ approximations respectively (in the worst-case), settling an open question raised in [21]. This matches the approximation ratio of a random solution, raising a natural question: can we beat average-linkage for these objectives? We answer this in the affirmative, giving two new algorithms based on semidefinite programming with provably better guarantees.

We consider revenue maximization in online auction/pricing problems. A seller sells an identical item in each period to a new buyer, or a new set of buyers. For the online pricing problem, both when the arriving buyer bids or only responds to the posted price, we design algorithms whose regret bounds scale with the best fixed price in-hindsight, rather than the range of the values. Under the bidding model, we further show our algorithms achieve a revenue convergence rate that matches the offline sample complexity of the single-item single-buyer auction. We also show regret bounds that are scale free, and match the offline sample complexity, when comparing to a benchmark that requires a lower bound on the market share. We further expand our results beyond pricing to multi-buyer auctions, and obtain online learning algorithms for auctions, with convergence rates matching the known sample complexity upper bound of online single-item multi-buyer auctions. These results are obtained by generalizing the classical learning from experts and multi-armed bandit problems to their multi-scale versions. In this version, the reward of each action is in a different range, and the regret with respect to a given action scales with its own range, rather than the maximum range. We obtain almost optimal multi-scale regret bounds by introducing a new Online Mirror Descent (OMD) algorithm whose mirror map is the multi-scale version of the negative entropy function. We further generalize to the bandit setting by introducing the stochastic variant of this OMD algorithm.

Hierarchical clustering is a popular unsupervised data analysis method. For many real-world applications, we would like to exploit prior information about the data that imposes constraints on the clustering hierarchy, and is not captured by the set of features available to the algorithm. This gives rise to the problem of hierarchical clustering with structural constraints. Structural constraints pose major challenges for bottom-up approaches like average/single linkage and even though they can be naturally incorporated into top-down divisive algorithms, no formal guarantees exist on the quality of their output. In this paper, we provide provable approximation guarantees for two simple top-down algorithms, using a recently introduced optimization viewpoint of hierarchical clustering with pairwise similarity information (Dasgupta, 2016). We show how to find good solutions even in the presence of conflicting prior information, by formulating a constraint-based regularization of the objective. Furthemore, we explore a variation of this objective for dissimilarity information (Cohen-Addad et al., 2018) and improve upon current techniques. Finally, we demonstrate our approach on a real dataset for the taxonomy application.

In this paper we study the fundamental problems of maximizing a continuous non monotone submodular function over a hypercube, with and without coordinate-wise concavity. This family of optimization problems has several applications in machine learning, economics, and communication systems. Our main result is the first 1/2 approximation algorithm for continuous submodular function maximization; this approximation factor of is the best possible for algorithms that use only polynomially many queries. For the special case of DR-submodular maximization, we provide a faster 1/2-approximation algorithm that runs in (almost) linear time. Both of these results improve upon prior work [Bian et al., 2017, Soma and Yoshida, 2017, Buchbinder et al., 2012]. Our first algorithm is a single-pass algorithm that uses novel ideas such as reducing the guaranteed approximation problem to analyzing a zero-sum game for each coordinate, and incorporates the geometry of this zero-sum game to fix the value at this coordinate. Our second algorithm is a faster single-pass algorithm that exploits coordinate-wise concavity to identify a monotone equilibrium condition sufficient for getting the required approximation guarantee, and hunts for the equilibrium point using binary search. We further run experiments to verify the performance of our proposed algorithms in related machine learning applications.

As online ad offerings become increasingly complex, with multiple size configurations and layouts available to advertisers, the sale of web advertising space increasingly resembles a combinatorial auction with complementarities. Standard ad auction formats do not immediately extend to these settings, and truthful combinatorial auctions, such as the Vickrey-Clarke-Groves auction, can yield unacceptably low revenue. Core selecting auctions, which apply to combinatorial markets, boost revenue by setting prices so that no group of agents, including the auctioneer, can jointly improve their utilities by switching to a different allocation and payments. Among outcomes in the core, bidder-optimal core points have been the most widely studied due to their incentive properties, such as being implementable at natural equilibria.

We consider revenue maximization in online auctions and pricing. A seller sells an identical item in each period to a new buyer, or a new set of buyers. For the online posted pricing problem, we show regret bounds that scale with the best fixed price, rather than the range of the values. We also show regret bounds that are almost scale free, and match the offline sample complexity, when comparing to a benchmark that requires a lower bound on the market share. These results are obtained by generalizing the classical learning from experts and multi-armed bandit problems to their multi-scale versions. In this version, the reward of each action is in a different range, and the regret w.r.t. a given action scales with its own range, rather than the maximum range.

We consider a scheduling problem where a cloud service provider has multiple units of a resource available over time. Selfish clients submit jobs, each with an arrival time, deadline, length, and value. The service provider's goal is to implement a truthful online mechanism for scheduling jobs so as to maximize the social welfare of the schedule. Recent work shows that under a stochastic assumption on job arrivals, there is a single-parameter family of mechanisms that achieves near-optimal social welfare. We show that given any such family of near-optimal online mechanisms, there exists an online mechanism that in the worst case performs nearly as well as the best of the given mechanisms. Our mechanism is truthful whenever the mechanisms in the given family are truthful and prompt, and achieves optimal (within constant factors) regret.

We provide a polynomial-time reduction from Bayesian incentive-compatible mechanism design to Bayesian algorithm design for welfare maximization problems. Unlike prior results, our reduction achieves exact incentive compatibility for problems with multi-dimensional and continuous type spaces.

Nearly fifteen years ago, Google unveiled the generalized second price (GSP) auction. By all theoretical accounts including their own [Varian 14], this was the wrong auction --- the Vickrey-Clarke-Groves (VCG) auction would have been the proper choice --- yet GSP has succeeded spectacularly.

For selling a single item to agents with independent but non-identically distributed values, the revenue optimal auction is complex. With respect to it, Hartline and Rough garden showed that the approximation factor of the second-price auction with an anonymous reserve is between two and four. We consider the more demanding problem of approximating the revenue of the ex ante relaxation of the auction problem by posting an anonymous price (while supplies last) and prove that their worst-case ratio is e. As a corollary, the upper-bound of anonymous pricing or anonymous reserves versus the optimal auction improves from four to e. We conclude that, up to an e factor, discrimination and simultaneity are unimportant for driving revenue in single-item auctions.

For a number of problems in the theory of online algorithms, it is known that the assumption that elements arrive in uniformly random order enables the design of algorithms with much better performance guarantees than under worst-case assumptions. The quintessential example of this phenomenon is the secretary problem, in which an algorithm attempts to stop a sequence at the moment it observes the maximum value in the sequence. As is well known, if the sequence is presented in uniformly random order there is an algorithm that succeeds with probability 1/e, whereas no non-trivial performance guarantee is possible if the elements arrive in worst-case order.