ABSTRACT

A water distribution problem in the Mexican Valley is modeled first as a three-person noncooperative game. Each player has a five-dimensional strategy vector. The strategy sets are defined by 15 linear constraints, and the three payoff functions are also linear. A nonlinear optimization problem is first formulated to obtain the Nash equilibrium based on the Kuhn-Tucker conditions, and then, duality theorem is used to develop a computational procedure. The problem can also be considered as a conflict between the three players. The non-symmetric Nash bargaining solution is suggested to find the solution. Multiobjective programming is an alternative solution concept, when the water supply of the three players are the objectives, and the water authority is considered to be the decision maker. The optimal water distribution strategies are determined by using these solution concepts and methods.

1. Introduction

Game theory is the most commonly applied methodology in decision making problems, when the decision makers have conflicting interests. The solution of a noncooperative game is a decision vector such that no decision maker can unilaterally change the decision and receive higher benefit. This solution concept is known as the Nash equilibrium [1].

The limited amount of natural resources creates a conflict between the users, since it is impossible to satisfy the demands of all users, so any user can receive more resources only in the expense of the others. It is well known that water shortage is one of the most worrying problems of the new millennium due to the increase of population, better living standards and the inefficiency of the way we use water [2]. This problem already became serious in the neighborhood of large cities with very large population. Mexico City with its 19 million inhabitants is considered the most populated city in the world. It is located in the Mexican valley where the very limited water resources are distributed between three users: agriculture, industry and domestic users. Therefore there is a conflict between them, and this conflict can be modeled by a three-person game, which will be the case study reported in this paper.

There is a large variety of computer methods to find Nash equilibrium in non-cooperative games. A comprehensive summary is given for example, in [1], where a combination of the Kuhn-Tucker conditions and nonlinear optimization is discussed in detail. We will apply this method in our case study, when an alternative algorithm is also developed based on duality theory. Nash equilibrium assumes that each decision maker wants to maximize its benefit without any consideration to the others.

This problem can also be considered as a conflict between the users, so conflict resolution methodology is a reasonable alternative approach, in which the decision makers select a Pareto optimal solution that satisfies certain fairness conditions. Most solution concepts can be also considered as outcomes of negotiation processes. In our case study the non-symmetric Nash bargaining solution is selected to find the solution [3]. A summary of the most commonly used conflict resolution methods is given for example in [4].

In many countries, like in Mexico, the water supply is provided to the users by a single governmental organization. Therefore we might also consider this problem as a single-decision maker’s problem with three objective functions, where the water amounts supplied to the three users are the objective functions. A comprehensive summary of the most popular methods for solving multiobjective programming problems can be found for example, in [5].

The application of game theory, conflict resolution and multi-objective programming in natural resources management has a long history. The survey papers [6,7] gave excellent overview of earlier works. More recently Donevska et al. [8] examined a similar problem to ours with water demands to agricultural and non-agricultural users in the Republic of Macedonia. Jensen et al. [9] investigated multiple usage of irrigation water. A multiobjective design of water distribution systems under uncertainty was developed combining multi-objective optimization with evolutionary algorithms [10,11]. Wang, et al. [12] used game theory for a water distribution problem for the South Saskatchewan Basin in Southern Alberta, Canada.

In our case study the non-cooperative Nash equilibrium of the three player game of the water users in the Mexican Valley will be first determined. All payoff functions and constraints will be linear, so taking advantage of the special structure of the model, the general solution algorithm based on the Kuhn-Tucker conditions can be significantly simplified and by using duality theorem an alternative method can be developed. The non-symmetric Nash bargaining solution of the problem will be next determined, which requires the solution of a nonlinear optimization problem with linear constraints and quasiconcave objective function. In finding solutions based on the concepts of multiobjective optimization we will use the weighting method [5].

Since the three applied solution concepts are based on different types of instituting water distribution, our results also show the consequences of different water distribution mechanisms on the optimal solutions. Since in the Mexican Valley the water distribution is decided by a government organization, the concept assuming a singledecision maker has to be adapted, which is given by multiobjective optimization. The comparison of the results still has practical importance by showing the possible consequences of changing the water distribution system. As we will see later, domestic water demands can never be satisfied, so there is a need of significant improvement of the distribution system and the utilization of the existing water resources.

This paper develops as follows. Section 2 will introduce the mathematical methodology. Section 3 will contain the model of the case study. Numerical results will be presented and the solutions methods will be compared in Section 4. The last section will conclude the paper.

2. The Mathematical Methodology

We will first present a nonlinear optimization problem to find the Nash equilibrium in a general class of n-person games, which will be later applied in the case study.

Consider an n-person noncooperative game, and assume that the strategy set of player is,

where is a continuously differentiable vector variable, vector valued function, and the payoff of player k is, where is also continuously differentiable. Then is a Nash equilibrium, if for all k, maximizes the payoff of player k,

subject to the feasibility constraint.

Assume that the Kuhn-Tucker regularity condition holds, then the Kuhn-Tucker necessary conditions imply the existence of a vector such that

(1)

where Equation (1) is the gradient vector (as row vector) of with respect to and is the Jacobian matrix of.

Consider next the optimization problem Minimize

subject to k

(2)

Since and the objective function is zero if and only if all Kuhn-Tucker conditions are satisfied. Therefore every equilibrium of the n-person game is an optimal solution of Equation (2). Hence the equilibrium of the game can be obtained by solving problem Equation (2).

The sufficiency of the Kuhn-Tucker conditions for concave problems implies that if all components of and are concave in, then all optimal solution of Equation (2) with zero objective function value are equilibria.

Consider next the linear case, when

and the strategy sets are defined by the linear constraints Equations (3) and (4).

(Individual constraints)    (3)

(Joint constraint).       (4)

Using the previous notation Equation (5) is generated,

(5)

So conditions Equation (1) become

(6)

where vector is broken up to two parts. So problem Equation (2) can be rewritten as Equation (7).

Minimize

subject to:

(7)

All constraints are linear, and the objective function is quadratic.

An alternative approach can be introduced as follows. By duality, is an equilibrium if and only if for all k, is an optimal solution of the linear proamming problem:

Maximize

subject to

The dual of this problem has the form Equations (8) and (9).

Minimize

(8)

subject to

(9)

So a vector is optimal if and only if the primal objective equals the dual objective, so the feasible solutions of Equation (10) give the set of all equilibria:

(10)

.

In computing the non-symmetric Nash bargaining solution assume that are the relative importance factors of the players. In addition, let denote the minimal value of the payoff of player k, which can be obtained by solving the single-objective optimization problem of Equation (11):

Minimize

subject to

(11)

Then the non-symmetric Nash bargaining solution can be obtained by solving problem in Equation (12):

Maximize

subject to

(12)

Notice that Equation (11) is a linear programming problem, and in the nonlinear model Equation (12) only the objective function is nonlinear, all constraints are linear.

The application of the weighting method requires the optimization of a linear combination of the objective functions in Equation (13):

Maximize

subject to

(13)

where is the relative importance factor of player k as before.

It is usually assumed that for all k, and

If for some k, then in the objective functions of both problems Equation (12) and Equation (13) the payoff of player k is completely ignored. Tradeoffs between the players are obtained if for all k.

3. The Case Study

The three players are: agriculture, industry and domestic users. They can receive surface water, ground water and treated water. Surface and ground water supply can be obtained from local sources and also can be imported from other neighboring watersheds. Let k = 1, 2, 3 denote the three users, so the decision variables of each of them are as follows:

= surface water usage from local source;

= groundwater usage from local source;

= treated water usage;

= imported surface water usage;

= imported groundwater usage.

So the strategy of each player is the five-element vector

The payoff function of each player is the total amount of water received Equation (14):

(14)

The players have two common constraints. The supplied water amount cannot be smaller than a minimal necessary amount and cannot be larger than the demand, D_k, in order to avoid wasting water as described by Equations (15) and (16):

(15)

(16)

In addition, each player has its own individual constraints.

The agricultural users (k = 1) have two major conditions. Introduce the following variables:

G = set of crops that can use only groundwater;

= ratio of crop i in agriculture area;

= water need of crop i per ha;

T = set of crops which can use treated water;

= total water need per ha.

Ground water has the best irrigation quality and treated water has the worst. Therefore water quality sensitive crops can use only ground water, and only the least sensitive crops are able to be irrigated by treated water. The ratio of available groundwater cannot be smaller than the water need of crops that can use only ground water

which can be rewritten into a linear form Equation (17)

(17)

with Similarly, the ratio of treated water availability cannot be larger than the ratio of water need of the crops which can use treated water:

which also can be rewritten into a linear form Equation (18):

(18)

with.

The industrial users (k = 2) also have their own constraints. Introduce the following variables:

= minimum proportion of groundwater that Industry has to receive;

= maximum proportion of treated water that Industry can use.

In order to keep a sufficient average quality of the water used by the industry, a minimum proportion of groundwater is specified, since groundwater has the best quality. The worst quality of treated water requires the industry to use only a limited proportion of treated water in its water usage. With given threshold values B_t and B_g these constraints can be rewritten as

Both conditions can be rewritten into linear forms Equations (19) and (20):

(19)

and

(20)

Domestic users (k = 3) have only treated water usage limitation, since it can be used for only limited purposes, such as irrigating in parks, etc.:

where:

B_d = maximum proportion of treated water that domestic users can receive.

This constraint is also equivalent with a linear inequality given in Equation (21):

(21)

There are four additional interconnecting constraints by the limited resources given in Equations (22)-(25):

(22)

(23)

(24)

(25)

where S_s = maximum available surface water amount from local source;

S_g = maximum available groundwater amount from local source;

= maximum available imported surface water amount;

= maximum available imported groundwater usage.

In Equations (22) and (23) we require that all local resources have to be used before importing water from other watersheds.

This model is a three-person noncooperative game with payoff functions given in Equation (14) and strategy sets defined by constraints Equations (15)-(25) with all nonnegative components.

4. Numerical Results

The data for the numerical study are the updated versions of those given in the earlier paper Salazar et al. [13]. The numerical values are given in Table 1.

Furthermore S_s = 58, S_g = 1702, = 453, = 169. These values and, D_k are measured in million m³/year , the other parameters are ratios, unitless quantities.

First the Nash equilibrium of the three-person noncooperative game is determined by solving the quadratic programming problem (7). The solution is presented in Table 2.

The objective function value is zero at the solution

Table 1. Model parameters.

Table 2. Equilibrium solution.

showing that global optimum is obtained. The linearity of all constraints and payoff functions imply that the KuhnTucker conditions are also sufficient, so any optimal solution of problem (7) provides equilibrium. Notice that all demands of agriculture and industry are satisfied, however domestic users receive only 59.43% of their demand. The demand of agriculture is completely satisfied with groundwater, so groundwater availability for the other users become very limited. In addition, the very restrictive constraint (21) limits the treated water usage. They are the main reason of the low water amount supplied to domestic users.

The non-symmetric Nash bargaining solution is then computed by solving the optimization problem (12). Because Mexico city has the largest population in the world, we give slightly higher importance to domestic users than to the others by selecting α₁ = α₂ = 0.3 and α₃ = 0.4. The solution is shown in Table 3.

Bargaining has to take care the interest of all players, so domestic users receive much higher amount of water than before. It is still much lower than the demand, it shows only 77.71% satisfaction.

The weighting method is finally applied with the same weights as before by solving the linear programming problem (13). The results are shown in Table 4.

Notice that domestic users receive even larger amount than before in the expense of the industry.

In order to find the individual maximum objective

Table 3. Nash-bargaining results.

Table 4. Weighting method solution.

function values we repeated the computations by the weighting method with weight selections w₁ = 1, w₂ = w₃ = 0; w₁ = w₂ = 0, w₃ = 1 and. The maximal values became 966, 230 and 1960. For agriculture and industry these numbers show that their demands can be completely satisfied. However, for domestic users the maximum possible water supply is only 92.3% of the total demand, meaning that there is no water distribution scheme which can satisfy all domestic demands. In all solutions all available surface and groundwater supplies are used, but the very restrictive constraints on the treated water ratio makes the use of more treated water impossible. In the cases of the equilibrium and the Nash bargaining solutions all demands of agriculture and industry are satisfied. Domestic needs are satisfied only on 59.43% and 77.71% levels, respectively. In the case of the weighting method agricultural demands are fully satisfied, industry receives only the minimum amount, and domestic users get only 79.83% of their need.

5. Conclusions

The water distribution problem of the Mexican Valley was considered, where agriculture, industry, and domestic users were the players in the game theoretic models, with the water supplies as the payoff functions and the objective functions in the case of multiobjective optimization.

The Nash equilibrium was first obtained by solving a special quadratic optimization problem with linear contraints, which was derived based on the Kuhn-Tucker conditions. The non-symmetric Nash bargaining solution was then obtained by maximizing the non-symmetric Nash product. The application of the weighting method required the solution of a special linear programming problem.

In the case of the game theoretical models all demands of agriculture and industry can be satisfied, but domestic users receive a very limited amount of water. In the case of multiobjective optimization (assuming a single decision maker as is the case in the current system) the domestic users are able to receive larger amount than in the other cases at the expense of the industry. The numerical results well demonstrate that there is no water distribution scheme which can satisfy all domestic demand. In all solutions all available surface and groundwater supplies have to be used. Water supply can be increased either by using more treated water on the expense of worsening water quality, or by increasing surface and groundwater supplies. Importing more water from neighboring regions would result in serious social conflicts, so more investment is needed for further developments and incentives should be given to the users for more efficient water usage. Maybe a market driven pricing policy is needed in the near future.

REFERENCES