Telecommunication Systems 3(1994)91-107

91

An efficient characterization of some cost allocation solutions associated with capacitated network design problems Darko Skorin-Kapov

Harriman School for Management and Policy, State University of New York at Stony Brook, Stony Brook, NY 11794-3775, USA E-mail: dskorin @ccmail.sunysb.edu H 6 c t o r F e r n a n d o Beltr~in

Applied Mathematics and Statistics, State University of New York at Stony Brook, Stony Brook, NY 11794-3600, USA E-mail: hbeltran @ ams.sunysb.edu Received October 1993; in final form May 1994

We analyze some game-theoretic solution concepts associated with a cost allocation problem arising from the Capacitated Network Design (CND) problem. The problem is formulated as a cost cooperative game in characteristic function form to be referred to as the CND game. We provide an efficient representation of several game-theoretic solution concepts associated with the CND game. In particular, we efficiently characterize the core, and in some cases the nucleolus, the least weighted e-core and a certain "central'" point in the least weighted e-core. Our model properly generalizes several previously studied cooperative games. We also employ our model to analyze cost allocation problems associated with several classes of network design problems, which were not previously studied in the literature. Specifically, we efficiently characterize the above cost allocation solutions for cost allocation problems associated with the Capacitated Concentrator Location problem, the Capacitated Minimum Spanning Tree problem, the Capacitated Fixed Cost Spanning Forest problem, and the Capacitated Steiner Tree problem.

1.

Introduction

W e c o n s i d e r the f o l l o w i n g i m p o r t a n t c l a s s o f ( t e l e c o m m u n i c a t i o n s ) n e t w o r k d e s i g n p r o b l e m s . T h e set o f u s e r s is in n e e d o f a c e r t a i n s e r v i c e t h a t c a n b e p r o v i d e d b y c o n n e c t i n g t h e m ( p o s s i b l y t h r o u g h o t h e r users) to c a p a c i t a t e d facilities, y e t to b e c o n s t r u c t e d . T h e o b j e c t i v e is to b u i l d a n e t w o r k that will p r o v i d e the a b o v e s e r v i c e at m i n i m u m cost.

9 J.C. Baltzer AG, Science Publishers

92

D. Skorin-Kapov, H.F. Beltrtin, Capacitated network design problems

Formally, let G = (N, E) be an underlying complete undirected network with a set of nodes N and a set of links E. The set N represents potential users, as well as potential facility sites. For each i E N, let d i > 0 be the demand for service at node i. A facility with capacity u i can be constructed ("opened") at node i ~ N, at cost c,. > 0. Note that for some i ~ N, we can have for example di = 0 or ci--oo, meaning, respectively, that user i does not require any service, and that a facility can not be opened at site i. Open facilities provide service required by the users, and any node receiving the service can pass an unused portion of it to adjacent nodes. Each node i should receive the service from a single facility and the facility opened at node i should serve at least i itself. There is a cost c ( ( i , j ) = cij>O, ( i , j ) E E , if arc (i,j) is used to deliver service. In the spirit of new technologies (satellites, optical fiber), we assume that links have virtually no capacity limits. E a c h customer with a positive demand for service should be connected, perhaps through other nodes, to an open facility. The objective is to satisfy the demand for service, by opening facilities and connecting the users to facilities, while satisfying the capacity constraints at minimum cost. We will refer to the above optimization problem as the Capacitated Network Design (CND) problem. Many variations and special cases of the CND problem appear in the design of telecommunication networks. Among them are: Capacitated Minimum Spanning Tree (CMST) problem, Capacitated Concentrator Location (CCL) problem, Capacitated Fixed Cost Spanning Forest (CFCSF) problem, and Capacitated Steiner Tree (CST) problem. With all these problems naturally arises the problem of allocating the corresponding total minimum cost among customers in a "fair" manner. Namely, we would like to allocate the cost in such a way that no subset of users would have an incentive to secede and build their own network. Clearly, breaking up the network might destroy global minimality of the cost. Game theory approach to the CND problem leads to the introduction of a cooperative game in characteristic function form, with user's nodes being the players, and a characteristic function defined on all subsets (coalitions) of users. The value of the characteristic function for a certain subset would be the cost of an optimal subnetwork providing service to that subset. We will formulate the associated cost allocation problem as a cost cooperative game in characteristic function form, referred to as the CND-game. In cooperative game theory, several different approaches for fair cost allocation have been suggested (for a survey of these concepts see, for example, Young [27] and Driessen [4]). Some of the suggested concepts are the core, the least e-core, the least per capita e-core, the nucleolus, and the nucleolus per capita. In this paper, we will analyze the core, the nucleolus and the least weighted e-core of the CNDgame. The CND-game properly generalizes (or is closely related to) several cooperative games studied in the literature, which were used to analyze a variety of cost allocation problems arising from uncapacitated network problems. Some of those classes are: Minimum Spanning Tree games (Bird [1], Granot and Huberman [10, 11]), Tree

D. Skorin-Kapov, H.F. Beltrdn, Capacitated network design problems

93

games (Megiddo [18]), Airport games (Littlechild [16]), Fixed Cost Spanning Forest (FCSF) games (Granot and Granot [9]), Steiner Tree (ST) games (Skorin-Kapov [25]), and Simple Plant Location games (Kolen [13], Kolen and Tamir [14]). Relatively little has been done on the analysis of game-theoretic cost allocation solutions for classes of capacitated network problems (for an example of work in that direction, see Skorin-Kapov [24]). The objective of this paper is to provide a game-theoretic analysis of cost allocation problems associated with several classes of capacitated network design problems. The main feature is that the introduction of capacities imposes a limit on the number of users that can be served by a single facility. Throughout the paper, we use this feature to show that several gametheoretic solution concepts can be characterized with the same set of constraints (polynomial in size). This further suggests that the computations of the above cost allocation solutions may be feasible for a large class of quite realistic and practical capacitated network design problems. The plan of the rest of the paper is as follows. In section 2, we introduce some definitions and preliminary considerations. In section 3, we analyze the core of the CND game and present its polynomial characterization. In section 4, in the case of a nonempty core, we develop a method to efficiently compute the nucleolus of the CND game. In section 5, we propose the least weighted e-core as a cost allocation solution concept associated with the CND game and give its polynomial characterization. Moreover, we efficiently compute "central" point in the least weighted e-core. In section 6, we examine several classes of network design problems. In particular, we apply our results to the corresponding cost allocation problems associated with the Capacitated Minimum Spannin Tree problem, the Capacitated Concentrator Location problem, the Capacitated Fixed Cost Spanning Forest problem, and the Capacitated Steiner Tree problem. A summary and concluding remarks are presented in section 7.

2.

Definitions and preliminaries

In order to analyze the cost allocation problem associated with the CND problem, we need to introduce the following game-theoretic definitions and notation. Let N = { 1, 2 . . . . . n } be a finite set of players and let c : 2 N ~ R, with c(0) = 0, be a characteristic function defined over subsets of N referred to as coalitions. If c(N) designates a cost that has to be shared by all the players, then the pair (N; c) is called a (cost) cooperative game, or simply a game. For x ~ R n and S ~_ N, let x ( S ) - Y.jesXj. We can interpret x(S) as the part of the total cost paid by the coalition S, A cost allocation vector x in a game (N; c) satisfies x(N) = c(N), and the solution theory of cooperative games is concerned with the selection of a reasonable subset of cost allocation vectors. The characteristic function c is submodular if c(S) + c(T) > c(S u T) + c(S c7 T) for all S, T c N. If c is submodular, (N; c) is said to be concave. Central to the solution theory of cooperative games is the

94

D. Skorin-Kapov, H.F. Beltrdn, Capacitated network design problems

concept of solution referred to as the core of a game. The core of a game (N; c) consists of all vectors x ~ R n such that x(S) < c(S) for all S c N, and x(N) = c(N). Observe that the core consists of all allocation vectors x which provide no incentive for any coalition to secede. In general, the core of a game may be empty. For a real number e, the e-core of a game (N; c) consists of all vectors x E R n such that x(S) + e < c(S) for all 0 r S c N. and x ( N ) = c(N). Clearly, for e small enough, the E-core of the game (N; c) is not empty. The least e-core is the intersection of all nonempty e-cores. Equivalently, let e0 be the largest e such that the e-core is not empty, then the least e-core is the t0-core. The nucleolus, introduced by Schmeidler [22], is another well-known concept of solution. Intuitively, the nucleolus is an allocation that makes least-well-off coalition S as well-off as possible in a lexicographical sense. We say that a coalition S is better-off than T, relative to an allocation x, if c(S) - x(S) > c(T) - x(T). Formally, the nucleolus can be presented as follows. For a game (N; c) and an associated cost allocation vector x, let quantity e(x, S) = c(S) - x(S) be referred to as the excess of S relative to x, and let e(x) be a vector in R (2~-2) whose entries are e(x, S), 0 ~ S c N, arranged in a nondecreasing order. The nucleolus is the vector x that maximizes e(x) lexicographically. In contrast to the core, a nucleolus always exists. Moreover, it is unique and it is contained in the core if the core is not empty. Another reasonable approach is to define the excess of a coalition on a per capita bases: ~(x, S) = (1/IS I) ( c ( S ) - x ( S ) ) . Let ~(x) be a vector in R (2n-2), whose entries are ~(x), 0 # S c N, arranged in a nondecreasing order. The p e r capita nucleolus (Grotte [8]) is the vector x that maximizes ~(x) lexicographically. The cost allocation problem associated with the CND problem is concerned with the allocation of the cost incurred by satisfying the users' demand for service. Consider a CND problem on the network G = (N, E). Denote by CNDs, for S c_ N, the CND problem obtained from the original problem by simply setting demands di, for all i E N IS, to zero. The pair (N; c), where c" 2 N ---->R is such that c(0) = 0 for each S c N, c(S) is the minimum objective function calue of CND s, is a cooperative game in characteristic function form, to be referred to as the Capacitated Network Design (CND) game. In our definition of the characteristic function c, we assume that the coalition S, while acting on its own, can establish a facility at a node i even if it is not owned by S (i ~ S), and can use a link (i, j ) even if it is not owned by S (i o r j ti~S). A similar approach in defining a characteristic function was taken in some related uncapacitated network games (for example, the FCFS game (Granot and Granot [9]) and the ST game (Skorin-Kapov [25]). However, it might be reasonable to argue that nodes out of S will not necessarily allow (at least not free of charge) a coalition S to use nodes and links which are not controlled by S. Consequently, a more restrictive model in which coalition S can not use nodes out of S may also be of interest. If such a more restrictive approach is taken, the CND game would no longer be monotone. Nevertheless, the entire analysis provided in this paper would still hold.

D. Skorin-Kapov, H.F. Beltrtin, Capacitated network design problems

95

It is easy to see that the CND problem is NP-hard. It can be demonstrated that the Capacitated Minimum Cost Spanning Tree (CMCST) is a special case of the CND problem. Indeed, consider the special case of the CND problem on an underlying network G = (N, E) in which all demands for service di, i E N are strictly positive. For i E N, ci denotes the cost of a potential facility i, and u i denotes the capacity of a facility i. Let G" = (N u { o }, E') be an augmented network with E" = E u {(o, i): i E N }, and for each i E N, let Col be the cost of link (o, i) and ui the capacity of link (o, i). The problem of finding a minimum cost spanning tree in G' rooted in o, with the additional constraint that the total demand of any subtree rooted in node i, which is a neighbor of o, should not exceed capacity ui, is called the Capacitated Minimum Spanning Tree (CMST) problem (see Gavish [6]). It is easy to see that finding an optimal solution to the above CND probem on G is equivalent to finding an optimal C M S T on G'. Thus, the CMST problem is a special case of the CND problem in which all users have strictly positive demand for service. Since the CMST problem is NP-hard (Garey and Johnson [5]), so is the CND problem. 3.

The core of the C N D game

We first show that the core of the CND game may be empty. Consider, for example, the network G = (N, E) consisting of a three-node ring (fig. 1) with N = { 1, 2, 3 } and E = {(1, 2),(2, 3),(1, 3)}. Let u 1 = u 2 = u 3 = 2 be the capacity of potential facilities, cl = c2 = c3 = 1 the cost of opening facilities, cl2 = c23 = cl3 = 0.1 the cost of potential links, and d t = d2 = d3 = 1 the demand for service.

Fig. 1. Network G = (N, E).

Now, one can easily verify that the core constraints induced by the twom e m b e r coalitions are X 1 -b X 2 _< 1.1,

X 1 -F X 3 _<

1.1, x2 + x3 <- 1 . 1 .

(3.1)

=2.1.

(3.2)

The entire cost is X 1 q - X 2 -I-X 3

If we sum up inequalities in (3.1), we obtain X l -I- X 2 q- X 3 ~ 1 . 6 5 ,

96

D. Skorin-Kapov, H.F. Beltrdn, Capacitated network design problems

which contradicts the total cost allocation in (3.2). Thus, we conclude that the core of the CND game associated with G is empty. Consider now a general case of the CND game. Let G = (N, E) be the underlying network, and for i E N, let d i be the demand for service, ui the capacity of a potential facility i, and c i the cost to open a facility i. Clearly, the exponential n u m b e r of core constraints, coupled with the fact that the computation of c(S) is NP-hard in general, makes the core computations hard. Nevertheless, below we provide an efficient representation of the core, which often enables us to test whether the core of a C N D game is empty, and generate core points (if they exist) in polynomial time. THEOREM 1 Let St'= {SIS is a subset of N, such that an optimal solution to CNDs has a single opened facility }. Then, the core of a CND game is given by all cost allocations x E R tNI, satisfying

c(S) - x(S) > O,

for all S E 5e,

c(N) - x(N) = 0.

(3.3) (3.4)

Proof We will show that all core constraints excluded from (3.3) and (3.4) are redundant. Let S be a proper subset of N which is not contained in 5r For any set Q, a collection of its subsets { Qi, i E I} is called a partition of Q if UietQi = Q, and Q i n Q j = O for i, j E1 and i~:j. Below, we will construct a partition of S, {Si, i ~ F}, such that: (i) Si ~ 5e, for each i E F; and (ii) c(S) > Y.ie Fc(Si). Observe that the optimal solution to CNDs is a forest which has one open facility in each connected component. In the first step of our construction, we obtain the partition {Si, i E F l } of S, where for each i E Fl, Si is the subset of users in S which are serviced by the same facility in the optimal solution to CNDs. Let ~(Si ) be the cost of the connected component in the optimal solution to CNDs which contains a subset of users Si (the cost of a facility serving users in Si + the cost of links in that connected component). Then c( S) = Y~i ~ FII ~( Si ) ~ ~ i ~ F1 c( Si ), which means that the current partition of S satisfies condition (ii). If for each i E F1 an optimal solution to CNDsi uses a single facility (i.e. (i) holds), we have already constructed the required partition of S. Otherwise, for each i E Fl for which the optimal solution to CNDs; has more than one open facility, we refine the current partition by further partitioning Si. Namely, we apply the first step of our construction to all sets S i, i ~ F~ which are not in ~. It is easy to verify that this refinement provides us with a new partition {Si, i EF2} of S, for which (ii) holds (i.e. c(S) > Y~ieFz r We proceed in this manner until a partition {Si, i ~ F} satisfying (i) and (ii) is found. Since each user is served by a single facility, the above construction will produce such a partition in less than n iterations.

D. Skorin-Kapov, H.F. Beltrdn, Capacitated network design problems

97

Let {Si, i ~ F} be a partition obtained by the above construction which satisfies conditions (i) and (ii). Then conditions (3.3) imply that c ( S ) - x ( S ) >_

( c ( S i ) - x ( S i ) ) >_ o . ieF

Hence, the core constraint induced by S is redundant and the proof is complete.

[]

It is reasonable to assume that capacities ui, i E N and demands di, i E N are such that the m a x i m u m number of users that can be served by a single facility is bounded with some fixed upper bound K. Then the size of each set S ~ 6e is bounded by K. Moreover, the size of a family of sets 5e is in the worst case bounded by a K-degree polynomial and consequently sets in b" can be generated in polynomial time. This further implies that if c(N) is obtained as an optimal solution to the CND problem, then the nonemptiness of the core of the CND game can be, at least in theory, efficiently tested. We will further discuss the matter of efficiency in section 6.

4.

The nucleolus of a C N D game

If the core of a CND game is not empty, it may consist of many cost allocations which are not equally "attractive". Consider a simple example of a CND game in which the underlying network G = (N, E) consists of a chain, given in fig. 2, with

9

9

@

Fig. 2. G = (N, E).

N = {1, 2, 3} and E = {(1, 2),(2, 3)}. Assume that demands are dl =d2 =d3 = 1, potential facility costs are cl = c2 = c3 = 2, link costs are cl2 = 0, c23 = 2, and capacities of potential facilities are u~ = u 2 = u 3 = 2. It is easy to check that the cost allocations Xl = 2, x2 = 0, x3 = 2 and x~ = 1, x~ = 1, x~ = 2 are both in the core of the game (N; c) associated with G. Clearly, the second solution is preferable to player 1, while the first solution is preferable to player 2. For the case when the core of a CND problem is not empty, we will try to determine an "attractive" point in the core, namely the nucleolus. A method for computing the nucleolus by solving a sequence of linear programming (LP) problems was implicitly suggested by Schmeidler [22] and then further studied in [15, 12,2,3,17]. The kth LP problem, LPk, solved by this method is

98

D. Skorin-Kapov, H.F. Beltrdn, Capacitated network design problems

max { t 9 ej = c ( S ) - x ( S ) , S 9

k, S ~ U

j=l

..... k-l,

e
} PJ' xi <- c({i}), i = 1. . . . . n, x ( N ) = c ( N )

,

(LPk)

j=l where for j > 1, Ej and Pj are, respectively, the optimal value and the set of subsets whose corresponding inequality constraints are satisfied as equalities at an optimal solution of LPj. The nucleolus is obtained at problem LPi if the optimal solution to LPi is unique. We will refer to this method as the linear programming (LP) procedures for computing the nucleolus. It is easy to show that the CND game is not necessarily concave, which implies (Maschler et al. [17]) that the redundant core constraints may be needed to determine the nucleolus. Nevertheless, when the core of a CND game is not empty, we show below that the collection of constraints used to characterize the core in theorem 1 is sufficient to completely determine the nucleolus of a CND game. THEOREM 2

If the core of a CND game is not empty, then the nucleolus of a CND game is completely determined by constraints associated with the family of coalitions 5e. Proof We will use a proof technique, first introduced by Granot and Huberman [11], to show that all core constraints induced by subsets not in 5e are redundant in the LP procedure for computing the nucleolus. Let S be a subset of N which is not contained in 6e. By theorem 1, there exists a partition of S {Si, i 9 F }, such that Si 9 SP for each i 9 F, and

c( S) - x( S) >~ ~ c( Si ) - ~ x( Si ) . i~F i~ F

(4.1)

Since the core is not empty, the nucleolus must be in the core and then c(Si) - x ( S i) > 0, for all i E F. This imples that

i~F

c( Si ) - ~a x( Si ) >- c( Si ) - x( Si ) i~F

for all i E F.

(4.2)

for all i E F.

(4.3)

Together, (4.1) and (4.2) imply that c(S) - x(S) > c(Si ) - x(Si )

D. Skorin-Kapov, H.F. Beltrdn, Capacitated network design problems

99

Now, if for Q, Q c N, LPt(Q) denotes the linear program in the LP procedure for computing the nucleolus of the CND game in which the constraint e < c ( Q ) - x ( Q ) corresponding to Q has been first satisfied as an equality at the corresponding optimal value et(a) , then et(s,) = c(Si ) - x(Si )

for i E F

(4.4)

and et(s) = c(S) - x ( S ) .

(4.5)

Observe that by (4.3), etcs)> etcsi), for all i E F, which implies that the constraints (4.4) would be satisfies as equalities in the LP procedures for computing nucleolus before constraint (4.5) is satisfied as an equality in this procedure. Moreover, since x ( S ) = ~ i ~ F X ( S i ) , constraints (4.4) completely determine the value of the total allocation to subset S, and therefore constraint (4.5) is redundant in the above procedure. [] Recall that the nucleolus is unique and it always exists. However, it appears to be difficult to efficiently characterize the nucleolus of a CND game when the core is empty. Therefore, in the next section we propose some alternative cost allocation solutions for that case.

5.

The least weighted e-core

In this section, we propose the least weighted E-core of a CND game as a solution concept for a fair cost allocation associated with the CND problem. For each coalition S, S c N, let w s be the weight associatd with S. Then the weighted E-core is a set of cost allocation vectors such that for all coalitions S, 0 ~ S c N : c ( S ) - x ( S ) > Wse and c ( N ) - x ( N ) = O. The weighted E-core can be interpreted as the set of efficient cost allocations that can not be improved upon by any coalition S if forming a coalition entails a cost - Wse. Clearly, the weighted E-core is not empty if e is sufficiently small. Let e' be the largest e for which the weighted E-core is not empty. Then the weighted e'-core is the least weighted E-core. It appears that e' is particularly interesting when it is negative, i.e. when the core of a game (N; c) is empty. For S c N, we can think of - W s e ' as the minimal weighted cost - W s e , or cross-subsidy, for which the weighted E-core is not empty. Note that the above cost-based subsidization does not use the information about the willingness of a coalition S to pay. Also note that even for the case of subsidy-free cost allocations, there is no generally preferable method of choosing one subsidy-free allocation rather than another (see, for example Sharkey [23]). We will show below that with a suitable choice of weights, the least weighted E-core of a CND game can be characterized by the collection of constraints associated

100

D. Skorin-Kapov, H.F. Beltrttn, Capacitated network design problems

with the family of coalitions 5~. It seems reasonable to assume that the potential cross-subsidy absorbed by the coalition S should be proportional to the size of S or the amount of total demand of users in S. Under such assumption, additivity of the weight function is a natural choice. The choice of appropriate weights will be further discussed in the remark after theorem 3. Let w be a real valued weight function, defined on the partition set of N, and for S c_ N, let w ( S ) = w s. We say that the weight function w is additive, if for any two subsets Si, $2 c_ N, such that Sx n S 2 -- 0, we have Ws~ + Ws2 = Wslus 2. THEOREM 3

Let w s, S c N, be the weights generated by an additive weight function w. Then the least weighted e-core of the CND game (N; c) is completely determined by constraints associated with the collection of coalitions 5~. Proof

We will prove below that the least weighted e-core constraints corresponding to subsets which are not in the collection 50 are redundant. Let e" = m a x { e l ( c ( S ) - x ( S ) > Wse,

for S E 50 and 0 ~ S c N, and c ( N ) = x ( N ) } ,

(5.1)

e" = max{el(c(S) - x(S) > wse,

for S E 2 N and 0 :g: S c N, and c ( N ) = x ( N ) }.

(5.2)

We will show that e' = e': Clearly, since (5.1) is a relaxation of (5.2), we have e' > e". It remains to be shown that e" > e'. Let (x, e') be an optimal solution to (5.1) and let S be any subset of N. Let Si, i E F, be the partition of S satisfying (i) and (ii) of theorem 1. This, together with the additivity of the weight function w, implies that

r

x(S) >_ Z ( c ( S i ) ieF

which further implies that e " > e'.

X(Si )) ~- Z Wsie' = wse', i~F []

Remark

The weights wi, i E N, should be decided upon on a case-by-case basis. One reasonable practical suggestion for the choice of a weight function is an additive

D. Skorin-Kapov, H.F. Beltrtin, Capacitated network design problems

101

function w, dependent on node demands, defined as follows; for i E N, w i = dilD, where D = ~,i~ Ndi is the total demand for service of the entire network. For a special case, when the above weights in theorem 3 are w s = I S I, for all S c N, the least weighted G-core is called the least per capita G-core. Also note that if weights Ws, S c N, in the analysis of theorem 3 are nonnegative, theorem 3 would hold in the case of an empty core for any super additive weight function w (w is super-additive if wsl + Ws2 < Ws~us2, for all SI, $2 c N, such that S I n $2 = 0), and in the case of a non-empty core for any sub-additive weight function (w is sub-additive if Ws~ + Ws2 > Wslus 2, for all SI, $2 ___N, such that $1 n $2 = 0). In order to further analyze the least weighted G-core we introduce, for an arbitrary 6, the game (N; ce) whose characteristic function cE is defined as follows:

c~(S)=

c(S)-wse

if 0 ~ S c N ,

c(S)

if S = N .

Observe that the core of the game (N; ce) coincides with the weighted G-core of the game (N; c). Let 6' be the largest e for which the game (N; ce) has a nonempty core. Then the core of a game (N; ce,) coincides with the least weighted G-core of a game (N; c). A sensible way of selecting a unique point from the least weighted G-core is selecting the nucleolus of the game (N; ce,). For example, when the core is empty, under the assumption that every coalition has agreed to participate in a crosssubsidy with additional cost - W s e ' , such a cost allocation would lexicographically maximize minimal excess. Next, we show that the nucleolus of a game (N; c~,) can also be characterized by the set of constraints associated with the collection Se. THEOREM 4 Let w s, S c_ N, be weights generated by an additive weight function w. Assume that the core of a game (N; c) is empty, and let 6' be the largest e for which the weighted G-core of a game (N; c) is not empty. Then the nucleolus of a corresponding game (N; c~,) is completely determined by constraints induced by the collection of coalitions 6e. Proof

Similarly to the proof of theorem 2, we will show that all core constraints induced by subsets not in 5e are redundant in the LP procedures for computing the nucleolus. Let S be a nonempty proper subset of N which is not contained in Se. Let { Si, i E F } be the partition of S satisfying conditions (i) and (ii) from theorem 1. Now we have

102

D. Skorin-Kapov, H.F. Beltrdn, Capacitated network design problems

c~, ( S ) - x ( S ) = c ( S ) - x ( S ) - w s e " >- ~ , ( c ( S i ) - x ( S i ) ) - w s e '

i~F = ~ , ( c ( S i ) - x ( S i ) - Wsi e ' ) > c(Si ) - x ( S i ) - Ws i e ' i~F

for each i E F.

(5.3)

The first inequality in (5.3) follows from condition (ii) of theorem 1, the second equality in (5.3) holds since w is additive, while the second inequality in (5.3) follows from the fact that the nucleolus of the game (N; cE,) is in the core of (N; cE,). If, similarly to the discussion in theorem 2, for Q c N, LPt(Q)denotes the linear program in the LP procedure for computing the nucleolus of the game (N; cE,) in which the constraint e < ce,(Q) - x ( Q ) corresponding to Q has been first satisfied as an equality at the corresponding optimal value et(a), then et(si) = c ( S i ) - x ( S i ) - Wsie"

for i ~ F

(5.4)

and et(s) = c ( S ) - x ( S ) - W s e ' .

(5.5)

Clearly, by (5.3) et(s) > Et(si), for all i E F, which implies that the constraints (5.4) would be satisfied as equalities in the LP procedure for computing the nucleolus before the constraint (5.5) is satisfied as an equality. Since by construction x ( S ) -" ~,i~ FX(Si), constraints (5.4) completely determine the value of the total allocation to subset S and constraint (5.5) is redundant in the above procedure. [] Observe that if Ws = IS I, for all S ~ N, and if the nucleolus of (N; cE,) is the unique solution to the first linear program in the LP procedure for computing the nucleolus, then the nucleolus of the game (N; ce,) coincides with the nucleolus per capita of the game (N; c).

6.

Applications and special cases

In this section, we will employ our characterization of the core, the nucleolus, the least weighted e-core, and the "center" of the least weighted e-core of the CND game presented in theorems 1 - 4 to several classes of capacitated network problems. In special cases of our CND problem, considered below, we assume that demands di, i E N , and capacities of potential facilities ui, i EN, are such that they determine some fixed upper bound K on the number of nodes that can be served by a single facility. Consequently, the cardinality of a set ~ is bounded with a Kdegree polynomial. Moreover, since the size of each set S E 6P is bounded by K, we can use total enumeration to generate all sets S ~ ~ and to compute the characteristic function value c(S), for each S ~ 5", in polynomial time. The worst case time required to compute c(S), although polynomial, is still exponential in the fixed number K,

D. Skorin-Kapov, H.F. Beltrtin, Capacitated network design problems

103

which may be a problem if K is not sufficiently small. However, the saving may be in the fact that the computation of c(S), for S ~ 5e, is trivially parallelizable. It is conceivable that parallelization might make even the use of "brute force" practical for the computation of c(S), S ~ 6e. In addition, in practical situations the underlying network G = (N, E) will not always be a complete graph and will often posses some structure. G may be a tree, a ring, a series parallel graph, a partial k-tree, nodes may have a bounded degree, etc. Clearly, recognizing the structure of G may further reduce the size of Se and the time needed to compute the characteristic function values for sets in 5e. Moreover, for such special cases of G we can sometimes compute the exact value of c(N). When the optimal solution to c(N) cannot be found, we approximate it with the best known heuristic solution for the network design problem. Next, we employ our CND game solution characterizations to several classes of cost allocation problems which were not previously studied in the literature. 6. I.

CAPACITATEDMINIMUM COST SPANNINGTREE GAME

Let G' = ( N u {o}, E} be an underlying network. For all i EN, let di > 0 be the demand for service. For each i adjacent to o, let coi be the cost of link (o, i) and ui the capacity of (o, i). The problem of finding a minimum spanning tree in G" rooted in o, with the additional constraint that the total demand of any subtree rooted in node i, which is a neighbor of o, should not exceed capacity ui, is called the Capacitated Minimum Spanning Tree (CMST) problem (see Gavish [6]). This model arises, for example, in computer networking when node o is a central processor and for reasons of reliability we wish to limit the number of terminals (nodes) attached to this node through any of its ports (incident arcs). It is easy to see that the CMST is equivalent to the CND problem defined on a network G obtained from G' by removing node o and all arcs adjacent to o, in which for all i E N, di is the demand of user i, ui is the capacity of a potential facility i, and ci = Col is the cost of opening facility i. It is now straightforward to define the corresponding CMST game in precisely the same manner as we defined the CND game, and then the entire cost allocation analysis presented in sections 3, 4 and 5 can be applied to the CMST game. 6.2.

CAPACITATEDFIXED COST SPANNING FOREST GAME

The CND problem properly generalizes the Fixed Cost Spanning Forest (FCSF) problem. Namely, the FCSF problem is a special case of the CND problem with all potential facilities having infinite capacities. The Steiner Tree (ST) problem can be formulated as follows. Given a connected undirected graph G = (N u {o }, E) and a set of nodes D, D c_ N, find a tree T in G whose node set containes D u {o} and the total edge-weight of T is minimum.

104

D. Skorin-Kapov, H.F. Beltrdn, Capacitated network design problems

The FCSF problem on the network G is equivalent to the Steiner Tree problem on the augmented network G', obtained from G by adding node o and links (o, i), with costs Coi= ci, for all potential facilities i (for more details, see Granot and Granot [9]). The CND game properly generalizes the FCSF game [9], and the Steiner Tree (ST) game [25]. We also stress that the exact polynomial computation of the core and the nucleolus of the uncapacitated FCSF game was done in [9] only for the special case when an underlying network G is a tree, and that only the heuristic approximation of the core points was computed for the uncapacitated Steiner Tree game in the general case [25]. Our analysis of the capacitated version of the above problem imposes no restriction on the structure of the underlying network G. However, when capacities are infinite, the set S~ used to characterize and compute the various solution concepts has an exponential cardinality, which implies that none of the solution concepts analyzed in this paper can be computed in polynomial time for that case. 6.3.

C A P A C I T A T E D C O N C E N T R A T O R (FACILITY) L O C A T I O N G A M E

The Capacitated Concentrator Location (CCL) problem is concerned with connecting several remote users (computers or terminals) to a central site (see Mirzaian [19], Pirkul [21]). This is accomplished via the use of concentrators. Relatively local sites are connected to a concentrator, and the concentrator is connected via a high-speed line or a satellite to the central site. Each concentrator has a capacity limit on the traffic it can handle. Let N be the set of users and potential concentrator sites. For i E N, let d i be the demand at i, ci the cost of opening a concentrator i with capacity ui, and for i,j EN, let c o be the cost of assigning user j to concentrator i. The objective is to minimize the total cost, which consists of the cost to open concentrators and the cost to assign users to concentrators. The CCL problem can be formulated as the following integer linear programming problem. For all i, j E N, let Yij be 0 - 1 variables with the following interpretation: Yii = 1 if a concentrator is opened at node i (and i is assigned to itself) and Yii ----0 otherwise, and Yij = 1 if u s e r j is serviced by concentrator i and Yij = 0 otherwise. Then the CCL problem is minimize

( ~ ciYii -I- i,j~N ~ ciJYiJ

subject to

~, Yij i~N

= 1

~, djYij < uiYii

for all i ~ N , (CCL) for all i E N,

j~N

Yij E {0, 1}

for all i, j E N.

D. Skorin-Kapov, H.F. Beltrtin, Capacitated network design problems

105

It is easy to see that the CCL problem is closely related to our CND problem. Let G = (N, N x N) be the underlying network. For i ~ N, let ci be the cost of opening a concentrator i with capacity ui and let di be the demand at node i. For i, j ~ N, let cij be the cost of using a link (i, j). Then, a slightly modified CND problem in which each node can receive service only directly from a facility is equivalent to the CCL problem. If we now define the CCL game in precisely the same manner as the CND game, it is easy to verify that the entire game-theoretic analysis presented in theorems 1 - 4 holds for the CCL game. The CCL problem is a proper generalization of the Capacitated Concentrator Covering game [24] (in which the cost of concentrators is allocated, while the cost of links is ignored), and the Star-Star Capacitated Concentrator Location game [25] (in which users in coalition S are allowed to receive service only from a concentrator in S). Also, observe that the CCL problem is closely related to the Simple Plant Location (SPL) problem. The SPL problem, defined with respect to G, is concerned with the location of facilities (plants, warehouses) at vertices in G so as to minimize the sum of set-up costs and the transportation costs for distributing the commodities between the facilities and the users. The SPL problem can be formulated as follows. For i E N, let ci be the cost of opening a facility i, and for i, j E N, let cij be the (transportation) cost incurred if user j is served by facility i and Yij the indicator whether j receives service from i. The SPL problem is then

subject to

~_, Yij =1

for all j E N,

ieN

~'~ Yij < n Yii

(SPL) for all i E N,

j~N

Yij E {0,1}

for all i , j E N.

Thus, the SPL problem can be viewed as a special case of the CCL problem with all demands equal to 1 and all capacities equal to n. The cost allocation problem associated with the SPL problem was analyzed for the special case when the underlying network G is a tree by Kolen [13] and Kolen and Tamir [14]. Our analysis of the cost allocation problem associated with the CCL problem in some sense extends considerations for the cost allocation problem associated with the SPL problem to a general network stucture with capacity constraints. Note, however, that in the capacitated version of the SPL problem studied in the literature (Capacitated Facility Location (CFL) problem (Geoffrion and McBride [7], Nauss [20])), user nodes can have more than one facility satisfying their demands, whereas in the CCL problem, a user must be assigned to a single concentrator.

106

7.

D. Skorin-Kapov, H.F. Beltrdn, Capacitated network design problems

Summary and conclusions

We considered the cost allocation problem associated with the Capacitated Network Design (CND) problem, which is a generalization of several classes of capacitated network problems. We formulated this problem as a cooperative game, referred to as the CND game. The efficient (often polynomial) characterization of several cost allocation solutions associated with the CND game was presented. Specifically, we characterized the core of the CND game with a polynomial number of constraints, and showed that for the case when the core is not empty, the nucleolus depends only on those core constraints. For the case when the core is empty, we provide a polynomial characterization of the least weighted e-core, and a polynomial characterization for the "center" of the least weighted e-core. If the optimal value of the objective cost function is given as a solution to the CND problem, then these characterizations enable us to compute the above cost allocation solutions in polynomial time. Moreover, we showed that our characterization of cost allocation solutions associated with the CND game can be employed for several other cost allocation problems, not previously studied in the literature. In particular, we provide such analysis of cost allocation solutions for the Capacitated M i n i m u m Spanning Tree game, the Capacitated Fixed Cost Spanning Forest game (or, equivalently, the Capacitated Steiner Tree game), and the Capacitated Concentrator (Facility) Location game.

Acknowledgements The authors are grateful to Professor Arie Tamir, to two anonymous referees, and to an associate editor for very helpful comments and suggestions which improved the presentation of this paper.

References [1] C. Bird, On cost allocation for a spanning tree: A gane theoretic approach, Networks 6(1976) 335 -350. [2] A. Charnes and K.O. Kortanek, On a class of convex and non-Archimedeansolution concepts for n-person games, System Research Memoradum No. 172, Technological Institute, Northwestern University (1967). [3] A. Charnes and K.O. Kortanek, On classes of convex and preemptive nuclei for n-person games, in: Proc. Princeton Syrup. on Mathematical Programming, ed. H.W. Kuhn (Princeton University Press, 1970) pp. 377-390. [4] T. Driessen, Cooperative Games, Solutions and Applications (Kluwer Academic, Dordrecht, 1988). [5] M.R.Garey and D.S. Johnson, Computersand Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979). [6] B. Gavish, Augmented Lagrangian based algorithms for centralized network design, IEEE Trans. Commun. COM-33(1985)1247-1257.

D. Skorin-Kapov, H.F. Beltrtin, Capacitated network design problems

[7] [8] [9] [10] [11] [12] [13] [14] [15]

[16] [17] [18] [19] [20] [21] [22]

107

A.M. Geoffriun and R. McBride, Lagrangian relaxation applied to capacitated facility location problems, AIIE Trans. 10(1978)40-47. J.H. Grotte, Computation of an observations on the nucleolus and the central games, M.Sc. Thesis, Comell University (1970). D. Granot and F. Granot, Computational complexity of a cost allocation approach to a fixed cost spanning forest problem, Math. Oper. Res. 17(1992)765-780. D. Granot and G. Huberman, Minimum cost spanning tree games, Math. Progr. 21(1981)1-18. D. Granot and G. Huberman, On the core and nucleolus of M.C.S.T. games, Math. Progr. 29(1984) 323 -347. M.A. Keane, Some topics in n-person game theory, Ph.D. Dissertation, Mathematics Department, Northwestern University (1969). A. Kolen, Solving covering problems and the uncapacitated plant location problem on trees, Euro. J. Oper. Res. 12(1983)266-278. A. Kolen and A. Tamir, Covering problems, in: Discrete Location Theory, eds. P.B. Michandani and R.L. Francis (Wiley, 1990) Ch. 6. A. Kopelowitz, Computation of the kernels of simple games and the nucleolus of n-person games, Research Memoradum No. 31, Department of Mathematics, The Hebrew University, Jerusalem (1967). S.C. Littlechild, A simple expression for the nucleolus in a special case, Int. J. Game Theory 3(1974)21-29. M. Machler, B. Peleg and L.S. Shapley, Geometric properties of the kernel, nucleolus and relation solution concepts, Math. Oper. Res. 4(1979)303-338. N. Megiddo, Computational complexity of the game theory approach to cost allocation for a tree, Math. Oper. Res. 3(1978)189-196. A. Mirzaian, Lagrangian relaxation of the start-star concentrator location problem: Approximation algorithm and bounds, Networks 15(1985)1-20. R.M. Nauss, An improved algorithm for the capacitated facility location problem, J. Oper. Res. Soc. 29(1978)1195-1202. H. Pirkul, Efficient algorithms for the capacitated concentrator location problem, Comp. Oper. Res. 14(1987)197-208. D. Schmeidler, The nucleolus of a characteristic function game, SIAM J. Appl. Math. 17(1969) 1163-1170.

[23] W.W. Sharkey, Economic and game-theoretic issues associated with cost allocation in a telecommunication network, in: Cost Allocation: Methods, Principles, Applications, ed. H.P. Young (North-Holland, Amsterdam, 1985) Ch. 8. [24] D. Skorin-Kapov, On a cost allocation problem arising from a capacitated concentrator covering problem, Oper. Res. Lett. 13(1993)315-323. [25] D. Skorin-Kapov, On the core of the minimum Steiner tree game in networks, Technical Report, Harriman School for Management, SUNY at Stony Brook (1993). [26] D. Skorin-Kapov and H.F. Beltr~, On a cost allocation problem arising from a star-star capacitated concentrator location problem, J. Comp. Inf. Tech~ 2(1994)1-8. [27] H.P. Young, Cost Allocation: Method, Principles, Applications (North-Holland, Amsterdam, 1985).