{'fraction_non_alphanumeric': 0.05192128518591716, 'fraction_numerical': 0.015669555888082668, 'mean_word_length': 3.8466748768472905, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 18, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 77, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On Policies for Single-leg Revenue Management with Limited Demand Information

In this paper we study the single-item revenue management problem, with no information given about the demand trajectory over time. When the item is sold through accepting/rejecting different fare classes, Ball and Queyranne (2009) have established the tight competitive ratio for this problem using booking limit policies, which raise the acceptance threshold as the remaining inventory dwindles. However, when the item is sold through dynamic pricing instead, there is the additional challenge that offering a low price may entice high-paying customers to substitute down. We show that despite this challenge, the same competitive ratio can still be achieved using a randomized dynamic pricing policy. Our policy incorporates the price-skimming technique from Eren and Maglaras (2010), but importantly we show how the randomized price distribution should be stochastically-increased as the remaining inventory dwindles. A key technical ingredient in our policy is a new"valuation tracking"subroutine, which tracks the possible values for the optimum, and follows the most"inventory-conservative"control which maintains the desired competitive ratio. Finally, we demonstrate the empirical effectiveness of our policy in simulations, where its average-case performance surpasses all naive modifications of the existing policies.


Introduction
In this paper we consider the single-leg revenue management problem, where a firm is selling multiple products that share a single capacity over a finite time horizon. The price of each product and the unreplenishable starting capacity are exogenously determined. The firm's objective is to maximize its total revenue earned, by dynamically controlling the availability of different products over time. The tradeoff lies between "myopic" controls which maximize the immediate revenue at a point in time, and "conservative" controls which ration capacity for the remaining time horizon.
The motivating application for this problem lies in airlines, where each flight leg has a limited seat capacity, and the products correspond to different "fare classes" (e.g. economy, business) which offer seats at different prices. The seat capacity and fare classes have been determined long in advance, through factors such as business strategy, positioning, competition, etc. The time horizon is finite, ending upon the flight's departure.
We study this problem in the setting where very limited information is given or can be learned about demand. This setting was introduced by Ball and Queyranne (2009), Lan et al. (2008), where meaningful controls can be derived based on only the knowledge of the fare class prices. The authors consider booking limit policies, which can be described as follows. Initially, all of the fare classes are made available to customers. Once the total seat sales surpasses a critical threshold, the lowest fare becomes unavailable. Progressively higher fares are made unavailable until the flight either becomes full or takes off.
An important assumption made in the model of Ball and Queyranne (2009) is that demand for the different fare classes is independent. That is, although the lower fares are made available until their booking thresholds are reached, there is no risk of cannibalizing the sales of higher fares.
The justification for this assumption in the literature is two-fold. First, the fare classes have been designed to segment customers and achieve price discrimination, i.e. the perks provided by business class dissuade price-insensitive business travelers from having interest in lower-class fares. Second, these business travelers tend to book last-minute, i.e. by the time they book the lower-class fares have usually become unavailable anyway.
However, marketplace and technology changes have introduced environments where these justifications may no longer hold. For example, the competition from low-cost carriers (e.g. Spirit Airlines) has forced major airlines (e.g. United Airlines) into adopting more overlapping fare family structures (e.g. adding a "basic economy" fare which competes with the regular economy fare).
Also, the advent of e-commerce has brought a significant increase in customer sophistication, as well as the firm's understanding of customers via "big data" analytics. The motivation of this paper is to derive advanced booking controls which rely on dynamic price-changing infrastructure instead of the independence assumption to differentiate between customers with different willingness-to-pay.

Model and Results
Throughout this paper, we analyze the "critical" case where customers always substitute to the lowest available fare. In Section 6, we explain why this is sufficient to allow for any setting where customers substitute according to a random-utility choice model.
In this critical case, the problem reduces to a dynamic pricing problem. We can describe each customer using a valuation, or maximum willingness-to-pay. At each point in time a single price is offered, and customers who encounter that price make a purchase if and only if it does not exceed their valuation. (Offering multiple prices is redundant, because the lower price would always be chosen over the higher price.) We let P denote the set of fare class prices, which are the feasible prices to charge. The starting capacity comes in the form of k discrete units of inventory. The selling horizon consists of T discrete time steps, which are sufficiently granular such that at most one customer arrives during each time step. We let V t denote the maximum price in P that the customer in time t is willing to pay, which is 0 if no customer arrived. An online algorithm must sequentially choose a price P t for each time t, and if V t ≥ P t , then revenue P t is earned and one unit of inventory is depleted.
In settings where no information is given about the sequence of valuations, an online algorithm is evaluated by comparing its total revenue earned on different sequences to that of a clairvoyant optimum. For any sequence V 1 , . . . , V T , the offline optimum OPT(V 1 , . . . , V T ) is defined as the maximum revenue that could have been earned from knowing all the valuations in advance, equal to the k largest values in V 1 , . . . , V T . For c ≤ 1, if an online algorithm can guarantee that its revenue is at least c · OPT(V 1 , . . . , V T ) on every sequence V 1 , . . . , V T , then it is said to be c-competitive.
If c is best-possible in that any (potentially randomized) online algorithm cannot simultaneously guarantee greater than c · OPT(V 1 , . . . , V T ) revenue over all sequences V 1 , . . . , V T , then c is called the competitive ratio.
In the model of Ball and Queyranne (2009), the competitive ratio for any problem instance is shown to be a function of only the price set P, which we will denote using c * (P). Their model corresponds to ours when each V t is deterministic and given at the start of time t. The decision at time t then reduces to an accept-reject decision, where accepting customer t corresponds to charging her maximum willingness-to-pay of V t , and rejecting customer t corresponds to charging any price above V t (possibly ∞ if the inventory has run out). Ball and Queyranne (2009) derive c * (P)-competitive booking limit policies which specify when to reject customers paying low prices.
In this paper, we derive c * (P)-competitive online algorithms under the following models with progressively less information: 1. V t is deterministic and given at the end of time t (Section 2). This model includes the case where the airline has a point estimate of V t at the start of time t, but does not use it in determining the price P t , because the airline wants to refrain from "personalized pricing".
2. V t is stochastic and distributionally-given at the end of time t (Section 3). In this model, the airline estimates a conditional distribution of the customer's valuation V t falling into the different fare classes, by using the arrival patterns of different fare classes as well as the customer's response to being offered price P t .
3. No information on V t is ever given (Section 4).
All of these algorithms are best-possible. Indeed, since an online algorithm cannot be better than c * (P)-competitive under the model of Ball and Queyranne (2009), an online algorithm also cannot be better than c * (P)-competitive under our models with less information.
Our algorithms use the price-skimming technique of Eren and Maglaras (2010), who analyze how the price of an item should be distributed (e.g. across stores, across time) when the price set P is known but demand is completely unknown. Their model corresponds to ours when the inventory constraint is irrelevant (e.g. when k ≥ T ), in which case they show that the competitive ratio is also c * (P). Our work shows how the price-skimming distribution should depend on inventory when it is relevant. More specifically, our algorithm determines the optimal path-dependent pricing distribution for each time step t, conditional on the amount of remaining inventory. Interestingly, our algorithm has the following feature: at any time step, the price distribution which maximizes the competitive ratio is strictly stochastically-decreasing in the amount of remaining inventory (see Section 2.4). In fact, this is analogous to a classical structural property when the demand sequence is known or distributionally-known: at any time step, the price which maximizes the expected revenue is strictly decreasing in the amount of remaining inventory (Gallego andVan Ryzin 1994, Zhao andZheng 2000).
Finally, in Section 5, we consider the personalized online revenue management setting where the distribution of each V t becomes available at the start of time t, and this information can (and should) be used in determining the offering to customer t. Introduced by Golrezaei et al. (2014), this setting has a very practical motivation of e-commerce, where purchase probabilities are estimated for each customer based on her personal characteristics (e.g. Mac users have a higher chance of buying business-class flights). Although our algorithms from Sections 2-3 focus on the setting without personalized pricing, we show in Section 5 that our algorithms can be naturally adapted to exploit personal information. The adapted algorithms maintain the competitive ratio of c * (P), which is best-possible even with personalized information, since c * (P) is best-possible under the setting of Ball and Queyranne (2009) where each customer's personal valuation is known deterministically.

Sketch of Techniques, and Comparison with Existing Techniques
The main technical contribution behind our results is a new "valuation tracking" procedure which incorporates both booking limits and price-skimming. We motivate it using the following example, under the model where each valuation V t is deterministic and revealed at the end of time t. The price set is P = {1, 2, 4}, and we will refer to customers with these valuations as being of type-L (Low), type-M (Medium), and type-H (High), respectively.
The competitive ratio for this price set derived by Ball and Queyranne (2009) and Eren and Maglaras (2010) is c * (P) = 1/2, and we describe below their respective 1/2-competitive policies.
• Booking Limits (Ball and Queyranne 2009): Initially charge $1; increase the price to $2 after 1/2 of the starting inventory has been sold; further increase the price to $4 after 3/4 of the starting inventory has been sold. (This is the variant of booking limits with "theft nesting".) • Price-skimming (Eren and Maglaras 2010): Charge $1 for 1/2 of the time steps; charge $2 for 1/4 of the time steps; charge $4 for 1/4 of the time steps.
We now discuss what happens if we try to implement these policies under our model.
Attempt 1: Direct implementation of booking limits. It is easy to see that this would not be 1/2-competitive-suppose just one type-H customer arrived at the start. The algorithm would be charging the low price of $1, while the offline optimum would be the customer's valuation of $4.
Any direct implementation of price-skimming would suffer similarly, since there could be a single type-H customer who arrives during a time when the price is set to $1.
Attempt 2: Price-skimming as a randomized price. It appears that the problem with Attempt 1 can be solved using the "random price" interpretation of price-skimming-instead of deterministically partitioning the time horizon according to ratios 1 2 , 1 4 , 1 4 and offering prices 1,2,4 respectively, one could at each time step choose the prices randomly with respective probabilities 1 2 , 1 4 , 1 4 . Then, if a single type-H customer arrives, the expected revenue would be 1 2 · 1 + 1 4 · 2 + 1 4 · 4 = 2 which is 1/2 of the customer's valuation of $4. It can be checked that 1/2 of the customer's valuation is also earned when it is $1 or $2; this is by construction of the price-skimming distribution.
However, having a fixed price-skimming distribution is no longer effective under inventory constraints. Indeed, if a long sequence of type-L customers arrive, then this would deplete the inventory with high probability, and type-H customers who arrive last-minute would not be served, and the ratio of optimum earned would again be 1/4.
Attempt 3: Naive incorporation of booking limits into price-skimming. It appears that the problem with Attempt 2 can be solved by respecting the booking limits, i.e. forbidding price-skimming from randomly choosing the price of $1 after 1/2 of the starting inventory has been sold. However, this still fails to be 1/2-competitive, as shown by the following example. Suppose the starting inventory is 4, and that 2 type-H customers arrive followed by a type-L customer, with no customers arriving after that. The optimum would be $9. However, the algorithm's revenue would only equal $4: it would earn $2 in expectation from each of the type-H customers, depleting 2 units of inventory, and then earn $0 from the type-L customer due to the booking limit.
Our procedure: Valuation tracking. The problem with Attempt 3 leads to the following observation-the optimum is guaranteed to increase from the first 4 customers (since there are 4 units of inventory), so in order to be 1/2-competitive, the algorithm must maintain the initial price-skimming distribution for the first 4 customers. After that, the algorithm can respect booking limits as long as customers rejected in this way would not increase the optimum, and in fact should do so, to avoid the problem in Attempt 2 of stocking out. This motivates our procedure below.
• Valuation Tracking: At each time t, let ℓ t denote the smallest value (possibly 0) in the 4 largest valuations to have arrived before time t (since 4 is the starting inventory). Then, randomly choose the price in a way such that the algorithm's expected revenue during time t is equal to V t − ℓ t is the gain in the offline optimum should the valuation of customer t be V t , and 1/2 is the desired competitive ratio. The constraint that the algorithm's revenue is exactly equal to (1) effectively forces it to use the most inventory-conservative controls which maintains 1/2competitiveness, thereby hedging against a stockout. The price distribution used at each time t depends on the inventory state, and in fact, the calculation for the algorithm's expected revenue must account for the probability of stocking out before time t. The surprising fact is that it is possible to choose price distributions which collectively guarantee (1).
We illustrate our basic valuation tracking procedure in Section 2.1 by "stacking" the past valuations in a geometric configuration, and formalize it in Section 2.2. The basic procedure is designed to have a clean analysis and we consider variants in Sections 2.3-2.4, as well as generalize it to the stochastic-valuation model in Section 3.2. A unique challenge arises in Section 3.3, where we use sampling to convert a c * (P)-competitive valuation tracking procedure with exponential runtime into a (c * (P) − ε)-competitive procedure with polynomial runtime.

Related Work
Single-leg revenue management is a cornerstone problem in the area of revenue management and pricing, as outlined in the book by Talluri and Van Ryzin (2006). Many different approaches for modeling demand have been considered over the years, as surveyed in Caldentey (2011), den Boer (2015). In contrast to other approaches, which optimize based on a forecast of future demand (Gallego andVan Ryzin 1994, Zhao andZheng 2000), learn an unknown demand function (Besbes and Zeevi 2009), or learn in various Bayesian Caldentey 2009, Chen andWu 2016) and minimax (Lim andShanthikumar 2007, Zhang et al. 2016) settings, competitive ratio analysis is a form of minimax analysis that operates without demand information.
Our work extends the notion of booking limits from Ball and Queyranne (2009) to allow for non-independent demand, by incorporating the price-skimming of Eren and Maglaras (2010).
We should point out that our "random price" interpretation of price-skimming originated from Bergemann and Schlag (2008). Randomization is a powerful technique for improving the competitive ratio of online algorithms; for further background we refer to the book by Borodin and El-Yaniv (2005).
Motivated by e-commerce, the competitive ratio has also been recently studied in many "personalized recommendation" settings (Golrezaei et al. 2014, Ma and Simchi-Levi 2017, Cheung et al. 2018. In these papers, there are multiple commodities ("legs") and interchangeability in which commodities are offered to each customer. Our paper differs from these papers in two ways. First, we do not rely on personalized controls, and instead derive a global price-skimming distribution, which is useful for online retailers who choose not to engage in personalized pricing. Also, even when personalization is desired, we show in Section 5 how to effectively use personalized information in the single-leg case, and obtain a competitive ratio c * (P) which is greater than the multi-leg competitive ratio from Ma and Simchi-Levi (2017).
Finally, while we analyze the problem of inventory-constrained dynamic pricing throughout this paper, our results easily generalize to the dynamic assortment setting, as explained in the conclusion (Section 6) of this paper. Our techniques prescribe the best-possible trade off between revenue maximization and inventory consumption (see Maglaras and Meissner (2006)) when there is a single flight leg, known fare classes, but general unknown demand.

Deterministic Valuations
In this section we consider the problem defined in Section 1.1 under the model where each customer's valuation is deterministic and revealed immediately after she leaves.
First we define some additional notation to that defined in Section 1.1. For any positive integer n, let [n] denote the set {1, . . . , n}. For notational convenience, we will assume that P consists of m discrete prices, i.e. P = {r (j) : j ∈ [m]}, sorted 0 < r (1) < . . . < r (m) . All of our results can be generalized to the case where P is a continuum of prices taking the form [r min , r max ], as we discuss in Section D. We define r (0) to be 0, and then the valuation V t at any time t lies in r (0) , . . . , r (m) , with V t = r (0) representing the lack of a customer during time t. Similarly, we define r (m+1) to be ∞, and then the price P t at any time t lies in r (1) , . . . , r (m+1) , with P t = r (∞) representing the firm shutting off demand during time t, which is the only option if its inventory is out of stock. Let X t be the indicator variable for making a sale during time t, i.e. it is 1 if V t ≥ P t , and 0 otherwise.
Let T denote the number of time steps. None of the algorithms in this paper assume any knowledge of T ; note that T can always be made arbitrarily large by inserting customers with valuation 0.
We will hereafter treat T as the unknown total number of customers, and use the phrase "customer t" to refer to valuation V t (even if it is 0).
An online algorithm must choose each P t based on the history of past prices and valuations, P 1 , V 1 , . . . , P t−1 , V t−1 . This history also determines the values of X 1 , . . . , X t−1 . The online algorithm does not know T , and has no information about V t , V t+1 , . . . , V T , when choosing P t . In contrast, the offline optimum knows the entire sequence V 1 , . . . , V T before having to choose any prices. Given any valuation sequence V 1 , . . . , V T , we use the P t and X t variables to refer to the execution of an online algorithm on the valuation sequence. Since the online algorithm may be randomized, we treat P t and X t as random variables. Let ALG(V 1 , . . . , V T ) denote the total revenue earned by the online algorithm, equal to We will omit the arguments (V 1 , . . . , V T ) in ALG and OPT when the context is clear.
As explained in Section 1.1, since our problem captures the problems of both Ball and Queyranne (2009) and Eren and Maglaras (2010), an upper bound for the value of c in (2) is given by c * (P), as defined below.
Definition 1. For any m ≥ 1, 0 < r (1) < . . . < r (m) , and P = {r (1) , . . . , r (m) }, define: The interpretation of q (j) in Ball and Queyranne (2009) is the fraction of initial inventory "set aside" for prices j and higher. The interpretation of q (j) in Eren and Maglaras (2010) is the fraction of time that price j should be charged. Both of the papers establish that the competitive ratio cannot be better than c * (P) via Yao's minimax principle (Yao 1977). Therefore, for any fixed (but possibly randomized) online algorithm in our problem, there exists a sequence V 1 , . . . , V T such E[ALG(V 1 , . . . , V T )] ≤ c * (P) · OPT(V 1 , . . . , V T ). In this paper we derive various c * (P)-competitive algorithms, using our valuation tracking procedure as the core subroutine.

Intuition behind Valuation Tracking Procedure
The goal of our basic procedure is to, for each customer, earn a constant fraction c * (P) of the gain in OPT from that customer arriving, which would imply being c * (P)-competitive. To accomplish this, it tracks the current value of OPT, i.e. the sum of the k largest valuations to have arrived thus far, which are assumed to be known.
The procedure considers the possibilities for the increase in OPT from the next customer, which we denote as ∆OPT. Since the smallest valuation currently counted toward OPT is 1, if the valuation of the next customer if 4, then ∆OPT = 3; if it is 2, then ∆OPT = 1. If the next customer has valuation not exceeding 1, then ∆OPT = 0. The procedure wants to guarantee that its expected revenue on the next customer is at least 1 2 · ∆OPT, for all of these possible valuations. To accomplish this, it has to consider the probability that it has stocked out at this point; on those sample paths its revenue is 0.
Our procedure cleanly accounts for the probability of stocking out using the following approach.
Each customer is assigned to a specific unit of inventory i ∈ [k] upon arrival. Each inventory unit i maintains a variable level[i], which is the maximum valuation of a customer previously assigned to it. The next customer is always assigned to an unit i * with the smallest value of level[i * ], regardless of whether that unit i * has already been sold. In this way, the assignment procedure is deterministic, and allows us to maintain an invariant: the probability a unit i has been sold is dependent on only the (deterministic) value of level[i]. The configuration of valuations, before and after a customer with valuation 2 arrives.
For each customer, the procedure makes an offer to her only if unit i * has not been sold, at a random price exceeding level[i * ]. The higher level[i * ] is, the more likely it is that unit i * has been sold, and the lower the expected revenue from that customer. However, if level[i * ] is high, then the potential increase in OPT from that customer is also lower; if the valuation of the customer does not exceed level[i * ], then both the procedure's revenue and ∆OPT are 0. By properly choosing the distributions for the random prices, our procedure is able to maintain the invariant on the probability of each unit being sold, while earning 1 2 · ∆OPT in expectation from each customer.
Returning to the example, given that the first 5 customers had valuations 4, 1, 4, 1, 2, the values of level[i] for i = 1, . . . , k are shown in the LHS of Fig. 1. The next customer, "customer #6", is assigned to inventory unit 2. After her valuation is revealed to be 2, the updated configuration is shown on the RHS of Fig. 1, regardless of whether she was rejected.
Customer #6 would have been rejected if unit 2 was sold before her arrival, even if other units were available. When P = {1, 2, 4}, the probability that a unit i has been sold equals 0, 1 2 , 3 4 , 1 if level[i] is 0, 1, 2, 4, respectively. These probabilities correspond to the values of q (j) from Definition 1. Since level[2] was 1 before customer #6 arrived, she is made an offer with probability 1 2 , at a random price exceeding 1. The price is 2 with probability proportional to 1 4 , and 4 with probability proportional to 1 4 (again using the values of q (j) ), hence each price would be offered Algorithm 1: Valuation Tracking Procedure Input: Customers t = 1, 2, . . . arriving online, with each valuation V t revealed after the price P t is chosen. Output: For each customer t, a (possibly random) price P t for her.
reject the customer by choosing price ∞; with probability 1 2 . The customer's valuation is 2, so she will only buy the item if offered price 2, which occurs with total probability 1 2 · 1 2 = 1 4 . Note that: 1. Customer #6 increases the probability of unit 2 being sold from 1 2 to 3 4 , which is consistent with her increasing level[2] from 1 to 2; 2. Customer #6 increases the value of OPT, equal to k i=1 level[i], by 1 (from 12 to 13); 3. Customer #6 brings in expected revenue 1 4 · 2 = 1 2 .
Therefore, during time step 6, our procedure has earned expected revenue 1 2 · ∆OPT. We will show that it achieves this for a general P, and all time steps t, regardless of the valuation of customer t.

Valuation Tracking Procedure and Analysis
We now formalize our valuation tracking procedure, in Algorithm 1.
In line 7, the procedure offers exactly one of the prices r (ℓ t +1) , . . . , r (m) , with the offering probabilities summing to unity. Note that it cannot branch to line 7 if ℓ t = m. This can be seen in the following way. If ℓ t = m, then i * t must have been assigned to some past customer t ′ with V t ′ = r (m) .
At time t ′ , either inventory unit i * t was already sold, or customer t ′ was offered a price at most r (m) , which she would have accepted. In either case, sold[i * t ] must be true.
The analysis of Algorithm 1 is conceptually simple. Let b i,t be the index in 0, . . . , m such that at the end of time t, and j t be the index such that V t = r (j t ) . We show that the following claims are maintained: 1. At the end of each time step t, the probability that any inventory unit i has been sold is During a time step t, if the valuation of the customer exceeds the level of the inventory unit she is assigned to, i.e. j t > ℓ t , then: (a) The expected revenue earned by Algorithm 1 is 1 If j t ≤ ℓ t during a time step t, then both the revenue of Algorithm 1 and the gain in OPT are 0.
These claims establish the following theorem, whose full proof is deferred to Section A.

Modified Algorithm based on Valuation Tracking Procedure
In this section we present a modified version of Algorithm 1 which is useful for the subsequent developments under the stochastic-valuation model in Section 3.
First we show how to modify Algorithm 1 so that its decision at each time t depends on only the remaining inventory, instead of the entire history of purchase decisions X 1 , . . . , X t−1 .
Definition 2. For all t = 0, . . . , T , let I t denote the random variable for the amount of remaining inventory at the end of time t, which is equal to Our modified algorithm makes an offer to customer t according to the probability that unit i * t hasn't been sold, conditioned on the realized value of I t−1 . In this way, its decisions depend on only the inventory state, instead of the exact decisions of past customers.
Definition 3 (Algorithm 1'). Define the following algorithm for choosing the price at each time t, based on the past valuations V 1 , . . . , V t−1 and the amount of remaining inventory I t−1 .
1. Consider the indices i * t and ℓ t during iteration t of Algorithm 1, which are deterministic based on V 1 , . . . , V t−1 .
2. Compute the probability that sold[i * t ] = true on a run of Algorithm 1, conditioned on I t−1 units of inventory remaining after time t − 1 in that run. Let γ t denote this probability.
3. With probability γ t , make an offer to customer t with the same price distribution as Algorithm 1 (line 7); with probability 1 − γ t , reject customer t.
Algorithm 1' chooses the distribution for P t by "averaging" over all runs of Algorithm 1 which have the same value of I t−1 . We first remark that this can be done in polynomial time, despite there being exponentially many sample paths for Algorithm 1. We prove the following in Section B.
Lemma 1. The value of γ t in Step 2 of Algorithm 1' can be computed in polynomial time.
We now introduce some notation to disambiguate between random variables depicting the runs of different algorithms.
Definition 4. For an algorithm A, let P A t , X A t , and I A t be the random variables for the price at time t, purchase decision at time t, and inventory remaining at the end of time t, respectively.
Let ALG A be the random variable for the total revenue earned by algorithm A. We will omit the superscripts A when the context is clear.
Let A = A1 refer to Algorithm 1 and A = A1 ′ refer to Algorithm 1'.
We show that Algorithms 1 and 1' are virtually the same in that they have identical distributions for the remaining inventory at each time step, as well as the random price at each time step conditioned on any value of remaining inventory. This also establishes that Algorithm 1' is feasible, in that it does not try to make a sale with zero remaining inventory.
Also, for all t = 0, . . . , T and k ′ ∈ {0, . . . , k}, Lemma 2, proven in Section B, is a consequence of the design of Algorithm 1'. For all t, the random price P A1 ′ t is identically distributed as P A1 t , conditional on any value for the amount of remaining inventory at the end of time t − 1. Hence if I A1 ′ t−1 and I A1 t−1 are identically distributed, then so are I A1 ′ t and I A1 t . This allows us to inductively establish that the two algorithms have the same aggregate behavior after combining all sample paths, even though their behavior may differ given a specific history of purchase decisions. This also makes it easy to see that the expected revenues of the two algorithms are the same. Lemma 2 directly implies the following theorem.

Further Modified Algorithm and Structural Properties
In this section we present a further-modified version of Algorithm 1' which satisfies two structural properties: (i) it never rejects a customer if it has remaining inventory, offering the maximum price instead; (ii) the distribution of prices offered to a customer is strictly stochastically-decreasing (see Corollary 1) in the amount of remaining inventory. Property (ii) is the stochastic analogue of the classical structural result from Gallego and Van Ryzin (1994, Thm. 1) and its generalization to non-homogeneous demand in Zhao and Zheng (2000, Thm. 3): at any time step, if the firm has more inventory, then the optimal offering price is strictly lower.
Definition 5 (Algorithm 1"). Define the following modification to Algorithm 1': in Step 3, offer price the maximum price r (m) to customer t, instead of rejecting her, with probability 1 − γ t .
We prove the following general lemma, which is intuitively easy to see, in Section B.
Lemma 3. Let A be any pricing algorithm. Let A ′ be the modified algorithm which: whenever A would reject a customer while there is remaining inventory, A ′ offers price r (m) instead. Then on Lemma 3 shows that Algorithm 1" is c * (P)-competitive. Now, we would like to further show that the probability of Algorithm 1' rejecting, or correspondingly the probability of Algorithm 1" offering the maximum price, is smaller when conditioned on larger values of remaining inventory.
Theorem 3. Suppose that the unconditional probability of Algorithm 1' rejecting customer t, This structural property is intuitive, and we defer its proof to Section B. Theorem 3 allows us to conclude with the following corollary about strict stochastic dominance.
denote the CDF's of the price P t offered by Algorithm 1" at time t conditional on the remaining inventory I t−1 being k 1 , k 2 , respectively. Then

Stochastic Valuations
The model with stochastic valuations differs from the model with deterministic valuations studied in the previous section in the following ways. The valuation of each arriving customer is now randomly drawn from some probability distribution. The valuations of different customers are independent, but not necessarily identically distributed. An online algorithm is given the valuation distribution for each customer after the price for that customer has been chosen.
Definition 6. We use the following notation, defined for all t: • V t : the valuation of customer t, a random variable taking values in {r (0) , r (1) , . . . , r (m) }; , the vector of realized valuations up to time t; • P A t : (P A 1 , . . . , P A t ), the vector of prices up to time t chosen by algorithm A.
We now provide a justification for our choice of offline optimum in our definition of competitiveness and competitive ratio, where in (2) we have replaced OPT(V 1 , . . . , V T ) with its expected value (and the values of V t are realized independently).

Discussion of the Offline Optimum with Stochastic Valuations
The weakest (least clairvoyant) offline benchmark one could compare against with stochastic valuations is the following. Consider an offline algorithm which is given the sequence of valuation distributions, v 1 , . . . , v T , in advance. Given this sequence, it can solve for the policy which maximizes expected revenue, using dynamic programming. Clearly, the expected revenue of such a policy is an upper bound on the expected revenue obtainable by an online algorithm.
However, such a benchmark is difficult to compare against, because the optimal policy knowing v 1 , . . . , v T , while computable in polynomial time, may not admit any structure. Therefore, we relax the offline optimum by allowing the offline algorithm to know the realizations of all the valuations V 1 , . . . , V T in advance. The optimal algorithm knowing such information then has a trivial structure (sell to the k largest valuations).
In line with the definition from Section 2, let OPT(V 1 , . . . , V T ) denote the sum of the k largest valuations in V 1 , . . . , V T . We define the competitive ratio with stochastic valuations to be In (3), the algorithm designer first commits to a (potentially randomized) algorithm ALG, after which an adversary chooses the sequence v 1 , . . . , v T , which determines the expected revenue of the online algorithm. The offline optimum is defined to be the expected value of We note that such an expected value cannot be computed in polynomial time; it is related to computing the expected project duration in a PERT network with independent task durations, which is #P-hard (Hagstrom 1988). Also, we should note that the definition of competitive ratio in (3) is equivalent to the following definition: which is a general fact in competitive ratio analysis (Krumke 2002).
Finally, we should point out that a different relaxation in the offline optimum is possible, originating from Gallego and Van Ryzin (1994); see also Talluri and Van Ryzin (2006). Given the valuation distributions, v 1 , . . . , v T , one can write the following Deterministic Linear Program (DLP): Let OPT LP (v 1 , . . . , v T ) denote the optimal objective value of the LP (4) where the value of each is an upper bound on the expected revenue of the optimal dynamic programming policy knowing v 1 , . . . , v T , since x (j) t encapsulates the unconditional probability of the policy offering price j to customer t.
Nonetheless, in this paper we don't compare against OPT LP (v 1 , . . . , v T ), which appears to be too strong of an offline benchmark. We show that the competitive ratio of c * (P), which was optimal in our deterministic setting, can still be achieved with stochastic valuations under definition (3). In other words, allowing the offline optimum to know the realizations of V 1 , . . . , V T does not decrease the competitive ratio. On the other hand, allowing the offline optimum to use the fractionality of the DLP (4) does decrease the competitive ratio; we provide some examples in Section E.

Optimally-Competitive Algorithm with Exponential Runtime
Having established our offline benchmark, we now derive c * (P)-competitive algorithms in the stochastic-valuation model. We do so by using our valuation tracking procedure as a subroutine, in a similar way to the development in Section 2.3, which may be helpful to reference.
Conceptually, our algorithm is a generalization of Algorithm 1' to stochastic valuations. However, since the assignment procedure in Algorithm 1 is no longer deterministic, we describe the algorithm in a different way. At a time step t, given v 1 , . . . , v t−1 and k ′ : 1. Consider a run of Algorithm 1 to the end of time t, where V 1 , . . . , V t−1 are randomly drawn the probability is over both the random valuations and the random prices chosen by the Let Exp denote this algorithm, and we will use the corresponding notation from Definition 4.
It will be seen that Exp is a feasible policy when we establish that I Exp In (5), the probability Pr[P A1 , which conditions on a fixed history is defined by lines 6-10 of Algorithm 1. Thus, calculating (5) requires enumerating all histories that result in I A1 t−1 = k ′ .
Unfortunately, at each time step t, this takes time exponential in t. The computational difficulty arises because the assignment procedure in Algorithm 1 is no longer deterministic, as it was throughout Section 2. For now, we ignore computational constraints and focus on obtaining an c * (P)-competitive online algorithm; in Section 3.3 we show how to use sampling to achieve polynomial runtime while only losing ε in the competitiveness.
The following lemma is analogous to Lemma 2 and proved in Section C.
Also, for all t = 0, . . . , T and k ′ ∈ {0, . . . , k}, Lemma 4 establishes that Exp is a feasible policy, i.e. it does not try to make a sale with no inventory remaining. Having established this, it remains to prove that Exp is optimally competitive.
Theorem 4 is proved in Section C.
We should point out that although Exp does not inherit the polynomial-time property from Algorithm 1', it does inherit the structural property of the price at any time being stochasticallydecreasing in the amount of remaining inventory. This is immediate from Theorem 3, which holds conditioned on any realization of V 1 , . . . , V T .
Also, note the following. P Exp t and P A1 t are only guaranteed to be identically distributed when averaged over all the sample paths up to time t − 1 such that the total remaining inventory is k ′ . They may not be identically distributed when conditioned on a specific purchase sequence our method works in general. For example, if valuations were correlated, then we would condition on both I t−1 and V 1 , . . . , V t−1 . One benefit of conditioning on only I t−1 in the independent case is to limit the state space, which is necessary for our polynomial-time sampling algorithm in Section 3.3.

Emulating the Exponential-runtime Algorithm using Sampling
In this section we show how to "emulate" Exp, using sampling, to achieve a polynomial runtime.
First we provide a high-level overview of the challenges and the techniques used to overcome them.
The intrinsic difficulty is that our original procedure is based on tracking the value of the offline optimum, but this becomes a #P-hard problem when the optimum equals the expected value of the k largest elements from independent realizations (see Hagstrom (1988)).
To overcome this using sampling, suppose we are at the start of time t, with inventory k ′ remaining. If we randomly sample a run of Algorithm 1 (drawing valuations randomly) such that I A1 t−1 = k ′ , and copy price P A1 This motivates the following algorithm: sample runs of Algorithm 1 to the end of t − 1 until hitting one where I A1 t−1 = k ′ , and then choose the price for time t according to lines 6-10 of Algorithm 1.
Such an algorithm is equivalent to Exp, and thus would be c * (P)-competitive.
However, on sample paths where Pr[I A1 t−1 = k ′ ] is small, the sampling could take arbitrarily long.
We limit the number of sampling tries so that the algorithm deterministically finishes in polynomial time, and show that the total measure of sample paths which fail at any point is O(ε).
Unfortunately, there could be correlation between the sampling failing, and having high revenue on a sample path. Nonetheless, we can couple the sample paths of the sampling algorithm to those of the exponential-time algorithm, mark the first point of failure on each sample path, and bound the difference in revenue after that point.
The details of the sampling algorithm, which we will call Samp, are specified in Algorithm 2.
In line 12, C is a positive integer to be chosen later. The decision of what to do when the sampling fails, i.e. defaults to line 13, is inconsequential, since in our analysis we do not expect any revenue from a sample path after the first point of failure.
To bound the revenue of Algorithm 2, we consider an algorithm which behaves identically to Algorithm 2, except even when it defaults to line 13, it is able to behave as if the sampling succeeded and makes the same decisions as lines 7-10. Such an algorithm is equivalent to Exp, and hereafter we will refer to it as Exp. The results of the sample runs do not affect the outcome of the algorithm, but help with bookkeeping. For convenience, here we will use different random variables to denote the valuations in the runs of Samp and Exp: V Samp t and V Exp t , respectively. We will also use the notation from Definition 4. Algorithm 2: Weakly Randomized Online Algorithm based on Inventory Remaining Input: Customers t = 1, 2, . . . arriving online, with each valuation distribution v t revealed after the price P t is chosen. Output: For each customer t, a (possibly random) price P t for her. 1 inventory = k; 2 t = 1; 3 while customer t arrives do • p t ′ is a price in {r (1) , . . . , r (m) , r (m+1) }, for all t ′ ∈ [t − 1]; • v t ′ is a valuation in {r (0) , r (1) , . . . , r (m) }, for all t ∈ [t − 1]. Furthermore, define the following vectors of random variables for all t ∈ [T + 1]: Now, we would like to partition the sample paths by the history up to the first point of failure, and prove that the two algorithms behave identically up to this point. Lemma 5. For a run of Algorithm 2, Lemma 5 is straight-forward, so we defer its proof to Section C. Having proved it, we can write: Since we also know that Pr[H Samp our goal is to compare the expected revenues of the two algorithms conditional on each history h t ∈ F t .
When t = T + 1, i.e. the sampling never fails, it is easy to see that the two revenues are equal.
Indeed, for any h T +1 ∈ F T +1 : Lemma 6. Recall that E[OPT(V 1 , . . . , V T )] is the expected value of the offline optimum with V 1 , . . . , V T drawn independently according to v 1 , . . . , v T . For t ≤ T and h t ∈ F t , Proof. Consider any t ∈ [T ] and h t ∈ F t . We have Meanwhile, We elaborate on the second term in (13). Clearly, The expectation in (14) is with respect to V Exp t , . . . , V Exp T being drawn independently according to v t , . . . , v T . (14) in turn is no greater than Substituting (10), for h T +1 ∈ F T +1 , and (11), for h 1 , . . . , h T ∈ F 1 , . . . , F T , into (8) and (9), we conclude that By Definition 9, the expression in parentheses is the total probability of the sampling failing at any point, before choosing the final price P Samp T . We bound the term for each t ∈ [T ] separately. As t increases, the number of samples increases, so the probability of failure decreases: Proof. Consider any t ∈ [T ]. For all h t ∈ F t , let G(h t ) = (f 1 , p 1 , v 1 , . . . , f t−1 , p t−1 , v t−1 ), which is the vector of the first 3(t − 1) entries in h t . Let G Exp t−1 = (F Exp 1 , P Exp 1 , V Exp 1 , . . . , F Exp t−1 , P Exp t−1 , V Exp t−1 ), which is a vector of 3(t − 1) random variables.
Now, for each h t ∈ F t , Pr[F Exp t = 1|G Exp t−1 = G(h t )] is the probability that all C(k + 1)t 2 independent runs of Algorithm 1 fail to match the inventory remaining at the start of time t according to where I A1 t−1 is the total inventory remaining at the start of time t in a run of Algorithm 1.
The following can be derived by substituting (17) into (16): At this point, we would like to argue that h t ∈F t : Applying the second statement of Lemma 4, we see that Pr[I Exp t−1 = k ′ ] = ρ t,k ′ . Substituting into (18), the following can be derived: The second inequality holds because for a single ρ t,k ′ ∈ [0, 1], the function ρ t,k ′ e −ρ t,k ′ C(k+1)t 2 is maximized at ρ t,k ′ = 1 C(k+1)t 2 . The proof of the lemma is now complete.
It now follows easily that the sampling algorithm is within ε of being optimally competitive.
Theorem 5 is straight-forward and proved in Section C.

No Information on Valuations
In this section we discuss whether it is possible for an online algorithm to be c * (P)-competitive without any information (before or after, deterministic or distributional) on the valuations.
First we show that this is impossible for any online algorithm which price-skims independently, i.e. realizes its random price at each time step using an independent source of random bits.
Proposition 1. Suppose that either: (i) m ≥ 2 and valuations can be 0 (as usual); or (ii) m ≥ 3 and valuations cannot be 0. (Recall that m is the number of prices.) Then for any online algorithm where each P t chosen independently based on the sales history X 1 , . . . , X t−1 , there exists a sequence Proof of Proposition 1. Let the starting inventory k = 1.
First, it is easy to see that if the distribution of P 1 is not such that Pr[P 1 = r (j) ] = q (j) q for all j ∈ [m], then for some deterministic instance consisting of a single valuation in {r (1) , . . . , r (m) },
However, we show that it is possible to be c * (P)-competitive if the online algorithm can priceskim in a "coordinated" fashion, with the same probabilities as in Eren and Maglaras (2010).
Proposition 2. Consider the following random-fixed-price policy: 1. Initially, choose a random price P which is equal to each r (j) with probability q (j) /q; 2. Offer price P as long as there is remaining inventory.
This policy is c * (P)-competitive.
Proof of Proposition 2. Consider any realization of the valuations, V 1 , . . . , V T . Iteratively define the following quantities, for j from m down to 1: Essentially, for each j, n (j) denotes the number of valuations equal to r (j) that should be picked out when picking out the min{k, T } largest valuations. OPT is then equal to m j=1 r (j) n (j) .

Now consider the execution of the policy on this instance. For all j ∈ [m], if the random fixed
price P is equal to r (j) , then the number of sales will be equal to min{ T t=1 ½(V t ≥ r (j) ), k}, which by definition is equal to m j ′ =j n (j ′ ) . Therefore, which equals 1 q OPT, completing the proof that the random fixed price is c * (P)-competitive.
It is known that correlated randomness is very powerful in the design of online algorithms (see, e.g., Karp et al. (1990), who derive an extremely elegant solution to the online matching problem using correlated randomness). Indeed, we can use our policy from Proposition 2 under our previous models with more information on the valuations and still have a c * (P)-competitive algorithm.
However, this is impractical for several reasons. First, the fact that the random price must be fixed makes it impossible to make use of additional information that may be available on the valuations (this issue was also raised in Eren and Maglaras (2010)). Second, the random-fixed-price policy does not show how the price should evolve as inventory is depleted, and does not satisfy the intuitive structural property in dynamic pricing that the price is greater if the remaining inventory is less (see Section 2.4). In Section 5, we show how our algorithms from Sections 2-3 can be adapted into the setting where the personal information of each customer can be used in determining her price.

Personalization Revenue Management Model
In this section we consider the personalized online revenue management setup introduced by Golrezaei et al. (2014), where: • the stochastic decision of each customer can be modeled accurately upon her arrival to the e-commerce platform (by using her characteristics); • however, the overall intensity and characteristics of customers to arrive over time is difficult to model (and treated as unknown/arbitrary).
In our model, this would correspond to the stochastic-valuation model in Section 3, with the change that the distribution of each V t is given before the algorithm has to set a price, instead of after.
The algorithms from Section 3 can still be applied, and will be c * (P)-competitive. Furthermore, it is not possible to be better than c * (P)-competitive even with this personalized information, as discussed in Section 1.1.
Nonetheless, in this section we specify how our online algorithms can exploit personalized information to strictly improve their decisions, while remaining c * (P)-competitive. Take any c * (P)competitive algorithm A for the stochastic-valuation model (e.g. the algorithm from Section 3.2, or a modification following Section 2.4 which never rejects customers before stocking out). For each time step t and inventory level k ′ > 0 such that Pr[I A t−1 = k ′ ] > 0, consider the distribution for the price P t chosen by algorithm A conditioned on I A t−1 = k ′ (this depends on the previously-observed valuation distributions v 1 , . . . , v t−1 ). Since now we also know the distribution v t of valuation V t , we can compute the probability of algorithm A making a sale during time t, as well as its expected revenue, We can interpret (21) as the reward given to the algorithm during time t in exchange for the probability (20) of consuming inventory. The price distribution used by the algorithm to obtain such an exchange was chosen without knowing the distribution of V t . However, since now we do know the distribution of V t , we can potentially make a decision which achieves more expected reward under the same consumption probability. Specifically, we solve the following LP: represents the probability that we should offer price j at time t, conditioned on the remaining inventory being k ′ . We know that setting each p j (t, k ′ ) = Pr[P A t = r (j) |I A t−1 = k ′ ] is a feasible solution, and hence the optimal objective value of the optimization problem is at least (21). Let {p * j (t, k ′ ) : j = 1, . . . , m} denote an optimal solution to the optimization problem, for all t and k ′ .
Proposition 3. Consider the online algorithm which, at each time step t, sets the price randomly according to probabilities {p * j (t, k ′ ) : j = 1, . . . , m}, where k ′ is the remaining inventory at the start of time t. Then for any sequence of valuation distributions v 1 , . . . , v T , the algorithm's total expected revenue is at least Proposition 3 is established in the same way as Theorems 2 and 4-for t = 1, . . . , T , we can inductively ensure from constraint (22) that the distribution for the starting inventory level matches that of A. Since the algorithm has the same distribution for inventory state at each time t and earns at least as much revenue as A in expectation on every inventory state, its total revenue must be at least the offline optimum (and in fact is often much better since it exploits personalization).

Conclusion
In this paper we have provided a general solution to the single-leg revenue management problem which yields the best-possible competitive ratio with limited demand information. Our policies unify the inventory-dependent booking policies in Ball and Queyranne (2009) with the random price-skimming policies in Eren and Maglaras (2010). An important feature of our policies is that they show at each time step how the price distribution should depend on inventory when the future is unknown, complementing classical results which show how the optimal price should depend on inventory when the future is known. Our policies were derived using a new "valuation tracking" technique, which geometrically tracks the optimum and hedges against the arrival sequence immediately ending in the most inventory-conservative fashion. We believe this to be of general interest for competitive ratio analysis.
Finally, we explain why our analysis of the pricing case, where each customer has a valuation and chooses the lowest fare not exceeding it, captures all rational choice models. Suppose instead that the firm could offer an assortment of fare classes, and that each customer has a ranked list of fare classes she is willing to purchase, and chooses the highest-ranked fare class that is offered to her. We can define V t to be the maximum fare in the list that customer t is willing to purchase, and then the offline optimum would still be the k largest values from V 1 , . . . , V T . Meanwhile, we can modify the online algorithm so that whenever it would have offered price P t , it now shows all fares greater than or equal to P t . This algorithm would still make a sale whenever V t ≥ P t , except now it has the opportunity to earn revenue greater than P t , if customer t does not choose the lowest offered fare. As a result, our c * (P)-competitive algorithms under the pricing model imply corresponding c * (P)-competitive algorithms under the assortment model.
Nevertheless, we would like to end on two open questions related to the assortment generalization.
First, our argument above assumes rational choice models; however in practice certain fare classes could be designed as "decoys" for other fare classes. Second, our algorithms imply an "assortmentskimming" distribution over revenue-ordered assortments, but this assumes there is no limit on the number of fare classes offered. We believe that assortment skimming under cardinality constraints is an interesting problem. ec1

E-Companion
Appendix A: Full Proof of Theorem 1 Definition EC.1. Define the following: • S i,t : the indicator random variable for whether inventory unit i is sold by the end of time t, i.e. the value of sold[i] at the end of time t, defined for all i ∈ [k] and t = 0, . . . , T ; • i t : the inventory unit assigned to customer t, taking a value in [k] for all t ∈ [T ]; • ℓ i,t : the value such that level[i] = r (ℓ i,t ) at the end of time t, taking a value in {0, 1, . . . , m} for all i ∈ [k] and t = 0, . . . , T ; • j t : the value in {0, 1, . . . , m} such that V t = r (j t ) , defined for all t ∈ [T ].
Fix the deterministic sequence of valuations V 1 , . . . , V T chosen by the adversary. i t , ℓ i,t , and j t are not random variables; they are determined by V 1 , . . . , V T .
We would like to write the random variables S i,t in terms of the other random variables. By definition, S i,0 = 0 for all i ∈ [k]. For t > 0, the following equations hold: (EC.1)-(EC.2) are easy to see. In the algorithm, the only inventory unit that could potentially be sold during time t is i t . This explains why (EC.2) holds for all i = i t . It also explains why S i t ,t = 1 if and only if S i t ,t−1 = 1 or X t = 1. Furthermore, S i t ,t−1 and X t cannot both be 1, since the algorithm does not try to sell inventory unit i t again at time t if it has already been sold. This completes the explanation for (EC.1).
We now analyze the state of the sold array during the execution of the algorithm.
Lemma EC.1. At the end of each time step t, the probability that any inventory unit i has been sold is 1 q ℓ i,t j=1 q (j) . Formally, for all t = 0, . . . , T ,  It remains prove E[S i t ,t ] = 1 q ℓ i t ,t j=1 q (j) . This is immediate if j t is no greater than ℓ i t ,t−1 (the value of the ℓ variable during iteration t of the algorithm), since both S i,t and ℓ i,t would be unchanged.
If j t > ℓ i t ,t−1 , the following can be derived (let ℓ = ℓ i t ,t−1 for brevity): The first equality follows from (EC.1) and the linearity of expectation. The second equality conditions on S i t ,t−1 being 0, since the value of X t is 0 if S i t ,t−1 = 1. The third equality uses the value of This completes the induction and the proof of the lemma. Now we analyze the expected revenue of the algorithm, which is E[ALG], or T t=1 E[P t X t ]. As argued earlier, there cannot be a sale in a time step t where j t ≤ ℓ i t ,t−1 , so for these time steps X t = 0 and E[P t X t ] = 0. The following lemma derives the value of E[P t X t ] when j t > ℓ i t ,t−1 .
Lemma EC.2. Suppose j t > ℓ i t ,t−1 in a time step t ∈ [T ]. Then the expected revenue earned by the algorithm during time step t is 1 q (r (j t ) − r (ℓ i t ,t−1 ) ).
Proof. Let t ∈ [T ] be any time step for which j t > ℓ i t ,t−1 . For brevity, let ℓ denote ℓ i t ,t−1 . The following can be derived: e-companion to Ma, Simchi-Levi, and Teo: Single-leg RM with Limited Demand Information The first equality conditions on S i t ,t−1 being 0; note that X t = 0 if S i t ,t−1 = 1. The second equality conditions on the value of P t , where we drop the conditioning on S i t ,t−1 in the term E[X t |P t = r (j) ] since P t = ∞ already implies S i t ,t−1 = 0. This term becomes ½[j t ≥ j] in the third equality, since it is deterministically 1 or 0 depending on whether V t ≥ r (j) , or equivalently j t ≥ j. The third equality also uses Lemma EC.1, for the value of Pr[S i t ,t−1 = 1]. The fourth equality uses the offering probabilities from line 7 of Algorithm 1. The fifth equality uses the explicit definition of q (j) from Definition 1, and it is easy to see that the final expression is equal to 1 q (r (j t ) − r (ℓ) ). Lemma EC.2 in turn implies the following lemma.
Lemma EC.3. The expected revenue earned by the algorithm up to time t, Proof. The customers up to time t can be partitioned according to the inventory unit they were assigned, so Before time t ′ n , level[i] was last updated at time t ′ n−1 , so ℓ i,t ′ n −1 = j t ′ n−1 . Therefore, the sum telescopes and the remaining term is 1 q r ) completes the proof. Having established the revenue of our online algorithm, we compare it to the offline optimum.
Knowing the sequence of valuations V 1 , . . . , V T in advance, it is clear that the following algorithm is optimal: 1. Find the min{k, T } customers with the largest valuations; 2. Charge each of these customers t her maximum willingness-to-pay V t ; 3. Reject all other customers.
The revenue OPT would be the the sum of the min{k, T } largest valuations.
Definition EC.2. For all t ∈ [T ], let M k (t) be a vector consisting of the k largest elements from (V 1 , . . . , V t ), in any order. If t < k, fill in the remaining entries of M k (t) with zeros. ec4 e-companion to Ma, Simchi-Levi, and Teo: Single-leg RM with Limited Demand Information where M k i (T ) denotes the i'th entry of M k (T ). It turns out that M k (t) is closely tracked by the level array from Algorithm 1, as t progresses from 1 to T . Both ℓ i,t (the value of level[i] at the end of time t) and M k (t) are deterministic functions of V 1 , . . . , V t .
With Lemma EC.3 and Lemma EC.4, it is easy to establish the competitiveness of Algorithm 1.
Our online algorithm is designed so that during each time step t, it earns exactly 1 q of the amount that the offline optimum would increase by with the addition of V t , and it does not need to observe V t beforehand to accomplish this.
Proof of Theorem 1. Fix any sequence of valuations (V 1 , . . . , , and the entries of M k (T ) is a permutation of the entries of (r (ℓ 1,T ) , . . . , r (ℓ k,T ) ), by Lemma EC.4. Therefore, OPT = k i=1 r (ℓ i,T ) = q · E[ALG], completing the proof of Theorem 1.  note that the assignment procedure in Algorithm 1 is deterministic. Therefore, each S i ′ ,t−1 is only dependent on the prices chosen for the customers assigned to i ′ , and while these prices could be dependent on each other, they are independent from the prices chosen for customers not assigned is simply the sum of k − 1 independent Bernoulli random variables with known mean (from Lemma EC.1), hence the probability that it equals a specific value can be computed using dynamic programming.
We elaborate on the dynamic programming. For notational convenience, without loss of generality assume i = k. We will inductively for a = 0, . . . , k − 1 maintain the value of Pr[ Proof of Lemma 2 and Theorem 2. We argue that Lemma 2 and Theorem 2 are the special cases of Lemma 4 and Theorem 4 from the stochastic-valuation model. It is easy to check that the statements are analogous, so it suffices to show that Exp (as defined in Section 3.2) executed on deterministic valuations is identical to Algorithm 1' (as defined in Section 2.3).
We show that the decision rule for a single time period t, and any amount of inventory remaining k ′ , is the same. Let i = i * t and ℓ = ℓ t , for brevity. Consider the values of i and ℓ during iteration t of Algorithm 1 (with the deterministic valuations V 1 , . . . , V T ). First consider any j = ℓ + 1, . . . , m.
e-companion to Ma, Simchi-Levi, and Teo: Single-leg RM with Limited Demand Information The first equality holds by the specification of algorithm Algorithm 1'. The second equality holds by the specification of Algorithm 1, where we can add the conditioning on I A1 t−1 = k ′ in the second probability due to independence. The final equality follows because P A1 t = r (j) = ∞ implies S i,t−1 = 0.
If j = m + 1, then since the event S i,t−1 = 1 occurs if and only if the event P A1 t = ∞ occurs.
. . , m, m+1}, so it is the same decision rule as Exp, completing the proof.
Proof of Lemma 3. Fix a valuation sequence V 1 , . . . , V T and consider any sample path in the execution of A; let the sample path be depicted by the sequence of random prices P A 1 , . . . , P A T . The revenue ALG A on that sample path is given by t:V t ≥P A t P A t ; note that the cardinality of the set {t : V t ≥ P A t } is at most k. On that same sample path, the modified algorithm A ′ would sell to the k customers with the smallest indices in {t : V t ≥ min{P A t , r (m) }} (or all the customers in that set if its cardinality is less than k). Let S denote the set of customers served by the modified algorithm. Let b = |{t ∈ S : P A t = ∞}|, the number of customers with valuation r (j) served by the modified algorithm that were rejected by the original algorithm.
It is easy to see that where S ′ is the set of customers that are no longer served by A ′ because it used up b extra units of inventory. Since |S ′ | ≤ b, and P A t ≤ r (m) for all t such that P A t ≤ V t , it is immediate that (EC.6) is non-negative. Since this holds on every sample path for A, we have completed the proof that

Proof of Theorem 3 The inventory level
(1 − S i,t−1 ), where S i,t−1 is the indicator random variable for inventory unit i being sold by the end of time t − 1. We will hereafter omit the subscript t − 1.
Each term (1 − S i ) is independent and equal to 1 with probability ( m j=b i +1 )q (j) /q, which is the probability that inventory unit i has not been sold. We will denote it using p i and let Y i = 1 − S i , e-companion to Ma, Simchi-Levi, and Teo: Single-leg RM with Limited Demand Information ec7 for brevity. As long as b i (the index in 0, . . . , m of the highest valuation assigned to inventory unit i) is not 0 or m, p i ∈ (0, 1). We will without loss of generality assume that p i ∈ (0, 1) for all i, redefining k and re-indexing as necessary (if p i = 0 or p i = 1 then Y i is deterministic and we can remove it from analysis of the random sum). By the assumptions in the statement of the theorem, this re-indexing does not cause i * t to fall outside of 1, . . . , k; in fact we can without loss of generality assume i * t = 1. Furthermore, k 1 , k 2 are at least 0 at at most the re-defined k, since they correspond to inventory levels that are realized with non-zero probability.
After all of these transformations, the statement reduces to where each Y i is an independent Bernoulli random variable of probability p i ∈ (0, 1) and 0 ≤ k 1 < k 2 ≤ k. Furthermore, we can without loss of generality assume that k 2 = k 1 + 1.
If k 1 = 0, then (EC.7) is clearly true, since the LHS is 0 while the RHS is non-zero. So assume that k 1 > 0 and we can rewrite (EC.7) as follows: Therefore, it suffices to prove that: After expanding, both sides are a sum of terms of the form where each a i is 0, 1, or 2 and the sum k i=2 a i equals 2k 1 , the total number of times that a "positive" term p i (as opposed to a "negative" term (1 − p i )) appears in the product. Let b denote the total number of i = 2, . . . , k such that a i = 1, which must be even. Now, observe that the total number of times the term (EC.9) appears in the LHS of the expansion of (EC.8) is b b/2 (because we choose b/2 of the b indices that are "positive" to come from the first bracket; the remaining b/2 must come from the second bracket) while the total number of times this term appears in the RHS is b b/2+1 (because we choose b/2 + 1 of the b indices that are "positive" to come from the first bracket), with the latter being strictly less. Furthermore, none of these terms are 0, since all of the values of p i lie strictly between 0 and 1. Therefore, the inequality is strict, completing the proof of the theorem.

Appendix C: Proofs from Section 3
Proof of Lemma 4. We proceed by induction on t. (7) is true for t = 0, since Pr[I Exp Now suppose t > 0 and that (7)  We now consider (7) for time t. Note that I Exp Now, for any k ′ ∈ {0, . . . , k}, if Pr[I Exp t−1 = k ′ ] > 0, then the following can be derived: e-companion to Ma, Simchi-Levi, and Teo: Single-leg RM with Limited Demand Information In the second equality, we remove the conditioning on I Exp t−1 = k ′ , since the valuation V t is an independent random variable unaffected by any history. The third equality follows because we have already established (6) for time t. The final equality also requires independence.
By the inductive hypothesis that (7) holds for time t − 1, Pr[I Exp is also non-zero, then the following can be derived using (EC.12): = 0, and therefore, (EC.13) still holds.

Pr[I Exp
Proof of Theorem 4. The following is straight-forward to derive: and g t ∈ G t . This is clearly true for t = 0. For t > 0, take any g t ∈ G t , and we can write We will prove that Pr[G Samp  are IID and none of the conditioning has any effect.
Having established this, note that for every t ∈ [T +1] and h t ∈ F t there exists a unique g t−1 ∈ G t−1 such that g t−1 is a prefix of h t . We know that for this Proof of Theorem 5. Applying Lemma 7 to (15), we see that The statement about runtime also follows easily from the specification of Algorithm 2 since the number of sample runs during each time period t, ⌈ 6 eπ 2 ε ⌉(k + 1)t 2 , is polynomial in 1 ε . ec12 e-companion to Ma, Simchi-Levi, and Teo: Single-leg RM with Limited Demand Information Algorithm 3: Weakly Randomized Online Algorithm for Continuum of Prices Input: Customers t = 1, 2, . . . arriving online, with each valuation V t revealed after the price P t is chosen. Output: For each customer t, a (possibly random) price P t for her. To analyze the competitiveness of Algorithm 3, we prove lemmas analogous to Lemmas EC.1-EC.2. We use the same notation as in Definition EC.1, except instead of ℓ i,t and j t , we use v i,t to denote the value of val[i] at the end of time t, taking a value in 0 ∪ [1, R].
Lemma EC.5. At the end of each time step t, the probability that any inventory unit i has been sold is 0 if v i,t = 0, and 1+ln R . This is immediate if V t ≤ v i t ,t−1 , by the induction hypothesis. Otherwise, if V t > v i t ,t−1 , we consider two cases. Let v = v i t ,t−1 for brevity.
If v = 0, then this equals This completes the induction and the proof of the lemma.
Lemma EC.6. Suppose V t = v i t ,t > v i t ,t−1 in a time step t ∈ [T ]. Then the expected revenue earned by the algorithm during time step t is 1 1+ln R (v i t ,t − v i t ,t−1 ).
Proof. Let t ∈ [T ] be any time step for which V t > v i t ,t−1 . Again, let v denote ℓ i t ,t−1 , and we consider the two cases v = 0 and v > 0. If v = 0, then E[P t X t ] = 1 1 + ln R In the first equality, a sale is guaranteed if P t = 1, earning revenue 1. The final term is the desired expression.
If v > 0, then as desired.
With these two lemmas, the rest of the proof follows Section A. Indeed, Lemma EC.3 says OPT ≥ 1 1+ln R , and since V 1 , . . . , V T was arbitrary, Algorithm 3 is 1 1+ln R -competitive.
Appendix E: Upper Bounds on the Competitive Ratio relative to the DLP First, it is well-known that the DLP overestimates the optimum by a factor of 1 − 1 e , even when the feasible price set P consists of a singleton (i.e. the dynamic pricing problem is trivial because there is only one price to choose from). The example requires the starting inventory k to be 1. Without loss of generality assume P = {1}. Consider T customers, each of whom have a valuation exceeding 1 with probability 1 T , and a valuation of 0 otherwise. It is easy to check that OPT LP = 1 in this case, by setting x If r ≤ 1 1−1/e , then the RHS of (EC.16) is equal to 1 − 1 e ≈ .632. However, if r > 1 1−1/e , then we show that the upper bound is r−r/e 2r−1−r/e , which decreases to e−1 2e−1 ≈ .387 as r → ∞.
We explain (EC.17). If the online algorithm decides to wait, then it will offer price r to all customers beyond the first. It gets a sale if v 2 = . . . = v T = (1 − 1 T −1 , 0, 1 T −1 ), which occurs with probability p = 1 r(1−1/e) , and further if at least 1 of the valuations V 2 , . . . , V T realizes to r, which yields the second term in (EC.17).