Keywords: Supply chain management, Cooperation, Joint replenishment, Coalition formation, Cost allocation, Stability, Cooperative game theory

List of Tables v

(each actor has his own preferences among the coalitions to which he could belong), we give a new formal representation of the cooperative game -called Hedonic Game. This mainly allow us to discuss the issue of treating the questions of alliance formation and prot allocation simultaneously. We show that under cost-based proportional allocations and equal allocations, there always exist at least two "ecient" coalition structures that are individually and weakly stable and may be strongly stable under some assumptions. Further, we apply this general approach to a FTLJRP-game with three components cost structure (xed and variable transportation cost and holding cost).

Chapter 8 : Extensions and Future Research Directions. Using cooperative game theory seems to be a natural and great framework to model cooperation in supply chains. However, this research area is a rather new stream of research in supply chain management, and several future developments can be done. In this chapter, we aim at introducing some extensions closely related to the present Ph.D thesis. We mainly discuss four topics including (1) Inventory centralization games with explicit transportation costs, (2) Cooperative games with explicit cost formation process, (3) Cooperation in multi-item inventory systems, and (4) Cooperation in service systems. Chapter 9 : Conclusion. This chapter is devoted to the general conclusions of this work. Full truckload shipments (2.2) 2.4.2 One-Supplier Multi-Retailer Joint Replenishment Games Here we consider joint replenishment games (JRP-games). Varying the cost structure, we dealt with two games: 1. In the rst model (Figure (2.5(a))), transportation costs, from supplier to retailer's warehouse, involve two cost components: a xed (a retailer-non-dependent) cost, A, and a variable (retailer-dependent cost), G i , per truck dispatched. With inventory holding costs,

Résumé : À l'ère de la mondialisation, l'environnement industriel et économique a subi plusieurs changements majeurs. Les chaînes logistiques sont en train de devenir de plus en plus de complexes réseaux composés de nombreux acteurs qui sont tantôt en concurrence et tantôt coopèrent pour répondre aux incessantes exigences des consommateurs. Dans un tel contexte, les entreprises se sont rapidement rendu compte de la limite du modèle complètement décentralisé où chacune d'entre elles optimise sa propre chaîne logistique indépendamment des autres acteurs. Afin de trouver de nouvelles sources de compétitivité et de faire face à la perpétuelle complexité de l'environnement économique, les entreprises tentent de dépasser la frontière des actions individuelles favorisant les actions coordonnées et centralisées. Désormais, la coopération entre les diverses chaînes logistiques et la formation d'alliances se trouvent au coeur des préoccupations des entreprises. En effet, en mutualisant les moyens logistiques, la coopération permet une meilleure exploitation des ressources et par le biais des actions collectives, elle permet de mieux bénéficier des économies d'échelles conduisant à réduire significativement les coûts et à générer des bénéfices considérables. Toutefois, dans de tels systèmes coopératifs, les acteurs sont indépendants et par ailleurs toujours intéressés en priorité par leurs profits individuels. De ce fait, la coopération soulève deux enjeux essentiels : (1) Quelles sont les alliances qui sont susceptibles de se former ? Et (2), comment partager les bénéfices réalisés sur les différents acteurs coopérants ? Dans cette thèse, nous nous intéressons au phénomène de la coopération dans les chaînes logistiques. Particulièrement, nous posons les précédentes questions dans des chaînes logistiques ou plusieurs firmes peuvent réduire leurs coûts logistiques en optant pour une gestion collective des stocks. Les principaux résultats de cette thèse portent sur l'utilisation des principes de la théorie des jeux coopératifs pour déterminer les alliances les plus profitables ainsi que la portion de profit que chaque firme doit recevoir afin de garder la stabilité des alliances formées.

Mots clefs :

Chaînes logistiques, Coopération, Formation d'alliances, Allocation des coûts, Stabilité, Théorie des jeux coopératifs.

Abstract:

In the age of outsourcing and globalization, the economic and industrial landscape has seen many radical changes. In such context, supply chains are becoming complex networks of a large number of entities that sometimes compete and sometimes cooperate to fulfill customers' needs. Standalone supply chains, where each entity makes its decisions so as to maximize its own profits according to its own objectives, often lead to a loss of efficiency and fail to face the complexity of the economic environment they are facing with. Cooperative structures, however, where resources/service facilities are shared and decisions are made to maximize the global profit, prove to be more beneficial and efficient. Consequentially, many companies are fundamentally changing their way of doing business by exceeding the border of standalone and individual actions toward collective actions and cooperative strategies. Therefore, building alliances appears as a successful strategy in modern supply chain networks. In general, cooperation enables a better exploitation of the system's resources and offers the opportunity to get benefit from large economies of scope, which in turn reduces the total cost/increases the total savings. However, it raises two natural questions that need to be addressed: (1) Which coalitions can be expected to be formed? And, (2) How will the cooperating actors share their total profit? In this Ph.D. dissertation, we tempt to address these questions in retail supply chains where independent retailers coordinate their replenishment from a supplier in order to save on delivery costs. Considering various joint replenishment environments, our principal contribution is to use principles from cooperative game theory to identify the most profitable alliances and to determine the portion of profit that would be allocated to each actor in order to guarantee the stability of the formed alliances.

Chapter 1

Introduction

The aim of this chapter is to give a general introduction to this Ph.D. thesis. First, we provide problem statement of our work. Second, we highlight some research questions that we answer in this dissertation. Finally, we present the structure of the manuscript.

1.1 Cooperation: A Successful Strategy in "Business Jungle" I am very pleased to begin this manuscript with a very nice Ascop 1 's fable written around the 6th century B.C.,

The Four Oxen and the Lion 2 "Those oxen are too good friends to suit me," said a hungry lion. "They are never far apart, and when I am near them they turn their tails to one another and show long sharp horns on every side. They even walk down to the river together when they become thirsty. If I could catch one of them by himself, I should have a feast."

But one day the oxen had a quarrel. "The grass is freshest over in the valley," said one of them. "Let us go there." "Oh, I don't like the grass there," said another. "It is better on the side of the hill. Let us spend the day there." "I do not want to climb the hill," said the third ox. "The grass right here suits me best." "I do not like any of the places of which you speak," said the fourth ox. "Come with me and I will nd you the best grass you ever tasted." "I am going to the valley," said the rst ox. "You three may go where you please."

"And I shall go to the hill," said the second ox. "I think you are mean not to go with me." "And I," said the third ox, "shall stay right here. You may all be sorry if you leave me. The lion may catch you." "I am not afraid of the lion," said the fourth ox; "and if none of you will go with me, I shall go by myself to hunt a better pasture than any of you can nd. I am older than you and I know where the best grass grows. You had better follow me." "We will not do it," said the other three oxen. "You are not our leader if you are older." So the four oxen separated. One went to the valley. The lion was down by the river and saw him coming. He waited quietly until the ox was very near; then he pounced upon him and killed him.

Then the lion looked about for the other oxen. One of them was feeding on the hill. He saw the lion coming, but, he could not get away. He could not defend himself with only one pair of horns; so he too was killed. As the other two oxen were far apart, it was an easy matter for the lion to kill them also. And that is the way the quarrel ended.

As one can easily guess, the moral lesson of this fable is "United we stand, Divided we fall" said also "Unity is Strength" or "Power lies in Unity". Such expressions have been and continue 1 Aesop (also spelled Esop) is said to have lived during the 6th century B.C. in Greece. Known to be the founding father of fables, i.e., short stories taught as moral lessons.

2 Ascop's fable, rewritten by Lida Brown McMurry in Fifty Famous Fables to be the moral lessons of a wide number of fables, stories and adages. In general, fables are the result of narrators' pure imagination, however the fables with moral lessons about cooperation and unity's strengths in the jungle world are not so imaginative because nature constitutes the best example of cooperation. For instance, contrary to the image of a struggle to death between human beings, the jungle is actually the theatre of much more symbiosis than competition. The study of real jungles proves that life since its birth on Earth, worked innitely more often on the mode of cooperation than on that of domination, otherwise the world would be nished for a long time. In our famous and familiar metaphor "Business is Jungle", a jungle is assumed to be nothing more than a dened area where things eat each other to survive. This metaphor appeared as a perfect metaphor for business because, for a long time, we believed that companies are doomed to be developed only in the military metaphor "business is war" ("outsmarting the competition, capturing market share, making a killing, ghting brands, beating up supplier") or in the old "business is jungle" metaphor ("the strongest that abolishes the weakest" ). Under business-as-war and business-as-jungle, self criterion is the only criterion for action and there are the victors and the vanquished: business is then nothing more than a win-lose game. This "predatory " logic of the liberal system is reaching its limits, and companies are actually adopting the real jungle life mode where surviving and gaining power is not only made by "abolishing the weakest" but somewhat by making friends, building alliances, and deploying coordinated actions. Business is no longer a win-lose game but rather a win-win game.

This change in the way of doing business radically revolutionizes supply chain congurations.

Indeed, in the age of outsourcing and globalization, supply chains are becoming complex networks of a large number of entities that sometimes compete and sometimes cooperate to fulll customers' needs. Standalone supply chains, where each entity makes its decisions so as to maximize its own prots according to its own objectives quite often lead to a loss of eciency and fail to face the complexity of the economic environment. Cooperative structures, however, where resources/service facilities are shared and decisions are made to maximize the global prot, prove to be more benecial and ecient. Consequentially, many companies are fundamentally changing their way of doing business by exceeding the border of standalone and individual actions toward collective actions and cooperative strategies. Therefore coalition/alliance formation appears as a key strategy in current supply chain networks. Alliance building promises to continue growing as the information and communication advances continue to make available new technologies and knowledge. These information infrastructures fundamentally change the way of doing business by making the distinct actors able to access high quality information on each other. In general, cooperation enables a better exploitation of the system's resources, oers the opportunity to benet from large economies of scale, reduces the risk and enhances the negotiation power: this in turn reduces the total cost/increases the total savings. At this point, there are a number of questions that are raised:

• Why is cooperation emerging now as a major brand in supply chain management?

• Is cooperation really highly Benecial?

• Is it dicult to build alliances?

To answer these questions, I will go back to "The Four Oxen and the Lion" Aesop's fable. I nd this fable particularly fascinating because in this story old than more twenty-ve centuries, Aesop did not only emphasize his moral lesson about the powerfulness of unity but rather, without knowing it, described and nicely pointed out the major challenges of the cooperation. On the one hand Aesop well illustrated the value that the cooperation brings into the Oxen's group -their risk management becomes collective and their global power is enhanced -on the other hand, he nicely showed how the success and the stability of an alliance are fragile -the cooperating actors (the oxen) do not have a shared vision which created some conicts and quarrels between them, which in turn causes the disbanding of the coalition. More than twenty-ve centuries later, in modern social science the questions raised by the cooperation are commonly called cooperative behavior questions and are mainly divided in two major questions. The rst one concerns the formation of alliances, and the second one is devoted to the "quantitative" and "qualitative" factors that can hinder or foster the success of alliances. "Qualitative" factors include human moral values such as trust, rivalry, communication, compatibility among the various cooperating actors. "Quantitative" factors concern the attempt to claim an unfair share of the value created by the cooperation. We should note that in supply chain management, the outcome or the value created by the cooperation is often modelled as money savings. Therefore, the question of splitting these created gains seems particularly relevant. Thus, any unfair share of the created value may give rise to defecting actors. This means that unsatised actors skip from their alliances to work for their own or to join other alliances. This is commonly called "stability" problem. To conclude, when dealing with the cooperation in supply chain networks, there are two questions that need to be dealt with: (1) Which alliances can be expected to be formed?

And, (2) How will the cooperating actors allocate their total cost/apportion their total prot?

Obviously the activities of alliance formation and prot allocation are dependent. For instance, the coalition that an actor wants to join depends on the portion of savings that the actor in question would gain in each potential coalition. Thus, the payos inuence the coalition structure and vice versa. In supply chain networks, as well as in general social networks, cooperative game theory have been quite often used to deal with cooperative behavior questions.

The main contribution of cooperative game theory is to provide methods that characterize situations where all cooperating agents agree on how to allocate resulting costs or to share resulting benets. This means that each party would feel that acting as a coalition is worthwhile for its own sake. The alliance in question is then called "stable". In supply chain management (as well as in general social science) most of the considered games were superadditive in the sense that any two or more disjoint coalitions, when acting together, can get at least as much as they can when acting separately. In such situations, there are good reasons to expect the formation of the grand coalition (the set grouping all cooperating actors). Therefore, most of early work focuses on the "stability" of the grand coalition, i.e., dealing with the question of distributing the gain available to the grand coalition to participants. However, as one can expect, many situations are not superadditive and the formation of the grand coalition itself may be quite dicult because acting together is costly or the cooperating actors do not wish to do so because they prefer smaller alliances. In these cases, the question of alliance formation is as challenging as the question of prot allocation.

In keeping with the recent trends in supply chain practice, the goal of this dissertation is to develop a modeling framework and theoretical understanding of cooperative behavior in retail supply chains. In particular, we consider both superadditive and non-superadditive joint replenishment environments, where independent rms coordinate their replenishment from a supplier in order to save on delivery costs. Our aim is to use principles from cooperative game theory to identify the most ecient alliances and to determine the portion of prot that would be allocated to each rm in order to guarantee the stability of the formed alliances. We use the term independent rms broadly to include economic entities that are independently owned and also entities, such as decentralized sub-divisions having the same owner. What is important to our analysis is that these entities are empowered to make independent decisions that minimize their individual costs/maximize their individual prot.

Scope of the Dissertation

In order to achieve our goals, this dissertation will analyze joint replenishment games with the following primary objectives:

• Provide a detailed analysis of the cooperation phenomenon and alliance formation in supply chain networks,

• Provide a critical review of the literature on the analysis of the cooperation in supply chains by means of cooperative game theory,

• Develop and solve cooperative games with applications in supply/replenishment chains,

• Stress the limits of superadditive games and the lack of prior attention to study nonsuperadditive games,

• Point out the drawbacks and the limits of studying totally centralized supply chain and develop more practical solutions that simultaneously treat the problems of alliance formation and prot allocation.

Thesis structure

The remaining part of this Ph.D. dissertation contains height chapters which are:

Chapter 2 : Introduction to Supply chain. This chapter aims at introducing and dening some concepts related to the supply chain used in this thesis. We begin by giving some insights into the history and advancement of logistics and supply chain. Then, we focus on some key components of supply chain management. The second part of the chapter is devoted to state this Ph.D. dissertation's work. To achieve this objective, we dene the functions and the goals of Joint Replenishment Problems and focus on our research topic; Joint Replenishment Games (JRP-Games). We mainly explain how our work diers from that done in traditional Joint replenishment Problems and introduce the JRP-games (models) studied in this dissertation.

Chapter 3 : Preliminaries on Cooperative Game Theory. This chapter aims at introducing and dening some concepts of cooperative game theory that we use throughout this dissertation. We begin by giving a brief historical note on game theory, in which we cover its historical roots prior to its formal denition in 1944. After that, we give formal denitions of n-person cooperative games. We then present the core concept and Shapley Value in addition to some basic allocations such as equal allocations and proportional allocations. After emphasizing alliance formation problems, we devote the last section of this chapter to cooperative games with coalition structures, i.e. situations where the players (participants) are organized in various disjoint coalitions. We formally dene such games and discuss their most central stability concepts:

the coalition structure core, individual stability and farsighted stability.

Chapter 4 : Cooperation in Supply Chain Networks. This chapter is devoted the to phenomenon of cooperation in supply chain networks. The goal is to understand why alliance building is being a key of competitiveness in modern supply chain networks. In the rst part of the chapter, we introduce and discuss the concepts of cooperation in supply chain networks. While, the second part of the chapter is devoted to review the emerging literature on the analysis of cooperation in supply chains by means of cooperative game theory. We conclude by highlighting some non-covered issues, and stressing the contributions of this Ph.D thesis to this new supply chain management research stream.

Chapter 5 : Prot sharing in one-supplier multi-retailer inventory system with full TruckLoad shipments. In this chapter, we are concerned with the problems of alliance formation and cost allocation in one-supplier multi-retailer inventory systems with full Truck-Load shipments. The retailers have to replenish their inventory from the supplier to satisfy a deterministic and constant rate demand of nal customers with full truckload shipments. Each full-truck order is associated with a xed transportation cost. The storage of products involve linear holding costs at the retailers' warehouses. Both cost components are supported by the retailers. To reduce their costs, retailers may choose to cooperate by making joint orders. The main goal of this chapter is to study the arising cooperative game called Joint Replenishment Game with Full TruckLoad shipments (for short, FTLJRP-game). We focus on the core and Shapley value; two of the most central solutions in cooperative game theory. Under the above cost structure the FTLJRP-game is superadditive. We mainly show that its core is non-empty and provide a core allocation. This core allocation is then compared to Shapley value. The comparison is based on four criteria: stability, complexity, fairness and practical setting.

Chapter 6 : Coalition Formation and Cost Allocation for Joint Replenishment Systems. This chapter aims at studying the issues of coalition formation and prot allocation in joint replenishment systems. Under this model, the reorder cost associated with an alliance/coalition of retailers placing an order at the same time equals some alliance-independent cost plus retailer-dependent costs. In addition, each retailer is associated with a retailer-dependent holding-cost rate. Despite early works on this eld, we do not aim at optimizing the supply chain as whole. In our analysis, we focus on a supply chain where the cooperation cannot be forced, i.e, each retailer joins the coalition he/she wants to belong to. We present an iterative procedure to form the coalitions and focus on analyzing the merits of such achieved "ecient coalition structure". Without too much loss of global supply chain performance, when considering the cost-based proportional rule, the ecient coalition structure is individually and weakly stable.

We provide a condition under which the strong stability (stability in the sense of coalition structure core) holds.

Chapter 7 : Stability of Hedonic Joint Replenishment Games with General Cost Function: Application to the one-supplier multi-retailer joint replenishment system with full Truckload shipments. In this chapter we analyze cooperative behavior questions in joint replenishment systems with general cost function. Using the notions of preference relations Chapter 2

Introduction to Supply Chain

This chapter aims at introducing and dening some concepts related to the supply chain used in this thesis. We begin by giving some insights into the history and advancement of logistics and supply chain. Then, we focus on some key components of supply chain management. The second part of the chapter is devoted to state this Ph.D. dissertation's work. To achieve this objective, we dene the functions and the goals of Joint Replenishment Problems and focus on our research topic; Joint Replenishment Games (JRP-Games). We mainly explain how our work diers from that done in traditional Joint replenishment Problems and introduce the JRP-games (models) studied in this dissertation.

Historical Background

The history of logistics goes a long way since humanity learned how to organize and build its own organizations. Its modern roots can be traced back to its military origins when modern armies started to consider logistics or the supply chain as part of their strategies [START_REF] Pimor | Logistique: Production, Distribution, Soutien[END_REF].

In fact, modern practices of supply chain management in business follows the general pattern as with managing logistics for defence or making war.

In war, logistics is the art of moving supplies and reinforcements along a supply chain in order to support the war eort and keep soldiers well-fed and ready to ght. Even the greatest army must be properly supplied to achieve victory. In business, logistics is the art of moving the product or service to the customer where and when the customer needs it and to be fast and exible enough to win the customer's business. The same fundamental truth that governs war also governs business: without an ecient supply chain, victory is impossible. An army without supplies cannot win wars, just as a business that fails to deliver its product on time cannot win customers. In business, as in war, superior logistics makes all the dierence.

During the Second World War, highly complex military supply chains have been set up. This induced considerable developments, such as transportation management and the use of complex production and transportation planing methods. Managerial logistics emerged out of military logistics in the middle of the twentieth century, and turned into a very important component in industry applications. In the same time, science landscape has seen the birth of the "Operational

Research" domain.

In the second half of the twentieth century, the industry went through a lot of changes. The most signicant ones were the important rise of the number of companies sharing the same market segment and the growth of technological and information advances. In this new environment, manufacturing industries based on mass-production have reached their limit. It became therefore necessary to take into account not only production activities, but also all industrial activities, including supply, distribution and other activities that are related to production process. As a consequence, the "modern" supply chain was born. This area has been widely improved after the development of "Computer Science" and "Operations Research". Since that, many elds of logistics like "Production Planning", "Inventory Management" and "Transportation

Management" are knowing very important improvements and continuing to trigger the interest of researchers and practitioners.

The Supply Chain Concept

Denition

A supply chain (Figure 2.1) is a network of facilities and distribution options that performs the functions of procurement of materials, transformation of these materials into intermediate and nished products, and the distribution of these nished products to customers. More generally, a supply chain may be dened as the set of parties and agents (such as suppliers, manufacturers, transporters, retailers, etc.) involved, directly or indirectly, in fullling a customer's request [START_REF] Chopra | Supply chain management: strategy, planning and operation[END_REF][START_REF] Sarmah | Buyer vendor coordination models in supply chain management[END_REF]. In fact, supply chains exist in both service and manufacturing organizations, although the complexity of the chain may vary greatly from industry to industry and from rm to rm. The objective of each supply chain is to maximize the overall generated value. The value a supply chain generates is the dierence between what the nal product is worth to the customer and the costs the supply chain incurs in lling the customer's requests. At the same time, other objective would be the increase of the customer's service level in order to satisfy its requirements in an optimal manner. Both objectives could of course be connected via some costs (like backlogging costs) [START_REF] Simchi-Levi | Designing and Managing the Supply Chain[END_REF].

The dierent entities and agents appear to be somewhat disparate, because in most cases, they are owned by several individuals/organisations. Nevertheless, they are all linked by the integrated nature of the supply chain business. Thus, a local weakness may aect the whole performance of the supply chain. This strategic viewpoint has created the challenge of coordinating eectively the entire supply chain, from upstream to downstream activities. A well-integrated supply chain requires coordination among all entities and agents. It should involve coordinating the ows of materials and information between suppliers, manufacturers, and customers [START_REF] Narasimhan | Linking business unit and material sourcing strategies[END_REF].

Supply Chain Management

Supply chain management (SCM) can be dened as the process of planning, implementing and monitoring the everyday operations of a supply chain. Supply chain management is an all encompassing process as it undertakes the management of availability of raw materials, their processing into nished goods and the distributions of these goods to nal customers. The aim of all this is to provide the highest level of satisfaction to the customer, thus increasing the business of the company.

With the increasing complexity of the supply chain, supply chain management has also become about coordinating and collaborating with the dierent trade partners now involved in the supply chain. Under this strategic point-of-view, [START_REF] Cooper | Characteristics of supply chain management and the implications for purchasing and logistics strategy[END_REF] compare supply chain management to a well-balanced and well-practiced relay team. Such a team is more competitive when each player knows how to be positioned for the hand-o. The relationships are the strongest between players who directly pass the baton, but the entire team needs to make a coordinated eort to win the race.

Supply Chain Decisions

Supply chain management decisions can be classied into three broad categories: strategic, tactical and operational (see Figure 2.2).

As the term implies, strategic decisions are typically made over a longer time horizon. These are closely linked to the corporate strategy and guide supply chain policies from a design perspective. Among these decisions, we nd the number, location and size of the warehouses, of the distribution centers and of the facilities. Strategic decisions may also include the decisions related to Information and Technology infrastructure that support the supply chain operations, and to strategic partnership.

Tactical (or mid term) decisions include planning decisions aiming at balancing charge and capacity. Such decisions include the production (contracting, locations, scheduling and planning process denition), the inventory (quantity, location and quantity of inventory), the sourcing contracts and other purchasing decisions.

Finally, the operational decision level is divided in two sub-levels. The so-called "ow management" level is relative to short time decisions, such as the decisions of launching the production, ordering and transportation orders. The second sub-level, called "scheduling," is relative to very [START_REF] Dallery | Notes de cours de logistique industrielle[END_REF] short-term decisions including the decisions of scheduling the dierent tasks inside a workshop.

The eort in the tactical and operational levels is to eectively and eciently manage the product ow in the "strategically" planned supply chain.

Joint Replenishment Problem and Joint Replenishment Game

As mentioned before, the goal of this Ph.d dissertation is to understand cooperative behavior of retail supply chains. The main of this section is to show how our work diers from that done in retail supply chain management. To achieve this goal, we introduce in the following joint replenishment problems -one of the most addressed issue in retail supply chains-then we focus on our concern : joint replenishment games.

Joint Replenishment Problem (JRP)

In the basic JRP (Figure 2.3(a)), a single facility replenishes a set of items over a nite horizon.

Whenever the facility places an order for a subset of the items, two types of costs are incurred:

A joint set-up cost and an item-dependent set-up cost. Called also, major set-up cost and minor set-up cost. These costs are stationary. The objective in the joint replenishment problem is to decide when and how many units to order for each item so as to minimize inventory holding and ordering costs over the planning horizon (see for example [START_REF] Chakravarty | An optimal heuristic for coordinated multi-item inventory replenishment[END_REF][START_REF] Bastian | Joint replenishment in multi-item inventory systems[END_REF]. We should note that the joint replenishment problem has been also studied for the one-supplier multi-retailer systems under the same cost structure. For instance, in these problems, n retailers replenishes their inventory form a single supplier via direct shipments. Fixed and variable costs are incurred for each truck dispatched and all trucks have the same capacity limit. Demands for the n retailers over a planning horizon of T periods are given. The objective is to nd the shipment quantities over the planning horizon to satisfy all demands at minimum system-wide inventory and transportation costs without backlogging. We should note that in the multi-retailer systems, a second version (more studied) of the JRP is considered. In this problem version (see Figure 2.3(b)), the retailers order goods from a warehouse whose inventory is in turn replenished by an external supplier, the holding cost at the centralized warehouse is included in the model.

The One-Supplier Multi-Retailer systems (in all its versions) with stationary xed charge costs and constant demand over a nite/innite horizon has been extensively studied. The most early ones can be traced back to [START_REF] Schwarz | A simple continuous review deterministic one-warehouse nretailer inventory problem[END_REF][START_REF] Roundy | 98% eective integer lot sizing for one warehouse multiretailer systems[END_REF]. We should mention that in basic joint replenishment problems, the considered cost structure has been concerned with only inventory costs.

In modern supply chains transportation plays a fundamental role as it allows production and consumption to take place at locations that are several hundreds or thousands of miles away from each other [START_REF] Chopra | Supply chain management: strategy, planning and operation[END_REF]. Moreover Transportation costs accounts for a signication part ( often between one-third and two-thirds) of the logistics costs [START_REF] Tseng | The role of transportation in logistics chain[END_REF]. As a result, recent versions of the joint replenishment problem take into account transportation decisions in considering explicit transportation costs as in [START_REF] Mutlu | The transporter's impact on channel coordination and contractual agreements[END_REF][START_REF] Sindhuchao | An integrated inventoryrouting system for multi-item joint replenishment with limited vehicle capacity[END_REF] or in modelling new supply chain trends such transportation with full truckload shipments. This transportation mode consists in moving a full load directly from its origin to its destination in a single trip. As emphasized by [START_REF] Muriel | Single-warehouse multi-retailer inventory systems with full truckload shipments[END_REF] this shipment mode is actually the most common mode of transportation in industry applications. In keeping with this trend, some authors have studied the one-supplier multi-retailer joint replenishment problem with Full TruckLoad Shipments. This means that all shipments from supplier/warehouse to retailers are full TruckLoad and direct shipments; that is, trucks move a full load directly from supplier/warehouse to a single retailer and back (all trucks have the same capacity limit)(see for example [START_REF] Muriel | Single-warehouse multi-retailer inventory systems with full truckload shipments[END_REF]).

Joint replenishment problems are computationally complex problems. For instance, the basic joint replenishment problem has been shown to be NP-hard [START_REF] Arkin | Computational complexity of uncapacitated multi-echelon production planning problems[END_REF]. Besides, the Single-supplier Multi-Retailer problem is also NP-hard with or without full TruckLoad shipment variant [START_REF] Muriel | Single-warehouse multi-retailer inventory systems with full truckload shipments[END_REF]. Therefore, the main goal of papers in this research topic was often to provide polynomial solutions or fast heuristics.

In this dissertation our interest is dierent, we are aiming to focus on the Joint Replenishment Game instead of traditional Joint Replenishment Problem.

Joint Replenishment Game (JRP-game)

The Single-Supplier Multi-Retailer Joint replenishment Game (JRP-Game) can be stated as follows: A number of independent retail facilities faces known demands of a single product (the products can be identical or not) over an innite planning horizon. They order goods from the same external supplier. All shipments from supplier's warehouse to retailers are direct; that is, trucks travel directly from the warehouse to a single retailer and back, see [START_REF] Gallego | On the eectiveness of direct shipping strategy for the one-warehouse multi-retailer r-systems[END_REF]. There is no limit on the quantity ordered each period. There are a xed and a variable cost per truck dispatched from supplier to retailers, and linear holding costs at the retailers' warehouses. All costs are stationary costs; i.e., the xed and variable transportation charges and the linear holding costs do not change over time. Both of transportation costs and linear inventory holding costs involved by products' storage are supported by the retailer.

The term game is broadly used to include that the retailer are independent and freely interacting in the afore-described supply chain. This means that the cooperation cannot be forced. Hence, unlike the traditional Joint Replenishment Problem we do not aim at optimizing the chain as whole. What is important to our analysis is that the retailers are empowered to make independent decisions that minimize their individual costs/maximize their individual prot. That is, each one of them may keep a standalone strategy where he/she optimizes his own system independently from the other retailers. Going from this decentralized situation, if they nd it benecial form them to do so, a group of retailers may form an alliance and replenish their inventory jointly to save on delivery costs. The objective is to study the formation of such alliances and to answer the related challenging questions. Particulary, Which are the alliances that are more likely to be formed? And giving a set of retailers willing to form an alliance, when and how many units to ship from supplier to each period so as to minimize their total transportation and holding costs without any shortages. And more importantly, how should these retailers "fairly" apportion their achieved savings? To deal with theses questions, we mainly use principles from cooperative game theory; a science especially designed to help cooperative behavior's understanding.

When considering full truckload shipments from the supplier to retailers, without loss of generality, we assume that the demand at each retailer in each period is less than a full truckload and all trucks have the same capacity limit. We refer to this version of the problem as the Single-Supplier Multi-Retailer Full Truckload Shipments Joint replenishment Game (FTLJRP-Game).

Dissertation's Models Description

In this Ph.D thesis, we consider the Single-Supplier Multi-Retailer Joint replenishment Games with/and without FTL Shipments (JRP-Games and FTLJRP-Games) under the afore-described three-components cost structure ,i.e.,

• Holding Costs: The storage of products in each retailer's warehouse involves a linear in- ventory holding cost.

Transportation costs, from the supplier to retailer's warehouse, involves two cost components:

• Fixed Transportation Cost: a retailer non-dependent cost involved per each truck dis- patched. Called also, xed ordering cost.

• Variable Transportation Cost : a retailer dependent cost involved per each truck dispatched.

Called also, individual cost.

More specically, in chapter 5, 6 and 7, we investigate the following four joint replenishment game variants.

One-Supplier Multi-Retailer Full TruckLoad Joint Replenishment Games

In these games we consider joint replenishment systems where each retailer replenishes his/her inventory using full truckload shipments. Let us denote, the truck capacity by CAP and product volume (weight) by V i. Varying the cost structure, we dealt with two models : With inventory holding costs, the standalone cost of retailer i ordering for a quantity Q i is:

C(Q i ) = A. D i Q i Transportation cost + h i .Q i 2
Holding cost

, such that:

(Q i .V i = CAP ) Full truckload shipments (2.1)
2. In the second model (Figure (2.4(b))), transportation costs, from supplier to retailer's warehouse, involve two cost components: a xed (a retailer-non-dependent) cost, A, and a variable (retailer-dependent cost), G i , per truck dispatched. With inventory holding costs, the standalone cost of retailer i ordering for a quantity Q i is:

C(Q i ) = (A + G i ). D i Q i Transportation costs + h i .Q i 2
Holding cost

, such that:

(Q i .V i = CAP )
C(Q i ) = (A + G i ). D i Q i Transportation costs + h i .Q i 2
Holding cost

(2.3) 2. In the second model (Figure (2.5(b))), we deal with general cost functions.

C(Q i ) = (C(i))
General Cost Function

(2.4)

The well-known Economic Order Quantity (EQO) (see [START_REF] Harris | How many parts to make at once[END_REF]; [START_REF] Silver | Inventory Management and Production Planning and Scheduling[END_REF]) is used as a reorder policy for both standalone and cooperative situation in our models.

Conclusion

This chapter constituted an introduction to the supply chain concepts and especially to the joint replenishment notions. We have begun by giving a brief historical background of the military origins of the supply chain. Then, we have dened the main notations and decision levels of the supply chain. Another important aspect of our work, which has been studied in this chapter is the denition of joint replenishment problems and the statement of joint replenishment games.

The main idea is that in traditional Joint Replenishment Problems, the goal was to optimize the supply chain as a whole, however, in this dissertation the focus will be on Joint Replenishment Games where the main goal is to study the dierent interactions between the independent entities that constitute the supply chain. To achieve our goals, we need many principles from cooperative game theory: a science specially designed to understand networks cooperative behavior.

The principal concepts of cooperative game theory will be strongly introduced and studied in the next chapter. While in chapter 4, we focus on the analysis of the cooperation in supply chain by means of cooperative game theory.

Chapter 3

Preliminaries on Cooperative Game Theory

This chapter aims at introducing and dening some concepts of cooperative game theory that we use throughout this dissertation. We begin by giving a brief historical note on game theory, in which we cover its historical roots prior to its formal denition in 1944. After that, we give formal denitions of n-person cooperative games.

We then present the core concept and Shapley Value in addition to some basic allocations such as equal allocations and proportional allocations. After emphasizing alliance formation problems, we devote the last section of this chapter to cooperative games with coalition structures, i.e. situations where the players (participants) are organized in various disjoint coalitions. We formally dene such games and discuss their most central stability concepts: the coalition structure core, individual stability and farsighted stability. 21

Background

Since humanity birth, man realizes that he is interacting, and in competition, with other individuals who are, themselves, aware of this. Thus he must (a) outsmart others, (b) learn from others' behavior, (c) cooperate with others, (d) bargain with others [START_REF] Gambarelli | The coming of game theory[END_REF].

This constitute the main fundamental ideas of game theory which is about what happens when people-or genes, or nations-interact [START_REF] Camerer | Behavioral Game Theory: Experiments in Strategic Interaction[END_REF]. Social scientists have long attempted to understand the fundamental causes of conict and cooperation in human societies. The advent of game theory in the middle of the twentieth century led to major new insights and enabled researchers to analyze the subject with mathematical rigor. As such, the modern denition of game theory is the study of mathematical models of conict and cooperation between intelligent rational decision makers" [START_REF] Myerson | An Introduction to Game Theory[END_REF].

Earlier game theory's roots can be traced back to the beginning of the 18th century. For instance, the rst work on this area can be attributed to James Waldegrave and Pierre-Remond de Montmort for their analysis of the card game "Le Her" [START_REF] De Montmort | Essay d'analyse sur les jeux de hazard[END_REF]. The main concept of the analysis at that time was the minimax problem (i.e., the existence of equilibrium strategies minimizing the maximum expected loss for each player). Later Bernoulli, while studying "Le Her", introduced the concept of expected utility and demonstrated its potential applications in Economics [START_REF] Bernoulli | Specimen theoriae novae de mesura sortis[END_REF]. Numerous other works could be cited until the beginning of the 20th century. A relevant detailed historical note is found in [START_REF] Gambarelli | The coming of game theory[END_REF].

As the 19th century turned into the 20th, numerous works mainly on strategies and twoperson games arise. This includes for example [START_REF] Zermelo | Über eine anwendung der mengenlehre auf die theorie des schachspiels[END_REF][START_REF] Bertrand | Calcul des probabilités, éléments de la théorie des probabilité[END_REF][START_REF] Borel | La théorie du jeu et les équations intégrales à noyau symetrique gauche[END_REF][START_REF] Von Neumann | Zur theorie der Gesellschaftsspiele[END_REF][START_REF] Von Neumann | Über ein Ökonomisches Gleichungssystem undeine Verallgemeinerung des Brouwerschen Fixpunktsatzes. Ergebnisse eines Mathematischen Seminars. Vienna. Translated by G.Morton in (1945) as A model of general economic equilibrium[END_REF]. In this period, and particularly in the decade 1930-1940, the science landscape has seen fundamental changes. The synergies of experts from dierent elds give birth to many new theories in physics, computer science, mathematics, economics. From this, and at Princeton University, game theory emerged from the collaboration of the mathematician John von Neumann1 and the economist Oscar Morgenstern 2 through their book The Theory of Games and Economic Behavior published in 1944. This book is universally known to give the starting point of game theory as a formal science. Earlier studies, even those by von Neumann himself, had not been introduced in the context of a precise science, which the publication of the above book created.

The real beginnings of Modern Game Theory can be dated from 1944 for two reasons:

rst, previous works were fragmentary and lacked organization; second, these works did not attract much attention. With the publication of von Neumann and Morgenstern's book, the Theory of Games had its own concrete organization of fundamental topics at both competitive and cooperative levels. Furthermore, the reputation of the two authors attracted the attention of both mathematicians and economists. [START_REF] Gambarelli | The coming of game theory[END_REF], page 6. In non-cooperative theory, a game is a detailed model of all the moves available to the players. By contrast, cooperative theory abstracts away from this level of detail, and only describes the outcomes that result when the players come together in dierent combinations [START_REF] Brandenburger | Cooperative game theory : Characteristic functions, allocations, marginal contribution[END_REF]. In what follows, we continue to give some insights on the advancement of each of both game theory branches.

Von

Non-Cooperative Game Theory

Non-cooperative game theory is concerned with the problem of one individual who has to choose among various risky options or to choose a best strategy from several possible choices. However, the preferences that an agent has on his actions depend on which actions the other parties take. The main idea of non-cooperative game theory is then to analyze and understand such Multiperson Decisionmaking Process. For instance, the various options and payos are often represented in a matrix which allows the calculation of the best single strategy or combination of strategy -one strategy for each player. Matrix algebra and techniques from linear programming are used quite often. The theory of non-cooperative game was mainly enhanced by John Nash's works [START_REF] Nash | Equilibrium points in n-person games[END_REF][START_REF] Nash | Non-cooperative games[END_REF][START_REF] Nash | Two-person cooperative games[END_REF]. A detailed biography of John Nash has been written by [START_REF] Nasar | The lost years of a nobel laureate[END_REF]. An interesting and detailed note on the history of Nash's work may be found in [START_REF] Myerson | Nash equilibrium and the history of economic theory[END_REF].

The most central solution concept in non-cooperative game theory is that of Nash equilibrium. Nash's concept, based on the idea of equilibrium in a physical system, was that players would adjust their strategies until no player could benet from changing. All players are then choosing strategies that are best (utility-maximizing) responses to all the other players' strategies [START_REF] Camerer | Behavioral Game Theory: Experiments in Strategic Interaction[END_REF].

Nash formally dened an equilibrium of a noncooperative game to be a prole of strategies, one for each player in the game, such that each player's strategy maximizes his expected utility payo against the given strategies of the other players....Nash's theory of noncooperative games should now be recognized as one of the outstanding intellectual advances of the twentieth century. The formulation of Nash equilibrium has had a fundamental and pervasive impact in economics and the social sciences which is comparable to that of the discovery of the DNA double helix in the biological sciences. [START_REF] Myerson | Nash equilibrium and the history of economic theory[END_REF], page 3.

Later, John [START_REF] Harsanyi | Games with incomplete information played by bayesian" players, iii: the basic probability distribution of the game[END_REF][START_REF] Harsanyi | Games with incomplete information played by bayesian" players, i: the basic model[END_REF] showed that Nash's solution concept could be generalized to games with incomplete information (that is, where players do not know each others' preferences). Reinhard [START_REF] Selten | A simple model of imperfect competition where 4 are few and 6 are many[END_REF][START_REF] Selten | Reexamination of the perfectness concept for equilibrium points in extensive games[END_REF] demonstrated that it could be rened for dynamic games and for games where players make mistakes with (innitesimally) small probabilities. The great intellectual achievements of these researchers that fundamentally change the economic science landscape have been recompensed in 1994, when John Nash, John Harsanyi, and Reinhard

Selten shared the Nobel Prize in Economic Science.

For better understanding of non-cooperative game theory, the reader is referred to the books: [START_REF] Fudenberg | Game Theory[END_REF], [START_REF] Myerson | Game Theory: Analysis of Conict[END_REF] and [START_REF] Camerer | Behavioral Game Theory: Experiments in Strategic Interaction[END_REF].

Cooperative Game Theory

Cooperative game theory is primarily concerned with coalitions-groups of players-who coordinate their actions and pool their winnings. The central problem here is to divide the extra earnings (or cost savings) among the members of the formed coalition [START_REF] Branzei | Models in Cooperative Game Theory : Crisp, Fuzzy, and Multi-Choice Games[END_REF].

Consequently, in a cooperative game, the players focus on the choice of stable" payo vectors and not on the choice of a stable" prole of strategies as in non-cooperative game [START_REF] Peleg | Introduction to the Theory of Cooperative Games[END_REF]. In other words, in non-cooperative game theory, the players cannot make binding agreements about what to do, so they must guess what others will do. Cooperative game theory deals with how players divide the spoils after they have made binding agreements [START_REF] Camerer | Behavioral Game Theory: Experiments in Strategic Interaction[END_REF].

Like non-cooperative games, the basis of this theory is attributed to Neumann and Morgenstern with their work on coalitional games in characteristic function form, also known as transferable utility games (TU-games). Since then several interesting concepts for cooperative game have been proposed. For instance, when continuing the enumeration of young Princeton mathematicians' contributions, Dobald [START_REF] Gillies | Some Theorems on n-Person Games[END_REF] in his Ph.D. thesis at the Department of Mathematics developed the concept of the core using the notion of domination presented by Neumann and Morgenstern. This concept represents the set of nondominated imputations called "stable" imputations. In other words, the core is the set of imputations having the propriety that no group of players would have the incentive to leave the system and form a coalition because they collectively receive at least as much as they could obtain for themselves as a coalition [START_REF] Gillies | Solutions to General Non-zero Sum Games[END_REF]. The core was criticized to be in some cases empty or to contain many imputations in other cases.

As John Nash revolutionized non-cooperative game theory, Lloyd Shapley revolutionized cooperative game theory. For instance, the well-known Shapley value was introduced in 1953 (Shapley, 1953b). The value concept solved the afore problems of existence and uniqueness that had until then eectively stopped the development of n-person cooperative games [START_REF] Gambarelli | The coming of game theory[END_REF]. Shapley set quite reasonable axioms (a detailed explanation of such axioms will be provided later) and determined that there was a unique function (the value) satisfying these axioms for any n-person cooperative games with transferable utility. The main idea of Shapley was to award, to each player, the average of his marginal contributions to each coalition. There are many historical and theoretical notes on Shapley value, same of them are [START_REF] Winter | The shapley value in Handbook of Game Theory with Economic Applications[END_REF][START_REF] Béal | Farsighted coalitional stability in tu-games[END_REF]. Shapley (1953a) also made an important stride in the development of dynamic games by introducing stochastic games, in which the game passes from position to position according to probability distributions inuenced by players. Shapley proved the existence of a value for these games, though they are formally innite, and found ways of computing optimal strategies. [START_REF] Shapley | On balanced sets and cores[END_REF] simultaneously and independently with [START_REF] Bondareva | Theory of the core in an n-person game (in russian)[END_REF] describes, in what we call today the Bondareva-Shapley theorem", a necessary and sucient condition for the nonemptiness of the core of a cooperative game. Specically, the game's core is non-empty if and only if the game is balanced. Later, [START_REF] Shapley | Cores of convex games[END_REF] applied these results to the particular class of convex games.

Early works on cooperative game theory supposed that the game is superadditive" in the sense that any two disjoint coalitions, when acting together, can get at least as much as they can when acting separately. In such situations, there are good reasons to expect the formation of the grand coalition (the coalition grouping all the players in the system). Therefore, these works focused on describing plausible ways of distributing the gain available to the grand coalition to individuals.

The 2005 Nobel Economics Prize (shared with Thomas Schelling) Robert John Aumann made an important stride in the development of cooperative game theory by studying coalition formation problems or the so-called games with coalition structures, i.e, an n-person cooperative games where the players are organized in several disjoint coalitions, forming a partition formally called coalition structure. The rst note on this context was perhaps that of [START_REF] Aumann | The bargaining set for cooperative games in Advances in Game Theory Edited by[END_REF]. A more detailed and generalized study may be found in [START_REF] Aumann | Cooperative games with coalition structures[END_REF]. [START_REF] Aumann | Cooperative games with coalition structures[END_REF] warn that in some cases "acting together may be dicult, costly or illegal, or the players may for various personal reasons not wish to do so". In addition to a nice explanation on coalition formation problems, [START_REF] Aumann | Cooperative games with coalition structures[END_REF] characterized the prot sharing in a context where many disjoint coalitions are involved. Their main remark is that in such context, the reward should be allocated in a way that there is no side-payment between the coalitions, i.e, the players within the same coalition share what they win by themselves (their coalition).

Moreover, [START_REF] Aumann | Cooperative games with coalition structures[END_REF] extend the grand coalition-solutions (the core, Shapley value , etc) to games with coalition structures. For detailed notes on coalition formation, the reader is referred to [START_REF] Drèze | Hedonic coalitions: Optimality and stability[END_REF][START_REF] Greenberg | Coalition Structures in Handbook of Game Theory with Economic Applications[END_REF][START_REF] Ray | A Game-Theoretic Perspective on Coalition Formation[END_REF].

At this point, we only have emphasized some of Shapley and Aummann contributions. However we should mention that many other scientists were involved in the advancement of cooperative game. We should also mention that the Core and Shapley value presented up to now are the most famous known solution concepts in cooperative game theory. Nevertheless there were indeed other solutions (not covered here) such as: the kernel, the nucleolus, von Neumann-Morgenstern solutions, bargaining sets, and others. For detailed accounts of cooperative game theory, the reader is referred to [START_REF] Curiel | Cooperative Game Theory and Applications: Cooperative Games Arising from Combinatorial Optimization Problems[END_REF], [START_REF] Slikker | Social and Economic Networks in Cooperative Game Theory[END_REF], [START_REF] Peleg | Introduction to the Theory of Cooperative Games[END_REF], [START_REF] Branzei | Models in Cooperative Game Theory : Crisp, Fuzzy, and Multi-Choice Games[END_REF] and [START_REF] Brandenburger | Cooperative game theory : Characteristic functions, allocations, marginal contribution[END_REF].

The rest of the chapter is devoted to cooperative games with transferable utility (TU-game).

We should note that a cooperative game might be a non-transferable utility game (NTU-game);

the reader is referred to [START_REF] Peleg | Introduction to the Theory of Cooperative Games[END_REF] and [START_REF] Tijs | Introduction to Game Theory[END_REF] for an introduction to NTU-games. In the following, we only present the concepts used throughout this dissertation and used in supply chain management literature in general. This includes, the core, the coalition structure core, Shapley value and farsighted Stability.

Cooperative Games: Representations and Denitions

Let N = {1, ..., n} be a non-empty nite set of agents (players) who consider dierent cooperation possibilities. Each subset S ⊆ N is referred to as a coalition or alliance. The set N is called the grand coalition and ∅ the empty set. We denote the collection of coalitions, i.e. the set of all subsets of N by Ω. The number of coalitions in Ω is 2 n (|Ω| = 2 n ). For each S ∈ Ω, |S| refers to the number of agents in S.

Denition 1 A cooperative game with transferable utility (TU-game) is a pair (N, v)

where N is the player set and v is the characteristic function, i.e. a function that associates a real number v(S) to each subset S of N . v : Ω -→ R and v(∅) = 0

The real v(S) can be interpreted as the maximal worth of cost savings that the members of S would divide among themselves if they were to cooperate together and with no player outside S. A game (N, v) is often identied with its characteristic function v. Note that the characteristic function may be a cost function that assigns to each group of players forming a coalition S the corresponding cost (C(S)). In this form, the game is called a cost game.

While the rst game is called savings game. Of course, both denitions are interrelated, since a cost game may be reformulated as a savings game with a worth function dened as:

v(S) = ( i∈S C({i}) -C(S)
). The subgame (S, v S ) denes the restriction of the game on coalition S, S ⊂ N. A cooperative game with transferable utility is also called a cooperative game in characteristic form or a coalitional game with transferable utility. In the rest of this chapter and over this dissertation a cooperative game (or simply, a game) is referred to as a transferable utility game (TU-game).

Denition 2 A game (N, v) is superadditive if:

(S, T ⊆ N and S ∩ T = ∅) =⇒ v(S ∪ T ) ≥ v(S) + v(T ). (3.1)
The following weak version of superadditivity is very useful.

Denition 3 A game (N, v) is weakly superadditive if:

v(S ∪ {i}) ≥ v(S) + v({i}) for all S ⊆ N and i ∈ S.

Condition (3.1) is satised in most of the applications of cooperative games [START_REF] Nagarajan | Game-theoretic analysis of cooperation among supply chain agents: Review and extensions[END_REF][START_REF] Hajduková | On coalition formation games[END_REF]. It means that any two disjoint coalitions, when acting together, can get at least as much as they can when acting separately. Therefore, the grand coalition N is formed quite often, i.e., it is benecial for all the players to cooperate together.

Denition 4 :

• A game (N, v) is convex if v(S) + v(T ) ≤ v(S ∪ T ) + v(S ∩ T ) for all S, T ⊆ N . Convex
games appear in some important applications of game theory [START_REF] Shapley | Cores of convex games[END_REF].

• A game (N, v) is positive if v(S) ≥ 0 for all S ⊆ N • A game (N, v) is monotone if v(S) ≤ v(T )
for any pair of coalitions (S, T ) such that Denition 5 The marginal contribution of player i to the coalition

S ⊆ T • A game (N, v) is symmetric if v(S) = v(T )
S, i ∈ S, is M C i (S, v) := v(S) -v(S\{i}).
In words, the marginal contribution of a player to the coalition that he belongs to is the amount by which the coalition's value would shrink if this player were to defect from this coalition.

Denition 6 An allocation (x 1 , x 2 , ..., x n ) is a division of the overall created value. It species for each player i ∈ N the prot portion (value) x i that this player will receive when he cooperates with the other players.

Denition 7 :

• An allocation (x 1 , x 2 , ..., x n ) is individually rational if x i ≥ v({i}) for all i. • An allocation (x 1 , x 2 , ..., x n ) is ecient if |N | i=1 x(i) = v(N ).
• An imputation is an ecient and individually rational allocation.

The above denition is quite intuitive. Indeed, individual rationality means that a division of the overall value (i.e. an allocation) must give each player as much value as that player receives without interacting with the other players (single coalition). Eciency, means that all the value that can be created, i.e., the quantity v(N ), is in fact divided.

The Core

To dene the core, some additional notations will be useful. For any subset S of the set of players N, let x(S) = i∈S x(i). In words, the term x(S) denotes the sum of the values received by each of the players i in the subset S.

Denition 8 An allocation

(x 1 , x 2 , ..., x n ) is collectively rational if x(S) ≥ v(S) for all S ⊆ N .
The collective rationality is an extension of the individual rationality to all possible coalitions.

It means that each coalition gets a total prot portion higher than what the coalition in question can realize by its own.

Denition 9 The core [START_REF] Gillies | Solutions to General Non-zero Sum Games[END_REF] is the set of ecient allocations satisfying the collective rationality.

Co(N, v) = x ∈ R N \x(N ) = v(N ) and ∀S ⊆ N, x(S) ≥ v(S) (3.2)
In a game (N, v), if any group of players, say S, anticipated capturing less value in total than the group could create on its own, i.e., if x(S) < v(S), then this group of players would do better to create a coalition apart ,S, and divide the value v(S) by themselves. This would not happen under core allocations. In summary, the core has the interesting interpretation that the total created value is allocated in such a way that no group of players would have the incentive to leave the system (the grand coalition N ) and form a coalition apart because they collectively receive at least as much value as they could obtain for themselves as a coalition. The grand coalition is then immune to coalitional deviations, this concept has been called, the core stability.

Denition 10 The grand coalition N is said to be stable or core stable if it has a non-empty core.

For better understanding of the core concept, we present the following example (presented in [START_REF] Béal | Théorie des jeux coopératifs[END_REF]). Consider a 3-player cooperative game (N, v) such that v({i}) = 0 for all i ∈ N = {1, 2, 3}, v({i, j}) = a for all i, j ∈ N, i = j and v(N)=6. We consider two cases, a = 2 and a = 5. As showed in equation (3.6), the core of the game is dened by the following system of equations:

         x 1 + x 2 + x 3 = 6 x i + x j ≥ a, ∀i, j ∈ N, i = j x i ≥ 0, ∀i ∈ N
By considering the projection in the plane of equation (x 1 + x 2 + x 3 = 6) we can easily represent the core in a 2-dimensional space. The result of the two cases (a=2 and a=5) is reported in (Figure 3.1). It is clear that the core contains an innity of allocations for a=2 while it prescribes the empty set for a =5. This simple example emphasizes two of the major challenging problems of the core. Indeed, on the one hand, the core may contain many allocations, and on the other hand the core may be empty. A game with an empty core is to be understood as a situation of strong instability, as any allocation proposed to the grand coalition is vulnerable to coalitional deviations. When the core contains several allocations the question is which one to choose. In this case, the literature on cooperative games generally has a list of desirable requirements that allocation rules may need to satisfy, such as equity, the list is long and is often depending on the context. In the next section we present some of these particular allocations.

The Core

x 2 =(0,6,0) x 1 =(6,0,0)

x 3 =(0,0,6) x({1,3})=2 x({1,2})=2 x({2,3})=2
Player 2 Player 1 Player 3

x 2 =(0,6,0) x 1 =(6,0,0)

x 3 =(0,0,6) x({2,3})=5 x({1,2})=5 x({1,3})=5 Player 2 Player 1 Player 3 a=2 a=5
The Core

x 2 =(0,6,0) x 1 =(6,0,0)

x 3 =(0,0,6) x({1,3})=2 x({1,2})=2 x({2,3})=2
Player 2 Player 1 Player 3

x 2 =(0,6,0) x 1 =(6,0,0)

x 3 =(0,0,6) x({2,3})=5 x({1,2})=5 x({1,3})=5

Basic Allocation Rules

In this section, we turn our attention to describing the three allocation rules that we use in the rest of the dissertation. This includes, equal allocations, proportional allocations and Shapley

Value allocations.

Shapley Value Allocations

This section is devoted to introduce the concepts and axioms of Shapley value (Shapley, 1953b),

one of the most central solution concepts in game theory. Shapley value is a solution that prescribes a single payo for each player, which is the average of all marginal contributions of that player to each coalition he is a member of. It satises the following axioms:

• (i) Eciency: The payos must add up to v(N ), which means that all the grand coalition surplus is allocated.

• (ii) Symmetry: If two players are substitutable because they contribute the same to each coalition, the solution should treat them equally.

• (iii) Additivity: The solution to the sum of two TU-games must be the sum of what it awards to each of the two games.

• (iv) Dummy player: If a player contributes nothing to every coalition, the solution should pay him nothing.

The main result of Shapley (1953b) is that:

Theorem 3.1 (Shapley, 1953b): There is a unique single-valued solution to TU-games satisfying eciency, symmetry, additivity and dummy. It is what we call today the Shapley value, the function that assigns to each player i the payo:

Sh(N, v)(i) = S⊆N :i∈S (|S| -1)!(|N | -|S|)! |N |! (v(S) -v(S \ {i}))
Shapley value awards to each player the average of his marginal contributions to each coalition. The marginal contribution of a player i with respect to a given ordering is dened as his marginal worth to the players before him in the order, v({1, 2, ..., i -1, i}) -v({1, 2, ..., i -1}),

where 1, 2, ..., i -1 are the players preceding i in the given ordering. Shapley value is obtained by averaging the marginal contributions for all possible orderings. In taking this average, all orders of the players are considered to be equally likely.

Shapley value is usually viewed as a good normative answer to the question posed in cooperative game theory. That is, those who contribute more to the groups that they belong to should be paid more. However, Shapley value may be not stable in the sense of the core. For instance, it may allocate a negative value to some players. Besides, Shapley value may lie outside the core unless for some special games like convex games [START_REF] Shapley | Cores of convex games[END_REF]. For a recent study on Shapley value's stability see [START_REF] Béal | Farsighted coalitional stability in tu-games[END_REF].

Equal Allocations

The simplest allocation of savings would be to give an equal portion to each player.

ϕ E i = v(N ) n (3.3)

Proportional allocations

Another simple way of allocating savings would be to distribute them proportionally to the initial inputs (contributions) of dierent players. For example, consider a savings game (N, v) such that

v(S) = ( i∈S C(i) -C(S)
) for any coalition S, the function C is the cost characteristic function.

The savings may be allocated proportionally to the standalone cost (initial cost) of each player, this what it is called the cost-based proportional rule. Each player i gets,

ϕ P i = C(i) j∈N C(j) .v(N ) (3.4)
So player i is paying,

C(i) -ϕ P i = C(i) j∈N C(j)
.C(N )

Games with Coalition Structures

Early work on cooperative game theory supposed that the games are superadditive. In the previous sections, we focused on describing plausible ways of distributing the gain available to the grand coalition N to individuals. Nevertheless, superadditivity is quite often violated, or large coalitions fail to be formed. The following section is devoted to underline the main solution concepts in such situations.

Denition 11 A coalition structure for N is a partition of the player set N , i.e. P = {S 1 , ..., S m } is a coalition structure for N ⇐⇒ (S i ∩ S j = ∅ for i = j and i=m i=1 S i = N ).

Let P be the nite set of coalition structures. The value or the savings associated to a coalition structure, P = {S 1 , ..., S m }, is equal to the sum of the savings of the coalitions forming it, i.e.,

v(P ) = S j ∈P v(S j ) (3.5)
Denition 12 If (N, v) is a game and P is a coalition structure for N , the triple (N, v, P ) is then called a game with coalition structure.

Clearly, (N, v) ≡ (N, v, {N }) hence we shall write (N, v) instead of (N, v, {N }).

In words, a game with coalition structure refers to a situation where the cooperating players are organized in many disjoint coalitions forming a coalition structure (partition).

The scenario usually associated with the coalition structure idea is as follows: the players consider forming the coalitions S 1 , ..., S m ; one may think of them as going to business lunches in m dierent groups, each S k forming a group. At these lunches they negotiate the division of the payo, on the assumption that the coalitions S 1 , ..., S m will be formed". [START_REF] Aumann | Cooperative games with coalition structures[END_REF], page 231-232.

Stability Concepts of Games with Coalition Structures

In a game with coalition structure (N, v, P ), each allocation or payo vector, x, need to satisfy the propriety ,(x(S i ) = v(S i ), ∀S i ∈ P ). This means that no side-payments is allowed between the various coalitions; the players within the same coalition would divide the value created by themselves (the quantity v(S)). As emphasized by [START_REF] Aumann | Cooperative games with coalition structures[END_REF], this axiom is the major axiom required for games with coalition structures.

For a given characteristic function v, the major element introduced by the coalition structure P lies in the condition x(S k ) = v(S k ), which constrain the solution to allocate exactly among the members of each coalition the total payo of that coalition". [START_REF] Aumann | Cooperative games with coalition structures[END_REF], page 231.

The Coalition Structure Core

Aumann and [START_REF] Aumann | Cooperative games with coalition structures[END_REF] rene the concept of the core to dene the coalition structure core.

In addition to the collective or group rationality, they consider the above constraint emplaning that there is no side-payments between coalitions.

Denition 13 The coalition structure core of a game (N, v, P ) is as follows:

Co(N, v, P ) = x ∈ R N \x(S i ) = v(S i ), S i ∈ P and ∀S ⊆ N, x(S) ≥ v(S) (3.6)
A coalition structure P is then stable if its coalition structure core contains at least one allocation. Such stability will be referred as the strong stability.

The coalition structure core stability means that no group of players (belonging to the same coalition or member of disjoint coalitions) will have the incentive to deviate. As such, the payo inside coalition S k involves a mixture of considerations which are endogenous to S k (no group of players inside S k will defect) and of considerations which are exogenous to S k reecting the "outside opportunities" of the members of S k (coalition that "cut across" the S k cannot be formed). It is always dicult to prove the non-emptiness of the coalition structure core and to nd coalition structure core allocations. For this reason, the following weak version of coalition structure core is very useful.

The weak version of the coalition structure core is obtained by ignoring the movement of groups of players that "cut across" two or more coalitions. In other word, the collective rationality will be restricted to group of players that are member of the same coalition. This has another interesting interpretation: it means that each coalition taken separately is core stable.

Denition 14 A coalition structure P = {S 1 , ..., S m } is said to be weakly stable if all subgames (S i , v S i ) are core stable, i.e., there exists an allocation x such that: x ∈ Co(S i , v S i ), ∀S i ∈ P .

We should note that as underlined by [START_REF] Aumann | Cooperative games with coalition structures[END_REF], x ∈ Co(S i , v S i ), ∀S i ∈ P does not imply that x ∈ Co (N, v, P ). For this reason, the presented concept is weaker than the coalition structure core.

Individual Stability

The stability concepts exposed above are used in models where a partition is considered to be stable if it is immune to coalition or group deviations. When only the immunity of individual move is required, we get the individual stability concept, which is also a weak concept. Individual stability was inspired by the classical notion of Nash equilibrium and was introduced to game theory by [START_REF] Drèze | Hedonic coalitions: Optimality and stability[END_REF]. This stability concept only ensures immunity to those movements of individuals where an unsatised player can defect from his coalition and join a new one. We should note that the defection is only accomplished when this move is benecial for the player and the coalition he joins no matter whether the coalition he leaves loses or wins.

Denition 15 . Individual stability. A coalition structure is said to be individually stable if no player can benet from moving from his coalition S to another existing coalition T while not making the members of T worse o.

Farsighted Stability

The core/coalition structure core concept presented in the previous sections has been-and continue to be-the most central solutions in cooperative game theory. Nevertheless, the core (along with the majority of solution concepts commonly used in game theory) has been criticized to be usually empty and too static or myopic. To understand this criticism, we consider the following situation. Assume that the grand coalition is formed, and suppose that the overall value is shared in a way that a given subset of players (coalition) can generate on its own more than the sum of allocations assigned to its members. In this case, the existing static concepts will immediately conclude that the grand coalition is not stable, because they assume that the subset of players in question will defect and form their own coalition. There are two main problems with such conclusion (the instability of the grand coalition). First, will the deviating coalition be stable? If not, why should we conclude that the move from the grand coalition will ever happen? Secondly, the static analysis does not check if a further defection will occur (Nagarajan et al., 2009). Core's myopia is then reected by the fact that a coalition does not take into account the possibility that the rest of the players may do. That is, after a group of individuals moves, another group and then a third group of individuals would move, and so on. Players are farsighted when they take into account such a sequence of moves and evaluate their payos in the end.

A solution concept that allows players to consider multiple possible further deviations is the largest consistent set (LCS) presented by [START_REF] Chwe | Farsighted coalitional stability[END_REF]. It is known and used as farsighted stability. The main idea of [START_REF] Chwe | Farsighted coalitional stability[END_REF] was to replace the direct dominance relation dening the core by some indirect dominance relation, which captures the fact that farsighted players consider the nal alternatives that their moves may lead to. He denes his LCS as follows:

I dene the largest consistent set, a solution concept which applies to situations in which coalitions freely form but cannot make binding contracts, act publicly, and are fully farsighted" in that a coalition considers the possibility that once it acts, another coalition might react, a third coalition might in turn react, and so on, without limit.....The largest consistent set dened here solves these two problems simultaneously: It takes farsightedness" fully into account and is non-empty in wide range of environment". [START_REF] Chwe | Farsighted coalitional stability[END_REF], page 299-300.

We should mention that following Chwe's work, many authors prove the existence, uniqueness, and non-emptiness of the largest consistent set (see for example [START_REF] Béal | Farsighted coalitional stability in tu-games[END_REF]). There are many strands of the literature that have emerged in the framework considered by [START_REF] Chwe | Farsighted coalitional stability[END_REF].

Now we briey review Chwe's formal denition of farsighted stability. Let P = {S 1 , ..., S m } a coalition structure and let ϕ i (P ) denotes the payo obtained by player i in coalition structure P . Let us denote by ≺ i the players' strong preference relations, described as follows: for two coalition structures, P 1 and P 2 , P 1 ≺ i P 2 ⇐⇒ ϕ i (P 1 ) < ϕ i (P 2 ), where ϕ i (P 1 ) and ϕ i (P 2 ) denote respectively the retailer i's allocation of saving in the coalition structures in coalition structures

P

Conclusion

This chapter constituted an introduction to some principles of cooperative game theory. We began by giving a brief historical note on game theory covering its historical roots prior to its formal denition in 1944. After that, we focused on the cooperative game's concepts we need in this thesis. We rst gave formal denitions and properties of n-person cooperative games, and then presented the core concept and Shapley Value in addition to some basic allocations such as equal allocations and proportional allocations. The last section of the chapter was devoted to the main stability concepts (this includes the coalition structure core, individual stability and farsighted stability) of games with coalition structures.

In the next chapter we will motivate our interest to study the cooperation in supply chain and we will discuss, through a detailed literature review, how the afore presented cooperative game theory concepts contributed to model and to understand supply chain cooperative systems.

Chapter 4

Cooperation in Supply Chain Networks

This chapter is devoted the to phenomenon of cooperation in supply chain networks.

The goal is to understand why alliance building is being a key of competitiveness in modern supply chain networks. In the rst part of the chapter, we introduce and discuss the concepts of cooperation in supply chain networks. While, the second part of the chapter is devoted to review the emerging literature on the analysis of cooperation in supply chains by means of cooperative game theory. We conclude by highlighting some non-covered issues, and stressing the contributions of this Ph.D thesis to this new supply chain management research stream.

Supply chain Changes and Challenges

Today's competitive, fast-moving business environment has irrevocably changed the supply chain and the management of its functions. For instance, the main idea of supply chain was referring to "something that consists of elements that are linked to each of their two immediate neighbors and which jointly provide a strong but exible connection" [START_REF] Rolf | Supply chains and social network analysis. 1st International European Forum on Innovation and System Dynamics in Food Networks[END_REF]. This traditional view of "chain" where dierent functions/rms are linked in a linear and simple fashion is no longer a reality given the complicated and global rate at which business is now conducted [START_REF] Ladd | From supply chain to supply network: A new paradigm in customer service and productivity[END_REF]. The paradigm of today's supply chain must be metamorphosed into a non-linear, complex network that allows ecient interaction among thousands of suppliers and partners regardless of their size, location or number of products. We no longer talk about "supply chain" but rather about "supply chain network."

Authors like [START_REF] Omta | Chain and network science: A research framework[END_REF][START_REF] Harland | Social network strategy and social capital[END_REF], [START_REF] Dyer | Creating and managing a highperformance knowledge-sharing network: the toyota case[END_REF]; [START_REF] Dyer | The relational view: Cooperative strategy and sources of interorganizational competitive advantage[END_REF], [START_REF] Lazzarini | Integrating supply chain and network analysis: The study of netchains[END_REF] and [START_REF] Netessine | Supply Chain Networks[END_REF] have emphasized the network character of SCM. In this growing literature, many terminologies have been proposed. [START_REF] Harland | Social network strategy and social capital[END_REF] and [START_REF] Nassimbeni | Network structures and co-ordination mechanisms. a taxonomy[END_REF] introduce "Supply Network", [START_REF] Lazzarini | Integrating supply chain and network analysis: The study of netchains[END_REF] propose the term "Netchain" while [START_REF] Netessine | Supply Chain Networks[END_REF] talks about "Supply Chain Networks".

The key word in these denitions is the term "Network". This term has been dened by [START_REF] Powell | Neither market nor hirarchy: Network forms of organization[END_REF] as a lateral and horizontal exchange of resources and communication between independent partners. As pointed out by [START_REF] García | From supply chain network orientation to supply chain network management. I Mediterranean Conference of Agro-Food Social Scientists. 103rd[END_REF] the denitions of networks are grouped around two key concepts: (1) a model of interaction based on exchange and relationships, and

(2) a ow of resources between independent units.

The network character of supply chain has been the topic of several textbooks up to now.

Many authors studied supply chain networks form a strategic and social point of view [START_REF] Dyer | Creating and managing a highperformance knowledge-sharing network: the toyota case[END_REF][START_REF] Lazzarini | Integrating supply chain and network analysis: The study of netchains[END_REF]. Other references focused on pointing out the changes in many examples of industries. For instance, [START_REF] Frank | Transaction costs as determinants of vertical coordination in the u. s. food industries[END_REF] have studied the vertical coordination aspects in U.S.Food Industries. [START_REF] Fearne | The evolution of partnerships in the meat supply chain: Insights from the british beef industry[END_REF] presented insights on the evolution of partnerships in Meat Industry networks. García andGarcía (2006, 2007) focused on the network character of Agri-Food industry. [START_REF] Netessine | Supply Chain Networks[END_REF] gives many telling examples that nicely illustrate the typical challenges that the automotive, the aerospace and defense industries are facing. The author ended his paper by an emphasis on academic research in supply chain network area. Early research framework was pointed out by [START_REF] Omta | Chain and network science: A research framework[END_REF].

Given the current economic climate and the complexity of supply chain networks mentioned above, companies looking to enhance their competitive advantage in the marketplace have imperatively to develop and to keep close relationship with each other. As such, the trend in modern supply chain networks is to seek partnerships in order to improve the eciency in the face of increasing globalization and outsourcing. For instance, in recent years and particularly in the last decade, we have all heard and continue to hear the term "supply chain cooperation" and "supply chain coordination" quite often. Its buzz quotient has been on the rise because of business landscape's changes. Indeed, in current supply chain networks, the organizations are considering the cooperation and the coordination in their business processes more strategically and look for more rened and closed relations with the other supply chain network participants.

These strategies appear as a key factor of competitiveness. However, even if it is a controversial topic in both academia and industry, the denition of supply chain cooperation/supply chain coordination continues to elude many. For instance, with all recent articles on this topic and the growing number of companies choosing such strategies to manage their supply chains, there still remains a great deal of confusion. On evaluating the related huge body of literature, we fail to identify one single consistent denition of the concepts. Indeed, people are using many terms, mainly: "cooperation" often used interchangeably with "coordination" and sometimes with "collaboration". However, these terms actually describe dierent levels of supply chain relationships.

In what follows, based on organizational studies and supply chain network related texts, we will try to make clear the boundaries of each term.

Coordination

In supply chain network, companies have individual (private) goals and objectives that they can achieve by themselves. In this case, they can control and execute their plans independently.

However, all companies are linked by the integrated nature of the supply chain business they are doing and are thus operating in the same environment. In such environment, conicts may arise. Therefore, they need to synchronize their course of actions in order to avoid harmful interactions. Such process is called coordination. In other words, coordination within a supply chain is a strategic response to the problems that arise from inter-organizational dependencies within the chain. Coordination takes place between two or more rms where tight control is involved through a coordination mechanism that synchronizes two or more specic functions [START_REF] Mentzer | Supply Chain Management[END_REF]. In today supply chain networks, as information technology is getting cheaper to deploy, rms' information systems are more strongly linked, and rms engage in more coordination mechanisms, such as Collaborative Planning, Forecasting and Vendor Managed Inventories (VMI) to get a better handle on demand information [START_REF] Arabe | Supply Chain Collaboration Unscrambled[END_REF]. More generally, in supply chain literature, the term "coordination" was used quite often to qualify Buyer-Supplier (or bilateral) relationships.

Cooperation

Cooperation also noted co-operation, takes its origins from the Latin co, meaning "together," and operari, meaning "to work". As such, cooperation refers to situations where many participants work together to achieve mutual goals. Cooperation has been dened as joint striving toward a common object or goal [START_REF] Stern | The interorganisational management of distribution channels -prerequisites and prescriptions[END_REF]. According to [START_REF] Stern | Distribution channels as political economies : a framework for comparative analysis[END_REF], cooperation is an activity in which potential collaborators are viewed as providing the means by which a divisible goal or object desired by the parties may be obtained and shared. In summary, cooperation is conceptualized as " a set of joint actions of rms in close relationship to accomplish a common set of goals that bring mutual benets" [START_REF] Mentzer | Supply Chain Management[END_REF]. By working together and coordinating their actions, the supply chain participants become partners in an alliance [START_REF] Monczka | Success factors in strategic supplier alliances: the buying company perspective[END_REF]. The term "alliance" is commonly used to give shape to cooperative behaviors in an interrm context. [START_REF] Lambe | National account management: large account selling or buyer-seller alliance?[END_REF] dene an alliance as a collaborative relationship among rms to achieve a common goal that each rm could not easily accomplish alone. Similarly, [START_REF] Zeng | Achieving cooperation in multiparty alliances: a social dilemma approach to partnership management[END_REF] dened an alliance as a broad term referring to collaborative arrangements in which participants explicitly agree to work together in the belief that, by doing so, they are more likely to succeed than by working alone. [START_REF] Gulati | Does familiarity breed trust? the implications of repeated ties for contractual choice in alliances[END_REF] suggests that alliances encompass a variety of agreements whereby two or more rms agree to pool their resources to pursue specic market opportunities.

In this dissertation the focus will be on the cooperation and strategic alliances as a key of business success and competitiveness in supply chain networks.

The Cooperation: Motives, Outcomes and Barriers

The cooperation and alliance formation appear as a successfully strategy and interesting trend in supply chain networks, however it raises a variety of challenging questions. For instance,

• Why Cooperate?

• How to cooperate?

• What are the outcomes of the cooperation?

• What factors can hinder the achievement of the cooperation?

The answers to the above questions is summarized in Figure

Outcomes

Competitive Advantages:

-Lower cost, -Higher value added, -High customer satisfaction, -Better service, -Better risk management, -High bargaining power, -Etc.

Cooperation Mechanisms

-Joint ventures, -Mergers, -Joint investments in specific assets, -Shared communication, -Joint planning and problem solving, -Joint-replenishment, -Shipment consolidation, -Etc.

Barriers

-Trust, -Compromise, -Interdependency, -Inter-organizational compatibility, -Shared vision and key processes, -Leading role in the cooperation, -Created value sharing, -Etc.

Motives

-Economic factors, -Technological advances, -Political-legal factors, -Socio-cultural factors, -Consumer's expectations, -Products' complexity, -Spatial dispersion of production, -Etc.

Traditional Supply Chain Supply Chain Network

Why Cooperate?

The business world is a rapidly changing landscape marked by unprecedented complexity. Increased global trade makes supply chains even longer and more dynamic. This profound impact of globalization on traditional supply chains makes many companies exceeding the border of individual actions toward collective actions/stategies to better deal with the geographical dispersion of supply chain entities, dierent laws and customs. Such cooperative strategies were also reinforced by the creation of new supply chain concepts such as Third-Party Logistics Providers [START_REF] Simchi-Levi | Designing and Managing the Supply Chain[END_REF][START_REF] Marasco | Third-party logistics: A literature review[END_REF].

The information and communication technologies (ICT) advances have also played a key role in changing the way of doing business. Thereby making distinct supply chain entities able to access high quality information of each other, new challenges and trends have emerged in supply chains. With the proliferation of the Internet and e-commerce, time becomes compressed.

The ow of information and orders becomes nearly instantaneous, especially where procurement systems were electronically integrated with the sales and production systems of their suppliers.

Among these new technologies, we may mention Radio Frequency Identication (RFID) technology and Electronic Data Interchange (EDI). For a detailed description of new trends in supply chain design and management with an emphasis on technologies and methodologies we refer the reader to [START_REF] Jung | Trends in Supply Chain Design and Management: Technologies and Methodologies[END_REF].

How to Cooperate?

To compete successfully, companies may use of several forms of cooperation such as mergers, joint ventures, joint investment in specic assets, joint replenishment and shipment consolidation. The detailed description of these mechanisms is out of the scope of this thesis. But the main idea of the cooperation in supply chain networks is that independent rms share their holding infrastructures and ordering channels. Therefore, when an alliance of rms is to form, each rm works with the best holding technology and ordering channels among the members of the coalition. This means that the members of that coalition manage their cost components (purchasing, holding inventory etc.) at the minimum cost of the coalition members [START_REF] Ozen | A multi-retailer decentralized distribution system with updated demand information[END_REF]. In other words, cooperation refers to situations where the activities and/or the resources of some independent rms are pooled and joint problems are solved. As one can expect, information sharing is a key determinant of success and achievement of supply chain partnerships [START_REF] Lascelles | The buyer-supplier relationship in total quality management[END_REF][START_REF] Galt | Supplier development: A british case study[END_REF][START_REF] Krause | The antecedents of buying rms' eorts to improve supplier[END_REF]. For instance, in order to nd joint solutions to their joint problems, supply chain actors must agree on sharing information related to these problems [START_REF] Carr | Strategically managed buyer-seller relationships and performance outcomes[END_REF].

What are the Outcomes of the Cooperation

When cooperating, companies win new business, achieve market penetration, improve their performance and increase their protability. Thus, cooperative strategies enable rms to keep costs down-all while improving their levels of service to meet the growing expectations of customers. In general, the values that cooperation brings into supply chain networks are threefold: reduction of the costs, risk pooling and negotiation power enhancing. The rst major advantage of cooperation is the reduction of costs through shared resources and economies of scale. Indeed, depending on the form of cooperation, the inventory levels and/or transportation costs are often reduced.

Moreover, with joint orders, many economies of scale can be achieved and signicant savings can be reached when joint investments in specic assets are done. A second issue is that of better risk management. Indeed, within a supply chain, an actor is no longer alone to deal with the internal and external disturbances facing him. In a given alliance, the risk management becomes collective, whereas it was individual. Finally, the last issue is that of power. When several actors are willing to cooperate, they create an entity that federates and pools their forces. Therefore, these actors benet from a greater power during their negotiations with their environment. This includes for example the case of several actors deciding to join together to impose lowest prices to their supplier.

What Factors Can Hinder the Success of the Cooperation?

Many studies in both industry and academia have emphasized the importance of cooperation in supply chain as a key topic given the current economic climate. However, many supply chain cooperative structures fail to realize such benets [START_REF] Boddy | Success and failure in implementing supply chain partnering: an empirical study[END_REF]. Similar to the body of literature focused on the contribution and the impact of the cooperation on the eectiveness of logistics networks, the barriers that may hinder the success of supply chain networks cooperative structures have been the topic of a separate body of literature. See for example [START_REF] Boddy | Success and failure in implementing supply chain partnering: an empirical study[END_REF][START_REF] Park | Inter-rm rivalry and managerial complexity: a conceptual framework of alliance failure[END_REF][START_REF] Mccarter | Happy together? insights and implications of viewing managed supply chains as a social dilemma[END_REF]. In such literature, several scholars suggest that conceptualizing strategic alliances as social dilemmas helps to understand how cooperation in strategic alliances can be achieved and sustained over time [START_REF] Zeng | Achieving cooperation in multiparty alliances: a social dilemma approach to partnership management[END_REF].

It has been shown that the success of supply chain alliances is not only related to the intention to cooperate. For instance, the fact that supply chain partners willingly choose to cooperate does not necessarily ensures that they will do so successfully. There are a number of factors that can hinder the development and the success of partnership in supply chain networks. This includes, trust between partners, compromise, interdependency or mutual dependency between partners, organizational compatibility (i.e., goals, objectives, shared operational philosophy and corporate culture), shared vision and key processes [START_REF] Mentzer | Dening supply chain management[END_REF]. In addition to "interrm rivalry" [START_REF] Park | Inter-rm rivalry and managerial complexity: a conceptual framework of alliance failure[END_REF] or misalignments in allying rms' eorts to cooperate, including reluctance to share information, skills and processes, and opportunistic behavior [START_REF] Dyer | Creating and managing a highperformance knowledge-sharing network: the toyota case[END_REF][START_REF] Fawcett | Strategic commitment to price to stimulate downstream innovation in a supply chain[END_REF].

In addition to the elements cited previously and that may cause the failure of a partnership even before its formation, there is another type of barrier that seems particularly relevant to the success of supply chain alliances. Such barrier does not occur in the form of not contributing to the creation of value, but in the attempt to claim an unfair share of the value that is created [START_REF] Gilbert | Strategic commitment to price to stimulate downstream innovation in a supply chain[END_REF]. Indeed, getting the cooperating agents to agree on how to share costs or divide the benets, they jointly created, was identied as the major obstacle to collaborative structures [START_REF] Chen | Inventory centralization games with price-dependent demand and quantity discount[END_REF]. Therefore, any unfair share of the created value may give rise to defecting actors. Defection here is a general term referring to any form of non-cooperative behavior by participants in a social dilemma [START_REF] Mccarter | Happy together? insights and implications of viewing managed supply chains as a social dilemma[END_REF]. Commonly, in supply chain networks, defection is used to refer to the fact that one (or more) participant skips from his/her alliance (network) to work for his/her own or to join another existing alliance.

In social networks as in supply chain networks, cooperative game theory is used to deal with these problems. Particularly, one of the principal contribution of cooperative game theory is to provide methods that get all cooperating agents agree on how to allocate resulting costs or to share resulting benets in a way that each party would feel that acting as a coalition is worthwhile for its own sake [START_REF] Anily | The cost allocation problem for the rst order interaction joint replenishment model[END_REF].

The Challenges of Cooperation

The above questions raised by coalitional behavior and cooperative strategies may be classied into two major problems (see Figure 4.2): (1) Alliance formation, and (2) Prot/Cost allocation.

• Alliance Formation: This problem concerns the formation of alliances/coalitions by the supply chain agents. In other words, this means partitioning the set of cooperating actors into exhaustive and disjoint alliances forming the so-called coalition structure (partition).

For each coalition, an associated optimization problem should be solved. This means pooling the activities and/or resources of the agents in the coalition, and solving this joint problem. For example, in joint replenishment system, the optimal reorder policy of each coalition has to be determined.

• Prot/Cost Allocation: Once the questions of alliance formation and joint problem optimization are solved, the problem that arises is how to divide the created overall value among the cooperations actors. This means that each actor would be associated to a portion of the savings generated by his/her coalition. This problem is no less important than alliance formation, because each actor is usually interested by what he will individually get out from the cooperation. Moreover, any "unfair" allocation immediately causes the disbanding of the alliance. For these reasons, cooperative game theory-with the so-called core allocations-is used quite often to deal with payo division question. Obviously, the problems of alliance formation and prot allocation are dependent. [START_REF] Shenoy | On coalition formation: A game-theoretical approach[END_REF] emphasized that these two aspects of coalitional behavior are closely related. On the one hand, the nal allocation of payos to the players depends on the coalitions that nally form, and, on the other hand, coalitions that nally form depend on the payos available to each player in each of these coalitions. In other words, the coalition that an actor wants to join depends on the portion of savings that the actor in question would gain in each potential coalition. Thus, the payos inuence the coalition structure and vice versa.

Literature Review

The above discussions clearly emphasize the revolutionizing move from simple supply chains toward supply chain networks in which rms sometimes compete and sometimes cooperate to achieve sustainable advantages. Academic literature on supply chain management has reacted to these changes and advances by providing both analytical and theoretical supports and methodologies on the subjects of competition, cooperation and coordination in supply chain networks.

Game theory with its cooperative and non-cooperative branches has played a great potential role in the analysis and the understanding of cooperative and competitive interactions of supply chain participants. [START_REF] Nalebu | Co-opetition[END_REF] give many telling examples of competition and cooperation in business landscape.

In what follows, we give a brief description of competition and coordination in supply chain.

After that, the focus will be to give a detailed overview of the study of the cooperation in supply chain networks by means of cooperative game theory.

Buyer-Supplier Coordination

There is an impressive body of literature on buyer-supplier bilateral relationships understanding.

The goal here is to identify operational plans to align both objectives of the buyer and the supplier in order to ensure better performance and cost minimization of the chain. In this setting, coordination mechanisms may be dened as a joint policy achieved by both parties and characterized by an agreement or contract such as quantity discount, credit option, buy back/return policies, quantity exibility, commitment of purchase quantity, etc. (see [START_REF] Cachon | Supply Chain Coordination with Contracts[END_REF]; [START_REF] Sarmah | Buyer vendor coordination models in supply chain management[END_REF]). More generally, this body of literature may be characterized by the study of competitive and cooperative inventory policy in the vendor-buyer system. Many papers have appeared under this topic, including [START_REF] Bylka | Competitive and cooperative policies for the vendor-buyer system[END_REF][START_REF] Simchi-Levi | Competitive and cooperative inventory policies in a two stage supply chain[END_REF][START_REF] Graves | Competition and outsourcing with scale economies[END_REF]. We should mention that many coordination mechanisms were extended to systems with multiple retailers (see, [START_REF] Cachon | Stock wars: inventory competition in a two echelon supply chain with multiple retailers[END_REF]; Chen et al. ( 2001)). Non-cooperative game theory was quite often used to understand buyer-supplier interactions. Indeed, the buyer and the supplier inventory situations were modelled as a two-person games (competitive games) where the main solution concept is to nd an equilibrium strategy (such as Pareto, Nash, Stackelberg equilibria). Detailed surveys on this topic are found in [START_REF] Cachon | Handbook of Quantitative Supply Chain Analysis: Modeling in the eBusiness Era[END_REF] and [START_REF] Leng | Game theoretic applications in supply chain management: a review[END_REF].

Inventory Centralization Games

For a long time, cooperative game theory has not enjoyed as much attention in economics literature as non-cooperative game theory. Therefore, papers studying supply chain management by means of cooperative game theory were scarce compared to papers employing non-cooperative games. Nevertheless, since the last few years, many academics as well as practitioners have been focusing on the great potential that cooperative game theory can oer to understand several business and supply chain applications. As such, the analysis of problems in Operations Research by means of cooperative game theory is becoming one of the trends and pillars of modern supply chain management literature.

Cooperative game theory mainly focuses on the outcome of the game in terms of the value created through cooperation of many actors (players). Hence, its major contribution to supply chain management is to allow modelling of outcomes of complex business process and supply chains with centralized decisions and actions. The eect of cooperation and centralization (in terms of created value and outcomes) itself is not a new topic in supply chain management literature. For instance, inventory management centralization and multi-retailer inventory joint replenishment systems were extensively investigated since the Eighties. (see [START_REF] Eppen | Eect of centralization on expected costs in a multi-location newsboy problem[END_REF][START_REF] Chen | Eects of centralization on expected costs in a multi-location newsboy problem[END_REF][START_REF] Chakravarty | An optimal heuristic for coordinated multi-item inventory replenishment[END_REF][START_REF] Bastian | Joint replenishment in multi-item inventory systems[END_REF][START_REF] Jackson | The joint replenishment problem with a powers-of-two restriction[END_REF][START_REF] Roundy | 98% eective integer lot sizing for one warehouse multiretailer systems[END_REF]). In inventory management centralization and joint replenishment frameworks, totally centralized chains have been shown to be more ecient than decentralized ones and solutions minimizing the total systemwide costs/maximizing the total systemwide prots have been found. However in most of these papers, supply chains were assumed to belong to one actor. As a consequence, the study of the interactions and relationship between the supply chain participants as well as the question of splitting the created value, were completely omitted for long years. Under cooperative game theory settings, such situations as well as new ones are modelled distinctively, with a central concern devoted to the questions of stability and savings splitting.

Given a supply chain, the participants may keep total decentralized strategies, which means that each of them will keep his standalone situation where he will look to optimize his own system regarding his own economic parameters and objectives. Going away from decentralized strategies, the supply chain participants may adopt cooperative strategies by centralizing their decisions and operating jointly, (e.g., they may share/mutualize some physical resources such as warehouses or vehicle eet or may do some project jointly such as shipment consolidation, joint replenishment). In this case, each of them will get a portion of the achieved savings. Inventory centralization games, refers to the study of cooperative behavior questions -alliance formation and savings allocation-in such centralized supply chains. To each centralized model, a cooperative game in which the supply chain participants are the players is associated. The value of a coalition of players is the savings/value that the players have achieved jointly and would divide among themselves. Of course, the allocation of the value created should full many properties. For example the stability propriety is fullled by the so-called core allocations , i.e., allocation of the created value among the cooperating actors such that no group of actors would like to cooperate on its own.

Recently, many inventory centralization games have been studied in various multi-retailer inventory systems. Some papers are reviewed in [START_REF] Cachon | Handbook of Quantitative Supply Chain Analysis: Modeling in the eBusiness Era[END_REF][START_REF] Leng | Game theoretic applications in supply chain management: a review[END_REF]. [START_REF] Nagarajan | Game-theoretic analysis of cooperation among supply chain agents: Review and extensions[END_REF] The core

Newsvendor Games

The newsvendor problem refers to a situation where a store (newsvendor) is facing a random demand (of newspapers) by ordering an amount of newspapers at the beginning of each day (period). Given their nature, the newspapers can be sold only in the day when they are ordered.

Then, at the end of the day (period) the non-sold newspapers are lost or discounted. We refer to [START_REF] Khouja | The single-period (news-vendor) problem: literature review and suggestions for future research[END_REF] for a detailed review of newsvendor models.

Newsvendor games are concerned with situations involving multiple newsvendors who make joint orders to satisfy the total demand they are faced with. The achieved savings is then allocated in a way that is advantageous to all the newsvendors. Probably, [START_REF] Wang | A three-person game theory model arising in stochastic inventory control theory[END_REF] is the rst investigation in this area. [START_REF] Wang | A three-person game theory model arising in stochastic inventory control theory[END_REF] studied a three-player newsvendor game in both cooperative and non-cooperative settings. Later, [START_REF] Hartman | Cores of inventory centralization games[END_REF] studied a multi-retailers cooperative game, each of them facing a newsvendor problem. They conditioned the non-emptiness of the core of the game by some assumptions on the demand distribution.

This result was generalized by [START_REF] Muller | The newsvendor game has a non-empty core[END_REF] who showed that whatever the demand distribution, the cores of newsvendor games are non-empty. [START_REF] Ozen | Cooperation between multiple newsvendors with warehouses[END_REF] consider multiplenewsvendors game with multiple warehouses with the assumptions that the ordered amounts of goods become available after a non-null lead time. The authors showed that the retailers can increase their expected joint prots by coordinating their orders and making allocations after the demand realization. They also proved that the associated game has a non-empty core.

A similar model was developed with the assumption that reallocation of inventories happens after a demand signal observation [START_REF] Ozen | A multi-retailer decentralized distribution system with updated demand information[END_REF]. The signal updates the information about the demand distribution. The authors discussed the impact of two classic contracting mechanisms (the wholesale price contract and the buy-back contract) in three dierent scenarios; non-cooperating retailers, cooperating retailers, and manufactures resale of the returned items. [START_REF] Slikker | Cooperation between multiple news-vendors with transshipments[END_REF] studied the cooperation between multiple newsvendors, with the inclusion of non-identical selling and purchasing prices and with transshipment. The main result of this study is that the cooperative newsvendor games with transshipment have a non empty core.

The transshipment was considered later in another game [START_REF] Huang | Inventory sharing in a repeated newsvendor game[END_REF]. [START_REF] Hartman | Optimizing centralized inventory operations in a cooperative game theory setting[END_REF] have focused on prot sharing mechanisms. They studied a cooperative game between several retailers with normally distributed and correlated individual demand. They showed that when holding and penalty shortage costs are identical for all subsets of stores, a game based on optimal expected costs (or the corresponding benets) is subadditive and for normally distributed demands, whatever the correlations the core is never empty. When the stores' holding and penalty costs dier, the corresponding game may have an empty core. A similar result was given by [START_REF] Hartman | Allocations of gains from inventory centralization in newsvendor environments[END_REF], who show that multiple newsvendors cooperative games with non-identical holding and penalty costs may have an empty core.

Economic Lot Sizing Games

The economic lot-sizing model is one of the well-known model in inventory theory. It consists of facing a demand for an identical (possibly dierent) product during each of a consecutive time period. The demand in a given time period can be fullled by orders in that period or at previous periods. The objective is to decide the order quantity (lot) at each time period to satisfy the total demand at a minimum total cost [START_REF] Heuvel | The economic lot-sizing problem: New results and extensions[END_REF]. Detailed survey on lot-sizing models are found in [START_REF] Heuvel | The economic lot-sizing problem: New results and extensions[END_REF][START_REF] Jans | Modeling industrial lot sizing problems: A review[END_REF][START_REF] Drexl | Lot sizing and scheduling -survey and extensions[END_REF][START_REF] Ben-Daya | The joint economic lot sizing problem: Review and extensions[END_REF]. Now, consider a situation where several retailers are operating in lot-sizing environment. In the decentralized case, each retailer would solve a classic economic lot-sizing problem to determine his optimal ordering policy. In the centralized case, the retailers may reduce their ordering cost by making joint orders. Under cooperative game theory setting, this situation is called economic lot-sizing game (ELS game). The standard form of this game was studied by [START_REF] Heuvel | Economic lot-sizing games[END_REF]. The authors consider a set of retailers selling the same item purchased at the same supplier. The demand of the items is known over a multi-period horizon time. When an order is placed the manufacturer charges ordering cost and production cost which is linear in the amount of the ordered items. In addition to these costs, retailers are supposed to carry inventory holding cost whenever an amount of item is kept in stock from one period to another. [START_REF] Heuvel | Economic lot-sizing games[END_REF] showed that it is always protable for a collective of retailers to cooperate. It means that making joint orders leads to some savings. When dealing with the problem of savings sharing, [START_REF] Heuvel | Economic lot-sizing games[END_REF] show that the ELS game have a nonempty core. [START_REF] Chen | Duality approaches to economic lot-sizing games[END_REF] consider a cooperative game between multiple retailers that are facing an economic lot-sizing problem with general concave ordering cost (the ordering cost is supposed to be a concave function of the order quantity). When they cooperate, the retailers form a coalition and place joint orders to a single supplier in order to reduce ordering cost. The demand of a given period can be backlogged and fullled by orders at later periods. The unfullled demand incurs penalty cost to the retailer. [START_REF] Chen | Duality approaches to economic lot-sizing games[END_REF] showed that the core of the ELS game with backlogging costs is nonempty. Moreover, using a method based on linear programming duality, a core allocation may be computed in polynomial time.

Inventory Games

The class of inventory games refers to inventory cooperative situations, like those described above with the distinctiveness of considering continuous time model assumptions. The Economic Order Quantity (EQO) is quite often used as a reorder policy in this class of inventory centralization games. The EQO model has a great use and inuence in the production and inventory literature.

Its root goes back to [START_REF] Harris | How many parts to make at once[END_REF] and its basic form concerns inventory situations with innite time horizon and constant demand rate [START_REF] Heuvel | The economic lot-sizing problem: New results and extensions[END_REF]. [START_REF] Tijs | Benet sharing in holding situations[END_REF] studied the so-called holding game where a collective of retailers may cooperate by sharing a storage capacity for their inventories. In other word, this holding game involves many agents; one of them has a capacitated storage facility. Available goods of other agents can be partially stored in the facility generating certain benet. The main addressed questions were to nd an optimal holding plan and to distribute the achieved benet. [START_REF] Meca | P-additive games[END_REF] consider a replenishment function based on the economic production quantity (EPQ) model where the ordered arrives gradually.

In addition to joint their orders, the retailers share holding facilities. This means that the rms make their orders jointly and store their items in the cheapest warehouse. The authors proved that this game called inventory-production game is totally balanced and then has a nonempty core. [START_REF] Guardiola | Production-inventory games: a new class of totally balanced combinatorial optimization games[END_REF] of retailers. This inventory centralization is called inventory game. [START_REF] Meca | Inventory games[END_REF] focus on allocating the joint prots among the dierent retailers. They show that the game has a nonempty core and they prove that proportional allocating rules belong to core. [START_REF] Dror | Shipment consolidation: Who pays for it and how much?[END_REF] extend the model studied by [START_REF] Meca | Inventory games[END_REF]; in their cost structure, a major setup cost is incurred for each order, which is independent of the set of retailers that places the order. In addition, a minor setup cost is incurred for each retailer that is included in the joint order. The authors focus on characterizing a necessary and sucient condition, which is a threshold value for the shared ordering cost, under which it is optimal for all the retailers to order together and to have a non-empty core for the game. [START_REF] Anily | The cost allocation problem for the rst order interaction joint replenishment model[END_REF] study the same model as [START_REF] Dror | Shipment consolidation: Who pays for it and how much?[END_REF] but their focus is mainly on studying a class of easy to implement policies, called power-of-two policies. They show that under the optimal power-of-two policy, the cooperative game associated with the joint replenishment model with rst-order interaction is concave and thus has a non-empty core. [START_REF] Zhang | Cost allocation for joint replenishment models[END_REF] extend the model of [START_REF] Anily | The cost allocation problem for the rst order interaction joint replenishment model[END_REF] to a more general game. He studied a cooperative game associated with the joint replenishment model where the joint setup cost is a submodular function of the set of retailers that places the order together. Like in [START_REF] Anily | The cost allocation problem for the rst order interaction joint replenishment model[END_REF], the game is dened under an optimal power-of-two policy. [START_REF] Zhang | Cost allocation for joint replenishment models[END_REF] used the strong duality theorem to prove that the game has a non empty core.

In the afore mentioned references, cooperative games only involve the set of rms/retailers in the system. The other supply chain parties such as suppliers are not formally included in the cooperative game. In the literature, we have identied only one paper, [START_REF] Guardiola | Cooperation and prot allocation in distribution chains[END_REF],

where the supplier is explicitly taking part of the cooperation. [START_REF] Guardiola | Cooperation and prot allocation in distribution chains[END_REF] studied the coordination of actions and the allocation of prots in a supply chain where the supplier oers wholesale prices to induce the retailers to make large orders. Two kinds of cooperation situations are compared: in the rst one, the supplier is not considered as a cooperating agent, while in the second situation, the supplier may cooperate with the retailers. The authors showed that it is preferable to include the supplier as a player in the cooperative game. They demonstrated that the prot in this case is higher than an exclusive retailers cooperation situation.

Inventory Games with Coalition Structures

Alliance formation topic and games with coalition structures have received very little attention in supply chain management literature. Papers employing cooperative game theory to study the formations and the interactions of alliances in supply chains are scarce as well: there are maybe ten or so of these. To the best of knowledge, no paper uses the coalition structure core to analyze a game with coalition structure in supply chain management research area. However, there have been quite a few papers that have analyzed farsighted satiability of coalition structures in some supply chain games. This includes, [START_REF] Granot | Competition and cooperation in decentralized push and pull assembly systems[END_REF]; [START_REF] Tucker | Formation of alliances in internet-based supply exchanges[END_REF]; Nagarajan and [START_REF] Nagarajan | Stable farsighted coalitions in competitive markets[END_REF]So²i¢ ( , 2009) ) and Nagarajan et al. (2009). Most of these references deal with coalition stability in assembly models excepting Nagarajan et al. (2009) who deal with group buying organizations' stability. [START_REF] Tucker | Formation of alliances in internet-based supply exchanges[END_REF] are probably the rst authors to deal with farsighted stability in supply chain management literature. They mainly focus on what coalition structures are the farsighted stable outcomes in a three-retailers cooperative game. [START_REF] Granot | Competition and cooperation in decentralized push and pull assembly systems[END_REF] analyze two contracting systems between an assembler and his suppliers. The push system allows the suppliers to set price rst and the assembler orders second. Despite the push system, in the pull system the assembler oers price to each supplier rst, and suppliers then determine quantity. The grand coalition is shown to be the farsighted coalition structure in the push system, while under the pull system, any coalition structure can be farsighted stable. Also, in assembly supply chain, Nagarajan and So²i¢ (2009) consider an assembler who purchases n components from n suppliers to build and sell the nal product. First, the authors consider the same cases as [START_REF] Granot | Competition and cooperation in decentralized push and pull assembly systems[END_REF]; in one case the suppliers are the Stackelberg leaders and in the second case, the assembler is the Stackelberg leader. Moreover, they consider the case where the assembler and the suppliers make decisions simultaneously. In this case, the authors characterize the farsighted coalition structures formed by the suppliers. [START_REF] Nagarajan | Stable farsighted coalitions in competitive markets[END_REF] 4.4 Supply Chain Games: Literature Analysis and Problem Setting

In this section, we discuss some non-covered issues in supply chain games literature and give brief description of our formal models, and outpoint our contributions to this literature.

Lack of Prior Attention

Analyzing the cooperation in supply chain networks by means of cooperative game theory is a rather new stream of research in supply chain management. As such, several questions were not well investigated or are not covered yet. On analyzing the afore cited references, one can easily conclude that most of early studies seem to be only interested in the stability of one set of agents. For instance, early works (see Figure (4.4)) supposed that the games are superadditive in the sense that it is benecial for all supply chain agents to cooperate together. Therefore, the non-emptiness of the core and the distribution of the savings available to the grand coalition to individuals appear as the most investigated questions. The questions of core's non-emptiness and games' superadditivity are interesting questions from a theoretical point of view. We should mention that superadditive games were deeply studied, even in the theory of games itself, because they have nice theoretical properties. Nevertheless, we think that theses issues are not sucient to model the cooperation in supply chain networks. Deeper and more detailed analysis are required to understand the interactions of rms in supply chain networks.

Decentralized system

Minimize/Maximize the total systemwide costs /profits In many situations, it is not sucient to declare that the game admits a non-empty core but we need to identify one such core allocation. And even a core allocation is found it is not sucient to declare that the supply chain participants will use such allocation. Because, core allocations only guarantee the immunity to group deviations (stability). However, there might be some core allocations which are costly or complicated to put into practice (for example they require a Third Party to manage the money's transfer between the partners). Moreover, core allocations often do not take into account the comparison between the payos attributed to each actor, and do not guarantee that the actors who contribute more to the alliance they belong to are paid more. In these situations, it is easy to expect the disbanding of such alliance. We believe that the above questions among many others should be well investigated in supply chain networks where cooperation do not means rms' rivalry elimination.

Above we warned that most of the studied supply chain cooperative games are superadditive.

In what follows, we will explain how this assumption is restrictive in supply chain models. In supply chain networks, as well as in general social networks, many situations are not superadditive by nature. And, in the absence of superadditivity, forming the grand coalition is not necessarily ecient, because a higher aggregate payo can be obtained from a dierent coalition structure.

Besides, the superadditivity itself can be called into question. There are many reasons that raise doubts concerning the formation of the grand coalition. For instance, as explained by Aumann and [START_REF] Aumann | Cooperative games with coalition structures[END_REF], "acting together may be dicult, costly or illegal, or the players may for various personal reasons not to do so". To form and to manage an alliance there might be some relevant costs of formation/management process that include for example, coordination overhead like communication costs and Third Logistic Party costs (when such party is used). Alliance formation/management cost process had not been considered in early cooperative games, however we believe that such cost component actually has a relevant importance in practice.

When considering this cost the grand coalition may appear interesting with regards to a smaller coalition. Moreover, in many cases acting together is dicult even impossible for practical reasons (as the geographic locations of the supply chain members) or because of some constraints in the supply chain. For example, in early inventory games, the supplier (or the external warehouse) is supposed to have an innite production capacity thus he can full the large quantities ordered by the grand coalition. However, as one can expect this assumption is quite far from real economic situations. Finally, the grand coalition may fail to be formed because of rms' rivalry and competition: There might be some "competitors" who do not wish to cooperate with each other, even if it is benecial for them to do so.

Before ending this section, we would like to emphasize that in addition to the focus on the core and superadditivity, most of early supply chain cooperative games are dealing with the cooperation in exclusive inventory-cost models. We nd it quite important to involve transportation decisions in supply chain cooperative models. Indeed, transportation costs may be as important as inventory costs, and including such costs would allow modelling more real-life situations and would put the accent on modern supply chain trends, such as green supply chains (for example through the consideration of greenhouse gas emissions).

Problem Setting

This Ph.D thesis contributes to the emerging literature on the analysis of issues in Management

Science by means of cooperative game theory. Our motivation is twofold. First, our interest to study the cooperation in supply chain was stimulated by the increasing appeal of alliance formation in current logistic networks. In such complex and dynamic networks, the coordination of actions and cooperative behaviors are becoming key strategies to win new business and to face the global trade changes. Second, alliance formation and payo allocation problems are becoming imperative optimization topics for both academics and practitioners. However, this research area is a rather new stream in supply chain management research and many non-covered topics still exist. In this Ph.D thesis, we hope providing answers to some non-covered questions and outpoint some new challenges.

Superadditive Games

Grand chain. We call this game the full-truck joint replenishment game. We show that this superadditive game has a non-empty core. We then identify a particular core allocation and discuss its main properties comparing to that of Shapley value. In the end of this chapter, we discuss the issue of imposing some constraints that hinder the formation of the grand coalition, and discuss the arising problem. In Chapter 6, we studied a non-superaddtive joint replenishment game. We begin our discussions by emphasizing that generating the coalition structure that optimizes the whole supply chain (full-cooperative coalition structure) is not a viable objective in our considered "independent" rms. After that we focuss on giving a procedure that generates a more appropriate coalition structure which we call ecient coalition structure. Such ecient partition is then showed to satisfy a set of desirable stability properties. Finally, in chapter 7, we extend the procedure presented in chapter 6 to inventory games with general cost functions.

We mainly present a new formal representation of the ecient coalition structure generation procedure. In this representation, the questions of alliance formation and prot allocation are treated simultaneously. The general results of this chapter are then applied in a non-superadditive full truckload joint replenishment game.

To conclude, our main contributions in these models are as follows:

(1) We focus on transportation decisions by studying the cooperation in a context of inventory systems with full truckload shipments.

(2) We push the discussion on payo division so far exceeding the notions of stability to discuss the issues of giving a higher importance to the gap of the allocated value to agents within the same alliance.

(3) We give much attention to study non-superadditive games.

In these games, we give the question of alliance formation as much attention as the question of payo division and try to present approaches that treat both questions simultaneously.

Conclusion

This chapter was devoted to understand the phenomenon of cooperation in supply chain networks.

We begun by emphasizing the network character of supply chains and stressing the great potential of alliance building as a key of competitiveness. Then, we provided a detailed comprehension of the cooperation in supply chains. After that, we reviewed and classied the emerging literature on the analysis of the cooperation in supply chain by means of cooperative game theory. Finally, we emphasized some non-covered issues in this literature, motivated our work and highlighted our contributions. The retailers may follow a total decentralized strategy, which means that each of them will try to optimize his/her own system regarding his/her own economic parameters and objectives.

Going away from the decentralized strategy, the retailers may adopt a cooperative strategy. In this case, signicant savings can be achieved by coordinating shipment decisions across them.

The focus of the paper is to identify the optimal cooperative conguration and to nd a fair way of sharing the savings resulting from the cooperation among the retailers. In the remainder of the paper, a coalition or an alliance refers to a set of retailers that agree to make joint orders.

The partition formed by these separate alliances is called coalition structure. The set grouping all retailers is called the grand coalition. Single coalition or stand-alone coalition refers to retailer acting individually.

The motivation of this work is twofold. First, our interest to study the cooperation in supply chain was stimulated by the increasing appeal of alliance formation in current logistic networks.

In such complex and dynamic networks, the coordination and cooperation are becoming imperative optimization topics. Second, the full truckload mode is becoming the most common mode of transportation used in industry applications. The use of such transportation mode integrates climate change and global warning considerations through the reduction of greenhouse gas emissions, as well as reducing considerably the logistics costs. Thus, combining both problems, by studying the cooperation in a context of inventory systems with full truckload shipments appears as a good participation and contribution for analyzing current logistic networks and enhancing their performance.

To achieve this goal, we mainly use cooperative game theory. We associate to the above described distribution chain a cooperative game in which the dierent retailers are the players. The value of a coalition of players equals the optimal joint prot they can achieve. We refer to this game as the full truckload joint replenishment game, hereafter FTLJR-game. We show that this game is superadditive, that is, every set of disjoint coalitions increases their savings

when they merge into one coalition. Consequentially, the grand coalition is the most optimal cooperative conguration. To examine the question of prots distribution, we focus on the core [START_REF] Gillies | Solutions to General Non-zero Sum Games[END_REF] and Shapley value (Shapley, 1953b), two of the most central solution concepts in cooperative game theory. We show that the core of FTLJR-game is never empty, which implies that all retailers in the chain are willing to cooperate because there exist stable distributions of the total prot among the retailers upon which no coalition can improve. The stability in the sense of the core means that no group of retailers would have the incentive to leave the grand coalition and form a smaller coalition because they collectively receive at least as much as they could obtain for themselves as a coalition. Further, we introduce a specic allocation of the profits, the so-called holding-cost based solution (HCB-solution). This solution is stable, that is, it always belongs to the core of the game, and it possesses several nice properties. In particular, it is a simple and practical solution under which no explicit transfer of savings between the retailers is used: The prot portion attributed to each retailer equals to its holding cost savings. After that, we turn our attention to study the properties of Shapley value. We show that Shapley value may lie outside the core of FTLJR-game, and we give some conditions under which it is a core stable allocation. Even though it may non-stable in the sense of the core, Shapley value is always farsighted stable.

Finally, a comparison between the HCB-solution and Shapley value is provided. The comparison involves four criteria: stability, computational complexity, fairness and practical setting.

In term of stability, each of the two solutions guarantees one stability concept; HCB-solution is core stable while Shapley value is farsighted stable. However, computing Shapley value is much more time consuming than computing HCB-solution. Before discussing whether Shapley value or HCB-solution is fair, we should make clear the meaning of fairness. Fairness is often confused with stability in cooperative games. In this case, the meaning is dierent; a fair allocation implies that each participant is satised with his/her allocated prot portion according to his/her contribution and/or to his/her partners' earnings. In this particular sense, Shapley value may be considered as one of the most fair solution concept in game theory. It distributes the rewards according to participants' marginal contribution. Thus, those who contribute more are paid more. We show through a counterexample that HCB-solution may fail to guarantee such propriety. From a practical point of view, the establishment of Shapley value is less convenient as, it requires a third party to manage the system, while HCB-solution does not.

The contents of this chapter are as follows. In section 5.2 we study the model and introduce the game. In section 5.3, we address the core stability of the grand coalition and study the properties of Shapley value. Moreover, we compare Shapley value to the proposed core allocation.

In section 5.4, in order to motivate the work in the rest of this dissertation, we analyze the case where the formation of the grand coalition can be constrained. We conclude by summarizing the main insights of our results and discuss some extensions in section 5.5.

Model Description and Notations

We consider alliance formation and cost allocation problems in an innite-time-horizon onesupplier n retailers joint replenishment model. Each retailer i is associated to an item characterized by a volume (or a weight) denoted by V i . We should note that the dierent items are assumed to be compatible to be delivered jointly. The demand rate, D i , of retailer i is supposed to be a deterministic and has a constant rate. The cost of holding one unit of product per unit of time at this retailer location is h i . For simplication, we let

H i = h i .D i 2
be the holding cost parameter of retailer i. We assume identical and constant lead times, and without loss of generality, are equal to zero. The inventory replenishment is made only by full truckload shipments.

A xed ordering cost A is charged for each full truckload delivery. As mentioned in Figure 5.1, we deal with a joint replenishment system. So a group of retailers may form an alliance or a coalition S, by joining their orders as a single large order. Similarly to the case where a retailer is ordering alone, the group of retailers can only order for full truckload delivery. Let the common ordering cycle time be denoted by T S . The corresponding frequency is denoted by N S . All notations and parameters are summarized below:

• N = {1, ..., n}: The set of retailers.

• D i : The deterministic demand of retailer i ∈ N .

• h i : The holding cost per time unit of retailer i ∈ N .

• H i = h i .D i 2 :
The holding cost parameter of retailer i ∈ N .

• V i : The volume/ weight of product i associated to retailer i ∈ N .

• A: The xed ordering cost.

• CAP: The vehicle capacity.

• Q i : The order size of retailer i ∈ N .

• T i : The ordering cycle time of retailer i ∈ N .

• N i : The ordering frequency of retailer i ∈ N .

• C(i): The average total cost per time unit of retailer i ∈ N .

• T S : The ordering cycle time of coalition S, ∅ ⊂ S ⊆ N .

• N S : The ordering frequency of coalition S, ∅ ⊂ S ⊆ N .

• C(S): The average total cost per time unit of coalition S, ∅ ⊂ S ⊆ N .

When ordering alone, the optimal replenishment strategy under full truckload shipments considerations for a retailer i is to order a full truck corresponding to the quantity

Q i = CAP V i every T i = Q i D i = CAP V i .D i unit of time.
In other terms, the optimal replenishment policy for a retailer i is to order a full truck with a frequency of N i = V i .D i CAP . The total average cost corresponding to such replenishment strategy is composed by two cost components. The rst one is related to the ordering cost occurred each time an order is made and is equal to A.N i . The second cost component corresponds to the holding cost (h i .Q i /2). As a result, the total average cost equals

C(i) = A.N i + h i .Q i 2 . Since N i = D i Q i , rewriting C(i)
as a function of the frequency N i gives :

C(i) = A.N i + H i N i , and N i = V i .D i CAP .∀i ∈ {1, ..., n}.
(5.1)

Above, we have determined the optimal replenishment policy for any retailer operating as a single-coalition (standalone situation). Hereafter, we focus on the case where a group of retailers cooperate by joining their orders. Consider a non-empty coalition of retailers S ⊆ N , if the retailers in S cooperate they will make their orders at the same time, thus they will have the same cycle time and the same ordering frequency respectively denoted by T S and N S . In coalition S each retailer i is ordering the quantity Q i,S = D i N S . Since we suppose that only full truck orders are authorized and no shortage is allowed, the total quantity delivered to coalition S equals the truck capacity CAP , i.e., i∈S D i .V i N S = CAP . This means that the common ordering frequency is the sum of the standalone ordering frequencies i.e.,

N S = i∈S D i .V i CAP = i∈S N i , ∅ ⊂ S ⊆ N (5.2)
Hence, coalition S charges (A.N S ) ordering cost. The delivered products are stored in local warehouses where every retailer supports his/her own holding cost, the holding cost charged by the coalition is the sum of the individual holding costs. As a result, the average total cost for an alliance S, C(S), is given by

C(S) = A.N S + P i∈S h i .Q i,S 2
. Expressing the order size Q i,S as a function of N S leads to :

Q i,S = D i N S .
The total average cost of coalition S is expressed as follows:

C(S) = A.N S + H S N S = A. i∈S N i + i∈S H i i∈S N i , ∅ ⊂ S ⊆ N (5.3)
The saving or the worth of this coalition corresponds to the cost reduction between the standalone situation and the cooperative situation, i.e:

v(S) = i∈S C(i) -C(S) = i∈S H i N i -i∈S H i i∈S N i , ∅ ⊂ S ⊆ N (5.4)
In the rest of the paper we will consider the savings full truckload joint replenishment game (FTLJR-game), that will be denoted by (N, v). Where N denotes the set of retailers in the distribution chain. v refers to the corresponding saving function; it assigns to each coalition its corresponding worth:

v : Ω → R such that v(S) = i∈S H i N i - P i∈S H i P i∈S N i and v(∅) = 0.
We should note that v(i) = 0 forall i ∈ N , this expresses the fact the standalone situation is our reference situation.

Proposition 5.1 Any coalition is protable, i.e, v(S) ≥ 0 or C(S) ≤ i∈S C(i), ∀S ⊆ N .

Proof: LetS be a non-empty coalition. As showed in equation ( 5.3): Proof: Let S and T two disjoint and non-empty coalitions:

C(S) = A. i∈S N i + P i∈S H i P i∈S N i ≤ A. i∈S N i + i∈S H i N i = i∈S C(i).
C(S) + C(T ) = A.( i∈S N i + i∈T N i ) + P i∈S H i P i∈S N i + P i∈T H i P i∈T N i ≥ A.( i∈S N i + i∈S N i ) + P i∈S H i + P i∈T H i P i∈S N i + P i∈T N i = A.( i∈S∪T N i + P i∈S∪T H i P i∈S∪T N i = C(S ∪ T ).
FTLJR-game is superadditive. Consequentially, the grand coalition is the most protable coalition structure for the whole system. This has the following interpretation: the total prot under full cooperation (grand coalition) is larger than the prot of any other coalition structure (the prot of a coalition structure is the sum of the prots of the coalitions forming it). In what follows, the focus will be on the problem of rewards distribution. The proposal is to identify, whether there exist, stable allocations of the total prot among the retailers. Stability here refers to stability in the sense of the core or in the farsighted sense.

Grand Coalition stability

Core Stability

When a group of retailers decides to cooperate, they will order jointly. As mentioned in equation (7.9), due to the full truckload shipment considerations, the common frequency of a coalition S equals the sum of the single-coalitions frequency of the member of coalition S. As a result, the total ordering cost is unchanged: A.N S = A. i∈S N i . However, the total holding cost is reduced to (

P i∈S H i P i∈S N i ) while it was ( i∈S H i N i ).
Consequentially, the full truckload joint replenishment leads to reduce the holding costs; while in classic joint replenishment games, the savings are often induced by the reduction of the ordering costs (or set up costs).

Hence, intuitively, one would like to allocate the joint costs in a way that each retailer supports the same ordering cost he/she supports when ordering alone, plus the holding cost occurred in the cooperative situation. Thus, a retailer i member of coalition S, ∅ ⊂ S ⊆ N will pay A.N i + H i P j∈S N j while he/she was paying C(i) = A.N i + H i N i . As a result, retailer i's savings will be :

X(i) = H i N i -H i P j∈S N j .
This prot allocation will refer to us the Holding Cost Based solution (HCB-solution).

Theorem 5.1 The HCB-solution, X = (X 1 , ..., X n ) ∈ R n , that assigns to each retailer i in coalition S, ∅ ⊂ S ⊆ N , the sum of his/her single-coalition ordering cost and his/her cooperative holding cost is a core allocation. X ∈ Co(N, v)

Proof: Forall i ∈ N, X(i) = H i N i - H i P j∈N N j = H i N i -H i N N , HCB-solution satises the following axioms: i) Individual rationality: ∀i ∈ N , N N ≥ N i , then: X i = H i N i -H i N N ≥ 0 = v(i) ii) Eciency: X(N ) = i∈N X i = i∈N ( H i N i -H i N N ) = i∈N H i N i - P i∈N H i N N = v(N )
iii) Collective rationality (Core stability):

∀∅ ⊂ S ⊆ N, X(S) = i∈S X i = i∈S H i N i - P i∈S H i N N ≥ i∈S H i N i - P i∈S H i N S = v(S) (Because N S = i∈S N i ≤ N N = i∈N N i ).

Shapley value

In this section, our aim is to study the properties of Shapley value as a reward distribution solution in the FTLJR-game.

Theorem 5.2 : , v), it guarantees the individual rationality.

• (i) Shapley value is an imputation: Sh(N, v) ∈ I(N
• (ii) Shapley value does not guarantee the stability in the sense of core.

Proof:

• (i)
The superadditivity of the game showed in proposition (5.2) implies that (v(S)-

v(S \ {i})) > v(i) = 0 for all i ∈ S ⊆ N .
Rewriting the Shapley Value of retailer i leads to:

Sh(N, v)(i) = S⊆N :i∈S (|S| -1)!(|N | -|S|)! |N |! (v(S) -v(S \ {i})) ≥ v(i). S⊆N :i∈S (|S| -1)!(|N | -|S|)! |N |! = 0
• (ii) To prove that Shapley value is out of the core, we use the following example. We consider a system of three retailers. Their corresponding parameters, costs and Shapley values are reported in Table 6.1. In Table 6.2, to each non-single coalition, we associate its value and corresponding Shapley value. Since v({1, 2}) ≥ Sh(N, v)({1, 2}), it is better for retailers 1 and 2 to deviate from the grand coalition {1, 2, 3} and work for their own by forming coalition {1, 2}. Hence, Shapley value does not guarantee the core-stability of coalition {1, 2, 3}. Above, we showed that the Shapley value may lie outside the core. However it may be in the core under some assumptions. For instance, when all holding costs and volumes are equal, Shapley value is a core allocation.

Theorem 5.3 If for all i ∈ N, H i = H and

V i = V then Sh(N, v) ∈ Co(N, v).
Proof: For any non-empty coalition,

S ⊆ N , v(S) = ( k∈S h k .D k 2.N k - P k∈S h k .D k 2 P k∈S N k ) and N k = D k .V k CAP .
If we assume that all holding costs and products volumes are equal, i.e, ∀k ∈ N,

h k = h and V k = V , the worth of coalition S, v(S) is simplied to: v(S) = h.CAP 2.V .(|S| -1). Hence, ∀i ∈ N and ∀S ⊆ N, v(S) -v(S \ {i}) = h.CAP 2.V .
Rewriting the Shapley Value of any retailer i leads to:

Sh(N, v)(i) = h.CAP 2.V . S⊆N :i∈S (|S| -1)!(|N | -|S|)! |N |! (5.5)
For |S| = 1, there is only one coalition containing retailer i, in this case

(|S|-1)!(|N |-|S|)! |N |! = 0.
For |S| = 2, ..., |N |, there exists (

|S|-1

|N |-1 ) coalitions with cardinality |S| that contain retailer i. Equation (5.5) may be rewritten as;

Sh(N, v)(i) = h.CAP 2.V . |N | |S|=2 (|S| -1)!(|N | -|S|)! |N |! .( |S|-1 |N |-1 ) = h.CAP 2.V . |N | |S|=2 (|S| -1)!(|N | -|S|)! |N |! . (|N | -1)! (|S| -1)!(|N | -|S|)! = h.CAP 2.V . |N | |S|=2 (|N | -1)! |N |! = h.CAP 2.V . |N | |S|=2 1 |N | = h.CAP 2.V (|N | -1) |N | ≥ v(i) = 0
Above we showed that Shapley value is an imputation, to prove that Shapley value belongs to the core of the game (N, v) reduces to prove that it satises the collective rationality property, that is we have to show that for every non-empty coalition S ⊆ N , Sh(N, v)(S) ≥ v(S).

For any non-empty coalition S ⊆ N We have,

Sh(N, v)(S) = i∈S Sh(N, v)(i) = i∈S h.CAP 2.V (|N | -1) |N | = h.CAP 2.V (|N | -1) |N | .|S| Since |N | ≥ |S| we have (|N |-1) |N | ≥ (|S|-1)
|S| , as result;

Sh(N, v)(S) = h.CAP 2.V (|N | -1) |N | .|S| ≥ h.CAP 2.V (|S| -1) |S| .|S| = h.CAP 2.V (|S| -1) = v(S).
Above we showed that Shapley value may not guarantee the core stability. However, Shapley value is always a farsighted stable imputation.

Theorem 5.4 : Sh(N, v) guarantee the farsighted stability of the grand coalition N .

Proof: The proof of this theorem arises immediately from the results of [START_REF] Béal | Farsighted coalitional stability in tu-games[END_REF]. The authors show that for all superadditive games (N, v), Shapley value is core stable or farsighted stable. Above we showed that Shapley value may lie outside the core, which proves the theorem.

Comparison

In this section, we aim at addressing the main advantages and weaknesses of HCB-solution and Shapley value.

We proved that HCB-solution, assigning to each retailer the sum of his/her single-coalition ordering cost and his/her cooperative holding cost, is a core allocation. In addition of satisfying the stability of the grand coalition, this allocation has the merit to be a practical and simple allocation. In fact, the worth of each cooperating retailer equals the gap in holding cost between the stand-alone situation and the cooperative situation. Hence, there will be no explicit money transfer between the cooperating retailers. And there will be no need to have a third party to manage the rewards distribution.

The portion of the prot of each retailer is function of his/her holding cost. However, the holding parameter of each retailer may be kept as private information. Only ordering frequencies are necessary for the cooperation. As a result, the savings of each retailer may be private information. This observation has the following interesting interpretation: It means that HCBsolution does not alter the "competition" and "rivalry" between the retailers. As such, in the one hand, each retailer may keep his savings as private information. In the other hand, he/she may enhance his/her savings on improving his/her own holding parameters.

After presenting some merits of HCB-solution, in what follows, we discuss its drawbacks and limitations. Even it though guarantees the core stability, there are some situations where the proposed core allocation lead to some "unfairness". For instance, when the ordering cost is important, the savings of the retailer having the highest ordering frequency would be not important enough compared to that of his/her partners. The same problem happens when the retailer having the highest ordering frequency has the lowest holding cost and the retailers having much lower ordering frequency have much higher holding cost. In both situations, retailer having the highest ordering frequency contributes more to the advantage of the other retailers then to his/her own advantage. For a better comprehension of these insights, we address below an example. Let us consider three retailers forming the alliance denoted by N = {1, 2, 3}. The retailers' parameters and standalone costs are reported in It is obvious that the grand coalition {1,2,3} is stable in the sense of the core. In fact no subcoalition will have the intention to defect from alliance {1,2,3} otherwise it will get less savings.

For instance, v({1, 2}) = 46.42 < X({1, 2}) = 48.33, v({1, 3}) = 94.23 < X({1, 3}) = 98.33 and v({2, 3}) = 83.33 < X({2, 3}) = 136.66.

The holding cost allocated to each retailer is proportional to the common ordering frequency

N {1,2,3} = N 1 + N 2 + N 3 .
Hence, retailers 2 and 3 benet from the large ordering frequency of retailer 1. As a result, retailer 3 having the lowest ordering frequency and the highest holding cost has the biggest prot: he/she gets a prot ratio of 77.9%, while retailer 1 having the largest ordering frequency only gets a prot ratio of 1.86%. Hence, it is easy to conclude that retailer 1 contributes to the advantage of retailers 2 and 3 more than to his/her own advantage. This may be possibly interpreted as an unfairness. Retailer 1 may cause the disbanding of coalition {1,2,3} because his/her savings would not seem important enough to cover the cooperation setting eort and investment. Moreover, in practice, a retailer taking part in a cooperation is not only interested in his/her own prot, but he/she is always interested in his/her prot regarding the prots of his/her partners. For this reason, when there is a huge gap between the prots of retailers forming an alliance, a retailer may be nonrational and can give up his/her negligible prot to deprive his/her partners ("rival/compititor") to have a more important prot:

the stability of the alliance is no longer guaranteed even if the prots are allocated by respect to game theory rules.

To avoid the above described limitation, one would think to look for allocations having the following propriety: those who contribute more to the groups that include them should be paid more. Shapley value (Shapley, 1953b) is usually viewed as a good normative answer to that question. Its major contribution is to distribute the rewards by respect to the contribution of each retailer. Hence, the prot portion attributed to each retailer depends on his/her contribution. In this sense, Shapley value is fairer than HCB-solution. To illustrate this statement let us consider the same example described in We should note that retailer 1 cannot be paid more because when increasing the total ordering frequency (which is benecial for retailers 2 and 3), retailer 1 is also increasing the total cost. Shapley value is one of the key solution concepts in cooperative game theory. As discussed above, its main advantage is that it is a fair allocation, but its main problem is that, for many games, Shapley value cannot be determined in polynomial time. Especially, when we deal with a game with large number of retailers, the problem of computing Shapley value becomes very time consuming. In addition to the computational aspect, Shapley value presents another limitation:

it may be less easy to put into practice than HCB-solution. For instance, under HCB-solution the prot of each retailer holds by reducing the holding costs. As a result, each retailer would take prot form the cooperating by himself/herself by improving his/her holding costs. However, under Shapley value, there must be an explicit transfer of value (money) between the dierent retailers; the presence of a Third Party to mange such situation may be required, which in turn generates additional charges.

We conclude this section by summarizing the main advantages and drawbacks of HCBsolution and Shapley value, see Table 5.8. Each of the two allocations guarantees the stability of the grand coalition. Shapley value ensures the farsighted stability while HCB-solution guarantee the stability in the sense of the core. In term of computational complexity, Shapley value is more complex than HCB-solution. However, Shapley value seems to be more fair than HCB-solution, in the sense that the retailers who contribute more are paid more. Nevertheless, compared to HCB-solution, the establishment of Shapley value solution is less practical and requires more coordination mechanisms and in turn may be more costly.

Cooperation under additional constraints

Above, we showed that due to the superadditivity and without additional constraints, the grand coalition grouping all retailers is the most benecial coalition structure. However, as one can expect, grouping all retailers in a single (large) coalition cannot be easily achieved. For instance, in addition to traditional "social" barriers that privileged small size coalitions to large size ones, there might be some exogenous or endogenous constraints that may hinder the formation of the grand coalition. For example, there might be constraints on the supplier's production capacity (it was assumed in the one-supplier multi-retailer inventory games, that the supplier production system is incapacitated and thus can full large ordered quantities). Also, there might be constraints on the number of coalitions, or on the sizes of coalitions (the number of agents per coalition does not exceed a threshold number). With any additional constraint, the grand coalition cannot be formed and the dierent retailers will form separate and disjoint coalitions forming a coalition structure (partition). The question now is how to form and to search for such coalition structure. Intuitively, as the concern of supply chain models was quite often to optimize the chain as a whole, one can look to nd the partition that minimizes the total systemwide costs/maximizes the total systemwide savings (see Figure 5.2). Such coalition structure will refers as the optimal coalition structure (or full-cooperative coalition structure).

Superadditive games

Grand For instance, when constraining the cardinality of the coalition structure (the number of coalitions in the system at least equals a threshold value, L ≥ 2) the optimization problem will be

P * 1 = argmax P ∈P v(P ) such that |P | ≥ L (5.6)
Similarly, the optimization problem of searching for the optimal coalition structure that maximizes the total systemwide savings under the constraint that the number of retailers per coalition is limited to m, 2 ≤ m < n, is as follows

P * 2 = argmax P ∈P v(P ) such that ∀S j ∈ P, |S j | ≤ m, 2 ≤ m < n (5.7)
Proposition 5.3 The problem of searching for the optimal coalition structure that contains at least L coalitions is equivalent to the problem of searching for the optimal coalition structure that contains exactly L coalitions.

P * 1 = argmax P ∈P v(P ) such that |P | ≥ L ⇐⇒ P * 1 = argmax P ∈P v(P ) such that |P | = L
Proof: The proof of the proposition arises immediately from the superadditivity of the game.

Let us suppose that the optimal coalition structure is formed by (L + 1) coalitions, i,e : P * 1 = {S 1 , ..., S L , S L+1 } = argmax P ∈P v(P ). Let P be the coalition structure obtained by the merging of coalitions S L and S L+1 so P = {S 1 , ..., S L-1 , S L ∪ S L+1 }. The superadditivity of the game gives v(S L ∪ S L+1 ) ≤ v(S L ) + v(S L+1 ) then v(P ) ≥ v(P * 1 ),which proves the proposition.

Proposition 5.4 The coalition structure maximizing the total systemwide prots with the constraint that the number of retailers within the same coalition does not exceed m, 2 ≤ m < n retailers is formed by exactly n m coalitions, i.e., . Now to prove that the optimal coalition structure should contain exactly n m , we show in what follows that for any coalition structure formed by more than n m coalitions, there exists a more protable coalition structure containing exactly n m coalitions. For any n, m ∈ N such that n ≥ m, there exists at least one coalition structure formed by n m coalitions: each of them do not exceed m retailers. And then, any coalition structure formed by more than n m coalitions may be transformed into a coalition structure formed by exactly n m ; each of them does not exceed m retailers. To achieve such transformation, two operations are used: merging and splitting. The margining consists in gathering the coalitions whose sum of members does not exceed m actors in only one coalition. When the merging is impossible, the splitting is used. It consists in disbanding one or more coalitions and to assign their various members to the other coalitions while respecting the constraint of cardinality. We should note that the choice of the coalition to split is not arbitrary and should concern the coalition having the lowest ordering frequency. Since we deal with a superadditive game where every set of disjoint coalitions are better o by merging into one, the operations of merging or splitting exposed above lead to a more protable coalition structure formed by exactly n m , which proves the proposition.

P * 2 = argmax P ∈P v(P ) such that ∀S j ∈ P, |S j | ≤ m =⇒ |P * 2 | = n m Proof: Let P * 2 = {S 1 , ...,
For a better understanding of the problem of constraining the formation of the grand coalition, we present in the following a small numerical example that will allow us to discuss and to motivate some future results. We consider a supply chain formed by 10 retailers. Their corresponding parameters (random parameters) and the outcome of the game are reported in Table 5.9.

Without any additional constraint it is benecial for all the retailers to form the grand coali-

With Cardinality Constraints:

P * = {{1, 3, 4, 5}{2, 6, 7, 10}{8, 9}} 5860
tion, when considering coalitions' cardinality constraints (the number of retailers per coalition is limited to 4 retailers), the coalition structure that optimizes the whole supply chain is P * = argmax P ∈P v(P ) such that ∀S j ∈ P, |S j | ≤ 4 = {{1, 3, 4, 5}{2, 6, 7, 10}{8, 9}}. Once the optimal (centralized) coalition structure P * is determined, the next natural question to be asked is how to allocate the total cost (C(P * ) = 5860) / divide the total savings (v(P * ) = 6989 -5860 = 1129)

among the various retailers that compose the system.

To deal with the prot sharing question, we should come back to the question of alliance formation, because both cooperative behavior problems are interrelated and thus cannot be treated separately. In our case, the coalitions are generated in a way that optimizes the supply chain as a whole. The question that immediately arises here is to determine whether the conguration that optimizes the chain as a whole is the most individually benecial conguration for the retailers. The second interesting question is whether a set of completely independent retailers will naturally form the "full-cooperative" coalition structure. If not, how do the dierent retailers form their alliances?

These questions constitute our main motivation for the rest of the dissertation. In the next chapter, we will show that the "full-cooperative" coalition structure is not a viable objective in nindependent retailer cooperative games and will propose a more appropriate coalition formation approach.

Conclusion

In this chapter, we were concerned with alliance formation and cost allocation in a one supplier multiple-retailer full truckload joint replenishment game. We considered a system where n retailers buy one or a set of products from the same supplier to meet a deterministic market demand.

The retailers may follow a total decentralized strategy, which means that each of them will look to optimize his/her own system regarding his/her own economic parameters and objectives. Going away from the decentralized strategy, the retailers may follow a cooperative strategy where they manage their system collectively, by making joint orders, to achieve some savings. In both structures, the delivery are made with full truckload shipments. A xed ordering cost is incurred for each dispatched truck. The delivered products are stored in local warehouses where holding costs are generated for each retailer.

The arising cooperative game is showed to be superadditive, that is without additional constraints, the grand coalition is the most protable conguration. Since the cooperation between retailers is essentially motivated by their own prot, and any unstable cost allocation may induce the disbanding of the grand coalition, we gave much attention to study the question of savings sharing and grand coalition stability. We mainly considered two stability concepts; the core stability and the farsighted stability. We showed that the core of the game is never empty and a core allocation was provided. After that, we turned our attention to investigate Shapley value properties. We showed that Shapeley value may lie outside the core; however, it is always farsighted stable. We then focused on a detailed comparison and discussion on the advantages and drawbacks of our proposed core allocation and Sahpley value solution. The comparison was mainly based on four aspects; stability, complexity, fairness and practical setting.

Finally, in the last section of the chapter, we discussed the issue of considering some constraints that hinder the formation of the grand coalition. The question that has been asked is how to form the alliances. We discussed the intuitive way of generating the coalition structure that optimizes the whole supply chain. The answer to this question will be more developed in chapter 6, where we will consider a non-supperadditive joint replenishment game.

Chapter 6

Coalition Formation and Cost

Allocation for Joint Replenishment

Systems

This chapter aims at studying the issues of coalition formation and prot allocation in joint replenishment systems. Under this model, the reorder cost associated with an alliance/coalition of retailers placing an order at the same time equals some allianceindependent cost plus retailer-dependent costs. In addition, each retailer is associated with a retailer-dependent holding-cost rate. Despite early works on this eld, we do not aim at optimizing the supply chain as whole. In our analysis, we focus on a supply chain where the cooperation cannot be forced, i.e, each retailer joins the coalition he/she wants to belong to. We present an iterative procedure to form the coalitions and focus on analyzing the merits of such achieved "ecient coalition structure".

Without too much loss of global supply chain performance, when considering the costbased proportional rule, the ecient coalition structure is individually and weakly stable. We provide a condition under which the strong stability (stability in the sense of coalition structure core) holds.

Introduction

This chapter examines the subject of cooperation in joint replenishment systems. In particular, we consider a decentralized supply chain formed by one supplier and n retailers belonging to dierent rms (or are decentralized divisions of the same rm). Each retailer buys only one product from the supplier (products bought by dierent retailers may be identical or specic to each retailer) to meet a deterministic market demand. In order to save on delivery costs, a set of retailers may cooperate by joining their orders as a large order. In such cooperative structure, a xed ordering cost is incurred for each order, which is independent of the set of retailers that places the order. In addition, an individual ordering cost is incurred for each retailer included in the joint order. When a retailer manages his/her inventory individually, he/she has to support a total delivery cost which consists of the xed ordering cost and an individual ordering cost.

The former denotes the xed nancial charges of placing an order. The later may include transportation costs and all additional charges related to the characteristics and resources of the retailer (geographic location, handling resources, etc.). The individual costs are supposed to be independent of the quantities. We assume that the delivered products are stored in local warehouses where holding costs are supported by each retailer. Our interest is to look at the afore-described supply chain and to study the alliances that the retailers may possibly form.

Furthermore, we provide insights on how to divide the prot among the cooperating retailers.

This chapter contributes to the emerging literature on the analysis of problems of distribution channel cooperation by means of cooperative game theory. Closely related to our work are the papers [START_REF] Dror | Shipment consolidation: Who pays for it and how much?[END_REF][START_REF] Anily | The cost allocation problem for the rst order interaction joint replenishment model[END_REF][START_REF] Zhang | Cost allocation for joint replenishment models[END_REF], see chapter 4 for a review. As emphasized in Chapter 3, alliance formation topic has received very little attention in supply chain management literature. This literature seems so far to have been interested only in the stability of one set of agents. Indeed, early works supposed that the games are superadditive in the sense that any two or more disjoint coalitions, when acting together, can get at least as much as they can when acting separately. In such situations there are good reasons to expect the formation of the grand coalition. However, many situations (as in the case of our model) are not superadditive. In this case, there are two fundamental questions that need to be answered:

(1) Which coalitions can be expected to be formed? and (2) How will the players of coalitions that are actually formed apportion their joint prot?

In this chapter, the focus will be to answer the above cooperative behavior questions using some principles of cooperative game theory, particularly the concept of "coalition structure core".

We wish to point out that, to the best of our knowledge, there is no paper in the supply chain management literature that has addressed explicitly the above two questions and this is the rst paper that uses the "coalition structure core" in such literature.

Most of the research on supply chain coordination/cooperation particularly in joint replenishment frame works, has been concerned with optimizing the whole supply chain. The main goal was to show that totally centralized structures are more ecient than decentralized one by nding the solution/policy that minimizes the total systemwide costs/maximizes the total systemwide prots. Therefore, to answer the question concerning coalition formation problem, one would look to optimize the whole considered distribution chain by nding the coalition structure that optimizes the global system performance.

Optimizing the whole supply chain requires full cooperation between the dierent retailers.

Thus, looking for such "full cooperative " structure is a viable objective when the system belongs to a single actor or is managed by one decision maker. In the current model we deal with totally independent retailers/rms. Therefore, there are good reasons to expect that such "full cooperative" structure fails to form, because acting together may be dicult. The factors of competition, rivalry, condence and fairness constitute the major barriers for achieving such objective. This motivates us to propose a new formulation of the coalition formation problem.

Our focus will be on a coalition structure where the dierent coalitions can compete against each other and the cooperation cannot be forced. The eciency of a given coalition is measured according to its prot rate. To build the desired ecient coalition structure (ECS), we use an iterative procedure that generates one ecient coalition at a time. That is, once the most ecient alliance is formed (the coalition having the highest prot rate), a group of retailers may react and form a second ecient coalition, a third one and so on until the formation of the coalition structure.

The activities of coalition formation and prot allocation are closely related. On the one hand, the nal allocation of payos to the players depends on the coalitions that are formed, and on the other hand, coalitions that are nally formed depend on the payos available to each player in each of these coalitions. Thus, we nd it interesting to link the prot allocation to coalition formation's criterion, which is the prot rate here. Therefore, the retailers within the same coalition get the same prot rate, the resulting allocation is the well-known cost-based proportional rule. Under this prot allocation, no retailer would have the incentive to leave his/her coalition to join another existing one. The ecient coalition structure is then individually stable. We also show that no group of retailers that are members of the same coalition would defect from their coalition to create a new alliance. This interesting group deviation immunity is referred to as a weak stability concept. We then provide some conditions under which the strong stability or the stability in the coalition structure core holds. Under strong stability, the ecient coalition structure will also be immune to the deviation of group of retailers that are members of distinct coalitions.

To build the ecient coalition, we need to explore the space of all possible coalitions which is not a viable method except for a small number of retailers. To nd an exact solution to the problem of coalition formation, we mainly use fractional programming, which is a technique developed in operations research to deal with optimization problem having a ratio objective function. That is, we reformulate the problem of nding the ecient coalitions as a singleratio fractional program that is then linearized and showed to be solvable in a polynomial time.

Before looking for this solution, our ambition was to know whether it is possible to predict who are the retailers that are likely to form an ecient coalition only by looking and comparing their parameters. In the hope of answering this question, we concentrated our investigations on nding a kind of "neighborhood logic" or "grouping sense" that the retailers in the ecient coalition would be likely to follow. We succeeded to nd an interesting neighborhood logic in two special cases of our problem (the case where all retailers' individual costs are equal and the case where all retailers' equal cycle time lengths are equal). Because of the complex form of the prot rate function, the grouping logic we found fails to be applied in the general case. Nevertheless, it gives very encouraging results and hence provides good heuristic solution.

The rest of the chapter is organized as follows. In section 6.2, we introduce and study our model. In section 6.3, we motivate our coalition structure approach and explain how to build the ecient coalitions. Section 6.4 is devoted to addressing the question of prot allocation and ecient coalition structure's stability. We propose, in section 6.5, an exact solution based on fractional programming techniques in addition to a grouping heuristic that is showed to be optimal for two particular cases of our model. Section 6.6 gives a numerical study in which we evaluate the algorithmic solution performance and compare our ecient coalition structure (ECS) to the optimal supply chain conguration. We conclude by summarizing the main insights of our results in section 6.7.

Model Description and Notations

The Model

We consider the problems of alliance formation and cost allocation in an innite-horizon onesupplier n retailers joint replenishment system. Each retailer i is assumed to face a deterministic, constant demand rate denoted by D i . The cost of holding one unit of product per unit of time at this retailer is h i . For simplication, we let

H i = h i .D i 2
be the holding cost parameter of retailer i. We assume identical and constant lead times, without loss of generality, assumed to zero.

Each time a delivery is requested by a retailer i, a xed ordering cost A is charged. In addition a retailer-dependent cost G i , called individual cost is supported.

A group of retailers may form an alliance or a coalition S, by joining their orders as a single large order. In this case, the total ordering cost K S equals A + i∈S G i . For simplication we let G S = i∈S G i be the total individual ordering cost of coalition S and H S = i∈S h i .D i 2 its holding cost parameter. The EOQ (Economic order quantity) is used as a reorder policy. The notations and parameters are summarized below:

• N ={1,...,n}: The set of retailers.

• D i : The deterministic demand of retailer i ∈ N .

• h i : The holding cost per time unit of retailer i ∈ N .

• A: The xed ordering cost.

• G i : The individual ordering cost of retailer i ∈ N .

• Q i : The order size of retailer i ∈ N .

• H i = h i .D i 2 :
The holding cost parameter of retailer i ∈ N .

• K i = A + G i :
The total ordering cost of retailer i ∈ N .

• C(i): The average total cost per time unit of retailer i ∈ N .

• T i : The ordering cycle time of retailer i ∈ N .

• G S = i∈S G i : The total individual ordering cost of coalition S, ∅ ⊂ S ⊆ N .

• K S = A + G S :
The total ordering cost of coalition S, ∅ ⊂ S ⊆ N .

• H S = i∈S h i .D i 2 :
The holding parameter of coalition S, ∅ ⊂ S ⊆ N .

• T S : The ordering cycle time of coalition S, ∅ ⊂ S ⊆ N .

When ordering alone, the optimal replenishment parameters of a retailer i may be described by the triplet

(T i * , Q * i , C * (i)).
Where Q * i refers to the optimal ordering quantity and is equal to

D i . K i H i . This quantity is ordered every T i * = K i H i unit of time. The total average cost is then C * (i) = 2. √ K i .H i .
Above, we have determined the optimal replenishment policy for any retailer operating as an independent economic entity. Hereafter, we focus on the case where a group of retailers cooperate by joining their orders as a single large order, in order to achieve some savings by supporting only one xed ordering cost. Consider a non-empty coalition of retailers S ⊆ N , if the retailers in S cooperate they will make their orders at the same time, thus they will have equal cycle times:

∀i ∈ S ⊆ N, T i = T S , T S denotes the common cycle time. Let i ∈ S any retailer. Expressing the order size Q i as a function of T S leads to :

Q i = D i .T S .
When joining their orders, the retailers charge one ordering cost. The total ordering cost induced by the joint orders is then given by : K S = A + G S . Since we suppose that the delivered products are stored in local warehouses where every retailer supports his/her own holding cost, the holding cost charged by the coalition is the sum of the individual holding costs. As a result, the average total cost for an alliance S, C(S), is given by :

C(S) = (A + i∈S G i ) T S + i∈S h i .Q i 2 = K S T S + H S .T S , ∅ ⊂ S ⊆ N (6.1)
Minimizing the total cost with respect to T S gives the following results: the common optimal cycle time length is

T * S = K S H S .
The optimal lot size ordered by a retailer i member of coalition

S is Q * i,S = D i .T * S = K S .D 2 i H S .
The optimal cost of coalition S is obtained by substituting T * S in equation (6.1):

C * (S) = 2. H S .K S , ∅ ⊂ S ⊆ N (6.2)
In summary, the optimal replenishment policy for a non-empty coalition S ⊆ N may be described by the tuple (T * S , Q * i,S , C * (S)).

For a system with a set of n retailers interested in a cooperative behavior, the question is how to nd the most advantageous alliances. In the next section, we give an analysis concerning cooperation mechanisms. In section 4, we will address the question of generating the alliances.

Cooperative System Analysis

To deal with the problems of alliance formation and prot allocation we mainly use cooperative game theory. We associate to the above described distribution chain a cooperative game with coalition structure referred to us as the joint replenishment game, hereafter JR-game and will be denoted by (N, v, P ). Where N = {1, 2, ..., n} is the set of all rms/retailers and P is any coalition structure from P the nite set of coalition structures.

As mentioned in equation ( 6.2), C(S) species for each non-empty coalition S, the cost of its optimal inventory replenishment policy, i.e, the minimal total cost that the rms in S can achieve when they operate jointly. To evaluate the savings achieved by any coalition S, we need to compare the cooperative situation to the decentralized situation where each retailer in S is working individually. The resulting savings function v is as follows:

v : Ω -→ R S v(S) = ( i∈S C(i) -C(S)) (6.3)
The saving function v describes for each coalition of players, S ∈ Ω, the maximal worth v(s) that they would divide among themselves if they were to cooperate together and with no player outside S. The decentralized situation where each retailer operates for his/her own is the situation of reference thus, the worth of single coalition is supposed to be null, i.e, i ∈ N, v(i) = 0.

Intuitively, a group of retailers decides to cooperate and to form a coalition only when their joint cost is less than the sum of their costs when each of them was operating alone. Such coalitions are called protable.

Denition 16 A coalition S is protable or attractive if it has a positive worth ,i.e, v(S) ≥ 0

or C(S) ≤ i∈S C(i), ∀S ∈ Ω.
The rst point to note in this model is that the protability condition is not guaranteed for all possible coalitions. To illustrate this observation, we present the following example. Let us consider a chain formed by a set of three retailers. The corresponding parameters and costs are reported in Table 6.1. In Table 6.2, we compute the savings achieved by all possible coalitions.

Therefore, we remark that the grand coalition {1, 2, 3} and coalition {1, 2} are not protable. Following the last remark, we should note that all coalitions will be protable in the special case where retailers' individual costs are equal to zero. The resulting situation corresponds to the model studied in [START_REF] Meca | Inventory games[END_REF].

Proposition 6.1 When individual costs are null, every alliance is protable.i.e:

If ∀ i ∈ N, G i = 0 then ∀ ∅ ⊂ S ⊆ N : C(S) ≤ i∈S C(i)
Proof: Let us denote by C (S) and C (i) the optimal cost respectively for a coalition S and for

a retailer i. C (i) = √ 2Ah i D i and C (S) = 2A i∈S h i D i . For A ≥ 0, C (S) = √ 2A i∈S h i D i ≤ √ 2A i∈S √ h i D i = i∈S C (i).
Adding a third cost component (individual cost) to the previous model changed its characteristics, thus it is not sucient anymore to have a non-null ordering cost to get protable coalitions.

Hereafter, we give some insights about the conditions under which a coalition is protable and we explain why others are not.

As mentioned in Figure 6.1, if a retailer i deviates from his/her optimal cycle time T * i to order at another cycle time T * S , his/her total cost is increased as a function of this deviation.

α i = T * S T * i , α i > 0. C(T * S ) = K i T * S + H i .T * S = K i α i .T * i + H i .α i .T * i by substituting T * i by its expression T * i = K i H i we get: C(T * S ) = √ K i .H i α i + α i . √ K i .H i = ( 1 α i + α i ) C(T * i )
2 . The cost rise of retailer i is then as follows:

i (α i ) = C(T * S ) -C(T * i ) = (α i -1) 2 2.α i .C(T * i ).
As a result, the total cost deviation of the retailers forming a coalition S, characterized by the common cycle time T * S is as follows :

S = i∈S (C(T * S ) -C(T * i )) = i∈S (α i -1) 2 2.α i .C(T * i ). ∅ ⊂ S ⊆ N. (6.4)
On the other hand by making joint orders, the retailers reduce their ordering costs: each of them was used to pay one ordering cost when he/she works individually by opposition to only one ordering cost in the case of an alliance. Indeed, for an alliance, S, formed by |S| retailers, the savings per unit of time is expressed by the following equation.

π S = (|S| -1).A T *

S

, for all ∅ ⊂ S ⊆ N. (6.5) Proposition 6.2 A coalition S is protable or attractive only beyond a threshold value of the ordering cost A min given by:

A min = (|S| -1). i∈S (α i -1) 2 T * i .C * (i) (6.6)
Proof: A coalition S is protable only if the cost rise induced by the cycle time deviation is balanced by the savings of ordering costs, i.e. π S ≥ S .

C(S)

≤ i∈S C(i) ⇐⇒ (|S|-1).A T * S ≥ i∈S (α i -1) 2 2.α i .C(T * i ) ⇐⇒ A ≥ (|S|-1). i∈S (α i -1) 2 T * i .C * (i).
The protability condition here has another crucial interpretation. It means that the game is not superadditive in the sense that it is not guaranteed that any two or more disjoint coalitions, when merging into one coalition, increase their savings. As a result, the grand coalition grouping all retailers may not be protable (see example Table 6.2). Therefore, the question that immediately arises and needs to be answered is: Which coalitions can be expected to be formed?

Ecient Coalition Structure Generation

Most of the research on supply chain coordination has been concerned with optimizing the whole supply chain. It has been shown that decentralized structures where each retailer makes his/her decisions so as to minimize his/her own costs often lead to a loss of eciency for the chain as a whole. However, totally centralized structures where decisions are made to minimize the total systemwide costs (maximize the total systemwide prots), prove to be more ecient [START_REF] Li | Coordination mechanisms of supply chain systems[END_REF]. Therefore, to answer the question concerning coalition formation problem, one would look to optimize the whole considered distribution chain by nding the coalition structure that optimizes the global system performance i.e.,

P * = argmax P ∈P v(P ) (6.7)
The result of the above optimization problem will be a partition (Optimal Coalition Structure) where the retailers are organized in many disjoint coalitions. Of course, the optimal coalition structure may be the grand coalition N , but this is not true in general because the game is not superadditive.

It is obvious that achieving the above goal requires a full cooperation between the dierent retailers. Hence, looking for such "full cooperative " structure will be a viable objective only when the system belongs to a single actor or is managed by one decision maker. In the current model, we deal with totally independent retailers. Therefore, there are good reasons to expect that "full cooperative" structure fails to be formed because as warned by [START_REF] Aumann | Cooperative games with coalition structures[END_REF] "acting together may be dicult or costly or the retailers may for various personal and economic reasons not wish to do so". The factors of competition, rivalry, condence and fairness constitute the major barriers of achieving such objective.

More importantly, since the retailers are independent actors, when cooperating, each one of them is mainly interested in his/her own prot and his/her own system performance. Prot sharing is therefore a fundamental question here. As exposed in cooperative game theory's preliminary chapter (see chapter 3), in a game with coalition structure, the payo is distributed in a way that there is no-side payment between the distinct coalitions. The players within the same coalition would divide among themselves the worth achieved by their own coalition. Thus, each player's payo is completely determined by the identity of the other members of his/her coalition, no matter the payo of other coalitions. Therefore, any retailer is only interested in the prot of the coalition he/she wants to join and does not care about the total systemwide prot.

Thus, global optimization or full cooperative system is not a viable objective in our nindependent retailer cooperative game. The focus here is to discuss the issue of generating an ecient coalition structure for n-independent retailer cooperative game. We propose to build the dierent coalitions in a completely independent manner privileging individual coalition's performance to that of the global system. Each retailer should have his/her own preferences over coalitions to which he/she could belong. To do so he/she needs to compare coalitions' performance. The question now is: is it sucient to compare two coalitions only by their respective savings? We nd savings amount criterion not sucient to compare two distinct coalitions with possibly dierent retailers' parameters. For instance, consider the example of a retailer i that needs to choose between two coalitions, S i and T i with equal cardinal. Let us assume that, C(S) = 100 and j∈S C(j) = 200, coalition S's savings is then equal to 100. Suppose that, C(T ) = 9000 and j∈T C(j) = 10000, coalition T 's savings is then equal to 1000. It is obvious that coalition T 's savings is ten times coalition S's savings. However, retailer i would choose coalition S, because it has a higher prot rate. Thus, we found it more judicious and more interesting to compare coalitions' performance or eciency regarding their respective prot rate than their savings.

Denition 17 : The prot rate of a given coalition S is the ratio of its savings to its decentralized cost,

π(S) = v(S) i∈S C(i) = i∈S C(i) -C(S) i∈S C(i) (%), S ∈ Ω. (6.8)
Following the characterization of coalitions' eciency, we turn our attention to focus on coalitions having higher prot rate. The coalition having the highest prot rate will be referred as the most ecient coalition and is dened as follows :

Denition 18 The most ecient coalition refers to the coalition that guarantees the highest prot rate:

S 1 = argmax S⊆N {π(S)} (6.9)
The most ecient coalition S 1 has the following interesting interpretation. Since it guarantees the highest prot rate, coalition S 1 will be the most preferred coalition for each one of its members. At the same time, this coalition is "saturated" in the sense that the adhesion of any retailer or group or retailers outside S 1 will be rejected, because by construction, this will decrease the coalition's prot rate. Now suppose that coalition S 1 is formed, the question is how should the retailers outside S 1 organize themselves to cooperate. To answer to this question, we rst consider the new system, or the updated system N \ S 1 and we suppose that, similarly to S 1 , the most ecient coalition S 2 in the new system N \ S 1 will arise.

S 2 = argmax S⊆(N \S 1 ) {π(S)} (6.10)

Now the procedure is simple, we assume that the remaining set of retailers N \ (S 1 ∪ S 2 )

will react in the same manner, that is a third ecient coalition S 3 will be formed, a fourth and so on until assigning all retailers to their ecient coalitions. It is clear that, by construction, the ecient coalitions are disjoint, therefore they form a partition of N . This partition will refers to the ecient coalition structure and will be denoted by P .

Denition 19 : The Ecient Coalition Structure (ECS) P refers to the partition that holds when each rm/retailer joins his/her ecient coalition, i.e, P = {S 1 , S 2 , ..., S m } such that each coalition S i satises the equation:

S i = argmax S⊆(N \∪ j=i-1 j=1 S j ) {π(S)}, S i ∈ P (6.11)
To conclude, the positioning of the above proposed ecient coalition structure in games with coalition structures is well illustrated by Figure (6.2 ). On analyzing the merits of the ecient coalition structure, P , the rst point to note is that this partition always exists and is easy to form. Second, P is formed by totally independent coalitions. This makes the management of such coalition structure easier than that of any other coalition structure. For instance, there is no need to have a third party to manage the whole system, each coalition is working for its own and since it contains a restricted number of rms compared to that of the grand coalition, mutual agreements can be found and the cooperation process can be put into practice easily. Moreover, ecient coalition structure P has another interesting interpretation. It does not alter the competition between the coalitions. That is when the most ecient coalition (the coalition having the highest power) is formed, some retailers react by forming a second ecient coalition and so on. The ecient coalition structure P is then original in the sense that it combines competition and cooperation. Indeed, the retailers rst compete among each other to form the most ecient coalition for their own sake, knowing that within the coalition they will be part of, they will cooperate with other retailers, that are part of the same coalition. This observation is extremely important since the wide supply chain literature was only concentrated in studying completely competitive situations or completely cooperative ones.

In coalition formation games, the quality of a coalition structure is often evaluated according to its stability. To know whether ECS is stable or not, we should answer the question : How will the retailers of coalitions that are actually formed apportion their joint prot?

Prot Sharing and Stability

The focus of this section will be to address the question of prot sharing through which the stability of ecient coalition structure P will be investigated. The rst point to note is that even if they are treated separately, the two aspects of coalitional behavior, coalition formation and prot allocation, are closely related. On the one hand, the nal allocation of payos to the players depends on the coalitions that are nally formed and, on the other hand, coalitions that nally form depend on the payos available to each player in each of these coalitions. Thus, the payos inuence the coalition structure and vice versa. In our case, the ecient coalition structure P is formed in a way that each retailer joins the coalition that guarantees the maximum possible prot rate. We should remember that coalition's prot rate was dened as the ratio of coalition's savings to coalition's decentralized cost. Intuitively, one way to satisfy the cooperating retailers within the same coalition is to pay them proportionally to their standalone costs. The resulting allocation is the well-known proportional rule. In what follows, we rst remember the cost-based proportional rule, the allocation that we use in the rest of the chapter. Then, we turn our attention to focus on coalition structure P 's stability.

Denition 20 : Proportional allocation

The cost-based proportional rule consists in allocating the savings in proportion with the initial cost of dierent retailers. Thus, in the ecient coalition structure P each retailer i member of coalition S k gets,

X(i, S k ) = C(i) j∈S k C(j) .v(S k ) = C(i).π(S k ). i ∈ S k ∈ P . (6.12)
Following the denition of the savings allocation rule, one can compute the prot rate of each retailer. The prot rate is the ratio of the attributed savings to the standalone (initial) cost of each retailer. In the ecient coalition structure P , the prot ratio of a retailer i member of coalition S k is as follows:

π(i, S k ) = X(i, S k ) C(i) = π(S k ), i ∈ S k ∈ P . (6.13)
The cost-based proportional rule has the interesting propriety that the retailers within the same coalition get the same prot ratio.

For a better understanding of the afore described ecient coalition structure and cost-based allocation, we present the following numerical example. We consider a 10-retailer coalition formation game. Retailers' parameters and the main outcomes of the game are reported in Table 6.3. The ecient coalition structure is P = {{5, 6, 9}, {3, 4, 8, 10}, {1, 7}, {2}}. The coalitions here are ranked by their prot rate, which corresponds to their order of formation. When costbased proportional allocation is used, the retailers within the same ecient coalition get the same prot ratio. Now we turn our attention to discuss whether the ecient coalition structure is stable or not.

We analyze the three stability notions dened in Chapter 3.

X(i, S k ) = C(i) P j∈S k C(j) .v(S k ) = C(i).π(S k
). This allocation possesses the following properties:

i) X(i, S k ) ≥ 0. ii) i∈S k X(i, S k ) = i∈S k C(i) P j∈S k C(j) .v(S k ) = v(S k ). iii)For all coalition T ⊆ S k , we have X(T ) = i∈T C(i).π(S k )
. By construction T is less ecient than S k , i.e, π(T ) ≤ π(S k ); otherwise T would have been selected by the algorithm

instead of S k . Consequentially, X(T ) = i∈T C(i).π(S k ) ≥ i∈T C(i).π(T ) = v(T ). The Cost-based proportional rule is then in the core of the subgame (S k , v S k
).

The coalition structure core is a stronger stability concept than the weak stability concept presented above since under coalition structure core stability, no group of retailers (member of the same coalition or member of distinct coalitions) will have the incentive to deviate. However, in practice, the group of retailers that are members of the same coalition are the most likely to deviate. For instance, the retailers that want to form a new coalition should have access to high quality information on each other and would have many meetings and appointments in order to nd mutual agreements, etc. For this reason, new alliances have more chance to be formed by retailers belonging to the same coalition than by retailers belonging to disjoint coalitions.

This is true because, on the one hand, retailers that are members of the same coalition have more access to information on each other, hence they may easily nd mutual agreements to coordinate their movements to form a new coalition. On the other hand, coordinating the actions of retailers member of several coalitions seems to be more complex because it requires much more coordination mechanisms. Consequentially, the weak stability under which the immunity is restricted to deviations of group of retailers member of the same coalition may be sucient in this sense to address the stability of the ecient coalition structure P . This stability is also reinforced by the proprieties of the cost-based proportional rule. Under this rule, the retailers within the same coalition get equal prot ratios. This equity aspect or fairness federates the intentions of retailers to cooperate.

Ecient coalition structure P , where retailers within the same coalition get the same prot ratio, is likely to be more stable than a coalition structure where the attributed prots are disproportionate. This is true because a cooperating retailer is not only interested in his/her own prot, but always he/she is interested in his/her prot regarding the prots of his/her partners. When there is huge gap between the prots of retailers forming the same alliance, an unsatised retailer may be nonrational and can give up his/her prot to deprive a "competitor" having a more important prot: the stability of the alliance is no longer guaranteed.

To take into account prot ratio equity, one would extend the meaning of rationality which traditionally reduces the motivation to cooperate to a resulting "positive" prot. Under prot rate equity, a rational retailer will not cooperate as soon as he/she has a positive prot, he/she will cooperate only when his/her resulting prot rate is similar to that of his/her partners. In this case, cost-based proportional rule ensures the strong stability of the ecient coalition structure P . In other words, cost-based proportional rule will be in the coalition structure core of P if it is the most privileged allocation. We should note that there are good reasons to expect that the cost-based proportional rule will be a privileged allocation, because, in addition to be fair in the sense of prot equity distribution, it is one of the most simple and practical allocations.

Theorem 6.3 : Strong stability: When the cost-based proportional rule is the most privileged allocation in the system, the ecient coalition structure P is strongly stable, i.e, X ∈ Co(N, v, P ).

Proof: Assume that the cost-based proportional rule is the most privileged allocation in the system, it is then easy to prove that this rule belongs to the coalition structure core of P . To prove that, we should show that no group of retailers would have the intention to deviate and form new coalition. The weak stability of coalition structure P shows that no group of retailers belonging to the same coalition will deviate. Hence the question of stability remains only for group of retailers that are members of at least two distinct coalitions. Let T be a group of retailers that are members of dierent coalitions. That is there exists a set of coalitions {S k , ..., S l } ⊆ P such that T ⊂ ( j=l j=k S k ) and T ∩ S j = ∅ ∀j ∈ {k, .., l}. Without loss of generality we suppose that S k = argmax(π(S k ), ..., π(S l )). By construction, coalition S k is more ecient than coalition T (π(T ) ≤ π(S k ), otherwise coalition T would have been selected by the algorithm and would belongs to the ecient coalition structure P . Since we deal with cost-based proportional rule, each retailer i member of the subset T ∩ S k will actually have a prot ratio of π(i, T ) = π(T ) which is less than what he/she gains before (π(S k )). Consequentially, coalition T cannot be formed.

An Optimal Algorithm for ECS Generation

Complexity Analysis

The ecient coalition structure P = {S 1 , S 2 , ..., S m } is obtained by a sequential approach generating an ecient coalition at a time. Each ecient coalition S i is the solution to the optimization problem (equation (6.11)): S i = argmax S⊆(N \∪ j=i-1 j=1 S j ) {π(S)}, S i ∈ P . The worst case is to select coalitions containing only two retailers for all steps. In this case, in a system with n retailers, we need n 2 iterations to build the ecient coalition structure. The number of necessary iterations does not really matter since it equals at worst to n 2 iterations. However, to nd the most ecient coalition, S 1 = argmax S⊆N {π(S)}, we need to enumerate all possible coalitions. In a system of n retailers there are (2 n -1) possible coalitions. This number doubles with each retailer added to the system. Consequentially, when the number of retailers is large, there will be too many possible coalitions to allow exhaustive search for the most ecient one. For example, in a system of 20 retailers there are 1.048.575 possible coalitions. As a result, exhaustive enumeration is not a viable method for searching for an ecient coalition structure unless when the number of retailers is small.

In the next section, we propose an optimal algorithmic solution for generating the ecient coalition structure. The algorithm we propose is based on single ratio fractional programming techniques. Moreover, we propose a heuristic solution that is showed to be optimal for two interesting particular cases, in the rst case, all individual costs are equal (∀i ∈ N, G i = G), and in the second case all retailers' cycle time lengths are equal.

Optimal Algorithm for the General Case

The proposal of this section is to provide an exact solution for searching for the ecient coalitions.

As explained above, we will focus on the optimization problem to generate the most ecient coalition:

S 1 = argmax S⊆N {π(S)}
Proposition 6.3 : Maximizing the prot ratio is equivalent to minimize the ratio of the coalition's cost to its corresponding decentralized cost:

S 1 = argmin S⊆N ( C(S) i∈S C(i) ) = argmin S⊆N ( (A + G S ).HD S i∈S C(i) ) (6.14)
Proof:

S 1 = argmax S⊆N {π(S)} = argmax S⊆N ( i∈S C(i) -C(S) i∈S C(i) ) = argmax S⊆N (1 - C(S) i∈S C(i) ) = argmin S⊆N ( C(S) i∈S C(i) ).
In what follows, for simplicity we will consider the minimization problem (7.13). The ratio C(S) P i∈S C(i) will refers to us as the cost ratio and will be denoted by CR(S).

The optimization problem (7.13) may be formulated as the following linear program. The decisions variables X j address the selection of one coalition from all possible 2 n -1 coalitions.

X j =    1 : if coalition j is selected 0 : otherwise (F ORM U LAT ION -I) min 2 n -1 j=1 ( C(S) i∈S C(i)
).X j (6.15)

2 n -1 j=1 X j = 1 (6.16) X j ∈ {0, 1}, ∀j = 1, 2, ..., 2 n -1 (6.17)
Since we deal with an objective function that aims at minimizing a ratio of two functions, single-ratio fractional programming theory [START_REF] Schaible | Fractional programming[END_REF][START_REF] Radzik | Fractional combinatorial optimization in Handbook of Combinatorial Optimization[END_REF]) may be used. However, the square root form of the objective function (6.15) makes it impossible to reformulate the above problem as a fractional program. Therefore, since the optimization problem

S 1 = argmin S⊆N {( C(S) P i∈S C(i) )} is equivalent to S 1 = argmin S⊆N {( C(S) i∈S C(i) ) 2 } = argmin S⊆N {( (A + i∈S G i ) i∈S HD i ( i∈S C(i)) 2 )}
The last square form factor may substitute the objective function (6.15). The resulting new objective function is then :

(A + i∈S G i ) i∈S HD i ( i∈S C(i)) 2 (6.18)
Now let us dene the new decision variables Y i , i = 1, .., n such that each Y i refers to whether retailer i is member of the ecient coalition or not.

Y i =    1 : if retailer i is in the ecient coalition 0 : otherwise
Rewriting the objective function (6.18) by introducing the binary variables Y i gives:

(A + n i=1 G i .Y i )( n i=1 HD i .Y i ) ( n i=1 C(i).Y i ) 2 = A. n i=1 HD i .Y i + n i=1 n j=1 HD i .G i .Y i .Y j ( n i=1 n j=1 C(i).C(j).Y i .Y j ) (6.19)
For simplication, for any couple of retailers i and j, we note G j .HD i by GHD ij and C(i).C(j) by C ij . The objective function (6.19) is then as follows:

A. n i=1 HD i .Y i + n i=1 n j=1 GHD ij .Y i .Y j ( n i=1 n j=1 C ij .Y i .Y j ) (6.20)
Finally, the 0-1 fractional program reformulation is as follows:

(F ORM U LAT ION -II) min A. n i=1 HD i .Y i + n i=1 n j=1 GHD ij .Y i .Y j ( n i=1 n j=1 C ij .Y i .Y j ) (6.21) n j=1 Y i >= 1 (6.22) Y i ∈ {0, 1}, ∀i = 1, 2, ..., n (6.23)
The objective function (6.21) denotes the ratio to be minimized. Constraint (6.22) ensures that the ecient coalition contains at least one retailer, and constraints (6.23) represent the binary form of the decision variables Y i . It is obvious that, this reformulation considerably reduces the number of variables compared to (F ORM U LAT ION -I). There is only n variables while in (F ORM U LAT ION -I) there are (2 n -1) variables. However, as one can expect, the fractional program cannot be solved in its current form (the objective function is non-linear) the state-ofthe-art of mixed-integer linear programming (MILP) cannot be used. The focus in what follows will be to linearize the fractional program exposed above. We should note that linearization techniques are used quite often in fractional programming literature [START_REF] Falk | Optimising the sum of linear fractional functions[END_REF][START_REF] Li | A global approach for general 0 -1 fractional programming[END_REF][START_REF] Wu | A note on a global approach for general 0 -1 fractional programming[END_REF][START_REF] Radzik | Fractional combinatorial optimization in Handbook of Combinatorial Optimization[END_REF]. Some recent 0-1 fractional program linearization are found in [START_REF] Tawarmalani | Global optimization of 0 -1 hyperbolic programs[END_REF][START_REF] Prokopyev | The equitable dispersion problem[END_REF]. Their main ideas are presented by the following propositions that we will apply in our model. Proposition 6.4 [START_REF] Prokopyev | The equitable dispersion problem[END_REF] .A polynomial mixed 0 -1 term z = x.y where x is a 0 -1 variable, and y is a nonnegative continuous variable, can be equivalently represented by the following four linear inequalities:

(1)z ≥ y -M (1 -x); (2)z ≤ y; (3)z ≤ M x; (4)z ≥ 0, where
M is an upper bound on y, i.e., 0 ≤ y ≤ M . Proposition 6.5 [START_REF] Prokopyev | The equitable dispersion problem[END_REF] .A polynomial mixed 0 -1 term z = x 1 .x 2 .y where

x 1 and x 2 are a 0 -1 variables, and y is a nonnegative continuous variable, can be equivalently represented by the following ve linear inequalities:

(1)z ≥ y -M (1 -x 1 -x 2 ); (2)z ≤ y; (3)z ≤ M x 1 ; (4)z ≤ M x 2 ;
(5)z ≥ 0, where M is an upper bound on y, i.e., 0 ≤ y ≤ M .

In order to reformulate the objective function (6.21) as a linear function, we dene the new variable T such that:

T = 1 n i=1 n j=1 C ij .Y i .Y j (6.24)
This denition is equivalent to:

n i=1 n j=1 C ij .Y i .Y j .T = 1 (6.25)
With the newly introduced variable T , the fractional program (F ORM U LAT ION -II) can be rewritten as:

(F ORM U LAT ION -III) min T,Y A. n i=1 HD i .Y i .T + n i=1 n j=1 GHD ij .Y i .Y j .T (6.26) n i=1 Y i ≥ 1 (6.27) n i=1 n j=1 C ij .Y i .Y j .T = 1 (6.28) Y i ∈ {0, 1}, ∀i = 1, 2, ..., n (6.29)
Next, nonlinear terms Y i .T and Y i .Y j .T can be linearized by introducing additional variables

Z i and Z ij (Z i = Z ii )
and applying the results of propositions 6.4 and 6.5. The parameter M can be set to 1. The resulting linear mixed-integer program is as follows:

(F ORM U LAT ION -IV ) min Y,T,Z A. n i=1 HD i .Z ii + n i=1 n j=1 GHD ij .Z ij (6.30) n i=1 Y i ≥ 1 (6.31) n i=1 n j=1 C ij .Z ij = 1 (6.32) T -Z ij ≤ (2 -Y i -Y j ), i = 1, 2, ..., n, ∀j = 1, 2, ..., n (6.33) Z ij ≤ T, ∀i = 1, 2, ..., n, ∀j = 1, 2, ..., n (6.34) Z ij ≤ Y i , ∀i = 1, 2, ..., n, ∀j = 1, 2, ..., n (6.35) Z ij ≤ Y j , ∀i = 1, 2, ..., n, ∀j = 1, 2, ..., n (6.36) Z ij ≥ 0, ∀i = 1, 2, ..., n, ∀j = 1, 2, ..., n (6.37) Y i ∈ {0, 1}, ∀i = 1, 2, ..., n (6.38)
The total number of variables in the model is (n(n + 1) + 1) where n are binary variables and

(n 2 + 1) are continuous. The total number of constraints is (5n 2 + 3) composed by 1 equality constraint, (n 2 ) positivity constraints and (4n 2 + 2) inequalities.

Proposition 6.6 By construction, (F ORM U LAT ION -I) and (F ORM U LAT ION -IV ) are equivalent, i.e., (6.15)-(6.17) ⇔ (6.30)-(6.38)

Heuristic Solution

Before thinking about the exact algorithmic solution presented above, our ambition was to know whether it is possible to predict who are the retailers that are likely to form an ecient coalition only by looking and comparing their standalone parameters/costs. In the hope of answering this question, we concentrated our investigations on nding a kind of "neighborhood logic"

or "grouping sense" that the retailers in the ecient coalition would be likely to follow. We succeeded to nd an interesting neighborhood logic in two special cases of our problem (he case where all retailers' individual costs are equal and the case where all retailers' equal cycle time lengths are equal). Because of the complex form of the prot rate function, the grouping logic we found fail to be applied in the general case, nevertheless it gives very encouraging results.

That is why we present it as a heuristic solution. The rest of the section will be organized as follows. We will be starting by giving the main idea of the grouping logic heuristic. After that we show that this heuristic is optimal for the two particular cases of our model (the case where all retailers' individual costs are equal and the case where all retailers' equal cycle time lengths are equal).

Neighborhood Logic Heuristic

To give the main idea of the heuristic, we need the following denition.

Denition 21 Assume that the dierent retailers are sorted by their increasing ratio of HD i

G i . A coalition S is a consecutive coalition if it satises the following condition: For i, j, k ∈ N, i = j = k such that HD i G i ≤ HD k G k ≤ HD j G j : {i, j} ⊂ S implies k ∈ S
The heuristic supposes that all ecient coalitions are consecutive coalitions. Thus, to nd the ecient coalitions, we do not need to enumerate all possible coalitions; the research space is restricted to consecutive coalitions. The main steps of the heuristic are :

• The retailers are sorted by their increasing ratio

HD i G i , i.e, HD 1 G 1 ≤ HD 2 G 2 ≤ ... ≤ HDn Gn .
• The set of all possible consecutive coalitions is generated.

• Selection of ecient coalitions iteratively.

For a system with n retailers, there are (n+1)n 2 consecutive coalitions. This number is very small compared to that of all possible coalitions (2 n -1). For example, in a system with 20 retailers there are 1.048.575 possible coalitions, only 210 of them are consecutive. Consequentially, the size of the problem becomes manageable and exhaustive enumeration may be used even for large size system.

Particular case 1: Equal individual costs Theorem 6.4 When all retailers' individual costs are equal, all ecient coalitions are consecu-

tive coalitions. ∀i ∈ N, G i = G =⇒ ∀S i ∈ P , S i is a consecutive coalition.
Proof: To prove this theorem, we prove that for any non-consecutive coalition, there exists at least one consecutive coalition more ecient than it. We remember that a coalition S is more ecient than a coalition T , means that coalition S ensures a higher prot rate or a lower cost Let T = {i, ..., j -1, j + 1, ..., t} be a coalition. Since T presents a hole (j ∈ T ), T is a non-consecutive coalition. We have to construct a consecutive coalition T more ecient then T , i.e. CR(T ) ≤ CR(T ).

Let S be any coalition of N and {x} be any retailer such that {x} ∈ S. The retailer {x} is characterized by its holding parameter HD x , for simplicity noted X. Let us dene the following function representing coalition (S ∪ {x})'s cost rate:

f : (2 n -1) × + → + (S, X) f (S, X) = CR(S ∪ {x}) = √ (A+(|S|+1).G)( P i∈S HD i +X) (A+G)( P i∈S √ HD i + √ X) (6.39)
The function f is a positive convex function that reaches its minimum for min S =

( P i∈S HD i ) 2 ( P i∈S √ HD i ) 2 .
The function f is decreasing for X ∈ [0, min S ] and is increasing function for X ∈ [min S , +∞[. Let us consider the coalitions S and S such that S = {i, ..., j -1, j + 1, ..., t -1} and S = {i + 1, ..., j -1, j + 1, ..., t}.

• If HD j ≥ min s , since (min S ≤ HD j ≤ HD t ) and the function f is increasing thus:

f (S, HD j ) ≤ f (S, HD t ), i.e, CR(T = S ∪ {j}) ≤ CR(T = S ∪ {t}). The consecutive coalition T = {i, ..., j -1, j, j + 1, ..., t -1} is then more ecient than coalition T .
• Else HD j < min S . First we need to present the following proposition: Proposition 7: For n reals (R 1 , ..., R n ) such that ∀i ∈ {1, ..., n -1} : 1 ≤ R i ≤ R i+1 we have:

P i=n-1 i=1 R i P i=n-1 i=1 √ R i ≤ P i=n i=2 R i P i=n i=2 √ R i . Proposition 7: RN = ( i=n i=2 R i )( i=n-1 i=1 √ R i ) -( i=n i=2 √ R i )( i=n-1 i=1 R i ) after simplication equals: RN = ( √ R n - √ R 1 )( i=n-1 i=2 ( √ R n . √ R i -R i ) + √ R 1 .( i=n-1 i=2 √ R i + √ R n )). We have R n ≥ R i , ∀i ∈ {1, ..., n} so ( √ R n . √ R i -R i ) ≥ 0 and ( √ R n - √ R 1 ) ≥ 0, thus RN ≥ 0.
From proposition 7 we have min S ≥ min S , in this case we have

HD i ≤ HD j ≤ min S the function f is decreasing then f (S , HD j ) ≤ f (S , HD i ), i.e, CR(T = S ∪ {j}) ≤ CR(T = S ∪ {i}). The consecutive coalition T = {i + 1, ..., j -1, j, j + 1, ..., t} is more ecient than coalition T .
Note that when the non-consecutive coalition T presents more than one hole, the theorem is still true, with the proof diering only in the construction of T and T .

Particular case 2: Equal cycle time lengths

Here we consider the particular case where all retailers' cycle time length (similarly ordering frequencies) are equal. The ecient coalitions are consecutive coalitions, and the most ecient coalitions are formed by the retailers having the lowest holding parameters. These theorems are considered to rene the heuristic solution.

Theorem 6.5 When all retailers' cycle time length are equal, all ecient coalitions are consecutive coalitions, i.e; ∀i, j ∈ N, i = j :

T * i = T * j , =⇒ ∀S i ∈ P , S i is a consecutive coalition.
Proof: Like in the proof of theorem 4, we prove that for any non-consecutive coalition, there exists at least one consecutive coalition more ecient than it. Suppose that the retailers are sorted by their increasing holding parameter HD i , suppose without loss of generality that the resulting order is :

HD 1 ≤ HD 2 ≤ ... ≤ HD n .
Assuming equal cycle time length leads to, ∀i, j ∈ N, i = j, T * i = T * j = T , and

T * i = 2.(a+G i ) HD i . Let V be a strictly positive constant such that, ∀i ∈ N : (A + Gi) = V.HD i .
Rewriting the cost rate of a coalition, S, with the newly parameter leads to :

CR(S) = 2.(A + i∈S G i ). i∈S HD i i∈S 2.(A + G i ).HD i = 1 - (|s| -1)A V. i∈S HD i (6.40)
Let T = {1, 2, ..., t -3, t -2, t}, be a non consecutive coalition ({t -1} ∈ T ) and let us build a more ecient consecutive coalition T (i.e, CR(T ) ≤ CR(T )).

Let T the coalition that holds when we substitute retailer {t} by retailer {t-1} in coalition T ,

thus T = {1, 2, ..., t -3, t -2, t -1}. It is obvious that i∈T HD i ≤ i∈T HD i and |T | = |T |,
then from equation (6.40) we get CR(T ) ≤ CR(T ). Note that when the non consecutive coalition

T presents more than one hole, the theorem is still true, with the proof diering only in the construction of T .

Theorem 6.6 The consecutive coalition formed by the retailers having the lowest holding parameters is more ecient then any other consecutive coalition with equal cardinal, that is, ∀k ∈ {2, ..., n} and T ⊆ N such that |T | = k we have : CR(S = {1, 2, ..., k}) ≤ CR(T ).

Proof: Let S = {1, 2, ..., k}, k ∈ {2, ..., n} be the coalition of k retailers and let T any coalition of k retailers, T ⊆ N, |T | = k. As showed in the proof of the previous theorem,

CR(S) = 1 -(k-1)A V. P i∈S HD i and CR(T ) = 1 -(k-1)A

V. P

i∈T HD i . Since the retailers are ranked sequentially in increasing order of HD i , i∈S HD i ≤ i∈T HD i then CR(S) ≤ CR(T ) . Now let us reformulate the procedure of generating the ecient coalitions taking into account the last two theorems. Suppose that the retailers are ranked by their holding parameters, without loss of generality let the order be, HD 1 ≤ HD 2 ≤ ... ≤ HD n . From theorem 6.6, the most ecient coalition S 1 can be determined by comparing the n -1 possible consecutive coalitions {1, 2, ..., k}, k ∈ {2, ..., n}, that is: S 1 = {1, 2, ..., l}=argmin{CR({1, 2}) , ..., CR({1,2,...,k}),CR({1, 2, ..., k + 1}), ..., CR({1, 2, ..., n})}. The most ecient coalition S 2 in the remaining set of retailers {l, l + 1, ..., n} is determined in the same way. That is,S 2 = argmin{CR({l +1, l +2}), ..., CR({l +1, l +2, ..., k}),CR({l +1, l +2, ..., k +1}),..., CR({l +1, l + 2, ..., n})}. The procedure is then repeated until that the set of remaining retailers is empty.

To nd the ecient coalition S 1 only n -1 coalitions are compared. This number decreases considerably for other ecient coalitions; it depends on the cardinal of the selected coalitions.

In general, to nd ecient coalition S i , i ≥ 2, (n -k=i-1 k=1 |S k | -1) coalitions should to be compared. The worst case is to get ecient coalitions formed by a couple of retailers (|S k | = 2).

In this case, we need to generate, ( n 2 ) ecient coalitions by comparing (n -2.(i -1) + 1) coalitions when forming ecient coalition S i . The total number of coalitions compared over the generation of the ecient coalition structure is then:

i= n 2 i=1 (n -2(i -1) + 1) this equals to ( n
2 ) 2 when n is even, and equals to n-1 2 ( n-1 2 + 1) otherwise.

Numerical Study

Our numerical study is twofold. First, we use a set of numerical tests to evaluate the performance of our proposed exact solution and heuristic. A second numerical set is devoted to compare the ecient coalition structure to the optimal coalition structure. In both numerical sets, the demand characterizing each retailer, D i , is generated randomly in the interval for each value of n we dealt with 10 instances. All computational experiments were performed on a PC with Intel Core 2 CPU of 3 Ghz and RAM of 0.99 GB. All instances were solved using ILOG OPL Development Studio 5.2 solver with default parameters. We also imposed 1 hour time limit.

Exact solution and Heuristic Performance

Our experiment here is to appreciate the performance of the proposed mixed-integer linear program F ORM U LAT ION -IV (exact solution) and the heuristic. To achieve this goal, we consider the problem of nding the most ecient coalition. For each instance, we compute the time used (seconds) and the prot rate for the exact solution, F ORM U LAT ION -IV , (ExactSOL), the heuristic (HeuristicSOL), and exhaustive enumeration-based solution, F ORM U LAT ION -I (ExhaustSOL). The resulting numerical results are reported in Table 6.4. When analyzing the numerical results, the rst remark is that even if it gives faster results for small size system, exhaustive enumeration-based solution is not viable for large size systems (n ≥ 20). The exact algorithm provides good results, for n = 25 the exact solution is found in approximatively 13 minutes. However, when the number of retailers becomes too large, the algorithm needs more than one hour to give the exact solution. We should note that in this chapter, we are dealing with the basic exact solution which is a mixed-integer linear program. This solution can be easily improved by using the wide mixed-integer programming literature. This was not possible when dealing with the square-root and fractional form of the problem. The heuristic solutions gives very encouraging results. On the one hand, the mean value of the prot gap does not exceed (3%) and a maximal gap of about (4%), on the other hand, the heuristic is too much faster than the exact solution. It requires less than one second time running while exact solution takes more than 700 seconds for higher instances.

Ecient Coalition Structure vs Optimal Coalition Structure

The focus of this section is to use a set of numerical studies to compare the ecient coalition (ECS) P we dened in this chapter, and the optimal coalition structure (OCS) P * , the coalition structure that optimizes the whole system. The comparison will be done according to two main criteria : the global prot ratio (π(P ) = v(P )

P i∈N C(i)
) and the number of coalitions in each coalition structure(|P |). The resulting numerical results are reported in Table 6.5. We should note that in column (∆(P * -P )), we give the gap between optimal coalition structure's criteria and that of the ecient coalition structure. That is, ∆ π = π(P * ) -π(P ) and

∆ |P | = |P * | -|P |.
On analyzing the numerical results, the rst point to note is that the average value of the gap prot does not exceed (5%), hence the ecient coalition structure does not signicantly aect the whole supply chain prot. By comparing the number of coalitions in both structures, one can easily see that the retailers are organized in many small size coalitions in the ecient coalition structure, while the optimal coalition structure is formed by a restricted number of large-size coalitions. This observation may has an interesting interpretation if one considers additional factors that are modelled such as cost and information exchange. Ecient coalitions are likely to be easier to form than optimal coalitions. That is, acting in a small coalition is often less costly than acting in a large one. Moreover, to cooperate, the dierent actors should coordinate their actions and exchange many information, that is often, condential information. Since we deal with totally independent retailers, it seems obvious that in this case the smaller is the number of cooperating actors fewer are the barriers to cooperate. As a result, the ecient coalition structure provides strong incentives for the retailers to cooperate.

Conclusion

In this chapter, we are concerned with alliance formation and cost allocation issues in a one supplier multiple-independent-retailer joint replenishment system. We show that research aiming at optimizing the whole (full cooperative approach) supply chain may present some drawbacks and is not appropriate for our n-independent retailers cooperative game. In our analysis, we focus on a supply chain where cooperation cannot be forced, i.e, each retailer joins the coalition he/she desires. We propose to build the dierent coalitions in a completely independent manner privileging individual coalition's performance to that of the global system. We presented an iterative procedure to form such coalitions and focused on analyzing the merits of such achieved ecient coalition structure.

The ecient coalition structure does not signicantly aect the global supply chain performance and has the merit to guarantee a set of stability notions. That is, under cost-based proportional rule, the retailers within the same coalition will get equal prot ratios. This makes the ecient coalition structure immune to individual-retailer deviations. That is, no retailer would leave his/her coalition to join another existing one. When analyzing group deviations, we

show that no group of retailers members of the same coalition will defect from their coalition and we provide some conditions and analysis under which the strong stability, i.e, the stability in the sense of the coalition structure core, holds. Equal prot ratio allocation and coalitions interdependency are then showed to provide strong incentives for the retailers to cooperate. Our last contribution was to analyze the afore-described coalition formation procedure from a computational complexity point of view. The procedure in its general form is based on exhaustive enumeration, which is not a viable optimization method except for small size systems. An interesting heuristic solution and a Polynomial-Time exact algorithm were provided. This exact solution was mainly based on 0-1 fractional programming techniques.

Motivated by the results we obtained in this chapter, we tempt in the following chapter to extend the notions of ecient coalitions to more general models. However, in addition to consider general cost functions, the model we will provide diers in the formal representation of the game and the analysis of the cooperation. We mainly, suppose that the cooperative game will be dened by a preference relation prole that species for each retailer his/her preferences to the coalition he/she desires.

Chapter 7

Stability of Hedonic Joint

Replenishment Games with General Cost Function : Application to one-supplier multi-retailer joint replenishment systems with full

Truckload shipments

In this chapter we analyze cooperative behavior questions in joint replenishment systems with general cost function. Using the notions of preference relations (each actor has his own preferences among the coalitions to which he could belong), we give a new formal representation of the cooperative game -called Hedonic Game. This mainly allow us to discuss the issue of treating the questions of alliance formation and prot allocation simultaneously. We show that under cost-based proportional allocations and equal allocations, there always exist at least two "ecient" coalition structures that are individually and weakly stable and may be strongly stable under some assumptions. Further, we apply this general approach to a FTLJRP-game with three components cost structure (xed and variable transportation cost and holding cost).

Introduction

As stressed in the previous chapters, the questions related to cooperative behavior in supply chain networks as well as in general social networks concern the interdependent problems of alliance formation and prot allocation. The aim of this chapter is to discuss a general approach that address both questions simultaneously. This work is motivated by the lack of prior attention to this research area in general. To the best of our knowledge, the wide literature on cooperative games in supply chain management as well as in multi-agent management systems (see Sandholm et al. (1999)) does not investigate both cooperative behaviors simultaneously.

To discussed the issue of generating stable coalition structures in inventory games with general cost function, we based our analysis on the principles of hedonic cooperative games. In this theory, the outcome of a given actor is totaly determined by the identity of the other members of his/her coalition. This class of cooperative games is formally dened by a pair (N, P), where

N = {1, 2, ...,
N i = {S ⊆ N : i ∈ S}.
The main idea of hedonic games is the partitioning of a society into coalitions where each player's payo is completely determined by the identity of other members of his/her coalition [START_REF] Bogomolnaia | The stability of hedonic coalition structures[END_REF][START_REF] Hajduková | On coalition formation games[END_REF].

In this chapter, we consider the hedonic settings to study the formation of stable coalition structures in inventory games with general cost function. In particular, we consider a set of rms/retailers N = {1, 2, ..., n}. The rms may form coalitions to achieve some savings. We assume that rms' preference relations are completely determined by the payo (the portion of savings) that they would gain in each potential coalition. Therefore, each rm would like to join the coalition oering the highest prot portion. However, to join this coalition, this rm should make all the members of the coalition in question better o, otherwise they would not accept his/her membership. Even though the rm makes all other members better o, this do not guarantee that this coalition will be formed as it may not be the "most preferred" coalition for some rms. Thus, the "ideal" situation is that a set of rms form a coalition that is "the most preferred" coalition for each one of them. In this case there will be no reason for one or more rms to defect from this coalition. Such coalition will be referred to as ecient coalition.

However, the existence or not of such "ecient" coalitions is closely related to the preference relation which is itself determined by the allocation rule used to split the achieved savings. Our interest in this chapter -considering general cost functions-is to determine whether there exists some allocation rules under which, when rms freely interact form "ecient" coalitions. Our convenience we will use the term rm interchangeably with the term retailer), denoted by N = {1, 2, ..., n}. Retailers place orders to a single supplier to satisfy customer demands. The cost of the optimal inventory replenishment policy of a retailer i working individually (the minimal cost that retailer i can achieve by himself/herself) is denoted C(i). When an alliance is to form, i.e., when a set of retailers , S, decide to cooperate and manage their inventories together by making joint orders, the cost of the optimal inventory replenishment policy of coalition S (the minimal cost that the retailers in S can achieve when they operate jointly without the retailers outside coalition S) is denoted C(S). The incentives to cooperate are not specied here and may include benets from economies of scale oered by the supplier or/and savings generated by a resources mutualization etc. As mentioned above we develop here a general approach (the results can be applied not only for JRP-games but also to general cooperative situations). Therefore the cost function, C, is a general function that not need to have special proprieties like concavity, convexity or superadditivity.

To evaluate whether a coalition is protable or not, we need to compare the cooperative situation to the decentralized situation/ the standalone situation where each rm is working individually. To achieve this goal, we let Ω be the space of the 2 n -1 possible non-empty coalitions in N and let v a savings function dened as follows:

v : Ω -→ R S v(S) = ( i∈S C(i) -C(S)) (7.1)
Denition 22 A coalition S is protable if and only if it has a positive worth (v(S) ≥ 0).

The saving function describes for each coalition of rms, S ∈ Ω, the maximal worth v(s) that they would divide among themselves if they were to cooperate together and with no rm outside S. The standalone situation where each retailer works on its own constitutes -by construction of function vthe situation of reference. For this reason, the worth of single coalition is null, i.e, i ∈ N, v(i) = 0.

The Game

Most of this section is based on the papers of [START_REF] Bogomolnaia | The stability of hedonic coalition structures[END_REF][START_REF] Hajduková | On coalition formation games[END_REF]. Let P be the nite set of coalition structures. The n-person cooperative game we are concerned with may be dened by the tuple (N, v, P ) where N = {1, 2, ..., n} is the set of rms (the players), P = {S 1 , ..., S m } is any coalition structure and v the characteristic function of the game is the savings function dened above (equation (7.1)). We should remember that the savings of a given coalition structure P = {S 1 , ..., S m } is the sum of the savings of the coalitions forming it, v(P ) = i=m i=1 v(S i ). In this model, we consider purely hedonic settings, that is each retailer's payo is completely determined by the identity of the other members of his/her coalition. Formally, each retailer is supposed to have his/her own preferences over coalitions to which he/she could belong. Let us denote by R = ( 1 , 2 , ..., n ) the preference prole, specifying for each retailer i ∈ N his/her preference relation i ,i.e., a reexive, complete and transitive binary relation on set N i = {S ⊆ N : i ∈ S}. In this model, retailer's preferences are related to the payo that this retailer will get in each coalition. Thus, if we denote by ϕ(S, i) the expected worth of retailer i in coalition S, S ∈ N i , asserting that retailer i prefers coalition S to coalition T is equivalent to asserting that his/her corresponding savings is higher in coalition S than in coalition T , i.e.,

S, T ∈ N

i : S i T ⇐⇒ ϕ(S, i) ≥ ϕ(T, i)
Strict preference relations and indierence relations of a player i are respectively denoted by i and ∼ i . Retailer i strictly prefers coalition S to coalition T , means that his/her payo in coalition S is strictly higher than his/her payo in coalition T , i.e.,

S, T ∈ N

i : S i T ⇐⇒ ϕ(S, i) > ϕ(T, i)
Finally, indierence relations mean that retailer i's payo is equal in both coalitions S, T , i.e,

S, T ∈ N

i : S ∼ i T ⇐⇒ ϕ(S, i) = ϕ(T, i)
Formally, the game in coalition structure (N, v, P ) may now be dened as a hedonic game dened by the couple (N, R). However one can wonder how to dene the payo allocation function ϕ(., .). In keeping with the notions of stability our aim in what follows is to answer simultaneously cooperative behavior questions of alliance formation and prot allocation. In other words, we are looking for an algorithm, which for any hedonic game (N, R) nds a stable partition. This is equivalent to say, given a xed allocation rule, we are looking for an algorithm that builds a stable coalition structure.

Stable Hedonic Coalition Structures Generation

Given an allocation rule ϕ(., .), or equivalently a preference prole R, our focus is to study the outcome of the hedonic coalition formation game.

As dened above, rms' preferences are directly related to the prot portion that will be allocated to each rm in each coalition. Thus rm i prefers joining coalition S than coalition T only if its payo in coalition (S ∪ {i}) is higher that its payo in coalition (T ∪ {i}), i.e., (S ∪ {i} i T ∪ {i} ⇐⇒ (ϕ((S ∪ {i}), i) ≥ ϕ((T ∪ {i}), i)). However, to concretely join coalition S, it is not sucient that rm i prefers coalition S to T . It is necessary that all the members of coalition S agree to accept rm i. In earlier cooperative game theory works, it was assumed that it is sucient that at least one member of coalition S is better o and the others are not worst o, to guarantee the acceptance of rm i's membership. In other cases, retailer i's membership will be accomplished even when the members of coalition S are not worst o (each one of them wins at least as much as without player i). In our context, since the rms are independent and the preference criterion is based on the expected worth, we nd it reasonable to say that the members of coalition S will accept the membership of rm i only when this will make each one of them "strictly" better o. In this case, coalition S is called a feasible coalition for rm i, and the set of all feasible coalitions for a rm i is denoted by N f i .

Denition 23 : A coalition S, S ∈ N i is a feasible coalition for rm i if rm i can join coalition S such feasible move is denoted i S. This means that rm i prefers coalition S at least than staying alone and all the members of coalition S will be strictly better o when rm i joins their coalition. Formally,

i S ⇐⇒    (S ∪ {i}) i {i} (S ∪ {i}) j S, ∀j ∈ S (7.2)
Since each retailer is principally interested in his/her own prot, it is easy to expect that he/she would like to join the coalition guarantying the maximum worth. In other words, each retailer would like to join his/her most preferred coalition

S ,i ∈ N f i such that ∀T ∈ N f i , S ,i i T (7.3)
Above, we discussed the way the "game" can be played from only one player's (retailer) point of view. Therefore, even if coalition S ,i is the most benecial (and feasible) coalition for retailer i this do not mean that this coalition will be formed, because obviously coalition S ,i may not be the most preferred coalition for the other (one or more) coalition's members. So the "ideal" is to nd a coalition that is the best (the most preferred) coalition simultaneously for all its members, such coalition will be referred to as an ecient coalition.

Denition 24 : A coalition S is an ecient coalition only when it is the most preferred coalition to each one of its members, S is ecient ⇐⇒ ∀i ∈ S , ∀T ∈ N f i ; S i T (7.4) Proposition 7.1 Each ecient coalition is "saturated" in the sense that the adhesion of new members is not accepted.

Proof: Considering an ecient coalition S and a player j outside S (j ∈ S ), by construc- tion coalition S is the most preferable coalition for all its members, therefore, ∀i ∈ S , S i (S ∪ {j}).

Another interpretation of the above proposition is that when S is an ecient coalition, no player outside S can join it because this will make him/her worse o or will make coalition S 's members worse o. Thus, the worth of each rm inside the ecient coalition is completely dependent by the identity of its other partners without the implication of rms or coalitions outside this coalition.

It is easy to remark that the ecient coalitions are disjoint (by construction). In what follows, the focus will be to address the proprieties of the ecient coalition structure P = {S 1 , S 2 , ..., S m } referring to the partition that holds when each rm joins its ecient coalition.

However, before moving to this discussion, some natural questions about the ecient coalitions need to be answered. For instance, do the ecient coalitions always exist? If not, what are the conditions under which their existence is guaranteed? And how to nd or to build such coalitions?

The concept of ecient coalitions have been dened through players' preferences relations.

These preference relations were themselves directly related to the prot portion expected by each player. Therefore, the existence or not of ecient coalitions cannot be studied separately from the allocation rule used to dene the preference relations prole. In what follows, we show that ecient coalitions exist at least for two allocation rules; Equal allocations and Proportional allocations. Only both of these allocations will be considered over the rest of the chapter.

Denition 25 : Proportional allocations

The proportional allocation rule distributes the rewards proportionally to the standalone costs. A rm i, member of coalition S will receive the worth

ϕ P (S, i) = C(i).v(S) j∈S C(j)
S ,P i = argmax S⊆(N \∪ j=i-1 j=1 S ,P j ) {( v(S) j∈S C(j)
)}, S ,P i ∈ P ,P (7.6)

S ,E i = argmax S⊆(N \∪ j=i-1 j=1 S ,E j ) {( v(S) |S| )}, S ,E i ∈ P ,E (7.7)
After describing the formation of ecient coalitions, the focus in the rest of the chapter is twofold. First we will analyze the above structures from a cooperative game point of view and secondly, we will compare both partitions.

The characterization of ecient coalitions was dened through rms' preference relations.

Thus, it may be easy to see that at the individual level each rm will be satised to be in its ecient coalition (its most preferred coalition). When extending this analysis to a group of rms, we remark that any sub-set of rms (within the same ecient coalition) feel that acting in ecient coalition is worthwihle for its own sake and therefore will not defect to form a separate coalition. In keeping with cooperative game theory principles, we can conclude that any ecient coalition is core stable.

Theorem 7.2 The core of any ecient coalition is non-empty.

Proof: To prove this theorem we should show that the core of any coalition in P ,P , or in P ,E is non-empty. Without loss of generality, let us consider, S ,P

, i) = i∈T C(i). v(S ,P 1 ) j∈S ,P 1 C(j) ≥ v(T )
Because by construction of S ,P 1 we have

v(S ,P 1 ) j∈S ,P 1 C(j) ≥ ( v(T ) j∈T C(j)
) based proportional rule is the allocation used in the system and let us focus on the stability of P ,P . Since we know that the proportional rule ensures the weak stability of P ,P , studying the strong stability is equivalent to studying the possible moves of rms that are members of at least two distinct coalitions. Thus, we should show that such a sub-coalitions cannot be formed.

Let T be a group of rms members of dierent coalitions. That is, there exists a set of coali-

C(j) ) ≥ ( v(T ) P j∈T C(j)
), otherwise coalition S ,P k is not satisfying the criteria of eciency and coalition T would be an ecient coalition, which is not the case. With these introduced proprieties, let us look to the the sub-coalition T = T ∩S ,P k . These rms if they were to deviate from their coalition S ,P k to coalition T , the worth of each one of them will decrease because, ϕ P (S ,P k

, i) = C(i).( v(S ,P k ) P j∈S ,P k C(j) ) ≥ ϕ P (T, i) = C(i).( v(T ) P j∈T C(j) )
. Consequentially, coalition T cannot be formed. As mentioned above, the proof is the same when we consider equal allocation.

Complexity Analysis

In this section, our aim is to highlight the computational complexity of generating coalition structures P ,P and P ,E . As mentioned in equation (7.6,7.7), the formation of coalitions structures P ,P and P ,E implies solving the respective optimization problems,

S ,P i = argmax S⊆(N \∪ j=i-1 j=1 S ,P j ) {( v(S) j∈S C(j) )} and S ,E i = argmax S⊆(N \∪ j=i-1 j=1 S ,E j ) {( v(S) |S| )}
Of course, since the solution of each one of the above optimization problems is only one ecient coalition, the procedure should be repeated until partitioning all the rms in coalitions. The worst case is to select coalitions containing only two rms for all steps. In this case n 2 iterations are needed for partitioning all the rms.

To nd the most ecient coalitions S ,P 1 and S ,E 1 , the space of all possible coalitions is explored. However, in a system of n rms, there are (2 n -1) possible coalitions. This number doubles with each rm added to the system. Therefore, when we deal with a large number of rms, there will be too much possible coalitions to allow exhaustive search for the most ecient ones. Both problems of generating ecient coalition structures P ,P and P ,E are with exponential complexity. At this level of the study, we cannot provide a solution for this exponential complexity; Any solution would be closely related to the form of the cost function C. Up to this level, we are dealing with general functions however, we would like to outpoint the fact that both optimization problems include functions in ratio forms. This makes the traditional linear programming theory unusefull, and we think that fractional programming theory is more appropriate here.

Comparisons

After discussing the main proprieties of coalition structures P ,P and P ,E from both cooperative game theory and computational point of views, the next natural question to be asked is how to compare these coalitions structures. We should note that with the use of cooperative game theory the quality of any coalition structure is quite often evaluated to its stability. However, in the current work both coalition structures full the same stability proprieties. To compare coalition structures P ,P and P ,E we should include more criteria and ask other questions, for instance: Do rms prefer one coalition structure to another? Does one of the two partitions contains more coalitions or is more protable than the other?

As one can expect, it is impossible to answer the above questions in the current general form of the cooperative game. To achieve our goal, we need to apply the afore-described results in an example of supply chain game with an explicit cost structure. This will be our focus in the rest of the chapter. We will consider both scenarios in a one-supplier multi-retailer full truckload shipments joint replenishment game (FTLJRP-game). In the rst scenario the rms will form ecient coalition structure P ,P whereas in the second one coalition structure P ,E will be considered. Since the questions of stability and gains splitting are valid in the general case, we will mainly investigate two topics : (1) The algorithmic question of generating the ecient coalitions, and (2) the comparison of the two scenarios.

7.4 Application: One-Supplier Multi-Retailer Full TruckLoad Shipments Joint Replenishment Game (FTLJRP-Game)

Model Description and Notations

We consider the issue of generating the afore-studied coalition structures P ,P and P ,E Single-Supplier Multi-Retailer Full Truckload Shipments Joint replenishment Game (FTLJRP-Game).

This )) can be stated as follows: A number of independent retail facilities, N = {1, ..., n}, faces known demands, D i , of a single product -characterized by a volume (or a weight) V i -over an innite planning horizon. They order goods from the same external supplier. All shipments from supplier's warehouse to retailers are direct full truckload shipments, all trucks have the same capacity limit called CAP . There are a xed ,A, and a variable ,G i , costs per truck dispatched from the supplier to retailers, and linear holding costs at the retailers' warehouses. The cost of holding one unit of product per unit of time at retailer i is h i . For simplication, we let H i = h i .D i 2 be the holding cost parameter of retailer i. All costs are stationary costs; i.e., the xed and variable transportation charges and the linear holding costs do not change over time. Both of transportation costs and linear inventory holding costs involved by products' storage are supported by the retailer. Each time a full truckload delivery is requested by a retailer i, a xed ordering cost A is charged. In addition a retailer-dependent cost G i , called individual cost is supported. When a group of retailers form an alliance S, by joining their orders as a single large order, they will pay only one ordering cost A for the full truck shipment while all individual costs will be kept (See Figure (7.1(b))). This means that the delivery cost will be A + i∈S G i . When ordering jointly, the common ordering cycle time is denoted by T S and the corresponding frequency is denoted by N S . The EOQ (Economic order quantity) is used as a reorder policy. The notations and parameters of the model are summarized below:

One-Supplier Multi-Retailer Full TruckLoad Joint Replenishment Games

• N = {1, ..., n}: The set of retailers.

• D i : The deterministic demand of retailer i ∈ N .

• G i : The individual ordering cost of retailer i ∈ N .

• h i : The holding cost per time unit of retailer i ∈ N .

• V i : The volume/ weight of product i associated to retailer i ∈ N .

• A: The xed ordering cost.

• CAP: The vehicle capacity.

• T i : The ordering cycle time of retailer i ∈ N .

• N i : The ordering frequency of retailer i ∈ N .

• Q i : The order size of retailer i ∈ N .

• H

i = h i .D i 2 :
The holding cost parameter of retailer i ∈ N .

• C(i): The average total cost per time unit of retailer i ∈ N .

• T S : The ordering cycle time of coalition S, ∅ ⊂ S ⊆ N .

• N S : The ordering frequency of coalition S, ∅ ⊂ S ⊆ N .

• C(S): The average total cost per time unit of coalition S, ∅ ⊂ S ⊆ N .

When ordering alone, the optimal replenishment strategy for a retailer i is to order a full truck corresponding to the quantity

Q i = CAP V i every T i = Q i D i = CAP V i .D i unit of time.
The corresponding ordering frequency is then :

N i = V i .D i CAP .
Retailer i charges a total delivery cost of (A + G i ).N i plus a total holding cost (h i .Q i /2). Consequentially the total average cost of retailer i equals

C(i) = (A + G i ).N i + h i .Q i 2 . Since N i = D i Q i , rewriting C(i)
as a function of the frequency N i gives :

C(i) = (A + G i ).N i + H i N i , and N i = V i .D i CAP .∀i ∈ {1, ...,
(S) = (A + i∈S G i ).N S + P i∈S h i .Q i 2
. Expressing the order size Q i as a function of N S leads to :

Q i = D i N S .
The total average cost of coalition S is then expressed as follows:

C(S) = (A + i∈S G i ).N S + i∈S H i N S = (A + i∈S G i ). i∈S N i + i∈S H i i∈S N i , ∅ ⊂ S ⊆ N (7.10)
(A + G i ).N i (A + P i∈S G i ). P i∈S N i - P i∈S P j∈S,i =j G i .N j Holding costs P i∈S H i N i P i∈S H i P i∈S N i + P i∈S H i N i - P i∈S H i P i∈S N i
Now to discuss whether it is interesting or not for a given set of retailers to cooperate we should compare the cost in the cooperative situation, C(S) to that in the standalone (decentralized) situation i∈S C(i). As summarized in Table (7.1), on the one hand the cooperative situation leads to a rise in the delivery costs due to the increase of the individual costs charge increase, on the other hand the holding costs in the cooperative situation are lower than the stand alone situation. Protability is then not guaranteed for all possible coalitions. To be protable, a given coalition should satisfy the propriety of proposition (7.2).

Proposition 7.2 A non-empty coalition S ⊆ N is only protable when the individual cost raising is balanced by the holding cost decrease.

C(S)

≤ i∈S C(i) ⇐⇒ i,j∈S,i =j G i .N j ≤ i∈S HD i N i -i∈S HD i i∈S N i A direct consequence of proposition (7.
2) is that the merging of two or more coalitions into one coalition does not guarantee a total cost decrease. Consequentially, the grand coalition may be non-protable: The game is non-superadditive.

In the rest of the chapter the aim will be to study the following games with coalition structures: (N, v, P ,P ) and (N, v, P ,E ). Where N is the rms, v is the savings function.

v : Ω -→ R S v(S) = ( i∈S C(i) -C(S)) (7.
S ,E i = argmax S⊆(N \∪ j=i-1 j=1 S ,E j ) {( v(S) |S| )}, S ,E i ∈ P ,E
The rest of the chapter is organized as follows. First, the aim will be to study the optimization problems of ecient alliance formation. Particularly, we will focus on solving the following optimization problems:

S ,P 1 = argmax S⊆N {( v(S) j∈S C(j) )} and S ,E 1 = argmax S⊆N {( v(S) |S| )}
Once alliance formation problems are solved, we used a set of numerical tests to compare both coalition structures.

Scenario 1 : Coalition Structure P ,P

The proposal of this section is to provide an exact solution for searching for the ecient coalition structure P ,P . As explained above, we will focus on the optimization problem of generating the most ecient coalition:

S ,P 1 = argmax S⊆N {( v(S) j∈S C(j)
)} (7.12) Proposition 7.3 : Maximizing the prot ratio is equivalent to minimize the ratio of the coalition's cost to its corresponding decentralized cost:

S 1 = argmin S⊆N ( C(S) i∈S C(i) ) (7.13) Proof: S 1 = argmax S⊆N ( P i∈S C(i)-C(S) P i∈S C(i) ) = argmax S⊆N (1-C(S) P i∈S C(i) )= argmin S⊆N ( C(S) P i∈S C(i) ).
In what follows, for simplicity, we will consider the minimization problem (7.13). The ratio

C(S) P

i∈S C(i) will refer to us as the cost ratio and will be denoted by CR(S).

The optimization problem (7.13) may be formulated as the following linear program. The decisions variables X j address the selection of one coalition from all possible 2 n -1 coalitions. In order to linearize the objective function (7.17), let us dene two new variables R and T such that:

T = 1 n i=1 C i .Y i and R = 1 n i=1 n j=1 N i .C j .Y i .Y j (7.20)
This denition is equivalent to:

n i=1 C i .Y i .T = 1 and n i=1 n j=1 N i .C j .Y i .Y j .R = 1 (7.21)
With the newly introduced variables R and T , formulation (F.II) can be rewritten as : In this section, we aim at studying the second scenario where the ecient coalition structure P ,E is to form. Similarly to the previous section, the focus will be on the following optimization problem

(F.III) min A. n i=1 N i .Y i .T + n i=1 n j=1 N i .G j .Y j .Y i .T + n i=1 H i .Y i .R (7.22) n i=1 Y i ≥ 1 (7.23) n i=1 C i .Y i .T = 1 (7.24) n i=1 n j=1 N i .C j .Y i .Y j .R = 1 (7.25) Y i ∈ {0, 1}, ∀i = 1, 2, ...,
N i .T ii + n i=1 n j=1 N i .G j T ij + n i=1 H i .R i (7.27) n i=1 Y i ≥ 1 (7.28) n i=1 C i .T ii = 1 (7.29) n i=1 n j=1 N i .C j .R ij = 1 (7.30) T -T i,j ≤ (2 -Y i -Y j ), ∀i = 1, 2, ..., n, ∀j = 1, 2, ..., n (7.31) T ij ≤ T, ∀i = 1, 2, ..., n, ∀j = 1, 2, ..., n (7.32) T ij ≤ Y i , ∀i = 1, 2, ..., n, ∀j = 1, 2, ..., n (7.33) T ij ≤ Y j , ∀i = 1, 2, ..., n, ∀j = 1, 2, ..., n (7.34) T ij ≥ 0, ∀i = 1, 2, ..., n, ∀j = 1, 2, ..., n (7.35) R -R i,j ≤ (2 -Y i -Y j ), ∀i = 1, 2, ..., n, ∀j = 1, 2, ..., n (7.36) R ij ≤ T, ∀i = 1, 2, ..., n, ∀j = 1, 2, ..., n (7.37) R ij ≤ Y i , ∀i = 1, 2, ..., n, ∀j = 1, 2, ..., n (7.38) R ij ≤ Y j , ∀i = 1, 2, ..., n, ∀j = 1, 2, ..., n (7.39) R ij ≥ 0, ∀i = 1, 2, ..., n, ∀j = 1, 2, ..., n (7.40) n i=1 Y i ≥ 1 (7.41) Y i ∈ {0, 1}, ∀i = 1,
S ,E 1 = argmax S⊆N { v(S) |S| } (7.43)
The optimization problem (7.43) may be formulated as the following linear program. The decisions variables X j address the selection of one coalition from all possible (2 n -1) coalitions.

X j =    1 : if coalition j is selected 0 : otherwise F E.I : max 2 n -1 j=1 v(S j ) |S j | .X j (7.44) 2 n -1 j=1 X j = 1 (7.45) X j ∈ {0, 1}, ∀j = 1, 2, ..., 2 n -1 (7.46)
We use the same technique in the previous section to reformulate the problem into 0-1 fractional program that we linearize in a second time. To achieve the 0-1 fractional program we dene the following new decision variables:

Y i =    1 : if retailer i is in coalition S 0 : otherwise
Expressing the objective function (7.44) with the newly added decision variables Y i gives the following result:

v(S) |S| = n i=1 ( H i N i ).Y i n i=1 Y i - n i=1 H i .Y i n i=1 n j=1 N i .Y i .Y j - n i=1 n j=1,j =i N i .G j Y i .Y j n i=1 Y i
Rewriting the problem (F E.I) with the new form of the objective function gives :

F E.II : max n i=1 ( H i N i ).Y i n i=1 Y i - n i=1 H i .Y i n i=1 n j=1 N i .Y i .Y j - n i=1 n j=1,j =i N i .G j Y i .Y j n i=1 Y i (7.47) n i=1 Y i ≥ 1 (7.48) Y i ∈ {0, 1}, ∀i = 1, 2, ..., n (7.49)
The objective function is represented by constraint (7.47). The constraint (7.48) ensures that the selected coalition is non-empty. The binary decision variables Y i are represented by constraints (7.49). In order to linearize the objective function (7.47), we dene two new variables R and T such that:

T = 1 n i=1 Y i and R = 1 n i=1 n j=1 N i .Y i .Y j (7.50)
This denition is equivalent to:

n i=1 Y i .T = 1 and n i=1 n j=1 N i .Y i .Y j .R = 1 (7.51)
With the newly introduced variables R and T , formulation (F E.II) can be rewritten as :

F E.III : max n i=1 ( H i N i ).T.Y i - n i=1 H i .Y i .R - n i=1 n j=1,j =i N i .G j .T.Y i .Y j (7.52) n i=1 Y i ≥ 1 (7.53) n i=1 Y i .T = 1 (7.54) n i=1 n j=1 N i .Y i .Y j .R = 1 (7.55) Y i ∈ {0, 1}, ∀i = 1,
( H i N i ).T ii - n i=1 H i .R ii - n i=1 n j=1,j =i N i .G j .T ij (7.57) n i=1 Y i ≥ 1 (7.58) n i=1 T ii = 1 (7.59) n i=1 n j=1 N i .R ij = 1 (7.60) T -T i,j ≤ (2 -Y i -Y j ), ∀i = 1, 2, ..., n, ∀j = 1, 2, ..., n (7.61) T ij ≤ T, ∀i = 1, 2, ..., n, ∀j = 1, 2, ..., n (7.62) T ij ≤ Y i , ∀i = 1, 2, ..., n, ∀j = 1, 2, ..., n (7.63) T ij ≤ Y j , ∀i = 1, 2, ..., n, ∀j = 1, 2, ..., n (7.64) T ij ≥ 0, ∀i = 1, 2, ..., n, ∀j = 1, 2, ..., n (7.65) R -R i,j ≤ (2 -Y i -Y j ), ∀i = 1, 2, ..., n, ∀j = 1, 2, ..., n (7.66) R ij ≤ T, ∀i = 1, 2, ..., n, ∀j = 1, 2, ..., n (7.67) R ij ≤ Y i , ∀i = 1,

Numerical Results and Comparisons

The focus of this section is to compare ecient coalition structures P ,P and P ,E . Using a set of numerical tests, we will discuss whether partition P ,P or P ,E diers by more coalitions or by a higher global prot rate.

We randomly generated the game's parameters. For instance, we used uniform distributions As mentioned above, the comparison between both coalition structures P ,P and P ,E will be done according to two criteria: the global prot ratio (π(P ) = v(P ) P i∈N C(i) , P ∈ {P ,P , P ,E }) and the number of coalitions in each coalition structure (|P |, P ∈ {P ,P , P ,E }). Our numerical results are reported in Table (7.4). We should note that in column (∆(P ,P -P ,E )), we compute the dierence between both coalition structure's criteria. That is, ∆ π = π(P ,P ) -π(P ,E ) and Consequentially, neither P ,P nor P ,E is a strictly dominating coalition structure. The analysis above does not take the individual preferences of rms into account. To determine whether rms prefer one coalition structure to the other one we should compare rms' worth in both structures.

∆ |P | = |P ,P | -|P ,E |.
In the ecient coalition structure P ,P , the savings are attributed proportionally to the standalone cost of each rm. As a result the value attributed to rm i member of coalition S ,P k is :

ϕ P (S ,P k , i) = C(i).( v(S ,P k ) j∈S ,P k C(j) ), S ,P k ∈ P ,P
The cost based proportional rule has the interesting propriety that the rms within the same coalition get the same prot ratio. For instance, the prot rate of a rm i in coalition S ,P k (the ratio of its allocated value to its standalone cost) is as follows:

Π(S ,P k , i) = ϕ P (S ,P k , i) C(i) = ( v(S ,P k ) j∈S ,P k C(j) )
Contrary to P ,P , in the ecient coalition structure P ,E , the savings are divided equally. It results that the rms within the same coalition gains the same portion of savings (in term of amount).

ϕ E (S ,E k , i) = ( v(S ,P k ) |S ,E k | ), S ,E k ∈ P ,E
In this case, the prot rate of a rm i member of coalition S ,E k is as follows:

Π(S ,E k , i) = ( v(S ,P k ) C(i)|S ,E k | )
To discuss whether it is better for rms forming an ecient coalition to have the same portion of savings or to have the same prot ratio, we consider in the following a 10-rm cooperative game and we compare the value allocated to each rm in both partitions P ,P and P ,E . The rms' parameters are reported in Table (7.5).

The outcome of the game is summarized in Table (7.6). Ecient coalition structure is P ,P = {{4, 5, 7}, {3, 6, 10}, {8, 9}, {1}, {2}} and ecient coalition structure is P ,E = {{3, 5, 7}, {4, 6, 10}, {1, 9}, {2, 8}}. In both partitions, coalitions are ranked by their order of formation (eciency).

We reported in Table (7.6) the worth of each rm: we reported the allocated savings portion (in one case the proportional rule is used while in the second case equal allocation is used) as well When observing the prot rate diagram below, we remark that neither P ,P nor P ,P is strictly better for all the rms. For instance, when moving from one scenario to the other some rms become better o, however, some others become worse o. To conclude, as discussed above both coalitions structures P ,P and P ,E seem to have the same proprieties. However, we need to be careful when interpreting these results. For instance, despite the apparent "fairness" in coalition structure P ,E , the portions of savings are completely independent of the contributions of the cooperating rms. As result, we think that equal allocation may lead to a situation where those who contribute more are not paid more. This would create "unsatised" rms and may thus constitute a motivation for the disbanding of the coalition structure.

Conclusion and Extensions

In this chapter, we discussed the issue of generating stable coalition structures in games with general cost function. We based our analysis on the principles of hedonic cooperative games. In this theory, the outcome of a given actor is totaly determined by the identity of the other members of his/her coalition. Moreover, the formal representation of such games is based on the so called preference prole that species for each actor his/her preferences among the coalitions he/she wants to belong to. In this work, we assumed that rms' preference relations are linked to the portion of savings that they would gain in each potential coalition. Therefore, each rm would like to join the coalition oering the highest prot portion. Such coalitions, when they exist, are called ecient. Our rst contribution was to show that when cost-based proportional rule and equal allocation rule are used to divide the total created value, the ecient coalitions always exist and satisfy a set of desirable proprieties. For instance, both of ecient coalition structures generated respectively with proportional allocation and equal allocation are stable in the sense of coalition structure core. Further, we stressed the exponential complexity of generating such ecient coalition structures.

Our second contribution was to apply the notions that we developed for general models to some concrete joint replenishment games. To achieve this goal, we consider a non-superadditive joint replenishment game with full truckload shipments. Since the question of forming the ecient coalitions as well as the question of prot allocation are valid in the general case, in the studied FTLJRP-game, we mainly provided a polynomial algorithmic solution to generate the coalitions.

Then, using a set of numerical results, compared both coalition structures. We showed that in these games no partition dominates the other. Nevertheless, we warned that equal allocations may lead to "unsatised" rms, because such allocation ignore rms' contributions.

Finally, future research on this topic could be aimed at answering the question of whether there exist some other allocation rules that guarantee the existence of ecient coalition structures. We think that the allocations based on marginal contributions such as Shapley value and marginal contribution-based proportional allocation do not full this propriety. We believe that it will be a very interesting contribution to show whether the cost-based proportional allocation and equal allocation are the unique rules that guarantee the existence of ecient coalitions. Another interesting extension of this work is to analyze the issue of considering coalition structures with mixed allocation rules, i.e., the rms express their preference relations according to dierent allocation rules. We should note that in this model as well as in the theory of games it-self a coalition structure is always assumed to apply the same allocation rule. Even though it will be a dicult problem from theoretical point of view, we believe that investigating such research direction will provide relevant methods to understand real-world cooperative structures.

Above, we detailed some extensions closely related this chapter's work. In the following chapter, the focus will be to emphasis more general research directions in the issue of analyzing the cooperation by means of cooperative game theory. that around one third to two thirds of the expenses of companies' logistics costs are spent on transportation [START_REF] Tseng | The role of transportation in logistics chain[END_REF][START_REF] Pimor | Logistique: Production, Distribution, Soutien[END_REF]. Motivated by the transportation decisions' critical role we think that it would be worth investigating cooperative situations with explicit transportation costs. The term "explicit" here refers to the inclusion of parameters such as, distance, vehicles' greenhouse gas emissions, vehicle capacity, etc. Even if it seems to be an interesting research topic, involving transportation decisions in supply chain games rises several challenging questions, for instance : What would be the value that transportation costs bring into inventory games? Which transportation cost function to include? What would be its impact on the games' structures and properties?

The answer to the rst question is intuitive, for instance the added value of considering transportation costs in inventory cooperative games is twofold. First, more practical situations can be modelled and more supply chain eciency can be realized. Second, including explicit transportation costs would allow us to model other cooperative behavior outcomes as well as new supply chain trends, such as green issues. The trend towards developing a green supply chain is now gaining popularity. Consumer are becoming more and more sensitive to the quality and protection of the environment. As a result, they are being more careful about products environmental labelling and carbon footprints in supply chains. To full customers' needs, managers are being compelled to consider the most ecient and environmentally friendly way to deal with transportation. In this context, mutualization of transportation resources seems to be a valuable way to help rms to cut the environmental impact of their supply chains.

Before giving some insights in the other questions, we would like to mention that even in the buyer-supplier contracting literature, few are the studies that explicitly consider transportation costs and their impact on channel coordination. See for example, [START_REF] Toptal | Generalized models and benchmarks for channel coordination[END_REF][START_REF] Toptal | Generalized models and benchmarks for channel coordination[END_REF]Çetinkaya, 2004, 2006). A detailed study on transportation functions and their impact on channel coordination and contractual agreements is found in [START_REF] Mutlu | The transporter's impact on channel coordination and contractual agreements[END_REF].

Some Transportation Cost Functions

Now let us focus on the transportation cost function and impacts on inventory games. In the literature, there are mainly two traditional transportation cost functions (many hybrid forms exist). In the rst structure, the delivery is made by a number of trucks (the number of trucks is not often a constraint), each with a certain capacity P and a xed operating cost R T . Hence, letting Q the quantity ordered by a given retailer, the truck cost is Q P R T . Often a per unit transportation cost denoted by c T is considered. As a result, the total cost for carrying Q units of product is

Q P R T + c T .Q (8.1)
The second classic transportation function's form is to include the notion of distance. Letting In particular, we consider a distribution system where a set of retailers may order a single product from a unique supplier to satisfy a deterministic and constant rate demand of nal customers. Each retailer, when ordering for a quantity of product, has to pay a xed ordering cost and a transportation cost. Moreover, the delivered products generate some holding cost.

The transportation cost is function of the distance separating the supplier from the retailer.

Retailers may choose to cooperate in order to realize some cost saving benets. In this case,

1 Extended versions of this analysis are: 1: El Omri, A. , Gaari, A., Jemai, Z. and Dallery, Y.(2007a). Multiple Retailers Cooperation For Joint Transportation and Inventory Decisions. Proceedings of 19th International Conference on Production Research (ICPR19), Valparaiso, Chili. 2: El Omri, A. , Gaari, A., Jemai, Z. and Dallery, Y.(2007b). La théorie des jeux pour la modélisation dun problème de coopération multi-clients. Proceedings of FRANCORO/ROADEF07, Grenoble, France they make joint orders and to minimize the transportation costs, retailers are delivered during the same truck trip, that we model as a travelling salesman tour. To summarize the model, each retailer i is assumed to face a deterministic, constant demand rate denoted by D i . The cost of holding one unit of product per unit of time at this retailer is h i . We assume identical and constant lead times, without loss of generality, assumed to zero. Each time a delivery is requested by a retailer i, a xed ordering cost A is charged. Moreover, the retailer is supposed to pay a direct shipping cost which is two times the distance separating the retailer in question from the supplier d i,0 multiplied by a per distance-unit transportation cost, δ T . The EOQ (Economic order quantity) is used as a reorder policy. The model's notations are summarized below:

• N ={1,...,n}: The set of retailers, {0} refers to the supplier.

• D i : The deterministic demand of retailer i ∈ N .

• h i : The holding cost per time unit of retailer i ∈ N .

• A: The xed ordering cost.

• d ij : The distance separating two locations i and j, where i, j ∈ N ∪ {0}.

• Q i : The order size of retailer i ∈ N .

• C(i): The average total cost per time unit of retailer i ∈ N .

• T i : The ordering cycle time of retailer i ∈ N .

• m i : The ordering cycle time of retailer i ∈ N .

• T S : The ordering cycle time of coalition S, ∅ ⊂ S ⊆ N .

• m S : The ordering frequency of coalition S, ∅ ⊂ S ⊆ N .

Letting the Economic Order Quantity be the reorder policy, the total average cost per time unit paid by any retailer i ∈ N is the sum of his/her ordering cost, transportation cost and holding cost.

C(Q i ) = 2.δ T .d i,0 . D i Q i Transportation cost + A. D i Q i Ordering cost + h i .Q i 2
Holding cost

The minimization of the above expression gives us the optimal total average cost, C(Q * i ) noted C * (i) for seek of simplication: As one can easily remark, retailer 3 is quite far from the supplier and both of retailers 1 and 2 are not. For this reason, it is benecial for retailer 1 and 2 to operate jointly without retailer 3. The grand coalition {1,2,3} is then non protable (v({1, 2, 3}) = i=3 i=1 C * (i) -C * ({1, 2, 3}) = 720 -717 = -3). Therefore the protability is not guaranteed for all possible coalitions because in some cases, the ordering cost savings is exceeded by a rise in the transportation cost and/or in the holding cost. A necessary condition for the protability of a non-empty coalition S is as follows:

Proposition 8.1 Giving a group of retailers. If their respective standalone ordering frequency is increased when they were to cooperate together then their alliance is protable, i.e.,

If m * S ≥ m * i , ∀i ∈ S ⇒ C * (S) ≤ i∈S C * (i)
Proof: The optimal quantity of a retailer i in the standalone situation is

Q * i = D i m * i .
In the cooperative situation, the optimal quantity of a retailer i member of coalition S is

Q * S,i = D i m * S . m * S ≥ m * i , ∀i ∈ S ⇒ Q * S,i ≤ Q * i , ∀i ∈ S ⇒ i∈S h i .Q * S,i 2 ≤ i∈S h i .Q * i 2 .
In both optimal standalone or optimal cooperative situations, the holding cost equal the delivery (transportation + ordering) cost. Consequentially, i∈S

h i .Q * S,i 2 ≤ i∈S h i .Q * i 2 ⇒ (A + δ T .T SP (S)).m * S ≤ i∈S (A + 2.δ T .d i,0 ).m * i ⇒ C * (S) ≤ i∈S C * (i).
The above example shows that the game is a non-superadditive game and thus both coalitional behavior questions have to be answered here. To deal with the questions of alliance formation and prot allocation, one would think to apply the same procedure -generation of the Ecient Coalition Structure-as in chapter 6 or chapter 7. We think that doing so would be quite dicult because to generate an ecient coalition, we should solve the following optimization problem: S = argmin S⊆N { 2.(A + δ T .T SP (S)). i∈S D i h i 2.(A + 2.δ T .d i,0 ).D i h i } (8.5)

In addition to the complexity of the TSP problem itself, the square root and the fractional form of the function in equation (8.5) makes it probably dicult to nd a solution. We should mention that an optimization problem with a similar cost function is found in [START_REF] Sindhuchao | An integrated inventoryrouting system for multi-item joint replenishment with limited vehicle capacity[END_REF].

The authors studied an integrated inventory-routing system for multi-item joint replenishment system, they model the transportation cost as TSP function and then discussed the problem of partitioning the set of items in order to optimize the whole system. The problem is showed to be NP-hard and a branch-and-bound solution was provided.

Even if the coalition structure is given exogenously, the problem of nding a stable outcome will be as much hard as the optimization problem. Because, traditionally the problems of determining wether an allocation is in the core are computationally hard [START_REF] Nagarajan | Game-theoretic analysis of cooperation among supply chain agents: Review and extensions[END_REF] independently of the cost function. However, in the current problem the cost function itself is rather a complex function. To conclude, including explicit transportation cost would give us the opportunity to better model and understand more practical cooperative situations in supply chains. However the computational aspect of the resulting problems will be quite hard and needs high level computer science and operation research mastery.

Cooperative Games with Explicit Cost Formation Process

In this section, we are interested in emphasizing the consideration of the coalition cost process in cooperative supply chain games. Our aim is to discuss the following pair of questions, (1) How to model alliance formation's cost ? (2) Which are the inuences of such cost on the mathematic and strategic levels of traditionally inventory games? 2 In almost all supply chain games, the cost of coalition formation process was ignored. For instance, to the best of our knowledge, in supply chain management literature there is no paper that includes explicitly the cost of forming the alliances. However, when forming an alliance, there might be many coordination overhead like communication costs or third-logistic-provider cost when the alliance is managed by a third logistic party. Obviously, it is unreasonable assumption to consider a xed cost per coalition because it is critical that the coalition cost formation should reects the amount of investment specic to each coalition. Therefore, the larger is the coalition, the higher is the cost formation.

One simple way to take this last remark into account is to model the alliance cost formation as a function of the alliance's cardinal. Therefore, letting α a xed cost coecient and S a given coalition formed by |S| agents, the cost of forming this coalition will be:

ACF (S) = α.|S|, |S| ≥ 2 (8.6)
In the above-presented formulation, alliance cost formation is assumed to be a linear function of alliance's cardinal. We believe that it will be also interesting to extend and to generalize this linear function by introducing a positive factor k that allows the alliance cost formation to be a polynomial function of alliance's cardinal.

ACF (S) = α.|S| k , k ≥ 1, |S| ≥ 2 (8.7)
The coalitions are often to form in highly competitive environments, where making agreements between a huge number of agents is quite dicult or too much costly. In this case, using the polynomial form seems to be an interesting way to penalize large size coalitions by varying the factor k (See Figure 8.2).

2 I thank Professor Michel Minoux for helping me to discuss these questions Including alliance cost formation to the traditional models often induces major changes in the characteristics of the games. For example, it is not guaranteed anymore to have protable coalitions and thus superadditive games. The protability is closely related to the coecient of alliance cost formation α. For instance, a non-single coalition is protable if and only if α satises the following condition:

α ≤ i∈S C(i) -C(S)
|S| k (8.9)

In this section, we have briey highlighted the importance of including the coalition cost formation process in cooperative games. This cost component actually has two major advantages.

On the one hand, it allows us to model and to take into account a non-negligible charge that has been ignored in almost all games. On the other hand, the alliance cost formation penalizes large size coalitions and thus helping to deal with more practical and realistic models where the cooperating actors are organized in many small size groups instead of the grand coalition or large size groups. Going away from the strategic usefulness of considering the cost of forming the alliances, at the practical and mathematical level, the consideration of coalition cost formation will put in advance the question of coalition formation since the superadditivity will be no longer service management systems and to employ principles from cooperative game theory to answer them. Detailed discussions on this research topic as well as many telling examples that motivate and enhance the interest to study the cooperation in service systems are found in [START_REF] Anily | Cooperation in service systems[END_REF]. Research in this area is very new stream, and related papers are quite rare (see [START_REF] Anily | Cooperation in service systems[END_REF]; [START_REF] Yu | On service capacity pooling and cost sharing among independent rms[END_REF]), but we expect seeing more models in the future. [START_REF] Yu | On service capacity pooling and cost sharing among independent rms[END_REF] analyze the benet of service capacity sharing for a set of independent rms. Firms have the choice to either operate on their own service facilities or to invest in a facility that is shared. Facilities are modeled as queueing systems with innite service rates. Firms decide on capacity levels (the service rate) to minimize delay costs and capacity investment costs possibly subject to service level constraints. The situation in which the rms decide to share a facility is formulated as a cooperative game, and a core allocation has been identied. [START_REF] Anily | Cooperation in service systems[END_REF] consider a number of servers that may improve the eciency of the system by pooling their service capacities to serve the union of the individual streams of customers. This economy of scope phenomenon is due to the reduction in the steady-state mean total number of customers in system. The authors suppose that the individual incoming streams of customers form Poisson processes and individual service times are exponential. To deal with the question of splitting the cost of the pooled system among the servers, [START_REF] Anily | Cooperation in service systems[END_REF] dene a transferable utility cooperative game in which the cost of a coalition is the mean number of customers (or jobs) in the pooled system. This game has been showed to have a non-empty core, and core allocations were identied.

Conclusion

In this chapter we pointed out some extensions and future developments in the area of studying the cooperation in supply chain by means of cooperative game theory. We mainly motivated and covered four topics including: (1) Inventory centralization games with explicit transportation costs, (2) Cooperative games with explicit cost formation process, (3) Cooperation in multi-item inventory systems, and (4) Cooperation in service systems. In addition to the afore-described "strategic" aspects, cooperative games involve another non-less important aspect: the complexity of computing stable outcomes. For instance, when dealing with cooperative games one has to

ask and to answer one of these questions:

• Given a game (N, v), does there exists a stable partition for this game?

• Given a game (N, v) and an allocation ϕ, is allocation ϕ in the core?

• Given a game (N, v), an allocation ϕ and a partition P , is P stable with respect to ϕ?

Conclusion

In the age of outsourcing and globalization, the economic and industrial landscape has seen many radical changes. In such context, supply chains are becoming complex networks of a large number of entities that sometimes compete and sometimes cooperate to fulll customers' needs.

Standalone supply chains, where each entity makes its decisions so as to maximize its own prots according to its own objectives, often lead to a loss of eciency and fail to face the complexity of the economic environment they are facing with. Cooperative structures, however, where resources/service facilities are shared and decisions are made to maximize the global prot, prove to be more benecial and ecient. Consequentially, many companies are fundamentally changing their way of doing business by exceeding the border of standalone and individual actions toward collective actions and cooperative strategies. Therefore, building alliances appears as a successful strategy in modern supply chain networks. In general, cooperation enables a better exploitation of the system's resources and oers the opportunity to get benet from large economies of scope, which in turn reduces the total cost/increases the total savings. However, cooperative behavior raises two challenging questions that constituted the main topics of this Ph.D thesis: (1) Which coalitions can be expected to be formed? And, (2) How will the cooperating actors share their total prot?

The aim of this dissertation is to develop a modeling framework and theoretical understanding of the cooperation in supply chain networks. In particular, we considered both superadditive and non-superadditive joint replenishment environments, where independent rms coordinate their replenishment from a supplier in order to save on delivery costs. In such environments, we used principles from cooperative game theory to deal with cooperative behavior questions: alliance formation and prot allocation. Our main contributions are detailed in eight chapters that may be organized in four parts:

The rst part (chapters 1, 2 and 3) constituted an introducing issue for this Ph.D thesis.

Indeed, after giving a general introduction in chapter 1, we presented, in chapter 2, an overview of the Supply Chain and dened its related aspects and issues. While in chapter 3, we focused on introducing the principles of cooperative game theory that are used to answer cooperative behavior questions.

The second part (chapters 4) of this Ph.D dissertation was devoted to understand the phenomenon of cooperation in supply chain networks. To achieve this goal we:

• Provided a detailed analysis of the cooperation phenomenon and alliance formation in supply chain networks,

• Provided a critical review of the literature on the analysis of the cooperation in supply chains by means of cooperative game theory, and

• Highlighted some non-covered issues which are of special interest. In particular, we stressed the limits of superadditive games and the lack of prior attention to study non-superadditive games.

In keeping with the lack of prior attention of the literature to some special issues, in the third part (chapters 5, 6 and 7) of this Ph.D thesis we mainly developed and solved three models. The main contributions may be summarized as follows:

• A study of cooperative games covering both superadditive and non-superadditive applications in supply/repleinshment chains,

• A focus on transportation decisions by studying the cooperation in a context of inventory systems with full truckload shipments,

• Discussions on payo division exceeding the traditional notions of stability to involve issues that take into account cooperating rms' rivalry,

• The emphasis of the limits of studying totally centralized supply chain in n-independent rms cooperative games,

• Development of practical solutions for non-superadditive games that may be applied in general cases, and

• The simultaneous consideration of alliance formation and prot allocation.

Results obtained in this Ph.D thesis provide interesting theoretical and managerial insights and stimulate the development of future research. Some research perspectives was detailed in the last part (chapter 8) of this dissertation. We mainly addressed four topics including: (1) Inventory centralization games with explicit transportation costs, (2) cooperative games with explicit cost formation process, (3) Cooperation in multi-echelon inventory systems, and (4) Cooperation in service systems. Nevertheless, we think that the list of interesting future research topics is still long and we hope to see many more papers in this area in the future.

Figure 2

 2 Figure 2.1: A simple supply chain illustration

Figure 2

 2 Figure2.2: Decision levels in a supply chain[START_REF] Dallery | Notes de cours de logistique industrielle[END_REF]

  Figure 2.3: Joint Replenishment Models

  Figure 2.4: One-Supplier Multi-Retailer Full TruckLoad Joint Replenishment Games

  Figure 2.5: One-Supplier Multi-Retailer Joint Replenishment Games

  Neumann and Morgenstern (1944)'s book gave formal denitions and interesting discussions of many concepts in game theory. Such concepts were reinforced by the publication of the second edition of the book in (1947) where the focus was on the development of the utility theory. This new research stream attracted the attention of many mathematicians and economists. Particulary, young Princeton mathematicians who have focused to develop and deeply extend Neumann and Morgenstern's work. Among these mathematicians were John Nash 3 , Lloyd Shapley. 4 and Donald Gillies 5 As a result, major changes and theoretical contributions were made to game theory. As mentioned above, Von Neumann and Morgenstern (1944)'s work cover the two fundamental behavioral social notions: conict (competition) and cooperation. As such, since its origin, the theory of games was divided into two distinct branches, called non-cooperative game theory and cooperative game theory. The two branches of game theory dier in the way they formalize interdependence among the players.

  for any couple of coalitions (S, T ) such that |S| = |T |. In such games, only the cardinality (the size) of coalitions is important. The players in a game are usually interested in what they individually will get out of the cooperation. The question of savings allocation is then the central question in cooperative game theory. In what follows, we present some denitions related to the sharing of the created value in cooperative games.

Figure 3

 3 Figure3.1: The core[START_REF] Béal | Théorie des jeux coopératifs[END_REF]

  (4.1) and commented in what follows.

Figure 4 . 1 :

 41 Figure 4.1: Cooperation in supply chain networks

Figure

  Figure 4.2: Coalitional Behavior's Challenges

  give a fascinating and detailed survey of exclusive cooperative game theory use in supply chain management. In what follows, we will cover some inventory centralization games closely related to this Ph.D. dissertation. We propose to classify the introduced games in terms of the used inventory model. For instance, we distinct two main classes; Cooperation in Supply Chain Networks Stochastic and Deterministic environments. In stochastic inventory environment, we basically identify the Newsvendor games. In deterministic environment, we identify Economic lot sizing games and inventory games. Our last focus will be on games with coalition structures. The resulting classication is presented in Figure (4.3). Analysis of the cooperation in Supply Chains by means of Cooperative Game Theory Stability of the grand coalition Games with Coalition Structures Stochastic Deterministic The core Analysis of the cooperation in Supply Chains by means of Cooperative Game Theory Stability of the grand coalition Games with Coalition Structures Stochastic Deterministic

Figure 4

 4 Figure 4.3: Classication of supply chain cooperative games

  discussed a similar class of inventory-production games. They consider a situation where a collective of retailers can share their production and inventory facilities. That is, the required items are produced, stored and backlogged by the player having the lowest production, holding and backlogging costs. The arising production-inventory game was showed to have the nice propriety of totally balancedness which means that the game has at least one core allocation. Meca et al. (2004) consider a set of retailers; each of them uses the E.O.Q model as a reorder policy to face a deterministic demand rate. Each retailer supports a linear holding cost, and a xed ordering cost. The retailers may save part of the xed ordering by making joint orders. In this case, the sum of the ordering costs is reduced to only one cost supported by the coalition

Figure 4 . 4 :

 44 Figure 4.4: Traditional supply chain games approaches

Figure 4 . 5 :

 45 Figure 4.5: Structure and Contributions of the Ph.D thesis

  , we are concerned with the problems of alliance formation and cost allocation in one-supplier multi-retailer inventory systems with full TruckLoad shipments. The retailers have to replenish their inventory from the supplier to satisfy a deterministic and constant rate demand of nal customers with full truckload shipments. Each full-truck order is associated with a xed transportation cost. The storage of products involve linear holding costs at the retailers' warehouses. Both cost components are supported by the retailers. To reduce their costs, retailers may choose to cooperate by making joint orders. The main goal of this chapter is to study the arising cooperative game called Joint Replenishment Game with Full TruckLoad shipments (for short, FTLJRP-game). We focus on the core and Shapley value; two of the most central solutions in cooperative game theory. Under the above cost structure the FTLJRP-game is superadditive. We mainly show that its core is non-empty and provide a core allocation. This core allocation is then compared to Shapley value.The comparison is based on four criteria: stability, complexity, the subject of cooperation in full-truck joint replenishment systems. In particular, we consider a single supplier multi-retailer distribution system in which the retail facilities face known demands of a single item (the items may be identical or not, what is important to our analysis is that the items are compatible to be delivered jointly). Each retailer replenishes his/her inventory using full truckload shipments. Transportation costs, from supplier to retailer's warehouse, involve a xed cost per truck dispatched. The storage of the products involves linear inventory holding costs. Both costs are supported by the retailer.

Figure 5

 5 Figure 5.1: One supplier multi-retailer full-truck load joint replenishment system

Proposition 5. 2

 2 The FTLJR-game is superadditive, i.e, every disjoint coalitions are better o by merging into one coalition, i.e; C(S) + C(T ) ≥ C(S ∪ T ), ∀S, T ∈ Ω and S ∩ T = ∅.

Figure 5 . 2 :

 52 Figure 5.2: Additional constraints' eects on the superadditivity

Figure 6

 6 Figure 6.1: Illustration of cycle time deviation

  rate. (π(S) ≥ π(T ) or CR(S) ≤ CR(T )). In the following, for simplicity, we use cost rate parameter. When all retailers' individual costs are equal, i.e, ∀i ∈ N, G i = G, the cost rate of any coalition S is, CR(S) = √ (A+|S|.G). P i∈S HD i P i∈S √ (A+G).HD i . Now suppose that the retailers are sorted by their increasing holding cost parameter HD i , i.e. HD 1 ≤ HD 2 ≤ ... ≤ HD n .

  [1, 500]. The corresponding holding cost h i is generated randomly in the interval [1, 10]. The individual cost G i is generated randomly in the interval [1, 50]. We consider three possible values of the xed ordering cost, A = 10, 30, 50. The number of the retailers in the system was varied in {5, 10, 15, 20, 25}. And

  π(S ) Time (s) ∆π(S ) ∆T ime(s) π(S ) Time (s) π(S ) Time (s) π(S ) Time (s) ∆π(S ) ∆T ime(s) π(S ) Time (s) π(S ) Time (s) π(S ) Time (s) ∆π(S ) ∆T ime(s)

  are imputations, proving the non-emptiness of the core reduces to prove that any sub-set of rm in an ecient coalition gains at least as much as they can get by themselves if they were to deviate and to form their own coalition. Let us consider ecient coalition S ,P 1 .Let T be sub-coalition of S ,P 1 , T ⊂ S ,P 1 and let us show that i∈T ϕ P (S ,P 1 , i) ≥ v(T ).

Figure 7

 7 Figure 7.1: One-Supplier Multi-Retailer Full TruckLoad Joint Replenishment Game with three cost components : Holding Cost, Fixed and Variable Transportation Costs

Figure 7

 7 Figure 7.2: Firms' Prot Prole in partitions P ,P and P ,E

  theory seems to be a natural and great framework to model cooperation in supply chains. However, this research area is a rather new stream of research in supply chain management, and several future developments can be done. In this chapter, we aim at introducing some extensions closely related to the present Ph.D thesis. We mainly discuss four topics including (1) Inventory centralization games with explicit transportation costs, (2) Cooperative games with explicit cost formation process, (3) Cooperation in multi-item inventory systems, and (geographical dispersion of production and commercial processes is among the major characteristics of supply chains. Managing such spatial dispersed customers, suppliers and partners imperatively involves a well developed transportation systems. Without well developed transportation systems, logistics could not bring its advantages into full play. It has been shown

  d i,j the distance that separates location i and location j, and δ T a per distance-unit transportation cost, the transportation cost is δ T .d i,j . A xed cost or a per unit transportation cost is often included. When considering a per unit transportation cost, the total cost for carrying the orderedquantity Q is δ T .d i,j + c T .Q (8.2)8.1.3 Inventory-Routing GameTo emphasize the challenges and impacts that an eventual transportation cost function can have on a traditional inventory game we address below what we call the inventory-routing games. 1 This game may be considered as an extension of the model studied in chapter 5; we consider the same joint replenishment situation where both of ordering and holding cost components are kept whole individual cost component is replaced by an explicit transportation function which a variant of the cost function in equation (8.2).

C

  * (i) = 2.(A + 2.δ T .d i,0 ).D i h i = 2.(A + 2.δ T .d i,0 ).m * i , i ∈ N.(8.3)Above, we have determined the optimal replenishment policy for any standalone situation. Now let us focus on the cooperative situation where a group of retailers, S, decides to cooperate by ordering jointly and delivered in a TSP tour. In this case the cooperating retailers will have the same ordering frequency m i = m S , ∀i ∈ S ⊆ N and the total average cost of the coalition is as follows:C(Q i ) = (δ T .T SP (S).m S ) s optimal total cost is obtained by the minimization of the above total cost with respect to the ordering frequency m s . The result is as follows:C * (S) = 2.(A + δ T .T SP (S)). i∈S D i h i = 2.(A + δ T .T SP (S)).m * S , S ⊆ N. (8.4)In what follows for better understanding of the model, we present a small numerical example that will also allow us to highlight the challenges that the transportation cost function brings into the model. We consider a 3-retailer cooperative game, in Figure8.1(a) we present the standalone situation in addition to the retailers parameters. In Figure8.1(b) we present all possible alliances.

Figure 8

 8 Figure 8.1: a 3-retailer inventory-routing game

Figure 8

 8 Figure 8.2: Alliance Cost Formation

  Thus, his action depends on his beliefs about what the others are willing to do. Of course, what the others do depends on their beliefs about what each agent does.

  1 and P 2 . If there exists a non empty coalition S such that P 1 ≺ i P 2 for all i ∈ S, we write P 1 ≺ S P 2 . Let us denote by S the following relation: P 1 S P 2 if the coalition structure P

2 is obtained when S deviates from the coalition structure P 1 . We say that P 1 is directly dominated by P 2 , denoted by P 1 < P 2 , if there exists an S such that P 1 S P 2 , and P 1 ≺ S P 2 . We say that P 1 is indirectly dominated by P m , denoted by P 1 << P m , if there exists P 1 , P 2 , P 3 , ..., P m and S 1 , S 2 , ..., S m-1 such that P i S i P i+1 and P i ≺ S i P m for i = 1, 2, 3, ..., m -1.

A set Y is called consistent if P ∈ Y if

and only if for all Z and S, such that P S Z, there is an B ∈ Y , where Z = B or Z << B, such that Z ≺ B. Like the core, LCS suers from a number of drawbacks, some of them have been pointed out by Chwe himself. Xue (1998) has rened Chwe's LCS by introducing the notion of perfect foresight. Recently, Mauleon and Vannetelbosch (2004) have rened Chwe's LCS by introducing the notion of cautiousness.

  study dynamic alliance formation among agents in competitive markets. They consider the problem of price competition in a n-agents game. The dierent agents are selling substitutable products and facing both deterministic and stochastic demand. The farsighted agents may form alliances in order to determine common price and compete against each other. Nagarajan et al.

(2009)

analyze the farsighted stability of group purchasing organizations. Group purchasing, also called, Group buying refers to group of many rms (buyers) that pool their purchasing requirements and buy large quantity of a particular product from a seller. This allows them to take advantage of signicant quantity discounts from the seller.

Nagarajan et al. (2009)

mainly consider the three well known allocations (proportional allocations, equal allocations and shapely value allocations), under which the farsighted stability of several group purchasing models were investigated.

Table 5 .

 5 1: Retailers parameters and Shapley value

	Retailer D i h i V i Cap A C(i) Sh(N, v)(i)
	{1}	100 6	1	20	20 160	36.99
	{2}	800 1	1	20	20 810	15.11
	{3}	700 1	1	20	20 710	14.76

  Table 7.2, coalitions' costs and values are reported in Table 5.4. HCB-solution is reported in Table 5.4.

					Table 5.5: HCB-solution
	Retailer Ordering Cost Holding Cost allocated Total Cost Prot amount: X(i) Prot ratio
	{1}	240		20			260	5	1.86%
	{2}	40			6.66			46.66	43.33	48.14%
	{3}	20			6.66			26.66	93.33	77.77%
	{1}	600 1	1	50	20 12	240	25	265
	{2}	100 2	1	50	20	2	40	50	90
	{3}	50	4	1	50	20	1	20	100	120
					Table 5.4: Coalitions' Costs and Savings
					Coalition (S) C(S)	v(S)
						{1}		265	0
						{2}		90	0
						{3}		120	0
					{1, 2}		308.33 46.67
					{1, 3}		290.76 94.23
					{2, 3}		126.66 83.33
					{1, 2, 3}	333.33 141.66

Table 5.3: Retailers' Costs and Parameters (Decentralized case)

Retailer D i h i V i Cap A N i Ordering Cost Holding Cost Total Cost: C(i)

Table 7

 7

.2. The marginal contribution of the dierent retailers is reported in Table

5

.6. Shapley value is obtained by averaging the marginal contributions for all possible orderings. The result is reported in Table

5

.7. As one can remark, the prot rate of retailer 1 under Shapley value is around ten times his/her prot rate under HCB-solution.

Table 5

 5

		.6: Retailers' marginal contribution
		Permutation		Retailer
			{1}	{2}	{3}
		1 2 3	0	46.42	95.23
		1 3 2	0	47.43	94.23
		2 1 3	46.42	0	95.23
		2 3 1	58.33	0	83.33
		3 1 2	94.23	47.43	0
		3 2 1	58.33	83.33	0
		Total	257.32 224.63 368.04
		Table 5.7: Shapley Value allocation
	Retailer allocated Total Cost: C(i)-Sh(N,v)(i) Prot amount: Sh(N,v)(i) Prot ratio
	{1}	222.11			42.88	16.18%
	{2}	52.56			37.43	41.59%
	{3}	58.65			61.34	51.11%

Table 5 .

 5 8: Comparison between Shapley value and HCB-solution

		Stability Complexity Fairness Practical setting
	Shapley Value	+	-	+	-
	Core allocation X	+	+	-	+

Table 5

 5

	.9: A 10-retailers totally centralized system
	Retailer	Di	hi	Vi	Cap	A	Cost: C(i)
	{1}	468	7	1	50	100	1111
	{2}	478	1	1	50	100	981
	{3}	372	8	1	50	100	944
	{4}	291	6	1	50	100	732
	{5}	469	10	1	50	100	1188
	{6}	144	9	1	50	100	513
	{7}	89	7	1	50	100	353
	{8}	269	2	1	50	100	588
	{9}	40	3	1	50	100	155
	{10}	137	6	1	50	100	424
	Total Decentralized System Cost:		6989
			Centralized System
	Without Additional Constraints:
	N = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

Table 6

 6

	.1: Retailers' parameters and costs
	Retailer	A	G i D i h i	C(i)
	{1}	100 70 100 1 184.3
	{2}	100 10 950 3 791.8
	{3}	100 80 250 1	300
	Table 6.2: Coalitions' costs and savings
	Coalition	C(S)	v(S)
	{1, 2}	1030.53 -54.3
	{1, 3}	418.33	66.06
	{2, 3}	1085.35	6.47
	{1, 2, 3}	1289.96 -13.73

Table 6

 6

	.3: Prot allocation in a 10-retailer coalition formation game
	Ecient Coalition:S	π(S )		Retailer's parameters		Retailer's savings
			{i}	G i	D i	h i	C(i)	X(i, S )	π(i, S )
	{5,6,9}	16.60%	{5}	1	3821	3	1521.68	252.81	16.60%
			{6}	130	4897	4	3001.74	498.2	16.60%
			{9}	191	4949	3	2939.54	487.9	16.60%
	{3,4,8,10}	8.38%	{3}	206	5384	9	5445.647	456.3	8.38%
			{4}	411	6725	6	6421.65	538.1	8.38%
			{8}	400	61160	8	7019.97	588.2	8.38%
			{10}	263	4280	6	4317.83	361.83	8.38%
	{1,7}	2.87%	{1}	620	2088	9	5201.96	149.2	2.87%
			{7}	867	6253	5	7776.02	223.17	2.87%
	{2}	0%	{2}	496	9647	4	6782	0	0%

  6.2 : Weak stability: The ecient coalition structure P is weakly stable. This means that all separate coalitions are core stable. The cost-based proportional rule is in the core of any subgame (S k , v S k ),i.e, X ∈ Co(S k , v S k ) for all S k ∈ P Proof: Let S k ∈ P any coalition. The cost-based proportional rule allocate to each retailer i, the prot portion:

	The individual stability of ecient coalition structure P means that no retailer will switch
	unilaterally from his/her current coalition to another existing one. This stability concept, only
	taking into account individual deviations, seems suitable whenever the cost of coordinating move-

Theorem 6.1 : Individual stability: The ecient coalition structure P is individually stable, i.e, it is immune to individual retailer deviations.

Proof: The proof of this theorem is valid by construction of the ecient coalition structure. For instance, let us discuss whether it is possible for a retailer i member of coalition S k to deviate and to join another coalition S t (S k = S t ∈ P ). Assume that retailer i defect from coalition S k to join S t . By construction we have π(S t ∪ {i}) ≤ π(S k ), otherwise, coalition (S t ∪ {i}) would have been selected by the algorithm instead of S k . The move of retailer i from coalition S k to coalition S t will make him/her worse o . ments to form a new coalition is high, or there are some other economic restrictions for building new coalitions. Going away from individual move's immunity, the question now is whether the coalition structure P is immune to group deviation. Theorem

Table 6 .

 6 4: Computing results for Exact Solution and Heuristic Solution

Table 6 .

 6 5: Computing results for Ecient Coalition Structure vs Optimal Coalition Structure

	9

* ) |P * | π(P ) |P | ∆ π ∆

  n} is the set of players, and P = ( 1 , 2 , ..., n ) denotes the preference prole, specifying for each player i ∈ N his/her preference relation i ,i.e. a reexive, complete and transitive binary relation on set

  Denition 27 : Ecient Coalition Structures (ECS) P ,P , P ,E , refers to the partitions that respectively hold when each rm joins its ecient coalition under equal allocations and proportional allocations, i.e., P ,P = {S ,P

	1	, S ,P 2	, ..., S ,P m } and P ,E = {S ,E 1	, S ,E 2	, ..., S ,E l	}
	such that:

  Above, we have determined the standalone optimal replenishment policy for any rm. In what follows, we focus on the cooperative situation. Consider a non-empty set of rms that decide to form a coalition ,S, to manage their inventory collectively by making joint orders. In this case it is obvious that in this cooperative structure all these rms will have one common cycle time T S and a common ordering frequency N S . Since we suppose that only full truck orders are authorized and no shortage is allowed it is easy to check that the common ordering frequency is the sum of the standalone ordering frequency, i.e., The delivered products are stored in local warehouses where every retailer supports his/her own holding cost; the holding cost charged by the coalition is the sum of the individual holding costs. As a result, the average total cost of alliance S, C(S), is C

	n}.	(7.8)
	N S =

i∈S

N i , ∅ ⊂ S ⊆ N (7.9)

As mentioned above, in the cooperative situation, only one ordering cost is supported. Thus, coalition S charges ((A + i∈S G i ).N S ) delivery cost.

Table 7

 7

		.1: Standalone situation vs Cooperative Situation
	Delivery costs	Standalone situation P i∈S	Cooperative Situation	variation	Gap

  11)P ,P and P ,E are the ecient coalition structures studied above (see Denition (27)).

	P ,P = {S ,P 1	, S ,P 2	, ..., S ,P m } such that:
	S ,P i	= argmax S⊆(N \∪ j=i-1 j=1 S ,P j	) {(	v(S) j∈S C(j)	)}, S ,P i	∈ P ,P
	And P ,E = {S ,E 1	, S ,E 2	, ..., S ,E l	} such that:

  Next, nonlinear termsY i .R , Y i .T , Y i .Y j .T and Y i .Y j .Rcan be linearized by introducing additional variables T ij and R ij . (F.IV )

	n	(7.26)
	min A.

n i=1

  As summarized in Table7.3, the total number of variables in model(P A(IV )) is (2n 2 +n+2)where n are binary variables and (n 2 + 2) are continuous. The total number of constraints is (10n 2 +3) where 2 constraints are equality constraints, (2.n 2 ) positivity constraints and (8.n 2 +1) Proposition 7.5 The exponentially complex optimization (F E.I) problem is equivalent to the polynomial complex optimization problem (F E.IV ), i.e., equations(7.44, 7.46) ⇐⇒ equations (7.57, 7.72).

			, n		(7.70)
	n
	Y i ≥ 1				(7.71)
	i=1
	Y i ∈ {0, 1}, ∀i = 1, 2, ..., n			(7.72)
	inequalities.
	Table 7.3: Model (F E.IV )'s complexity
		Variables	Constraints
	Binary Continuous " = "	≥ / ≤	≥ 0
	n	2n 2 + 2	2	8n 2 + 1 2n 2
	Total	2n 2 + n + 2		10n 2 + 3

2, ..., n, ∀j = 1, 2, ..., n (7.68

)

R ij ≤ Y j , ∀i = 1, 2, ..., n, ∀j = 1, 2, ..., n (7.69)

R ij ≥ 0, ∀i = 1, 2, ..., n, ∀j = 1, 2, ...

  U[100; 500], U[0; 100] and U[1; 10] to respectively generate each demand rate, D i , each individual cost G i and each holding cost h i . In these numerical studies, the ordering cost A and the truck capacity CAP were set respectively to 100 and 200. We considered the simple case of identical products' volume and set this parameter to V i = 1. The number of rms in the cooperative game was varied in {5, 10, 15} and for each value of n we dealt with 10 instances. All computational experiments were performed on a PC with Intel Core 2 CPU of 3 Ghz and RAM of 0.99 GB. All instances were solved using ILOG OPL Development Studio 5.2 solver with default parameters.

Table 7 .

 7 4: Computing results for P ,P vs P ,E On analyzing the above numerical results, the rst point to note is that coalition structures P ,P and P ,E are closely similar in terms of their global prot rate and number of coalitions.

	Problem size		P ,P		P ,E	∆ P ,P -P ,E
		|P ,P | π(P ,P ) |P ,E | π(P ,E ) ∆ |P |	∆ π
	Max	3	39,56 %	3	40,75 %	0	3 %
	n=5 Mean	2,3	28,57 %	2,6	28,56 % -0,3	0 %
	Min	2	15,29 %	2	17,99 %	-1 -3,43 %
	Max	5	39,74 %	6	37,94 %	1	4,7 %
	n=10 Mean	4,7	29,85 %	5	29,4 % -0,2 0,44 %
	Min	4	19,45 %	4	21,9 %	-1 -2,46 %
	Max	10	46,67 %	9	48,25 %	1	1,61 %
	n=15 Mean	8	26,57 %	8	26,69 % -0,2 -0,11 %
	Min	5	13,17 %	6	16,11 %	-2 -2,94 %

Table 7

 7 In order to compare rms' created values we present in Figure(7.2) the prot rate prole in both coalition structures P ,P and P ,E .

	.5: Firms' parameters
	Firm {i}	D i	G i	h i
	{1}	534	91	7
	{2}	105	90	1
	{3}	496	28	8
	{4}	355	28	6
	{5}	242	7	10
	{6}	232	83	9
	{7}	533	9	7
	{8}	187	52	2
	{9}	274	40	3
	{10}	287	50	6
	as the corresponding prot rate.

Table 7 .

 7 6: Formation of coalition structures P ,P and P ,E in a 10-rm cooperative game

		Coalition Structure P ,P			Coalition Structure P ,E
	S ,P k		Firms's outcome		S ,E k		Firms's outcome
		{i}	C(i)	ϕ P (S ,P k	, i) Π(S ,P k	, i)		{i}	C(i)	ϕ E (S ,E k	, i) Π(S ,E k	, i)
	{4, 5, 7}	{4}	827,2	393,08	47,52 %	{3, 5, 7}	{3} 1117,4	508,71	45,52 %
		{5} 1129,5	536,73	47,52 %		{5} 1129,5	508,71	45 %
		{7} 990,49	470,68	47,52 %		{7} 990,49	508,71	51,4 %
	{3, 6, 10} {3} 1117,4	350,08	31,33 %	{4, 6, 10} {4}	827,2	311,5	37,65 %
		{6} 1112,3	348,48	31,33 %		{6} 1112,3	311,5	28 %
		{10} 815,25	255,41	31,33 %		{10} 815,25	311,5	38,2 %
	{8, 9}	{8} 342,12	54,1	15,81 %	{1, 9}	{1}	1210	102	8,42 %
		{9}	491,8	77,8	15,81 %		{9}	491,8	102	20,74 %
	{1}	{1}	1210	0	0 %		{2, 8}	{2} 199,75	12,25	6,13 %
	{2}	{2} 199,75	0	0 %			{8} 342,12	12,25	3,58 %

John von Neumann (December

28, 190328, -February 8, 1957) ) was a Hungarian American mathematician who made major contributions to a vast range of elds, including set theory, functional analysis, quantum mechanics, economics and game theory, computer science, as well as many other mathematical elds.2 Oskar Morgenstern(January 24, 1902-July 26, 1977) was a German-born Austrian economist.He helped found the mathematical eld of game theory.

John ForbesNash (born June 13, 1928) is an American mathematician and economist who worked on game theory, dierential geometry, and partial dierential equations, as well as many other mathematical elds. He shared the 1994 Nobel Memorial Prize in Economic Sciences with game theorists Reinhard Selten and John Harsanyi.

Lloyd Stowell Shapley (born June 2, 1923) is a distinguished American mathematician and economist. He has contributed to the elds of mathematical economics and especially game theory.

Donald BruceGillies (October 15, 1928 -July 17, 1975) was a Canadian mathematician and computer scientist, known for his work in game theory, computer design, and minicomputer programming environments.

focus will be then to provide insights on the "stability" of the formed structures and determine the related algorithmic complexity.

Under the cost-based proportional rules and equal allocation rules, we show that ecient coalition structures always exist and are stable coalition structures. However, the problem of nding the ecient coalitions -in the general case-is an exponentially complex problem.

Further, we focus on partitioning the set of rms into ecient coalitions that form what we call the ecient coalition structure. The problem is showed to be exponentially complex and both ecient coalition structures (one generated with cost-based proportional rule and the other with equal allocation rule) are showed to be stable coalition structures.

In the second part of the chapter, we applied the results valid for games with general cost function to a concrete supply chain game. We consider the issue of generating the afore-described coalition structures, in the one-supplier multi-retailer full TruckLoad shipments Joint replenishment Game (FTLJRP-Game)under three cost-components ( xed and variable Transportation costs and Holding Cost), i.e., in this model, we consider the same cost structure as in the JRPgame studied in Chapter (5) while we keep the assumption of full truckload shipment as in the model studied in Chapter (4). For this non-superadditive FTLJRP-Game we provide a polynomial algorithmic solution to identify ecient coalitions. And, using a set of numerical results, we compare both coalition structures (one generated with cost-based proportional rule and the other with equal allocation rule). We show that no partition dominates the other, nevertheless, the use of equal allocations may lead in some cases to "unsatised" rms.

The rest of the chapter is organized as follows. In section 7.2, we introduce the general model and the associated hedonic game. Section 7.3 describes the formation of stable ecient coalition structures when cost-based proportional allocation and equal allocation are respectively used. Section 7.4 is devoted to the application of our general results to FTLJRP-Games. We conclude by summarizing the main insights of our results and discuss some extensions in section 7.5.

The Model and the Game

In this section, we rst present the general joint replenishment model we deal with. We then focuss on the introduction of the associated n-person hedonic cooperative game.

The Model

In this chapter we do not restrict ourselves to a particular supply chain conguration or cost structure. We are developing a general approach that can be applied to all joint replenishment games as well as to group buying games. In this model, we are given a set of n retailers (for Denition 26 : Equal allocations This allocation rule assigns an equal savings portion to each rm. Thus, a rm i, member of coalition S will receive the worth

Theorem 7.1 In a hedonic game (N, R) where the preference prole is determined by costbased proportional allocations or equal allocations, ϕ(., .) ∈ {ϕ P (., .), ϕ E (., .)}, ecient coalitions always exist and are expressed as follows:

• ϕ(., .) ≡ ϕ P (., .) :

• ϕ(., .) ≡ ϕ E (., .) :

Proof: The coalition S ,P

) always exists by nature of the optimization problem. To show that coalition S ,P 1 is an ecient coalition, we should show that any rm in S ,P 1 prefers this coalition to any other coalition. So let us consider a rm i and a coalition T, T ∈ N i , by construction of S ,P 1 we have:

1 is then ecient. The proof is similar when we consider equal allocations.

Now let us consider ecient coalition formation under proportional allocations. Once coalition S ,P

1 is formed, we suppose that the rms in the new system N \ S ,P 1 will react similarly, that is the ecient coalition S ,P 2 will be formed.

Now the procedure is reapplied; a third ecient coalition S ,P 3 will be formed, a fourth and so on until assigning all retailers to their ecient coalitions. It is clear that, by construction, the ecient coalitions are disjoint, therefore they form a partition of N . This partition will refers to the ecient coalition structure and will be denoted by P ,P . When considering, equal allocations, the ecient coalition structure P ,E will be formed in the same way as P ,P . To summarize both partitions are formally dened as follows:

This means that sub-set T will not defect from ecient coalition

At this level of our analysis, we only focus on the propriety of an ecient coalition without the implication of rms and the other alliances outside this ecient coalition. However, as one can expect studying the stability of a coalition structure in general, particularly that of partitions P ,P and P ,E , implies the study of possible interactions between coalitions, i.e., the possible moves of groups of rms that are not only in the same coalition but also belonging to several coalitions.

When dealing with this issue, i.e., the stability of coalition structures P ,P and P ,E , the rst point to note is that both of coalition structures P ,P and P ,E are weakly stable (this is an immediate result from Theorem (7.2).

Theorem 7.3 : Weak stability: Ecient coalition structures P ,P and P ,E are weakly stable in the sense that the cost based proportional rule is in the core of any coalition of P ,P and equal allocation is in the core of any coalition of P ,E The weak stability exposed above means that in the ecient coalitions no group of rms within the same ecient coalition will have the incentive to deviate. When extending this analysis to include the movement of group of rms that may belong to several coalitions, we have the following results.

Theorem 7.4 : Strong stability (stability in the sense of coalition structure core (see chapter

3)):

1. Given the coast based proportional allocation, ϕ P (., .), ecient coalition P ,P is a stable coalition structure.

2. Given equal allocation rule, ϕ E (., .), ecient coalition P ,E is a stable coalition structure.

Proof: The proof of the strong stability is strictly the same for both coalitions structures P ,P and P ,E and is, like in the above theorems, valid by construction. Let us assume that the cost

).X j (7.14)

Because of its exponential complexity, the current (F.I) may be only used for systems with a small number of rms. When dealing with a large number, the problem becomes too complex to allow the use of exhaustive enumeration. Since we deal with an objective function that aims at minimizing a ratio of two functions, fractional programming theory may be used to reformulate the problem (we used the same technique as in Chapter 5). To achieve 0-1 fractional program formulation, we dene the following new decision variables:

Expressing the cost reduction ratio of one coalition S with the newly added decision variables Y i gives the following 0-1 fractional ratio that represents the objective function (for simplicity C(i) will be replaced by C i ).

CR(S) =

Formulation (F.I) is then equivalent to the following formulation.

(F.II)

guaranteed.

Multi-Item inventory games

Our survey of the models using cooperative game theory to study cooperation in supply chain reveals that most of the inventory centralization games concern single-item joint replenishment system. This means that, the studied cooperative situations involve many retailers each of them is associated to a single (often identical) product purchased from the same supplier and/or shipped from the same warehouse. To the best of our knowledge, there is no paper that has studied the questions of alliance formation and prot allocation in n-retailer cooperative game where each retailer is operating in a multi-item environment. We feel that generalizing and extending the study of cooperation from the one-supplier multi-retailer inventory systems to multi-item multi-retailer inventory system with single/multiple suppliers (see Figure 8.3) is a great-potential research stream in supply chain management. The motivation to deal with the cooperation in multi-item inventory system is twofold. On the one hand, this will allow us to have models that are more closer to supply chain real-situations.

On the other hand multi-item inventory games will rise several new useful and topic questions.

In addition to the traditional complexity of multi-item inventory management, the problem of coalition formation is very challenging here. For instance, one can imagine a conguration where the alliances are formed around the various items. That is, the distinct items are managed separately by applying traditional inventory games results to each item. In this case, several coalition structures are to form and a given retailer may be member of many distinct coalitions.

In spite of this decentralized way to manage the distinct items, one can think at looking for a single coalition structure where the retailers within the same coalition manage a set of items collectively.

In other words, the consideration of multi-item environment rise the fundamental question about what would be better to form; "dynamic alliances" or "strategic alliances". We should mention that "dynamic alliances" refer to alliances that are changing over time, while "strategic" ones refer to alliances that are strategically designed for long/mid term time horizon. Each of these two coalition formation mode involves a distinct view of the cooperation and has its own advantages and limitations. For instance, when forming "dynamic alliances", the agents can rapidly react to face the economic changes of their environment. However, this involves computationally complex problems. Under "strategic alliances" system view, defecting from a coalition and/or creating or joining a new one are strategically complex decisions. Because such decisions imply the rise of all the challenges related to cooperative behavior (such as, trust, "condential" information sharing with new partners, rivalry, etc.). For this reason, the formation of an alliance is a long term (mid term decision in some cases) decision. However, designing such "static" alliances involves the question of "robustness". As such, "strategic" alliances should be "robust" in the sense that are capable of coping well with variations in their operating environment (for example agents parameters variations) with minimal damage, alteration and/or loss of eciency. We believe that investigating the issues of "dynamic" alliance formation and "robust" alliance formation is very great research topic that will provide more comprehension of the cooperation in supply chain networks. We should note that such issues are capturing the attentions of some academics. Probably [START_REF] Nagarajan | Stable farsighted coalitions in competitive markets[END_REF] are the rst authors that dealt with dynamic alliance formation in supply chain.

Cooperation in Service System

The wide literature on the study of cooperation in supply chain has been concentrated on analyzing activities' pooling in various retailing and manufacturing systems. The most common analyzed situations are situations where for example, many retailers coordinate their replenishment from a supplier in order to save on delivery costs, and where many manufacturers coordinate the operations of various stages in the production process in order to save on the holding costs.

In general, due to the economies of scales and other motives, cooperation enables a signicant reduction of the total cost. Once the operational policy of the supply chain is determined, the next natural question that has been asked is how to allocate the total cost among the various retailers/manufacturers that compose the system.

As in retailing and manufacturing systems, the cooperation among several service providers enables a better exploitation of the system's resources, which in turn reduces the total cost.

Research in this area is to pose similar questions (alliance formation and cost allocation) in