Assortment optimization for online video games

1. Introduction

Over the last decade, online video games have seen tremendous growth. This growth has only increased since the start of the COVID-19 pandemic, as video games can provide an outlet for connection in isolation. A recent market report (Newzoo, 2023), for example, states that there are over 3.5 billion video game players worldwide and that the video game industry is projected to exceed $211 billion in revenue by 2025. In recent years, microtransactions have become a significant and increasing source of revenue for video game publishers. Microtransactions are in-game purchases where customers spend small amounts of in-game or real-world currency to obtain virtual items. Typically, these items are used to improve a player’s appearance in the game or to gain an advantage over other players. In the first quarter of 2023 alone, Activision Blizzard (one of the major video game companies) announced $1.29 billion in revenue from microtransactions. These microtransactions now comprise over 70% of revenues for video game companies, surpassing traditional game sales (Newzoo, 2023). Given the abundance of transactional and contextual data available due to the very nature of online video games, microtransactions provide numerous opportunities to increase revenue while enhancing the customer experience.

OPEN IN VIEWER

Figure 1.

Store interface of Fortnite: The Featured section (left) and the Just For You (JFY) section (right).

When customers of an online video game visit its virtual store, they are presented with a set of in-game items, known as an assortment. Due to the capacity of the store interface, only a limited number of items can be displayed. The seller must then decide upon an assortment to maximize expected revenues. This is known as assortment optimization (Gallego and Topaloglu, 2019, Chapter 5). Although assortment optimization has become increasingly pervasive and successful in traditional online retailing, its adoption by video game companies is still in its infancy.

The layout of these virtual stores usually has a common structure and includes both a Featured section to promote new or popular items and a Just For You (JFY) section tailored to customer tastes. The Featured assortment is offered to all customers, whereas the JFY section can be personalized. Figure 1 shows the store interface of Fortnite, a successful video game that was released in 2017 by Epic Games. The left side of Figure 1 shows two products with larger displays that comprise its Featured section. The right side of Figure 1 shows six products with smaller displays as “DAILY ITEMS,” which corresponds to the JFY section. For each product, its price is expressed using in-game currency, which can be obtained by real money or by certain activities conducted in the game. For example, the product “DIECAST” requires 1,200 units of the in-game currency. Notably, Fortnite generated revenues of $1.8 billion in 2019, all of which came from microtransactions (Li et al., 2020). Another successful video game, Call of Duty: Warzone, generated almost $500 million in revenue through microtransactions 3 months after its release in March 2020 (IGN India, 2020; Tassi, 2020). Given the magnitude of these financial implications, the unique structure of online video game stores motivates us to investigate the assortment optimization problems that arise in this setting.

In online video game stores, customers can usually only purchase items offered in the assortment; unlike traditional online retail stores, there is no place to search for or buy from a complete list of all items. This practice intentionally creates artificial scarcity, which prevails in the video game industry (Matthews, 2008). Therefore, the Featured section typically includes highly attractive and popular items that often emerge after in-game content updates. A shared, non-personalized Featured section ensures that customers can purchase such items (e.g., the newest weapon) when customers see these items used by friends or opponents in game sessions. A personalized JFY section, on the other hand, can account for the heterogeneity of customer preferences and improve revenue by offering customers items that more accurately match their tastes (Arora et al., 2008). In addition, these personalized sections attract customer attention and foster customer loyalty and lock-in (Ansari and Mela, 2003; El Housni and Topaloglu, 2023). We note that the Featured and JFY section assortments are usually drawn from non-overlapping pools of items. Currently, video game companies mostly use Featured assortments that are manually chosen by developers in an ad-hoc fashion, while they mostly use machine learning methods to determine the items in JFY assortments. However, Feldman et al. (2022) show that using customer choice models can provide better results than machine learning-based methods when determining assortments. In this article, we propose a modeling framework to systematically select both the Featured and JFY section assortments in an integrated fashion by employing a sophisticated choice model.

The structure of such stores naturally motivates us to model customers’ choices using a nested logit model. As a popular extension to the well-known multinomial logit (MNL) model pioneered by Luce (1959) and McFadden (1974), the nested logit model was first introduced by Williams (1977). Under the nested logit model, items are organized in nests. The choice process is such that the customer first selects a nest; subsequently, the customer chooses an item in that nest. We model the Featured and JFY sections as two nests, each with a display capacity limited by the store interface. In addition, the no-purchase option is modeled as a separate nest. Relative to the MNL model, the nested logit model captures differences in substitution, visibility, and attention between the Featured and JFY sections. We validate this setup using numerical experiments that show that using the nested logit model leads to improved parameter estimation and higher revenues.

Our work complements a research stream in assortment planning under discrete choice models that focuses on developing algorithms for the corresponding revenue maximization problems. In particular, we develop solution algorithms for a constrained mixture-of-nested-logit assortment optimization problem, where customers are grouped into different segments, and each segment is equipped with different nested logit choice model parameters. Assortments are partitioned into featured and personalized sections that are subject to display capacity constraints. The resulting constrained-mixture-of-nested-logit assortment optimization problem provides flexibility in modeling customers’ choices but is notoriously difficult to solve. However, video game stores provide a natural application to motivate this problem, given the structure of the store layout and the absence of search or options. To the best of our knowledge, our paper is the first to devise both exact solution methods and approximate solution algorithms with performance guarantees for this problem class. While our motivation stems from online video games, our model and solution methods can also be used in other applications that involve assortment optimization with both common and personalized sections. One potential application is omnichannel retailing, where the Featured section would correspond to a brick-and-mortar store and the JFY section would correspond to an online channel. This setting, however, might impose corporate requirements; for example, the products offered in the online channel might have to be restricted to a subset or superset of the ones offered in the brick-and-mortar store (Chen et al., 2026b; El Housni and Topaloglu, 2023).

The use of a JFY assortment is closely related to an emerging research stream on assortment personalization, which focuses on offering items tailored to each customer’s taste based on previously collected data. As retailers increasingly collect large amounts of customer data, personalized assortment planning has received considerable attention in recent years. Much of the research in this area assumes that sellers have limited prior information on customers’ preferences and proposes efficient learning algorithms to address the exploration versus exploitation trade-off. While the segmentation of customers and estimation of choice model parameters are interesting and important research questions in and of themselves, we restrict our attention to solving static revenue maximization problems. Throughout this article, we assume that customer segmentation is readily available and that the segment sizes and choice model parameters are known. This is not unusual for video game companies, which often have substantial resources dedicated to analyzing customers’ preferences and conducting behavioral segmentation.

2. Model formulation and preliminaries

We consider the store of an online video game with a shared Featured section and a personalized JFY section. We use F = { 1 , … , F } to represent the set of all candidate items in the Featured section, and J = { 1 , … , J } to represent the set of all candidate items in the JFY section. We also use r i F and r j J to denote the revenues associated with items i ∈ F and j ∈ J . Given the layout of store interfaces, we further use c F and c J to denote the display capacity of the Featured and JFY sections, respectively.

We consider a set S = { 1 , … , S } of customer segments. The probability that a customer in segment s visits the store equals λ s , where ∑ s ∈ S λ s = 1 . Items in the Featured section are offered to all customers, while items in the JFY section are personalized for each segment. We use a binary vector a F ∈ { 0 , 1 } F to represent the items included in the Featured section, that is, a i F = 1 if and only if item i is included. Similarly, we also use binary vectors a s J ∈ { 0 , 1 } J to represent the items included in the JFY section for segment s ∈ S , and use a J = ( a 1 J , … , a S J ) to represent the personalized JFY assortments for all segments.

We assume that the customers in each segment choose among the items offered according to the nested logit model due to the unique structure of virtual stores. The Featured and JFY sections can naturally be modeled using two nests. We further assume that the no-purchase option is a separate nest (it is not available within the Featured or JFY nest), that is, if a customer decides to make a purchase in one of the Featured and JFY nests, she will choose one of the offered items. This assumption is common in the literature (see Berbeglia et al., 2022; Chen et al., 2021; Gallego and Topaloglu, 2014). Under this nested logit model, arriving customers decide either to make a purchase in the Featured or JFY nest or leave without a purchase (see Figure 2 for an illustration).

OPEN IN VIEWER

Figure 2.

Illustration of the nested logit choice model.

For a customer in segment s ∈ S , let v s i F be the preference weight she attaches to item i in the Featured section and v s j J the preference weight she attaches to item j in the JFY section. Given an assortment ( a F , a J ) , we also define the total preference weight of all offered items in the Featured and JFY sections as follows:

ϑ s F ( a F ) = ∑ i ∈ F v s i F a i F and ϑ s J ( a s J ) = ∑ j ∈ J v s j J a s j J for all s ∈ S .

q s F ( a F ) = ∑ i ∈ F v s i F r i F a i F ϑ s F ( a F ) ,

q s J ( a s J ) = ∑ j ∈ J v s j J r j J a s j J ϑ s J ( a s J ) .

We normalize weights such that the preference weight of not making a purchase equals 1 for all customer segments. For each segment s , the Featured and JFY sections further have dissimilarity parameters Γ s and γ s , respectively, which characterize the degree of dissimilarity of the items that can be offered in these sections. If the assortment ( a F , a J ) is offered, the respective probabilities that a customer in segment s decides to purchase an item in the Featured and JFY sections will equal

p s F ( a F , a J ) = ϑ s F ( a F ) Γ s 1 + ϑ s F ( a F ) Γ s + ϑ s J ( a s J ) γ s , and p s J ( a F , a J ) = ϑ s J ( a s J ) γ s 1 + ϑ s F ( a F ) Γ s + ϑ s J ( a s J ) γ s .

Under the mixture-of-nested-logit choice model, the total expected revenue when offering the assortment ( a F , a J ) will thus equal

z ( a F , a J ) = ∑ s ∈ S λ s [ p s F ( a F , a J ) q s F ( a F ) + p s J ( a F , a J ) q s J ( a s J ) ] = ∑ s ∈ S λ s ϑ s F ( a F ) Γ s q s F ( a F ) + ϑ s J ( a s J ) γ s q s J ( a s J ) 1 + ϑ s F ( a F ) Γ s + ϑ s J ( a s J ) γ s .

A = { ( a F , a J ) ∈ { 0 , 1 } F + S J : ∑ i ∈ F a i F ≤ c F , ∑ j ∈ J a s j J ≤ c J , ∀ s ∈ S } ,

P : z * = max ( a F , a J ) ∈ A z ( a F , a J ) .

(1)

Before concluding this section, we present the hardness result of problem ( P ). As a first step, we observe that problem ( P ) reduces to an assortment optimization problem under the mixture-of-MNL model when the dissimilarity parameter Γ s equals 1 and the display capacity c J for the personalized assortments equals 0 . Because Rusmevichientong et al. (2014) show that assortment optimization under the mixture-of-MNL model is NP-complete, even with two customer segments, this immediately establishes the complexity of solving problem ( P ). Recently, Désir et al. (2022) also show that assortment optimization under the mixture-of-MNL model is hard to approximate within any reasonable factor when the number of segments S is not a constant (Désir et al., 2022: Theorem 2). We formally state these results here:

To conclude this section, we emphasize that the coupling requirement imposed by the shared Featured section drastically changes the problem structure from a computational perspective. If the coupling requirement is relaxed, problem ( P ) becomes polynomially solvable. If the coupling requirement is imposed, however, problem ( P ) is NP-Hard even when there are only two customer segments (i.e., | S | = 2 ) and the preference weights of the Featured items are the same for all customers (i.e., v s i F = v s ′ i F for all segments s in S and items i in F ). We prove these results in E-Companion EC.5, where we also identify a tractable case even when coupling requirements are imposed.

In this section, we develop mixed-integer programming (MIP) formulations for the assortment optimization problem that exploit its unique structure. To exploit this structure, we present a key property of ( P ). Building on this result, we then show that ( P ) can be reformulated as a convex MIP using conic inequality constraints. This reformulation enables the use of powerful polyhedral outer-approximation methods to solve the resulting optimization problem. To further improve computational performance, we also introduce a preprocessing technique and additional reformulations that rely on the structural property.

3.1. Structural property

Determining the Featured section assortment is a key complicating factor in problem ( P ). If the Featured section assortment is fixed, however, problem ( P ) becomes separable by the customer segments, and the assortment optimization problem for each customer segment can be solved efficiently. Specifically, consider the problem where a Featured section assortment a ^ F is given

P ~ ( a ^ F ) : z ~ * ( a ^ F ) = max a J : ( a ^ F , a J ) ∈ A z ( a ^ F , a J ) .

(2)

Then, z ~ * ( a ^ F ) = ∑ s ∈ S λ s z ~ s * ( a ^ F ) , where z ~ s * ( a ^ F ) is obtained by solving the following problem for each segment:

P ~ s ( a ^ F ) : z ~ s * ( a ^ F ) = max a s J ∈ { 0 , 1 } J : ∑ j ∈ J a s j J ≤ c J ϑ s F ( a ^ F ) Γ s q s F ( a ^ F ) + ϑ s J ( a s J ) γ s q s J ( a s J ) 1 + ϑ s F ( a ^ F ) Γ s + ϑ s J ( a s J ) γ s .

(3)

The following theorem combines the results from Rusmevichientong et al. (2010) and Gallego and Topaloglu (2014), and shows that the assortment optimization problem can be solved efficiently when given a fixed Featured section assortment.

Theorem 1

For any segment s ∈ S and Featured section assortment a ^ F ∈ { 0 , 1 } F , the assortment optimization P ~ s ( a ^ F ) can be solved with a running time of O ( | J | 2 ) .

Theorem 1 relies on the StaticMNL algorithm proposed by Rusmevichientong et al. (2010) to generate a collection, denoted by C s J , of O ( | J | 2 ) candidate JFY assortments for each segment s . Using Lemma 3 in Gallego and Topaloglu (2014), Theorem 1 ensures that an optimal JFY assortment for segment s must be included in C s J . This is illustrated in Algorithm 1, where the StaticMNL algorithm takes the segment’s preference weights, item revenues, and display capacity as inputs. The time complexity is O ( | S | | J | 2 ) . Video game companies could use this algorithm in lieu of machine learning methods when the Featured section assortments are determined separately; in addition, this procedure serves as a building block for our subsequent development.

3.2. Formulation as a minimization problem

To construct a convex MIP, we start by reformulating ( P ) as a minimization problem, similar to the approach taken by Şen et al. (2018) for assortment optimization under mixture-of-MNL models. Letting

r ¯ = max [ max i ∈ F r i F , max j ∈ J r j J ] ,

we define

q ¯ s F ( a F ) = ∑ i ∈ F ( r ¯ − r i F ) v s i F a i F ϑ s F ( a F ) and q ¯ s J ( a s J ) = ∑ j ∈ J ( r ¯ − r j J ) v s j J a s j J ϑ s J ( a s J ) ,

and observe that the probability that a customer in segment s does not make a purchase equals

1 1 + ϑ s F ( a F ) Γ s + ϑ s J ( a s J ) γ s .

Next, we let

z ¯ s ( a F , a J ) = r ¯ + ϑ s F ( a F ) Γ s q ¯ s F ( a F ) + ϑ s J ( a s J ) γ s q ¯ s J ( a s J ) 1 + ϑ s F ( a F ) Γ s + ϑ s J ( a s J ) γ s ,

and note that

z ( a F , a J ) = r ¯ − ∑ s ∈ S λ s z ¯ s ( a F , a J ) .

As the first item is constant, we can find an optimal assortment by minimizing the second term, resulting in the minimization problem

P ¯ : z ¯ * = min ( a F , a J ) ∈ A ∑ s ∈ S λ s z ¯ s ( a F , a J ) .

(4)

3.3. Formulation as a convex MIP

We formulate ( P ¯ ) as a convex MIP. We use the observation that an optimal JFY assortment for segment s must be included in a polynomially bounded set of candidates C s J = { a s , 1 J , … , a s , C s J J } as shown in Theorem 1. For each of exposition, we define α s = ∑ i ∈ F v s i F a i F , n s , c = ϑ s J ( a s , c J ) γ s q ¯ s J ( a s , c J ) and d s , c = ϑ s J ( a s , c J ) γ s for all s ∈ S and every candidate solution a s , c J ∈ C s J . Furthermore, we use binary variables a i F to represent whether a featured item i is selected and binary variables x s , c to represent whether the candidate JFY assortment c is selected for segment s .

With these definitions, we can formulate problem ( P ¯ ) as follows:

P ¯ : z ¯ * = min a F ∈ { 0 , 1 } F , x ∈ { 0 , 1 } ∑ s ∈ S C s J , α ∈ R + S ∑ s ∈ S λ s ( r ¯ + α s Γ s − 1 ∑ i ∈ F v s i F ( r ¯ − r i F ) a i F + ∑ c ∈ C s J n s , c x s , c 1 + α s Γ s + ∑ c ∈ C s J d s , c x s , c )

(5)

s . t . ∑ i ∈ F v s i F a i F = α s , ∀ s ∈ S ,

(6)

∑ i ∈ F a i F ≤ c F ,

(7)

∑ c ∈ C s J x s , c = 1 , ∀ s ∈ S .

(8)

Constraint (6) defines α s , while constraints (7) and (8) restrict the selection of featured and JFY assortments.

Next, we show that the objective function (5) can be transformed into a convex function. To that end, we first define

f s = 1 1 + α s Γ s + ∑ c ∈ C s J d s , c x s , c and g s , c = x s , c 2 1 + α s Γ s + ∑ c ∈ C s J d s , c x s , c .

We also let

u s = ∑ c ∈ C s J ( 1 + d s , c ) 1 Γ s x s , c and h s , i = ( a i F ) 2 α s + u s Γ s α s 1 − Γ s .

With these definitions, given that a F and x are binary and ∑ c ∈ C s J x s , c = 1 for all s ∈ S , we find that the objective function (5) will be equal to

∑ s ∈ S λ s r ¯ f s + ∑ s ∈ S , c ∈ C s J λ s n s , c g s , c + ∑ s ∈ S , i ∈ F λ s v s i F ( r ¯ − r i F ) h s , i .

(9)

The convexity of the transformed objective function (9) follows when the functions f s , g s , c , and h s , i are convex, which is established in the following proposition.

Proposition 2

For each s ∈ S , the functions f s , g s , c , and h s , i are convex for all α s , a i F , u s , x s , c ≥ 0 ( i ∈ F , c ∈ C s J ) such that ∑ c ∈ C s J x s , c = 1 .

Putting everything together, we find that P ¯ can be formulated as follows:

MINLP0 : z ¯ * = min ∑ s ∈ S λ s r ¯ f s + ∑ s ∈ S , c ∈ C s J λ s n s , c g s , c + ∑ s ∈ S , i ∈ F λ s v s i F ( r ¯ − r i F ) h s , i s . t . ∑ i ∈ F v s i F a i F = α s , ∀ s ∈ S ,

(10)

∑ i ∈ F a i F ≤ c F ,

(11)

∑ c ∈ C s J x s , c = 1 , ∀ s ∈ S ,

(12)

t s ≤ α s Γ s , ∀ s ∈ S ,

(13)

f ~ s = 1 + t s + ∑ c ∈ C s J d s , c x s , c , ∀ s ∈ S ,

(14)

f s f ~ s ≥ 1 , ∀ s ∈ S ,

(15)

g s , c f ~ s ≥ x s , c 2 , ∀ s ∈ S , c ∈ C s J ,

(16)

u s = ∑ c ∈ C s J ( 1 + d s , c ) 1 Γ s x s , c , ∀ s ∈ S ,

(17)

w s ≤ u s Γ s α s 1 − Γ s , ∀ s ∈ S ,

(18)

e ~ s = α s + w s , ∀ s ∈ S ,

(19)

h s , i e ~ s ≥ ( a i F ) 2 , ∀ s ∈ S , i ∈ F ,

(20)

a i F ∈ { 0 , 1 } , ∀ i ∈ F ,

(21)

x s , c ∈ { 0 , 1 } , ∀ s ∈ S , c ∈ C s J ,

(22)

α s ≥ 0 , ∀ s ∈ S .

(23)

We emphasize that the nonlinear constraints in this formulation can be expressed as conic inequalities. Specifically, constraints (15), (16), and (20) correspond to rotated second order cones, while constraints (13) and (18) correspond to power cones. This enables the use of powerful branch-and-bound based outer approximation algorithms (Coey et al., 2020) that iteratively refine polyhedral relaxations of the conic constraints in a branch-and-cut framework.

3.4. Strengthening the formulation

In this section, we propose several improvements to formulation MINLP0. First, we highlight the bilinear terms that arise in this formulation to strengthen MINLP0 using McCormick estimators (McCormick, 1976) and additional conic constraints. Next, we develop a preprocessing procedure to derive tight bounds for the McCormick estimators. Finally, we reformulate the resulting formulation using so-called “by”-variables (Pritsker et al., 1969); while this does not necessarily strengthen the formulation, we find that this reformulation can substantially improve computational performance.

3.4.1. McCormick estimators

To start, we observe that the decision variables g s , c and h s , i correspond to bilinear terms, that is, g s , c ≡ f s x s , c = f s x s , c 2 and h s , i ≡ e s a i F = e s ( a i F ) 2 given that a F and x are binary. Here, we define e s = 1 e ~ s , which can be ensured by adding the conic inequality

e s e ~ s ≥ 1 ,

to our formulation for all s ∈ S .

The McCormick estimators provide a well-known approach that uses conditional lower and upper bounds to establish a convex relaxation of bilinear terms. For the bilinear terms g s , c , this leads to additional constraints

f _ s , c 1 x s , c ≤ g s , c ≤ f ¯ s , c 1 x s , c , f s − f ¯ s , c 0 ( 1 − x s , c ) ≤ g s , c ≤ f s − f _ s , c 0 ( 1 − x s , c ) ,

(24)

where f _ s , c 1 and f ¯ s , c 1 are lower and upper bounds on f s if x s , c = 1 , and f _ s , c 0 and f ¯ s , c 0 are lower and upper bounds on f s if x s , c = 0 . We also add similar constraints for the bilinear terms h s , i , yielding

e _ s , i 1 a i F ≤ h s , i ≤ e ¯ s , i 1 a i F , e s − e ¯ s , i 0 ( 1 − a i F ) ≤ h s , i ≤ e s − e _ s , i 0 ( 1 − a i F ) .

Here, e _ s , i 1 and e ¯ s , i 1 are lower and upper bounds on e s if a i F = 1 , and e _ s , i 0 and e ¯ s , i 0 are lower and upper bounds on e s if a i F = 0 .

OPEN IN VIEWER

Figure 3.

Preprocessing for conditional bounds: (a) range of optimal values, (b) c cannot be optimal, and (c) c can be optimal.

3.4.2. Establishing conditional bounds

The extent to which the McCormick estimators can strengthen the formulation depends on the conditional bounds we can construct. To establish tight bounds, we use a preprocessing routine.

The general idea behind this procedure is as follows. Recall that α s = ∑ i ∈ F v s i F a i F for all s ∈ S . We also define σ s = ∑ i ∈ F v s i F ( r ¯ − r i F ) a i F for all s ∈ S . Then, for a given segment s and featured assortment a F , we can write

z ¯ s ( a F , a J ) = z ¯ s ( α s , σ s ) = min ∑ c ∈ C s J x s , c = 1 ( r ¯ + α s Γ s − 1 σ s + ∑ c ∈ C s J n s , c x s , c 1 + α s Γ s + ∑ c ∈ C s J d s , c x s , c ) .

More specifically, given that a candidate c is selected, we define

z ¯ s , c ( α s , σ s ) = μ s , c ( α s ) + σ s ν s , c ( α s ) ,

where

μ s , c ( α s ) = r ¯ + n s , c 1 + α s Γ s + d s , c and ν s , c ( α s ) = α s Γ s − 1 1 + α s Γ s + d s , c .

For each segment s ∈ S , we can therefore establish positive lower and upper bounds α s _ , α s ¯ for α s and σ s _ , σ s ¯ for σ s . For example, we can let α s _ = min i v s i F , α s ¯ = c F ⋅ max i v s i F , σ s _ = min i v s i F ( r ¯ − r i F ) , and σ s ¯ = c F ⋅ max i v s i F ( r ¯ − r i F ) . Then, we partition the region [ α s _ , α s ¯ ] × [ σ s _ , σ s ¯ ] into K s regions. For each region [ α s , k _ , α s , k ¯ ] × [ σ s , k _ , σ s , k ¯ ] , where k ∈ 1 , … , K s , we then determine whether a candidate c ∈ C s J can potentially be part of an optimal solution in that region; we let o s , c , k = 1 if and only if candidate c can be optimal in region k . We use this to determine bounds on α s and σ s when a candidate c can be optimal, that is,

α s , c l = min k ∈ 1 , … , K s ∧ o s , c , k = 1 α s , k _ , and α s , c u = max k ∈ 1 , … , K s ∧ o s , c , k = 1 α s , k ¯ ,

(25)

σ s , c l = min k ∈ 1 , … , K s ∧ o s , c , k = 1 σ s , k _ , and σ s , c u = max k ∈ 1 , … , K s ∧ o s , c , k = 1 σ s , k ¯ .

(26)

These values, in turn, can be used to determine the conditional bounds in the McCormick estimators. Specifically, we have

f _ s , c 1 = 1 1 + α s , c u Γ s + d s , c , and f _ s , c 0 = min c ′ ∈ C s J : c ′ ≠ c 1 1 + α s , c ′ u Γ s + d s , c ′ , f ¯ s , c 1 = 1 1 + α s , c l Γ s + d s , c , and f ¯ s , c 0 = max c ′ ∈ C s J : c ′ ≠ c 1 1 + α s , c ′ l Γ s + d s , c ′ .

To determine whether a candidate c ∈ C s J can potentially be part of an optimal solution in a region [ α s , k _ , α s , k ¯ ] × [ σ s , k _ , σ s , k ¯ ] (i.e., to decide the value of o s , c , k as 1 or 0 in (25) and (26)), we first observe that z ¯ s , c ( α s , σ s ) reduces to a linear function in σ s for a given candidate c ∈ C s J and α s .

Next, we can also observe that both the intercept μ s , c ( α s ) and the slope ν s , c ( α s ) are decreasing in α s because α s > 0 and 0 < Γ s ≤ 1 . As a result, when candidate c is selected and α s ∈ [ α s , k _ , α s , k ¯ ] , the possible values of z ¯ s , c ( α s , σ s ) are bounded from below by the linear function

μ s , c ( α s , k ¯ ) + σ s ν s , c ( α s , k ¯ ) ,

and bounded from above by the linear function

μ s , c ( α s , k _ ) + σ s ν s , c ( α s , k _ ) .

We illustrate these potential solution values in Figure 3(a). This, however, allows us to establish a criterion to determine whether a candidate c ∈ C s J can potentially be part of an optimal solution in the given region. More precisely, we note that candidate c cannot be optimal in that region (i.e., candidate c is dominated) if and only if there exists some other candidate c ′ ∈ C s J such that

μ s , c ( α s , k ¯ ) + σ s , k _ ν s , c ( α s , k ¯ ) ≥ μ s , c ′ ( α s , k _ ) + σ s , k _ ν s , c ′ ( α s , k _ ) , and μ s , c ( α s , k ¯ ) + σ s , k ¯ ν s , c ( α s , k ¯ ) ≥ μ s , c ′ ( α s , k _ ) + σ s , k ¯ ν s , c ′ ( α s , k _ ) ,

as illustrated in Figure 3(b). Figure 3(c) further illustrates a situation where the candidate c ∈ C s J could potentially still be part of an optimal solution. Because each of these terms is easily evaluated, we can efficiently determine whether a candidate can be optimal in a given region.

Finally, we also establish conditional bounds on the bilinear terms h s , i . To do so, we let a ^ s | a i F = 1 l and a ^ s | a i F = 1 u be lower and upper bounds on α s when a i F = 1 and let a ^ s | a i F = 0 l and a ^ s | a i F = 0 u be lower and upper bounds on α s when a i F = 0 . These bounds are easily calculated and yield the following conditional bounds in the corresponding McCormick estimators:

e _ s , i 1 = 1 a ^ s | a i F = 1 u + [ max c ∈ C s J ( 1 + d s , c ) ] a ^ s | a i F = 1 u 1 − Γ s , and e _ s , i 0 = 1 a ^ s | a i F = 0 u + [ max c ∈ C s J ( 1 + d s , c ) ] a ^ s | a i F = 0 u 1 − Γ s , e ¯ s , i 1 = 1 a ^ s | a i F = 1 l + [ min c ∈ C s J ( 1 + d s , c ) ] a ^ s | a i F = 1 l 1 − Γ s , and e ¯ s , i 1 = 1 a ^ s | a i F = 0 l + [ min c ∈ C s J ( 1 + d s , c ) ] a ^ s | a i F = 0 l 1 − Γ s .

3.4.3. Reformulation

As a final step, we further reformulate the problem using a key observation that allows for a natural ordering of the candidate solutions, as reflected in the following proposition. With slight abuse of the notation, we also use c to denote the index (position) of candidate assortment c in this order.

Proposition 3

For all s ∈ S , there exists an ordering of the candidates c ∈ C s J such that d s , c ≥ d s , c + 1 and n s , c ≥ n s , c + 1 for all c ∈ { 1 , … , C s J } .

This allows us to use so-called “by”-variables, that is, we define variable x ~ s , c = 1 if and only if the candidate selected for segment s is among the first c candidates. Note that this implies that

x ~ s , c ≤ x ~ s , c + 1 for all s ∈ S , c ∈ 1 , … , C s J − 1 , and

x ~ s , C s J = 1 for all s ∈ S .

We also define n ~ s , c = n s , c − n s , c + 1 ≥ 0 and d ~ s , c = d s , c − d s , c + 1 ≥ 0 for all s ∈ S and c ∈ C s J , where we assume n s , C s J + 1 = d s , C s J + 1 = 0 . In addition, we let m ~ s , c = ( 1 + d s , c ) 1 Γ s − ( 1 + d s , c + 1 ) 1 Γ s for s ∈ S and c < C s J and let m ~ s , c = ( 1 + d s , c ) 1 Γ s when c = C s J .

Then, we use the substitutions x s , c = x ~ s , c − x ~ s , c − 1 to obtain the following formulation:

MINLP1 : z ~ * = min ∑ s ∈ S λ s r ¯ f s + ∑ s ∈ S , c ∈ C s J λ s n ~ s , c g s , c + ∑ s ∈ S , i ∈ F λ s v s i F ( r ¯ − r i F ) h s , i s . t . ∑ i ∈ F v s i F a i F = α s , ∀ s ∈ S ,

(27)

∑ i ∈ F a i F ≤ c F ,

(28)

x ~ s , c ≤ x ~ s , c + 1 , ∀ s ∈ S , c ∈ 1 , … , C s J − 1 ,

(29)

x ~ s , C s J = 1 , ∀ s ∈ S ,

(30)

t s ≤ α s Γ s , ∀ s ∈ S ,

(31)

f ~ s = 1 + t s + ∑ c ∈ C s J d ~ s , c x ~ s , c , ∀ s ∈ S ,

(32)

f s f ~ s ≥ 1 , ∀ s ∈ S ,

(33)

g s , c f ~ s ≥ x ~ s , c 2 , ∀ s ∈ S , c ∈ C s J ,

(34)

u s = ∑ c ∈ C s J m ~ s , c x ~ s , c , ∀ s ∈ S ,

(35)

w s ≤ u s Γ s α s 1 − Γ s , ∀ s ∈ S ,

(36)

e ~ s = α s + w s , ∀ s ∈ S ,

(37)

h s , i e ~ s ≥ ( a i F ) 2 , ∀ s ∈ S , i ∈ F ,

(38)

a i F ∈ { 0 , 1 } , ∀ i ∈ F ,

(39)

x ~ s , c ∈ { 0 , 1 } , ∀ s ∈ S , c ∈ C s J ,

(40)

α s ≥ 0 , ∀ s ∈ S .

(41)

Note that this reformulation does not impact the convexity of the objective function or the validity of the conic inequalities, as the coefficients n ~ s , c , d ~ s , c , and m ~ s , c will all be non-negative.

Finally, recall that x ~ s , c = 1 means that the candidate selected for segment s is among the first c candidates. Thus, we reformulate the McCormick inequalities (24) to

( min c ′ ∈ 1 , … , c f _ s , c ′ 1 ) x ~ s , c ≤ g s , c ≤ ( max c ′ ∈ 1 , … , c f ¯ s , c ′ 1 ) x ~ s , c , f s − ( max c ′ ∈ c + 1 , … , C s J f ¯ s , c ′ 0 ) ( 1 − x ~ s , c ) ≤ g s , c ≤ f s − ( min c ′ ∈ c + 1 , … , C s J f _ s , c ′ 0 ) ( 1 − x ~ s , c ) ,

(42)

for all s ∈ S and c ∈ C s J , using the definition of the “by”-variables. While the variable substitutions present a linear transformation that does not necessarily strengthen the formulation, we observed that they yield more balanced search trees that can substantially improve computational performance.

4. Approximate solution methods

In this section, we present three approximate solution methods for the assortment optimization problem ( P ) . Each of these solution strategies is based on reformulating the problem as a two-stage optimization problem ( P ^ ) , where the shared Featured section assortment is determined in the first stage, and personalized JFY assortments are determined in the second stage. Given that determining optimal personalized JFY assortments in the second stage can be done efficiently, determining high-quality Featured assortments in the first stage will play a critical role. For each of the three solution methods, we also establish a performance guarantee. To illustrate the two-stage optimization problem ( P ^ ) , consider a given Featured section assortment a F and define as follows:

α s = ϑ s F ( a F ) = ∑ i ∈ F v s i F a i F , ∀ s ∈ S , and β s = ∑ i ∈ F v s i F r i F a i F , ∀ s ∈ S .

Substituting these terms, the segment-specific assortment optimization problems P ~ s ( a F ) are, therefore, equivalent to

z s ( α s , β s ) = max a s J ∈ { 0 , 1 } J : ∑ j ∈ J a s j J ≤ c J α s Γ s − 1 β s + ϑ s J ( a s J ) γ s q s J ( a s J ) 1 + α s Γ s + ϑ s J ( a s J ) γ s .

We use these observations to reformulate the original assortment optimization problem ( P ); that is, ( P ) is equivalent to

P ^ : z * = max a F ∈ { 0 , 1 } J , ( α , β ) ∈ { { 0 } ∪ A × B } ∑ s ∈ S z s ( α s , β s ) s . t . ∑ i ∈ F v s i F a i F = α s , ∀ s ∈ S , ∑ i ∈ F v s i F r i F a i F = β s , ∀ s ∈ S , ∑ i ∈ F a i F ≤ c F .

For any segment s , we can establish positive lower and upper bounds α s _ , α s ¯ for α s and β s _ , β s ¯ for β s . This allows us to restrict the feasible range of α and β to A = { α ∈ R + S : α s _ ≤ α s ≤ α s ¯ } and B = { β ∈ R + S : β s _ ≤ β s ≤ β s ¯ } . We include the point 0 in the feasible range because the Featured section could be empty.

4.1. Fully polynomial-time approximation scheme

To start, we design an FPTAS for the assortment optimization problem to generate assortments that achieve at least ( 1 − ϵ ) of the optimal revenue with a running time that is polynomial in the instance parameters and 1 / ϵ for any approximation ratio ϵ . We assume that the number of customer segments is constant, given that Désir et al. (2022) show that assortment optimization of the mixture-of-MNL model (which is a special case of our problem) is hard to approximate when the number of customer segments is not constant.

The general idea behind this FTPAS relies on the following property: intuitively, two Featured assortments with corresponding α s and β s values that are close for all segments s will yield similar objective values. This motivates a divide-and-conquer strategy where the region A × B of feasible points ( α , β ) is partitioned into a multidimensional grid. For each region in this grid, we then generate a Featured assortment with corresponding α s and β s values that are within this region (or show that no such assortment exists) and use the property mentioned earlier to bound the approximation error. Clearly, achieving the desired approximation ratio requires careful construction of the multidimensional grid. At the same time, this strategy requires an efficient procedure for generating Featured assortments. The full details are included in EC.1.1. The main result is the following theorem:

Theorem 2

Let ( a ^ F , a ^ J ) be the solution found by Algorithm EC.3 in EC.1.1. Then, we have

z ( a ^ F , a ^ J ) ≥ 1 − 2 ϵ ( 1 + ϵ ) 2 ( 1 + 2 ϵ ) ⋅ z * .

Moreover, its running time equals O ( ( ln A max ϵ ) 2 | S | ⋅ ( | F | ⋅ ( c F ϵ ) 2 | S | + | S | | J | 2 ) ) , where A max := max { max s α s ¯ α s _ , max s β s ¯ β s _ } , and α s _ , α s ¯ are lower and upper bounds for α s and β s _ , β s ¯ are lower and upper bounds for β s for a segment s ∈ S .

4.2. Piecewise-linear approximated MILP

In this section, we propose a MILP formulation, which aims to find an optimal Featured assortment in the first stage of the assortment optimization problem. Our approach uses piecewise-linear functions to approximate the nonlinear objective functions z s ( α s , β s ) for each s in S . We create breakpoints on α s and β s , and represent function values between breakpoints by convex combinations of function values at these breakpoints. In contrast to the FPTAS, this may allow us to create fewer grid points. The full details are included in EC.1.2, and the resulting MIP formulation is referred to as PLA .

From a general perspective, the formulation PLA can be interpreted as a guided search for a high-quality Featured assortment. By controlling the granularity of the parameter grid, however, PLA is, in fact, able to achieve solutions with an arbitrary level of precision. We formally show this in the following theorem:

Theorem 3

Consider some ϵ > 0 and let α s = ( α s 0 , α s 1 , … , α s G s ) and β s = ( β s 0 , β s 1 , … , β s H s ) represent a collection of grid points for all s ∈ S such that

α s 0 = 0 , α s g ≤ α s g + 1 and α s g + 1 α s g ≤ 1 + ϵ for all s ∈ S and g ∈ 1 , … , G s − 1 , and

β s 0 = 0 , β s h ≤ β s h + 1 and β s h + 1 β s h ≤ 1 + ϵ for all s ∈ S and h ∈ 1 , … , H s − 1 .

Furthermore, let a ^ F be an optimal solution to the formulation PLA with this collection of grid points, and let a ^ J represent the optimal JFY assortments returned by the FindJFYwithFixedFeatured ( a ^ F ) algorithm (Algorithm 1).

Then, we have

z ( a ^ F , a ^ J ) ≥ 1 ( 1 + ϵ ) 4 z * .

We emphasize that the approximation results for both the FPTAS and MILP are based on identical structural properties of the functions z s ( α s , β s ) for segments s ∈ S . A key difference between the two approaches, however, is that the FPTAS relies on a polynomially sized dynamic programming problem for each region of the multidimensional grid and does not exploit the structural properties between breakpoints. In the MILP formulation, on the other hand, we approximate the value z s ( α s , β s ) at any point ( α s , β s ) by a convex combination of its adjacent breakpoints. This allows us to better approximate the function values using a smaller collection of breakpoints, even if doing so negatively impacts tractability from a theoretical perspective. In our numerical experiments, we show that the MILP significantly outperforms the FPTAS in practice. Therefore, we believe that using MILP formulations can provide a valuable complement to the existing FPTAS and PTAS literature in revenue management.

4.3. Heuristic algorithm

The FPTAS and MILP outlined in the previous sections can both be used to obtain solutions with an arbitrary performance guarantee. When the number of customer segments S is large, however, their computational performance becomes prohibitive. In this section, we propose a heuristic that efficiently finds high-quality solutions, even when the number of segments S is large. In addition, we provide a performance bound for the heuristic.

The key idea of our heuristic method is to find a high-quality Featured assortment a F , based on the fact that we can efficiently find optimal JFY assortments for a given a F . To achieve such an assortment, we consider each customer segment separately and apply the StaticMNL algorithm to produce a collection of candidate Featured assortments. The overall motivation behind this approach is that each of these candidate Featured assortments will be optimal only when the single customer segment considered is present (Gallego and Topaloglu, 2014: Theorem 4).

We detail the steps of the heuristic in Algorithm 2. After initializing the Featured assortment as an empty set, we use the algorithm StaticMNL to obtain candidate Featured assortments for each segment. Then, the heuristic uses the FindJFYwithFixedFeatured algorithm to find the best Featured assortment from among these candidates, together with its associated JFY assortment. According to Theorem 2.2 by Rusmevichientong et al. (2010), the StaticMNL algorithm produces O ( | F | 2 ) candidate Featured assortments in O ( | F | 2 ) time for each segment. The FindJFYwithFixedFeatured algorithm has time complexity O ( | S | | J | 2 ) . Thus, the heuristic has time complexity O ( | S | 2 | F | 2 | J | 2 ) , which enables its use, even when the number of segments S is large. In addition, however, it is possible to provide a performance guarantee for the solutions obtained by the heuristic algorithm. This is shown in the following theorem:

Theorem 4

Let a ^ F and a ^ J be the solution returned by Algorithm 2. Then, we have

z ( a ^ F , a ^ J ) ≥ 1 | S | ⋅ z * .

The three approximate solution methods can find feasible solutions for problem (P) to establish a lower bound. Frequently, upper bounds can be useful for evaluating solution quality. For this purpose, we also develop valid upper bounds. Our upper bound is closely related to the bounds proposed by Feldman and Topaloglu (2015a), where the authors bound the optimal expected revenue of both the mixture-of-MNL model and the mixture-of-nested-logit model. A key distinction of our work is that the upper bound in this work can be used when the number of candidate items is large, whereas Feldman and Topaloglu (2015a) assume a small number of candidate items. In addition, our work incorporates display capacity constraints and proposes various algorithmic enhancements, both of which are crucial in practice. While we focus on instances with two nests in our setting, it is important to emphasize that this bounding approach can be generalized to assortment optimization under a constrained mixture-of-nested-logit model with any number of nests. A full derivation can be found in EC.2.

5. Numerical experiments

In this section, we conduct numerical experiments on a variety of problem instances to evaluate the performance of our proposed approaches under various settings.

5.1. Instance data

In our numerical study, we generate three classes of instances, which we refer to as small, medium, and large. Table 1 provides a detailed description of these instance classes. Recall that S equals the number of segments of its customers, F equals the number of candidate Featured items, J equals the number of candidate JFY items, and c F and c J represent the display capacity of the Featured and JFY sections, respectively.

OPEN IN VIEWER

Table 1.

Instance classes.

Size	S	F	J	c F	c J
small	2	10	20	3	3
medium	6	20	60	4	4
large	10	30	100	5	5

For each class, we randomly generate 100 instances. The parameters we use to generate our instances are based on conversations with our industry partner to mimic the instances found in their video game stores. The unit price r i F of each candidate Featured item i is sampled from a uniform distribution U ( 0.8 , 4 ) while the unit price r j J of each candidate JFY item j is sampled from a uniform distribution U ( 0.2 , 1 ) , as Featured items are generally more expensive than JFY items. The arrival rate λ s of each customer segment is sampled from a uniform distribution U ( 0.5 , 1 ) and then normalized. The dissimilarity parameters Γ s and γ s are sampled from uniform distribution U ( 0.25 , 1 ) . The preference weights of both the Featured and JFY items are randomly sampled from the exponential distribution E x p ( 0.005 ) . To facilitate future research, we will make all instances publicly available.

5.2. Solution methods

We briefly summarize the solution methods evaluated in our numerical study. To generate assortments, we consider the following methods. Greedy (GRD): As a benchmark, we implement an iterative greedy algorithm (see EC.7). FPTAS: Our FPTAS is described in Algorithm EC.3 in EC.1.1. MILP: Our MILP formulation (see EC.1.2) aims to approximate the objective function using fewer breakpoints than the FPTAS. Heuristic (HEU): We use the heuristic algorithm outlined in Section 4.3. MINLP1: We use the MINLP formulation MINLP1 described in Section 3.4.3. Also, we include two variants MINLP0 and MINLP1-noPre to demonstrate the impact of applying the strengthening and preprocessing techniques, respectively. More details are in EC.6.

5.3. Computational results

5.3.1. Computation times

All experiments were performed on a Mac Studio with an Apple M1 Ultra Chip with 20 cores and 128 GB of RAM. All code is written in Python 3.11.

Computation times are reported in Table 2. We present the average, 95th percentile, and maximum computation time over the 100 instances in each class. The greedy procedure, heuristic algorithm, and MILP formulation can all be solved efficiently, while the FPTAS becomes intractable when instance sizes are larger. As a result, we do not show the FPTAS results for medium and large instances.

OPEN IN VIEWER

Table 2.

Computation times (seconds).

		Approximation methods				MINLPs
Size	Stat.	GRD	FPTAS	HEU	MILP	MINLP1	MINLP1-noPre	MINLP0
small	Avg	0.018	9.236	0.007	0.227	0.144	0.137	0.245
	95th	0.027	24.482	0.009	0.284	0.261	0.380	0.456
	Max	0.032	114.528	0.010	0.377	0.291	0.589	0.617
medium	Avg	0.258	NA	0.197	1.245	3.362	8.386	8.081
	95th	0.279	NA	0.233	1.589	11.036	13.167	14.442
	Max	0.290	NA	0.249	3.000	16.519	20.341	74.169
large	Avg	1.331	NA	1.204	3.804	40.039	179.338	944.399
	95th	1.397	NA	1.359	5.346	99.212	785.065	3600
	Max	1.475	NA	1.568	8.314	891.182	2932.342	3600 (23)

Table 2 also shows that MINLP1 can efficiently find optimal solutions, with an average computation time of 15 seconds across all instances. Moreover, Table 2 highlights that the strengthening techniques we introduce are critical to achieve this performance. For large instances, the MINLP1 formulation is over 20 times faster on average than the MINLP0 formulation that omits the strengthening techniques. In fact, the MINLP0 formulation reaches the time limit (3,600 seconds) without finding an optimal solution for 23 of the 100 large instances. Relative to the MINLP1-noPre formulation, MINLP1 accelerates computation time by a factor of 2.5 and 4.5 for the medium and large instances, respectively. This illustrates the impact of the conditional bounds we establish. The computational results also show the robustness of the strengthening techniques, since the 95th percentile and the maximum computation time of MINLP1 are significantly less than MINLP0 and MINLP1-noPre. We further visualize the results in Figure 4, which plots the performance profile (Dolan and Moré, 2002) of the three formulations for the large instances and shows the fraction of instances Π ( t ) that can be solved to optimality within a time limit t .

OPEN IN VIEWER

Figure 4.

Performance profile of the three conic formulations on the 100 large instances.

5.3.2. Solution quality

Table 3 summarizes the solution quality of our procedures. First, Table 3 reports optimality gaps for the greedy procedure, FPTAS, heuristic, and MILP formulation. Optimality gaps are calculated as u b − l b u b , where l b represents the objective value of the solution procedure, and u b represents the upper bound obtained by formulation MINLP1. In addition, we determine optimality gaps for the best solution found among all approximate solution methods. Given the computational efficiency of these solution methods, such an ensemble approach is practically viable. As before, we present the average, 95th percentile, and maximum optimality gap over the 100 instances in each class.

OPEN IN VIEWER

Table 3.

Solution quality (optimality gap (%) vs. MINLP).

	small					medium				large
	GRD	FPTAS	HEU	MILP	Best	GRD	HEU	MILP	Best	GRD	HEU	MILP	Best
Avg	0.33	0.29	0.17	0.10	0.03	0.35	0.18	0.14	0.05	0.23	0.27	0.09	0.05
95th	1.94	1.35	0.81	0.22	0.12	1.86	0.84	0.65	0.15	1.54	0.98	0.50	0.18
Max	5.68	2.46	1.90	2.98	0.24	7.06	1.42	2.45	0.85	6.64	1.44	1.51	0.76

For small instances, all solution methods outperform the baseline provided by the iterative greedy algorithm. The average optimality gap for the greedy algorithm equals 0.33 % across 100 instances, with a worst-case optimality gap as large as 5.68 % . The FPTAS, MILP formulation, and heuristic all achieve smaller average gaps with worst-case optimality gaps below 3% for each class of instances. Among these four solution methods, we observe that the MILP formulation achieves the best revenue performance on average, with an average optimality gap of 0.10 % . The heuristic procedure is also competitive and outperforms the FPTAS with only a fraction of its computation time. We emphasize the potential benefits of the ensemble approach that selects the best solution found among all solution methods. Across all 300 instances, this approach achieves a 0.04 % optimality gap on average and a worst-case optimality gap of 0.85 % . By contrast, the iterative greedy algorithm obtains a worst-case optimality gap of 7.06 % .

6. Managerial insights

In this section, we investigate how the structure of our assortment optimization model impacts performance. First, we aim to understand how the coupling introduced by the shared Featured section affects the platform’s expected revenue and customer utility? To that end, we compare our model with two alternatives:

Full personalization, which retains only the personalized JFY sections for each customer segment.

Full coupling, which retains only the shared Featured section that is identical across all customer segments.

To evaluate the performance of these two alternatives relative to our model setup, we vary the parameter c F , as discussed in Section 6.1. Second, we also aim to understand how our use of a mixture-of-nested-logit model impacts performance? To do so, we compare our model with two further alternatives:

A strategy that relies on the mixture-of-MNL model, in which neither the concept of nesting nor the dissimilarity parameters are incorporated to capture hierarchical substitution effects.

A strategy that selects “most popular” products while respecting capacity constraints, which reflects the current practice of our industrial partner.

We evaluate the performance of these two strategies relative to our model setup in Subsection 6.2.

6.1. Impact of the featured section

In this subsection, we evaluate the impact of the Featured section on both the platform’s expected revenue and customer utility. Expected revenue is defined by the objective function in our optimization models. For the customer utility, we adopt the definition by Sumida et al. (2021) and Wang and Yan (2025), and formally give the expression for our problem as

∑ s ∈ S λ s [ ϑ s F ( a F ) Γ s + ϑ s J ( a s J ) γ s 1 + ϑ s F ( a F ) Γ s + ϑ s J ( a s J ) γ s log ( 1 + ϑ s F ( a F ) Γ s + ϑ s J ( a s J ) γ s ) ] .

6.1.1. Instance generation

To examine the impact of a shared Featured section, we conduct additional experiments with medium instances. We fix the total item capacity at 8 as before and vary the capacity allocated to the Featured and JFY sections, parameterized by the display capacity c F of the Featured section. We consider three scenarios in our experiments: (i) Featured items have a higher mean price than JFY items, (ii) Featured items have a lower mean price than JFY items, and (iii) Featured items have the same mean price as JFY items. In each of the first two scenarios, higher item prices are sampled from a uniform distribution U ( 0.8 , 4 ) while lower item prices are sampled from a uniform distribution U ( 0.2 , 1 ) . In the third scenario, all item prices are sampled from a uniform distribution U ( 0.8 , 4 ) . To evaluate performance, we consider both expected revenue and expected customer utility and present our results in Figure 5. To facilitate meaningful comparisons, both revenue and customer utility are normalized relative to full personalization, which is used as the baseline and denoted as “FP” in the figures. With full personalization ( c F = 0 and c J = 8 ), each customer segment is offered its own assortment (which may include both Featured and JFY items) and no coupling requirements are imposed. By contrast, with full coupling ( c F = 8 and c J = 0 ) only Featured products are offered and those products are required to be identical across segments. Each point in Figure 5 corresponds to an average value over 100 instances, leading to a total of 2,700 instances that are optimized in these experiments.

OPEN IN VIEWER

Figure 5.

Customer utility and expected revenue varying with c F : (a) higher featured prices, (b) lower featured prices, and (c) no price differential.

6.1.2. Results

In our first scenario (see Figure 5(a)), we observe a robust trade-off between utility and revenue. Relative to full personalization ( c F = 0 ), the presence of a Featured section clearly achieves higher customer utility while sacrificing revenue. Customer utility can be improved by more than 15% with a Featured section except for the full coupling case where all items are allocated to the Featured section (i.e., c F = 8 and c J = 0 ). More importantly, full personalization does not necessarily achieve the highest expected revenue. Focusing on the (circle-marked) blue line in Figure 5(a), we find that the Featured section generates higher expected revenue than full personalization when c F ≥ 5 . The underlying reason is that under full personalization, the dissimilarity parameters γ s may not properly reflect the overall heterogeneity for the assortments. Without a Featured nest, the model consequently loses the flexibility to represent differences in substitution patterns, visibility, and customers’ attention between the Featured and JFY items. This flexibility is preserved by introducing multiple nests (the Featured and JFY sections) and highlights the importance of the model structure we propose. We consider the estimation of dissimilarity parameters in Section 6.2, where we confirm the benefit of incorporating nested structure both in terms of parameter estimation and revenue maximization.

In the second scenario, where Featured items are lower-priced (see Figure 5(b)), we again observe that the presence of a Featured section improves customer utility, with a slightly smaller improvement than in the first scenario. In this case, however, revenue will decrease as the size of the Feature assortment increases. When Featured items have higher prices (see Figure 5(a)), expected revenue will improve as c F increases because the additional space is available to present these items. When Featured items have lower prices (see Figure 5(b)), increasing c F now decreases expected revenue as displaying more lower-priced Featured items cannibalizes revenue from personalization through the JFY section. In fact, a detailed examination of the optimal solutions for c F = 0 shows that the original Featured items completely lose their attractiveness in this scenario. Thus, expected revenues with a Featured section are lower than with full personalization. This suggests that the platform can benefit from adapting its assortment strategy toward full personalization in this scenario. Nevertheless, the Featured section’s positive impact on customer utility (and potential engagement) indicates that a careful allocation of display capacity could prove beneficial.

In the third scenario without any price differential (see Figure 5(c)), we observe that customer utility benefits from the introduction of the Featured section, though to a lesser extent than in the first two scenarios. Interestingly, we also observe that introducing a Featured section generates higher expected revenue than full personalization ( c F = 0 ) and that the revenue impact is even more significant than that in Higher Featured Prices (see Figure 5(a)). This provides further evidence that a shared Featured section, combined with a personalized section, can improve both expected revenue and customer utility when display capacity is carefully allocated.

Overall, our results suggest that (i) a careful allocation display capacity can consistently improve customer utility after introducing a Featured section, (ii) using a Featured section combined with the personalized JFY section can lead to higher expected revenue compared with full personalization setting and/or full coupling setting, dependent on the relative price positioning of the Featured and JFY items, and (iii) nesting the two groups allows the platform to better capture customer behavior and model the substitution patterns in a more refined manner.

6.2. Advantages of the mixture-of-nested-logit model

In this section, we perform a simulation study to validate our use of the mixture-of-nested-logit model. Specifically, we compare using our mixture-of-nested-logit model with using both a mixture-of-MNL model (which is the most common choice model used in the literature) and the current practice used by our industrial partner. In each setting, we require a shared Featured section across customer segments while allowing a personalized JFY section for each segment. We impose separate capacity constraints for each section.

6.2.1. Simulation framework

Our simulation framework consists of the following components.

Ground truth data. As a first step, we generate instances using the rank list-based (also called stochastic preference) model following the procedure described in Section 3 of Berbeglia et al. (2022). While other discrete choice models for creating instances do exist, Berbeglia et al. (2022) state that the rank list-based method is equivalent to the general random utility class and has an intuitive interpretation. We believe this approach can provide a fair comparison between the use of various models, as the rank list-based method does not rely on any structural assumptions present in the mixture-of-nested-logit and mixture-of-MNL models.

Each instance generated by the rank list-based method consists of a preset number k of strict preference lists among all alternatives and a probability distribution over those k preferences. We use k ∈ { 10 , 100 } , and define the first list such that the no-purchase option is ranked first. This list is assigned a probability p 1 . For the remaining lists i = 2 , … , k , we define p i = u i ( 1 − p 1 ) / ( ∑ j = 2 k u j ) , where u i is a random number drawn from a uniform distribution between zero to one, such that ∑ i = 1 k p i = 1 . Thus, p 1 corresponds to a lower bound of the ground-truth probability of the no-purchase option. In online sales, the purchase rate is usually very low. For example, over 70% of the items added to a cart are not purchased by retail visitors (Dynamic Yield, 2025). While this rate varies, it is usually between 60% and 80%. Similarly, Baymard (2025b) find that the so-called online shopping cart abandonment rate for 2025 is over 70%, based on 49 different studies (Baymard, 2025a). The cart abandonment rate represents the rate of the number of considered items (those added to the cart) that do not complete the check-out process. A detailed discussion can be found in the review (Wang et al., 2023).

Given this information, we use p 1 ∈ { 0.5 , 0.7 , 0.9 } to reflect the fact that non-purchase behavior is more frequent. We consider 10 Featured and 20 JFY products and construct offer sets consisting of three to six Featured products and six to 12 JFY products. Offer sets are randomly selected for each of the T periods ( T ∈ { 150 , 600 } ), with each period including 10 purchases (from items in the offer set or the no-purchase option) based on the preference ranking list. For each combination of k , p 1 , and T , we generate 20 instances. As a result, we have 240 instances in total that we use as the transaction dataset.

Parameter estimation. We implement a conditional gradient method to estimate parameters from the transaction dataset. This approach has been used by Berbeglia et al. (2022) for latent class MNL estimation, and was originally developed by Jagabathula et al. (2020) for the nonparametric estimation problem for mixing distributions. We follow the same procedure as Berbeglia et al. (2022), and apply this method to estimate the parameters for both the mixture-of-nested-logit and mixture-of-MNL models.

Assortment optimization. For each instance, we obtain assortments based on the estimated parameters for the mixture-of-nested-logit model and the mixture-of-MNL model, respectively. For the mixture-of-nested-logit model, we solve problem (P) to obtain the assortment. For the mixture-of-MNL model, we find an assortment with the same capacity constraints as the mixture-of-nested-logit model by solving a MILP formulation that is outlined in EC.4. We refer to the current practice used by our industry partner as the “most-popular” approach, since it aims to recommend items that result in higher sales. In our implementation of this approach, we determined the expected revenue of each product based on the estimated parameters for the mixture-of-nested-logit model. The “most-popular” approach then selects items with the highest sales while respecting capacity constraints to generate an assortment.

Ground-truth-based expected revenues. To evaluate an assortment’s performance, we determine its expected revenue based on the ground truth data. Given preference rank lists and their probability distribution, we generate the purchase probabilities for the products in an assortment as well as the probability of the no-purchase option. This allows us to calculate the expected revenue of the assortment based on the ground truth.

6.2.2. Simulation results

We first evaluate the performance of our parameter estimation procedure. Subsequently, we evaluate the revenue impact of using the mixture-of-nested-logit model relative to using the mixture-of-MNL model and the most-popular approach.

Estimation performance. Following Berbeglia et al. (2022), we use the soft root mean squared error (RMSE) as the performance metric for the parameter estimation, given the known ground truths. The RMSE provides a clear indication of how closely the estimated model aligns with the ground truth. In Table 4, we report the mean (Mean) and standard error of the mean (SEM) of the RMSE ( % ) under each of the configurations, respectively. The RMSE of the mixture-of-nested-logit averages at 3.22%, indicating that our estimation method achieves the same level of performance as the methods by Berbeglia et al. (2022). We also observe the following key findings. The RMSE for instances with k = 100 is significantly smaller than (around half to) that of those with k = 10 . This aligns with the findings in Section 3.2.3 of Berbeglia et al. (2022), where it is explained by the consistency of the underlying preferences. In addition, the RMSE consistently decreases as p 1 increases across. Finally, the mixture-of-nested-logit model generally exhibits a smaller RMSE than the mixture-of-MNL model. The average RMSEs of the two models are 3.22% and 5.84%, respectively. This is expected as the mixture-of-nested-logit model incorporates more parameters, and demonstrates that the mixture-of-nested-logit mode can better capture customer behavior than the mixture-of-MNL model.

OPEN IN VIEWER

Table 4.

Results on the mean RMSE ( % ) of the parameter estimations.

		k = 10						k = 100
		T = 150			T = 600			T = 150			T = 600
		0.5	0.7	0.9	0.5	0.7	0.9	0.5	0.7	0.9	0.5	0.7	0.9
Mixture-of-nested-logit	Mean	7.97	4.34	1.45	7.73	4.04	1.37	3.56	2.03	0.81	2.93	1.74	0.62
	SEM	0.37	0.13	0.03	0.32	0.08	0.04	0.27	0.08	0.03	0.06	0.04	0.02
Mixture-of-MNL	Mean	11.26	6.92	2.32	11.08	6.89	2.31	7.57	5.23	2.11	7.41	5.08	1.96
	SEM	0.38	0.25	0.08	0.37	0.24	0.08	0.18	0.13	0.05	0.14	0.08	0.03

Comparisons on expected revenues. As stated before, we use expected revenue based on ground truth data as the performance metric to evaluate an assortment. We report the expected revenues of the mixture-of-nested-logit model, the mixture-of-MNL model, and the most-popular approach in Table EC.2, which shows minimum (Min), maximum (Max), mean (Mean), and standard error of the mean (SEM) for each approach. To better visualize the gains of the mixture-of-nested-logit model over the mixture-of-MNL model, Figure 6(a) displays the ratio between the expected revenue of the mixture-of-nested-logit model and the expected revenue of the mixture-of-MNL model. For each combination of k , T , and p 1 , the bar represents the average ratio, and the line gives the 95% confidence interval of the average ratio over all 20 instances. For the majority of instances, the average ratio values are over 1 , indicating that the mixture-of-nested-logit model outperforms the mixture-of-MNL model in expected revenue. We also observe that the gains are more significant when k is smaller and p 1 is larger. Overall, the average revenue gains are over 25%. This strongly supports the benefits of considering nests in the mixture-of-nested-logit model, rather than using the mixture-of-MNL model.

Next, we examine the most-popular approach that closely aligns with current practice for our industry partner. Similar to Figure 6(a), we use Figure 6(b) to show the ratio between the expected revenue of the mixture-of-nested-logit model and the expected revenue of the most-popular approach. Figure 6(b) shows that the mixture-of-nested-logit model consistently outperforms the most-popular approach. Assortments found by problem (P) achieve higher expected revenues than the current practice, and average revenue gains exceed 50%, which is significant given the scale of microtransactions.

OPEN IN VIEWER

Figure 6.

Expected revenue ratios: (a) comparing with mixture-of-multinomial logit (MNL) and (b) comparing with most-popular approach.

7. Conclusions and future research

In this article, we study an assortment optimization problem under discrete choice models that arises in virtual stores for online video games. For marketing and operations purposes, video game stores include both a Featured section and a JFY section. Customer heterogeneity is characterized by customer segments.

We propose both exact and approximate solution methods. We present an exact MINLP formulation that can find optimal solutions efficiently. Furthermore, we propose an FPTAS and an MILP formulation that return high-quality solutions with arbitrary theoretical performance guarantees. We also design a heuristic algorithm for large instances, for which we also derive a performance guarantee. We conduct numerical experiments on instances that are based on practice. These experiments illustrate that our approaches perform well across various settings.

From a methodological perspective, our work is the first to devise solution algorithms for assortment optimization under the mixture-of-nested-logit model, which is one of the most difficult problem classes arising in assortment optimization. In addition, we evaluate how to allocate space between the Featured and JFY sections to illustrate the impact of a shared Featured section on balancing revenue and customer engagement utility. Finally, we perform simulations using ground-truth instances to show that incorporating nests in the mixture-of-nested-logit model better captures consumer behavior. Crucially, the assortments generated through our proposed solution methods can yield substantial increases in expected revenue. By including nests, we see an average revenue improvement of over 25%. The additional gains average more than 50% compared with our industry partner’s existing practices.

Our work opens up a number of directions for future research. From a methodological perspective, the exact MINLP formulation demonstrates the potential of exact methods for assortment optimization problems. It may be worth further exploring opportunities to improve its efficiency. From an application perspective, a unique feature of online video game stores is that the seller has access to the complete purchase history and inventory information of all customers. This provides numerous opportunities for assortment personalization well beyond the static customer segmentation considered in this article.

Supplemental Material

sj-pdf-1-pao-10.1177_10591478261446056 - Supplemental material for Assortment optimization for online video games

Supplemental material, sj-pdf-1-pao-10.1177_10591478261446056 for Assortment optimization for online video games by Yunlong Wang, Fan You, Thomas Vossen and Rui Zhang in Production and Operations Management