天美传媒

Date Posted:Mon, 13 May 2024 14:14:43 -0500
As digital marketplaces and services continue to expand, it is crucial to maintain a safe and fair environment for all users. This requires implementing fairness constraints into the sequential decision-making processes of these platforms to ensure equal treatment. However, this can be challenging as these processes often need to solve NP-complete problems with exponentially large decision spaces at each time step. To overcome this, we propose a general framework incorporating robustness and fairness into NP-complete problems, such as optimizing product rankings and maximizing sub-modular functions. Our framework casts the problem as a max-min game between a primal player aiming to maximize the platform's objective and a dual player in charge of group fairness constraints. We show that one can trace the entire Pareto fairness curve by changing the thresholds on the fairness constraints. We provide theoretical guarantees for our method and empirically evaluate it, demonstrating its effectiveness.

Date Posted:Mon, 22 Apr 2024 00:00:00 -0500
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 X_1, X_2, ... 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 X_i, we can still discard X_i later and accept another variable X_j, at a \textit{buyback cost} of fX_i. 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 ? ?(f log(1/f)). Our results are obtained by two fundamentally different approaches: One is inspire

Date Posted:Thu, 11 Apr 2024 00:00:00 -0500
Primarily motivated by applications in cloud computing marketplaces, we study a simple, yet powerful, adversarial online allocation problem in which jobs of various lengths arrive online over continuous time and upon arrival are immediately and irrevocably assigned to one of the available offline servers (if any). The servers have given initial capacity. Once a job is assigned to a server, the job uses one unit of capacity for its duration and releases this unit once it is finished. In addition, the algorithm obtains a reward from this assignment. We consider a general heterogeneous model where both the reward and duration of each job assignment can depend on the job-server pair. The goal of the online algorithm is to sequentially assign jobs to servers to maximize the total collected rewards and aims to be online competitive against an omniscient optimal benchmark that knows all the jobs in advance. Our main result is designing a new family of online assignment algorithms, which we call "Forward-Looking BALANCE (FLB)", and using a primal-dual framework to show that this family obtains an asymptotically optimal competitive ratio in various regimes if we choose a proper member.

In summary, this meta-algorithm has two important primitives: (i) keeping track of the capacity used for each server at each time and applying a penalty function to this quantity, and (ii) adjusting the reward of assigning an arriving job to a server by subtracting the total penalty of a particu

Date Posted:Fri, 05 Apr 2024 19:26:59 -0500
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

Date Posted:Tue, 26 Mar 2024 00:00:00 -0500
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). This problem is primarily motivated by the staffing challenges that arise in last-mile delivery operations. A company such as Amazon has access to flexible gig economy workers (through Amazon Flex) whose availability decreases closer to the target operating day, but they can be hired at any time before that day if they are available.

We study the above problem when predictions take the form of uncertainty intervals that encompass the true demand. The goal of the decision-maker is to minimize the staffing imbalance cost at the end of the horizon against any sequence of prediction intervals being chosen by an adversary. Our main result is the characterization of a simple and computationally efficient online algorithm that obtains the optimal worst-case imbalance cost; said differently, it is minimax optimal. At high level, our algorithm relies on identifying a restr

Date Posted:Mon, 27 Feb 2023 00:00:00 -0600
In domains like digital health or EdTech, recommendation systems often encounter a critical
challenge: users, driven by impulsive or short-sighted tendencies, exhibit preferences that starkly
contrast with the platform?s forward-looking, long-term payoffs. This discrepancy complicates
the task of learning-to-rank items to maximize the platform?s total payoff, as it may lead to
insufficient exploration on higher payoff items due to misalignment between user preferences
and platform payoffs. Our paper addresses this challenge by leveraging the limited attention
span of users, known as position bias. We consider a simple model in which a platform displays
a ranked list of items in an online fashion to a sequence of T arriving users. At each time, the
arriving user selects an item by first considering a prefix window of a certain size of these ranked
items and then picking the highest preferred item in that window (and the platform observes
its payoff for this item as feedback). We study how to exploit the combinatorial structure of
our model to design online learning algorithms that learn and optimize the unknown collected
payoffs and obtain vanishing regret with respect to hindsight optimal benchmarks.

We first consider the bandit online learning problem with adversarial window sizes and
stochastic i.i.d. payoffs. We design an active-elimination-based algorithm that achieves an optimal instance-dependent regret bound of O(log(T )),

Date Posted:Mon, 06 Feb 2023 00:00:00 -0600
We study a general class of constrained sequential search problems for selecting multiple candidates from a pool that belongs to different societal groups. We focus on search processes under ex-ante constraints primarily motivated by inducing societally desirable outcomes such as attaining demographic parity among different groups, achieving diversity through quotas, or subsidizing disadvantaged groups within budget. We start with a canonical search model, known as the Pandora's box model (Weitzman, 1979), under a single affine constraint on the probability of selection and inspection of each candidate. We show that the optimal policy for such a constrained problem retains the index-based structure of the optimal policy for the unconstrained one but potentially randomizes between two policies that are dual-based adjustments of the unconstrained problem; thus they are easy to compute and economically interpretable. Building on these insights, we consider the richer class of search processes, such as search with rejection and multistage search, that can be modeled by joint Markov scheduling (JMS) (Dumitriu et al., 2003; Gittins, 1979). Imposing general affine and convex ex-ante constraints, we give a primal-dual algorithm to find the near-feasible and near-optimal policy. This algorithm, too, randomizes over index-based policies; this time, over a polynomial number of policies whose indices are dual-based adjustments to the Gittins indices of the unconstrained JMS. Our algori

Date Posted:Mon, 31 Oct 2022 21:12:00 -0500
We study the classic online bipartite matching problem with a twist: offline vertices, called resources, are reusable. In particular, when a resource is matched to an online vertex it is unavailable for a deterministic time duration d after which it becomes available again for a re-match. Thus, a resource can be matched to many different online vertices over a period of time. While recent work on the problem have resolved the asymptotic case where we have large starting inventory (i.e., many copies) of every resource, we consider the (more general) case of unit inventory} and give the first algorithms that are provably better than the naive greedy approach which has a competitive ratio of (exactly) 0.5. Our first algorithm, which achieves a competitive ratio of 0.589, generalizes the classic RANKING algorithm for online bipartite matching of non-reusable resources (Karp et al., 1990), by "reranking" resources independently over time. While reranking resources frequently has the same worst case performance as greedy, we show that reranking intermittently on a periodic schedule succeeds in addressing reusability of resources and performs significantly better than greedy in the worst case. Our second algorithm, which achieves a competitive ratio of 0.505, is a primal-dual randomized algorithm that works by suggesting up to two resources as candidate matches for every online vertex, and then breaking the tie to make the final matching selection in a randomized correlated fashion

Date Posted:Wed, 19 Oct 2022 02:05:14 -0500
Motivated by applications in hotel upsell revenue management and selling banner ads on popular websites, we study the online resource allocation problem with overbooking and cancellation costs, also known as the "buyback" setting. To model this problem, we consider a variation of the classic edge-weighted online matching problem in which the decision maker can reclaim 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 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. Interestingly, our result shows a phase transition: for small buyback regime, i.e., f<(e-2)/2, the optimal competitive ratio is e/(e-1-f), and for large buyback regime, i.e., f>(e-2)/2, the competitive ratio is W(-1/(e(1+f))), when W is the non-principal branch of the Lambert W function.

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. We further study lower and upper bounds on the competitive ratio in variants of this model, e.

Date Posted:Mon, 15 Aug 2022 04:10:19 -0500
Experimentation is prevalent in online marketplaces and social networks to assess the effectiveness of new market intervention. To mitigate the interference among users in an experiment, a common practice is to use a cluster-based experiment, where the designer partitions the market into loosely connected clusters and assigns all users in the same cluster to the same variant (treatment or control). Given the experiment, we assume an unbiased Horvitz-Thompson estimator is used to estimate the total market effect of the treatment. We consider the optimization problem of choosing (correlated) randomized assignments of clusters to treatment and control to minimize the worst-case variance of the estimator under a constraint that the marginal assignment probability is q \in (0,1) for all clusters. This problem can be formulated as a linear program where both the number of decision variables and constraints are exponential in the number of clusters---and hence is generally computationally ...

Date Posted:Mon, 20 Jun 2022 09:49:21 -0500
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 ...

Date Posted:Mon, 13 Jun 2022 09:53:22 -0500
Experimentation is prevalent in online marketplaces and social networks to assess the effectiveness of new market intervention. To mitigate the interference among users in an experiment, a common practice is to use a cluster-based experiment, where the designer partitions the market into loosely connected clusters and assigns all users in the same cluster to the same variant (treatment or control). Given the experiment, we assume an unbiased Horvitz-Thompson estimator is used to estimate the total market effect of the treatment. We consider the optimization problem of choosing (correlated) randomized assignments of clusters to treatment and control to minimize the worst-case variance of the estimator under a constraint that the marginal assignment probability is q \in (0,1) for all clusters. This problem can be formulated as a linear program where both the number of decision variables and constraints are exponential in the number of clusters---and hence is generally computationally ...

Date Posted:Tue, 10 May 2022 09:48:37 -0500
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 all the initial inventories are no less than c_min, our main result is a near-optimal 1-min(1/2,\sqrt{log(c_min)/c_min}) competitive algorithm for the general case of reusable resources. As a side result, by leveraging techniques from the literature on prophet inequality, we further show an improved near-optimal 1-1/\sqrt{c_min+3} competitive algorithm for the special case of non-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 ...

Date Posted:Mon, 28 Mar 2022 20:13:04 -0500
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 p_1 > p_2 >... > p_k for the auction clock such that auction expected revenue is maximized. The prices 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/e^k 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.

Date Posted:Wed, 16 Feb 2022 13:47:48 -0600
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 ...

Date Posted:Tue, 25 Jan 2022 13:48:38 -0600
We study a 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.

First, using a reduction to maximizing submodular functions over matroids, we give an optimal (1-1/e)-approximation for this problem. We then consider a variant in which the platform cares not only about user engagement, but also about diversification across various groups of users, that is, guaranteeing a certain ...

Date Posted:Tue, 25 Jan 2022 13:48:05 -0600
Matching and pricing are two critical levers in two-sided marketplaces to connect demand and supply. The platform can produce more efficient matching and pricing decisions by batching the demand requests. We initiate the study of the two-stage stochastic matching problem, with or without pricing, to enable the platform to make improved decisions in a batch with an eye toward the imminent future demand requests. This problem is motivated in part by applications in online marketplaces such as ride hailing platforms.

We design online competitive algorithms for vertex-weighted (or unweighted) two-stage stochastic matching for maximizing supply efficiency, and two-stage joint matching and pricing for maximizing market efficiency. In the former problem, 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. Using a factor revealing program and connections to ...

Date Posted:Tue, 25 Jan 2022 12:52:09 -0600
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. To better achieve their dual aims of equity and efficiency in such contexts, social planners intend to maximize the minimum fill rate across agents, where each agent's fill rate (i.e., the fraction of its demand that is satisfied) is determined by a one-time allocation that must be irrevocably decided upon its arrival. For an arbitrarily correlated sequence of demands, we establish upper bounds on both the expected minimum fill rate (ex-post fairness) and the minimum expected fill rate (ex-ante fairness) achievable by any policy. Our ...

Date Posted:Fri, 21 Jan 2022 09:56:49 -0600
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. To better achieve their dual aims of equity and efficiency in such contexts, social planners intend to maximize the minimum fill rate across agents, where each agent's fill rate (i.e., the fraction of its demand that is satisfied) is determined by a one-time allocation that must be irrevocably decided upon its arrival. For an arbitrarily correlated sequence of demands, we establish upper bounds on both the expected minimum fill rate (ex-post fairness) and the minimum expected fill rate (ex-ante fairness) achievable by any policy. Our ...

Date Posted:Fri, 21 Jan 2022 09:56:49 -0600
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. To better achieve their dual aims of equity and efficiency in such contexts, social planners intend to maximize the minimum fill rate across agents, where each agent's fill rate (i.e., the fraction of its demand that is satisfied) is determined by a one-time allocation that must be irrevocably decided upon its arrival. For an arbitrarily correlated sequence of demands, we establish upper bounds on both the expected minimum fill rate (ex-post fairness) and the minimum expected fill rate (ex-ante fairness) achievable by any policy. Our ...

Date Posted:Wed, 19 Jan 2022 15:10:57 -0600
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. To better achieve their dual aims of equity and efficiency in such contexts, social planners intend to maximize the minimum fill rate across agents, where each agent's fill rate (i.e., the fraction of its demand that is satisfied) is determined by a one-time allocation that must be irrevocably decided upon its arrival. For an arbitrarily correlated sequence of demands, we establish upper bounds on both the expected minimum fill rate (ex-post fairness) and the minimum expected fill rate (ex-ante fairness) achievable by any policy. Our ...

Date Posted:Wed, 19 Jan 2022 04:28:33 -0600
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 show that the resulting online algorithms have $O(\sqrt{T})$ (approximate) regret under the full information setting. We further introduce a bandit extension of Blackwell approachability that we call Bandit Blackwell approachability. We leverage this notion to transform greedy robust offline algorithms into a $O(T^{2/3})$ (approximate) regret in the bandit setting. Demonstrating the flexibility of our framework, we apply our offline-to-online transformation to several problems at the intersection of revenue ...

Date Posted:Mon, 03 Jan 2022 05:52:11 -0600
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 show that the resulting online algorithms have $O(\sqrt{T})$ (approximate) regret under the full information setting. We further introduce a bandit extension of Blackwell approachability that we call Bandit Blackwell approachability. We leverage this notion to transform greedy robust offline algorithms into a $O(T^{2/3})$ (approximate) regret in the bandit setting. Demonstrating the flexibility of our framework, we apply our offline-to-online transformation to several problems at the intersection of revenue ...

Date Posted:Wed, 29 Sep 2021 18:20:37 -0500
Motivated by the prevalence of experimentation in online platforms and social networks, we consider the problem of designing randomized experiments to assess the effectiveness of a new market intervention for a network of users. An experiment assigns each user to either the treatment or the control group. The outcome of each user depends on her assignment as well as the assignments of her neighbors. Given the experiment, the unbiased Horvitz-Thompson estimator is used to estimate the total market effect of the treatment. The decision maker chooses randomized assignments of users to treatment and control, in order to minimize the worst-case variance of this estimator. We focus on networks that can be partitioned into communities, where the users in the same community are densely connected, and users from different communities are only loosely connected. In such settings, it is almost without loss to assign all users in the same community to the same variant (treatment or control). ...

Date Posted:Mon, 20 Sep 2021 06:36:09 -0500
In modern applications of real-time resource allocation, for example allocating ad opportunities created by users to relevant advertisers during video streaming, a prevalent scenario is when an arriving user can be served under different "configurations''. For example, in video advertising, a configuration can be an arrangement of video-ads of various lengths and formats for a subset of advertisers, showing up at different time-stamps of the video. Each selected configuration assigns a certain number of impressions to each advertiser. Depending on their long-term contracts, each advertiser is willing to pay for a certain number of impressions during the decision making horizon at a per-impression price depending on the assigned configuration. While this application is real-time, there is an inherent allowance for latency in showing ads to users, as several of these ads show up in the middle (or at the end) of the video. This provides an opportunity for ad allocator to batch the users and to make more profitable allocation decisions. While designing algorithms for the fully online variant of this setting has been studied in the literature [Devanur et al., 2016], the multi-stage variant where the allocation decisions are made batch-by-batch is not studied.


Motivated by the above application, we study designing optimal competitive multi-stage configuration allocation algorithms (with preemption) in an adversarial setting, where users arrive in batches in a stage-wise

Date Posted:Tue, 24 Aug 2021 10:55:09 -0500
In several applications of real-time matching of demand to supply in online marketplaces, the platform allows for some latency to batch the demand and improve the efficiency of the resulting matching. Motivated by these applications, we study the optimal trade-off between batching and inefficiency in the context of designing robust online allocations. In particular, we consider K-stage variants of the classic vertex weighted bipartite b-matching and AdWords problems in the adversarial setting, where online vertices arrive stage-wise and in K batches---in contrast to online arrival. 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 ratio bound known for the online variants of these problems (Mehta et al., 2007; Aggarwal et al., 2011).

Our main technique at high-level is developing algorithmic tools to vary the trade-off between "greedy-ness' and `"hedging" of the matching ...

Date Posted:Mon, 16 Aug 2021 19:04:52 -0500
Motivated by the prevalence of experimentation in online platforms and social networks, we consider the problem of designing randomized experiments to assess the effectiveness of a new market intervention for a network of users. An experiment assigns each user to either the treatment or the control group. The outcome of each user depends on her assignment as well as the assignments of her neighbors. Given the experiment, the unbiased Horvitz-Thompson estimator is used to estimate the total market effect of the treatment. The decision maker chooses randomized assignments of users to treatment and control, in order to minimize the worst-case variance of this estimator. We focus on networks that can be partitioned into communities, where the users in the same community are densely connected, and users from different communities are only loosely connected. In such settings, it is almost without loss to assign all users in the same community to the same variant (treatment or control). ...

Date Posted:Wed, 16 Jun 2021 04:05:18 -0500
Motivated by the prevalence of experimentation in online platforms and social networks, we consider the problem of designing randomized experiments to assess the effectiveness of a new market intervention for a network of users. An experiment assigns each user to either the treatment or the control group. The outcome of each user depends on her assignment as well as the assignments of her neighbors. Given the experiment, the unbiased Horvitz-Thompson estimator is used to estimate the total market effect of the treatment. The decision maker chooses randomized assignments of users to treatment and control, in order to minimize the worst-case variance of this estimator. We focus on networks that can be partitioned into communities, where the users in the same community are densely connected, and users from different communities are only loosely connected. In such settings, it is almost without loss to assign all users in the same community to the same variant (treatment or control). The ...

Date Posted:Wed, 02 Jun 2021 15:17:48 -0500
Motivated by the prevalence of experimentation in online platforms and social networks, we consider the problem of designing a randomized experiment to assess the effectiveness of a new treatment for a network of users. The outcome of each user depends on the assignment of the treatment to her as well as her neighbors. Given the experiment, the unbiased Horvitz-Thompson estimator is used to estimate the total market effect of the treatment. The decision-maker chooses an optimal joint distribution of randomized assignments of users to treatment and control, in order to minimize the worst-case variance of this estimator. We focus on networks that can be partitioned into communities, where the users in the same community are densely connected, and users from different communities are only loosely connected. In such settings, it is near-optimal to assign all users in the same community to the same variant (treatment or control). The problem of designing the optimal randomized assignments ...

Date Posted:Wed, 02 Jun 2021 15:17:23 -0500
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. To better achieve their dual aims of equity and efficiency in such contexts, social planners intend to maximize the minimum fill rate across agents, where each agent's fill rate must be irrevocably decided upon its arrival. For an arbitrarily correlated sequence of demands, we establish upper bounds on both the expected minimum fill rate (ex-post fairness) and the minimum expected fill rate (ex-ante fairness) achievable by any policy. Our bounds are parameterized by the number of agents and the expected demand-to-supply ratio, and they ...

Date Posted:Tue, 01 Jun 2021 19:07:38 -0500
Experimentation is prevalent in online marketplaces and social networks to assess the effectiveness of new market intervention. To mitigate the interference among users in an experiment, a common practice is to use a cluster-based experiment, where the designer partitions the market into loosely connected clusters and assigns all users in the same cluster to the same variant (treatment or control). Given the experiment, we assume an unbiased Horvitz-Thompson estimator is used to estimate the total market effect of the treatment. We consider the optimization problem of choosing (correlated) randomized assignments of clusters to treatment and control to minimize the worst-case variance of the estimator under a constraint that the marginal assignment probability is q \in (0,1) for all clusters. This problem can be formulated as a linear program where both the number of decision variables and constraints are exponential in the number of clusters---and hence is generally computationally intractable.

We develop a family of practical experiments that we refer to as \emph{independent block randomization (IBR)} experiments. Such an experiment partitions clusters into blocks so that each block contains clusters of similar size. It then treats a fraction q of the clusters in each block (chosen uniformly at random) and does so independently across blocks. The optimal cluster partition can be obtained in a tractable way using dynamic programming. We show that these policies are asy

Date Posted:Tue, 01 Jun 2021 10:11:28 -0500
Motivated by the prevalence of experimentation in online platforms and social networks, we consider the problem of designing a randomized experiment to assess the effectiveness of a new treatment for a network of users. The outcome of each user depends on the assignment of the treatment to her as well as her neighbors. Given the experiment, the unbiased Horvitz-Thompson estimator is used to estimate the total market effect of the treatment. The decision-maker chooses an optimal joint distribution of randomized assignments of users to treatment and control, in order to minimize the worst-case variance of this estimator. We focus on networks that can be partitioned into communities, where the users in the same community are densely connected, and users from different communities are only loosely connected. In such settings, it is near-optimal to assign all users in the same community to the same variant (treatment or control). The problem of designing the optimal randomized assignments ...

Date Posted:Mon, 17 May 2021 05:58:23 -0500
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 show that the resulting online algorithms have O(T^{1/2}) (approximate) regret under the full information setting. We further introduce a bandit extension of Blackwell approachability that we call Bandit Blackwell approachability. We leverage this notion to transform greedy robust offline algorithms into a O(T^{2/3})(approximate) regret in the bandit setting. Demonstrating the flexibility of our framework, we apply our offline-to-online transformation to several problems at the intersection of revenue ...

Date Posted:Mon, 17 May 2021 05:55:45 -0500
Matching and pricing are two critical levers in two-sided marketplaces to connect demand and supply. The platform can produce more efficient matching and pricing decisions by batching the demand requests. We initiate the study of the two-stage stochastic matching problem, with or without pricing, to enable the platform to make improved decisions in a batch with an eye toward the imminent future demand requests. This problem is motivated in part by applications in online marketplaces such as ride hailing platforms.

We design online competitive algorithms for vertex-weighted (or unweighted) two-stage stochastic matching for maximizing supply efficiency, and two-stage joint matching and pricing for maximizing market efficiency. In the former problem, 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. Using a factor revealing program and connections to ...

Date Posted:Tue, 27 Apr 2021 12:39:59 -0500
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 ...

Date Posted:Tue, 27 Apr 2021 12:39:30 -0500
Matching and pricing are two critical levers in two-sided marketplaces to connect demand and supply. The platform can produce more efficient matching and pricing decisions by batching the demand requests. We initiate the study of the two-stage stochastic matching problem, with or without pricing, to enable the platform to make improved decisions in a batch with an eye toward the imminent future demand requests. This problem is motivated in part by applications in online marketplaces such as ride hailing platforms.

We design online competitive algorithms for vertex-weighted (or unweighted) two-stage stochastic matching for maximizing supply efficiency, and two-stage joint matching and pricing for maximizing market efficiency. In the former problem, 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. Using a factor revealing program and connections to ...

Date Posted:Sun, 25 Apr 2021 04:28:17 -0500
Matching and pricing are two critical levers in two-sided marketplaces to connect demand and supply. The platform can produce more efficient matching and pricing decisions by batching the demand requests. We initiate the study of the two-stage stochastic matching problem, with or without pricing, to enable the platform to make improved decisions in a batch with an eye toward the imminent future demand requests. This problem is motivated in part by applications in online marketplaces such as ride hailing platforms.

We design online competitive algorithms for vertex-weighted (or unweighted) two-stage stochastic matching for maximizing supply efficiency, and two-stage joint matching and pricing for maximizing market efficiency. In the former problem, 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. Using a factor revealing program and connections to ...

Date Posted:Tue, 20 Apr 2021 07:49:43 -0500
We study a 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.

First, using a reduction to maximizing submodular functions over matroids, we give an optimal (1-1/e)-approximation for this problem. We then consider a variant in which the platform cares not only about user engagement, but also about diversification across various groups of users, that is, guaranteeing a certain ...

Date Posted:Tue, 02 Mar 2021 18:22:39 -0600
In classic adversarial online resource allocation problems, such as matching, AdWords, or assortment plan- ning, customers (demand) arrive online, while products (supply) are given offline with a fixed initial inventory. To ensure acceptable revenue guarantees given the uncertainty in future customer arrivals, the decision maker must balance consumption across different products. Motivated by this, the famous policy ? \emph{inventory balancing (IB)} ? is introduced and studied in the literature and has proved to be optimal or near-optimal competitive in almost all classic settings. However, an important feature that these classic models do not capture are various forms of possible inventory shocks on the supply side, which plays an important role in several real-world applications of online assortment and could significantly impact the revenue performance of the IB algorithm.

Motivated by this, we introduce and study a new variant of online assortment planning with inventory shocks. Our model considers both exogenous shocks (e.g., due to purchase returns from another channel or misalignment between inventory management and sale) that are adversarial, and endogenous shocks (due to return of sold units by employing a simple restocking strategy with a lead time). For the objective of maximizing total revenue, we show that the original IB no longer achieves the optimal competitive ratio in this new model. In contrast, we design a new family of algorithms, which we call \em

Date Posted:Thu, 18 Feb 2021 03:43:19 -0600
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. To better achieve their dual aims of equity and efficiency in such contexts, social planners intend to maximize the minimum fill rate across agents, where each agent's fill rate must be irrevocably decided upon its arrival. For an arbitrarily correlated sequence of demands, we establish upper bounds on both the expected minimum fill rate (ex-post fairness) and the minimum expected fill rate (ex-ante fairness) achievable by any policy. Our bounds are parameterized by the number of agents and the expected demand-to-supply ratio, and they ...

Date Posted:Tue, 02 Feb 2021 22:55:52 -0600
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 theoret

Date Posted:Tue, 02 Feb 2021 12:59:02 -0600
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. To better achieve their dual aims of equity and efficiency in such contexts, social planners intend to maximize the minimum fill rate across agents, where each agent's fill rate must be irrevocably decided upon its arrival. For an arbitrarily correlated sequence of demands, we establish upper bounds on both the expected minimum fill rate (ex-post fairness) and the minimum expected fill rate (ex-ante fairness) achievable by any policy. Our bounds are parameterized by the number of agents and the expected demand-to-supply ratio, and they ...

Date Posted:Thu, 21 Jan 2021 04:27:51 -0600
Matching and pricing are two critical levers in two-sided marketplaces to connect demand and supply. The platform can produce more efficient matching and pricing decisions by batching the demand requests. We initiate the study of the two-stage stochastic matching problem, with or without pricing, to enable the platform to make improved decisions in a batch with an eye toward the imminent future demand requests. This problem is motivated in part by applications in online marketplaces such as ride hailing platforms.

We design online competitive algorithms for vertex-weighted (or unweighted) two-stage stochastic matching for maximizing supply efficiency, and two-stage joint matching and pricing for maximizing market efficiency. In the former problem, 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. Using a novel factor revealing program and connections ...

Date Posted:Wed, 13 Jan 2021 22:04:51 -0600
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 [x_ij] and asked to sample a matching such that the probability of each edge (i,j) be present in the matching is exactly equal to x_ij.

We show that a polytope P admits a Bernoulli factory if and and only if P is the intersection of [0, 1]^n with an affine subspace. Our construction is based on an algebraic formulation of the problem, involving identifying a family of Bernstein polynomials (one per vertex) that satisfy a certain algebraic identity on P. The main technical tool behind our construction is a connection between these polynomials and the geometry of zonotope tilings. We apply these results to construct an explicit factory for the perfect matching polytope. The resulting factory is deeply connected to the combinatorial enumeration of arborescences and may

Date Posted:Wed, 13 Jan 2021 12:08:19 -0600
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 [x_ij] and asked to sample a matching such that the probability of each edge (i,j) be present in the matching is exactly equal to x_ij.

We show that a polytope P admits a Bernoulli factory if and and only if P is the intersection of [0, 1]^n with an affine subspace. Our ...

Date Posted:Thu, 07 Jan 2021 03:56:52 -0600
We study a 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.

First, using a reduction to maximizing submodular functions over matroids, we give an optimal (1-1/e)-approximation for this problem. We then consider a variant in which the platform cares not only about user engagement, but also about diversification across various groups of users, that is, guaranteeing a certain ...

Date Posted:Thu, 22 Oct 2020 07:08:08 -0500
Standard ad auction formats do not immediately extend to settings where multiple size configurations and layouts are available to advertisers. In these settings, the sale of web advertising space increasingly resembles a combinatorial auction with complementarities, where truthful auctions such as the Vickrey-Clarke-Groves (VCG) can yield unacceptably low revenue. We therefore study core selecting auctions, which boost revenue by setting payments so that no group of agents, including the auctioneer, can jointly improve their utilities by switching to a different outcome. Our main result is a combinatorial algorithm that finds an approximate bidder optimal core point with almost linear number of calls to the welfare maximization oracle. Our algorithm is faster than previously-proposed heuristics in the literature and has theoretical guarantees. We conclude that core pricing is implementable even for very time sensitive practical use cases such as realtime auctions for online ...

Date Posted:Thu, 22 Oct 2020 03:38:16 -0500
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,\sqrt{log(c_min)/c_min}) competitive algorithm for the general case of reusable resources. For the special case of non-reusable resources, we further show an improved near-optimal 1-1/\sqrt{c_min+3} competitive algorithm.

Our algorithms rely on an expected LP benchmark for the problem, solve this LP, and simulate the solution through an independent randomized rounding. To obtain point-wise inventory feasibility in a computationally efficient fashion from these simulation-based ...

Date Posted:Wed, 21 Oct 2020 16:05:39 -0500
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 all the initial inventories are no less than c_min, our main result is a near-optimal 1-min(1/2,\sqrt{log(c_min)/c_min}) competitive algorithm for the general case of reusable resources. As a side result, by leveraging techniques from the literature on prophet inequality, we further show an improved near-optimal 1-1/\sqrt{c_min+3} competitive algorithm for the special case of non-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 introdu

Date Posted:Wed, 21 Oct 2020 16:04:28 -0500
Standard ad auction formats do not immediately extend to settings where multiple size configurations and layouts are available to advertisers. In these settings, the sale of web advertising space increasingly resembles a combinatorial auction with complementarities, where truthful auctions such as the Vickrey-Clarke-Groves (VCG) can yield unacceptably low revenue. We therefore study core selecting auctions, which boost revenue by setting payments so that no group of agents, including the auctioneer, can jointly improve their utilities by switching to a different outcome. Our main result is a combinatorial algorithm that finds an approximate bidder optimal core point with almost linear number of calls to the welfare maximization oracle. Our algorithm is faster than previously-proposed heuristics in the literature and has theoretical guarantees. We conclude that core pricing is implementable even for very time sensitive practical use cases such as realtime auctions for online advertising and can yield more revenue. We justify this claim experimentally using the Microsoft Bing Ad Auction data, through which we show our core pricing algorithm generates almost 26% more revenue than VCG on average, about 9% more revenue than other core pricing rules known in the literature, and almost matches the revenue of the standard Generalized Second Price (GSP) auction.

Date Posted:Wed, 21 Oct 2020 07:05:40 -0500
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,\sqrt{log(c_min)/c_min}) competitive algorithm for the general case of reusable resources. For the special case of non-reusable resources, we further show an improved near-optimal 1-1/\sqrt{c_min+3} competitive algorithm.

Our algorithms rely on an expected LP benchmark for the problem, solve this LP, and simulate the solution through an independent randomized rounding. To obtain point-wise inventory feasibility in a computationally efficient fashion from these simulation-based ...

Date Posted:Wed, 21 Oct 2020 07:04:28 -0500
Standard ad auction formats do not immediately extend to settings where multiple size configurations and layouts are available to advertisers. In these settings, the sale of web advertising space increasingly resembles a combinatorial auction with complementarities, where truthful auctions such as the Vickrey-Clarke-Groves (VCG) can yield unacceptably low revenue. We therefore study core selecting auctions, which boost revenue by setting payments so that no group of agents, including the auctioneer, can jointly improve their utilities by switching to a different outcome. Our main result is a combinatorial algorithm that finds an approximate bidder optimal core point with almost linear number of calls to the welfare maximization oracle. Our algorithm is faster than previously-proposed heuristics in the literature and has theoretical guarantees. We conclude that core pricing is implementable even for very time sensitive practical use cases such as realtime auctions for online ...

Date Posted:Mon, 28 Sep 2020 03:45:00 -0500
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 ...

Date Posted:Fri, 11 Sep 2020 03:26:41 -0500
In many application 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 identifying a particular sequence of polynomials with decreasing degrees that can be used as strictly concave regularizers. We then show the fractional online algorithm that returns the corresponding regularized maximum weight fractional matchings in ...

Date Posted:Fri, 11 Sep 2020 03:26:28 -0500
Matching and pricing are two critical levers in ride sharing marketplaces to match demand and supply. There, the platform can produce more efficient matching and pricing decisions by batching the requests. The goal of this paper is extending this batching paradigm to enable the platform to make such decisions in a batch with an eye toward the future. We therefore study the "two-stage stochastic matching problem", with or without pricing.

We design online competitive algorithms for driver-weighted two-stage stochastic matching for maximizing supply efficiency, and two-stage joint matching and pricing for maximizing market efficiency. In the former problem, by a primal-dual analysis, we show a family of convex-programming based matchings that distribute the demand in a balanced way among supply obtain the optimal 3/4-competitive ratio against the optimum offline benchmark. Using a novel factor revealing program and connections to submodular optimization, we improve this ratio ...

Date Posted:Fri, 11 Sep 2020 03:26:07 -0500
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 show that the resulting online algorithms have O(T^{1/2}) (approximate) regret under the full information setting. We further introduce a bandit extension of Blackwell approachability that we call Bandit Blackwell approachability. We leverage this notion to transform greedy robust offline algorithms into a O(T^{2/3})(approximate) regret in the bandit setting. Demonstrating the flexibility of our framework, we apply our offline-to-online transformation to several problems at the intersection of revenue ...

Date Posted:Fri, 11 Sep 2020 03:22:36 -0500
We study a 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 makes a decision 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.

First, using a reduction to maximizing submodular functions over matroids we give an optimal (1-1/e)-approximation for this problem. We then consider a variant in which the platform not only cares about user engagement, but also cares about diversification across various groups of users, that is, guaranteeing a ...

Date Posted:Fri, 11 Sep 2020 03:20:58 -0500
Motivated by applications of rental services in e-commerce, we consider real-time assortment of reusable products. In our model, arriving consumers with heterogeneous types choose rental products from the offered assortment, pay the rental fees, and return the product to the platform after a rental time. Consumers' types specify their choice models, rental fees and rental time distributions for various products. Our goal is to design competitive online policies against an appropriate benchmark for both the prior-free setting, in which types are arbitrary (or adversarial), and the Bayesian setting, in which types are drawn independently from known distributions.

Our contribution is threefold. We first introduce offline linear programming benchmarks in both settings, that use time-varying inventory constraints to capture feasibility of a policy under rentals, and are required to satisfy these constraints only in expectation. Second, in the prior-free setting, we ...

Date Posted:Fri, 11 Sep 2020 03:20:19 -0500
In the Bayesian online selection problem, the goal is to design a pricing scheme for a sequence of arriving buyers that maximizes the expected social-welfare (or revenue) subject to different types of structural constraints. Inspired by applications in operations management, the focus of this paper is on the cases where the set of served customers is characterized by a laminar matroid.

We give the first Polynomial-Time Approximation Scheme (PTAS) for the problem when the laminar matroid has constant depth. Our approach is based on rounding the solution of a hierarchy of linear programming relaxations that approximate the optimum online solution with any degree of accuracy plus a concentration argument that shows the rounding incurs a small loss. We also study another variation, which we call the production constrained problem, for which the allowable set of served customers is characterized by a collection of production and shipping constraints forming a certain form of ...

Date Posted:Thu, 10 Sep 2020 13:50:43 -0500
In several applications of real-time matching of demand to supply in online marketplaces, the platform allows for some latency to batch the demand and improve the efficiency of the resulting matching. Motivated by these applications, we study the optimal trade-off between batching and inefficiency in the context of designing robust online allocations. As our base model, we consider K-stage variants of the classic vertex weighted bipartite b-matching in the adversarial setting, where online vertices arrive stage-wise and in K batches ? in contrast to online arrival. Our main result for this problem is an optimal 1?(1?1/K)^K- competitive (fractional) matching algorithm, improving the classic (1 ? 1/e) competitive ratio bound known for its online variant (Mehta et al., 2007; Aggarwal et al., 2011). We also extend this result to the rich model of multi-stage configuration allocation with free-disposals (Devanur et al., 2016), which is motivated by the display advertising application in the context of video streaming platforms.

Our main technique at high-level is developing algorithmic tools to vary the trade-off between ?greedy- ness? and ?hedging? of the matching algorithm across stages. We rely on a particular family of convex- programming based matchings that distribute the demand in a specifically balanced way among supply in different stages, while carefully modifying the balancedness of the resulting matching across stages. More precisely, we identify a sequence of p

Date Posted:Thu, 10 Sep 2020 04:50:43 -0500
In many application 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 identifying a particular sequence of polynomials with decreasing degrees that can be used as strictly concave regularizers. We then show the fractional online algorithm that returns the corresponding regularized maximum weight fractional matchings in ...

Date Posted:Thu, 10 Sep 2020 04:10:06 -0500
In the Bayesian online selection problem, the goal is to design a pricing scheme for a sequence of arriving buyers that maximizes the expected social-welfare (or revenue) subject to different types of structural constraints. Inspired by applications in operations management, the focus of this paper is on the cases where the set of served customers is characterized by a laminar matroid.

We give the first Polynomial-Time Approximation Scheme (PTAS) for the problem when the laminar matroid has constant depth. Our approach is based on rounding the solution of a hierarchy of linear programming relaxations that approximate the optimum online solution with any degree of accuracy plus a concentration argument that shows the rounding incurs a small loss. We also study another variation, which we call the production constrained problem, for which the allowable set of served customers is characterized by a collection of production and shipping constraints forming a certain form of ...

Date Posted:Thu, 10 Sep 2020 04:09:13 -0500
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 show that the resulting online algorithms have O(T^{1/2}) (approximate) regret under the full information setting. We further introduce a bandit extension of Blackwell approachability that we call Bandit Blackwell approachability. We leverage this notion to transform greedy robust offline algorithms into a O(T^{2/3})(approximate) regret in the bandit setting. Demonstrating the flexibility of our framework, we apply our offline-to-online transformation to several problems at the intersection of revenue ...

Date Posted:Thu, 10 Sep 2020 04:09:03 -0500
We study a 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 makes a decision 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.

First, using a reduction to maximizing submodular functions over matroids we give an optimal (1-1/e)-approximation for this problem. We then consider a variant in which the platform not only cares about user engagement, but also cares about diversification across various groups of users, that is, guaranteeing a ...

Date Posted:Thu, 23 Jul 2020 03:49:51 -0500
We study a 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 makes a decision 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.

The above problem gives rise to an interesting 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. Using a reduction to maximizing submodular functions over matroids we give an optimal (1-1/e)-approximation for this problem.

We also consider a variant in which users are partitioned into several groups. In this variant, the platform not only cares about overall user engagement among all the ...

Date Posted:Wed, 22 Jul 2020 13:50:38 -0500
Matching and pricing are two critical levers in two-sided marketplaces to connect demand and supply. The platform can produce more efficient matching and pricing decisions by batching the demand requests. We initiate the study of the two-stage stochastic matching problem, with or without pricing, to enable the platform to make improved decisions in a batch with an eye toward the imminent future demand requests. This problem is motivated in part by applications in online marketplaces such as ride hailing platforms.

We design online competitive algorithms for vertex-weighted (or unweighted) two-stage stochastic matching for maximizing supply efficiency, and two-stage joint matching and pricing for maximizing market efficiency. In the former problem, 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. Using a factor revealing program and connections to submodular optimization, we improve this ratio against the optimum online benchmark to (1?1/e+1/e^2) ? 0.767 for the unweighted and 0.761 for the weighted case. In the latter problem, we design optimal 1/2-competitive joint pricing and matching algorithm by borrowing ideas from the ex-ante prophet inequality literature. We also show an improved (1?1/e)-competitive algorithm for the special case of demand efficiency objective using the correlation gap of submodular functions. Finally, we complement our

Date Posted:Wed, 22 Jul 2020 04:51:35 -0500
Matching and pricing are two critical levers in ride sharing marketplaces to match demand and supply. There, the platform can produce more efficient matching and pricing decisions by batching the requests. The goal of this paper is extending this batching paradigm to enable the platform to make such decisions in a batch with an eye toward the future. We therefore study the "two-stage stochastic matching problem", with or without pricing.

We design online competitive algorithms for driver-weighted two-stage stochastic matching for maximizing supply efficiency, and two-stage joint matching and pricing for maximizing market efficiency. In the former problem, by a primal-dual analysis, we show a family of convex-programming based matchings that distribute the demand in a balanced way among supply obtain the optimal 3/4-competitive ratio against the optimum offline benchmark. Using a novel factor revealing program and connections to submodular optimization, we improve this ratio ...

Date Posted:Mon, 20 Jul 2020 03:52:39 -0500
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 show that the resulting online algorithms have O(T^{1/2}) (approximate) regret under the full information setting. We further introduce a bandit extension of Blackwell approachability that we call Bandit Blackwell approachability. We leverage this notion to transform greedy robust offline algorithms into a O(T^{2/3})(approximate) regret in the bandit setting. Demonstrating the flexibility of our framework, we apply our offline-to-online transformation to several problems at the intersection of revenue ...

Date Posted:Thu, 02 Jul 2020 03:13:14 -0500
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 show that the resulting online algorithms have O(T^{1/2}) (approximate) regret under the full information setting. We further introduce a bandit extension of Blackwell approachability that we call Bandit Blackwell approachability. We leverage this notion to transform greedy robust offline algorithms into a O(T^{2/3})(approximate) regret in the bandit setting. Demonstrating the flexibility of our framework, we apply our offline-to-online transformation to several problems at the intersection of revenue ...

Date Posted:Thu, 25 Jun 2020 13:28:54 -0500
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 show that the resulting online algorithms have $O(\sqrt{T})$ (approximate) regret under the full information setting. We further introduce a bandit extension of Blackwell approachability that we call Bandit Blackwell approachability. We leverage this notion to transform greedy robust offline algorithms into a $O(T^{2/3})$ (approximate) regret in the bandit setting. Demonstrating the flexibility of our framework, we apply our offline-to-online transformation to several problems at the intersection of revenue management, market design, and online optimization, including product ranking optimization in online platforms, reserve price optimization in auctions, and submodular maximization. We also extend our reduction to greedy-like first-order methods used in continuous optimization, such as those used for maximizing continuous strong DR monotone submodular functions subject to convex constraints. We show that our transformation, when applied to these applications, leads to new regret bounds or improves the

Date Posted:Thu, 25 Jun 2020 04:29:41 -0500
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 show that the resulting online algorithms have O(T^{1/2}) (approximate) regret under the full information setting. We further introduce a bandit extension of Blackwell approachability that we call Bandit Blackwell approachability. We leverage this notion to transform greedy robust offline algorithms into a O(T^{2/3})(approximate) regret in the bandit setting. Demonstrating the flexibility of our framework, we apply our offline-to-online transformation to several problems at the intersection of revenue ...

Date Posted:Wed, 18 Mar 2020 21:28:10 -0500
We study a 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.

First, using a reduction to maximizing submodular functions over matroids, we give an optimal (1-1/e)-approximation for this problem. We then consider a variant in which the platform cares not only about user engagement, but also about diversification across various groups of users, that is, guaranteeing a certain probability of purchase in each group. We characterize the polytope of feasible solutions and give a bi-criteria ((1-1/e)^2,(1-1/e)^2)-approximation for this problem by rounding an approximate solution of a linear programming relaxation. For rounding, we relay on our reduction and the particular rounding techniques for matroid polytopes. For the special case in which underlying submodular functions are coverage functions -- which is practically relevant in online retail -- we propose an alternative LP

Date Posted:Wed, 18 Mar 2020 12:28:20 -0500
We study an optimization problem capturing a core operational question for online retailing platforms. Given models for the users' preferences over products as well as the number of items they are willing to observe before clicking on one or abandoning the search, what is the best way to rank the relevant products in response to a search query?

In order to capture both popularity and diversity effects, we model the probability that a user clicks on an element from a subset of products as a monotone submodular function of this set. We also assume that the patience level of the users, or the number of items they are willing to observe before clicking on one or abandoning the search, is a given random variable. Under those assumptions, the objective functions capturing user engagement or platform revenue can be written as a new family of submodular optimization problems over a sequence of elements.

We call this family of natural optimization problems "sequential ...

Date Posted:Thu, 21 Nov 2019 05:41:03 -0600
Motivated by applications of rental services in e-commerce, we consider real-time assortment of reusable products. In our model, arriving consumers with heterogeneous types choose rental products from the offered assortment, pay the rental fees, and return the product to the platform after a rental time. Consumers' types specify their choice models, rental fees and rental time distributions for various products. Our goal is to design competitive online policies against an appropriate benchmark for both the prior-free setting, in which types are arbitrary (or adversarial), and the Bayesian setting, in which types are drawn independently from known distributions.

Our contribution is threefold. We first introduce offline linear programming benchmarks in both settings, that use time-varying inventory constraints to capture feasibility of a policy under rentals, and are required to satisfy these constraints only in expectation. Second, in the prior-free setting, we ...

Date Posted:Sat, 14 Sep 2019 04:14:55 -0500
Motivated by applications of rental services in e-commerce, we consider real-time assortment of reusable products. In our model, arriving consumers with heterogeneous types choose rental products from the offered assortment, pay the rental fees, and return the product to the platform after a random time. Consumers' types specify their choice models, rental fees and rental time distributions for various products. Our goal is to design competitive online policies against an appropriate benchmark for both the prior-free setting, in which types are arbitrary (or adversarial), and the Bayesian setting, in which types are drawn independently from known distributions.

Our contribution is threefold. We first introduce offline linear programming benchmarks in both settings, that use time-varying inventory constraints to capture feasibility of a policy under rentals, and are required to satisfy these constraints only in expectation. Second, in the prior-free setting, we ...

Date Posted:Mon, 05 Aug 2019 20:29:04 -0500
he Bayesian online selection problem aims to design a pricing scheme for a sequence of arriving buyers that maximizes the expected social welfare (or revenue) subject to different structural constraints. Inspired by applications with a hierarchy of service, this paper focuses on the cases where a laminar matroid characterizes the set of served buyers. We give the first Polynomial-Time Approximation Scheme (PTAS) for the problem when the laminar matroid has constant depth. Our approach is based on rounding the solution of a hierarchy of linear programming relaxations that approximate the optimum online solution with any degree of accuracy, plus a concentration argument showing that rounding incurs a small loss. We also study another variation, which we call the production-constrained problem. The allowable set of served buyers is characterized by a collection of production and shipping constraints that form a particular example of a laminar matroid. Using a similar LP-based approach, we design a PTAS for this problem, although in this special case the depth of the underlying laminar matroid is not necessarily a constant. The analysis exploits the negative dependency of the optimum selection rule in the lower levels of the laminar family. Finally, to demonstrate the generality of our technique, we employ the linear programming-based approach employed in the paper to re-derive some of the classic prophet inequalities known in the literature ? as a side result.

Date Posted:Mon, 05 Aug 2019 11:29:10 -0500
In the Bayesian online selection problem, the goal is to design a pricing scheme for a sequence of arriving buyers that maximizes the expected social-welfare (or revenue) subject to different types of structural constraints. Inspired by applications in operations management, the focus of this paper is on the cases where the set of served customers is characterized by a laminar matroid.

We give the first Polynomial-Time Approximation Scheme (PTAS) for the problem when the laminar matroid has constant depth. Our approach is based on rounding the solution of a hierarchy of linear programming relaxations that approximate the optimum online solution with any degree of accuracy plus a concentration argument that shows the rounding incurs a small loss. We also study another variation, which we call the production constrained problem, for which the allowable set of served customers is characterized by a collection of production and shipping constraints forming a certain form of ...

Date Posted:Thu, 18 Jul 2019 10:09:53 -0500
Motivated by applications of rental services in e-commerce, we consider real-time assortment of reusable products. In our model, arriving consumers with heterogeneous types choose rental products from the offered assortment, pay the rental fees, and return the product to the platform after a random time. Consumers' types specify their choice models, rental fees and rental time distributions for various products. Our goal is to design competitive online policies against an appropriate benchmark for both the prior-free setting, in which types are arbitrary (or adversarial), and the Bayesian setting, in which types are drawn independently from known distributions.

Our contribution is threefold. We first introduce offline linear programming benchmarks in both settings, that use time-varying inventory constraints to capture feasibility of a policy under rentals, and are required to satisfy these constraints only in expectation. Second, in the prior-free setting, we ...

Date Posted:Wed, 17 Jul 2019 19:24:22 -0500
Motivated by applications of rental services in e-commerce, we consider real-time assortment of reusable products. In our model, arriving consumers with heterogeneous types choose rental products from the offered assortment, pay the rental fees, and return the product to the platform after a rental time. Consumers' types specify their choice models, rental fees and rental time distributions for various products. Our goal is to design competitive online policies against an appropriate benchmark for both the prior-free setting, in which types are arbitrary (or adversarial), and the Bayesian setting, in which types are drawn independently from known distributions.

Our contribution is threefold. We first introduce offline linear programming benchmarks in both settings, that use time-varying inventory constraints to capture feasibility of a policy under rentals, and are required to satisfy these constraints only in expectation. Second, in the prior-free setting, we develop a randomized primal-dual framework based on our introduced LP to settle that inventory balancing policies of Golrezaei et al. (2014) obtain same (asymptotically optimal) competitive ratios as with non-reusable resources when product rental times are fixed over time. As a corollary, we obtain the optimal competitive ratio of (1 ? 1/e) when inventories are large. We also show this family of policies are constant competitive under i.i.d. (over time) stochastic rental times.

Third, we

Date Posted:Wed, 17 Jul 2019 10:24:42 -0500
Motivated by applications of rental services in e-commerce, we consider real-time assortment of reusable products. In our model, arriving consumers with heterogeneous types choose rental products from the offered assortment, pay the rental fees, and return the product to the platform after a random time. Consumers' types specify their choice models, rental fees and rental time distributions for various products. Our goal is to design competitive online policies against an appropriate benchmark for both the prior-free setting, in which types are arbitrary (or adversarial), and the Bayesian setting, in which types are drawn independently from known distributions.

Our contribution is threefold. We first introduce offline linear programming benchmarks in both settings, that use time-varying inventory constraints to capture feasibility of a policy under rentals, and are required to satisfy these constraints only in expectation. Second, in the prior-free setting, we ...