THREE ESSAYS IN SUPPLY CHAIN MANAGEMENT by GREYS SOSIC B.Sc. (Mathematics), University of Zagreb, 1988 M.Sc. (Mathematics), University of Zagreb, 1996 A THESIS SUBMITTED IN PARTIAL F U L F I L M E N T OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY in THE F A C U L T Y OF G R A D U A T E STUDIES (THE F A C U L T Y OF C O M M E R C E A N D BUSINESS ADMINISTRATION) We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH C O L U M B I A July 2002 © Greys Sosic, 2002 In presenting this thesis in partial fulfillment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Operations and Logistics Division Faculty of Commerce and Business Administration The University of British Columbia 2053 Main Mall Vancouver BC, Canada V6T 1Z2 Date 11 Abstract The three essays in this thesis address various problems in the general area of supply chain management. In general, supply chain management is concerned with management of the flow of goods, information, and funds among supply chain members, such as suppliers, manufacturers, distributors, retailers, and consumers. As such, its scope includes timing and quantity of material flow, logistics, improving efficiencies in problems with several decision makers, etc. The first essay in this thesis considers the problem of improving coordination in a decentralized system of retailers, while the second one addresses stability and profitability of Internet-based supply exchange alliances. The third essay analyzes a logistics problem, of finding an optimal route for a capacitated vehicle which travels on a graph and which can perform pickups and deliveries. In the first essay, we study a three-stage model of a decentralized distribution system with n retailers who each faces a stochastic demand for an identical product. In the first stage, before the demand is realized, each retailer independently orders her initial inventory. In the second stage, after the realization of the demand, each retailer decides what portion of her residual supply/demand she wants to share with the other retailers. In the third stage, residual inventories are transshipped in order to possibly meet residual demands, and an additional profit is allocated among the retailers. We study the effect of implementing various allocations rules in the third stage on the levels of the residual supply/demand the retailers are willing to share with others in the second stage, and the tradeoff involved in achieving a solution which is also optimal for the corresponding centralized system. The second essay is concerned with the formation of Internet-based supply exchange alliances among three or fewer retailers of possibly substitutable products. We provide some conditions, in terms of product substitutability and quality of suppliers, which Ill would lead to the formation of a three member alliance, or a two member alliance, or no alliance at all. We also study the effect of alliance structure and quality of suppliers on the profit of a retailer. The third essay considers a vehicle routing problem with pickups and deliveries (VRPD problem) on some special graphs. Some vertices on the graph represent delivery customers, and other vertices represent pickup customers. The objective is to find a minimum length tour for a capacitated vehicle, which starts at a depot and travels on the graph while satisfying all the requests by the customers without violating the vehicle capacity constraint, and returns to a depot. We have developed linear time algorithms for the VRPD problem on a path and on tree graphs, linear and O (| V\ log | V\) algorithm for a VRPD problem defined on a path with parametric initial capacity, and quadratic and O (| V\2 log | V\) algorithms for a VRPD problem defined over a cycle graph. Table of Contents Abstract... ii Table of Contents iv List of Figures vii List of Tables viii Acknowledgements ix CHAPTER 1 Introduction 1 1.1 Supply chain management 1 1.3 Game-theoretical concepts 2 1.2.1 Non-cooperative games 3 1.2.2 Cooperative games 4 1.2.3 Monotonic allocation rules 7 1.3 Summary of contributions 8 CHAPTER 2 A three-stage model for a decentralized distribution system of retailers 11 2.1 Introduction 11 2.2 The A B Z distribution model 14 2.3 The three-stage model and some related models 17 2.3.1 A decentralized system without transshipments 19 2.3.2 A centralized system with transshipments 20 2.3.3 A decentralized system with transshipments 21 2.4 Game-theoretical concepts... 24 2.4.1 Core allocations for transshipment games. ; : 25 2.4.2 Monotonic allocation rules for transshipment games 25 V 2.5 Allocations based on dual prices 27 2.6 Core allocations 30 2.6.1 Two players 30 2.6.2 Three players 31 2.6.3 Four players 33 2.6.4 General case 35 2.7 Achieving a first best solution 35 2.8 Conclusion 37 2.9 Appendix 39 CHAPTER 3 Formation of alliances in Internet-based supply exchanges 56 3.1 Introduction 56 3.2 The model 60 3.3 Profit as a function of alliance structure 63 3.3.1 Two-retailer alliance •• 64 3.3.2 Three-retailer alliance 67 3.4 Preference for a partner 70 3.4.1 Preference for a partner in a two-retailer alliance 70 3.4.2 Participation in a two-retailer alliance when profit decreases 71 3.5 Stability criteria : 73 3.6 Stable coalition structures 77 3.7 Concluding remarks 81 3.8 Appendix 85 CHAPTER 4 The vehicle routing problem with pickups and deliveries (VRPD) on some special graphs 98 4.1 Introduction 98 VI 4.2 Preliminary and notation 99 4.3 The VRPD problem on a path 101 4.4 The VRPD problem on a tree graph 104 4.4.1 The case where s = t 105 4.4.2 The tree case where 5 and t are predetermined 106 4.4.3 The case where t is endogenously determined 107 4.4.4 The tree case with s and t endogenously determined 109 4.5 The VRPD problem on a cycle graph I l l 4.5.1 The VRPD (C, r, N) problem with s and / endogenously determined 112 4.5.2 The VRPD problem on a cycle graph when s and t are predetermined and s±t..\\4 4.5.3 The VRPD problem on a cycle graph when 5 and / are predetermined and s = r..l28 4.6 Appendix 129 Bibliography 140 List of Figures vu CHAPTER 4 Figure 4.1 Form(l) 1 1 7 119 Figure 4.2 Form (2) 120 Figure 4.3 Form (3) 121 Figure 4.4 Form (4) Figure 4.5 Example ^ 5 List of Tables V l l l CHAPTER 2 Table 2.1 Payoffs for a discrete transshipment game with two players 45 CHAPTER 3 Table 3.1 Conditions for an increase in a retailer i's profit in the alliance (ij) 66 Table 3.2 Conditions for an increase in retailers' profit when k joins the alliance (if) 68 Table 3.3 Conditions for an increase in i's profit when independent retailers join in (ijk).... 69 Table 3.4 Retailer i's preferences for pairing when A'', > A ' , 71 CHAPTER 4 Table 4.1 Demands in the vertices 125 Table 4.2 Lengths of the arcs 126 Table 4.3 Step 1, w(7/,) = 46 126 Table 4.4 Step 2, w(T2) = 46 127 Table 4.5 Step 3, w(T}) = 44 127 Table 4.6 Step 4, w(T4) = 50 127 Table 4.7 Step 5, w(T5) = 46 128 Acknowledgements IX First of all, I would like to thank Professors Daniel and Frieda Granot, my research supervisors, for their continuous support and encouragement through my years spent at UBC. They both provided me with the essential guidance, and I consider myself very lucky for the opportunity of working with them. I am extremely grateful to Danny for introducing me to the field of Game Theory and spending many hours discussing my research and reviewing my work. My thanks also go to Professors Derek Atkins and Charles Weinberg, who served on my supervisory committee and provided valuable comments on my work, and many other faculty members at U B C , who were always willing to offer their assistance. I am also grateful to Professors Luka Neralic and Sanjo Zlobec, who served on the supervisory committee for my Masters thesis in Zagreb, and provided me with the advice and guidance, that eventually resulted in my joining the Doctoral program at U B C . And finally, my deepest thanks go to my family - my parents, my sister, and my fiancee - who were always there when I needed them. Chapter 1 Introduction 1.1 Supply chain management The essays in this thesis address various problems in the general area of supply chain management. In general, supply chain management is concerned with management of the flow of goods, information, and funds among supply chain members, such as suppliers, manufacturers, distributors, retailers, and consumers. Although the term supply chain management became increasingly popular in recent years, some of the problems that supply chain management deals with are not as new. As an exam-ple, inventory control, which is nowadays a topic in supply chain management, was considered by scientists at the beginning of the 20th century, when Harris published two papers (1913, 1915) that dealt with decisions in inventory control. In addition to analyzing timing and quantity of material flow, which is the topic of multi-echelon inventory theory, research in supply chain management covers much broader topics, such as product design, production, contracts, performance measures and quality control, logistics, etc. While the early research in supply chain management analyzed mostly problems with the objective of minimizing the cost of a single decision maker, current work in 1 CHAPTER 1. INTRODUCTION 2 this area broadened the nature of the problems being considered. Thus, recent papers are often concerned with profit maximization instead of cost minimization, and the fo-cus has shifted from a single company to the more realistic case, wherein relationships among several companies are being studied. One of the important problems addressed by supply chain management today is improving efficiencies in models with several decision makers, where each decision maker is a member of the supply chain who optimizes his individual goals, which may lead to a solution that is not globally opti-mal (e.g. double marginalization). Situations with multiple decision makers required a new paradigm for modeling, and the use of game theory is becoming increasingly popular in this area. Thus, non-cooperative game theory is used for modeling com-petitive framework, wherein each decision maker is concerned with optimizing his individual objectives, while cooperative games are being used to study cooperative behavior among the companies that may lead to an increase in profit realized by com-panies involved. Since the first two essays in the thesis fall into this category and use game-theoretical framework, let us briefly introduce here some concepts from game theory. 1.2 Game-theoretical concepts We start with some definitions related to non-cooperative games, which are used as a framework for modeling competitive behavior among the firms. This subsection is mostly based on Fudenberg and Tirole (1991). We then proceed by introducing some elements from cooperative game theory, which will be used for modeling cooperation among the firms, and some monotonicity concepts, which will be used in the first essay. CHAPTER 1. INTRODUCTION 3 1.2.1 Non-cooperative games A game in a strategic form has three elements: the set of players N = {1,2,... ,n}, the pure strategy space Si for each player i, and payoff functions Ui(s) for each strategy profile s = ( s i , S 2 , . . . , sn), Sj 6 5j. A mixed strategy <7j is a probability distribution over pure strategies. Let z_i :— (zi,..., Zi_i, Zi+\,..., z^), V Z e i R n . • A mixed-strategy profile a* is a Aas/j equilibrium if, for all players i , Mi (^ ' ^ I i ) > VSi e Si. A pure-strategy Nash equilibrium is a pure-strategy profile that satisfies the same conditions. When a game has several "stages", we may want to impose some additional re-strictions on the Nash equilibria, in order to "pick" those equilibria that are more "credible" or "reasonable". More formally, we will say that a multi-stage game with observed actions is a game where all players knew the actions chosen at all previous stages, 0 , 1 , . . . , k — 1 , when choosing their actions at stage k, and where all players move simultaneously in each stage. Let hk+1 denote the history at the end of stage k, that is, the sequence of actions in the previous periods. Further, let G(hk) denote the game from stage k on with history hk, and let a strategy profile s\hk be defined in a following way: For each player i, Si\hk is the restriction of sz to the histories consistent with hk. • A strategy profile s of a multi-stage game with observed actions is a subgame-perfect Nash equilibrium if, for every hk, the restriction s\hk to G(hk) is a Nash equilibrium of G(hk). Besides considering only games wherein players act unilaterally, noncooperative framework can also be used for the analysis of coalition deviation. Some of the approaches are given below. CHAPTER 1. INTRODUCTION 4 • A strategy profile is said to be a strong Nash equilibrium (Aumann, 1959) if no set of players can jointly deviate and make all of its members better off. Un-like Nash equilibrium, which considers only unilateral deviations, strong Nash equilibrium considers deviations by all proper coalitions. Although applied to noncooperative environment, this solution concept requires some form of bind-ing agreement among the players - players have to follow strategies they have agreed upon, even if some of them might profit by deviating. • Coalition-Proof Nash equilibrium (Bernheim, Peleg and Whinston, 1987) in-volves "self-enforcing" agreements among the members of a coalition. That is, an agreement is coalition-proof if it is efficient within the class of self-enforcing agreements, where self-enforceability requires that no coalition can benefit by deviating in a self-enforcing way. Coalition-Proof Nash equilibrium is farsighted, in the sense that it takes into consideration possible future deviations by play-ers, but the attention is restricted to deviations that are immune to deviations by subcoalitions. In other words, it does not take into account the possibility that some members of the deviating coalition may further deviate with someone outside that coalition. 1.2.2 Cooperative games A pair (N,v), where N — {1,2,... ,n} is the set of players, and v : 2N -> IR is a function such that w(0) = 0, is called a (revenue) cooperative game, or an n-person game in coalitional form. A subset S C N is called a coalition, N is called the grand coalition, and v is called the characteristic function of the game. In general, v(S) represents the revenue that coalition S can achieve on its own. A coalition structure, B, is a partition on N. That is, B = {Bu ..., Bm}, B, C N for all i, U™ ^ = N, B3r\Bk = $,j^k. A mapping $ which assigns to every cooperative game (N,v) a subset $(u) C IRn is called a solution concept. $ is a one-point solution concept if $(v) assigns a single vector, cp = (cpi,..., cpn) £ MN, to every cooperative game (N, v).- We will refer to CHAPTER 1. INTRODUCTION 5 one-point solution concepts as allocation rules, and the value, <p, that an allocation rule assigns to a particular game (N, v) will be called an allocation. If J2N <Pi = V{N), we say that the allocation is efficient. A simple example of an efficient allocation rule is the egalitarian rule, which allocates an equal portion of the value of the grand coalition to each player, ipi = v(N)/n. An allocation cp is individually rational if <Pi > f ° r a u Some of the solution concepts which are often used and have some desirable properties are given below. • The fractional rule - it allocates a fixed portion of the value of the grand coali-tion to each player, ipi = jiv(N), ji > 0, Y,N7I — 1- Clearly, the egalitarian rule is a special case of the fractional rule with 7* = 1/n V i • The core (Gillies, 1959) - an allocation ip is a member of the core of (N,v) if it satisfies If $(w) is an element of the core for every cooperative game (N,v), then $ will be referred to as a core allocation rule. When core allocations are used, no subset of players has an incentive to secede from the grand coalition and form its own coalition, because they collectively receive at least as much as what they can obtain as a coalition. In general, the core can be an empty set. • Nucleolus (Schmeidler, 1969) - the unique allocation ip that lexicographically minimizes the vector of excesses e(S,tp) = v(S) — Y^sVi-, S C N, when these excesses are arranged in nonincreasing order. The nucleolus is always in the core when the core is nonempty, and it is a piecewise linear function of v. • Shapley value (Shapley, 1953) - an allocation rule that satisfies the following axioms: 1. Symmetry: for all permutations ir of N, Q^fav) = $i{v), where by irv we mean u(= nv) such that, for any S = i2, • • •, is}, «(Mi i ) ,7r( i2) , . . . ,7r(is)}) = v(S); TZ=1<Pl(v) = v(N). VS C N, (1.1) CHAPTER 1. INTRODUCTION 6 2. Null player, if i is a null player, i.e. v(SU {i}) = v(S) for all S C N, then $i(v) = 0; 3. Efficiency: EN $i(v) = "Wi 4. Additivity: <&i(v + w) = + for any pair of cooperative games (7V,w) and (N,w). An intuitive interpretation of Shapley value is as follows. Consider all possible orderings of players, and define a marginal contribution of player i with respect to a given ordering as his marginal worth to the coalition formed by the play-ers before him in the order, v({l, 2 , . . . , i — 1, i}) — v({l, 2,. . ., i — 1}), where 1,2,...,'/ — 1 are the players preceding i in the given ordering. Shapley value is obtained by averaging the marginal contributions for all possible orderings. This average is given by *.<«>= E ( i s | - i ) ' ( r i s | ) ! w 5 ) - ^ \ ( i } ) . d.2) {s-.ies} n-and it was shown by Shapley (1953) that (1.2) is the unique allocation rule which satisfies the above four axioms. Hart and Mas-Colell (1988) provide another axiomatization of Shapley value using consistency, and Young (1985) has developed still another axiomatization of Shapley value wherein a strong monotonicity axiom replaces the null player and additivity axioms. Young's notion of monotonicity is very relevant to our analysis of transshipment games in the first essay, and therefore it is discussed in more details in the next subsection. • A coalition structure core, introduced by Aumann and Dreze (1974), is de-fined with respect to a certain coalition structure B. In addition to allocat-ing to each coalition at least its value, every element of the coalition struc-ture core must allocate to each element of the partition B exactly its value, ZieBjW = v(Bj),VBJ<EB. CHAPTER 1. INTRODUCTION 7 1.2.3 Monotonic allocation rules We list three different types of monotonicity that are often encountered in cooperative games, as described in Young (1985): • Aggregate monotonicity - if the value of the grand coalition increases, while the value of all other coalitions remain unchanged, then no player should get less than before. Thus, if $ is aggregate monotonic then v(N) > w(N) and v(S) = w(S) VS C N ^(v) > $i(w) V i . • Coalitional monotonicity - if the value of coalitions containing a particular player i increase, while the value of coalitions not containing player i remain un-changed, then player i should not get less than before. Thus, <3> is coalitionally monotonic if for all i, v, w, • Strong monotonicity - if the value of coalitions containing a particular player i increase relative to the value of coalitions not containing i, then player i should not get less than before. Thus, $ is strongly monotonic if Apparently, the nucleolus does not satisfy any of the above conditions (Megiddo, 1974; Young, 1985), the fractional rule satisfies aggregate and coalitional monotonicity (Shubik, 1962; Young, 1985), while Shapley value is the only symmetric allocation rule that satisfies all of the above monotonicity conditions (Young, 1985). The following theorem is due to Young (1985): v{S) - v(S \ {i}) > w{S) - w(S \ {i}) VS > Mw). Theorem 1.1 No core allocation rule is coalitionally monotonic for a cooperative game with five or more players. CHAPTER 1. INTRODUCTION 8 For a strengthening of this result to games with four players see Housman and Clark (1998). Coalitional monotonicity is very important in cost and profit allocations, as it is noted, for example, by Shubik (1962) and Biddle and Steinberg (1984). Indeed, methods that do not satisfy coalitional monotonicity may induce players to increase their cost contributions and obtain lower cost allocations, or players may be induced to decrease their profit contributions and obtain higher profit allocations. However, as stated in the theorem above, coalitionally monotonic rules may result with allocations that are not members of the core. 1.3 Summary of contributions Each one of the three essays in this thesis is concerned with a different aspect of supply chain management. The first essay considers the problem of improving coordination in a decentralized system of retailers, while the second one addresses stability and profitability of Internet-based supply exchange alliances. The third essay analyzes a logistics problem, of finding an optimal route for a capacitated vehicle which travels on a graph and which can perform pickups and deliveries. In the first essay, we study a three-stage model of a decentralized distribution system with n retailers who each faces a stochastic demand for an identical product. In the first stage, before the demand is realized, each retailer independently orders her initial inventory. In the second stage, after the realization of the demand, each retailer decides what portion of her residual supply/demand she wants to share with the other retailers. In the third stage, the residual inventories are transshipped in order to meet residual demands, and an additional profit is allocated among retailers. Our model is an extension of the two-stage model of Anupindi, Bassok and Zemel (ABZ, 2001, 1999), which implicitly assumes that all residuals enter the transshipment stage. We show that allocation rules based bn dual solutions, which were used in the last stage of the A B Z model, may induce the retailers to hold back some of their CHAPTER 1. INTRODUCTION 9 residuals. We study the effect of implementing various allocations rules in the third stage on the values of the residual supply/demand the retailers are willing to share with others in the second stage, and the tradeoff involved in achieving a solution for the decentralized system which is also optimal for the corresponding centralized system. We show that, regardless of which allocation rule is being implemented, a completely decentralized management of inventories may result with residual losses. These losses may stem either from the formation of subcoalitions in the transshipment stage, or from strategic withholding of residuals. Clarifying the sources of these losses could guide the retailers in establishing a more cooperative and less competitive code of practice. The second essay is concerned with the formation of Internet-based supply ex-change alliances among three or fewer retailers of possibly substitutable products. In different industries, such as automobiles, chemicals, or retailing, competitors are join-ing forces in establishing electronic marketplaces in order to reduce inefficiencies in the purchasing process and cut the costs, by combining their buying power. Joining such an alliance forces a company to share its suppliers with others. It also leads to reduced costs, including those of possible rivals, since members share the development and operating costs. It may lead to a more intense competition among the increased number of suppliers, and it may further benefit an alliance member at the expense of companies left outside the alliance. Natural questions that could arise are, then, when would a firm prefer to take part in an electronic marketplace joint venture, when would it prefer that other firms, possibly rivals, join the venture, and what are the financial consequences of either joining an alliance or remaining independent? In an attempt to gain a better understanding of the issues, we have developed a model of three retailers whose products may have certain degree of substitutability. We provide some conditions, in terms of product substitutability and quality of suppliers, which would lead to the formation of a three member alliance, or a two member alliance, or no alliance at all. We also study the effect of alliance structure and quality of suppliers on the profit of a company. In the third essay we develop algorithms for a vehicle routing problem with pick-CHAPTER 1. INTRODUCTION 10 ups and deliveries (VRPD) on some special graphs. The V R P D problem is in general denned on a graph G = (V, E), where some vertices represent delivery customers who expect deliveries from a depot, and other vertices represent pickup customers who have available supply to be picked up and transported to a depot. The objective is to find a minimum length tour for a capacitated vehicle, which starts at a depot and travels in G while satisfying all the requests by the customers without violating the vehicle capacity constraint, and returns to a depot. V R P D problems have many applications. For example, it is reported by Casco et al. (1988) that the U.S. grocery industry has saved over $160 million a year in distribution costs since 1982, by al-lowing vehicles on their delivery routes to pickup large volume from suppliers. Other applications studied in the literature include pickup and delivery from Quality Stores (Yano et al., 1987), pickup and delivery for ocean-borne transportation, and pickup and delivery of inner-city under-privileged children to summer vacations at volunteer families living out of town (Mosheiov, 1994). We have developed linear time algo-rithms for the V R P D problem on a path and on tree graphs, linear and 0 ( | V | log \ V\) algorithm for a V R P D problem defined on a path with parametric initial capacity, and quadratic and 0 ( | U | 2 log |U|) algorithms for a V R P D problem defined over a cycle graph. Chapter 2 A three-stage model for a decentralized distribution system of retailers 2.1 Introduction In their recent papers, (2001) and (1999), Anupindi, Bassok and Zemel (ABZ) have analyzed a distribution problem with n independent retailers of an identical product. Each of the retailers faces a stochastic demand, and must order her inventory before the demand is realized. After the realization of the demand, some retailers may have residual supplies, and others may have residual demands. Thus, the retailers can gain additional profit if residual supplies are shipped to retailers with residual demands. A B Z have formulated this distribution problem as a decentralized two-stage dis-tribution model in which retailers make unilateral order decisions based on prior agreements as to how additional profit that result from transshipment of residual supplies is allocated. In the first, non-cooperative stage, each retailer orders her own 11 CHAPTER 2. A THREE-STAGE MODEL 12 inventory to satisfy her own demand, and in the second, cooperative stage, retailers transship goods to satisfy the residual demands and allocate the corresponding addi-tional profit. Naturally, the quantities ordered in the non-cooperative stage depend on the allocation rule used in the cooperative stage, and the allocation rule suggested by A B Z is based on a dual solution for the transshipment problem. Such an allocation is always in the core of the associated transshipment game, and therefore encourages the retailers not to form subcoalitions during the transshipment stage. Finally, A B Z were able to construct an allocation rule which induces the retailers to order amounts which coincide with orders that would have been placed in the corresponding central-ized distribution system and which also induces an allocation of the additional profit stemming from the transshipment stage based on a dual solution. As pointed out by A B Z , in the centralized model "...one seeks to implement both the inventory deployment decision and the shipping decision such that the perfor-mance (expected profits) of the entire system is optimized'1 (ABZ, 2001, p.9.), while in the decentralized model with coopetition, the "...various retail outlets belong to inde-pendent agents, who are interested in maximizing their own performance, rather than that of the entire system." (ABZ, 2001, p.11.) Thus, to the extent that the retailers in the decentralized distribution system are exclusively concerned with maximizing their individual profit, they should be able to unilaterally decide how much of their residual inventory, whether it is excess supply or excess demand, they are willing to share with the other retailers. Indeed, it is not clear whether allocations based on dual prices will always induce the retailers to share their total residual supply or residual demand in the cooperative stage. For example, could such an allocation induce some players to share less and, as a result, obtain larger allocation of the additional profit realized from the transshipment of the residual inventory? Or, in general, is there a core allocation that will induce the retailers to share their total residual supply/demand? In an attempt to answer these questions, we suggest in this essay a new decen-tralized distribution model that contains an additional stage, placed between the two stages in the A B Z model. Therein, retailers can decide, in a non-cooperative fashion, CHAPTER 2. A THREE-STAGE MODEL 13 how much of their total residual supply/demand they want to share with the other retailers in the cooperative stage. We have found that allocations based on dual solu-tions will not induce the retailers to share their total residuals with others. Further, we demonstrate that for four or more players there are no core allocations that will result in retailers sharing their total residual supply or demand, and that for six or more players there are no core allocations that will induce retailers to share their residuals in amounts that preserve the value of the maximum additional profit that could be generated from transshipments. On the other hand, monotone allocations, such as Shapley value or the fractional allocation, would lead to the desired result. Wo also show that there are allocations that induce players to share residuals in amounts that preserve the value of the maximum additional profit and lead to a solution which is also optimal to the centralized system, i.e. a first best solution. However, these allocations are not members of the core of the corresponding transshipment game. Although our model is most closely related to that of A B Z (2001), let us briefly point to some other relevant work. Among the papers that analyze the effects of centralization in a multi-retailor system, see, for example, Eppen (1979), who demon-strates the benefits of centralization using the newsvendor framework. There are several papers that study multi-retailer models wherein customers who cannot satisfy their demand with the stock on hand at, one retailer can search for the product at other retailers. Parlar (1988) analyzes an inventory problem with two substitutable products with random demands, where residual demand at one retailer can be satis-fied by the residual supply at the other retailer. Anupindi and Bassok (1999) analyze the effect that centralization of stocks have on the retailers, the manufacturer, and the system as a whole1. They prove that the benefits to the manufacturer depend on the extent of the search performed by the customers. Van Ryzin and Mahajan (1999) an-alyze a model of a two-echelon supply chain with competition among either the man-ufacturers or the retailers in one of the echelons, wherein vendor-managed-inventory and rotailer-managed-inventory are used as coordination mechanisms. Some of the results they obtained support and provide additional insights to conclusions derived by Anupindi and Bassok (1999). Lippman and McCardle (1997) study a competitive CHAPTER 2. A THREE-STAGE MODEL 14 newsboy model and examine the relationship between the equilibrium inventory levels and the allocation of the demand among the competing firms. We note, however, that the last four models differ from ours, wherein the retailers transship residual supplies in order to satisfy their local customers. Rudi et al. (2001) study transshipments be-tween two independent retailers and use transshipment prices to induce the retailers to choose the inventory levels that lead to joint-profit maximization. The plan of the essay is as follows. In the next section we present and critique the A B Z model. In Section 2.3, we describe our three-stage model and some related models. In Section 2.4 we present some game-theoretical solution concepts that are subsequently used in the essay. Section 2.5 analyzes allocations based on dual prices, while Section 2.6 analyzes general core allocations. Section 2.7 describes allocations that induce first-best solutions. Some concluding remarks are presented in Section 2.8. A l l proofs are given in the Appendix. 2.2 T h e A B Z distribution model Recall that the A B Z decentralized distribution model consists of two stages. In the first, non-cooperative stage, before the demand is realized, each retailer has to de-termine her own inventory position, and in the second, cooperative stage, after the demand is realized, the available inventory stock is shipped to locations with residual demands and the excess profit generated by those sales is allocated among the retail-ers. Individual inventory order decisions by the independent retailers in the first stage form a Nash equilibrium profile, and they are dependent on the allocation mechanism used in the second stage. The allocation mechanism used in the second stage is based on a dual solution of the transshipment problem, and it motivates retailers not to form subcoalitions during this stage. Formally, the basic variant of the A B Z model, which excludes the possibility of storing the stocks at commonly shared warehouses, can be described as follows. Let N = { 1 , . . . , n} represent the set of independent retailers of an identical prod-CHAPTER 2. A THREE-STAGE MODEL 15 uct, who face random demands and manage their own inventories. Let Ti,c\, and Vi denote, respectively, the retail price, cost, and salvage value for retailer i. Before the actual demand is realized, each retailer orders a certain quantity of stock Xi. Let Hx denote the residual supply and let Ex denote the residual demand for retailer i. Thus, Further, denote by Y^- and Uj, respectively, the amount of stock transshipped and the per unit cost of transshipment from retailer i to retailer j. The model assumes pooling of residuals - each retailer covers her own demand first using local inventory and only then the residual inventories are shipped to satisfy, if possible, any unmet demand at other locations. The model has two stages: 1. In the first, non-cooperative stage, before the demand is realized, each retailer must determine her starting inventory position Xi\ 2. In the second, cooperative stage, after the demand is realized, the residual inventories are transshipped in order to meet the residual demands, and the ad-ditional profit generated is allocated among the retailers. Naturally, the trans-shipment schedule should maximize the overall profit. Thus, for players in a coalition S C JV, the transshipment schedule Y^ is an optimal solution for the following problem: Hi = maxjXj — Di, 0} Ei = maxj/Jj — Xi, 0}. (2-1) i ? s ( X , D) := max Y E i j e s ^ j - vt - t^Yij subject to : T,jesYij < Ht, % e S Yij > 0, i,j G 5 . A B Z assume that not all customers may accept transshipments, which is captured by pij < 1. We will, however, for simplicity assume that p^ = 1. CHAPTER 2. A THREE-STAGE MODEL 16 Although the allocations of profit from transshipments are done after the real-ization of the demands, an agreement regarding the allocation mechanism must be reached before the demands are realized. A B Z required that the allocation mech-anism should have a core property. Thus, if tp;(X,D) denotes retailer i's share of the maximal additional profit that stems from an optimal transshipment of residual inventories, then E ? = i £ t ( X , D ) = RN(X,D) and £ l £ S cp,(X, D) > i ? s ( X , D ) for all S C N = { l , . . . , n } . Finally, retailer i's individual profit function can be written as Pi(X, D) = r% min{Xu A } + vlHi - C i I , + ^ ( X , D) , and the starting inventory positions, chosen by the various retailers, form a Nash equilibrium profile. A B Z (2001) were able to construct an allocation mechanism that is in the core, and which induces a Nash equilibrium solution wherein the retailers' starting inventory levels Xi coincide with optimal inventory levels in the centralized system. A critical implicit assumption of the A B Z model is that the total residual sup-ply/demand at every retailer enters the second stage of the model. That is, each retailer must share her total residual demand, if any, or she must be prepared to ship her total residual supply. However, it is not clear whether such a policy can be enforced in a decentralized system. In fact, it does not appear to be consistent with the basic premise in the A B Z model, wherein "...decisions of inventory ... and the financial decision of allocation of revenues/costs must be made in a way consistent with the individual incentives of the various independent retailers." (ABZ, 2001, Ab-stract.) To the extent that the independent retailers can elect not to share their entire residual supply/demand with the other retailers, it is not clear that withholding some of their residual supply/demand will not make them better off. Thus, it is the main objective of this essay to evaluate and analyze the implications of a strategic behavior by the retailers, regarding the residual supply/demand they are willing to share with others, on the A B Z model. In the remainder of this essay, we analyze whether it is reasonable to expect the CHAPTER 2. A THREE-STAGE MODEL 17 retailers to share their total residual supply/demand in the cooperative stage, as was implicitly assumed by A B Z . In fact, we show that when there are four or more retail-ers, there may not exist core allocations which will induce the retailers to share their total residuals, and when there are six or more retailers, there may not exist core allocations which will induce the retailers to share their residuals in amounts that preserve the maximum value of the profit that can be generated in the transshipment stage. Moreover, we demonstrate that when the demand facing each retailer is a continuous random variable, allocation rules based on dual prices, as used by A B Z , may essentially induce all retailers not to share any amount of their residuals in the cooperative stage. This, of course, would lead to no additional profit in the trans-shipment stage, and no pooling of residuals. On the other hand, we show that there exist monotonic allocation rules, such as Shapley value or the fractional allocation rule, which will induce the retailers to share their residuals with other retailers in amounts that lead to maximum additional profit. Moreover, we prove the existence of allocation rules that will preserve the expected individual profit for the retailers, and would lead to a total profit, in this modified decentralized system, that coincides with the profit from the corresponding centralized system. 2.3 T h e three-stage model and some related models In this section we describe the three-stage model introduced in this essay, together with some related models that are used for reference and comparison. We consider a set N = { 1 , . . . , n] of retailers of an identical product and assume that the retailers face random demands Di and manage their own inventories. We further assume that there are no capacity constraints - each retailer can order her optimal inventory level. As already mentioned, our model has three stages: 1. In the first stage, before the demand Di is realized, each retailer orders a certain CHAPTER 2. A THREE-STAGE MODEL 18 quantity of stock Xi. The decision is made independently of the other retailers, and it depends on the agreements used in the third stage. 2. In the second stage, after the demand is realized, each retailer decides how much of her residual supply/demand she would like to share with others in the third, cooperative stage. The actual residual supply, Hi, and the actual residual demand, Ei, for retailer i are defined by (2.1), and we denote by Hi G [0, Hi) and Ei G [0, Ei] the amount of residual that retailer i is sharing with others in the second stage. This decision is made independently of the other retailers, and it depends on prior agreements to be implemented in the third stage. 3. In the third stage, residual inventories are transshipped in order to meet residual demands, and the additional profit is allocated among the retailers. Thus, the first stage of both our model and A B Z model are identical; we have added a second stage in which, depending on agreements regarding the allocation of profit generated in the third stage, reached prior to the beginning of the first stage, retailers decide what portion of their actual residual supply/demand they would like to use in the cooperative stage; our third stage coincides with the second stage of the A B Z model, although it is implicitly assumed in the A B Z model that Ei = Ei and Hi = Hi. We will carefully analyze the implications of such an assumption and demonstrate that, in general, it may not be consistent with using core allocations in the third stage of the model, as was suggested in the A B Z model. Observe that we do not assume asymmetric information about the values of the residuals. Rather, we assume common knowledge of the actual values of the residuals, coupled with strategic behavior by the retailers as to how much of their residuals they are willing to share with others. Let ri,Ci, and Vi denote, respectively, the retail price, cost, and salvage value for retailer i, let Yij and tij denote the amount of stock transshipped and the unit cost of transshipment from retailer i to retailer j, and let Cij := rj — Vi — tij. We further denote by X = (XuX2,...,Xn), D = (Di,D2,Dn), and Y = {Yl3,i,j = l , . . . , n } . To simplify the notation, we will denote by Di,Hi,Ei both the random variables and their realizations; the interpretation of the symbol will be clear from the context. CHAPTER 2. A THREE-STAGE MODEL 19 Observe that only one value of the pair of actual residuals can be positive for a fixed retailer. Thus, Ei- Hi = Ef Hi = 0. We will refer to a retailer with Hi > 0 as a supply-player, and to a retailer with Ei > 0 as a demand-player. Further, the vector of shared residuals will be denoted by (H, E) = (Hi,..., Hn, Ex,..., En). In the next three subsections we consider a distribution system without cooper-ation, a centralized distribution system, and our decentralized distribution system. Results obtained are used to compare the three models. 2.3.1 A decentralized system without transshipments We briefly consider here a distribution system without any cooperation whatsoever among the retailers - each retailer is only concerned with her own demand, and no transshipments are made. In this case each retailer's individual profit is given by P?(X, D) = P9(XU A) = n mm{Xi, A} + - aXi, whose expected value is given by J° (X) = jf(Xi) fAl udFi(u) + XiF^Xi) + Vi XiFi(Xi) - \ X l udFi(u) Jo J L 0 = [(u - Ci) - (rt - vl)Fi(Xi)} Xi + (n - v,) / udF^u), Jo where Fi(x) = 1 - Fi(x). Clearly, Ji(X{) coincides with the objective function in the classical newsvendor problem. Thus, the stock level X? which maximizes the expected profit is given by Ci - CiXi Ti ~ Vi The corresponding maximal expected profit for retailer i is then Ci) - [Ti - Vi) n-Vii X? i) / udFi(u) Jo = (n-Vi) j udFi(u) Jo CHAPTER 2. A THREE-STAGE MODEL 20 2.3.2 A centralized system with transshipments In a centralized system, all decisions are assumed to be made by a single decision maker whose goal is to maximize the total profit of the entire system. For given inventory decisions, demand realizations, and a fixed transshipment pattern, the total profit can be written as F C ( X , D , Y ) = f> 4 mm{Xu A } + ^ - c,X 2] + £ {Tj - v{ - Uj)Yir Clearly, for given inventory decisions, the optimal shipping pattern should maximize the profit subject to residual supply and demand constraints as follows: P C ( X , D ) = m a x Y P c ( X , D , Y ) subject to : £ " = 1 Yi3 < Hi, i = l,...,n Z^Yij/pijKEj, j = l,...,n Yij > 0, i , j = 1,.. • ,n , where denotes the fraction of customers at location j that could not be satisfied from the stock on hand and are willing to wait for transshipments from location i. For simplicity, we assume that p^ = 1, i.e. all customers that could not be satisfied from the existing inventory at location j are willing to wait for transshipments from other locations. If we denote by (2.3) i ? c ( X , D) := max Y E?J=I(J*J - vt -subject to : T,]=i Yij < Hi, i = 1,..., n T?=iYij<Ej, j = l , . . . , n Ytj>0, " i,j = l...,n, then the profit-maximizing problem (2.2) can be written as P C ( X , D ) = E7=i[ri mm{Xi, Di} + ViHt - c ^ ] + P C ( X , D ) . (2.4) CHAPTER 2. A THREE-STAGE MODEL 21 Let RC{X) := E[R°(X,D)] and J C ( X ) := E[PC(X,D)}, and let X c denote the inventory levels that maximize the expected profit JC(X); we will refer to X c as a first best solution. The following theorem proves that the expected profit in a system without cooperation is never higher than the expected profit in a centralized system. Thus, centralization and cooperation never lead to lower expected profit (see also, e.g., Eppen, 1979; Parlar, 1988; and A B Z , 2001). Theorem 2.1 £ j < W ) < ^ ( X C ) - (2-5) i=l 2.3.3 A decentralized system with transshipments We next consider a decentralized distribution system, which is the main topic of our interest. In the decentralized model the retailers make their decisions with the goal of maximizing their own individual profit, even if that may result with a lower overall profit of the entire system. In our model, the first two stages, in which inventories are ordered and amounts of residuals to be shared with others are decided upon, are competitive. The third stage, in which residual inventories are transshipped, is cooperative. The solution concept applied in the first two stages is subgame perfect Nash equilibrium, which depends on the allocation rule used in the third stage. Let R(X, D , H , E , Y ) denote the additional profit that results from transshipments for given inventory decisions, X , demand realizations, D , shared residual supplies and demands, H and E , and shipping pattern Y . Further, using similar notation to that introduced in the previous subsection, let R*S(X, D , H , E ) denote the maximal resid-ual profit that can be generated for given inventory decisions, demand realizations, CHAPTER 2. A THREE-STAGE MODEL 22 and shared residuals for retailers in S C N. Thus, P £ ( X , D , H , E ) := max Y T,i,jesirj ~ vi - tij)Yij subject to : HjesYij < Hu ^ G S (2.6) Yij>0, i,jeS. The profit function for retailer i can be written as P ( X , D , H , E ) = r , m i n ^ , D{} + ViHi - ClXt + <pt(X, D , H , E ) , (2.7) where <Pi(X, D , H , E ) is the allocation of the maximal additional profit R*N(X, D , H , E ) that results from transshipments in the cooperative stage. We want tp to be efficient, i.e. to satisfy J2 V i ( X , D , H , E ) = R*N(X, D , H , E ) . (2.8) We say that ( H , E ) is a value-preserving sharing of residuals if R*N(X, D , H , E ) = i ^ ( X , D , H , E ) . (2.9) For simplicity, when the retailers use value-preserving sharing of residuals, we will write R*N(X,D) instead of R*N{X, D , H , E ) , P 2 ( X , D ) instead of P 2 ( X , D , H , E ) , and </?i(X, D ) instead of ^ ( X , D , H , E ) . Let R*N(X) := E[R*N(X, D ) ] denote the expected value of the corresponding maximal residual profit, and let J j ( X ) := E[Pi(X, D ) ] denote the expected value of the individual profit. Let us also denote by <Pi(X) the allocation to retailer i of the expected value of the maximal additional profit R*N(X). Besides being efficient, we want the allocation tp to be individually rational, i.e. to satisfy c ^ ( X , D , H , E ) > 0 or t # ( X ) > 0 for all i. The following proposition is a straightforward result of the above analysis. Proposition 2.2 For given inventory decisions and demand realizations, the set of optimal shipping patterns coincide for the centralized system (i.e., (2.3)) and the CHAPTER 2. A THREE-STAGE MODEL 23 decentralized system (i.e., (2.6) for S = N), in which the retailers share all their residuals with others. In addition, for value-preserving sharing of residuals, the following equation holds: X : P l ( X , D ) = P c ( X , D ) . (2.10) i=i In the first and the second stage, decisions about inventories and amounts of shared residuals are made individually by using solution concepts from non-cooperative game theory, namely Nash equilibrium and subgame perfection. For a given allocation rule in the cooperative stage, we have to determine inventory levels, X * , in the first competitive stage and amounts of residuals that retailers want to share with others, (H*,E*), in the second competitive stage. Given inventory levels X , let ( H A , E A ) denote the Nash equilibrium for amounts of shared residuals in the second stage. Clearly, the decisions ( H A , E A ) are made after the demand is realized, and should satisfy Pi(X, D , H A , E A j > P i ( X , D , Hu H A ; , Eu E A J Vi£ < Hu Ei < Ex, V^ e N. Next, let X * denote a Nash equilibrium for the inventory levels in the first stage, and suppose that the allocations used in the third stage induce value-preserving shar-ing of residuals. Then, the expected profit is a function of the inventory decisions only, and X * must satisfy Jj(X*) > J i (A^,X^j ) VXj , Vi € N, wherein the payoffs are determined by Nash equilibrium decisions in the second stage, ( H A ' * , E A * ) . Theorem 2.3 and Proposition 2.4 below, taken from A B Z (2001) (see also Fu-denberg and Tirole, 1991; Ba§ar and Olsder, 1995; and Karlin, 1968), provide the conditions that ensure the existence of a pure strategy Nash equilibrium for the A B Z decentralized distribution problem and can be shown to hold for any value-preserving sharing of residuals. Theorem 2.3 Consider the payoff' function J i (X) for retailer i. Suppose: 1. Jj(X) is simultaneously continuous in X , and CHAPTER 2. A THREE-STAGE MODEL 2. Jj(X) is unimodal in Xi for every X _ j . 24 Then there exists a Nash equilibrium in pure strategies for the inventory decision game in a decentralized system. Propos i t ion 2.4 7/P ; (X) is unimodal in Xi for every X _ i and the demand density functions are Poly a Frequency Functions then Jj(X) is unimodal in Xi for every X _ j . The following theorem demonstrates that the profit in the centralized system is never smaller than the total profit in the decentralized system (see also, e.g., A B Z , 2001). Theorem 2.5 n J C ( X C ) > ^ J , ( X * ) . 1=1 For value-preserving sharing of residuals, the expected profit is only a function of the inventory decision. The relationship between individual profit in the decentralized systems with and without transshipments is given by the following proposition. Propos i t ion 2.6 J,(X*) > (2.11) 2.4 Game-theoretical concepts In the third stage of the model, we need to transship residual supplies in order to meet residual demands, and to allocate the additional profit resulted from the transship-ments. The paradigm for the decentralized model in this stage is a cooperative game, introduced in Subsection 1.2.2. Therefore, we briefly present below some aspects of cooperative game theory which are relevant to our distribution problem. CHAPTER 2. A THREE-STAGE MODEL 25 2.4.1 Core allocations for transshipment games A transshipment game (N, v) is defined with respect to the optimal transshipment problem (2.6), and v(S) = R*S{X, D , H , E) , S C N. Hence, the retailers will also be referred to as players. Let cpi(X, D , H , E) denote an allocation of the additional profit to player i for given inventory decisions, demand realization, and shared amounts of residuals. Then, <Pi(X, D , H , E) is a core allocation if £ > 2 ( X , D , H , E ) > i ? * ( X , D , H , E ) VS C N, f > ( X , D , H , E ) = i r „ ( X , D , H , E ) . Core allocations provide an incentive to players not to secede from the grand coalition. It follows from Owen (1975) (see also Samet and Zemel, 1984 and A B Z , 2001) that allocation rules based on dual prices, (pi(X,-D,U,E) = aiHi + PiEi, (2.12) where a.x and are the dual prices associated with the constraints on Hi and Ei in the optimal transshipment problem (2.6) with S = N, are always core allocations. Although the core in general can be empty, as noted in Subsection 1.2.2, the core is always non-empty for transshipment games. 2.4.2 Monotonic allocation rules for transshipment games Before presenting our results, we need to introduce some new definitions. An allocation rule is called completely sharing if it induces all the retailers to share their total residual supply/demand with other retailers, and it is. called value-preserving if it induces all the retailers to share their residual supply/demand in amounts that do not result in a decrease in the total additional profit. Clearly, every completely sharing allocation rule is value-preserving, but the reverse does not always hold. CHAPTER 2. A THREE-STAGE MODEL 26 A player i is said to be relevant if her residual supply/demand makes a positive contribution to the optimal value that can be realized in the transshipment stage with shared residuals (H,E). This is illustrated in the following example. Example: Consider a case with two supply-players and two demand-players, wherein Hi = 6,H2 = 6, E3 = 7,E4 = 2, and r 3 - v i - tu = r 4 - v i - tu = 1, r3 - v2 - t 2 3 = r4 - v2 - t24 = 0. Since per unit additional profit that can be realized by shipping from retailer 2 equals 0, retailer 2 is not a relevant player in this case, and the maximum additional profit that can be realized is v(N) — 6. In addition, players 1 and 3 can realize the addi-tional profit of 6 without the participation of retailer 4, so the latter is not relevant either. Hence, this example has only two relevant players, retailers 1 and 3. Thus, a supply-player i is relevant if Hj < J2j-n Ej and r,- — Vi — Uj is strictly positive for some j such that Ej > 0; depending on the amount such a player i shares with others, we can have Y,N Hj < E N EJ,HN HJ = Y.N Ej> o r 12NHJ > T,NEJ-Similarly, a demand-player i is relevant if Y,j^iEj < J2j^Hj, and r; — Vj — tji is strictly positive for some j such that Hj > 0. Clearly, only relevant players need to be considered when analyzing value-preserving allocation rules. In our three-stage distribution model, it is important that completely sharing or value-preserving allocation rules are used in the third stage. Indeed, the use of allocation rules that are not value-preserving may induce players to share less than the actual value of their residual levels in order to increase their share of the profit. This may result in a decrease of the total additional profit, therefore making it impossible to achieve a first-best solution. Proposition 2.7 An allocation rule $ is value-preserving if for all relevant players CHAPTER 2. A THREE-STAGE MODEL 27 i and all transshipment games (N, v) and (N, w) v{N) > w(N) v{S) > w(S) \/S C N,i e S, v{S) =w(S) V S C N,i Thus, there is a certain similarity between value-preserving and coalitionally mono-tonic rules, introduced in Subsection 1.2.3. However, neither are all coalitionally monotonic rules value-preserving, nor are all value-preserving rules coalitionally mono-tonic. A similar relationship exists between coalitionally monotonic allocation rules and completely sharing allocation rules. That is, neither are all coalitionally mono-tonic allocation rules completely sharing, nor are all completely sharing allocation rules coalitionally monotonic. However, the following proposition holds. Propos i t ion 2.8 Shapley value and the fractional rule (where each player receives a positive fraction of the value of the grand coalition) are both coalitionally monotonic and value-preserving allocation rules. Although Young (1985) and Housman and Clark (1998) show that there are no general coalitionally monotonic core allocation rules for four or more players, in the following sections we try to determine whether it is possible to find value-preserving core allocations for our particular class of transshipment games. 2.5 Allocations based on dual prices As mentioned earlier, allocations based on dual prices, defined by (2.12), are always in the core. Therefore, since they are rather easy to compute, they are attractive as core allocation rules. Indeed, A B Z (2001) have used dual prices as allocation rules in the cooperative transshipment stage. However, as we show in this section, dual prices allocation rules are not value-preserving. Moreover, we show that there can be no Nash equilibrium in pure strategies in the second stage of our model, in which all CHAPTER 2. A THREE-STAGE MODEL 28 players are relevant and some of the players share positive amounts of their residuals. Thus, it could happen that no additional profit is generated in the transshipment stage if dual prices are used as allocation rules. For the remainder of the essay, we refer to transshipment games in which the total residual supply equals the total residual demand, J27=i H = J27=\ Hi, as balanced transshipment games. Consider the case with two players, wherein one player has a residual supply while the other has a residual demand. If dual allocations are used, the entire additional profit is allocated to the player with fewer resources. Therefore, each player would want to share a little bit less than the other one, and there will be no transshipment in equilibrium. This result is generalized in the following theorem. Theorem 2.9 When allocation rules based on dual prices are used in the transship-ment game and the demands are continuous random variables, there is no pure strat-egy Nash equilibrium profile in the second stage wherein some of the players share a positive amount of their residuals and with respect to which all players are relevant. For a discussion of mixed strategies Nash equilibrium for this problem, see the Appendix. Next, for transshipment games with general demand distribution functions, we have the following theorem. Theorem 2.10 There are no completely sharing or value-preserving allocation rules for transshipment games which are based on dual prices. Thus, allocations based on dual prices cannot be completely sharing or value-preserving, and they consequently cannot lead to a first-best solution in our three-stage model. This implies that the allocation rule used in A B Z (2001) for achieving a first best solution is not value-preserving, and can actually lead to zero additional profit if the retailers are free to "withhold" some of their residual supply/demand. CHAPTER 2. A THREE-STAGE MODEL 29 The failure of dual allocations to induce a distribution of residuals which captures all the potential additional profit persists even if retailers are allowed to redistribute, in an identical manner, residuals which were strategically withheld. Indeed, assume that the retailers agree that if "money was left on the table" after the initial distribu-tion of residuals, then they can pursue a second distribution of the leftover residuals in an identical manner to the initial distribution. That is, the retailers can make strate-gic choices at this additional stage, in a noncooperative manner, about the amount of leftover residuals they are willing to share, and dual allocations are used to determine the allocation of the additional profit. Now, clearly, the second stage at which the leftover residuals are redistributed is conceptually identical to a single distribution stage of residuals. Thus, for example, Theorem 2.9 is valid for this second distribution stage. In particular, it follows from Theorem 2.9 that it may very well happen that no leftover residuals whatsoever will be distributed in this stage. (For example, if there is only one supply-player and only one demand-player, then no residuals will be distributed in the second stage.) The payoffs to the retailers when they first embark on distribution of residuals is equal to their payoffs from the initial distribution of residuals, plus any additional payoffs that would accrue to them if leftover residuals are distributed in the second stage. However, as explained above, it may very well happen that no residuals are distributed at the second stage, and thus the payoffs from this stage may be zero. Consequently, the first stage at which residuals are distributed is conceptually identical to a single stage of distribution of residuals, for which Theorem 2.9 is valid. We can conclude, therefore, that two rounds of distribution of residuals, based on dual allocations, may not lead to value-preservation. This implies that we could, for example, extend Theorem 2.9 in the following manner: When allocation rules based on dual prices are used in the transshipment game and the demands are continuous random variables, there is no subgame perfect pure strategy Nash equilibrium pro-file in the second stage, in which residuals are distributed in two successive rounds, wherein some of the players share a positive amount of their residuals and with respect to which all players are relevant. CHAPTER 2. A THREE-STAGE MODEL 30 An analogous extension can be done for the case when the demand is discrete, and thus Theorem 2.10 can be extended to conclude that there are no completely sharing or value-preserving allocation rules for transshipment games which are based on dual prices and at which residuals are distributed in two successive stages. 2.6 Core allocations In this section, we study whether there exist general core allocation rules for trans-shipment games which are value-preserving. Clearly, we can restrict the analysis to instances where there exist at least one player with a residual supply and at least another player with a residual demand. We will first analyze cases with a small number of players and we will show that it is always possible to find completely sharing or value-preserving core allocation rules in these simple cases. However, we will subsequently show that in the general case with an arbitrary number of players, it is impossible to find value-preserving core allocation rules for transshipment games. For simplicity, when analyzing the amounts of shared residuals after the inventory decisions are made and the demand is realized, we will use the notation </3j(H, E) instead of ^ ( X , D , H , E) , or when it is clear what amounts we are referring to, we will only use cpt. 2.6.1 Two players Let us first assume that we have two players, and that each player gets a fixed positive share of the additional profit. As previously mentioned, the only interesting case is when there exist one supply-player and one demand-player, so without loss of generality we can assume that Hi > 0, E2 > 0. Recall that c^ - := r,- — vi — ty, and CHAPTER 2. A THREE-STAGE MODEL 31 consider an allocation of the form cp! = 7 - c 1 2 - m i n { # 1 , £ 2 } , ^ cp2 = (1 - 7) • C12 • mm{Hi,E2}, with 7 G (0,1). This allocation is in the core, as it can be seen from the following proposition. P r o p o s i t i o n 2.11 When n = 2, any efficient allocation rule that allocates to each player a non-negative share of the additional profit is in the core of the transshipment game. The allocation to each player in (2.13) is a non-decreasing function of the amount she shares with others. Thus, the player with a lower residual would share all of her residual, while the player with a larger residual is indifferent about the amount she shares as long as it is value-preserving. Clearly, this also includes the equilibrium profile in which both players share all of their residuals. 2.6.2 Three players Assume now that there are three players and that all of them have non-zero residual supply or demand. Any core allocation should satisfy the following conditions: <Pi > 0, 1 = 1,2,3 cpi + ipj > cli • max. {min{Hi, Ej},min{Ei, Hj}} , i = l,2,j>i (2-14) <Pi + tp2 + (P3 = v(N), where clJ' is defined by { Cij, if m&x{min{Hi, Ej},min{Ei, Hj}} = min{Hi, Ej} (2.15) Cji, if m&x{m'm{Hi, Ej},mm{Ei, Hj}} = m'm{Ei, Hj}. With more than two players and assuming general coefficients c^, the expression for v(N) becomes more complex. For example, with three players and assuming = 1 CHAPTER 2. A THREE-STAGE MODEL 32 for all i,j, v(N) = max{min{Hx,E2 +E3},mm{Ex,H2 +H3},min{H2,Ex +E3}, min{£ 2 , Hx + H3}, min{# 3 , Ex + E2}, m in{£ 3 , Hx + H2}}. For simplicity, for the remainder of this section we will assume = 1 for all As mentioned earlier, the only interesting cases are those with one supply-player and two demand-players, or one demand-player and two supply-players. Without loss of generality, assume there exists only one supply-player; if we have only one demand-player, we replace the E's with the H's, and vice versa, below. Next, denote the players so that Hx > 0, H2 = H3 = 0, Ex = 0, E3 > E2 > 0. Additional profit is achieved only by coalitions that contain player 1 and at least one of players 2 and 3. Further, since H2 = H3 = 0, it is easy to see that max {min{//i , Ei}, m in jE i , Hi}} = min{Hi,Ei}, i = 2, 3, max {min{.ff2, E3}, mm{E2, H3}} = 0, and max {mm{HuE2-r E3},mm{Ex,H2 +H3},mm{H2,Ex +E3}, min{£ 2 , Hx + H3}, mm{H3, Ex + E2}, min{E3, Hx + H2}} = min{Hx,E2 + E3}. It follows from (2.14) that if ip is a core allocation for the game described above, then the following relations must be satisfied: <Pi > 0, .> = 1 ,2 ,3 <px + (pi > mm{Hx,Ei} i = 2 ,3 , (2-16) ^1 + ^2 + ^3 = min{ifi , E2 + E3}. Now consider an allocation ip defined by ipx = mm{Hx,E2}, p2 = min{Hx,E2 + E3} - mm{Hx,E3}, tp3 = min{Hx,E3} - min{Hx,E2}. CHAPTER 2. A THREE-STAGE MODEL 33 It is easy to verify that such an allocation satisfies (2.16), and thus it is always in the core. Further, for each player, her allocation is a non-decreasing function of the amount she shares with others. Thus, players with lower residuals would share all of their residuals, while players with higher residuals are indifferent about the amount they share as long as it is value-preserving. Clearly, this also includes the equilibrium profile in which all players share all of their residuals. 2.6.3 Four players Assume now that we have four players and that all four players have non-zero resid-ual supply or demand. We consider two different cases: one supply-player (resp., demand-player) and three demand-players (resp., supply-players), and two supply-players and two demand-players. O n e s u p p l y - p l a y e r a n d t h r e e d e m a n d - p l a y e r s Without loss of generality, we can assume that only one player has a residual supply; if we have only one demand-player, we should replace the E's with the iPs , and vice versa, below. Denote the players so that Hi > 0, H2 = H3 = H4 = 0, Ei = 0, E4 > E3 > E2 > 0. Similarly to the case with n = 3, <p is a core allocation if the following relations are satisfied: <P\ + Vi Vi + Vi + Vi > 0, i = l ,2 ,3,4 > minimi , z = 2,3,4 1 1 (2.17) > m i n { # i , £ i + £,•}, i,j = 2,3,4, i<j + tp4 = min{ifi , E2 + £ 3 + £ 4 } -CHAPTER 2. A THREE-STAGE MODEL 34 Now consider the following allocation: cpi = mm{Hi,E2 + E3} V ? 2 = m i n { i f i , E2 + E3 + E4} - min{HuE3 + E4} tp3 = m'm{Hi,E3 + EA] — m'm{Hi,E2 + EA] cp4 = mm{Hl,E2 +E4} - mm{HuE2 +E3}. As in the case with n = 3, it is easy to verify that such an allocation satisfies (2.17) and thus it is always in the core. Further, for each player, her allocation is a non-decreasing function of the amount she shares with others. Thus, players with lower residuals would share all of their residuals, while players with higher residuals are indifferent about the amount they share as long as it is value-preserving. Clearly, this also includes the equilibrium profile in which all players share all of their residuals. Two supply-players and two demand-players We have demonstrated above that we can always find a completely sharing alloca-tion for the case of four players with only one supply-player; however, we show below and in the Appendix that when there are two supply-players and two demand-players, completely sharing allocations may not exist. Theorem 2.12 There are no completely sharing core allocation rules for transship-ment games with four or more retailers. From Theorem 2.12, we conclude that one cannot always find a completely sharing core allocation for the case of four players. However, we still might be able to find value-preserving core allocations for this case. Indeed, for an example of a value-preserving core allocation for n = 4 with two supply-players and two demand-players, see Appendix. In order to show that there are no coalitionally monotonic core allocation rules in games with four players, Housman and Clark (1998) have constructed the fol-lowing example: N = {1,2,3,4}, v(S) = 0 if \S\ = 1, u({l,2}) = v({3,4}) = 0, CHAPTER 2. A THREE-STAGE MODEL 35 v(N) = 2, and v(S) = 1, otherwise. Observe that this game corresponds to a trans-shipment game with two supply-players and two demand-players where Hi = H2 = 1, E3 = E4 = 1. This implies that there are no coalitionally monotonic core allocation rules for a transshipment game with two supply-players and two demand-players. However, as shown in the Appendix, one can still construct a value-preserving core allocation rule for such a game. 2.6.4 General case Finally, with six or more players, it may be impossible to find value-preserving core allocations. Theorem 2.13 There are no value-preserving core allocation rules for transshipment games with six or more retailers. 2.7 Achieving a first best solution Dual solution allocation rules or, in general, core allocation rules, would tend to prevent the creation of subcoalitions in the transshipment stage. However, as it was established in the last two sections, they will usually induce retailers not to share their residual inventories in the transshipment stage in a way that is optimal for the system as a whole. By contrast, Shapley value or the fractional allocation rule are not core allocation rules. However, they will induce value-preserving sharing of residuals. Thus, Shapley value and the fractional allocation rule induce sharing of residuals in amounts which are optimal for given inventory decisions. We next discuss whether their implementation in the cooperative stage would lead to inventory decisions in the first stage, which are optimal for the centralized system. Let us first consider the value-preserving core allocation rule from Subsection 2.6.1 with n = 2; without making assumptions about the residual supplies and the residual CHAPTER 2. A THREE-STAGE MODEL 36 demands, the allocations to the players can be written as <pi = 7i ' c i 2 • mm{HuE2} + (1 - 7 2 ) • c 2 i • min{H2, A}, ip2 = (1 - 7 l ) • C l 2 • mm{HuE2} + 7 2 • c 2 i • min{H2, Ei}. A B Z (1999, Theorem 3.2) provide sufficient conditions for achieving a first best so-lution in the two retailers case. These conditions require that a certain relationship between a first best solution, X c , and a non-cooperative solution, X°, be satisfied, and four integrals have to be calculated to determine the appropriate values of ji and 72, which would lead to a first best solution. Thus, when using allocations of residual profit, the process of determining value-preserving core allocations which achieve a first best solution can be rather elaborate even with only two retailers. Furthermore, since the above allocation coincides with Shapley value when 71 = 7 2 = 1/2, we can conclude that neither the fractional rule nor the Shapley value always lead to a first best solution. A simpler approach to achieve a first best solution is used in A B Z (2001). Therein, allocations of residual profit are replaced with allocations of the total profit of the entire decentralized system. Following the lead of A B Z (2001), the following theorem presents a value-preserving allocation rule that leads to a first best solution and is easy to implement. Theorem 2.14 The allocation rule defined by <Pi{X, D , H , E) = 7 i J2 Pj{X,T>, H , E) - [n min{A^, A } + - c ^ ] , (2.18) 3=1 with 7j G (0, l ) , E j = i 7 j = 1; i-s a n efficient value-preserving allocation rule which induces the inventory levels in a first best solution to be a Nash equilibrium profile. It follows from (2.5) and (2.11) that players should expect larger individual profit by cooperation, since it generates an additional profit. However, (2.11) assumes individual rationality. Now, consider the egalitarian rule for the allocation of the total profit, P i ( X , D ) = P c ( X , D ) / n , that is obtained from (2.7) and (2.18) for 7 i = 1/n. CHAPTER 2. A THREE-STAGE MODEL 37 This allocation differs from the allocations discussed earlier, since it allocates the total profit and not only the residual profit. Hence, it may fail to satisfy individual rationality. Indeed, for J c ( X c ) / n < Jf(X^), the allocation of the residual profit to player i, c p i ( X c ) , could be negative. Consequently, player i can expect a larger individual profit if she acts alone, and therefore she may be reluctant to cooperate. To induce cooperation, we can, for example, use coefficients, 7;, which are proportional to the expected individual profit, as suggested by Gerchak and Gupta (1991). Namely, P 2 ( X , D ) = ^ | ^ P C ( X , D ) . Clearly, it follows from (2.5) that for this allocation J i ( X c ) > Jf(Xf), i.e. the ex-pected residual allocation vector c/?(X c) satisfies individual rationality constrains. 2.8 Conclusion In this essay we have presented and analyzed a three-stage model of a decentralized distribution system of retailers. In the first stage, each retailer unilaterally decides on the amount of inventory to order to satisfy her customers. In the second stage, the retailer decides how much of her residual supply/demand she would like to share with the other retailers, and in the third stage residual supplies are shipped to retailers with residual demands, and the additional profit is allocated among the retailers. Naturally, the decisions by the retailers in the first two stages, which are done in a "non-cooperative" fashion, depend on the allocation rules used in the third stage. We have shown that Shapley value and the fractional allocation of residual profit induce value-preserving sharing of residuals by the retailers, which leads to the best result for given inventory decisions. We have further shown that the fractional allo-cation rule defined by (2.18), which allocates the total profit of the system, leads to a first best solution. Its coefficients, ji, may have to be somewhat modified, as dis-cussed in the last section, to ensure that it is individually rational. Clearly, though, neither Shapley value nor the fractional allocation rule are, in general, core allocation CHAPTER 2. A THREE-STAGE MODEL 38 rules. Thus, they may fail to discourage the formation of subcoalitions during the transshipment stage, which could result with lower total additional profit from the pooling of residual inventories Our model is an extension of A B Z two-stage model, wherein it is assumed that every retailer will share her entire residual supply/demand with the rest of the retail-ers, and the allocation rules are dual solutions of the corresponding transshipment problem. The advantage of such allocation rules is that they are contained in the core of the transshipment game, which will reduce the likelihood that subcoalitions will be created that would pursue transshipments exclusively among members of the same subcoalition. However, as demonstrated in this essay, allocation rules based on dual solutions may induce retailers not to share all of their residual supplies/demands with the other retailers. In fact, it could happen that retailers will not share any of their residual inventories with one another, resulting with no additional profit whatsoever, because residual inventories will not be transshipped. Similarly, it was shown that whenever the number of retailers is at least six, core allocation rules may induce non value-preserving sharing of supply/demand residuals. Thus, core allocation rules may reduce the additional profit that can be realized in the transshipment stage. One of our main conclusions, therefore, is that regardless of which allocation rule is being implemented, a completely decentralized management of inventories may result with residual losses. These losses may stem either from the formation of subcoalitions in the transshipment stage, if value-preserving and thus non core allocations are used, or from strategic withholding of residuals, if core and thus non value-preserving allocations are used. Clarifying the sources of these losses could guide the retailers in establishing a more cooperative and less competitive code of practice. Further, it could also, hopefully, be used by the supplier(s) to design and introduce effective incentive schemes which would reduce or eliminate these losses. We note here that our results may change if a retailer is allowed to manage demand by changing his retail price, possibly after the realization of the demand. Thus, CHAPTER 2. A THREE-STAGE MODEL 39 instead of having only the option of sharing his residual inventory with other retailers in the third stage of our model, a retailer with a residual supply may be able to sell all or part of it himself, at a different price. We think that this might be an interesting topic for a future research. 2.9 Append ix Proof of Theorem 2.1: It is easy to see that (2.4) is equivalent to P C ( X , D ) = E ? = i i ? ( X , D ) . + RC(X, D ) , and thus we have J C ( X ) = £ ? = 1 J ° ( X ) + P C ( X ) . If we denote by X ° = . . . , X°), then t < 14W) + P C ( X ° ) = J C ( X ° ) < J C ( X C ) , i=l i=l where the last inequality follows from the definition of X C as a vector that maximizes the expected profit, J c , for the centralized system. • Proof of Proposition 2.2: From the definitions of the additional profit in the centralized and decentralized case, it follows that (2.3) and (2.6), for S = N and under the assumption that the retailers share all their residuals, define the same problem. In both cases, transshipments that maximize additional profit subject to the same constraints are selected. Thus, for every inventory level and demand realization we have P C ( X , D ) — R*N(X, D , H , E ) , and it follows from (2.9) that, for value-preserving sharing of residuals, P C ( X , D ) = ^ ( X , D ) . (2.19) CHAPTER 2. A THREE-STAGE MODEL 40 Further, (2.7) and (2.8) imply that £ P i ( X , D ) = ^ [ r i m i n g , A } + ^ i - c i ^ i + ^ ( X ) D ) ] (2.20) i = i i = i = JT [n mm{Xu A } + - ClXt] + R*N(X, D) . (2.21) However, (2.19) implies that (2.21) is equivalent to (2.4), and the proof follows. • Proof of Theorem 2.5: Since value-preserving sharing of residuals lead to the highest residual profit value among all feasible amounts, it is enough to show that the statement holds for value-preserving sharing of residuals. J C ( X C ) = max x ^[Er=i [^ ra in{A: I ,A} + ^ - c i X i ] + i l c ( X , D ) ] > E [ZtAri min{A7, A } + vxH* - ClX*} + P C ( X * , D)] = E [ E ? = 1 h min lX* , A } + ViH! - Q I * + ^ ( X * , D)]] = E?=iJi(X*). Proof of Proposition 2.6: jt(x*) > uxlxu) = / ^ ( A ^ X ^ D ) ] = EinmmiX^D^+v^-c^ + ViiX^XU,!))} ' = J j ' ^ J + ^ ^ . X i . D ) ] > J?(Xf), where the first inequality follows from the definition of Nash equilibrium, and the last inequality follows from individual rationality of profit allocations. • Proof of Proposition 2.7: Let us consider an arbitrary transshipment game (N,v), with shared amounts of residuals Ei, Hi, and let w denote the characteristic function of CHAPTER 2. A THREE-STAGE MODEL 41 the game in which an arbitrary relevant player i shares less of her residual with others, so that v(N) > w(N). Without loss of generality, we can assume that i is a supply-player. Then, there exists an e > 0 such that for a shared amount of residual Hi — e by player i, R*N{X, D , Hi - e, H _ j , E) < i ^ ( X , D , H , E ) . Since v(S) = R*S(X,B,U,E) and w(S) = R*s(X,B,Hi - e , H _ , , E ) , it follows that v(S) > w{S) VS C TV such that i G S, while the values of all coalitions not containing i remain unchanged. An allocation rule $ is value-preserving if it induces retailer i not to share less of her residual with others, which implies that $ must satisfy > &i(w). • Proof of Proposition 2.8: As previously stated, both Shapley value and the fractional rule are coalitionally monotonic. Now, Shapley value, <£, as defined by (1.2), consists of a weighted sum of elements (v(S) — v(S \ {?})). Assume that v(N) > w(N),v(S) > w(S) VS C N,i G S, and v{S) = w{S) VS C N, i # S, as in Proposition 2.7. Clearly, this implies that v(S\ {i}) = w(S\ {i}) for all S C N, hence > $i(w). Next, recall that the fractional rule is defined by $i(v) = ^iv(N), ji > 0, Y,Nli - 1- Therefore, v(N) > w(N) implies > $i(w). • Proof of Theorem 2.9: Let us first consider an unbalanced transshipment game; without loss of generality, we can assume that the total residual supply is smaller than the total residual demand. Thus, J2N Hi < YIN Ej- Suppose that (&,$) is an optimal solution of the dual problem for problem (2.6) with S = N. Thus, (a, $) is optimal for the following problem: min E j v ^ i ^ i + PiEi) subject to : aj + > rj — vj — ty, 1 (2.22) 1, ,71. Let us further assume that f3j > 0 for all Ej > 0, and let Pjo = min{/37- : Ej > 0}. CHAPTER 2. A THREE-STAGE MODEL 42 Next, let /V+ = {j e N : Ej > 0 or (Ej = 0 and fa > p » } C N, and define an alternative solution for the dual problem by I /3j0, otherwise Clearly, since a = a and /3 > B, (a, ft) is also feasible for (2.22). Moreover, for this new dual solution (a, B) we have N N N N+ N\N+ N N since Ej = 0 for j € N \ N£- Thus, (a, /3) is also optimal for (2.22). Now, define yet another solution for the dual problem by P'j=Pj-PjO, cv • = &i + BJO . Clearly, (a1, B') is also feasible for (2.22). Moreover, for this new dual solution (a1, B') we have N N N N N N N N which contradicts our assumption that (a,/3) is optimal for (2.22). Thus, whenever E / v Hi < J2N Ej, some of the players with residual demand will be allocated zero units of additional profit. Let j° be one such player. Since BJO = 0, it follows from the dual constraints a.i + Pj > Vj — Vi — Uj, i ^ j, that at > T J O — Vi — Uj° f ° r a i l * 7^ j°-Since HJO = 0, it follows that cti > TJO — Vi — UJO for all i such that Hi > 0. Thus, allocations to relevant players with positive residual supply based on dual solutions are positive. CHAPTER 2. A THREE-STAGE MODEL 43 We can conclude from the above that in any unbalanced transshipment game, relevant players belonging to the group with strictly more residual resources (sup-ply/demand) who are allocated zero units of profit in the transshipment stage, would like to share less than the actual values of their residuals. Thus, there are no dual al-locations which will induce the retailers to share all of their residuals in an unbalanced transshipment game. To see whether there are value-preserving allocations, we have to analyze balanced transshipment games. Following the same arguments as above, we cannot have an equilibrium if some of the players with residual supply/demand are allocated zero units of additional profit. Thus, suppose that all players are allocated some positive values, i.e. there exists an optimal dual solution (a, $) with a, > 0 V Hi > 0, Pj>0 V Ej > 0. Consider an arbitrary player i0. If i0 decreases the amount of her shared residual by e, the transshipment game becomes unbalanced and some players' allocations, which are currently strictly positive, become zero. Therefore, one can find a player i0 such that a decrease in her coefficient in the objective function for (2.22), which changes the relationship between the total residual supply and the total residual demand, results in a new optimal solution (a, (3) such that dj 0 > aio, if i0 is a supply-player, or /3~io > Pi0, if io is a demand-player. Without loss of generality, we can assume that i0 is a supply-player. Thus, when she shares an amount Hio — e, her allocation is V^ o = ®i0(Hio ~~ €)- By selecting e < Q'o.~Q'QH i o, player i0 can strictly increase her dual allocation. Since E i v ( « t f f i + PiEi) - aioe < Y,N(&iHi + PiEi), it follows that the allocation rule based on dual prices is not value-preserving. Now, suppose that (H*,E*) is a Nash equilibrium profile. It is shown above that in a balanced transshipment game in which all players receive a positive al-location of residual profit, relevant players want to deviate and share less. So, a Nash equilibrium profile cannot be achieved when the amounts of shared residuals satisfy CHAPTER 2. A THREE-STAGE MODEL 44 Next, let us consider unbalanced transshipment games; without loss of generality, we can assume that YIj=\H* < YJj=\E*. It is demonstrated above that some of the relevant demand-players will be allocated zero units of residual profit. Further, assuming Y?j=i H* > 0, some of those demand-players will have an incentive to deviate to a point where ]C"=i E* < £ " = 1 H*. In this new unbalanced transshipment game, we can conclude by symmetry that some of the relevant supply-players will be allocated zero units of residual profit. Assuming Y!j=\E* > 0, those relevant supply-players will now have an incentive to deviate to a point where YJj=\ H* < J2]=i E*. Thus, in an unbalanced transshipment game with Y^j=i E* > YJj=\ H* > 0, where all players are relevant, a Nash equilibrium profile would have to satisfy n n n £ f f ; < 5 > ; < 5 > ; > j=i i=i i=i which is a contradiction. Finally, suppose that in the unbalanced transshipment game we have 2~Z"=1 E* > 5Z"=1 H* = 0, and select a supply-player i0 such that Tj — vio — tlQj > 0 for some relevant player j with E* > 0. It follows from the discussion above that by deviating to some positive H*o < YJj=\E*, player i0 creates a new unbalanced transshipment game in which she is allocated a positive share of the residual profit. Thus, whenever S " = 1 H* = 0 in an equilibrium profile and all players are relevant, we must have E* = 0 for all players j. We can conclude that when all players are relevant, the only Nash equilibrium profile is achieved when players do not share any amounts of their residuals, which completes the proof. • Proof of Theorem 2.10: There are two separate cases we need to consider - con-tinuous and discrete demand distributions. It suffices to find one transshipment game in each category for which there are no value-preserving allocations. In the previous theorem, we have shown that there are no value-preserving allo-cation rules for the continuous case. Now, let us consider the discrete case, i.e. the model in which the demands have discrete distributions. Without loss of generality, we can analyze the case with only two players, which occurs in any game with n play-CHAPTER 2. A THREE-STAGE MODEL 45 ers when n — 2 players have zero units of residual supply/demand. We can analyze a simple case with two retailers where Hi, Ei 6 {kS, k integer, 8 > 0}. Let us assume that player 1 is a supply-player and player 2 is a demand-player, and let us denote by C12 — r2 — vi — ti2- The payoffs for this game are given by Table 2.1: rows of the table correspond to the residual supply shared by player 1, columns correspond to the residual demand shared by player 2, and the ordered pairs represent the allocations of the residual profit based on dual prices - the first coordinate is the allocation to player 1, the second is the allocation to player 2, and 7; G [0, i5ci2]. 0 8 28 38 48 0 (0,0) (0,0) (0,0) (0,0) (0,0) 8 (0,0) (li,8c12 - 71) (<5ci2)0) (<5ci2,0) (5C12.0) 28 (0,0) (0,8c12) (72 ,25ci 2 - 72) (28cl2,0) (25c1 2,0) 38 (0,0) (0,8cl2) (0,2(Jc12) (j3,38c12 - 73) (3<Jc12)0) 48 (0,0) (0,8cl2) (0,2(Jc12) (0,3<k12) (7 4 ,4<5c 1 2 -Table 2.1: Payoffs for a discrete transshipment game with two players • A l l points (0, iS) and (18, 0), i = 0,1, 2, 3, . . . , are Nash equilibrium profiles; the players are indifferent about the residuals they share since the residual profit is always zero. • Consider the case where both players have at least 8 units. - If 7 l = 0, player 1 gets 0 whenever player 2 shares 8. Thus, player 1 is indifferent about the amount she shares and (18, 8), i = 1, 2, 3 , . . . , are Nash equilibrium profiles. - If 7 l = <5ci2, player 2 gets 0 whenever player 1 shares 8. Player 2 is indifferent about the amount he shares and (8, i8), i = 1, 2, 3 , . . . , are Nash equilibrium profiles. CHAPTER 2. A THREE-STAGE MODEL 46 - If 7 1 6 (0,<5ci2), then jx > 0,5ci 2 - 7i > 0, and (5,8) is the unique Nash equilibrium profile in which at least one of the players shares 8. Consider the case where both players have at least 28. Clearly, whenever Hi > E2, player 1 wants to deviate to a point where Hi < E2; similarly, whenever E2 > Hi, player 2 wants to deviate to a point where E2 < Hx. Thus, the only points we need to consider for Nash equilibrium profiles are those where Hi = E2. - If (28, 28) is an equilibrium profile, we should have 7 2 > 8cn > 7 2 = 0C\2, 28ci2 - 7 2 > 8cu j i.e. (28, 28) is a Nash equilibrium profile with a corresponding equilibrium outcome (8ci2,8ci2) if 7 2 = 8ci2. - If (38, 38) is an equilibrium profile, we should have 7 s > 2<5c12 38ci2 - 7 3 > 25c i 2 which is a contradiction. } 28cu < 7 3 < 8ci2, Thus, whenever both players have strictly more than 28 units of residual sup-ply/demand, they will share strictly less than it, and no completely sharing or value-preserving allocation can be found for the discrete case as well. • Proof of Proposition 2.11: In order for an allocation ip to be in the core, it has to satisfy (1.1). When n = 2, we only have subcoalitions consisting of one player, and thus the core constraints are of the form ^ > 0 V i^ + ^ 2 = c 1 2 • max{min{iJi, E2}, min{i?i, H2}}, CHAPTER 2. A THREE-STAGE MODEL 47 where c u is defined by (2.15). • Proof of Theorem 2.12: It is sufficient to find one transshipment game with four retailers for which there is no completely sharing core allocation rule. Let v be the characteristic function of the game with two supply-players and two demand-players with Hi = 2, H2 = 4, E3 = 4, E4 = 6. Assuming ci3 = 1 for all i, j leads to v(N) = 6. Then, if = (<&i(f), $ 2 ( f ) , ®3(v), )) is a core allocation rule for this game, we must have $i(v) + $2(w) + $4(v) > v({l, 2, 4}) = 6. Thus, every core allocation rule, $, for this game must satisfy &3(v) = 0. Similarly, we have the following core constraints: $i («) + $ 3(u) >v({l,3}) = 2 $ 2(i;) + $3(u) >^({2,3}) =4, which imply that the core for this game consists of the unique point (2, 4, 0, 0). Hence, the unique core allocation rule, $(u), for this game is $(v) = (2,4,0,0). Now, $ will be a completely sharing allocation rule if the allocation to player 4 does not increase in any game in which she shares less of her residual demand, while the amounts shared by the other players remain unchanged. Thus, we must have $ 4 H = 0 (2.23) for all such games (N,w). In particular, let w be the characteristic function of the game in which player 4 decreases the amount she shares by 4. units, so that Hi = 2, H2 — 4, E3 = 4, E4 = 2. Consider the following core constraint: $ i H + $ 4 H >v({l,4}) =2 . Together with (2.23), it implies that all completely sharing core allocation rules for w must satisfy $ i M > 2. (2.24) CHAPTER 2. A THREE-STAGE MODEL 48 Finally, let v be the characteristic function of the game with Hi = 6, H2 = 4, E3 = 4, E\ = 2. Using similar arguments as above, we conclude that the value of any core allocation rule for this game is uniquely determined, &(v) = (0,0,4,2). Further, $ will be a completely sharing allocation rule if the allocation to player 1 does not increase in any game in which he shares less of his residual demand, while the amounts shared by the other players remain unchanged. Observe that the game with the characteristic function w corresponds to such a game - the amount shared by player 1 has decreased by 4 units, while the amounts shared by the other play-ers remain unchanged. Thus, $ is a completely sharing core allocation rule only if &i(w) = 0, which contradicts (2.24). Hence, a completely sharing allocation rule for a transshipment game with two supply-players and two demand-players does not exist. • Proof of Theorem 2.13: It is enough to find one transshipment game with six retailers for which one cannot find a value-preserving core allocation rule. Assume n = 6, and that two players have residual supply, four players have residual demand, and the total residual supply is equal to the total residual demand. Denote the players so that Hi = H2 = 12, E2 = E4 = 4, E5 = 6, E& = 10, and let cy- = 1 for all i and j. A value-preserving core allocation rule must result with an allocation ip of the total additional profit which is equal to twenty four. In order to find the conditions that such an allocation ip has to satisfy, consider the following cases: 1. Either player 1 or player 2 decides to share only 8, all other players share everything. For simplicity, assume that Hi = 8, H2 = 12, E3 = E4 = 4, E5 = 6,E6 = 10. Now, consider the following core constraints: <Pi + V>2 + + <P5 + <A> > v({l,2,A, 5,6}) = 20 + ^2 + <^ 3 + <Ps + <PB > v({l, 2, 3, 5, 6}) = 20, and v({l,..., 6}) = 20. Clearly then, the first two inequalities must be satisfied as equalities, which implies that for all vectors <p in the core, <p3 = <p>4 = 0. CHAPTER 2. A THREE-STAGE MODEL 49 Since (fi + p3 + y?4 > i>({l,3,4}) = 8, we must have <pi > 8. Thus, if one of the players 1 or 2 shares 4 units less, her individual profit will be at least 8, while the total additional profit decreases by 4 units. To avoid such a case, the allocations to players 1 and 2 cannot be smaller than 8 => <p\i p2 > 8. 2. Either player 3 or player 4 decides to share only 2, all other players share everything. For simplicity, assume that Hx = H2 = 12, E3 = 2, EA = 4, E5 = 6, E6 = 10. As it was done in the first case, it is easy to verify that in every core allocation for this instance, player 3 receives at least 2 units, while the total additional profit decreases by 2 units. To avoid such a case, the allocations to players 3 and 4 cannot be smaller than 2 => cp3, cp4 > 2. 3. Player 5 decides to share only 4, all other players share everything. We have Hi — H2 = 12, E3 = E4 = E5 = 4, E6 = 10; it is easy to verify, as it was done in the first case, that in every core allocation for this instance, player 5 never receives less than 2 units, while the total additional profit decreases by 2 units. To avoid such a case, the allocation to player 5 cannot be smaller than 2 => <p5 > 2. 4. Player 6 decides to share only 6, all other players share everything. We have Hv = H2 = 12, E3 = E4 = 4, E5 = E6 — 6; it is easy to verify, as it was done in the first case, that in every core allocation for this instance, player 6 never receives less than 4 units, while the total additional profit decreases by 4 units. To avoid such a case, the allocation to player 6 cannot be smaller than 4 => <A3 > 4." Since we are assuming that ip is an efficient allocation rule, we have £ i= i Pi = 24. On the other hand, to prevent players from sharing less than their actual residuals, which would lead to a decrease in the additional profit, we must have D f = i <Pi > 2 -8 + 2- 2 + 2 + 4 = 26, which leads to 24 = £ i= i > 26, implying that such an allocation cannot be found. • CHAPTER 2. A THREE-STAGE MODEL 50 Proof of Theorem 2.14: The allocation rule (2.18) gives player i a share of the residual profit defined as a fixed portion of the total profit reduced by her individual profit. It follows from (2.7) that the profit function for player i is then defined as a fixed portion of the total profit, P ( X , D , H , E ) = 7 * £ ? = 1 ^ ( X , D , H , E ) = 7* {E"=i[r-i mm{Xu Dt} + vxHx - aXi] + R*N(X, D , H , E)} . Clearly, since the above function is non-decreasing in the amounts of shared residual supplies and demands, it is maximized for value-preserving sharing of residuals. Thus, this allocation rule is value-preserving, and we can use a simplified notation (without H and E) below. The efficiency of the allocation rule (2.18) follows from (2.20)-(2.21): 71 71 71 X > ( X , D ) = ^ P j ( X , D ) - ^ [ r , m i n { X t , A } + ^ i - c l X l ] = J R ^ ( X , D ) . i=i j=i j=i Next, we want to show that a first best solution is a' Nash equilibrium profile. It follows from (2.10) and (2.25) that the individual profit for player i can be written as P l ( X , D ) = 7 l J P c ( X , D ) . (2.26) Thus, for this particular allocation, the individual profit for any player is maximized when the total profit for the centralized system is maximized. Suppose that X c is a first best solution which is not a Nash equilibrium in the first stage of the decen-tralized distribution model; this implies the existence of a player i and X* such that J i ( A 7 , X ^ ) > Jl(Xf,X'Ll). However, since (2.26) implies that Jj(X) = 7 i J c ( X ) , we can conclude that J c ( X * , X i j ) > J C ( X C ) , which contradicts the definition of a first best solution. • I. Mixed strategies Nash equilibria for the transshipment game Let us consider Nash equilibrium in mixed strategies for some games with a small number of players. We assume that all players are relevant, and that each player faces a continuous demand distribution. CHAPTER 2. A THREE-STAGE MODEL 51 Consider first a simple transshipment game with one supply-player and one demand-player, with mixed strategies defined as follows. The supply-player selects h and h, so that 0 < h < h < H, and the amount he shares is uniformly distributed on [h, h]. Similarly, the demand-player selects e and e, so that 0 < e < e < E, and the amount she shares is uniformly distributed on [e, e]. Without loss of generality, we can assume e<h. Then, we have to consider two cases: • If e < h < h < e, then it can be shown that the expected allocation to the demand-player is decreasing in e, implying e = h. Next, the first or-der conditions of the expected allocation to the supply-player result with a unique solution in which the maximum expected allocation is attained, wherein h=h = e = 0. Finally, since e < e, e = 0. • If e < h < e < h, it can be shown that the first order conditions of the expected allocations to the demand-player and to the supply-player imply that the players' selections must satisfy e = h=h = e. Thus, in this case the Nash equilibrium profile is realized in pure strategies. It follows from Theorem 2.9 that, in some sense, there is a unique pure strategy equilibrium profile wherein both players share zero residuals. Thus, if the two players' strategies are uniformly distributed as explained above, then it is enough to consider only Nash equilibrium in pure strategies. Let us assume that, when there are more than two players, all of them start their randomization from zero. That is, each supply-player i selects hi < Hi and the amount he shares is uniformly distributed on [0,/ij], and each demand-player j selects ej < Ej and the amount she shares is uniformly distributed on [0,ej]. Now, consider a transshipment game with three players; without loss of gener-ality, we can assume that players 1 and 2 are supply-players, that player 3 is a demand-player, and that C i 2 < C i 3 . By solving'the transshipment problem, we find the following: • For Hi + H2 < E3, ai = c i 3 , a 2 = c 2 3 , B3 = 0 can be completed to a dual optimal CHAPTER 2. A THREE-STAGE MODEL 52 solution; • For H2 < E3 < Hi + H2, 07 = 0, a2 = c 2 3 — C i 3 , f33 = C13 can be completed to a dual optimal solution; • For E3 < H2, c*i = 0, a2 = 0, /33 = c i 3 can be completed to a dual optimal solution. One can also verify that for e3 > hi + h2, player's 3 expected allocation is decreasing in e3, and therefore she selects e3 < hi + h2. Similarly, for h2 > e3, player's 2 expected allocation is decreasing in h2, and therefore he selects h2 < e3. Hence, the players' selections satisfy h2 < e3 < hi + h2. For any such selection, player's 3 expected allocation increases in e3 while keeping e3 < hx + h2, leading to e3 = hi+h2. Similarly, player's 2 expected allocation increases in h2 while keeping h2 < e3, leading to hi = e3. Finally, player's 1 allocation increases with hi for hi < e3, and decreases with an increase in h\ for hx > e3, leading to hi = e3. Hence, hi,h2, and e3 should satisfy hi = h2 = e3 = hi + h2, which has a unique solution hi = h2 = e3 = 0. Thus, in this case as well, the only Nash equilibrium profile is one in which all retailers share zero residuals. Apparently, similar results can be obtained for any number of players, implying that if the players' strategies are uniformly distributed as explained above, then it is enough to consider only pure strategies. However, the derivation of the appropriate algebraic expressions for more then three players becomes tedious, since the number of possible relationships among players' selections h^s and efs grows exponentially. II. A value-preserving allocation rule for a transshipment game with two supply-players and two demand-players Denote the players so that H{ > 0, H2 > 0, H3 = HA = 0, Ei = E2 = 0, Ez > 0, E4 > 0, and suppose that the shared residuals satisfy: Hi < H2, £3 < EA, Hi + H2<E3 + £4, CHAPTER 2. A THREE-STAGE MODEL 53 i.e. the total shared residual supply is not larger than the total shared residual de-mand, and consequently the maximum additional profit is H\ + H2. We can use the above ordering among residual supplies and demands to simplify the representa-tion of the core in this particular case. Observe that, for a core allocation rule <f, fi + <f3 + f4 > v({l,3,4}) = mm{H1,E3 + E4} = Hx. Since £ i= i fi = Hx+ H2, it follows that ip2 < H2. Then, one can show that the core for our particular case consists of all vectors satisfying the following constraints: <Pi > 0, i = 1,2,3,4 fi < Hx P2 < H2 f3 < Hx + H2 -min{H x +H2,E4} Pi = Hx -f H2 - (f i + ip2 + f3) P1 + P2 + P3 > m i n i / / ! + H2, E3), and min{Hi,E3} < ipx + ip3 < Hx-\-H2 - mm{H2,EA} mm{H2,E3} < ip2 + f3 < H2. If we denote a V b = max{o, b}, then the following allocation satisfies the above constraints and therefore is a member of the core: <Pi = \[Hl + mm{Hl,E3,EA-H3_l,E3 + Ei-(Hi + H2)}yQ], z = 1,2, ^ = Q V ^ I ^ , • • • " (2.27) f>4 = Hi + H2 - (fi + ip2 + f3). In order to show that the allocation rule defined by (2.27) is value-preserving, we need to analyze the various allocations to the four retailers and their possible unilat-eral decisions on the amount of their residuals that they want to share with others for all possible relationships among the residual supplies and the residual demands. Recall that we assumed Hx < H2, E3 < E4, Hi + H2 < E3 + E4. CHAPTER 2. A THREE-STAGE MODEL 54 Let us start with the case where neither of the demand-players is relevant. This is the case where the total residual supply is lower than the residual demand of any of the players 3 or 4. That is, Hi + H2 < E3 and Hi + H2 < E4. The core has a unique point, cpi = Hx,f>2 = H2,ip3 = f4 = 0, which coincides with the allocation (2.27), in which each of the supply-players gets an amount equal to the amount she shares, while the demand-players do not get anything. Now, for this allocation, each one of the players 1 and 2 would want to share as much as she can. Assuming the rest of the players share their total residuals, each one of the players 3 and 4 is indifferent about the amount she shares. Thus, a Nash equilibrium profile for this case is achieved when all players share their total residuals, (Hi, H2,E3, E4), and the unique corresponding core allocation is (Hi, H2, 0, 0). Next, consider the remaining relationships between the residual supplies and the residual demands and the corresponding core allocation, ip, derived from (2.27): 1. Hi < E3, H2 < E3, E3 < Hi + H2 < E4; ipi = Hx, ip2 = H2, ip3 = f4 = 0. 2. H{ < E3,H2 < E3,Hi + H2 > E4; fi = (Hi -H2 + E4)/2, ip2 = (-Hi + H2 + E4)/2, ip3 = <p4 = (Hx -H2 + E4)/2. 3. Hi < E3, E3 < H2 < E4, Hi + H2 < E4; (pi = Hi, ip2 = E3, (p3 = 0, f4 = H2 - E3. 4. Hx < Ez, E3<H2< E4, Hi + H2> E4; (pi = (Hi -H2 + E4)/2,f2 = (-Hi + E3 + E4)/2,tp3 = (Hx - H2 + E4)/2, <p4 = (Hi + 2H2 - E z - E4)/2. 5. E3<Hi< E4, E3<H2< E4, Hx + H2 < E4, fi = (Hi + E3)/2, f2 = (H2 + E3)/2, f3 = 0,<p4 = (Hi + H2 - E3)/2. 6. E3<Hi< E4, E3 < H2 <E4,Hi + H2> E4; fx = (_#2 + E3 + E4)/2, f2 = (-Hx + E3 + E4)/2, f3 = (Hx + H2 - E4)/2, VA = Hi+H2-E3- E4/2. CHAPTER 2. A THREE-STAGE MODEL 55 7. Hi < E3, H2 > E4; fi = Hi/2, ip2 = (-Hi + E3 + E 4 ) / 2 , (^ 3 = (#i + H2 - E4)/2, (p4 = (Hi+H2-E3)/2. It can be observed that the allocations to players with a lower total residual, namely players 1 and 2, either do not depend on the amounts they share, or increase with the amounts they share. Thus, players 1 and 2 are either indifferent about the amounts they share, or they would like to share as much as possible, while keeping H\ + H2 < E3 + E4. On the other hand, the allocations to players with a higher total residual, namely players 3 and 4, either do not depend on the amounts they share, or decrease with an increase in the amounts they share. Thus, players 3 and 4 are either indifferent about the amounts they share, or they would like to decrease the shared amount. However, a decrease in either player's 3 or 4 amount of shared residuals that changes the relationship between the total shared residual supply and the total shared residual demand so that Hi + H2 > E3 + E4 will reverse the position of players 3 and 4 with the former position of players 1 and 2, in which case players 3 and 4 become either indifferent about the amounts they share, or they want to share as much as possible, while keeping Hi + H2 > E3 + E4. We can conclude that a Nash equilibrium profile is attained with shared amounts that induce a balanced transshipment game in which players 1 and 2 share their total residuals, i.e. Hi = Hi} i = l,2, and Hx + H2 = E3 + E4. While supply-players share their total residuals, it is not obvious what should be the shared amount of a particular demand-player. Clearly, if Hi + H2 = E3 + E4, a unique Nash equilibrium profile is realized in which each player share his total residuals, and the corresponding allocation is <p\ = Hi/2,f2 = H2/2,f>3 = E3/2, ip4 = E4/2. However, when Hi + H2 < E3 + E4, a continuum of Nash equilibria exists, namely (HX,H2, E3, Hx + H2 - E3) with E3 G [max{0, Hx + H2- E4), E3}. None of these Nash equilibria is completely sharing, but all of them are value-preserving. Chapter 3 Formation of alliances in Internet-based supply exchanges 3.1 Introduction After its initial boom in the year 2000, which was followed by a period of a somewhat slower growth, business-to-business commerce is again getting stronger in the year 2002. While the volume of B2B commerce in 2000 was $226 billion, eMarketer, a provider of Internet and e-business statistics, estimates that it reached $449 billion in 20011. Many researchers predict huge B2B revenues for the year 2002: eMarketer predicts $820 billion, Forrester Research $2,061 trillion, Goldman Sachs $1.3 trillion, to mention just a few2. On-line marketplace sales accounted for less than one percent of total B2B transactions in 2000, which, nevertheless, represented a 585 percent increase from 19993. Ovum, a UK-based consulting company, predicts that this number will further grow, from five percent in 2001 to 35 percent in 20064. 1 "E-Business Numbers 2001", Line56 News, January 31, 2002 2"eMarketer's Sunny B2B Outlook", Line56 News, March 5, 2002 3 "E-Markets: Back Again", Line56 News, November 15, 2001 4 "Ovum's E-Business Big Five" ,Line56 News, January 17, 2002 56 CHAPTER 3. FORMATION OF ALLIANCES 57 In different industries, such as automobiles, chemicals, or retailing, competitors are joining forces in establishing electronic marketplaces in order to reduce inefficiencies in the purchasing process and cut the costs, by combining their buying power. With an electronic exchange, the seller needs to list his products only once, while currently suppliers have to notify buyers individually about the current availability of products, and buyers have to shop around. The saving of $250 million by I B M when buying $13 billion worth of parts on the Web in 19995 can serve as an illustration of the potential savings that can result from on-line purchases. Various companies, including Boeing, DuPont, Sears Roebuck, General Motors, and Ford, have joined with their rivals to form industry marketplaces. Exostar is a global e-marketplace founded by some of the world's largest aerospace and defense companies - B A E Systems, Boeing, Lockheed Martin Corp, Raytheon Co., and Rolls-Royce. ChemConnect is an online chemicals and plastics marketplace, which has among its members companies such as B A S F A G , BP, The Dow Chemical Com-pany, DuPont, ShellChemicals, and many others. Hitachi, I B M , Nortel Network, Seagate Technology, Toshiba, L G Electronics and Matsushita Electrics (Panasonic) have founded e2open.com, an e-marketplace for buyers and sellers of technology prod-ucts. The largest online exchange created so far is Covisint, initiated by the Big Three automakers. Ford and G M announced on February 25, 2000 that they will merge their Internet-based supply exchanges, and that DaimlerChrysler will join the venture. This exchange was joined by Nissan and Renault on April 14, 2000, and by Peugeot Citroen on May 22, 2001. The venture is planned to operate as an independent company, with each of the Big Three automakers having an equal ownership, for the purpose of creating a single auto-parts exchange for their suppliers. The Big Three, who spend around $247 billion annually on purchases from their 30,000 suppliers, plan to to hold auctions for equipment and supplies. In May 2001, one such auction was conducted, involving DaimlerChrysler and five suppliers. 1,200 parts worth over 3 billion euros were exchanged, making it the largest on-line auction ever conducted 5 " I B M to unveil component marketplace on Net", CNET News, May 1, 2000 CHAPTER 3. FORMATION OF ALLIANCES 58 on an exchange6. Kevin English, Covisint's president and C E O , announced that Covisint's auction site handled $51 billion in transactions in 2001, which was its first full year of service. Covisint expects that the auction and procurement functions will reduce unwanted inventory and cut bureaucracy and cost. According to Ford, labor and paperwork costs for a single purchase average $150, while corresponding online cost ranges $5-$157. Investment bankers have predicted, according to the Covisint webpage, that the exchange will yield a saving of $2,000-$3,000 per vehicle on a $19,000 vehicle. However, not all automakers are willing to join Covisint. Volkswagen announced8 its plans for establishing a rival exchange, that would lead to substantial savings through inventory reduction resulting from a more efficient supply chain and through lower prices. B M W also announced9 the intent to build its own marketplace, to solicit proposals from part suppliers and to conduct online buying auctions. Some key electronic companies, including Sun Microsystems and Oracle, are being more cautious before linking with their rivals. Their opinion is that huge market-places shared with competitors could compromise their confidential list of approved vendors10. A Merrill Lynch analyst has recently stated that some leading technology companies (Sun, Oracle, General Electrics) do not believe in big online exchanges, such as Covisint or e2open.com. Sun views its approved vendor list as "top secret" and cannot understand why HP wants to share information with Compaq, or Ford with G M . Instead, he argues that Sun believes that it is more useful to set up its own private auction exchange to ensure privacy and to keep its top vendors under wraps. Thus, on one hand, the decision to join a marketplace forces a company to share its suppliers with other alliance members. On the other hand, alliance membership leads to reduced costs, including those of possible rivals, since members share the develop-ment and operation costs, and a larger marketplace may also lead to a more intense 6 "Largest auction ever?", Line56 News, May 16, 2001 7 " F T C green-lights Big Three Net exchange", CNET News, September 11, 2000 8"Volkswagen plans Internet exchange to rival G M , Ford", CNET News, Apr i l 12, 2000 9 " B M W builds Net marketplace with Ar iba" , CNET News, Apr i l 20, 2000 1 0 "Tech companies wary of online exchanges", CNET News, June 13, 2000 CHAPTER 3. FORMATION OF ALLIANCES 59 competition among the increased number of suppliers. In addition, an alliance mem-ber may further benefit at the expense of companies left outside the alliance. Some natural questions that could arise are, then, when would a firm prefer to take part in an electronic marketplace joint venture, when would it prefer that other firms, possi-bly rivals, join the venture, and what are the financial consequences of either joining an alliance or remaining independent? In an attempt to gain a better understanding of the issues, we have constructed a model with three companies, wherein a certain degree of substitutability may exist between the products of any two companies. In particular, we provide some conditions, in terms of product substitutability and qual-ity of suppliers, that lead to the formation of an alliance of all three retailers, or the alliance of only two retailers, or the case where no alliance is formed because all retailers prefer to act independently. We also study the effect of alliance structure and quality of suppliers on the profit of a company. We note that our analysis can be extended to more general strategic alliances, in which membership in an alliance leads to a decrease in input prices and/or operating costs. In our model, we assume that demands are linear and deterministic, and that all retailers have complete information. This is clearly a great simplification, but we believe it can be used for an initial approach to the problem. Although there is a large body of literature on strategic alliances, as far as we know, there is not much written about alliance formation in on-line exchanges. For some related work on supply chain contracting and supplier coalitions in electronic markets, see Jin and Wu (2000, 2001). For an analysis of general strategic alliances, see, e.g., Lewis (1990), and for an analysis of alliances in airline industry, see, e.g., Oum et al. (2000). . The structure of the essay is as follows. In the next section, we present our model with three retailers of possibly substitutable products, where the demand functions are obtained as natural extensions of the demand functions used in the two-retailers model introduced by McGuire and Staelin (1983). In Section 3.3 we study the changes in a retailer's profit as a function of the substitutability levels among products, qual-ity of suppliers, and market structure. Section 3.4 analyzes retailers' preference for a CHAPTER 3. FORMATION OF ALLIANCES 60 partner in a two-retailer alliance. Section 3.5 briefly introduces, as stability criteria, the farsighted coalitional stability and the largest consistent set, which are subse-quently used in our analysis. In Section 3.6, we characterize some stable alliance structures for some special cases, wherein all products are either non-substitutable or highly substitutable, and in Section 3.7, we demonstrate that our results shed some light on the issues discussed above, and we further discuss the applicability of our results to more general situations with more than three retailers. A l l proofs are given in the Appendix. 3.2 T h e model We are presenting a model with three retailers, where the demand functions are obtained as natural extensions of the demand functions used in the model of two retailers with possibly substitutable products and deterministic and linear demands, introduced by McGuire and Staelin (1983). Following their notation, let S represent a scale factor corresponding to the industry demand when the prices of all products are set to zero, while the /i's and 0's represent two aspects of product differentiation - the absolute difference in demands and the substitutability of two products, respectively. Changes in /i's alter the relative product preferences, while changes in #'s affect the substitutability of the two products. When % = 0, products i and j have independent demands; product substitutability increases with dij, and they become highly substitutable as 6%j —> 1. The demand functions are given by: c L P Pi g pi 2 V k [i - e^ii - elk) with i,j,k e {1,2,3} such that i ^ j ^ k ^ i, 0 < (ii, /i2, ^3 < 1, Mi + fJ-2 + M3 = 1) P > 0) 3 > 0, and 0 < % < 1. Notice that when there is no substitutability among the products, the term within the brackets reduces to 1 — Bp\, which corresponds to a standard demand for a single product. Similarly, when one product, k, is not substitutable by the two remaining products, i and j, the equations for q[ and q'j coincide with the demand functions in the McGuire-Staelin model. CHAPTER 3. FORMATION OF ALLIANCES 61 We are assuming that the demands q\ are non-negative, which can be written as 2(1 - 0„-)(i - eik) - 2pp\ + pelJ(2 - One)?', + peik{2 - el3)P'k > o, for k £ {1, 2, 3} such that i ^ j ^ k ^ i. This leads to the following assumption about the retailers' profits. Assumption 3.1 The profit realized by each retailer (in any alliance structure) is non-negative, !![ = q'i(p'i — w'^j > 0. Following the lead of McGuire-Staelin, we rescale the model in order to reduce the number of variables. The rescaled model will involve only the retail prices, Pi,p2,P3, and the coefficients of substitutability, #12, #13, #23- Thus, let Qi = HiS' P , P l ( i _ ^ . ) ( l - 0 l f c ) P " P , (i - el3){i - elk)w^ for i,j,k £ {1,2,3} such that i 7^ j / k ^ i. Using the rescaled variables, the demands can be expressed in terms of the rescaled prices and coefficients of substi-tutability as qi = 1 - pi +.— 2 - Oij Q 2 - 9ik a (3.1) 1 — Uij 1 — Uik for k £ {1, 2, 3}, i 7^ j 7^ k 7^ i, while the profits are given by Ui = (pt - Wi)qi, i = 1,2,3. The following relationships between profits and rescaled profits hold: n 2 = — ^ z — / T 7 1 — ^ n ; , i,j,k e {1,2,3}, % ± 3 ± k ± i, or IT; = PiFlj. Observe that px does not depend on the variables pt and Wi, hence the analysis of the retailers' behavior based on IIj's will lead to the same results as the analysis based on 174's. CHAPTER 3. FORMATION OF ALLIANCES 62 The first order conditions that the rescaled profits Ui need to satisfy with respect to the rescaled retail prices pi result in the following system of equations: 1 - 2pi + 1 — 9jk 2 — 9, ik eljPj + 1 — 6jk 2 — 9i e. OikPk + Wi = 0, 2 i-elk ^J 2 i for i, j, k £ {1,2, 3}, i ^ j ^ k ^ i. Let us denote a = 32 - 923(2 - 9l3-9l2)(4- 913912)- 9213(2 - 923 - 912)(4- 9239l2)-- 922 (2 - 923 - 913)(4 - 9239l3) - 89239l39l2 + 9\39\39\2. Then, the solution of the system (3.2) is given by (3.2) Vi 1 6 - ^ ( 2 - % ) ( 2 - ^ ik a (1 + Wi) + + (1 - 9jk)(2 - 9ik) _ 49ij + 9jk9ik{2 - %) ^ + w.^ + ( i - 9lk) a (1 — 9jk){2 — 9ij) 49ik + 9jk9ij(2 — 9ik) (1 + VJk), (1 - 9l3) a for z,jf, A; € {1,2,3}, i ^ j ^ k ^ i. By substituting the expressions for p; in (3.1), we obtain: 16 - 9%(2 - 9lk)(2 - 9tJ) _ r _ 1 6 - ^ f c ( 2 - ^ ) ( 2 - % ) -ft = + (1 — fl?fc)(2 - i^fc) 4% + 9jk9ik(2 — Qjj) (1 - ' a (1 — 9jk)(2 - 9ij) 49ik + 9jk9ij(2 - 9ik) (1 - %) a Let us now introduce the following notation: Ai = 16-92jk(2-9tJ)(2-9lk), Bi = 49jk + 9ij9ik(2 — 9jk), 7z = 1+ 1 (1 + Wj)-(1 + lWfc). 1 — Observe that cn > 0, Ai > 0,Bi > 0, 7 i > 0. The above expressions for the retail prices and demands can, consequently, be rewritten as Pi = ^{Al{l + wi) + (l-9jk)[jjBk{l + wj)+jkBj{l + wk)}}, q, = ^ {A, - (a - A^w, + {1 - 9]k)[-fjBk{l + Wj) +-fkBj{l + wk)}} , (3.3) CHAPTER 3. FORMATION OF ALLIANCES 63 and therefore, the profit for retailer i is given by M (3.4) = ^{Ai-(a- Ai)wi + (1 - 9jk)[<yJBk(l + w3) + lkB0(l + wk)]}2 . Observe that when one product is not substitutable by the remaining two (i.e., dik = Ojk = 0), (3.3) and (3.4) are equivalent to corresponding expressions in McGuire and Staelin (1983). The following proposition describes how the wholesale prices of the other retailers influence a retailer's retail price, demand for his product, and his profit. In the sequel, increase (resp., decrease) means does not decrease (resp., increase). Proposition 3.2 pi,qi, and Ui are increasing in Wj,j ^ i. If i is substitutable by j (9ij > 0) and/or k is substitutable by both i and j (9ik9jk > 0), then Pi, qi, and Ui are strictly increasing in Wj. 3.3 Profit as a function of alliance structure In this section, we study the effects that the formation of an alliance has on the profits of the retailers. We will show that changes in their profits depend on the level of substitutability among products, on the quality of their suppliers, reflected through the relative decreases in wholesale prices stemming from alliance memberships, and on the market structure. On-line procurement decreases the labor and paperwork costs significantly, making it beneficial for companies to move their transactions on-line. Goldman-Sachs esti-mates (Helper and MacDuffie, 2000) that electronic procurement results in savings of more than 7% on purchased parts and 4.4% of the total cost for a $20,000 car. Ford claims that it has recouped its initial investment in Covisint by July 1, 2001 1 1, and it forecasted a further $350 million in savings during 2001 by using the exchange. The 1 1 "Ford recoups investment in Covisint web exchange", Financial Times, FT.com, July 1, 2001 CHAPTER 3. FORMATION OF ALLIANCES 64 formation of an alliance may result in some further benefits for its members. Collab-oration results in a lower share of development and operations costs. Observe also that the retailers in an alliance agree to "share" their suppliers. Thus, retailers within an alliance have access to a larger pool of suppliers, which may cause an additional decrease in their individual wholesale prices. The use of an auction model for some of the purchases may further cut the wholesale prices, due to an increased competition among the suppliers. In the reminder of the essay, for simplicity of presentation, a decrease in wholesale prices resulting from alliance membership is assumed to incor-porate as well the decrease in processing, development, and operations costs resulting from such membership. The above discussion motivates the following observation. Observation 3.3 Upon the formation of an alliance in an Internet-based supply ex-change, the wholesale prices for all retailers within that alliance strictly decrease12. Notice that this does not imply that each retailer's profit increases. However, since the coefficients of all wholesale prices, uij, in the expression for a retail price, P i , in (3.3) are non-negative, with the coefficient of Wi being strictly positive, the retail prices of all retailers decrease (strictly decrease, for alliance members) upon the formation of an alliance. In the remainder of the essay, we denote by {(ijk)} the alliance of all retailers, and by {{ij),k} the alliance between retailers i and j, with retailer k remaining independent. {(ij),k) will be called a paired structure, retailers i and j will be called paired retailers, while retailer k will be referred to as the unpaired retailer. {i,j,k} will denote an alliance structure wherein all retailers are independent, and it will be called the independent structure. 1 2 I f this model is to be extended to analyze the formation of alliances in a more general framework, the decrease in wholesale price for all alliance members should be included as an assumption of the model. CHAPTER 3. FORMATION OF ALLIANCES 65 3.3.1 Two-retailer alliance We start our analysis by considering the formation of an alliance between two of the three existing retailers. Let us consider the pairing of retailers i and j, that is, the structure {{ij),k}. Then, both Wi and w3 strictly decrease, hence we can replace wx by Wi - AY, and w3 by w3 - A) 7 , with AJ J ' > 0, A) 7 > 0. It follows from (3.4) that the profit function for retailer i in this structure, denoted by f l / 7 , is given by n? = &{Ai-(a-AA(wi-A?) + + (1 - Ojk) • [ljBk(l + w3 - Aj) + lkB3{\ + wk)}}2 1 ' V l (x Q 2 (3.5) The profit for retailer i increases upon pairing with j, when the current structure changes from {i,j,k} to {(ij),k), whenever II--7 — Fli > 0. This difference in profits is given by 1 nr-n \ = f2 [(a - Ai)A? - (i - 9Jk)l3BkAj (a - AJA? - (1 - e]k)l3BkA)j + 2 a y n ~ ^+\/4lJ a '(a - Ai)A\j - (1 - d]k)l3BkAli Since + \JIi1/ > 0 follows from Assumption 3.1, i's profit increases upon pairing with j if • • . Aij > (1 ~ 0jk)ljBk i 3 1 ~ a-A, j' (3.6) Analys i s of some special cases. We now consider some special cases, wherein 6i3 = 0 or 6l3 ->• 1 for all i,j G {1, 2, 3}. Let us first assume that all products are highly substitutable. That is, 9i3 —> 1 for all i, je{l, 2, 3}. Then, (1 - 9jk)7j = (1 - 9jk){2 - 9ik)/(l - 9lk) -4 1, a - At -> 10, and Bk —>• 5. Therefore, it follows from (3.6) that i's profit increases in the alliance (ij) if the decrease in his wholesale price is at least as large as one half of j's wholesale price decrease (A]3 > A ^ / 2 ) . CHAPTER 3. FORMATION OF ALLIANCES 66 If we assume non-substitutability between products i and j (% = 0) and high substitutability of product k by both products i and j (0^ —> I, Ojk —> 1), the profit for retailer i increases upon pairing with j if the decrease in his wholesale price is not smaller than one fifth of j ' s wholesale price decrease ( A / > A y / 5 ) . In general, let us denote non-substitutability between products i and j (% = 0) by NS, and high substitutability of i and j (% —> 1) by HS. Then, for different possibilities of HS and NS among the three products, Table 3.1 provides conditions for an increase in i's profit, as a function of the relative decreases in i's and j ' s wholesale prices. 0l3 9jk IT/ > IT (a) NS NS NS A / > 0 (b) NS NS anything AV > 0 (c) NS anything NS A iJ ' > 0 (d) NS HS HS A / ' > A f / 5 (e) HS NS NS A : j > A y (0 HS NS HS A; j ' > o (g) HS HS NS never (h) HS HS HS A ? > A ^ / 2 Table 3.1: Conditions for an increase in a retailer i's profit in the alliance (ij) In the remainder of this essay, we say that retailers i and j are compatible if their pairing increases their individual profits, that is, if 11/ > EL;, IT}3 > Uj. The statements in the following proposition follow from Table 3.1. Propos i t ion 3.4 Retailers i and j are compatible if any of the following conditions is satisfied: • product i is non-substitutable by either j or k (Oij = 0^ = 0), CHAPTER 3. FORMATION OF ALLIANCES 67 • products i and j are not substitutable, the third product, k, is highly substitutable by both i and j (0„- = 0, Bik -> 1, 9jk -¥ I), and bAj > A? > Aj/5, • all products are highly substitutable, and 2Al- > A1? > AJ/2. 3.3.2 Three-retailer alliance Let us now consider the formation of an alliance of all three retailers. The addition of another retailer to an alliance of two retailers, which increases the pool of suppliers and results in a smaller share of the development and maintenance costs, results in a decrease of the wholesale prices for all three retailers. Further, we make the following additional reasonable assumption that a reduction in one retailer's wholesale price in an alliance of all three retailers is smaller than the sum of the reductions he realizes in both paired alliances. Formally, we have: Assumption 3.5 A1/ + A]k > Ai > A1/, i ^ j ^ k ^ i, where Aj > 0 is the reduction in retailer's i wholesale price in the alliance of all retailers. The profit for retailer i in the alliance (ijk) is given by Let us assume the existence of an alliance, (ij), and let us analyze the changes in the retailers' profits when retailer k joins this alliance. The difference between i's profit in {(ij), k} and his profit in {(ijk)} is given by n f = L{Ai-(a-Ai)(wi-Ai) + + (1 - Ojk) • hjBk(l + w3 - A3) + jkBj(l + wk- Ak)}}2 i , o A=T(a - Ai)^ ~ (l-ejk)('yjBkAj + 'ykBjAk) [(a - AAAj - (1 - 6> i f c )( 7 ,£ f c A, + lkB3Ak)f a2 . a a •{(a- Ai)(At - A?') - (1 - 9jk) [l3Bk(A3 - Af) + lkB3Ak]} . CHAPTER 3. FORMATION OF ALLIANCES 68 Since \JlV^k + yTI / > 0 follows from Assumption 3.1, i's profit increases when k joins the alliance (ij) if A , _ > ( 1 _ ^ - A ^ ^ A . a - Ai Analys is of some special cases We now consider some special cases, wherein 9l3 = 0 or % -> 1 for all i,j e {1, 2, 3}. Let us assume that all products are highly substitutable, i.e. 9i3 —» 1 for all i , j G {1, 2, 3}. As shown in Subsection 3.3.1, in this case (l — Oj^jj —» 1, a — Ai —> 10, and Bk —> 5. Similarly, it can be shown that (1 — 9jk)jk ~^ 1 and B3 —> 5. Therefore, it follows from (3.7) that i's profit increases when k joins the alliance (ij) if the marginal decrease in i's wholesale price is at least as large as the average of the marginal decreases in j ' s and /c's wholesale prices, i.e. A , — A / > [(Aj — Ay*) + Ak}/2. The results for all special cases are summarized in the first column of Table 3.2. 9l3 9jk uf > n y n f > n f (a) NS NS NS A , - A / > 0 Ak>0 (b) NS NS HS Ai - A? > 0 Ak > A3 - A y (c) NS HS NS Ai - AV > Ak A , > A , - AV (d) NS HS HS A , - A? > (A3 - A * ) / 5 never (e) HS NS NS Ai - A'/ > A3 - A*/ Ak > 0 (f) HS NS HS A, - AV > A f c / 5 Ak > (A, - A / ) / 5 (g) HS HS NS never Ak > (A3 - A V ) / 5 (h) HS HS HS A 2 - A?' > Ak > [(A, - AV) + Ak}/2 [(A, - A ? ) + (A, - A«)]/2 Table 3.2: Conditions for an increase in retailers' profit when k joins the alliance (ij) Now, consider the changes in the profits for k upon joining the alliance (ij). The CHAPTER 3. FORMATION OF ALLIANCES 69 difference between /c's profits in the alliances {(ij),k} and {(ijk)} is given by Jnijk TWk-lW = ^—— k x±k k k a {(a - Ak)Ak - (1 - %) [nBjiAi - A{) + ^ ( A , - AV)]} Since \JlVkjk + \J\Vl > 0 follows from Assumption 3.1, k's profit increases upon joining the alliance of the remaining two retailers if a - A f c Analysis of some special cases We now consider some special cases, wherein Bij = 0 or % -> 1 for all i,j e {1, 2, 3}. Let us assume that all products are highly substitutable, i.e. Bij —¥ 1 for all i,j e {1,2,3}. Then, similarly to our analysis in Subsection 3.3.1, it can be shown that in this case (1 - % ) 7 i —• 1, (1 - %) 7 j —> 1, a - Ak —> 10, and 5 i —> 5, —>• 5. Therefore, it follows from (3.8) that k's profit increases when he joins the alliance (ij) if the decrease in his wholesale price is at least as large as the average of his externality effect on the wholesale prices of the remaining two retailers, i.e. Ak > [(Ai - A- J ) + (Aj - Aj)}/2. The results for the other special cases are summa-rized in the second column of Table 3.2. Observe that similar results hold when the current structure is the independent structure, {i,j,k}, and the retailers consider the formation of the alliance of all re-tailers, {(ijk)}. One only needs to replace Aj - Af by A^, and Aj — A1- by Aj. The results for this case are given in Table 3.3. 3.4 Preference for a Partner In this section, we analyze retailers' preferences for a formation of a two-retailer al-liance. We subsequently study some cases wherein a retailer may prefer to participate CHAPTER 3. FORMATION OF ALLIANCES 70 Qij Oik Ojk uyk > ^ (a) NS NS NS Aj > 0 (b) NS NS HS A , > 0 (c) NS HS NS Ai > Ak (d) NS HS HS Ai > A , / 5 (e) HS HS NS never (f) HS HS HS A , > (Aj + Ak)/2 Table 3.3: Conditions for an increase in i's profit when independent retailers join in (ijk) in a certain paired alliance in which his profit decreases, in order to prevent the for-mation of a different paired alliance, wherein he would be the unpaired retailer and realize even smaller profits. 3.4.1 Preference for a partner in a two-retailer alliance Retailer i prefers pairing with j than with k, hereafter denoted by (ik) -<i (ij), if it results in a higher profit for i (i.e. U1/ > Uf). From (3.5), this condition corresponds to ( 0 1 ? + vW) • {(« - Ai)(A? - Af) - (1 - O^BkAj - ^ A f ) } > 0. Since \fu~f + yfuf > 0 follows from Assumption 3.1, i's profit is larger in {(ij), k} than in {(ik),j} if A / - A• > (1 - 9jk) h k 3 _ 7k 3 k . (3.9) Analysis of some special cases Without loss of generality, let us assume that A / > Af. CHAPTER 3. FORMATION OF ALLIANCES 71 It follows from Table 3.1 (g) that, when products j and k are not substitutable, while i is highly substitutable by both j and k, i always prefers staying independent to pairing with any of the retailers. Thus, we need not consider this case. Let us assume that all products are highly substitutable, i.e. 9i3 —> 1 for all i,j G {1,2,3}. As shown in Subsection 3.3.1, (1 — 93k)lj —» 1, a — Aj —>• 10, and Bk —> 5. Similarly, it can be shown that in this case (\ — 9jk)lk 1 ar>d Bj —> 5. Therefore, it follows from (3.9) that i prefers to pair with j than with k if A? - A f > (Af - Af)/2. Oij 9ik 9jk (ik) <i (ij) (a) NS NS NS A? - Af > 0 (b) NS NS anything AV - A f > 0 (c) NS anything NS AV - A f > 0 (d) NS HS HS A? - A f > Ay / 5 (e) HS NS NS AV - A f > Af • (f) HS NS HS A--7 - A f > 0 (g) HS HS HS A? - A f > (Af - Af )/2 Table 3.4: Retailer i's preferences for pairing when A1/ > A\' Table 3.4 summarizes conditions for (ik) -<i (ij), regardless whether pairing with j results with a decrease in i's profit. In the following subsection, we analyze the cases wherein a retailer i may prefer being in a paired alliance (ij) to being the unpaired retailer, even if it results in a decrease of his profit, that is, when LTj > TIV. 3.4.2 Participation in a two-retailer alliance when profit decreases Let us now assume that i's profit strictly decreases upon pairing with j (I7.V < TLJ, and consider pairing of the remaining two retailers, (jk). If we replace Wj by Wj — A^fc CHAPTER 3. FORMATION OF ALLIANCES 72 and wk by wk - A f , it follows from (3.5) that the profit function for retailer i when he is the unpaired retailer, denoted by I l f , is given by i 2 a l- {A, -(a- Ai)Wi + (1 - Ojk)[^Bk(l + WJ - A f ) + 7^ ( 1 + wk - A{k)}}' U i / ^ ( l - ^ ) [ 7 , ^ A f + 7 . ^ A f ] | [l-e]kf[l3BkA]k + 7 ^ A f ] 2 _ The following proposition will be used in the subsequent analysis. Proposition 3.6 The profit a retailer, i, can realize as the unpaired retailer is always smaller than his profit in the independent structure. That is, Il{k < Hi. Thus, whenever i's profit increases upon pairing with j (U1/ > Hi), Proposition 3.6 implies that i prefers {{ij),k} to {{jk),i}. On the other hand, when IT-'* < 11/ < IT and j may decide to join k if an alliance of i and j is not formed, it is more profitable for retailer i to join j than to allow the formation of the alliance (jk), wherein his profit would be inferior. To determine the conditions for Yljk < I I / , consider the inequality n / - n f = ^ 3 + J ^ K {{A _ AAA? - (1 - ejk) [ 7 ^ ( A y - A f ) - lkB3Af ]} > 0. Since \JlVj + i / n f > 0 follows from Assumption 3.1, i prefers {(ij),k} to {(jk),i} when > ^ ( A y - A f j - ^ A f a - Ai Analysis of some special cases We consider here some special cases, wherein 9ij = 0 or 9ij —> 1 for all i,j. It follows from Table 3.1 (a)-(c) that IT/ > lb if products i and j are not sub-stitutable, and product k is non-substitutable by at least one of the remaining two products. It further follows from Table 3.1 (f) that the same is true when products i CHAPTER 3. FORMATION OF ALLIANCES 73 and k are not substitutable, while j is highly substitutable by both i and k. Therefore, none of these cases needs to be considered here. Whenever products j and k are not substitutable, while i is highly substitutable by both j and k, which corresponds to Table 3.1 (g), the right-hand side in (3.10) increases without bound as 9i3- —>• l,9ik —> 1, hence retailer i never has an incentive to pair with j when TV3 < n*. If product k is not substitutable by either i or j (8ik = 9jk = 0), while prod-ucts i and j are highly substitutable (% —» 1), and A - J < Af, it follows from Table 3.1 (e) that i's profit strictly decreases. Since a — Ai = 8,1 — 9jk = 1, jj = 2,Bk = 4, jkBj = 0, it follows from (3.10) that i benefits from a member-ship in the alliance (ij) if A/ > A)3 - Af. If we assume non-substitutability between products i and j (% = 0) and high substitutability of product k by both i and j (9ik —>• l,9jk —> 1), it follows from Table 3.1 (d) and from the case 9jk = 0, 9l3 —> l,8ik —> 1, which is described above, that retailer k never wants to pair with either of the remaining two retailers. Hence, the formation of an alliance (jk) is unlikely, and this case needs not be considered here. Finally, let us assume that all products are highly substitutable. If A13 < A13/2, Table 3.1 (h) implies that TV3 < Tli. It follows from (3.10) that retailer i prefers {(ij), k} to {(jk), z} if Af > (AJ - Af - Af )/2. We can summarize this analysis in the following proposition. Propos i t ion 3.7 When the profit for retailer i strictly decreases in the alliance struc-ture {(i]),k}, he still prefers this alliance structure to being the unpaired retailer if and only if one of the following conditions is satisfied: • Product i is highly substitutable by product j, k is not substitutable by either of the two remaining products (% —>• l,9ik = 9jk = 0), and Af > Af — Af, or • All products are highly substitutable, and Af > (Af — Af — Af)/2. CHAPTER 3. FORMATION OF ALLIANCES 74 3.5 Stability criteria In Section 3.3, we have analyzed changes in retailers' profits resulting from the for-mation of an alliance. However, an alliance will be formed and will continue to exist only if all members of that alliance agree to participate and to stay in that alliance. Therefore, some individual rationality constraints and some stability conditions need to be satisfied. The framework we use to study these conditions is game theory, introduced in Section 1.2. Since all retailers in our problem can communicate among themselves, we may ex-pect that they will consider both unilateral deviations from given coalition structures and joint deviations by coalitions. Unfortunately, most solution concepts used for analyzing stability of coalition structures (core (Gillies, 1959), coalition structure core (Aumann and Dreze, 1974), strong Nash equilibrium (Aumann, 1959)) preclude the possibility that once the players decide to deviate, there may be further deviations, or they do not take into account the possibility that some members of a deviating coali-tion may further deviate with members outside that coalition (coalition-proof Nash equilibrium (Bernheim et al., 1987)). For an approach to overcome the "nestedness" restriction in Bernheim et al. (1987), see Xue (2000). Our need for farsightedness, i.e. for players to consider possible reactions to their actions, may be illustrated by the following example. Example: Consider the following three coalition structures, with the corresponding made-up payoffs for individual players: • The grand coalition, {(123)}, with profits n} 2 3 = 4.5, n^ 2 3 = 4, U\23 = 5; • A paired structure, {(13), 2}, with profits n} 3 = 3.5, n^ 3 = 3, n j 3 = 4.5; • A paired structure, {(12), 3}, with profits n} 2 = 4, n^ 2 = 5, H ^ 2 = 4. Assume that the current status quo is the grand coalition. If player 2 decides to deviate, {(123)} ^ 2 {(13), 2}, it results with a paired structure in which his profit CHAPTER 3. FORMATION OF ALLIANCES 75 decreases from 4 to 3, and such a deviation is not likely to occur in a myopic con-text. However, if we assume a farsighted environment, a paired structure {(13), 2} becomes a new status quo after this deviation by 2, and the corresponding profit for 1 is 3.5. Player 1 can now increase his profit to 4 by jointly deviating with 2, {(123)} -^ 2 {(13), 2} —^ 2 {(12), 3}, and 2 is likely to participate in such devia-tion, because his profit in this coalition structure is higher than in both remaining structures. Observe that a joint deviation of 1 and 2 was not likely to occur when the status quo was the grand coalition, because it would have resulted with a decrease in profit for player 1, from 4.5 to 4. Thus, using a farsighted solution concept may lead to significantly different set of stable structures compared to those obtained by using myopic solution concepts. A solution concept that allows players to look ahead and consider possible further deviations, and which considers deviations by coalitions where subcoalitions may further deviate with players outside that coalition, is the largest consistent set, intro-duced by Chwe (1994). It is defined below, and is used as a stability criterion in our analysis of stable alliance structures. Let us denote by -<j the players' strong preference relations, described as follows: for two coalition structures, B\ and <B2, Bi ^ B2 & n f 1 < n f 2 , where n f is a retailer i's profit in the coalition structure B. If B\ -<i B2 for all i G S, we write B\ -<s B2. Denote by ^ 5 the following relation: B\ —^ 5 B2 if the coalition structure B2 is obtained when S deviates from the coalition structure B\. We say that B\ is directly dominated by B2, denoted by B\ < B2, if there exists an S such that Bi &2, and B\ <s &2- We say that B\ is indirectly dominated by Bm, denoted by B\ <C Bm, if there exist B\, B2, B3,..., Bm and S\, S2, S3,..., 5 m _i such that Bi a n d Bi -<st Bm for i = 1, 2 ,3 , . . . , m — 1. A set Y is called consistent if B G Y if and only if for all V and S, such that CHAPTER 3. FORMATION OF ALLIANCES 76 B V, there is an Z G Y, where V = Z or V <C Z, such that B ^ s Z. Since every coalition considers the possibility that, once it reacts, another coalition may react, and then yet another, and so on, a consistent set incorporates farsighted coalitional stability. If Y is consistent and B G Y, it does not imply that B is necessarily stable, but that it is possible for B to be stable. However, if B Y, B cannot be stable. The following is an example of the largest consitent set. Example: Consider the following set of all possible coalition structures and corre-sponding profits for individual players: • The independent structure, {1, 2, 3}, with profits rix = 4, I I 2 = 1, II3 = 2.5; • A paired structure, {(12), 3}, with profits n} 2 = 5,n^ 2 = 2, H p = 2; • A paired structure, {(13), 2}, with profits n 1 3 = 4.5, n^ 3 = 0.5, U\3 = 5; • A paired structure, {(23), 1}, with profits n 2 3 = 2.5, n 2 3 = 2.5, n 2 3 = 3; • The grand coalition, {(123)}, with profits II}23 = 3.5, n^ 2 3 = l , n 1 2 3 = 3.5. Observe first that all three pairs of players are compatible - in each paired structure, the profit of both paired players is higher than in the independent structure. There-fore, the independent structure is not stable. Furthermore, both paired coalitions (12) and (13) can benefit by deviating from the grand coalition, so {(123)} is not stable either. Hence, let us consider paired structures. Observe that the profit for player 1 is larger when he is paired with 2 then when he is paired with 3, IT\2 > U\3, hence (13) ^ (12). Similarly, (12) ^ 2 (23) and (23) ^ 3 (13). Consider now a paired structure {(12), 3}. Since 3 is the unpaired player, he cannot change this structure unilaterally. As mentioned above, players 1 and 2 are compatible, hence neither of them would want to deviate alone, which would lead to the independent structure and a decrease in their individual profits. Further, profit CHAPTER 3. FORMATION OF ALLIANCES 77 for 1 and 2 is lower in the grand coalition, so they would not want to jointly deviate with 3 and form the grand coalition. This leaves us with possible deviations by two pairs of players, 1 and 3, and 2 and 3. Since the profit for player 1 is at its highest when he is paired with 2, he would not benefit from a joint deviation with 3. On the other hand, (12) (23), and the profit for 3 is higher when he is with 2 than when he is the unpaired player, so we may consider a joint deviation by 2 and 3, {(12), 3} -^2,3 {(23), 1}. The new status quo, after this deviation, is {(23), 1}, and the similar analysis as above shows that there will be no unilateral deviations by individual players, or joint deviations by all three players. Since (12) < 2 (23), 2 would not want to jointly deviate with 1, but (23) ^ 3 (13) implies that 3 would benefit from a deviation with 1. Such deviation, {(23), 1} —^3 {(13), 2}, would benefit player 1, since his profit is higher with 3 than when he is the unpaired player. However, in this new coalition structure, the profit for player 2 is only 0.5, while his profit in {(12), 3} was 2. Since 2 was a member of the first deviating coalition, (23), and this deviation eventually resulted with an outcome in which the profit for player 2 has decreased, this initial deviation is not likely to happen, and {(12), 3} is in the largest consistent set. In a similar way, it can be shown that the remaining two paired coalition structures also belong to the largest consistent set. Hence, the largest consistent set in this case contains three possibly stable coalition structures. The largest consistent set is unique, and has the merit of "ruling out with con-fidence" . For a more detailed analysis of farsighted coalitional stability, see Chwe (1994). Xue (1998) has refined Chwe's largest consistent set by introducing the notion of perfect foresight. Finally, for a recent survey on coalition formation see Greenberg (1994), and for a recent analysis of stability in oligopoly markets using Chwe's largest consistent set criterion see Masuda, Suzuki, and Muto (2000). CHAPTER 3. FORMATION OF ALLIANCES 78 3.6 Stable coalition structures In this section, we characterize a stable alliance structure as a function of product substitutability and reduction in wholesale prices due to alliance membership. We only consider the cases where either % = 0 or 0i3- —> 1 for all i,j 6 {1,2,3}, but the analysis can easily be extended to arbitrary values of the %'s. There are three possible stable alliance structures we need to consider: an alliance of all three retailers (the grand coalition), a two-retailer alliance (a paired structure), and the case where all the retailers act independently (the independent structure). Because of difficulties involved in evaluation of the exact benefits of each retailer and, consequently, determination of the amounts of side payments among the alliance members, and perhaps because of possible legal restrictions, it appears that an alliance model without side payments is the one prevalent in real life. A n example of such a model is Covisint, which operates as an independent business in which G M , Ford, and DaimlerChrysler have equal ownership. Therefore, we consider here an alliance model without side payments among the retailers. When all products are non-substitutable, the only stable structure is the alliance of all retailers. Indeed, it follows from Tables 3.1 and 3.2 that the grand coalition would yield the largest profit for each one of the retailers. Thus, they all have an incentive for a joint deviation from any other coalition structure to the grand coalition. Formally, we have: Theorem 3.8 When none of the products are substitutable, the consistent set con-tains a single stable point, the grand coalition {(ijk)}. It is, therefore, always beneficial for retailers to participate in the grand coalition if their products are not substitutable. Examples of such alliances are those be-tween Oracle, Sears, and the French retailer Carrefour, or corProcure, the horizontal e-marketplace established by Australia's leading companies, among which are Am-cor (cartonboard), A M P (finance), Australia Post, Coca-Cola (soft drinks), Foster's (beer), Quantas (airline), and others. CHAPTER 3. FORMATION OF ALLIANCES 79 Theorem 3.8 describes the only case where the alliance of all three retailers is the unique stable structure. Theorems 3.9, 3.11 and 3.12 describe some other instances wherein some of the products are substitutable and the grand coalition may be one of several potentially stable structures. Before we proceed, we need the following definition. When there are no pairs of players who prefer each other to the third player, i.e., (ik) <i (ij) <j (jk) <k (ik) hold, we will denote it by [ijk] and call it circular preferences. Finally, recall that Table 3.4 summarizes preference conditions for two-member alliances. Let us start by analyzing the case with two highly substitutable products, where the third product is non-substitutable by either of the remaining two products. Theorem 3.9 When two products, j and k, are highly substitutable, and the third product, i, is non-substitutable by either of the remaining two products (Oij = 9lk = 0, 9jk 1), then: 1. If i and j prefer each other to retailer k, {(ij),k} is in the consistent set. The grand coalition {(ijk)} is also in the consistent set if and only if, in addition, retailers j and k benefit equally when k joins the alliance (ij). 2. If circular preferences [ijk] hold, then: (a) If k prefers being the unpaired retailer to pairing with the retailer he least prefers, j, {(ij),k} is in the consistent set. The grand coalition {(ijk)} is also in the consistent set if and only if, in addition, retailers j and k benefit equally when k joins the alliance (ij). (b) Otherwise, if k is indifferent between being the unpaired retailer and pairing with j, the consistent set contains all paired structures, {(ij), k}, {(jk), i}, and {(ik),j}. The grand coalition {(ijk)} is also in the consistent set if and only if, in addition, retailers j and k benefit equally when one of the three retailers joins a paired alliance of the other two retailers. CHAPTER 3. FORMATION OF ALLIANCES 80 Next, consider the case with two non-substitutable products, where the third product is highly substitutable by both remaining products. It leads to the following result. Theorem 3.10 When two products, i and j, are not substitutable, and the third product, k, is highly substitutable by both i and j (6ij = 0,0^ —> l,@jk ~^ 1); the consistent set contains a single stable structure {(ij),k}, whenever i and j are com-patible. Otherwise, if i and j are not compatible, the unique stable coalition structure is the independent structure {i,j,k}. Observe that there is always a unique stable structure for this case, and it is never the grand coalition. Lastly, let us assume that all products are highly substitutable. First, consider the case with a pair of retailers who both prefer each other to pairing with the remaining retailer. Theorem 3.11 When all products are highly substitutable, and there is a pair of retailers, i and j, who prefer each other to the third retailer, k, then: 1. If i and j are compatible, then {(ij),k) is in the consistent set. The grand coalition {(ijk)} is also in the consistent set if and only if, in addition, all retailers benefit equally when k joins the alliance (ij). 2. If i and j are not compatible, while i and k are compatible, then: (a) If j prefers pairing with i to being the unpaired retailer, {(ij),k} is in the consistent set. (b) Otherwise, if j prefers being the unpaired retailer to pairing with i, the unique stable coalition structure is {(ik),j}. 3. If there are no pairs of compatible retailers, the unique stable coalition structure is the independent structure {i,j,k}. CHAPTER 3. FORMATION OF ALLIANCES 81 Thus, when all products are highly substitutable, and there is a pair of retailers who both prefer each other to pairing with the remaining retailer, the grand coalition is in the consistent set if and only if i and j are compatible and all retailers benefit equally from participation in the grand coalition. When there is no pair of retailers preferring each other, we have: Theorem 3.12 When all products are highly substitutable, and circular preferences [ijk] hold, the consistent set is defined as follows: 1. If there is at least one pair of compatible retailers, then: (a) If all retailers prefer pairing with the retailer they least prefer to being the unpaired retailer, then the consistent set contains all paired structures, {(u)>^}> .?'}> and {0'^ )>*}- The grand coalition {(ijk)} is also in the consistent set if and only if, in addition, all retailers benefit equally when one of the retailers joins a paired alliance of the other two retailers. (b) If exactly one retailer, k, prefers being the unpaired retailer to pairing with the retailer he least prefers, then {(ij),k} is in the consistent set. The grand coalition {(ijk)} is also in the consistent set if and only if, in addition, all retailers benefit equally when k joins the alliance (ij). (c) If both retailers i and k prefer being unpaired to pairing with the retailer they least prefer, the unique stable coalition structure is obtained by pairing of compatible retailers, {(ij),k}. 2. If there are no pairs of compatible retailers, then the independent structure {i,j,k} is in the consistent set. This is a unique stable coalition structure, unless all retailers benefit equally upon the formation of the grand coalition, whence the grand coalition {(ijk)} is in the consistent set as well. Observe that, when all products are highly substitutable, the grand coalition may be one of the possible stable structures in most cases, provided it brings equal benefits to all retailers, that is, if there are no retailers who benefit more or less than the other retailers. CHAPTER 3. FORMATION OF ALLIANCES 82 3.7 Concluding remarks The objective of this essay was to provide a better understanding for the motivation behind the formation of alliances and the benefits that an alliance provides to its members. For that purpose, we have studied the effect of formation of an alliance on the profits of retailers in the marketplace, and we provided conditions for stability of alliance structures among three or fewer retailers of possibly substitutable products. We have shown that in the model wherein all pairs of products are non-substitutable, the alliance of all retailers is the only stable set. However, once some of the retailers have substitutable products, this is not the case anymore. Thus, for example, when only one pair, say i and j, of the products (out of the three pairs) is not substitutable, the alliance of all three retailers is never in the consistent set. Rather, in this case either the alliance of i and j or the independent structure is the stable set. Similarly, when all products are highly substitutable, the alliance of all three retailers is in the consistent set only when all retailers benefit precisely equally from that alliance. The more likely solutions in the consistent set are a paired alliance, when there exists a pair of compatible retailers, or the independent structure wherein no alliance is formed, if all retailers are incompatible. Although there are only three retailers in our model, we feel that our results can provide some insight into more general cases. Indeed, if all the retailers have non-substitutable products, we can infer that the highest profit for each one of the retailers would be realized in the alliance of all retailers. When retailers have both non-substitutable and highly substitutable products, it appears that an alliance of all retailers whose products are non-substitutable, in which some compatibility con-ditions among the retailers are satisfied, should benefit all its participants. Finally, if all retailers have highly substitutable products, an alliance of all compatible retailers appears to be in the consistent set. In addition, if all retailers benefit equally from the formation of the grand coalition (in terms of reduction in their wholesale prices), the alliance of all retailers could be stable as well. As it should be evident from our analysis, the decrease in wholesale prices and CHAPTER 3. FORMATION OF ALLIANCES 83 processing costs has a relatively minor effect on the profit firms realize by forming or expanding an alliance, and, as a result, on the alliance stability. Indeed, a firm may realize a decrease in its wholesale prices and processing costs by, for example, joining an alliance, and still have its profit decrease as a result of joining this alliance. It is the relative decrease in wholesale prices and processing costs, as presented in Tables 3.1-3.3, which should be monitored to determine the benefits and wisdom of either forming, joining, or expanding an alliance. A majority of exchanges today are vertical exchanges, formed along specific indus-tries. They may be privately owned by a single company (e.g., B M W or Volkswagen), or they may be owned by several industry leaders (e.g. Covisint). Our results for the model with high substitutability among all products show that an alliance of all retailers is not always stable. It may be stable only if it provides equal benefits to all its participants. Thus, for instance, if there is a new company, which benefits signifi-cantly more from a membership in an alliance than the other participants, the grand coalition is never stable. A similar conclusion can be made if one of the potential alliance members is a well established company, which would benefit significantly less than the other participants. G M , Ford, and DaimlerChrysler are the three largest companies in the automo-tive industry. Each of them has been present in the market for a long time, sells several millions vehicles per year, and possesses manufacturing facilities in various countries. It seems reasonable, therefore, to assume that each company has a pool of good suppliers, has equally efficient processes for dealing with its suppliers, and that their alliance would generate reductions in wholesale prices that are close to being equal. We can also assume that there is a high substitutability among their products. Under these assumptions, the profitability from membership in the alliance of all three of them, along with the possible stability of this alliance, are consistent with our results. We note, however, that B M W and V W have decided to build their individual marketplaces and not join the Big Three. This may imply that B M W and V W believe that their benefits from alliance membership would be smaller compared to those of other alliance members. However, other, idiosyncratic reasons may justify CHAPTER 3. FORMATION OF ALLIANCES 84 their decision as well 1 3 - security concerns, mode of relationship with suppliers, a prior dispute between V W and G M (involving a former G M executive), or BMW's unsuccessful partnership with Rover. We have also seen that some major electronic companies prefer not to join their rivals in the formation of Internet marketplaces. As mentioned earlier, Sun Microsys-tems regards its list of suppliers as highly confidential. Thus, Sun most likely feels that the benefits it can realize by joining an alliance would be smaller compared to benefits realized by other potential partners, and therefore, prefers to stay indepen-dent. Sun's reluctance to participate in an alliance with its rivals, where there is a high level of substitutability among products, is consistent with our results. That is, the small decrease in the wholesale prices and processing costs that Sun believes it would realize, compared to other members, imply that Sun feels that it is incompat-ible with its rivals, and that its participation in such an alliance will actually reduce its profits. It should be noted that our model has not incorporated a possible reaction by the suppliers, some of whom, quite likely, will see their profit margins reduce substantially due to the introduction of electronic exchanges. It appears reasonable that the sup-pliers, in general, would prefer not to deal with a single exchange which incorporates all the major producers in the industry. Indeed, such an exchange would limit the options available to suppliers, and would force them, at least for some time, to "play" by the exchange rules. In that respect, the encouragement13 provided by some sup-pliers who, in order to save some information technology and related cost, have urged the Big Three car manufacturers to cease the development of individual exchanges and embark on developing a common electronic exchange seems to be unwise. On their part, the Big Three, perhaps in order to limit the suppliers' options, appear to prefer13 that all car manufacturers join Covisint. Our analysis reveals that, in gen-eral, a relatively small or less efficient car manufacturer would benefit from joining Covisint, but the inclusion of such a member could possibly decrease the profits of the bigger manufacturers in this exchange. 1 3 "Covis int likely to have rivals", Detroit Free Press, www.freep.com, July 13, 2000 CHAPTER 3. FORMATION OF ALLIANCES 85 As mentioned earlier, this essay represents an initial attempt to obtain some in-sights into the motivation behind the formation of alliances. Some of the assumptions made in this model, such as linear and deterministic demand, or complete informa-tion, are rather restrictive, and their relaxation can provide an interesting area for future research. We believe that this subject is becoming increasingly important with the advancements in B2B exchanges. For some additional work on coalition formation and supply chain coordination in electronic markets, see Jin and Wu (2000, 2001). 3.8 Append ix Proof of Proposition 3.2: The first statement of the proposition holds since the coefficients of Wj (or Wk) in the expressions for pt,qt, and I7.J in (3.3) and (3.4) are non-negative. For the second statement, observe that Bk > 0 whenever Qld > 0 or dikdjk > 0, and that jj > 0. • Proof of Proposition 3.6: It follows from Observation 3.3 that the wholesale prices for retailers j and k decrease upon the formation of the alliance (jk). Consequently, Proposition 3.2 implies that z's profit decreases. Formally, n f = — {Ai-ia-AJwi + il-ejJhjBkil + W j - A f ) + 7 * ^ ( 1 + w f c -A{ f e )]} Proof of Theorem 3.9: Let us denote 012 = 013 = 0, 0 2 3 -> 1. Table 3.1 (b) and (c) imply that 1 is compatible with both 2 and 3. Without loss of generality, let us assume (13) <i (12). —2 - (1 - 9jk)(7jBkAf + jkBjAi") 2 1. Observe that, if we choose i = 3,j = 2, and k = 1, then by Table 3.4 (e) CHAPTER 3. FORMATION OF ALLIANCES 86 {(13) , 2} ^ 3 { (23) , 1} holds if Af - Af > A f . Similarly, if we choose i = 2, j = 3, k = 1, then, from Table 3.4 (e) it follows that { (12) , 3} < 2 { (23) , 1} if Af - Af > Af. Therefore, { (12) , 3} r<2 { (23) , 1} and { (13) , 2} r<3 { (23) , 1} cannot both be true, and either 2 or 3 strictly prefers pairing with 1 to (23). If we assume that (12) < 2 (23), then (23) -< 3 (13), and because we assumed that (13) d i (12), circular preferences [123] hold. This case is handled in the second part of the proof, and thus we will assume that (23) -< 2 (12). P A I R E D S T R U C T U R E S . Since (13) d i (12), neither 1 nor 2 want to secede from { (12) , 3} , unless all retailers can strictly increase their profits in the grand coalition. Because both 1 and 2 benefit from their joint deviation to { (12) , 3} , neither { (13) , 2} nor { (23) , 1} are stable, unless 1 is indifferent between 2 and 3. In the latter case, since 1 and 3 are compatible, { (13) , 2} is also in the consistent set. I N D E P E N D E N T S T R U C T U R E { 1 , 2 , 3 } . Since 1 is compatible with both 2 and 3, a joint deviation of, e.g., 1 and 2 benefits both retailers, hence { 1 , 2 , 3 } is unstable. G R A N D C O A L I T I O N { (123)} . It follows from Table 3.4 (b) and Table 3.3 (b) that retailer 1 prefers { (123)} to all other coalition structures, so he has no incentive to secede from the grand coalition. Table 3.2 (c) (choose i = 2, j = 1, k — 3) implies that retailers 2 and 3 prefer the grand coalition to { (12) , 3} only when A 2 — Af > A 3 and A 3 > A2 — Af. Both inequalities can be satisfied only when both retailers benefit equally from the grand coalition, that is, A 2 — Af = A 3 , and are indifferent between { (123)} and { (12) , 3 } . Therefore, the grand coalition does not result in a strict increase of all retailers' profits, and both the paired structure { (12) , 3} and the grand coalition are in the consistent set. Now, assume that some retailers prefer { (12) , 3} to the grand coalition, i.e. A 2 - Af ^ A 3 . Consider first the case A 2 - Af > A 3 . From Table 3.2 (c), this implies { (123)} -< 3 { (12) , 3} . Thus, since being unpaired is better for 3 than the grand coalition, a deviation { (123)} ^ 3 { (12) , 3} strictly increases 3's profit. Therefore, since { (12) , 3} d 3 { 1 , 2 , 3 } , we can conclude that the grand CHAPTER 3. FORMATION OF ALLIANCES 87 coalition is not stable. Next, assume A 2 - A ^ 2 < A 3 , which implies {(123)} < 2 {(12), 3} and {(12), 3} -<3 {(123)} (see Table 3.2 (c)). Although a deviation from the grand coalition may decrease his profits, 2 may choose to secede in anticipation of a further deviation with retailer 1, {(123)} ^ 2 {(13), 2} ->>li2 {(12), 3} (which is possible since 1 prefers 2). Thus, a deviation may lead to a strict increase of 2's profit, and the grand coalition is unstable. 2. Now, assume that circular preferences [123] hold. Thus, we can assume that (12) < 2 (23), which corresponds to A f < Af - Al22 (see Table 3.4 (e)). (a) First, suppose Af < Af - A ^ 2 . Then, by Table 3.1 (e), retailers 2 and 3 are not compatible, and by Proposition 3.7, this implies that {(23),1}^ 3 {(12),3}. P A I R E D S T R U C T U R E {(12),3}.. Since both {(12),3} and {1,2,3} are strictly better for 3 than {(23), 1}, 3 does not want to join 2 in a deviation from either of the two afore mentioned structures. Since 2 is compatible with 1, 2 does not want to secede from the coalition (12), and 1 prefers 2 anyway. Thus, {(12), 3} is in the. consistent set, unless all retailers can strictly increase their profits by forming the grand coalition. P A I R E D S T R U C T U R E {(23), 1}. Retailer 3 strictly benefits from a devia-tion, hence this coalition structure is unstable. P A I R E D S T R U C T U R E {(13), 2}. Since retailers 1 and 2 are compatible, n^ 2 > n 2 . Hence, by Proposition 3.6, {(13), 2} ^ 2 {(12), 3}. Since it is assumed that (13) (12), both 1 and 2 benefit from the joint deviation {(13), 2} —^i2 {(12), 3}, and {(13), 2} is not stable, unless 1 is indifferent between 2 and 3, whence {(13), 2} is also in the consistent set. I N D E P E N D E N T S T R U C T U R E {1,2,3}. Instability follows from the compat-ibility of 1 and 2. G R A N D C O A L I T I O N {(123)}. The analysis of this alliance in part (1) is valid for this case as well. CHAPTER 3. FORMATION OF ALLIANCES 88 (b) Now, suppose A f > A f — A22. Together with the above assumption A f < A f - A f , we can conclude that A f = A f - A f . That is, 3 cannot strictly prefer pairing with the retailer he least prefer, 2, to being the unpaired retailer, and both 2 and 3 are indifferent between {(12), 3} and {(23), 1}. P A I R E D S T R U C T U R E S . Consider first the coalition structure {(12), 3}. Since it is assumed that (13) d i (12), 1 does not want to secede. On the other hand, 2 and 3 may consider the formation of the alliance (23). Since (23) X 3 (13), and 1 is compatible with 3, both 1 and 3 benefit from a further deviation, {(12), 3} ^ 2 > 3 {(23), 1} —^3 {(13), 2}. This results in a decrease of 2's profit, hence 2's original deviation is deterred by a joint deviation of 1 and 3. Thus, {(12), 3} is in the consistent set, unless all retailers strictly increase their profits by deviating to the grand coalition. Similar analysis shows that the remaining two paired structures are also in the consistent set. I N D E P E N D E N T S T R U C T U R E {1,2,3}. Instability follows from, e.g., the compatibility of 1 and 2. G R A N D C O A L I T I O N {(123)}. Similarly as in part (1) of this proof, it is easy to show that the grand coalition can be stable if either A 2 — A f = A3, or A 3 - A f = A 3, or A 2 - A f = A 3 - A f . That is, the grand coalition is in the consistent set if retailers 2 and 3 are indifferent between it and any of the paired structures. Observe that the grand coalition does not strictly increase all retailers' profits in any of the cases, therefore all paired structures are in the consistent set. If none of the above equations hold, an analysis similar to that in part (1) of this proof shows that the grand coalition cannot be stable. • Proo f of Theorem 3.10: Let us denote 912 = 0,9W ->• 1, 922, ->• 1. G R A N D C O A L I T I O N {(123)}. It follows from Table 3.2 (d) that retailer 3 always benefits from a deviation, since his profit is at its lowest in the grand coalition. Therefore, {(123)} is not stable. CHAPTER 3. FORMATION OF ALLIANCES 89 For the analysis of the remaining coalition structures, let us assume first that 1 and 2 are compatible. P A I R E D S T R U C T U R E {(23), 1}. Table 3.1 (g) implies that {1,2,3} is better for 3 than pairing with either of retailers 1 or 2, hence 3 would prefer to secede. 1 and 2 may then jointly deviate, {(23), 1} {1,2,3} - ^ 1 2 {(12), 3}. By Proposition 3.7, it follows that pairing with 2 never benefits 3 whenever n 3 > U23, that is, {(23), 1} -<3 {(12), 3}. Therefore, {(23), 1} is not stable since the deviation strictly increases 3's profit. Non-stability of {(13), 2} is shown in a similar way. P A I R E D S T R U C T U R E {(12), 3}. Let us first assume that at least one of retailers 1 or 2 prefers retailer 3. Without loss of generality, we can assume (12) -<2 (23). We have shown above that {(23), 1} -<3 {(12), 3}, hence 3 prefers not to deviate with 2 and form the alliance (23). Since it is assumed that (13) -<i (12), {(12), 3} is in the consistent set. If, on the other hand, both retailers 1 and 2 prefer each other to retailer 3, that is, (13) (12) and (23) < 2 (12), then {(12), 3} is again in the consistent set. I N D E P E N D E N T S T R U C T U R E {1,2,3}. Instability follows from the compatibility of 1 and 2. Next, suppose that 1 and 2 are not compatible. P A I R E D S T R U C T U R E {(23), 1}. As we have shown above, 3 would prefer to secede from this structure. Because of incompatibility of 1 and 2, there are no further deviations from {1,2,3}. Thus, such a deviation by 3 strictly increases its profit, hence {(23), 1} is unstable. Non-stability of {(13), 2} is shown in a similar way. P A I R E D S T R U C T U R E {(12), 3}. Since 1 and 2 are not compatible, a deviation is better for at least one of them. No further deviations from {1, 2, 3} will occur, since 3 prefers the independent structure to pairing with any of the two remaining retailers. Therefore, {(12), 3} is unstable. I N D E P E N D E N T S T R U C T U R E {1,2,3}. It follows from the above analysis that {1,2,3} is in the consistent set. • CHAPTER 3. FORMATION OF ALLIANCES 90 P r o o f of Theorem 3.11: Without loss of generality, let us denote players who prefer each other to the third player by 1 and 2; therefore, (13) (12), (23) < 2 (12). 1. Let us first assume 1 and 2 are compatible. P A I R E D S T R U C T U R E S . Because of their compatibility, neither 1 nor 2 want to secede from {(12), 3}. It is easy to show that the remaining two paired structures are not stable, since both 1 and 2 prefer the alliance (12) to any other paired alliance. In the degenerate cases, where 1 is indifferent between 2 and 3, {(13), 2} is also in the consistent set. If, in addition, 2 is also indifferent between 1 and 3, we obtain circular preferences, which is considered in Theorem 3.12. I N D E P E N D E N T S T R U C T U R E {1,2,3}. Instability follows from the compatibility of 1 and 2. G R A N D C O A L I T I O N {(123)}. It follows from Table 3.2 (h) that all three retailers prefer {(123)} to the possibly stable structure {(12), 3} if 2 ( A ! - A l 2 ) > ( A 2 - A 2 2 ) + A 3 , 2 ( A 2 - A 1 2 ) > ( A 1 - A 1 2 ) + A 3 , and 2 A 3 > ( A 1 - A l 2 ) + ( A 2 - A 1 2 ) . A l l three inequalities can hold simultaneously only as equations, in which case Ai — A p = A 2 — A\2 = A 3 . Thus, the grand coalition can be stable when it provides equal benefits to all retailers, when retailer 3 joins {(12), 3} to form {(123)}. Let us assume that the equal benefit assumption does not hold. That is, at least one retailer prefers {(12), 3} to {(123)}. • If 2 A 3 < ( A i - A} 2 ) + ( A 2 - A 1 2 ) , then Table 3.2 (h) implies {(123)} ^ 3 {(12), 3}, and {(123)} {(12), 3} is a deviation that strictly increases 3's profit. CHAPTER 3. FORMATION OF ALLIANCES 91 • If 2(AX - A | : 2(A 2 - Al2 ) < ( A 2 - A f ) + A 3 , and ) < (Aj - A} 2 ) + A 3 , it follows from Table 3.2 (h) that both {(123)} {(12), 3} and {(123)} -<2 {(12), 3}. Retailers 1 and 2 can, therefore, jointly deviate and strictly increase their profits. • Lastly, let us assume that only one of the retailers, 1 and 2, wants to secede. Without loss of generality, let us assume 2(AX - A} 2 ) < ( A 2 - A 1 2 ) + A 3 , and 2 ( A 2 - A 2 2 ) > ( A 1 - A } 2 ) + A 3 . Then, Table 3.2 (h) implies that {(123)} ^ {(12), 3} and {(12), 3} ^2 .{(123)}. If 1 secedes, then since (23) d 2 (12), player 2 may consider a further deviation with 1, {(123)} —h {(23), 1} — ^ 2 {(12), 3}, which leads to a strict increase in I's profit. Therefore, if at least one retailer prefers the paired structure, {(123)} is unsta-2. Let us now assume that 1 and 2 are not compatible, but 1 is compatible with 3. Together with (13) d i (12), this implies that 2's profit strictly decreases in the alliance (12). (a) Since it is assumed that 2 prefers pairing with 1 than being the unpaired retailer, it follows from Proposition 3.7 that 2 A f > A } 2 - A } 3 - A f . Fur-ther, since 2's profit strictly decreases by joining 1, {(12), 3} -<2 {1,2,3}. P A I R E D S T R U C T U R E S A N D T H E I N D E P E N D E N T S T R U C T U R E . 2'S devia-tion from the alliance (12) is deterred by a further joint deviation of 1 and 3, {(12), 3} ^ 2 {1,2,3} ^ 1 3 {(13), 2}, which decreases 2's profit. Since (13) d i (12), 1 does not want to secede from (12), and {(12), 3} is, there-fore, in the consistent set. It is easy to see that none of the coalition ble. CHAPTER 3. FORMATION OF ALLIANCES 92 structures {(13), 2}, {(23), 1}, or the independent structure {1,2,3}, can be stable, unless 1 is indifferent between 2 and 3, whence {(13), 2} is also in the consistent set. G R A N D C O A L I T I O N {(123)}. The analysis of the stability of the grand coalition for this case is similar to that in part (1) of this proof. Therefore, {(123)} is in the consistent set only if the retailers are indifferent between the possibly stable structure {(12), 3} and the grand coalition, that is, if A t - A J 2 = A 2 - A 1 2 = A 3 . By assumption, {(23), 1} < 2 {1,2, 3}. Thus, 2's profit decreases when joining 3, which implies that 3's profit increases when joining 2. Therefore, {1,2,3} ^ 3 {(23), 1}. By Table 3.1 (h), this implies that A f > 2Af. Assumption 3.5 implies that A 2 < A^ 2 + Af and A 3 > A 2 3 . Thus, A 3 > A 2 3 > 2 A 2 3 > A 2 3 > A 2 - A 2 2 , and the above condition, A 2 — A 2 2 = A 3 , cannot be satisfied. Consequently, {(123)} is unstable. (b) If 2 does not prefer pairing with 1 than being the unpaired retailer, then {(12), 3} ^ 2 {(13), 2} and 2 A 1 2 < A\2 - A 1 3 - A 1 3 . Then, it follows from Table 3.1 (h), Proposition 3.7, and since it is assumed that 1 and 2 prefer each other than 3, i.e., (23) -<2 (12), that {(23),1} < 2 {(12),3} < 2 {(13),2} X 2 {1,2,3}. P A I R E D S T R U C T U R E S A N D T H E I N D E P E N D E N T S T R U C T U R E . Since (23) -<2 (12) and n 2 > n p , a deviation from both (12) and (23) strictly in-creases 2's profit. Hence, since it is assumed that 2 prefers being unpaired than joining his preferred retailer, {(12), 3} and {(23), 1} are not stable. The same holds for {1, 2, 3}, because of the compatibility of 1 and 3. Since 2 does not want to pair with any of the two remaining retailers, neither 1 nor 3 have any incentive to secede from {(13), 2}, which is, therefore, in the consistent set. CHAPTER 3. FORMATION OF ALLIANCES 93 G R A N D C O A L I T I O N {(123)}. Recall first that 1 prefers 2 on 3, and 1 is compatible with 3. Thus, retailer I's profit increases upon joining 2. Since 1 and 2 are not compatible, 2's profit decreases upon joining retailer 1. Since 2 prefers 1 on 3, retailer 2's profit decreases upon joining 3. Thus, by Table 3.1 (f), 2 A 2 3 < A 2 3 . By assumption, 2 A 1 2 < A 1 2 - A } 3 - A 1 3 , and by Assumption 3.5, A 2 < A f + A f , A 3 > A f , A : > A f . The last five inequalities imply 2 A 2 < ( A f - A f ) + ( A f - A f ) < (Ax - A}3) + ( A 3 - A f ) . Now, similarly as in part (1) of this proof, it can be shown that all three retailers are indifferent between the grand coalition and the paired struc-ture {(13), 2} if A j — A f = A 3 - A f = A 2 . Suppose A i - A f = A 3 - A f . Then, the last inequality implies that A 2 < Ax — A f , hence A i — A f = A 2 cannot be satisfied. Therefore, at least one retailer prefers {(13), 2} to {(123)}, and it can.be shown, similarly as in part (1) of this proof, that this implies instability of the grand coalition. 3. Let as now assume that there are no pairs of compatible retailers. Then, the profit of one of the retailers, 1 or 2, strictly decreases in the alliance (12). Without loss of generality, let us assume n f < II 2. Then, it follows from (23) ^2 (12) that n f < n 2 as well. That is, 2's profit strictly decreases by pairing with either 1 or 3. Since 1 and 3 are not compatible, let us further assume IT > n f . P A I R E D S T R U C T U R E S A N D T H E I N D E P E N D E N T S T R U C T U R E . {(13), 2} —^ {1, 2, 3} is a deviation that benefits retailer 1, and no other paired coalition will be formed, since 2's profit is strictly higher in the independent structure. Similarly, deviations from {(12), 3} and {(23), 1} benefit retailer 2, hence none of the paired coalition structures can be stable. G R A N D C O A L I T I O N {(123)}. It follows from Table 3.3 (f) that all three re-tailers prefer {(123)} to {1,2,3} if 2A, > Aj + A k , for all i,j,k € {1,2,3}, * J k — i- These inequalities can hold simultaneously only as equations, CHAPTER 3. FORMATION OF ALLIANCES 94 in which case A x = A 2 = A 3 . This condition cannot be satisfied. Indeed, from Table 3.1 (f), if retailers 1 or 2 do not benefit from joining 3, then 3 benefits from an alliance with either 1 or 2, while 2 does not benefit from joining any of the remaining two retailers. Thus, at least one retailer prefers { 1 , 2 , 3 } to {(123)} , and the only stable coalition structure is { 1 , 2, 3} . • P r o o f of Theorem 3.12: Let us assume circular preferences [123], and thus (13) < { (12), (12) < 2 (23), (23) r<3 (13). 1. Since there is at least one pair of compatible retailers, let us assume 1 and 2 are compatible. (a) Let us first assume that both retailers 1 and 3 prefer pairing with their least preferred retailer than being unpaired. (Observe that 2, who prefers 3, prefers also pairing with 1 than remaining unpaired,since 1 and 2 are assumed to be compatible). Thus, { (23) , 1} -<\ {(13) , 2} , and {(12) , 3} ^ 3 { (23) , 1}. By Proposition 3.6, { (13) , 2} < 2 { 1 , 2, 3} , and since 1 and 2 are compatible, {1 , 2, 3} < 2 { (12) , 3} . P A I R E D S T R U C T U R E { ( 1 2 ) , 3 } . Since { (12) , 3} <2 { (23) , 1} and {(12) , 3} ^ 3 { (23) , 1}, 2 and 3 both benefit from a deviation to the coali-tion (23). Now, since (23) ^ 3 (13) and { (23) , 1} < X { (13) , 2} , 1 and 3 both benefit from a further deviation, { (12) , 3} - ^ 2 3 { (23) , 1} — ^ {(13) , 2} . This results in a decrease of 2's profit, thus deterring 2's original devia-tion. Retailer 1 prefers the alliance { (12) , 3} to all other paired structures or the independent structure, so he does not want to secede, and { (12) , 3} is in the consistent set. Similar analysis shows the remaining two paired structures are also in the consistent set. I N D E P E N D E N T S T R U C T U R E { 1 , 2 , 3 } . Instability follows from the compat-ibility of 1 and 2. G R A N D C O A L I T I O N { (123 )} . The analysis is similar to that in part (1) of the proof of Theorem 3.11. Hence, if Aj - A - J = Aj - A1- = Ak for some CHAPTER 3. FORMATION OF ALLIANCES 95 i,j,k, the retailers are indifferent between the grand coalition and a paired structure {{ij),k}, and {{ijk)} is in the consistent set as well. (b) Let us now assume that there is exactly one retailer who prefers being the unpaired retailer to pairing with the retailer he least prefers. Case 1: Retailer 1 is compatible with both 2 and 3. It follows that 3 must be the retailer who prefers being unpaired, and thus, by Proposition 3.7, 2 A f < A f - A } 2 - A f . P A I R E D S T R U C T U R E S . Consider the paired structure {(12), 3}. Retailer 3 prefers being unpaired to pairing with 2, and 2 is compatible with 1, hence 2 prefers not to secede. Since 1 prefers 2, {(12), 3} is in the consistent set. {(23), 1} is unstable, since 3 prefers to secede. Retailers 1 and 2 benefit from a deviation from {(13), 2}, unless 1 is indifferent between 2 and 3, whence {(13), 2} is in the consistent set. I N D E P E N D E N T S T R U C T U R E {1,2,3}. Instability follows from the compat-ibility of 1 and 2. G R A N D C O A L I T I O N {(123)}. The analysis is similar to that in part (1) of the proof of Theorem 3.11. Hence, if A j - A } 2 = A 2 - A f = A 3 , the retailers are indifferent between the grand coalition and a paired structure {(12), 3}, and {(123)} is in the consistent set as well. Case 2: Only retailers 1 and 2 are compatible. Assume first that 3 prefers to be unpaired than pairing with 2, while 1 prefers pairing with 3 than remaining unpaired. (Thus, by Proposition 3.7, 2 A f < A f - A f - A f , and 2 A f > A f - A f - A f ) . A similar analysis to that done above shows that {(12), 3} is in the consistent set. {(13), 2} is in the consistent set if 1 is indifferent between 2 and 3, and 3 prefers pairing with 1 than being unpaired, while the grand coalition is in the consistent set if A : - A } 2 = A 2 - A f = A 3 . Assume now that 1 prefers being unpaired than pairing with 3, while 3 prefers pairing with 2 than remaining unpaired. Thus, CHAPTER 3. FORMATION OF ALLIANCES 96 2 A f > A f - A f - A f , and 2 A f < A f - A f - A f . P A I R E D S T R U C T U R E S . Consider the structure {(23), 1}. Although 3 prefers 1, he does not want to secede, because 1 prefers being unpaired. Since 2 prefers 3, and 3 prefers pairing with 2 than being unpaired, this coalition structure is in the consistent set. {(13), 2} is unstable, since a deviation strictly increases the profit of retailer 1, and {(12), 3} is unstable, because 2 and 3.benefit from a joint deviation to {(23), 1}. I N D E P E N D E N T S T R U C T U R E {1,2,3}. Instability follows from the compat-ibility of 1 and 2. G R A N D C O A L I T I O N {(123)}. The analysis is similar to that in part (1) of the proof of Theorem 3.11. Hence, if A 2 - A f = A 3 - A f = A i , the retailers are indifferent between the grand coalition and the paired structure {(23), 1}, and {(123)} is in the consistent set. (c) Let us assume now that both 1 and 3 prefer remaining unpaired than pairing with their least preferred retailer. (Thus, 2 A f < A f — A [ 2 — A f , and 2 A f < A f - A f - A f ) . Hence, neither 1 and 3, nor 3 and 2, are compatible, and retailers 1 and 2 are the only compatible retailers. P A I R E D S T R U C T U R E S . Consider the structure {(12), 3}. Although 2 prefers 3, he does not want to secede, because 3 prefers being unpaired. Since 1 prefers 2, and 1 and 2 are compatible, this coalition structure is in the consistent set. {(13), 2} is unstable because (13) di (12), 1 and 2 are compatible, and 3 prefers being alone than pairing with 2, and {(23), 1} is unstable since 3 prefers to secede than pairing with 2. I N D E P E N D E N T S T R U C T U R E {1,2,3}. Instability follows from the compat-ibility of 1 and 2. G R A N D C O A L I T I O N {(123)}. The analysis is similar to that in part (1) of the proof of Theorem 3.11. Hence, if Ax - A f = A 2 - A f = A 3 , the retailers are indifferent between the grand coalition and the paired structure {(12), 3}. Since A i < A f + A f , the assumption CHAPTER 3. FORMATION OF ALLIANCES 97 2 A f < A f - A f - A f implies 2(Aj - A f ) < A f - A f - A f . Assum-ing, further, that A x - A f = A 3 , results in 2 A 3 < A f - A f - A f . Since A 3 > A f , this last inequality implies A f + A f < 0, which is a contradic-tion. Thus, the above condition, Ax — A f = A 3 , cannot be satisfied, and {(123)} cannot be stable. 2. If there are no pairs of compatible retailers, neither pair will deviate from the independent structure, which is then in the consistent set. It is the only stable structure, unless A i = A 2 = A 3 , whence the potential for the stability of the grand coalition follows from the similar analysis to that in part (3) of the proof of Theorem 3.11. I Chapter 4 The vehicle routing problem with pickups and deliveries ( V R P D ) on some special graphs 4.1 Introduction In this essay we study a vehicle routing problem defined on a graph G = (V,E), with vertex set V and edge set E. One, or perhaps two vertices in G are depots, or distribution centres, while other vertices in G represent customers. Some of these customers, referred to as delivery or demand customers, require a shipment from a depot and others, referred to as pickup or supply customers, have some supply which they would like to send to a depot. Items to be picked up at the supply vertices are distinct from those which have to be delivered to the demand vertices. The objective is to find a minimum length tour for a capacitated vehicle, which starts at a depot loaded with enough supply to satisfy the demand customers, travels in G while delivering supply to the demand customers and collecting supply from the 98 CHAPTER 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 99 supply customers without violating the vehicle capacity constraint, and returns to a depot. We will refer to the above routing problem as the vehicle routing with pickups and deliveries (VRPD) problem. Routing problems with pickups and deliveries have many real life applications, see, e.g., Bodin et al. (1983), and Casco et al. (1988) and references cited therein. For example, it is reported by Casco et al. (1988) that the U.S. grocery industry has saved over $160 million a year in distribution costs since 1982, by allowing vehicles on their delivery routes to pickup large volume from suppliers. Other applications studied in the literature include pickup and delivery from Quality Stores (Yano et al., 1987), pickup and delivery for ocean-borne transportation and pickup and delivery of inner-city under-privileged children to summer vacations at volunteer families living out of town (Mosheiov, 1994). In this essay, we study the V R P D problem on some special graphs with one or possible two depots, whose location(s) is either exogenously or endogenously deter-mined. Specifically, let | V | denote the number of vertices.in the graph. Then, we develop 0( |U|) time algorithms for the V R P D problem on a path and on tree graphs, 0 ( |V | ) and 0( |U | log |V ' | ) algorithm for a V R P D problem defined on a path with parametric initial capacity, and 0 ( |U | 2 ) and 0 ( | U | 2 log |V|) algorithms for a V R P D problem defined over a cycle graph. 4.2 Preliminary and notation Let G — (V, E) be an undirected graph with edge length function I : E —>• IR+ and request function r : V —>• Z. A vertex v for which r(v) > 0 is referred to as a supply or pickup vertex, and if r(v) < 0 then v is referred to as a demand or delivery vertex. A vehicle, N = A ^ c ^ c 2 ) , with a maximum capacity c 1 and initial load c 2, is available at a depot s E V. The vehicle routing with pickups and deliveries (VRPD) problem is concerned with finding a shortest tour for the vehicle which starts at s, travels along G while picking up supply from supply vertices and delivering supply to CHAPTER 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 100 demand vertices without violating the vehicle capacity constraint, and ends the tour at t £ V. Throughout this essay we let c, c = c1 — c2, denote the available capacity on the vehicle before any pickups or deliveries. It is assumed that the items to be picked up at the supply vertices are distinct from those delivered to the demand vertices, so that we cannot pickup an item from one vertex and deliver it to another vertex at the same trip. Further, we assume no preemption. That is, any item which is picked up at a supply vertex can only be unloaded at t, and any item loaded at s for delivery at a demand vertex v, can only be unloaded at v. A tour T in the V R P D problem is denoted by the sequence of vertices visited by the vehicle with the corresponding requests actually performed in each one of them. That is, T = {(x0 = s, b0), (x{, 6 1 ) , . . . , (xt = t,bt)}, where x{ £ V, (xi,xl+l) £ E, and denotes the number of units the vehicle either picked up or delivered at Xj. If bi < 0 (resp., bi > 0), a delivery (resp., pickup) was performed at vertex Xi. A feasible tour of the vehicle N = N(cl,c2), starts at s and ends at t after fulfilling all the requests associated with all the vertices in V without violating the vehicle's capacity constraint. An optimal tour is a feasible tour of minimum total length. In order to assure the existence of a feasible tour in G, we can assume that the total demand at all demand vertices is equal to c 2, and the total supply at all supply vertices is not larger than c 1. The following is an important property of feasible tours for the V R P D problem defined over a general graph G. Observation 4.1 Tour feasibility is maintained when deliveries are advanced or pick-ups are postponed. In other words, suppose a feasible tour T visits a vertex v more than once. If v is a demand vertex, then T can deliver all the requested items on its first visit to v without affecting the tour feasibility. If v is a supply vertex, then T can pickup all the supply available at v on its last visit to v without affecting the tour feasibility. CHAPTER 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 101 Actually, such changes to a feasible tour T may enable one to construct a shorter feasible tour therefrom. Accordingly, we have: Assumpt ion 4.2 In the sequel, unless otherwise stated, we restrict ourselves to fea-sible tours that deliver all the demand on their first visit to a demand vertex and pickup all the available supply on their last visit to a supply vertex. For a single exception to this assumption see Observation 4-4-4.3 T h e V R P D problem on a path We analyze in this section the V R P D problem on a path L, when s and t are the two end vertices of L. This special case is used subsequently to develop algorithms for the V R P D problem on tree and cycle graphs. The case where the locations of s and t are either fixed at some arbitrary vertices on the line, or are endogenously determined, are left to Section 4.4, where the tree case is studied. We use the following notation and definitions in this section. The path L has vertex set V = {v0, v x , v n + i } and edge set E = {U" = 0e; = (vi, vi+x)}. Thus, v0 and vn+i are the leaves of L. We assume that s = vQ,t = vn+x and recall that we denote by c,c = c1 — c2, the available capacity of the vehicle starting at s. Let Si = J2)=o rivj) denote the cumulative requirements on L from v0 to t>j. The partial sums Si induce a partition of the path L to maximal subintervals on which the partial sums Si strictly exceed the available capacity c, and maximal subintervals on which these partial sums do not strictly exceed c. We will refer to the former as positive subintervals and the latter as non-positive subintervals. For a positive subinterval, / , we denote by v(I) the lowest indexed vertex in / and by v(I) the vertex immediately following the maximal indexed vertex in I. Thus, if / = {vp, ...,vq}, then v(I) = vp and v(I) = vq+x. We will refer to v(I) as the upper boundary vertex of / . Observe that an upper boundary vertex must be a demand vertex. CHAPTER 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 102 A linear time algorithm for the V R P D problem on a path is presented below. A n a l g o r i t h m f o r t h e p a t h Step 1 Compute the partial sums Si,i = 1, ...,n Step 2 While traversing L from s to t do: (i) If Vi is a demand vertex (i.e., r(vi) < 0), unload the required demand at (ii) If Vi is a supply vertex (i.e., r(vi) > 0) and Si < c (i.e., Vi is contained in a non-positive subinterval), load the supply available at Vi. (iii) If Vi is a supply vertex and Si > c (i.e., Vi is contained in a positive subinterval), and this is the first visit of the vehicle at vt, do not load the supply at Vi. (iv) If Vi is an upper boundary vertex v(I) of a positive subinterval / do the following: • Unload the demand required by v(I). • Return idly to it (I). • Traverse the subinterval from v(I) to v(I) while loading all the supply at supply vertices on I. • Proceed from vx to The optimal tour, T, generated by the above algorithm can be equivalently described as follows. T starts at s and proceeds towards t. Deliveries are made at every demand vertex the first time the vehicle visits such a vertex. If a supply vertex, v, is reached, no supply was left behind to be picked up and the vehicle has enough capacity, it picks up all the supply at v. If the vehicle does not have enough capacity to load the supply at v, it proceeds towards t leaving the supply behind. Once some supply was left behind, the vehicle continues to proceed towards t without picking up any supply, until T first reaches a vertex u at which it has enough capacity to pick up all the CHAPTER 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 103 supply left behind. It then returns idly to the supply vertex v closest to s that has available supply, and then moves back towards u while picking up all supply between v and u. The length of the optimal tour, w(T), generated by the above algorithm is given by w(T) = £ ( / ( e i ) : S, < c) + 3 £ ( / ( e i ) : 5, > c), where e2 = (vl, vi+l). In the correctness proof of the algorithm we use the following lemma. L e m m a 4.3 An optimal tour T for the VRPD (L, r, N, v0, vn+i) problem from s = v0 to t = vn+i traverses every edge in L either once or three times. Correctness of the a lgor i thm The sequence of partial sums, Si, denotes the difference between the total supply and the total demand of vertices in the subpath s — Vi. When Si does not strictly exceed c, the initial available capacity of the vehicle, the vehicle can perform all the supply and demand requests in the subpath s — Vi without leaving this subpath, i.e., without traversing edge e; = (vi,Vi+i). That is, when Si < c, there exists a feasible tour only for the subpath s — Vi. When 5, > c, there is no feasible tour just for the subpath s — Vi. Indeed, any feasible tour for L, including an optimal tour, traverses an edge e; with Si > c strictly more than once. It will traverse it for the first time to unload some items at demand vertices on the subpath Vi+\ —t, and then it traverses it back on the way to load excess supply left behind on the subpath s — Vi. Lemma 4.3 implies that an optimal tour traverses an edge ej with St > c exactly three times. The tour T generated by the algorithm is obviously feasible. Moreover, it is optimal since it traverses every edge ei with Si > c exactly three times, and every other edge exactly once. Thus, the length, w(T), of an optimal tour, T, generated by the algorithm is given by w(T) = £ ( / ( e t ) : 5, < c) + 3 £({(e0 : $ > c). • Finally, we note that if we relax Assumption 4.2, other optimal tours can be generated. Indeed: CHAPTER 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 104 Observation 4.4 Different loading and unloading policies at supply and demand ver-tices could lead to different optimal tours, whose lengths, of course, are all equal. In-deed, the reader can verify that the following modification of the algorithm would also yield an optimal tour for a VRPD problem on a path. The vehicle proceeds from s towards t. Upon encountering a vertex v then: • If r(v) < 0 and no supply was left behind, a delivery at v must be made. • If r(v) < 0 and some supply was left behind, the delivery at v is optimal. How-ever, if delivery is not done, then the net supply left behind is decreased by \r{v)\. • If r(v) > 0 and there is not enough capacity on the vehicle, the supply at v is left behind. • If r(v) > 0 and there is enough capacity on the vehicle, loading the supply at v is optional. However, if supply is not loaded, then net supply left behind is adjusted. • Immediately when the vehicle reaches a vertex u at which it has enough capacity to pick up all net supply left behind, it returns to the supply vertex, w, closest to s at which supply was left behind. On its way from u to w, deliveries, if any, are made, and on the way back from w to u, all supply is picked up. 4.4 T h e V R P D problem on a tree graph In this section we study the V R P D problem on a tree graph. We start with the case where s = t. Then, we discuss the case where s and t are predetermined but not necessarily coincide, and finally we consider the case where either 5 or t or both are endogenously determined. CHAPTER 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 105 4.4.1 The case where s — t Any feasible tour for the V R P D problem on a tree that starts and ends at the same vertex and visits all the vertices therein, traverses each edge at least twice. A linear time algorithm which produces a feasible tour that traverses every edge exactly twice, i.e. an optimal tour, was first developed by Anily and Mosheiov (1994) and later by Chalasani et al. (1996), who used it to obtain a 2-approximation algorithm for the V R P D problem on a general graph. For completeness, we describe below this algorithm. Proofs of correctness can be found in Anily and Mosheiov (1994) and Chalasani et al. (1996). Since the length of an optimal tour on a tree is independent of the choice of s, the vertex s can be chosen arbitrarily. Once chosen, we regard the tree as rooted away from s. For each i , i / s, we denote by f(x) the father of x in the tree and refer to s as a son of f(x). A n a l g o r i t h m for s = t Step 1 For each vertex Vi compute the sum, Ri, of the r / s in the subtree rooted at Vi. Step 2 Let x be the current vertex and xx,... ,xk be its sons. Assume, without loss of generality, that Rx < • • • < Rk. Starting with x = s traverse the tree as follows: • Go to the minimal indexed unvisited son of x, if one exists; else go back to f(x). • If x = s and all sons of s were already visited, STOP. • While traversing the tree, a delivery to any demand vertex x is made when the vehicle first visits x. A pickup from any supply vertex x is made when the vehicle last visits x, that is, when it leaves x to its father f(x). CHAPTER 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 1 0 6 4.4.2 The tree case where s and t are predetermined Let s and t be two distinct arbitrary vertices in the tree, let P denote the unique path between s and £ in the tree, and let {xx = s, x2, • • •, xk = t} and E(P) denote the vertex set and the edge set of the path P, respectively. Denote by G\,... ,Gk the collection of subtrees obtained upon deletion of E(P) from the tree, where it is assumed that Xi 6 G{. A linear time algorithm for our vehicle routing problem on a tree is presented below. A n algorithm for s ^ i Step 1 For each vertex xz G P compute r'(xi) - the sum of the r^'s in G 2 . This defines a request function r' on the vertices of P. Step 2 Using the algorithm for the V R P D problem on a path, find an optimal tour V for V R P D (P, r', N, s, t). Denote its length by iw(T'). An optimal tour T for the tree is obtained from T' as follows. T coincides with T" on P . When T" performs a request by a vertex X{ G P , T follows an optimal tour in the subtree G% that starts and ends at (Observe that when T" calls for the vehicle to perform a request by xx G P , the vehicle must have enough capacity to fulfill all the requests generated by vertices in 6?,.) The length of the optimal tour, w(T), generated by the algorithm is given by w(T) := w(T') + 2Y,ejeE\E{P)l(ej). Correctness of the algorithm Obviously, the tour introduced by the algorithm is feasible. Any feasible tour for the tree traverses every edge in the subtrees (i.e. in E \E(P)) at least twice, and it induces a tour for V R P D (P, r', JV, s, t) whose length is at least the length of an optimal tour for V R P D (P, r', A ,^ s, t). Since the tour T generated by the algorithm traverses CHAPTER 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 107 every edge in the subtrees exactly twice and the induced tour for V R P D (P, r', N, s, t) is optimal 1 we conclude that T is optimal. • For simplicity, assume that the requirements at the leaves of the tree are not zero. In view of Lemma 4.3 and the above discussion of the correctness of the algorithm, we have: Corollary 4.5 Let T be an optimal tour in a tree graph with predetermined s and t. Then, every edge on the path between s and t is traversed either once or three times by T, and all other edges are traversed precisely twice. 4.4.3 The case where t is endogenously determined In order to find a vertex t for which the length of an optimal tour from a predetermined vertex s to t is minimal, one can apply, for all possible locations of t, the algorithm developed in Subsection 4.4.2 for predetermined s and t. This will result with a quadratic time algorithm. In this subsection we develop a linear time algorithm for the case where s is predetermined and t is endogenously determined. Since s is predetermined, we root the tree in s, direct the edges from a father to its sons, and denote ej = {f(vi),Vi), where f(vi) is the father of Vi in the tree. A n algorithm when t is endogenously determined Step 1 For each vertex v{ compute the sum, R\, of the r / s in the subtree rooted in Vi. Denote by R\ the sum of the r / s in the rest of the tree. Thus, R\ := Rs — R%-Step 2 For each edge ej define //(ej) as follows: /(ej), if Ri > c J'(ei) := —/(ej), otherwise. Observe that if r'(zj) > 0 and r(x{) < 0, the optimal tour does not perform a delivery upon its first visit to the demand vertex i;. The optimality of the tour follows from Observation 4.4. CHAPTER 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 108 Step 3 For each Vi compute w(vi), w(vi) = E(/ ' ( e i ) : ei 1S o n t n e s — Vi path). w(s) := 0. Step 4 w(vio) :- m'mi=it...t\v\{w(vi)}. Step 5 Find an optimal tour, T, for the tree from s to t := vio using the algorithm developed in Subsection 4.4.2. Then, T is optimal for a tree graph with t endogenously determined and vj{T):=w{vio) + 2Y,ejzEl{ej)-Implementation and correctness of the algorithm Step 1 can be easily implemented in linear time by performing one pass on the tree from the leaves towards the root s. Ri := r; + E* = 1 i?j j . where vix,..., vik are the sons of vt. If Vi is a leaf, then Ri := To implement Step 3 in linear time we perform a Breadth First Search starting from s. We set w(s) to be zero, and for Vi ^ s we set w(vi) := w(f(vi)) + w(ei). Next, let us prove the correctness of the algorithm. Consider an arbitrary edge ej, and assume that it is contained in the subpath Pj = s — i>j. Denote by E(Pi) the edge set of Pj. Then, by Corollary 4.5, ej is traversed by an optimal tour from s to Vi either once or three times. Consider the algorithm for predetermined s and t, developed in Subsection 4.4.2. It calls the algorithm on a path which computes the partial sum of the r/s along the line. Note that the partial sum of the r/s along the •5 _ fivj) path, used by the algorithm on a path, is equal to Rj computed in Step 1 above. Thus, if Rj < c, ej is traversed once. Otherwise, Rj > c and ej is traversed three times. Thus, the length of an optimal tour, TVi, that starts at s and ends at Vi is: w{TVi) = 2T,ejeE\E(pi)l(ej) + 3E e j. e£(p.)A(fl. > c)Z(ej) + ^ejeE{pi)A(Rj<c)Kej) = 2E e j. e £;/(ej) + %ejeE(Pi)A(Rj>c)Kej) ~ ^Jej&E{Pi)A(Rj<c)Kej) = 2J:e.eEl(ej) + w(vi). The algorithm chooses t to be a vertex vio, for which w(vio) = mmi=it_t\v\{vj(vi)}. • CHAPTER 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 109 4 . 4 . 4 The tree case with s and t endogenously determined In order to find a pair of vertices s and t, for which the length of an optimal tour from s to t is shorter than the length of an optimal tour from any vertex to any other vertex on the tree, one can apply, for all possible locations for s, the algorithm for a fixed s given in Subsection 4.4.3. This will result with a quadratic time algorithm. We develop below a linear time algorithm for the V R P D problem on a tree graph G for the case where both s and t are not predetermined. First, we need to introduce the following notation. For an arbitrary edge e = (u[,u2) in G, we denote by H(ux) and i f (1*2) the two components of the tree containing ux and u2, respectively, which are obtained after the removal of e. Denote by R(H(ui)) and R(H(u2)) the total requirement of vertices contained in component H(u\) and H(u2), respectively. An algorithm when s and t are endogenously determined Step 1 Replace each edge, e = (ux,u2) 6 G, in the tree graph G by two anti-parallel directed arcs ax = (ux,u2) and a2 = (u2,ux), and denote by G the directed graph derived from G. Step 2 For each directed arc a = (ux, u2) in G derived from edge e = (ux, u2) in G let l (a) = t ((uuu2)) = < —/(e), otherwise. Step 3 Choose an arbitrary vertex, v0, as the root of the directed graph G. A sub-graph of G rooted at some vertex v is the directed graph that is associated with the subtree of the tree G rooted at v, when G is also viewed as rooted at v0. Now, in G, rooted at v0, find the length of a shortest path, P, and its end vertices sp and tp as follows: (i) For every leaf vertex q, except the root, set l(F(q)) := 0 and l(T(q)) := 0. CHAPTER 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 110 (ii) Recursively, compute l(F(vi)) - the length of a shortest path from to a vertex contained in the subgraph rooted in v^, l(F(vi)):= min { / ( F ( ^ ) + £ > 2 , ^ ) } , . and l(T(vi)) - the length of a shortest path from a vertex contained in the subgraph rooted in i>j to l(T(vi)) := min { / (T(^ . ) )+f (^ . , ^ )} , where , • • •, vik are the sons of V{. (iii) Compute l(P(vi)) - the length of a shortest path which traverses vx and is contained in the subgraph rooted at vf / x x ( /(F(ui)) + /(T(^)), if ^ ( ^ ) ) < 0 and /(Tfa)) < 0 l{P(vi)) := < I mm{l(F(vi)),l(T(yi))}, otherwise. (iv) l(P) := mmi=it„.t\v\{l{P(vi))}. Set sp and ip to be the start and end vertices of the directed path P. An optimal tour for the tree from Sp to tp, generated by the algorithm developed in Subsection 4.4.2, is an optimal tour for a tree when both s and t are endogenously determined. Implementation and correctness of the algorithm Step 3 (ii) is implemented in linear time, by performing one pass on G from the leaves backwards to the root v0. By Subsection 4.4.2, Step 3 (iv) is also carried out in linear time. Thus, the above algorithm is linear. The arc weights introduced in Step 2 and the fact that we have to find a shortest directed path in G are justified by a proof similar to the correctness proof given in Subsection 4.4.3. The choice of the root, v0, for G in Step 3 is arbitrary, and is done just to enable us to carry out the computation in linear time. In Step 3 (ii) we find recursively, for each vertex v, the length of a shortest directed path which traverses v and is contained in the subgraph of G rooted at v. The correctness proof follows since the shortest path we seek traverses some vertex v of G and is contained in the subgraph of G rooted therein. • CHAPTER 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 111 4.5 T h e V R P D problem on a cycle graph In this section we consider the V R P D problem on a cycle graph C, denoted V R P D {C,r,N). In Subsection 4.5.1, we develop algorithms for the V R P D (C,r,N) problem in the case where both the starting vertex s and the terminal vertex t of the tour are endogenously determined by the algorithm, for both cases s = t and s ^ t. In Subsections 4.5.2 and 4.5.3, we develop algorithms which find an optimal tour for the case where the locations of both s and t are predetermined, V R P D (C, r, N, s, t). We start with some notation and lemmas. Throughout this section we assume that the vertices of the cycle graph C, vi,..., v\v\, are ordered clockwise, et = (vi,vi+i) G E, 1 < i < | V | , and e\v\ — {v\v\,V\). We denote the length of the cycle by 1(C) = T}^[l(ei) and the length of a feasible tour, T, by.iu(T), which is the sum of lengths of all the edges traversed by T. We assume, without loss of generality, that there exists at least one supply vertex in C, otherwise the problem reduces to the traveling salesman prob-lem on a cycle graph, which is trivial. We assume, without loss of generality, that r(vi) 7^ 0, 1 < i < \V\. Otherwise, we can delete any vertex vx for which r(vi) = 0 along with its two incident edges, and connect its two adjacent vertices V i - \ and vi+i by a new edge whose length equals the sum of the lengths of the two edges deleted. Since any feasible tour in C must visit all the vertices we have: Observation 4.6 At most one edge in C is not traversed by a feasible tour for a VRPD (C, r , N) problem. Let {Si} denote the sequence of partial sums of the sequence {r(vj) : 1 < j < \V\}. Thus, S{ = Yl)=i r(vj)- Let -0 be a vertex for which max i = i v . . i |y |{5i} is attained. Then, it is easy to see that the following result holds. Lemma 4.7 A feasible tour for a VRPD (C, r , N) problem, which starts and ends at v traverses all the edges in C exactly once. CHAPTER 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 112 A proof of Lemma 4.7, not using the sequence of partial sums, was given by Mosheiov (1994). 4.5.1 The V R P D (C, r, N) problem with s and t endogenously determined A n algorithm for a cycle graph with s and t endogenously determined Step 1 For every edge E C, for which either there exists a feasible tour that starts at Vi+\ and goes clockwise to Vi, or starts at Vi and goes counterclockwise to vi+i traversing every edge exactly once, let w{Tei) := 1(C) — /(e,). Let w(Tk0) :~ min{w(Tei)}. i Step 2 For the rest of the edges e3 in C compute w(Tej), the length of an optimal tour, T e . , that does not traverse ej. Observe that the removal of an edge ej induces a V R P D problem on the path C\ej, in which s and t are endogenously determined. Thus, Te. and w(Tej) can be generated by the algorithm developed in Subsection 4.4.4. Let w(Tin) := min {w(Te.)\. The length of the optimal tour, w(T), generated by the algorithm is given by w(T) := mm{w{Tjo),w{Tko)}. That is, if w(Tj0) < w(Tk0) then an optimal tour is T := T}0, else T := Tko. Implementation and correctness of the algorithm Step 1 can be implemented in linear time, but Step 2 involves 0 ( |V | ) calls (in the worst case) of the linear time algorithm developed in Subsection 4.4.4. Thus, the time complexity of the above algorithm is 0 ( | V | 2 ) . CHAPTER 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 113 Steps 1 and 2 check all the feasible tours that traverse all edges in C except one. Indeed, in Step 2 the algorithm generates for each j, an optimal tour for a V R P D problem on a path C \ej, where s ^ t are endogenously determined. On the other hand, Lemma 4.7 guarantees the existence of a feasible tour that traverses every edge in C exactly once for some s = t = Vj. Thus, there are feasible tours that traverse all the edges except one, exactly once. Any such tour starts at a vertex Vi for which max Si is attained (see Lemma 4.7), and ends at if the corresponding tour travels clockwise, or at vl+\ if the tour travels counterclockwise. Such tours are examined by the algorithm in Step 1. Note that one could have applied Step 2 to all the edges of C. However, it is more efficient to find optimal tours which do not traverse edges satisfying the condition in Step 1. Indeed, such tours can be found in constant time, instead of linear time per edge if Step 2 is applied. • Observation 4.6 and Lemma 4.7 suggest the following linear time algorithm for a V R P D (C,r,N) problem with s = t endogenously determined. A n algorithm for a cycle graph with s = t Step 1 For every edge e3 <E C let w(Tej) := 2(l(C) - l{e3)). Observe that w(Tej) is the length of a shortest tour for the V R P D problem defined on the path derived from C after the elimination of e,-, with s = t = Vj. Let w(Tjo) := j=™™ {w{Tej)}-Step 2 Find an index ko, such that a feasible tour that starts and ends in vko and travels clockwise, traverses every edge exactly once, with s = t = vko. Denote this tour by Tko, w(Tka) = l(C). Let w{T) = min{w{Tjo),w(Tko)}. If w(Tj0) < iu(Tko), then an optimal tour T starts at V j 0 + \ , travels to Vj0 clockwise performing all delivery requests and then returns counterclockwise from Vj0 to V j 0 + i CHAPTER 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 114 performing all pickup requests. Else, T := Tko is an optimal tour. Implementation and correctness of the algorithm Clearly, the above algorithm can be carried out in linear time. To verify its cor-rectness, observe that by Observation 4.6, at most one edge in C is not traversed by a feasible tour on C. The removal of an edge ej from C induces a V R P D problem on a path C \ej, in which s = t are endogenously determined. As observed in Subsec-tion 4.4.1, the length of an optimal tour on a tree with s = t is independent of the choice of s, and is always equal to twice the length of the tree. Thus, for a V R P D problem on C \ ej, we can choose s — t to coincide with Vj+i-It remains to check all the feasible tours that traverse all edges in C at least once. Lemma 4.7 guarantees the existence of a feasible tour that traverses every edge in C exactly once, and all such tours, whose length is 1(C), are found in Step 2 of the algorithm. • 4.5.2 The V R P D problem on a cycle graph when s and t are predetermined and s ^ t Before analyzing the case where s and t are predetermined, we construct below a parametric algorithm for the V R P D problem on a path, which computes the length of optimal tours for all nonnegative initial capacities c in 0 ( | V | log |V|) time. This parametric algorithm is used in our 0 ( | V | 2 log | V|) algorithm for the V R P D problem on a cycle when s and t, s ^ t, are predetermined, which is described below. We note that under some conditions (see Observations 4.8 and 4.12 bellow) our parametric algorithm has linear complexity, in which case our algorithm for the cycle can be executed in 0 ( | V | 2 ) time. CHAPTER 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 115 An algorithm for a path with s ^ i and parametric initial capacity Step 1 Calculate the partial sum Sj for each vertex Vj of the path, and sort these sums, to obtain the subsequence, S[, S'2, • • •, S'k, of all distinct values of the 5/s arranged in an ascending order. For each S[, let E(Sl) = {ej = [vj,v3+l) : Sj = Sj}. Step 2 • If the initial available capacity of the vehicle c < St, where St is the partial sum at t, the tour is infeasible. • If the initial available capacity of the vehicle c > S'k , an optimal tour Tk will traverse the whole path exactly once, and have the length w(Tk) = d(s,t), where d(s,t) is the length of the path from s to t. • For i = k — 1,..., 1 and an initial available capacity of the vehicle c e [SI, S'i+l), an optimal tour Tt traverses three times all segments tra-versed three times by Ti+i and all edges in E(S[). The length of the tour is w(Ti) = w(Ti+1) + 2 J2 Since the partial sums and the sets E(S[) can be found in linear time, the com-plexity of the algorithm is the complexity of sorting the partial sums, which can be done in 0 ( | V | l o g | V | ) time. Observation 4.8 We have assumed above that the sorting algorithm has complexity 0(\V\log | V | ) . However, we note here that some sorting algorithms can be executed in linear time under some additional assumptions about the input. For instance, if we can assume that the sequence of partial sums, S[, S'2, • • •, S'k, is drawn from a uniform distribution over some finite interval, then the bucket sort algorithm runs in linear time, and the complexity of our algorithm for a path with s ^ t and parametric initial capacity is 0(\V\). Bucket sort may run in linear time even if the input is not drawn from a uniform distribution, as long as the sum of the squares of the bucket sizes is linear in the total number of elements. CHAPTER 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 116 Lemma 4.9 For a path L, denote by L' the graph in which the supplies r(vij,..., r(vlk) at the first k supply vertices in the direction s — t are replaced with 0. An optimal tour T' on the path L' with an initial vehicle capacity c coincides with an optimal tour T on the path L with an initial vehicle capacity c + £ j = i r(vij)-For a cycle C with predetermined s ^ t, let A and B denote the two s — t paths contained in the cycle. Proposition 4.10 Each feasible tour, T, on a cycle that visits all vertices has to have one of the following forms: Form (i): One edge in one of the s — t paths is not traversed at all by T and all other edges in that s — t path are traversed at least twice, Form (ii): Every edge in C is traversed at least once, and every edge in one of the s — t paths is traversed at least twice. Since every tour must have one of the forms mentioned above, so does an optimal tour. If an optimal tour traverses all edges at least once, it can be done in four ways, as we show below. Denote by A the s — t path in which every edge is traversed by an optimal tour at least twice. Let T be a feasible tour and let Q be a subpath of T from v\ to v2. If Q is contained in A (resp., B) and V\,v2 £ {s,t}, then Q will be referred to as a visit by T in A (resp., B), and if vx ^ v2, then Q will be referred to as a complete visit by T in A (resp., B). Theorem 4.11 The subpath A can be traversed by an optimal tour, T, in four pos-sible forms: Form (1): There are precisely two complete visits in A, both of which start at s. Form (2): There are two complete visits in A. The first complete visit starts at s, the second complete visit starts at t, and there may be some other incomplete visits m A after the complete visits therein. CHAPTER 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 117 Form (3): There are two complete visits in A. The first complete visit starts at t, the second complete visit starts at s, and there may be another incomplete visit in A which precedes the two complete visits therein. Form (4): There is one visit in A, which enters at s and leaves at s, and there is another visit in A which enters at t and leaves at t. To find an optimal tour, we must check all possible tours that have the Form (i) in Proposition 4.10, or Forms (1), (2), (3) and (4) in Theorem 4.11, excluding the cases that were shown to be non-optimal in the proof of Theorem 4.11. A n algorithm for a cycle graph with s ^ t Step 1 (In this step we calculate, in 0 ( | V | 2 ) time, the length of a shortest tour which is of the Form (i) in Proposition 4.10.) • For every edge (v, w) in C, use the algorithm for a tree to find an optimal tour T]w on the v — w path derived from C by eliminating (v,w). • Let w(Ti) := mm{w(T„w) : (v,w) in C and v,w g {s,t}}. Step 2 (In this step we calculate, in 0( | V | 2 log \V\) time, the length of a shortest tour which is of the Form (1) in Theorem 4.11. The general description of this tour is presented in Figure 4.1). Figure 4.1: Form (1) CHAPTER 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 118 • For every demand vertex v ^ t denote by B (resp., A) the s — t path that contains2(resp., does not contain) v. Let Sv denote the absolute value of the total demand in all demand vertices contained in A and in the subpath of B between s and v. Let U\,U2, • • • ,uk denote the supply vertices in B, arranged in an increasing distance from t, u\ ^ t, and let SVuj = SVUj_l +r(uj),j = 1,..., k, SVUQ = Sv. Consider the V R P D problem defined on a path L which coincides with B, but in which the demand in all demand vertices contained in the s — v subpath of B were set to zero, and L is traversed in the direction from t to s. (a) Use the parametric algorithm for the V R P D problem on a path, with parametric available capacity a, to determine the length of a shortest tour, T2a, on L, for a = c + SVUo,c + S V U 1 , c + SVUk, where c is the initial available capacity when the vehicle starts at s. (b) Let T 2 = a rgmin{w(T 2 c + 5 w u . ) + 2d{uj,t) : j = 0,...,k}, where d(uj, t) is the distance between Uj and t on B and d(u0, t) = 0. (c) Let w(T2) := m i n ^ T 2 ) + 2d(s,v) + 21(A)], where d(s,v) is the distance between s and v on B. Step 3 (In this step we calculate, in 0 ( | U | 2 log |V|) time, the length of a shortest tour which is of the Form (2) in Theorem 4.11. The general description of this tour is presented in Figure 4.2). • For every demand vertex v ^ s, denote by B (resp., .4.) the s — t path that contains3 (resp., does not contain) v. Let Sv denote the absolute value of the total demand in all demand vertices contained in A and in 2 For v = s, this part of the algorithm is performed twice. Once when the tour T is as shown in Figure 4.1, in which the initial incomplete visit in B is eliminated. The other case is obtained when the roles of A and B are reversed. 3 For v = t, this part of the algorithm is performed twice. Once when the tour T is as shown in Figure 4.2, in which the first incomplete visit in B, starting and ending at t, is eliminated. The other case is obtained when the roles of A and B are reversed. CHAPTER 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 119 the subpath of B between v and t. Let u\, u2,.. •, uk denote the supply-vertices in A, arranged in an increasing distance from t, u\ ^ t, and let SVUj = SVUj_l +r(uj),j = 1,..., k, Svuo = Sv. Consider the V R P D problem defined on a path L , which coincides with the circle disconnected at t. Thus, one end point of L is t, the other is t', and the (t — t') path consists of subpath A concatenated with subpath B. However, the demand in all demand vertices contained in A and in the t — v subpath of B are set to zero, while the demand/supply of all other vertices in L remains equal to their values in C. (a) Use the parametric algorithm for the V R P D problem on a path, with parametric available capacity a, to determine the length of a shortest tour, T 3 a , on L , for a = c + 5^„0, c + SVUi,..., c + SVUk, where c is the initial available capacity when the vehicle starts at s. (b) Let T„3 = a r g m i n { u ; ( r 3 c + ^ u . ) + 2d(Uj,t) : j = 0,...,k}, where d(uj, t) is the distance between Uj and t on A and d(u0, t) = 0. (c) Let w(T3) := mmv[w(Tlz) + 2d(v, t) + l(A)], where d(v,t) is the distance between v and t on B. Step 4 (In this step we calculate, in 0 ( | F | 2 log\V\) time, the length of a shortest tour which is of the Form (3) in Theorem 4.11. The general description of this tour is presented in Figure 4.3). Figure 4.2: Form (2) CHAPTER 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 120 • For every demand vertex v ^ t, denote by A (resp., B) the s — t path that contains4 (resp., does not contain) v. Let Sv denote the absolute value of the total demand in all demand vertices contained in the subpath of A between s and v. Let ux, ux,..., uk denote the supply vertices in B, arranged in We observe that for some pairs (v,Uj), there is no feasible solution for a V R P D problem on B, from s to t, with initial capacity a = c + SVUj, in which the demand at all demand vertices in the subpath (s,Uj) of B was set to zero. That is, the net supply in the subpath (uj,t) of B, excluding the supply at Uj, exceeds a. In these cases, there exists a supply vertex ru on B such that according to an optimal tour, displayed in Figure 4.3, the vehicle will not pick up the supply from all supply vertices on the subpath (w, t) during this part of the tour. Rather, the vehicle will leave this supply behind, will enter A at t for a complete visit therein and will follow the route shown in Figure 4.3. Upon the return of the vehicle to t, it will enter B at t for an incomplete visit in order to pickup up the supply left behind in the subpath (w,t). Therefore, in (a) below, when we 4 For v = s, this part of the algorithm is performed two times. Once when the tour T is as shown in Figure 4.3, in which the initial incomplete visit in A is eliminated. The other case is obtained when the roles of .4 and B are reversed. Figure 4.3: Form (3) an increasing distance from s, U\ ^ s, and let SVUj = 5, j 1 , . . . , /C , SVUQ Sy • + r(uj), CHAPTER 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 121 apply the parametric algorithm for the V R P D problem defined on B, we increase the demand at t to a large enough value M, say M is equal to the total supply on B. The justification for such a modification follows from the algorithm on the tree for s ^ t. (a) Use the parametric algorithm for the V R P D problem on a path, with parametric available capacity a, to determine the length of a short-est tour, T 4 Q , on B, for a = c + SVUo,c + SVUl,..., c + SVUk, where c is the initial available capacity when the vehicle starts at s, and r(t) = -(T,r(vj) :VjeB and r(vj) > 0). (b) Let T 4 = a r g m i n { ^ T 4 c + S i i u . ) + 2d(s,Uj) : j = 0,. . . , k} , where d(s,Uj) is the distance between s and Uj on B and d(s,uo) = 0. (c) Let w(T 4 ) := m i n ^ T 4 ) + 2d(s,w) + 21(A)], where d(s,u) is the Step 5 (In this step we calculate, in 0 ( | U | 2 log \V\) time, the length of a shortest tour which is of the Form (4) in Theorem 4.11. The general description of this tour is presented in Figure 4.4). • For every demand vertex v £ {s, t} for which there exists at least one supply vertex between 5 and v, denote by A (resp., B) the s — t path that contains (resp., does not contain) v. Let Sv denote the absolute value of the total demands minus total supplies in all vertices contained distance between s and v on A. Figure 4.4: Form (4) CHAPTER 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 122 in the subpath of A between s and v. Let ux, u2, • • •, uk denote the supply vertices in the subpath of A between s and v, arranged in an increasing distance from v, and let Svu. = SVUj_l + r(u3),j = 1,..., k, Svuo = Sv. Let i = min{j = 1,..., k : SVUj > 0}. Similar to the observation made in Step 4, for some pairs (v,Uj), there is no feasible solution for a V R P D problem on B, from s to t, with initial capacity a = c + SVUj, in which the demand at all demand vertices in the subpath (s, Uj) of B was set to zero. That is, the net supply in the subpath (uj,t) of B, excluding the supply at u3, exceeds a. In these cases, there exists a supply vertex w on B such that according to an optimal tour, displayed in Figure 4.4, the vehicle will not pick up the supply from all supply vertices on the subpath (w,t) during this part of the tour. Rather, the vehicle will leave this supply behind, will enter A&tt for an incomplete visit therein and will follow the route shown in Figure 4.4. Upon the return of the vehicle to t, it will enter B at t for an incomplete visit in order to pickup up the supply left behind in the subpath (w,t). Therefore, in (a) below, when we apply the parametric algorithm for the V R P D problem defined on B, we increase the demand at t to a large enough value M, say M is equal to the total supply on B. The justification for such a modification follows from the algorithm on the tree for s ^ t. (a) Use the parametric algorithm for the V R P D problem on a path, with parametric available capacity a, to determine the length of a shortest tour, T 5 Q , on B, for a = c + SVUi,c + SVUt+i,..., c + SVUk, where c is the initial available capacity when the vehicle starts at s, and r{t) = -{J2r{vj :VJ e B and r(v3) > 0). (b) Let T;5 = argmin{u; ( r 5 c + S i ) )+2d(uj, v) : j = i , k } , where d(u3, v) is the distance between u3 and n on A (c) Let w(T5) := min„[ty(Tw5) + 21{A)]. CHAPTER 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 123 The optimal tour, T, generated by the above algorithm is T = argmin{^(T'),z = 1,2,3,4,5}. i Implementation and correctness of the algorithm Each step involves 0 ( |V | ) calls to an algorithm of complexity | V | l o g | V | , so the total time complexity of the above algorithm is 0 ( | V | 2 log |V | ) . For a possible im-provement of the complexity see Observation 4.12 bellow. The correctness of the algorithm follows from the proofs of Proposition 4.10 and Theorem 4.11. Indeed, an optimal tour is either of the form (i) in Proposition 4.10 or its structure coincides with one of the tours displayed in Figures 4.1 - 4.4, as proven in Theorem 4.11. Step 1 checks all optimal tours that satisfy (i) in Proposition 4.10. The algorithm for the tree with endpoints vuvi+i finds an optimal tour that starts at s, ends at t, and does not traverse e — (vi,Vi+i). Step 2 checks all the optimal tours of the Form (1) in Theorem 4.11 as displayed in Figure 4.1. The tour goes along B from s to v doing only deliveries, which will increase the available capacity of the vehicle. Since the s — v subpath of B will be traversed again, all pickups in that subpath will be done in the last visit therein. Thus, the tour returns from v idly to s along B. Since each edge in A is traversed twice, all the pickups in A will be done in the next visit in A, and in the first complete visit in A only deliveries are performed. Then, the tour goes from i to s along B using the parametric path algorithm. If an optimal tour is obtained for some capacity c + Svu, it follows from Lemma 4.9 that the same tour can be used for a problem where the pickups on B between t and u are not performed during this visit. The tour continues from s to t along A doing only pickups. If u ^ t, the tour continues along B idly to u, and returns back to t doing pickups. Step 3 checks all the optimal tours of the Form (2) in Theorem 4.11, as displayed in Figure 4.2. The tour goes along A from s to t doing only deliveries. Since A will be traversed again, all pickups will be done in the last visit therein. Then, the tour goes CHAPTER 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 124 along B from / to r doing only deliveries, which will increase1 the available capacity of the vehicle1. Since this subpath will lie traverse'el again, all pickups thenun will be1 elone in the last visit. The tour returns from v ielly to t along B. It then goes along .1 from t to .s, continuing alemg B from ,s to /, using the1 parametric path algorithm. If an optimal tour is obtained for some capacity c + S„u, it follows from Lemma 4.9 that the same tour can be used for a problem where the pickups on A between t and v are1 not performed during this visit. If u f t, the tour continues along .4 ielly to v, and returns back to t elenng pie'kups. Step 4 eheuks all the optimal tours of the Form (3) in Theorem 4.11, as displayed in Figure1 4.3. The1 tour goes along .4 from « to v doing only deliveries, and returns ielly t.e) ,s. Since this subpath will be1 traverse'el again, all pickups will be elone in the last visit therein. The parametric path algorithm is used for traversing B from ,s to t, anel therefremi the temr goe\s along .4 from t te> ,s elenng eleliveules. If the optimal te)ur obtained! by the parametric algorithm on B is attained for an initial capacity r + S„„. it follows from Lemma 4.9 that, the same tour can be used for a problem where1 the pickups on B between .s anel v. are1 neit performed during the1 complete visit in B. Thus, if a ^ the1 tour continues from .s along B idly to u, and returns back to ,s doing pickups. Then if returns along A to / doing picku])s, anel continues along B ielly to w and back to t if any pickups were left from by the parametric algorithm on B. Step 5 checks all the optimal tours of the Form (4) in Theorem 4.11, as displayed in Figure 4.4. The1 tour goes from ,s to v along A doing only deliveries. The tour returns from r to s along .4 performing pickups. The1 parametric path algorithm is use>d for traversing B from .s to /. and therefrom the tour then goes idly along A from / to //. doing deliveries, anel returns back to / doing pickups. If an optimal tour is obtained by the parametric algorithm for some1 capacity c + Sva, it follows from Lemma 4.9 that the same1 tour can be' used for a problemi where1 the1 pickups on .4 between r anel u are not performed during the1 first visit in .4. It, follows from Lemma 4.9 that only eases when r + S„u is non negative1 have to be considered. If there were any pickups 1(41 from the path algorithm on B, the tour continues along B idly to w and back to CHAPTER 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 125 t performing the remaining pickups. Now, as previously noted, every tour that visits all vertices must do it in one of the ways described in Proposition 4.10. Further, an optimal tour of the Form (ii) in Proposition 4.10, has one of the four structures described in Theorem 4.11. Therefore, the shortest of the five tours given above is an optimal tour for the cycle. • Observation 4.12 We have noted in Observation 4-8 that the sorting algorithm can be executed in linear time, under some additional assumptions (e.g., uniform distri-bution of the partial sums). When this is the case, each step of our algorithm for a cycle graph with s ^ t involves 0(\V\) calls to an algorithm of complexity \V\, so the total time complexity of the above algorithm is 0(\V\2). Example : Consider the V R P D problem on a cycle graph shown in Figure 4.5. v5 Figure 4.5: Example The demands in the vertices are given by Table 4.1. V2 ^3 v4 v5 v6 v7 ^8 r{vi) 2 -2 3 -4 -1 1 -3 4 Table 4.1: Demands in the vertices CHAPTER 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 126 e (vuv2) (v2,v3) (v3,v4) (v4,v5) (v5,v6) (v6,v7) (v7,V8) 1(e) 3 2 4 3 4 3 3 4 Table 4.2: Lengths of the arcs The lengths of the arcs are given by Table 4.2. Now, applying the algorithm described above will result with the following. Step 1 The first column in Table 4.3 represents the edge of the cycle that is not traversed, the second is the corresponding shortest tour, and the third is the length of the tour. The minimum tour length is w(T\) = 46. e T 1{T) (Vi,V2) ViV8V7V6V5V4V3V2V3V4V5V6V7V8ViVsV7V6V5 60 (v2,V3) ViV2ViVsV7V6V5V4V3V4V5V6V7VsV7VGV5 54 (v3,v4) v i v 8 v 7 v 6 v 5 v 4 v 5 v e v 7 v 8 v i v 2 v 3 v 2 v i v 8 v 7 v 6 v 5 58 (v4,v5) v i v 2 v 3 v 4 v 3 v 2 v i v 8 v 7 v 8 v 7 v 6 v 5 v 6 v 5 46 (v5,Va) ViV2V3V4V5V4V3V2ViV8V7VGV7V8ViV2V3V4V5 56 (v6,v7) v i v 2 v 3 v 4 v 3 v 2 v i v 8 v 7 v 8 v i v 2 v 3 v 4 v 5 v 6 v 5 52 (V7,V8) ViV2V3V4V5V6V7V6V5V4V3V2ViV8ViV2V3V4V5 58 (v8,vi) viv2VxV2v3v4v3v4v5vev7v8v7vGv5 46 Table 4.3: Step 1, w(Ti) = 46 Step 2 The first column in Table 4.4 represents the demand vertex where the first visit in B ends (see Figure 4.1), the second is the corresponding shortest tour, and the third is the length of the tour. The minimum tour length is w(T2) = 46. Step 3 The first column in Table 4.5 represents the demand vertex where the first visit in B ends (see Figure 4.2), the second is the corresponding shortest tour, CHAPTER 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 127 v T l(T) v2 ViV2VyVsv7vev5V4V3v2v1vsv7vev5 46 V4 ViV2V3V4V3V2ViV8V7VeV5V4V3V2V1V8V7VeV5 58 v7 viv8v7vsViV2v3v4v5VQV7v8viv2v3v4v5 52 Table 4.4: Step 2, w(T2) = 46 and the third is the length of the tour. The minimum tour length is w(T3) = 44. V T l(T) V2 VIV%V7V%V5V4V3V2V3V4VZ,VQV7V%VIV2V3V4VC> 58 V4 VIV8V7V6V5V4V5V6V7V8V1V2V3V4V5 46 v5 viv8v7v6v5vfiv7v8viv2v3v4v5vev7vsv7vfiv5 60 VXV2V3V4V5V4V3V2VXV8V7V8V7Vsv5 44 v7 ViV2V3V4V5V6V7V6V5V4V3V2ViV8V7VeV5 52 Table 4.5: Step 3, w(T3) = 44 Step 4 The first column in Table 4.6 represents the demand vertex where the first visit in A ends (see Figure 4.3), the second is the corresponding shortest tour, and the third is the length of the tour. The minimum tour length is w(T4) = 50. v T l(T) V2 ViV2ViV8V7V8V7V(iV5V4V3V2ViV2V3V4V5 50 v4 v ^ v ^ ^ ^ v i v ^ v e v s v ^ ^ v ^ v s v ^ 56 v7 v i v 8 v 7 v 8 v i v 2 v 3 v 4 v 5 v 6 v 7 v 8 v i v 8 v 7 v 6 v 5 54 Table 4.6: Step 4, w(T4) = 50 CHAPTER 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 128 Step 5 The first column in Table 4.7 represents the demand vertex where the first visit in A ends (see Figure 4.4), the second is the corresponding shortest tour, and the third is the length of the tour. The minimum tour length is w(T5) = 46. V T l(T) VA VlV2VzVAVzV2ViV8V7V&VbVAVj,VAVb 46 v7 ViV8V7VSViV2V:iV4V5V(iV7VsV7VeVr) 46 Table 4.7: Step 5, w(T5) = 46 A shortest tour, T, corresponds to T 3 , with length w(T) = 44. It starts by performing-deliveries at v2, vA and v5, and pickups at v 3 and vx on the way back to v\. Continuing its way to vb along the other s — t path, the tour then skips the pickup at vertex v$, makes a delivery at v7, returns for a pickup at v8, and then reverses direction and makes a pickup at i / 6 on its way to vertex t. 4 . 5 . 3 The V R P D problem on a cycle graph when s and t are predetermined and s = t The case where s = t can be transformed to the case where s ^ t, by inserting a zero-length edge between s and t. Then, the algorithm for a cycle with s ^ f can be applied to this case as well. However, when s = t, i.e. when one of the s — t paths in C is of length zero, the algorithm can be simplified. For completeness, we briefly describe the simplified algorithm. Denote by C\ the cycle obtained from C by inserting the vertex t between s and v\y\, with d(t,v\v\) = d(s,v\V\), and d(s,t) = 0, and by C2 the cycle obtained from C by inserting the vertex t between s and vx, with d(t,vi) = d(s,vi), and d(s,t) = 0. Apply Step 1 of the algorithm for a cycle with s / t , for one of the cycles, either C\ or C2, and Step 2 for both cycles, C\ and C2. The shortest tour among those obtained in Step 1, for either C\ or C2, and those CHAPTER 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 129 obtained in Step 2 for C\ and C 2 is an optimal tour for C with s = t. Implementation and correctness of the algorithm Step 1 checks all the tours on C in which one edge is not traversed. The algorithm for a tree decides if the tour starts its first visit clockwise or counterclockwise, so we don't need to check both C\ and C 2 , Step 2 checks all the ways of traversing the whole cycle C in both directions. On one of the cycles the optimal path algorithm is performed clockwise, and on the other counterclockwise, with the edge (s, t) of length 0 traversed two times. A tour starts (eventually) along the cycle counterclockwise (resp., clockwise) doing deliveries, returns idly clockwise (resp., counterclockwise) to s, goes along A clockwise (resp., counterclockwise) to s using the parametric path algorithm. If an optimal tour is obtained for some capacity c + Svu, it follows from Lemma 4.9 that the same tour can be used for a problem where the pickups between s and u are not performed during this visit. So, if some of the pickups were left behind, the tour continues idly clockwise (resp., counterclockwise) to u and returns back to s counterclockwise (resp., clockwise) while performing the pickups. • 4.6 Append ix Proof of Lemma 4.3: Every edge in L is traversed by T at least once. Suppose that there exists an edge e in L traversed by T more than once. Then, e is traversed by T at least three times. Suppose, on the contrary, that e is traversed by T more than three times. We will show that this implies the existence of a shorter feasible tour T", that traverses e exactly three times, contradicting the optimality of T. Let Vj — Vji be the maximal (with respect to inclusion) subpath of L containing e that is traversed more than once. That is, every edge in Vj — Vj> is traversed more than once (though they do not have to be traversed the same number of times), and the edges (VJ-I,VJ), ( iy, ty+i) are traversed exactly once. This implies that T first per-CHAPTER 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 130 forms all the requests in the subpath s — f j - i , then moves to v3 and after fulfilling all the requests in the subpath Vj — ty, it continues and performs the requests in the subpath Vf+i — t. The following tour T' traverses Vj — Vj> exactly three times, and is shorter than T. It coincides with T until T first reaches Vj. Then T' performs all the requests in the subpath v3 — vy in the following manner: It first travels from v3 to Vji delivering supply to demand vertices while ignoring any pickup requests. Then, it moves back idly from ty to v3, and finally it returns from Vj to vy performing all the pickup requests along this subpath. At this point T' has performed all the requests done by T, just before it moved from vy to ly+i- Note that after moving from to Vji+i, both T and T' fulfilled all the requests in the subpath s — Vj>. From T' coincides with T. Thus, T' is a feasible tour which coincides with T on the subpaths s — Vj-i and vy+i — t, and is shorter than T on the subpath Vj — ty, contradicting the optimality of T. I Proof of Lemma 4.9: If the sum of all deliveries prior to Vik+\ is S (S < 0), T' will traverse all edges prior to v l k + i only once, and the vehicle capacity upon reaching Vik+i will be c — S. T will also traverse all edges prior to vik+l only once. Further, the net load picked up by the vehicle until reaching i>ifc+i is Y!j=\r(vij) ~ S. Therefore, upon reach-ing vlk + i, the vehicle's capacity is also equal to c — S. Since the remaining parts of L and L' are identical, T and T" will also coincide on the remaining part of the path. • Proof of Proposition 4.10: Let vertices i>j,i>t+i be on A, e = (vi,vi+\). (i) Any tour that does not traverse e but visits all vertices in C must contain a subtour wherein it travels from 5 along A to Vi, returns back to s, goes along B to t, continues along A to fj+i, and then returns along A to t. A l l edges on A except e are traversed at least twice and e is not traversed. (ii) Suppose that e is traversed by a tour exactly once, and that each other edge is traversed at least once. If e is traversed in the direction from s to t, the tour is CHAPTER 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 131 going along A in direction from s to t, and does not return to s along A once it reached t. In order for it to visit all vertices along B, the tour must traverse all edges in a subpath (possible empty) of B at least twice before entering A (goes along B in the direction from s to i , until some vertex u\, then back to s and continues along A), and all edges in a subpath (possible empty) of B at least twice after leaving A (goes along B in the direction from t to s, until some vertex u2, then back to t). If e is traversed in the direction from t to s, all edges in B are traversed at least once before the tour first reached t. Since e is traversed exactly once, the tour does not return to t along A. So all edges in B are traversed at least once more on the way from s to t. Either way, all edges in B are traversed at least twice. • In order to prove Theorem 4.11, we need the following lemmas: Lemma 4.13 If a tour traverses all edges in one of the s — t paths at least twice, and all edges in the other s — t path at least three times, the tour cannot be optimal. Proof: Without loss of generality, let us assume that all edges in A are traversed at least three times by a tour T, and let v € A be the supply vertex on A closest to s. The tour that starts along B from s to i and continues along A from t to s doing all deliveries, continues along B from s to t performing pickups, along A from t to v idly, and then back to t along A doing pickups, is a feasible tour shorter than T, so T cannot be optimal: • Lemma 4.14 If an optimal tour, T, starts along A and leaves A for the first time at s, its next visit in A must start at t. Proof: Suppose T is an optimal tour which starts along A and leaves A for the first time at s, but, on the contrary, its next visit in A starts at s. Then, T enters B at s after leaving A, and must leave B at s as well. Let Ax = (s,Ui) denote the segment of A visited by T during its first visit in A, and B\ = (s, Vj) the segment of B visited by T during its first visit in B. CHAPTER 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 132 • If T made only deliveries on By, then it did not need to enter A before visiting B. Indeed, it could start by entering B at s, doing only deliveries along By, exit B at s and combine its two visits in A into one visit. Such a tour will be shorter than T. • If some pickups were performed on By, it follows from Assumption 4.2 that the tour will not visit again the vertices where pickups were performed. If Vj was a pickup vertex, this would mean that the edge (VJ,VJ+I) would remain untraversed. That contradicts the assumption that each edge is traversed at least once, so Vj must be a delivery vertex. Let us denote by vk the supply vertex on By closest to Vj. Using the same argument, if a pickup at vk is performed during the first visit in By, edge (VJ, vJ+\) will not be traversed by T. Let vt be the supply vertex closest to s on By where pickup was not performed during the first visit of T in B (possible v\ = vk); T did not perform any pickup at supply vertices between vi and vk. To perform the pickup at vi, T must enter B at t and leave it at t. That means that T must go along A from s to t, then continue along B from t until vi and return to t along B. Since all edges in A must be traversed at least twice, T must then go along A towards s, past ux to some supply vertex u^, and then return back to t. However, this implies that T traverses all edges on A at least three times and all edges on B at least twice. It follows from Lemma 4.13 that T cannot be optimal. • Lemma 4.15 If the first visit in A by an optimal tour, T, starts and ends at s, and the second visit in A starts and ends at t, T will not visit A again. Proof: The whole length of B is traversed at least once before T enters A for its second visit. Therefore, all deliveries along B were performed before the beginning of T's second visit in A. Any visit by T in B, which starts and ends at t, done after T's second visit in A, will increase the load of the vehicle. Thus, such a visit, if exists, can be delayed until the end of the tour. Therefore, if there is a third visit by T in A, the starting vertex of such a visit must be s. If the third visit in A is not complete, T must have traversed all edges in B at least three times and, by assumption, all edges CHAPTER 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 133 in A have been traversed twice. If the third visit in A is a complete visit, T must have traversed all edges in A at least three times (by assumption each edge therein must be traversed at least twice), and each edge in B at least twice. So, by Lemma 4.13, such a tour cannot be optimal. Therefore, T will not contain a third visit in A. • Lemma 4.16 If the first visit in A by a tour, T, starts and exits at t, and the second visit in A starts and exits at s, the tour T is not optimal. Proof: The whole length of B is traversed at least twice before T enters A for its second visit. After the second visit in A, we have two possible cases: • A l l edges in A were traversed at least twice. Then, from s, T can either go to t along B, or, if no pickups were yet performed in A , T can go from s to t along A. In both cases, non optimality of T follows from Lemma 4.13. • Edges between some vertices u and v in A were not traversed. However, by assumption all edges in A must be traversed at least twice. Thus, T must have at least one more visit in A. However, one can easily verify that these additional visits in A will imply that either T will have to traverse each edge in B at least three times and each edge in A at least twice, or T will have to traverse each edge in A at least three times and each edge in B at least twice. In both cases, non optimality of such a tour follows from Lemma 4.13. • Lemma 4.17 A tour T that has two successive incomplete visits in A (or B) starting and ending in the same vertex, either s or t, cannot be optimal. Proof: We will prove the result for the s — t path A, and a starting and ending vertex s. A l l pickups and deliveries that were performed during the tour's two visits in A could have been done during just one visit. Indeed, let v\ and v2, respectively, denote the furthest points from s on A reached by T during its first and second incomplete visit in A, and let v3 denote the furthest point from s on B reached by T during its incomplete visit in B done in between its two incomplete visits in A. Then, the' CHAPTER 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 134 total length of those incomplete visits by T is equal to 2(rf(s, vx) + d(s, v2) + d(s, v3)), where d(s,vi) and d(s,v2) are calculated along A and d(s,v3) is calculated along B. Now, if the net load picked up by T during its incomplete visit in B is negative (resp., positive), a shorter tour can be obtained by combining the two incomplete visits in A into one incomplete visit, which is done after (resp., before) the incomplete visit in B. The length of that part of the tour will be 2(max{d(s, vi), d(s, v2)} + d(s,v3)) < 2(d(s, vi) + d(s, v2) + d(s, v3)). • Lemma 4.18 A complete visit in A by an optimal tourT must be followed by another complete visit in A. Proof: After a complete visit of T in A, all deliveries along A were performed and only pickups (if any) are left for subsequent visits. On the other hand, it follows from Lemmas 4.15, 4.16, and 4.17 that T contains at most one incomplete visit, Qi, in A, which was carried out before the first complete visit therein. However, pickups were not done in any such incomplete visit in A. Indeed, by Assumption 4.2, pickups can be delayed to the last visit to a pickup vertex. Thus, at the end of the complete visit in A, there are edges in A that were traversed only once. Since we assume that every edge in A is traversed at least twice, T must contain at least one other visit, Q, in A. • If, at the outset, A did not contain supply vertices, then, since T is assumed to be an optimal tour and there are no deliveries left to be performed in A, Q must be a complete visit in A. Indeed, if T contains an incomplete visit in A in which neither deliveries or pickups are performed, then T is not optimal. • If some pickups are left in A after the complete visit therein, and Q is an incomplete visit which starts and ends at the same vertex, say s, and performs its last pickup at i>j, it did not visit any vertex after Vi. Since some pickups were performed in Q, all subsequent visits in A cannot be complete and the tour must go to t along B. If some pickup is still left in A after Q, the last incomplete visit in A must start and end at t, and it cannot go beyond vi+x, the vertex following Vi on A in the direction from s to t. If Q\ did not exist, or Q\ started at s and CHAPTER 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 135 ended at some vertex Vj that is closer to s on A than Vi, or Qi started at t and ended at some vertex vk that is closer to t on A than vi+i, then (vi,vi+\) will be traversed only once, which contradicts our assumption that all edges in A are traversed at least twice. Otherwise, all edges in A will be traversed at least three times, and all edges in B at least twice, and non optimality of T in that case follows from Lemma 4.13. Thus, Q must be a complete visit. A similar conclusion is reached when Q is an incomplete visit which starts and ends at t, and the proof follows. ' • Lemma 4.19 A tour that makes two complete visits in A which start at t cannot be optimal. Proof: After the first complete visit in A which started at t, all edges in both A and B were traversed at least once, and all deliveries in C were performed: A tour which contains a second complete visit in A which starts at t will traverse all edges on one s — t path of C at least three times, and all edges on the other s — t path at least twice. Therefore, by Lemma 4.13, such a tour cannot be optimal. • Proof of Theorem 4.11 An optimal tour, T, can start either along A or along B. If it starts along A, then A is entered for the first time at s. (I) If T, on its first visit in A, leaves A at s, we know from Lemma 4.14 that the second visit must start at t. It can leave A, in the second visit, either at s or at t. • If the second visit exits at t, it follows from Lemma 4.15 that T has Form (4). • If the second visit exits at s, it follows from Lemma 4.18 that there is a third visit to A which is complete. - If the third visit starts at s and ends at t, T has Form (3). A l l deliveries on A and B were carried out before the beginning of the third visit in A, so all pickups are performed during the third visit in A and A will not be visited again. CHAPTER 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 136 - If the third visit starts at t and ends at s, by Lemma 4.19, T cannot be optimal. (II) If an optimal tour, T, on its first visit in A, exits A at t, all deliveries in A were carried out and only pickups are left in A. The second visit in A can start either at s or at t. • If the second visit starts at s, it must end at t because of Lemma 4.18, and T has Form (1). A l l deliveries in A and B were done before the tour's second visit in A, so all the pickups are carried out during the tour's second visit in A, and A will not be visited again. • If the second visit starts at t, it must end at s because of Lemma 4.18, and T has Form (2). There could be other visits in A, which are not complete, if some pickups were left on A after the second visit therein. If the tour, T, starts along B, A can be entered for the first time either at s or at t. (Ill) If A is entered at s, T has left B at s. • If T exits A at s, it is entering B again. - If T has not performed any pickups during its first visits in B or A, it is not optimal since all deliveries in B done during the tour's first visit therein could be done during its second visit in B. - If some pickups were performed during T's first visit in A, T cannot have subsequent complete visits in A, since a pickup from a supply vertex is left for the last visit by the tour to that vertex. Moreover, its second visit in A must start and end at t, and by Lemma 4.15, there are no other visits in A. At the end of the tour's first visit in A, B is traversed from s to t in an optimal manner. However, since the tour started along B, it follows that there was not enough available capacity on the vehicle to perform all the pickups during the first visit by T in A. That is, the sum of all pickups and deliveries performed CHAPTER 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 137 during the first visit by T in A is strictly positive. Thus, the length of an optimal subtour in B from s to t, when the vehicle starts with its initial capacity and performs all requests in B is shorter than the length of that part of T used to traverse edges in B. This suggests that T is not optimal, and a shorter tour can be obtained by a vehicle which starts at s and traverses B in an optimal manner, while performing all requests therein. Then, upon reaching t, the vehicle enters A and travels along A from t to the vertex closest to s in A doing deliveries, and then it returns to t along A while performing only pickups. - If some pickups were performed during the first visit in B, T cannot have subsequent complete visits in B , since a pickup from a supply vertex is left for the tour's last visit in that vertex. So, since the tour must eventually reach t, no pickups were performed during its first visit in A, and the tour must exit B at s after its second visit therein. However, by Lemma 4.17, such a tour is not optimal. • If T exits its first visit in A at t, all deliveries on A were done and only pickups therein remain to be performed. The second visit in A can start at s or at t. - If the second visit starts at s, it must end at t because of Lemma 4.18, and T has Form (1). A l l deliveries on A and B were done before the second visit in A, so all the pickups are performed during the second visit in A, and A will not be entered again. - If the second visit starts at t, then it follows from Lemma 4.18 that it must end at s. Therefrom, the tour traverses B in the direction from s to t. Thus, the vehicle did not pickup supply from any vertex in B in its first incomplete visit therein. Now, since the tour started with an incomplete visit in B, starting and ending at s, the net supply picked up by the vehicle from its first entry into A at s on its first visit, until its exit at 5 at the end of its second visit in A, must be positive. Thus, the length of an optimal subtour in B from s to t, when the CHAPTER 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 138 vehicle starts with its initial capacity and performs all requests in B is shorter than the length of that part of T used to traverse edges in B. This suggest that T is not optimal, and a shorter tour can be obtained by a vehicle which starts at 5 and traverses B in an optimal manner, while performing all requests therein, and then the tour performs one incomplete visit in A, starting and ending at t, while reaching until the closest vertex to s on A. (IV) If ,4 is entered at t, T has traversed all the edges in B at least once and has exited B at t. • If T exits A at s, the second visit can start at s or at t. - If the second visit starts at s, it must end at t because of Lemma 4.18, and T has Form (3). A l l deliveries on A and B were done before the second visit in A, so all the pickups are performed during the second visit in A, and A will not be entered again. - If the second visit starts at t, it must end at s because of Lemma 4.18. It follows from Lemma 4.19 that T cannot be optimal. • If T exits A at t, its second visit in A can start at s or at t. - If the second visit starts at s, all the edges in B were traversed at least twice before the beginning of the second visit in A. Since we assume that all edges in A are traversed at least twice, T will eventually traverse all edges in one of the s — t paths at least twice, and all edges in the other s — t path at least three times. It follows from Lemma 4.13 that T cannot be optimal. If, on the other hand, all edges in B are traversed at least twice, and T traverses some of the edges in A only once, we have obtained an analogue version of the second case in II above, where B is replaced with A. Since the first complete visit in B has started at s, and the second has started at t, T has Form (2). - If the second visit starts at t, then either there was an incomplete visit 4. THE VRPD PROBLEM ON SOME SPECIAL GRAPHS 139 in B, starting and ending at t, between the first and the second visits in A, or there was no such visit in B. In the former case, since all deliveries in B were performed in the first (complete) visit therein, such an incomplete visit can only reduce the available capacity of the vehicle, and thus can be delayed until the end of the tour. In the later case, the first visit in A can be combined with the second (complete) visit in A. In both cases we conclude that if the second visit starts at t, the tour is not optimal. • Bibliography A N I L Y , S., G . M O S H E I O V . 1994. The traveling salesman problem with delivery and back hauls, Operations Research Letters 1 6 , 11-18. A N U P I N D I , R. , Y . B A S S O K . 1999. Centralization of Stocks: Retailers vs. Manu-facturer, Management Science 45, 178-191. A N U P I N D I , R. , Y . B A S S O K , E . Z E M E L . 2001. A General Framework for the Study of Decentralized Distribution Systems, Manufacturing and Service Operations Management 3, 349-368. A N U P I N D I , R. , Y . B A S S O K , E . Z E M E L . 1999. Study of Decentralized Distribution Systems: Part II - Applications, Working paper, Kellogg Graduate School of Management, Northwestern University, Evanston, IL. A U M A N N , R . J . 1959. Acceptable points in general cooperative n-person games, in Contributions to the Theory of Games IV, A . W . Tucker and R.D. Luce eds., Princeton University Press, N.J . , 287-324. A U M A N N , R . J . , J . H . D R E Z E . 1974. Cooperative Games with Coalition Structures, International Journal of Game Theory, 3 217-237. B A § A R , T . , G . J . O L S D E R . 1995. Dynamic Noncooperative Game Theory, Aca-demic Press, Inc., San Diego. B E R N H E I M , B . D . , B . P E L E G , M . D . W H I N S T O N . 1987. Coalition-Proof Nash Equilibria, I. Concepts, Journal of Economic Theory, 42 1-12. 140 BIBLIOGRAPHY 141 B I D D L E , G . C . , R. S T E I N B E R G . 1984. Allocations of Joint and Common Costs, Journal of Accounting Literature 3 , 1-45. B O D I N , L . , B . . G O L D E N , A . A S S A D , M . B A L L . 1983. Routing and scheduling of vehicles and crews - state of the art, Computer and Operations Research 10, 63-211. C A S C O , D . , B . G O L D E N , E . W A S I L . 1988. Vehicle routing with backhands: Mod-els, algorithms and case-studies, in Vehicle Routing: Methods and Studies, ( B . Golden and A. Assad, eds.) Studies in Management Science and Systems, Vol. 16, North Holland Publishing, Amsterdam. C H A L A S A N I , P . , R. M O T W A N I , A . S . R A O . 1996. Algorithms for robot grasp and delivery, Proceedings of 2nd International Workshop of Algorithmic Founda-tions of Robotics, Toulouse France July 1996, 347-362. C H W E , M . S . -Y. 1994. Farsighted Coalitional Stability, Journal of Economic The-ory, 6 3 299-325. CNET News, http://news.cnet.com. Covisint webpage, http://www.covisint.com. Detroit Free Press, http://www.freep.com. E P P E N , G . D . 1979. Effects of Centralization on Expected Costs in a Multi-Location Newsboy Problem, Management Science 25, 498-501. FT.com, http://news.ft.com. F U D E N B E R G , D . , J . T I R O L E . 1991. Game Theory, The MIT Press, Cambridge, Massachusetts. r G E R C H A K , Y . , D . G U P T A . 1991. On Apportioning Costs to Customers in Central-ized Continuous Review Inventory Systems, Journal of Operations Management 10, 546-551. BIBLIOGRAPHY 142 G I L L I E S , D . B . 1959. Solutions to General Non-zero Sum Games, in Contributions to the Theory of Games IV, A . W . Tucker and R.D. Luce eds., Princeton University Press, 47-83. G R E E N B E R G , J . 1994. Coalition Structures, in Handbook of Game Theory Vol.2, R.J . Aumann and S. Hart eds., Elsevier Science B.V. , 1305-1337. H A R R I S , F . W . 1913. How Many Parts to Make at Once, Factory, The Magazine of Management 10, 135-136, 152. H A R R I S , F . W . 1915. Operations and Costs, Factory Management Series, A . W . Shaw Co., Chicago, IL, 48-52. H A R T , S., A . M A S - C O L E L L . 1988. The Potential of the Shapley Value, in A . E . Roth (Ed.), The Shapley Value, Cambridge University Press, Cambridge, N Y , 127-137. H E L P E R , S., J .P . M A C D U F F I E . 2000. E-volving the Auto Industry: E-Commerce Effects on Consumer and Supplier Relationships, prepared for E-Business and the Changing Terms of Competition: A View From within the Sectors, Wharton School, University of Pennsylvania, Philadelphia. H O U S M A N , D . , L . C L A R K . 1998. Core and Monotonic Allocation Methods, Inter-national Journal of Game Theory 27 , 611-616. J I N , M . , S.D. W U . 2000. Supply Chain Contracting in Electronic Markets: Incen-tives and Coordination Mechanisms, Working Paper, Lehigh University. J I N , M . , S .D. W u . 2001. Supplier Coalitions in eCommerce Auctions: Validity Requirements and Profit Distribution, Working Paper, Lehigh University. K A R L I N , S. 1968. Total Positivity, Stanford University Press, Stanford, C A . L E W I S , J . D . 1990. Partnerships for Profit: Structuring and Managing Strategic Alliances, Free Press, New York. Line56 News, http://www.line56.com. BIBLIOGRAPHY 143 L I P P M A N , S .A. , K . F . M C C A R D L E . 1997. The Competitive Newsboy, Operations Research 45, 54-65. M A S U D A , T . , A . S U Z U K I , S, M U T O . 2000. Farsighted von Neumann-Morgenstern Stability Leads to Efficiency in Oligopoly Markets, Research Paper, Tokyo Institute of Technology. M c G u i R E , T . W . , R. S T A E L I N . 1983. An Industry Equilibrium Analysis of Down-stream Vertical Integration, Marketing Science, 2 161-191. M E G I D D O , N . 1974. On the Nonmonotonicity of the Bargaining Set, the Kernel and the Nucleolus of a Game, SIAM Journal on Applied Mathematics 27, 355-358. M O S H E I O V , G . 1994. The traveling salesman problem with pickup and delivery, European Journal of Operations Research 79 (2), 299-310. O U M , T . H . , J . - H . P A R K , A . Z H A N G . 2000. Globalization and Strategic Alliances: The Case of the Airline Industry, Pergamon, New York. O W E N , G . 1975. On the Core of Linear Production Games, Mathematical Program-ming 9, 358-370. P A R L A R , M . 1988. Game Theoretic Analysis of the Substitutable Product Inventory problem with Random Demands, Naval Research Logistics 35, 397-409. R U D I , N . , S. K A P U R , D . F . P Y K E . 2001. A Two-Location Inventory Model with Transshipment and Local Decision Making, Management Science 47, 1668-1680. S A M E T , D . , E . Z E M E L . 1984. On the Core and Dual Sets of Linear Programming Games, Mathematics of Operations Research 9, 309-316. S C H M E I D L E R , D . 1969. The Nucleolus of a Characteristic Function Game, SIAM Journal on Applied Mathematics 17, 1163-1170. S H A P L E Y , L . S . 1953. A Value for N-Person Games, Contribution to the Theory of Games vol.2, Princeton University Press, Princeton, N.J . 307-317. BIBLIOGRAPHY 144 S H U B I K , M . 1962. Incentives, Decentralized Control, the Assignment of Joint Costs, and Internal Pricing, Management Science 8, 325-343. V A N R Y Z I N , G . , S . M A H A J A N . 1999. Supply Chain Coordination Under Horizontal Competition, submitted to Manufacturing and Service Operations Management. X U E , L . 1998. Coalitional Stability Under Perfect Foresight, Economic Theory, 11 603-627. X U E , L . 2000. Negotiation-proof Nash Equilibrium, International J. of Game The-ory, 2 9 339-357. Y A N O , C , T . C H A N , L . R I C H T E R , T . C U T L E R , K . M U R T Y , D . M C G E T T I G A N . 1987. Vehicle routing at quality stores, Interfaces 17, 52-63. Y O U N G , H . P . 1985. Monotonic Solutions of Cooperative Games, International Journal of Game Theory 14, 65-72.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Three essays in supply chain management
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Three essays in supply chain management Sosic, Greys 2002
pdf
Page Metadata
Item Metadata
Title | Three essays in supply chain management |
Creator |
Sosic, Greys |
Date Issued | 2002 |
Description | The three essays in this thesis address various problems in the general area of supply chain management. In general, supply chain management is concerned with management of the flow of goods, information, and funds among supply chain members, such as suppliers, manufacturers, distributors, retailers, and consumers. As such, its scope includes timing and quantity of material flow, logistics, improving efficiencies in problems with several decision makers, etc. The first essay in this thesis considers the problem of improving coordination in a decentralized system of retailers, while the second one addresses stability and profitability of Internet-based supply exchange alliances. The third essay analyzes a logistics problem, of finding an optimal route for a capacitated vehicle which travels on a graph and which can perform pickups and deliveries. In the first essay, we study a three-stage model of a decentralized distribution system with n retailers who each faces a stochastic demand for an identical product. In the first stage, before the demand is realized, each retailer independently orders her initial inventory. In the second stage, after the realization of the demand, each retailer decides what portion of her residual supply/demand she wants to share with the other retailers. In the third stage, residual inventories are transshipped in order to possibly meet residual demands, and an additional profit is allocated among the retailers. We study the effect of implementing various allocations rules in the third stage on the levels of the residual supply/demand the retailers are willing to share with others in the second stage, and the tradeoff involved in achieving a solution which is also optimal for the corresponding centralized system. The second essay is concerned with the formation of Internet-based supply exchange alliances among three or fewer retailers of possibly substitutable products. We provide some conditions, in terms of product substitutability and quality of suppliers, which would lead to the formation of a three member alliance, or a two member alliance, or no alliance at all. We also study the effect of alliance structure and quality of suppliers on the profit of a retailer. The third essay considers a vehicle routing problem with pickups and deliveries (VRPD problem) on some special graphs. Some vertices on the graph represent delivery customers, and other vertices represent pickup customers. The objective is to find a minimum length tour for a capacitated vehicle, which starts at a depot and travels on the graph while satisfying all the requests by the customers without violating the vehicle capacity constraint, and returns to a depot. We have developed linear time algorithms for the VRPD problem on a path and on tree graphs, linear and O (|V| log |V|) algorithm for a VRPD problem defined on a path with parametric initial capacity, and quadratic and O (|V|² log |V|) algorithms for a VRPD problem defined over a cycle graph. |
Extent | 7082068 bytes |
Subject |
Physical distribution of goods Business logistics Supply and demand |
Genre |
Thesis/Dissertation |
Type |
Text |
FileFormat | application/pdf |
Language | eng |
Date Available | 2009-10-05 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
IsShownAt | 10.14288/1.0090712 |
URI | http://hdl.handle.net/2429/13611 |
Degree |
Doctor of Philosophy - PhD |
Program |
Business Administration |
Affiliation |
Business, Sauder School of |
Degree Grantor | University of British Columbia |
GraduationDate | 2002-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_2002-750868.pdf [ 6.75MB ]
- Metadata
- JSON: 831-1.0090712.json
- JSON-LD: 831-1.0090712-ld.json
- RDF/XML (Pretty): 831-1.0090712-rdf.xml
- RDF/JSON: 831-1.0090712-rdf.json
- Turtle: 831-1.0090712-turtle.txt
- N-Triples: 831-1.0090712-rdf-ntriples.txt
- Original Record: 831-1.0090712-source.json
- Full Text
- 831-1.0090712-fulltext.txt
- Citation
- 831-1.0090712.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0090712/manifest