I joind City University of New York as an associate professor of operations management in Fall 2020. Prior to that I was an assistant professor of operations management in New York University in 20112018. I received my Ph.D. from the Department of Management Science and Engineering at Stanford University in 2010.
Research Interests

Areas: Ridesharing Marketplace, ECommerce, Matching and Search Markets

Methodologies: Mathematical Programming, Stochastic Optimization, Online Optimization, Matching and Search Theory
Journal Papers

LargeScale Bundle Size Pricing: A Theoretical Analysis,
with T. Abdallah and J. Reed.
Operations Research, Forthcoming.
[Abstract]
Bundle size pricing (BSP) is a multidimensional 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 largescale BSP problem where a multiproduct 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 multidimensional problem to a simple multiunit 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 supplydemand 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 costperclick models and (as opposed to uniform bidding strategies as the current state of the art) can apply to payperimpression or payperconversion 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 longstanding Θ(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 socalled 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 realworld 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 nonadaptive policies  is bounded and is equal to 1.58. We propose a polynomialtime nonadaptive 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 maxmin fair allocation of indivisible goods, also known as the Santa Claus problem. There are m items and n players. Every item has some nonnegative 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 Maxmin 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 maxmin 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^{3} 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.
Working Papers

Minimum Earnings Regulation and the Stability of Marketplaces,
with I. Lobel and G. van Ryzin.
[Abstract]
We build a model to study the implications of utilizationbased minimum earning regulations of the kind recently enacted by New York City for its ridehailing providers. We identify the precise conditions under which a utilizationbased minimum earnings rule causes marketplace instability, where stability is defined as the ability of platforms to keep wages bounded while maintaining the current flexible (freeentry) 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 ridehailing 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.
[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 (11/e) optimal approximation algorithm for maximizing user engagement and a bicriteria approximation algorithm for maximizing revenue subject to a lower bound on user engagement.

The Limits of Bundling: High Demand with Limited Inventory,
with T. Abdallah and J. Reed.
(Presentation in INFORMS 2019 by Tarek Abdallah.)

A Smoother Driver Pay Mechanism,
with D. Freund and G. van Ryzin.
(Presentation in INFORMS 2019.)

Shared Rides Sustainability.
with D. Freund and T. Jehl.

Matching Markets: Equilibrium, Homophily and Mixing,
with D. Acemoglu, C. Borgs, J. Chayes, and A. Saberi.
Refereed Conference Papers

Concise Bid Optimization Strategies with Multiple Budget Constraints,
with M. Bateni, K. Bhawalkar, and V. Mirrokni.
Proceedings of the 10th Conference on Web and Internet Economics (WINE), 2014.

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.
Proceedings of the 21st ACMSIAM Symposium on Discrete Algorithms (SODA), 2010. (Winner of the Best Paper Award)

On the Inefficiency Ratio of Stable Equilibria in Congestion Games,
with A. Saberi.
Proceedings of the 5th Conference on Web and Internet Economics (WINE), 2009.

Santa claus meets hypergraph matchings,
with U. Feige and A. Saberi.
Proceedings of the 11th Workshop on Approximation, Randomization and Combinatorial
Optimization (APPROX), 2008.

Stochastic Submodular Maximization,
with H. Nazerzadeh and A. Saberi.
Proceedings of the 4th Conference on Web and Internet Economics (WINE), 2008.

An approximation algorithm for maxmin fair allocation of indivisible goods,
with A. Saberi.
Proceedings of the 39th ACM Symposium on Theory of Computing (STOC), 2007.