N E T W O R K SYNTHESIS P R O B L E M : COST ALLOCATION AND ALGORITHMS B y M E H R A N HOJATI B.Sc. (Economics), London School of Economics & Political Science, 1980 M.Sc. (Operational Research), London School of Economics & Political Science, 1981 A T H E S I S 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 T H E R E Q U I R E M E N T S F O R T H E D E G R E E O F D O C T O R O F P H I L O S O P H Y in F A C U L T Y O F G R A D U A T E S T U D I E S ( C O M M E R C E A N D B U S I N E S S A D M I N I S T R A T I O N ) We accept this thesis as conforming to the required standard T H E U N I V E R S I T Y O F B R I T I S H C O L U M B I A © Mehran Hojati , 1987 October 1987 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department The University of British Columbia 1956 Main Mall Vancouver, Canada V6T 1Y3 Date nrJr 8, If89 DE-6(3 /81 ) 11 A B S T R A C T This thesis is concerned wi th 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 min imum cost, which satisfies known requirements, i.e., lower bounds on the max imum 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. The total construc-t ion 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 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 con-struction costs are equal across the edges, can be efficiently solved, see Gomory and H u [60], by some combinatorial method, other than linear programming. A cost allocation problem which is associated wi th the network synthesis problem would naturally arise, if we assume that the various nodes in the network represent different users or commu-nities. 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 nonsimul-taneous 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 wi th two issues. Fi rs t , we wi l l analyze the cost allocation problems arising in the simultaneous and the equal cost nonsimultaneous network syn-thesis problem. Secondly, we wi l l consider the Steiner network synthesis problem, wi th particular emphasis on simplifying the computations in some special cases, not consid-ered before. We wi l l employ cooperative game theory to formulate the cost allocation problems, and we wi 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 wi l l present irredundant representations of the cores. For the equal cost nonsimultaneous network synthesis game, we wi l l use the irredundant representation of i i i 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 wi l l develop, in a special case, a decomposition of the game, which we wi l l later use to efficiently compute the Shapley value of the game when the requirement structure is a tree; the decomposition wi 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 wi l l also use the irredundant representation of the core to derive an explicit closed form expression for the nucleolus, and we wi l l 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 con-tributions 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 wi l l employ a transformation procedure to simplify the computations. This w i l l enable us to efficiently solve the Steiner network synthesis problem wi th five or less nodes which have equal positive requirements from each other. Final ly , 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 2 and M 3 - f ree graphs, we wi l l provide combinatorial algorithms which are expected to simplify the computations. C on tents A B S T R A C T i i Table of Contents iv Lis t of Tables v i i Lis t of Figures v i i i A C K N O W L E D G E M E N T x 1 I N T R O D U C T I O N 1 1.1 The Network Synthesis Problem 1 1.2 Cost Al locat ion and Introduction to Cooperative Game Theory 4 1.3 The Steiner Network Synthesis Problem 12 2 C O S T A L L O C A T I O N I N T H E N E T W O R K S Y N T H E S I S P R O B -L E M 17 2.1 Introduction, Notat ion and Preliminaries 17 2.1.1 Introduction 17 2.1.2 Game Theory Notat ion and Preliminaries 18 2.1.3 Graph Theory Notat ion and Preliminaries 22 2.2 Concavity of the Network Synthesis Games 26 2.3 Irredundant Representation of the Cores of ( iV ;c i ) and (N;c2) 30 2.4 The Nucleolus of the Network Synthesis Games 36 2.5 Nearly Decomposable Network Synthesis Games 41 2.6 Decomposit ion of Cores of Nearly Decomposable Games (N; C\) and (N; c2) 43 iv V 2.7 The Nucleolus of the Nearly Decomposable Game (N; c 2) 47 2.8 Shapley Values of ( iV;c i ) and Nearly Decomposable (N;^) 51 2.9 Summary and Further Research for the Cost Al loca t ion Problem . . . . 56 3 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 -W O R K S Y N T H E S I S P R O B L E M 58 3.1 The Steiner Network Synthesis Problem 58 3.2 Simplifying the Equal-Requirement Case: Preliminaries 60 3.2.1 Linear Programming Formulations and the Transformation . . . 61 3.2.2 Dual Problems and the Laminar i ty of Dua l Solutions to (P') . . 63 3.3 Opt imal i ty of the Subnetwork W 65 3.3.1 A Modified Dijkst ra A lgo r i t hm 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 3.4 Summary and Further Research for the Transformation 72 4 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 I N S O M E S P E -C I A L G R A P H S 73 4.1 Trees and Rings; Series-Parallel Graphs: Preliminaries and the Equal Requirement Case 74 4.1.1 Trees and Rings 74 4.1.2 Series-Parallel Graphs: Preliminaries and the Equa l Requirement Case 75 4.2 Series-Parallel Graphs: Non-Equal Requirement Case 85 4.2.1 The Addi t iona l Complications 85 4.2.2 The Monotone Requirement Case 89 4.2.3 The Non-Monotone Requirement Case 93 4.3 M 2 and M 3 - F r e e Graphs 96 v i 4.3.1 Preliminaries 98 4.3.2 Bui ld ing Blocks and Composi t ion rules 99 4.3.3 A Combinatorial Algor i thm 101 4.3.4 A Fractional Solution 102 4.4 Summary and Further Research 104 4.5 A F i n a l Comment 105 B I B L I O G R A P H Y 107 List of Tables 4.1 The Series Composi t ion Ma t r i x 82 4.2 The Paral lel Composi t ion Ma t r i x 83 4.3 The Computations for Example 4.1 85 4.4 The Computations used in Example 4.5 94 4.5 The Computations used in Example 4.6 97 v i i List of Figures 1.1 A Rectangular Warehouse, and Some Items (the thicklined nodes) to be Picked up 15 2.1 A Requirement Structure (left), and a M R S T in it (right) 23 2.2 The Equal-Requirement Subtrees 24 2.3 Op t ima l Solution Subnetworks for the Equal-Requirement Subtrees. . . 24 2.4 The Superimposed Opt imal Solution Subnetwork 24 2.5 A Requirement Structure, and the Opt ima l Solution Networks 27 2.6 A Spanning Tree Requirement Structure Used in Theorem 2.3 34 2.7 A Spanning Tree Requirement Structure 42 2.8 The Requirement Structure (left) used in Example 2.4, and the Networks Result ing from the Near-Decomposition (center and right) 54 3.1 Graph G, and point set Si 64 3.2 A n Opt imal Solution Subnetwork in G', and the Dijkst ra Cuts 68 3.3 A n Opt imal Solution Subnetwork in G, and the Dijkst ra Cuts 69 3.4 Mi (left), M 2 (center), and M 3 (right) 71 4.1 Types i , i i , i i i , iv , v , v i , and v i i (from left to right) of Par t ia l Extreme Solu-t ion Subnetworks in a Simple Path Associated wi th the Steiner Network Synthesis Problem, with Requirements Equa l to 2, in a Series-Parallel G r a p h 81 4.2 A Series-Parallel Graph (left), and its Reduced Graph (right) 83 v i i i ix 4.3 A Binary Decomposition Tree for the Reduced Graph in Figure 4.2. . . 84 4.4 A n Opt ima l Solution Subnetwork for Example 4.1 86 4.5 A Series-Parallel Graph (left), and an Opt imal Solution Subnetwork in it (right) 87 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 87 4.7 Opt ima l Solution Subnetworks 1 (left) and 2 (center), and the Superim-posed Subnetwork (right) 88 4.8 A n Opt imal Solution Subnetwork (left), and another Opt imal Solution Subnetwork (right) used in Example 4.3 89 4.9 A Series-Parallel Graph (left), and its Reduced Graph (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 Par t ia l Composed Solution Subnetworks for (E ,E ,1C) - (E ,E ,1C) at Stages 1 (left), 2 (center), and 3 (right) 93 4.12 The M R S T used in Example 4.6 95 4.13 Best Par t ia l Composed Solution Subnetworks of Type ( 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 K4 (left), and its Cockade wi th Three Triangles (right) 101 4.16 A Fractional Solution for the (Steiner) Network Synthesis Problem. . . . 103 X A C K N O W L E D G E M E N T The author is indebted to his research supervisor, Professor Daniel Granot, for intro-ducing 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, Dr . Maurice Queyranne and D r . Richard Anstee, for offering many hours of consultation, as well as for carefully reading the thesis and making cri t ical but beneficial suggestions. The author is grateful for the financial sup-port given to h i m by the University of Br i t i sh Columbia and the Faculty of Commerce and Business Adminis t ra t ion . C hapter 1 I N T R O D U C T I O N 1.1 The Network Synthesis Problem This thesis is concerned w i th a network design problem which is referred to in the literature as the network synthesis problem. The objective is to design an undirected network wi th a minimum construction cost, which satisfies known requirements, i.e., lower bounds on the max imum 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 non-simultaneous 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 in this thesis we are primari ly concerned wi th the nonsimultaneous case, for brevity, we wi l l refer to the nonsimultaneous network synthesis problem as the network synthesis problem. The 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). The capacities are allowed to assume integer and noninteger nonnegative values. The network synthesis problem originated as a research problem in Electr ical Engi-neering, see e.g., Wing and Chien [158]. The problem was formulated as a linear program wi th a large number of constraints, and a special equal-cost case, i.e., when the Unit construction costs are equal across edges, was solved efficiently by some combinato-rial methods other than linear programming. Gomory and H u [58] gave a conceptually simpler method for solving the equal-cost case, and in [59], they devised some row gener-ation simplex methods to simplify and accelerate the computations in the linear program 1 2 formulation of the problem. The row generation methods deal only wi th a small subset of the constraints at each step of the algorithm. Al though 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 al l simplex type methods, the number of steps required to solve the problem wi l l be too large (exponential). That is, the number of computational operations cannot be bounded by a polynomial 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 land , Goldfarb, and Todd [20] proved that despite the large number of constraints, the ellipsoid method may, in theory, be applied to solve the network synthesis problem in polynomial number of operations. Nevertheless, no practical implementation of the ellipsoid method is available to date. A natural application of the network synthesis problem is in communication network design. In many cases, for example in a 'private telecommunication network', see e.g., Bel l -Northern Research [12], it is desirable to have known minimum 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. This 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 l imit on the probability of being blocked. The 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. Another 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 in the nodes and/or in the edges. Here, every pair of nodes is required to have a known degree of connectivity. The nonsimultaneous network synthesis problem is a special case of survivable network design, in which the requirements can be thought of as the required connectivities. Final ly , the network synthesis problem is related to some combinatorial opt imizat ion problems such as the Steiner problems, see e.g., [28,40,122,156,159]. Formally, in the network synthesis problems, see Gomory and H u [58,59,60], we need to design, at a min imum cost, an undirected network wi th n nodes, which satisfies 3 known requirements, i.e., lower bounds on maximum flow, between every pair of nodes. We wi l l refer to the network to be designed as the solution network. The 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. Denoting the set of nodes by N = { l , . . . , n} , for each pair of nodes {i,j} Q N, i < j, d^ is the cost of bui lding one unit capacity on edge and is the requirement between i and j. Throughout 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 t J represents the capacity, to be constructed, of edge 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. The 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 min imum total cost d • b — Y^i<i<j<nd>ijbij. We note that the decision variables 6 = (6 t J) are allowed to assume noninteger nonnegative values. 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 opt imal solutions to this network synthesis problem would use some nodes in N\T as intermediate points. We call the nonsimultaneous network synthesis problem wi th n nodes and t = \T\ < n demand nodes the Steiner network synthesis problem. The Steiner network synthesis problem is a proper generalization of the network synthesis problem, since for T = N the two are equivalent. A cost allocation problem which is associated wi th 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. This allocation method must be perceived by the users to be fair, since, otherwise, they wi l l not support the implementation of an optimal solution which minimizes the overall construction cost. The thesis consists of four chapters. After an introductory chapter, we analyze, in Chapter 2, the cost allocation problems arising in the equal cost nonsimultaneous net-4 work synthesis problem and the simultaneous network synthesis problem, while Chap-ters 3 and 4 are devoted to the Steiner network synthesis problem. More specifically, Chapter 3 is concerned wi th a simplifying transformation, while in Chapter 4, we present the case when the solution network has to be embedded in (i.e., restricted to) some spe-cial 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 Coopera-tive Game Theory In many cases, the nodes of the network to be designed represent users or communities wi th conflicting interests, who may find it advantageous to cooperate and bui ld the network. Moreover, the total construction cost of the network has to be fully financed by the users. The question arising here is how to allocate this construction cost among the users or nodes in a 'fair ' way. We wi l l use cooperative game theory to answer this question. Before discussing the game-theoretic approach, we need to 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: 2N —> 9t, wi th c(0) = 0, be a characteristic function defined on all the nonempty subsets S C JV, referred to as coalitions. The pair (JV; c) is called a (cost) cooperative game in characteristic function form (see Von Neumann 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) = Yljes Xj. If x € 9t n satisfies x(N) = c(N), then x wi l l be referred to as a cost allocation vector. The core C[(JV;c)], see e.g., Gil l ies [57], of a (cost) game (JV;c) is the set of al 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 Let 7r be a permutation of N = { 1 , 2 , . . . , r e } , and let II be the set of al l such permutations. For h £ N, let Sh(n) be the set of elements of 7r to the left of (preceding) h in 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{<Sh(^U{h})-c(Sh(n))). n- wen Thus , the Shapley value is an apriori expected value to a player for joining a game [131]. In general, the Shapley value is not contained in the core of the associated game. Given a game [N;c) and a cost allocation vector y, form a vector 6(y) e 9 J 2 " - 2 , and let its components be the values c(S) — y(S), S ^ 0, S C TV. Next , arrange the components of 6(y) in a nondecreasing order, i.e., h > g 9h{y) > 0g(y). Let the symbol denote the lexicographic order. The cost allocation vector u is the nucleolus of (N;c), see Schmeidler [130], if 0(v) >z 6(y) for all cost allocation vectors y. The nucleolus is consistent w i th the maximin criterion of Rawls [123], which advocates maximiz ing the min imum benefit obtained by any individual . In contrast wi th 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. The 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 Chapter 2 of the thesis, i.e., they arise naturally in mathematical programming problems. For a survey of cost allocation methods in general, see Young [162], and for a survey of cost allocation problems arising from mathematical programming problems, see D . Granot 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 al location. The assignment game, introduced by Shapley and Shubik [133] (see also Gale and Shapley [52]), considers a set N\ of buyers and a set iV 2 of sellers in a market in which 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. Let TV = Ni U JV~2, and let v(S) denote the maximum benefit that the members of a coalition 6 S C N can generate. Thus, v{S) = max{ E . e s n N , E j e s n N 2 : Eiesruv, < 1, J £ S n JV 2, Y^jesnN2 xij < 1, i £ SnJV] , x,j (E {0,1} }, where x t J- = 1 if buyer i and seller j strike a deal, x,j = 0 otherwise. Then, the revenue game (N;v) is called the assignment game. The core of the assignment game coincides wi th the set of optimal dual solutions associated wi th 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 pro-gramming problem when the resources are owned by individuals wi th conflicting in-terests. Individual i, of the set of individuals JV, possesses b\ units of the resource k, k = 1,... ,m. The 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 produc-t ion function is assumed to be linear, with a technology matrix A £ 3ft m x p. Further, it is assumed that for any coalit ion S C N, bk(S) = E i e s ^ ' & = l , . . . , m . The linear production game is the pair (N;v), where v(S) = max{ cx : Ax < b(S), x > 0} is the revenue to S C JV. If y = (yk) is an optimal dual solution for the linear programming as-sociated wi th 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 in network flow problems in which the edges of the network are owned by different individuals. Let the capacity of edge k be <ifc, and let the resource vector of individual i be b' = (b'k), b'k = dk if i controls k, b\ = 0 otherwise. Further, let Xk denote the amount of flow through edge k, and let x = (xk). It is well known that the network flow problem can be solved as a linear programme. Thus, the network flow games are special cases of the linear production game, where the technology matrix A reflects the capacity constraints 0 < x < d and the conservation of flow constraints Ax — 0. If edge capacities are all one unit, then al 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]. Locat ion games arise when a group of users D — {pi ,P2 5 • • • ,Pm} find it advantageous to cooperate and bui ld a number of facilities in some candidate sites C = { q ± , q2, • • •, The cost of bui lding a facility in the location qj is Wj > 0, which is independent of the other constructions. Let w(S) be the min imum 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 wi th in an r, kilometer radius of p^. The location game is represented by the pair (D;w). Let the matr ix A € * R m x f c be such that its i-j 'th component Aij = 1 if qj is w i th in r, kilometer radius of p t , = 0 otherwise. Then the location problem can be formulated as min{ X ^ - i WjVj '• Ay > 1, yj 6 {0,1} }, where y — (yj), y_, = 1 if a facility is open in the site qj, yj — 0 otherwise. Tamir (147] studied the case when the users, the facilities, and the travel routes can be embedded on a tree network. In this special case, Tamir [147,148] showed that the location game is a special case of the linear production game, and that the core of the location game coincides with the set of opt imal dual solutions. Spanning tree games, which were motivated by Claus and Klei tman 's [34] cost al-location analysis in a tree, were first introduced by Claus and D . Granot [33], B i r d [19], and Granot and Huberman [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. The 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 min imum cost spanning tree connecting every community in S to 0, where E$ is the edges of the tree. Further, let C{S) = X)(i,j)eE.y ct 'r Then, the pair (JV;c) represent the min imum 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. Granot and Huberman [67] have shown, beside other things, that if TN = (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 path between j and the central supplier 0, then (x1,x2, •.. ,xn) 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]. Two special cases of the spanning tree games are the airport game and the tree network game. The airport game, first studied by Thompson [151] and later by, for example, Li t t lechi ld and Owen [91], Li t t lechi ld [89], Li t t lechi ld and Thompson [93], and Dubey [43], is concerned with the fair allocation of the construction cost of an airport runway among the aircrafts which use i t . The kth smallest aircraft type requires a runway whose construction cost is ck > Ck-\, k = 1,2, . . . , n , c 0 = 0. Further, c(S) = max{ ck : S n TV*. ^ 0 }, S C TV. The nucleolus of airport game can be computed in 0 ( n 2 ) , see [89]. The Shapley value <f> — (<^ »,) of the airport game is explici t ly given by 8 <f>i = </>,_! + (c,- — c , _ i ) / Y!k=i mki where is the number of landings of type k aircrafts, and cj>o — 0. The tree network game, studied by Megiddo [107], is both 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. The nucleolus of the tree network game can be computed in O(rc-logn), see Ga l i l [53]. The 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 . Granot [62], relaxes the addit ivi ty constraint bk(S) = Y.ies°\^ ^ ~ 1,2, . . . , m , in the linear production game. D . Granot [62] considers each resource k separately, and introduces the resource games (N;bk), 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 net-work 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 in i t ia l endowments. Let UJ(XJ) be the uti l i ty to individual j of having a vector Xj of commodities, and let o ; be his ini t ial endowment of the commodities. Then, for each coalit ion S C N = { l , 2,..., n}, let u(S) = max{ T,jes uj{xj) '• iZjes xj = T,jesaj, J £ S }. The pair (N;u) represents the market game. The core of the market game is nonempty, see [133]. 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 al l subgames induced by al l 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 Dubey and Shapley [44]. Non-atomic games, see e.g., A u m a n n and Shapley [5], extend the theory of coop-erative games to games wi th infinite number of players. Briefly, in non-atomic games, ( I , C) is a measurable space, where J is the set of players and C is the cr-field of measur-able subsets (coalitions) of / . Further, v is a real-valued set function defined on C, wi th t>(0) = 0. The pair (/; v) is called a non-atomic game. The Aumann-Shapley value, <^>, 9 of a non-atomic game satisfies a set of axioms similar to those satisfied by the Shapley value. Let 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 th 0 < |M(^)| < |A*(-S") | - Let / be a continuously differen-tiable function on the range R of p, wi th / ( 0 ) = 0 . Then, when R has dimension n, A u m a n n and Shapley [5] proved that To motivate non-atomic games, we describe how it may be applied in a production set-t ing, where n infinitely divisible commodities are produced. Suppose that f(p\, fa, • • •, pn) is a cost function wi th / ( 0 , 0 , . . . , 0 ) = 0 , where the variable pk denotes the nonnega-tive quantity of commodity 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 pk — J fJ-(tp,1(I),tp,2{I), • • • ,tpn{I)) • dt. Thus, the Aumann-Shapley o f l k value 4> of a subset of commodities S is 4>{f o p)(S) = J2k=i ^kiS) • pk, i.e., the quanti-ties of different commodities in S times their (Aumann-Shapley) prices. Two notable applications of Aumann-Shapley prices are in telephone and transportation networks. Bi l le ra , Heath, and Raanan [17 ] studied the internal telephone bi l l ing 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 in the Uni ted States. Each 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 month would be charged an additional amount. The 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, Bi l lera , 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, Bi l le ra , Heath, and Raanan 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. The Aumann-Shapley prices have actually been used at Cornel l university to determine the internal telephone bil l ing rates since 1 9 7 8 . Samet, Tauman, and Zang [ 1 2 8 ] used the Aumann-Shapley prices in the transporta-10 t ion problem. The transportation problem is to route an economic good in a cheap-est way from some suppliers to some demand points. The cost allocation problem is how to ' fair ly ' 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, Tauman, 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 fur-ther research advocating the use of Aumann-Shapley value, especially in production, see [16,18,108,109,110,127,161]. Next, we survey some other papers advocating the use of cooperative game the-ory 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 which suggested the use of the core and other game-theoretic solutions, especially in pricing policies of regulated monop-olies, are reported in [48,136,137,164]. The research in [27,30,79,88,95,96,126,142,154] advocates the use of game theory and Shapley value in 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 Talmud, for which, for quite a while, a unified explanation was not available. Aumann and Maschler used cooperative game theory to provide the unifying ground, and showed that the solutions to these problems prescribed by the Talmud are precisely the nucleoli of the corresponding cooperative games. Joint cost allocation arises often in multipurpose reservoir development. Suppose that a dam 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. The dam can be built to different heights, depending on which purposes it w i l l serve. The cost function usually exhibits decreasing marginal cost upto a cri t ical height of the dam, above which marginal cost wi l l be increasing due to technological l imitations. The water resource planning problem is how to allocate the costs among the different purposes. This problem dates back to the creation of the Tennessee Valley Author i ty ( T V A ) in the 1930's, see Ransmeier [121], Parker [119], and Straffm and 11 Heaney [145]. The 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. Al though 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 ) . This 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 in Tijs and Driessen [152]. The S C R B method can be described as follows. The Separable Cost of a purpose i G N is its marginal cost s,- = c(N) — c(N\{i}). The Remaining benefit to i (from cooperating) is — c({i}) — S j . The S C R B method assigns the cost allocation vector x = (Xi), Xi - s{ + —[ C(JV) - £ 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 Xp = $195,951 for power, out of a total cost of $412,584. 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 telecommuni-cation networks, see [3,6,25,31,38,90,111,124,138,143,149]. For economics and finance applications in cost allocation in airport management, see [9,29,87]. For other methods of cost allocation (e.g., min imum resource allocation, activity level, net realizable value, independent cost proportional) suggested in accounting li t-erature, see [7,8,10,21,22,25,26,35,46,54,71,72,73,78,83,86,98,112,150,157]. For some ac-counting reasons for allocating joint costs, see [8,165]. For surveys of corporate allocation practices, see [51,104]. Mot iva ted by the numerous papers cited above, we employ in this thesis the coopera-tive game methodology to analyze cost allocation issues which arise in 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 character-istic function form, and prove that they are concave games. 12 • The 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 wi l l present an irredundant representation of the core, which we then employ to derive an explicit closed form expression for the nucleolus of the game when the requirement struc-ture is a spanning tree. Further, we wi l l develop a decomposition of the game in a special case, which we later use to efficiently compute the Shapley value of the game when the requirement structure is a tree. This decomposition wi l l also be used to decompose the core and the nucleolus of the game in the special case. • For the simultaneous network synthesis game, we wi l l also present an irredundant representation of the core, which we wi l l employ to derive an explicit closed form expression for the nucleolus of the game. Further, we wi l l decompose the core of the game in 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 wi th 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 Gomory and H u [58,59,60], is as follows: Minimize E cij°ij l<i<j<n Subject To £ btj > rQ 0 ^ Q c N (i'.j)e(Q.w\G) l < t < J < n bij > 0 1 < i < j < n , 13 where (Q, N\Q) is the set of edges wi th one endpoint in Q C N and the other in JV\ Q, and rQ = max{ r{j : i G Q, j G N\Q }. Since, in general, every constraint in the above L P formulation is irredundant, see B l a n d , Goldfarb, and Todd [20], the linear programming formulation presented above, in general, cannot be simplified any further. This implies that, in general, to solve the network synthesis problem we need to solve an L P problem with 2 n ~ ] — 1 + n' inequalities. However, for any given instance of the problem, many constraints are redundant. This redundancy generally depends on both the requirement structure and the cost structure. Thus , one is led to consider some special cases of the requirement structure or the cost structure. Recall that Gomory and H u [58] considered the special cost structure when all unit construction costs are equal. F i rs t , as a special case of the requirement structure, we wi 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 problem by assuming that the positive requirements between pairs of nodes in T are equal. This case, i.e., the equal positive requirements sparse requirement structure case wi l l be considered in Chapter 3. For this case, we wi l l present a transformation to simplify the compu-tations. Expl ic i t ly , we transform the equal positive requirements sparse requirement structure Steiner network synthesis problem into a smaller network synthesis problem wi th nodeset T and wi th distances equal to the shortest (cheapest) distances in the original problem. We then solve the smaller network synthesis problem, possibly using a linear programming algori thm, and we transform an opt imal solution subnetwork back to the original problem. We wi l l prove, using the linear programming duality, that the transformed solution is indeed an opt imal 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 iv ia 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 wi th a smaller problem where for each requirement rjk, k there is a new requirement J-,-* of the same magnitude. However, the case when some unit costs are very large (infinity) is interesting. This effectively implies that the edges wi th 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 wi l l consider, in Chapter 4, the special cases when the solution network has to be embedded in trees, rings (cycles), series-parallel graphs, or M 2 a n d M 3 -free graphs. A series-parallel 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 path (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. Thus, we are interested in 'edge' or 'two terminal ' series-parallel graphs which are also considered in, e.g., [14,36,74,153]. A M 2 and Ms-free graph is a graph which does not have M 2 nor M 3 as a minor (see Figure 3.4 for a display of M2 and M 3 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, isolated-node deletion, and edge contraction (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 (u,v)). We note that rings (cycles) are special cases of series-parallel graphs, and we wi l l prove, in Section 4.3, that series-parallel graphs are special cases of M2 and M 3 -free graphs. 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. This fact enables us to solve the Steiner network synthesis problem in the above special cases by some combinatorial algorithms. Moreover, we wi l l show, by Example 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 optimal solution more complicated. Even 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 M2 and M 3 - f ree graphs, there is a lot of scope for application. To demonstrate this, we briefly describe the paper by Ratl iff and Rosenthal [122]. In [122] entitled 'Order -P ick ing 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. Problem' , Ratl i ff and Rosenthal described a rectangular warehouse which is displayed in Figure 1.1. It can easily be seen that this graph is series-parallel. The horizontal edges represent cross-overs, each 2 meters long, and the vertical paths represent aisles, each 15 meters long. The thicklined nodes on the vertical paths, except the one on the 3rd vertical path from the right, represent items which need to be picked up at a point in t ime. The position of each item can be discerned by the numbers, distances in meters, on the graph, and each i tem is located on either side of an aisle. The current position of the forklift is represented by the thicklined node on the 3rd vertical path from the right. The forklift is supposed to collect all the ordered items and return to its starting point with the ordered items. To save time and costs, it is desirable that the total distance travelled by the forklift is minimized. It is clear that the movement of the forklift describes a Steiner tour, i.e., a cycle vis i t ing each demand node at least once. Thus , Ratl iff 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 wi th 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 opt imal communication and electrical networks which should satisfy some connectivity requirements. For example, suppose that the graph in 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. Then, the problem of designing a min imum length line-failure immune network is exactly the Steiner network synthesis problem wi th requirements equal to 2, considered in Section 4.1.2. Chapter 2 C O S T A L L O C A T I O N IN T H E N E T W O R K S Y N T H E S I S P R O B L E M 2.1 Introduction, Notation and Preliminaries 2.1.1 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 cal l . The main problem in communication network design is to determine which pair of nodes to connect wi th 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 minimum cost and the edge capacities are large enough to satisfy requirements for every pair of users. A user is associated wi th 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 min imum number of possible calls between the pair at time r . If the requirements are independent of time and have to be satisfied simultaneously for al l pairs of users, then the problem of finding a min imum 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 nonsimultaneous 17 18 network synthesis problem [59,158]. The input data in both cases consist of integers Tij, rij = rji > 0, which are the requirements between users i and j , and numbers duv, duv = dvu > 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. Gomory and H u [59], also see Wing and Chien [158], formulated the nonsimultaneous network synthesis problem as a linear programming problem wi th a large number of constraints, and devised a row generation technique for solving it. Furthermore, in [58] (see also [158]), Gomory and H u provided a very efficient method for solving the equal-cost nonsimultaneous network synthesis problem, i.e., when duv — dv>ui for every two pairs of nodes {u,v} and {u1, v'}. Of course, we can assume, without loss of generality, that in the equal-cost case, dav = 1 for every pair of nodes {u,v}. The solution to the simultaneous network synthesis problem can also be found very efficiently, see Gomory and H u [60]. Specifically, starting from a zero capacity network, it is only necessary to find a shortest (cheapest) path 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 in Chapter 2 of this thesis is to analyze cost allocation problems which naturally arise in the above network design problems, namely, how to allocate the cost of constructing the communication network among the various users. This is a crucial problem, 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 opt imal . We wi 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 wi th cost rather than revenue allocation issues which are usually associated wi th cooperative games. Therefore, tra-dit ional inequalities in game theory should be reversed. The symbol '0' w i l l denote the empty set, ' c ' denotes 'is properly (strictly) included in ' , 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, and let c:2N —> 3?, w i th c(0) = 0, be a characteristic function defined on nonempty subsets of JV, referred to as coalitions. The pair (JV;c) is called a (cost) cooperative game in characteristic function form (see Von Neumann and Morgenstern [155]), or for short a game. It is assumed that all the strategic essence of the game is summarized in the characteristic function. Thus, games in characteristic function form are more abstract than games in strategic form which actively utilize a lot more strategic information, see [155]. Orig-inally, Von Neumann 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, in many situations, c(5) can be interpreted as the best the subset S can do as a coalit ion, assuming that the other players do not care. This assumption is used throughout Chapter 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, see e.g., Shapley [132], if for any part i t ion of N, {Ni,..., Nh}, h > 2, and for every subset S C JV, J2c(SnN9)=c(S). 9=1 For a vector x G 5?" and for a subset S C JV, let x(S) = J2jes xj- If x G 9f" satisfies x(N) = 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. The above inequalities are referred to as the 'stand-alone cost 20 tests' in some papers, see e.g., Young [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>h(c)) e ft" given by ^ ) = k ( » ) u W ) - « ) ) ) -Although, the Shapley value always exists, it may not, in general, be contained in the core. For concave games, however, the Shapley value is always contained in the core, and, in fact, coincides wi th 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 : £ f c ^ f c ( c ) = ^AO-S y m m e t r y : If for a pair of players p and q, and for al l subsets 5 C N, S $ p,q, we have c(S U {p}) = c(S U {?}), then 4>p{c) — cf>q(c). 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)p{c) = 0. A d d i t i v i t y : If any three characteristic functions c, c', and c", defined on al l subsets of N, satisfy c(S) + c'[S) = c"{S), S C TV, then 4>h(c) + d>h(c') = <j>h{c") f o r a 1 1 players h. 21 It can be shown, see e.g., Young [162], that the Shapley value is also monotone, i.e., an increase in the cost of a particular coalition implies, ceteris paribus, no decrease in the allocation to any member of that coalition. This 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 ex(5, x, c) = c(S)—x(S) be the excess of coalition S wi th respect to x in a game (N;c). For two players p and q, let spq(N, x, c) = min{ ex(S, x, c) : S C N, S 3 p, S 73 q }. The kernel for the set of imputations of a game (N; c), wi th respect to grand coalition, see Davis and Maschler [39], is the set of all imputations x such that either spq(N,x, c) < sqp(N,x,c) or xq = c({q}), for all {p, q] C JV. The pre-kernel for the set of pre-imputations is the set of all pre-imputations x which satisfy spq(N,x,c) — sqp(N,x,c), {Pi<l} Q N. For concave games, the kernel and the pre-kernel coincide, see [102,103]. The kernel always exists, see [39], and if the core is nonempty, the intersection of core and kernel is nonempty and possesses nice geometric properties, see Maschler, Peleg, and Shapley [103], which are useful in studying the nucleolus described next. Given a game (N;c) and a cost allocation vector y, form a vector 6(y) € 3 f 2 ' - 2 , and let its components take the values ex(5, y,c), such that each component takes a value associated wi th a distinct nonempty proper subset S C N. Next , arrange the components of 6(y) in a nondecreasing order, i.e., h > g => 6h{y) > Ogiu)- Let the symbol '>:' denote the lexicographic order. The cost allocation vector v is the nucleolus of (N;c) if 6{u) > 6(y) for all cost allocation vectors y. The nucleolus, which was introduced by Schmeidler [130], always exists and is contained in the kernel. When the core is nonempty, the nucleolus is contained in i t . 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], implying that for this class of games, the nucleolus and the kernel coincide. Unfortunately, the nucleolus is not monotone, see Megiddo [105]. However, this is true for any other solution method which yields a vector in the (nonempty) core, see Young [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 vh(a • c + /?) = a • Vh{c) + For a variant of the nucleolus, where the benefits are measured per capita, i.e., ex (x ,S , c ) = (c(S) — x ( 5 ) ) / | 5 | , see Grotte [69]. 2.1.3 Graph Theory Notation and Preliminaries Throughout this thesis, we wi l l only consider undirected simple graphs, i.e., undirected loopless graphs wi th no multiple 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 in TV, called the edge set of G. A network is a graph wi th weights associated wi th its edges. The networks induced by the solutions to the simultaneous and the nonsimultaneous network synthesis problems wi l l be refered to as solution networks and wi l l be denoted by G\ = (N,El) and G\ = (N,E$), respectively, where 6*u (resp., b2uv) is the capacity or weight associated wi th edge (u,v) £ El (resp., El)'. The capacity of an edge is zero if and only if the edge does not exist. In Chapter 4, we wi l l consider some special cases when some edges do not exist, in which case, for emphasis we wi l l refer to Gl as the solution subnetwork. We wi l l also need to represent the requirements as an undirected network GT = (N,Er), referred to as the requirement structure, where [i,j) £ Er if r,j > 0, and rtj is the weight associated wi th (i,j) G ET. A path or a walk from i\ to u in a graph G — (N,E) is specified by an alternating sequence of nodes and edges (ii, i2), i2, (&2> * 3 ) , • • • , {ih-i, H such that ij G TV, j = l,...,h, and (ij~i,ij) G E, j' = 2 , . . . , h. A simple path is a path wi th distinct nodes. A cycle or a circuit is a path from a node to itself, i.e., i j = th- A simple cycle is a cycle w i t h distinct nodes. A Hamiltonian cycle is a simple cycle visi t ing all the nodes. A graph is connected if there is a path 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 Chapter 2, we wil l assume that the requirement structure Gr is always connected, since, otherwise, by their solution methods, the equal cost nonsimultaneous and the si-multaneous network synthesis problem, and, by the definition of a decomposable game above, the induced games can be decomposed and analysed separately for each con-nected component. Furthermore, we wi l l 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]). For any requirement structure, every max-imum requirement spanning tree in it induces the same optimal solution networks as the requirement structure for both the simultaneous and the nonsimultaneous network synthesis problem. • Figure 2.1 above displays a requirement structure and a maximum requirement spanning tree ( M R S T ) in it. Essentially, Gomory 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 in the requirement structure, then decompose the M R S T into a minimum number of equal-requirement subtrees, next solve the problem for each equal-requirement subtree to get optimal solution subnetworks, and finally superimpose the derived subnetworks. Example 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 equal-requirement subtrees it decomposes into are displayed in Figure 2.2. Op t ima l solution subnetworks, one Hamil tonian cycle of half the requirement's capacity for each equal-requirement subtree, are displayed in Figure 2.3. Final ly, the superimposed optimal solution subnetwork is shown in Figure 2.4. We observe, from Figure 2.4, that the min imum total cost = min imum total capacity = 19, and, from Figure 2.1, that the sum of the maximum requirement of each node is 9+6+9+7+7 = 38, twice the min imum total cost. Indeed, this is true for any instance of the equal cost nonsimultaneous network synthesis problem, and easily follows from Gomory and Hu's algori thm [58]. • 24 Figure 2.2: The Equal-Requirement Subtrees. Figure 2.3: Opt imal Solution Subnetworks for the Equal-Requirement Subtrees. Figure 2.4: The Superimposed Opt imal Solution Subnetwork. 25 The remainder of this section consists of some notation and definitions, most of which, except the last paragraph, are used in Chapter 2. Let a requirement structure Gr — (N,ET) be given. A subset S C TV is connected in Gr if for every pair of nodes hj S S, there exists a path between i and j in Gr which uses only the nodes in S. In connection wi th 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 Gr, but wi l l 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. The resulting enlarged subset, denoted by S, wi l l be referred to as the closure of S wi th respect to Gr. 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) £ Er, i,j £ S}. A subset S is said to be closure-connected in Gr if S is disconnected, but its closure S is connected. For a disconnected subset S C TV, let {Ri, R2,..., Rh} denote a parti t ion of S into nonempty connected subsets. We say that {R\,..., Rh} is a minimal partition of S if it has a min imum number of components, i.e., h is min imum, 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,R2}, Rx = {1,2}, R2 = {5,6,8}, is a minimal part i t ion of S. Given an edge £ Er, let TV, (resp., TV,-) denote the collection of nodes, including node i (resp., j), from which there is a path in Gr to node i (resp., j) that does not pass through node j (resp., i). For example, in Figure 2.7, for edge (4,5), TV4 = {1,2,3,4} and TV5 = {5,6,7,8}. We observe that, in general, TVjHTVj ^ 0. However, if TV.-nTV,- = 0, then is a bridge, i.e., the removal of w i l l decompose Gr into two connected components. If TVj n TV, = 0 for every edge £ Er, then Gr is a spanning tree. We 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 Gr, where two nodes i and j are adjacent if (i,j) £ Er- For example, in Figure 2.7, for edge (4,5) M 4 = {2} and M 5 = {6,7,8}. Throughout the thesis, we wi l l find it convenient to represent the nodes TV and the costs d = (dij) by a network G = (N,E), where E 3 (i,j)' if the unit cost < oo, and the weight (length) of any edge (i,j) 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 wi l l use the terminology of the Steiner network synthesis problem in network G. Further, for each pair of nodes i,j £ JV, we let d'^ denote the length (cost) of a shortest (cheapest) path between nodes i and j in G. 2.2 Concavity of the Network Synthesis Games In this section, we formally introduce the simultaneous and the nonsimultaneous network synthesis games. We wi 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., c2(S)) be the min imum cost incurred by coalit ion S if its members construct a 'separate' optimal solution network that satisfies simultaneously (resp., nonsimultaneously) their communication require-ments. It seems plausible to let these communication requirements be r t J , i £ S, j £ JV. This ascertains that members of S w i l l acquire their requirements regardless of the action taken by the other users. We define ci(0) = c2(0) = 0, and refer to the pair (JV;cj) (resp., (JV;c2)), wi th the characteristic function c\ (resp., c 2) defined above, as the simultaneous (resp., the nonsimultaneous) network synthesis game. When all unit costs are equal (or duv = 1, u,v £ JV), we obtain the equal cost network synthesis games. Since, in Chapter 2, we only analyse the equa7 cost case of the nonsimultaneous network synthesis game, we let (JV; c 2) refer to this game. E x a m p l e 2.2. Consider the requirement structure Gr = (JV,E r ) , shown on the top left corner of Figure 2.5, where the requirements are shown on the edges and the unit costs are equal to one. Let b^v(S) (resp., ^ ( S ) ) be the optimal capacity of edge (u,v) in a separate optimal solution network which satisfies the requirements of coalition S simultaneously (resp., nonsimultaneously). It can be verified, using Gomory and Hu's algori thm [58] outlined in Subsection 2.1.3 above, that 6f2({l}) = 1, ^({l}) = 3, ^Ldl}) = 1> a n < ^ therefore c2({l}) = 5. See Figure 2.5 for the solution networks, where each unit capacity is represented by a line. Similarly, &i 2({2}) = 1, ^ 3 ( { 2 } ) = 1, bh(I2)) = 5 ' a n d therefore c 2 ( { 2 » = 7. Final ly , for every other nonempty subset S C JV, b2n(S) = 2, b\3{S) = 2, bj3(S) = 4, and therefore e2[S) = 8. Furthermore, it is easy to verify, using Gomory and Hu's algori thm [60] outlined in Subsection 2.1.1, that 6} 2({1}) = 2, b\3({l}) = 4, 6 | s « l » = 0, and therefore (^{l}) = 6. Similarly, 27 Figure 2.5: A Requirement Structure, and the Opt imal Solution Networks. 6} 2({2}) = 2, b\3{{2}) = 0, b\3{{2}) = 6, and therefore C l ( { 2 } ) = 8. Also , &} 2 ({3» = °> 6 i s ({3}) = 4> ft2s({3}) = 6> a n d therefore ^ ({3} ) = 10. Final ly , for every other nonempty subset S C JV, 6j 2(S) = 2, 6} 3(S) = 4, b\3{S) = 6, and therefore ^ ( 5 ) = 12. • We next prove that the equal cost nonsimultaneous and the simultaneous network synthesis games (JV;c 2 ) and (N;c\) are concave. Fi rs 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 max{ wjk : 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. Let i G TV and T C U C N\{i}. Then , for every j in T , max{ wjk : k G T V \ T } - max{ wjk : k G N\[T U {i}) } < max{ u; i A : : k G TV\C/} - max{ wjk : k e N\(U U {i}) }. (2.1) Furthermore, by definition of 6(-) we have 6(T)-6(Tu{i}) = J2m&x{wjk:keN\T}- Y, max{ Wjk : fc G T V \ ( T U {?}) } >er jeTu{t} < ^ m a x { w y t : k G TV\£7 } - 51 max( w:k • k G N\(U U { t '» }, by (2.1) j'er j'eru{t} = 53 max{ wjk : k G N\U} - 53 max{ u; j f c : k G TV\C7 } jet/ >ei/\r - X] max{w;jjt : k G N\(U U {i}) } + 51 m a x { u ; ^ : A; G T V \ ( f / U {i}) } ie^u{i} jeu\T = ^ max{u(, ' i : k G TV\C/} - 5Z max{ w y t : A: € JV\(I7 U {t}) } j'ec j'6t/u{t} -f 51 ( m a x ( w i f c : kE N\(U U {i}) } - max{ u;,- t : A; G TV\£7 }) < 53 maxliwj-j. : fc G N\U} - 51 max{ tuyjfc : k G N\(U U {i}) } jet/ >et/u{t} = S(U) - S(U U {»}). Thus, 6(Tu{i})-S(T) > 6(U U {t}) - 6{U), which proves the submodularity of 6. The submodularity of a follows using identical arguments, or alternatively, see Lovasz [100]. Now, we are ready to prove the submodularity of c x and c 2 . Theorem 2.1. The characteristic functions C\ and c 2 are submodular set functions 29 on subsets of N. P r o o f . Considering C j first, recall that we denoted by d'jk the length (cost) of a shortest (cheapest) path between nodes j and k. It follows from Gomory and H u [60] that for every subset 5 C JV, Ci(S) = E E r]kd']k+ E Y.r]kd'k j€S k£S, k>j k£N\S j€S = I T , Hrikd'jk+ E E r>k4fc = (^E S > i * 4 * + E Y.r3kd'jk). (2.2) j'es fceAr ifceAr\5 jes A similar formula follows, by Gomory and H u [58], for c 2 and every subset S C JV, c2(-5) = ^(Em a x( rifc ^ m a x { r j t : ^ S } ) , (2.3) because the right hand side of (2.3) is a lower bound on the cost of constructing a network which satisfies, nonsimultaneously, the requirements rjk, j 6E 5 , k £ N', and Gomory and H u [58] proved that this lower bound can always be achieved. Now, we observe that the first expression in the right hand side of (2.2) (resp., (2.3)) is an additive (or modular) set function on subsets S of TV, because YlkeN rjkd'jk (resp., max{ Tjk : k £ N }) does not depend on S. The second expression in the right hand side of (2.2) (resp., (2.3)) is submodular by Lemma 2.2 if we substitute r (resp., rd') for w, and exchange N\S and S. Since the sum of a submodular and a modular set function is submodular, and since a scalar multiple of a submodular function is submodular, it follows that C\ and c 2 are submodular functions. • The submodulari ty of the characteristic functions imply, by Shapley [132], that the games [N\c\) and ( iV;c 2 ) are concave, and therefore have nonempty cores. Thus, it is always possible to allocate the cost of constructing a communication network among the players or users in a way that no subset of players can be better off by constructing its own separate network. However, the cores of (N; C i ) and (N; c 2) would likely be quite large. Al though one can efficiently (in linear time) generate each extreme point of the cores, provided that the values of C\ and c 2 are available (see Shapley [132]), none 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, in part icular, the Shapley value of the network synthesis games, is contained in the core. Unfortunately, it is computationally impractical 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) in 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, which is slightly more general than a spanning tree. 2.3 Irredundant Representation of the Cores of -(TV; c^) and ( J V ; c 2 ) In this section, we wi l l provide an irredundant characterization of the cores of the network synthesis games (/V;cx) and (7V;c 2 ) . For (JV;ci ) , we wi l l show that the core constraints induced by the subsets of N that are connected and whose complements are also connected, in 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 Figure 2.7, S = {1 ,2 ,3 ,4} is connected wi th N\ S = {5 ,6 ,7 ,8} also connected, whereas S = {6,8} is closure-connected with N\S = {1 ,2 ,3 ,4 ,5 ,7} connected in the requirement structure shown. Recall that given a requirement structure Gr — (N,Er), we let the closure 5 of a set 5 to be S = S U { k £ N\S : (i,k),(j,k) G Er, {i,j} CS}, and that S is said to be closure-connected if S is disconnected but S is connected in Gr. For simplicity of exposit ion, we now present two additional notation: IS(Gr) 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., 7S{Gr) = { S C N : both S ^ 0 and N\S are connected in Gr}, and JH S {Gr) w i l l denote the collection of all nonempty connected or closure-connected subsets of TV, whose complements are connected in Gr, i.e., TM S(Gr) = JS{Gr) U { S C TV : S ^ 0 closure-connected, N\S connected in Gr}. The following lemma regarding the cost structure of a connected or a closure-connected subset, whose complement is disconnected, wi l l be used subsequently in Theorem 2.2 below. For an example of a closure-connected subset, whose comple-ment is disconnected in the requirement structure GT displayed in Figure 2.7, consider S = {1,3 ,4 ,5} which is closure-connected, but N\S — {2,6 ,7 ,8} is disconnected in Gr. Lemma 2.3. Let Gr = (N,Er) be a requirement structure which induces the net-work synthesis games (N;ci) and (TV ; c 2 ) , and let S be a connected or closure-connected subset of N whose complement N\S is disconnected in Gr. If {R\,... ,Rh} is a minimal partition of N\S, then for a = 1,2, E ca(N\Rg) = {h-l)- ca(N) + ca(S). Proof. Let Tf be the set of nodes in Rf which are adjacent to at least one node of S in G r , i.e., Tf = {p E Rf : {p,q) G Er, q G 5 } , / = l,...,h. F i rs t , we wil l prove the lemma for c 2 . Let c'2(U) = | Y^peu m a x { rpq : q £ N }, U C TV. We note that c'2(N) = c2{N). B y (2.3), c2(N\Rg) = c'2(N\Rg) + W m a x { r p ? :qeS}. z per, Summing over g = 1 , . . . , h, we get t,C2(N\Rg) = Ec'2(N\Rg) + l Y , E m a x { r « : ? e S } 3=1 3=1 3=1 p€Tg 32 h j h = h • c2{N) - £ c'2{R9) + - E E MAX{ rpq:qES} 3=1 Z 3=1 p€Tg = (h - 1) • c2(N) + c'2{S) + \]t E ^ ( r P r ^ S } 3=1 P6T9 = ( / i - l ) - c 2 ( J V ) + c 2 ( S ) , by (2.3). Now, to prove the lemma for c i , substitute zZqeN rpqd'pq for max{ r p 5 : q £ J V } , and S 9 e s rpqd'pq for max{ r p g : </ £ 5 } in the above equations. The result follows identically. • In Theorem 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 x) and (JV; c 2 ) . Theorem 2.2. The core constraints induced by the nonempty members of JS(Gr) (resp., J SI S(Gr)) and the constraint x(N) = Ci(JV) (resp., x(N) = c 2(JV)) are sufficient to completely describe the core of the network synthesis game (N;ci) (resp., (JV;c 2)) induced by the requirement structure Gr = (N,Er). Proof. We wi l l show that al l the other core constraints for (JV;c x ) (resp., (JV;c 2 )) are implied by the constraints associated with the nonempty members of JS (Gr) (resp., JMS(Gr)) and the constraint x(N) = Ci(N) (resp., x(JV) = c 2 (JV)). Consider a core constraint induced by a connected (in case of (N;ci)) or possibly closure-connected (in case of (JV;c 2 )) subset S C JV, whose complement N\S is disconnected in Gr. Let {Ri,. . . ,Rh} be a minimal parti t ion of N\S, and let x be a point in the core of the induced game (JV;cj) (resp., (JV;c 2 ) ) . We wi l l show that the inequality x(S) < Ci(S) (resp., x(S) < c2(S)) is implied from the inequalities x(N\Rg) < Ci(N\Rg) (resp., x(N\Rg) < c2(N\Rg)), g = l,...,h. We note that the subsets N\Rg are connected (resp., connected or closure connected) wi th connected complements in Gr, and thus belong to JS(Gr) (resp., JMS(Gr)). Therefore, for a — 1,2, (h - 1) • x(N) + x(S) = Yx(N\Rg) 3=1 < £ e . ( J V \ J 2 , ) 3=1 = (h-l)-ca[N)+ca(S), by Lemma 2.3, 33 and since x(N) = ca(N), it follows that x(S) < ca(S). For a subset S C N which is disconnected but not closure-connected (in case of ( J V ; c 2 ) ) or possibly closure-connected (in case of ( J V ; c i ) ) , let {Ri,..., Rh} denote a min imal part i t ion of S, and let H = { l , . . . ,h}. Then , by (2.2) (in case of (TV;c i ) ) and by (2.3) (in case of (TV; c 2 ) ) , we have ca(\jg£HRg) = zZgeH ca(Rg), a = 1,2. We note that for each g G H, Rg is connected, and if N\Rg is also connected, then Rg G TS(Gr) and Rg G 7klS(GT). Otherwise, by the previous paragraph, the constraints induced by the members of 7S(Gr) or the connected members of IMS(Gr) imply that x(Rg) < ca(Rg), a = 1,2. Therefore, for a = 1,2, x{S) = £ x ( i ? 5 ) geH = ca(S). Clearly, a subset N\{i}, i G A^, is either connected or closure-connected and thus belongs to 7US(Gr) and, if connected, to 7S(Gr) as well . However, observe that its associated core constraint can be replaced by a nonnegativity constraint. This wi l l not change the characterization of the core. Indeed, for a = 1,2, x{N\{i}) < x{N), by xi > 0, = ca(N) = c 0 ( i V \ { t » , from (2.2) and (2.3). 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 2) are also necessary for this description. Indeed, Theorem 2 .3. Given a general requirement structure Gr, the core constraints in-duced by the nonempty members of 7S(Gr) (resp., 7M$(Gr)) are, in general, necessary to describe the cores of the induced games (N;ci) and (N;c2), in the sense that for any 34 Figure 2.6: A Spanning Tree Requirement Structure Used in Theorem 2.3. n, one can construct a requirement structure such that the removal of any of the above constraints will introduce vectors which are not in the core of these games. proof. Consider the requirement structure Gr = (N,Er) displayed i n Figure 2.6, where N = { 1 , . . . , re}, re > 2, Er = {(1,2), ( 1 , 3 ) , . . . , (1, n)}, and riy = = 1, £ Er. F i rs t , we analyze the game (TV; c 2) induced from Gr. The core constraints as-sociated wi th the nonempty connected subsets of TV, whose complements are connected, in Gr are Xj < 1, j = 2 , . . . ,71, (2.4) and x(JV\{j}) < n/2 , y = 2, , re. (2.5) The core constraints associated wi th the nonempty closure-connected subsets of TV, whose complements are connected in G r , are x{S) < (s + l ) / 2 , 5 C { 2 , . . . , n } , s = | S | > 2. Now, consider the vector x 1 , J , j = 2 , . . . , re, defined as f ( « - 3 ) / 2 , 3/2, 10, if S= 1; if 9 = i ; otherwise. (2.6) 35 Then , x1^ violates the constraint Xj < 1 in (2.4), but satisfies all the other core con-straints. Next , let z 2 j , j = 2 , . . . , n , be given by if g = i ; if g = i ; otherwise. Then , z 2 ' J violates the constraint x(N\{j}) < n/2 in (2.5), but satisfies all the other core constraints. Similarly, define z 3 , 5 , S C {2 , . . . , r e} , 5 > 2, as ({n-s)/2-l, if 9 = 1 ; x3gs = • 1 /2+ 1/5, . if 0 6 5; , 0, otherwise. Then , x 3 , 5 violates the constraint x(S) < (s + l ) / 2 in (2.6), but satisfies all the other core constraints. Now, for the game (/VJCJ) induced by Gr, the core constraints associated wi th the nonempty connected subsets of / V , whose complements are connected in Gr, are exactly (2.4), and (2.5) wi th n/2 replaced by re — 1. The vector x1'* (resp., z 2 j ) above can be modified by replacing (re — 3 ) / 2 with re — 5 / 2 (resp., 1/2 wi th 1). Then , the above proof follows identically. • In view of Theorems 2.2 and 2.3 above, the constraints associated wi th the nonempty members of 7S[GT) (resp., INS(Gr)) and the constraint x(N) = Ci(N) (resp., x(N) = c2(N)) provide us, in some sense, with an irredundant representation of the core of (TV; C l ) (resp., (7V;c 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{Gr) and IMS(Gr)- Indeed, if edge (2,3) wi th r2z = d2S = 1 is added to Gr in the above example,- then the connected subset 7 V \ { 2 , 3 } , whose complement {2,3} is also connected in Gr, induces the core constraint x(N\{2,3}) < n/2 (resp., z (7V\{2 ,3}) < re — 1) for the network synthesis game (N;c2) (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 ) . ( 3 / 2 , - 1 / 2 , 1/2, 36 Clearly, Theorems 2.2 and 2.3 substantially reduce the number of constraints re-quired to represent the cores of (JV; C i ) and (JV; c 2 ) . In particular, if G> is a simple path, then only 2n — 1 (resp., 3n — l ) constraints are required to describe the core of ( JV ;c i ) (resp., ( JV ; c 2 ) ) induced by Gr. We remark, however, that the redundant core constraints are, in general, not nec-essarily 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 wi th the nucleolus and is unique, it fol-lows that for the network synthesis games (JV; C i ) and (TV; c 2 ) , the nucleolus is uniquely 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 Kopelowitz method [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 wi l l be a polynomial number of these linear programs in the sequence, it follows, by Khachian [84], that whenever the core of a concave game and, in particular, the network synthesis games, can be represented by a polynomial number of constraints, the computation of the nucleolus can also be done in polynomial t ime. However, it is not clear how a reduction of the core constraints can, in general, be used to lessen the computational effort required to find the Shapley value. Nevertheless, we wi l l 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 2 ) whose associated requirement structure is a 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 ) , and for the nucleolus of the game ( J V ; c 2 ) whose associated requirement structure is a spanning tree. Given a (general) requirement structure Gr = (N,Er), consider the vectors \i = 37 fij - ^ max{ rjk : k E N}, and £ = {£,•) e 5Rn, 6' = « E r i * 4 * -We note that both /Li and £ are functions of Gr. F i rs t , we wi l l show that p (resp., £) belongs to the core of the induced game (TV; c 2) (resp., (N;ci)). Later, we wi l l show that £ is the nucleolus of ( T V ; ^ ) , and that p is the nucleolus of (TV;c 2 ), provided that Gr is a spanning tree. Lemma 2.4. The vector u, (resp., £) belongs to the core of (TV;c 2) {resp., (N\Ci)). Proof. We first prove the lemma for p. B y (2.3), c i i s ) = \ (E m a x( rjk:keN}+ E m a x l r i * : k e 5 } ) ;'es j eJV\ s • = KS) + \ E m a x( rjk : k <E S} 1 jeN\s > p{S), where the strict inequality follows because the requirement structure GT is connected. Furthermore, by (2.3), p{N) = \ J2jeN max{ r j J t : k £ TV } = c 2(TV). The strict inequality 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), J2k€N Tjkd'-k for maxf/ -^ : k £ TV }, £ f c 6 5 Tjkd'jk for max{ : k £ 5 }, £ for /x, and C i for c 2 in the above proof. • Recall that spq{N,x,c) = min{ c(5) — x(5) = ex(S,x,c) : S C TV, S 3 p , S ^ q}. Theorem 2.4. £ «s £/ie nucleolus of the game ( T V ;C i ) . Proof. For every subset 5 C TV, by (2.2) and the definition of f, we have ex (5 ,e,ci) = c1(S)-aS) = i (E E ^ + E E rikdfik)-W E ^ 4 * z >es fceTV jes keN\s ies keN 38 jes keN\s = e x ( J V \ S , f , C l ) . Now, 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 x) = min{ ex(S, £, cx) : S C JV, S B p, S $ q). Since ex(5, £, c x) = ex (JV\ 5, £, q ) , S C JV, it must be that J V \ T minimizes { ex(5, £, c x) : S C JV, S 3 q, S $ p}. Therefore, spq(N, £,Cx) = ex(T, £, c x) = ex(N\T, £,C]) = sqp(N, £, c ^ , and the concavity of (JV jC i ) implies that £ is the nucleolus. • The remaining of this section is concerned only wi th the game (JV; c 2 ) . First , recall 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 £V, G 5 } , and that 5 is closure-connected if S is disconnected, but S is connected in G>. Further, for edge G Er, let JV, (resp., JV,) denote the collection of nodes, including node i (resp., j), from which there is a path to node i (resp., j) that does not pass through node j (resp., i). L e m m a 2.5 below wi l l be used subsequently in Theorem 2.5 which proves that (J, is the nucleolus of ( J V ; c 2 ) , if the associated requirement structure is a spanning tree. L e m m a 2 .5. If an edge (i,j) is a bridge in a requirement structure GT = (N,Er) then (i) c 2(JV,) - fi{Ni) = ex(JV,-,/ i ,c 2 ) = ex(Nj: p,,c2) = r,-,-/2, and for every cost allocation y (with e x ( JV , y , c 2 ) = 0), (ii) ex(JV , - ,y,c 2 ) + ex(Nj,y,c2) = r,-,-. In addition, if Gr is a spanning tree, then for every closure-connected subset S C JV with a minimal partition {Ri,..., Rh), whose complement N\S is connected, in Gr (iii) ex(5, p, c 2) > ex(Rg,p,c2), g = l,...,h. Proof. (i) and (ii) follow from the definition of p and (2.3). To prove (iii) , since J V \ S is connected and Gr is a spanning tree, it follows that S\S contains a unique node k. Furthermore, k is the only node in N\S adjacent to some node in S. Now, consider a component Rg of 5 and let / be the unique node in Rg adjacent to k. Then, ex(Rg,p,c2) = rkl/2, by (i) above 39 < - max{ rkp : p £ S }, since / £ S = ex(S, p,c2), by (2.3) and the definition of p. • Theorem 2.5. If the requirement structure Gr = (N,Er) is a spanning tree, then p is the nucleolus of the induced network synthesis game ( JV;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, c2) — ex(U, c 2 ) . B y Theorem 2.4 and Lemma 2.5 (iii) above, we can assume that U is the node set of a maximal connected subtree rooted at some node k, on the unique path between p and q, which does not contain q, i.e., U 3 p,k, U q, and U, N\U are connected in Gr. Let / be the node in Gr which is adjacent to k and is on the unique path between k and q. B y Lemma 2.4 (i), ex(U, p,c2) = rkl/2. Therefore, if edge has a min imum requirement among all the edges on the path between p and q, then we must have that spq(N,p,c2) = ex(JV,,/z, c 2) = rij/2. Similarly, sqp(N,p,c2) = ex(Nj,p,c2) = rij/2. Thus, spq(N,p,c2) = sqp(N,p,c2) for every pair p,q £ JV, and the concavity of (N;c2) implies that /x is the nucleolus. • Example 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. Example 2.3. Consider the requirement structure Gr = (N,Er) displayed on the top left corner of Figure 2.5, where the requirements are shown on the edges and the unit costs are equal to one. The vector p for Gr is equal to (2,3,3), but one can easily verify that the nucleolus of the induced game (N;c2) 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. Fi rs t , given a requirement structure Gr = (N,Er), let Tr be a maximum requirement spanning tree ( M R S T ) in it (for i l lustrat ion, see Figure 2.1 in Section 2.1). Proposit ion. p coincides with the nucleolus of the game (N;c2) induced by a requirement structure Gr = (N,Er), if all the requirements of any MRST in Gr are equal. 40 Proof. Let Tr be a M R S T in Gr, and let the value of the common requirement in Tr be r. Clearly, max{ rik : k £ N } — max{ : k G JV }, t ,y G /V", and pj = | max{ : k £ N} = r/2, j 6 N. Furthermore, from (2.3), C2{S) = ]. (E m a x ( r;-fc : fc € JV } + m a x { r i * * € S }) jes j€N\s = —- + - E m a x ( rifc : fc G S } 6 • r r Therefore, for every nonempty subset 5 C JV, e x ( 5 , M , c 2 ) = c 2 ( S ) - fi(S) > ^ + ^ - ^ = ^. Now, e x ( J V \ { j } , / , , c 2 ) = c 2 ( J V \ { i } ) - / x ( J V \ { y } ) = c 2(JV) -^x(JV) by (2.3), = m = r/2. Therefore, ex(N\{j}, p, c 2 ) < e x (5 , yii, c 2 ) , S 1 C JV, 5 ^ 0. Thus, for every pair of nodes p ,g G JV, we have 5 p ? ( J V , / x , c 2 ) = ex ( JV\{g} , / i , c 2 ) = r/2 = ex(JV\{p}, /x ,c 2 ) The result follows by the concavity of the game (JV; c 2 ) . 41 2.5 Nearly Decomposable Network Synthesis Games We introduce, in this section, the class of nearly decomposable network synthesis games, and show, in 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. Fi rs t , recall that for any two adjacent nodes i and j in a requirement structure G> = (N,Er), we denoted by M j (resp., Mj) the set of nodes in TV, (resp., Nj) adjacent to i (resp., j). If is a bridge in Gr, the induced game (TV;^) is said to be nearly decomposable, w i th a bridge If in addit ion, then Gr is said to possess the bridge property, and, without causing confusion, the in-duced game (JV;c 2 ) is said to be nearly decomposable, wi th a bridge For example, in Figure 2.7, the requirement structure has the bridge property wi th (4,5) as a bridge, but not w i th (2,4) as a bridge. We observe that a spanning tree requirement structure t r iv ia l ly possesses the bridge property, i.e., there always exists a bridge w i th an asso-ciated requirement satisfying the above inequality. We observe further that if GT has the bridge property, it can induce both nearly decomposable games {N;ci) and ( A r ; c 2 ) . However, if Gr does not satisfy the bridge property, while having only a bridge, it in-duces the nearly decomposable game (N;ci), but not the nearly decomposable game Suppose that the requirement structure Gr = (N,Er), inducing the game (N;ci) (resp., the (7V;c 2)), has a bridge (resp., the bridge property wi th a bridge) and define for subsets S C N, rij < min{ min{ rik : k £ M, }, min{ Tji : / £ Mj } }, (N;c2). otherwise. (2.7) 42 and Figure 2.7: A Spanning Tree Requirement Structure. c 2 (5 ) = c2{s) -mi 2 if either both i 6 S and 5 n { M , U {j}} = or both j £ 5 and 5 n {M,- U {»'}} = 0 otherwise. (2.8) Furthermore, construct two component games (A^;cj) and (TV^;^) (resp., (TV,;c 2) and (Nj-,c2)) whose characteristic functions are the restriction of Ci(S) (resp., c2(S)) to all subset S of TV,- and Nj, respectively. Now, let E\ (resp., E3r) be the collection of edges of Gr wi th both endpoints in TV, (resp., TV,), e.g., in the requirement struc-ture shown in Figure 2.7, for bridge (4,5), TV4 = {1,2,3,4} , £ r 4 = {(1,2), (2,3), (2,4)}, TV5 = {5 ,6,7,8} , and Ehr = {(5,6), (5,7), (5,8)}. One can easily verify that (TV,;^) and (Nj\c.i) (resp., (TV,;c 2) and (TV,;e 2)) are precisely the simultaneous (resp., the equal cost nonsimultaneous) network synthesis games induced by the requirement substructures {Ni,Er) and {N^E}). Since each of these component games is smaller than the original games, its compu-tational 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 structure Gr -- (N,ET) has a bridge (resp., the bridge property with a bridge) and induces the games (N;ci); ( T V ; c i ) , (Ni;c\), and (Nj\ci) (resp., (N;c2), ( T V ; c 2 ) , (TVJ;C2), and (TV , ; c 2 ) ) , then 43 (i) c!{Ni) + ~a{Nj) = Cl[N) - njd'xj {resp., ~c2{Nl) + c2{Nj) = c2{N)) (ii) ca(S) = ca{Nt n S) + ca{Nj D S), S C N, i.e. the game {N;ca), a = 1,2, is decomposable into two component games {Nh;ca), h = i,j. proof. (i) follows from (2.7), (2.2) (resp., (2.8),(2.3)), and the definition of a bridge (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 Decompos-able Games (TV; ci) and (N; c 2 ) In this section, we decompose the cores of the nearly decomposable games (N;ci) and (7V;c2), w i th a bridge Theorems 2.6 and 2.7 below demonstrate that one can use the cores of the component games to characterize the cores of the nearly decomposable games {N;c2) and ( T V ; ^ ) . Firs t , let the nodes in N be ordered such that Ni = { l , . . . , m } and Nj = {m + l , . . . , n } , and denote the cores of the two component games (AV, c a ) , o, = 1,2, by C\{Nh;ca)], h = i,j. Let Gr = {N,Er) be the associated requirement structure, and recall that for any pair of nodes p,q 6 N, rpq (resp., d'pq) is the requirement (resp., the cost of a cheapest path) between p and q. We first consider the core of the nearly decomposable game (Af;c 2), w i th a bridge {i,j). For a cost allocation vector y — {yu---,Vn), let (Xj{y) = min{£ 2(5) - y{S) : S C Nj\{j}, S n M ^ 0 } , and ai{y) = min{ c 2(5) - y{S) : S C JV,.\{*-}, S n M,- ^ 0 }. Since y(Ar^) = c2{Nh), h = i,j, it follows by (2.8) that OLj{y) = min{c 2 (5) - y{S) = ex{S,y,c2) : S D TV,-, 5 ^ j, S n Mj ^0} , and at{y) =mm{ex{S,y,c2) : S D Nj, S $ i, 5 n M t - ^ 0 } . 44 If Mi (resp., Mj) = 0, we let a.j(y) (resp., «»(j/)) = Uj/2. The core of the t r iv ia l (inessen-tial) game ( { p } ; ^ ) , p G N, consists of the unique point yp = ^ ( { p } ) . Let ' x ' denote the Cartesian product, and for all (y r , ...,ym) G C [ ( ^ ; c 2 ) ] , ( y m + i , • • • ,Vn) £ C[(NJ;C2)], and a(y), y = ( y i , . . . ,ym) x ( y m + i , . . . , y „ ) , in the range m a x { - r t j / 2 , - a t ( y ) } < a(y) < m i n { r t ; / 2 , ctj{y)}, let C a ( » ) [ ( M - ; c 2 ) ] = {{yi,---,Vi + a.{y),...,ym) : ( y i , . . . , y m ) G C[(/V,;c 2 )]} and ^ - " ( v j K ^ i ; ^ ) ] = { ( y m + i , - - - , y j - a ( y ) , . . . , y n ) : ( y m +i , • • • , y n ) £ C\{Nj\c2)}}. Theorem 2 .6. For the nearly decomposable game (7V;c 2) with a bridge C[{N-,*)\=\J Ca{v][(Nt-C2)\ x C_ a ( w ) [ (JV,- ;c 2 ) ] where the union is over a(y) in the range max{ — r^/2, —a,(y)} < a(y) < min{r,- J-/2,a J-(t/)}. Proof. F i r s t , suppose that ( j / i , . . . , ym) G C[(7V,; c 2)] and ( y m + i , . . . , y„) G C[(iV i ; c 2)]. For every a(y) in the above range, define x — (x/,) G 9? n as follows. Vh + a(y) if h = i xh = { y f c - a(y) if h = j (2.9) y^ otherwise. We wi l l show, by contradiction, that the vector x, given in (2.9) above, is contained in C\(N;c2)}. So, suppose x ^ C[(-/V;c 2 )] , i.e., there exists at least one subset S C TV such that x (5 ) > c 2 ( 5 ) . There are three cases. 1. S f l — 0- B y Theorem 2.2 above, we can assume that either S C Ni\{i} or S C T V ^ I J ' } . In both cases, x (5) = y(5) and c2(S) = c2(S). Therefore, the inequality x(S) > c2(S) implies y{S) > c 2 ( 5 ) , a contradiction. 45 2. S contains either i or j , say i , but not both. B y Theorem 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 2(JV.) implies y(JV,) > c 2(JV.) + r , ; / 2 - a(y) > c 2(JV,), contradicting the supposition that ( y x , . . . , y m ) G C[(iV,; c 2)]. Otherwise, i.e., when 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 2(5), we have otj(y) < c2(S) — y{S) < ct(y), a contradiction. 3. S n {i,j} = B y Theorem 2.2 above, either S D N3 or S D N. Assume that S D Nj. Then, the inequality x(S) > c2(S) implies y(SflJV,-) + a(y) + y{Nj) — a(y) = x(S) > c2(S) = c2(S n JV,-) + c2(Nj), a contradiction to the suppositions that ( y i , . . . , y m ) £ C[(JV,;c 2)] and {ym+1,..., y n ) G C[(JV,-; c 2)]. Conversely, suppose x G C[(A^;c 2)]. We wi l l show that there exists a constant a in the above range such that ( y 1 ? . . . , ym) and ( y m + i , . . . , y„) , derived from x and a through (2.9), are contained in C[(iV,; c 2)] and C[(A^;c 2 ) ] , respectively. B y Theorem 2.2 above, foTh = i,j, ex(Nh,x,c2) < ex(S,x,c2), S C Nh, S 3 h. (2.10) Furthermore, by (2.3), c 2(JV,) + c2(JVy) — r,j = c 2 ( i V ) , and by the fact that x is a cost allocation, x(Ni) + x(Nj) = c2(N). Hence, x(Ni) = c2(Ni) - nj/2 + e and x(Nj) = c2(JV,-) - - e. (2.11) Fi rs t , we wi l l show that e is in the range max{ —r t J-/2, — a,(x)} < e < min{r ,v ? /2 , a ; (x )} . Assume, without loss of generality, that e > 0. Since x G C[(JV;c 2 )], it follows that e < Tij/2. To show that e < ct , (x), suppose that T C iV>, T $ j , T D M, ^ 0, and ex(T, x , c 2 ) = cij(x). Then , ex{Nt U T, x, c 2) = c2(JV,- U T) - x(JV, U T) = c2{Ni)-rij/2 + c2(T)-x(N,)-x{T), by (2.3) = - e + ex(r ,x,c 2), by (2.11) > 0, since x G C[(JV;c 2)] 46 imply ing that otj{x) ex(T, x,c2) > e. Furthermore, for any subset S C TV,-, S 3 i, x{S) = c 2 (S) - ex(S,x,c2) < c2{S) - ex{Ni,x,c2), = c2{S)-rtj/2 + e, by (2.10) by (2.11). (2.12) Similarly, for any subset S C Nj, S 3 j , x{S) < c2{S) -m/2 — €. (2.13) Now, we wi l l show that ( y i , . . . , y m ) and ( y m + i , . . . , y n ) , derived from x and a = a(y) = e through (2.9), are contained in C[(JV,;c 2)] and C[(NJ; C2)}, respectively. First note that by (2.9) and the choice of o:^(-), we have oth{y) — ah{x), h = and therefore a is in the required range. Now, if S C Ni, S $ i, and y(S) > c2(S), then x(S) = y(S) > c2(S) — c2(S), contradicting the supposition that x 6 C[( iV;c 2 ) ] . Similarly, we can show that y(S) < c2(S), S C Nj, S $ j . Furthermore, if S C Ni, S 3 i, and y{S) > Z2{S), then x(S) = y{S) + e > c2{S) + e = c2{S) - r^/2 + e, contradicting (2.12). Similarly, if y(S) > c 2 ( 5 ) , S C Nj, and S 3 j , then (2.13) wi l l be 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;c2)} 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 ( J V ; C I ) , and for a constant a, let C a[(JV.-;ci)] = {(y1,...,yi + rijd'ij/2 + a,...,ym) : {yu...,ym) € C[(JV,-; cj)]} and C-aKNj-,^)] = {{ym+1,... ,yj + Tijd'^/2 - a,... ,yn) : ( y m + i , . . . , y„) G C[(/V i ; ex)} }. 47 We note that the core of the t r iv ia l (inessential) game ({p};c?i), p G N, consists of the unique point yp = 0. Now, unlike in the Theorem 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 J Jo!- J-/2, r,-;-d|--/2], ( j / i > - - - , ! / m ) € C[(A r , ;ci)] and (ym+i, • • • , yn) € C[(7V,-; Cj)], that y = ( y x , . . . , y m ) x ( y m + i , . . . , y n ) is contained in C\(N; Ci)}, which significantly simplifies the computations. This result is stated formally in Theorem 2.7 below, whose proof is omitted here, since it is similar to the proof of Theorem 2.6 above. Theorem 2.7. For the nearly decomposable game (N;ci) with a bridge (i,j), 2.7 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 2) we 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 wi l l extend the above result by providing a decomposition procedure for the nucleolus of the nearly decomposable game (7V;c 2 ) , wi th a bridge {i,j)- Namely, Theorem 2.8 below proves that the nucleolus of (N;c2) is the Cartesian product of the nucleoli of the component games (iV,;c"2) and (Nj\c2). Firs t , recall that for a cost allocation vector i G F and for a pair of nodes p,q 6 N, spq(N,x,c2) = min{ex(>S,x,c 2 ) : S C N, S 3 p, S q}. To simplify the exposition, we extend this definition to the component games (TV/,; c 2 ) , h = i,j, as follows: for S C Nh, h = and for x 6 9J n , we let the excess of 5 at x w i th respect to c 2 be denoted by ex(5, x, c 2) = c2(S) — x(S), and for any pair of nodes p, q G Nh, we let C[(JV; C l ) ] = | J C a[(JV,-;ci)] X C_ a[(iV,;c~ 1)] where the union is over all a in the range —rijd'i;j/2 < a < r,-ydJ--/2. 'h,x,c2) = m i n { e x ( 5 , x , c 2 ) : S C TV^, S 9 p, S $ q}. 48 L e m m a 2 .7. For a vector y in the core of the nearly decomposable game ( JV;c 2 ) , with a bridge satisfying y(Nh) — c2[Nh), h = i,j, and for every pair of nodes p,q e Nh, we have spq{N,y,c2) - spq{Nh,y,c2): Proof. Given the pair of nodes p,q G JV,-, choose a subset U C N, U 3 p, U $ q, such that ex(U,y,c2) = spq(N ,y,c2), and a subset T C JV,, T 3 p, T $ q, such that e x ( T , y , c 2 ) = spq(Ni,y,c2). We wi l l show that ex(U,y,c2) = e x ( T , y , c 2 ) . Firs t , by Theorem 2.2 above, if U 3 i, then U Z> Nj. Otherwise, either U C JV,\ {/,'}, or both U n {Nj U {i}} = Nj and U n M , ± 0. If both U n {TV, U {?'}} = JV,- and U n M , / 0, then e x ( l / n J V „ y , c 2 ) = c 2(£7 n JV,-) - y(U n JV,) = ^(t/nJVO + y ^ O - y ^ ) = c 2 ( ^ n J V , - ) + c 2 ( J V i ) - y ( £ 7 ) = c 2(LT) - y ( * 7 ) , by (2.3) and (2.8) = ex ( t / , y , c 2 ) . (2.14) Now, consider the following four cases. 1. U ^ i and T ^ i . B y the definition of spq(N,y,c2) we have ex(U,y,c2) < ex(T, y , c 2 ) , and by (2.8) we have ex(T, y , c 2 ) = ex(T, y , c 2 ) . Moreover, by the definition of spq(Ni,y,c2) we have e x ( T , y , c 2 ) < ex(£7 D J V i 5 y , c 2 ) , and by (2.8) V e have ex(/7 n JV,-, y, c 2) = ex(t/ n JV,-,y,e 2). Furthermore, by (2.14) we have ex(£/ n JV, ,y , c 2 ) = e x ( £ / , y , c 2 ) . 2. U 9 i and T ^ i. Then, as in item 1 above we get ex([7, y , c 2 ) < ex(T, y , c 2 ) < ex(U n JV,, y , c 2 ) . Furthermore, since U D JV, and ex(Nj,y,c2) = 0, it follows by (2.8) that ex(C7 D JV, ,y , c 2 ) = ex(C7 fl N,y,c2) + ex(Nj,y,c2) = ex(U,y,c2). 3. U ^ i and T 3 i . Then, by the definition of spq(N,y,c2) we have ex(U,y,c2) < ex{TuNj,y,c2). Furthermore, by (2.8) we have that both ex(TL)Nj,y, c2) = ex(jTU Nj,y,c2) and ex(r U Nj,y,c2) = ex(T,y,c2) + ex{Nj,y,c2). Since ex(7V i ,y ,c 2 ) -0, it follows that ex(T U Nj,y,c2) = ex(T, y , c 2 ) . Now, by the definition of spq(Ni, y, c 2) we have that ex(T, y, c 2) < ex(UnNi, y , c 2 ) , and by (2.8) we have that 49 ex(U n Ni,y,c2) = ex(£7 D Ni,y,c2). Final ly , by (2.14) we get ex(U D N,y,c2) = ex{U,y,c2). 4. U 3 i and T 3 i. Then, as in item 2 above we get ex(T,y,c2) < e x ( C , y , c 2 ) , but as in item 3 we get ex(U,y,c2) < ex(T,y,c2). The above four cases, which are of course exhaustive, reveal that for every pair of nodes p,q £ JV,, we have that spq(N,y,c2) = ex{U,y,c2) = ex(T,y,c2) = spq(Nl,y,c2). The analysis for any pair of nodes p, q £ Nj is identical. • Now, we are ready to present the decomposition result for the nucleolus. Theorem 2.8. The nucleolus of the nearly decomposable game ( J V ; c 2 ) , with a bridge is the Cartesian product of the nucleoli of its two component games (JV , ; c 2 ) and {NJ; c 2 ) . Proof. Let ul and u3 be the nucleoli of (JVJ;C 2) and (Nj\c2), respectively, and let v be their Cartesian product. We wi l l show that u is the nucleolus of ( J V ; c 2 ) . F i rs t , by Theorem 2.6 above we have that v £ C[ (JV ; c 2 ) ] . Furthermore, since i / ' is the nucleolus of (JV , ; e 2 ) , it follows for every pair of nodes p,q £ Ni that spq{Ni, vl, c2) = sqp{Ni,u%,c2). Thus, spq(Ni, u,c2) = sqp[Ni,u,c2), and by L e m m a 2.7 above, we have that spq(N, v, c 2) = sqp(N, u, c2). The analysis for any pair of nodes p,q £ Nj is identical. Now, suppose p £ JV,- and q £ Nj. Let T and U be two subsets of JV which minimize { ex(S,v,c2) : S C JV, S 3 p, S $ q} and { ex (5 ,u ,c 2 ) : S C JV, S 3 q, S $ p}, respec-tively. We wi l l show, by contradiction, that spq(N,v,c2) = ex(T,u,c2) = ex(U,u,c2) = sqp(N, v, c 2 ) . Suppose not, i.e., suppose, without loss of generality, that ex(T, u, c2) < ex(U,v,c2). Since ex(JVF E, v, c 2 ) = 7*^/2, / i = t , j , it follows that ex(T, i^, c 2) < ex(C7, v,c2) < r , j / 2 , and that T ^ JV,-. If ex(t/, v, c2) — r^/2, then let U = Nj. 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 l , c 2 ) : S1 C JV,, S 3 i, S $ p}. Then, by the definition of sqp(N,y,c2) we get that ex(U,v,c2) < ex{W U Nj,v,c2), and by (2.8) we have that ex(W U Nj,v,c2) — ex(W, vl,c2). Moreover, B y the choice of W we get that ex(W,vl,c2) = sip(Ni,u1,c2), and since is the nucleolus of (JV , ;c 2 ) it follows 50 that Sip(Ni,u\c2) = spi(Ni,ul,c2). Furthermore, since T C A7,-, T $ i, and T 3 p, it follows by (2.8) that T minimizes { ex(S, */ , c 2) : S C N, S 3 p, S $ i}, and therefore Spi(Ni,i/',c2) = e x ( T , ^ , c 2 ) . To summarize, ex(U,v,c2) < ex(W U Nj,v,c2) = ex(W / ,z/ ' ,c 2 ) = sip(Ni,i't,c2) = s p i ( N i , i / % ,c2) = ex(T,u,c2), which is a contradiction. 2. T 3 B y Theorem 2.2 above, T D N i , and by (2.8) we have that ex(T,u,c2) = ex(T n N j , v\ c 2 ) . Furthermore, since T D Nj 3 j , T n Nj C AT,, and T n Nj $ q, it follows by (2.8) that r n / V , minimizes { ex(5, i / J ' , c 2 ) : S C N j , S3 j, S $ q}., otherwise, T cannot minimize {ex(S,v,c2) : S C N , S 3 p, S $ q}. Thus, ex(T n Nj,v3,c2) = Sjq(Nj,vi,c2). Furthermore, since v3 is the nucleolus of (Nj-,c2), it follows that Sjq(Nj,u3, c 2 ) = sqj{Nj,u3,c2). In addit ion, by (2.8) we have that sqj(Nj,u3,c2) > ex(U,i/,c2), since U could have been chosen such that it also minimized {ex(S, v3,c2) : S C N j , S 3 q, S $ j}. To summarize, ex(T,u,c2) = ex(T C\ Nj,v%,c2) = sjq(Nj,u3,c2) = sqj(Nj,u3,c2) > ex(U,v,c2), which is a contradiction. 3. T 3 i , T $ j , (T ^ N j ) . Then, by Theorem 2.2 above, T D N t and T n M,- ^ 0. Let / € T D M j , and suppose a subset W C minimizes {ex (S , v3, c 2) : 5 C A^-, S 3 j, S $ I}, i.e., ex(W, i / - 7 , c 2) = Sji(Nj,u3 , c 2 ) . Since is the nucleolus of (NJ;C2), it follows that Sji(Nj,u3,c2) = sij(Nj,u3,c2). Furthermore, since T C) Nj 3 I, T C\ Nj C A7,-, and T n J V j ^ j , it follows by (2.8) that T n JV,-minimizes { ex(5, c 2) : S C A j , S 3 I, S $ j}, otherwise, T cannot minimize ( e x ( 5 , i / , c 2 ) : S C N , S 3 p, S $ g} . Thus, s^N^u3,c2) = ex(T n Nj,v3,c2). Moreover, by (2.8) we get that ex(T n N j , v3, c2) = ex(T, v, c2), but ex(T, v, c2) is supposed to be strictly less than r , j /2 . Therefore, c2(W) — u3(W) = ex(W,v3 ,c2) = Sji(Nj,i/3,c2) = Sij(Nj,uJ,c2) = ex(T C\ Nj,v3,c2) = ex(T,v,c2) < r , j /2 , and c 2 ( T D N j ) - v j [ T n N j ) = ex(TnNj,u\c2) = ex{T,u,c2) < r 0 - / 2 . A d d i n g the two derived inequalities c2(W)-v3(W) < r t > / 2 and c2{T^Nj)-u3(TnNj) < r 0 - / 2 , and rearranging some terms, we get i/3'(W)-rV3' ( T o N j ) > c 2 (W / )+c 2 (TnA r j )— r,-j. Since there is a common requirement Tji associated wi th both W and TC\ N j , and since, by the bridge property, Tj\ > r^-, it follows by (2.3) that c 2(Vy) + c 2 (T n Nj) — r,j > t 2 { W u { T C \ N j } ) + c 2 { W n { T n N j } ) . Thus, v>(W\j{TnNj})+v>{Wn{TnNj}) = vj(W)+v>{TnNj) > ~c2(W) + ~c2(TnNj)-rij > i2{Wu{TnNj}) + c 2 { W n { T n N j } ) , 51 contradicting the supposition that vj £ C\(Nj-,c2)}. Therefore, spq(N,v,c2) = sqp(N,i/,c2), p,q £ N, and the concavity of (JV;c 2 ) implies that v is its nucleolus. • We note that the nucleolus of the t r iv ia l (inessential) component game ({p};c2), p £ JV, is i/p = c2({p}). Furthermore, if any of the component games is associated w i t h a requirement structure which satisfies the bridge property, then we can apply the decomposition, in turn, to this game. Clearly, if the requirement structure is a spanning tree, we can repeatedly apply the decomposition to obtain n t r ivial 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 = (vp) which coincides wi th p = (pp), vp = pp = | max{ rpq : q £ JV} . This suggests an alternative constructive method, as opposed to the analytic method presented in Theorem 2.5 above, for proving that p is the nucleolus of (N;c2), if the associated requirement structure is a spanning tree. 2.8 Shapley Values of ( T V ; C i ) and Nearly Decompos-able ( T V ; c 2 ) The derivation of Shapley value, in general, requires an enormous amount of computa-t ion. However, it is possible to significantly reduce the computations required to find the Shapley values of (JV;ci) and the nearly decomposable (N;c2). For (JV;ci) , we wi l l show that the Shapley value coincides w i th the nucleolus. For the nearly decomposable ( JV;c 2 ) , in Theorem 2.9 below, we wi l l show that the Shapley value can efficiently be computed from the Shapley values of its component games. Fi rs t , to prove that the Shapley value of (JV;ci) coincides with its nucleolus, recall that, by Gomory and H u [60], an opt imal solution to the simultaneous network synthesis problem can be found as follows. Starting from a zero capacity network, increase the capacity of the edges on a cheapest path between each pair of nodes p and q by rpq, and at the cost of rpq • d'pq. Now, if there is only one requirement, the Shapley value, by the symmetry axiom, 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 addit ivi ty axiom of the Shapley value, the cost allocation vector assigned by this procedure coincides wi th the Shapley value. Furthermore, it is evident that the assigned cost allocation vector wi l l be equal to £ = ( £ p ) , £ p = \ Hq£N rpqd'pq- Now, since, in 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 (JV;c 2 ) . F i r s t , recall that we denoted by 7r a permutation of the elements of N, and 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 in 7r. The following (counting) lemma wi l l be used in Theorem 2.9. below. Lemma 2.8. Given any two nodes g,h € N and given a subset M C N\{g,h}, \M\ = m, let A\ (resp., A2) denote the set of all permutations n (of the elements of N) that satisfy both Sh(ir) 3 g and Sh(n) n M = 0 (resp., Sh(-jr) n ( M U {g}) = 0). Then \Ai\ 1 1 1 1 (2.15) n! (m + l ) ( m + 2) and L - f i = — (2.16) n! m + 2 v ; Proof. For each positioning of the members of N\{M U {g,h}}, there are ml and (m + 1)!, out of a possible (m + 2)!, permutations that belong to A\ and A2, 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), and | A 2 | / n ! = n(n - 1) . . . (m + 3) • (m + l ) ! / r i ! = l / ( m + 2). • Before stating Theorem 2.9, recall that the Shapley value <p(c) — (<f>h[c)) of a game (7V;c) is given by <f>h(c) = ^ E x e n ( c i s h { ^ ) "U {^}) - cl'S'fel71'))), where IT is the set of all permutations 7r. Furthermore, let ra, (resp., ra,) denote the cardinality of Mj (resp. Mj), where M, (resp. Mj) is the set of nodes adjacent to i (resp., j), excluding j (resp., i), in a requirement structure Gr. We note that the Shapley value of the t r iv ia l (inessential) game ({p};c 2 ) , p 6 N, is the point <j>v(c2) = c 2 ({p}). 5 3 B y L e m m a 2 . 6 above, the (concave) game (N; c2) is decomposable into two (concave) games (./V,;c 2) and (Nj-,c2). Therefore, by Shapley [ 1 3 2 ] , Shapley value of (N;c2) is the Cartesian product of the Shapley values of (7VJ;C2) and (Nj\c2). Hence, (j>h{c2) in Theorem 2 . 9 below can be taken as the Shapley value of the node h in the appropriate component game (Ni;c2) or {Nj\c2). Theorem 2 .9. The Shapley value 4>(c2) — ((ph{c2)) of the nearly decomposable game (N;c2), with a bridge can be calculated from the Shapley value 4>{b) = ((j>h(c2)) of the game (N; c 2) as follows: ' M*) ~ ( ( m t + l ) ( m , + 2 ) ) • f heMg,ge{l,j} ( 2 . 1 7 ) Mb) + ( ^ 2 - ( m , + 1 ) ( m . + 2)) k = i ( 2 - 1 8 ) MC2} Mb) + - (TOj+1)1(mj+2)) -rf h — j (2.19) 4>h{b) otherwise. (2.20) Proof. F i rs t , we wil l show (2.20). F rom (2.8) we have that c2(S) / c2(S) only if either both 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 t U Mj U {i,j}}, we get c2(Sh{ir) U {h}) - c2{Sh{-n)) = c2{Sh(n) U {h}) - ~c2{Sh{n)). Thus, (2.20) follows from the definition of the Shapley value. To show (2.17), let h £ M ; and, for simplicity, let Sh represent Sh(ir). Then, it follows from (2.3) and (2.8) that ^ M / . - n <v\ ) b(Shu{h})-rtJ/2-~c2(Sk) 3eSh,Shn{Mtu{i}} = H> c2(SkU{h})-c2(Sh) = \ c2(Sh U {h}) — c2(Sh) otherwise. Now, from (2.15), the number of permutations of members of N satisfying j £ Sh and Sh n {Mi U {«'}} = 0 is n! / ( (m, + l)(m,- + 2)), which implies (2.17). The case for h £ Mj can be proven using identical arguments. To show (2.18), for simplicity, we let 5, represent 5,(7r). Then , from (2.3) and (2.8), 54 Figure 2.8: The Requirement Structure (left) used in Example 2.4, and the Networks Result ing from the Near-Decomposition (center and right). c 2 ( 5 , - U { i » - c 2 ( 5 , - ) c 2 (5 , -U { t } ) +rij/2-c2{Si) c2{Si\j{i})-c2{Si) -r{j/2 c 2 ( 5,-U { « } ) - c 2 ( S , - ) S{ n {Mj U {j}} = 0 (2.21) j € S i 5 S,-nAf,- = 0 (2.22) otherwise. Now, 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 t- +2)) , respectively, from which (2.18) follows. One can prove (2.19) using identical arguments. • Aga in , when the requirement structure is a spanning tree, we can use the decomposi-t ion to obtain n t r iv ia l games, each containing only one player. Then, the Shapley value of the induced game (JV;c 2 ) can be found, using Theorem 2.9 above, by backsubstitu-tion, which wi l l be illustrated in Example 2.4 below. As a consequence of Theorem 2.9, the computation of the Shapley value of (N; c 2 ) , whose associated requirement structure is a spanning tree, can be done in O(n) , i.e., linear t ime. Example 2.4 below illustrates this fact, in addition to elucidating the (near) decomposition procedure. Example 2.4. Consider the requirement structure Gr — (N,Er) shown in F ig -ure 2.8, where TV = { l , . . . , 4 } , Er = {(1,2), (1, 3), (1,4)}, r 1 2 = 1, r 1 3 = 2, r 1 4 = 3, and dpq = 1, (p,o) € Er. The nucleolus of the induced game (N; c 2 ) , by Section 2.4, is H = (1.5,-5,1,1.5). To find the Shapley value of (N;c2), we observe that Gr has the bridge property, wi th a bridge (1,2). Now, 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 in addition 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 ) - \ (2-23) MO = ^ " 0 + Q - ( 3 p ) - 5 = ^ ) + ^ (2-24) and for / i = 3,4, MO = - ( — ^ ) • ^ = * h ( c a ) - ~ (2.25) Now, we have to find 4>{c2) for the component games ({2}; c 2) and ({1,3,4}; c 2 ) . The first game is t r iv ia l , thus, its Shapley value is simply 4>2{0 = c 2 ({2}) , which by (2.8) is equal to 1 — | = | . Substituting this back in (2.23), we get <t>2(0 = | — | = | . To find the Shapley value of the component game ( { l , 3 , 4 } ; c 2 ) , we decompose it further using edge (1,3) as the bridge. The requirement substructure associated wi th this game is ( { l , 3,4}, {(1,3), (1,4)}), which is displayed in the center of Figure 2.8. Now, in (2.8), replace c 2 by c 2, and c 2 by c 2 , to derive two component games ( { l , 4};c 2) and ({3};c 2 ) from the game ( { l , 3 , 4 } ;c 2). Furthermore, for the pair g,h £ {1,3}, let mg be the number of nodes (except h) adjacent to g, in the requirement substructure ({1 ,3 ,4} , {(1,3), (1,4)}). Then , m i = 1 and m 3 = 0. In (2.17) to (2.20), replace MO by <Mc 2), M O by M O , and mg by mg to get Mb) = Mb) + Q - I) • \ = Mb) - \ (2-26) Mb) = MO + ( ^ - ^ ) - \ = Mb) + \ (2.27) Mb) = M O - ( ~ ) - \ = M O ~ \ (2-28) A g a i n , the component game ({3}; c 2) is t r iv ia l , and therefore <^>3(c2) = c 2 ({3}) = 2 — 1 = 1. Subst i tut ing 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. The Shapley value of the component game ( { l , 4};c 2), associated wi th the requirement substructure ({1,4}, {(1,4)}) which 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(c2) = 414(02) = f c 2 ( { l , 4 } ) = | . Substituting the value of <j>4(c2) back in (2.28) we get </>3(c2) = I — I = | , and substituting this back in (2.25) we get <^4(c2) = | — ^ = f j . Similar ly , substi tuting the value of </>i(c2) in (2.27) we get </>i(c2) = f + § = ^1 AN<^ substi tut ing this in (2.24) gives <£ i ( c 2 ) = ^ + ~ = Therefore, the Shapley value of {N;c2) is (j>(c2) = ^ (49 ,9 ,19 ,31) . • 2.9 Summary and Further Research for the Cost Allocation Problem In Chapter 2, we considered the cost allocation problems which naturally arise in the simultaneous and the equal cost nonsimultaneous network synthesis problem, if we as-sume that the various nodes in the network represent different users or communities. We employed the cooperative game theory to analyze these cost allocation problems, and proved 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 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 nucle-olus when the requirement structure is a spanning tree. Then, 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. The (near) decomposition was also used to simplify the analysis of the core and the nucleolus of the game in the special case. For the simultaneous network synthesis problem, we also used the irredundant rep-resentation 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. Our results may be used as guidelines for construction cost allocation in some com-municat ion networks. Further, we have presented two more special cases when the Shapley value and the nucleolus can be computed efficiently. 57 We did not consider the cost allocation problem in the nonequal-cost nonsimultane-ous 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, and using the formulation presented in Section 4.5, we can polynomially find a point in the core. Of course, one can use the results we wi 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 3 -free graphs. Chapter 3 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 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 3.1 The Steiner Network Synthesis Problem The nonsimultaneous network synthesis problem, see Gomory and H u [58,59,60], is to design, at min imum cost, an undirected communication network wi th n nodes which satisfies given requirements, i.e., lower bounds on maximum flow, between every pair of nodes, one requirement at a time. The data for any instance of this problem 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}, i < j, dij is the cost of building one unit capacity on edge and r,y is the requirement between i and j. Throughout 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 between nodes i and j , j > i. The 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. The cost of providing capacity 6,-y on edge is cJ,y6,y, and the objective is to provide sufficient capacity to meet al l n ' requirements at minimum total cost d-b = zZi<i<j<n difiij- 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 in TV \ T cannot simply be ignored, since it is conceivable that al l optimal solutions to this network synthesis problem use some nodes in N\T as intermediate points. We call the nonsimultaneous network synthesis problem, wi th 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 problem, since for T = TV, the two are equivalent. For the remaining of this thesis, we wi l l be chiefly concerned wi th the Steiner network synthesis problem, since the extra generality in the Steiner network synthesis problem, compared wi th the ordinary nonsimultaneous network synthesis problem, usually does not increase the complexity of the problem. F rom the M a x - F l o w M i n - C u t Theorem, see e.g., Ford 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 3 j, b(Q,N\Q) = £ bkl > r,-,-. k€Q, leN\Q Thus, the set of al 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 and {«'. j ' } , {«'.J> ^ { t ' , / } , such that {i,i'} C Q and C N\Q. Therefore, one of the constraints b(Q,N\Q) > r,j and b(Q,N\Q) > r^ji 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 }. Then, the Steiner network synthesis problem can be writ ten as the following linear program: Minimize £ d i 3 • 6,3 l<i<j<n Subject To £ btj > rQ (Q,N\Q), 0 ^ Q PtT C T l<i'<J<n bij > 0 1 < i < j < n 60 where a cutset (Q,N\Q) is the set of edges wi th one endpoint in Q and the other in N\Q. In chapter 3, we wi l l 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. When the number of demand nodes t = \T\ is small relative to n, it may be worthwhile to eliminate the increased com-plexity resulting from the intermediate nodes. This is achieved using a transformation. Before outl ining the transformation, since in Chapter 3 we are concerned wi th the equal-requirement case, we find it convenient to represent the input to the Steiner network synthesis problem by a network G — (N,E), where E 5 if the unit cost < oo, and the weight (length) of any edge is equal to a\j. Furthermore, in G, we wi l l represent the demand nodes by thicklined circles. Thus, we may interpret the Steiner network synthesis problem as the problem of finding a min imum cost subnetwork in G, satisfying the requirements between the thicklined demand nodes nonsimultaneously. Th i s interpretation wi l l be called the Steiner network synthesis problem in network G. Now, the transformation can be summarized as follows. We transform the Steiner net-work synthesis problem in G into a smaller network synthesis problem wi th nodeset T and costs (distances) equal to the shortest (cheapest) distances in G. Then , we solve the smaller network synthesis problem, possibly using a linear programming algorithm. F ina l ly , we transform an optimal solution in the smaller network synthesis problem back to the original problem. We wi l l prove, using linear programming duality, that the transformed solution is indeed an opt imal solution to the original equal-requirement Steiner network synthesis problem. The transformation requires 0[t • n2) operations, but we wi l l show, in Subsection 3.3.3., how an 0 ( n 2 ) algorithm can be obtained for the equal-requirement Steiner network synthesis problem when t < 5. 3.2 Simplifying the Equal-Requirement Case: Pre-liminaries Consider the Steiner network synthesis problem when the positive requirements are equal. Since the capacities are permitted to be noninteger, we can mult iply the posi-tive requirements and the derived capacities by the same constant, thus making all the 61 positive requirements equal to 2 units. In this section, we wi l l first present two linear programming formulations used in the transformation, and then describe the construc-tion of a solution to the Steiner network synthesis problem. Final ly, we present two dual problems, and state a property of the dual solutions. 3.2.1 Linear Programming Formulations and the Transforma-tion The Steiner network synthesis problem, wi th requirements equal to 2, can be formulated as the following linear program: M i n i m i z e £ d t J • 6,j i < * < j < « (P) S u b j e c t T o £ bi,- > 2 [Q,N\Q), 0 ^ Q D T C T {iJ)S(Q.N\Q) i < • ' < ; < » « kj > 0 1 < i < j < n. 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 to dtj. We wi l l refer to this formulation as the Steiner network synthesis problem in network G. Further, we let d'i:j be the length of a shortest (cheapest) path between demand nodes i and j in G. For 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) in G, i.e., d[j — d'ji for the edge joining i and j. (We wi l l use primes to denote quantities associated wi th G'.) The transformation wi l l be done as follows: 1. Transform the equal-requirement Steiner network synthesis problem in G into a smaller network synthesis problem in the shrunken network G ' . 2. Solve the network synthesis problem in G ' , possibly using linear programming. 3. Transform an optimal solution subnetwork W in G ' back to the original problem, thus constructing a solution subnetwork W in 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 in G have been determined, possibly using Dijkstra 's algorithm [40]. For Step 2, we first formulate the network synthesis problem, w i th requirements equal to 2, in G' as the following linear program: M i n i m i z e £ d' • b'^ {•'..OCT S u b j e c t T o £ 6J. > 2 (Q', Q') , Q' C T, Q' = T\Q a.j)e(Q'.Q') {i,j}CT. i<3 b'a > 0 {iJ}QT, K j where cutset (Q\ Q') is the set of edges wi th one endpoint in Q' C T and the other in Q' = T\Q', and b\- is the capacity of edge (i,j) in (P'). Now, we assume that (P') has been solved, and denote an optimal 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) G W (with capacity 6J- > 0), we find a shortest path between i and j in G, and let the capacity of every edge on this path 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 wi 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') The dual linear program to (P) can be written as follows: Maximize 2 £ SQ (Q,N\Q) ( D ) Subject To £ sQ < dij 1 < » < i < « {Q,ff\Q)B[ij) sQ > 0 (Q,N\Q), where SQ is the dual variable corresponding to the cutset (Q,N\Q) in (P). Similarly, the dual linear program to (P') can be formulated as follows: Maximize 2 £ S'Q, ( D ' ) Subject To £ s'QI < d'i3 M , { t , j } c r , « < i (Q'.<5')3(.'-j) S'Q, > o (Q',0'), where S'Q, is the dual variable corresponding to the cutset (Q',Q') in (P'), Q = T\Q. We assume that (D') has also been solved, and denote the positive values of an opt imal solution to (D') by { S'Q, : i — 1 , . . . , k' }. Before stating Lemma 3.1 concerning the structure of { Q[ : i = 1 , . . . , k' }, we wi l l 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, if the family of the subsets {Qi : i = 1,... ,k} \s nested. L e m m a 3.1 (Adapted From Cornuejols, Fonlupt, and Naddef [36, Theorem 4.9]). Let b' be an extreme solution to (P'). Then, the dual solution { S'Q, : i = 1,. . . , k' } cor-responding to b' can be chosen such that the associated cutsets { (Q[, Q[) : i = 1,..., k'} form a laminar family. • 64 Figure 3.1: Graph G , and point set Si. If we let b' be a solution to (P') which corresponds to the optimal solution subnet-work W, 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 (Q1, Q') in { (QJ, Ot) '• i = 1,. • • ,k! }, we wi l l associate some cutsets {(Qi,Qi) ' i = l , . . . , f c } in (P). These cutsets wi l l be generated by a modification of the Dijkst ra algori thm, which we wil l describe in the next section. Fi rs 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) there are points on (u,v) at distance d from u and distance duv — d from v, 0 < d < duv. The shortest distance between a node i £ N and a set of points S of G is denoted by d(i, S) = min{ 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. Let Si = {j : j a point of G such that d(l,j) < l } . The point set Sx is represented by thick line segments and a thicklined circle in Figure 3.1, where d(l,Si) = d(2 ,S x) = 0, d(3,Si) = 1, d(4,Si) = 2, etc. • 3.3 Optimality of the Subnetwork W In this section, we wi l l describe a modified version of Di jkst ra algorithm, and use it to construct a solution to (D) from an optimal solution to (D'). Final ly , we wi l l prove that the derived dual solution is, in fact, optimal to (D). 3.3.1 A Modified Dijkstra Algorithm and the Construction of a Solution to (D) Given a point set S, referred to as the root set, consisting of some points on network G , the modified Di jks t ra 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 } wi th 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) be the set of nodes v such that d(v,S) is minimized, and let SQ(S,) = d(v,S), Si = S 0 U {j : j a point of G , d(j,S) < SQJSJ) }, and Q{S2) = Q{Si)uVi. • In general, for / = 2 , . . . , m , let Vj C Ar\<5(S;_1) be the set of nodes v such that d(t;,S;_i) is minimized, and let SQ^S,) = d(u,Sj_i), Si = S;_i U {j : j a point of G , d(j , S;_i) < 5^ (5 , ) }, and Q(Si+x) = Q(Sj) U V;. The algori thm terminates when Q(Sm) = N. The cutsets { (Q(S,), Q(S,)) : i = 1 , . . . , m }, referred to as the Dijkstra cutsets around S, are by construction laminar. Example 3.2. Aga in consider the network displayed in Figure 3.1, and recall that S = {j '• j a point of G , d ( l , j ) < l } . From the modified Di jks t ra algorithm, we get 66 S0 = S and Q(Si) = {1,2}; sQtSl) = 1, Si = S 0 U {j : j a point of G , d(j,S0) < 1} , and Q(S2) = {1 ,2 ,3}; sQ>S2) = 1, S2 = Si U {j : j a point of G , d ( i , Sx) < l } , and Q(S 3) = {1 ,2 ,3 ,4} ; etc. • We wi 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 t, but at a distance zero from S,-. Some of the frontiers for Example 3.2 above are shown in 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 Di jks t ra 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 St. 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 in the intersection of F,-, the frontier of Si, w i th (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. This implies that the cutset (Q(S,-),Q(S,-)) wi 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 Di jks t ra algori thm that SQ(Si) < l{xi-\,Xi), t = l , . . . , m (3.1) where /(x,-_i,x,-) is the length of the interval [x,-_i,xt-] on (u,v). Now we can explain how to construct a solution { SQ{ : i = 1,... ,k} to (D) using the opt imal solution { S'Q, : i = 1 , . . . , k' } to (D') which corresponds to a laminar family of cutsets { (Q[, Q\) : i = 1,..., k' }. Firs t , note that { Q\ : i = l,...,k'}, being a nested family of nodesets, can be part ial ly 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 on the rooted tree is any node v such that the unique simple path between v and the root contains u. We wi l l proceed by scanning the rooted tree from bot tom up, i.e., at any stage, 6 7 only the nodes whose descendants have already been scanned are scanned (this is called 'post-order scan' in 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', and 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 with a node of the rooted tree we mean the largest (possibly reduced) enhanced root set generated, while we scan that node, by the modified Dijkst ra algorithm before we 'interrupt ' it . The reason for the interruption w i l l be clear in the next paragraph. Given the root set S associated wi th Q' and given S'Q,, we wi l l use the modified Di jks t ra algori thm to generate the Dijkstra 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 Dijkst ra algorithm as soon as £ T = 1 SQ(S,) ex-ceeds S'Q,, i.e., when we reach an integer k which satisfies both Y^,i=iSQ(sl) < S'Q' A N D SQ{Si) > s'Ql. We wi l l possibly reduce sQ(Sk) to s'Q, - zZi=i 5Q(s,)> and possibly reduce Sk to Sk-i U { j : j a point of G, d(j,Sk-i) < SQ{sk) } 5 and we w i l l refer to the (possibly) reduced Sk as the largest (reduced) enhanced root set associated wi th Q'. A t the termination of the scanning, the set of all Dijkstra cutsets { (Qi,Qi) '• i = 1 , . . . , k } and the corresponding (possibly reduced) values { SQ. : i = 1 , . . . , k }, gener-ated before the algori thm 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, and that Qe{Qi : i=l,...,k} < ? ' £ { < ? ; : t = l,...,*:'} E x a m p l e 3 .3 . We provide in Figure 3.2 the costs dj-, an optimal primal solution subnetwork in G', and an opt imal dual solution { S'Q, : i = 1,. :.,k'} wi th cutsets {{Q'i,Qi) '• i — 1, - - - , A;' }, for the network G', derived from the graph displayed in Figure 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, and two thick lines represent one unit capacity in the primal optimal 68 Figure 3.2: A n Opt imal Solution Subnetwork in G', and the Di jks t ra Cuts. 69 Figure 3.3: A n Opt imal Solution Subnetwork in G, and the Dijkstra Cuts 70 subnetwork. Furthermore, Q[ = { l } , s'Ql = 3; Q'2 = {7}, s'Ql = \\; Q'3 = {9}, s'q, = 2\; Q\ = {7 ,9} , s'Q,t = 2; Q' 5 = {14}, ^ , = 2; = {1,14}, = i ; Q' 7 = {12}, sj,, = i f ; Q's = {5}> = 1 and Q' 9 = {5,12}, s^, = 1. Figure 3.3 displays, in thick lines, the derived optimal primal solution subnetwork in G, and the derived opt imal dual solution { SQ{ : i — 1 , . . . , k } wi th cutsets { (Qi, Qi) : i = 1 , . . . , k }, obtained from the solutions displayed in Figure 3.2 above. In Figure 3.3, Qi = {1,2} , sQl = 1; Q 2 = {1 ,2 ,3} , sQ2 = 1; Q3 = {1 ,2 ,3 ,4} , SQ3 = 1; Q4 = F4 = {7}; Q5 = {6,7}, SQ^ = 1; Q 6 = {6,7}, reduced, 5 Q g = f; Q 7 = F7 = {9}; Q 8 = {8,9}, sQs = 2; Q 9 = {8 ,9} , reduced, sQo = f; Q 1 0 = {6 ,7 ,8 ,9 ,10} , s Q l 0 = §; Q n = {6 ,7 ,8 ,9 ,10 ,11} , = 1; = {6 ,7 ,8 ,9 ,10 ,11} , reduced, sQi2 = f; <?13 = F 1 3 = {14}; Q u = {13,14}, * Q 1 4 = 2; QIB = {1 ,2 ,3 ,4 ,13 ,14} , 5 < 3 i s = | ; Q 1 6 = JF16 = {12}; Q 1 7 = {12}, reduced, sQn = l h = = ( 5 }5 'Sis = {5}> reduced, sQl0 = i f ; and Q20 = {5,12}, s Q , „ = 1. • 3.3.2 Feasibility of the Derived Dual Solution Since the pr imal solution subnetwork W is feasible, and since the objective function value of the pr imal (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 SQ<cuv (u,v)EE. (3.2) L e m m a 3.2. The system of inequalities (S.S) above holds. Proof. Suppose u, but not v, is contained in the nodesets Q u(,) : i = 1 , . . . , v, and v, but not u, is contained in the nodesets Qv(i) : i = 1 , . . . ,v, among the derived nodesets Qi : i = 1,..., k. Since { Qi; : i = 1 , . . . , k } is nested, we can assume that Qu(i) C Qu(i+i), i = l,...,v — 1, and that Qv(i) C Qv(i+i), i = \,...,v — 1. Let the corresponding (reduced) enhanced root sets be {£„(,•) : i = l,...,v} and {Sv^) : i = respectively. As described earlier, we only need to consider those (reduced) enhanced root sets which intersect (u,v) in one interval. Thus, let these intervals be {Iu{i) '• i = l , . . . , v } and {/„(,) : i = respectively. B y (3.1) and by the fact that 71 Figure 3.4: M i (left), M 2 (center), and M 3 (right). these (reduced) enhanced root sets are nested, we get that SQ(S U ( I - ( ) < / ( /« (» ) ) — ^"(t-i))? i = l,...,v, and that S Q ( 5 „ ( i ) ) < - / ( / „ ( , • - ! ) ) , i = l , . . . , i > , where Ju(0) = u and Iv(0) = v. Therefore, £ Q ; ( Q , O ) 9 ( U , „ ) SQ = H=i ^ ( s . ^ J + E ^ i ^ ( 5 „ ( l ) ) < /(/„(„)) +'(V)) ^ cuv, which 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). A graph is M i , M 2 , or Mz-free if it cannot be reduced to the graph M i , nor M 2 nor M 3 (see Fonlupt and Naddef [49] for more details), where M i , M 2 and M 3 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 (Adapted from Fonlupt and Naddef [49]). The extreme solutions to (P') restricted to M i , M 2 , and Mz-free graphs form Steiner tours. • Since the costs (distances) rfj • of the edges in G' are shortest distances in 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') which induces a Hamil tonian cycle, where we recall that a Hami l ton ian cycle is a cycle which visits each node in T exactly once. Since there are at most 4!/2 Hamil tonian cycles, one can enumerate all of them, and subsequently find an 72 opt imal solution. This procedure avoids using linear programming to solve (P'). Thus, we obtain the following result: C o r o l l a r y . For t < 5, the equal-requirement Steiner network synthesis problem can be solved in 0 (5 ! • ra2). • 3.4 Summary and Further Research for the Trans-formation In Chapter 3, we were concerned wi th 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 in 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 optimization. C h a p t e r 4 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 S P E C I A L G R A P H S In this chapter, we wi 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 3 - f ree graphs. This is 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 programming 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 wi th 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. Fi rs t , in Section 4.1, we w i l l describe simple algorithms for the two easy cases when the solution subnetwork has to be embedded in a tree or in a r ing (cycle). A ring (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 Be rn , Lawler , and Wong [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 in order to solve the general requirement Steiner network synthesis problem in the series-parallel graphs, while in Section 4.3, we wi 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 3 -free graphs. The reason for the existence of combinatorial algorithms for the Steiner network synthesis problem in the above special graphs is that al l extreme solutions to any of the reduced linear programs have integer or half-integer values. We wi l l demonstrate, by an example, that the Steiner network synthesis problem in a graph reducible to M2 or M 3 may have extreme solutions wi th arbitrary fractional values, implying 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: Pre-liminaries and the Equal Requirement Case In this section, we wi 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). Then , after some preliminary results and definitions, we wi l l describe how the dynamic programming type of Bern , Lawler , and Wong [14] can be used to solve the equal-requirement Steiner network synthesis problem in series-parallel graphs. 4.1.1 Trees and Rings Firs t consider the simple case when the opt imal solution subnetwork has to be embedded in a tree T. For each edge £ T, let its capacity b^ = max{ ruw : u £ T, w £ Tj }, where Tk, k = is the connected subtree containing k which remains after the removal of edge 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 algori thm is 0 ( n + t2), where t = |T | , and T is the set of demand points. Now, consider the nontr ivial case of a ring (or cycle). We arrange the require-ments rij in a nonincreasing order, i.e., r\, r2,..., rk, w i th > Tj for i < j. In this case, the following procedure provides an opt imal solution. 75 • Starting w i th 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 rij2. 2. Set the costs of the positive capacity edges in the current solution temporarily to zero, and raise to r, the capacity of al 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 optimal for all the re-quirements considered up to and including that iteration, it follows by induction on the number of iterations that the above algorithm provides an optimal solution. The complexity of the above algorithm is 0(nk + t2), where k is the number of necessary positive requirements, which by Gomory and Hu [58] wi l l 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 Re-quirement Case In this subsection, after some definitions, we present a theorem and some other results concerning the Steiner network synthesis problem in series-parallel graphs. Then, we show how the dynamic programming type algori thm of Bern , Lawler, and Wong [14] can be used to solve the equal-requirement case. For 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 wi 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 2 are series-parallel graphs with respective pairs of terminals { « i , i > i } and {^2,^2}, then so are their series and parallel compositions, where in the series composition, vt coincides with u 2 , and the composed graph Gi © G 2 has two terminals ux and v2, and in the parallel composition, ux coincides with u 2 , vx coincides with v2, and the composed graph Gi © G 2 has two terminals ux and vx. 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, wi th 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 graph have only integer or half-integer values. Proof (By Induction on the Number of Edges in Series-Parallel Graphs). If the series-parallel graph is an edge, it is evident that the unique extreme solution to the reduced linear program associated wi th the Steiner network synthesis problem in the edge has an integer value. Now, suppose that all extreme solutions to the reduced linear program associated wi th the Steiner network synthesis problem in any m-edged (i.e., w i th 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 wi th 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 wi l l refer to the set of constraints in the reduced linear program associated wi th 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 )-dimensional vector (one dimension for each edge) satisfying the old (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' in G(m + 1) is a copy of edge e in G(m). Then, 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 be(m + 1) and bei(m + 1) wi l l be positive. Hence, by induction, b(m -+- 1) must have integer or 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" = (VJ,V) in G(m + 1). If w is not a demand node, i.e., it is only an intermediate node, then the new system consists of two copies of the old system, one copy wi th bei(m + l ) , the other wi th be»(m + 1) replacing be(m). Then , we must have that 6 e»(m + l ) = 6 e » ( m + l ) . Now, we define a solution b(m) to the old system using b(m+l) as follows: bi(m) — bi(m+l),l ^ e, / 6 G(m), and be(m) — bei(m + 1) = 6 e »(m + l ) . Then, 6(m) must be an extreme solution to the old system, which by induction has integer or half-integer values. Thus, b(m + l) also has integer or half-integer values. Now, suppose w is a demand node. In this case, in the new system (a) the two copies of the old system, one wi th bei(m + 1), the other wi th 6 e »(m + l ) replacing be(m), may have larger right hand sides (reflecting the additional requirements of to), and (b) there is the additional constraint bei(m + 1) + 6 e »(m + 1) > rw, rw = max t r ^ , i 6 G(m + 1), i=t w. To proceed wi th the proof, we need to revise the requirement structure such that the two copies of the old system wi 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 bei(m + 1) = S e»(m + 1), we create two requirements riu {= riw), if i 7^ u, and riv (— riw), if i ^ v; otherwise, if 6 e » ( m + 1) > ben(m + 1), we create a requirement riv (= r , w ) , if i ^ v, or else, if bei(m + l ) < fee«(m + 1), a requirement riu (= riw), if i ^ u. We w i l l refer to the set of constraints in the reduced linear program associated wi th the Steiner network synthesis problem, wi th the revised requirement structure, in G(m) as the revised old system. Now, we define a solution b(m) to the revised old system, using b(m + 1 ) , as follows: 6;(m) = bi(m +1), / ^ e, I 6 G(m), and be(m) = 6e<(m + 1). Consider the following two cases: 1. If bei[m + 1) = ben(m + 1), then the new system wi th b(m + 1) = b(m + l ) is just like the revised old system wi th b(m) = b(m + 1), wi th the exception of the addit ional constraint bei(m + 1) + 6 e »(m +1) > rw. - If bei(m + l ) + ben(m + 1) = rw, then b(m) must be an extreme solution 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 be>(m + l ) + 6 e » ( m + 1) > rw, then 6(m) must be an extreme solution to 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 bei(m + 1) > 6 e »(ra + 1). Then, we must have that the inequality bei(m + l ) + 6 e »(m + 1) > rw is tight, or else, we can reduce bei(m + 1), because as far as demand nodes, other than w, in G(m + 1) are concerned, only the smaller of bei(m + l ) and be>i(m + l ) could possibly be a 'bottleneck'. However, if we can reduce bei(m + 1) , then b(m + 1) could not have been an extreme solution to the new system. So, suppose bei(m + l ) + 6 e » ( m + 1) = rw. Now, by the construction of the revised requirement structure above, b(m) must be an extreme solution to the revised old system. Thus, by induction, b{m) has integer or half-integer values, and, in particular, S e/(m + l ) = be(m) is integer or half-integer. Furthermore, from equation 6 e »(m + l ) = rw — bei(m + 1), we have that ben(m + 1) is also integer or half-integer. • It is a simple corollary to Theorem 4.1 above, or alternatively see Cornuejols, Fonlupt, and Naddef [36], that when the requirements are equal to 2, all the extreme solutions to the reduced linear program associated wi th the Steiner network synthesis problem in series-parallel graphs have integer values. For the rest of this section, we wi l l consider the equal requirement case. The results obtained for this case wi l l be used in the next section to solve the general requirement case. Recall that in the equal-requirement case, we can assume that al l the requirements are equal to 2, because we can mult iply all the requirements and all the derived capacities by the same constant. The algori thm we wi l l use here to solve the equal-requirement Steiner network syn-thesis problem is similar to that given by Ratliff and Rosenthal [122], who considered the Steiner tour problem in rectangular graphs, i.e., graphs in which all the simple cycles have an even number of edges. Thus, our algori thm is related to the dynamic programming type algorithm of Bern , Lawler, and Wong [14], who generalized, among 80 other things, Ratl iff 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 i ,E ' t ) of a connected graph G = (N,E) is a component of G if there is a pair of nodes {u,v} in Ni such that every simple path connecting a node in iV, wi th a node in N\(Ni U {u, v}) contains either u or v. We wi 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,-) and 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. Recal l that we referred to the subnetwork induced by an extreme solution to the reduced linear program associated wi th 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 and an extreme solution subnetwork in a component G t . Thus, we w i l l refer to the restriction of an extreme solution to a component G , as a partial extreme solution in G , , and we wi l l refer to the subnetwork induced by a part ial extreme solution in G , as a partial extreme solution subnetwork (PESS) in G , . The following lemma states that the P E S S ' s in any component of a series-parallel graph, associated wi th the Steiner network synthesis problem, with requirement equal to 2, in 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 sum 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 0C) , one component ( IC) , or two components (2C). L e m m a 4.1. Partial extreme solution subnetworks in any component G , of a series-parallel graph G, associated with the Steiner network synthesis problem, with requirements equal to 2, in G, are of the types (equivalence classes) (E,E,1C), (U,U,1C), (E,0,1C), (0,E,1C), (E,E,2C), (0,0,0C), or (0,0,1C). • Since, as a consequence of Theorem 4.1 above, the extreme solutions to the reduced linear program associated wi th the Steiner network synthesis problem, wi th require-ments 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 Ratl iff and Rosen-81 <u) (u) (u) ® (u) ® ® £ <j 9 <!> o v H M } o » © d ) (X) ® ® Figure 4.1: Types i , i i , i i i , iv , v, v i , and v i i (from left to right) of Par t ia l Extreme Solution Subnetworks in a Simple Path Associated wi th the Steiner Network Synthesis Problem, wi th Requirements Equal to 2, in a Series-Parallel Graph . thai 1122]. A complete proof is easy but quite lengthy, and is omitted here. If the component Gi is a simple path, 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 rep-resent some demand nodes (not shown), and the shown demand nodes are thicklined circles. For brevity, we wi l l be referring to these configurations as type i , type i i , . . . , and type v i i . An Algorithm for the Steiner Network Synthesis Problem, with Require-ments equal to 2, in a Series-Parallel Graph G Conceptually, the algori thm 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 . Then , construct 82 Table 4.1: The Series Composit ion 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) (U,U,1C) (E.0.1C) (E,E,2C) (E,E,2C) (E,0,1C) (U,U,1C) (U,U,1C) (U,U,1C) (E,0,1C) (E,E,2C) (E,E,2C) (E.O.IC) (0,E,1C) (0,E,1C) (0,0,1C) (0,0,1C) (E,E,2C) (E.E.2C) (0,0,0C) (0,E,1C) (0,0,1C) (0,E,1C) (0,0,0C) (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 (PESS) of each type, at each internal node of the binary decomposition tree, by composing (in series if the node is labelled S, in 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 which is also feasible. For i l lustrat ion, see Example 4.1. below. The complexity of scanning is 0 ( 7 3 • (2n — 3)) = O(n) , since (a) at each internal node, there are at most 7 2 ways of composing a particular P E S S from the best P E S S ' s in 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 algori thm, which are similar to those given by Rat l i f f and Rosenthal [122], are displayed in Tables 4.1 and 4.2, respectively. In Table 4.1, the left column contains the types of P E S S ' s in the (left) component G x (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 in the series composition G x © G 2 (with terminals u and v), where the empty 83 Table 4.2: The Parallel Composit ion M a t r i x (E,E,1C) (U,U,1C) (E,0,1C) (0,E,1C) (E.E.2C) (0,0,0c) (o,o,ic) (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) (0,0,0C) (E,E,1C) (U,U,1C) (E,0,1C) (0,E,1C) (E,E,2C) (0,0,0C) (0,0,1C) (0,0,1C) (0,0,1 C) C5 eg e 6 en e 9 2 w 2 W 2 w 2 w 2 Figure 4.2: A Series-Parallel Graph (left), and its Reduced Graph (right). ei2 cells indicate infeasible series compositions. Similarly, in Table 4.2, the left column contains types of P E S S ' s in the (left) component Gi (with terminals U\ and i>i), the top row contains types of P E S S ' s in the (right) component G 2 (with terminals u2 and v2), and the other cells represent types of P E S S ' s in the parallel composition Gx © G2 (with terminals u\ and V\). The following example illustrates the above algorithm. Example 4.1. Consider the left graph in Figure 4.2, where the costs (or distances) dij are shown on the edges, and the demand nodes are thicklined circles. This graph, which is similar to that in Ratliff and Rosenthal [122], is easily seen to be series-parallel. Discarding the degree 2 nodes, we get the reduced graph wi th edges e l 5 . . . , eX 2, displayed 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 Binary Decomposition Tree for the Reduced Graph in Figure 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 in series or parallel , respectively. We have also assigned a number to all internal nodes, and for clarity, also to the nodes labelled tx and e 1 2 , to indicate the pattern of scanning. We wi l l scan the binary decomposition tree from left to right, starting at 1 and finishing at 12. The results of compositions are shown in Table 4.3, where the top row specifies the stage of the dynamic programming type algorithm which also corresponds to the numbers assigned to some of the nodes in the binary decomposition tree. The 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 PESS(s) in the left component, and 7 is the type(s) of best PESS(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 in left component is a best-upto-the-previous-stage composed P E S S , whereas best P E S S in the right component is a best P E S S in a simple path (see Figure 4.1). For brevity, /? w i l l take values 1 , 2 , . . . , and 7 representing the types ( E , E , l C ) , . . . , (0 ,0 , IC) , 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 Figure 4.1 above. Also , we ignore, in this example, the last two rows of the table corresponding to the types (0,0,0C) and (0,0,IC), because every left component and the last right component contain at least a demand node. Stage 12's column in Table 4.3 contains the cost of best complete extreme solution subnetworks of each type, in addit ion to the information necessary for constructing these subnetworks by backtracking. We note that, in general, only types ( E , E , 1 C ) , (E ,0 ,1C) , (0 ,E,1C), and 85 Table 4.3: The Computations for Example 4.1 Stage Type 1 2 3 4 5 6 1 (E.E.1C) 38, - , i 34, 2, ii 38, 1, i 42, l , i 53, 2, ii 57, 1, i 2 (U,U,1C) 19, - , i i 37, 2, v 36, 1, i i 38, 2, ii 53, 3 or 4, ii 55, 1 or 2, i i 3 (E,0,1C) 28, - , iii 48, 3, i i i 34, 1, vi 38, 3, i 62, 3, iii 53, 1, vi 4 (0,E,1C) 26, - , iv 48, 4, iv 38, 1, i 38, 4, vi 62, 4, iv 57, 1, i 5 (E,E,2C) 28, v 44, 4, v 48, 5, i 52, 5, i 56, 3 or 4, v 60, 5, i Stage Type 7 8 9 10 11 12 1 61, 1, i 61, 1, iv 65, 1, i 69, 1, i 76, 2, i i 95, 1 or 2, ii 2 57, 2, i i 57, 2, iv 59, 2, i i 61, 2, ii 76, 4, i i 95, 2, i i 3 57, 3, i 87, 3, i i i 61, 1, vi 65, 3, i 81, 3, iii 106, 1, iii 4 57, 4, vi 57, 4, iv 61, 4, i 61, 4, vi 77, 4, iv 104, 1, iv 5 64, 5, i 57, 3, iv 61, 5, i 65, 4 or 5, i 77, 4, iii 101, 4 or 5, v (0,0,1 C) of complete solution subnetworks can be feasible, since the other types cannot possess all the connectivity requirements. This 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 The purpose of this section is to gain some insight into the general requirement Steiner network synthesis problem. After i l lustrating the additional complications in the non-equal requirement case, we consider a special case, refered to as the monotone require-ment case, which is a more general model than the equal-requirement case. Subse-quently, we consider the non-monotone requirement model. 4.2.1 The Additional Complications As stated in L e m m a 2.1 in Section 2.1 above, Gomory and H u [58] proved that the opt imal solutions to the network synthesis problem induced by a full requirement struc-86 o—o 9 9 ? 0 9 o 0 1 9 1 6 T o Figure 4.4: A n Opt imal Solution Subnetwork for Example 4.1. ture and by any of its maximum requirement spanning tree ( M R S T ) ' s wi l l be identical. Now, following Gomory and Hu's [58] decomposition approach to the equal-cost net-work synthesis problem, see Example 2.1 in Section 2.1, one would naturally attempt to solve the non-equal requirement (Steiner) network synthesis problem by (a) decom-posing 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 opt imal solution subnetwork, and finally (c) superimposing these derived subnetworks (also see Example 4.2 below for further il lustration). Al though, 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. The superimposed optimal solution subnetwork, though a feasible solution, may not be opt imal , as shown in Example 4.2 below. 2. If the requirement structure is disconnected and/or any of the equal-requirement subtrees is disconnected, it is not clear whether the optimal solution subnetworks and/or the superimposed subnetwork wi l l be connected, as shown in Example 4.3 below. We note that in the equal-cost case, both the optimal solution subnetworks and the superimposed subnetwork wi l l always be connected if the requirement structure is connected. 8 7 © © © © © 9 © © © © © © Figure 4.5: A Series-Parallel Graph (left), and an Opt imal Solution Subnetwork in it (right). ©^~© © © ^ D © $ ® - J - © © © Figure 4.6: A M R S T (left), Equal-Requirement Subtrees 1 (center) and 2 (right), De-rived 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 wi th 2 units of requirement between every pair, w i th 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 opt imal to the Steiner network synthesis problem in G, and has a total cost of 60 units. A M R S T 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, optimal solution subnetworks 1 and 2 to the Equal-Requirement subtrees 1 and 2 are shown on the 88 O — © - < ) i) <L © © o © © ? © © © © © © © Figure 4.7: Opt imal Solution Subnetworks 1 (left) and 2 (center), and the Superimposed Subnetwork (right). left and center of Figure 4.7. Final ly , the superimposed subnetwork is shown on the right of Figure 4.7, where each line represents one unit of capacity. The superimposed subnetwork is not an opt imal solution subnetwork to the Steiner network synthesis problem in G, since it has a total cost of 61 units. The reason for the suboptimality of the superimposed subnetwork is that each of the optimal solution subnetworks are determined independently, and therefore the excess capacity which may occur in the other subnetwork cannot be uti l ized. Specifically, in the opt imal solution subnetwork 1, there is 1 unit excess capacity between u and v, which is not taken advantage of by the superposition. • Example 4.3 below illustrates the disconnectivity issue mentioned in i tem 2 above. E x a m p l e 4.3. Again consider the left graph G in Figure 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 opt imal ways, shown in Figure 4.8. Depending on costs (distances) one of the solutions wi l l be cheaper than the other. For example, if 0I34 is decreased (resp., increased), the solution subnetwork on the right wi l l be cheaper (resp., more expensive) than the other solution displayed in Figure 4.8. • 89 O — O o o ( 3 ) © © © © o © © o o Figure 4.8: A n Opt ima l Solution Subnetwork (left), and another Opt ima l Solution Subnetwork (right) used in Example 4.3. Al though the decomposition of a M R S T does not, in general, provide an optimal solution to the Steiner network synthesis problem, we wi l l show in the remainder of this section, for the series-parallel graphs, and in the next section, for the M2 and M3 - f ree graphs, that it can be modified to do so. Fi rs t , we assume that a M R S T is monotone, i.e., it decomposes only into connected equal-requirement subtrees. 4.2.2 The Monotone Requirement Case Without loss of generality, we can assume that al l the requirements in a monotone M R S T are even, otherwise, we wi l l mult iply the capacities and the requirements by 2. Thus, a l l the equal-requirement subtrees, derived in the decomposition, are connected and have even requirements. Again , without loss of generality, we can assume that al l the requirements in each equal-requirement subtree are equal to 2. The major difference between this case and the equal-requirement case, presented in Subsection 4.1.2 above, is that, in this case we need to consider 7 types of par t ia l extreme solution subnetwork (PESS) ' s associated wi th each of the equal-requirement subtrees. Therefore, if there are k equal-requirement subtrees, we have to keep track of 7k types 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. Then, there are 7 2 = 49 types of P E S S ' s , each being the Cartesian product of two P E S S ' s , one associated wi th 9 0 one of the subtrees, and the other wi th the other subtree (see Example 4.4 below). To prevent confusion, we wi l l refer to these Cartesian P E S S ' s as partial composed solutions subnetworks ( P C S S ) . 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 with the following two exceptions: • Instead of being 7 by 7, the composition matrices are 7fc by 7k. • The type of a P C S S depends on the types of P E S S ' s associated wi th all the subtrees (see Example 4.4 below for illustration). Since, by Theorem 4.1 above, the extreme solutions to the Steiner network synthesis problem, wi th 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 algorithm provides an optimal solution to the monotone requirement Steiner network synthesis problem. Furthermore, the algorithm requires 0{7k • n) operations, which is linear in ra, and by Gomory and H u [58], k cannot be greater than |!T| — 1, implying that for small values of k, the above algorithm wi l l be practical (see Example 4.5 below for il lustration). 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. Thus, 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. The 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, and 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 matr ix 91 presented in Table 4.1 above. For example, the series composition of ( (U,U,1C), (E,0 ,1C)) and ( (E ,E ,1C) , (0 ,E ,1C)) is ( (U ,U ,1C) , (E ,E ,2C) ) . The 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)) wi th ( (a ' , / ? ' ,7 ' ) , (6',e',c')) in parallel. Fi rs t , we say that (E ,E ,1C) has 2 units of connectivity, because 2 units of flow can be channelled between the two terminals u and v, and that similarly, (U ,U ,1C) has 1 unit of connectivity. Now, if the sum 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,1C) , ( E , E , 2 C ) , (0,0,0C), or (0,0,1C) (except when infeasible) as ( U , U , l C ) , and to categorize (U ,U,1C) 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. • Example 4.5 below illustrates the algorithm 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 maximum requirement spanning tree ( M R S T ) is shown on the left in Figure 4.10, and two equal-requirement subtrees, derived from the M R S T by the decomposition, are shown on the center and right. The computations resulting from the compositions are displayed in Table 4.4, whose left column 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 wi th the equal-requirement subtree 1 (on the center of Figure 4.10), and (6,e,c) is associated wi th the equal-requirement subtree 2 (on the right of Figure 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, which is displayed on the right in Figure 4.9, Stage 2 corresponds to the parallel composition e\ © e 2 of e\ and e 2, and Stage 3 corresponds to the parallel composition of ex © e2 wi th e$. Furthermore, each of the other cells in 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 Decomposit ion. 93 © o Figure 4.11: Best Par t ia l Composed Solution Subnetworks for (E ,E ,1C) - (E ,E ,1C) 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 i l lustrat ion, we show, in Figure 4.11, the best P C S S ' s corresponding to the type (E ,E ,1C) - (E ,E ,1C) at stages 1, 2, and 3, where each ordinary line represents one unit capacity for the equal-requirement subtree 1 and, if possible, shared wi th the equal-requirement subtree 2, whereas each thick line represents one unit of capacity only for the equal-requirement subtree 2. The right column in Table 4.4 indicates the feasible solution subnetworks, the cheapest of which, in fact, corresponds to the type ( E , E , 1 C ) - ( E , E , 1 C ) , displayed on the right of Figure 4.11. • 4.2.3 The Non-Monotone Requirement Case In the non-monotone requirement case, the requirement structure and/or some of the equal-requirement subtrees, derived from it through the decomposition, may be discon-nected. We note that this case is the most general requirement structure. To solve the non-monotone requirement case, we wi l l modify the dynamic programming type algori thm used for the monotone requirement case, in Subsection 4.2.2 above. Fi rs t , we note that in the monotone requirement case, while we were computing the Carte-sian product of part ial composed solution subnetwork (PCSS) ' s , for each edge, we, in effect, added the capacity of the edge across the partial extreme solution subnetwork Table 4.4: The Computations used in Example 4.5. Type Stage 1 2 3 1 (E,E,1C) • (E,E,1C) 7 6 , - , 1 64, 13, 8 68, 2, 13 feasible 2 (E,E,1C) • (U,U,1C) 5 7 , - , 2 49, 13, 9 63, 2, 34 3 (E,E,1C) (E,0,1C) 4 8 , - , 3 58, 13, 10 77, 3, 34 feasible 4 (E,E,1C) (0,E,1C) 4 6 , - , 4 56, 13, 11 75, 4, 34 feasible 5 (E.E.1C) • (E,E,2C) 56, -, 5 48, 13, 12 67, 5, 34 6 (E,E,1C) • (o,o,oc) 38, - , 6 7 (E,E,1C) • (o,o,ic) 58, - , 7 50, 13,14 86, 14, 13 feasible 8 (U,U,1C) • (E,E,1C) 57, - , 8 63, 34, 8 77, 8, 34 9 (U,U,1C) • (U,U,1C) 38, - i 9 48, 34,9 62, 9, 34 10 (U,U,1C) (E,0,1C) 2 9 , - 10 57, 34, 10 71, 10, 34 11 (U,U,1C) • (0,E,1C) 27 , - , 11 55, 34, 11 69, 11, 34 12 (U,U,1C) • (E,E,2C) 37 , - , 12 47, 34, 12 61, 12, 34 13 (U,U,1C) • (o,o,oc) 38, - , 13 33, 34, 13 47, 13, 34 14 (U,U,1C) • (o,o,ic) 58, - 14 49, 34, 14 63, 14, 34 15 (E.0.1C) • (E,E,1C) 68, - 15 84, 20,15 116, 15, 20 feasible 16 (E,0,1C) • (U,U,1C) 4 9 , - 16 69, 20, 16 101, 16, 20 17 (E,0,1C) • (E,0,1C) 4 0 , - 17 78, 20, 17 110, 17, 20 feasible 18 (E,0,1C) • (0,E,1C) 38, - 18 76, 20, 18 108, 18, 20 feasible 19 (E,0,1C) • (E,E,2C) 4 8 , - 19 68, 20,19 100, 19, 20 20 (E,0,1C) • (o,o,oc) 30, - 20 54, 20, 20 86, 20, 20 21 (E,0,1C) • (o,o,ic) 50, - ,21 54, 20, 21 86, 21, 20 feasible 22 (0,E,1C) • (E,E,1C) 66, - 22 80, 27, 22 110, 22, 27 feasible 23 (0,E,1C) • (U,U,1C) 4 7 , - 23 65, 27, 23 95, 23, 27 24 (0,E,1C) • (E,0,1C) 38, - 24 62, 27, 24 104, 24, 27 feasible 25 (0,E,1C) • (0,E,1C) 36, - 25 61, 27, 25 102, 25, 27 feasible 26 (0,E,1C) • (E,E,2C) 4 6 , - 26 64, 27, 26 94, 26, 27 27 (0,E,1C) • (o,o,oc) 2 8 , - 27 50, 27, 27 80, 27, 27 28 (0,E,1C) • (0,0,IC) 2 8 , - 28 50, 27, 28 80, 28, 27 feasible 29 (E,E,2C) • (E,E,1C) 5 7 , - 29 62, 34, 29 76, 29, 34 30 (E,E,2C) • (U,U,1C) 3 7 , - 30 47, 34, 30 61, 30, 34 31 (E,E,2C) • (E,0,1C) 2 8 , - 31 56, 34, 31 70, 31, 34 32 (E.E.2C) • (0,E,1C) 1 8 , - 32 54, 34, 32 68, 32, 34 33 (E.E.2C) • (E,E,2C) 1 8 , - 33 46, 34, 33 60, 33, 34 34 (E,E,2C) • (o,o,oc) 1 8 , - 34 32, 34, 34 60, 34, 34 35 (E,E,2C) • (o,o,ic) 38, - 35 48, 34, 35 76, 35, 34 95 Figure 4.12: The M R S T used in Example 4.6. (PESS) ' s in the Cartesian product. Now, to proceed wi th the modification, let T r be any disconnected equal-requirement subtree derived from a M R S T by the decomposi-t ion, and let T}, T 2 , . . . , Tlr be a min imum number of connected subtrees comprising Tr. For i l lustrat ion, see Example 4.6 below and Figure 4.12. Now, instead of associating a P E S S to TT, we wi l l associate a P E S S to each of the connected subtrees T*, i' = 1 , . . . , / , comprising it. However, while computing the Cartesian product of P E S S ' s , for each edge, we wi l l first find the max imum capacity of the edge across the P E S S ' s associated wi th T), T r 2 , . . . , J|f, and then add this max imum value to the sum of the capacities for the edge across the other P E S S ' s in the Cartesian product. This is because the requirements in T,,T?,...,T}. 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 than | T | 2 , where T is the set of demand nodes. Thus, 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 practical . Example 4.6 below illustrates the above algori thm for the general requirement Steiner network synthesis problem. Example 4.6. Suppose that the requirements in a M R S T , Tr, shown in Figure 4.12, have to be satisfied in 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 r 2 . The computations are summarized in Table 4.5, 96 Figure 4.13: Best Par t ia l Composed Solution Subnetworks of Type (E ,E ,1C) - (E ,E ,1C) at Stages 1 (left), 2 (center), and 3 (right). where the first 3-tuple in the left column of the table corresponds to T r J , and the second 3-tuple corresponds to T2. 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, in 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 r 2 , and 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 M2 and M 3-Free Graphs In this section, we wi l l only briefly explain how the modified dynamic programming type algori thm, 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 M2 and M 3 - f ree graphs. We further demonstrate, by an example, that the Steiner network synthesis problem in a graph reducible to M2 or M3 may have extreme solutions with arbitrary fractional values, implying that the dynamic programming type algorithm cannot easily be extended to the Steiner network synthesis problem in more general graphs. Table 4.5: The Computations used in Example 4.6. Stage Type 1 2 3 1 (E.E.1C) • (E,E,1C) 38, 1 34, 9, 9 48, 1, 18 feasible 2 (E,E,1C) • (U,U,1C) 38, - , 2 39, 10, 9 53, 2, 18 feasible 3 (E,E,1C) • (E,0,1C) 38, - , 3 51, 10, 10 83, 3, 17 feasible 4 (E,E,1C) • (0,E,1C) 38, - , 4 51, 11, 11 65, 4, 18 feasible 5 (E,E,1C) • (E,E,2C) 38, - , 5 42, 10,11 56, 5, 18 feasible 6 (E,E,1C) • (0,0,0C) 38, - , 6 34, 13,13 42, 6, 20 7 (E,E,1C) • (0,0,1C) 38, - , 7 8 (U,U,1C) • (E,E,1C) 38, - , 8 38, 23, 9 52, 8, 18 feasible 9 (U,U,1C) • (U,U,1C) 19, - , 9 33, 24, 9 47, 9, 18 feasible 10 (U,U,1C) • (E,0,1C) 24, - , 10 45, 24, 10 77, 10, 17 11 (U,U,1C) • (0,E,1C) 33, - 11 46, 25, 11 60, 11, 18 12 (U,U,1C) • (E,E,2C) 28, - , 12 36, 24,11 50, 10, 18 13 (U,U,1C) • (0,0,0C) 19, - , 13 23, 27, 13 31, 13, 20 14 (U,U,1C) • (0,0,1C) 29, - , 14 15 (E,0,1C) • (E,E,1C) 38, - , 15 53, 16,16 67, 15, 18 feasible 16 (E,0,1C) • (U,U,1C) 34, 16 49, 17, 16 63, 16, 18 17 (E,0,1C) • (E,0,1C) 30, - , 17 54, 17, 17 86, 17, 17 feasible 18 (E,0,1C) • (0,E,1C) 38, - 18 52, 18,18 66, 18, 18 feasible 19 (E,0,1C) • (E,E,2C) 38, 19 44, 17,18 58, 17, 18 feasible 20 (E,0,1C) • (0,0,0C) 30, - , 20 38, 20, 20 46, 20, 20 21 (E,0,1C) • (0,0,1C) 30, -,21 22 (0,E,1C) • (E,E,1C) 38, - , 22 49, 23,23 79, 22, 25 feasible 23 (0,E,1C) • (U,U,1C) 23, - , 23 44, 24,23 74, 22, 25 24 (0,E,1C) • (E,0,1C) 18, 24 48, 24, 24 88, 24, 24 feasible 25 (0,E,1C) • (0,E,1C) 28, - 25 50, 25,25 80, 25, 25 feasible 26 (0,E,1C) • (E,E,2C) 18, - , 26 40, 24, 25 70, 24, 25 27 (0,E,1C) • (0,0,0C) 28, - , 27 30, 27, 27 60, 27, 27 28 (0,E,1C) • (0,0,IC) 28, - , 28 29 (E,E,2C) • (E,E,1C) 38, - , 29 42, 23, 16 56, 29, 18 feasible 30 (E,E,2C) • (U,U,1C) 28, - , 30 37, 24, 16 51, 29, 18 31 (E,E,2C) • (E,0,1C) 38, - , 31 42, 24, 17 74, 31, 17 32 (E,E,2C) - . ( O ^ I C ) 18, - , 32 42, 25, 18 56, 32, 18 33 (E,E,2C) • (E,E,2C) 18, - , 33 32, 24,18 46, 31, 18 34 (E,E,2C) • (0,0,00) 18, - , 34 16, 27,20 24, 34, 20 35 (E,E,2C) • (0,0,1C) 38, - , 35 4.3.1 Preliminaries 98 Fonlupt and Naddef [49] were the first to introduce the class of M i , M 2 , and M3-free graphs (see Figure 3.4 for a display of M i , M 2 , and M 3 graphs), i.e., the graphs which do not have M 1 ; nor M 2 , nor M 3 as a minor, where, as we recall, a graph H is a minor of a graph G if G can be reduced to H by a sequence of edge deletion, isolated-node deletion, and edge contraction (see Subsection 3.3.3 for more details). The larger class of M 2 and M3-free graphs, of course, consists of the graphs which do not have M 2 nor M 3 as a minor. Fonlupt and Naddef [49], when considering the Steiner Tour problem in some special graphs, had to exclude M x as a minor, since a network which reduces to M x , but not to M 2 nor M 3 , w i th edge capacities equal to one unit , cannot be a solution to the Steiner Tour problem, whereas it can be an optimal solution subnetwork to the Steiner network synthesis problem, wi th requirements equal to 2 (see e.g., the left subnetwork in Figure 4.7). Thus, we have no reason to exclude M i as a minor. A n interesting characteristic of M 2 and M 3 -free graphs is that they include the series-parallel graphs as a special case. This fact is proven in the following lemma: L e m m a 4.2. The M 2 and M^-free graphs properly contain the series-parallel graphs. Proof. (By contradiction.) Suppose that there exists a series-parallel graph G which has M 2 or M 3 as a minor. It can easily be seen that both M 2 and M 3 have Ki (i.e., the complete graph on 4 nodes) as a minor, thus, K4 must be a minor of 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. • Thus, by solving the Steiner network synthesis problem in M 2 and M 3 -free graphs, we w i l l be extending the results described in Sections 4.1 and 4.2 above for the series-parallel graphs. Another interesting characteristic of M 2 and M 3-free graphs is stated in the following lemma: L e m m a 4.3. A l l extreme solutions to the reduced linear program associated with the Steiner network synthesis problem, w i th requirements equal to 2, in M 2 and M 3 -free graphs have integer values. • 99 The proof of Lemma 4.3 above is lengthy but similar to that given in Fonlupt and Naddef [49], and is omitted here. 4.3.2 Building Blocks and Composition rules Firs t , we need the following definitions. A cockade, see Dirac [42], of two graphs G x and G 2 is their composition such that an edge (ui,vi) in Gx is superimposed on an edge (u2,v2) in G 2 , wi th ux coinciding wi th u2 and V\ coinciding wi th v2. The superimposed edge (ui,vi), or (u2,v2), wi l l be called a hinge. A subdivision of a graph H is a graph G which 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., Wald and Colbourn [156], which are cockades formed by using the triangle as the bui lding block. In fact, Wald and Colbourn [156] proved that series-parallel graphs are part ial 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. M2 and M3 - f ree graphs, in turn , are a generalization of 2-trees, since, by the following theorem, in addition to the triangle, the following bui lding blocks can also be used to form cockades (Dirac [42] used the same building blocks to construct M3 - f ree graphs): • K4, and K5 (i.e., the complete graph on 5 nodes). • Wn, n > 6, i.e., the wheels wi th one centre-node and n rim-nodes, see the left graph in Figure 4.14. • P 3 n , n > 3, i.e., the 3-propellers wi th 3 central nodes and n outer nodes, see the right graph in Figure 4.14. Theorem 4.2 (Dirac [42], Theorem 4). A finite graph with at least three nodes which contains neither a M 3 nor a subdivision of M 3 is either a K3, K4, K5, wheel or 3-propeller, 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 3 . Thus, the graphs stated in Theorem 4.2 above 100 Figure 4.14: A Wheel (left), and a Propeller (right). are precisely the M 3 - f ree graphs. To also exclude M 2 as a minor, all we need to do is to restrict the composit ion of the building blocks when forming cockades. It can be verified that the following restrictions are all the restrictions necessary. 1. For any K4, do not use as hinge all the three edges incident to a node, because (a) any K4, K5, wheel or 3-propeller, or a cockade composed of such graphs, reduce to a triangle (b) the cockade of K4 and 3 triangles using 3 of its edges incident to the same node, results in a graph which contains M 2 as a subgraph, and hence as a minor. For i l lustrat ion, consider the KA shown on the left of Figure 4.15, and its cockade G w i th 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 addit ion to the restriction given in item 1 above, do not use as hinge any two edges incident to a node together wi th the edge which has no endpoints in common wi th them, because this case reduces to item 1 above as follows. Consider the left graph G in Figure 2.1, and suppose edges (1,2), (1,3), and (4,5) are used as hinge. Then , contracting edge (1,5) reduces G to K4 and this case to item 1 above. 3. For any wheel Wn, n > 6, in addition to the restriction given in i tem 1 above, do not use as hinge any spoke, i.e., any edge which connects the centre-node to a 101 Figure 4.15: K4 (left), and its Cockade wi th Three Triangles (right). rim-node. This 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 wi th 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 , n > 6, the same restriction as in item 1 above applies, since the three inner nodes and any of the outer nodes form a K4. 4.3.3 A Combinatorial Algorithm Firs t consider the equal-requirement case, i.e., when all the requirements are equal to 2. The 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 wi th 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 - f ree 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 programming type algo-r i t hm may be devised to solve the Steiner network synthesis problem, wi th requirements equal to 2, in M 2 and M 3 - f ree graphs. A l l we have to ascertain is that best (cheapest) 102 par t ia l extreme solution subnetwork (PESS) for each of the 7 types in each basic build-ing block can be computed in linear time, because, best P E S S ' s in the partial basic bui ld ing blocks can be computed as in the basic building blocks above, by assigning a large cost to the removed edges. Fi rs t , we note that all the basic building blocks are Mi, M 2 and M 3 - f ree , so by Lemma 3.3, we can restrict our search to optimal partial Steiner tours. Now, in K3, K4 and K*,, we can use the transformation described in Chapter 3 above to find best (cheapest) partial Steiner tours in 0 (1 ) . Best (cheapest) part ial Steiner tours in the wheels and the 3-propellers can also be obtained in linear t ime, because wheels and 3-propellers can be constructed recursively, see e.g., [1,2,14], and because part ial Steiner tours in recursively defined graphs can be found in linear t ime, using the algori thm by Bern , Lawler, and Wong [14]. The 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 program associated wi th the (Steiner) network synthesis problem (even when the requirements are equal) in graphs reducible to M 2 or Ms, which have arbitrary fractional values p/q, such that this ratio cannot be simplified and that q grows (linearly) wi th the number of the nodes n. Thus, it is highly unlikely that there exists any polynomial dynamic programming type algorithms for the (Steiner) network synthesis problem in a more general class of graphs than M 2 and M 3 - f ree graphs. It is easy to see that the graph, displayed in Figure 4.16, is reducible to M 2 and M 3 . E x a m p l e 4.7 (Adapted from Boyd and Pulleyblank [24]). Consider the network G displayed in Figure 4.16, where the capacities are given on the edges, and k is any odd integer > 3. Further, the number of nodes is 2k + 4, and the number of positive capacity edges is 3k + 6. Let b be the vector of positive capacities in G. Obviously, b is a feasible solution to the reduced linear program associated wi th the (Steiner) network synthesis problem, wi th requirements equal to 2, in G. B o y d and Pulleyblank [24] used this example to show that the Travelling Salesman problem ( T S P ) , without the zero-one integrality constraints, can have extreme solutions wi th 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 Problem. 104 i £ JV) in the reduced linear program associated wi th the (Steiner) network synthesis problem, w i th 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 wi th the (Steiner) network synthesis problem, wi th 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 form 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 in G. These constraints are as follows. There are 2k + 4 equations associated with the cutsets (Q,N\Q), \Q\ — 1, i.e., one equation for each node. Further, there are A; + 1 equations associated wi th 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. Final ly , the constraint associated wi th the cutset (Q,N\Q) = { e l 5 e 2 , . . . , ek} is 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. Then, we considered the series-parallel graphs, and showed that, when the solution subnetwork is to be embedded in series-parallel graphs, all the extreme solutions to the Steiner network synthesis problem wi l l have integer or half-integer values. Further, we showed how the dynamic programming type algori thm of Bern, Lawler , and Wong [14] can be used to solve the Steiner network synthesis problem in series-parallel graphs. Then, we considered the M 2 and M 3 - f ree 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 3 - f ree graphs. The Steiner network synthesis problem is closely related to the Generalized Steiner problem ( G S P ) , see Winter [159], which is precisely the Steiner network synthesis prob-lem wi th 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 in series-parallel graphs and in M 2 and M 3 - f ree graphs can easily be extended to the G S P . Thus, we gen-eralized the result given by Winter [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. Restrict ing the solution network to the above special graphs may appear to be a l imi ta t ion of this chapter. However, we have shown that more general graphs may allow solutions wi th fractional values, which complicate the computations. Therefore, the dynamic programming type algorithm does not appear to be suitable for more general graphs. 4 .5 A Final Comment The author wishes to thank the external examiner, D r . A . Tamir , for pointing out a linear programming formulation of the nonsimultaneous network synthesis problem which has a polynomial number of constraints and variables. This formulation is as follows: M i n f £ dij • l<:'j<n, i^j S . T . E fg- E fJL = ~rkl \<k<l<n i'gJV, i^k m£N, m^k E fu - £ ffl = ru l<k<l<n £ . . / # - E J?m = o jeN, j^k,l, \ < k < l < n rkl fij < bij 1 < i,j <n, i ^ j , 1 < k < I < n b^ = bji 1 < i,j <n, j b^ > 0 1 < i,j < n, i' ^ j fij > 0 1 < i,j < n , i / j, 1 < Jfc < / < n The above formulation has the following immediate implications that are relevant to this thesis: 106 • Using 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) min imum 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 in the shrunken network. B ibliography [l] Arnborg , Stefan, and Andrzej Proskurowski. "Linear T ime Algor i thms for N P -Hard Problems on Graphs Embedded in k-Trees." T R I T A - N A - 8 4 0 4 , Department of Numerical Analysis and Comput ing Science, The Royal Institute of Technology, Stockholm, 1984. Arnborg , Stefan, and Andrzej Proskurowski. "Characterization and Recognition of Par t ia l 3-Trees." SIAM J. Alg. Disc. Meth., (2) (Apr i l 1986), 305-314. Ar t i e , R . , and C . Averous. "The Telephone System as a Publ ic Good : Static and Dynamic Aspects." Bell Journal of Economics and Management Science, 4 (1973). Aumann , R . J . , and M . Maschler. "Game Theoretic Analysis of a Bankrupcy Problem from the Talmud." Journal of Economic Theory, 36 (1985), 195-213. Aumann , R . J . , and L . S. Shapley. Values of Non-Atomic Games. Pr inceton, New Jersey: Princeton University Press, 1974. A u t i n , C , and G . Leblanc. "Empir ica l Evaluation of Cross-Subsidy Tests for Canadian Interregional Telecommunication Networks." In L . Courvi l le , A . de Fontenay, and R . Dobel (Eds.), Economic Analysis of Telecommunications, Ams-terdam: Nor th Hol land, 1983. P p . 341-364. Baker, K . R. , and R. E . Taylor. " A Linear Programming Framework for Cost Al locat ion and External Acquis i t ion when Reciprocal Services Exis ts ." The Ac-counting Review, 54 (1979), 784-790. Balachandran, B . V . , and R . T . S. Ramakrishnan. "Joint Cost Allocations: A Unified Approach." The Accounting Review, (January 1981), 85-96. Ba l insk i , M . L . , and F . M . Sands. "The Al locat ion of Runway Slots by Auct ion." In H . P. Young (Ed.) , Cost Allocation: Methods, Principles, Applications, Ams-terdam: Nor th Hol land, 1985. P p . 179-192. Banker, R . D . "Equity Considerations in Traditional Fu l l Cost Al loca t ion Prac-tices: A n Axiomat ic Perspective." In Joint Cost Allocations, Norman , Oklahoma: Center for Economic and Management Research, 1981. P p . 110-130. Baumol , W . J . , and D . Bradford. "Opt imal Departures from Marg ina l Cost Pr ic-ing." American Economic Review, 60 (1970), 265-283. 107 108 [12] Bel l -Nor thern Research. "Designing Voice Communicat ion Networks." In Suc-cessfull Operational Research in Canada, Canadian Operational Research Society, 1985. [13] Berge, Claude. Graphs, Second Revised Edi t ion . Amsterdam: North-Holland, 1985. [14] Bern , M . W . , E . L . Lawler, and A . L . Wong. "Why Certain Subgraph Computa-tions Require Only Linear Time." Proc. 26th Ann. IEEE Symp. on Foundations of Computer Science, (1985), 117-125. [15] Biddle , G . C , and R . Steinberg. "Al locat ion of Joint and Common Costs." Journal of Accounting Literature, 3 (1984), 1-45. [16] Bi l l e ra , L . J . , and D . C . Heath. "Al locat ion of Shared Costs: A Set of Axioms Y i e l d i n g a Unique Procedure." Mathematics of O. R., 7 (1982), 32-39. [17] Bi l l e ra , L . J . , D . C . Heath, and J . Raanan. "Internal Telephone B i l l i n g Rates—A Novel Appl ica t ion of Non-Atomic 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 Allocat-ing C o m m o n Costs from a Product ion Process." Journal of Accounting research, 19 (1981), 185-196. [19] B i r d , C . G . , "On Cost Al locat ion for a Spanning Tree: A Game Theory A p -proach." Networks, 6 (1976), 335-350. [20] B l a n d , R . G . , D . Goldfarb, and M . J . Todd . "The El l ipso id Me thod : A Survey." Operations Research, 29(6) (1981), 1039-1091. [21] Boatsman, J . R . , D . R . Hansen, and J . I. K imbre l l . " A Rat ional and Some E v i -dence Supporting an Alternative to the Simple Shapley Value." In Joint Cost Al-locations, Norman , Oklahoma: Center for Economic and Management Research, 1981. [22] Bodnar , G . , and E . J . Lusk. "Motivat ional Considerations in Cost Allocat ion Systems: A Condit ioning Theory Approach." The Accounting Review, (October 1977), 857-868. [23] Bondy, J . A . , and U . S. Mur ty . Graph Theory with Applications. London: M a c M i l -lan press, 1976. [24] B o y d , Sy lv ia C , and W . R . Pulley blank. "Optimizat ion Over the Subtour E l i m -ination Polytope of the Travelling Salesman Problem." Research Report 84-12, Faculty of Mathematics , University of Waterloo, 1984. [25] Brander , J . A . , and B . J . Spencer. "Local Telephone Pr ic ing: Two Tariffs and Price Discr iminat ion." In L . Courvi l le , A . de Fontenay, and R . Dobel (Eds.), Economic Analysis of Telecommunications, Amsterdam: Nor th Hol land, 1983. P p . 305-316. 109 [26] Brief, R . P. , and J . Owen. " A Least Squares Al locat ion Mode l . " Journal of Ac-counting Review, (Au tumn 1968), 193-198. [27] Cal len , J . L . "Financial Cost Allocations: A Game Theoretic Approach." Ac-counting Review, 53 (1978), 303-309. [28] Campbel l , Br i an , and Ronald L . Rard in . "Polynomial T ime Solution of Steiner Tree Problems on Special Planar Graphs." Research Memorandom No. 86-7, In-dustrial Engineering, Purdue University, M a y 1986. [29] Ca r l i n , A . , and R . E . Park. "Marginal Cost Pr ic ing of Airpor t Runway Capacity." American Economic Review, 60(3) (1970), 310-319. [30] Champsaur, P. "How to Share the Cost of a Publ ic Good." International Journal of Game Theory, 4 (1975), 113-129. [31] Christensen, L . R . , D . Cummings, and P. E . Schoech. "Econometric Estimation of Scale Economies in Telecommunications." In L . Courvil le , A . de Fontenay, and R . Dobel (Eds.), Economic Analysis of Telecommunications, Amsterdam: Nor th Hol land, 1983. P p . 27-53. [32] Christofides, Nicos, and C . A . Whit lock. "Network Synthesis wi th Connectivity Const ra in ts -A Survey." Operational Research'81. In J . P. Brans (Ed.) , Amster-dam: Nor th Hol land, 1981. P p . 705-723. [33] Claus, A . , and D . Granot. "Game Theory Appl icat ion to Cost Al loca t ion for a Spanning Tree." Working Paper No. 402, Faculty of Commerce and Business Adminis t ra t ion , University of Br i t i sh Columbia , June 1976. [34] Claus, A . , and D . J . K le i tman . "Cost Al locat ion for a Spanning Tree." Networks, 3 (1973), 289-304. [35] Cohen, S. I., and M . Loeb. "Publ ic Goods, Common Inputs, and the Efficiency of Fu l l Cost Allocations." Accounting Review, 57 (1982), 336-347. [36] Cornuejols, G . , J . Fonlupt, and D . Naddef. "The Travelling Salesman Problem on a Graph and Some Related Integer Polyhedra." Mathematical Programming, 33(1) (1985), 1-27. [37] Cornuejols, G . , D . Naddef, and W . R. Pulleyblank. "Hal in Graphs and the Trav-elling Salesman problem." Mathematical Programming, 26 (1983), 287-294. [38] Cur ien , Nicolas. "Cost Al loca t ion and Pr ic ing Pol icy: The Case of French Telecommunications." In H . P. Young (Ed.) , Cost Allocation: Methods, Principles, Applications, Amsterdam: Nor th Hol land, 1985. Pp . 167-178. [39] Davis , M . , and M . Maschler. "The Kernel of a Cooperative Game." Naval Research Logistics Quarterly, 12 (1965), 223-259. [40] Di jks t ra , E . W . " A Note on T w o Problems in Connection wi th Graphs." Nu-merische Mathematik, 1 (1959), 269-271. 110 Di rac , G . A . " A Property of 4-Chromatic Graphs and Some Remarks on Cr i t ica l Graphs." J. London Math. Society, 17 (1962), 85-92. Dirac , G . A . "Some Results Concerning the Structure of Graphs." Canadian Math. Bull, 6 (1963), 183-210. Dubey, P. "The Shapley Value as Aircraft Landing Fees—Revisited." Management Science, 28 (1982), 869-874. Dubey, P., and L . S. Shapley. "Totally Balanced Games Ar is ing from Controlled Programming Problems." Mathematical Programming, 29 (1984), 245-267. Dufhn, R . J . "Topology of Series-Parallel Networks." Journal of Mathematical, Analysis and Applications, 10 (1965), 303-310. Eckel , L . G . "Arbi t rary and Incorrigible Allocations." Accounting Review, 50 (1976), 764-777. Engelbrecht-Wiggans, R. , and D . Granot . " O n Market Prices in Linear Product ion Games." Mathematical Programming, 32 (1985), 366-370. Faulhaber, G . "Cross-Subsidization: Pr ic ing in Publ ic Enterprises." American Economic Review, 65 (1975), 966-977. Fonlupt, J . , and D . Naddef. " The Travelling Salesman Problem i n . Graphs wi th Some Excluded Minors ." Working Paper No. 557, Universite Scientifique et Medicale de Grenoble, France, Sept. 1985. Ford, L . R . , and D . R . Fulkerson. Flows in Networks. Princeton: Princeton Un i -versity Press, 1962. Fremgen, J . M . , and S. S. Liao . "The Al locat ion of Corporate Indirect Costs." Nat ional 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. "Applications of Efficient Mergeable Heaps for Opt imizat ion Problems on Trees." Acta Informatica, 13 (1980), 53-58. Gangolly, J . S. " O n Joint Cost Al loca t ion: Independent Cost Proport ional Scheme ( ICPS) 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 Game Theoretic Appl ica t ion to Planning Investment in Electr ical Power." International Economic Review, 15 (1974), 195-208. Gil l ies , D . B . Some Theorems on n-Person Games. P h . D . Thesis, Department of Mathematics , Princeton University, 1953. I l l [58] Gomory, R . E . , and T . C . H u . "Mul t i -Terminal Network Flows." J. SIAM, 9(4) (1961), 551-570. [59] Gomory, R . E . , and T . C . H u . " A n Appl ica t ion of Generalized Linear Program-ming to Network Flows." J. Soc. Indust. Appl. Math., 10(2) (1962), 260-283. [60] Gomory, R . E . , and T . C . H u . "Synthesis of a Communicat ion Network." J. Soc. Indust. Appl. Math., 12(2) (1964), 348-369. [61] Granot , Daniel . " A Note on the Room-Mate Problem and a Related Revenue Al loca t ion Problem." Management Science, 30 (1984), 633-643. [62] Granot , Daniel . " A Generalized Linear Product ion Mode l : A Unifying Model . " Mathematical Programming, 34 (1986), 212-222. [63] Granot , Daniel , and Frieda Granot. "On Some Network Flow Games." Working Paper No. 1056, University of Br i t i sh Columbia , 1984. [64] Granot , Daniel , and Frieda Granot. "On Cost and Revenue Al loca t ion Problems Ar is ing in Mathemat ica l Programming Models." Proceedings of the 6th Mathe-matical Programming Symposium, Japan, November 1985. P p . 121-146. [65] Granot , Daniel , and Frieda Granot . " A F ixed Cost Spanning Forest Problem." Working Paper, University of Br i t i sh Columbia , 1987. [66] Granot , Danie l , and Mehran Hojat i . "On Cost Al locat ion in Communicat ion Net-works." Submitted to Math, of O.R. [67] Granot , Daniel , and G . Huberman. " M i n i m u m Cost Spanning Tree Games." Math-ematical Programming, 21 (1981), 1-18. [68] Granot , Danie l , and G . Huberman. "On the Core and Nucleolus of M . C . S. T . Games." Mathematical Programming, 29 (1984), 323-347. [69] Grot te , J . H . Computation of and Observations on the Nucleolus and the Central Games. M . S c . Thesis, Cornell University, 1970. [70] Groves, T . , and J . Ledyard. "Opt imal Al locat ion of Publ ic Goods: A Solution to the Free Rider Problem." Econometrica, 45 (1977), 785-809. [71] Hamlen, Susan S., W i l l i a m A . Hamlen, Jr . "The Concept of Fairness in the Choice of Joint Cost Al loca t ion Methods." In Joint Cost Allocations, Norman , Oklahoma: Center for Economic and Management Research, 1981. [72] Hamlen, S. S., W . A . Hamlen, and J . T . Tschirhart . "The Use of Core Theory in Evaluat ing Joint Cost Al loca t ion Schemes." Accounting Review, 52 (July 1977), 616-627. [73] Hamlen, S. S., W . A . Hamlen, and J . T . Tschirhart . "The Use of the Generalized Shapley Al loca t ion in Joint Cost Al loca t ion ." Accounting Review, (Apr i l 1980), 269-287. 112 Hassin, R . and A . Tamir . "Efficient Algori thms for Optimizat ion and Selection on Series-Parallel Graphs." SIAM J. Alg. Disc. Meth., Vo l 7 (1986), 379-389. Heaney, J . P. "Efficiency/Equity Analysis of Environmental Problems: A Game Theoretic Perspective." In S. J . Brams, A . Schotter, and G . Schwodiauer (Eds.), Vienna : Physica-Verlag, 1979. P p . 352-369. Hojat i , Mehran , Richard Anstee, Daniel Granot , and Maurice Queyranne. "On Steiner Network Synthesis Problem: Simplifying the Equal-Requirement Case." Working Paper No. 1216, Faculty of Commerce and Business Administrat ion, University of Br i t i sh Columbia , March 1987. Hojat i , Mehran , Daniel Granot , and Maurice Queyranne. " A Two-Source, One-Sink Network Synthesis Problem." Working Paper, University of Br i t i sh Columbia , August 1985. I tami, H . , and R. S. Kap lan . " A n Act iv i ty Analysis Approach to Unit Costing wi th Mul t ip l e Interactive Products." Management Science, 26 (1980), 826-839. Jensen, D . L . " A Class of Mutua l ly Satisfactory Allocations." Accounting Review, 52 (October 1977), 842-856. K a l a i , E . , and E . Zemel. "Generalized Network Problems Yie ld ing 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." Math, of O.R., 7 (1982), 476-478. Kaneko, M . "The Central Assignment Game and the Assignment Markets." Jour-nal of Mathematical Economics, 10 (1982), 205-232. K a p l a n , R . , and G . Thompson. "Overhead Al locat ion V i a Mathematical Program-ming Models ." Accounting Review, (Apr i l 1971), 352-364. Khach ian , L . G . " A Polynomial Algor i thm for Linear Programming." Doklady Akad. Nauk USSR, 244(5) (1979), 1093-96. English Translation in Soviet Math. Doklady, 20, 191-94. Kopelowi tz , A . "Computat ion of the Kernels of Simple Games and the Nucleolus of n-Person Games.". Research Memorandum No. 31, Department of Mathematics, The Hebrew University, 1967. Lev, B . , and H . The i l . " A M a x i m u m Entropy Approach to the Choice of Asset Depreciation." Journal of Accounting Research, (Au tumn 1978), 286-293. Levine, M . E . "Landing Fees and the Airpor t Conjestion Problem." Journal of Law and Economics, 12 (1969), 79-108. L i t t l ech i ld , S. C . " A Game-Theoretic Approach to Publ ic Util i t ies Pr ic ing." West-ern Economic Journal, 7(2) (1970), 162-166. 113 Li t t l ech i ld , S. C . " A Simple Expression for the Nucleolus in a Special Case." Int. J. Game Theory, 3 (1974), 21-29. Li t t lech i ld , S. C . Elements of Telecommunications Economics. London: Institute of Electr ical Engineering, 1979. Li t t l ech i ld , S. C , and Guilermo Owen. " A Simplistic Expression for the Shapley Value in a Special Case." Management Science, 20 (1973), 370-2. Li t t lechi ld , S. C , and Guilermo Owen. " A Further Note on the Nucleolus of the 'A i rpor t Game'." Int. J. Game Theory, 5 (1976), 91-95. Li t t lechi ld , S. C , and G . F . Thompson. "Aircraft Landing Fees: A Game Theory Approach." Bell Journal of Economics, 8 (1977), 186-204. Loehman, E . , J . Orlando, J . Tschirhart , and A . Whins ton. "Cost Al loca t ion for Regional Waste-Water Treatment System." Water Resources Research, 15 (1979), 193-202. Loehman, E . , and A . Whins ton. " A New Theory of Pr ic ing and Decision-making for Publ ic Investment." The Bell Journal of Economics and Management Science, (Autumn 1971). Loehman, E . , and A . Whinston. " A n Axiomat ic Approach to Cost Al loca t ion for Publ ic Investment." Public Finance Quarterly, (Apr i l 1974). Loehman, E . , and A . Whinston. " A Generalized Cost Al loca t ion Scheme". In S. A . Y . L i n (Ed.) , Theory and Measurement of Economic Externalities. New York: Academic Press, 1976. P p . 87-101. Louderback, J . G . "Another Approach to Al locat ing Joint Costs: A Comment." Accounting Review, (July 1976), 683-685. Loughl in , J . C. "The Efficiency and Equi ty of Cost Al loca t ion Methods for M u l -tipurpose Water Projects." Water Resources Research, 13 (1977), 8-14. Lovasz, L . "Submodular Functions and Convexity." In A . Bachem, M . Grotschel, and B . Kor te (Eds.), Mathematical Programming: The State of Art, Ber l in : 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 Kernel and Bargaining Set for Convex Games." Int. J. Game Theory, 1 (1971), 73-93. Maschler , M . , B . Peleg, and L . S. Shapley. "Geometric Properties of the Kernel , Nucleolus, and Related Solution Concepts." Math, of O.R., 4 (1979), 303-338. M a u t z , R . k., and K . F . Skousen. "Common Cost Al loca t ion in Diversified Com-panies." Financial Executive, 15(7) (1968), 19-25. 114 [105] Megiddo, N imrod . "On the Monotonici ty of the Bargaining Set, the Kernel , and the Nucleolus of a Game." SIAM Journal on Applied Mathematics, 27 (1974), 355-358. [106] Megiddo, N . "Computational Complexi ty and the Game Theory Approach to Cost Al loca t ion for a Tree." Math, of O.R., 3 (1978), 189-196. [107] Megiddo, N . "Cost Al locat ion for Steiner Trees." Networks, 8 (1978), 1-6. [108] M i r m a n , L . J . , D . Samet, and Y . Tauman. " A n Axiomat ic Approach to the A l -location of a F ixed Cost Through Prices." Bell Journal of Economics, 14 (1983), 139-151. [109] M i r m a n , L . J . , and Y . Tauman. "Demand Compatible Equitable Cost Sharing Prices." Math, of O. R.,7 (1982), 40-56. [110] M i r m a n , L . J . , Y . Tauman, and Israel Zang. "On the Use of Game-Theoretic Concepts in Cost Al locat ion ." In H . P. Young (Ed.) , Cost Allocation: Methods, Principles, Applications, Amsterdam: Nor th Holland, 1985. Pp . 55-77. [ i l l ] Mi t che l l , B . M . "Opt imal Pr ic ing of Local Telephone Service." American Eco-nomic Review, 64(4) (1978), 517-537. [112] Moriar i ty , Shane. "Another Approach to Al loca t ing Joint Costs". Accounting Re-view, (October 1975), 791-795. [113] Okada, Norio. "Cost Al locat ion in Mult ipurpose Reservoir Development: The Japanese Experience." In H . P. Young (Ed.) , Cost Allocation: Methods, Principles, Applications, Amsterdam: Nor th Hol land, 1985. P p . 193-205. [114] O ' N e i l l , B . " A Problem of Rights Arb i t ra t ion from the Talmud." Math. Soc. Sci., 2 (1982), 345-371. [115] Owen, Gui l lermo. " A Note on the Shapley Value." Management Science, 14 (1968), 731-732. [116] Owen, Gui l lermo. "Mult i l inear Extensions of Games." Management Science, 18 (1972), 65-79. [117] Owen, Gui l lermo. "On the Core of Linear Product ion Games." Mathematical Pro-gramming, 9 (1975), 358-370. [118] Owen, Gui l lermo. Game Theory, 2nd Edi t ion . New York: Academic Press, 1982. [119] Parker, T . "Allocat ion of the Tennessee Valley Projects." Transactions of the American Society of Civil Engineers, 108 (1943), 174-187. [120] Qu inz i i , M . "Core and Competi t ive Equ i l ib r i a w i th Indivisibilities." International Journal of Game Theory, 13 (1984), 41-60. [121] Ransmeier, J . S. The Tennessee Valley Authority: A Case Study in the Economics of Multiple Purpose Stream Planning. The Vanderbilt University Press, 1942. 115 [122] Ratliff, D . M . , and A . S. Rosenthal. "Order-Picking in a Rectangular Warehouse: A Solvable Case of the Travelling Salesman Problem." Operations Research, 31 (1983), 507-521. [123] Rawls , J . "Justice as Fairness." Philosophical Review, 67 (1953). [124] Rohls , J . " A Theory of Interdependent Demand for a Communicat ion Service." Bell Journal of Economics and Management Science, 5(1) (1974), 16-37. [125] Rosenmuller, J . " L P Games wi th Sufficiently Many Players." International Jour-nal of Game Theory, 11 (1982), 124-149. [126] R o t h , A . E . , and R . E . Verrecchia. "The Shapley Value as Appl ied to Cost A l lo -cation: A Reinterpretation." Journal of Accounting Research, (1979). [127] Samet, Dov, and Ya i r Tauman. "The Determination of Margina l Prices Under a Set of Axioms." Econometrica, 50 (1982), 895-909. [128] Samet, Dov, Yair Tauman, and Israel Zang. " A n Appl ica t ion of the Aumann-Shapley Prices for Cost Al locat ion in Transportation Problems." Mathematics of Operations Research, 9(1) (February 1984), 25-42. [129] Samet, D . , and E . Zemel. "On the Core and Dual Set of Linear Programming Games." Mathematics of O. R. 9 (1984), 309-316. [130] Schmeidler, D . "The Nucleolus of a Characteristic Funct ion Game." SIAM J. Applied Math., 17 (1969), 1163-1170. [131] Shapley, L . S. " A Value for n-Person Games." Annals of Math. Study, 28 (1953), 307-317. [132] Shapley, L . S. "Cores of Convex Games." Int. J. Game Theory, 1 (1971), 11-26. [133] Shapley, L . S., and M . Shubik. "On Market games." Journal of Economic Theory, 1 (1969), 9-25. [134] Shapley, L . S., and M . Shubik. "The Assignment Game; I. The Core." Int. J. Game Theory, 1 (1972), 111-130. [135] Shapley, L . S., and M . Shubik. "Competit ive Outcomes in the Cores of Market Games." International Journal of Game Theory, 4 (1975), 229-237. [136] Sharkey, W . W . "Suggestions for a Game-Theoretic Approach to Publ ic Ut i l i ty Pr ic ing and Cost Al loca t ion ." Bell Journal of Economics, 13 (1982), 57-68. [137] Sharkey, W . W . The Theory of Natural Monopoly. London: Cambridge University Press, 1982. [138] Sharkey, W . W . "Economic and Game-Theoretic Issues Associated wi th Cost Al loca t ion in a Telecommunication Network." In H . P. Young (Ed.) , Cost Allo-cation: Methods, Principles, Applications, Amsterdam: Nor th Hol land , 1985. P p . 155-165. 116 [139] Shubik, M . "Incentives, Decentralized Control , The Assignment of Joint Costs and Internal Pr ic ing." Management Science, (Apr i l 1962). [140] Shubik, M . , and R . Weber. "Systems Defence Games: Colonel Blo t to Command and Control ." Naval Research Logistics Quarterly, 28 (1981). [141] Sobolev, A . I. "Characterization of the Principle of Opt imal i ty for Cooperative Games Through Functional Equations." In N . N . Vorobyev (Ed.), Mathematical Methods in Social Sciences, Vipusk 6, Vi ln ius , U S S R , 1975. P p . 92-151. [142] Spinetto, R . D . "Fairness in Cost Al loca t ion and Cooperative Games." Decision Sciences, 6(3) (July 1975), 482-491. [143] Squire, L . "Some Aspects of Opt imal Pr ic ing for Telecommunications." Bell Jour-nal of Economics and Management Science, 4(2) (1973), 515-525. [144] Steiglitz, K . , P. Weiner, and D . J . K le i tman . "The Design of M i n i m a l Cost Sur-vivable Networks." IEEE Trans. Cir. Theory, 16(4) (1969), 455-60. [145] StrafHn, P. , and J . P. Heaney. "Game Theory and the Tennessee Valley Authori ty." International Journal of Game Theory, 10 (1981), 35-43. [146] Suzuki , M . , and M . Nakayama. "The Cost Assignment of the Cooperative Water Resource Development: A Game Theoretical Approach." Management Science, 22 (1976), 1081-1086. [147] Tamir , A . "On the Core of Cost Al locat ion Games Defined on Locat ion Problems." Department of Statistics, Te l -Aviv University, Ju ly 1980. [148] Tamir , A . " A Class of Balanced Matrices Ar i s ing from Locat ion Problems." SIAM J. Alg. Disc. Meth., 4 (1983), 363-370. [149] Taylor, A . L . Telecommunications Demand: A Survey and Critique. Cambridge, M A . : Ballinger, 1980. [150] Thomas, A . L . "Useful Arbi t ra ry Allocations." Accounting Review, 45 (1971), 472-479. [151] Thompson, G . F . Airport Costs and Pricing. Unpublished P h . D . Dissertation, University of B i rmingham, England, 1971. [152] Ti js , S. H . , and T . S. H . Driessen. "Game Theory and Cost Al loca t ion Problems." Management Science, 32(8) (August 1986), 1015-1028. [153] Valdes, J . , R . E . Tarjan, and Eugene L . Lawler. "The Recognition of Series-Parallel Digraph." SIAM J. Computing, Vo l 11 (1982), 298-313. [154] Verrecchia, Robert E . " A Question of Equi ty : Use of the Shapley Value to Allocate State and Loca l Income and Franchise Taxes." In Joint Cost Allocations, Norman, Oklahoma: Center for Economic and Management Research, 1981. P p . 14-40. 117 [155] Von Neumann, John, and Oscar Morgenstern. Theory of Games and Economic Behaviour, Princeton: Princeton University Press, 1953. [156] Wa ld , J . A . , and C . J . Colbourn. "Steiner Trees, Par t ia l 2-Trees, and M i n i m u m IFI Neworks." Networks, 13 (1983), 159-167. [157] Wei], R . L . "Al loca t ing Joint Costs." American Economic Review, 58 (1968), 1342-1345. [158] W i n g , 0 . , and R . T . Chien . "Opt imal Synthesis of a Communicat ion Net." IRE Transactions on Circuit Theory, 8 (1961), 44-49. [159] Winter , Pawel. "Generalized Steiner Problem in Outerplanar Networks." BIT, 25 (1985), 485-496. [160] Young, H . Peyton. "Monotonic Solutions of Cooperative Games." International Journal of Game Theory, 14(2) (1985), 65-72. [161] Young, H . Peyton. "Producer Incentives in Cost Al locat ion." Econometrica, 53(4) (July 1985), 757-765. [162] Young, H . Peyton. "Methods and Principles of Cost Al locat ion ." In H . P. Young (Ed.) , Cost Allocation: Methods, Principles, Applications, Amsterdam: Nor th Hol land, 1985. P p . 3-29. [163] Young, H . P., N . Okada, and N . Hashimoto. "Cost Al locat ion in Water Resources Development." Water Resources Research, 18 (1982), 463-475. [164] Zajac, E . Fairness or Efficiency: An Introduction to Public Utility Pricing. C a m -bridge, M A . : Ball inger, 1978. [165] Zimmerman, J . L . "The Costs and Benefits of Cost Allocations." Accounting Re-view, (July 1979), 504-521.
- 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. |
DOI | 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:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0097387/manifest