Assortment management under the generalized attraction model with a capacity constraint

Abstract

We consider an assortment optimization problem where a retailer chooses a set of substitutable products to maximize the total expected revenue or profit subject to a capacity constraint. The customer purchase behavior follows the generalized attraction model (GAM), of which the multinomial logit model and the independent demand model are special cases. We visualize the efficient assortments and propose a nonrecursive polynomial-time algorithm to find the optimal one for the static problem. We then connect it with the concept of efficient set in the context of revenue management and show that the efficient sets, the only candidates for the optimal assortments under the capacitated GAM formulation, are of polynomial size. Moreover, the efficient sets significantly reduce the computational complexity in the dynamic assortment management and the optimal policy has a time-threshold structure.

APPENDIX

Proofs

Proof of Proposition 1: Similar to Rusmevichientong et al (2010) in the MNL model, we compare R(S _C ^l) with R(S _C ^l+1) in the GAM formulation. From the above analysis, S _C ^l+1=S _C ^l{i _l }∪{j _l } or S _C ^l+1=S _C ^l\{i _l }. First, consider S _C ^l+1=S _C ^l{i _l }∪{j _l }. Denote X=S _C ^l{i _l } for notational convenience. Then, S _C ^l=X∪{i _l }, S _C ^l+1=X∪{j _l }, and we have

The third equality holds because and

Second, consider the case S _C ^l+1=S _C ^l{i _l }. Then, S _C ^l=X∪{i _l }, S _C ^l+1=X and is the x-coordinate of the intersection between and the x-axis h₀(γ)=0.

The last equality holds because

Because is increasing in l and is decreasing, denote Thus, we can see that R(S _C ^l) is increasing in l for l<l^* and is decreasing in l for l⩾l^* since from our analysis.

The uni-modality of Q(S _C ^l) is very simple as it is a special case of R(S _C ^l) with p _i =1 for each i∈M. We next prove the monotonicity of Q(S _C ^l) under the parsimonious GAM formulation. For the case S _C ^l+1=S _C ^l{i _l }∪{j _l },

In the parsimonious formulation, ṽ _i =(v _i )/(1+∑_k=1^mw _k )=(v _i )/(1+θ∑_k=1^mv _k ), w̃ _i =(v _i −w _i )/(1+∑_k=1^mw _k )=((1−θ)v _i )/(1+θ∑_k=1^mv _k ) and (ṽ _il w̃ _jl −ṽ _jl w̃ _il )/(w̃ _jl −w̃ _il )=0. Then,

The inequality holds because that is equivalent to that in the parsimonious GAM formulation.

For the case S _C ^l+1=S _C ^l/{i _l },

The second equality holds because for any k∈X in the parsimonious GAM formulation. □

Proof of Lemma 1: It is apparent that R̄(q) is increasing in q. For 0⩽q, q′⩽1 and 0⩽β⩽1, suppose that the corresponding probabilities are α(S, q) and α(S, q′) such that R̄(q)=∑_∣S∣⩽Cα(S, q)R(S), ∑_∣S∣⩽Cα(S, q)Q(S)⩽q, ∑_∣S∣⩽Cα(S, q)=1, α(S, q)⩾0; and R̄(q′)=∑_∣S∣⩽Cα(S, q′)R(S), ∑_∣S∣⩽Cα(S, q′)Q(S)⩽q′, ∑_∣S∣⩽Cα(S, q′)=1, α(S, q′)⩾0. Define new probabilities as follows: α(S, βq+(1−β)q′)=βα(S, q)+(1−β)α(S, q′). It is straightforward to verify that

By the definition of R̄(·),

So, R̄(q) is concave in q. □

Proof of Proposition 2: Similar to Talluri and van Ryzin (2004) without a capacity constraint, suppose T is an optimal solution to problem (4), then R(T)−μQ(T)⩾R(S)−μQ(S) for all S⊆M and ∣S∣⩽C, or

Multiplying both sides by α(S) and taking sum over ∣S∣⩽C result in

We claim that there does not exist a set of α(S) such that Q(T)⩾∑_S∈⊆Mα(S)Q(S) and R(T)<∑_S∈⊆Mα(S)R(S); otherwise, it contradicts the above inequality. Therefore, T is an efficient set.

Second, suppose that T is an efficient set by Definition 2 so it must be on the efficient frontier R̄(q); otherwise there exists a convex combination of some sets that consumes less resource but produces strictly more profit, which contradicts the definition of efficient set. Because R̄(q) is concave from Lemma 1, there exists a μ such that

Set T is an optimal solution to problem (4). □

Proof of Theorem 2: We will show that each efficient assortment S _C ^l for l⩾l^* is an efficient set by Definition 2 and vice versa.

Suppose that T is an optimal solution to problem (4) for some μ⩾0. From subsection ‘Identify efficient sets for GAM with a capacity constraint’, g _ij (μ) is the x-coordinate of the intersection point between the lines h _i (γ,μ) and h _j (γ,μ) for each μ, that is, where for the parsimonious GAM formulation. Notice that the ordering of g _ij (μ) is the same as of in the parsimonious GAM formulation.

From Theorem 1, there exists a unique interval, denoted by that contains the unique solution to problem (4) or its equivalent problem (9) below, denoted by γ^*(μ), and set T includes all the products corresponding the top at most C lines with positive values in interval :

The index l^*(μ) must be greater than or equal to l^*, the index corresponding to the optimal assortment of problem (2), because each intersection point g _ij (μ) is on the left-hand side of by μ/(1−θ) units for all i,j∈M. Actually, l^*(μ) is increasing with respect to μ in the parsimonious GAM formulation. The efficient assortment corresponding to interval is the same efficient assortment corresponding to which is equivalent to set T. By similar arguments, we can show that each assortment {S _C ^l,l=l^*, l^*+1, …, K} is an optimal solution to problem (4) for some μ⩾0, respectively. □

Proof of Proposition 3: It is sufficient to show that the ranking of intersections g _ij (μ) uniquely determines the ordering of lines {h _i (γ,μ):i∈M⁺} for any γ in each interval constituted by any two consecutive points among We will next construct the ordering for each interval and show that the efficient assortments by Definition 1 depend on g _ij (μ) only through their ranking.

We will construct the ordering from the very right interval Obviously, the ordering of {h _i (γ,μ):i∈M⁺} only depends on w̃ _i and it can be expressed by σ^K(μ)≔{σ₁^K(μ),σ₂^K(μ),…, σ _m ^K(μ),σ_m+1^K(μ)} such that The ordering does not change for

Suppose that the ordering of lines {h _i (γ, μ):i∈M⁺} for any is σ^l(μ)=(σ₁^l(μ), σ₂^l(μ), …, σ _m ^l(μ), σ_m+1^l(μ)), that is, Because is the closest intersection on the left-hand side, line is strictly higher than line is strictly higher than line that is, for any However, the ordering of lines and exchanges for that is, The ordering of all other lines does not change for any because they are linear functions and there is no other intersection among them in the interval Moreover, j _l and i _l must be two consecutive lines on the ordering σ^l(μ) and suppose σ _k ^l(μ)=j _l ,σ_k+1^l(μ)=i _l without loss of generality; otherwise, it contradicts the ordering of g _ij (μ). We claim that the ordering of {h _i (γ,μ):i∈M⁺} for any is σ^l−1(μ)=(σ₁^l−1(μ), σ₂^l−1(μ), …, σ _m ^l−1(μ), σ_m+1^l−1(μ)), where σ _k ^l−1(μ)=i _l , σ_k+1^l−1(μ)=j _l and σ _s ^l−1(μ)=σ _s ^l(μ) for all s∈M⁺ and s≠k, k+1. In other words, the ordering of {h _i (γ,μ), i∈M⁺} only changes at each intersection point and the new ordering is updated by exchanging the two lines of that intersection.

Thus, we have constructed the ordering of {h _i (γ,μ):i∈M⁺} and shown that they are uniquely determined by the ranking of their intersections. Therefore, the intersection ranking also uniquely determines the efficient assortments by Definition 1 that are the top at most C lines with positive values in each interval. □