Arash Asadpour: NYU Stern

Journal Papers

Minimum Earnings Regulation and the Stability of Marketplaces,
with I. Lobel and G. van Ryzin.
Manufacturing & Service Operations Management, 2022.
[Abstract]
We build a model to study the implications of utilization-based minimum earning regulations of the kind recently enacted by New York City for its ride-hailing providers. We identify the precise conditions under which a utilization-based minimum earnings rule causes marketplace instability, where stability is defined as the ability of platforms to keep wages bounded while maintaining the current flexible (free-entry) work model. We also calibrate our model using publicly available data, showing the limited power of the law to increase earnings within an open marketplace. We argue that affected ride-hailing companies might respond to the law by reducing driver flexibility.

Ranking an Assortment of Products Via Sequential Submodular Optimization,
with R. Niazadeh, A. Saberi, and A. Shameli.
Operations Research, 2022.
[Abstract]
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 submodular optimization''. By building on and extending the literature on submodular maximization subject to matroid constraints, we derive a (1-1/e) optimal approximation algorithm for maximizing user engagement and a bi-criteria approximation algorithm for maximizing revenue subject to a lower bound on user engagement.

Large-Scale Bundle Size Pricing: A Theoretical Analysis,
with T. Abdallah and J. Reed.
Operations Research, 2021.
[Abstract]
Bundle size pricing (BSP) is a multi-dimensional selling mechanism where the firm prices the size of the bundle rather than the different possible combinations of bundles. In BSP, the firm offers the customer a menu of different sizes and prices. The customer then chooses the size that maximizes his surplus and customizes his bundle given his chosen size. While BSP is commonly used across several industries, little is known about the optimal BSP policy in terms of sizes and prices along with the theoretical properties of its profit. In this paper, we provide a simple and tractable theoretical framework to analyze the large-scale BSP problem where a multi-product firm is selling a large number of products. The BSP problem is in general hard as it involves optimizing over order statistics, however we show that for large numbers of products, the BSP problem transforms from a hard multi-dimensional problem to a simple multi-unit pricing problem with concave and increasing utilities. Our framework allows us to identify the main source of inefficiency of BSP that is the heterogeneity of marginal costs across products. For this reason, we propose two new BSP policies called "clustered BSP" and "assorted BSP" that significantly reduce the inefficiency of regular BSP. We then utilize our framework to study richer models of BSP such as when customers have budgets and when there exists multiple customer types.

Online Resource Allocation with Limited Flexibility,
with X. Wang and J. Zhang.
Management Science, 2020.
[Abstract]
We consider a class of online resource allocation problems in which there are n types of resources with limited initial inventory and n demand classes. The resources are flexible in that each type of resources can serve more than one demand class. In this paper, we focus on a special class of structures with limited flexibility, the long chain design, which was proposed by Jordan and Graves (1995) and has been an important concept in the design of sparse flexible processes. We show the effectiveness of the long chain design in mitigating supply-demand mismatch under a simple myopic online allocation policy. In particular, we provide an upper bound on the expected total number of lost sales that is irrespective of how large the market size is.

Concise Bid Optimization Strategies with Multiple Budget Constraints,
with M. Bateni, K. Bhawalkar, and V. Mirrokni.
Management Science, 2019.
[Abstract]
A major challenge faced by marketers attempting to optimize their advertising campaigns is to deal with budget constraints. The problem is even harder in the face of multidimensional budget constraints, particularly in the presence of many decision variables involved and the interplay among the decision variables through such constraints. Concise bidding strategies help advertisers deal with this challenge by introducing fewer variables to act on.
In this paper, we study the problem of finding optimal concise bidding strategies for advertising campaigns with multiple budget constraints. We provide approximation algorihtms based on ideas from dynamic programming and also a very fast dependent randomized rounding of the LP relaxation that runs in linear time and may be of independent interest. Our results do not rely on any concavity assumption about the value or the cost functions. Moreover, our results are not limited to cost-per-click models and (as opposed to uniform bidding strategies as the current state of the art) can apply to pay-per-impression or pay-per-conversion models, too. We accompany our theoretical results with experimental findings that show an improvement between 1% to 6% over uniform bidding in case of one budget constraint, and an average increase of 5% over an enhanced version of uniform bidding designed for the problems with multiple budget constraints.

An O(log n / log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem,
with M. X. Goemans, A. Madry, S. Oveis Gharan, and A. Saberi.
Operations Research, 2017.
[Abstract]
We present a randomized O(log n / log log n)-approximation algorithm for the asymmetric traveling sales- man problem (ATSP). This provides the first asymptotic improvement over the long-standing Θ(logn)-approximation bound stemming from the work of Frieze et al. [FGM82].
The key ingredient of our approach is a new connection between the approximability of the ATSP and the notion of so-called thin trees. To exploit this connection, we employ maximum entropy rounding—a novel method of randomized rounding of LP relaxations of optimization problems. We believe that this method might be of independent interest.

Maximizing Stochastic Monotone Submodular Functions,
with H. Nazerzadeh.
Management Science, 2016.
[Abstract]
We study the problem of maximizing a stochastic monotone submodular function with respect to a matroid constraint. Due to the presence of diminishing marginal values in real-world problems, our model can capture the effect of stochasticity in a wide range of applications. We show that the adaptivity gap - the ratio between the values of optimal adaptive and optimal non-adaptive policies - is bounded and is equal to 1.58. We propose a polynomial-time non-adaptive policy that achieves this bound. We also present an adaptive myopic policy that obtains at least half of the optimal value. Furthermore, when the matroid is uniform, the myopic policy achieves the optimal approximation ratio of 0.63.

Santa claus Meets Hypergraph Matchings,
with U. Feige and A. Saberi.
Transactions on Algorithms, 2012.
[Abstract]
We consider the restricted assignment version of the problem of max-min fair allocation of indivisible goods, also known as the Santa Claus problem. There are m items and n players. Every item has some non-negative value, and every player is interested in only some of the items. The goal is to distribute the items to the players in a way that maximizes the minimum of the sum of the values of the items given to any player. It was previously shown via a nonconstructive proof that uses the Lovász local lemma that the integrality gap of a certain configuration LP for the problem is no worse than some (unspecified) constant. This gives a polynomial time algorithm to estimate the optimum value ofthe problem within a constant factor, but does not provide a polynomial time algorithm for finding a corresponding allocation.
We use a different approach to analyze the integrality gap. Our approach is based upon local search techniques for finding perfect matchings in certain classes of hypergraphs. As a result, we prove that the integrality gap of the configuration LP is no worse than 1/4. Our proof provides a local search algorithm which finds the corresponding allocation, but is nonconstructive in the sense that this algorithm is not known to converge to a local optimum in a polynomial number of steps.

An Approximation Algorithm for Max-min Fair Allocation of Indivisible Goods,
with A. Saberi.
SIAM Jounal on Computing, 2010.
[Abstract]
In this paper, we give the first approximation algorithm for the problem of max-min fair allocation of indivisible goods. An instance of this problem consists of a set of k people and m indivisible goods. Each person has a known linear utility function over the set of goods which might be different from the utility functions of other people. The goal is to distribute the goods among the people and maximize the minimum utility received by them.
The approximation ratio of our algorithm is Ω(1/(k^0.5 log³ k))). As a crucial part of our algorithm, we design and analyze an iterative method for rounding a fractional matching on a tree to an integral matching which might be of independent interest. We also provide better bounds when we are allowed to exclude a small fraction of the people from the problem.