{'fraction_non_alphanumeric': 0.04282843506656619, 'fraction_numerical': 0.006468224064305451, 'mean_word_length': 4.19406392694064, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Assortment Optimization with Repeated Exposures and Product-dependent Patience Cost

In this paper, we study the assortment optimization problem faced by many online retailers such as Amazon. We develop a \emph{cascade multinomial logit model}, based on the classic multinomial logit model, to capture the consumers' purchasing behavior across multiple stages. Different from existing studies, our model allows for repeated exposures of a product, i.e., the same product can be displayed multiple times across different stages. In addition, each consumer has a \emph{patience budget} that is sampled from a known distribution and each product is associated with a \emph{patience cost}, which captures the cognitive efforts spent on browsing that product. Given an assortment of products, a consumer sequentially browses them stage by stage. After browsing all products in one stage, if the utility of a product exceeds the utility of the outside option, the consumer proceeds to purchase the product and leave the platform. Otherwise, if the patience cost of all products browsed up to that point is no larger than her patience budget, she continues to view the next stage. We propose an approximation solution to this problem.


Introduction
In this paper, we consider the sequential assortment optimization problem with repeated exposures and product-dependent patience cost. The input of our problem is a set of products and a limited number of stages, each stage has a limited capacity, our goal is to find the best assignment of products to stages that maximizes the expected revenue. We develop a variant of multinomial logit model, called cascade multinomial logit model (C-MNL), to capture the consumer's purchasing behavior across multiple stages. In our model, each consumer has a patience budget which is drawn from a known distribution, and each product is associated with a patience cost that quantifies the cognitive efforts spent on browsing a product. In each stage, the consumer browses all products displayed in that stage, if the utility of some product is larger than the no-purchase option, then she purchases the one with the largest utility and leaves the system. Otherwise, the consumer continues to enter the next stage if and only if her current patience budget is non-negative. Our model generalizes the previous studies on sequential assortment optimization in two ways: 1. Our model allows for repeated exposures, i.e., the same product can be displayed multiple times across different stages. In the filed of marketing, it has been well recognized that a consumer typically must be exposed to an advertisement or a message more than once in order to get familiar with it and take actions. From a consumer cognition perspective, we believe that assortment planning is similar to online advertising in that they both push a set of products' information to the consumer. We develop a rigorous mathematical model to capture the effect of repeated exposures.
2. We assign a product-dependent patience cost to each product. The patience cost of a product quantifies the amount of efforts needed to read and digest the information about that product. Most of existing studies [1] assign a fixed and identical patience cost to each stage, e.g., they assume that the patience cost of browsing all products in one stage does not depend on the offered products in that stage. In contrast, our model allows different products to have different patience cost, and the patience cost of viewing one stage is characterized by the summation of the individual patience costs of all products allocated to that stage. Our model is motivated by the observation that browsing different products may require different amount of cognitive efforts.
3. Our problem formulation incorporates a set of practical constraints. For example, there is a constraint on the number of products displayed in each stage, and there is also a limit on the maximum number of exposures of a product. We develop an approximation algorithm with polynomial time complexity when the number of stages is a constant. An interesting research direction is to design an efficient algorithm whose running time is polynomial in the number of stages.
Related Works. Our work is closely related to the assortment optimization problems [2,3,4,5,6]. Among existing studies on assortment optimization, [7] and [8] were the first to study this problem under MNL model with position bias. Since then, there is considerable number of studies [9,10,11] on assortment optimization problem with position bias. However, most of them adopt the consider-then-choose model where the consumer first browses a random number of products and then makes her purchase decision within these products. Our model differs from theirs in that we do not separate "consider" from "choose", e.g., the list of products browsed by a consumer is jointly decided by her patience budget and the choice model. We build our study on the recent advances of sequential assortment optimization [1]. As mentioned earlier in this section, our model generalizes the previous studies by allowing for repeated exposures and product-dependent patience cost. In addition, our problem formulation incorporates a set of practical constraints.

Cascade Multinomial Logit Model and Problem Formulation
In the rest of this paper, we use [i] to denote the set {1, · · · , i} for any positive integer i.
Cascade Multinomial Logit Model. We first explain the idea of C-MNL. Assume there is a set of n products [n] and a set of m stages [m]. The capacity of each stage is d, e.g., we can assign at most d products to each stage. Each product can be displayed in at most w stages and the same product can be displayed at most once in each stage.
The utility U i,k of the k-th exposure of product i ∈ [n] is a random value drawn from the Gumbel distribution with location-scale parameters (µ i,k , 1). The utility of the nopurchase option, denoted by U 0 , is a random value drawn from the Gumbel distribution with location-scale parameters (0, 1). The patience budget of a consumer is given by the random variable B. Let F (q) denote the probability that B ≥ q. Each product i ∈ [n] is associated with a patience cost c i : Browsing a product i ∈ [n] consumes the consumer c i amount of patience budget. In addition, let r i denote the revenue of product i ∈ [n]: The platform earns revenue r i if the consumer purchases i. We made two innocuous assumptions in this paper. Assumption 1. For any two non-negative numbers q 1 ≥ 0 and q 2 ≥ 0, F (q 2 ) ≥ This assumption states that the patience budget of a customer declines rapidly as she browses more stages. We believe that as more stages browsed without a purchase, it is more likely that the customer will run out of her patience budget sooner.
This assumption states that the expected utility of a product reaches its maximum point at the first exposure and then declines with each additional exposure. This is called burnout effect in the field of online advertising [12]. In the context of assortment optimization, because the platform still pushes the product to a customer, we expect a similar repetition effect: the probability of purchasing a product declines with each additional exposure of that product. In our choice model, an arriving customer sequentially browses the assortments in each stage. In each stage, if the largest utility for a product is larger than the nopurchase option, she purchases it and leaves the systems. Otherwise, if her remained patience budget is non-negative, she enters the next stage, otherwise, she leaves the system.
. We say an assortment x is feasible if and only if it satisfies the following two conditions: (1) x i,s,z s. The first condition ensures that each product is displayed at most once in each stage, and the second condition ensures that the resulting assortment is implementable, e.g., the (q+1)-th exposure of a product can only be displayed after the first q exposures of that product have been displayed.
Problem Formulation. Before introducing our problem, we first present a closed form expression of choice probabilities. Lemma 1. Let X denote the set of all feasible assortments, if we offer x ∈ X , then the The proof of the above lemma is similar to the proof of Theorem 2.1 in [1], thus omitted here to save space.
We next derive the expected revenue f (x) of any feasible assortment x ∈ X .
This lemma follows immediately from Lemma 1 and the fact that the revenue of product i ∈ [n] is r i . For simplicity of notation, we use β i,k to denote e µ i,k in the rest of this paper. Now we are ready to introduce the assortment optimization problem with repeated exposures and product-dependent patience cost. The objective of our problem P.0 is to find the best feasible assortment that maximizes the expected revenue. A formal definition of our problem is listed as follows.

Technical Lemma
In this section, we will present one technical lemma that will be used in our latter algorithm design and analysis. For ease of presentation, we first introduce the concept of reachability. Given a solution, we define the reachability of a stage or a product as the probability that the customer has enough patience to browse that stage or that product. A formal definition of reachability is provided in Definition 1.
We next provide an important observation about the optimal solution x opt , which we will use to design our solution.
such that the reachability of all products under y is at least ρ.
Proof: Assume t ρ is the last stage in x opt whose reachability is no smaller than ρ, e.g., We next construct two assortments based on x opt : The first assortment, denoted by x opt ≤tρ , is constructed by removing all products displayed after t ρ from the optimal solution. The second assortment, denoted by x opt >tρ , is constructed by removing all products scheduled earlier than t ρ from the optimal solution and moving the rest of products t ρ stages ahead. It is easy to verify that the reachability of every product in the first assortment is no smaller than ρ.
We first show that We first derive the expected revenue of the optimal solution x opt .
We next analyze the expected revenue of x opt >tρ . For ease of presentation, let σ i denote the number of exposures of product i in the optimal solution before stage t ρ . For To prove inequality 1, it suffice to prove that the value of (3) is upper bounded by ρ times the value of (5). We next prove a stronger result, that is, for every t ∈ [t ρ + 1, m]: We first prove that the denominator of LHS of (7) is no smaller than the denominator of RHS of (7). This is true because β i,k−σi x opt i,k,z . We next focus on proving that The second inequality is due to F ( This finishes the proof of (7), which implies (1), that is, . Now we are ready to prove this lemma. Because x opt is the optimal solution, we have f (x opt >tρ ) ≤ f (x opt ). Together with (1), . According to the definition of x opt ≤tρ , the reachability of all products in x opt ≤tρ is at least ρ. Thus, x opt ≤tρ is such a solution y that satisfies f (y) ≥ (1 − ρ)f (x opt ).

Approximate Solution
In this section, we develop an approximate solution to our problem. For ease of presentation, given any x ∈ X , define Note that g(x) is the utility of x when the reachability of all stages are 1, e.g., this happens when the patience budget of the consumer is always infinity. Before presenting our algorithm, we first introduce a new problem P.1 whose solution is a key ingredient of algorithm.

P.1 Maximizex∈X g(x)
subject to: The objective of P.1 is to identify the best feasible assortment x that maximizes g(x) subject to (C1). The condition (C1) ensures that the reachability of all non-empty stages must be no smaller than ρ. As compared with the original problem P.0, we move the variables of patience cost from the objective function to the constraint (C1), which makes P.1 easier to tackle.
Given the formulation of P.1, we are now ready to present our algorithm, called assortment optimization under cascade multinomial logit model (ACME), for finding an approximate solution to P.0.
Description of ACME. 3. Return the better solution between x ′ and x ′′ as the final solution.
We first discuss the second step of ACME. It was worth noting that when there is only one stage, e.g, m = 1, P.0 is reduced to the classic assortment optimization problem subject to a cardinality constraint. We can solve it optimally based on [13] and obtain x ′′ . We next present the main theorem of this paper. It says that if we can find an approximation algorithm for P.1, we can solve P.0 approximately.
Proof: Recall that t ρ is the last stage in x opt whose reachability is no smaller than ρ, e.g., t ρ = arg max t∈[m] F ( . Let x opt <tρ denote a "sub" schedule of x opt , removing all products Inequality 11 is due to f (x opt <tρ ) ≤ g(x opt <tρ ), and F ( x opt i,k,z c i ) ≤ 1. Inequality 12 is due to x opt ≤tρ is a feasible solution to P.1 and x * is the optimal solution to P.1. Inequality 13 is due to β i,1 ≥ β i,k for all i ∈ [n] and k ∈ [w], and β i,1 x opt i,k,tρ . Inequality 14 is due to x ′′ is the optimal solution to the assortment optimization problem with a single stage.
Assume g(x ′ ) ≥ κg(x * ), based on inequality 14, we have f (x opt ≤tρ ) ≤ g(x ′ )/κ + f (x ′′ ). Because the reachability of all stages under x ′ is lower bounded by ρ, we Because ACME picks the better one between x ′ and x ′′ as the final solution, this theorem holds.
In the rest of this paper, we introduce a 1−ǫ(1+ǫ) (1+ǫ(1+ǫ)) 2 -approximate solution to P.1 based on dynamic program. We build our solution on the recent advances in the assortment optimization problem subject to one capacity constraint [14], we generalize their idea and provide an approximate algorithm for the assortment optimization problem subject to a capacity constraint, a cardinality constraint, and a matroid-type feasibility constraint.

A Dynamic Program based Solution to P.1
We first introduce some notations. Let α min = min i∈Ω r i be the minimum revenue of a single product and let α max = max i∈[n] r i be the maximum revenue of a single product. Define β min = min i∈[n],k∈[w] β i,k and β max = max i∈[n],k∈[w] β i,k . Let For a given ǫ > 0, we first construct a geometric grid I × J where I and J are defined as follows.    Proof: Our proof is based on the following two observations. First, the total number |I| · |J| of guesses is bounded by = O(ln dγmax ǫγmin ln dβmax ǫβmin ). Second, the size of u and v is bounded by d × ⌈d/ǫ⌉ ≤ d(d/ǫ + 1). Third, the time complexity of computing h(j, u, v, l) is is O(m w ), e.g., this is done by enumerating all possible y j .
It follows that the total time complexity of the dynamic program is O(m w (d(d/ǫ + 1)) m ln dγmax ǫγmin ln dβmax ǫβmin ).
Lemma 5. Let x * denote the optimal solution to P.1. For any ǫ > 0, i,k,z = 0, e.g., the optimal solution x * only utilizes the first m * stages. Assume for all z ∈ [m * ], γ min (1+ǫ Recall that the dynamic program enumerates all guesses in I m × J m . Consider the case x * i,k,z denote the summation of the scaled values of the optimal solution. It is clear that h(n, u * , v * , l * ) ≤ ρ.
Recall that we use x ′ to denote the solution returned from the dynamic program.
We first give a lower bound on where the second inequality is due to the assumption that γ min (1+ǫ) az ≤ n i=1 γ i,k,z x * i,k,z and the last inequality is due toγ i,k,z ≥ γ i,k γmin(1+ǫ) az +1 ǫ/d for all i ∈ [n].

Conclusion
In this work, we have considered the assortment optimization problem across multiple stages. Our model allows for both repeated exposures and product-dependent patience cost. We develop an approximation algorithm to this problem whose running time increases exponential with the number of stages. It would be useful to develop effective algorithms when the number of stages is large.