Yuxuan Tang
Aggregating Preferences from (Ranked) Choices: A Simple Mallows-type Model
We study a Mallows-type (i.e., distance-based) probabilistic ranking model to aggregate people’s (ranked) choices. In the data, every participant provides a top-k ranked list of items (thereafter referred to as “ranked” choices) among a given display set . When k = 1, such lists are equivalent to “choices” commonly studied in choice modeling. The general (k > 1) setting is less explored, and largely motivated by applications in voting, preference learning, etc.
Every probabilistic ranking model aggregates into a ranked choice model in a “canonical” way: The probability of choosing a top-k ranked list from a display set equals the sum of the probabilities associated with all the rankings in which the list takes the top k positions among all the items in the display set. In this way, the ranked choice model is “rationalized” by a distribution over participants’ preferences. A distance-based ranking model specifies a parsimonious distribution over rankings (in a similar spirit to the Gaussian distribution for scalars). It can be used as “kernels” to “smooth out” the sparse distributions over rankings estimated from data to improve the generalization power.
The main difficulty in applying Mallows-type models to choice modeling is that the corresponding (ranked) choice probabilities are difficult to obtain. We identify a novel distance-based probabilistic ranking model. It is similar to the Mallows model only with a twist in the distance function. The new function penalizes disagreements close to the top positions more than those at the bottom (unlike the Kendall-tau distance function, which penalizes all pairwise disagreements equally).
We show that our probabilistic ranking model aggregates into simple closed-form expressions for the ranked choice probabilities. This is a property that its counterparts do not possess even for k = 1. Furthermore, the new ranking model is relatively easy to estimate as the MLE problem reduces to a well-studied ranking-aggregation-type problem, which enjoys computational advantages. (For example, it admits a PTAS.) We also study the statistical guarantees (e.g., consistency) of the MLE solutions.
As a proof of concept, we compare our model with the two most representative probabilistic ranking models (the Plackett-Luce model and the Mallows model) when k = 1 on real-world data. We find our method achieves a better generalization power, especially when there is a limited variety of display sets.
Will Ma
Simple and Order-optimal Correlated Rounding Schemes for Multi-item E-commerce Order Fulfillment
Yuan Guo
A Customer Choice Model of Impulse Buying in Social Commerce
Anand Deo
Overcoming The Sample Complexity Barrier in Risk Analytics with Debiased Learning
Yuting Zhu
Training Scalable Personalization Policies with Constraints
Big data and new methods allow firms to personalize their marketing actions for different customers. The growth in industry interest in personalization has been mirrored by rapid growth in academic interest in personalization (targeting). This academic attention has primarily focused on training personalization policies without constraints. However, in practice, internal business rules or society considerations often impose constraints on firms’ targeting policies. In this paper, we investigate how to train scalable targeting policies in the presence of constraints.
Constraints on targeting policies are typically of two types. Volume constraints limit the total number of marketing actions that can be taken. This type of constraint may result from capacity constraints. For example, a firm’s ability to make outbound phone calls may be limited by the availability of trained associates to make these calls. Budget constraints may also impose minimum and/or maximum limits on the total number of marketing actions. These constraints may operate in aggregate, or they may apply to specific customer segments. Similarity constraints limit differences in marketing actions taken with different customer segments. These constraints are often motivated by concerns for fairness. For example, a constraint might require that the firm takes similar marketing actions with neighboring zip codes, or that customers located near one store are treated with similar marketing actions as customers located near other stores.
While there are many standard methods for optimizing problems with constraints, large numbers of decision variables and large numbers of constraints can both make the problem challenging. In a personalization problem, the number of decision variables and the number of constraints can both potentially be large. For example, if a separate decision is made for each customer, the number of decision variables may be in the millions. Even where decisions are made at the customer segment level, if there are many segments, there will be many decision variables. Similarly, if constraints apply to specific segments, the number of constraints will be at least as large as the number of segments and may grow as a polynomial function of the number of segments. Standard optimization methods are not well-suited to solving optimization problems with either large numbers of decision variables, or large numbers of constraints.
We formulate the personalization problem as a linear programming problem with constraints and illustrate how to incorporate both volume constraints and similarity constraints. We then adapt and apply a recently developed algorithm, which is designed to solve large-scale linear programming problems. The algorithm belongs within the class of first-order methods, which use gradient information to construct algorithms to find optimal solutions. This class of methods scales very well, and is widely used in many applications, including many machine learning algorithms. The algorithm that we adapt leverages the primal-dual hybrid gradient. Similar methods are widely used in image processing and computer vision. Recent developments have made the algorithm especially suitable for large-scale linear programming problems.
We provide two theoretical results. The first result compares the proposed algorithm with state-of-the-art benchmarks: primal simplex, dual simplex and barrier methods. We prove that the algorithm can solve larger problems (in terms of customers and constraints) than any of these methods. The second theoretical result extends existing guarantees on optimality and computation speed, by adjusting the method (and existing theory) to accommodate the characteristics of personalization problems.
To illustrate the practical value of the method, we apply it to an actual personalization problem. The problem involves choosing which promotions to send to prospective customers. The response functions are estimated using a large-scale field experiment that includes approximately 2.4 million households and five marketing actions. The findings provide practical empirical evidence of how the proposed method extends the scale of solvable personalization problems in the presence of constraints. Our analysis recognizes that different firms that have access to different hardware resources. As we change the available hardware, our method consistently solves problems faster, yields higher profits, and accommodates both a larger number of customers and a larger number of constraints.
Huaiyang Zhong
Wheels on the Bus: Impact of Vaccine Rollouts on Demand for Public Transportation
Jinglong Zhao
Synthetic Controls for Experimental Design
Consider the problem of a ride-sharing company choosing between two compensation plans for drivers (Doudchenko, Gilinson and Wernerfelt, n.d.; Jones and Barrows, 2019). The company can either keep the current compensation plan or adopt a new one with higher incentives. In order to estimate the effect of a change in compensation plans on profits, the company’s data science unit designs and implements an experimental evaluation where the new plan is deployed at a small scale, say, in one of the local markets (cities) in the US. In this setting, a randomized control trial— or A/B test, where drivers in a local market are randomized into the new plan (active treatment arm) or the status-quo (control treatment arm)— is problematic. If drivers in the active treatment arm respond to higher incentives by working longer hours, they will effectively steal business from drivers in the control arm of the experiment, which will result in biased experimental estimates.
A possible approach to this problem is to assign an entire local market to treatment, and use the rest of the local markets, which remain under the current compensation plan during the experimental window, as potential comparison units. In this setting, using randomization to assign the active treatment allows ex-ante (i.e., pre-randomization) unbiased estimation of the effect of the active treatment. However, ex-post (i.e., post-randomization) biases can be large if, at baseline, the treated unit is different from the untreated units in the values of the features that affect the outcomes of interest. As in the ride-sharing example where there is only one treated local market, large biases may arise more generally in randomized studies when either the treatment arm or the control arm contains a small number of units, so randomized treatment assignment may not produce treated and control groups that are similar in their features.
To address these challenges, we propose the use of the synthetic control method (Abadie, Diamond and Hainmueller, 2010, Abadie and Gardeazabal, 2003) as an experimental design to select treated units in non-randomized experiments, as well as the untreated units to be used as a comparison group. We use the name synthetic control designs to refer to the resulting experimental designs.
In our framework, the choice of the treated unit (or treated units, if multiple treated units are desired) aims to accomplish two goals. First, it is often useful to select the treated units such that their features are representative of the features of an aggregate of interest, like an entire country market. The treatment effect for the treated units selected in this way may more accurately reflect the effect of the treatment on the entire aggregate of interest. Second, the treated units should not be idiosyncratic in the sense that their features cannot be closely approximated by the units in the control arm. Otherwise, the reliability of the estimate of the effect on the treated unit may be questionable. We show how to achieve these two objectives, whenever they are possible to achieve, using synthetic control techniques.
While we are aware of the extensive use of synthetic control techniques for experimental design in business analytics units, especially in the technology companies,the academic literature on this subject is at a nascent stage. There are, however, three publicly available studies that are connected to this article. To our knowledge, Doudchenko, Gilinson and Wernerfelt (n.d.) is the first (and only) publicly available study on the topic of experimental design with synthetic controls, and it is closely related to the present article. The focus of Doudchenko, Gilinson and Wernerfelt (n.d.) is on statistical power, which they calculate by simulation of the estimated effects of placebo interventions on historical (pre-experimental) data. That is, the selection of treated units is based on a measure of statistical power implied by the distribution of the placebo estimates for each unit. As a result, estimates based on the procedure in Doudchenko, Gilinson and Wernerfelt (n.d.) target the effect of the treatment for the unit or units that are most closely tracked in the placebo distribution. In the present article, we aim to take a different perspective on the problem of unit selection in experiments with synthetic controls; one that takes into account the extent to which different sets of treated and control units approximate an aggregate causal effect of interest.
In this paper, we propose various designs aimed to estimate average treatment effects, analyze the properties of such designs and the resulting estimators, and devise inferential methods to test a null hypothesis of no treatment effects. In addition, we report simulation results that demonstrate the applicability and computational feasibility of the methods proposed in this article.
Corporate research units and academic investigators are often confronted with settings where interventions at the level of micro-units (i.e., customers, workers, or families) are unfeasible, impractical or ineffective (see, e.g., Duflo, Glennerster and Kremer, 2007, Jones and Barrows, 2019). There is, in consequence, a wide range of potential applications of experimental design methods for large aggregate entities, like the ones proposed in this article.
Renyu Zhang
Deep Learning Based Casual Inference with Combinatorial A/B Tests on Large-Scale Platforms
Internet-based online platforms have substantially impacted people’s lives and the global economy. They have penetrated billions of people’s daily lives in various areas such as social media (Facebook and WeChat), online shopping (Amazon and Alibaba), and urban transportation (Uber and Didi), to name a few. Because of the tremendous values created by these platforms, it is also estimated by the Committee on Judiciary of the USA that the total market value of platform-based tech firms will reach more than 30% of the annual global GDP within the next 10 years. The prosperity of these platforms relies heavily on the enormous data they own, and the data analytics methodologies that drive their strategic and operations decisions. Randomized experiments (a.k.a. A/B tests) have now become a ubiquitous and critical data-driven decision tool to efficiently evaluate and optimize their strategies. In practice, a large-scale online platform like Facebook usually launches thousands of experiments every day to fast iterate their business operations such as product designs and recommendation algorithms. Consequently, each user of the platform is independently
treated by thousands of A/B tests simultaneously. This triggers interesting and important research questions for platforms to best leverage the power of A/B tests:
- How to estimate and infer the overall treatment effect of multiple experiments on a platform?
- Without observing the outcomes of all experiment combinations, how to identify the optimal experiment combination?
Platform managers usually assume the treatment effects of different experiments are linearly additive, so the optimal combination is that of all the experiments with a positive average treatment effect. However, we observe from the real data of a large-scale online video-sharing platform (Platform O hereafter) that linear additivity does not hold, and that the overall treatment effect of multiple experiments varies for different users. The goal of this paper is to address the aforementioned research questions taking into account the non-additivity and heterogeneous treatment effect (HTE) of multiple experiments
Jiatao Ding
From Black to Grey: Improving Access to Antimalarial Drugs in the Presence of Counterfeits
Malaria is a life-threatening disease caused by parasites transmitted to people through the bites of infected female Anopheles mosquitoes. Despite being preventable and curable, more than 400,000 people die of malaria every year, with the Africa region accounting for approximately 19 in 20 cases and deaths globally. The first-line therapy for malaria infection in malaria-endemic counties is a class of antimalarial drugs known as artemisinin combination therapies (ACTs). ACTs are more than 95% effective in preventing death from malaria in both adults and children and are well-tolerated. Unfortunately, high production costs mean a lack of affordable access to ACTs in the private sector supply chain. The lack of affordability has motivated donors, such as the World Bank, the Clinton Health Access Initiative, and the Bill & Melinda Gates Foundation, to subsidize distribution channels to improve the availability of ACTs. Yet, despite these efforts, the price of ACTs in many regions remains too high, in part due to funding shortfalls, leaving malaria one of the biggest preventable killers of children on the planet.
The high demand for drugs, low accessibility of legitimate drugs, and funding shortfall have fostered the prevalence of counterfeit medicines. Counterfeits have a strong market penetration across Africa, especially in the private sector. For example, non-quality assured ACTs accounted for approximately 20% of the private sector market for ACTs in Kenya and 42% of the market in the Democratic Republic of the Congo. Importantly, counterfeit drugs come in different forms: from generic drugs, to substandard drugs, to falsified counterfeits with no active compound. These different types of counterfeits differ significantly in terms of quality and cost: a generic drug is an exact copy of the originator product, which is more affordable and meets quality standards; a substandard drug fails to meet quality standards as it may be contaminated or poorly packaged; a falsified drug is deliberately and fraudulently mislabelled, and is unlikely to contain the active pharmaceutical ingredient. Depending on the type, counterfeits may have very different implications for public health.
Motivated by these market characteristics, this paper investigates how donors should allocate limited budgets to subsidize pharmaceutical products in markets where counterfeits are present. Moreover, we investigate the impact of interventions designed to combat counterfeit drugs. We study three strategies that have been employed and target different stakeholders: adopting traceability technology by donors, improving consumers’ ability to infer drug quality, and directly eliminate counterfeits from retailers.
Bingnan Lu
Pooled Testing in the Presence of Congestion
When the demand for diagnostic testing for medical conditions, such as infections due to the COVID-19 virus, is extensive, testing facilities can resort to the testing of samples from multiple individuals all at once, so-called pooled testing, instead of testing samples individually. Specifically, under a pooled testing regime, mixed samples from a group of individuals are tested for the presence of infection. A negative test implies that none of the individual samples show the presence of infection (assuming the tests are sufficiently accurate). A positive test implies that at least one individual sample within the sample group is testing positive. The individual samples within the group are then retested individually to identify which ones are positive.
Pooled testing has the advantage of reducing the number of samples that have to be tested individually but can increase the number of sample retests. Hence, it is important to identify the sample group size that can balance this tradeoff and maximize the performance objective of the testing facility.
There is a long history of pooled testing, both in practice and in the literature, dating back to Dorfman (1943) who appears to be the first to suggest pooled testing as a strategy to improve available testing capacity. The literature that followed is extensive (see for example Sobel and Groll (1959), Du et al. (2000), Aldridge et al. (2019) and the references therein). However, most of this literature focuses on pooling strategies that maximize throughput (the number of test requests that can be fulfilled per unit time) and does not take into account how this may affect the delay experienced by individuals in getting back test results. In other words, much of the existing literature does not study the relationship between the sample group size and congestion.
In this paper, we study the operation of a testing facility that diagnoses infected individuals. In particular, we focus on how the facility should select the sample pooling size that minimizes the total waiting time for testing results. We model the testing process as a two-stage tandem queueing system with batch service and re-entry. Requests for individual tests arrive to the first stage of the system, where testing samples are collected and formed into batches (i.e. a mixture of samples) with a predetermined pooling size. Batches once formed exit the first stage and enter the second stage for virological testing. Samples in a batch that tests negative leave the system. Otherwise, samples individually rejoin the second stage for another test to identify each positive sample in this batch.
We provide conditions on the disease prevalence rate and the arrival intensity that guarantee system stability (i.e. a finite expected waiting time). We provide analytical expressions for estimating expected time spent in the system by each sample. We also develop an algorithm to obtain the batch size that minimizes the delay in delivering test results. We show that this batch size is different from the batch size suggested by the traditional pooled testing strategy originally developed by Dorfman in the 1940s, which minimizes the overall testing requirement instead of time in the system. We show that, in general, the optimal batch size decreases in the prevalence rate and increases in the testing times.
Sundara Natarajan Panchanatham (Onsite)
Inventory Allocation Policy for Cold Blood Banks
Background: Patients affected by hematological (blood-related) diseases such as leukemia, lymphoma, severe aplastic anemia etc. requires transplantation of genetically compatible hematopoietic stem cells (HSCs) extracted from the bone marrow (BM) of live donors or the umbilical cord blood (CB) of babies. Every year approximately 13,000 individuals require BM donations (outside of the family members) or compatible CB cells held in storage for treatment. For the transplant to take place successfully, the patient in need of the stem cell must be genetically compatible with the source and the compatibility is determined by similarity in the genetic codes. Put specifically, the compatibility often referred to as a “match", is the number of places the genetic codes are the same for a patient and the BM donor/CB cells in a string of genetic codes of length six (called phenotype). If all the six places in the phenotype matches between the BM donor/CBU cells and the recipient, this is referred to as a 6/6 match. If there is a mismatch in one place, it is a 5/6 match and so on. To facilitate the search for HSCs, BM registries (BMR) that collect the details of potential donors and public CB banks (CBB) that store units of CB (CBU) donated by the public are setup across the U.S. by National Marrow Donor Program (NMDP). NMDP through its flagship program called “Be the match" acts as interface between the patients (physicians) and the BMR/CBB. With over 10 million unique phenotypes in the US population and limited inventory relative to each variety, then the appropriate sizing, screening and allocation policy followed in the two institutions (BMR and CBB), is an important operations problem from a public policy viewpoint.
Problem Definition: The two sources of HSCs, BM, and CB cells, differ along different dimensions including sourcing, costs, availability, and, importantly, medical effectiveness (where BM donations performs slightly better than cord blood cells). Simply put, the BM donors are a cost-effective source with strict matching requirements (only 6/6 match) whereas the CB units are a cost-intensive source with flexible matching requirements (allows up to 4/6 match). Due to the medical effectiveness, a BM donor is always preferred for a transplant and only the unmet demand spills over to the CBBs. The fact the only a 6/6 match alone is possible in the case of BM transplant renders the capacity and allocation decision very straight forward despite both demand and supply uncertainty. However, with only spillover demand from the BM registry and the possibility of multiple choices to meet a demand (due to flexible 5/6 & 4/6 matches) it is unclear as to what the optimal inventory and allocation policy should be for the CBBs. The recent emergence of international BM donor networks further necessitates the efficient operations of the CB banks. In this work, we focus on designing evidence-based and cost-effective allocation rules and inventory policies for the CBBs that deliver high societal benefits. The allocation and inventory issues in the public CBBs haven’t been studied in the relevant body of literature across operations, health economics and medical domains, and we are the first to address it to the best of our knowledge.
Methodology: Factors including the huge magnitude of unique population phenotypes (~10 million), partial substitutability among phenotypes (5/6 and 4/6 matches), spillover of demand from another source combined with both supply and demand uncertainty makes it extremely difficult to investigate the inventory/allocation policies for the CBBs through the standard methods used in operations research. So, we develop a simulation-based optimization (SBO) framework that minimizes the immediate regret/estimated loss for the CBB during allocation of inventories to incoming demand. Similarly, the proposed approach screens incoming supplies of the CB units and admits them only if they increase the overall value of a CB bank. We compare the temporal variation in several performance measures related to the matching process for the proposed (SBO) framework against the current industry practice. Keeping in mind the complexity associated with practical implementation of the SBO framework, we also design several heuristics and benchmark them against the performance of the SBO framework.
Managerial Implications: The results showcase that our SBO approach along with some of the proposed heuristics perform substantially better than the current industry practice. Our research creates high societal value by providing simple and effective rules for CBB operation in addition to making lives easy for CBB managers bogged down by the complexity of the system.
Minmin Zhang
Inventory Allocation Policy for Cold Blood Banks
The COVID-19 pandemic posed an epic challenge to the U.S. healthcare industry. It has disrupted nearly all aspects of healthcare delivery. In response to the pandemic, multiple states temporarily suspended non-essential surgical procedures between March and May 2020. The suspensions prompted the healthcare industry to shed millions of jobs and limit the availability of resources necessary for essential procedures.
In this paper, we estimate the potential spillover effect of suspended non-essential surgery on patients’ access to essential health services, using deceased-donor kidney transplantation as the clinical setting. Kidney transplantation is the preferred therapy
for patients with end-stage renal disease. Even though the U.S. leads the world in kidney transplantation—with 4% of the world population, the U.S. accounts for almost a quarter of transplants performed worldwide—nearly 5,000 ESRD patients die every
year while waiting for a transplant. To minimize disruptions to deceased-donor organ transplants, the Centers for Medicare & Medicaid Services clarified that state guidances for non-essential surgery do not apply to them, because they are essential surgery. In
other words, regardless of whether a state has suspended non-essential surgery, deceased-donor organ transplantation procedures are essential surgery so should not be postponed. By contrast, living-donor organ transplantation does not have the same distinction, mainly because of the potential infection risk posed to living donors. Indeed, the American Society of Transplantation (AST) recommended suspension of livingdonor transplantation during the initial months of the pandemic. We focus on deceaseddonor kidney transplantation in this paper.
To be certain, three key factors make disruptions to deceased-donor organ transplants inevitable. First, during the pandemic, the reduction in the population mobility has naturally led to a shrunken pool of deceased individuals who are eligible for organ donation. Second, as they scramble to tackle surging COVID-19 cases, hospitals might find themselves constrained by dwindling healthcare resources that are necessary for performing organ transplant procedures. Third, as the number of COVID-19 infection cases has grown over time in various states, out of an abundance of caution, certain clinicians and patients may hesitate to proceed with transplant procedures. However, these three factors are shared across all states, regardless of whether a guidance for nonessential surgery has been issued. Indeed, by controlling these factors, we can tease out the effect of state guidances for non-essential surgery—inapplicable to deceased-donor organ transplantation—on the transplant volume.
Estimating the effect of state guidances for non-essential surgery on essential surgery is a challenging task, in no small part because nationwide clinical datasets (e.g., claims and electronic records)—containing all the cases for a given type of essential surgery with uniform data-reporting standards—are rarely available. Fortunately, we obtained a nationwide dataset from the United Network for Organ Sharing (UNOS) for kidney transplantation covering the initial half of 2020. We examine the dataset through the
lens of the staggered suspension and resumption of non-essential surgery. Our data confirm the basic intuition that the COVID-19 pandemic led to a sharp reduction in the number of organ transplant procedures across all states. However, in states that issued
guidances for non-essential surgery, the reduction was particularly salient. We tease out the effect of state guidances using a difference-in-differences approach. We estimate that a state guidance for non-essential surgery caused a 32.3% drop in the volume of
deceased-donor organ transplants. Through this unique switching “on” and “off” of state guidances amid a major public health crisis, our study illustrates the spillover effect of health policy on patients' access to essential health services.
Contributing to policy debates about the impact of suspending non-essential surgery, our paper analyzes a high-acuity surgery setting with a uniquely clean and systematic dataset, which enables us to use a difference-in-differences approach to tease out the effect of state guidances. We show that although various states’ efforts aimed at preserving healthcare capacity are laudable, suspending non-essential procedures can lead to a spillover effect that will end up hurting patients’ access to essential procedures. Our findings are significant for potential future public health crises (including future waves of the COVID-19 pandemic) that may necessitate another round of surgical shutdown and subsequent reopening. Informed by our findings, instead of postponing all non-essential procedures, policymakers should explore more granular approaches to safeguard the healthcare workforce and resources critical to supporting essential care. They should also monitor the changes in hospitals’ service offering and provide financial and regulatory support proactively to reduce negative spillovers of their well intentioned policies.
Huo Tianming
Online Reusable Resource Allocation with Multi-class Arrivals
In today’s world, many businesses involve not simply selling products, but instead renting them out for short periods. Sharing economy, including car renting and cloud computing, has become deeply integrated into our daily life. In addition, applications including hotel capacity management, appointment booking involve allocating reusable resources. A key challenge in these settings is the volatility and unpredictability of customers’ arrivals, for example due to pandemics and military conflicts.
We study an adversarial online reusable resource allocation problem. There is a single type of resource pool with 𝐶 units for serving 𝑀(𝑀 ≥ 2) classes of customers. Each class 𝑚 is associated with a price willing to pay per unit time 𝑟 (𝑚) and a usage duration 𝐷 (𝑚) . We assume that 0 < 𝑟 (𝑚) ≤ 𝑟 (𝑚+1) , 0 < 𝐷 (𝑚) ≤ 𝐷 (𝑚+1) and 𝑟 (𝑚)𝐷 (𝑚) < 𝑟 (𝑚+1)𝐷 (𝑚+1) for all 𝑚 ∈ {1, … , 𝑀 − 1}. The time horizon is partitioned so that one customer arrives at each time period. This is without loss of generality since we model empty arrival as class 0 with 𝑟 (0) = 𝐷 (0) = 0.
At each time step 𝑡, one customer arrives with 𝑟𝑡𝐷𝑡 being the price willing to pay for the whole usage. The agent observes the customer type and then decide to accept or to reject the customer. If the decision is to accept, then one unit of resource will be allocated and occupied from time 𝑡 to 𝑡 + 𝐷𝑡 − 1, and a revenue of 𝑟𝑡𝐷𝑡 is earned. If the decision is to reject, then no unit is allocated and no revenue is earned. The future arrival sequence is adversarially chosen, which means that the arrival could follow some changing distributions which are unknown to the agent. The objective is to maximize the total revenue, subject to the constraint that the number of units being occupied at each time step should not exceed the total capacity. Our model is an adversarial variant to the stochastic model by Levi and Radovanovi (2010). When we set the usage durations to be infinite in our model, the specialized model coincides with Ball and Queyranne (2009). Our model can also be cast as a pricing variant to the online assortment problem (see Feng et al. 2019 for example). We quantify the performance of an online algorithm with its Competitive Ratio (CR), which is the minimum ratio between the revenue achieved by the algorithm and the revenue achieved by the optimal offline algorithm who knows the full sequence from the beginning, where the minimum is taken over all possible instances.
We propose an original online policy, the Protection Level Policy for Reusable Resources (PLP-RR). At each time step 𝑡, PLP-RR sets a rejection price 𝑅𝑡 , and only accept customers with a price willing to pay strictly higher than the rejection price. The rejection price depends on quantities {𝐼𝑡(𝑚)}𝑚=0 𝑀−1 , where 𝐼 𝑡 (𝑚) = |{𝑠 ∈ {1, … 𝑡 − 1}: 𝑅𝑠 = 𝑟 (𝑚)𝐷 (𝑚) , 𝑠 + 𝐷𝑠 − 1 ≥ 𝑡}|. To interpret, 𝐼 𝑡 (𝑚) is the number of resource units that are (1) allocated under the rejection price 𝑟 (𝑚)𝐷 (𝑚) , (2) still being occupied at time 𝑡. PLP-RR takes into inputs a set of parameters {𝐶 (𝑚) }𝑚=0 𝑀−1 , and rejection price 𝑅𝑡 is set as 𝑟 (𝑚)𝐷 (𝑚) , where 𝑚 is the smallest integer that satisfies 𝐼 𝑡 (𝑚) < 𝐶 (𝑚) . The intuition of the algorithm is that the total capacity is partitioned into 𝑀 classes such that there are 𝐶 (𝑚−1) number of class 𝑚 units for all 𝑚 ∈ {1, … , 𝑀}. Class 𝑚 units can only be allocated to customers of class 𝑚, … , 𝑀. That is, class 1 units can be allocated to all non-empty customers, class 2 units can be allocated to a customer of class 2 or above. The definition of class 𝑚 units is the units to be allocated with rejection price being 𝑟 (𝑚−1)𝐷 (𝑚−1) . As a result of the algorithm, the parameters {𝐶 (𝑚) }𝑚=0 𝑀−1 serves as booking limits in the sense that at any time 𝑡, the number of customers who has a price willing to pay at most 𝑟 (𝑚+1)𝐷 (𝑚+1) , and still occupying a unit of resource at time 𝑡 is at most ∑ 𝐶 𝑚 (𝑛) 𝑛=0.
We prove that PLP-RR achieves asymptotic optimality with large capacity when the usage duration of any class divides that of any higher class, which is what we call divisible durations. The loss factor, which approaches to zero when capacity is large, is due to the rounding the theoretically optimal booking limits to obtain a set of integer booking limits. PLP-RR achieves optimality if the theoretically optimal booking limits are a set of integers and therefore no rounding is needed. The case where all classes of customers having the same usage duration also satisfies the duration divisibility condition. We highlight that such loss factors are not unique to our result, and similar loss factors appear in Ball and Queyranne (2009) for non-reusable resources, which is a special case in our model. When the durations are general, PLP-RR achieves an asymptotic competitive ratio that is within a factor of half of optimality. To be exact, the factor ratio of optimality depends on the durations of the classes and is lower bounded by half.
We use a primal-dual approach to prove the competitive ratio, where we construct a linear program whose dual is an upper bound to the offline optimum. To be exact, we propose an original Auxiliary Algorithm (AA) where a feasible dual solution is constructed, and the ratio between primal objective value which is the total revenue, and dual objective value achieved by the dual variables constructed in AA are lower bounded by the competitive ratio. Our primal-dual approach is fundamentally different from traditional primal-dual online algorithms from Buchbinder and Naor (2009) in the sense that traditional primal-dual algorithms involve an online update of the dual variables, which is used to guide the online decisions. However, our analysis only sets the values of the dual variables in AA after the whole online process. The dual is only used for analytical purpose but not for online decisions. We are hopeful that such a novel primal-dual approach might find applications in other online problems.
We then show that similar methodology can be extended to the advance booking problem, where usage only starts after a period of time since the customer arrival. We use 𝑠𝑡 to denote the starting time of usage for customer arrived at time 𝑡. Therefore, the requested usage period for the customer at time 𝑡 will be from time 𝑠𝑡 to 𝑠𝑡 + 𝐷𝑡 − 1. We propose the Protection Level Policy for Advance Booking (PLP-AB), in which the rejection price depends on {𝐼 𝑡,𝜏 (𝑚) }𝜏∈[𝑠𝑡 ,𝑠𝑡+𝐷𝑡−1],𝑚∈[0,𝑀−1] , where 𝐼 𝑡,𝜏 (𝑚) denotes the number of units allocated until time 𝑡 − 1, that is still being occupied at time 𝜏, and with the rejection price being 𝑟(𝑚)𝐷 (𝑚) when allocated. To be exact, the customer will only be accepted if there is available unit with a class number at most that of the customer, for all the time steps in the usage period requested by the customer. This is different from PLP-RR where only the inventory time 𝑡 is needed to make the decision.
We show that PLP-AB achieves an asymptotic competitive ratio that is within a factor of half of that for resource allocation with large capacity. This is proved using a similar primal-dual approach where an Auxiliary Algorithm is proposed to construct a feasible dual solution that upper bounds the offline optimum.
We conduct numerical experiments to evaluate the empirical performance of both PLP-RR and PLP-AB. We compare the algorithms with the First-Come-First-Serve (FCFS) policy under adversarial arrival with slight stochasticity and completely stochastic arrival patterns. We have three important observations. First, both algorithms have better empirical performance than competitive ratio even with slight stochasticity in the arrival pattern. Second, both algorithms perform dominate the FCFS policy under both arrival patterns for resource allocation and advance booking problem respectively. Lastly, both algorithms are more resilient than the FCFS policy when the arrival pattern changes from stochastic to adversarial, since much less performance degradations are seen.
Gang Guo
The Effect of Platform Dynamic Pricing Competition on Sellers
Online platforms use aggressive price promotions to build a customer base and compete for market share during the start-up phase. Sellers pay fees when selling on platforms that compete with their own (direct) sales channel. They see an increase in sales but become more dependent on platforms and have less bargaining power as the online market grows. Raising the commission rate is one predictable action of the platform. Other downsides of the platform are mentioned in Hagiu and Wright (2021), e.g. platform siphoning, manipulation of recommendations, and price restrictions.
Our paper studies a fundamental research question. What is the effect of platform competition on sellers? More specifically, we answer the following counterfactual questions:
- First, what are the sellers’ profits if there are no platform channels?
- Second, what if there is an increase in platform commission fees from 5% to 15%?
- Third, any effective ways to mitigate the platform’s negative impact.
