Jing Peng
email: jing.peng@ecp.fr

Oualid Jouini
email: oualid.jouini@ecp.fr

Yves Dallery
email: yves.dallery@ecp.fr

Zied Jemai
email: zied.jemai@ecp.fr

Keywords: service pooling, queueing systems, cooperative game theory, core allocations, general service times

We study the cost-sharing problem among independent service providers in a service capacity pooling system. The effective improvement of such pooling system can be achieved by reducing the resource idleness in case of congestion. In this paper, we model both the service provider and the cooperative coalition as a single server queue. We attempt to answer the following questions: (i) which coalition strategy should be used; and (ii) which allocation rule should be selected in order to maintain the stability of the coalition? In particular, we consider the service pooling with a fixed service capacity for M/G/1 service systems. The benefit of the pooling system is due to the shortened waiting queue in the overall system. We develop the corresponding cooperative game with transferable utility, and analyze the core allocations. Although it is difficult to express a core allocation explicitly for the game, we prove the nonemptiness of the core. We give a reasonable expression of Equal Profit Method to distribute the cost for our game, and investigate a number of cost allocation rules under three typical situations to evaluate the gain of the service pooling strategy for each service provider. The numerical results show that the cost allocation rule proposed gives a reasonable cost-sharing result considering the contribution of each participant.

I. INTRODUCTION

Services play an important role in the world economy. Based on the report from the office of United States Trade Representative, four out of five jobs in US are proposed by service industry [START_REF] Jemai | United States Trade Representative and Investment[END_REF]. In France, service presents the biggest sector of the economy and accounts for 79% of total GDP according to statistical data from the World Bank. In the context of economic globalization, competition and cooperation in service industries are more and more popular in nowadays: price competition among fast food restaurant chains, operation combination of telecommunication companies, collaborative after-sell and maintenance services in electronic manufacturing industry etc. In this paper, we focus on the collaboration benefit between several independent service providers in terms of capacity sharing. In order to make service systems more efficient, there are several basic cooperative methods: queueing cooperation, e.g., scheduling among simultaneous arrival agencies or rerouting among different servers [START_REF] Katta | Cooperation in queues[END_REF], [START_REF] Kayi | Characterizations of pareto-efficient, fair, and strategy-proof allocation rules in queueing problems[END_REF]; service pooling, e.g., service rate pooling or staffing allocation [START_REF] Guo | A fair staff allocation rule for the capacity pooling of multiple call centers[END_REF]; cross-training [START_REF] Tekin | Pooling strategies for call center agent cross-training[END_REF]; collaboration with third-party service providers, e.g., service outsourcing [START_REF] Aksin | Call center outsourcing contract analysis and choice[END_REF], etc. In some cases, different methods can be combined to form a more profitable collaborative structure [START_REF] Anily | Subadditive and homogeneous of degree one games are totally balanced[END_REF]. Under certain conditions, service providers could earn more revenue or reduce expenses by using the collaboration methods mentioned above.

All the previous methods can be classified broadly into three typical cooperation forms: vertical form, i.e., collaboration between customers and servers; horizontal form, i.e., collaboration among homogeneous servers; and external form, e.g., collaborative outsourcing. We focus in this study on horizontal service pooling among independent service providers. The obvious gain is the mitigated congestion in the cooperative system, owing to the disappearance of servers' idleness with waiting customers in the queues. Altogether, the coalition service set is more efficient than individual ones. The pooling advantage for the whole system is apparent, but the collaborative gain of the entire alliance cannot be the incentive for each individual service provider to join the coalition. It is therefore important to address the following questions: which independent service providers should collaborate together; and how to share the cost of the pooling system among the participants to keep each individual staying in the coalition?

In this paper, we consider a set of independent single-server service providers, each of which faces its own incoming stream of customers/demand. Customer inter-arrival and service times are assumed to be random and distributed independently. We suppose that an individual incoming stream is strictly unrelated to those of other providers. This means that there is no competitive relationship among service providers in the set. The providers in the coalition could then join a profitable coalition by operating their service capacities in common. Alternatively, each provider could make his own decision independently to either join any coalition or not, based on his individual benefit. Once the coalitions is formed, the most important problem in the entire coalition for every independent provider returns to a cost-sharing problem under collaboration.

Cooperative game theory provides interesting concepts to find profitable coalition structures and solves the cost sharing problem among cooperative players. We assume that the total cost is a transferable utility, e.g., money in the general case. The corresponding cooperative game with transferable utility (TU-game) is defined among the set of independent service providers, and has a characteristic function defined by the total operating costs associated with each coalition for the cases of fixed system capacity. In order to make a profitable service pooling strategy, we prove that the system total cost could be minimized in the grand coalition. Therefore, as mentioned above, we focus on the cost-sharing problem to guarantee the stability of the grand coalition.

There exists a large literature focusing on the cooperative behavior among independent participants using cooperative game theory: [START_REF] González | Optimal sharing of surgical costs in the presence of queues[END_REF] is the earliest research that deals with the cost allocation problem for operating-theatre sharing in medical service. The authors separate the operating-theatre costs as variable and fixed cost, and focus on the Shapley value of two sub-games. In [START_REF] Garcia-Sanz | Cooperation in markovian queueing models[END_REF], the authors address an extension of [START_REF] González | Optimal sharing of surgical costs in the presence of queues[END_REF], considering preemptive priority for the customers from different individual servers to provide a more profitable pooling system. Our work is inspired by two recent papers [START_REF] Yu | Capacity sharing and cost allocation among independent firms with congestion[END_REF], [START_REF] Anily | Cooperation in service systems[END_REF], which study the service capacity pooling problem using cooperative game theory. Two similar general M/M/1 service pooling systems have been considered in these two papers. [START_REF] Yu | Capacity sharing and cost allocation among independent firms with congestion[END_REF] uses the optimal service rate that minimizes the system operating cost, in addition, an incomplete information problem has been treated here. In [START_REF] Anily | Cooperation in service systems[END_REF], the authors choose a variable service rate, which varies with customer incoming rate. Based on a system performance defined in terms of the mean number of waiting customers in the system, authors give the expressions of all cost allocation rules. With the work of [START_REF] Karsten | Resource pooling and cost allocation among independent service providers[END_REF], [START_REF]Analysis of resource pooling games via a new extension of the erlang loss function[END_REF], the service cost allocation problem in [START_REF] Yu | Capacity sharing and cost allocation among independent firms with congestion[END_REF] and [START_REF] Anily | Cooperation in service systems[END_REF] are extended to multiserver settings with Erlang-B and Erlang-C queueing models.

Using an M/M/1 queueing modeling, several existing studies address the pooling, scheduling, staff allocation, or outsourcing problems in service systems [START_REF] Katta | Cooperation in queues[END_REF]- [START_REF] Guo | A fair staff allocation rule for the capacity pooling of multiple call centers[END_REF], [START_REF] Aksin | Call center outsourcing contract analysis and choice[END_REF]- [START_REF] Anily | Cooperation in service systems[END_REF]. In this work, we extend the service pooling problem to the more general case of M/G/1 systems. Although its prevalence in practice, no studies of service pooling for M/G/1 systems exist in the literature. Considering the efficiency and quality driven in service systems, our system total cost consists of the service capacity cost and the system congestion cost. We prove that the service pooling game with a fixed service capacity sharing always has a stable cost-sharing allocation for the grand coalition. We attempt to consider the contribution of each service provider to coalitions with the Equal Profit Method proposed by [START_REF] Frisk | Cost allocation in collaborative forest transportation[END_REF]. With numerical experiments, we compare the allocation method proposed using two different contribution weights with the Shapley-value, the Tau-value, the nucleolus and the Equal Profit Method. By a reasonable selection of the contribution weights for each individual participant, this rule gives an attracted pooling gain for the participant with a high contribution to the coalition, especially in the quality driven condition.

The rest of the paper is structured as follows: Section 2 presents both the individual and collaborative modeling of service systems. In Section 3, the service pooling problem with a fixed service capacity is defined and analyzed as a TU-game. Then, we propose a reasonable expression of Equal Profit Method, and investigate the allocation method proposed with a number of traditional cost allocation rules for our game under three typical situations in Section 4. Finally, conclusions and future work are presented.

II. SERVICE POOLING MODELING

We consider a set of n service providers, N = {1, . . . , n}. Each service provider i ∈ N is modeled as a single server queue handling a single class of customers. We assume that the waiting space is large enough, no customer would abandon after entering the system, and there is no fail in the service processing, i.e., no retrial is considered here. The incoming stream of customers/demand to the service provider i follows a Poisson process, and the customers are served in the order of their arrivals, i.e., under the first come, first served (FCFS) discipline of service. The service times for a given service provider are assumed to be identically distributed and allowed to follow a general distribution. Following the above assumptions, the individual service process is modeled as an M/G/1 queueing system. For the total operating cost of an individual server, we consider a traditional economic framework with two types of costs [START_REF] Guajardo | Cost allocation in inventory pools of spare parts with service-differentiated demand classes[END_REF]. The first type is a linear capacity cost per unit time, which is proportional to the system service capacity. This captures the equipment's depreciation or maintenance fee, employee's salary, etc. We also assume a congestion cost incurred for each unit time the customers spend in the queue. For each service provider i, we then define the following parameters:

• λ i : Mean arrival rate of customers for the provider i;

• X i : A random variable describing the service time at the server i, with mean 1/µ i and coefficient of variation c i ;

• ρ i = λ i /µ i : Server utilization for the provider i, with µ i > λ i ;

• W q,i : Customer expected waiting time in the queue for the provider i;

• h i : Service capacity cost parameter per unit time for the provider i;

• d i : Congestion cost parameter per unit time per customer waiting in the queue at the server i.

For any service provider i, we denote the capacity, the congestion and the total costs per unit time by H i , D i and C i respectively. Using the Pollaczek-Khinchin formula in [START_REF] Pollaczeck | Uber eine aufgabe der wahrscheinlichkeitstheorie[END_REF], we could write

C i = H i + D i = h i µ i + d i λ i W q,i = h i µ i + d i λ i λ i E(X 2 i ) 2(1 -ρ i ) . ( 1
)
The service capacity pooling consists of two typical methods with demand pooling. In the first one, the service providers form a common facility with parallel-servers and one single queue. All incoming customers are served in the multi-server queueing system. In the second one, the service providers share their service capacities together and run as a "super-server", i.e., a single server with a high service capacity. We consider there the second configuration. We assume that s independent service providers of any subset ∅ ⊂ S = {1, . . . , s} ⊆ N would decide to share their capacities as a "super-server" for reducing the collective cost. We suppose that the component arrival processes, with rate λ i for i ∈ S, are independently distributed. Therefore, the combined arrival process in the pooling system, which has a rate λ S = ∑ S λ i , also follows a Poisson process. We suppose that the pooling system provides same services to all customers, and the service times for the pooling server follow a general distribution. We denote the mean service capacity by µ S for the pooling system S. Based on these assumptions, the s providers act as an M/G/1 "superserver" (Figure 1). By using the same technology and paying at the same salary level, we assume here the service capacity cost parameters to be the same h i = h, for all providers in the set N . Because all the customers have equal importance for the pooling system S, it is reasonable to suppose that the system congestion cost parameters are equal, d i = d, for any provider in the set N . In particular, we assume that the coefficient of variation of service times for all providers in the set N are the equivalent c S,i = c S = c N . The total cost of the pooling system S is the sum of service capacity cost and system congestion cost as individual providers. Thus, for any pooling system S ⊂ N , we define the parameters as follows:

• λ S : Mean arrival rate of customers for the pooling system S;

• X S : A random variable, service time at the pooling server S, with the mean 1/µ S and the coefficient of variation c S ;

• ρ S = λ S /µ S : Server utilization for the pooling system S, with µ S > λ S ;

• W q,S : Customer expected waiting time in the queue for the pooling system S;

• h: Service capacity cost parameter per unit time within the subset S;

• d: Congestion cost parameter per unit time per customer waiting in the queue within the subset S.

For a pooling system S, we denote the capacity, the congestion and the total costs per unit time by H S , D S and C S , respectively. The expected total cost per unit time is given by

C S = H S + D S = hµ S + dλ S W q,S = hµ S + dλ S λ S E(X 2 S ) 2(1 -ρ S ) . ( 2
)
With all definitions above, we propose both the individual service model and the pooling service model in M/G/1 queueing systems. Our objective is to verify the benefit and the stability of service capacity pooling. It consists of two steps: to confirm that the service capacity pooling brings benefit to the whole set of service providers; to verify that each individual service provider could get better interest in the coalition structure with its distributed cost from the coalition cost. Cooperative game theory provides a formal method to formulate, structure and analyze the cooperative behavior of independent individuals. In the two following sections, we will build the corresponding cooperative game under the capacity pooling strategy, in order to find the most profitable pooling coalition structure and allocate the total cost of pooling server to each independent service provider.

III. SERVICE POOLING GAME FOR M/G/1 SERVICE

SYSTEMS

In this section, we consider that the service capacity of each individual service provider is fixed. This is a reasonable assumption in several situations, where the changing of basic equipment or physical location is too expensive or almost impossible. We suppose that the pooling capacity µ S of any subset S is the sum of service capacities of all members i ∈ S. Let us denote by C f ix (•), the total cost function of a subset S ⊂ N under the fixed service capacity pooling. With the predetermined system parameters (h, d, c N ), we have

C f ix (∅) = 0, C f ix (i) = C i (λ i , µ i ), C f ix (S) = C S (λ S , µ S = ∑ j∈S µ j ).
(

) 3
Consider a finite set of independent service providers N = {1, . . . , n} (agents), which is known as the grand coalition in cooperative game. Let S be any subset of N , and it is called coalition of agents. In every coalition, the agents could reduce their total costs by sharing their capacities together. We assume that each service provider could only join one coalition, and the pooling cost could be redistributed among the providers with no limitation in the coalition. Thus, a cooperative game with transferable utility (TU-game) (N, C f ix ) is completely specified by its characteristic function C f ix : 2 N → R assigning to any non-empty coalition S.

To simplify the analysis of the game (N, C f ix ), we define f = c 2 N and rewrite equations ( 1) and (2) as follows.

C i = h i µ i + d i λ i λ i E(X 2 i ) 2(1 -ρ i ) = hµ i + d(1 + f ) 2ρ -1 i (ρ -1 i -1)
, for any i ∈ N ; (4a)

C S = hµ S + dλ S λ S E(X 2 S ) 2(1 -ρ S ) = hµ S + d(1 + f ) 2ρ -1 S (ρ -1 S -1)
, for any ∅ ⊆ S ⊆ N. (4b)

Note that the capacity holding cost and the system congestion cost, both are single-variable functions in either the service capacity, or the server utilization. We denote the expected queue length of coalition S by L q,S . Proposition 1 states the effectiveness improvement of service quality in terms of L q,S in the pooling system. Proposition 1. The expected queue length is strictly subadditive in the pooling system with a fixed service capacity.

Proof . For any ∅ ⊆ S, T ⊆ N with S ∩ T = ∅, we suppose that ρ S ≤ ρ T . Then, the utilization of the pooling server S ∪ T has the property: ρ S ≤ ρ S∪T ≤ ρ T . And the queue length

L q,S = (1 + f )/[2ρ -1 S (ρ -1 S -1)
] is an increasing function in 0 < ρ S < 1. Thus, L q,S ≤ L q,S∪T ≤ L q,T . So L q,S∪T < L q,S + L q,T . The subadditivity of expected queue length has been proved.

From Proposition 1, we find that the average number of waiting customers is always reduced in the pooling system. The proof above also shows that L q,S is not monotone, the joint queue length may be increased with new number joining, e.g., when provider i joins coalition S with ρ S < ρ i . This property is similar to that in the M/M/1 service pooling game proposed by Anily in [START_REF] Anily | Cooperation in service systems[END_REF]. We now present the two main results for the game (N, C f ix ) analysis in Theorem 1 and 2. We start with the most profitable coalition structure of the game (N, C f ix ).

Theorem 1. The service pooling game (N, C f ix ) is a strictly subadditive game, and the grand coalition is the most profitable coalition structure.

Proof . In the total cost function C f ix (S) = H S + D S = h S µ S + d S L q,S , H S = h S µ S is additive, and D S = d S L q,S is strictly subadditive based on proposition 1. It is clear that C f ix is strictly subadditive, so (N, C f ix ) is a strictly subadditive game, and any splitting of the grand coalition means an additional congestion cost for the entire set N . Therefore, the grand coalition N is the most profitable coalition structure for the game (N, C f ix ).

Subadditivity is a necessary condition required for the formation of the grand coalition. Theorem 1 states that there is always a benefit if two service providers or pooling systems share their service capacities as a "super-server" with a fixed service capacity. When each provider maintains its individual server with its own capacity, it has to pay its capacity cost and the individual congestion cost. In the context of resource pooling, each participant could save money in the collective congestion cost. Although the profitability of the grand coalition is affirmed by Theorem 1, the existence of stable cost allocation has not been confirmed yet. In order to encourage every provider joining the grand coalition, our interest now is to find a stable allocation rule to share the reduced congestion cost in the coalition derived from service capacity pooling. One of the important properties for the stable cost allocation analysis is the concavity of cost games in the following definition. (i) For any pair of subsets ∅ ⊆ S ⊂ T ⊂ N , and any agent

l ∈ N \T , v(S ∪ {l}) -v(S) ≥ v(T ∪ {l}) -v(T ); or (ii) For any pair of subsets ∅ ⊆ S, T ⊂ N , v(S ∪ T ) + v(S ∩ T ) ≤ v(S) + v(T ); or (iii) For any pair of subsets S ⊂ T ⊂ N \ R, v(S ∪ R) - v(S) ≥ v(T ∪ R) -v(T ).
If (N, C f ix ) is concave, the non-emptiness of the core and the existence of population monotonic allocation scheme (PMAS, which presents a dynamic solution for all sub-games) would be ensured. Unfortunately, the following example illustrates that the game (N, C f ix ) is not concave in general.

Example. Consider the case where h = 0 (because of the additivity of capacity holding cost, this assumption does not affect the final result), d = 1 and f = 0.2, a set N = {1, 2, 3} of three service providers, and the other parameters as defined in Table I.

We use the same arrival and service rates as that in the example of [START_REF] Yu | Capacity sharing and cost allocation among independent firms with congestion[END_REF]. There are big differences among service utilizations of each agent in this situation. By choosing S = {1}, T = {1, 3} with l = 2, we obtain C f ix (S ∪ {l}) -C f ix (S) =

-3.88 < C f ix (T ∪ {l}) -C f ix (T ) = -0.03, meaning that the game (N, C f ix ) is not concave in this setting.
In Table II, the total cost of each coalition and the corresponding costs of Shapley-value allocation, which has x sh 1 = 1.88, x sh 2 = -0.54 and x sh 2 = -0.97, are computed for every coalition S ∈ N with |S| ≥ 2. We find that C f ix ({1, 2}) = 0.37 < x sh 1 +x sh 2 = 1.88+(-0.54) = 1.34, also, C f ix ({1, 3}) = 0.4 < x sh 1 + x sh 3 = 1.88 + (-0.97) = 0.91. It means that the Shapley-value allocation is not stable in this case, although the pooling contribution of each agent is well shown by this allocation. Meanwhile, the general proportional allocation rule x p i = p i C f ix / ∑ j∈N p j , depending on the initial individual service capacity (p i = µ i ) or the own customer arrival rate (p i = λ i ), also could not guarantee the stability of the grand coalition N .

In order to keep all agents staying in the coalition, we should find at least one stable cost allocation if it exists. Unfortunately, we could not give an explicit stable cost-sharing solution for the game (N, C f ix ). However, we prove the existence of the stable cost allocation solutions. To prove the non-emptiness of the core, we use the "Bondareva-Shapley Theorem" [START_REF] Bondareva | Some applications of linear programming methods to the theory of cooperative games[END_REF] (B-S Theorem), which is well known in nonempty core demonstration for TU-games: "A TU-game (N, v) has a non-empty core if and only if it is balanced". The following definitions are the relevant notions of balancedness. Definition 2. A collection B on N is a balanced collection, if for any S ∈ B, it exist its weights β S to make

∑ S∈B β S 1 S = 1 N . This equation is equivalent to ∑ S∋i β S = 1, for any i ∈ N . Definition 3. A cost TU-game (N, v) is a balanced game, if for any balanced collection B on N , we have v(N ) ≤ ∑ S∈B β S v(S) (v(N ) ≥ ∑ S∈B β S v(S) for profit games).
For the balancdness proof of the game (N, C f ix ), we use the following proposition.

Proposition 2. The expected waiting time W q (λ S , µ S ) in the queue is a decreasing and convex function in µ S with a fixed λ S for µ S > λ S .

Proof .

We have

∂W q /∂µ S = -λ S (1 + f )(2µ S - λ S )/[2µ 2 S (µ S -λ S ) 2 ] < 0 and ∂ 2 W q /∂µ 2 S = λ S (1 + f )[λ 2 S + 3µ S (µ S -λ S )]/[λ 3 S (λ S -λ S ) 3 ] > 0, for µ S > λ S . So, W q (µ S ) is decreasing and convex in µ S .
With Proposition 2, we are prepared to prove the nonemptiness of the core for the game (N, C f ix ).

Theorem 2. The service pooling game (N, C f ix ) has a nonempty core, and there are infinitely many solutions in the core if n > 1.

Proof . The game (N, C f ix ) could be divided into two games: the game (N, H f ix ) with H f ix (S) = hµ S , which is a linear game, and the game (N, D f ix ) with D f ix (S) = dL q (λ S , µ S ) = dλ S W q (λ S , µ S ). It is clear that (N, H f ix ) has a core with one core allocation. Now, we will prove that the game (N, D f ix ) has a non-empty core by B-S Theorem.

For any balanced collection B on N , we have:

D f ix (N ) = dλ N W q (λ N , µ N ) = dλ N W q (λ N , ∑ S∈B β S µ S λ N λ S • λ S λ N ) (5a) ≤ dλ N • ∑ S∈B β S λ S λ N W q (λ N , µ S λ N λ S ) (5b) = ∑ S∈B β S dλ S W q (λ N , µ S λ N λ S ) = ∑ S∈B β S dλ S [ 1 + f 2 λ -1 N 1 ρ -1 S (ρ -1 S -1) ] < ∑ S∈B β S dλ S W q (λ S , µ S ) (5c) = ∑ S∈B β S D f ix (S).
From the definition of a balanced collection, there is ∑ S∈B β S µ S = µ N to guarantee the equality in (5a). Meanwhile, the inequality in (5b) holds by the convex property of W q (λ S , µ S ) in Proposition 2 and ∑ S∈B β S λ S = λ N based on Definition 2. Since S is a subset of N , the inequality in (5c) holds.

Thus, the game (N, D f ix ) is a balanced game. According to the B-S Theorem, the game (N, D f ix ) has a non-empty core. Using Lemma A.2 of [START_REF] Karsten | Resource pooling and cost allocation among independent service providers[END_REF], we could simply state that: if n > 1, the game (N, C f ix ) has infinitely many core allocations. The proof of the theorem is completed.

From Theorem 2, we could conclude that the service pooling game (N, C f ix ) with a fixed service capacity always has a cost allocation to guarantee the stability of the grand coalition. Thus, the grand coalition is the most profitable coalition solution in the context of capacity pooling. For the further results of the individual pooling costs, the explicit numerical solution of the game (N, C f ix ) could be computed by a Linear Programming method, e.g., the Equal Profit Method in [START_REF] Frisk | Cost allocation in collaborative forest transportation[END_REF] or the Nucleolus computing [START_REF] Schmeidler | The nucleolus of a characteristic function game[END_REF].

IV. COST-SHARING IN M/G/1 POOLING SYSTEM

Obtaining a stable allocation is one important objective of the service pooling problem. We denote the cost allocations of the grand coalition by x = {x i , . . . , x n } for the cost TU-game (N, C f ix ). The stable allocation rule should be efficient ∑ i∈N x i = C N and justified by coalition rationality ∑ i∈S x i ≤ C S for any subset S in N . In this section, we propose a reasonable expression for Equal Profit Method, and compare the expression proposed with another rules and its original form by numerical experiments.

A. Cost allocation rules 1) Shapley-value:

The Shapley-value, introduced by Shapley in 1952 [START_REF] Shapley | A value for n-person games[END_REF], is a popular allocation concept in cooperative game theory. It provides us with a well-known fair allocation rule for cooperative games, but there is no general property to keep the stability of the grand coalition. The Shapley-value is defined as the average marginal cost of each cooperative subset for each participant, and it is given by

x sh i = ∑ S⊆N \{i} |S|!(|N | -|S| -1)! |N |! [C S∪{i} -C S ], (6)
where C S∪{i} -C S is the marginal cost of provider i as the last player joining the coalition S. Shapley-value is the unique allocation rule satisfying the four desirable properties: anonymity, efficiency, additivity and dummy player property.

In order to verify the Shapley-value is a core allocation for a cost cooperative game (N, v), it is sufficient to test the concavity of the characteristic function v, which has been proved by [START_REF] Shapley | Cores of convex games[END_REF]. Unfortunately, the game (N, C f ix ) defined here is non-concave and the Shapley-value couldn't guarantee the stability of grand coalition in general.

2) Tau-value: The set of cost allocations, defined by the lower bound

M i (N, C f ix ) = C N -C N \{i} and the upper bound m i (C f ix ) = max S:i∈S {C S - ∑ j∈S\{i} M j (N, C f ix )} of the shared cost,
includes all the core allocations. The τvalue, defined by Tijs in 1981 [START_REF] Tijs | Bounds for the core of a game and the t-value[END_REF], is a cost allocation defined as

x τ i = αm i (C f ix ) + (1 -α)M i (N, C f ix ), (7)
with the unique α ∈ [0, 1] calculated by the efficiency of x τ . It is a special linear combination of M i (N, C f ix ) and m i (C f ix ). For two player games, the τ -value is equal to the Shapley-value and it presents a stable cost allocation for all quasi-balanced two player games. Although we could not give an explicit demonstration of its stability, the τ -value proposes stable results in the following experiments.

3) Nucleolus: The excess of a cost allocation x for a coalition S ⊆ N is defined as

e x,S = C S - ∑ i∈S x i , (8)
which is been used to measure unhappiness of the coalitions by the lexicographic ordering comparison for all possible allocations. When the coalition cost is allocated by x, S is more satisfied with a higher e x,S . Based on the concept of minimized maximum unhappiness, the Nucleolus was introduced by Schmeidler in [START_REF] Schmeidler | The nucleolus of a characteristic function game[END_REF]. Although Schmeidler didn't define it explicitly, its uniqueness has been proved by Driessen in 1969 [START_REF] Driessen | Cooperative Games, Solutions and Applications[END_REF]. It is a stable allocation rule for all TU-games with a nonempty core, and coincides with dummy player property, zero independent and reduced-game property.

4) Equal Profit Method:

Another interesting definition of "fair" is the equal profit concept, which defined by Frisk et al. in 2010 [START_REF] Frisk | Cost allocation in collaborative forest transportation[END_REF]. They describe the cost TU-games as a linear programming problem to minimize the gap of the relative savings

r i = (C i -x i )/C i . min f (x) s.t f (x) ≥ max{r i -r j }, ∀i, j ∈ N ∑ i∈S x i ≤ C S , ∀S ⊂ N ∑ i∈N x i = C N , ( 9
)
where the results x EP M defined as the core allocation calculated by Equal Profit Method (EPM). It seems to be a "fair" and stable allocation rule considering the most closed relative savings for each individual, despite the different contribution of each participant to the grand coalition N . This "fair" definition just considers the individual factor. In some cases, the participant, which has a low individual payment, might do not want to join the coalition in order to protect its individual information, although it could get a same level relative saving with others.

5) EPM based on Contribution

Weights: Now, we define the relative contribution weights w i = λ i /(µ i -λ i ) for each participant in our service pooling game. The customer arrival rate λ i describes the individual requirement of each participant, and the system idle capacity µ i -λ i presents the individual contribution to the collaboration. Then, we propose the new relative saving formula as

rw i = w i * C i -x i C i = λ(C i -x i ) (µ -λ)C i . ( 10
)
Thus, we get the EPM with Contribution Weights (EPM-CW) as

min f (x) s.t f (x) ≥ max{rw i -rw j }, ∀i, j ∈ N ∑ i∈S x i ≤ C S , ∀S ⊂ N ∑ i∈N x i = C N . ( 11
)
With the constraints defined in equation [START_REF] Anily | Cooperation in service systems[END_REF], EPMCW presents a stable allocation rule by solving the linear programming problem above, if the core is not empty. The contribution of each provider has been considered in the relative contribution weights w i , and the results are easily controllable by w i with different definitions, e.g., w * i = λ 2 i /(µ i -λ i ).

B. Numerical results and analysis

We illustrate the previous concepts in three typical service pooling cases of 6 service companies, which have equal individual service capacities. To do so, we consider the three following sets of data with different h ∈ [0, 1] (the variation of the three system parameters h, d, f have similar impacts on the results). The first case presents a set of companies with low server utilizations. It means that all the companies in this set are not very efficient. There are both the low efficient companies and the busy companies in the second case. And the third one only consists of the busy companies. The initial parameters for each set are listed in Table III.

Fig. 2, 3 and 4 reveal the distributed costs, using different preceding concepts described in IV-A , for our game (N, C f ix ) in the cases above under h = 0, i.e., the quality driven case. We select two different relative contribution rates for EPMCW calculation: w i for EPMCW1 and w * i for EPMCW2. From these figures, we find that the results given by the τ -value and the nucleolus are very close, especially in the third case. The Shapley-value reflects the contributions of each provider for all the possible coalitions. Unfortunately, the corresponding allocations are not stable in all the three cases, e.g., x sh 1 +x sh 5 = 1.2811 ≥ C {1,5} = 0.8067 in the case 3.

EPM provides a stable allocation rule, which is a little far from the others for several companies, particularly for the company with relative large or small contribution to the coalitions. The goal or the "fair" defined by EPM is to minimize the gap between the relative earnings of players, and the constraints consists of all stable requirements. Thus, the companies with a special contribution might not satisfy the similar relative saving. For example, the first company in Fig. 4, which has a low individual operating cost, will pay nothing by EPM computing, but it could earn money in other allocations. EPMCW1 and EPMCW2 give closed results in Fig. 3 and4, but they propose very different results in Fig. 1. In these figures, we find that the EPMCW2 is more closed to the Shapley-value. It seems like w * i presents a more suitable contribution weights than w i defined in equation [START_REF] Yu | Capacity sharing and cost allocation among independent firms with congestion[END_REF]. With same individual service capacities used for all companies, this phenomenon could be explicated by the characteristic function C f ix of this service pooling game defined in equation ( 4). It is easy to find that the second contribution weights w * i are more closed to the individual operating cost C i .

Table IV shows the relative savings r i for each distributed cost obtained by the previous rules and compared to the individual costs in the set of low efficient companies (the case 1 in Fig. 2). When h = 0, the service capacity pooling brings a large relative saving to all companies. The relative difference is large between the result of EPMCW1 and EPMCW2. While the relative saving declines, h = 0.5, the difference between EPMCW1 and EPMCW2 reduces. If the relative saving is small enough, e.g., h = 1 with r N ≤ 3%, the two allocations given by EPMCW and the allocation of EPM are very similar.

V. CONCLUSION

Using cooperative game theory, we have approached the cost sharing problem among a set of independent service providers in the complete service capacity pooling system.

We extended the service pooling game in M/G/1 service systems. When the service capacities are fixed, the service pooling game would be a sum of two games: an additive service holding cost game and a subadditive service congestion game. We have proved that the stable cost allocation always exists. Thus, the stable numerical cost allocation could be derived using linear programming computing for any cases. Considering the contribution and requirement of each service providers, we propose an improved expression of Equal Profit Method, the Equal Profit Method based on Contribution Weights. We have applied it in our M/G/1 service pooling cases. With numerical experiments, we found that it provides a reasonable stable allocation rule, which could reflect the contributions of each participant in the coalition.

There are possible generalizations and complementarities that can be taken in future research. In our setting, (h, d, f ) are system parameters. Because of the problems based on the localization, it is also reasonable to suppose that d i is specialized for each service provider. The expected waiting time could increase by service capacity pooling for several service providers. For this, we could not guarantee the subadditivity of the congestion cost. In this way, the grand coalition may not be the most profitable coalition structure for this new game. Thus, the coalition formation problem should be considered in the service pooling game study.

It would be also interesting to extend the analysis of this paper to the case of service systems with customers abandonment or callback. Indeed, the abandonment is a common phenomenon in service systems. The customers will abandon with the unsatisfying of the real waiting times. Thus, the stability requirement λ < µ is not necessary. Considering the callback of the fail/unsatisfying demand, it is necessary to propose a fair indicator to evaluate the quality of services. There are a few options here: the customers waiting times, the service times, the probability of failure, etc. It will be an interesting future research to analyze the properties of the relevant games.

Fig. 1 .

 1 Fig. 1. Centralized Coalition of a Set of Service Providers

Definition 1 .

 1 A TU-game (N, v) is concave if:

Fig. 2 .Fig. 3 .

 23 Fig. 2. Cost allocations of case 1 under h = 0 by Shapley-value, Tau-value, Nucleolus, EPM, EPMCW1 and EPMCW2

Fig. 4 .

 4 Fig. 4. Cost allocations of case 3 under h = 0 by Shapley-value, Tau-value, Nucleolus, EPM, EPMCW1 and EPMCW2

TABLE III

 III

		.	CUSTOMER ARRIVAL RATES AND SYSTEM PARAMETERS
		Initial data					Customer arrival rates
	µ	h	d	f	No.	1	2	3	4	5	6
	10	[0, 1]	2	0.2	1	2	3	3	4	3.5	4
		-			2	7	9	8	7	8.5	9.5
		-			3	2	7	4	7.5	9	3

TABLE IV .

 IV RELATIVE SAVINGS r i FOR CASE 1 WITH DIFFERENT RULES UNDER h = 0 AND 0.5

	h = 0	Shapley	Tau-v	Nucl.	EPM	E-CW1	E-CW2
	Com 1	173.0%	128.5%	110.5%	84.7%	164.0%	164.0%
	Com 2	92.6%	84.3%	84.9%	85.0%	104.7%	79.8%
	Com 3	92.6%	84.3%	84.9%	85.0%	104.7%	79.8%
	Com 4	74.3%	81.9%	83.5%	84.6%	68.1%	81.5%
	Com 5	80.3%	81.9%	82.7%	85.1%	84.2%	79.9%
	Com 6	74.3%	81.9%	83.5%	84.6%	68.1%	81.5%
	Stable	No	Yes	Yes	Yes	Yes	Yes
	h = 0.5	Shapley	Tau-v	Nucl.	EPM	E-CW1	E-CW2
	Com 1	2.05%	1.52%	1.31%	1.94%	1.94%	1.94%
	Com 2	2.77%	2.52%	2.51%	3.14%	3.14%	3.14%
	Com 3	2.77%	2.52%	2.51%	3.14%	3.14%	3.14%
	Com 4	4.47%	4.93%	5.02%	3.94%	3.82%	3.82%
	Com 5	3.48%	3.55%	3.58%	3.94%	4.19%	4.19%
	Com 6	4.47%	4.93%	5.02%	3.94%	3.82%	3.82%
	Stable	No	Yes	Yes	Yes	Yes	Yes