N E T W O R K SYNTHESIS P R O B L E M : COST A L L O C A T I O N AND ALGORITHMS By M E H R A N HOJATI B.Sc. M.Sc. (Economics), London School of Economics & Political Science, 1980 (Operational Research), London School of Economics & Political Science, 1981 A THESIS S U B M I T T E D IN P A R T I A L F U L F I L L M E N T O F THE REQUIREMENTS FORTHE DEGREE OF DOCTOR OF PHILOSOPHY in FACULTY O F G R A D U A T E STUDIES ( C O M M E R C E A N D BUSINESS ADMINISTRATION) We accept this thesis as conforming to the required standard T H E UNIVERSITY OF BRITISH COLUMBIA © M e h r a n Hojati, 1987 October 1987 In presenting degree this at the thesis in University of partial fulfilment of of department this or publication of thesis for by his or her Department The University of British Columbia 1956 Main Mall Vancouver, Canada V6T 1 Y 3 DE-6(3/81) representatives. If89 for an advanced Library shall make it agree that permission for extensive It this thesis for financial gain shall not nrJr 8, that the scholarly purposes may be permission. Date requirements British Columbia, I agree freely available for reference and study. I further copying the is granted by the understood that head of copying my or be allowed without my written 11 ABSTRACT T h i s thesis is concerned w i t h a network design problem which is referred to in the literature as the network synthesis problem. T h e objective is to design an undirected network, at a m i n i m u m cost, w h i c h satisfies k n o w n requirements, i.e., lower bounds on the m a x i m u m flows, between every pair of nodes. If the requirements are to be satisfied nonsimultaneously, i.e., one at a time, the problem is called the nonsimultaneous net- work synthesis problem, whereas if the requirements are to be satisfied simultaneously, the problem is called the simultaneous network synthesis problem. T h e total construc- tion cost of the network is the s u m of the construction cost of capacities on the edges, where the construction cost of a unit capacity is fixed for any edge, independent of the size of the capacity, but it may differ from edge to edge. T h e capacities are allowed to assume noninteger nonnegative values. T h e simultaneous network synthesis problem was efficiently solved by G o m o r y and H u [60], whereas the nonsimultaneous network synthesis problem can only be formulated and solved as a linear program with a large number of constraints. However, the special equal-cost case, i.e., when the unit construction costs are equal across the edges, can be efficiently solved, see G o m o r y and H u [60], by some combinatorial method, other than linear programming. A cost allocation problem which is associated w i t h the network synthesis problem would naturally arise, if we assume that the various nodes in the network represent different users or communities. In this case, we need to find a fair method for allocating the construction cost of the network among the different users. A n interesting generalization of the nonsimultaneous network synthesis problem, the Steiner network synthesis problem, is derived, when only a proper subset of the nodes have positive requirements from each other. The thesis is concerned w i t h two issues. F i r s t , we w i l l analyze the cost allocation problems arising in the simultaneous and the equal cost nonsimultaneous network synthesis problem. Secondly, we w i l l consider the Steiner network synthesis problem, w i t h particular emphasis on simplifying the computations in some special cases, not considered before. We w i l l employ cooperative game theory to formulate the cost allocation problems, a n d we w i l l prove that the derived games are 'concave', which implies the existence of the core and the inclusion of the Shapley value and the nucleolus in the core, and then we w i l l present irredundant representations of the cores. For the equal cost nonsimultaneous network synthesis game, we will use the irredundant representation of iii the core to provide an explicit closed form expression for the nucleolus of the game, when the requirement structure is a spanning tree; then, we w i l l develop, in a special case, a decomposition of the game, which we w i l l later use to efficiently compute the Shapley value of the game when the requirement structure is a tree; the decomposition w i l l also be used for the core and the nucleolus of the game in the special case. For the simultaneous network synthesis game, we w i l l also use the irredundant representation of the core to derive an explicit closed form expression for the nucleolus, and we will also decompose the core of this game in the special case, a n d prove that the Shapley value and the nucleolus coincide. Secondly, for the Steiner network synthesis problem, two conceptually different contributions have been made, one being a simplifying transformation, and the other being the case when the network has to be embedded i n (i.e., restricted to) some special graphs. Namely, when the requirement structure is sparse (because there are only a few demand nodes and the rest are just intermediate nodes) and the positive requirements are equal, we w i l l employ a transformation procedure to simplify the computations. T h i s w i l l enable us to efficiently solve the Steiner network synthesis p r o b l e m w i t h five or less nodes which have equal positive requirements from each other. Finally, when the solution network to the Steiner network synthesis problem is to be embedded i n (restricted to) some special graphs, namely trees, rings (circles), series-parallel graphs, or M 2 and M - f r e e graphs, we w i l l provide combinatorial algorithms w h i c h are expected 3 to simplify the computations. C on tents 1 2 ABSTRACT ii Table of Contents iv List of Tables vii List of Figures viii ACKNOWLEDGEMENT x INTRODUCTION 1 1.1 T h e Network Synthesis P r o b l e m 1 1.2 Cost A l l o c a t i o n and Introduction to Cooperative Game Theory 4 1.3 T h e Steiner Network Synthesis P r o b l e m COST ALLOCATION IN THE NETWORK 12 SYNTHESIS PROB- 17 LEM 2.1 Introduction, Notation and Preliminaries 17 2.1.1 Introduction 17 2.1.2 G a m e Theory N o t a t i o n and Preliminaries 18 2.1.3 G r a p h Theory Notation and Preliminaries 22 2.2 C o n c a v i t y of the Network Synthesis Games 26 2.3 Irredundant Representation of the Cores of ( i V ; c i ) and (N;c ) 30 2.4 T h e Nucleolus of the Network Synthesis Games 36 2.5 Nearly Decomposable Network Synthesis Games 41 2.6 Decomposition of Cores of Nearly Decomposable Games (N; C\) a n d (N; c ) 2 2 iv 43 V 3 2.7 T h e Nucleolus of the Nearly Decomposable G a m e (N; c ) 47 2.8 Shapley Values of ( i V ; c i ) and Nearly Decomposable (N;^) 51 2.9 S u m m a r y and Further Research for the Cost A l l o c a t i o n P r o b l e m . . . . 56 2 A S I M P L I F Y I N G T R A N S F O R M A T I O N F O R The S T E I N E R N E T WORK SYNTHESIS PROBLEM 58 3.1 T h e Steiner Network Synthesis P r o b l e m 58 3.2 Simplifying the Equal-Requirement Case: Preliminaries 60 3.3 3.2.1 Linear P r o g r a m m i n g Formulations and the Transformation 3.2.2 D u a l Problems and the L a m i n a r i t y of D u a l Solutions to (P') 4 61 . . O p t i m a l i t y of the Subnetwork W 3.3.1 3.4 . . . 63 65 A Modified D i j k s t r a A l g o r i t h m and the Construction of a Solution to (D) 65 3.3.2 Feasibility of the Derived D u a l Solution 70 3.3.3 Implication of the Transformation 71 S u m m a r y and Further Research for the Transformation 72 T H E S T E I N E R N E T W O R K S Y N T H E S I S P R O B L E M IN S O M E SPECIAL GRAPHS 4.1 Trees and Rings; Series-Parallel Graphs: Preliminaries and the E q u a l Requirement Case 74 4.1.1 Trees and Rings 74 4.1.2 Series-Parallel Graphs: Preliminaries and the E q u a l Requirement Case 4.2 4.3 73 75 Series-Parallel G r a p h s : N o n - E q u a l Requirement Case 85 4.2.1 T h e A d d i t i o n a l Complications 85 4.2.2 T h e Monotone Requirement Case 89 4.2.3 T h e N o n - M o n o t o n e Requirement Case 93 M 2 and M - F r e e Graphs 3 96 vi 4.3.1 Preliminaries 98 4.3.2 B u i l d i n g Blocks and C o m p o s i t i o n rules 99 4.3.3 A Combinatorial A l g o r i t h m 101 4.3.4 A Fractional Solution 102 4.4 S u m m a r y and Further Research 104 4.5 A F i n a l Comment 105 BIBLIOGRAPHY 107 L i s t of Tables 4.1 T h e Series C o m p o s i t i o n M a t r i x 82 4.2 The Parallel Composition Matrix 83 4.3 T h e C o m p u t a t i o n s for E x a m p l e 4.1 85 4.4 T h e C o m p u t a t i o n s used in E x a m p l e 4.5 94 4.5 T h e Computations used i n E x a m p l e 4.6 97 vii List of Figures 1.1 A Rectangular Warehouse, and Some Items (the thicklined nodes) to be P i c k e d up 15 2.1 A Requirement Structure (left), and a M R S T in it (right) 23 2.2 T h e Equal-Requirement Subtrees 24 2.3 O p t i m a l Solution Subnetworks for the Equal-Requirement Subtrees. 2.4 T h e Superimposed O p t i m a l Solution Subnetwork 24 2.5 A Requirement Structure, and the O p t i m a l Solution Networks 27 2.6 A Spanning Tree Requirement Structure Used in T h e o r e m 2.3 34 2.7 A Spanning Tree Requirement Structure 42 2.8 T h e Requirement Structure (left) used i n E x a m p l e 2.4, and the Networks . . 24 Resulting from the Near-Decomposition (center and right) 54 3.1 G r a p h G, and point set Si 64 3.2 A n O p t i m a l Solution Subnetwork i n G', and the D i j k s t r a Cuts 68 3.3 A n O p t i m a l Solution Subnetwork i n G, and the D i j k s t r a C u t s 69 3.4 Mi (left), M 71 4.1 Types i , i i , i i i , i v , v , v i , and v i i (from left to right) of P a r t i a l E x t r e m e Solu- 2 (center), and M 3 (right) tion Subnetworks i n a Simple P a t h Associated w i t h the Steiner Network Synthesis P r o b l e m , w i t h Requirements E q u a l to 2, in a Series-Parallel 4.2 Graph 81 A Series-Parallel G r a p h (left), and its Reduced G r a p h (right) 83 viii ix 4.3 A B i n a r y Decomposition Tree for the Reduced G r a p h in Figure 4.2. . . 4.4 A n O p t i m a l Solution Subnetwork for E x a m p l e 4.1 4.5 A Series-Parallel G r a p h (left), and an O p t i m a l Solution Subnetwork i n it (right) 4.6 4.9 87 87 O p t i m a l Solution Subnetworks 1 (left) and 2 (center), and the Superimposed Subnetwork (right) 4.8 86 A M R S T (left), Equal-Requirement Subtrees 1 (center) and 2 (right), Derived i n the Decomposition from the M R S T 4.7 84 88 A n O p t i m a l Solution Subnetwork (left), and another O p t i m a l Solution Subnetwork (right) used in E x a m p l e 4.3 89 A Series-Parallel G r a p h (left), and its Reduced G r a p h (right) 92 4.10 A M R S T (left), and Equal-Requirement Subtrees 1 (center), and 2 (right), Derived from the M R S T by the Decomposition 92 4.11 Best P a r t i a l Composed Solution Subnetworks for ( E , E , 1 C ) - ( E , E , 1 C ) at Stages 1 (left), 2 (center), and 3 (right) 4.12 T h e M R S T used i n E x a m p l e 4.6 93 95 4.13 Best P a r t i a l Composed Solution Subnetworks of T y p e ( E , E , l C ) - ( E , E , l C ) at Stages 1 (left), 2 (center), and 3 (right) 96 4.14 A Wheel (left), and a Propeller (right) 100 4.15 K 101 4 (left), and its Cockade w i t h Three Triangles (right) 4.16 A Fractional Solution for the (Steiner) Network Synthesis P r o b l e m . . . . 103 X ACKNOWLEDGEMENT T h e author is indebted to his research supervisor, Professor Daniel G r a n o t , for introducing h i m to the subject of this thesis and guiding h i m through it, as well as providing financial and moral support. Furthermore, the author wishes to thank members of his dissertation committee, especially, D r . M a u r i c e Queyranne and D r . R i c h a r d Anstee, for offering many hours of consultation, as well as for carefully reading the thesis and m a k i n g critical but beneficial suggestions. T h e author is grateful for the financial support given to h i m by the University of B r i t i s h C o l u m b i a and the Faculty of Commerce and Business A d m i n i s t r a t i o n . C hapter 1 INTRODUCTION 1.1 The Network Synthesis Problem T h i s thesis is concerned w i t h a network design problem w h i c h is referred to in the literature as the network synthesis problem. T h e objective is to design an undirected network w i t h a m i n i m u m construction cost, w h i c h satisfies known requirements, i.e., lower bounds on the m a x i m u m flows, between every pair of nodes. If the requirements are to be satisfied nonsimultaneously, i.e., one at a time, the problem is called the nonsimultaneous network synthesis problem, whereas if the requirements are to be satisfied simultaneously, the problem is referred to as the simultaneous network synthesis prob- lem. Since i n this thesis we are p r i m a r i l y concerned w i t h the nonsimultaneous case, for brevity, we w i l l refer to the nonsimultaneous network synthesis problem as the network synthesis problem. T h e total construction cost is the sum of the construction cost of capacities on the edges, and the construction cost of a unit capacity is fixed for any edge, and thus is independent of the size of the capacity, but it may differ from edge to edge (e.g., it may be proportional to the edge's length). T h e capacities are allowed to assume integer and noninteger nonnegative values. T h e network synthesis problem originated as a research problem i n Electrical E n g i neering, see e.g., W i n g and C h i e n [158]. T h e problem was formulated as a linear program w i t h a large number of constraints, and a special equal-cost case, i.e., w h e n the Unit construction costs are equal across edges, was solved efficiently by some combinatorial methods other than linear programming. G o m o r y and H u [58] gave a conceptually simpler method for solving the equal-cost case, and in [59], they devised some row generation simplex methods to simplify and accelerate the computations in the linear program 1 2 formulation of the problem. T h e row generation methods deal only w i t h a small subset of the constraints at each step of the algorithm. A l t h o u g h the row generation methods are probably the most practical way to solve the general network synthesis problem, it is possible that for some instance of the problem, like a l l simplex type methods, the number of steps required to solve the problem w i l l be too large (exponential). T h a t is, the number of computational operations cannot be bounded by a p o l y n o m i a l function of the size of the input data, where the input size is roughly the logarithm to the base 2 of the number of nodes, all the requirement values, and all the cost values; see Garey and Johnson [55] for the complexity issues. However, B l a n d , Goldfarb, and T o d d [20] proved that despite the large number of constraints, the ellipsoid method may, in theory, be applied to solve the network synthesis problem in p o l y n o m i a l number of operations. Nevertheless, no practical implementation of the ellipsoid method is available to date. A n a t u r a l application of the network synthesis problem is in communication network design. In many cases, for example in a 'private telecommunication network', see e.g., B e l l - N o r t h e r n Research [12], it is desirable to have known m i n i m u m capacities between pairs of nodes or users. However, it is likely that, at any point in time, more than two pairs of users may want to communicate. T h i s may not be possible, because some calls may be 'blocked' by others. Therefore, it is also desirable for each pair of users to have an upper limit on the probability of being blocked. T h e simultaneous and the nonsimultaneous network synthesis problems are two special cases of the private telecommunication network design, when blocking is, respectively, never and always allowed. A n o t h e r application of the network synthesis problem is in those communication and transportation network design where reliability (i.e., connectivity) of the network is important, see e.g., [144,156], and for a survey, see [32]. A failure can occur i n the nodes a n d / o r i n the edges. Here, every pair of nodes is required to have a known degree of connectivity. T h e nonsimultaneous network synthesis problem is a special case of survivable network design, i n which the requirements can be thought of as the required connectivities. Finally, the network synthesis problem is related to some combinatorial o p t i m i z a t i o n problems such as the Steiner problems, see e.g., [28,40,122,156,159]. Formally, in the network synthesis problems, see G o m o r y and H u [58,59,60], we need to design, at a m i n i m u m cost, an undirected network w i t h n nodes, which satisfies 3 k n o w n requirements, i.e., lower bounds on m a x i m u m flow, between every pair of nodes. We will refer to the network to be designed as the solution network. T h e data for any instance of this problem consists of a positive integer n and two lists of n' = n(n — 1)/2 nonnegative integers: d — {dij) and r = {Uj), 1 < i < j < n. nodes by N = { l , . . . , n } , for each pair of nodes {i,j} b u i l d i n g one unit capacity on edge and Denoting the set of Q N, i < j, d^ is the cost of is the requirement between i and j. T h r o u g h o u t the thesis, we may allow costs and requirements to be zero or infinity. We define the n'-vector b = (bij) to be the vector of edge capacities to be determined, i.e., 6 represents the capacity, to be constructed, of edge tJ j > i. In the nonsimultaneous network synthesis problem, the network must have sufficient capacity to accommodate a requirement of r,j units between nodes i and j, j > i, when i and j act as the unique source-sink pair, whereas, in the simultaneous network synthesis problem, every pair of nodes can simultaneously act as the source-sink pair. T h e cost of building a capacity bij on edge (i,j) is d,j6,'ji and the objective is to provide sufficient capacity on edges to meet all n' requirements at m i n i m u m total cost d • b — Y^i<i<j< d>ijbij. We note that n the decision variables 6 = (6 ) are allowed to assume noninteger nonnegative values. tJ A n interesting generalization of the nonsimultaneous network synthesis problem is derived when only a proper subset T of the node set N have positive requirements from each other. We observe that the nodes in N\T cannot simply be eliminated, since it is conceivable that all o p t i m a l solutions to this network synthesis problem would use some nodes in N\T as intermediate points. We call the nonsimultaneous network synthesis p r o b l e m w i t h n nodes and t = \T\ < n demand nodes the Steiner network synthesis problem. T h e Steiner network synthesis p r o b l e m is a proper generalization of the network synthesis problem, since for T = N the two are equivalent. A cost allocation problem which is associated w i t h the network synthesis problem would naturally arise, if we assume that the various nodes in the network represent communities or different users. Indeed, in this case, we need to find a fair method for allocating the construction cost among the different users. T h i s allocation method must be perceived by the users to be fair, since, otherwise, they w i l l not support the implementation of an o p t i m a l solution which minimizes the overall construction cost. The thesis consists of four chapters. After an introductory chapter, we analyze, in C h a p t e r 2, the cost allocation problems arising i n the equal cost nonsimultaneous net- 4 work synthesis problem and the simultaneous network synthesis problem, while Chapters 3 and 4 are devoted to the Steiner network synthesis problem. M o r e specifically, C h a p t e r 3 is concerned w i t h a simplifying transformation, while i n Chapter 4, we present the case when the solution network has to be embedded i n (i.e., restricted to) some special graphs. For the rest of this introductory chapter, we provide, in Section 1.2, a brief survey of the cost allocation problems and some necessary preliminaries from game theory, while in Section 1.3, we formally present a formulation of the Steiner network synthesis problem and discuss related computational issues. 1.2 Cost Allocation and Introduction to Cooperative Game Theory In many cases, the nodes of the network to be designed represent users or communities w i t h conflicting interests, who may find it advantageous to cooperate a n d b u i l d the network. Moreover, the total construction cost of the network has to be fully financed by the users. T h e question arising here is how to allocate this construction cost among the users or nodes in a 'fair' way. We w i l l use cooperative game theory to answer this question. Before discussing the game-theoretic approach, we need t o present the concepts of a cooperative game, the core, Shapley value and the nucleolus. For the basic game theory notation and definitions, see [101,118,155]. Let N — { 1 , 2 , . . . , n } , n > 2, be a finite set of players, and let c: 2 N 0, be a characteristic to as coalitions. function function —> 9t, w i t h c(0) = defined on all the nonempty subsets S C JV, referred The pair (JV; c) is called a (cost) cooperative game in characteristic form (see V o n N e u m a n n and Morgenstern [155]), or for short a game. If for all T C U C N\{i}, i € N, we have c{U U {*"}) - c{U) < c{T U {i}) - c{T), then (JV;c) is called a concave game; see Shapley [132]. For a vector x £ 3?" and for a subset S C JV, let x(S) x(N) = c(N), = Yljes Xj. If x € 9t n satisfies then x will be referred to as a cost allocation vector. The core C[(JV;c)], see e.g., Gillies [57], of a (cost) game (JV;c) is the set of a l l cost allocation vectors x such that x(S) < c(S), for all S C JV. We observe that the core consists of all cost allocation vectors which provide no incentive for any coalition to split from the rest of the players and act alone. 5 L e t 7r be a permutation of N = { 1 , 2 , . . . , r e } , and let II be the set of all such permutations. For h £ N, let Sh(n) be the set of elements of 7r to the left of (preceding) h i n 7T. Shapley value, see [131], is a function, uniquely satisfying a compelling set of axioms, which assigns to each cooperative game (N;c) a vector (f>(c) = ( ^ ( c ) ) € 3?" given by Mc) = ^E{<S (^U{h})-c(S (n))). h n h - wen T h u s , the Shapley value is an apriori expected value to a player for j o i n i n g a game [131]. In general, the Shapley value is not contained in the core of the associated game. G i v e n a game [N;c) and a cost allocation vector y, form a vector 6(y) e 9 J " , 2 and let its components be the values c(S) — y(S), S ^ 0, S C TV. N e x t , arrange the components of 6(y) i n a nondecreasing order, i.e., h > g the s y m b o l nucleolus denote the lexicographic order. of (N;c), - 2 9h{y) > 0 (y). g Let T h e cost allocation vector u is the see Schmeidler [130], if 0(v) >z 6(y) for all cost allocation vectors y. T h e nucleolus is consistent w i t h the m a x i m i n criterion of Rawls [123], which advocates m a x i m i z i n g the m i n i m u m benefit obtained by any i n d i v i d u a l . In contrast w i t h Shapley value, the nucleolus can easily be shown, see e.g., [130], to be contained in the core. 'Fairness' is vague and hard-to-define. In the cost allocation literature, the Shapley value and the nucleolus are often taken as fair allocations. T h e cost allocation problem, in general, has attracted a fair amount of attention. We w i l l first present a brief survey of cost allocation research which are conceptually similar to C h a p t e r 2 of the thesis, i.e., they arise naturally i n mathematical programming problems. For a survey of cost allocation methods in general, see Y o u n g [162], and for a survey of cost allocation problems arising from mathematical programming problems, see D . G r a n o t and F . Granot [64]. In what follows, we have also included some revenue allocation problems, since there is no essential difference between revenue and cost allocation. T h e assignment game, introduced by Shapley and Shubik [133] (see also Gale and Shapley [52]), considers a set N\ of buyers and a set i V of sellers i n a market in which 2 only bilateral trading between one buyer and one seller is permitted. If a deal is struck between buyer i and seller j, the total joint benefit to them is denoted by u,j. L e t TV = Ni U JV~2, and let v(S) denote the m a x i m u m benefit that the members of a coalition 6 S C N can generate. T h u s , v{S) = max{ S n JV , 2 Y^jesnN ij x 2 E.esnN, E j e snN : 2 < 1, J £ Eiesruv, < 1, i £ S n J V ] , x,j (E {0,1} }, where x - = 1 if buyer i and seller j tJ strike a deal, x,j = 0 otherwise. T h e n , the revenue game (N;v) is called the assignment game. The core of the assignment game coincides w i t h the set of optimal dual solutions associated w i t h the corresponding assignment problem. For further research on the assignment game, see e.g., [63,82,120]. The linear production game, introduced by Owen [117], arises from a linear prog r a m m i n g problem when the resources are owned by individuals w i t h conflicting interests. Individual i, of the set of individuals JV, possesses b\ units of the resource k, k = 1,... ,m. T h e m different resources are used as input factors to produce p different final commodities. F i n a l commodity j is priced at Cj dollars per unit, and the production function is assumed to be linear, w i t h a technology matrix A £ 3ft . Further, it mxp is assumed that for any coalition S C N, b (S) k production game is the pair (N;v), where v(S) = Eies^' & = l,...,m. = max{ cx : Ax < b(S), T h e linear x > 0 } is the revenue to S C JV. If y = (y ) is an optimal dual solution for the linear programming ask sociated w i t h v(N), then Owen [117] showed that the revenue allocation u, = E£Li yk°\ is always in the core of the linear production game. For further research on the linear production game, see [47,125,129]. Network flow games arise i n network flow problems in which the edges of the network are owned by different individuals. Let the capacity of edge k be <i , and let the resource fc vector of i n d i v i d u a l i be b' = (b' ), b' = d k k k if i controls k, b\ = 0 otherwise. let Xk denote the amount of flow through edge k, and let x = (x ). k Further, It is well known that the network flow problem can be solved as a linear programme. T h u s , the network flow games are special cases of the linear production game, where the technology m a t r i x A reflects the capacity constraints 0 < x < d and the conservation of flow constraints Ax — 0. If edge capacities are all one unit, then a l l the points in the core of the network flow game can be derived from optimal dual solutions corresponding to the capacity constraints, see [63]. For further research on the network flow games, see [63,80,81,129]. L o c a t i o n games arise when a group of users D — { p i , P 2 • • • ,Pm} find it advantageous 5 to cooperate and b u i l d a number of facilities in some candidate sites C = { q ± , q , • • •, 2 T h e cost of b u i l d i n g a facility in the location qj is Wj > 0, which is independent of the other constructions. Let w(S) be the m i n i m u m construction cost of building sufficient 7 number of facilities for the users in S, such that for each user p, G S, there is at least one facility w i t h i n an r, kilometer radius of p^. T h e location game is represented by the pair (D;w). Let the m a t r i x A € * R if qj is w i t h i n r, kilometer radius of p , WjVj be such that its i-j'th component Aij = 1 = 0 otherwise. T h e n the location problem t can be formulated as min{ X ^ - i mxfc '• Ay > 1, yj 6 {0,1} }, where y — (yj), y_, = 1 if a facility is open in the site qj, yj — 0 otherwise. T a m i r (147] studied the case when the users, the facilities, and the travel routes can be embedded on a tree network. In this special case, T a m i r [147,148] showed that the location game is a special case of the linear p r o d u c t i o n game, and that the core of the location game coincides w i t h the set of o p t i m a l dual solutions. Spanning tree games, which were motivated by Claus and K l e i t m a n ' s [34] cost allocation analysis in a tree, were first introduced by Claus and D . G r a n o t [33], B i r d [19], and G r a n o t and H u b e r m a n [67]. Here, a set of communities N = {1,2,... ,n} desire to be connected, v i a a tree network, to a central supplier, denoted by 0. T h e cost of connecting i and j , i,j 6 N U {0}, is the number Cij > 0, independent of other factors. For each 5CJV, let Ts = [S U { O } , ^ ) denote a m i n i m u m cost spanning tree connecting every community in S to 0, where E$ is the edges of the tree. Further, let {S) C X)(i,j)eE.y t'r = c T h e n , the pair (JV;c) represent the m i n i m u m cost spanning tree ( M . C . S . T . ) game. A natural application of the M . C . S . T . game is in cost allocation in a cablevision network. G r a n o t and H u b e r m a n [67] have shown, beside other things, that if T N = (TV U { O } , ^ ) is an optimal M . C . S . T . , and if Xj is the cost of the unique edge in Tj^ incident to node j and on the unique p a t h between j and the central supplier 0, then (x ,x , 1 2 •.. ,x ) n is in the core of the M . C . S . T . game. For further research on the M . C . S . T . games, see [61,62,65,68,107]. T w o special cases of the spanning tree games are the airport game and the tree network game. T h e airport game, first studied by T h o m p s o n [151] and later by, for example, L i t t l e c h i l d and Owen [91], L i t t l e c h i l d [89], L i t t l e c h i l d and T h o m p s o n [93], and D u b e y [43], is concerned w i t h the fair allocation of the construction cost of an airport runway among the aircrafts which use i t . T h e kth smallest aircraft type requires a runway whose construction cost is c k > Ck-\, k = 1,2, . . . , n , c 0 = 0. Further, c(S) = m a x { c : S n TV*. ^ 0 }, S C TV. The nucleolus of airport game can be computed k in 0 ( n ) , see [89]. The Shapley value <f> — (<^»,) of the airport game is explicitly given by 2 8 <f>i = </>,_! + (c,- — c , _ i ) / Y!k=i ki m where is the number of landings of type k aircrafts, and cj>o — 0. The tree network game, studied by Megiddo [107], is b o t h a direct generalization of the airport game, where runways are allowed to assume tree network shapes, and a special case of the M . C . S . T . game. T h e nucleolus of the tree network game can be computed in O(rc-logn), see G a l i l [53]. T h e Shapley value of the tree network game can be computed as in the airport game, i.e., the cost of each segment of the runway is divided equally among all the users of that segment. The generalized linear production game, introduced by D . G r a n o t [62], relaxes the additivity constraint b (S) k = Y.ies°\^ ^ ~ 1,2, . . . , m , in the linear production game. D . G r a n o t [62] considers each resource k separately, and introduces the resource games (N;b ), k k = 1 , 2 , . . . , ra. A sufficient condition for the generalized linear production game to have a nonempty core is that every resource game has a nonempty core [62]. Consequently, it was shown in [62] that many node controlled network games, e.g., M . C . S . T . games, M i n i m u m Cost Directed Spanning Tree games, node controlled network flow games and more, have nonempty cores. Nonlinear programming games were first introduced by Shapley and Shubik [133,135] in the form of market games, where n traders seek a fair and beneficial exchange of their initial endowments. Let UJ(XJ) be the utility to individual j of having a vector Xj of commodities, and let o be his initial endowment of the commodities. T h e n , for each ; coalition S C N = { l , 2,..., n}, let u(S) = max{ T,jes j{ j) '• iZjes j = T,jes j, u S }. T h e pair (N;u) nonempty, see [133]. represents the market game. x x a J£ T h e core of the market game is In fact, the core of a market game induced by any subset of traders is nonempty, and it was further shown in [133] that every cooperative game, for which the cores of all subgames induced by all subsets of players are nonempty, can be formulated as a market game. For other nonlinear programming games, see K a l a i and Zemel [81], and D u b e y and Shapley [44]. Non-atomic games, see e.g., A u m a n n and Shapley [5], extend the theory of cooperative games to games w i t h infinite number of players. Briefly, i n non-atomic games, (I, C) is a measurable space, where J is the set of players and C is the cr-field of measurable subsets (coalitions) of / . Further, v is a real-valued set function defined on C, w i t h t>(0) = 0. T h e pair (/; v) is called a non-atomic game. T h e Aumann-Shapley value, <^>, 9 of a non-atomic game satisfies a set of axioms similar to those satisfied by the Shapley value. L e t p, be a vector of non-atomic measures on (/, C ) , i.e., V S G C, Izx(S')| > 0 =>• there exists T C 5 , T G C w i t h 0 < |M(^)| < |A*(-S") | - L e t / be a continuously differentiable function on the range R of p, w i t h / ( 0 ) = 0 . T h e n , when R has dimension n, A u m a n n and Shapley [5] proved that T o motivate non-atomic games, we describe how it may be applied i n a production sett i n g , where n infinitely divisible commodities are produced. Suppose that f(p\, fa, • • •, p ) n is a cost function w i t h / ( 0 , 0 , . . . ,0) = 0, where the variable p k denotes the nonnega- tive quantity of c o m m o d i t y k = 1 , 2 , . . . , n produced. If the total quantities produced is ( ^ i ( / ) , ^ 2 ( ^ ) v i M n ( ^ ) ) , the Aumann-Shapley prices p — {Pk), k = 1,2, . . . , n , can be computed by p — J fJ-(tp, (I),tp, {I), • • • ,tp {I)) • dt. Thus, the Aumann-Shapley k 1 o 2 n f l k value 4> of a subset of commodities S is 4>{f o p)(S) = J2k=i ^kiS) • p , i.e., the quantik ties of different commodities i n S times their (Aumann-Shapley) prices. T w o notable applications of A u m a n n - S h a p l e y prices are i n telephone and transportation networks. B i l l e r a , H e a t h , and R a a n a n [17] studied the internal telephone billing rates levied, to offset the fixed rental costs of W A T S lines which connects Cornell University's campus telephone network to various geographic areas i n the U n i t e d States. E a c h W A T S line can be leased on either an unlimited-usage basis or a limited-usage basis, where each phone call above a certain quantity in a m o n t h would be charged an additional amount. T h e routing of phone calls is such that if the direct route for any call is not available, other secondary indirect routes would be used. Therefore, Billera, Heath, and Raanan argued that it is 'unfair' to charge a call according to the W A T S line it was actually channelled through, and to only overcharge the calls which occur late in a month after the quota level has been exceeded. Thus, B i l l e r a , H e a t h , and R a a n a n considered each phone call as a player, and since there were a large number of calls in a month, they used non-atomic game theory to formulate the problem. T h e A u m a n n - S h a p l e y prices have actually been used at Cornell university to determine the internal telephone billing rates since 1 9 7 8 . Samet, T a u m a n , a n d Zang [ 1 2 8 ] used the A u m a n n - S h a p l e y prices i n the transporta- 10 tion problem. T h e transportation problem is to route an economic good in a cheapest way from some suppliers to some demand points. T h e cost allocation problem is how to 'fairly' allocate the total transportation cost among the demand points. It is well known that the transportation problem can be formulated as a linear programme. However, Samet, Tauman, and Zang showed, by an example, that the optimal dual solutions in a transportation problem may generate 'unfair' cost allocations. Thus, Samet, T a u m a n , and Zang formulated the cost allocation problem as a non-atomic game, and used the Aumann-Shapley prices as a 'fair' cost allocation scheme. For further research advocating the use of Aumann-Shapley value, especially i n production, see [16,18,108,109,110,127,161]. Next, we survey some other papers advocating the use of cooperative game theory for cost and revenue allocation. The first paper proposing the use of game theory concepts in cost allocation was by Shubik [139]. Shubik suggested Shapley value as a 'fair' cost allocation scheme. Some other research w h i c h suggested the use of the core and other game-theoretic solutions, especially in pricing policies of regulated monopolies, are reported in [48,136,137,164]. The research i n [27,30,79,88,95,96,126,142,154] advocates the use of game theory and Shapley value i n allocating joint costs, especially in public investments and in decentralized companies. A u m a n n and Maschler [4], see also O ' N e i l l [114], considered three bankrupcy problems mentioned in the T a l m u d , for which, for quite a while, a unified explanation was not available. A u m a n n and Maschler used cooperative game theory to provide the unifying ground, and showed that the solutions to these problems prescribed by the T a l m u d are precisely the nucleoli of the corresponding cooperative games. Joint cost allocation arises often in multipurpose reservoir development. Suppose that a d a m on a river is planned to serve many different regional interests, e.g., flood control, hydro-electric power, navigation, irrigation, and municipal and industrial water supply. T h e d a m can be built to different heights, depending on which purposes it w i l l serve. T h e cost function usually exhibits decreasing marginal cost upto a critical height of the d a m , above which marginal cost w i l l be increasing due to technological limitations. T h e water resource planning problem is how to allocate the costs among the different purposes. T h i s problem dates back to the creation of the Tennessee Valley A u t h o r i t y ( T V A ) in the 1930's, see Ransmeier [121], Parker [119], and Straffm and 11 Heaney [145]. T h e joint costs, based on the actual T V A data [121], for the three purposes navigation (n), flood control (f), and power (p) in thousands of dollars are c({n}) = 163,520, c ( { / } ) = 140,826, c({p}) = 250,096, c ( { n , / » = 301,607, c({n,p}) - 378,821, c ( { / , p } ) = 367,370, and c ( { n , / , p } ) = 412,584. A l t h o u g h the T V A asserted that its cost allocation was not based on any single mathematical formula, according to Ransmeier [121], the T V A used a method which has developed into the separable costs remaining benefits method ( S C R B ) . T h i s method has been used for cost allocation in most other multipurpose reservoir projects since 1930's, see e.g., [56,75,94,99,113,163]. For an exception, see Suzuki and Nakayama [146] who suggested using the nucleolus of the water resource planning game. A related method (r-value) is described i n Tijs and Driessen [152]. T h e S C R B m e t h o d can be described as follows. T h e Separable Cost of a purpose i G N is its m a r g i n a l cost s,- = c(N) — c(N\{i}). i (from cooperating) is vector x = (Xi), Xi - s + { The R e m a i n i n g benefit to — c({i}) — S j . T h e S C R B method assigns the cost allocation —[ (JV) - £ C e i V Sj}. For the T V A data above, the S C R B method prescribes Xn = $117,476 for navigation, Xf = $99,157 for flood control, and X = $195,951 for power, out of a total cost of $412,584. p For cost and revenue allocation methods suggested in the economic literature (e.g., the Ramsey prices, marginal cost), see [11,70]. For economic pricing in telecommunication networks, see [3,6,25,31,38,90,111,124,138,143,149]. For economics and finance applications i n cost allocation in airport management, see [9,29,87]. For other methods of cost allocation (e.g., m i n i m u m resource allocation, activity level, net realizable value, independent cost proportional) suggested in accounting literature, see [7,8,10,21,22,25,26,35,46,54,71,72,73,78,83,86,98,112,150,157]. For some accounting reasons for allocating j o i n t costs, see [8,165]. For surveys of corporate allocation practices, see [51,104]. M o t i v a t e d by the numerous papers cited above, we employ in this thesis the cooperative game methodology to analyze cost allocation issues which arise i n the simultaneous and the nonsimultaneous network synthesis problem. Conceptually, our analysis is done as follows: • We w i l l formulate the cost allocation problems as cooperative games in characteristic function form, and prove that they are concave games. 12 • T h e concavity of the games implies that the cores exist, and that the Shapley value and the nucleolus are contained in the core. • For the equal cost nonsimultaneous network synthesis game, we w i l l present an irredundant representation of the core, w h i c h we then employ to derive an explicit closed form expression for the nucleolus of the game when the requirement structure is a spanning tree. Further, we will develop a decomposition of the game i n a special case, w h i c h we later use to efficiently compute the Shapley value of the game when the requirement structure is a tree. T h i s decomposition w i l l also be used to decompose the core and the nucleolus of the game i n the special case. • For the simultaneous network synthesis game, we w i l l also present an irredundant representation of the core, which we w i l l employ to derive an explicit closed form expression for the nucleolus of the game. Further, we will decompose the core of the game i n the special case, and finally prove that Shapley value and the nucleolus of this game coincide. Throughout the thesis, we attempt to develop efficient computation schemes for both the nucleolus and the Shapley value, since, in general, their computation requires a large, in fact exponential, number of operations. 1.3 The Steiner Network Synthesis Problem In Chapters 3 and 4, we are concerned w i t h the Steiner network synthesis problem, with particular emphasis on simplifying its computation in some special cases, not considered before. The linear programming ( L P ) formulation of the nonsimultaneous network synthesis problem, see G o m o r y and H u [58,59,60], is as follows: Minimize E ij°ij c l<i<j<n Subject T o £ b tj > r bij > 0 Q 0 ^ Q c N (i'.j)e(Q.w\G) l<t<J<n 1 < i < j < n, 13 where (Q, N\Q) and r Q is the set of edges w i t h one endpoint i n Q C N and the other i n JV\ Q, = m a x { r j : i G Q, j G N\Q { }. Since, in general, every constraint i n the above L P formulation is irredundant, see B l a n d , Goldfarb, and T o d d [20], the linear programming formulation presented above, in general, cannot be simplified any further. T h i s implies that, in general, to solve the network synthesis problem we need to solve an L P problem w i t h 2 ~ — 1 + n' inequalities. n ] However, for any given instance of the problem, many constraints are redundant. This redundancy generally depends on b o t h the requirement structure and the cost structure. T h u s , one is led to consider some special cases of the requirement structure structure. or the cost Recall that G o m o r y and H u [58] considered the special cost structure when all unit construction costs are equal. F i r s t , as a special case of the requirement structure, we w i l l consider the case when the requirement structure is sparse, because there are only a few demand nodes T and the rest are just intermediate nodes. We further simplify the p r o b l e m by assuming t h a t the positive requirements between pairs of nodes in T are equal. T h i s case, i.e., the equal positive requirements sparse requirement structure case w i l l be considered in C h a p t e r 3. For this case, we w i l l present a transformation to simplify the computations. E x p l i c i t l y , we transform the equal positive requirements sparse requirement structure Steiner network synthesis problem into a smaller network synthesis problem w i t h nodeset T and w i t h distances equal to the shortest (cheapest) distances in the original problem. We then solve the smaller network synthesis problem, possibly using a linear programming a l g o r i t h m , and we transform an o p t i m a l solution subnetwork back to the original problem. We will prove, using the linear programming duality, that the transformed solution is indeed an o p t i m a l solution to the original problem. Secondly, as to special cases of the cost structure, we first note that the case of a sparse cost structure, i.e., when some unit costs are zero, is t r i v i a l , since i f dij = 0, then we can take bij to be as large as necessary, thus enabling us to contract edge on one endpoint, say i, and to proceed w i t h a smaller problem where for each requirement r jk, k there is a new requirement J-,-* of the same magnitude. However, the case when some unit costs are very large (infinity) is interesting. T h i s effectively implies t h a t the edges w i t h a very large unit cost cannot be constructed. Equivalently, the solution network is being restricted to some special graphs, since if dij is infinity then 14 we can remove variable 6,^ from the linear programming formulation. We refer to the linear programming formulation remaining after all redundant variables are removed as the reduced linear program. Further, by an extreme solution, when the solution network has to be embedded in (i.e., restricted to) some special graphs, we mean an extreme solution to the feasible set of the reduced linear program. We note that, in this case, we do not impose any restrictions on the requirement structure. Specifically, we will consider, in Chapter 4, the special cases when the solution network has to be embedded in trees, rings (cycles), series-parallel graphs, or M parallel a 2 n d M - f r e e graphs. A series- 3 graph can be obtained by a sequence of node insertion and edge duplication from an edge, where node insertion is the operation of converting an edge (u, v) into a p a t h (u,w), (w,v) by inserting a node w in (u,v), and edge duplication is the operation of adding one more edge between u and v. T h u s , we are interested in 'edge' or 'two t e r m i n a l ' series-parallel graphs which are also considered i n , e.g., [14,36,74,153]. A M and M -free s graph is a graph which does not have M nor M 2 for a display of M 2 and M 3 as a m i n o r (see Figure 3.4 graphs), where a graph H is a minor of a graph G, if G can be reduced to i f by a sequence of edge deletion, contraction 3 2 isolated-node deletion, (edge contraction is the operation of shrinking an edge (u,v) its endpoints, say u, and replacing each edge (w,v), w / and edge onto one of u , by an edge (u,v)). We note that rings (cycles) are special cases of series-parallel graphs, and we will prove, in Section 4.3, that series-parallel graphs are special cases of M 2 a n d M - f r e e graphs. 3 Furthermore, all extreme solutions to the Steiner network synthesis problem, when the solution network is restricted to the above special graphs, happen to have integer or half-integer values. T h i s fact enables us to solve the Steiner network synthesis problem in the above special cases by some combinatorial algorithms. Moreover, we will show, by E x a m p l e 4.7 in Section 4.3 that in larger classes of graphs, extreme solutions may have arbitrary fractional values, which would make the derivation of an o p t i m a l solution more complicated. E v e n though, in this thesis, we consider only the special cases of embedding the solution to the Steiner network synthesis problem in trees, rings, series-parallel graphs, or M and M - f r e e graphs, there is a lot of scope for application. To demonstrate this, we briefly describe the paper by Ratliff and Rosenthal [122]. In [122] entitled 2 3 ' O r d e r - P i c k i n g in a Rectangular Warehouse: A Solvable Case of the Travelling Salesman 15 9 6 3 6 6 6 15 6 Figure 1.1: A Rectangular Warehouse, and Some Items (the thicklined nodes) to be Picked up. P r o b l e m ' , Ratliff and Rosenthal described a rectangular warehouse which is displayed in F i g u r e 1.1. It can easily be seen that this graph is series-parallel. T h e horizontal edges represent cross-overs, each 2 meters long, and the vertical paths represent aisles, each 15 meters long. T h e thicklined nodes on the vertical paths, except the one on the 3rd vertical path from the right, represent items which need to be picked u p at a point in time. T h e position of each item can be discerned by the numbers, distances in meters, on the graph, and each i t e m is located on either side of an aisle. T h e current position of the forklift is represented by the thicklined node on the 3rd vertical path from the right. T h e forklift is supposed to collect all the ordered items and return to its starting point w i t h the ordered items. T o save time and costs, it is desirable that the total distance travelled by the forklift is m i n i m i z e d . It is clear that the movement of the forklift describes a Steiner tour, i.e., a cycle v i s i t i n g each demand node at least once. T h u s , Ratliff and Rosenthal [122] presented an algorithm to find the shortest Steiner tour in the graph, and made it available in the form of a personal computer software for commercial use. We observe that the Steiner network synthesis problem w i t h requirements equal to 2 can be thought of as a generalization of the Steiner tour problem. Moreover, beside the above application, the Steiner network synthesis problem can also be used to design o p t i m a l c o m m u n i c a t i o n and electrical networks which should satisfy some connectivity requirements. For example, suppose that the graph i n Figure 1.1 represents a new 16 rectangular office floor and that the nodes represent rooms which require a telephone. Furthermore, suppose that the network connecting these telephones to each other and to a central switch board is stipulated to be line-failure immune, i.e., the network should be operational even after one transmission line failure. T h e n , the p r o b l e m of designing a m i n i m u m length line-failure immune network is exactly the Steiner network synthesis problem w i t h requirements equal to 2, considered i n Section 4.1.2. Chapter 2 COST A L L O C A T I O N IN T H E NETWORK SYNTHESIS PROBLEM 2.1 2.1.1 Introduction, Notation and Preliminaries Introduction A communication network can be thought of as a set of nodes connected by edges. A t the nodes, calls can be originated, terminated, or switched. Conceptually, an edge consists of a bundle of circuits, each of which can carry one call. T h e main problem in c o m m u n i c a t i o n network design is to determine which pair of nodes to connect w i t h edges and how many circuits to allocate to each edge, see Bell-Northern Research [12]. We assume that the undirected communication network to be constructed is of m i n i m u m cost and the edge capacities are large enough to satisfy requirements for every pair of users. A user is associated w i t h a node in which calls originate or terminate, and a requirement between a pair of users at time T can be thought of as a m i n i m u m number of possible calls between the pair at time r . If the requirements are independent of time and have to be satisfied simultaneously for a l l pairs of users, then the problem of finding a m i n i m u m cost network is called the simultaneous network synthesis problem [60]. If time is broken up into distinct periods, and during any one period the requirement between only one pair of users (which is taken as a fixed constant during the period) is to be satisfied while the other requirements are considered as zero during the period (i.e., the requirements are completely time-shared), the problem is called the 17 nonsimultaneous 18 network synthesis problem [59,158]. T h e input data i n both cases consist of integers Tij, rij = rji > 0, which are the requirements between users i and j , and numbers d uv = d vu d, uv > 0, which are the linear construction cost of installing a unit capacity (one circuit) between nodes u and v. Throughout the thesis, we may allow the requirements and the costs to be zero or infinity. G o m o r y and H u [59], also see W i n g and Chien [158], formulated the nonsimultaneous network synthesis problem as a linear programming p r o b l e m w i t h a large number of constraints, and devised a row generation technique for solving it. Furthermore, in [58] (see also [158]), G o m o r y and H u provided a very efficient m e t h o d for solving the equal-cost nonsimultaneous network synthesis problem, i.e., when d uv — d > i for every two pairs of nodes {u,v} v u and {u , v'}. O f course, we can 1 assume, w i t h o u t loss of generality, that in the equal-cost case, d of nodes {u,v}. av = 1 for every pair T h e solution to the simultaneous network synthesis problem can also be found very efficiently, see G o m o r y and H u [60]. Specifically, starting from a zero capacity network, it is only necessary to find a shortest (cheapest) p a t h between every pair of nodes (users) i and j and then give to each edge on this path an additional capacity r . i ; Our objective i n Chapter 2 of this thesis is to analyze cost allocation problems w h i c h naturally arise in the above network design problems, namely, how to allocate the cost of constructing the c o m m u n i c a t i o n network among the various users. This is a crucial p r o b l e m , since if any group of users feels that it is being over-charged, it may secede and construct its own separate communication network. This would, most probably, lead to inefficiency and an overall allocation of cost which is not Pareto o p t i m a l . We w i l l formulate these cost allocation problems as cooperative games, referred to as the simultaneous and the nonsimultaneous network synthesis games, and evaluate the possible use of various concepts of solution, introduced in cooperative game theory, as candidates for cost allocation in the network synthesis problems. 2.1.2 Game Theory Notation and Preliminaries A s it should be apparent by now, in Chapter 2 we deal w i t h cost rather than revenue allocation issues which are usually associated w i t h cooperative games. Therefore, traditional inequalities in game theory should be reversed. T h e s y m b o l '0' w i l l denote the empty set, ' c ' denotes 'is properly (strictly) included i n ' , and ' C ' denotes 'is included 19 in (and may be identical to)'. Let JV = { l , 2 , . . . , n } , n > 2, be a finite set of players, w i t h c(0) = 0, be a characteristic to as coalitions. function function and let c:2 N —> 3?, defined on nonempty subsets of JV, referred T h e pair (JV;c) is called a (cost) cooperative game in characteristic form (see V o n N e u m a n n and Morgenstern [155]), or for short a game. It is assumed that all the strategic essence of the game is summarized i n the characteristic function. T h u s , games in characteristic function form are more abstract t h a n games in strategic form which actively utilize a lot more strategic information, see [155]. Originally, V o n N e u m a n n and Morgenstern assumed that c(5) and c(N\S) are the values determined from a zero-sum two-person game played by the two coalitions S and N\S. However, i n many situations, c(5) can be interpreted as the best the subset S can do as a coalition, assuming that the other players do not care. T h i s assumption is used throughout C h a p t e r 2. If the characteristic function c is subadditive, i.e., c(UL)T) < c(U) + c(T), U,T C N, U Pi T = 0, then the game (JV; c) is called proper, whereas if the characteristic function c is submodular, i.e., c(U U T ) + c(U D T) < c(U) + c(T), U,T C JV, or equivalently c{U U {i}) - c{U) < c{T U {.}) - c{T), T C U C N\{i}, i £ N, then the game [N;c) is called concave (see Shapley [132]). We observe that every concave game is proper. A game (JV; c) is decomposable, {Ni,..., Nh}, see e.g., Shapley [132], if for any partition of N, h > 2, and for every subset S C JV, J2c(SnN )=c(S). 9 9=1 For a vector x G 5?" and for a subset S C JV, let x(S) x(N) = J2jes jx If x G 9f" satisfies = c(JV), then x w i l l be referred to as a cost allocation vector or a pre-imputation. A cost allocation vector x satisfying z , < c({i}), i G JV, is called an imputation. The core C[(JV;c)] of a (cost) game (JV;c) is the set of all cost allocation vectors x such that x(S) < c(S), S C JV. T h e above inequalities are referred to as the 'stand-alone cost 20 tests' in some papers, see e.g., Y o u n g [162]. We observe that the core consists of all cost allocation vectors which provide no incentive for any coalition to split from the rest of the players and act alone. It can be shown that the above core inequalities are equivalent to the inequalities x(S) > c(N) -c(N\S), S C N (see e.g., [162]). The latter inequalities, referred to as the 'incremental cost tests', are based on 'equity', since they imply that S cannot be subsidized by N\S. In general, the core of a game may be empty, however, the core of a concave game is always nonempty, see Shapley [132]. Let 7r be a permutation of N = {1,2,... ,n}, and let II be the set of all permutations. For h 6 N, let Sh[w) be the set of elements of 7r to the left of (preceding) h in 7r. The Shapley value, see Shapley [131], is a function, uniquely satisfying a compelling set of axioms (briefly described below), which assigns to each cooperative game (TV; c) a vector <j>(c) = [<t> (c)) e ft" given by h ^ ) = k ( » ) u W ) - « ) ) ) A l t h o u g h , the Shapley value always exists, it may not, in general, be contained i n the core. For concave games, however, the Shapley value is always contained i n the core, and, in fact, coincides w i t h the core's center of gravity (see Shapley [132]). For a generalization of the Shapley value, when the players have different 'importance' weights, see [97,115,116,140]. The axioms Shapley value uniquely satisfies are (see Shapley [131]): B r e a k - E v e n : £ ^ (c) = ^AOf c f c S y m m e t r y : If for a pair of players p and q, and for all subsets 5 C N, S $ p,q, we have c(S U {p}) = c(S U {?}), then 4> {c) — cf> (c). p q D u m m y P l a y e r : If for a player p and for all subsets S c N, S j$ p, we have c ( 5 U {p}) = c{S), then <f) {c) = 0. p A d d i t i v i t y : If any three characteristic functions c, c', and c", defined on all subsets of N, satisfy c(S) + c'[S) = c"{S), S C TV, then 4> (c) + d> (c') = <j> { ") c h players h. h h f o r a 1 1 21 It can be shown, see e.g., Y o u n g [162], that the Shapley value is also monotone, i.e., an increase i n the cost of a particular coalition implies, ceteris paribus, no decrease in the allocation to any member of that coalition. T h i s is one of the major strengths of the Shapley value, especially when allocating joint costs in firms, see e.g., [18,70,139,161], because it charges a user more if the users's cost contribution increases. For a cost allocation vector x, let e x ( 5 , x, c) = c(S)—x(S) w i t h respect to x in a game (N;c). s (N, pq be the excess of coalition S For two players p and q, let x, c) = m i n { ex(S, x, c) : S C N, S 3 p, S 73 q }. T h e kernel for the set of imputations of a game (N; c), w i t h respect to g r a n d coalition, see Davis a n d M a s c h l e r [39], is the set of all imputations x such that either s (N,x, c) < pq s (N,x,c) or x qp q = c({q}), for all {p, q] C JV. T h e pre-kernel for the set of pre- i m p u t a t i o n s is the set of all pre-imputations x which satisfy s (N,x,c) pq {Pi<l} Q N. — s (N,x,c), qp For concave games, the kernel and the pre-kernel coincide, see [102,103]. T h e kernel always exists, see [39], and if the core is nonempty, the intersection of core a n d kernel is nonempty and possesses nice geometric properties, see M a s c h l e r , Peleg, a n d Shapley [103], which are useful in studying the nucleolus described next. G i v e n a game (N;c) and a cost allocation vector y, form a vector 6(y) and let its components take the values e x ( 5 , y,c), € 3f ' , 2 - 2 such that each component takes a value associated w i t h a distinct nonempty proper subset S C N. N e x t , arrange the components of 6(y) in a nondecreasing order, i.e., h > g => 6h{y) > Ogiu)- L e t the s y m b o l '>:' denote the lexicographic order. T h e cost allocation vector v is the of (N;c) if 6{u) > 6(y) for all cost allocation vectors y. nucleolus The nucleolus, which was introduced by Schmeidler [130], always exists and is contained in the kernel. W h e n the core is nonempty, the nucleolus is contained i n it. In fact, the nucleolus is the lexicographic center of the core, see [103]. For concave games, the kernel is unique, see Maschler, Peleg, and Shapley [102], i m p l y i n g that for this class of games, the nucleolus and the kernel coincide. Unfortunately, the nucleolus is not monotone, see M e g i d d o [105]. However, this is true for any other solution m e t h o d w h i c h yields a vector i n the (nonempty) core, see Y o u n g [160]. One positive characteristic of the nucleolus is that it is covariant, see e.g., [141,162], i.e., for any scalar a and vector j3 — {fih), and for any 22 h G TV, we have v (a • c + /?) = a • Vh{c) + For a variant of the nucleolus, where the h benefits are measured per capita, i.e., e x ( x , S , c ) = (c(S) — x ( 5 ) ) / | 5 | , see Grotte [69]. 2.1.3 Graph Theory Notation and Preliminaries T h r o u g h o u t this thesis, we w i l l only consider undirected simple graphs, i.e., undirected loopless graphs w i t h no m u l t i p l e edges (see e.g., [23,13] for basic graph theory notation). We denote a graph by G = (TV, E), where JV is the node set, and E is a set of unordered pairs of nodes i n TV, called the edge set of G. A network is a graph w i t h weights associated w i t h its edges. T h e networks induced by the solutions to the simultaneous and the nonsimultaneous network synthesis problems w i l l be refered to as solution and w i l l be denoted by G\ = (N,El) and G\ = (N,E$), networks respectively, where 6* (resp., u b ) is the capacity or weight associated w i t h edge (u,v) £ El (resp., El)'. T h e capacity 2 uv of a n edge is zero if and only if the edge does not exist. In Chapter 4, we w i l l consider some special cases when some edges do not exist, i n which case, for emphasis we will refer to Gl as the solution subnetwork. We will also need to represent the requirements as an undirected network G = (N,E ), T [i,j) referred to as the requirement r structure, where £ E if r,j > 0, and r j is the weight associated w i t h (i,j) G E . r t T A path or a walk from i\ to u i n a graph G — (N,E) is specified by a n alternating sequence of nodes a n d edges j = l,...,h, a n d (ij~i,ij) (ii, i ), i , 2 2 (&2> * 3 ) , • • • , G E, j' = 2 , . . . , h. {ih-i, H such that ij G TV, A simple path is a path w i t h distinct nodes. A cycle or a circuit is a path from a node to itself, i.e., i j = th- A simple is a cycle w i t h distinct nodes. A Hamiltonian cycle cycle is a simple cycle visiting all the nodes. A graph is connected if there is a p a th between every pair of its nodes. A graph H = (N{H),E{H)) is a subgraph of G = (TV,E), if N(H) C TV and E(H) C E. A graph is a forest if it contains no simple cycles as a subgraph. A forest is a spanning tree if it is connected and spans all the nodes. In C h a p t e r 2, we will assume that the requirement structure G is always connected, r since, otherwise, by their solution methods, the equal cost nonsimultaneous and the simultaneous network synthesis problem, and, by the definition of a decomposable game above, the induced games c a n be decomposed a n d analysed separately for each connected component. Furthermore, we will pay special attention to the case when the requirement structure is a spanning tree, because of the following lemma: 23 Figure 2.1: A Requirement Structure (left), and a M R S T in it (right). Lemma 2.1 (Gomory and H u [58]). imum requirement the requirement spanning For any requirement tree in it induces the same optimal structure for both the simultaneous structure, every max- solution networks as and the nonsimultaneous network synthesis problem. • Figure 2.1 above displays a requirement structure and a m a x i m u m requirement spanning tree ( M R S T ) in it. Essentially, G o m o r y and Hu's algorithm [58] to solve the equal cost nonsimultaneous network synthesis problem is as follows. Given a requirement structure and equal unit costs, first find a M R S T i n the requirement structure, then decompose the M R S T into a m i n i m u m number of equal-requirement subtrees, next solve the problem for each equal-requirement subtree to get o p t i m a l solution subnetworks, and finally superimpose the derived subnetworks. E x a m p l e 2.1 below illustrates these steps: Example 2.1. Consider the requirement structure shown on the left of Figure 2.1, where the requirements are displayed on the edges, and the unit costs are equal to one. A M R S T in this requirement structure is shown on the right of Figure 2.1, and the equalrequirement subtrees it decomposes into are displayed in Figure 2.2. O p t i m a l solution subnetworks, one H a m i l t o n i a n cycle of half the requirement's capacity for each equalrequirement subtree, are displayed in Figure 2.3. Finally, the superimposed o p t i m a l solution subnetwork is shown in Figure 2.4. We observe, from Figure 2.4, that the m i n i m u m total cost = m i n i m u m total capacity = 19, and, from Figure 2.1, that the sum of the m a x i m u m requirement of each node is 9 + 6 + 9 + 7 + 7 = 38, twice the m i n i m u m total cost. Indeed, this is true for any instance of the equal cost nonsimultaneous network synthesis problem, and easily follows from G o m o r y and H u ' s a l g o r i t h m [58]. • 24 Figure 2.2: The Equal-Requirement Subtrees. Figure 2.3: O p t i m a l Solution Subnetworks for the Equal-Requirement Subtrees. Figure 2.4: T h e Superimposed O p t i m a l Solution Subnetwork. 25 The remainder of this section consists of some notation and definitions, most of w h i c h , except the last paragraph, are used i n C h a p t e r 2. L e t a requirement structure G — (N,E ) hj S S, there exists a p a t h between i and j i n G which uses only the nodes in S. In r T be given. A subset S C TV is connected i n G if for every pair of nodes r r connection w i t h the nonsimultaneous network synthesis game, some special subsets of TV w i l l be significant, namely, the subsets S which are not connected i n G , but will r be connected if some isolated nodes were to be included in S, where some nodes are isolated if they have no requirements from each other. T h e resulting enlarged subset, denoted by S, will be referred to as the closure of S w i t h respect to G . r For example, in Figure 2.6, for S = {2,3}, we have S = {1,2,3}. Formally, S = S U {k £ N\S : [i,k),{j,k) A subset S is said to be closure-connected £ E, r i,j £ S}. in G if S is disconnected, but its closure S is r connected. For a disconnected subset S C TV, let {Ri, R ,..., Rh} denote a partition of S 2 into nonempty connected subsets. We say that {R\,..., Rh} is a minimal partition of S if it has a m i n i m u m number of components, i.e., h is m i n i m u m , among all such partitions of S. For example, in the requirement structure shown in Figure 2.7, S = {1,2,5,6,8} is disconnected, and {Ri,R }, R 2 G i v e n an edge x = {1,2}, R 2 = {5,6,8}, is a m i n i m a l p a r t i t i o n of S. £ E , let TV, (resp., TV,-) denote the collection of nodes, including r node i (resp., j), from which there is a path i n G to node i (resp., j) that does not pass r through node j (resp., i). For example, in Figure 2.7, for edge (4,5), TV = {1,2,3,4} 4 and TV = {5,6,7,8}. We observe that, i n general, TVjHTVj ^ 0. However, if TV.-nTV,- = 0, 5 then is a bridge, i.e., the removal of w i l l decompose G into two connected r components. If TVj n TV, = 0 for every edge £ E , then G is a spanning tree. We r r w i l l denote by M , (resp., Mj) the set of nodes in TV, (resp., TV,) which are adjacent to i (resp., j) in G , where two nodes i and j are adjacent r F i g u r e 2.7, for edge (4,5) M 4 = {2} and M 5 if (i,j) £ Er F o r example, in = {6,7,8}. Throughout the thesis, we will find it convenient to represent the nodes TV and the costs d = (dij) by a network G = (N,E), and the weight (length) of any edge (i,j) where E 3 (i,j)' if the unit cost < oo, is equal to d^. In fact, when the requirement structure can be determined from the context, e.g., when all the requirements are equal, 26 we w i l l use the terminology of the Steiner network synthesis problem i n network G. F u r t h e r , for each pair of nodes i,j £ JV, we let d'^ denote the length (cost) of a shortest (cheapest) p a t h between nodes i and j i n G. 2.2 Concavity of the Network Synthesis Games In this section, we formally introduce the simultaneous and the nonsimultaneous network synthesis games. We w i l l prove that the former and, when all unit costs are equal, the latter are concave games. For each nonempty subset 5 C JV, we let e ^ S ) (resp., c (S)) be the m i n i m u m cost 2 incurred by coalition S if its members construct a 'separate' o p t i m a l solution network that satisfies simultaneously (resp., nonsimultaneously) their communication requirements. It seems plausible t o let these c o m m u n i c a t i o n requirements be r , i £ S, j £ JV. t J T h i s ascertains that members of S w i l l acquire their requirements regardless of the action taken b y the other users. We define ci(0) = c (0) = 0, a n d refer to the pair 2 (JV;cj) (resp., (JV;c2)), w i t h the characteristic function c\ (resp., c ) defined above, as 2 the simultaneous (resp., the nonsimultaneous) costs are equal (or d = 1, uv network synthesis game. W h e n all unit u,v £ JV), we o b t a i n the equal cost network synthesis games. Since, in C h a p t e r 2, we only analyse the equa7 cost case of the nonsimultaneous network synthesis game, we let (JV; c ) refer t o this game. 2 E x a m p l e 2.2. Consider the requirement structure G = ( J V , E ) , shown on the top r r left corner of Figure 2.5, where the requirements are shown on the edges and the unit costs are equal t o one. Let b^ (S) (resp., ^ ( S ) ) be the optimal capacity of edge (u,v) v in a separate o p t i m a l solution network which satisfies the requirements of coalition S simultaneously (resp., nonsimultaneously). It can be verified, using G o m o r y and Hu's a l g o r i t h m [58] outlined i n Subsection 2.1.3 above, that ^Ldl}) 1> = a n < ^ therefore c ({l}) 2 6f ({l}) 2 = 1, ^({l}) = 3, = 5. See Figure 2.5 for the solution networks, where each unit capacity is represented by a line. Similarly, &i ({2}) = 1, ^ ( { 2 } ) = 1, 2 b h(I )) 2 = 5 ' S C JV, b (S) 2 n a n d 3 therefore c ( { 2 » = 7. F i n a l l y , for every other nonempty subset 2 = 2, b\ {S) = 2, bj (S) 3 3 = 4, a n d therefore e [S) = 8. Furthermore, it 2 is easy t o verify, using G o m o r y and H u ' s a l g o r i t h m [60] outlined i n Subsection 2.1.1, that 6} ({1}) = 2, b\ ({l}) 2 3 = 4, 6 | « l » = 0, and therefore s ^({l}) = 6. Similarly, 27 F i g u r e 2.5: A Requirement Structure, and the O p t i m a l Solution Networks. 6} ({2}) = 2, b\ {{2}) = 0, b\ {{2}) = 6, and therefore 2 3 °> i s ( { 3 } ) = > 6 4 3 ft 2s({ }) = > 3 6 a n d Cl ( { 2 } ) = 8. A l s o , &} ({3» = 2 therefore ^ ( { 3 } ) = 10. Finally, for every other nonempty subset S C JV, 6j (S) = 2, 6} (S) = 4, b\ {S) = 6, and therefore ^ ( 5 ) = 12. 2 3 3 • We next prove that the equal cost nonsimultaneous and the simultaneous network synthesis games (JV;c ) and (N;c\) 2 are concave. F i r s t , in an undirected network G = (JV, JS), let w : E —* 3ft be a nonnegative weight function defined over the edges E, and + for every subset S C JV, define 6(S) = J2 m a x { w jk : k e N\S } and L e m m a 2.2. £(•) and er(-) are submodular set functions on subsets of JV. 28 Proof. We first prove the submodularity of 6. L e t i G TV and T C U C N\{i}. T h e n , for every j i n T , max{ w : k G T V \ T } - max{ w jk < max{ u; iA: : k G N\[T U {i}) } jk : k G T V \ C / } - max{ w : k e N\(U U {i}) }. jk (2.1) Furthermore, by definition of 6(-) we have 6(T)-6(Tu{i}) = J2m&x{w :keN\T}- Y, jk >er max{ Wj :fcG T V \ ( T U {?}) } k jeTu{t} < ^max{w : k G TV\£7 } - y t j'er 51 max : k G N\U} jk - X] - 53 max{ u; >ei/\r max{w;jjt : k G N\(U max{u(,'i : k G T V \ C / } - j'ec 5Z jfc by (2.1) : k G TV\C7 } U {i}) } ie^u{i} -f w j'eru{t} = 53 m a x { w jet/ = ^ :k • k G N\(U U { t ' » }, ( + 51 m a x { u ; ^ : A; G T V \ ( f / U {i}) } jeu\T max{ w y t : A: € JV\(I7 U {t}) } j'6t/u{t} 51 (m a x ( w ifc : kE N\(U U {i}) } - max{ u;,- : A; G TV\£7 }) < 53 maxliwj-j. :fcG N\U} jet/ t - 51 max{ tuyjfc : k G N\(U U {i}) } >et/u{t} = S(U) - S(U U {»}). T h u s , 6(Tu{i})-S(T) > 6(U U {t}) - 6{U), which proves the submodularity of 6. T h e submodularity of a follows using identical arguments, or alternatively, see Lovasz [100]. N o w , we are ready to prove the submodularity of c and c . x T h e o r e m 2.1. The characteristic functions 2 C\ and c are submodular 2 set functions 29 on subsets of N. Proof. C o n s i d e r i n g C j first, recall that we denoted by d'j the length (cost) of a k shortest (cheapest) path between nodes j and k. It follows from G o m o r y and H u [60] that for every subset 5 C JV, Ci(S) = E E j€S r d' + ]k = I T , H ikd' + = ^(E ]k k£N\S E r jk j'es Y.r d' E ]k k£S, k>j S>i*4* + fceAr k j€S E >k4fc r Y.r kd' ). E 3 ifceAr\5 (2.2) jk jes A similar formula follows, by G o m o r y a n d H u [58], for c and every subset S C JV, 2 c 2(-5) = ^(E max ( ifc r ^ m a x { r j t : ^ S } ) , (2.3) because the right hand side of (2.3) is a lower b o u n d on the cost of constructing a network which satisfies, nonsimultaneously, the requirements rj , j 6E 5 , k £ N', and G o m o r y and k H u [58] proved that this lower b o u n d can always be achieved. N o w , we observe that the first expression i n the right h a n d side of (2.2) (resp., (2.3)) is an additive (or modular) set function o n subsets S of TV, because YlkeN jkd'j r k (resp., m a x { Tj : k £ N }) does k not depend o n S. T h e second expression i n the right h a n d side of (2.2) (resp., (2.3)) is s u b m o d u l a r by L e m m a 2.2 if we substitute r (resp., rd') for w, a n d exchange N\S and S. Since the s u m of a submodular and a modular set function is submodular, and since a scalar m u l t i p l e of a submodular function is submodular, it follows that C\ and c are s u b m o d u l a r functions. • 2 T h e s u b m o d u l a r i t y of the characteristic functions imply, by Shapley [132], that the games [N\c\) and ( i V ; c ) are concave, and therefore have nonempty cores. Thus, it is 2 always possible to allocate the cost of constructing a communication network among the players or users i n a way that no subset of players can be better off by constructing its own separate network. However, the cores of (N; C i ) a n d (N; c ) would likely be 2 quite large. A l t h o u g h one can efficiently (in linear time) generate each extreme point of the cores, provided that the values of C\ a n d c are available (see Shapley [132]), none 2 30 of these extreme points could possibly serve as a 'fair' cost allocation scheme for the network synthesis problems. Therefore, it would be desirable to generate solutions such as the Shapley value and the nucleolus which have been extensively studied and are widely accepted as reasonable and compromise solutions. We note that the Shapley value of a concave game, and, i n p a r t i c u l a r , the Shapley value of the network synthesis games, is contained in the core. Unfortunately, it is computationally i m p r a c t i c a l to find the Shapley value and the nucleolus of general concave games, and, in particular, those of the general network synthesis games. However, in Section 2.4 below, we are able to provide closed form expressions for the nucleolus of the game (N]Ci), and the nucleolus of (N;c2) i n the special case, when the associated requirement structure is a spanning tree. Furthermore, in Sections 2.6 to 2.8 below, we w i l l develop some useful decomposition results for the core, nucleolus, and Shapley value of the network synthesis games, when the requirement structure has a bridge, w h i c h is slightly more general than a spanning tree. 2.3 Irredundant Representation of the Cores of -(TV; c^) and (JV;c ) 2 In this section, we w i l l provide an irredundant characterization of the cores of the network synthesis games (/V;cx) and (7V;c ). For ( J V ; c i ) , we w i l l show that the core 2 constraints induced by the subsets of N that are connected and whose complements are also connected, i n the associated requirement structure, are sufficient and, in some sense, also necessary to describe the core. For (/V~;c2), in addition to the connected subsets whose complements are connected, an irredundant representation of the core requires the constraints induced by the closure-connected subsets whose complements are connected. For example, in F i g u r e 2.7, S = { 1 , 2 , 3 , 4 } is connected w i t h N\ S = { 5 , 6 , 7 , 8 } also connected, whereas S = {6,8} is closure-connected w i t h N\S = { 1 , 2 , 3 , 4 , 5 , 7 } connected in the requirement structure shown. — (N,E ), Recall that given a requirement structure G r set 5 to be S = S U { k £ N\S be closure-connected : (i,k),(j,k) r G E, r {i,j} we let the closure 5 of a C S } , and that S is said to if S is disconnected but S is connected in G . r exposition, we now present two additional n o t a t i o n : IS(G ) r F o r simplicity of w i l l denote the collection 31 of all nonempty connected subsets of TV, whose complements are also connected in G , r i.e., = { S C N : b o t h S ^ 0 a n d N\S 7S{G ) r are connected i n G }, r and JH S {G ) w i l l denote the collection of all nonempty connected or closure-connected r subsets of TV, whose complements are connected i n G , i.e., r TM S(G ) = JS{G ) r The r U { S C TV : S ^ 0 closure-connected, N\S connected i n G }. r following l e m m a regarding the cost structure of a connected or a closure- connected subset, whose complement is disconnected, w i l l be used subsequently i n T h e o r e m 2.2 below. F o r an example of a closure-connected subset, whose comple- ment is disconnected i n the requirement structure G displayed i n Figure 2.7, consider T S = { 1 , 3 , 4 , 5 } which is closure-connected, b u t N\S — { 2 , 6 , 7 , 8 } is disconnected i n G . r Let G = (N,E ) Lemma 2.3. r r be a requirement 2 subset of N whose complement N\S is disconnected of N\S, a r ,Rh} is a minimal = {h-l)- g c (N) + c (S). a a L e t Tf be the set of nodes i n Rf which are adjacent to at least one node of S i n G , i.e., T r = {p E R f : {p,q) G E , f 2 c' (N) = c {N). q G 5 } , / = l,...,h. r prove the l e m m a for c . L e t c' (U) = | Y^peu 2 in G . If {R\,... closure-connected then for a = 1,2, E c (N\R ) Proof. which induces the net- and ( T V ; c ) , and let S be a connected or work synthesis games (N;ci) partition structure m a { r x 2 : q £ N }, U C TV. We note that pq B y (2.3), 2 c (N\R ) 2 g = c' (N\R ) 2 g + W z max{r :qeS}. p ? per, S u m m i n g over g = 1 , . . . , h, we get t,C2(N\R ) 3=1 g = Ec' (N\R ) 2 3=1 g +lY, E m 3=1 p€T g a F i r s t , we will x { « ?eS} r : 32 h = h j h • c {N) - £ c' {R ) + - E 2 2 3=1 Z { r :qES} MAX pq 3=1 p€T g (h - 1) • c2(N) + c'2{S) = E 9 + \]t E ^ ( P r ^ S } r 3=1 P6T 9 = 9 2 q r pqd' for m a x { r pq p g by (2.3). 2 to prove the lemma for c i , substitute zZ eN Now, S es ( / i - l ) - c ( J V ) + c (S), pqd' r pq for m a x { r p 5 : q £ J V } , and : </ £ 5 } in the above equations. T h e result follows identically. • In T h e o r e m 2.2 below, We first characterize the subsets of the core constraints which are sufficient to represent the cores of the network synthesis games (JV; c ) and (JV; c ) . x The core constraints Theorem 2.2. r describe the core of the network synthesis structure G = game (N;ci) JS(G ) r sufficient 2 induced by the requirement Proof. induced by the nonempty members of and the constraint x(N) = Ci(JV) (resp., x(N) = c (JV)) are (resp., J SI S(G )) to completely 2 (resp., (JV;c )) 2 (N,E ). r r We w i l l show that a l l the other core constraints for (JV;c ) (resp., (JV;c )) x 2 are implied by the constraints associated w i t h the nonempty members of JS (G ) (resp., r JMS(G )) r and the constraint x(N) = Ci(N) (resp., x(JV) = c (JV)). Consider a core 2 constraint induced by a connected (in case of (N;ci)) or possibly closure-connected (in case of (JV;c )) subset S C JV, whose complement N\S 2 {Ri,. . . ,Rh} be a m i n i m a l p a r t i t i o n of N\S, is disconnected i n G . L e t r and let x be a point in the core of the induced game (JV;cj) (resp., ( J V ; c ) ) . We w i l l show that the inequality x(S) < Ci(S) 2 (resp., x(S) < c (S)) 2 x(N\R ) g < c (N\R )), 2 g is implied from the inequalities x(N\R ) g g = l,...,h. < Ci(N\R ) g We note that the subsets N\R g (resp., are connected (resp., connected or closure connected) w i t h connected complements i n G , a n d thus r belong to JS(G ) r (resp., JMS(G )). Therefore, for a — 1,2, r (h - 1) • x(N) + x(S) Yx(N\R ) = g 3=1 < £e.(JV\J2,) 3=1 = (h-l)-c [N)+c (S), a a by L e m m a 2.3, 33 and since x(N) = c (N), it follows that x(S) a < c (S). a For a subset S C N w h i c h is disconnected but not closure-connected (in case of ( J V ; c ) ) or possibly closure-connected (in case of ( J V ; c i ) ) , let {Ri,..., Rh} denote a 2 m i n i m a l p a r t i t i o n of S, and let H = { l , . . . ,h}. T h e n , by (2.2) (in case of (TV;ci)) and by (2.3) (in case of (TV; c ) ) , we have c (\j R ) = zZ eH a(R ), 2 for each g G H, R g R g G 7klS(G ). T a g£H c g g g a = 1,2. We note that is also connected, then R G TS(G ) is connected, and if N\R g g and r Otherwise, by the previous paragraph, the constraints induced by the members of 7S(G ) or the connected members of IMS(G ) r imply that x(R ) r g < c (R ), a g a = 1,2. Therefore, for a = 1,2, x{S) = £x(i? ) 5 geH = Clearly, a subset N\{i}, belongs to 7US(G ) r c (S). a i G A^, is either connected or closure-connected and thus and, if connected, to 7S(G ) r as well. However, observe that its associated core constraint can be replaced by a nonnegativity constraint. T h i s will not change the characterization of the core. Indeed, for a = 1,2, x{N\{i}) < = = x{N), by xi > 0, c (N) a c (iV\{t», from (2.2) and (2.3). 0 The subsets of core constraints which we found above to be sufficient for representing the core of the network synthesis games (7V;ci) and (7V;c ) are also necessary 2 for this description. Indeed, T h e o r e m 2.3. Given a general requirement duced by the nonempty members of 7S(G ) r structure G , the core constraints r (resp., 7M$(G )) to describe the cores of the induced games (N;ci) r and (N;c ), 2 are, in general, in- necessary in the sense that for any 34 Figure 2.6: A Spanning Tree Requirement Structure Used i n T h e o r e m 2.3. n, one can construct constraints a requirement structure such that the removal of any of the above will introduce vectors which are not in the core of these games. Consider the requirement structure G proof. = (N,E ) r where N = { 1 , . . . , re}, re > 2, E r displayed i n Figure 2.6, r = { ( 1 , 2 ) , ( 1 , 3 ) , . . . , (1, n ) } , and r iy = = 1, £ E . F i r s t , we analyze the game (TV; c ) induced from G . T h e core constraints asr 2 r sociated w i t h the nonempty connected subsets of TV, whose complements are connected, in G r are j = 2,... Xj < 1, (2.4) ,71, and x(JV\{j}) < n / 2 , y = 2, , re. (2.5) T h e core constraints associated w i t h the nonempty closure-connected subsets of TV, whose complements are connected in G , are r x{S) < (s + l ) / 2 , N o w , consider the vector x 1 , J 5 C { 2 , . . . , n } , s = | S | > 2. , j = 2 , . . . , re, defined as f («-3)/2, 3/2, 10, if S= 1; if 9 = i ; otherwise. (2.6) 35 Then, x ^ violates the constraint Xj < 1 i n (2.4), but satisfies all the other core con- 1 straints. N e x t , let z 2 j , j = 2 , . . . , n , be given by (3/2, if g = i ; -1/2, if g = i ; 1/2, otherwise. T h e n , z ' violates the constraint x(N\{j}) 2 < n/2 in (2.5), but satisfies all the other J core constraints. Similarly, define z 3 , 5 , S C { 2 , . . . , r e } , 5 > 2, as ({n-s)/2-l, x 3 s g if 9 = 1 ; = • 1 / 2 + 1/5, . , 0, Then, x 3 , 5 if 0 6 5 ; otherwise. violates the constraint x(S) < (s + l ) / 2 in (2.6), but satisfies all the other core constraints. N o w , for the game (/VJCJ) induced by G , the core constraints associated w i t h the r nonempty connected subsets of / V , whose complements are connected i n G , are exactly r (2.4), and (2.5) w i t h n/2 replaced by re — 1. T h e vector x '* (resp., z 1 ) above can be 2 j modified by replacing (re — 3 ) / 2 w i t h re — 5 / 2 (resp., 1/2 w i t h 1). T h e n , the above proof follows identically. • In view of Theorems 2.2 and 2.3 above, the constraints associated w i t h the nonempty members of 7S[G ) (resp., INS(G )) T c (N)) 2 r and the constraint x(N) = Ci(N) (resp., x(N) = provide us, in some sense, w i t h an irredundant representation of the core of ( T V ; ) (resp., (7V;c )). Cl 2 However, observe that there are some instances of the network synthesis games, whose cores need not be described by all the constraints induced by the nonempty members of JS{G ) r and IMS(G )r Indeed, if edge (2,3) w i t h r z = d 2 2S = 1 is added to G i n the above example,- then the connected subset 7 V \ { 2 , 3 } , whose complement r {2,3} is also connected in G , induces the core constraint x(N\{2,3}) r z ( 7 V \ { 2 , 3 } ) < re — 1) for the network synthesis game (N;c ) 2 < n/2 (resp., (resp., (iV;ci)). However, this constraint is redundant, since it is implied by the constraints z ( / V * \ { i } ) < re/2, j = 2 , 3 , and x(N) = re/2 (resp., x(N\{j}) < re - 1, j = 2 , 3 , and x(N) = re - l ) . 36 Clearly, Theorems 2.2 and 2.3 substantially reduce the number of constraints required to represent the cores of (JV; C i ) and (JV; c ) . In particular, if G> is a simple path, 2 then only 2n — 1 (resp., 3n — l ) constraints are required to describe the core of ( J V ; c i ) (resp., ( J V ; c ) ) induced by G . 2 r We remark, however, that the redundant core constraints are, in general, not necessarily redundant for computing the nucleolus of a general cooperative game, see Maschler, Peleg, and Shapley [103]. However, if the intersection of the core and the kernel is unique, Maschler, Peleg, and Shapley [103, Corollary 4.11] proved that the redundant core constraints are also redundant for the computation of the nucleolus. Since, in concave games, the kernel coincides w i t h the nucleolus and is unique, it follows that for the network synthesis games (JV; C i ) and (TV; c ) , the nucleolus is uniquely 2 determined by the irredundant core constraints. Furthermore, if there are a polynomial number of irredundant core constraints, then, in the computation of the nucleolus by the K o p e l o w i t z m e t h o d [85], each linear program, in the sequence of linear programs arising in this method, has a polynomial (in n) number of irredundant constraints. Since there will be a p o l y n o m i a l number of these linear programs in the sequence, it follows, by K h a c h i a n [84], that whenever the core of a concave game and, in particular, the network synthesis games, can be represented by a p o l y n o m i a l number of constraints, the c o m p u t a t i o n of the nucleolus can also be done i n polynomial time. However, it is not clear how a reduction of the core constraints can, i n general, be used to lessen the computational effort required to find the Shapley value. Nevertheless, we will show, in Section 2.8 below, how to compute, in constant time, the Shapley value of (JV; C j ) , and, in linear time, the Shapley value of ( J V ; c ) whose associated requirement structure is a 2 spanning tree. 2.4 The Nucleolus of the Network Synthesis Games We provide, in this section, simple closed form expressions for the nucleolus of the game ( J V ; c i ) , a n d for the nucleolus of the game ( J V ; c ) whose associated requirement 2 structure is a spanning tree. G i v e n a (general) requirement structure G r = (N,E ), r consider the vectors \i = 37 fij - and £ = {£,•) e ^ max{ r :k E jk N}, 5R , n 6' = « E i*4*- r We note that b o t h /Li and £ are functions of G . r F i r s t , we w i l l show that p (resp., £) belongs to the core of the induced game (TV; c ) (resp., (N;ci)). Later, we will show 2 that £ is the nucleolus of ( T V ; ^ ) , and that p is the nucleolus of (TV;c ), provided that 2 G r is a spanning tree. Lemma 2.4. Proof. The vector u, (resp., £) belongs to the core of (TV;c ) {resp., 2 (N\Ci)). We first prove the lemma for p. B y (2.3), c ii ) \ (E = s max ( E r :keN}+ jk ;'es = KS) + \ 1 > m jeJV\s E max jeN\s ( r a x l r i* : k e }) 5 • : k <E S} jk p{S), where the strict inequality follows because the requirement structure G Furthermore, by (2.3), p{N) = \ J2jeN max{ r jJt T is connected. : k £ TV } = c (TV). T h e strict inequality 2 above implies that p is in the relative interior of the core of (TV;c ). 2 Now, to prove the lemma for £, replace (2.2) for (2.3), J2 k £ TV }, £ f c 5 Tj d'j k 6 k for max{ : k £ 5 }, £ for /x, and Ci Tj d'- k€N k k for m a x f / - ^ : for c i n the above proof. 2 • Recall that s {N,x,c) Theorem 2.4. Proof. : S C TV, S 3 p , S ^ = min{ c(5) — x ( 5 ) = ex(S,x,c) pq £ «s £/ie nucleolus of the game (TV;Ci). For every subset 5 C TV, by (2.2) and the definition of f, we have ex(5,e,ci) c (S)-aS) = = 1 i(E z >es E ^ fceTV + E jes E keN\s E ^ 4 * r df )-W ik ik ies keN q}. 38 jes keN\s ex(JV\S,f, ). = C l N o w , for every pair of nodes p,q G JV, choose a subset T C JV such that T 3 p, T $ q, and ex(T, £, c ) = m i n { e x ( S , £, c ) : S C JV, S B p, S $ q). x Since e x ( 5 , £, c ) = e x ( J V \ x x 5 , £, q ) , S C JV, it must be that J V \ T minimizes { e x ( 5 , £, c ) : S C JV, S 3 q, S $ p}. x £,Cx) = ex(T, £, c ) = ex(N\T, £,C]) = s (N, Therefore, s (N, pq x qp £, c ^ , and the concavity of ( J V j C i ) implies that £ is the nucleolus. • T h e r e m a i n i n g of this section is concerned only w i t h the game (JV; c ) . F i r s t , recall 2 that for a subset 5 C JV, the closure S is defined as S = 5 U { k G J V \ 5 : (i, fc), ( j , /c) G G 5 } , and that 5 is closure-connected if S is disconnected, but S is connected £V, G E, in G>. Further, for edge r let JV, (resp., JV,) denote the collection of nodes, including node i (resp., j), from which there is a p a t h to node i (resp., j) that does not pass through node j (resp., i). L e m m a 2.5 below w i l l be used subsequently in T h e o r e m 2.5 which proves that (J, is the nucleolus of ( J V ; c ) , if the associated requirement structure is a spanning tree. 2 L e m m a 2.5. If an edge (i,j) is a bridge in a requirement structure G = T (N,E ) r then (i) c (JV,) - fi{Ni) = ex(JV,-,/i,c ) = ex(N 2 2 In addition, if G with a minimal 2 is a spanning r partition {Ri,..., (iii) e x ( 5 , p, c ) > ex(R ,p,c ), 2 Proof. g 2 2 (ii) ex(JV,-,y,c ) + ex(N ,y,c ) j p,,c ) = r,-,-/2, y (with e x ( J V , y , c ) = 0), and for every cost allocation 2 j: 2 = r,-,-. tree, then for every closure-connected Rh), whose complement g = N\S subset S C JV is connected, in G r l,...,h. (i) and (ii) follow from the definition of p and (2.3). To prove (iii), since J V \ S is connected and G r is a spanning tree, it follows that S\S node k. Furthermore, k is the only node in N\S consider a component R g ex(R ,p,c ) g 2 adjacent to some node in S. N o w , of 5 and let / be the unique node in R g = r /2, kl by (i) above contains a unique adjacent to k. T h e n , 39 < - max{ r = ex(S, p,c ), kp : p £ S }, since / £ S by (2.3) and the definition of p. 2 • T h e o r e m 2.5. If the requirement structure G = (N,E ) r is a spanning tree, then r p is the nucleolus of the induced network synthesis game ( J V ; c ) . 2 Proof. For every pair of nodes p,q £ JV, choose a subset U C JV such that U 3 p, U $ q, and Spg(JV, p, c ) — ex(U, c ) . B y T h e o r e m 2.4 and L e m m a 2.5 (iii) 2 2 above, we can assume that U is the node set of a m a x i m a l connected subtree rooted at some node k, on the unique path between p and q, which does not contain q, i.e., U 3 U q, and U, N\U are connected in G . L e t / be the node in G which is adjacent to r r k and is on the unique path between k and q. B y L e m m a 2.4 (i), ex(U, p,c ) 2 Therefore, if edge pq qp = ex(Nj,p,c ) 2 = r /2. kl has a m i n i m u m requirement among all the edges on the p a t h between p and q, then we must have that s (N,p,c ) s (N,p,c ) p,k, 2 = rij/2. p,q £ JV, and the concavity of (N;c ) 2 = ex(JV,,/z, c ) = ij/2. r 2 2 Thus, s (N,p,c ) pq 2 = s (N,p,c ) qp Similarly, for every pair 2 implies that /x is the nucleolus. • E x a m p l e 2.3 below shows that the result presented in Theorem 2.5 above may not hold for a requirement structure which is more general than a spanning tree. E x a m p l e 2.3. Consider the requirement structure G = (N,E ) r r displayed on the top left corner of Figure 2.5, where the requirements are shown on the edges and the u n i t costs are equal to one. T h e vector p for G is equal to (2,3,3), but one can easily r verify that the nucleolus of the induced game (N;c ) 2 is equal to (2.5,2.75,2.75). • Nevertheless, u, also plays an important role for another special class of requirement structures, specified in the proposition below. G r = (N,E ), let T r r F i r s t , given a requirement structure be a m a x i m u m requirement spanning tree ( M R S T ) in it (for illustration, see Figure 2.1 in Section 2.1). Proposition. requirement equal. structure p coincides G r with the nucleolus of the game (N;c ) 2 = (N,E ), r if all the requirements induced by a of any MRST in G r are 40 Proof. Let T be a M R S T i n G , and let the value of the common requirement i n T r r be r. Clearly, m a x { r ik k £ N} : k G JV }, t,y G /V", and pj = | max{ : k £ N } — max{ r : = r/2, j 6 N. Furthermore, from (2.3), C 2{S) = ]. (E m a x r- : fc € ( ; fc JV } + jes • { r i* * € S }) j€N\s = —- + - E 6 m a x r m a x ( r :fcG S } ifc r Therefore, for every nonempty subset 5 C JV, e x ( 5 , M , c ) = c ( S ) - fi(S) > ^ 2 2 + ^ - ^ = ^. Now, ex(JV\{j},/,,c ) 2 = c (JV\{i})-/x(JV\{y}) = c (JV) -^x(JV) 2 = m= Therefore, ex(N\{j}, by (2.3), 2 r/2. p, c ) < e x ( 5 , yii, c ) , S C JV, 5 ^ 0. Thus, for every pair of nodes 1 2 2 p , g G JV, we have 5 (JV,/x,c ) p? 2 = = = ex(JV\{g},/i,c ) 2 r/2 ex(JV\{p},/x,c ) 2 T h e result follows by the concavity of the game (JV; c ) . 2 41 2.5 Nearly Decomposable Network Synthesis Games We introduce, i n this section, the class of nearly decomposable network synthesis games, and show, i n the subsequent Sections 2.6 to 2.8, that one can provide computationally useful decomposition results for the core, the nucleolus, and the Shapley value of this class of games. F i r s t , recall that for any two adjacent nodes i and j in a requirement structure G> = (N,E ), we denoted by M j (resp., Mj) the set of nodes in TV, (resp., Nj) r to i (resp., j). If is a bridge in G , the induced game ( T V ; ^ ) is said to be nearly r decomposable, w i t h a bridge ij r then G r adjacent If in addition, < min{ m i n { r ik : k £ M, }, min{ Tji : / £ Mj } }, is said to possess the bridge property, and, without causing confusion, the in- duced game (JV;c ) is said to be nearly decomposable, w i t h a bridge 2 For example, in F i g u r e 2.7, the requirement structure has the bridge property w i t h (4,5) as a bridge, but not w i t h (2,4) as a bridge. We observe that a spanning tree requirement structure t r i v i a l l y possesses the bridge property, i.e., there always exists a bridge w i t h an associated requirement satisfying the above inequality. We observe further that if G has T the bridge property, it can induce b o t h nearly decomposable games {N;ci) and ( A ; c ) . r 2 However, if G does not satisfy the bridge property, while having only a bridge, it inr duces the nearly decomposable game (N;ci), but not the nearly decomposable game (N;c ). 2 Suppose that the requirement structure G r = (N,E ), r inducing the game (resp., the (7V;c )), has a bridge (resp., the bridge property w i t h a bridge) 2 (N;ci) and define for subsets S C N, (2.7) otherwise. 42 Figure 2.7: A Spanning Tree Requirement Structure. and c {s) -mi if either both i 6 S and 5 n { M , U {j}} = 2 2 or b o t h j £ 5 and 5 n {M,- U {»'}} = 0 c (5) = (2.8) 2 otherwise. Furthermore, construct two component games (A^;cj) and (TV^;^) (resp., (TV,;c ) 2 and (Nj-,c )) whose characteristic functions are the restriction of Ci(S) 2 (resp., c (S)) 2 to all subset S of TV,- and Nj, respectively. N o w , let E\ (resp., E ) be the collection 3 r of edges of G r w i t h b o t h endpoints in TV, (resp., TV,), e.g., in the requirement ture shown in F i g u r e 2.7, for bridge (4,5), TV = { 1 , 2 , 3 , 4 } , £ 4 TV = { 5 , 6 , 7 , 8 } , and E (Nj\c.i) r = {(5,6), (5,7), (5,8)}. One can easily verify that (TV,;^) and h 5 r (resp., (TV,;c ) and (TV,;e )) are precisely the simultaneous (resp., the equal cost 2 2 nonsimultaneous) network synthesis games induced by the requirement {Ni,E ) r struc- = { ( 1 , 2 ) , (2,3), (2,4)}, 4 and substructures {N^E}). Since each of these component games is smaller than the original games, its computational analysis is considerably easier. The following lemma establishes the relationship between the network synthesis games and the component games. Lemma 2.6. If a requirement bridge property with a bridge) and (Nj\ci) (resp., (N;c ), 2 structure G -- (N,E ) r T has a bridge (resp., the and induces the games (N;ci); (TV;c ), 2 (TVJ;C ), and ( T V , ; c ) ) , then 2 2 (TV;ci), (Ni;c\), 43 (i) c!{Ni) + ~a{Nj) = [N) - njd' Cl (ii) c (S) = c {N a a {resp., ~c {N ) + c {Nj) = c {N)) xj 2 n S) + c {Nj D S), t a decomposable into two component l 2 2 S C N, i.e. the game {N;c ), a games {Nh;c ), a = 1,2, is h = i,j. a (i) follows from (2.7), (2.2) (resp., (2.8),(2.3)), and the definition of a bridge proof. (resp., the bridge property), (ii) follows from (2.7), (2.2) (resp., (2.8),(2.3)), and the definition of a decomposable game. 2.6 • Decomposition of Cores of Nearly Decomposable Games (TV; ci) and (N; c ) 2 In this section, we decompose the cores of the nearly decomposable games (N;ci) (7V;c ), w i t h a bridge and Theorems 2.6 and 2.7 below demonstrate that one can use 2 the cores of the component games to characterize the cores of the nearly decomposable games {N;c ) 2 and (TV;^). F i r s t , let the nodes i n N be ordered such that Ni = { l , . . . , m } and Nj = {m + l , . . . , n } , and denote the cores of the two component games (AV, c ) , o, = 1,2, by a C\{N ;c )], h h = i,j. a Let G = {N,E ) r r be the associated requirement structure, and recall that for any pair of nodes p,q 6 N, r (resp., d' ) is the requirement (resp., pq pq the cost of a cheapest path) between p and q. We first consider the core of the nearly decomposable game (Af;c ), w i t h a bridge {i,j). 2 {yu---,Vn), For a cost allocation vector y — let (Xj{y) = min{£ 2 (5) - SnM^0}, y{S) : S C Nj\{j}, and {y) ai Since y(A ^) = c {Nh), r 2 = m i n { c (5) - y{S) : S C JV,.\{*-}, S n M,- ^ 0 }. 2 h = i,j, it follows by (2.8) that OLj{y) = min{c 2 (5) - y{S) = ex{S,y,c ) 2 : S D TV,-, 5 ^ j, S n Mj ^ 0 } , and a {y) t =mm{ex{S,y,c ) 2 : S D Nj, S $ i, 5nM -^0}. t 44 If Mi (resp., Mj) = 0, we let a.j(y) (resp., «»(j/)) = Uj/2. T h e core of the t r i v i a l (inessen- tial) game ( { p } ; ^ ) , p G N, consists of the unique point y and a(y), x (y y = ( y i , . . . ,y ) m m + = ^ ( { p } ) . L e t ' x ' denote G C[(^;c )], ( y the C a r t e s i a n product, and for all ( y , ...,y ) r p m 2 m + i , • • • ,Vn) £ C[(NJ;C )], 2 i , . . . , y „ ) , in the range m a x { - r j / 2 , - a ( y ) } < a(y) < t t m i n { r / 2 , ctj{y)}, let t ; C a ( » ) [ ( M - ; c ) ] = {{yi,---,Vi 2 : ( y i , . . . , y ) G C[(/V,;c )]} + a.{y),...,y ) m m 2 and ^ - " ( v j K ^ i ; ^ ) ] = { ( y m + i , - - - , y j - a ( y ) , . . . , y ) : ( y + i , • • •, y ) £ n T h e o r e m 2.6. For the nearly decomposable C[{N-,*)\=\J t F i r s t , suppose that ( j / i , . . . , y) m C\{Nj\c )}}. 2 2 C_ where the union is over a(y) in the range max{ — r^/2, Proof. n game (7V;c ) with a bridge x C [(N -C2)\ a{v] m a(w) [(JV,-;c )] 2 —a,(y)} < a(y) < min{r,- -/2,a -(t/)}. J J G C[(7V,; c )] and ( y + i , . . . , y„) G C[(iV ; c )]. 2 i m 2 For every a ( y ) i n the above range, define x — (x/,) G 9? as follows. n Vh + a(y) if h = i h = { y - a(y) if h = j x fc y^ (2.9) otherwise. We w i l l show, by c o n t r a d i c t i o n , that the vector x , given in (2.9) above, is contained in C\(N;c )}. 2 So, suppose x ^ C[(-/V;c )], i.e., there exists at least one subset S C TV 2 such that x ( 5 ) > c ( 5 ) . There are three cases. 2 1. S f l — 0- B y T h e o r e m 2.2 above, we can assume that either S C or S C T V ^ I J ' } . In b o t h cases, x ( 5 ) = y ( 5 ) and c (S) 2 inequality x(S) > c (S) 2 = c (S). 2 implies y{S) > c ( 5 ) , a contradiction. 2 Ni\{i} Therefore, the 45 2. S contains either i or j , say i , but not b o t h . B y T h e o r e m 2.2 above, we can assume that either S = TV,-, or S D Ni and S D M , 7^ 0. If 5 = TV,, then the inequality x(JV.) > c (JV.) implies y(JV,) > c (JV.) + r , / 2 - a(y) > c (JV,), 2 2 ; 2 contradicting the supposition that ( y , . . . , y ) G C[(iV,; c )]. Otherwise, i.e., when x m 2 S D JV,- and S n M y 7^ 0, by the definition of ctj(y), (2.8), (2.9), and the inequality x(S) > c ( 5 ) , we have otj(y) < c (S) 3. S n {i,j} — y{S) 2 2 = B y Theorem 2.2 above, either S D N that S D Nj. T h e n , the inequality x(S) a(y) = x(S) < ct(y), a contradiction. > c (S) 2 2 Assume a contradiction to the suppositions 2 y ) G C[(JV,-; c )]. that ( y i , . . . , y ) £ C[(JV,;c )] and {y ,..., m or S D N. implies y(SflJV,-) + a ( y ) + y{Nj) — 2 n JV,-) + c (Nj), = c (S 2 > c (S) 3 m+1 n 2 Conversely, suppose x G C[(A^;c )]. We w i l l show that there exists a constant a in 2 the above range such that ( y . . . , y ) 1 ? m and ( y m + i , . . . , y „ ) , derived from x and a through (2.9), are contained in C[(iV,; c )] and C [ ( A ^ ; c ) ] , respectively. B y T h e o r e m 2.2 above, 2 foTh = 2 i,j, ex(N ,x,c ) h < ex(S,x,c ), 2 S C N, 2 h S 3 h. (2.10) Furthermore, by (2.3), c (JV,) + c (JVy) — r,j = c ( i V ) , and by the fact that x is a cost allocation, x(Ni) x(Ni) 2 2 + x(Nj) = c (N). = c (Ni) - nj/2 2 2 + e 2 Hence, and x(Nj) = c (JV,-) - - e. 2 (2.11) F i r s t , we w i l l show that e is in the range max{ —r -/2, — a,(x)} < e < m i n { r , v / 2 , a ( x ) } . tJ Assume, w i t h o u t loss of generality, that e > 0. e < Tij/2. ? ; Since x G C[(JV;c )], it follows that 2 T o show that e < ct,(x), suppose that T C iV>, T $ j , T D M, ^ 0, and e x ( T , x , c ) = cij(x). 2 Then, ex{N U T , x, c ) t 2 = c (JV,- U T) - x(JV, U T) = c {Ni)- /2 = - e + ex(r,x,c ), > 0, 2 2 rij + c (T)-x(N,)-x{T), 2 2 by (2.11) since x G C[(JV;c )] 2 by (2.3) 46 i m p l y i n g that otj{x) ex(T, x,c ) > e. 2 Furthermore, for any subset S C TV,-, S 3 i, x{S) = c (S) - < c {S) = c {S)-r /2 2 2 by (2.10) ex{Ni,x,c ), 2 + e, tj x{S) a(y) 2 - Similarly, for any subset S C Nj, Now, ex(S,x,c ) 2 by (2.11). (2.12) S 3 j, -m/2 — < c {S) 2 (2.13) €. we w i l l show that ( y i , . . . , y ) and ( y + i , . . . , y ) , derived from x and a = m m n = e through (2.9), are contained in C[(JV,;c )] and C[(NJ; C )}, respectively. F i r s t 2 2 note that by (2.9) and the choice of o:^(-), we have oth{y) — ah{x), therefore then x(S) a is in the required range. = y(S) > c (S) — c (S), 2 2 Similarly, we can show that y(S) S 3 i, and y{S) > Z {S), N o w , if S C Ni, S $ i, and y(S) and > c (S), 2 contradicting the supposition that x 6 C [ ( i V ; c ) ] . 2 < c (S), S C Nj, S $ j . 2 then x(S) 2 h = = y{S) + e > c {S) Furthermore, if S C + e = c {S) 2 2 - r^/2 Ni, + e, contradicting (2.12). Similarly, if y ( S ) > c ( 5 ) , S C Nj, and S 3 j , then (2.13) will be 2 contradicted, which completes the proof. • We realize, of course, that Theorem 2.6 above is not very practical, since for every y (E C\(N;c )} 2 it requires the computation of ccj{y) and cti(y). However, the computational effort can significantly be reduced for the game (7V;ci). Indeed, consider the network synthesis game and for a constant a, let ( J V ; C I ) , C [(JV.-;ci)] = {(y ,...,y a 1 i + r jd' /2 i ij + a,...,y ) : {y ...,y ) m u m € C[(JV,-; cj)]} and C-aKNj-,^)] = {{y m+1 ,... ,yj + Tijd'^/2 - a,... ,y ) n : (y m + i , . . . , y„) G C[(/V ; e )} }. i x 47 We note that the core of the t r i v i a l (inessential) game ({p};c?i), p G N, consists of the unique point y = 0. p Now, unlike in the T h e o r e m 2.6 above, we need not restrict the values of a(y) for (N; ci) to be between — a,-(y) and ctj(y). In this case we have, for a G [ — r o!- -/2, r,- -d|--/2], JJ € C[(A ,;ci)] and (y +i, • • •, y ) (j/i>---,!/m) (y m + € C[(7V,-; r m n Cj)], that y = J ; (yx,...,y ) m x i , . . . , y ) is contained in C\(N; Ci)}, which significantly simplifies the computations. n T h i s result is stated formally i n T h e o r e m 2.7 below, whose proof is omitted here, since it is similar to the proof of T h e o r e m 2.6 above. Theorem 2.7. For the nearly decomposable game (N;ci) with a bridge (i,j), C [ ( J V ; ) ] = | J C [(JV,-;ci)] X C_ [(iV,;c~ )] Cl a a where the union is over all a in the range —rijd' j/2 < a < r,-ydJ--/2. i; 2.7 1 The Nucleolus of the Nearly Decomposable Game In Section 2.4 above, we presented a closed form expression for the nucleolus of the network synthesis game (N;ci). However, for the network synthesis game (TV; c ) we 2 were only able to provide a closed form expression of the nucleolus in the special case of an associated spanning tree requirement structure. In this section, we w i l l extend the above result by providing a decomposition procedure for the nucleolus of the nearly decomposable game (7V;c ), w i t h a bridge {i,j)2 Namely, T h e o r e m 2.8 below proves that the nucleolus of (N;c ) is the Cartesian product of the nucleoli of the component 2 games (iV,;c" ) and (Nj\c ). 2 2 F i r s t , recall that for a cost allocation vector i G F and for a pair of nodes p,q 6 N, s (N,x,c ) pq = min{ex(>S,x,c ) : S C N, S 3 p, S 2 q}. T o simplify the exposition, we 2 extend this definition to the component games (TV/,; c ) , h = i,j, 2 h = as follows: for S C Nh, and for x 6 9 J , we let the excess of 5 at x w i t h respect to c be denoted by n 2 ex(5, x, c ) = c (S) 2 2 — x(S), and for any pair of nodes p, q G Nh, we let ' ,x,c ) = m i n { e x ( 5 , x , c ) : S C TV^, S 9 p, S $ q}. h 2 2 48 L e m m a 2.7. For a vector y in the core of the nearly decomposable game ( J V ; c ) , 2 with a bridge p,q e N , satisfying y(Nh) we have s {N,y,c ) h pq - 2 — c [Nh), h = i,j, 2 and for every pair of nodes s {N ,y,c ): pq h 2 G i v e n the pair of nodes p,q G JV,-, choose a subset U C N, U 3 p, U $ q, Proof. such that ex(U,y,c ) = s (N 2 e x ( T , y , c ) = s (Ni,y,c ). 2 ,y,c ), pq pq 2 and a subset T C JV,, T 3 p, T $ q, such that We w i l l show that ex(U,y,c ) 2 = ex(T,y,c ). 2 T h e o r e m 2.2 above, if U 3 i, then U Z> Nj. F i r s t , by 2 Otherwise, either U C JV,\ {/,'}, or both = Nj and U n M , ± 0. If b o t h U n {TV, U {?'}} = JV,- and U n M , / U n {Nj U {i}} 0, then e x ( l / n JV„y,c ) 2 = c (£7 n JV,-) - y(U n JV,) = ^(t/nJVO + y ^ O - y ^ ) = c (^nJV,-) + c ( J V ) - y ( £ 7 ) = c (LT) - y ( * 7 ) , = ex(t/,y,c ). 2 2 i 2 by (2.3) and (2.8) 2 (2.14) 2 N o w , consider the following four cases. 1. U ^ i a n d T ^ i . B y the definition of s (N,y,c ) pq we have ex(U,y,c ) 2 ex(T, y , c ) , and by (2.8) we have e x ( T , y , c ) = e x ( T , y , c ) . 2 2 definition of s (Ni,y,c ) pq < 2 2 Moreover, by the we have e x ( T , y , c ) < ex(£7 D J V y , c ) , and by (2.8) 2 2 i 5 V e have ex(/7 n JV,-, y, c ) = ex(t/ n JV,-,y,e ). 2 2 2 Furthermore, by (2.14) we have ex(£/ n J V , , y , c ) = e x ( £ / , y , c ) . 2 2 2. U 9 i a n d T ^ i. T h e n , as in item 1 above we get ex([7, y , c ) < ex(T, y , c ) < 2 ex(U n JV,, y , c ) . Furthermore, since U D JV, and ex(Nj,y,c ) 2 2 3. U ^ i a n d T 3 i . ex{TuNj,y,c ). 2 Nj,y,c ) 2 2 2 pq and ex(r U Nj,y,c ) 2 = ex(T,y,c ) 2 = + ex{Nj,y,c ). 2 2 ex(T, y , c ) . y, c ) we have that e x ( T , y, c ) < ex(UnNi, 2 2 = ex(U,y,c ). 2 we have ex(U,y,c ) < 2 Furthermore, by (2.8) we have that both ex(TL)Nj,y, 2 pq + ex(Nj,y,c ) T h e n , by the definition of s (N,y,c ) 0, it follows that e x ( T U Nj,y,c ) s (Ni, = 0, it follows by 2 (2.8) that ex(C7 D J V , , y , c ) = ex(C7 fl N,y,c ) 2 c ) = ex(jTU 2 Since e x ( 7 V , y , c ) i 2 - N o w , by the definition of 2 y , c ) , and by (2.8) we have that 2 49 ex(U n Ni,y,c ) = ex(£7 D Ni,y,c ). 2 F i n a l l y , by (2.14) we get ex(U D N,y,c ) 2 = 2 ex{U,y,c ). 2 4. U 3 i and T 3 i. T h e n , as in item 2 above we get ex(T,y,c ) < ex(C,y,c ), 2 but as in item 3 we get ex(U,y,c ) < 2 2 ex(T,y,c ). 2 The above four cases, which are of course exhaustive, reveal that for every pair of nodes p,q £ JV,, we have that s (N,y,c ) pq = ex{U,y,c ) 2 = ex(T,y,c ) 2 = s (N ,y,c ). 2 pq l The 2 analysis for any pair of nodes p, q £ Nj is identical. • Now, we are ready to present the decomposition result for the nucleolus. Theorem bridge and The nucleolus of the nearly decomposable 2.8. game ( J V ; c ) , with a 2 is the Cartesian product of the nucleoli of its two component games (JV,;c ) 2 c ). {NJ; 2 Proof. Let u and u l be the nucleoli of (JVJ;C ) and (Nj\c ), 3 let v be their Cartesian product. respectively, and 2 2 We w i l l show that u is the nucleolus of ( J V ; c ) . 2 F i r s t , by T h e o r e m 2.6 above we have that v £ C [ ( J V ; c ) ] . Furthermore, since i / ' is the 2 nucleolus of ( J V , ; e ) , it follows for every pair of nodes p,q £ Ni that s {Ni, 2 s {Ni,u ,c ). T h u s , s (Ni, % qp pq 2 u,c ) pq that s (N, v, c ) = s (N, pq 2 = s [Ni,u,c ), 2 qp 2 v, c ) = l 2 and by L e m m a 2.7 above, we have u, c ). T h e analysis for any pair of nodes p,q £ Nj is identical. qp 2 Now, suppose p £ JV,- and q £ Nj. Let T and U be two subsets of JV w h i c h minimize { ex(S,v,c ) : S C JV, S 3 p, S $ q} and { e x ( 5 , u , c ) : S C JV, S 3 q, S $ p}, respec- 2 2 tively. We w i l l show, by contradiction, that s (N,v,c ) pq s (N, qp 2 = ex(T,u,c ) 2 = ex(U,u,c ) = 2 v, c ) . Suppose not, i.e., suppose, without loss of generality, that ex(T, u, c ) < 2 2 Since ex(JV , v, c ) = 7*^/2, / i = t , j , it follows that e x ( T , i^, c ) < ex(C7, v,c ) ex(U,v,c ). 2 FE 2 2 r , j / 2 , and that T ^ JV,-. If ex(t/, v, c ) — r^/2, 2 then let U = Nj. 2 Consider the following three exhaustive cases. 1. T =4 i. • B y Theorem 2.2 above, T C JV,-\{t'}. Suppose that a subset W C JV,minimizes { e x ( 5 , u , c ) : S C JV,, S 3 i, S $ p}. l T h e n , by the definition of 1 2 s (N,y,c ) qp 2 2 l 2 l 2 2 = s (Ni,u ,c ), 1 ip 2 — ex(W, v ,c ). that ex(W U Nj,v,c ) ex(W,v ,c ) < ex{W U Nj,v,c ), we get that ex(U,v,c ) 2 and by (2.8) we have Moreover, B y the choice of W we get that and since is the nucleolus of (JV,;c ) it follows 2 < 50 that Si (Ni,u\c ) p = s i(Ni,u ,c ). Furthermore, since T C A ,-, T $ i, and T 3 p, l 2 p 7 2 it follows by (2.8) that T minimizes { ex(S, * / , c ) : S C N, S 3 p, S $ 2 and therefore Spi(Ni,i/',c ) = e x ( T , ^ , c ) . T o summarize, ex(U,v,c ) 2 Nj,v,c ) 2 = ex(W ,z/',c ) = s p(N ,i' ,c ) / 2 i i 2 < ex(W U 2 = s i(Ni,i/ t 2 ,c ) = ex(T,u,c ), % p 2 i}, which is a 2 contradiction. 2. T 3 B y Theorem 2.2 above, T D N i , a n d by (2.8) we have that ex(T,u,c ) = 2 ex(T n N j , v\ c ) . Furthermore, since T D Nj 3 j , T n Nj C AT,, a n d T n Nj $ q, 2 it follows by (2.8) that r n / V , minimizes { e x ( 5 , i / ' , c ) : S C N j , S3 j, S $ q}., J 2 otherwise, T cannot m i n i m i z e {ex(S,v,c ) : S C N , S 3 p, S $ q}. 2 e x ( T n Nj,v ,c ) = Sj (Nj,vi,c ). 3 2 (Nj-,c ), q Furthermore, since v 2 it follows that Sj (Nj,u , c ) = s j{Nj,u ,c ). 3 2 have that s j(Nj,u ,c ) 2 : S C N j , S 3 q, S $ j}. 3 2 = ex(T C\ Nj,v ,c ) = s (Nj,u ,c ) % 2 2 since U could have been chosen such that 2 it also minimized {ex(S, v ,c ) ex(T,u,c ) q > ex(U,i/,c ), 3 q 2 is the nucleolus of 3 In addition, by (2.8) we 3 q jq To summarize, = s (Nj,u ,c ) 3 2 Thus, > 3 2 qj 2 ex(U,v,c ), 2 w h i c h is a contradiction. 3. T 3 i , T $ j , ( T ^ N j ) . 0. 5 T h e n , by Theorem 2.2 above, T D N a n d T n M , - ^ t L e t / € T D M j , a n d suppose a subset W C C A^-, S 3 j, minimizes { e x ( S , v , c ) : 3 2 S $ I}, i.e., ex(W, i / - , c ) = Sji(Nj,u 7 ,c ). 3 2 nucleolus of (NJ;C ), it follows that Sji(Nj,u ,c ) = sij(Nj,u ,c ). 3 2 Since 2 Furthermore, 3 2 is the 2 since T C) Nj 3 I, T C\ Nj C A ,-, and T n J V j ^ j , it follows by (2.8) that T n JV,7 minimizes { e x ( 5 , c ) : S C A j , S 3 I, S $ j}, otherwise, T cannot minimize 2 ( e x ( 5 , i / , c ) : S C N , S 3 p, S $ g } . Thus, s^N^u ,c ) = ex(T n 3 2 2 Nj,v ,c ). 3 2 Moreover, by (2.8) we get that e x ( T n N j , v , c ) = ex(T, v, c ), but ex(T, v, c ) is 3 2 2 2 supposed to be strictly less than r , j / 2 . Therefore, c (W) — u (W) = ex(W,v 3 3 2 Sji(Nj,i/ ,c ) = Sij(Nj,u ,c ) 3 c (TDNj)2 = ex(T C\ Nj,v ,c ) J 2 v [TnNj) j = ex(T,v,c ) 3 2 2 = ex(TnNj,u\c ) derived inequalities c (W)-v (W) < r - / 2 . A d d i n g the two 2 0 < r / 2 and c {T^Nj)-u (TnNj) < r - / 2 , and 3 2 t > 2 rearranging some terms, we get i/ '(W)-rV ' 3 3 (ToNj) 2 < r , j / 2 , and 2 = ex{T,u,c ) 2 3 ,c ) = 0 > c ( W ) + c ( T n A j ) — r,-j. Since / 2 r 2 there is a common requirement Tji associated w i t h b o t h W and TC\ N j , and since, by the bridge property, Tj\ > r^-, it follows by (2.3) that c (Vy) + c ( T n Nj) — r,j > 2 t {Wu{TC\Nj}) 2 v (W)+v>{TnNj) j +c {Wn{TnNj}). Thus, v>(W\j{TnNj})+v>{Wn{TnNj}) 2 > ~c (W) + 2 2 ~c (TnNj)- j 2 ri > i {Wu{TnNj}) 2 = + c {Wn{TnNj}), 2 51 contradicting the supposition that v j Therefore, s (N,v,c ) pq = s (N,i/,c ), 2 qp 2 £ C\(Nj-,c )}. 2 p,q £ N, and the concavity of (JV;c ) implies 2 t h a t v is its nucleolus. • We note that the nucleolus of the t r i v i a l (inessential) component game p £ JV, is i/p = c ({p}). ({p};c ), 2 Furthermore, if any of the component games is associated 2 w i t h a requirement structure which satisfies the bridge property, then we can apply the decomposition, in t u r n , to this game. Clearly, if the requirement structure is a spanning tree, we can repeatedly apply the decomposition to obtain n trivial equal cost nonsimultaneous network synthesis games, each containing only one player. It is not difficult to see that the above procedure, when applied to a spanning tree requirement structure, results in a nucleolus v = (v ) p | max{ r pq w h i c h coincides w i t h p = (p ), p : q £ J V } . This suggests an alternative constructive v p = p p = method, as opposed to the analytic method presented in Theorem 2.5 above, for proving that p is the nucleolus of (N;c ), 2 if the associated requirement structure is a spanning tree. Shapley Values of ( T V ; C i ) and Nearly Decomposable ( T V ; c ) 2.8 2 The derivation of Shapley value, in general, requires an enormous amount of computat i o n . However, it is possible to significantly reduce the computations required to find the Shapley values of (JV;ci) and the nearly decomposable (N;c ). 2 For (JV;ci), we will show that the Shapley value coincides w i t h the nucleolus. For the nearly decomposable ( J V ; c ) , in T h e o r e m 2.9 below, we w i l l show that the Shapley value can efficiently be 2 computed from the Shapley values of its component games. F i r s t , to prove that the Shapley value of (JV;ci) coincides with its nucleolus, recall that, by G o m o r y and H u [60], an o p t i m a l solution to the simultaneous network synthesis p r o b l e m can be found as follows. Starting from a zero capacity network, increase the capacity of the edges on a cheapest p a t h between each pair of nodes p and q by r , pq at the cost of r pq and • d' . N o w , if there is only one requirement, the Shapley value, by the pq s y m m e t r y a x i o m , assigns the cost equally among the two users. If there are more than one requirements, each requirement can be considered separately and its cost divided 52 equally among the two users of that requirement. B y the additivity axiom of the Shapley value, the cost allocation vector assigned by this procedure coincides w i t h the Shapley value. Furthermore, it is evident that the assigned cost allocation vector w i l l be equal \ Hq£N pqd' r to £ = ( £ ) , £ = p pq p Now, since, i n Section 2.4 above, we proved that the nucleolus is equal to f, it follows that the Shapley value and the nucleolus of (TV; ci) coincide. The remainder of this section considers the Shapley value of the nearly decomposable ( J V ; c ) . F i r s t , recall that we denoted by 7r a permutation of the elements of N, and 2 that for each permutation 7r and for any node h 6 N, we denoted Sh(n) to be the set of the elements of 7r preceding (to the left of) h i n 7r. T h e following (counting) lemma w i l l be used in Theorem 2.9. below. Given any two nodes g,h € N and given a subset M C Lemma 2.8. \M\ = m, let A\ (resp., A ) denote the set of all permutations N\{g,h}, n (of the elements of N) 2 3 g and S (n) n M = 0 (resp., S (-jr) n ( M U {g}) = 0). Then that satisfy both S (ir) h h h \ i\ n! 1 (m + l ) ( m + 2) A 1 1 1 (2.15) and L-fi = — n! m+2 Proof. and (2.16) v U {g,h}}, F o r each positioning of the members of N\{M ; there are ml ( m + 1)!, out of a possible (m + 2)!, permutations that belong to A\ and A , 2 respectively. Since, there are n ! / ( m + 2)! = n(n — 1) . . . (m + 3) such positionings, it follows that \Ai\/n\ = n(n - 1) . . . (m + 3) • m ! / n ! = l / ( m + l ) ( m + 2), a n d | A | / n ! = 2 n(n - 1) . . . (m + 3) • (m + l ) ! / r i ! = l / ( m + 2). • Before stating T h e o r e m 2.9, recall that the Shapley value <p(c) — (<f>h[c)) of a game (7V;c) is given by <f> (c) = ^ E e n ( i h { ^ ) c h s x "U {^}) - cl'S'fel '))), where IT is the set of 71 all permutations 7r. Furthermore, let ra, (resp.,ra,)denote the cardinality of M j (resp. Mj), where M, (resp. Mj) is the set of nodes adjacent to i (resp., j), excluding j (resp., i), i n a requirement structure G . We note that the Shapley value of the trivial r (inessential) game ( { p } ; c ) , p 6 N, is the point <j> (c ) = c ({p}). 2 v 2 2 53 B y L e m m a 2 . 6 above, the (concave) game (N; c ) is decomposable into two (concave) 2 games (./V,;c ) and (Nj-,c ). 2 Therefore, by Shapley 2 Shapley value of (N;c ) [132], is 2 the Cartesian product of the Shapley values of (7VJ;C ) and (Nj\c ). 2 Hence, (j>h{c ) in 2 2 T h e o r e m 2 . 9 below can be taken as the Shapley value of the node h i n the appropriate component game (Ni;c ) or 2 2 with a bridge 2 2 The Shapley value 4>(c ) — ((ph{c )) of the nearly decomposable game T h e o r e m 2.9. (N;c ), {Nj\c ). 2 can be calculated from the Shapley value 4>{b) = ((j>h(c )) of 2 the game (N; c ) as follows: 2 M 2} C ' M*) ~ ((m Mb) + ( ^ 2 t + l)(m, 2)) Mb) + + - ( - m , + 1 • )( . m f + heM ,ge{l,j} 2)) k 1 = (TOj+1) (mj+2) ( i ) -f r 4>h{b) Proof. (2.17) g 2 - 1 8 h—j ) (2.19) otherwise. (2.20) F i r s t , we will show (2.20). F r o m (2.8) we have that c (S) / c (S) only i f 2 2 either b o t h i £ S and S D {Mj U {;"}} = 0, or both j £ S and S n { M , U {i}} = 0. Therefore, for each permutation n and for each h £ i V \ { M U Mj U {i,j}}, t c (S {ir) 2 h U {h}) - c {S {-n)) 2 = c {S (n) h 2 h U {h}) - we get ~c {S {n)). 2 h T h u s , (2.20) follows from the definition of the Shapley value. To show (2.17), let h £ M ; and, for simplicity, let S represent S (ir). h h T h e n , it follows from (2.3) and (2.8) that ^M/.-n c (S U{h})-c (S ) 2 k 2 h <v\ ) b(S u{h})-r /2-~c (S ) = \ c (S U {h}) — c (Sh) h 2 h tJ 2 k 2 eS ,S n{M u{i}} 3 h h = H> t otherwise. Now, from (2.15), the number of permutations of members of N satisfying j £ S and h S n {Mi U {«'}} = 0 is n ! / ( ( m , + l)(m,- + 2)), which implies (2.17). The case for h £ Mj h can be proven using identical arguments. To show (2.18), for simplicity, we let 5, represent 5,(7r). T h e n , from (2.3) a n d (2.8), 54 F i g u r e 2.8: T h e Requirement Structure (left) used i n E x a m p l e 2.4, and the Networks Resulting from the Near-Decomposition (center and right). c (5,-U{t}) +r /2-c {S ) 2 c (5,-U{i»-c (5,-) 2 ij c {Si\j{i})-c {Si) 2 2 2 S n {Mj U {j}} i { -r /2 2 j € S {j c (5,-U{«})-c (S,-) 2 i 5 = 0 (2.21) S,-nAf,- = 0 (2.22) otherwise. 2 N o w , by (2.16) and (2.15), the number of permutations satisfying (2.21) and (2.22) is n\j(m,j + 2) and n ! / ( ( m , + l)(m - + 2 ) ) , respectively, from which (2.18) follows. One can t prove (2.19) using identical arguments. • A g a i n , when the requirement structure is a spanning tree, we can use the decomposit i o n to o b t a i n n t r i v i a l games, each containing only one player. T h e n , the Shapley value of the induced game (JV;c ) can be found, using T h e o r e m 2.9 above, by 2 backsubstitu- tion, which w i l l be illustrated in E x a m p l e 2.4 below. A s a consequence of Theorem 2.9, the c o m p u t a t i o n of the Shapley value of (N; c ) , whose associated requirement structure 2 is a spanning tree, can be done in O ( n ) , i.e., linear time. E x a m p l e 2.4 below illustrates this fact, i n a d d i t i o n to elucidating the (near) decomposition procedure. E x a m p l e 2.4. Consider the requirement structure G ure 2.8, where TV = { l , . . . , 4 } , E and d pq = 1, (p,o) € E . r H = (1.5,-5,1,1.5). r = { ( 1 , 2 ) , (1, 3), (1,4)}, — (N,E ) r shown in F i g - r r 1 2 = 1, r 1 3 = 2, r 1 4 = 3, T h e nucleolus of the induced game (N; c ) , by Section 2.4, is 2 To find the Shapley value of (N;c ), 2 we observe that G r has the bridge property, w i t h a bridge (1,2). N o w , node 2 has no nodes adjacent to it except node 1, i.e., m 2 = 0, and node 1 has two nodes adjacent to it i n a d d i t i o n to node 2, i.e., 55 m i = 2. Substituting the above data in (2.17) to (2.20), we get MO = Mb) + ( \ - \ ) - \ = M b ) - \ MO = ^"0+Q-(3p)-5 = ^ (- ) 2 ) + ^ 23 (2-24) and for / i = 3,4, MO = - (—^) • ^ = * (c ) - ~ h (2.25) a Now, we have to find 4>{c ) for the component games ({2}; c ) and ( { 1 , 3 , 4 } ; c ) . T h e 2 2 2 first game is t r i v i a l , thus, its Shapley value is simply 4> {0 = c ( { 2 } ) , which by (2.8) 2 2 is equal to 1 — | = | . Substituting this back i n (2.23), we get <t> (0 = | — | = | . To 2 find the Shapley value of the component game ( { l , 3 , 4 } ; c ) , we decompose it further 2 using edge (1,3) as the bridge. T h e requirement substructure associated w i t h this game is ( { l , 3,4}, { ( 1 , 3 ) , (1,4)}), which is displayed i n the center of F i g u r e 2.8. N o w , in (2.8), replace c 2 by c , and c 2 2 by c , to derive two component games ( { l , 4 } ; c ) 2 2 and ( { 3 } ; c ) from the game ( { l , 3 , 4 } ; c ) . Furthermore, for the pair g,h £ { 1 , 3 } , let m be the number of nodes (except h) adjacent to g, in the requirement substructure g 2 2 ( { 1 , 3 , 4 } , { ( 1 , 3 ) , (1,4)}). T h e n , m i = 1 and m 3 by get <Mc ), M O 2 by M O , and m by g m g to Mb) = Mb) Mb) = MO Mb) = M O - ( ~ ) - \ A g a i n , the component game ({3}; + Q - I) = 0. In (2.17) to (2.20), replace + c ) 2 • \ = Mb) ( ^ - ^ ) - \ - \ = Mb) (2-26) + \ (2.27) = M O ~ \ is t r i v i a l , and therefore MO (2-28) <^>3(c ) 2 = c ({3}) = 2 — 1 = 2 1. S u b s t i t u t i n g this back in (2.26) we get 4>z{b) = 1 — \ = | , and substituting the value of Mb) back in (2.25) we get MO = f — ^ = ^f. T h e Shapley value of the component game ( { l , 4 } ; c ) , associated w i t h the requirement substructure ( { 1 , 4 } , {(1,4)}) which 2 56 is displayed in the right of Figure 2.8, is equally simple to find. It can easily be verified, using (2.17) to (2.20), or since players 1 and 4 are 'symmetric' in the game ({1,4}; c ) , 2 that<^>i(c ) = 414(02) = f c ( { l , 4 } ) = | . Substituting the value of <j>4(c ) back in (2.28) we 2 2 2 get </>3(c ) = I — I = | , and substituting this back in (2.25) we get <^ (c ) = | — ^ = f j . 2 4 S i m i l a r l y , substituting the value of </>i(c ) in (2.27) we get 2 s u b s t i t u t i n g this i n (2.24) gives < £ i ( c ) = ^ + ~ = 2 {N;c ) 2 2.9 </>i(c) = 2 2 f + § = ^1 ^ AN< Therefore, the Shapley value of is (j>(c ) = ^ ( 4 9 , 9 , 1 9 , 3 1 ) . 2 Summary and Further Research for the Cost Allocation Problem In C h a p t e r 2, we considered the cost allocation problems which naturally arise in the simultaneous and the equal cost nonsimultaneous network synthesis problem, if we assume that the various nodes in the network represent different users or communities. We employed the cooperative game theory to analyze these cost allocation problems, a n d proved that the derived games are concave, w h i c h implies the existence of the core, a n d the inclusion of the Shapley value and the nucleolus in the core, and then presented irredundant representations of the cores. For the equal cost nonsimultaneous network synthesis game, we used the irredundant representation of the core to provide an explicit closed form expression for the nucleolus when the requirement structure is a spanning tree. T h e n , we developed a (near) decomposition of the game in a special case, which we later used to efficiently compute the Shapley value when the requirement structure is a tree. T h e (near) decomposition was also used to simplify the analysis of the core and the nucleolus of the game i n the special case. For the simultaneous network synthesis problem, we also used the irredundant representation of its core to derive an explicit closed form expression for the nucleolus. Further, we also (near) decomposed the core of this game in the special case, and proved that the Shapley value and the nucleolus coincide. O u r results may be used as guidelines for construction cost allocation i n some comm u n i c a t i o n networks. Further, we have presented two more special cases when the Shapley value and the nucleolus can be computed efficiently. • 57 W e d i d not consider the cost allocation problem in the nonequal-cost nonsimultaneous network synthesis problem, because the computation of the cost function, in this case, is only possible through solving an exponential number of large linear programs. Nevertheless, it has been shown by D . Granot [62] that the core in this case exists, a n d using the formulation presented in Section 4.5, we can p o l y n o m i a l l y find a point in the core. O f course, one can use the results we w i l l derive in the rest of the thesis to simplify the derivation of the cost function in some special cases, namely, when the solution network is to be embedded in (restricted to) trees, rings (cycles), series-parallel, or Mi and M - f r e e graphs. 3 Chapter 3 A SIMPLIFYING TRANSFORMATION F O R The STEINER NETWORK SYNTHESIS PROBLEM 3.1 The Steiner Network Synthesis Problem T h e nonsimultaneous network synthesis problem, see G o m o r y and H u [58,59,60], is to design, at m i n i m u m cost, an undirected communication network w i t h n nodes which satisfies given requirements, i.e., lower bounds on m a x i m u m flow, between every pair of nodes, one requirement at a time. T h e data for any instance of this p r o b l e m consist of a positive integer n and two lists of n' = n(n — l ) / 2 nonnegative integers: d — (d(j) and r = (r,y), 1 < i < j < n. For each pair of nodes {i, j} C N = { 1 , . . . ,n}, dij is the cost of building one unit capacity on edge i < j, and r,y is the requirement between i and j. T h r o u g h o u t the thesis, we may allow the costs and requirements to be zero or infinity. We define the ri'-vector b — (6^) to be the vector of edge capacities to be determined, i.e., fe,y represents the capacity to be constructed on edge nodes i and j , j > i. between T h e network must have sufficient capacity to accommodate a requirement (flow rate) of r, - units between nodes i and j , j > i, when i and j act as ; the unique source-sink pair. T h e cost of providing capacity 6,-y on edge is cJ,y6,y, and the objective is to provide sufficient capacity to meet a l l n ' requirements at m i n i m u m t o t a l cost d-b = zZi<i<j< difiijn We note that the decision variables fe = (fe,y) are allowed to assume noninteger values. 58 59 A n interesting generalization of the nonsimultaneous network synthesis problem is derived when only a proper subset T of the node set JV have positive requirements from each other. We observe that the nodes i n TV \ T cannot simply be ignored, since it is conceivable that a l l o p t i m a l solutions to this network synthesis problem use some nodes in N\T as intermediate points. We call the nonsimultaneous network synthesis problem, w i t h n nodes and t = \T\ < n terminals, the Steiner network synthesis problem. The Steiner network synthesis problem is a proper generalization of the network synthesis p r o b l e m , since for T = TV, the two are equivalent. For the remaining of this thesis, we w i l l be chiefly concerned w i t h the Steiner network synthesis problem, since the extra generality in the Steiner network synthesis problem, compared w i t h the ordinary nonsimultaneous network synthesis problem, usually does not increase the complexity of the problem. F r o m the M a x - F l o w M i n - C u t Theorem, see e.g., F o r d and Fulkerson [50], it is clear that a given capacity vector b G 3?"' satisfies the single requirement r,.,, if and only if the capacity of every i-j cutset is at least r , j , i.e., for every subset Q C TV, Q 3 i, N\Q b(Q,N\Q) = £ b kl 3 j, > r,-,-. k€Q, leN\Q Thus, the set of a l l feasible solutions b to the Steiner network synthesis problem consists of a l l b > 0 satisfying the above inequality for all pairs i and j , 1 < i < j < n. However, a large number of these constraints are redundant, since for n > 3 and for a given proper subset Q, i.e., 0 ^ Q C TV, there are distinct pairs of nodes {«'. j ' } , {«'.J> ^ {t',/}, constraints b(Q,N\Q) such that {i,i'} C Q and > r,j and b(Q,N\Q) > r^ji C N\Q. and Therefore, one of the is implied by the other. To eliminate the redundancy, for every proper subset Q C TV, let rg = max{ r,-- : i G Q, j G N\Q ; }. T h e n , the Steiner network synthesis problem can be w r i t t e n as the following linear program: Minimize Subject T o £ d l<i<j<n i3 £ • 6, 3 b tj > r (Q,N\Q), bij > 0 1< i < j < n Q 0 ^ Q PtT C T l<i'<J<n 60 where a cutset (Q,N\Q) in is the set of edges w i t h one endpoint i n Q and the other N\Q. In chapter 3, we will consider the case when the requirement structure is sparse, be- cause there are only a few demand nodes and the rest are just intermediate nodes. We further assume that the positive requirements are equal. W h e n the number of demand nodes t = \T\ is small relative to n, it may be worthwhile to eliminate the increased complexity resulting from the intermediate nodes. T h i s is achieved using a transformation. Before o u t l i n i n g the transformation, since in Chapter 3 we are concerned w i t h the equalrequirement case, we find it convenient to represent the input to the Steiner network synthesis problem by a network G — (N,E), and the weight (length) of any edge where E 5 is equal to a\j. if the unit cost < oo, Furthermore, i n G, we will represent the demand nodes by thicklined circles. T h u s , we may interpret the Steiner network synthesis problem as the problem of finding a m i n i m u m cost subnetwork i n G, satisfying the requirements between the thicklined demand nodes nonsimultaneously. T h i s interpretation w i l l be called the Steiner network synthesis problem i n network G. N o w , the transformation can be summarized as follows. We transform the Steiner network synthesis problem i n G into a smaller network synthesis problem w i t h nodeset T a n d costs (distances) equal to the shortest (cheapest) distances in G. T h e n , we solve the smaller network synthesis problem, possibly using a linear programming algorithm. F i n a l l y , we transform an o p t i m a l solution in the smaller network synthesis problem back to the original problem. We w i l l prove, using linear programming duality, that the transformed solution is indeed an o p t i m a l solution to the original equal-requirement Steiner network synthesis problem. T h e transformation requires 0[t • n ) 2 operations, but we w i l l show, in Subsection 3.3.3., how an 0 ( n ) algorithm can be obtained for the 2 equal-requirement Steiner network synthesis problem when t < 5. 3.2 Simplifying the Equal-Requirement Case: Preliminaries Consider the Steiner network synthesis problem when the positive requirements are equal. Since the capacities are permitted to be noninteger, we can m u l t i p l y the positive requirements and the derived capacities by the same constant, thus m a k i n g all the 61 positive requirements equal to 2 units. In this section, we w i l l first present two linear p r o g r a m m i n g formulations used in the transformation, and then describe the construction of a solution to the Steiner network synthesis problem. Finally, we present two dual problems, a n d state a property of the dual solutions. 3.2.1 Linear Programming Formulations and the Transformation T h e Steiner network synthesis problem, w i t h requirements equal to 2, can be formulated as the following linear program: Minimize £ d t J • 6,j i<*<j<« (P) Subject T o £ 0^ QDT C T bi,- > 2 [Q,N\Q), kj 0 1 < i < j < n. {iJ)S(Q.N\Q) i <•'<;<»« > Alternatively, the problem can be stated as the problem of finding a m i n i m u m cost subnetwork of the network G which satisfies the requirements nonsimultaneously, where G — (N,E), E 9 if < oo, and the length (cost) of is equal t o d j. We will t refer to this formulation as the Steiner network synthesis problem in network G. Further, we let d' j be the length of a shortest (cheapest) path between demand nodes i and j i: in G. F o r the transformation, we need to define another smaller network, G' = (T, £ " ) , called the shrunken network, where the edges E' have lengths (costs) corresponding to the shortest distances (costs) i n G, i.e., d[j — d'j for the edge joining i and j. (We will i use primes to denote quantities associated w i t h G ' . ) T h e transformation w i l l be done as follows: 1. Transform the equal-requirement Steiner network synthesis problem in G into a smaller network synthesis problem i n the shrunken network G ' . 2. Solve the network synthesis problem i n G ' , possibly using linear programming. 3. Transform an o p t i m a l solution subnetwork W i n G ' back to the original problem, thus constructing a solution subnetwork W i n G . 62 We proceed by assuming that Step 1 of the transformation has been completed, and the vector a" = (d\j) of the shortest distances i n G have been determined, possibly using Dijkstra's algorithm [40]. For Step 2, we first formulate the network synthesis problem, w i t h requirements equal to 2, i n G' as the following linear program: Minimize £ d' • b'^ {•'..OCT Subject To £ 6J. > 2 (Q', Q ' ) , Q' C T, Q' = b'a > 0 {iJ}QT, T\Q a.j)e(Q'.Q') {i,j}CT. i< 3 K j where cutset (Q\ Q') is the set of edges w i t h one endpoint in Q' C T and the other in Q' = T\Q', and b\- is the capacity of edge (i,j) in (P'). N o w , we assume that (P') has been solved, and denote an o p t i m a l solution to it by b' = (b'-). Further, we denote by W the subnetwork in G' induced by the positive values of b'. Step 3 of the transformation, i.e., the construction of the subnetwork W in G from the subnetwork W in G', is as follows: for each edge (i,j) GW (with capacity 6J- > 0), we find a shortest path between i and j i n G, and let the capacity of every edge on this p a t h be equal to 6J-. A t the termination of the above procedure, the positive-capacity edges in G induce the subnetwork W. B y construction, the total cost of W w i l l be equal to the total cost of W. Further, W w i l l be feasible to the original equal-requirement Steiner network synthesis problem, but it is not obvious that W is optimal for the original problem. We w i l l prove, in the rest of this section and in the next section, using linear programming duality, that W is indeed an optimal solution subnetwork to the original equal-requirement Steiner network synthesis problem in G. 63 3.2.2 Dual Problems and the Laminarity of Dual Solutions to (P') T h e d u a l linear program to (P) can be written as follows: Maximize 2 £ SQ (Q,N\Q) (D) Subject T o £ s Q < dij 1< »<i < « {Q,ff\Q)B[ij) s Q > 0 (Q,N\Q), where SQ is the dual variable corresponding to the cutset (Q,N\Q) i n (P). Similarly, the dual linear program to (P') can be formulated as follows: Maximize (D') 2 £ S'Q, Subject T o £ s' QI < d' , { t , j } c r , « < i M i3 (Q'.<5')3(.'-j) S'Q, > o (Q',0'), where S'Q, is the dual variable corresponding to the cutset (Q',Q') i n (P'), Q = T\Q. We assume that (D') has also been solved, a n d denote the positive values of an o p t i m a l solution to (D') by { S'Q, : i — 1 , . . . , k' }. Before stating L e m m a 3.1 concerning the structure of { Q[ : i = 1 , . . . , k' }, we will state the following definitions. A family of subsets { Q,• : i — 1 , . . . , k } is said to be nested, see Cornuejols, Fonlupt, and Naddef [36], if for any i ^ j , either Q C Qj, or Qj C Qi, or Qi n Qj = 0. A family of edge { cutsets {(Qi, Qi) : i = l , . . . , f c } is said to be laminar, {Qi if the family of the subsets : i = 1,... ,k} \s nested. Lemma 3.1 ( A d a p t e d F r o m Cornuejols, Fonlupt, a n d Naddef [36, Theorem 4.9]). Let b' be an extreme solution responding to (P'). Then, the dual solution to b' can be chosen such that the associated form a laminar family. { S'Q, : i = 1 , . . . , k' } cor- cutsets { (Q[, Q[) : i = 1 , . . . , k'} • 64 Figure 3.1: G r a p h G , and point set Si. If we let b' be a solution to (P') work W, which corresponds to the o p t i m a l solution subnet- then, by L e m m a 3.1 above, we can choose { S'Q, : i' = 1 , . . . , k' } so that the corresponding cutsets { (Q' , { : i = 1 , . . . , k' } form a laminar family. To each cutset (Q , Q') in { (QJ, Ot) '• i = 1,. • • ,k! }, we will associate some cutsets 1 {(Qi,Qi) ' i = l , . . . , f c } in (P). These cutsets w i l l be generated by a modification of the D i j k s t r a a l g o r i t h m , which we will describe in the next section. F i r s t , we state the following two definitions. A point on a graph G — (N,E) is either a node of G or what we envision as a point part way along an edge, i.e., for each edge (u,v) are points on (u,v) at distance d from u and distance d uv there — d from v, 0 < d < d. uv The shortest distance between a node i £ N and a set of points S of G is denoted by d(i, S) = m i n { d(i,j) : j 6 S }, where d(i,j) is the shortest distance between i and point j e S on G. Example 3.1. Consider the graph G = (N,E) in Figure 3.1, where the distances 65 (costs) are shown on the edges. l}. T h e point set S x : j a point of G such that d(l,j) < is represented by thick line segments and a thicklined circle in F i g u r e 3.1, where d(l,Si) 3.3 Let Si = {j = d(2,S ) = 0, d(3,Si) = 1, d(4,Si) = 2, etc. • x Optimality of the Subnetwork W In this section, we w i l l describe a modified version of D i j k s t r a algorithm, and use it to construct a solution to (D) from an optimal solution to (D'). that the derived dual solution is, in fact, optimal to 3.3.1 Finally, we will prove (D). A Modified Dijkstra Algorithm and the Construction of a Solution to (D) G i v e n a point set S, referred to as the root set, consisting of some points on network G , the modified D i j k s t r a algorithm finds the shortest distances between all the nodes in N\S and the point set S as follows: • Determine node subsets { Q(S,) : i = 1 , . . . , m } w i t h associated variables { SQ(S.) i = 1 , . . . , m } and point subsets {Si : i' = 0 , . . . , m }, such that Q(Si) : contains all the nodes in S, and So = S. • Let Vi C N\Q(Si) let SQ(S,) Q{S ) 2 = d(v,S), = be the set of nodes v such that d(v,S) Si = S U {j 0 : is m i n i m i z e d , and j a point of G , d(j,S) < SQJSJ) }, and Q{Si)uVi. • In general, for / = 2 , . . . , m , let Vj C A \<5(S;_ ) be the set of nodes v such that r 1 d(t;,S;_i) is m i n i m i z e d , and let G , d(j, S;_i) < Q(S ) m 5^(5,) SQ^S,) = }, and Q(Si ) +x d(u,Sj_i), Si = S;_i U {j : j a point of = Q(Sj) U V;. T h e algorithm terminates when = N. T h e cutsets { (Q(S,), Q(S,)) : i = 1 , . . . , m }, referred to as the Dijkstra cutsets around S, are by construction laminar. E x a m p l e 3.2. S = {j A g a i n consider the network displayed in Figure 3.1, and recall that '• j a point of G , d ( l , j ) < l } . F r o m the modified D i j k s t r a algorithm, we get 66 S 0 = S and Q(Si) and Q(S ) 2 = {1,2}; s t ) Q = {1,2,3}; s > Q S2) Sl = 1, Si = S U {j = 1, S 0 2 = Si U {j : j a point of G , d(j,S ) 0 < 1}, : j a point of G , d ( i , S ) < l } , and x Q(S ) = { 1 , 2 , 3 , 4 } ; etc. • 3 We w i l l refer to the derived point sets { S; : i = 0 , . . . , rn } as the enhanced root sets, and we define the frontier Fi of an enhanced root set S, to be the set of points of G not in S , but at a distance zero from S,-. Some of the frontiers for Example 3.2 t above are shown i n Figure 3.1, where to facilitate recognition, the frontiers are shown as almost connected contours. We observe that the construction of the enhanced root sets S{ in the modified D i j k s t r a algorithm is such that if a point X ; £ S, is on an edge (u,v), then either all the points between u and x, or all the points between v and x, on (u,v) belong to S . t Therefore, the intersection of S, and (u,v) consists of at most two disjoint intervals, one containing u and the other containing v. If the intersection consists of one interval, let x; be the unique point i n the intersection of F,-, the frontier of Si, w i t h (u, v) which is at distance zero from the interval. Otherwise, the intersection consists of two disjoint intervals, which we are not interested i n , because Q(Si), the set of nodes of Si, w i l l contain both u and v. T h i s implies that the cutset (Q(S,-),Q(S,-)) w i l l not contain (u,v), and, hence, later in (3.2) we can ignore this case. It follows by the construction of the modified D i j k s t r a a l g o r i t h m that SQ(Si) < l{xi-\,Xi), t = where /(x,-_i,x,-) is the length of the interval [x,-_i,x -] on (u,v). t Now we can explain how to construct a solution { SQ : i = 1,... { the o p t i m a l solution { S'Q, : i = 1 , . . . , k' } to (D') (3.1) l , . . . , m ,k} to (D) using which corresponds to a laminar family of cutsets { (Q[, Q\) : i = 1,..., k' }. F i r s t , note that { Q\ : i = l,...,k'}, being a nested family of nodesets, can be partially ordered by inclusion, and, thus, can be represented by a rooted tree such that Q\ is a descendant of Q'j if Q[ C Q'j, where a descendant of a node u o n the rooted tree is any node v such that the unique simple path between v and the root contains u. We w i l l proceed by scanning the rooted tree from b o t t o m up, i.e., at any stage, 67 only the nodes whose descendants have already been scanned are scanned (this is called 'post-order scan' i n Cornuejols, Fonlupt, and Naddef [37]). To scan the node of the rooted tree corresponding to a nodeset Q' G { Q\ • i = 1 , . . . , k'}, if Q' has no descendants, then let its root set S be Q', a n d let the frontier F of S be S itself. Otherwise, let the root set S be the union of the largest (reduced) enhanced root sets of its children (i.e., immediate descendants), where by the largest (reduced) enhanced root set associated w i t h a node of the rooted tree we mean the largest (possibly reduced) enhanced root set generated, while we scan that node, by the modified D i j k s t r a algorithm before we 'interrupt' i t . T h e reason for the interruption w i l l be clear i n the next paragraph. G i v e n the root set S associated w i t h Q' and given S'Q,, we will use the modified D i j k s t r a a l g o r i t h m to generate the D i j k s t r a cutsets { (Q(Si), Q{Si)) : i = 1,..., m }, the associated variables { SQ(S<) : i = l , . . . , m } , and the point sets { S, : i = 0, . . . , m } . However, we w i l l interrupt the modified D i j k s t r a a l g o r i t h m as soon as £ T ceeds S'Q,, i.e., when we reach an integer k which satisfies b o t h Y^,i=i Q(s ) S l S Q{Si) reduce S k > s' . Ql We w i l l possibly reduce s ( ) Q Sk t o S -i U { j : j a point of G, d(j,Sk-i) k = 1 SQ(S,) ex- < 'Q' S A N D to s' , - zZi=i Q(s,)> a n d possibly 5 Q < SQ{s ) } a n d we w i l l refer to the k 5 (possibly) reduced S as the largest (reduced) enhanced root set associated w i t h Q'. k A t the t e r m i n a t i o n of the scanning, the set of all D i j k s t r a cutsets { (Qi,Qi) '• i = 1 , . . . , k } and the corresponding (possibly reduced) values { SQ. : i = 1 , . . . , k }, generated before the a l g o r i t h m was interrupted at each stage, are the solution to (D) which we were seeking. We note that, by construction, {{Qi, Qi) : i = l,...,k} is also a laminar family of cutsets, a n d that Qe{Qi : i=l,...,k} E x a m p l e 3.3. <?'£{<?; : t= l,...,*:'} We provide in F i g u r e 3.2 the costs dj-, an o p t i m a l p r i m a l solution subnetwork i n G', a n d an o p t i m a l dual solution { S'Q, : i = 1,. :.,k'} {{Q'i,Qi) w i t h cutsets '• i — 1, - - - , A;' }, for the network G', derived from the graph displayed i n F i g u r e 3.1 when the nodes 1,5,7,9,12, and 14 are the only demand nodes which have 2 units of requirements from each other. In Figure 3.2, one thick line represents half a unit capacity, a n d two thick lines represent one unit capacity i n the p r i m a l optimal 68 Figure 3.2: A n O p t i m a l Solution Subnetwork in G', and the D i j k s t r a Cuts. 69 Figure 3.3: A n O p t i m a l Solution Subnetwork in G, and the D i j k s t r a Cuts 70 subnetwork. Furthermore, Q[ = { l } , s' = 3; Q' = {7}, s' Ql 2 Q\ = { 7 , 9 } , s' , = 2; Q' = {14}, ^ , = 2; Q Q's = { }> t 3 = {1,14}, 5 = 1 5 = \\; Q' = {9}, s' , = 2\; Ql q = i ; Q' = {12}, sj,, = i f ; 7 and Q' = {5,12}, s^, = 1. 9 Figure 3.3 displays, i n thick lines, the derived o p t i m a l p r i m a l solution subnetwork in G, and the derived o p t i m a l dual solution { SQ : i — 1 , . . . , k } w i t h cutsets { (Qi, Qi) : i = { 1 , . . . , k }, obtained from the solutions displayed i n F i g u r e 3.2 above. In F i g u r e 3.3, Qi = {1,2}, s = 1; Q = { 1 , 2 , 3 } , s Ql 2 = 1; Q = { 1 , 2 , 3 , 4 } , SQ = 1; Q = F = {7}; Q = Q2 3 { 6 , 7 } , SQ^ = 1; Q = { 6 , 7 } , reduced, 6 Q = { 8 , 9 } , reduced, s 9 Qo = 1; *Q 1 4 Qn s = f; Q 1 0 5 Q 3 7 = h l = = 5 8 = §; Q Q l 0 = f; <? = F Qi2 13 = |; Q 1 6 ( }5 'Sis = { }> reduced, s 5 7 = {6,7,8,9,10}, s 5 < 3 i s 4 = f; Q = F = {9}; Q = { 8 , 9 } , s g = { 6 , 7 , 8 , 9 , 1 0 , 1 1 } , reduced, s = 2; Q I B = { 1 , 2 , 3 , 4 , 1 3 , 1 4 } , 4 1 3 n 5 Ql0 = {6,7,8,9,10,11}, = {14}; Q = JF = {12}; Q 16 = i f ; and Q 20 = 2; Qs 1 7 u = {13,14}, = {12}, reduced, = { 5 , 1 2 } , s , „ = 1. Q • 3.3.2 Feasibility of the Derived Dual Solution Since the p r i m a l solution subnetwork W is feasible, and since the objective function value of the p r i m a l (P) and the dual (D) problems are equal, by the linear programming duality it suffices to prove that the dual solution is feasible. B y construction, SQ > 0, Q £ { Q,; : i = 1 , . . . , A:}. It remains to prove that E L e m m a 3.2. Proof. SQ<c (u,v)EE. uv The system of inequalities (3.2) (S.S) above holds. Suppose u, b u t not v, is contained in the nodesets Q (,) : i = 1 , . . . , v, and v, u but not u, is contained i n the nodesets Q (i) : i = 1 , . . . ,v, among the derived nodesets v Qi : i = 1,..., k. Since { Qi; : i = 1 , . . . , k } is nested, we can assume that Q (i) C Q (i+i), u i = l,...,v (reduced) — 1, and that Q (i) C Q (i+i), v v i = \,...,v enhanced root sets be {£„(,•) : i = l,...,v} — 1. L e t the corresponding a n d {S ^) : i = v respectively. A s described earlier, we only need t o consider those (reduced) root sets w h i c h intersect (u,v) i n one interval. i = l , . . . , v } a n d {/„(,) : i = u enhanced T h u s , let these intervals be {I {i) '• respectively. u B y (3.1) a n d by the fact that 71 Figure 3.4: M i (left), M 2 (center), and M these (reduced) enhanced root sets are nested, we get that i = l,...,v, I v(0) c, uv and that = v. Therefore, SQ(5„ ) ( i ) < £Q Q,O)9(U,„) ; ( 3 (right). SQ(S - ) < / ( / « ( » ) ) — U(I ( ^"(t-i))? - / ( / „ ( , • - ! ) ) , i = l , . . . , i > , where J ( ) = u and u S Q = H=i ^(s.^J + E ^ i ^(5„ ( l ) ) 0 < /(/„(„)) +'(V)) ^ w h i c h completes the proof. 3.3.3 • Implication of the Transformation We first need the following definitions. A graph G reduces to a graph H if we can derive H from G by a sequence of edge deletion, isolated-node deletion, and edge contraction, where edge contraction is the operation of shrinking an edge (u,v) onto one of its endpoints, say u, and replacing each edge (w,v), w ^ u , by an edge [w,u). M i , M , or Mz-free if it cannot be reduced to the graph M i , nor M nor M 2 2 a n d N a d d e f [49] for more details), where M i , M 2 and M 3 3 A graph is (see Fonlupt are displayed in Figure 3.4. A Steiner tour is a cycle which visits every node (in T) at least once. L e m m a 3.3 ( A d a p t e d from Fonlupt and Naddef [49]). (P') to M i , M , and M -free restricted 2 z The extreme solutions graphs form Steiner tours. to • Since the costs (distances) rfj • of the edges in G' are shortest distances i n G, they satisfy the triangle inequality. Therefore, L e m m a 3.3 above implies that for t < 5, there exists a solution to (P') w h i c h induces a H a m i l t o n i a n cycle, where we recall that a H a m i l t o n i a n cycle is a cycle which visits each node in T exactly once. Since there are at most 4!/2 H a m i l t o n i a n cycles, one can enumerate all of them, and subsequently find an 72 o p t i m a l solution. T h i s procedure avoids using linear programming to solve (P'). Thus, we obtain the following result: Corollary. For t < 5, the equal-requirement can be solved in 0 ( 5 ! • 3.4 Steiner network synthesis problem ra ). • 2 Summary and Further Research for the Transformation In C h a p t e r 3, we were concerned w i t h a transformation to simplify the computations required to solve the Steiner network synthesis problem, we considered the case when the requirement structure was sparse, because there were only a few demand nodes and the rest were just intermediate nodes, and when the positive requirements were equal. For this case, we found that the linear programming formulation of the Steiner network synthesis problem could be simplified by employing a transformation procedure, which also implied that, when the number of demand nodes is less than or equal to five, the equal-requirement Steiner network synthesis problem can be solved i n 0 ( n ) . 2 We only considered the case of equal positive requirements when we examined the sparse requirement structures, because the transformation does not easily extend to the general requirement case. However, the transformation appears to be general enough to apply to many other problems arising in networks and combinatorial o p t i m i z a t i o n . Chapter 4 THE STEINER NETWORK S Y N T H E S I S P R O B L E M IN S O M E SPECIAL GRAPHS In this chapter, we w i l l consider the case when the solution network to the Steiner network synthesis problem has to be embedded in (i.e., restricted to) some special graphs, namely trees, rings, series-parallel graphs, or M 2 and M - f r e e graphs. T h i s is 3 equivalent to the case when the unit costs of the edges, not in these special graphs, are very large (infinity), since if is infinity then we can remove variable 6,-y from the linear p r o g r a m m i n g formulation of the Steiner network synthesis problem, presented in Section 3.1 above. We call the linear programming formulation remaining after all the redundant variables are removed as the reduced linear program. For brevity, we sometimes refer to the Steiner network synthesis problem, when the solution subnetwork has to be embedded in a special graph, as the Steiner network synthesis problem in the special graph. Furthermore, by an extreme solution to the Steiner network synthesis problem in some special graphs, we mean an extreme solution to the feasible set of the reduced linear program associated w i t h the Steiner network synthesis problem in that special graph. We note that, in this chapter, we do not impose any restrictions on the requirement structure. A summary of this chapter is as follows. F i r s t , i n Section 4.1, we w i l l describe simple algorithms for the two easy cases when the solution subnetwork has to be embedded i n a tree or in a r i n g (cycle). A r i n g (cycle) is a special case of series-parallel graphs, but its simpler structure leads to a more efficient algorithm. We w i l l then state some preliminary results for the Steiner network synthesis problem in the series-parallel graphs, and show how the dynamic programmig type algorithm 73 74 of B e r n , L a w l e r , and W o n g [14] can be used to solve the equal-requirement case. In Section 4.2, we w i l l modify the dynamic programming type algorithm i n order to solve the general requirement Steiner network synthesis problem in the series-parallel graphs, while in Section 4.3, we w i l l briefly describe how the same algorithm can be applied to solve the Steiner network synthesis problem in the more general case of M 2 and M -free 3 graphs. T h e reason for the existence of combinatorial algorithms for the Steiner network synthesis problem i n the above special graphs is that all extreme solutions to any of the reduced linear programs have integer or half-integer values. We w i l l demonstrate, by an example, that the Steiner network synthesis problem i n a graph reducible to M 2 or M 3 may have extreme solutions w i t h arbitrary fractional values, i m p l y i n g that a polynomial combinatorial algorithm is not likely to exist for the Steiner network synthesis problem in more general graphs. 4.1 Trees and Rings; Series-Parallel Graphs: Preliminaries and the Equal Requirement Case In this section, we w i l l first describe simple (combinatorial) algorithms for the Steiner network synthesis problem when the solution subnetwork is restricted to a tree or a ring (cycle). T h e n , after some preliminary results and definitions, we w i l l describe how the dynamic p r o g r a m m i n g type of B e r n , L a w l e r , and W o n g [14] can be used to solve the equal-requirement Steiner network synthesis problem i n series-parallel graphs. 4.1.1 Trees and Rings F i r s t consider the simple case when the o p t i m a l solution subnetwork has to be embedded in a tree T. For each edge where T , k = k of edge £ T, let its capacity b^ = max{ r uw : u £ T, w £ Tj }, is the connected subtree containing k w h i c h remains after the removal from the tree. If all the unit costs are positive, 6 = (bij) is the optimal solution. We note that the nonnegative costs play no role here, and that the complexity of the above a l g o r i t h m is 0 ( n + t ), where t = | T | , and T is the set of demand points. 2 Now, consider the n o n t r i v i a l case of a ring (or cycle). ments rij i n a nonincreasing order, i.e., r\, r ,..., r , w i t h 2 k the following procedure provides an o p t i m a l solution. We arrange the require> Tj for i < j. In this case, 75 • Starting w i t h a zero capacity network, raise to ri the capacity of every edge on the shorter (cheaper) of the two simple paths on the ring between the pair of nodes which have requirement r\. • For r j , i = 2 , . . . k, compute the cost of alternatives 1 and 2 below, and choose alternative 1 and stop if its cost is not more than alternative 2's cost, else choose alternative 2. 1. In the current solution, raise the capacity of all zero-capacity edges to r,-/2, and reduce the capacity of all positive capacity edges by r j2. i 2. Set the costs of the positive capacity edges in the current solution temporarily to zero, and raise to r, the capacity of a l l zero-capacity edges on the shorter (cheaper) of the two simple paths on the ring between the pair of nodes which have requirement rj. We can terminate the algorithm the first time alternative 1 is chosen, since all the succeeding requirements in the ordered list, which are not larger, w i l l be satisfied by the current solution. Since the network obtained at the end of each iteration is o p t i m a l for all the requirements considered up to and including that iteration, it follows by induction on the number of iterations that the above algorithm provides an optimal solution. T h e complexity of the above algorithm is 0(nk + t ), 2 where k is the number of necessary positive requirements, which by Gomory and H u [58] will not be larger than t — 1, i.e., the number of edges in a M a x i m u m Requirement Spanning Tree. 4.1.2 Series-Parallel Graphs: Preliminaries and the Equal Requirement Case In this subsection, after some definitions, we present a theorem and some other results concerning the Steiner network synthesis p r o b l e m in series-parallel graphs. T h e n , we show how the dynamic programming type a l g o r i t h m of B e r n , Lawler, a n d Wong [14] can be used to solve the equal-requirement case. F o r the rest of this section and most of the following section, we assume that the requirement structure is connected. However, in Subsection 4.2.3, we w i l l relax this assumption. 76 Recall that a series-parallel graph can be obtained by a sequence of node insertion and edge duplication from an edge (see e.g., [14,36,74,153]), where node insertion is the operation of converting an edge (u,v) into a path (u,u>), (w,v) by inserting a node w in (u,v), and edge duplication is the operation of adding one more edge between u and v. The above defines a series-parallel graph which is also referred to in the literature as an 'edge' series-parallel graph, see e.g., [14,153]. There are two alternative characterization of series-parallel graphs, the 'two terminal' recursive construction and the excluded minor characterization. First, the 'two terminal' recursive construction, see e.g., [14,74,153], of a series-parallel graph is as follows: 1. A single edge (u,v) is a series-parallel graph with two terminals u and v. 2. If Gi and G are series-parallel graphs with respective pairs of terminals 2 { « i , i > i } and {^2,^2}, then so are their series and parallel compositions, where in the series composition, v coincides with u , and the composed graph Gi © G 2 t terminals u x has two 2 and v , and in the parallel composition, u coincides with u , v 2 2 x x coincides with v , and the composed graph Gi © G has two terminals u and v . 2 2 x x The 'two-terminal' recursive construction of a series-parallel graph G can be represented as a binary decomposition tree, see Valdes, Tarjan, and Lawler [153], where each external node (leaf) of the tree represents a node in G, and each internal node is labeled S or P and represents the series or parallel composition of the series-parallel graphs represented by the subtrees rooted at the children of the node. Each component Gi of G , generated in the above process, is associated with two nodes {u,, v,-} such that every simple path connecting a node in G , with a node in G \ G , must contain either w, or u,-. Thus, a binary decomposition tree, which can be constructed in linear time, see [153], provides a concise description of the structure of a series-parallel graph. The third characterization of a series-parallel graph is by excluding a minor. First we need some definitions. A node v is a cut node or one-node cutset of G if the removal v, and all the edges incident to it, from G disconnects G . Further, G is biconnected if G has no cut node. Dirac [41], and independently Duffin [45], proved that a biconnected graph is series-parallel if and only if it does not have K4 (i.e., the complete graph on 4 nodes) as a minor (see Subsection 3.3.3 or 4.3.1 for the definition of a minor). Next, we will prove that the Steiner network synthesis problem can only have integer 77 or half-integer extreme solutions when the solution subnetwork is to be embedded in (i.e., restricted to) series-parallel graphs. This generalizes a result of Cornuejols, Fonlupt, and Naddef [36] who, in effect, proved that the network synthesis problem, w i t h requirements equal to 2 and restricted to series-parallel graphs, has integer extreme solutions. We note that all the requirements are assumed to be integer. Theorem 4.1. All extreme solutions to the reduced linear program associated with the Steiner network synthesis problem in any series-parallel half-integer graph have only integer or values. ( B y Induction on the N u m b e r of Edges i n Series-Parallel G r a p h s ) . Proof If the series-parallel graph is an edge, it is evident that the unique extreme solution to the reduced linear program associated w i t h the Steiner network synthesis problem in the edge has an integer value. N o w , suppose that all extreme solutions to the reduced linear program associated w i t h the Steiner network synthesis problem i n any m-edged (i.e., w i t h m edges) series-parallel graphs have integer or half-integer values. We have to prove that all extreme solutions to the reduced linear program associated w i t h the Steiner network synthesis problem in any (m+l)-edged series-parallel graph have integer or half-integer values. Let G(m + l ) be such a (m + l)-edged series-parallel graph. B y the definition of series-parallel graphs, G(m + 1) must be obtained from a m-edged series-parallel graph G(m) by either node insertion or edge duplication. For brevity, we w i l l refer to the set of constraints in the reduced linear program associated w i t h the Steiner network synthesis problem in G(m) (resp., G(m + 1)) as the old (resp., new) system. Let b(m) (resp., b(m + 1)) be a m (resp., m + l ) - d i m e n s i o n a l vector (one dimension for each edge) satisfying the o l d (resp., new) system, and let b(m + l ) be any extreme solution to the new system. We have to prove that b(m + 1) has only integer or half-integer values. Consider the following two cases: • Edge duplication: Suppose that edge e' i n G(m + 1) is a copy of edge e in G(m). T h e n , every constraint in the new system containing e' also contains e. Since, b(m + l ) is an extreme solution, it follows that at most one of b (m + 1) and e b i(m + 1) w i l l be positive. Hence, by i n d u c t i o n , b(m -+- 1) must have integer or e half-integer values. • Node insertion: Suppose a node w is inserted in an edge e = (u,v) of G(m), 78 constructing edges e' = (u,w) and e" = in G(m + 1). If w is not a demand (VJ,V) node, i.e., it is only an intermediate node, then the new system consists of two copies of the old system, one copy w i t h b i(m + l ) , the other w i t h b »(m e e + 1) replacing b (m). T h e n , we must have that 6 »(m + l ) = 6 » ( m + l ) . N o w , we define e e e a solution b(m) to the old system using b(m+l) / 6 G(m), and b (m) e as follows: bi(m) — bi(m+l),l ^ e, — b i(m + 1) = 6 » ( m + l ) . T h e n , 6(m) must be an extreme e e solution to the o l d system, w h i c h by i n d u c t i o n has integer or half-integer values. T h u s , b(m + l) also has integer or half-integer values. N o w , suppose w is a demand node. In this case, in the new system (a) the two copies of the o l d system, one w i t h b i(m + 1), the other w i t h 6 » ( m + l ) replacing b (m), may have larger right hand e e e sides (reflecting the additional requirements of to), and (b) there is the additional constraint b i(m + 1) + 6 » ( m + 1) > r , e e r w = m a x r ^ , i 6 G(m + 1), i=t w. To w t proceed w i t h the proof, we need to revise the requirement structure such that the two copies of the o l d system w i l l have the same right hand side as the (revised) old system. Such a revision is always possible, and can be obtained as follows: for each requirement r t u l , if b i(m + 1) = S »(m + 1), we create two requirements iu {= iw), if i 7^ u, and r r (— r ), r iv iu if i ^ v; otherwise, if 6 » ( m + 1) > b n(m + 1), iw we create a requirement r a requirement r e e iv (= r ), e e (= r , ) , if i ^ v, or else, if b i(m + l ) < fe «(m + 1), w e e if i ^ u. We w i l l refer to the set of constraints in the iw reduced linear program associated w i t h the Steiner network synthesis problem, w i t h the revised requirement structure, i n G(m) as the revised old system. N o w , we define a solution b(m) to the revised o l d system, using b(m + 1 ) , as follows: 6;(m) = bi(m +1), / ^ e, I 6 G(m), and b (m) = 6 <(m + 1). Consider the following e e two cases: 1. If b i[m + 1) = b n(m + 1), then the new system w i t h b(m + 1) = b(m + l ) is e e just like the revised old system w i t h b(m) = b(m + 1), w i t h the exception of the a d d i t i o n a l constraint b i(m + 1) + 6 » ( m + 1 ) > e - e r. w If b i(m + l ) + b n(m + 1) = r , then b(m) must be an extreme solution e w e to the revised old system, since b(m + l ) is an extreme solution to the new system, and the set of feasible solutions to the revised old system has one dimension less than that of the new system. — If b >(m + l ) + 6 » ( m + 1) > r , then 6(m) must be an extreme solution to e e w 79 the revised old system, or else, b(m + 1) cannot be an extreme solution to the new system. Therefore, in either of the above two cases, by induction, b(m) has integer or half-integer values, implying that b(m + 1) also has integer or half-integer values. 2. Suppose, without loss of generality, that must have that the inequality we can reduce b i(m e b i(m e b i(m e + 1) > 6 »(ra + 1). T h e n , we e + l ) + 6 » ( m + 1) > r e w is tight, or else, + 1), because as far as demand nodes, other than w, in G(m + 1) are concerned, only the smaller of b i(m + l ) a n d b >i(m + l ) e e could possibly be a 'bottleneck'. However, if we can reduce b i(m e + 1 ) , then b(m + 1) could not have been an extreme solution to the new system. So, suppose b i(m e + l ) + 6 » ( m + 1) = r . N o w , by the construction of the revised e w requirement structure above, b(m) must be an extreme solution to the revised old system. T h u s , by induction, b{m) has integer or half-integer values, and, in particular, S /(m + l ) = b (m) is integer or half-integer. Furthermore, from e e equation 6 » ( m + l ) = r — e w b i(m e + 1), we have that b n(m e or half-integer. + 1) is also integer • It is a simple corollary to T h e o r e m 4.1 above, or alternatively see Cornuejols, Fonlupt, and Naddef [36], that when the requirements are equal t o 2, all the extreme solutions to the reduced linear program associated w i t h the Steiner network synthesis problem i n series-parallel graphs have integer values. For the rest of this section, we w i l l consider the equal requirement case. The results obtained for this case will be used in the next section to solve the general requirement case. Recall that in the equal-requirement case, we can assume that a l l the requirements are equal to 2, because we can m u l t i p l y all the requirements and all the derived capacities by the same constant. T h e a l g o r i t h m we w i l l use here to solve the equal-requirement Steiner network synthesis p r o b l e m is similar to that given by Ratliff and Rosenthal [122], who considered the Steiner tour problem i n rectangular graphs, i.e., graphs i n which a l l the simple cycles have an even number of edges. T h u s , our a l g o r i t h m is related to the dynamic p r o g r a m m i n g type algorithm of B e r n , Lawler, and Wong [14], who generalized, among 80 other things, Ratliff and Rosenthal's result to Steiner tour problem in any recursively constructed graphs which require a finite number of composition rules. Before outlining the algorithm, we need the following definitions and preliminaries. A connected subgraph G = (JV ,E' ) of a connected graph G = (N,E) { i t of G if there is a pair of nodes {u,v} node i n iV, w i t h a node in N\(Ni is a component in Ni such that every simple p a t h connecting a U {u, v}) contains either u or v. We w i l l refer to {u, v} as a two-node cutset in G. We note that the above definition allows a single edge (u,, v,-) a n d its two endpoints u , , i>, to be a component of G , and the pair of nodes {u,, v,} to be a two-node cutset in G. Recall that we referred to the subnetwork induced by an extreme solution to the reduced linear program associated w i t h the Steiner network synthesis problem in some special graphs as an extreme solution subnetwork in G. We now need to introduce some more notation for the restriction of an extreme solution a n d an extreme solution subnetwork in a component G . T h u s , we w i l l refer to the t restriction of an extreme solution to a component G , as a partial extreme solution in G , , and we w i l l refer to the subnetwork induced by a p a r t i a l extreme solution in G , as a partial extreme solution subnetwork ( P E S S ) in G , . T h e following l e m m a states that the P E S S ' s in any component of a series-parallel graph, associated w i t h the Steiner network synthesis problem, w i t h requirement equal to 2, i n the same series-parallel graph, can be categorized into 7 equivalence classes or types. A type is identified by a 3-tuple ( a , / ? , ^ ) , where a denotes the degree parity of node u, i.e., whether the s u m of capacity of the edges incident to u is even (denoted by E ) , odd ( U ) , or zero (0), /3 is the degree parity of node v, and 7 shows the number of connected components of the P E S S , zero components (denoted by 0 C ) , one component ( I C ) , or two components ( 2 C ) . L e m m a 4.1. Partial a series-parallel graph G, associated requirements (E,0,1C), extreme solution subnetworks with the Steiner network synthesis problem, equal to 2, in G, are of the types (equivalence (0,E,1C), (E,E,2C), (0,0,0C), or (0,0,1C). in any component G , of classes) (E,E,1C), with (U,U,1C), • Since, as a consequence of T h e o r e m 4.1 above, the extreme solutions to the reduced linear p r o g r a m associated w i t h the Steiner network synthesis problem, w i t h requirements equal to 2, in series-parallel graphs must have integer values, it follows that L e m m a 4.1 above can be proved in a similar manner to that given by Ratliff and Rosen- 81 <u) (u) (u) ® (u) ® ® £ <j 9 <!> o v H M } o» © (X) d) ® ® Figure 4.1: Types i , i i , i i i , i v , v, v i , and v i i (from left to right) of P a r t i a l Extreme Solution Subnetworks i n a Simple P a t h Associated w i t h the Steiner Network Synthesis P r o b l e m , w i t h Requirements E q u a l to 2, in a Series-Parallel G r a p h . t h a i 1122]. A complete proof is easy but quite lengthy, and is omitted here. If the component Gi is a simple p a t h , then the 7 types of partial extreme solution subnetworks w i l l have the simple configurations displayed in Figure 4.1. In this figure, ordinary dots may represent some intermediate nodes (not shown), bold dots may represent some demand nodes (not shown), and the shown demand nodes are thicklined circles. For brevity, we w i l l be referring to these configurations as type i , type i i , . . . , and type v i i . A n Algorithm for the Steiner Network Synthesis Problem, with Requirements equal to 2, in a Series-Parallel Graph G Conceptually, the a l g o r i t h m can be described as follows: • Discard the degree 2 nodes of G by using a sequence of the reverse operation to node insertion, to get G ' , referred to as the reduced graph of G . T h e n , construct 82 Table 4.1: T h e Series Composition M a t r i x (E,E,1C) (U,U,1C) (E,0,1C) (0,E,1C) (E,E,2C) (0,0,0C) (0,0,1C) (E,E,1C) (U,U,1C) (E,0,1C) (0,E,1C) (E,E,2C) (0,0,0C) (E,E,1C) (U,U,1C) (E,E,2C) (0,E,1C) (E.E.2C) (0,E,1C) (U,U,1C) (U,U,1C) (E.0.1C) (E,E,2C) (E,E,2C) (E,0,1C) (E,E,2C) (E.O.IC) (0,0,1C) (0,E,1C) (0,0,0C) (0,0,1C) (0,0,1C) (0,0,1C) (0,0,1C) (0,0,1C) a binary decomposition tree of G ' in O(n) (see e.g., Valdes, Tarjan, and Lawler [153]). • Use post-order scan (i.e., scan only the nodes of the binary decomposition tree whose descendants have already been scanned) in order to find a best partial extreme solution subnetwork ( P E S S ) of each type, at each internal node of the binary decomposition tree, by composing (in series if the node is labelled S, i n parallel if labelled P) the best P E S S in the components represented by the subtrees rooted at the children of the node. The series and parallel compositions are governed by the rules given in the composition matrices. A t the termination of scanning, we choose the cheapest of the 7 types of P E S S ' s w h i c h is also feasible. For i l l u s t r a t i o n , see E x a m p l e 4.1. below. T h e complexity of scanning is 0 ( 7 • 3 (2n — 3)) = O ( n ) , since (a) at each internal node, there are at most 7 ways of 2 composing a particular P E S S from the best P E S S ' s i n the components represented by the subtrees rooted at the children of the node, (b) there are at most 7 different types of P E S S ' s , (c) and there are at most 2n — 3 internal nodes in the binary decomposition tree. The series and parallel composition matrices in the above algorithm, which are similar to those given by Ratliff and Rosenthal [122], are displayed in Tables 4.1 and 4.2, respectively. In Table 4.1, the left c o l u m n contains the types of P E S S ' s in the component G x (left) (with terminals u and w), the top row contains the types of P E S S ' s in the (right) component G 2 (with terminals w and v), and the other cells contain types of P E S S ' s i n the series composition G © G x 2 (with terminals u and v), where the empty 83 Table 4.2: T h e Parallel C o m p o s i t i o n M a t r i x (E,E,1C) (U,U,1C) (E,0,1C) (0,E,1C) (E,E,2C) (0,0,0C) (0,0,1C) (E,E,1C) (E,E,1C) (E,E,1C) (E.E.1C) (E,E,1C) (E,E,1C) (E,E,1C) (U,U,1C) (E,E,1C) (E,E,1C) (U,U,1C) (U,U,1C) (U,U,1C) (U,U,1C) (E,0,1C) (E,E,1C) (U,U,1C) (E.0.1C) (E.E.2C) (E,E,2C) (E,0,1C) (0,E,1C) (E.E.1C) (U.U.1C) (E,E,2C) (0,E,1C) (E,E,2C) (0,E,1C) (E.E.2C) (E.E.1C) (U,U,1C) (E,E,2C) (E,E,2C) (E,E,2C) (E,E,2C) eg e 2 (0,0,1C) (0,0,1 C) C5 w (o,o,ic) (0,0,0c) (E,E,1C) (U,U,1C) (E,0,1C) (0,E,1C) (E,E,2C) (0,0,0C) 2 W 2 w 2 w e 6 ei2 en 9 2 F i g u r e 4.2: A Series-Parallel G r a p h (left), and its Reduced G r a p h (right). cells indicate infeasible series compositions. Similarly, in Table 4.2, the left column contains types of P E S S ' s i n the (left) component Gi (with terminals U\ a n d i>i), the top row contains types of P E S S ' s i n the (right) component G 2 (with terminals u and v ), 2 and the other cells represent types of P E S S ' s i n the parallel composition G © G x 2 2 (with terminals u\ and V\). T h e following example illustrates the above algorithm. Example 4.1. Consider the left graph i n Figure 4.2, where the costs (or distances) dij are shown on the edges, and the demand nodes are thicklined circles. T h i s graph, w h i c h is similar to that i n Ratliff and Rosenthal [122], is easily seen to be series-parallel. D i s c a r d i n g the degree 2 nodes, we get the reduced graph w i t h edges e l5 . . . , e , displayed X2 on the right of Figure 4.2. A binary decomposition tree for the reduced graph is displayed 84 1 2 3 4 5 6 7 8 9 10 11 12 Figure 4.3: A B i n a r y Decomposition Tree for the Reduced G r a p h i n F i g u r e 4.2. in Figure 4.3, where a leaf node is labelled the same as the edge it represents, and an internal node is labelled S or P if the subtrees rooted at the children of the node are composed i n series or parallel, respectively. We have also assigned a number to all internal nodes, and for clarity, also to the nodes labelled t x pattern of scanning. and e , to indicate the 12 We w i l l scan the binary decomposition tree from left to right, starting at 1 and finishing at 12. T h e results of compositions are shown in Table 4.3, where the top row specifies the stage of the dynamic programming type algorithm w h i c h also corresponds to the numbers assigned to some of the nodes in the binary decomposition tree. T h e left column of Table 4.3 specifies the types of P E S S ' s , and each of the other cells contains a 3-tuple a,/?,"y, where a is the cost of a best P E S S of its row type upto and including its stage, /? is the type(s) of best P E S S ( s ) in the left component, and 7 is the type(s) of best P E S S ( s ) in the right component. If there are more than one type of best P E S S ' s in the left and the right component, to avoid confusion, we can use a , / ^ , ^ ; 02,12', etc. We note that, in this example, best P E S S i n left component is a best-upto-the-previous-stage composed P E S S , whereas best P E S S i n the right component is a best P E S S in a simple p a t h (see F i g u r e 4.1). For brevity, /? w i l l take values 1 , 2 , . . . , and 7 representing the types ( E , E , l C ) , . . . , ( 0 , 0 , I C ) , respectively, and 7 w i l l take values i , i i , . . . , and v i i for the types of P E S S ' s in a simple path, displayed in F i g u r e 4.1 above. A l s o , we ignore, in this example, the last two rows of the table corresponding to the types (0,0,0C) and ( 0 , 0 , I C ) , because every left component and the last right component contain at least a demand node. Stage 12's c o l u m n in Table 4.3 contains the cost of best complete extreme solution subnetworks of each type, i n a d d i t i o n to the information necessary for constructing these subnetworks by backtracking. We note that, i n general, only types ( E , E , 1 C ) , ( E , 0 , 1 C ) , ( 0 , E , 1 C ) , and 85 Table 4.3: T h e Computations for E x a m p l e 4.1 Stage 2 1 3 4 5 6 42, l , i 38, 2, ii 38, 3, i 38, 4, vi 52, 5, i 53, 2, ii 53, 3 or 4, ii 62, 3, iii 62, 4, iv 56, 3 or 4, v 57, 1, i 55, 1 or 2, ii 53, 1, vi 57, 1, i 60, 5, i Type 1 2 3 4 5 (E.E.1C) (U,U,1C) (E,0,1C) (0,E,1C) (E,E,2C) Stage 38, - , i 19, - , i i 28, - , iii 26, - , iv 28, v 34, 2, ii 38, 1, i 37, 2, v 36, 1, i i 48, 3, i i i 34, 1, vi 48, 4, iv 38, 1, i 44, 4, v 48, 5, i 7 8 9 10 11 12 65, 1, i 59, 2, ii 61, 1, vi 61, 4, i 61, 5, i 69, 1, i 61, 2, ii 65, 3, i 61, 4, vi 65, 4 or 5, i 76, 2, ii 76, 4, i i 81, 3, iii 77, 4, iv 77, 4, iii 95, 1 or 2, ii 95, 2, ii 106, 1, iii 104, 1, iv 101, 4 or 5, v Type 1 2 3 4 5 61, 1, i 57, 2, ii 57, 3, i 57, 4, vi 64, 5, i 61, 57, 87, 57, 57, 1, iv 2, iv 3, iii 4, iv 3, iv (0,0,1 C) of complete solution subnetworks can be feasible, since the other types cannot possess all the connectivity requirements. T h i s example has 4 distinct extreme solution subnetworks, one of which is displayed in Figure 4.4. 4.2 • Series-Parallel Graphs: Non-Equal Requirement Case T h e purpose of this section is to gain some insight into the general requirement Steiner network synthesis problem. After i l l u s t r a t i n g the additional complications in the nonequal requirement case, we consider a special case, refered to as the monotone requirement case, which is a more general model than the equal-requirement case. Subse- quently, we consider the non-monotone requirement m o d e l . 4.2.1 The Additional Complications A s stated in L e m m a 2.1 i n Section 2.1 above, G o m o r y and H u [58] proved that the o p t i m a l solutions to the network synthesis problem induced by a full requirement struc- 86 o—o 9 9 9 ? 0 1 9 6 T o 0 1 o Figure 4.4: A n O p t i m a l Solution Subnetwork for E x a m p l e 4.1. ture and by any of its m a x i m u m requirement spanning tree ( M R S T ) ' s w i l l be identical. Now, following G o m o r y and H u ' s [58] decomposition approach to the equal-cost network synthesis problem, see E x a m p l e 2.1 in Section 2.1, one would naturally attempt to solve the non-equal requirement (Steiner) network synthesis problem by (a) decomposing a M R S T of the requirement structure into equal-requirement subtrees, then (b) independently solving the problem for each equal-requirement subtree by deriving an o p t i m a l solution subnetwork, and finally (c) superimposing these derived subnetworks (also see E x a m p l e 4.2 below for further illustration). A l t h o u g h , optimal solutions can sometimes be found for the non-equal cost (Steiner) network synthesis problem by using this decomposition, in general, one cannot ensure this result, because: 1. T h e superimposed o p t i m a l solution subnetwork, though a feasible solution, may not be o p t i m a l , as shown in E x a m p l e 4.2 below. 2. If the requirement structure is disconnected a n d / o r any of the equal-requirement subtrees is disconnected, it is not clear whether the o p t i m a l solution subnetworks a n d / o r the superimposed subnetwork w i l l be connected, as shown i n E x a m p l e 4.3 below. We note that in the equal-cost case, b o t h the o p t i m a l solution subnetworks and the superimposed subnetwork w i l l always be connected if the requirement structure is connected. 87 © © © © © 9 © © © © © © Figure 4.5: A Series-Parallel G r a p h (left), and an O p t i m a l Solution Subnetwork in it (right). © ©^~© $ ®- -© J ©^D © © © Figure 4.6: A M R S T (left), Equal-Requirement Subtrees 1 (center) and 2 (right), Derived in the Decomposition from the M R S T . Example 4.2. Consider the left graph G in Figure 4.5, where the unit costs (distances) dij are displayed on the edges, and the thicklined circles 1,2, . . . , and 6 are demand nodes w i t h 2 units of requirement between every pair, w i t h the exception of nodes 3 and 4 which have 3 units of requirement from each other. It can be varified that the solution subnetwork displayed in the right of Figure 4.5 is o p t i m a l to the Steiner network synthesis problem i n G, and has a total cost of 60 units. A MRST in the requirement structure described above is shown on the left of Figure 4.6, and the equal-requirement subtrees 1 and 2 derived by the decomposition of the M R S T are show on the center and right of Figure 4.6, respectively. Furthermore, o p t i m a l solution subnetworks 1 and 2 to the Equal-Requirement subtrees 1 and 2 are shown on the 88 i) <L ©© o © © O—©-<) © © © © © ? © © Figure 4.7: O p t i m a l Solution Subnetworks 1 (left) and 2 (center), and the Superimposed Subnetwork (right). left and center of Figure 4.7. F i n a l l y , the superimposed subnetwork is shown on the right of F i g u r e 4.7, where each line represents one unit of capacity. T h e superimposed subnetwork is not an o p t i m a l solution subnetwork to the Steiner network synthesis problem i n G, since it has a total cost of 61 units. T h e reason for the suboptimality of the superimposed subnetwork is that each of the o p t i m a l solution subnetworks are determined independently, and therefore the excess capacity which may occur in the other subnetwork cannot be utilized. Specifically, i n the o p t i m a l solution subnetwork 1, there is 1 unit excess capacity between u and v, which is not taken advantage of by the superposition. • E x a m p l e 4.3 below illustrates the disconnectivity issue mentioned i n i t e m 2 above. E x a m p l e 4.3. A g a i n consider the left graph G in F i g u r e 4.5, but suppose that the only positive requirements are 2 units between nodes 3 and 4, and 2 units between nodes 5 and 6. We can satisfy the above requirements in two o p t i m a l ways, shown in Figure 4.8. Depending on costs (distances) the other. For example, if 0I34 one of the solutions w i l l be cheaper than is decreased (resp., increased), the solution subnetwork on the right w i l l be cheaper (resp., more expensive) than the other solution displayed in Figure 4.8. • 89 o O — O (3) o © © © © © © o o o F i g u r e 4.8: A n O p t i m a l Solution Subnetwork (left), and another O p t i m a l Solution Subnetwork (right) used in E x a m p l e 4.3. A l t h o u g h the decomposition of a M R S T does not, i n general, provide an optimal solution to the Steiner network synthesis problem, we w i l l show i n the remainder of this section, for the series-parallel graphs, and in the next section, for the M 2 and M3-free graphs, that it can be modified to do so. F i r s t , we assume that a M R S T is i.e., it decomposes only into connected 4.2.2 monotone, equal-requirement subtrees. The Monotone Requirement Case W i t h o u t loss of generality, we can assume that a l l the requirements in a monotone M R S T are even, otherwise, we will m u l t i p l y the capacities and the requirements by 2. T h u s , a l l the equal-requirement subtrees, derived in the decomposition, are connected and have even requirements. A g a i n , without loss of generality, we can assume that a l l the requirements i n each equal-requirement subtree are equal to 2. The major difference between this case and the equal-requirement case, presented i n Subsection 4.1.2 above, is that, in this case we need to consider 7 types of p a r t i a l extreme solution subnetwork ( P E S S ) ' s associated w i t h each of the equal-requirement subtrees. Therefore, if there are k equal-requirement subtrees, we have to keep track of 7 types k of P E S S ' s . For example, suppose that there are 2 different equal-requirement subtrees, and that their positive requirements are either 2 or 4 units. T h e n , there are 7 = 49 2 types of P E S S ' s , each being the Cartesian product of two P E S S ' s , one associated w i t h 90 one of the subtrees, and the other w i t h the other subtree (see E x a m p l e 4.4 below). To prevent confusion, we w i l l refer to these Cartesian P E S S ' s as partial composed subnetworks solutions (PCSS). The series and parallel composition matrices for this case is similar to those presented for the equal-requirement case in Subsection 4.1.2 above, but w i t h the following two exceptions: • Instead of being 7 by 7, the composition matrices are 7 by 7 . fc k • The type of a P C S S depends on the types of P E S S ' s associated w i t h all the subtrees (see E x a m p l e 4.4 below for illustration). Since, by T h e o r e m 4.1 above, the extreme solutions to the Steiner network synthesis problem, w i t h even requirements, have integer values, in view of the results given in Section 4.1 above and the modifications to the P E S S types described above in this section, it follows that the (modified) dynamic programming type a l g o r i t h m provides an o p t i m a l solution to the monotone requirement Steiner network synthesis problem. Furthermore, the algorithm requires 0{7 k • n) operations, w h i c h is linear in ra, and by G o m o r y and H u [58], k cannot be greater than |!T| — 1, i m p l y i n g that for small values of k, the above a l g o r i t h m w i l l be practical (see E x a m p l e 4.5 below for illustration). E x a m p l e 4.4. For simplicity, suppose that the requirement structure decomposes into 2 equal-requirement subtrees, and that the positive requirements are either 2 or 4 units. T h u s , the requirements of the two subtrees are 2 units each. We note that one of the subtrees contains all the demand nodes, whereas the other (smaller) subtree contains only those demand nodes which have at least one requirement of 4 units. T h e P C S S ' s in this case can be classified by a pair of ordered 3-tuples ((a,/?,'•/), (6, e,f)), where the left 3-tuple ( a , / ? , 7 ) corresponds to the bigger subtree, a n d the right 3-tuple (S,e, f) corresponds to the smaller one. Since each of the 3-tuples can have 7 P E S S types, there are 7 2 = 49 different types of P C S S ' s in this case. Like the equal-requirement case, one can form series and parallel composition matrices for this case using the following simple composition rules. In the series composition of ((a,/3,7), (6, e,f)) and ((a',/?', 7'), (<5', e', c')), the left and right 3-tuples can be composed independently, using the series composition m a t r i x 91 presented i n Table 4.1 above. For example, the series composition of ( ( U , U , 1 C ) , ( E , 0 , 1 C ) ) and ( ( E , E , 1 C ) , ( 0 , E , 1 C ) ) is ( ( U , U , 1 C ) , ( E , E , 2 C ) ) . T h e parallel composition can also be done independently for each 3-tuple, except in the following cases. Suppose that we want to compose ((a,/?, 7 ) , [6,e,c)) ( ( a ' , / ? ' , 7 ' ) , (6',e',c')) in parallel. F i r s t , we say that ( E , E , 1 C ) has 2 units of with connectivity, because 2 units of flow can be channelled between the two terminals u and v, and that similarly, ( U , U , 1 C ) has 1 unit of connectivity. N o w , if the s u m of the connectivities of ( a , / ? , 7 ) and ( a ' , / ? ' , 7 ' ) is larger than 2, then the additional connectivity, that above 2, can be used to increase the connectivity of the parallel composition of (6,e,f) and (<S',e',<;') as follows: one additional unit of connectivity allows us to categorize (E,0,1C), ( 0 , E , 1 C ) , ( E , E , 2 C ) , (0,0,0C), or (0,0,1C) (except when infeasible) as ( U , U , l C ) , and to categorize ( U , U , 1 C ) as ( E , E , 1 C ) , whereas 2 additional units of connectivity allows us to categorize any P E S S type (except when infeasible) as ( E , E , 2 C ) . Since the above modification is symmetric between the first and the second 3-tuples, the additional connectivity of the parallel composition of (6, e,c) and (S',e',c') w i l l also increase the connectivity of the parallel composition of (a,/?, 7 ) and (a',/3', 7 ' ) , in a similar manner to that described above. • E x a m p l e 4.5 below illustrates the a l g o r i t h m for the monotone requirement Steiner network synthesis problem. Example 4.5. Consider the left graph in Figure 4.9 and the reduced graph derived from it, by discarding degree 2 nodes, on the right. A m a x i m u m requirement spanning tree ( M R S T ) is shown on the left in F i g u r e 4.10, and two equal-requirement subtrees, derived from the M R S T by the decomposition, are shown on the center and right. T h e computations resulting from the compositions are displayed in Table 4.4, whose left c o l u m n contains types of P C S S ' s , represented by ((a,/?, 7 ) , (6, e,^)), where (a, [3,7) corresponds to the P E S S ' s associated w i t h the equal-requirement subtree 1 (on the center of F i g u r e 4.10), and (6,e,c) is associated w i t h the equal-requirement subtree 2 (on the right of F i g u r e 4.10). We need not consider, in this example, the pair of ordered 3-tuples whose left 3-tuple is either (0,0,0C) or (0,0,IC). Stage 1 in Table 4.4 corresponds to edge ej in the reduced graph, w h i c h is displayed on the right in F i g u r e 4.9, Stage 2 corresponds to the parallel composition e\ © e of e\ and e , and Stage 3 corresponds 2 2 to the parallel composition of e © e w i t h e$. Furthermore, each of the other cells i n x 2 92 Figure 4.10: A M R S T (left), and Equal-Requirement Subtrees 1 (center), and 2 (right), Derived from the M R S T by the Decomposition. 93 © o F i g u r e 4.11: Best P a r t i a l Composed Solution Subnetworks for ( E , E , 1 C ) - ( E , E , 1 C ) at Stages 1 (left), 2 (center), and 3 (right). Table 4.4 contains a 3-tuple (a, (3,7), where a is the cost of a best P C S S of its row type upto and including its stage, /? is the type of best P C S S in the left component, and 7 is the type of best P C S S in the right component. For illustration, we show, in F i g u r e 4.11, the best P C S S ' s corresponding to the type ( E , E , 1 C ) - ( E , E , 1 C ) at stages 1, 2, and 3, where each ordinary line represents one unit capacity for the equal-requirement subtree 1 and, if possible, shared w i t h the equal-requirement subtree 2, whereas each thick line represents one unit of capacity only for the equal-requirement subtree 2. T h e right c o l u m n in Table 4.4 indicates the feasible solution subnetworks, the cheapest of w h i c h , i n fact, corresponds to the type ( E , E , 1 C ) - ( E , E , 1 C ) , displayed on the right of F i g u r e 4.11. 4.2.3 • The Non-Monotone Requirement Case In the non-monotone requirement case, the requirement structure a n d / o r some of the equal-requirement subtrees, derived from it through the decomposition, may be disconnected. We note that this case is the most general requirement structure. To solve the non-monotone requirement case, we w i l l modify the dynamic p r o g r a m m i n g type a l g o r i t h m used for the monotone requirement case, in Subsection 4.2.2 above. First, we note that in the monotone requirement case, while we were c o m p u t i n g the Cartesian product of p a r t i a l composed solution subnetwork ( P C S S ) ' s , for each edge, we, in effect, added the capacity of the edge across the partial extreme solution subnetwork Table 4.4: T h e Computations used in E x a m p l e 4.5. Stage 1 2 3 Type 1 2 3 4 5 6 7 (E,E,1C) • (E,E,1C) (E,E,1C) • (U,U,1C) (E,E,1C) (E,0,1C) (E,E,1C) (0,E,1C) (E.E.1C) • (E,E,2C) (E,E,1C) • (o,o,oc) (E,E,1C) • (o,o,ic) 76,- , 1 57,- , 2 48,- , 3 46,- , 4 56, -, 5 38, - , 6 58, - , 7 64, 13, 8 49, 13, 9 58, 13, 10 56, 13, 11 48, 13, 12 68, 63, 77, 75, 67, 50, 13,14 86, 14, 13 8 9 10 11 12 13 14 (U,U,1C) • (E,E,1C) (U,U,1C) • (U,U,1C) (U,U,1C) (E,0,1C) (U,U,1C) • (0,E,1C) (U,U,1C) • (E,E,2C) (U,U,1C) • (o,o,oc) (U,U,1C) • (o,o,ic) 57, - , 8 38, - i 2 9 , - 10 2 7 , - , 11 3 7 , - , 12 38, - , 13 58, - 14 63, 34, 8 48, 34,9 57, 34, 10 55, 34, 11 47, 34, 12 33, 34, 13 49, 34, 14 77, 8, 34 62, 9, 34 71, 10, 34 69, 11, 34 61, 12, 34 47, 13, 34 63, 14, 34 15 16 17 18 19 20 21 (E.0.1C) • (E,E,1C) (E,0,1C) • (U,U,1C) (E,0,1C) • (E,0,1C) (E,0,1C) • (0,E,1C) (E,0,1C) • (E,E,2C) (E,0,1C) • (o,o,oc) (E,0,1C) • (o,o,ic) 68, - 15 4 9 , - 16 4 0 , - 17 38, - 18 4 8 , - 19 30, - 20 50, - ,21 84, 69, 78, 76, 68, 54, 54, 20,15 20, 16 20, 17 20, 18 20,19 20, 20 20, 21 116, 15, 20 101, 16, 20 110, 17, 20 108, 18, 20 100, 19, 20 86, 20, 20 86, 21, 20 feasible 22 23 24 25 26 27 28 (0,E,1C) • (E,E,1C) (0,E,1C) • (U,U,1C) (0,E,1C) • (E,0,1C) (0,E,1C) • (0,E,1C) (0,E,1C) • (E,E,2C) (0,E,1C) • (o,o,oc) (0,E,1C) • (0,0,IC) 66, 47,38, 36, 46,28,28,- 22 23 24 25 26 27 28 80, 65, 62, 61, 64, 50, 50, 27, 27, 27, 27, 27, 27, 27, 22 23 24 25 26 27 28 110, 22, 27 95, 23, 27 104, 24, 27 102, 25, 27 94, 26, 27 80, 27, 27 80, 28, 27 feasible 29 30 31 32 33 34 35 (E,E,2C) • (E,E,1C) (E,E,2C) • (U,U,1C) (E,E,2C) • (E,0,1C) (E.E.2C) • (0,E,1C) (E.E.2C) • (E,E,2C) (E,E,2C) • (o,o,oc) (E,E,2C) • (o,o,ic) 57,37,28,18,18,18,38, - 29 30 31 32 33 34 35 62, 47, 56, 54, 46, 32, 48, 34, 34, 34, 34, 34, 34, 34, 29 30 31 32 33 34 35 76, 61, 70, 68, 60, 60, 76, 9 2, 2, 3, 4, 5, 13 34 34 34 34 29, 30, 31, 32, 33, 34, 35, 34 34 34 34 34 34 34 feasible feasible feasible feasible feasible feasible feasible feasible feasible feasible 95 Figure 4.12: T h e M R S T used in E x a m p l e 4.6. ( P E S S ) ' s in the Cartesian product. N o w , to proceed w i t h the modification, let T be r any disconnected equal-requirement subtree derived from a M R S T by the decomposit i o n , and let T}, T , . . . , T be a m i n i m u m number of connected subtrees comprising T . 2 l r r For illustration, see E x a m p l e 4.6 below and Figure 4.12. N o w , instead of associating a P E S S to T , we w i l l associate a P E S S to each of the connected subtrees T*, i' = 1 , . . . , / , T comprising it. However, while c o m p u t i n g the Cartesian product of P E S S ' s , for each edge, we w i l l first find the m a x i m u m capacity of the edge across the P E S S ' s associated w i t h T), T , . . . , J|f, and then add this m a x i m u m value to the sum of the capacities 2 r for the edge across the other P E S S ' s in the Cartesian product. requirements in T,,T?,...,T}. T h i s is because the need not be satisfied simultaneously. To complete the modification, we expand the types of P E S S ' s by (0,0,2C), (0,0,3C), and (0,0,kC), where k is the number of equal-requirement subtrees that the M R S T decomposes into. It can be easily seen that k cannot be larger t h a n | T | , where T is the set of demand 2 nodes. T h u s , the complexity of the modified dynamic programming type algorithm in the general requirement case is 0 ( ( 6 + k) k • n ) , which, for small values of fc, is small enough to render the algorithm p r a c t i c a l . E x a m p l e 4.6 below illustrates the above a l g o r i t h m for the general requirement Steiner network synthesis problem. Example 4.6. Suppose that the requirements i n a M R S T , T , shown i n Figure 4.12, r have to be satisfied i n the left graph of Figure 4.9. We let the subnetwork (a weighted path) whose nodes are 2, 3, and 5 to be T}, and the subnetwork (also a weighted path) whose nodes are 1, 4, and 6 to be T . T h e computations are s u m m a r i z e d i n Table 4.5, 2 r 96 Figure 4.13: Best P a r t i a l Composed Solution Subnetworks of T y p e ( E , E , 1 C ) - ( E , E , 1 C ) at Stages 1 (left), 2 (center), and 3 (right). where the first 3-tuple in the left column of the table corresponds to T , and the second J r 3-tuple corresponds to T . 2 For brevity, we do not show the types of P C S S ' s which are not relevant to this example. To illustrate Table 4.5, we display, i n Figure 4.13, the best (cheapest) P C S S ' s corresponding to the type ( E , E , 1 C ) - ( E , E , 1 C ) at each stage, where an ordinary line represents one unit of capacity shared between T) and T , and 2 r a thick line represent one unit of capacity used only by either T} or T?. The optimal solution subnetwork, in fact, corresponds to the type ( E , E , 1 C ) - ( E , E , 1 C ) , and is the right subnetwork in Figure 4.13. 4.3 • M and M -Free Graphs 2 3 In this section, we w i l l only briefly explain how the modified dynamic programming type a l g o r i t h m , presented in Section 4.2 above, for the Steiner network synthesis problem in series-parallel graphs can be used to solve the Steiner network synthesis problem in M 2 and M - f r e e graphs. We further demonstrate, by an example, that the Steiner network 3 synthesis p r o b l e m in a graph reducible to M 2 or M 3 may have extreme solutions w i t h arbitrary fractional values, i m p l y i n g that the dynamic p r o g r a m m i n g type algorithm cannot easily be extended to the Steiner network synthesis problem in more general graphs. Table 4.5: The Computations used in E x a m p l e 4.6. 1 Stage 2 3 Type 1 2 3 4 5 6 7 (E.E.1C) • (E,E,1C) (E,E,1C) • (U,U,1C) (E,E,1C) • (E,0,1C) (E,E,1C) • (0,E,1C) (E,E,1C) • (E,E,2C) (E,E,1C) • (0,0,0C) (E,E,1C) • (0,0,1C) 38, 38, 38, 38, 38, 38, 38, -, -, -, -, -, -, 1 2 3 4 5 6 7 34, 9, 9 39, 10, 9 51, 10, 10 51, 11, 11 42, 10,11 34, 13,13 48, 53, 83, 65, 56, 42, 8 9 10 11 12 13 14 (U,U,1C) • (E,E,1C) (U,U,1C) • (U,U,1C) (U,U,1C) • (E,0,1C) (U,U,1C) • (0,E,1C) (U,U,1C) • (E,E,2C) (U,U,1C) • (0,0,0C) (U,U,1C) • (0,0,1C) 38, - , 19, - , 24, - , 33, 28, - , 19, - , 29, - , 8 9 10 11 12 13 14 38, 23, 9 33, 24, 9 45, 24, 10 46, 25, 11 36, 24,11 23, 27, 13 52, 8, 18 47, 9, 18 77, 10, 17 60, 11, 18 50, 10, 18 31, 13, 20 feasible feasible 15 16 17 18 19 20 21 (E,0,1C) • (E,E,1C) (E,0,1C) • (U,U,1C) (E,0,1C) • (E,0,1C) (E,0,1C) • (0,E,1C) (E,0,1C) • (E,E,2C) (E,0,1C) • (0,0,0C) (E,0,1C) • (0,0,1C) 38, - , 15 34, 16 30, - , 17 38, - 18 38, 19 30, - , 20 30, -,21 53, 49, 54, 52, 44, 38, 16,16 17, 16 17, 17 18,18 17,18 20, 20 67, 63, 86, 66, 58, 46, 15, 16, 17, 18, 17, 20, 18 18 17 18 18 20 feasible 22 23 24 25 26 27 28 (0,E,1C) • (E,E,1C) (0,E,1C) • (U,U,1C) (0,E,1C) • (E,0,1C) (0,E,1C) • (0,E,1C) (0,E,1C) • (E,E,2C) (0,E,1C) • (0,0,0C) (0,E,1C) • (0,0,IC) 38, 23, 18, 28, 18, 28, 28, - , 22 - , 23 24 - 25 - , 26 - , 27 - , 28 49, 44, 48, 50, 40, 30, 23,23 24,23 24, 24 25,25 24, 25 27, 27 79, 74, 88, 80, 70, 60, 22, 22, 24, 25, 24, 27, 25 25 24 25 25 27 feasible 29 30 31 32 33 34 35 (E,E,2C) • (E,E,1C) (E,E,2C) • (U,U,1C) (E,E,2C) • (E,0,1C) (E,E,2C) - . ( O ^ I C ) (E,E,2C) • (E,E,2C) (E,E,2C) • (0,0,00) (E,E,2C) • (0,0,1C) 38, 28, 38, 18, 18, 18, 38, -, -, -, -, -, -, -, 42, 37, 42, 42, 32, 16, 23, 16 24, 16 24, 17 25, 18 24,18 27,20 56, 51, 74, 56, 46, 24, 29, 29, 31, 32, 31, 34, 18 18 17 18 18 20 feasible 29 30 31 32 33 34 35 1, 2, 3, 4, 5, 6, 18 18 17 18 18 20 feasible feasible feasible feasible feasible feasible feasible feasible feasible feasible 98 4.3.1 Preliminaries Fonlupt and Naddef [49] were the first to introduce the class of M i , M , and M3-free 2 graphs (see F i g u r e 3.4 for a display of M i , M , and M graphs), i.e., the graphs which do 2 not have M 1 ; 3 nor M , nor M as a minor, where, as we recall, a graph H is a minor of a 2 3 graph G if G can be reduced to H by a sequence of edge deletion, and edge contraction isolated-node deletion, (see Subsection 3.3.3 for more details). The larger class of M M3-free graphs, of course, consists of the graphs which do not have M 2 nor M 2 and as a 3 m i n o r . F o n l u p t and Naddef [49], when considering the Steiner Tour p r o b l e m in some special graphs, had to exclude M as a minor, since a network which reduces to M , but x not to M 2 x nor M , w i t h edge capacities equal to one unit, cannot be a solution to the 3 Steiner T o u r p r o b l e m , whereas it can be an o p t i m a l solution subnetwork to the Steiner network synthesis problem, w i t h requirements equal to 2 (see e.g., the left subnetwork in Figure 4.7). T h u s , we have no reason to exclude M i as a minor. A n interesting characteristic of M 2 and M -free graphs is that they include the 3 series-parallel graphs as a special case. T h i s fact is proven i n the following lemma: L e m m a 4.2. The M 2 and M^-free graphs properly contain the series-parallel graphs. Proof. ( B y contradiction.) w h i c h has M 2 Ki or M 3 as a minor. Suppose that there exists a series-parallel graph G It can easily be seen that b o t h M (i.e., the complete graph on 4 nodes) as a minor, thus, K 2 and M have 3 must be a minor of 4 G. However, from the excluded minor characterization of the series-parallel graphs in Subsection 3.4.2 above, it is evident that G cannot be a series-parallel graph. T h u s , by solving the Steiner network synthesis problem in M 2 • and M -free graphs, we 3 w i l l be extending the results described in Sections 4.1 and 4.2 above for the seriesparallel graphs. A n o t h e r interesting characteristic of M 2 and M -free graphs is stated 3 in the following lemma: L e m m a 4.3. A l l extreme solutions to the reduced linear program associated w i t h the Steiner network synthesis problem, w i t h requirements equal to 2, in M graphs have integer values. 2 and M - f r e e 3 • 99 T h e proof of L e m m a 4.3 above is lengthy but similar to that given i n Fonlupt and Naddef [49], and is omitted here. 4.3.2 Building Blocks and Composition rules F i r s t , we need the following definitions. A cockade, see Dirac [42], of two graphs G and G is their composition such that an edge (ui,vi) in G is superimposed on an edge 2 (u ,v ) 2 x x i n G , w i t h u coinciding w i t h u and V\ coinciding w i t h v . T h e superimposed 2 2 edge (ui,vi), x or (u ,v ), 2 2 2 2 will be called a hinge. A subdivision of a graph H is a graph G w h i c h can be derived from H by a sequence of node insertion. A slight generalization of the series-parallel graphs are the 2-trees, see e.g., W a l d and C o l b o u r n [156], which are cockades formed by using the triangle as the b u i l d i n g block. In fact, W a l d and C o l b o u r n [156] proved that series-parallel graphs are p a r t i a l 2-trees, i.e., they can be obtained from 2-trees by a sequence of edge deletion. We note that the Steiner network synthesis problem in 2-trees can also be solved by the algorithms presented in Sections 4.1 and 4.2 above. M and M3-free graphs, in t u r n , are a generalization of 2-trees, since, by the following 2 theorem, in addition to the triangle, the following b u i l d i n g blocks can also be used to form cockades (Dirac [42] used the same building blocks to construct M3-free graphs): • K, and K • W, n > 6, i.e., the wheels w i t h one centre-node and n rim-nodes, see the left 4 n 5 (i.e., the complete graph on 5 nodes). graph in Figure 4.14. • P 3 n , n > 3, i.e., the 3-propellers w i t h 3 central nodes a n d n outer nodes, see the right graph in Figure 4.14. Theorem 4.2 which contains 3-propeller, (Dirac [42], Theorem 4). neither a M 3 nor a subdivision A finite graph with at least three nodes of M 3 is either a K , 3 K, 4 K, 5 wheel or or a cockade composed of such graphs, or else it can be obtained from a graph coming under one of these categories by deleting edges. Since M 3 has only degree 3 nodes, it follows that excluding subdivisions of M • 3 is equivalent to excluding minors of M . T h u s , the graphs stated in T h e o r e m 4.2 above 3 100 Figure 4.14: A Wheel (left), and a Propeller (right). are precisely the M - f r e e graphs. 3 To also exclude M 2 as a minor, all we need to do is to restrict the composition of the building blocks when forming cockades. It can be verified that the following restrictions are all the restrictions necessary. 1. For any K , do not use as hinge all the three edges incident to a node, because (a) 4 any K , 4 K, 5 wheel or 3-propeller, or a cockade composed of such graphs, reduce to a triangle (b) the cockade of K 4 and 3 triangles using 3 of its edges incident to the same node, results i n a graph which contains M a m i n o r . For i l l u s t r a t i o n , consider the K A 2 as a subgraph, and hence as shown on the left of Figure 4.15, and its cockade G w i t h three triangles, using the edges (1,4), (1,3), and (1,2), is shown on the right. If we remove these three edges from G, the resulting graph is M . 2 2. For any K$, in a d d i t i o n to the restriction given in item 1 above, do not use as hinge any two edges incident to a node together w i t h the edge which has no endpoints in common w i t h them, because this case reduces to item 1 above as follows. Consider the left graph G i n Figure 2.1, and suppose edges (1,2), (1,3), and (4,5) are used as hinge. T h e n , contracting edge (1,5) reduces G to K 4 and this case to item 1 above. 3. For any wheel W , n n > 6, i n addition to the restriction given in item 1 above, do not use as hinge any spoke, i.e., any edge which connects the centre-node to a 101 Figure 4.15: K (left), and its Cockade w i t h Three Triangles (right). 4 rim-node. T h i s is because, in the left graph of Figure 4.14, if edge ( u , x ) is used as a hinge, then any two outer nodes, say v and w, not adjacent to x, together w i t h u reduce to a triangle whose nodes can be connected to x by 3 node-disjoint paths, each containing 2 edges. This specifies a M 2 subgraph, and hence a M 2 minor. 4. For any 3-propeller P 3 , , n > 6, the same restriction as in item 1 above applies, n since the three inner nodes and any of the outer nodes form a 4.3.3 K. 4 A Combinatorial Algorithm F i r s t consider the equal-requirement case, i.e., when all the requirements are equal to 2. T h e decomposition of a (connected) M 2 and M3-free graph can be done in a similar way to that done for a series-parallel graph, i.e., by considering only the nodes w i t h a degree greater than or equal to 3, and repeatedly decomposing the graph by finding any two-node cutsets which decompose the graph into its connected components. Thus, for a M 2 and M3-free graph, we can derive, in O ( n ) , a binary decomposition tree whose leaves correspond to the (partial) building blocks described above. Now, as in Section 4.1 and 4.2 above, a linear time dynamic p r o g r a m m i n g type algor i t h m may be devised to solve the Steiner network synthesis problem, w i t h requirements equal to 2, in M 2 and M - f r e e graphs. A l l we have to ascertain is that best (cheapest) 3 102 p a r t i a l extreme solution subnetwork ( P E S S ) for each of the 7 types i n each basic building block can be computed in linear time, because, best P E S S ' s in the partial basic b u i l d i n g blocks can be computed as i n the basic building blocks above, by assigning a large cost to the removed edges. F i r s t , we note that all the basic building blocks are Mi, M 2 and M - f r e e , so by L e m m a 3.3, we can restrict our search to optimal partial 3 Steiner tours. N o w , in K , 3 K 4 and K*,, we can use the transformation described in C h a p t e r 3 above to find best (cheapest) partial Steiner tours in 0 ( 1 ) . Best (cheapest) p a r t i a l Steiner tours in the wheels and the 3-propellers can also be obtained in linear time, because wheels and 3-propellers can be constructed recursively, see e.g., [1,2,14], and because p a r t i a l Steiner tours in recursively defined graphs can be found i n linear time, using the a l g o r i t h m by B e r n , Lawler, and Wong [14]. T h e extension to the general requirement case seems to be similar to that described for the series-parallel graphs in Section 4.2, and, hence, the details are omitted here. 4.3.4 A Fractional Solution We w i l l present below an example to show that there exist extreme solutions to the linear p r o g r a m associated w i t h the (Steiner) network synthesis p r o b l e m (even when the requirements are equal) i n graphs reducible to M or Ms, which have arbitrary fractional 2 values p/q, such that this ratio cannot be simplified and that q grows (linearly) w i t h the number of the nodes n. Thus, it is highly unlikely that there exists any p o l y n o m i a l dynamic programming type algorithms for the (Steiner) network synthesis problem in a more general class of graphs than M 2 and M - f r e e graphs. It is easy to see that the 3 graph, displayed in Figure 4.16, is reducible to M E x a m p l e 4.7 2 and M . 3 ( A d a p t e d from B o y d and P u l l e y b l a n k [24]). Consider the network G displayed i n Figure 4.16, where the capacities are given on the edges, and k is any o d d integer > 3. Further, the number of nodes is 2k + 4, and the number of positive capacity edges is 3k + 6. L e t b be the vector of positive capacities in G. Obviously, b is a feasible solution to the reduced linear program associated w i t h the (Steiner) network synthesis problem, w i t h requirements equal to 2, in G. B o y d and P u l l e y b l a n k [24] used this example to show that the Travelling Salesman problem ( T S P ) , without the zeroone integrality constraints, can have extreme solutions w i t h arbitrary fractional values. However, unlike the T S P , we do not have degree 2 constraints (i.e., Eygjv, j^i^ij = 2, 103 Figure 4.16: A Fractional Solution for the (Steiner) Network Synthesis P r o b l e m . 104 i £ JV) in the reduced linear program associated w i t h the (Steiner) network synthesis p r o b l e m , w i t h requirements equal to 2, in G. Therefore, we need to provide a different proof of the extremality of this solution to the linear program associated w i t h the (Steiner) network synthesis problem, w i t h requirements equal to 2, in G. To show this, it is sufficient to show that there exist at least 3k + 6 'independent' equations of the f o r m Yl(i,j)e{Q,N\Q) °ij — 2, 0 ^ Q C JV, in the reduced linear program, which is equal to the number of positive-capacity edges i n G. These constraints are as follows. There are 2k + 4 equations associated w i t h the cutsets (Q,N\Q), \Q\ — 1, i.e., one equation for each node. Further, there are A; + 1 equations associated w i t h the cutsets (Q, N\Q), \Q\ = 2 , i.e., one equation for each pair of nodes which are the endpoints of a capacity 1 edge. F i n a l l y , the constraint associated w i t h the cutset (Q,N\Q) = { e e , . . . , e } is l 5 2 k also an equation. 4.4 • Summary and Further Research In Chapter 4, we were concerned with simplifying the computation required to solve the Steiner network synthesis problem, when the solution network has to be embedded in (restricted to) some special graphs. We first considered trees and rings (cycles), and provided efficient algorithms in these cases. T h e n , we considered the series-parallel graphs, and showed that, when the solution subnetwork is to be embedded in seriesparallel graphs, all the extreme solutions to the Steiner network synthesis problem w i l l have integer or half-integer values. Further, we showed how the dynamic programming type a l g o r i t h m of B e r n , Lawler, and Wong [14] can be used to solve the Steiner network synthesis p r o b l e m in series-parallel graphs. T h e n , we considered the M 2 and M - f r e e 3 graphs which we proved to contain the series-parallel graphs as a special case, and finally, we outlined how the dynamic programming type algorithm can be modified to solve the Steiner network synthesis problem in M 2 and M - f r e e graphs. 3 The Steiner network synthesis problem is closely related to the Generalized Steiner problem ( G S P ) , see W i n t e r [159], which is precisely the Steiner network synthesis problem w i t h the added integrality condition that the edge capacities are either zero or one. A l l the results we obtained for the Steiner network synthesis problem i n series-parallel graphs and i n M 2 and M - f r e e graphs can easily be extended to the G S P . T h u s , we gen3 eralized the result given by W i n t e r [159] for the G S P in outerplanar graphs, when the 105 requirements are equal to 2, where outerplanar graphs are a special case of series-parallel graphs. Restricting the solution network to the above special graphs may appear to be a l i m i t a t i o n of this chapter. However, we have shown that more general graphs may allow solutions w i t h fractional values, which complicate the computations. Therefore, the d y n a m i c p r o g r a m m i n g type algorithm does not appear to be suitable for more general graphs. 4.5 A Final Comment T h e author wishes to thank the external examiner, D r . A . T a m i r , for pointing out a linear programming formulation of the nonsimultaneous network synthesis problem which has a p o l y n o m i a l number of constraints and variables. T h i s formulation is as follows: Min f £ l<:'j<n, S.T. E fg- i'gJV, i^k E dij • i^j E fJL = ~r \<k<l<n ffl = r l<k<l<n = o jeN, j^k,l, rkl < fij bij 1 < i,j <n, b^ = bji 1 < i,j <n, b^ > 0 1 < i,j < n, i' ^ j fij > 0 1 < i,j < n , i / j, kl m£N, m^k fu - £ £../#- E J? m u \ < k < l < n i^j, 1< k < I < n j 1 < Jfc < / < n T h e above formulation has the following immediate implications that are relevant to this thesis: 106 • U s i n g a compact formulation similar to above formulation and Owen's theorem on linear production games, it is quite simple to observe the existence of a core point of the game induced by the (directed) m i n i m u m spanning tree problem, defined on page 7, which can be derived from a dual solution of this compact formulation. • W i t h the polynomial formulation step 2 of the transformation given in Section 3.2.1 can be executed in time which is strongly polynomial in the number of nodes i n the shrunken network. B ibliography [l] A r n b o r g , Stefan, and Andrzej Proskurowski. "Linear T i m e A l g o r i t h m s for N P H a r d Problems on Graphs Embedded in k-Trees." T R I T A - N A - 8 4 0 4 , Department of N u m e r i c a l Analysis and C o m p u t i n g Science, T h e R o y a l Institute of Technology, S t o c k h o l m , 1984. A r n b o r g , Stefan, and Andrzej Proskurowski. "Characterization and Recognition of P a r t i a l 3-Trees." SIAM J. Alg. Disc. Meth., (2) ( A p r i l 1986), 305-314. A r t i e , R . , and C . Averous. "The Telephone System as a P u b l i c G o o d : Static and D y n a m i c Aspects." Bell Journal of Economics and Management Science, 4 (1973). A u m a n n , R . J . , and M . Maschler. "Game Theoretic Analysis of a B a n k r u p c y P r o b l e m from the T a l m u d . " Journal of Economic Theory, 36 (1985), 195-213. A u m a n n , R . J . , and L . S. Shapley. Values of Non-Atomic Jersey: Princeton University Press, 1974. Games. P r i n c e t o n , New A u t i n , C , and G . L e b l a n c . " E m p i r i c a l Evaluation of Cross-Subsidy Tests for C a n a d i a n Interregional Telecommunication Networks." In L . C o u r v i l l e , A . de Fontenay, and R . D o b e l (Eds.), Economic Analysis of Telecommunications, Amsterdam: N o r t h H o l l a n d , 1983. P p . 341-364. Baker, K . R . , and R . E . Taylor. " A Linear P r o g r a m m i n g Framework for Cost A l l o c a t i o n and E x t e r n a l A c q u i s i t i o n when Reciprocal Services E x i s t s . " The Accounting Review, 54 (1979), 784-790. Balachandran, B . V . , and R . T . S. R a m a k r i s h n a n . "Joint Cost Allocations: A Unified A p p r o a c h . " The Accounting Review, (January 1981), 85-96. B a l i n s k i , M . L . , and F . M . Sands. "The A l l o c a t i o n of Runway Slots by A u c t i o n . " In H . P . Y o u n g ( E d . ) , Cost Allocation: Methods, Principles, Applications, Amsterdam: N o r t h H o l l a n d , 1985. P p . 179-192. Banker, R . D . " E q u i t y Considerations i n Traditional F u l l Cost A l l o c a t i o n Practices: A n A x i o m a t i c Perspective." In Joint Cost Allocations, N o r m a n , O k l a h o m a : Center for Economic and Management Research, 1981. P p . 110-130. B a u m o l , W . J . , and D . B r a d f o r d . " O p t i m a l Departures from M a r g i n a l Cost P r i c ing." American Economic Review, 60 (1970), 265-283. 107 108 [12] B e l l - N o r t h e r n Research. "Designing Voice C o m m u n i c a t i o n Networks." In Successfull Operational Research in Canada, C a n a d i a n Operational Research Society, 1985. [13] Berge, C l a u d e . Graphs, 1985. Second Revised E d i t i o n . A m s t e r d a m : N o r t h - H o l l a n d , [14] B e r n , M . W . , E . L . Lawler, and A . L . W o n g . " W h y C e r t a i n Subgraph Computations Require O n l y Linear T i m e . " Proc. 26th Ann. IEEE Symp. on Foundations of Computer Science, (1985), 117-125. [15] B i d d l e , G . C , and R . Steinberg. " A l l o c a t i o n of Joint and C o m m o n Costs." Journal of Accounting Literature, 3 (1984), 1-45. [16] B i l l e r a , L . J . , and D . C . Heath. " A l l o c a t i o n of Shared Costs: A Set of A x i o m s Y i e l d i n g a U n i q u e Procedure." Mathematics of O. R., 7 (1982), 32-39. [17] B i l l e r a , L . J . , D . C . Heath, and J . R a a n a n . "Internal Telephone B i l l i n g R a t e s — A Novel A p p l i c a t i o n of N o n - A t o m i c Game Theory." Operations Research, 26 (1978), 956-965. [18] B i l l e r a , L . J . , D . C . Heath, and R . E . Verrecchia. " A Unique Procedure for Allocating C o m m o n Costs from a P r o d u c t i o n Process." Journal of Accounting research, 19 (1981), 185-196. [19] B i r d , C . G . , " O n Cost A l l o c a t i o n for a Spanning Tree: A G a m e Theory A p proach." Networks, 6 (1976), 335-350. [20] B l a n d , R . G . , D . Goldfarb, and M . J . T o d d . "The E l l i p s o i d M e t h o d : A Survey." Operations Research, 29(6) (1981), 1039-1091. [21] B o a t s m a n , J . R . , D . R . Hansen, and J . I. K i m b r e l l . " A R a t i o n a l and Some E v i dence Supporting an Alternative to the Simple Shapley Value." In Joint Cost Allocations, N o r m a n , O k l a h o m a : Center for Economic and Management Research, 1981. [22] B o d n a r , G . , and E . J . Lusk. " M o t i v a t i o n a l Considerations i n Cost Allocation Systems: A C o n d i t i o n i n g Theory A p p r o a c h . " The Accounting Review, (October 1977), 857-868. [23] B o n d y , J . A . , and U . S. M u r t y . Graph Theory with Applications. lan press, 1976. London: M a c M i l - [24] B o y d , S y l v i a C , and W . R . Pulley blank. " O p t i m i z a t i o n Over the Subtour E l i m ination P o l y t o p e of the Travelling Salesman P r o b l e m . " Research Report 84-12, Faculty of M a t h e m a t i c s , University of Waterloo, 1984. [25] B r a n d e r , J . A . , and B . J . Spencer. "Local Telephone P r i c i n g : T w o Tariffs and Price D i s c r i m i n a t i o n . " In L . Courville, A . de Fontenay, and R . D o b e l (Eds.), Economic Analysis of Telecommunications, A m s t e r d a m : N o r t h H o l l a n d , 1983. P p . 305-316. 109 [26] Brief, R . P . , and J . Owen. " A Least Squares A l l o c a t i o n M o d e l . " Journal counting Review, ( A u t u m n 1968), 193-198. of Ac- [27] C a l l e n , J . L . "Financial Cost Allocations: A Game Theoretic A p p r o a c h . " Accounting Review, 53 (1978), 303-309. [28] C a m p b e l l , B r i a n , and R o n a l d L . R a r d i n . "Polynomial T i m e Solution of Steiner Tree Problems on Special P l a n a r Graphs." Research M e m o r a n d o m N o . 86-7, Industrial Engineering, Purdue University, M a y 1986. [29] C a r l i n , A . , and R . E . Park. " M a r g i n a l Cost P r i c i n g of A i r p o r t Runway Capacity." American Economic Review, 60(3) (1970), 310-319. [30] Champsaur, P. "How to Share the Cost of a P u b l i c G o o d . " International of Game Theory, 4 (1975), 113-129. Journal [31] Christensen, L . R . , D . C u m m i n g s , and P . E . Schoech. "Econometric Estimation of Scale Economies in Telecommunications." In L . Courville, A . de Fontenay, and R . Dobel (Eds.), Economic Analysis of Telecommunications, Amsterdam: North H o l l a n d , 1983. P p . 27-53. [32] Christofides, Nicos, and C . A . W h i t l o c k . "Network Synthesis w i t h Connectivity C o n s t r a i n t s - A Survey." Operational Research'81. In J . P . Brans ( E d . ) , Amsterdam: N o r t h H o l l a n d , 1981. P p . 705-723. [33] C l a u s , A . , and D . Granot. "Game Theory A p p l i c a t i o n to Cost A l l o c a t i o n for a Spanning Tree." W o r k i n g Paper N o . 402, Faculty of Commerce and Business A d m i n i s t r a t i o n , University of B r i t i s h C o l u m b i a , June 1976. [34] C l a u s , A . , and D . J . K l e i t m a n . "Cost A l l o c a t i o n for a Spanning Tree." 3 (1973), 289-304. Networks, [35] C o h e n , S. I., and M . Loeb. " P u b l i c Goods, C o m m o n Inputs, and the Efficiency of F u l l Cost A l l o c a t i o n s . " Accounting Review, 57 (1982), 336-347. [36] Cornuejols, G . , J . Fonlupt, and D . Naddef. "The Travelling Salesman Problem on a G r a p h and Some Related Integer Polyhedra." Mathematical Programming, 33(1) (1985), 1-27. [37] Cornuejols, G . , D . Naddef, and W . R . P u l l e y b l a n k . "Halin Graphs and the Travelling Salesman problem." Mathematical Programming, 26 (1983), 287-294. [38] C u r i e n , Nicolas. "Cost A l l o c a t i o n and P r i c i n g Policy: The Case of French Telecommunications." In H . P. Y o u n g (Ed.), Cost Allocation: Methods, Principles, Applications, A m s t e r d a m : N o r t h H o l l a n d , 1985. P p . 167-178. [39] D a v i s , M . , and M . Maschler. "The K e r n e l of a Cooperative Game." Naval Logistics Quarterly, 12 (1965), 223-259. Research [40] D i j k s t r a , E . W . " A Note on T w o Problems i n Connection w i t h Graphs." merische Mathematik, 1 (1959), 269-271. Nu- 110 D i r a c , G . A . " A Property of 4 - C h r o m a t i c Graphs and Some Remarks on C r i t i c a l Graphs." J. London Math. Society, 17 (1962), 85-92. D i r a c , G . A . "Some Results Concerning the Structure of Graphs." Canadian Bull, 6 (1963), 183-210. Math. Dubey, P. "The Shapley Value as Aircraft L a n d i n g Fees—Revisited." Management Science, 28 (1982), 869-874. Dubey, P., and L . S. Shapley. "Totally Balanced Games A r i s i n g from Controlled P r o g r a m m i n g Problems." Mathematical Programming, 29 (1984), 245-267. Dufhn, R . J . "Topology of Series-Parallel Networks." Journal Analysis and Applications, 10 (1965), 303-310. of Eckel, L . G . " A r b i t r a r y and Incorrigible Allocations." Accounting (1976), 764-777. Mathematical, Review, 50 Engelbrecht-Wiggans, R . , and D . G r a n o t . " O n M a r k e t Prices i n Linear P r o d u c t i o n Games." Mathematical Programming, 32 (1985), 366-370. Faulhaber, G . "Cross-Subsidization: P r i c i n g in P u b l i c Enterprises." Economic Review, 65 (1975), 966-977. American Fonlupt, J . , and D . Naddef. " T h e Travelling Salesman P r o b l e m i n . Graphs w i t h Some E x c l u d e d M i n o r s . " W o r k i n g Paper N o . 557, Universite Scientifique et M e d i c a l e de Grenoble, France, Sept. 1985. F o r d , L . R . , and D . R . Fulkerson. Flows in Networks. P r i n c e t o n : P r i n c e t o n U n i versity Press, 1962. Fremgen, J . M . , and S. S. L i a o . "The A l l o c a t i o n of Corporate Indirect Costs." N a t i o n a l Association of Accountants, 1981. Gale, D . , and L . S. Shapley. "College Admissions and the Stability of Marriage." American Mathematical Monthly, 69 (1962), 9-14. G a l i l , Z. " A p p l i c a t i o n s of Efficient Mergeable Heaps for O p t i m i z a t i o n Problems on Trees." Acta Informatica, 13 (1980), 53-58. Gangolly, J . S. " O n Joint Cost A l l o c a t i o n : Independent Cost P r o p o r t i o n a l Scheme ( I C P S ) and its Properties." Journal of Accounting Research, 19 (1981), 299-312. Garey, M . R . , and D . S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W . H . Freeman, 1979. Gately, D . "Sharing the Gains from Regional Cooperation: A G a m e Theoretic A p p l i c a t i o n to P l a n n i n g Investment in E l e c t r i c a l Power." International Economic Review, 15 (1974), 195-208. Gillies, D . B . Some Theorems on n-Person M a t h e m a t i c s , P r i n c e t o n University, 1953. Games. P h . D . Thesis, Department of Ill [58] G o m o r y , R . E . , and T . C . H u . " M u l t i - T e r m i n a l Network Flows." J. SIAM, (1961), 551-570. 9(4) [59] G o m o r y , R . E . , and T . C . H u . " A n A p p l i c a t i o n of Generalized L i n e a r Programm i n g to Network Flows." J. Soc. Indust. Appl. Math., 10(2) (1962), 260-283. [60] G o m o r y , R . E . , and T . C . H u . "Synthesis of a C o m m u n i c a t i o n Network." J. Soc. Indust. Appl. Math., 12(2) (1964), 348-369. [61] G r a n o t , D a n i e l . " A Note on the R o o m - M a t e P r o b l e m and a Related Revenue A l l o c a t i o n P r o b l e m . " Management Science, 30 (1984), 633-643. [62] G r a n o t , D a n i e l . " A Generalized Linear P r o d u c t i o n M o d e l : A Unifying M o d e l . " Mathematical Programming, 34 (1986), 212-222. [63] G r a n o t , D a n i e l , and Frieda Granot. " O n Some Network F l o w Games." Working Paper N o . 1056, University of B r i t i s h C o l u m b i a , 1984. [64] G r a n o t , D a n i e l , and Frieda Granot. " O n Cost and Revenue A l l o c a t i o n Problems A r i s i n g i n M a t h e m a t i c a l P r o g r a m m i n g M o d e l s . " Proceedings of the 6th Mathematical Programming Symposium, Japan, November 1985. P p . 121-146. [65] G r a n o t , Daniel, and Frieda G r a n o t . " A F i x e d Cost Spanning Forest Problem." W o r k i n g Paper, University of B r i t i s h C o l u m b i a , 1987. [66] G r a n o t , D a n i e l , and M e h r a n H o j a t i . " O n Cost A l l o c a t i o n i n C o m m u n i c a t i o n Networks." S u b m i t t e d to Math, of O.R. [67] G r a n o t , D a n i e l , and G . H u b e r m a n . " M i n i m u m Cost Spanning Tree Games." Mathematical Programming, 21 (1981), 1-18. [68] G r a n o t , D a n i e l , and G . H u b e r m a n . " O n the Core and Nucleolus of M . C . S. T . Games." Mathematical Programming, 29 (1984), 323-347. [69] G r o t t e , J . H . Computation of and Observations on the Nucleolus Games. M . S c . Thesis, Cornell University, 1970. and the Central [70] Groves, T . , and J . L e d y a r d . " O p t i m a l A l l o c a t i o n of P u b l i c Goods: A Solution to the Free R i d e r P r o b l e m . " Econometrica, 45 (1977), 785-809. [71] H a m l e n , Susan S., W i l l i a m A . H a m l e n , J r . "The Concept of Fairness in the Choice of Joint Cost A l l o c a t i o n Methods." In Joint Cost Allocations, N o r m a n , O k l a h o m a : Center for E c o n o m i c and Management Research, 1981. [72] H a m l e n , S. S., W . A . H a m l e n , and J . T . Tschirhart. "The Use of Core Theory in E v a l u a t i n g Joint Cost A l l o c a t i o n Schemes." Accounting Review, 52 (July 1977), 616-627. [73] H a m l e n , S. S., W . A . H a m l e n , and J . T . Tschirhart. "The Use of the Generalized Shapley A l l o c a t i o n in Joint Cost A l l o c a t i o n . " Accounting Review, ( A p r i l 1980), 269-287. 112 Hassin, R . and A . T a m i r . "Efficient A l g o r i t h m s for O p t i m i z a t i o n and Selection on Series-Parallel Graphs." SIAM J. Alg. Disc. Meth., V o l 7 (1986), 379-389. Heaney, J . P . "Efficiency/Equity Analysis of Environmental Problems: A Game Theoretic Perspective." In S. J . B r a m s , A . Schotter, and G . Schwodiauer (Eds.), V i e n n a : Physica-Verlag, 1979. P p . 352-369. H o j a t i , M e h r a n , R i c h a r d Anstee, Daniel G r a n o t , and M a u r i c e Queyranne. " O n Steiner Network Synthesis P r o b l e m : Simplifying the Equal-Requirement Case." W o r k i n g Paper N o . 1216, Faculty of Commerce and Business A d m i n i s t r a t i o n , University of B r i t i s h C o l u m b i a , M a r c h 1987. H o j a t i , M e h r a n , Daniel G r a n o t , and M a u r i c e Queyranne. " A Two-Source, One-Sink Network Synthesis P r o b l e m . " Working Paper, University of B r i t i s h C o l u m b i a , August 1985. Itami, H . , and R . S. K a p l a n . " A n A c t i v i t y Analysis A p p r o a c h to Unit Costing w i t h M u l t i p l e Interactive Products." Management Science, 26 (1980), 826-839. Jensen, D . L . " A Class of M u t u a l l y Satisfactory Allocations." Accounting 52 (October 1977), 842-856. Review, K a l a i , E . , and E . Zemel. "Generalized Network Problems Y i e l d i n g Totally B a l anced Games." Operations Research, 30 (1982), 998-1008. K a l a i , E . , and E . Zemel. "Totally Balanced Games and Games of Flows." of O.R., 7 (1982), 476-478. Math, K a n e k o , M . "The Central Assignment Game and the Assignment Markets." Journal of Mathematical Economics, 10 (1982), 205-232. K a p l a n , R . , and G . T h o m p s o n . "Overhead A l l o c a t i o n V i a M a t h e m a t i c a l Programm i n g M o d e l s . " Accounting Review, ( A p r i l 1971), 352-364. K h a c h i a n , L . G . " A P o l y n o m i a l A l g o r i t h m for Linear P r o g r a m m i n g . " Doklady Akad. Nauk USSR, 244(5) (1979), 1093-96. English Translation in Soviet Math. Doklady, 20, 191-94. K o p e l o w i t z , A . " C o m p u t a t i o n of the Kernels of Simple Games and the Nucleolus of n-Person Games.". Research M e m o r a n d u m N o . 31, Department of Mathematics, T h e Hebrew University, 1967. L e v , B . , and H . T h e i l . " A M a x i m u m Entropy A p p r o a c h to the Choice of Asset Depreciation." Journal of Accounting Research, ( A u t u m n 1978), 286-293. L e v i n e , M . E . " L a n d i n g Fees and the A i r p o r t Conjestion P r o b l e m . " Journal Law and Economics, 12 (1969), 79-108. of L i t t l e c h i l d , S. C . " A Game-Theoretic A p p r o a c h to P u b l i c Utilities P r i c i n g . " Western Economic Journal, 7(2) (1970), 162-166. 113 L i t t l e c h i l d , S. C . " A Simple Expression for the Nucleolus in a Special Case." Int. J. Game Theory, 3 (1974), 21-29. L i t t l e c h i l d , S. C . Elements of Telecommunications of E l e c t r i c a l Engineering, 1979. Economics. L o n d o n : Institute L i t t l e c h i l d , S. C , and G u i l e r m o Owen. " A Simplistic Expression for the Shapley Value in a Special Case." Management Science, 20 (1973), 370-2. L i t t l e c h i l d , S. C , and G u i l e r m o Owen. " A Further Note on the Nucleolus of the ' A i r p o r t Game'." Int. J. Game Theory, 5 (1976), 91-95. L i t t l e c h i l d , S. C , and G . F . Thompson. "Aircraft L a n d i n g Fees: A G a m e Theory A p p r o a c h . " Bell Journal of Economics, 8 (1977), 186-204. L o e h m a n , E . , J . O r l a n d o , J . Tschirhart, and A . W h i n s t o n . "Cost A l l o c a t i o n for Regional Waste-Water Treatment System." Water Resources Research, 15 (1979), 193-202. L o e h m a n , E . , and A . W h i n s t o n . " A New Theory of P r i c i n g and Decision-making for P u b l i c Investment." The Bell Journal of Economics and Management Science, ( A u t u m n 1971). L o e h m a n , E . , and A . W h i n s t o n . " A n A x i o m a t i c A p p r o a c h to Cost A l l o c a t i o n for P u b l i c Investment." Public Finance Quarterly, ( A p r i l 1974). L o e h m a n , E . , and A . W h i n s t o n . " A Generalized Cost A l l o c a t i o n Scheme". In S. A . Y . L i n ( E d . ) , Theory and Measurement of Economic Externalities. New Y o r k : Academic Press, 1976. P p . 87-101. Louderback, J . G . " A n o t h e r A p p r o a c h to A l l o c a t i n g Joint Costs: A Comment." Accounting Review, (July 1976), 683-685. L o u g h l i n , J . C . "The Efficiency and E q u i t y of Cost A l l o c a t i o n M e t h o d s for M u l tipurpose Water Projects." Water Resources Research, 13 (1977), 8-14. Lovasz, L . "Submodular Functions and Convexity." In A . B a c h e m , M . Grotschel, and B . K o r t e (Eds.), Mathematical Programming: The State of Art, B e r l i n : Springer-Verlag, 1983. P p . 235-257. Luce, R . D . , and H . Raiffa. Games and Decisions. Wiley, 1957. Maschler, M . , B . Peleg, and L . S. Shapley. "The K e r n e l and B a r g a i n i n g Set for Convex Games." Int. J. Game Theory, 1 (1971), 73-93. Maschler, M . , B . Peleg, and L . S. Shapley. "Geometric Properties of the K e r n e l , Nucleolus, and Related Solution Concepts." Math, of O.R., 4 (1979), 303-338. M a u t z , R . k., and K . F . Skousen. " C o m m o n Cost A l l o c a t i o n i n Diversified C o m panies." Financial Executive, 15(7) (1968), 19-25. 114 [105] M e g i d d o , N i m r o d . " O n the Monotonicity of the Bargaining Set, the K e r n e l , and the Nucleolus of a Game." SIAM Journal on Applied Mathematics, 27 (1974), 355-358. [106] M e g i d d o , N . "Computational C o m p l e x i t y and the G a m e Theory A p p r o a c h to Cost A l l o c a t i o n for a Tree." Math, of O.R., 3 (1978), 189-196. [107] M e g i d d o , N . "Cost A l l o c a t i o n for Steiner Trees." Networks, 8 (1978), 1-6. [108] M i r m a n , L . J . , D . Samet, and Y . Tauman. " A n A x i o m a t i c A p p r o a c h to the A l location of a F i x e d Cost T h r o u g h Prices." Bell Journal of Economics, 14 (1983), 139-151. [109] M i r m a n , L . J . , and Y . T a u m a n . "Demand Compatible Equitable Cost Sharing Prices." Math, of O. R.,7 (1982), 40-56. [110] M i r m a n , L . J . , Y . T a u m a n , and Israel Zang. " O n the Use of Game-Theoretic Concepts in Cost A l l o c a t i o n . " In H . P. Y o u n g (Ed.), Cost Allocation: Methods, Principles, Applications, A m s t e r d a m : N o r t h H o l l a n d , 1985. P p . 55-77. [ i l l ] M i t c h e l l , B . M . " O p t i m a l P r i c i n g of L o c a l Telephone Service." American nomic Review, 64(4) (1978), 517-537. Eco- [112] M o r i a r i t y , Shane. "Another A p p r o a c h to A l l o c a t i n g Joint Costs". Accounting view, (October 1975), 791-795. Re- [113] O k a d a , Norio. "Cost A l l o c a t i o n i n M u l t i p u r p o s e Reservoir Development: The Japanese Experience." In H . P . Y o u n g ( E d . ) , Cost Allocation: Methods, Principles, Applications, A m s t e r d a m : N o r t h H o l l a n d , 1985. P p . 193-205. [114] O ' N e i l l , B . " A P r o b l e m of Rights A r b i t r a t i o n from the T a l m u d . " Math. 2 (1982), 345-371. Soc. Sci., [115] Owen, G u i l l e r m o . " A Note on the Shapley Value." Management (1968), 731-732. Science, 14 [116] Owen, G u i l l e r m o . " M u l t i l i n e a r Extensions of Games." Management (1972), 65-79. Science, 18 [117] Owen, G u i l l e r m o . " O n the Core of Linear P r o d u c t i o n Games." Mathematical gramming, 9 (1975), 358-370. Pro- [118] Owen, G u i l l e r m o . Game Theory, 2nd E d i t i o n . New Y o r k : Academic Press, 1982. [119] Parker, T . " A l l o c a t i o n of the Tennessee Valley Projects." American Society of Civil Engineers, 108 (1943), 174-187. Transactions [120] Q u i n z i i , M . "Core and Competitive E q u i l i b r i a w i t h Indivisibilities." Journal of Game Theory, 13 (1984), 41-60. of the International [121] Ransmeier, J . S. The Tennessee Valley Authority: A Case Study in the Economics of Multiple Purpose Stream Planning. T h e Vanderbilt University Press, 1942. 115 [122] Ratliff, D . M . , and A . S. Rosenthal. " O r d e r - P i c k i n g in a Rectangular Warehouse: A Solvable Case of the Travelling Salesman Problem." Operations Research, 31 (1983), 507-521. [123] R a w l s , J . "Justice as Fairness." Philosophical Review, 67 (1953). [124] R o h l s , J . " A Theory of Interdependent Demand for a C o m m u n i c a t i o n Service." Bell Journal of Economics and Management Science, 5(1) (1974), 16-37. [125] Rosenmuller, J . " L P Games w i t h Sufficiently M a n y Players." International nal of Game Theory, 11 (1982), 124-149. Jour- [126] R o t h , A . E . , and R . E . Verrecchia. "The Shapley Value as A p p l i e d to Cost A l l o cation: A Reinterpretation." Journal of Accounting Research, (1979). [127] Samet, D o v , and Y a i r T a u m a n . "The Determination of M a r g i n a l Prices Under a Set of A x i o m s . " Econometrica, 50 (1982), 895-909. [128] Samet, D o v , Y a i r T a u m a n , and Israel Zang. " A n A p p l i c a t i o n of the A u m a n n Shapley Prices for Cost A l l o c a t i o n in Transportation Problems." Mathematics of Operations Research, 9(1) (February 1984), 25-42. [129] Samet, D . , and E . Zemel. " O n the Core and D u a l Set of Linear Programming Games." Mathematics of O. R. 9 (1984), 309-316. [130] Schmeidler, D . "The Nucleolus of a Characteristic F u n c t i o n G a m e . " SIAM Applied Math., 17 (1969), 1163-1170. [131] Shapley, L . S. " A Value for n-Person Games." Annals 307-317. J. of Math. Study, 28 (1953), [132] Shapley, L . S. "Cores of Convex Games." Int. J. Game Theory, 1 (1971), 11-26. [133] Shapley, L . S., and M . Shubik. " O n M a r k e t games." Journal 1 (1969), 9-25. of Economic Theory, [134] Shapley, L . S., and M . Shubik. "The Assignment Game; I. T h e Core." Int. Game Theory, 1 (1972), 111-130. J. [135] Shapley, L . S., and M . Shubik. "Competitive Outcomes in the Cores of M a r k e t Games." International Journal of Game Theory, 4 (1975), 229-237. [136] Sharkey, W . W . "Suggestions for a Game-Theoretic A p p r o a c h to P u b l i c U t i l i t y P r i c i n g and Cost A l l o c a t i o n . " Bell Journal of Economics, 13 (1982), 57-68. [137] Sharkey, W . W . The Theory of Natural Monopoly. Press, 1982. L o n d o n : C a m b r i d g e University [138] Sharkey, W . W . "Economic and Game-Theoretic Issues Associated w i t h Cost A l l o c a t i o n in a Telecommunication Network." In H . P. Young ( E d . ) , Cost Allocation: Methods, Principles, Applications, A m s t e r d a m : N o r t h H o l l a n d , 1985. P p . 155-165. 116 [139] Shubik, M . "Incentives, Decentralized C o n t r o l , T h e Assignment of Joint Costs and Internal P r i c i n g . " Management Science, ( A p r i l 1962). [140] Shubik, M . , and R . Weber. "Systems Defence Games: Colonel B l o t t o C o m m a n d and C o n t r o l . " Naval Research Logistics Quarterly, 28 (1981). [141] Sobolev, A . I. "Characterization of the P r i n c i p l e of O p t i m a l i t y for Cooperative Games T h r o u g h Functional Equations." In N . N . Vorobyev (Ed.), Mathematical Methods in Social Sciences, V i p u s k 6, V i l n i u s , U S S R , 1975. P p . 92-151. [142] Spinetto, R . D . "Fairness in Cost A l l o c a t i o n and Cooperative Games." Sciences, 6(3) (July 1975), 482-491. Decision [143] Squire, L . "Some Aspects of O p t i m a l P r i c i n g for Telecommunications." Bell nal of Economics and Management Science, 4(2) (1973), 515-525. Jour- [144] Steiglitz, K . , P . Weiner, and D . J . K l e i t m a n . "The Design of M i n i m a l Cost Survivable Networks." IEEE Trans. Cir. Theory, 16(4) (1969), 455-60. [145] StrafHn, P . , and J . P. Heaney. "Game Theory and the Tennessee Valley A u t h o r i t y . " International Journal of Game Theory, 10 (1981), 35-43. [146] S u z u k i , M . , and M . Nakayama. "The Cost Assignment of the Cooperative Water Resource Development: A Game Theoretical A p p r o a c h . " Management Science, 22 (1976), 1081-1086. [147] T a m i r , A . " O n the Core of Cost A l l o c a t i o n Games Defined on L o c a t i o n Problems." Department of Statistics, T e l - A v i v University, J u l y 1980. [148] T a m i r , A . " A Class of Balanced Matrices A r i s i n g from L o c a t i o n Problems." J. Alg. Disc. Meth., 4 (1983), 363-370. [149] Taylor, A . L . Telecommunications M A . : Ballinger, 1980. Demand: A Survey and Critique. [150] T h o m a s , A . L . "Useful A r b i t r a r y Allocations." Accounting 472-479. [151] T h o m p s o n , G . F . Airport Costs and Pricing. University of B i r m i n g h a m , E n g l a n d , 1971. SIAM Cambridge, Review, 45 (1971), U n p u b l i s h e d P h . D . Dissertation, [152] T i j s , S. H . , and T . S. H . Driessen. "Game Theory and Cost A l l o c a t i o n Problems." Management Science, 32(8) (August 1986), 1015-1028. [153] Valdes, J . , R . E . Tarjan, and Eugene L . Lawler. "The Recognition of Series-Parallel D i g r a p h . " SIAM J. Computing, V o l 11 (1982), 298-313. [154] Verrecchia, R o b e r t E . " A Question of E q u i t y : Use of the Shapley V a l u e to A l l o c a t e State and L o c a l Income and Franchise Taxes." In Joint Cost Allocations, N o r m a n , O k l a h o m a : Center for Economic and Management Research, 1981. P p . 14-40. 117 [155] V o n N e u m a n n , J o h n , and Oscar Morgenstern. Theory of Games and Behaviour, P r i n c e t o n : Princeton University Press, 1953. Economic [156] W a l d , J . A . , and C . J . C o l b o u r n . "Steiner Trees, P a r t i a l 2-Trees, and M i n i m u m I F I Neworks." Networks, 13 (1983), 159-167. [157] Wei], R . L . " A l l o c a t i n g Joint Costs." American 1342-1345. Economic Review, 58 (1968), [158] W i n g , 0 . , and R . T . C h i e n . " O p t i m a l Synthesis of a C o m m u n i c a t i o n Net." Transactions on Circuit Theory, 8 (1961), 44-49. IRE [159] W i n t e r , Pawel. "Generalized Steiner P r o b l e m in Outerplanar Networks." BIT, 25 (1985), 485-496. [160] Y o u n g , H . P e y t o n . "Monotonic Solutions of Cooperative Games." Journal of Game Theory, 14(2) (1985), 65-72. International [161] Y o u n g , H . P e y t o n . "Producer Incentives in Cost A l l o c a t i o n . " Econometrica, (July 1985), 757-765. 53(4) [162] Y o u n g , H . P e y t o n . "Methods and Principles of Cost A l l o c a t i o n . " In H . P . Y o u n g (Ed.), Cost Allocation: Methods, Principles, Applications, Amsterdam: North H o l l a n d , 1985. P p . 3-29. [163] Y o u n g , H . P., N . O k a d a , and N . Hashimoto. "Cost A l l o c a t i o n i n Water Resources Development." Water Resources Research, 18 (1982), 463-475. [164] Zajac, E . Fairness or Efficiency: bridge, M A . : B a l l i n g e r , 1978. An Introduction to Public Utility Pricing. [165] Z i m m e r m a n , J . L . "The Costs and Benefits of Cost A l l o c a t i o n s . " Accounting view, (July 1979), 504-521. Cam- Re-
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Network synthesis problem : cost allocation and algorithms
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Network synthesis problem : cost allocation and algorithms Hojati, Mehran 1987
pdf
Page Metadata
Item Metadata
Title | Network synthesis problem : cost allocation and algorithms |
Creator |
Hojati, Mehran |
Publisher | University of British Columbia |
Date Issued | 1987 |
Description | This thesis is concerned with a network design problem which is referred to in the literature as the network synthesis problem. The objective is to design an undirected network, at a minimum cost, which satisfies known requirements, i.e., lower bounds on the maximum flows, between every pair of nodes. If the requirements are to be satisfied nonsimultaneously, i.e., one at a time, the problem is called the nonsimultaneous network synthesis problem, whereas if the requirements are to be satisfied simultaneously, the problem is called the simultaneous network synthesis problem. The total construction cost of the network is the sum of the construction cost of capacities on the edges, where the construction cost of a unit capacity is fixed for any edge, independent of the size of the capacity, but it may differ from edge to edge. The capacities are allowed to assume noninteger nonnegative values. The simultaneous network synthesis problem was efficiently solved by Gomory and Hu [60], whereas the nonsimultaneous network synthesis problem can only be formulated and solved as a linear program with a large number of constraints. However, the special equal-cost case, i.e., when the unit construction costs are equal across the edges, can be efficiently solved, see Gomory and Hu [60], by some combinatorial method, other than linear programming. A cost allocation problem which is associated with the network synthesis problem would naturally arise, if we assume that the various nodes in the network represent different users or communities. In this case, we need to find a fair method for allocating the construction cost of the network among the different users. An interesting generalization of the nonsimultaneous network synthesis problem, the Steiner network synthesis problem, is derived, when only a proper subset of the nodes have positive requirements from each other. The thesis is concerned with two issues. First, we will analyze the cost allocation problems arising in the simultaneous and the equal cost nonsimultaneous network synthesis problem. Secondly, we will consider the Steiner network synthesis problem, with particular emphasis on simplifying the computations in some special cases, not considered before. We will employ cooperative game theory to formulate the cost allocation problems, and we will prove that the derived games are 'concave', which implies the existence of the core and the inclusion of the Shapley value and the nucleolus in the core, and then we will present irredundant representations of the cores. For the equal cost nonsimultaneous network synthesis game, we will use the irredundant representation of the core to provide an explicit closed form expression for the nucleolus of the game, when the requirement structure is a spanning tree; then, we will develop, in a special case, a decomposition of the game, which we will later use to efficiently compute the Shapley value of the game when the requirement structure is a tree; the decomposition will also be used for the core and the nucleolus of the game in the special case. For the simultaneous network synthesis game, we will also use the irredundant representation of the core to derive an explicit closed form expression for the nucleolus, and we will also decompose the core of this game in the special case, and prove that the Shapley value and the nucleolus coincide. Secondly, for the Steiner network synthesis problem, two conceptually different contributions have been made, one being a simplifying transformation, and the other being the case when the network has to be embedded in (i.e., restricted to) some special graphs. Namely, when the requirement structure is sparse (because there are only a few demand nodes and the rest are just intermediate nodes) and the positive requirements are equal, we will employ a transformation procedure to simplify the computations. This will enable us to efficiently solve the Steiner network synthesis problem with five or less nodes which have equal positive requirements from each other. Finally, when the solution network to the Steiner network synthesis problem is to be embedded in (restricted to) some special graphs, namely trees, rings (circles), series-parallel graphs, or M₂ and M₃-free graphs, we will provide combinatorial algorithms which are expected to simplify the computations. |
Subject |
Network analysis (Planning) |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-08-13 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
IsShownAt | 10.14288/1.0097387 |
URI | http://hdl.handle.net/2429/27318 |
Degree |
Doctor of Philosophy - PhD |
Program |
Business Administration |
Affiliation |
Business, Sauder School of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-UBC_1987_A1 H63_9.pdf [ 7.37MB ]
- Metadata
- JSON: 831-1.0097387.json
- JSON-LD: 831-1.0097387-ld.json
- RDF/XML (Pretty): 831-1.0097387-rdf.xml
- RDF/JSON: 831-1.0097387-rdf.json
- Turtle: 831-1.0097387-turtle.txt
- N-Triples: 831-1.0097387-rdf-ntriples.txt
- Original Record: 831-1.0097387-source.json
- Full Text
- 831-1.0097387-fulltext.txt
- Citation
- 831-1.0097387.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0097387/manifest