Category Management

Category Management and Coordination in Retail Assortment Planning in the Presence of Basket Shopping Consumers∗ Gérard P. Cachon A. Gürhan Kök The Wharton School Fuqua School of Business University of Pennsylvania Duke University Philadelphia PA, 19104 Durham NC, 27708 cachon@wharton.upenn.edu gurhan.kok@duke.edu opim.wharton.upenn.edu/~cachon www.fuqua.duke.edu/faculty/alpha/kok.htm July 2004 Abstract This paper studies the assortment planning problem with multiple merchandise categories. The categories interact with each other due to the effects of basket shopping consumers. We present a model in which a retailer chooses the number of variants to offer in each category and the consumers of multiple categories (i.e., basket shoppers) make their store choice between the retail store and an exogenous outside alternative based on their total utilities from their shopping basket. We investigate the interaction of the category variety decisions at the retail store under centralized and decentralized management regimes. The common practice of category management is an example of a decentralized regime for controlling assortment because each category manager is responsible for maximizing his or her assigned category’s profit. We show that category management never finds the optimal solution and generally provides less variety than optimal. In a numerical study we demonstrate that the profit loss due to category management can be significant. We provide guidelines on which type of categories the retailer should carry and which should have more variety. Finally, we propose a decentralized regime that uses basket profits, a new metric, rather than accounting profits. Basket profits are easily evaluated from available data and this method produces near optimal solutions. ∗The authors would like to thank David Bell, Morris Cohen, Marshall Fisher, Abba Krieger, Debu Prohit, and Ananth Raman for helpful discussions. An electronic copy of this paper is available from the authors’ webpages.Retailers have increased product selections in all merchandise categories for a number of possible reasons, including heterogeneous customer preferences, variety seeking consumers and brand competition: Quelch and Kenny (1994) report that the number of products in the market place increased by 16% per year between 1985 and 1992 while shelf space expanded only by 1.5% per year during the same period. This rapid growth in variety has raised questions as to whether it is excessive. For example, many retailers are adopting an “efficient assortment” strategy, which primarily seeks to find the profit maximizing level of variety by eliminating low-selling products (Kurt Salmon Associates 1993), and “category management”, which attempts to maximize the profits within a category (AC Nielsen 1998). There is even empirical evidence that variety levels have become so excessive that reducing variety does not decrease sales (Dreze et al. 1994, Broniarcyzk et al. 1998, Boatwright and Nunes, 2001). And from the perspective of operations within the store and across the supply chain, it is clear that variety is costly: greater variety can lead to slower selling inventory, poor product availability, higher handling costs and greater markdown costs. While there may be agreement that reducing variety can increase short run profits, there is far less agreement with respect to its impact on long run profits. Assortment planning models in the literature, and organizational forms such as category management, focus on the selection of products in a single category assuming store traffic is exogenous, i.e., variety within a category influences demand conditional on a store visit, but does not influence store choice. However, if, based on single category analyses, a retailer reduces variety in all categories, then the store becomes less attractive and some customers are likely to defect to other retailers, thereby reducing store traffic. This concern is particularly relevant with respect to basket shoppers: if a basket shopper does not find an item that she wants in one category, she may purchase her entire basket from another retailer. Although retailers are well aware of this issue, there is little research on what to do about it. This paper works with a stylized model to develop managerial insights regarding the assortment planning process in an environment with multiple categories. The retailer offers a selection of products in each merchandise category. Basket shopping consumers choose between the retailer and an outside alternative to maximize their total shopping utility. The retailer’s decisions across merchandise categories can be managed under centralized or decentralized regimes. Decentralized regimes (optimization on a category by category basis), such as category management (CM), are analytically manageable but they ignore (in their pure form) the impact of cross-category interac-1tions. Centralized regimes account for these effects, but only in theory they do so because they are not implementable in practice: it is extremely difficult to design a model to account for all crosscategory effects, to estimate its parameters with available data and to actually solve it. Chen et al (1999) also emphasize the need for models that are solvable with parameters that can be estimated from available data. As CM and centralization are two extremes, merchandising managers often create an intermediate approach by adding constraints to the planning process based on their own knowledge about the store’s categories and customers: e.g., include a particular product, have at least two brands in a subgroup, ensure that the timing and depth of promotions are coordinated across obviously complementary products (chips and salsa, beer and pretzels, etc.), etc. But it is not clear if the appropriate constraints are implemented (e.g., should there be at least two brands or five brands, etc.) or whether all of the necessary interactions are accounted for with this ad-hoc approach. We address the following research questions in this paper. What is the loss due to decentralization compared to the optimal solution? (In some cases decentralization may perform well.) Do decentralized solutions have a consistent bias? (Too much or too little variety.) Is there a way to have the best of both worlds, i.e., are there easily solvable management regimes, based on readily available data, that lead to nearly optimal assortments? We find that the impact of basket shopping consumers on assortment planning is more complex than one might initially suspect because basket shopping generates two contradictory effects. To illustrate, consider a supermarket example. Capers, a low penetration, low frequency product is often not profitable, but customers that buy capers usually buy large baskets of products. Hence, expanding variety in the spices-condiments category (A) to include capers increases store traffic and sales in some other category (B), i.e., more variety in category A makes adding variety to category B more attractive because category A might pull in more shoppers to the store (i.e., categories are strategic complements). This is an intuitive effect, and it leads to the conclusion that ignoring interactions leads to less than the optimal amount of variety (capers are not included in the assortment if you maximize profit in that category alone; they are included only if total store profit is maximized). However, if category A is very attractive, category B can free ride with lower variety (i.e., categories are strategic substitutes): if the spice-condiment category is deep because of the inclusion of capers, other categories need less variety to attract the same basket shoppers. That effect contradicts the initial intuition, hence, maybe decentralized management 2leads to too much variety. In economic models, activities are usually assumed to be (or found to be) either strategic complements or substitutes, but not both. Our model provides a realistic counter-example. We characterize the assortment chosen with a decentralized regime, which we refer to as category management (CM), as well as the assortment with a centralized solution (assuming an ideal situation in which we are able to estimate all of the demand parameters, solve the problem, etc.). We show that if there are any basket shoppers, CM never finds the optimal solution and mostly provides less variety than optimal, even though two categories can be either complements or substitutes depending on their variety levels. With numerical examples we demonstrate that the profit loss due to CM can be significant, 28% on average. More importantly, the performance gets worse as the number of categories increases. Our point is that decentralization can be costly if there are basket shopping consumers and the interactions among categories is not explicitly modeled. To address the potential problem with a decentralized approach to assortment planning, we propose a simple heuristic that retains decentralized decision making (category managers optimize their own categories’ profit) but adjusts how profits are measured. To be specific, instead of using an accounting measure of a category’s profit, we define a new measure called basket profits. Basket profits can be estimated using point-of-sale data and it enables CM to approximately measure the true marginal benefits of merchandising decisions. We believe this analytical approach is an attractive alternative relative to ad-hoc coordination across category managers. The next section describes our model, followed by the literature review in Section 2. Section 3 details the consumer choice process and Section 4 presents the solution under different management regimes. Discussion of managerial implications in Section 5 is followed by the heuristic solution in Section 6, a brief numerical study in Section 7 and concluding remarks in Section 8. 1 ModelBasics Consider a retailer that carries multiple categories of goods (e.g., shirts, ties, sports jackets). The retailer offers a certain assortment defined by what categories she carries and the selection of products in each category. The set of categories is denoted J = {1, 2, ..,N} and the set of variants in category j is denoted Sj = {1, 2, .., Ij}. The retailer carries assortment X = (X1,X2, ..,XJ ), where Xj ⊂ Sj, for all j. There is an outside alternative (possibly another retailer) that consumers can choose to do their shopping. The outside alternative carries assortment Z = (Z1, Z2, ..,ZJ ) 3where Zj ⊂ Sj , for all j. In this paper we take the perspective of the retailer and analyze her decisions X assuming that Z is exogenous. It is worth noting here that the outside alternative can be interpreted in three meaningful ways: I1 the retailer’s direct competitor (e.g., the store across the street), I2 an aggregate representation of the world outside the retailer, I3 a no purchase option calibrated such that the retailer’s share in the model given X and Z is the ratio of its current market share to the maximum potential market share it could achieve by carrying the broadest and deepest possible assortment, Xj = Sj for all j ∈ J. We make the following assumptions about the retailer’s operations. The cost of providing an assortment Xj is Cj(Xj), which is increasing, convex in Xj and can be parameterized with a scalar cj such that ∂Cj(cj)/∂cj > 0 (Appendix A describes a realistic replenishment system that yields convex costs in assortment depth.) Let pj > 0 be the per-unit margin for all variants in category j1. Consistent with the notation for the assortment decisions, a variable name in bold letter denotes a vector of those variables; c = (c1, ..., cN) and p = (p1, ..., pN). There are different types of consumers in the market that are characterized by the contents of their shopping baskets. Let t be the index to the elements of the power set of J, {B : B ⊆ J}. Bt ⊂ J denotes a shopping basket that contains categories j ∈ Bt. Thenumber of type t consumers in the market is randomly distributed with mean λt. A consumer of type t purchases exactly one unit of a product from each category in her shopping list Bt. Consumers have perfect information about the offerings at the retail store and the outside alternative (i.e., X and Z). A type t consumer systematically evaluates the attractiveness of the retailer, At(X), and the outside alternative, At(Z), and chooses the alternative that maximizes her total utility from the shopping experience. Rhee and Bell (2002) show that consumers patronize many stores but they typically have a primary affiliation to a “main store” that captures the majority of their spending. The 1The assumption of identical absolute margins of all variants in a category is restrictive. However, it may be realistic in certain cases. For example, different color/size shirts of the same style have the same price tag. Moreover, Anderson et al. (1992) and Cattani et al. (2003) prove that when customers follow a MNL choice model, optimal pricing policy for a group of variants is an identical absolute mark-up policy. This theoretical result fully supports our assumption. 4choice between the retailer and the outside alternative in our model corresponds to the choice of a “main store”. Thus, customers in our model do not split their shopping between two stores. 2 Related Literature Interest in category management (CM) is high. According to a recent industry report, 83% of the grocery retailers view CM as the most important issue facing them (Progressive Grocer 1996). The shift from brand-centered management to CM resulted in a more profitable pricing structure by eliminating the competitive pricing between brands (AC Nielsen 1998, Basuroy et al. 2001, Zenor 1994). Our paper attempts to shift the discussion from brand level to the category level and raises questions about the interaction among categories. Chen et al. (1999) also study the impact of basket shopping consumers. They show that merchandising decisions should not be governed by accounting profits, but rather by a new construct they develop called marketing profits. Like us, they argue that simple techniques, based on readily available data, are needed to guide decision making. However, there are some significant differences between their work and ours. In their model each consumer type bases its store choice decision on the variety of a single category, what they call the lead category. Hence, expanding variety in category B has no influence on the store choice decision of category A lead customers. In contrast, our consumers base their decisions on the total utility of their basket, which may include multiple categories. As a result, there are minimal strategic interactions among categories in their model, whereas in our model the strategic interactions are strong and lead to both strategic substitutes and complements. A second key difference is how they improve decision making. They assume a store makes optimal shelf space decisions and then infer marketing profit parameters that would imply those decisions are optimal. They then use those marketing profit estimates to guide other merchandising decisions, such as advertising allocation. We use point of sales data to estimate basket profits, without assuming the retailer’s assortment is optimal, and then derive optimal assortment decisions in a decentralized regime. There are many different modeling approaches to consumer choice over multiple products. See Anderson, de Palma and Thisse (1992) for a review. We follow the approach taken by Guadagni and Little (1983) and others: we presume each consumer receives a random utility from each item in the choice set and the highest utility item is chosen. As a result, increasing the breadth and depth of the assortment in our model increases total demand. The findings in Dhar, Hoch and 5Kumar (2001) are generally consistent with that assumption. However, we recognize that our model does not explicitly account for other possible factors that influence the relationship between assortment variety and demand: the space devoted to a category and the presence or absence of a favorite item influence the perception of variety (Kahn and Lehmann 1991, Broniarczyk et al. 1998) as well as a the arrangement, complexity and presence of repeated items in an assortment (Hoch et al. 1999, Huffman and Kahn 1998, Simonson 1999). Although research has primarily focused on single category choice decisions, there is recent research that examines multiple category purchases in a single shopping occasion by modeling the dependency across multi-category items explicitly (see Russell et al. 1997 for a review). Manchanda et al. (1999) find that two categories may co-occur in a consumer basket either due to their complementary nature (e.g., cake mix and frosting) or due to coincidence (e.g., similar purchase cycles or other unobserved factors). Bell and Lattin (1998) show that consumers make their store choice based on the total basket utility. Bodapati and Srinivasan (1999) relates feature advertising to store traffic effects using a nested logit framework. In these papers and in ours, consumers first assign a utility to an anticipated market basket and subsequently use this utility to determine store choice. Fixed costs for each store visit (e.g., search and travel costs) provide an intuitive explanation for why consumers basket shop. Bell, Ho and Tang (1998) use market basket data to analyze consumer store choices and explicitly consider the roles of fixed and variable costs of shopping. We do not explicitly derive optimal baskets -we take them as given. A number of recent papers study assortment selection and stocking decisions for a group of substitutable products in a single category (e.g., van Ryzin and Mahajan 1999, Mahajan and van Ryzin 2001, Smith and Agrawal 2000, Kok and Fisher 2004) and several papers focus only on stocking decisions (e.g., McGillivray and Silver 1978, Parlar 1988, Netessine and Rudi 2003). Unlike our paper, they assume store traffic is exogenous. Agrawal and Smith (2003) study assortment selection and inventory optimization with consumers that purchase sets of complementary items (e.g., shirt and tie, only shirt, skirt and blouse, etc.). These papers do not consider simple heuristics nor compare their centralized decision making regime to a decentralized regime. We use game theory to study competitive interactions in our CM (decentralized) regime. Gruca and Sudharshan (1991) and Basuroy and Nguyen (1998) study a market share game based on the Multinomial Logit (MNL) model and demonstrate that certain conditions are needed for equilibrium 6to exist. Although our model of consumers’ product and store choice is based on a nested MNL model, our retailer’s share equation has the same form as a Multiplicative Competitive Interactions (MCI) model. Karnani (1985) studies an MCI market share model with several firms that compete in a single market through several marketing decisions, including price. Existence of equilibria is not guaranteed in his model, because the profit function of a single firm is not jointly concave in the marketing variables. Our model is similar to his, however we have several customer types corresponding to several markets and we do not include price as a choice variable. Finding the centralized solution in our model with a single customer type corresponds to finding the best response of a firm in Karnani’s model and we show that this is not straightforward. Monahan (1987) studies a model in which two firms compete with each other in several markets under an MCI model with a single marketing variable. Our model also has several markets, but the retailer’s shares in different markets (customer types) are interdependent and multiple marketing variables (i.e., variety levels in all categories) play a role in each market. Netessine and Zhang (2004) show that decentralized retailers selling strategic complements carry less inventory than optimal. We show that CM provides less variety than optimal in the presence of basket shoppers even though the interactions among categories in our model are not always strategic complements. 3 ConsumerChoice Our consumer choice model is based on a nested Multinomial Logit (MNL) framework. A consumer chooses between the retailer and the outside alternative based her expected utility with each option. Her total utility at the retailer (or the outside alternative) is the sum of her utilities from each category in her basket. In merchandise category j, a consumer’s utility from purchasing variant i in category j is uji = vji + ε where ε are i.i.d. according to a Gumbel distribution with zero mean and variance π2μ2/6, i.e., F(y) = exp£−e−(y/μ+γ)¤ , where γ is Euler’s constant (γ ≈ 0.5722). Without loss of generality, we order the variants in a category in decreasing expected utilities, i.e., vj1 ≥ vj2 ≥ .. ≥ vjIj . Let U(Xj) be a consumer’s utility from the purchase of one variant in category j with assortment Xj , i.e., U(Xj) = max{uji : i ∈ Xj}. Because the Gumbel distribution is closed under maximization, U(Xj) follows a Gumbel distributed with mean E[U(Xj )] = μ ln P i∈Xj evji/μ and scale parameter μ (Ben-Akiva and Lerman 1985). The analogous results follow for the outside alternative. Consider a consumer type with a single category basket, i.e., Bt = {j}. From the MNL formula, 7the probability the consumer chooses the retailer over the outside alternative is st(Xj) = exp (E[U(Xj )]/μ) exp (E[U(Xj )]/μ) + exp(E[U(Zj )]/μ) = Aj(Xj) Aj(Xj) + Aj(Zj), Aj(Xj) = Xi∈Xj evi/μ. (1) Now consider a customer with a multi-category basket. Her total basket utility is Lt(X) = P j∈Bt U(Xj), the sum of the utilities of the categories in her basket. Lt(X) is not Gumbel because the Gumbel distribution is not closed under addition. The store choice probability of the consumers can not be specified in closed form with the true distribution of Lt. To be able to use the MNL formula, we show in Appendix B that the distribution of Lt can be approximated with a Gumbel distribution. (In particular, the Kolmogorov-Smirnov statistic, the maximum distance between the two distributions, is fairly small across different parameter values.) As for empirical support, Bell and Lattin (1998) use the MNL framework to estimate the basket utilities from consumer basket data and report their model fits the store choice data well. Let Gt(X) be a Gumbel random variable whose mean and variance are the same with Lt(X), i.e., E[Gt(X)] = Xj∈Bt μ lnXi∈Xj evji/μ = μ ln Yj∈Bt Xi∈Xj evji/μ and V (Gt) = |Bt|πμ2/6. Hence the scale parameter of Gt is μp|Bt|. Consumer type t chooses the maximum of Gt(X) and Gt(Z) to decide where to shop, and from the MNL share formula st(X) = At(X) At(X) + At(Z) (2) where At(X) = expμ ln Yj∈Bt Xi∈Xj evji/μ,μp|Bt| = Yj∈Bt Aj(Xj) 1 √|Bt| Rewrite the share formula: st(X) = Q j∈Bt Aj(Xj)1/√|Bt| Q j∈Bt Aj(Xj)1/√|Bt| + Q j∈Bt Aj(Zj)1/√|Bt| (3) The MNL and the Multiplicative Competitive Interactions (MCI) models are presented as alternative formulations in text books and the choice between them depends on the particular application. Our share formula, (3), has the form of a MCI model although our consumer choice model is a nested MNL model. 84 Analysis In this section, we present a game theoretic analysis of category management (CM), which is our representation of the decentralized regime because each category manager seeks to maximize her own profit. We also characterize the optimal solution for the retailer (i.e., the centralized regime). The analysis of the CM game is complex because the best response functions are not monotone. Nevertheless, we provide equilibrium existence conditions and we characterize the equilibria. The centralized regime is also not well-behaved, yet we are able to provide some structure and monotonicity results. The expected profit in category j is πj(X) = pj P t|j∈Bt λtst(X) − Cj(Xj) Proposition 1 The retailer’s optimal assortment in category j is of the type {0, 1, 2, ..,xj} where xj ∈ {1, .., Ij}. Proof. The proof is by contradiction. Consider two products i and k where i < k. Suppose k ∈ Xj and i /∈ Xj and let X0j= Xj ∪ {i}\{k} Since vi ≥ vk, Aj(X0j) > Aj(Xj). We also have Cj(X0j) = Cj(Xj), because |X0j | = |Xj |. Hence πj(X1, ..,X0j, ..XN) ≥ πj(X1, ..,Xj, ..XN). van Ryzin and Mahajan (1999) prove the same result for a single category by explicitly modeling the inventory costs of each product in a newsvendor framework. As a result, we can think of the variety decision in each category in terms of the number of variants in the category, xj (as opposed to a set of variants). The analogous result holds for the outside alternative, zj . Redefine the attractiveness and share functions with these new decision variables. The variety levels at the retailer and the outside alternative are x = (x1, x2, .., xJ ), and z = (z1, z2, .., zJ ) where xj and zj ∈ {0, 1, .., Ij} for all j. Aj : {0, 1, 2, ..} → < and Aj(xj) = Pxj i=1 evji/μ. The basket attractiveness function is then At(x) = Q j∈Bt Aj(xj)1/√Bt and the retailer’s share is st(x) = At(x) At(x) + At(z) (4) Observe that Aj(xj) is nonnegative, increasing and concave in xj . Similarly At(x) is increasing and concave in xj for all j and t. Finally, we can rewrite the category profit function. πj(x) = pj P t|j∈Bt λtst(x) − Cj(xj). 9The assortment decision x is a vector of integers. Hereafter, we work with the continuous version of the problem: differentiability facilitates the derivation and presentation of the results and allows comparative statics; and existence cannot be guaranteed under integrality constraints. 4.1 Category management The common practice of category management (CM) is an example of a decentralized regime for controlling assortment because each category manager is charged with maximizing profit with his or her assigned merchandise category. Since basket shoppers’ store choice decision depends on the variety levels of other categories, category j’s optimal variety level depends on the vector of variety levels of the other categories denoted x−j (i.e., x−j = (x1, ..,xj−1, xj+1, ..,xN). Hence a game theoretic situation arises where category j employs a best response, defined as follows: the strategy xj(x−j) is category j’s best response to x−j if xj(x−j) = argmax xj ©πj(xj, x−j), s.t. 0 ≤ xj ≤ Ijª , ∀j (CM) Category managers do not actually need to know the λt parameters and the definition of the st functions. We expect them to find the variety level that maximizes the category profits (i.e., the best response function) given other categories’ variety levels. They would estimate a demand function, say dj(xj), as a proxy for P t|j∈Bt λtst(x) and then solve a single variable concave optimization problem to find xj(x−j). Note that dj(xj) depends on the variety levels of other categories. CM can be interpreted as an explicit non-cooperative game between the category managers, because each category manager is responsible exclusively for the profits of her own category. Alternatively, it can be interpreted as an iterative application of single category planning where each category’s variety level optimized assuming all other assortment decisions for the retailer are fixed. The following theorem establishes the existence of equilibrium and lays the groundwork for further analysis. Theorem 2 (Existence) A Nash equilibrium in the CM game exists and any Nash equilibrium is characterized by the following conditions. P t|j∈Bt pjλt ∂st(x) ∂xj − C0j(xj) = 0, j = 1..N. (5) 10Proof. Define πjxj (x) ≡ ∂πj(xj, x−j)/∂xj and πjxjxk (x) ≡ ∂2πj(xj, x−j)/∂xj∂xk : πjxj (x)= P t|j∈Bt pjλt ∂st(x) ∂xj − C0j(xj) (6) πjxjxj (x)= P t|j∈Bt pjλt ∂2st(x) ∂x2j− C00 j (xj) (7) As shown in Appendix C, At(x) is concave in xj ; therefore st(x) is concave in xj , for all t. Also C00 j (xj) ≥ 0 by assumption. Consequently, the category profit πj(x) is concave in xj . Existence of an equilibrium follows from Theorem 1.2. in Fudenberg and Tirole (2000). Although an equilibrium exists, numerical examples show that there can be multiple equilibria even in the N = 2 case. Figures 1 and 2 illustrate examples with one and three equilibria respectively. We also found examples with multiple equilibria for N >2. The shape of the reaction functions xj(x−j) helps us to understand the dynamics of the game from each category’s perspective. From (5) and the Implicit Function Theorem, ∂xj(x−j) ∂xk = − P t|{j,k}⊆Bt pjλt ∂2st(x) ∂xk∂xj, P t|j∈Bt pjλt ∂2st(x) ∂x2j− C00 j (xj) The denominator is always negative, therefore the sign of ∂xj(x−j)/∂xk depends on the sign of ∂2st(x)/∂xk∂xj for all t : {j, k} ⊆ Bt. We see from Equation (11) in Appendix C that ∂2st(x)/∂xk∂xj < (>)0 when At(z) > (<)At(x). Remark 3 i) For each category pair (j, k), z} ⊆ X−. Proof. i) Define X+t = nx ∈ 0. Let X+jk = {x ∈ X+t , ∀t|{j, k} ⊆ Bt}. In X+jk, πjxjxk (x) is positive, hence πj(x) is supermodular in (xj, xk). Similarly define X−t = nx ∈ Qj∈Bt Aj(zj)o and X−jk = {x ∈ X−t , ∀t|{j, k} ⊆ Bt}. In X−jk, πj(x) is submodular in (xj, xk). Notice that z} = {x|xj > zj for all j} ⊆ X−jk for all j, k. Hence {x ≥ z} ⊆ X−. 11In theoretical models with multiple activities, usually one type of interaction (either complements or substitutes) is assumed to hold everywhere or is found to hold everywhere. In our model however, the type of interaction between the categories depends on the attractiveness of all the shopping baskets that contain these two categories, which in turn depends on the variety levels of categories j, k, and other categories that co-exist in the shopping baskets with j and k. Inthe N = 2 case, since there is only one basket type with both j and k in it, we can tell exactly the sign of ∂xj(x−j)/∂xk in any region in <2. The categories are strategic complements if Aj(xj)Ak(xk) < Aj(zj)Ak(zk) and substitutes otherwise. As our analysis suggests, the reaction functions in Figure 1 are increasing-decreasing in the other category’s variety level. However, we can not partition the action space as clearly in the N >2 case, because we do not know the slope of the best response functions in xk for some j and k. By definition of equilibrium x satisfies (5) for all categories including j and k : P t|j∈Bt pj λt ∂st(x) ∂xj − C0j(xj) = 0 and P t|j∈Bt pkλt ∂st(x) ∂xk − C0k(xk) = 0. Now, ∂st(x) ∂xj = ∂st(xj, x−j) ∂xj < ∂st(xk, x−j) ∂xk < ∂st(xk, x−k) ∂xk = ∂st(x) ∂xj The first inequality follows from the concavity of st in xj and xj > xk. The second inequality follows from the supermodularity of st() and x−j < x−k. Also we have pj = pk and C0j(xj) ≥ C0k(xk). Hence the LHS of the equation for j is always strictly smaller than the one for k. Asaresult,both conditions can not be satisfied at the same time and x can not be an equilibrium. The action space defined in Theorem 4 is quite realistic under interpretation (I2) of the outside alternative, because x < z implies that the retailer’s market share is less than half of the whole market. Even in the original game with the unrestricted strategy space, if the cost of providing variety is too high and all the equilibria are in X+, the results of Theorem 4 apply. In a symmetric game, the categories have the same price, cost, competition, and demand vectors. Second part of the above Theorem rules out the asymmetric equilibria in a symmetric game (CM_R). The same result can also be established for the submodular region of the game (see part 3 of Proposition 11 in Appendix D), but we are only able to rule out asymmetric equilibria for the whole game in the case of two symmetric categories. Theorem 5 In the game CM with N = 2 and two categories are symmetric, there exists only symmetric equilibria. Proof. i) By the second part of Theorem (4) and part (iii) of Proposition (11), the only region that can have asymmetric equilibria is <2 − {x ≤ z} − X−. This region is a subset of X+ and it is composed of two distinct parts on each side of the diagonal, denoted F1 and F2 (see Figure 3 for illustration of these regions. Reaction functions are symmetric. If x1(x2) passes through one of 13F1 or F2, x2(x1) passes through the other and vice versa. Hence there cannot be an intersection in either F1 or F2. 4.2 Optimal solution In the centralized system, total store profits are optimized over all category variety levels. max x (Π(x) = NPj=1 πj(x), s.t. 0 ≤ xj ≤ Ij, ∀j) (OPT) Differentiate Π(x) with respect to xj. ∂Π(x) ∂xj = X t|j∈Bt pjλt ∂st(x) ∂xj − C0j(xj) +XN k=1 k6=j X t|j,k∈Bt pkλt ∂st(x) ∂xj (8) The marginal effect of xj on the total profit is composed of its impact on own and cross category sales. After reorganizing terms, the first order conditions for optimality are X t|j∈Bt Xk∈Bt pk λt ∂st(x) ∂xj − C0j(xj) = 0, ∀j (9) The first order optimality conditions are based on the total profit earned from each customer type, whereas the CM solution is based on the category profits. Since st(x) is concave in xj , ∂2Π(x)/∂x2j< 0, for all j and t, and the first order condition (9) characterize the unique optimal variety level xj for fixed x−j. However, we are not able to show that the joint optimization problem is unimodular, therefore the system of equations ∂Π(x)/∂xj = 0 for j = 1, ..,N is not sufficient for optimality. It is easy to find numerical examples where Π(x) is not jointly concave, even with N = 2. We start the characterization of the optimal solution by describing two special cases of problems. Note that Case A problems include all two category problems including the Case B problems. Case A N categories. Basket types have the following property: |{Bt : j, k, l ∈ Bt}| ≤ 1 for all j, k, l such that j 6= k, j 6= l, and k 6= l. Case B N = 2. Symmetric categories. All customers are basket shoppers (i.e., λt > 0 only for Bt = {1, 2}). The products in a category are equally popular (i.e., Aj(x) is linear). Cost of variety is linear (i.e., C00 j (x) = 0). 14Theorem 6 Consider the special case A. i) If a symmetric solution to the first order conditions of OPT (9) satisfies At(x) > 2τ −1 2τ+1At(z) where τ = 1/p|Bt| for any t, it is a local optimal solution and can not be part of a continuum of local optima. ii) There exist at most one symmetric solution to (9) in X−. Proof. i) A sufficient condition for a stationary point to be a local maximum is that the Jacobian of Πjxj = 0, j = 1..N is diagonally dominant, because a symmetric diagonally dominant matrix with negative diagonal entries is negative definite (Corollary 7.2.3 of Horn and Johnson, 1985). We need Πjxjxj (x) + Pk6=j |Πjxjxk (x)| < 0 and x ∈ X. Replace pj in the proof of Proposition 11 with Pl∈Bt pl and show that diagonal dominance is achieved if At(x) > 2τ −1 2τ+1At(z) is satisfied. Hence, in this interval Π(x) is jointly concave at the symmetric stationary points. ii) Following the same line of analysis we did for the game (CM), we can show that ∂Π(x) ∂xk∂xj < 0 in X−. Therefore, the solution to the first order condition for category j for fixed x−j is decreasing in x−j in X−. Decreasing reaction functions can intersect at the diagonal at most once. Theorem 7 Consider the special case B. Focus only on the symmetric solutions x = (x, x). The profit function is convex-concave in x, therefore either (0, 0) or the largest stationary point with positive profit is the global optimal solution. Proof. Total profit function is Π(x, x) = (p1 + p2)x2τ /(x2τ + z2τ ) − C1(x) − C2(x). The second derivative is given by (p1 + p2)2τx2τ −2z2τ (x2τ + z2τ )3 ¡x2τ (−1 − τ) + zτ (τ − 1)¢ whose sign is positive at x = 0, decreases with x, and is negative for large values of x. Hence the profit function is convex-concave in x. The function is decreasing for large x, therefore there is a local maximum in the concave part of the function, which is the global optimum if it yields positive profit. Similar to the decentralized solution, the theory of supermodularity enables us to characterize the properties of the optimal solution and provide comparative statics for the restricted problem. Theorem 8 (Restricted problem) Redefine the action space of the optimization problem (OPT) as max x (Π(x) = NPj=1 πj(x), s.t. 0 ≤ xj ≤ zj, ∀j) (OPT_R) 15i) The set of solutions to the first order conditions (9) of OPT_R has a smallest and a largest element that are monotone increasing in p and λ and decreasing in z and c. ii) The set of optimal points argmax{Π(x), s.t., 0 ≤ xj ≤ zj , ∀j} is non-empty, has a smallest and a largest element that are monotone increasing in p and λ and decreasing in z and c. Proof. i) The existence of a largest and a smallest equilibrium and the monotonicity of the set in the parameters follow from applying the theory of supermodular games to the first order optimality conditions, similar to the proof of Theorem 4. However, a stationary point may not be a local maximum. ii) The result on the set of optimal points follow from the optimization of a supermodular function (Theorem 2.8.3 in Topkis, 1999). 4.3 Comparison of the centralized and decentralized solutions Let Xcm be the set of Nash equilibria in the CM game. Similarly Xo is the set of stationary points of the optimal profit function, OPT. We assume the optimal solution is interior. The following theorems show that CM never finds the optimal solution as long as there are basket shoppers. Theorem 9 Suppose that there exists at least one consumer type with more than one category in their basket and positive demand rate, i.e., |Bt| > 1 and λt > 0. i) The set of Nash equilibria Xcm in the category management game, CM, does not contain the global optimal solution to OPT. Xcm does not contain any of the local optimal solutions either. ii) If data is symmetric across all categories, then there is a symmetric stationary point in Xo greater than any symmetric equilibrium in Xcm (and it is a local optimum if it satisfies At(x) > 2τ −1 2τ+1At(z)). iii) Consider the special case B. The optimal solution is greater than the largest symmetric equilibrium. Proof. Compare the first order conditions to the optimization problem (OPT) given by (9) and the game (CM) given by (6): Πxj (x) − πjxj (x) = XN k=1,k6=j X t|j,k∈Bt pkλt ∂st(x) ∂xj > 0 if there is one basket type with more than one category and positive demand rate. Therefore, no point x can satisfy both set of conditions, i.e., Xcm ∩Xo = ∅. ii) For fixed vector of variety levels of other categories, x−j,the solution to the first order conditions for category j (xoj(x−j)) is always larger than the best response of category j in the game (xcm j (x−j)). In the symmetric game, let the 16largest symmetric equilibrium have variety level xcm for all categories. It is sufficient to consider an arbitrary category. We have xoj(xcm −j ) > xcm j (xcm −j) = xcm. We also know that xoj(xcm −j ) does not go to infinity since it is decreasing in X−. Therefore, xoj(xcm −j ) will cross the 45 degree line at least once more and the intersection is a stationary point of (OPT), i.e., ∃x1 : xoj(x1−j) = x1 > xcm. iii) Follows from part (ii) and that the largest stationary point is the optimal solution in case B according to Theorem 7. Theorem 10 (Restricted Problem) Suppose that there exists at least one consumer type with more than one category in their basket and positive demand rate, i.e., |Bt| > 1 and λt > 0. The global optimal solution of the optimization problem OPT_R, xo, has strictly higher variety in at least one category than any of the Nash equilibria of the game CM_R, including the Pareto best equilibrium, i.e., ∃j, xoj> xcm j , ∀xcm ∈ Xcm. Proof. Let xo be the optimal solution to (OPT_R) and xcm be any equilibrium of the game (CM_R). By contradiction, suppose that xo < xcm. Π(xo) =Xj πj(xoj, xo−j) sjk and sk > sjk if and only if xo < z. Hence, the retailer prefers to have a higher proportion of basket shoppers among its customers of categories j and k when xo > z (when its market share is greater than 50% of its potential). This occurs because it is easier for a larger retailer to attract basket shoppers than a small retailer (basket shoppers choose based on multiple categories rather than one). The result implies that a retailer is better off with a collection of independent categories if xo < z and better off with basket categories if xo > z. The situation a retailer is in probably depends on how the outside alternative is interpreted. With interpretation I2, the outside alternative is the aggregate representation of all the other firms, so the retailer probably has less than 50% of the whole market and is better off with a collection of independent categories. With interpretation I3, the retailer probably has more than 50% of its market potential, so the retailer prefers to carry basket categories. I3 is the better interpretation if a retailer’s demand would increase by less than 100% if it were to carry a full assortment in every category. 5.2 Which categories should have more variety? Consider two categories with same total demand but one category is more of a basket category than the other. In which category should the retailer provide more variety? Let subscripts j,k, and l denote the individual category shoppers of the respective categories. Also jk and jl denote the consumers with shopping baskets {j, k} and {j, l}, respectively. Suppose the demand rate of 18all baskets with variant k are identical to those with l. The only exception is the rate of individual category shoppers (λk and λl) and basket shoppers of j and k or j and l (λjk and λkl). Let λk = Λ+δ, λjl = Λ − δ, λl = Λ − δ, λjl = Λ+δ where Λ ≥ δ ≥ 0. If δ = 0, categories k and l are identical, as δ increases, demand to each category remains constant, l becomes more of a basket category. By the implicit function theorem, ∂xck/∂δ has the same sign as ∂2Π(x) ∂δ∂xj ¯¯¯¯ xo = pks0k(xok) − (pj + pk) ∂sjk(xoj, xok) ∂xk Similarly, xclincrease with δ if pls0l(xcl) < (pj + pl) ∂sjl(xoj, xol) ∂xl If categories k and l are symmetric, then as δ increases from zero, xok and xolmove in reverse directions. In §4.1, we showed that ∂2sjl(xj, xl)/∂xj ∂xl > 0 if Aj(xj)Al(xl) < Aj(zj)Al(zl) and > 0 otherwise. Hence ∂sjl(xj, xl)/∂xl is an increasing-decreasing function of xj. There may be an interval of xojsay, (xoj,xoj), where the inequality is satisfied and ∂xol/∂δ > 0, i.e. the optimal variety level of the basket category is higher than the optimal variety of the independent category. For xoj< xojand xoj> xoj, the reverse is true. The intuition for this result is as following. If xj is too low, it is not possible to attract many basket shoppers by increasing the variety of the basket category only, so it is better to increase variety in the independent category. If xj is in that interval, the basket category should be assigned more variety. As xj gets too large, there is no need to increase variety in the basket category l because j’s variety level is already attracting many basket customers to category l. To illustrate this result, we generated a series of numerical examples by varying cj to control xcj. Similar analysis yields that the equilibrium variety levels display the same properties. xcm increases with δ when xcm j ∈ (xcm j ,xcm j ) which is defined by the region pls0l(xcm l ) < pl∂sjl(xcm j , xcm l )/∂xl. With symmetric categories pl < pj + pk, hence (xcm j ,xcm j ) ⊂ (xcm j ,xcm j ), i.e., there may be cases where the optimal solution assigns more variety to the basket category and the category management solution does the reverse. 6 Category management with basket profits The CM equilibrium solution emerges as the outcome of a natural iterative process: category managers set variety levels, store traffic and sales are realized, category managers reassess the 19demand function for their category and choose new assortments, etc. The same process occurs if the retailer does category by category optimization. Either way, the process converges to one of the CM equilibria. Despite its simplicity, we show in the next section that CM can significantly deviate from the optimal solution. However, it is not easy to implement the centralized optimal solution: that solution involves estimating the number of customers for all 2N basket types and an N−dimensional optimization of an ill-behaved function. In this section we introduce a decentralized heuristic that promises the best of both worlds (i.e., the simplicity of CM and a profit level close to that of the optimal solution). The main weakness of CM is that it fails to recognize the intercategory effects of variety decisions and underestimates the marginal benefit of variety. As we have seen, the marginal benefit of variety is quite complex. Consider basket shoppers that purchases from two categories, A and B. Increasing variety in A increases demand from these shoppers in both category A and B. But more variety in A may also warrant a change in the variety of B, depending on the current variety levels: variety should be added to B if they are acting as complements and less if they are substitutes. From the perspective of the manager of category A, an additional sale is only worth pA, but from the retailer’s perspective it is worth more. We approximate the true marginal benefit to the retailer with the weighted average of the gross margins across basket types. We call this new metric basket profits because it measures the total profit earned from a customer. Specifically, let ˆpj be the basket profit from category j : ˆpj = X t|j∈Bt λtXl∈Bt pl, X t|j∈Bt λt The manager for category j is then measured with the following profit function: ˆπj(x) = ˆpj P t|j∈Bt λtst(x) − Cj(xj). Each CM then chooses variety xBj(x−j) = argmax xj ©ˆπj(xj, x−j), s.t. 0 ≤ xj ≤ Ijª , ∀j. (CM_B) Note that all our results on the CM equilibria apply directly to the CM_B heuristic. If we compare the derivative of the CM’s profit function to the optimality conditions (9), we see that CM_B uses a weighted average ˆpj for all consumer types instead of using Pk∈Bt pk for consumer type t. This approximation should work well if ∂st(x)/∂xj for all t are close to each other, however, 20even in symmetric category examples, ∂st(x)/∂xj varies with the basket size. From a practical perspective, note that the basket profit for each category is easily computed from POS data: it is the average gross margin earned from customers who purchased a basket including that category. 7 Numerical Results This section reports on numerical study that focuses on the magnitude of the profit loss due to CM relative to the optimal solution and the performance of CM with basket profits. Group 1: We generated 72 symmetric scenarios from all combinations of the following parameters: p = 1 Aj(x) = x zj = {5, 10} N = {2, 3, 5} Cj(x) = cjx cj = {2, 4} Demand in each category is 100 units and demand is divided across baskets according to the basket ratio vectors given in Table 1. For example, the vector {.2, .6, .2} for N = 3 means that 20% of the demand goes to baskets of size one, 60% goes to baskets of size two, and 20% to baskets of size three. For category 1, there are two baskets of size two, {1,2} and {1,3} and 60 units of demand is equally divided among them. Hence, λ1 = 20, λ2 = 20, λ3 = 20, λ12 = 30, λ13 = 30, λ23 = 30, and λ123 = 20. The unique CM equilibrium has no variety in 12 out of the 72 scenarios, resulting in a 100% profit loss relative to the optimal solution. In 21 scenarios there are multiple CM equilibria, one of which was the zero equilibrium. In those cases we assumed the better equilibrium prevails. Table 2 presents summary data on the performance of CM: the average profit loss due to decentralization is 28% and on average variety is 44% less than optimal. The performance of CM deteriorates with more categories (N), higher outside variety (z), higher variety costs (c) and a higher proportion of basket shoppers. Group 2: To explore asymmetric categories, we focus on the N = 2 cases of Group 1. A total of 48 examples are generated from all combinations of zj ∈{5,10} and cj ∈{2,4} for the two categories, i.e., 16 examples for each of the three basket types. The average CM loss is 8% in the asymmetric examples in comparison to the 13% loss for the two symmetric category examples in Group 1. Table 3 presents results for CM with basket profits (CM_B) in comparison to traditional CM and the optimal solution for the examples with N = 2 from both Groups 1 and 2 and with N = 3 from Group 1. Like CM, CM_B may lead to multiple equilibria. We first consider the best 21equilibrium of CM_B. The maximum loss with basket profits is only 2.1% and the average loss is only 0.2%. Variety with basket profits is on average 4.6% higher than optimal. Furthermore, CM_B works equally well for asymmetric and symmetric scenarios. One drawback of the basket profits heuristic is that it could converge to a bad equilibrium in case of multiple equilibria. Table 3 shows that even the worst equilibrium of CM_B performs better than the best equilibrium of CM (i.e., average profit loss for worst of CM_B is 8.5% whereas it is 13.2% for best of CM). The reason for inferior performance is that all categories have zero variety in the worst equilibria in our experiments (CM_B usually has a unique equilibrium in asymmetric examples, and as a result performs well). Starting with a high variety level when a category is first introduced ensures that CM_B (or CM) converges to the best equilibrium. 8 Conclusion We study a retailer’s assortment planning problem with multiple categories and basket shopping consumers that choose between the retailer and an outside alternative. We investigate the retailer’s assortment decisions across categories under centralized and decentralized management regimes. We find that variety levels between categories can be either strategic complements or strategic substitutes. Nevertheless, we also find that decentralized assortment planning, as with category managers responsible for their own category’s profit, is likely to lead to lower than optimal variety and significantly lower profits than optimal. But a centralized optimal solution is almost surely not implementable in practice due to the complexity of the required data estimation and optimization. Therefore, we propose a decentralized regime, like category management, but instead of evaluating each category manager’s accounting profit, we measure their basket profits, where basket profits are estimated using point of sales data. We find that our basket profit approach provides nearly the optimal variety and optimal profit. Hence, although the presence of basket shopping consumers is known to create significant analytical complications for the assortment planning problem, a robust and simple analytical solution exists. A Example of a replenishment system with convex operating cost Consider a single category with x products and demand λ(x) = A(x) (A(x) + A(z))−1 where A0(x) > 0 and A00(x) ≤ 0. Item i’s demand rate is λi(x), where Pi λi(x) = λ(x). Total shelf space capacity is S and assume each item’s maximum inventory level is proportional to its demand 22rate, Si = Sλi(x)/λ(x). There are commercial algorithms that allocate shelf space in this way (see Bultez and Naert 1988 for references). In a continuous review inventory system with zero lead time an order is placed whenever the inventory level is zero and the average inventory level for a single product is Si/2. Total average inventory is S/2, hence inventory holding cost is independent of x. The number of orders per unit time for item i is λi(x)/Si(x) = λ(x)/S, i.e., the order frequency is identical across all items. The total number of orders in the category is xλ(x)/S, whose second derivative is 2λ0(x) + xλ00(x) S = A(z) (A(x) + A(z))3 (2A0(x)((A(x) + A(z) − xA0(x) + A00(x)(A(x) + A(z))) ≥ A(z) (A(x) + A(z))3 (2A0(x)A(z) + A00(x)(A(x) + A(z))) The inequality is due to the concavity of A(x). A00(x) ≤ 0 and A(0) = 0 implies A(x) ≥ xA0(x). If the x products have similar demand rates, A(x) is linear. A00(x) = 0 and the cost function is convex in x. With strictly concave A(x), the cost function is still convex if A(x) is not too concave. For example, if A(x) = lnx, the sign of the second derivative is determined by A(z)(−1+2x) −ln x, which is strictly positive for z ≥ e and x > 1. B Sum of two Gumbel distributed random variables The sum of two Gumbel distributions does not have a closed form distribution function. We approximated the sum of Gumbel distributed random variables with a Gumbel distribution. Here we discuss the quality of this approximation. One measure of similarity of two probability distributions is the Kolmogorov-Smirnov (K-S) distance, which is the supremum of the distance between the cumulative density functions. Consider the case with three Gumbel random variables, X,Y and Z with parameters (ηX, μX), (ηY , μY ), and (ηZ, μZ). The mean of X+Y is ηX +ηY +γ(μX +μY ) and its variance is π2μ2/6. We set the parameters of Z to have the same mean and variance with X + Y as follows. μZ = qμ2X + μ2Y and ηZ = ηX + ηY + γ(μX + μY − μZ) K-S distance is sup u |FX+Y (u) − FZ(u)| ≈ max p∈{0.01,..,0.99}¯¯FX+Y (F−1 Z (p)) − p¯¯ We computed FX+Y using numerical integration and searched for the maximum over percentiles for the combination of the following parameters: ηX = {10, 40}, ηY = {10, 40}, μX = {5, 20}, 23μY = {5, 20}. The K-S distance never exceeded 0.019 in these examples, which we believe is fairly small. It is also of interest to note that the K-S distance seems to be effected by only the ratio of μX/μY but none of the other parameters, reaching the maximum at μX/μY = 1. Figure 5 provides an example of the cumulative density functions of X + Y and Z. Finally, from the perspective of our model, we are interested more in how the resulting choice probabilities are affected with the approximation. Consider that X, Y, A,B are all Gumbel distributions, X + Y and A + B are approximated by Gumbels Z and C respectively. We compare Pr{X +Y < A+ B} and Pr{Z < C}. Notice that the latter one can be computed using the MNL formula. For the combination of the set of parameters above, the maximum difference in probabilities is 0.010, which is also fairly small and in the same order of magnitude with the K-S distance. Table 4 presents a set of resulting choice probabilities with both the true distributions and the Gumbel approximations. C Derivatives Let τ = 1/√Bt, Φ = At(x)+At(z) and Δ = At(z) −At(x). The first and second derivatives of the attractiveness function are ∂At(x) ∂xj = I{j∈Bt}τAt(x)Aj(xj)−1A0j(xj) ∂2At(x) ∂x2j = I{j∈Bt}τAt(x)Aj(xj)−1 ¡Aj(xj)−1A0j(xj)2 (τ − 1) + A00 j (xj)¢ ∂2At(x) ∂xj ∂xk = I{j,k∈Bt}τ 2At(x)Aj(xj)−1Ak(xk)−1A0j(xj)A0k(xk) The first and second derivatives of the share function are derived below. ∂st(x) ∂xj = I{j∈Bt} At(z) (At(x) + At(z))2 ∂At(x) ∂xj = I{j∈Bt}At(z) Φ2 τAt(x)Aj(xj)−1A0j(xj) 24∂2st(x) ∂x2j= At(z) (At(x) + At(z))3 Ã−2μ∂At(x) ∂xj ¶2 + (At(x) + At(z)) ∂2At(x) ∂x2j ! =I{j∈Bt}At(z) Φ3  −2 ³At(x)Aj(xj)−1A0j(xj)τ´2 +ΦτAt(x)Aj(xj)−1 ³Aj(xj)−1A0j(xj)2 (τ − 1) + A00 j (xj)´ =I{j∈Bt}At(z)At(x)Aj(xj)−1 Φ3 ¡−2At(x)Aj(xj)−1A0j(xj)2τ + Φ ¡¡Aj(xj)−1A0j(xj)2 (τ − 1) + A00 j (xj)¢¢¢ =I{j∈Bt}At(z)At(x)Aj(xj)−1τ Φ3 ¡Aj(xj)−1A0j(xj)2 (−2τAt(x) + (−1+τ ) Φ) + ΦA00 j (xj)¢ =−I{j∈Bt}At(z)At(x)Aj(xj)−1τ (At(x) + At(z))3 ¡Aj(xj)−1A0j(xj)2(Φ − τ Δ) − ΦA00 j (xj)¢ (10) ≤ 0. ∂2st(x) ∂xk∂xj = At(z) (At(x) + At(z))3 μ−2∂At(x) ∂xk ∂At(x) ∂xj + (At(x) + At(z)) ∂2At(x) ∂xk∂xj ¶ =I{j,k∈Bt}At(z) Φ3 τ 2At(x)Aj(xj)−1Ak(xk)−1A0j(xj)A0k(xk)(At(z) − At(x)) (11) D Statement and proof of intermediate step Proposition 11 Consider the special case A. i) If CM symmetric equilibrium x satisfies At(x) > (2τ −1) (2τ+1)At(z), for all t where τ = 1.p|Bt| , then x can not be part of a continuum of equilibria. ii) The game CM has at most one symmetric equilibrium in X−. iii) If categories are symmetric and there exists an equilibrium in X−, then it is the unique equilibrium in X− and it is symmetric. Proof. i) As we mentioned before, the game (CM) has multiple equilibria, but we use the uniqueness conditions as an argument in our proof. Showing that a best reply map (xj(x−j))j=1,..,N is a contraction mapping is sufficient for a game to have a unique equilibrium. A sufficient condition for a mapping to be a contraction is that the Jacobian of πjxj = 0, j = 1..N is diagonally dominant (Section 2.5., Vives 1999), i.e., πjxjxj (x) +Xk6=j |πjxjxk (x)|<0 P t|j∈Bt pj λt ∂2st(x) ∂x2j− C00 j (xj) +Xk6=j X t|{j,k}⊆Bt pj λt¯¯¯¯∂2st(x) ∂xk∂xj¯¯¯¯<0 In the special case A, ∩k6=j{t|j, k ∈ Bt} = ∅, and ∪k6=j{t|j, k ∈ Bt} ⊆ {t|j ∈ Bt}. So there is no baskets counted twice in the double summation. Hence, a sufficient condition for diagonal 25dominance is to show that ¯¯¯∂2st(x) ∂xk∂xj¯¯¯< −∂2st(x) ∂x2jfor all t, j, and k. From (10) and (11), we see that sufficient condition ¯¯¯∂2st(x) ∂xk∂xj¯¯¯< −∂2st(x) ∂x2j, ∀t may not hold in general. However, it holds when Aj(xj) = Ak(xk), A0j(xj) = A0k(xk), and (Φ − τ Δ) > τ |Δ|. In X+, the last condition is equivalent to At(x) > (2τ −1) (2τ+1)At(z) (the coefficient (2τ −1) (2τ+1) is approximately 0.17. Therefore the proposition applies to a large part of the strategy space. In X−, |Δ| = −Δ, (Φ−τ Δ) > −τ Δ is satisfied. Notice that the sufficiency condition for diagonal dominance is achieved without using the nonnegative terms −ΦA00 j (xj) and ∂2st(x) ∂x2jfor t : j ∈ Bt, k /∈ Bt in the argument. Due to the slacks not used in proving the sufficiency condition and the continuity of all the terms, we can argue (or formally prove) that diagonal dominance of the Jacobian is satisfied not only at the diagonal but also in an ε neighborhood of the diagonal when ε is chosen sufficiently small. Using this result, we define new games on smaller compact N-cubes around the diagonal of Operations Research. 49 334-351. [28] Manchanda, P., A. Ansari, S. Gupta. 1999. The "shopping basket": A model for multicategory purchase incidence decisions. Marketing Science. 18 (2). 95-114. [29] McGillivray, A.R., E.A. Silver. 1978. Some concepts for inventory control under subsitutable demand. INFOR. 16. 47-63. [30] Monahan, G.E. 1987. The structure of equilibria in market share attraction models. Management Science. 33 (2) 228-243. [31] Netessine, S., N. Rudi. 2003. Centralized and competitive inventory models with demand substitution. Operations Research. 51. 329-335. [32] Netessine S., F. Zhang. 2003. The impact of supply-side externalities among downstream firms on supply chain efficiency. Working paper. The Wharton School. University of Pennsylvania. [33] Quelch, J.A., D. Kenny. 1994. Extend profits, not product lines. Harvard Bus Rev. 72 153-160. [34] Parlar, M. 1988. Game theoretic analysis of the substitutable product inventory problem with random demands. Naval Research Logistics. 35. 397-409. [35] Progressive Grocer. 1996. Can retailer-controlled brands dominate category management? 75. A9-A10. [36] Rhee, H., D.R. Bell. 2002. The inter-store mobility of supermarket shoppers. J of Ret. 78 (4) 225-237. [37] Russell, G.J., D.R. Bell, et al. 1997. Perspectives on multiple category choice. Marketting Letters. 8 (3) 297-305. [38] Smith, S.A., N. Agrawal. 2000. Management of multi-item retail inventory systems with demand substitution. Operations Research. 48 50-64. 28[39] Simonson, I. 1999. The effect of product assortment on buyer preferences. J of Ret. 75 347-70. [40] Topkis D.M. 1998. Supermodularity and Complementarity. Princeton University Press.. [41] van Ryzin, G., S. Mahajan. 1999. On the relationship between inventory costs and variety benefits in retail assortments. Management Science. 45 1496-1509. [42] Vives, X. 1999. Oligopoly pricing: old ideas and new tools. Cambridge, MA. The MIT Press. [43] Zenor, M.J. 1994. The Profit benefits of category management. J of Mrkt Res. 31 (2). 202-213. 290369 12 150 3 6 9 12 15 Variety level in category 2 Variety level in category 1 Figure 1. A two category example with unique category management equilibrium. N=2, symmetric categories, pj=1, Aj(x)=x, Cj(x)=cjx, cj=2, zj=5 for all j. λ1=50, λ2=50, λ12=50. 0369 12 150 3 6 9 12 15 Variety level in category 2 Variety level in category 1 Figure 2. A two category example depicting the three category management equilibria and the optimal solution. N=2, symmetric categories, pj=1, Aj(x)=x, Cj(x)=cjx, cj=2.8, zj=5 for all j. λ1=0, λ2=0, λ12=100. EQ EQ1 EQ2 EQ3 Optimal Figure 3. A two category example illustrating the regions relevant to the proof of Proposition 5. N=2, symmetric categories, pj=1, Aj(x)=x, Cj(x)=cjx, cj=3, zj=10 for all j. λ1=100, λ2=100, λ12=100. 0369 12 150 3 6 9 12 15 Variety level in category 2 Variety level in category 1 Figure 4. A two category example depicting the unique category management equilibrium at zero and the optimal solution. N=2, symmetric categories, pj=1, Aj(x)=x, Cj(x)=cjx, cj=4, zj=10 for all j. λ1=0, λ2=0, λ12=100. EQ Optimal 20 40 60 80 100 0.2 0.4 0.6 0.81 gumbelCDF trueCDF Figure 5. Cumulative density functions of the sum of two Gumbel random variables and its Gumbel approximation. ηx=ηy=20, μx=μy=10. Table 1. Allocation of basket shoppers in numerical experiments. First entry in a vector is the percentage of shoppers with a basket of size one, the second entry is the shoppers with a basket size of two, and so on. Proportion of basket shoppers N = 2 N = 3 N = 5 (.8, .2, 0, 0, 0) (.5, .5, 0, 0, 0) (.6, .2, .2, 0, 0) (.2, .6, .2, 0, 0) (.2, .2, .6, 0, 0) (.2, .2, .2, .2,.2) (.2, 0, .6, 0, .2) (.2, 0, .2, 0, .6) (0, 0, .2, .2, .6) (.8, .2, 0) (.5, .5, 0) (.2, .8, 0) (.6, .2, .2) (.2, .2, .6) (0, .2, .8) low medium high (.8, .2) (.5, .5) (.2, .8) Table 2. Summary of numerical results. Profit loss, 1 -Πcm/Πo Decrease in variety level, 1 -xcm/xo 2 13% 31% 3 23% 41% 5 35% 51% low 14% 34% high 41% 55% low 14% 34% high 41% 55% Proportion low 4% 20% of basket medium 27% 47% shoppers high 51% 66% zNc Table 3. Performance of the category management (CM) and the basket profits heuristic (CM_B) in comparison to the optimal solution. (B and W denotes the best and worst equilibria of CM_B, respectively). N Data 1 -Πcm/Πo 1 -ΠB/Πo 1 -ΠW/Πo 1 -xcm/xo 1 -xB/xo 1 -xW/xo Symmetric 13.4% 0.2% 8.5% 30.6% -4.7% 4.0% Asymmetric 6.8% 0.1% 0.1% 26.5% -3.9% -3.7% 3 Symmetric 22.8% 0.3% 21.1% 40.8% -5.7% 15.5% 13.2% 0.2% 8.5% 31.8% -4.5% 4.0% 2 Average profit loss Average deviation in variety levels Average Table 4. Resulting choice probabilities using the true distribution of the sum of two Gumbel random variables and its multinomial logit approximation. (X,Y) (A,B) TRUE MNL (5,5) (10,10) 0.401 0.395 (5,10) (10,10) 0.458 0.456 (10,10) (10,10) 0.500 0.500 (5,20) (10,10) 0.542 0.544 (20,20) (10,10) 0.661 0.669 Mean Pr{X+Y>A+B}