# Rad Niazadeh

Assistant Professor of Operations Management

Assistant Professor of Operations Management

Rad Niazadeh is an assistant professor in Operations Management. He studies the interplay between algorithms, incentives, and learning in online marketplaces, with a focus on applications in revenue management and market design. In particular, he is interested in algorithmic mechanism design and game theory, online learning theory and applications, online algorithms, and algorithmic aspects of machine learning in operations research.

Prior to joining Chicago Booth, Rad was a Motwani postdoctoral fellow at Stanford University (department of Computer Science) and a visiting researcher at Google Research NYC (market algorithms team). He received his PhD in Computer Science from Cornell University (minored in Applied Mathematics). Additionally, he holds M.Sc. and B.Sc. degrees in Electrical Engineering from Sharif University of Technology.

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

Rad has received the 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.

"Batching and Optimal Multi-stage Bipartite Allocations”, with Yiding Feng, Available at SSRN 3689448---preliminary conference version in Innovations in Theoretical Computer Science (ITCS), 2021.

"Two-stage Stochastic Matching and Pricing with Applications to Ride Hailing”, with Yiding Feng and Amin Saberi, Available at SSRN 3613755---preliminary conference version in ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021.

"Combinatorial Bernoulli Factories: Matchings, Flows, and Other Polytopes", with Renato Paes Leme and Jon Schneider, Available at SSRN 3726753---preliminary conference version in ACM Symposium on Theory of Computing (STOC), 2021.

"Bernoulli Factories and Black-Box Reductions in Mechanism Design”, with Shaddin Dughmi, Jason Hartline and Bobby Kleinberg, Journal of the ACM (JACM), 2020.

"Fast Core Pricing for Rich Advertising Auctions", with Jason Hartline, Mohammad Reza Khani, Nicole Immorlica, and Brendan Lucier, Operations Research (OR), 2020.

"Optimal Algorithms for Continuous Non-monotone Submodular and DR-submodular Maxmization", with Tim Roughgarden and Joshua Wang, Journal of Machine Learning Research (JMLR), 2020.

"Multi-scale Online Learning: Theory and Applications to Online Auctions and Pricing", with Sébastien Bubeck, Nikhil Devanur and Zhiyi Huang, Journal of Machine Learning Research (JMLR), 2019.

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

Chicago Booth Review publishes the latest research-driven insights on business, policy, and markets.

Get the Latest Insights from Rad Niazadeh in Chicago Booth Review