# Rad Niazadeh

Assistant Professor of Operations Management and Asness Junior Faculty Fellow

Coronavirus Updates

Assistant Professor of Operations Management and Asness Junior Faculty Fellow

Rad Niazadeh is an Assistant Professor of Operations Management and Asness Junior Faculty Fellow at Chicago Booth. He is also part of the faculty at the Toyota Technological Institute at Chicago (TTIC) by a courtesy appointment. Prior to joining Chicago Booth, he was a visiting researcher at the Google Research NYC's market algorithms team, and a postdoctoral fellow at Stanford University, Computer Science. He received his PhD in Computer Science, with a minor in Applied Mathematics, from Cornell University.

Rad studies the interplay between algorithms (for computation), data (for learning), and incentives (for modeling strategic behavior) in real-time operations management. His primary research goal is to build theoretical methodologies and application-based frameworks for data-driven sequential decision-making in complex and dynamic operational scenarios, mostly related to the operations of online platforms, electronic markets, and modern non-profit organizations. On the practical side, he utilizes the theory to develop (i) computationally and economically efficient real-time market algorithms and (ii) socially-aware decision-making policies that prioritize equity, fairness, and non-discrimination in the operations of non-profit organizations, governmental agencies, and online platforms.

Professor Niazadeh’s research has been published in journals such as Management Science, Operations Research, Mathematics of Operations Research, Journal of Machine Learning Research, Games and Economic Behavior, Journal of the ACM, Bernoulli, and in (peer-reviewed) top conference proceedings in computer science such as ACM STOC, IEEE FOCS, NeurIPS, ICML, ACM EC, ACM-SIAM SODA and ITCS.

Rad has received the INFORMS Auctions and Market Design Michael H. Rothkopf Junior Researcher Paper Prize (first place) in 2021, INFORMS Data Mining and Decision Analytics Best Paper Award (third place) in 2021, INFORMS Revenue Management and Pricing Dissertation Award (honorable mention) in 2018, the Google PhD Fellowship in Market Algorithms in 2016, Stanford Motwani fellowship in 2017, and Cornell Jacobs fellowship in 2012.

"Dynamic Matching with Post-allocation Service and its Application to Refugee Resettlement", with Kirk Bansak, Soonbong Lee, Vahideh Manshadi, and Elisabeth Paulson (preprint availble upon resquest)

"Optimal Prophet Ineqaulities with Cancellation Costs", with Farbod Ekbatani, Pranav Nuti, and Jan Vondrak (preprint availble upon resquest; preliminary conference version in **ACM STOC'24**)

"Online Job Assignment", with Farbod Ekbatani, Yiding Feng, and Ian Kash, SSRN preprint: 4745629

"Online Matching with Cancellation Costs", with Farbod Ekbatani and Yiding Feng, SSRN preprint: 4245468 (preliminary conference version in **ACM EC’23**)

"Markovian Search with Socially Aware Constraints", with Mohammad Reza Aminian and Vahideh Manshadi, SSRN preprint: 4347447

"Misalignment, Learning, and Ranking: Harnessing Users Limited Attention", with Arpit Agarwal and Prathamesh Patil, SSRN preprint: 4365381

"Robustness of Online Inventory Balancing Algorithm to Inventory Shocks", with Yiding Feng and Amin Saberi, SSRN preprint: 3795056

"Linear Programming Based Near-Optimal Pricing for Laminar Bayesian Online Selection", with Nima Anari, Ali Shameli, and Amin Saberi, minor revision from **Mathmetics of Operations Research**, SSRN preprint: 3430156 (preliminary conference version in **ACM EC'19**)

"Batching and Optimal Multi-stage Bipartite Allocations", with Yiding Feng, *minor revision* from **Management Science, **SSRN preprint: 3689448 (preliminary conference version in **ITCS'21**)

"Bernoulli Factories for Flow-Based Polytopes", with With Jon Schneider and Renato Paes Leme, **SIAM Journal on Discrete Mathematics (SIDMA), 2023**.

"Near-optimal Bayesian Online Assortment of Reusable Resources", with Yiding Feng and Amin Saberi, **Operations Research**, 2024 (preliminary conference version in **ACM EC’22**)

"Correlated Cluster-Based Randomized Experiments: Robust Variance Minimization", with Chen Chen and Ozan Candogan, **Management Science**, 2023 (preliminary conference version in **ACM EC’23**)

"Online Bipartite Matching with Reusable Resources", with Steven Delong, Alireza Farhadi, Balu Sivan, and Rajan Udwani, **Mathematics of Operations Research**, 2023 (preliminary conference version in **ACM EC’22**)

"Stateful Posted Pricing with Vanishing Regret via Dynamic Deterministic Markov Decision Processes", with Yuval Emek, Ron Lavi and Yangguang Shi, **Mathematics of Operations Research** (preliminary conference version in **NeurIPS'20**)

"Two-stage Stochastic Matching and Pricing with Applications to Ride Hailing", with Yiding Feng and Amin Saberi, **Operations Research**, 2023 (preliminary conference version in **ACM-SIAM SODA’21**, spotlight talk in RMP’21 conference)

"Fair Dynamic Rationing", with Vahideh Manshadi and Scott Rodilitz,**Management Science**, 2023 (preliminary conference version in **ACM EC’21**, spotlight talk in RMP’21 conference)

"Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimiza-tion", with Negin Golrezaei, Joshua Wang, Fransisca Susan and Ashwinkumar Badanidiyuru, **Management Science**, 2022 (preliminary conference version in **ACM EC’21**)

"Sequential Submodular Maximization and Applications to Ranking an Assortment of Products", with Arash Asadpour, Amin Saberi and Ali Shameli,**Operations Research**, 2022 (preliminary conference version in **ACM EC’22**)

"Combinatorial Bernoulli Factories", with Renato Paes Leme and Jon Schneider, **Bernoulli (Journal of the Bernoulli Society)**, 2023 (preliminary conference version in **ACM STOC’21**)

"Bernoulli Factories and Black-Box Reductions in Mechanism Design", with Shaddin Dughmi, Jason Hartline and Robert Kleinberg, **Journal of the ACM**, 2021 (preliminary conference version in **ACM STOC’17**, presented at 6th World Congress of the Game Theory Society — GAMES’21)

"Fast Core Pricing for Rich Advertising Auctions", with Jason Hartline, Mohammad Reza Khani, Nicole Immorlica, and Brendan Lucier, **Operations Research** (OR), 2020 (preliminary conference version in **ACM EC’19**)

"Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization", with Tim Roughgarden and Joshua Wang,**Journal of Machine Learning Research**, 2020 (preliminary conference version in **NeurIPS’18**, oral presentation)

"Multi-scale Online Learning and its Applications to Online Auctions", with Se´bastien Bubeck, Nikhil Devanur and Zhiyi Huang, **Journal of Machine Learning Research**, 2019 (preliminary conference version in **ACM EC’17**)

"Descending Price Auctions with Bounded Number of Price Levels and Batched Prophet Inequality", with Saeed Alaei, Ali Makhdoumi, and Azarakhsh Malekian, in Proc. 23rd ACM conference on Economics and Computation (**ACM ****EC 2022**)

REVISION: Correlated Cluster-Based Randomized Experiments: Robust Variance Minimization

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 ...

REVISION: Fair Dynamic Rationing

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 ...

REVISION: Correlated Cluster-Based Randomized Experiments: Robust Variance Minimization

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 ...

REVISION: Near-Optimal Bayesian Online Assortment of Reusable Resources

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 ...

REVISION: Fair Dynamic Rationing

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 ...

REVISION: Sequential Submodular Maximization and Applications to Ranking an Assortment of Products

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 ...

REVISION: Two-stage Stochastic Matching and Pricing with Applications to Ride Hailing

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 ...

REVISION: Fair Dynamic Rationing

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 ...

REVISION: Fair Dynamic Rationing

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 ...

REVISION: Fair Dynamic Rationing

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 ...

REVISION: Fair Dynamic Rationing

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 ...

REVISION: Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization

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 ...

REVISION: Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization

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 ...

REVISION: Near-Optimal Experimental Design for Networks: Independent Block Randomization

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). ...

REVISION: Batching and Optimal Multi-stage Bipartite Allocations

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 ...

REVISION: Near-Optimal Experimental Design for Networks: Independent Block Randomization

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). ...

REVISION: Near-Optimal Experimental Design for Networks: Independent Block Randomization

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 ...

REVISION: Near-Optimal Experimental Design for Networks: Independent Block Randomization

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 ...

REVISION: Fair Dynamic Rationing

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 ...

REVISION: Near-Optimal Experimental Design for Networks: Independent Block Randomization

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 ...

REVISION: Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization

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 ...

REVISION: Two-stage Stochastic Matching and Pricing with Applications to Ride Hailing

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 ...

REVISION: Batching and Optimal Multi-stage Bipartite Allocations

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 ...

REVISION: Two-stage Stochastic Matching and Pricing with Applications to Ride Hailing

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 ...

REVISION: Two-stage Stochastic Matching and Pricing with Applications to Ride Hailing

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 ...

REVISION: Sequential Submodular Maximization and Applications to Ranking an Assortment of Products

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 ...

REVISION: Fair Dynamic Rationing

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 ...

REVISION: Fair Dynamic Rationing

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 ...

REVISION: Two-stage Stochastic Matching and Pricing with Applications to Ride Hailing

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 ...

New: Combinatorial Bernoulli Factories: Matchings, Flows and Other Polytopes

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 ...

REVISION: Sequential Submodular Maximization and Applications to Ranking an Assortment of Products

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 ...

REVISION: Fast Core Pricing for Rich Advertising Auctions

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 ...

REVISION: Near-Optimal Bayesian Online Assortment of Reusable Resources

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 ...

REVISION: Near-Optimal Bayesian Online Assortment of Reusable Resources

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 ...

REVISION: Fast Core Pricing for Rich Advertising Auctions

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 ...

REVISION: Batching and Optimal Multi-stage Bipartite Allocations

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 ...

REVISION: Batching and Optimal Multi-stage Bipartite Allocations

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 ...

REVISION: Two-stage Matching and Pricing with Applications to Ride Hailing

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 ...

REVISION: Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization

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 ...

REVISION: Sequential Submodular Maximization and Applications to Ranking an Assortment of Products

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 ...

REVISION: Linear Programming Based Online Policies for Real-Time Assortment of Reusable Resources

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 ...

REVISION: Linear Programming Based Near-Optimal Pricing for Laminar Bayesian Online Selection

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 ...

REVISION: Batching and Optimal Multi-stage Bipartite Allocations

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 ...

REVISION: Linear Programming Based Near-Optimal Pricing for Laminar Bayesian Online Selection

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 ...

REVISION: Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization

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 ...

REVISION: Sequential Submodular Maximization and Applications to Ranking an Assortment of Products

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 ...

REVISION: Sequential Submodular Maximization and Applications to Ranking an Assortment of Products

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 ...

REVISION: Two-stage Matching and Pricing with Applications to Ride Hailing

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 ...

REVISION: Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization

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 ...

REVISION: Online Learning via Offline Greedy: Applications in Market Design and Optimization

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 ...

REVISION: Online Learning via Offline Greedy: Applications in Market Design and Optimization

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 ...

REVISION: Ranking an Assortment of Products Via Sequential Submodular Optimization

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 ...

REVISION: Linear Programming Based Online Policies for Real-Time Assortment of Reusable Resources

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 ...

REVISION: Linear Programming Based Online Policies for Real-Time Assortment of Reusable Resources

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 ...

REVISION: Linear Programming Based Near-Optimal Pricing for Laminar Bayesian Online Selection

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 ...

REVISION: Linear Programming Based Online Policies for Real-Time Assortment of Reusable Resources

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 ...

REVISION: Linear Programming Based Online Policies for Real-Time Assortment of Reusable Resources

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 ...

User attempts to outwit algorithms can lead to less-optimal outcomes for everyone.

{PubDate}Research identifies a fair and efficient method for allocating scarce resources in an emergency.

{PubDate}