An Application of the MP Method for Solving the Problem of Distribution

1. Introduction

The problem of distribution (allocation or division) is a common, everyday problem. It consists of dividing a certain amount among several (two or more) users. We experience this problem every day through the distribution of our salaries on life's necessities, family members, overhead expenses and other costs. The payment of wages to workers and the distribution of incentives from certain funds are also examples. The problem is not only connected with the distribution of the financial resources. It also covers the distribution of food, water, energy, oil and gas, goods and any other property at the global or local levels.

The problem of distribution (PD) is easy to solve if the available amount which has to be divided is large enough. In fact, in this case the problem does not exist because each user can get as much as he needs or requires. Usually, the available amount is limited and such distribution is impossible. In these cases, objective possibilities and the aspirations of the users have to be respected, which implies some kind of cooperation among the users.

The PD has been extensively studied in the literature and it is usually considered as a cost and profit allocation problem. Usually, researchers use cooperative games as the framework in determining the algorithms for solving this problem. The following text presents some papers in which such ideas have been used.

In [2], the allocation of operating costs among the lines of an insurance company as an accounting problem is presented. It is proved that the cost allocation problem is identical to the determination of the value of a cooperative game with transferable utilities. A new method, called ‘proportional nucleus' is proposed as a solution to the problem.

In [3], the authors solve the cost and profit allocation problem among connected companies, as well as the determination of production and transportation plans, by applying a solution concept from game theory.

In [4], the cost allocation problem within the generalized linear programming class of games is investigated. It is assumed that a group of agents participate in a common project and that each agent defines his requirements for his expected benefit resulting from the project. The joint cost or profit of the project must be allocated among the agents in order to satisfy a set of required properties. The authors present a general and efficient algorithmic framework for computing exact cost allocations in generalized linear programming games. The literature surveys of cost allocation by linear programming and generalized linear programming games are given in [5] and [6].

The game theoretic models of cost allocation used to solve the cooperative advertising problems are studied in [7]. For this purpose, different models are proposed. Some models are focused on advertising spending by manufacturers and retailers, and manufacturers' support programmes for local advertising.

The cost allocation problem also occurs in public utilities [8], [9], the joint production of goods [7] and electricity [10], [11], [12], [13], [14], the use of networks [15], accounting [16], management [17] and other situations.

In this paper, we present a new approach to solve the cost (profit) allocation (distribution) problem. The paper is an application of a new method for solving a general multi-objective linear programming problem (MOLPP) from [1]. The reasons for using it are its properties: (1) it is an iterative method (if the obtained solution is not satisfactory, then it can be improved by the next iteration(s)); (2) it is based on the principles of game theory (cooperation among decision-makers); (3) each iteration consists of a linear programming problem which yields a unique solution; (4) the solution is obtained by respecting the aspirations of decision-makers within the frame of given possibilities; (5) in each iteration, we can compute objective indicators which show the reality of aspirations and which may be used to define the strategy for the next iteration. These properties are very important in the solving procedure for the considered distribution problem (which is a specific case of MOLPP). The proposed method allows different criteria to be involved in the solution process. For a better understanding of how these possibilities become prominent according to the specific nature of the problem, we provide several examples. The main contribution of the paper is an application to an investment model (see Section 4) which suggests one means for economic recovery. The benefits of such a model are confirmed by explicit mathematical results (with general and particular parameter values).

2. Statement of the problem

Let b be the available amount (budget) which has to be divided among n users (players) P _i , i=1, 2, …, n, and let x = (x₁, x₂,…,x_n)εRⁿ. We define a general constraint set B ⊂ R n , B = { x ∈ R n : x ≥ 0 , x 1 + x 2 + … + x n ≤ b } , where x_i denotes the part of the available amount which may be assigned to P _i . For n = 2, the set B is sketched in Figure 1 (it is the triangle OMN where O(0,0), M(b, 0), N(0, b)). Note that, for practical reasons, the general set B may be reduced to the available set S ⊆ B.

OPEN IN VIEWER

Figure 1.

The constraint set (general and available)

For example, if we divide the entire budget b, then we have x₁ + x₂ + … + x_n = b, which defines S (the line MN in Figure 1). We can also have restrictions for the lower bounds (x_i≥g_i and/or x₁ + x₂ + … + x_n≥g) or for the upper bounds (x_i≤r_i), which will reduce B to S (see Figure 1). If we do not intend to spend the whole budget b, then a constraint such as x₁ + x₂ + … + x_n≤r <b can appear as well. Various kinds of other restrictions are also possible. Thus, the PD can be stated in the following general form,

optimize ( x 1 , x 2 , … x n ) , where ( x 1 , x 2 , … x n ) ∈ S ⊆ B .

(1)

Here, the word “optimize” does not have a strictly defined meaning. The meaning may vary in different practical situations, although generally it means the maximization of some kind of utility which is not necessarily the amount x_i for each player P _i . Below we consider such alternative optimization possibilities in the PD (1).

3. The new method for solving the problem

To solve the PD (1), we will use the technique from [1]. We consider the standard case of proportional distribution and the generalized case separately.

3.1 The standard case

First, we consider the well-known standard PD where each of the players wants to maximize his part of the budget. In this case, the PD (1) has the following form,

max x ∈ B ( x 1 , x 2 , … x n ) .

(2)

Since (2) is MOLPP, we will use the new method, which was established in [1], for such problems. Suppose that some of the players Pi (or all of them) have the aspiration level d_i. This means that Pi wants to get x_i≥d_i. Generally, d_i may be any non-negative number. In practical situations, d_i is an amount which P _i needs or expects. It can also be the lower bound, i.e., the smallest amount which ensures the normal functioning for P _i or for the sector i which P _i represents. Thus, using [1] Sec. 1.1, we define the desired budget,

D = { x ∈ R n : x i ≥ d i ≥ 0 , i = 1 , 2 , … , n } ,

and, for Λ≥0, shifted desired budget,

D λ = { x ∈ R n : x i ≥ λ d i ≥ 0 , i = 1 , 2 , … , n } ,

where, for each P _i who did not define his level d_i, we assume that d_i = 0 (see the graphic illustration in Figure 2 for n = 2). Here, we also assume that d_i≠0 for at least one i ε {1, 2,…, n}.

OPEN IN VIEWER

Figure 2.

The standard case

According to [1] Sec. 1.1, we can state the following linear programming problem (LPP) which is assigned to (2),

max ( x , λ ) ∈ G λ , where G = { ( x , λ ) ∈ R n + 1 : x ≥ 0 , λ ≥ 0 , x 1 + x 2 + … + x n ≤ b , x i ≥ λ d i , i = 1 , 2 , … , n } ,

(3)

or more briefly, max x ∈ B ∩ D λ λ . This problem is easy to solve. The solution is (the point T in Figure 2),

x i * = λ * d i , i = 1 , 2 , … , n , where λ * = b d 1 + d 2 + … + d n .

(4)

The obtained solution is a standard proportional distribution, x_*1:x_*2: … :x_*n = d₁:d₂: … :d_n. Note that if Pi does not define his aspiration level (d_i = 0), then he gets nothing (x_i* = 0). The optimal value Λ* indicates to what extent the desired aspirations may be realized.

Applying the same kind of analysis as in [1] Sec. 1.1, we can make the following observations and comments. If a player is not satisfied with the obtained solution (4), then the aspiration levels need to be redefined and the problem (3) has to be solved again. This determines the next step (iteration) of the method. Note that since all the constraints at the optimal point are active (equalities), any increase of a certain aspiration level will cause a decrease in the optimal values of the other players, and vice versa. Thus, the redefinition of the aspiration levels is a matter of agreement (cooperation) among the players. Note also that any player Pi can define his absolute level g_i (if the others agree with that). In this case, the constraint x_i≥g_i – instead of x_i>≥Λd_i – participates in the definition of G. In other words, this player does not participate in the definition of D_Λ but he causes the reduction of the general set B to S (see Section 1). Many other cooperative restrictions for the next step, such as xi + x_j≥g_ij or xi + x_j≤r_ij, etc., are also possible. In this way, after several subsequent iterations based on cooperation, the players can reach the solution which will satisfy all of them.

3.2 The generalized case

The generalization of the problem (2) is motivated and directed by practical considerations. For example, suppose that the state distributes incentives to different economic sectors. The prosperity of an individual sector does not depend only on the obtained incentive but also on the production of other sectors. Such prosperity can be measured by some kind of utility function for each sector and/or for the whole economy.

For these reasons we assume that, in the problem (1), we have k utility functions u_i(x₁, x₂,…,x_n), i = 1, 2,…,k. Here, k is generally independent of n (k may be greater than n, equal to n, less than n and even equal to 1). Note that u_i is not necessarily the utility function for the player P _i . It may be assigned to a regulatory subject (state, government, investor) or any other user. Now, the goal is to maximize the utility functions u_i, i = 1, 2,…,k instead of the amounts x_i, i = 1,2,…,n. We have

max x ∈ S ⊆ B ( u 1 ( x ) , u 2 ( x ) , … , u k ( x ) ) ,

(5)

which is the MOLPP again and thus the detailed analysis from [1] can be applied. The assigned LPP which has to be solved is

max ( x , λ ) ∈ G λ , where G = { ( x , λ ) ∈ R n + 1 : x ∈ S , λ ≥ 0 , u i ( x ) ≥ λ d i , i = 1 , 2 , … , k } ,

(6)

and d_i is the aspiration level for u_i. This problem is one step of the method. It can be iterated until the best possible solution is obtained.

Very often, on the economic and the political stage, we can see entities associated in coalitions. One expects to receive greater benefits as a member of a given coalition than by one's self. Some ideas regarding coalitions were studied in [18]. In light of our analysis, such ideas lead us to solve the MOLPP (5) by using our method (6). To clarify this point, we provide the following example.

Example 1. Suppose that we have four players P _i , i = 1,2,3,4 with their utility functions u_i(x), i = 1, 2, 3, 4, x ε R ⁿ . If each player plays alone, then we have the PD (5), max (u₁(x), u₂(x), u₃(x), u₄(x)).

Let us consider now the possibility of a coalition. Suppose that u_ij(x) is the utility function for coalition {P _i , P _j }, i,jε{1,2,3,4}, i≠j. We have another six problems with one two-member coalition,

max x ∈ s ( u 12 ( x ) , u 3 ( x ) , u 4 ( x ) ) , max x ∈ s ( u 13 ( x ) , u 2 ( x ) , u 4 ( x ) ) , max x ∈ s ( u 14 ( x ) , u 2 ( x ) , u 3 ( x ) ) , max x ∈ s ( u 23 ( x ) , u 1 ( x ) , u 4 ( x ) ) , max x ∈ s ( u 24 ( x ) , u 1 ( x ) , u 3 ( x ) ) , max x ∈ s ( u 34 ( x ) , u 1 ( x ) , u 2 ( x ) ) ,

and three problems with two two-member coalitions,

max x ∈ S ( u 12 ( x ) , u 34 ( x ) ) , max x ∈ S ( u 13 ( x ) , u 24 ( x ) ) , max x ∈ S ( u 14 ( x ) , u 23 ( x ) ) ,

Similarly, if u_ijl(x) is the utility function for coalition {P _i , P P _l }, i, j, lε{1, 2, 3, 4}, i≠j, i≠l, j≠l, then we also have four problems with one three-member coalition

max x ∈ S ( u 123 ( x ) , u 4 ( x ) ) , max x ∈ S ( u 124 ( x ) , u 3 ( x ) ) , max x ∈ S ( u 134 ( x ) , u 2 ( x ) ) , max x ∈ S ( u 234 ( x ) , u 1 ( x ) ) .

Finally, if we consider the global coalition {P₁, P₂, P₃, P₄} and the utility function u₁₂₃₄(x), then we have one more problem max x ∈ S u 1234 ( x ) .

Thus, if we permit all possible coalitions then we have 15 MOLPP problems (5) which may be solved using the method (6). When all these solutions are known, the players – who have the option to choose – can choose the best means of coalition-building for themselves. After such a choice has been made, the accepted solution may be modified just because of the possibility of choosing (the player(s) who have made a choice may require an additional stimulation or reward). Here, in this example, we have permitted every possible coalition, which is not the case in practical situations. Some coalitions are useless or else impossible. This can be clearly seen in everyday economic situations and especially in political life.

To explain some of these possibilities, we provide the following example.

Example 2. Suppose that the players P, i = 1, 2,…,n formed three coalitions (k=3): C₁ = {P _i : i = 1, 2, …, n ₁}, C₂ = {P _i : i=n₁ + 1,n₁ + 2,…,n₂} and C₃ = {P _i : i=n₂+ 1, n₂ + 2,…,n}. Let u_i(x) be the utility function and d_i be the aspiration level for coalition C_i, i = 1, 2, 3. We solve (5) by solving the assigned problem (6). Let Λ_*=0.75 be the solution and x_* ε S be the optimal point. This means that each coalition can realize its aspiration with at least 75%. We can compute the indicators

λ i = u i ( x * ) d i , i = 1 , 2 , 3 .

Suppose that we obtained Λ₁=0.81, Λ₂=0.75, Λ₃=0.9. We see that C₂ can realize exactly 75% (Λ₂=Λ_*), while the realizations for C₁ and C₃ can be better (81% and 90%). This means that d1 and d₃ can be increased up to

d 1 ′ ≤ λ 1 λ * d 1 = 1.08 d 1 , d 3 ′ ≤ λ 3 λ * d 3 = 1.2 d 3 ,

without affecting the optimal solution Λ_* =0.75. Why is it that this solution cannot be larger? Because d₂ is set too high. If d₂ is decreased, then the realizations become better. If we want to have Λ_*≥μ in the next iteration, we have to require d ' i ≤ ( λ i / μ ) d i , i = 1, 2, 3. For example, Λ_*≥0.8 will be ensured if d₂ is decreased (d'₂≤.9375d₂), while d₁ and d₃ can be even increased (d’₁≤1.0125d₁, d'₃≥1.125d₃). In this way, the players can define a strategy which will lead to the final satisfactory solution in the next iteration(s).

4. Applications

In the last few years, the economic crisis has become a global problem. Many states are faced with reduced production, consumption and social standards. New progressive and useful investments are necessary to revitalize economic life. The following example is a small contribution in this direction.

Example 3 (an investment model). Suppose that the economy of a considered state has two sectors, A and B. We define two non-negative variables: x₁ and x₂, being the production volume of sectors A and B, respectively. The sectors can buy goods and raw materials for their production and consumption on the domestic market (A from B and/or B from A) or on the foreign market (imports). Similarly, the sectors can sell their products on the domestic market (A to B and/or B to A) or on the foreign market (exports). Since our aim is to present the model in a general form, we define the basic assumptions by using the following parameters. Let r_i, q_i, p_i denote the average export, import and domestic prices, respectively, for a unit of the production range of the sectors A (i = 1) and B (i=2). Let a (b) be the number of purchased goods and amount of raw materials per unit of production of the sectors A (B). Let di and c_i be the fixed costs and variable costs per unit of production of the sectors A (i = 1) and B (i=2), respectively.

We suppose that the government ensures the investment fund f for economic recovery. The criterion of distribution from the fund to the sectors A and B is based on the planned effects of this investment. The government will stimulate exports by ε per penny of exported goods, and buying on the domestic market by β per penny of purchased goods. At the same time, to increase production and employment, it will discourage imports (by using certain restrictive rules such as additional taxes, laws, etc.) by γ per penny of imported goods. The measure for the efficacy of any investment will be the total revenue of each sector. How can the distribution be realized according to the given criteria?

The PD here is the MOLPP (5) with two utility functions: the total revenue function u₁ for sector A and u₂ for sector B. The constraint set S is given by the available amount in the investment fund. We have the following four cases.

I The sectors do not cooperate. They import necessary goods and export their products. The stimulation is given for exports along with disincentives for imports. We have

A → max { u 1 ( x 1 ) = ( 1 + ɛ ) r 1 x 1 - ( 1 + γ ) a q 2 x 1 } , B → max { u 2 ( x 2 ) = ( 1 + ɛ ) r 2 x 2 - ( 1 + γ ) b q 1 x 2 } , under constraint ɛ ( r 1 x 1 + r 2 x 2 ) ≤ f .

The fund distribution is: εr₁ x ₁ to A and εr₂x₂ to B.

II Sector A cooperates with B. This means that A buys necessary goods from B while B imports. The stimulation is given for exports (which is now r ₁ x ₁ for A and r₂(x₂-ax₁) for B) and for domestic purchases ap₂ x₁ while the imports of B are discouraged. Thus, we have

A → max { u 1 ( x 1 ) = ( 1 + ε ) r 1 x 1 - ( 1 + β ) a p 2 x 1 } , B → max { u 2 ( x 1 , x 2 ) = ( 1 + ε ) r 2 ( x 2 - a x 1 ) + a p 2 x 1 - ( 1 + γ ) b q 1 x 2 } under constraint ε [ r 1 x 1 + r 2 ( x 2 - a x 1 ) ] + β a p 2 x 1 ≤ f , x 2 - a x 1 ≥ 0 .

Note that the last constraint ensures that B produces enough to meet the needs of A. The fund distribution is: εr₁ x ₁+βap₂x₁ to A and εr₂(x₂-ax₁) to B.

III The sector B cooperates with A. This means that B buys necessary goods from A while A imports. The export is now r₂x₂ for B and r₁(x ₁-bx₂) for A, while the domestic purchasing is bp₁x₂. We have

A → max { u 1 ( x 1 , x 2 ) = ( 1 + ɛ ) r 1 ( x 1 - b x 2 ) + b p 1 x 2 - ( 1 + γ ) a q 2 x 1 } B → max { u 2 ( x 2 ) = ( 1 + ɛ ) r 2 x 2 - ( 1 - β ) b q 1 x 2 } , under constraint ɛ [ r 1 ( x 1 - b x 2 ) + r 2 x 2 ] + β b p 1 x 2 ≤ f , x 1 - b x 2 ≥ 0 .

The fund distribution is: εr₁(x ₁-bx₂) to A and εr₂x₂ + βbp ₁x₂ to B.

IV The sectors cooperate. They buy from each other and export the rest of their products. The exports are now r₁(x₁−bx₂) for A and r₂(x₂−ax₁) for B, while the domestic purchasing is ap₂x₁ + bp₁x₂. We have

A → max { u 1 ( x 1 , x 2 ) = ( 1 + ɛ ) r 1 ( x 1 - b x 2 ) + b p 1 x 2 - ( 1 - β ) a p 2 x 1 } B → max { u 2 ( x 1 , x 2 ) = ( 1 + ɛ ) r 2 ( x 2 - a x 1 ) + b p 2 x 1 - ( 1 - β ) a p 1 x 2 } , under constraints ɛ [ r 1 ( r 1 - b x 2 ) + r 2 ( x 2 - a x 1 ) ] + + β ( a p 2 x 1 + b p 1 x 2 ) ≤ f , x 1 - b x 2 ≥ 0 , x 2 - a x 1 ≥ 0 .

The fund distribution is: εr₁(x₁-bx₂)+ βap₂ x₁ to A and εr₂(x₂-ax₁)+βbp₁x₂ to B.

These problems could be solved by solving the assigned LPP (6). The desired budget D and the shifted budget D_Λ are defined by using the fixed costs d_i, i = 1, 2 as the aspiration levels, which is a natural choice. When the optimal solution (x₁*, x₂*) is known, the profit of each sector is given by

π i ( x 1 * , x 2 * ) = u i ( x 1 * , x 2 * ) - d i - c i x i * , i = 1 for A , i = 2 for B .

Now, we will illustrate the given investment model for the following values of the parameters

( r 1 , q 1 , p 1 ) = ( 20 , 21 , 22 ) , ( r 2 , q 2 , p 2 ) = ( 32 , 30 , 34 ) ( a , b ) = ( 0.3 , 0.5 ) ( d 1 , d 2 ) = ( 5000000 , 8000000 ) , ( c 1 , c 2 ) = ( 6 , 10 ) , ( ε , β , γ ) = ( 0.4 , 0.2 , 0.2 ) , f = 15000000 .

For each of Cases I-IV, we state the MOLPP (5) and th assigned LPP (6).

I In the first case, we have

max ( 17.2 x 1 , 32.2 x 2 ) , max λ 8 x 1 + 12.8 x 2 ≤ 15000000 ⇒ x 1 + 12.8 x 2 ≤ 15000000 x 1 , x 2 ≥ 0 17.2 x 1 ≥ 5000000 λ 32.2 x 2 ≥ 8000000 λ λ , x 1 , x 2 ≥ 0

and the solution is

λ * = 2.724446 , x 1 * = 791990.24 , x 2 * = 676881.10 , u 1 * = 13622232.13 , u 2 * = 21795571.41 , π 1 * = 3870290.69 , π 2 * = 7026760.42 , Fund : 6335921.92 to A , 8664078.08 to B .

II In the second case, we have

max ( 19.84 x 1 , - 3.24 x 1 + 32.2 x 2 ) , max λ 6.2 x 1 + 12.8 x 2 ≤ 15000000 ⇒ 6.2 x 1 + 12.8 x 2 ≤ 15000000 x 2 - 0.3 x 1 ≥ 0 x 2 - 0.3 x 1 ≥ 0 x 1 , x 2 ≥ 0 19.84 x 1 ≥ 5000000 λ - 3.24 x 1 + 32.2 x 2 ≥ 8000000 λ λ , x 1 , x 2 ≥ 0

and the solution is

λ * = 2.960210 , x 1 * = 746020.61 , x 2 * = 810521.27 , u 1 * = 14801048.82 , u 2 * = 23681678.10 , π 1 * = 5324925.18 , π 2 * = 7576465.41 , Fund : 7490046.88 to A , 7509953.12 to B .

III In the third case, we have

max ( 17.2 x 1 , - 3 x 2 , 36 x 2 ) , max λ 8 x 1 + 11 x 2 ≤ 15000000 ⇒ 8 x 1 + 11 x 2 ≤ 15000000 x 1 - 0.5 x 2 ≥ 0 x 1 - 0.5 x 2 ≥ 0 x 1 , x 2 ≥ 0 17.2 x 1 - 3 x 2 ≥ 5000000 λ 36 x 2 ≥ 8000000 λ λ , x 1 , x 2 ≥ 0

and the solution is

λ * = 2.952696 , x 1 * = 972787.37 , x 2 * = 656154.62 , u 1 * = 14763479.15 , u 2 * = 23621566.63 , π 1 * = 3926754.83 , π 2 * = 9060020.35 , Fund : 5157680.57 to A , 9842319.43 to B .

IV In the fourth case, we have

max ( 19.84 x 1 , - 3 x 2 - 3.24 x 1 + 36 x 2 ) , max λ 6.2 x 1 + 11 x 2 ≤ 15000000 ⇒ 6.2 x 1 + 11 x 2 ≤ 15000000 x 1 - 0.5 x 2 ≥ 0 x 1 - 0.5 x 2 ≥ 0 x 2 - 0.3 x 1 ≥ 0 x 2 - 0.3 x 1 ≥ 0 x 1 , x 2 ≥ 0 19.84 x 1 - 3 x 2 ≥ 5000000 λ - 3.24 x 1 + 36 x 2 ≥ 8000000 λ λ , x 1 , x 2 ≥ 0

and the solution is

λ * = 3.313912 , x 1 * = 959572.52 , x 2 * = 822786.40 , u 1 * = 16569559.60 , u 2 * = 26511295.36 , π 1 * = 5812124.48 , π 2 * = 10283431.38 , Fund : 6342962.51 to A , 8657037.49 to B .

The obtained results do not require much comment – the benefits of such an investment for economic recovery are obvious. The mutual cooperation between the sectors and the export orientation (the fourth case) significantly increases their production volume, total revenue and profit. Note that in this case the total profit of the sectors exceeds the investment fund., Thus the sectors alone have sufficient funds for further investments.

5. Conclusions

In the paper, we apply the new, efficient method which was established in [1] for solving the cost (profit) allocation (distribution) problem. We consider both the standard and the generalized case.

In the standard case of proportional distribution, the players maximize the amount which they would obtain according to their aspirations. The optimal value of the indicator Λ shows to what extent the aspirations can be realized. If a player is not satisfied with the realization, then the next step (iteration) can be performed.

The generalized case is more interesting. The players can form coalitions to increase profit. In this case, the allocation is determined by the maximization of certain utility functions. There is an indicator with the same meaning and also the possibility of iteration. We apply the method in order to analyse an investment model for economic recovery. Financial incentives for exports and for buying on the domestic market would revitalize the economy of a state. The production volume, total revenue and profit of various economic sectors would be significantly increased. The explicit mathematical results clearly confirm this conclusion.