Events & Seminars

Prophet inequalities are a useful tool for designing online allocation procedures and comparing their performance to the optimal offline allocation. In the basic setting of $k$-unit prophet inequalities, the magical procedure of Alaei (2011) with its celebrated performance guarantee of $1-1/sqrt(k+3)$ has found widespread adoption in mechanism design and general online allocation problems in online advertising, healthcare scheduling, and revenue management. Despite being commonly used for implementing a fractional allocation in an online fashion, the tightness of Alaei’s procedure for a given $k$ has remained unknown. In this paper we resolve this question, characterizing the tight bound by identifying the structure of the optimal online implementation, and consequently improving the best-known guarantee for $k$-unit prophet inequalities for all $k>1$.

We also consider the more general online stochastic knapsack problem where each individual allocation can consume an arbitrary fraction of the initial capacity. Here we introduce a new “best-fit” procedure for implementing a fractionally-feasible knapsack solution online, with a performance guarantee of $1/( 3+ e^(-2) ) ~ 0.319$, which we also show is tight with respect to the standard LP relaxation. This improves the previously best- known guarantee of 0.2 for online knapsack.

Our analysis differs from existing ones by eschewing the need to split items into “large” or “small” based on capacity consumption, using instead an invariant for the overall utilization on different sample paths.

Finally, we refine our technique for the unit-density special case of knapsack, and improve the guarantee from 0.321 to 0.3557 in the multi-resource appointment scheduling application of Stein et al. (2020).

(Joint work with Jiashuo Jiang and Jiawei Zhang)

This paper examines an innovative return policy, return insurance, emerging on various shopping platforms such as Taobao.com and JD.com. Return insurance is underwritten by an insurer and can be purchased by either a retailer or a consumer. Under such insurance, the insurer partially compensates consumers for their hassle costs associated with product return. We analyze the informational roles of return insurance when product quality is the retailer's private information, consumers infer quality from the retailer's price and insurance adoption, and the insurer strategically chooses insurance premiums.

We show that return insurance can be an effective signal of high quality. When consumers have little confidence about high quality and expect a significant gap between high and low qualities, a high-quality retailer can be differentiated from a low-quality retailer solely through its adoption of return insurance. We confirm, both analytically and empirically with a data set consisting of over 10,000 sellers on JD.com, that return insurance is more likely adopted by higher-quality sellers under information asymmetry. Furthermore, we find that the presence of the third party (i.e., the insurer) leads to double marginalization in signaling, which strengthens a signal's differentiating power and sometimes renders return insurance a preferred signal, in comparison with free return, whereby retailers directly compensate for consumers' return hassles. As an effective and costly signal of quality, return insurance may also improve consumer surplus and reduce product returns. Its profit advantage to the insurer is most pronounced under significant quality uncertainty.

Traffic congestion is a serious global issue. A potential solution, which requires zero investment in infrastructure, is to convince solo car users to carpool. In this paper, we leverage the Waze Carpool service and run the largest ever digital field experiment to nudge commuters to carpool. Our field experiment involves more than half a million users across four U.S. states between June 10 and July 3, 2019. We identify users who can save a significant commute time by carpooling through the use of a high- occupancy vehicle (HOV) lane, users who can still use a HOV lane but have a low time saving, and users who do not have access to a HOV lane on their commute. We send them in-app notifications with different framings: mentioning the HOV lane, highlighting the time saving, emphasizing the monetary welcome bonus (for users who do not have access to a HOV lane), and a generic carpool invitation. We find a strong relationship between the affinity to carpool and the potential time saving through a HOV lane. Specifically, we estimate that mentioning the HOV lane increases the click-through rate (i.e., proportion of users who clicked on the button inviting them to try the carpool service) and the on-boarding rate (i.e., proportion of users who signed up and created an account with the carpool service) by 133-185% and 64-141%, respectively relative to a generic invitation. We conclude by discussing the implications of our findings for carpool platforms and public policy.

(Joint work with Michael-David Fiszer, Avia Ratzon, and Roy Sasson)

This paper considers a re-sourcing setting in which a qualified supplier (the incumbent) and multiple suppliers which have not yet been qualified (the entrants) compete in an open-bid descending auction for a single-supplier contract. Due to the risk of supplier nonperformance, the buyer only awards the contract to a qualified supplier; meanwhile, the buyer can conduct supplier qualification screening at a cost, to verify whether the entrant suppliers can perform the contract. Conventionally, the buyer would screen entrants before running an auction, i.e., the pre-qualification strategy (PRE). We explore an alternative approach called post-qualification strategy (POST), in which the buyer first runs an auction and then conducts qualification screenings based on the suppliers' auction bids. Our characterization of the dynamic structure of the suppliers' equilibrium bidding strategy enables the calculation of the buyer's expected cost under POST, which is computationally intractable without this characterization. We derive analytical conditions under which POST is cheaper than PRE, and also use a comprehensive numerical study to quantify the benefit of POST. We find that using the cheaper option between PRE and POST not only provides significant cost-savings over the conventional PRE-only approach but also captures the majority of the benefit an optimal mechanism can offer over PRE. Our results highlight the practical benefit of POST.

Online marketplaces, such as Amazon, Alibaba, or Google Shopping, allow sellers to promote their products by charging them for the right to be displayed on top of organic search results. In this paper, we study the problem of designing auctions for promoted products and highlight some new challenges emerging from the interplay of two unique features: substitution effects and information asymmetry. The presence of substitution effects, which we capture by assuming that consumers choose sellers according to a multinomial logit model, implies that the probability a seller is chosen depends on the assortment of sellers displayed alongside. Additionally, sellers may hold private information about how their own products match consumers’ interests, which the platform can elicit to make better assortment decisions. We first show that the first-best allocation, i.e., the welfare-maximizing assortment in the absence of private information, cannot be implemented truthfully in general. Thus motivated, we initiate the study of incentive-compatible assortment optimization by characterizing prior-free and prior-dependent mechanisms, and quantifying the worst-case social cost of implementing truthful assortment mechanisms. An important finding is that the worst-case social cost of implementing truthful mechanisms can be high when the number of sellers is large. Structurally, we show that optimal mechanisms may need to downward distort the efficient allocation both at the top and the bottom. This is joint work with Santiago Balseiro.

Battery swapping for electric vehicle refueling is reviving and thriving. Despite a captivating sustainable future where swapping batteries will be as convenient as refueling gas today, a tension is mounting in practice (beyond the traditional “range anxiety” issue): On one hand, it is desirable to maximize battery proximity and availability to customers. On the other hand, power grids for charging depleted batteries are not accessible everywhere. To reconcile this tension, some cities are embracing an emerging infrastructure network: Decentralized swapping stations replenish charged batteries from centralized charging stations. It remains unclear how to design such a network, or whether transitioning into this paradigm will save batteries which are environmentally detrimental. In this paper, we model this new urban infrastructure network. This task is complicated by non-Poisson swaps (observed from real data), and by the intertwined stochastic operations of swapping, charging, stocking and circulating batteries among swapping and charging stations. We show that these complexities can be captured by analytical models. We next propose a new location-inventory model for citywide deployment of hub charging stations, which jointly determines the location, allocation and reorder quantity decisions with a non-convex non- concave objective function. We solve this problem exactly and efficiently by exploiting the hidden submodularity and combining constraint-generation and parameter-search techniques. Even for solving convexified problems, our algorithm brings a speedup of at least three orders of magnitude relative to Gurobi solver. The major insight is twofold: Centralizing battery charging may harm cost-efficiency and battery asset-lightness; however, this finding is reversed if foreseeing that decentralized charging will have limited access to grids permitting fast charging. We also identify planning and operational flexibilities brought by centralized charging. In a broader sense, this work deepens our understanding about how mobility and energy are coupled in future smart cities.

We study the problem of dynamic batch learning in high-dimensional sparse linear contextual bandits, where a decision maker can only adapt decisions at a batch level. In particular, the decision maker, only observing rewards at the end of each batch, dynamically decides how many individuals to include in the next batch (at the current batch's end) and what personalized action-selection scheme to adopt within the batch. Such batch constraints are ubiquitous in a variety of practical contexts, including personalized product offerings in marketing and medical treatment selection in clinical trials. We characterize the fundamental learning limit in this problem via a novel lower bound analysis and provide a simple, exploration-free algorithm that uses the LASSO estimator, which achieves the minimax optimal performance characterized by the lower bound (up to log factors). To our best knowledge, our work provides the first inroad into a rigorous understanding of dynamic batch learning with high-dimensional covariates.