**Abstract**

The objective of this review is to provide a general view of the literature of different game theory methods which are implemented in order to allocate cost in water resources. Specifically, several cooperative game theory solution concepts will be included on this research such as the Shapley Value, the Non-Separable Cost Gap (NSCG), the Core and some of its variants. These methods will be discussed on the basis of efficacy and equity. To conclude, it will be assessed the appropriateness of each method so as to allocate joint cost in water resources in fair ways.** **

**Table of Contents**

2.3.1 The Least Core and the Nucleolus

2.3.2 The Weak Least Core and the Weak Nucleolus

2.3.3 The Proportional Least Core and the Proportional Nucleolus

**Glossary**

SCRB: Separable Cost – Remaining Benefits

NTU: Non-Transferable Utility

WN: Weak Nucleolus

PN: Proportional Nucleolus

NSCG: Non-Separable Cost Gap

NSC: Non-Separable Cost

**Chapter 1: Introduction**

One of the most serious issues for the public enterprises is how to allocate the cost of goods or services with respect to fairness (Young et. al, 1982). Particularly, there is an extensive concern in the water resources field about the way cost is divided in a shared project among multiple participants (Okada, 1981). This issue is called cost allocation problem and its methods will be discussed in this review. In common water resources, it is observed that the sum of the marginal cost of each user is less than the entire cost of the project. (Young et. al, 1982). Over the recent years, many researches have been made on cost allocation in water resources around the world. A great number of these investigations implemented and focused on game theory methods so as to find solutions for cost allocation problems. In this literature review, cooperative game theory techniques will be analysed that were used in several occasions in order to allocate joint cost in fair ways.

Cooperative Game Theory methods contribute in finding out successful solutions when several numbers of players are called to decide independently and collectively (Dinar et al., 1992). As a result, Cooperative Game Theory is considered as a more effective model than a market model. Specifically, a market model refers to a significant number of agents who are not deviate from the market price. In this case, Cooperative Game Theory is assumed that is less efficient than model market due to the comparison among players is not fully captured on the basis of utility scales (Dinar et al., 1992). It is evident from the bibliography that Cooperative Game Theory methods have been implemented in several cases in which yielded costs and profits by cooperation, are distributed among the agents.

One of the most famous cost allocation solution concepts that have been applied in water resources field, is the Separable Costs – Remaining Benefits (SCRB) technique. This method was implemented first for multipurpose reservoir projects in the United States during the 1950 decade and in other countries (Young et. al, 1982). Despite the wide implementation of this technique, many researches, found out that it has remarkable weaknesses. Subsequently, due to the fact that common methods such as SCRB could not respond in the bargaining of cost allocation, researchers were led to develop a new suggestion in the water resources area (Okada, 1981).

**Chapter 2: Literature Review**

In this chapter we survey several Cooperative Game Theory methods which solve the cost allocation problems in water resources, based on commonsense, fair and equity by taking the strategic possibilities into account (Young et. al, 1982). These methods that will be discussed are the Core and its extensions, the Shapley Value and the Non-Separable Cost Gap (NSCG).

**2.1 The Core**** **

Dinar et al. (1992) implemented the core method on a case study which illustrates a cooperative game that includes three farms (1, 2, 3). In many regions, irrigation water allocation is subject to water rights (quotas) which have not changed over the years. Thus, several problems are caused in the water allocation. Dinar et al. (1992) describe a farm area where the water is limited due to the above problem, and the additional resources are not appropriate due to the high salinity. The farms cooperate in order to determine the quality of the water and to transfer the water amongst them. Therefore, the farms seek to find a joint solution about the cooperation in the area and the income distributions issues due to the relevance of these two problems. To be more specific, the cooperation refers to transfers of water only with the distribution of income among the farms determined by those transfers (Dinar et al., 1992). For instance, Farm 1 transfers water to Farm 2 in a particular month, and the next month Farm 2 develops a reverse transfer process. This is called the Non-Transferable Utility (NTU). In the NTU situation regional income maximisation depends on income distribution constraint (Dinar et al., 1992) which means that they have to be solved as one. On this concept, direct transfers of income may occur.

The core of a cost game is described as the set of all cost allocations in the cost game and it refers to the cost allocations that can be improved upon by no coalition

sin

S, where

Sstands for the set of all feasible coalitions (Hildenbrand and Kirman, 1976, Dierssen & Tijs, 1985, Dinar et al., 1992). In this problem, we will use income instead of cost. The authors are wondering which coalitions between these farms are rational and feasible. It is observed that the technical feasibility can be evaluated by the construction of the regional water supply system. On the other hand, the socio-economic feasibility can be affected due to possible strategic behavior by the farms. In addition, Dinar et al. (1992) suppose that all pairwise coalitions are feasible.

The core of the three-farm cooperative in the NTU situation is defined by the forms below:

y2≥g21y1 (2.1)

y2≥g23y3 (2.2)

y3≥h31y1 (2.3)

y1+y2+y3=V1,2,3 (2.4)

(Dinar et al., 1992)

Where

yiis the farm income,

g2iyiis the income transformation function for the coalition of Farms 2 and

i (i=1,3),

h31(y1)is the income transformation function for Farms 3 and 1, and

V1,2,3is the total income of the three farms cooperation (Grand coalition). Its magnitude is subject to the income allocations

yi. It is also mentioned that any point

g1y1, y2meeting

y2≥ g21y1meets also

y1≥g21-1(y2). Same inverse forms apply to

g23y3and

h31y1.Regarding the constraints (2.1)-(2.3), satisfy the individual rationality requirements of the farms (Dinar et al., 1992).

The solution of the core of the three farms cooperative game comes from the maximising of

yiRwhich is the farm income with cooperation. In addition,

Ris defined as the water quality. Farm income with cooperation is also dependent on the constraint

yiR≥yi0(3), where

yi0is the farm income without cooperation, and on the constraints (2.1)-(2.3) for several combinations of

y2and

y3. The non-linear functions

g21(y1),

g23(y3)and

h31(y1) were piece-wise linearly approximated and a separable programming routine was used (Dinar et al., 1992). The solution of the problem was derived separately for each different pre-determined values of

R. Furthermore, it is noticed that the optimal

Rmay have different values depending the area on the core representation.

Figure 2.1 illustrates the computed core, based on the additional that is produced by cooperation. It can be easily seen that the point (0,0,0) is the income of the three farms without cooperation. Additionally, the values of the three axes represent the additional income. On the graph, it can be observed the additional incomes of Farm 1,2 and 3. The shadowed field in the

y2*y3*plane expresses combinations of

y2*y3*that are not subject to the restrictions (2.1)-(2.3) (Dinar et al., 1992).

Figure 2.1: The core of the three farms cooperative game in the NTU situation (Dinar et al., 1992)

Dinar et al. (1992) come to several conclusions after implementing the core. First, they mention that in this study, the size of the core is very large and it is not a convex set. As a result, the possibility of producing new points in the core of selected points lying in the core is reduced. Second, computing the core of the three farms cooperative game requires heavy calculations. In a coalition with more members, the computations might be prohibitive (Dinar et al., 1992).

In conclusion, the authors seem to be skeptical about the practicality and the effectiveness of the core on applications like the above.

**2.2 Shapley Value**** **

The Shapley Value is a cooperative game theory method and one of most widely applied technique on water resource projects. For n players, it is defined as:

yi=∑s=1ns-1!n-s!n!∑S:i∈S S=s[cS-cS-i] (2.4)

(Young et al, 1982)

According to the founder (Shapley, 1953), this is one of the earliest allocation methods which is based on a consistent set of postulates about the way that an allocation should be applied. Specifically, all players have to declare participation in a specific order. If a coalition

Shas already created and everyone has joined, the marginal cost contribution to

Sof the last member of the coalition is

c(S) – c(S – i)(Young et al., 1982). Thus, the Shapley Value is calculated using the average marginal contribution of each player.

Young et al. (1982) implemented the Shapley value on the water supply issue of the three nearby municipalities in Sweden, that we mentioned previously. On the Table 2.1, the Shapley Values for each municipality is presented.

Table 2.1: The Shapley Values for Municipalities A, B and C (Young et al., 1982)

The first column represents the six possible orders for signing up and the rest of the columns describe the marginal contribution of each municipality (Young et al., 1982). Thus, according to Young et al. (1982) the calculation of the Shapley value is derived by the dividing the possible marginal contributions of each municipality (Total) by the number of possible orders of signing.

Young et al. (1982) applied also the Shapley value on another cost allocation game about the water supply in the region of Skone in Sweden, among 18 municipalities which are divided by 6 groups. Specifically, this cost allocation problem refers to a project about the designing of an alternative way to be obtained water by several of these municipalities. The total cost of this project was counted to 83.82 million Swedish Korona (Skr). Thus, Young et al. (1982) applied the Shapley value and other cost allocation methods obtaining the below results.

Table 2.2: Cost Allocations of Skr 83.82 Million by Seven Method (Young et al., 1982)

After evaluating the above cost allocation techniques, Young et al. (1982) observed that a calculation of the Shapley value requires the alternative costs for all possible subset. In addition, the Shapley Value fails the group rationality and marginality tests (Young et al., 1982).

**2.****3**** Extensions of the Core**

In this chapter we will refer to situations in which the core does not exist. The way to gain a solution for the game is to relax the inequalities that define the core, which is called extending the core (Sadegh & Kerachian, 2011). These cooperative game theory methods that arise by extending the core are the Least Core and Nucleolus, the Weak Least Core and the Weak Nucleolus and the Proportional Least Core and the Proportional Nucleolus.

__2.3.1 The Least Core and the Nucleolus__

Shapley & Shubik (1966) were the first who introduced a method in case that the core is empty. In 1979, Maschler et al. (1979) named this cooperative game theory technique as the least core in order to ensure existence and uniqueness of the allocation vector (Drechsel, 2010). The smallest possible uniform tax

zis imposed to all the coalition formations except for the grand coalition

N(Sadegh & Kerachian, 2011). This imposing tax on all proper subgroups is considered a way of encouraging the whole group to stick together (Young et al., 1982). The least core solution concept is defined as the set of cost allocations

xof a cooperative cost game

(N;u)(Schulz & Uhan, 2013) that are optimal solutions to the linear program:

z* = minimize z (2.5)

subject to xN= uN, (2.6)

xS≤ uS+z for all S⊆N, S≠∅,N (2.7)

(Schulz & Uhan, 2013)

The optimum value

z*of the above linear program is the least core value of the game

(N;u)(Schulz & Uhan, 2013). An alternative way to write this linear program is:

z*= minx:x(N)=u(N) maxS⊆N, S≠ ∅,N ex,S (2.8)

Where

ex,S= xS-uS for all S⊆N. The Least Core is always explicit and exists, despite the fact that the core may exist or may not exist (Schulz Uhan, 2013). (2.9) (Schulz & Uhan, 2013)

The

ex,Sdenotes the dissatisfaction or the excess (Young et al.,1982) of a coalition

Sfor a cost allocation

x. In other words, it describes the additional cost that a coalition

Sis charged when costs are allocated on the basis of

x. Thus, the least core contributes to the minimisation of the maximum dissatisfaction of any coalition. This means that the least core includes the cost allocations which are “least objectionable” (Schulz & Uhan, 2013). In case that the core of a cooperative game exists, the least core value of any coalition in the core is negative or zero. In addition, the absolute value of the dissatisfaction of a coalition depicts its earnings according to this cost allocation. Regarding to this case, the least core constitutes an improvement of the core. To put it differently, the least core comprises all the adequate and stable cost allocations that conduce to the maximisation of the minimum benefits of any coalition (Schulz & Uhan, 2013). On the other hand, in case that the core of a cooperative game does not exist, the dissatisfaction represents the smallest possible penalty that is charged to any coalition which acts independently. This penalty, urges the players to cooperate while assuring an efficient and a steady cost allocation. Except for the above, the least core value can be considered as the minimum cost to form a coalition for which applying the subgroup rationality, subjects to

x(S) ≤ u(S)for all

S ⊆N, is not worth it (Schulz & Uhan, 2013).

In accordance with Maschler et al. (1979), the least core is related to other cooperative game theory solution concepts such as the nucleolus (Schmeidler, 1969). More specifically, in a cost allocation

x∈RN, the excess vector

θ(x)is defined as the

2N-2dimensional vector which contains the

ex,Sfor all

S ⊆ Nin order that

S≠∅,N. The nucleolus solution concept is the cost allocation that lexicographically contributes to the minimisation of the excess vector

θx(Schulz & Uhan, 2013). Particularly, Maschler et al. (1979) presented that for a cooperative game

(N,u)the calculation of nucleolus is achieved by solving

|N|linear programs of (2.5)-(2.7).

Nucleolus method has been implemented to allocate costs in water resources a number of times. To be more specific, Shoubi et al. (2013) applied the nucleolus method in a cost allocation game for building a joint water reservation system among four municipalities. Several kinds of coalitions of the municipalities were formed in order to assess the performance of the methods that were applied. Below, Figure 2.2, Table 2.3 and Table 2.4 depict the results that were obtained by implementing the nucleolus technique.

Figure 2.2: Comparison between allocated costs based on different methods and cost incurred to each municipality in noncooperation situation (Shoubi et al., 2013)

Table 2.3: Comparison of the results based on different methods (in million$) (Shoubi et al., 2013)

Table 2.4: Percentage of benefits earned by each municipality based on different concepts (Shoubi et al., 2013)

Shoubi et al. (2013) compared the nucleolus with SCRB, proportional allocation methods, and the Shapley value. Except for the proportional allocation methods, the remainder of them take into consideration both individual and group rationality in a coalition. This means that no municipality pays more than the amount it would have paid, if it had gone alone. In contrast the proportional allocation methods do not follow the individual and group rationality hence, they will be excluded from the comparison. Figure 2.2 and Tables 2.3 and 2.4 show that, the municipality A earns more after applying Shapley value, while municipality B and C earn more from nucleolus. Regarding the municipality D, it earns more by using SCRB technique. Finally, Shoubi et al. (2013) came into the conclusion that the nucleolus is the most appropriate technique. Despite that, Shapley value and SCRB are considered as reliable methods for cooperation.

__2.3.2 The Weak Least Core and the Weak Nucleolus__** **

The method of Weak Least Core is to some extent similar to the Least Core (Sadegh & Kerachian, 2011). Let us assume that a minimum uniform tax is inflicted on every player who acts individually out of the whole group (Young et al., 1980).

Therefore, we can determine the least

εfor which there is a solution

xto the system below:

∑Sxi≧uS-εS ∀ S⊂N (2.10)

∑Sxi=uN (2.11)

(Young et al., 1980)

Where

|S|indicates the number of players that form the coalition

S. The weak least core is defined by the set of all corresponding imputations

x(Young et al., 1980). According to Shapley and Shubik (1973), for any ε, the set of all solutions of the (2.10) and (2.11) relationships is named “weak ε core” or “weak least core”. As in the calculation of the nucleolus by defining the excess of

Sto be equal to:

ε= uS-∑Sxi|S| (2.12)

(Young et al., 1980)

we can derive a solution which is called the weak nucleolus.

This method seems to be almost identical with the nucleolus technique but it has been proved that it has an additional significant feature not possessed by the nucleolus. Namely, Aoki (1996) showed that weak nucleolus is possible to allocate larger amount of cost savings to high contribution players and smaller amount to players who their contribution is low. To put it differently, weak nucleolus is more sensitive to player’s contribution than the nucleolus.

On the other hand, weak nucleolus may not satisfy the individual rationality when the core is empty (Young et al., 1980). In accordance with Grotte (1970, 1976), if we set as a constraint the individual rationality then this method will overcome this disadvantage. In spite of this, in consonance with the dummy principle, players who contribute nothing to savings have to be excluded from the coalition (Young et al., 1982). As we discussed weak nucleolus may allocate a small amount of cost savings to players whose contribution is low. Therefore, weak nucleolus fails to follow this principle.

__2.3.3 The Proportional Least Core and the Proportional Nucleolus__

An alternative way to extend the core is to set a minimum tax (or subsidy) on all coalitions based on the proportion of their cost (Young et al., 1980). Therefore, we solve the system below, assuming a tax rate

t:

mint

Subject to

∑Sxi≧1-tuS ∀ S⊂N (2.13)

and

∑Sxi=uN (2.14)

(Young et al., 1980)

Young et al, (1980) mentioned that there is a smallest possible

tif

uS>0for

S≠N.As in the calculation of the nucleolus by defining the excess of

Sto be equal to:

ε= uS-∑Sxiu(S) (2.15)

(Young et al., 1980)

we can derive a solution which is called the proportional nucleolus. In case that

uS=0, we assume that

a/0>b/0if

a>b(Young et al., 1980).

Moreover, Drechsel (2010) mentioned that in 1984, Lemaire (1984) presented the difference between the nucleolus and the proportional nucleolus as follows: “In one case coalitions are taxed in order to make the core exist, in the other case coalitions are subsidised in order to reduce the core to a single imputation”.

In addition, it is perceived that proportional nucleolus has similar characteristics as weak nucleolus. More specifically, Aoki (1996) observed that proportional nucleolus allocates larger amount of cost savings to the high contribution player. Furthermore, it allocates smaller amount of cost savings to the low contribution player. Thus, proportional nucleolus encounters the same difficulty as weak nucleolus. In addition, he noticed that proportional nucleolus may not allocate any cost saving to the low contribution players, in a few cases (Aoki, 1996). Thus, proportional nucleolus seems to be unfair to players that contribute extremely low in a coalition. Finally, Aoki (1996) came into the conclusion that proportional nucleolus is similar as weak nucleolus but it is more sensitive to player’s contribution.

__2.____3____.4 Numerical Example__** **

As discussed in the previous sections, Young et al.(1980) extended the least core and introduced two nucleoli. One was the Weak Nucleolus and the other is the Proportional Nucleolus (Aoki, 1996).

In 1981, Okada (1981) applied the weak nucleolus and the proportional nucleolus methods on a cost allocation problem which concerns the river management, the hydroelectric power, the municipal water supply and the industrial water supply in Japan.

He defined the weak nucleolus as:

λS=S λu=1 (2.16)

(Okada, 1981)

Where

Sis the subsets of the coalition groups,

λSis the weight to be assigned to the proper individuals or subgroups,

|S|is the size of subset

Sor in other words the number of uses who create coalition

Sand

uis one of the uses (Okada, 1981). This means that the weights have to be allocated to all depending on the size of the coalition.

He defined the proportional nucleolus as:

λS=∑u∈SC(u)-CS λu= 0 (2.17)

(Okada, 1981)

Where

C(u)is the alternative individual cost of use

uand

C(S)is the cost of an alternative project (coalition

S) (Okada, 1981). In this method the weights have to be allocated to all depending on the sum of the amounts that all uses which belong to the coalition

Sthat prefer to cooperate rather than go alone.

In accordance with Okada (1981) the weak nucleolus and the proportional nucleolus methods satisfy the core, if it is formed. This happens due to the fact that they always satisfy the monotonicity principle[1]. Below, the Tables 2.5.a and 2.5.b illustrate the results of the weak nucleolus and the proportional nucleolus with direct costs specified and unspecified.

Table 2.5.a: Cost Allocation using Weak Nucleolus and Proportional Nucleolus with Direct Costs Specified

(Okada, 1981)

Table 2.5.b: Cost Allocation using Weak Nucleolus and Proportional Nucleolus with Direct Costs Unspecified (Okada, 1981)

It can be seen from the Tables that the results of the proportional nucleolus and the weak nucleolus are identical for both cases.

Moreover, Okada (1981) compared the above methods with the conventional cost allocation method SCRB. After assessing the results for each method, he came into the overall conclusion that the proportional nucleolus and the weak nucleolus are more advantageous than the SCRB method.** **

**2.4 ****Non-Separable Cost Gap**** **

Driessen & Tijs (1985) presented a new cost allocation method, the Non-Separable Cost Gap (NSCG). According to the authors, this method is derived from the

τvalue which is a game theoretical concept established by Tijs (1981). First, they set a cost game

(N;c)with a nonnegative cost gap function

gc The cost gap function gc describes the remaining alternate cost of coalition T (Driessen Tijs, 1985).and a player

i ∈N, where

Nis the total number of players (Driessen & Tijs, 1985). Then, they set as

Tthe coalition and as

ithe player of this coalition. Each player

idenies any cost allocation, that requires to pay more than

SCic+ gcT.[2] The rationale of player

iis based on the threat of creation a coalition

Tand to set a different cost allocation

c(T). In this cost allocation, all the members are required to pay only their separable costs except for the player

iwho pays the remaining cost.

The remaining cost is equal to:

cT- ∑j ∈ T-iSCjc

or

SCic+gcT

(2.18)

(Driessen & Tijs, 1985)

In every coalition

T, the above motive of player

iis implemented and as a result player

iis not going to be charged more than:

minT;i∈T [SCjc+gcT

]

or

SCic+minT;i∈TgcT (2.19)

(Driessen & Tijs, 1985)

Driessen & Tijs (1985) established the concession amount of player

iin a cost game

(N;c)by

λic= minT;i∈TgcT (2.20)

(Driessen & Tijs, 1985)

The concession amount

λicof player

i is seen as his maximal contribution to the non-separable cost

NSCc NSCc is the remaining cost in a game resulting after the allocation of the separable cost to each player. It is defined as NSCc=cN- ∑j=1nSCj(c). (Driessen Tijs, 1985)(Driessen & Tijs, 1985). The authors supposed that the sum of those maximal contributions is at least the non-separable cost:

∑j=1nλjc≥NSCc (2.21)

(Driessen & Tijs, 1985)

The NSCG technique is derived when non-separable cost is allocated among the players depending on their concession amounts. As long as the cost gap function is not negative and (2.21) is met in the cost game

(N;c), the cost allocated to player

ithrough NSCG method is defined as:

NSCGic= SCic

NSCc=0 (2.22)

= SCic+ λic∑j=1nλjc-1NSCc NSCc>0 (2.23)

(Driessen & Tijs, 1985)

Moreover, according to the paper:

NSCGc=SCRB(c)

when

λic=ciand

-SCic= gci for all i∈N. (2.24)

Driessen & Tijs (1985) implemented the NSCG method on the example was set by Young et al. (1982, p. 464) about three nearby municipalities (1,2,3) which built a shared water supply in order to be provided with municipal water. In this cost game

(N;c)where

N={1,2,3}, we have the below cost values:

c(1) = 6.5 c(12) = 10.3 c(123) = 10.6

c(2) = 4.2 c(13) = 8.0

c(3) = 1.5 c(23) = 5.3

(Driessen & Tijs, 1985)

Where the costs are in dollars

×106.

Below, Table 2.6 describes the comparisons between several cost allocation techniques. It can be seen that

NSCc=10.6-8.2=2.4. In addition, SCRB and NSCG methods seem to have identical results. This is due to the convexity of

c(Driessen & Tijs, 1985).

Table 2.6: Comparative Results for the Convex Cost Game (Driessen & Tijs, 1985)

The convexity of c means that the core of the cost game is the convex hull of the cost allocations (6.5, 3.8, 0.3), (6.1, 4.2, 0.3), (6.5, 2.6, 1.5), (5.3, 4.2, 1.1), and (5.3, 3.8, 1.5) (Driessen & Tijs, 1985). The core is formed below:

Figure 2.3: Shaded pentagon represents the core and the indicated point inside it is equal to the cost allocation by the NSCG method (Driessen & Tijs, 1985)

Moreover, the authors evaluate the NSCG method in the example that was set by Young (1982, p.2) where

N={1,2,3}and the costs are:

c1= 15 c12= 35 c123= 78

c(2) = 20 c(13) = 61

c(3) = 55 c(23) = 65

(Driessen & Tijs, 1985)

In this case, the cost game is not convex due to the fact that

c(13)+ c(23) < c(123) + c3(Driessen & Tijs, 1985). Table 2.7 below, illustrates the cost allocations by several methods. It is worth to mention that

NSCc= 78 – 73 = 5.

Table 2.7: Comparative Results for the Nonconvex Cost Game (Driessen & Tijs, 1985)

The core of the cost game turns out to be the convex hull of the cost allocations (13, 17, 48), (13, 20, 45), (15, 17, 46) and (15, 20, 43) (Driessen & Tijs, 1985). The core is formed below:

Figure 2.4: Shaded quadrilateral represents the core and the indicated point inside it is equal to the cost allocation by the NSCG method (Driessen & Tijs, 1985)

In conclusion, cost allocation using the NSCG technique represents the center of gravity of the core.

**2.5 Discussion**** **

In this chapter we will discuss the application of the above cooperative game theory methods in other cases related to water resources and the comparisons of these methods with other techniques. Finally, we will extract some conclusions.

The core was implemented by Lejano & Davos (1995) in a cost allocation problem about a water reuse project (Terminal Island Treatment Plant) in Southern California among four agencies (the LA Department of Public Works, the LA Department of Water and Power, the Water Replenishment District of Southern California and the Department of Water of the City of Long Beach). In this project, the authors applied the Shapley value whose results are not encouraging compared with other methods that they used such as nucleolus and normalised nucleolus. Namely, Lejano & Davos (1995) observed that the nucleolus method provides a broader margin of assurance than the normalised nucleolus that each agency will join the grand coalition for the TITP project. However, the normalised nucleolus supplies a larger margin of assurance than the nucleolus technique that any subcoalition among the four agencies will not be formed as an alternative to the grand coalition (Lejano & Davos, 1995).

In addition, Aadland & Kolpin (1998) found out that the Shapley value was one of the methods that farmers in south-central Montana use in order to allocate cost among them for every maintenance project of the main irrigation ditch. In this case, the only difference is that the Shapley value method was named as serial allocation rule (Fiestras-Janeiro et al., 2011).

Dinar et al. (1992) applied the nucleolus, the Shapley value and its variant the generalised Shapley value in a regional game in order to allocate the additional costs and benefits in three Farms (A, B, C) and a Town. In this case, the Shapley value effects more for the Town and the Farm A than its variant which is more sufficient for the Farm B and the Farm C. Also, the nucleolus method seems to be less adequate than Shapley value for the Town and the Farm A but more productive than the generalised Shapley value for the Farm B and the Farm C.

Except for this, the Shapley value and the generalised Shapley value were implemented by Loehman et al. (1979) in Missouri. Specifically, they evaluated the cost allocation problem of building a regional waste-water treatment system with eight effluent discharges along the Meramec River Basin in the area of Missouri (Fiestras-Janeiro et al., 2011). Furthermore, Loehman et al. (1979) compared the generalised Shapley value with the Nucleolus method and they came into the conclusion that the first is more easily computed due to the fact that no linear programs need to be solved.

Additionally, Wang et al. (2003) had applied the Shapley value, the weak nucleolus and the proportional nucleolus on a cooperative water reallocation game, by using net benefits among three stakeholders (Irrigation Water Association, City 1, City 2) along a river, for five years. This study showed that for the Irrigation Water Association the Shapley Value and the nucleolus are the less efficient methods while the weak nucleolus and the normalised nucleolus yielded more benefits. Regarding the City 1 and the City 2, the differences between the methods were negligible. Particularly, for both of the cities the nucleolus and the Shapley value were the methods which increased most the earnings of the cities. On the other hand, weak nucleolus for the City 1 and normalised nucleolus for the City 2 were the less effective methods.

**Chapter 3: Methodology**

In this chapter we will discuss about the methodology research that was adopted for this study. The research design is quantitative analysis.

**3.2 Data Gathering**

The data is secondary and it was provided to me by the Agency Development of Crete. More specifically, this agency supplied me with the water use per capita and the total water demand of three municipalities that are located in the island of Crete, along with the prices that it charges them for the year 2016. In addition, I acquired data about the distances between the Aposelemis dam and the municipalities. These distances were used in order to determine the cost for each municipality, in case that it would not join the coalition and it prefers to go alone.

The communication between me and the agency was made by e-mail. Particularly, the employee who undertook my request for the data sent me a report which included the above information. However, I was contacting frequently with the agency by telephone to clarify my questions. In these phone calls, the person who works for the agency was giving me more explanations about the data that I had received and he was answering any queries that I had.

Except for the above, other agencies that helped me obtain the appropriate data that I used on this study are the Decentralized Administration of Crete, the Sewerage Service and the Municipal Water Supply of each municipality. Moreover, regarding the population of each municipality, I exported information from the Hellenic Statistical Authority website.

**3.3 Objectives & Aims**

The objective of this dissertation is to study several solution concepts from the bibliography that are referred to the cooperative game theory and then to apply them in order to allocate the costs of the Aposelemis dam among three municipalities in the island of Crete.

Therefore, the aim of this study is to find out the most equitable possible way to allocate the Aposelemis dam’s costs which is exploited by these three municipalities in Crete. This will be achieved by implementing particular cooperative game theory cost allocation methods. From the comparison of the above methods, we will propose the fairest one of them so as to allocate the water costs among the municipalities.

Ethics

Alternative choices

Limitations: One of my concerns was that I had to communicate with a Greek agency in order to acquire the appropriate data. Consequently, I had to translate all of the information that I had provided in such a way as to make them understandable in English.

**Chapter 4: Data Presentation**

**Chapter 5: Conclusions**

In this study, we surveyed the literature in order to find out Cooperative Game Theory methods which are applied in cost allocation problems related with water resources. Then, we analysed important techniques such as the Core and some of its variants, the Shapley Value and the Non-Separable Cost Gap by applying them on particular examples from the water resources field. Finally, we discussed about other cases in which the above methods were implemented, and we mentioned the comparisons among them and among other cost allocation techniques on the basis of fairness, equity and effectiveness.** **

**References**** **

Aadland, D. and Kolpin, V., 1998. Shared irrigation costs: an empirical and axiomatic analysis. *Mathematical Social Sciences*, *35*(2), pp.203-218.

Aoki, M., 1996. Various Nucleoli in Common Cost Aliocation. *Aomori Public College*, pp.1-21.

Dinar, A., Ratner, A. and Yaron, D., 1992. Evaluating cooperative game theory in water resources. *Theory and decision*, *32*(1), pp.1-20.

Drechsel, J., 2010. Cooperation in supply chains. In *Cooperative lot sizing games in supply chains* (pp. 55-61). Springer, Berlin, Heidelberg.

Driessen, T.S.H. and Tijs, S.H., 1985. The cost gap method and other cost allocation methods for multipurpose water projects. *Water Resources Research*, *21*(10), pp.1469-1475.

Fiestras-Janeiro, M.G., García-Jurado, I. and Mosquera, M.A., 2011. Cooperative games and cost allocation problems. *Top*, *19*(1), pp.1-22.

Grotte, J.H., 1970. *Computation of and observations on the nucleolus, the normalized nucleolus, and the central games*. Cornell University, Sept..

Grotte, J.H., 1976. Dynamics of cooperative games. *International Journal of Game Theory*, *5*(1), pp.27-64.

Hildebrand, W. and Kirman, A., 1976. General equilibrium analysis.

Lejano, R.P. and Davos, C.A., 1995. Cost allocation of multiagency water resource projects: Game theoretic approaches and case study. *Water Resources Research*, *31*(5), pp.1387-1393.

Lemaire, J., 1984. An application of game theory: cost allocation. *ASTIN Bulletin: The Journal of the IAA*, *14*(1), pp.61-81.

Loehman, E., Orlando, J., Tschirhart, J. and Whinston, A., 1979. Cost allocation for a regional wastewater treatment system. *Water Resources Research*, *15*(2), pp.193-202.

Maschler, M., Peleg, B. and Shapley, L.S., 1979. Geometric properties of the kernel, nucleolus, and related solution concepts. *Mathematics of operations research*, *4*(4), pp.303-338.

Okada, N., 1981. Cost allocation in multi-purpose reservoir development. *IFAC Proceedings Volumes*, *14*(2), pp.3879-3885.

Sadegh, M. and Kerachian, R., 2011. Water resources allocation using solution concepts of fuzzy cooperative games: fuzzy least core and fuzzy weak least core. *Water resources management*, *25*(10), pp.2543-2573.

Schulz, A.S. and Uhan, N.A., 2013. Approximating the least core value and least core of cooperative games with supermodular costs. *Discrete Optimization*, *10*(2), pp.163-180.

Schmeidler, D., 1969. The nucleolus of a characteristic function game. *SIAM Journal on applied mathematics*, *17*(6), pp.1163-1170.

Shapley, L.S., 1953. A value for n-person games. *Contributions to the Theory of Games*, *2*(28), pp.307-317.

Shapley, L.S. and Shubik, M., 1966. Quasi-cores in a monetary economy with nonconvex preferences. *Econometrica: Journal of the Econometric Society*, pp.805-827.

Shapley, L.S. and Shubik, M., 1973. *Game Theory in Economics, 6: Characteristic Function, Core, and Stable Set*. Rand Corporation.

Shoubi, M.V., Barough, A.S. and Amirsoleimani, O., 2013. Application of Cost Allocation Concepts of Game Theory Approach for Cost Sharing Process. *Research Journal of Applied Sciences, Engineering and Technology*, *5*(12), pp.3457-3464.

Tijs, S., 1981. *Bounds for the core of a game and the t-value*(No. ebc650eb-f25e-4802-ba0b-271afa6774f9). Tilburg University, School of Economics and Management.

Wang, L.Z., Fang, L. and Hipel, K.W., 2003. Water resources allocation: a cooperative game theoretic approach. *Journal of Environmental Informatics*, *2*(2), pp.11-22.

Young, H.P., Okada, N. and Hashimoto, T., 1980. Cost allocation in water resources development-A case study of Sweden.

Young, H.P., Okada, N. and Hashimoto, T., 1982. Cost allocation in water resources development. *Water resources research*, *18*(3), pp.463-475.

[1] The monotonicity principle shows that if the cost exceeds the expectations, the allocation of the participants should not go down (Okada, 1981). The inverse also applies. Monotonicity is important for fair allocations when the total amount which is allocated varies.

SCicis the separable cost of player

iin a cost game

(N;c)and it is defined as

SCic=cN-c(N-i). It represents the cost allocated to each player which is not less than the marginal cost including him in a project (Driessen & Tijs, 1985).