COST/REVENUE ALLOCATION ON NETWORKSByRichard Weiping ZhuB. Sc. (Mathematics) Anhui Normal University, 1983M. Sc. (Mathematics) The University of British Columbia, 1990A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFDOCTOR OF PHILOSOPHYinTHE FACULTY OF GRADUATE STUDIESTHE DEPARTMENT OF MATHEMATICSWe accept this thesis as conformingto th required standardTHE UNIVERSITY OF BRITISH COLUMBIAApril 1995© Richard Weiping Zhu, 1995In presenting this thesis in partial fulfilment of the requirements for an advanceddegree at the University of British Columbia, I agree that the Library shall make itfreely available for reference and study. I further agree that permission for extensivecopying of this thesis for scholarly purposes may be granted by the head of mydepartment or by his or her representatives, It is understood that copying orpublication of this thesis for financial gain shall not be allowed without my writtenpermission.(Signature)_____________________Department of_________________The University of British ColumbiaVancouver, CanadaDate riA /9’ 9TDE-6 (2)88)AbstractThe thesis addresses some theoretical and computational issues arising from cost andrevenue allocation problems in networks. It employs techniques from mathematical programming, combinatorial optimization and graph theory, as well as methodology developed in game theory.In Chapter 2, two related cost allocation problems arising from circular networks,namely, traveling salesman cost allocation and construction cost allocation, are analysed. In Chapter 3, the problem of allocating construction and maintenance cost of atree enterprise, such as a telecommunication network or a cable-vision network, is studied. In both chapters, the main solution concepts (core, kernel, prekernel and nucleolus)developed in cooperative game theory are evaluated as possible cost allocation schemesfor the above allocation problems. Interesting geometric relationships among these solution concepts are derived and some characterizations of them are obtained. Thesecharacterizations suggest that the nucleolus is one of the most prominent choices as anallocation scheme for all the cost allocation problems considered in my thesis. Efficient,strongly polynomial algorithms are then developed for calculating the nucleolus of thesegames. Although the general approach in Chapters 2 and 3 is similar, the techniquesused in each chapter for developing the computational algorithms are different.In the second part of the thesis, three related theoretical issues are investigated. InChapter 4, a complete characterization of naturally submodular digraphs is derived interms of forbidden digraph configurations and graph decomposition. One motivationfor such a characterization is that naturally submodular digraphs have many desirableproperties which are useful for analysing cost/revenue allocation problems and some other11problems arising in logistics. In Chapter 5, a generic scheme for computing the nucleolusof a general cooperative game is developed. Finally, in Chapter 6 the possible use of thebargaining set as a cost allocation scheme is evaluated. In particular, it is shown thereinthat D.Granot’s bargaining set coincides with the core in simple network flow games, andit coincides with the kernel for simple, monotone, constant-sum games.111Table of ContentsAbstract iiList of Figures viAcknowledgements vii1 Introduction and Preliminaries 11.1 Introduction 11.1.1 Cost and Revenue Allocation 11.1.2 Methods of Cost and Revenue Allocation . 51.1.3 Contributions and Organization of the Thesis 91.2 Notation and Preliminaries 111.2.1 General Preliminaries 121.2.2 Graph Theory 121.2.3 Game Theory 161.2.4 Algorithms and Complexity 222 Cost Allocation on Circular Networks 252.1 Circular Networks and Associated Games 262.2 The Core, the Kernel and the Prekernel of a CN Game 282.3 The Nucleolus of a CN Game 352.4 An Algorithm for Computing the Nucleolus of a CN Game 412.5 Concluding Remarks and Extensions 58iv3 Cost Allocation on Standard Tree Enterprises 603.1 The tree enterprise and its games 613.2 The eqnations for the kernel/nucleolus of a standard tree 653.3 The proto-nucleolus and the strnctnre of the kernel/nucleolus of the standard tree game 733.4 Examples 783.5 An algorithm for computing the kernel/nucleolus of a standard tree game 803.6 Shortcuts in Algorithm 3.5.15: The case of a chain enterprise 894 Naturally Submodular Digraphs and Their Characterizations 924.1 Notation and Preliminaries 944.2 Characterizations of Naturally Submodular Digraphs 954.3 Characterizations of Naturally Submodular Bi-digraphs 1095 The Characterization Set for the Nucleolus 1135.1 Sequential LP Processes 1155.2 Characterization Sets for the Nucleolus . . 1215.3 Saturated Coalitions for Monotone Games 1275.4 Polynomial Computability of the Nucleolus 1315.5 Examples 1356 Allocation through the Reactive Bargaining Set 1396.1 The Reactive Bargaining Set . 1406.2 Simple Network Games . 1426.3 Constant-sum, Monotone Simple Games . . 146Bibliography 149vList of Figures2.1 A CN game of type II that is not convex 303.1 Computing the proto-nucleolus 743.2 Good arcs may turn out bad 783.3 Condensations that fail 794.1 The Digraph F1 and F2 964.2 The Layout of C and P 974.3 The Layout of C and C1 994.4 The Layout of C and T 1014.5 The Layout of P1 1024.6 F1 and F2 are not naturally submodular 1094.7 A bi-digraph which is not naturally submodular 110viAcknowledgementsIt was not until I began writing the acknowledgements that I realized to how manygood people I became greatly indebted during the long, enjoyable, sometimes frustrating,process of writing this thesis. They have been such an important, indispensable part ofmy life that I have sometimes taken their help, their inspiration and their encouragementfor granted.I would like to thank Danny and Frieda, my research supervisors, for their constantguidance and inspiration. Their comments and my many discussions with them wereessential for the completion of this thesis. Further, it was through reading the numerouscorrections that they patiently made on the dozens of earlier drafts of the thesis that Ilearned the basics of academic writing.I want to thank Richard Anstee for the encouragement and all the help he offeredduring last five years. I also feel indebted to Joel Friedman for his kindly agreeing to bea member of my thesis supervisory committee.I am grateful to many friends and fellow graduate students in the Department ofMathematics. They helped me see clearly, and got me involved in many exciting mathematical and non-mathematical discussions, which supported my spirit and reinforced myinterest in mathematics.Finally, I want to express my gratitude and love to many friends who helped balancemy life as a doctoral student. The parties, sport and card games, hiking trips, andmany other events that I enjoyed with them made my student life more enjoyable andmemorable.vuChapter 1Introduction and Preliminaries1.1 Introduction1.1.1 Cost and Revenue AllocationIn recent years, interest in the theory and practice of allocating joint and common costsand revenues has been extensive and has led to a substantial literature on the subject.The problem of cost and revenue allocation is widespread, both in public enterprisesas well as within private corporations. It arises in cost accounting and in the pricingpolicies of public utilities providing telephone and cable TV services, electric power, andtransportation. It occurs in cost-benefit analyses of public projects designed to servedifferent constituencies, such as a multipurpose reservoir, or a public medical library. Itis implicit in the determination of access fees or user charges for common facilities suchas airport runways. It even crops up in such routine matters as how to allocate travelexpenses among the sponsors of a business trip.There are two fundamental reasons for studying cost and revenue allocations. One isrelated to economies of scale. In many situations, being able to allocate common cost orrevenue in a fair manner is a critical necessity for achieving system efficiency. The otherreason stems from the fact that cost and revenue allocations arise naturally in manymodern optimization models. Indeed, traditionally, it is assumed that the resourcesused in an optimization model are under the control of one individual or a group ofindividuals having identical interests. But when the resources are owned by individuals1Chapter 1. Introduction and Preliminaries 2having conflicting objectives, these individuals will not support the implementation of asolution which is optimal for the entire group unless their expectation for a fair allocationof the joint cost/revenue are met.Let us look at some cost/revenue allocation examples.Example 1.1 The TVA and Multipurpose reservoirs. The Tennessee Valley Authority (TVA) was formed in the early 1930’s and authorized to undertake large scalemultiple purpose water resource development projects in the Tennessee River basin. Themajor purpose to be served were improved navigation, flood control, and provision ofelectric power, with subsidiary benefits to irrigation, national defence and the production of fertilizers. Depending on which purposes are to be included, the cost associatedwith the project will be different. However, such a cost function typically exhibits decreasing marginal costs. The TVA’s problem was how to apportion the costs among thedifferent purposes. This allocation problem was extremely important and controversial,and could not be done arbitrarily, since, for example, “the amount of cost allocated tothe purpose of providing electrical power would affect the rate at which the TVA powerwould be sold, and hence the extent to which it would compete with privately producedpower.” (Ransmaier [1942])The TVA engineers and economists devoted considerable time and thought to a number of cost allocation schemes in the late 1930’s. Their work is surveyed in Ransmeier[1942] and Parker [1943]. Other related studies can be found in Straffin and Heaney[1981] and Young, Okada and Hashimoto [1982].Example 1.2 Cable TV Microwave Cost Sharing. This example is one of publicutility pricing, and is based on actual cost data collected by the Nova Scotia ProvincialGovernment [1976]. In the Maritimes (of Canada), prior to August 1973 there were 14licensed CATV systems serving 26 communities in Nova Scotia and New Brunswick. TheCRTC decision, issued in August 1973, licensed 13 new or extended systems to serve 34Chapter 1. Introduction and Preliminaries 3additional communities. To further extend the cable television service to other Maritimecommunities, a committee, called the Consultative Committee on Communications, wasformed and authorized to investigate the feasibility, both technical and financial, of suchan extension. The Committee concluded in May 1974 that a common network, whichextends coverage to all communities in the three Maritime provinces with populations ofover 1,000 people plus some smaller communities which are immediately adjacent to thelarger communities, is technically and financially feasible. Then, the next problem wasto decide how to fairly share the extension and operational costs among all communities.Such costs are shared through subscription fees. The key issue here was how to price theCATV services in such a way that there would be no, or only limited, cross subsidizationwithin the Maritime provinces.Other related problems include the cost allocation and price policy problems intelecommunication or telephone systems studied by Mitchell [1979], Johnson [1982],Sharkey [1983], Curien [1983] and Granot and Hojati [1990]; the general public utility pricing problems investigated by Littlechild [1970], Zajac [1978] and Sharkey [1982];the airport landing fees considered by Littlechild and Thompson [1977] and Littlechildand Owen [1977]; minimum cost spanning tree problems examined by Bird [1976], Clausand Granot [1976], Megiddo [1978], Granot and Huberman [1981,1982,1984] and Granot,Maschler, Owen and Zhu [1994]; and the spanning network problem proposed by Granotand Maschler [1994a].Example 1.3 Travel Expenses Sharing. A Professor from the University of BritishColumbia is invited on a lecture tour originating in Vancouver, with stops in Edmonton,Toronto, Montreal and Windsor. The total fare is $800. The problem is how to allocatethe fare “fairly” among the four sponsors of the trip. The problem becomes even morecomplicated if the professor gives two lectures in Edmonton, three lectures in Toronto andone lecture each in Montreal and Windsor. Indeed, in the latter case a modeling problemChapter 1. Introduction and Preliminaries 4arises: Are the different lectures the primary entities to which costs are assigned? Oris it the sponsors? Similar problems were studied by Fishburn and Pollak [1983], Tamir[1989], Derks and Kuipers [1992], Potters, Curiel and Tijs [1992] and Granot, Granotand Zhu [1994a].Example 1.4 Revenue Allocation in the Linear Production Model. Owen [1975]considered the following economic linear production model where individuals, or organizations, pool resources to produce finished goods which can be sold at a given market price.Each of n individuals is in possession of a resource vector b = (b,. . . , b)(i = 1, 2,... , n).The resources themselves are of no value, i.e., there is no primary demand for them. Thereis, however, a secondary demand for these resources: they can be used to produce p typesof goods which can be sold at given market prices c = (ci,.. . , cj. It is assumed thatthe production is linear with production matrix APX. Therefore, for any subset S C N(N = {1, 2,.. . , n}), this coalition of individuals have the joint resource vectorSEN. (1.1)iESIf they wish to maximize their revenues, they will therefore look for a production vectorx which solvesv(S) = max{cx: Ax b(s), x O}. (1.2)The revenue function v defined by (1.2) is superadditive, and thus system efficiency isreached when all individuals pool their resources together. However, a critical necessityfor reaching such system efficiency is allocating the common revenues fairly among allindividuals.Some related models are assignment problems studied by Shapley and Shubik [1972],network flow problems investigated by Kalai and Zemel [1982a,b], Dubey and Shapley[1984] and Granot and Granot [1992], network synthesis problems considered by GranotChapter 1. Introduction and Preliminaries 5and Hojati [1990] and Tamir [1991] and the generalized linear production model, whichproperly generalizes Owen’s model, suggested by Granot [1986].1.1.2 Methods of Cost and Revenue AllocationAs demonstrated in the examples presented in the last subsection, the focus of the analysis of cost/revenue allocation problems is to devise criteria and methods such that thecommon or joint cost/revenue is allocated in an equitable, reasonable and stable manner.Thus, cost/revenue allocation is ultimately concerned with fairness and stability. Themethods and principles of cost/revenue allocation that are likely to find acceptance mustsomehow be grounded in primitive, common-sense ideas of fairness and equity.Broadly speaking, there are two main approaches which can be used to achieve fair andstable allocations. One is the normative approach, in which all of the objective data are athand and the problem is to devise a formula for making an allocation based on the data.The other one is the so-called procedural approach, where the objective of an allocator isto design a procedure, e.g., an arbitration rule, an auction, or a competitive market, thatseems fair and impartial a priori, and by its functioning produces an allocation. Despitethe fact that each approach has its own merits and both are widely applied in real worldallocation problems, the normative approach to cost/revenue allocation problems seemsto have received more attention in the literature than the procedural approach. In thisthesis, all methods investigated fall into the realm of the normative approach.Important features of the normative approach to the cost (similarly, revenue) allocations can be captured in the following framework. Let N = {1, 2,. . . , n} represents a setof potential customers of a public service or public facility. Each customer will either beserved at some targeted level or not served at all. It is assumed that the cost data aresummarized by a joint or common cost function c(S), which is defined for all subsetsS ç N of the potential customers. c(S) represents the cost of serving the customers inChapter 1. Introduction and Preliminaries 6S by the most efficient means (c(O) = 0). The problem is to determine how to share thecost of the public service fairly, based on the costs of providing it. A (normative) costallocation method is a set function /‘ defined for all N and all joint cost functions c onN such thatb(c) C {(x1,. . . ,x,) e RN: x c(N)},iENwhere x is the charge assessed to customer i.There are many allocation methods that fit into this framework. Among them isa school of allocation methods whose origins can be traced back to cooperaticve gametheory.Allocation Methods Derived from Game TheoryA cooperative game in characteristic function form is a pair (N; v), where N is the setof players and v is the characteristic function defined on 2N with v(ø) = 0. A substantialpart of the literature in cooperative game theory addresses the following question: Howwould or should the players share the proceeds, given that various coalitions have beenformed. A solution concept in game theory specifies, for each game (N; v), a set of payoffvectors. Different criteria give rise to different solution concepts, and some of the well-known ones are core, Shapley value, nucleolus, kernel, prekernel, bargaining set and vonNeumann-Morgenstern stable sets. Section §1.2.3 below provides a brief review of thatpart of cooperative game theory which is related to this thesis.The setting of the normative approach to cost (similarly revenue) allocation naturally defines a cooperative game, with the set of potential customers N as the playerset and the joint cost function c as the characteristic function. Therefore, the varioussolution concepts, introduced in cooperative game theory, can be evaluated as possiblecost allocation schemes. Here are some examples.The Core: The core consists of all allocation vectors that can not be improvedChapter 1. Introduction and Preliminaries 7upon by any customer or any group of customers by deviating from the group of allcustomers and acting alone. Therefore, the core vectors satisfy the individual and thegroup rationality, namely, they can survive a process of competition in which every oneseeks to join a coalition offering the highest return. It is worth mentioning that the ideaof the core was foreshadowed in the thought of the engineers and economists of the TVAin their search for allocation methods of water resources development before the firstgame theory book by von Neumann and Morgenstern [1944], and almost a decade beforeits importance became manifest in game theory.Shapley Value: Imagine that the participants in a cost allocation problem are rational agents who view the outcome as being subject to uncertainty. They might reasonabout their prospect as follows. Everyone is thought of as ‘signing up’ in some randomorder. At each stage of the sign-up, each participant must pay the incremental cost, i.e.,the marginal cost, of being included at the moment of signing. Then, the Shapley valueis the allocation method which assigns every participant the average marginal cost underthe assumption that each of the n! possible ordering is equally possible. Shapley value isone of the most widely applied allocation methods in cost/revenue allocation in practice.The Nucleolus: Suppose the satisfactory level of a coalition S (S c N) to a proposedcost allocation vector x is measured by the value e(S, x) c(S) — x(S). The smallere(S, x) is, the less satisfactory coalition S is with the vector x. Assume that the loudnessof a coalition’s complaint against an allocation vector is proportional to its dissatisfactorylevel. Then, the nucleolus is the allocation vector resulting from the following process.The cost allocator chooses allocation vectors which minimize the loudest complaint; subject to achieving this, he chooses vectors which minimize the second loudest complaint;and so on. Like Shapley value, the nucleolus always exists and consists of a single vectorfor all cooperative games. Moreover, the nucleolus has the additional property that it iscontained in the core if the core is nonempty.Chapter 1. Introduction and Preliminaries 8Other Allocation MethodsApart from allocation methods which are derived from solution concepts of cooperative game theory, there are myriads of other allocation methods which have beenproposed and practised. Some examples include the separable costs remaining benefitsmethod (James and Lee [1971]), Stanley’s method (Nova Scotia Provincial Government[1976]), Moriarity’s method and its modifications (Moriarity [1975,1976] and Louderback[1976]), and Ramsey Pricing (Ramsey [1927]).The Separable Costs Remaining Benefits (SORB) Method: This method allocatesthe costs according to the following simple formula= +r [c(N) —ZjENXi jENwhere, for each i E N, s = c(N)—c(N\i) is called the separable cost to i and r = c(i)—sis called the remaining benefit to i. This method is the principal textbook methodused by civil engineers to allocate the costs of multipurpose reservoirs. In practice,an earlier version of this method, called the alternative justifiable expenditure method,was used by the TVA to allocate their water resource development costs. Accordingto Ransmeier [1942], the TVA used the alternative justifiable expenditure method tocalculate an allocation, and then merely “rounded off” the resulting allocation in light oftheir judgement. A variant of the SCRB method, called the proportional willingness-to-pay method, is used by Fishburn and Pollak [1983] to allocate the cost of a business tripamong its sponsors.Ramsey Pricing: This method has been discussed extensively in the economics literature (see Manne [1952] and Boiteux [1971]). The essential property of this method isthat the percentage mark-up over marginal cost is greater the more inelastic the demandfor the good is.As it is quite apparent, there is no shortage of plausible methods for allocating jointChapter 1. Introduction and Preliminaries 9or common cost/revenue. Thus, the essence of the allocation problems lies not in definingmethods, but in formulating principles and standards that should govern allocations, andthen determining which methods satisfy them.1.1.3 Contributions and Organization of the ThesisThis thesis addresses some theoretical and computational issues arising from cost andrevenue allocation problems. Techniques from linear programming, combinatorial optimization and graph theory are used to develop efficient computational schemes forcalculating various solution concepts and to obtain related characterization results.In Chapter 2, the problem of allocating the traveling cost of a server among customerslocated in vertices of a circular network is investigated. The characteristic function ofthe cooperative game associated with this allocation problem is shown to be submodular,and thus the associated game, called a circular network game, is convex. For allocationproblems which give rise to convex games, the nucleolus is a prominent choice for acost allocation scheme. Indeed, the nucleolus of a convex game is contained in the core,and it coincides with both the kernel and the pre-kernel. By identifying and exploitingsome special structure of a circular network game, an 0(n3) algorithm for computingits nucleolus is developed, where n is the number of vertices in the circular network. Arelated cost allocation problem in circular networks, in which the cost of constructing thenetwork is allocated among the users, is also studied. Even though the associated gameis no longer convex, similar structural and computational results have been obtained forthis class of games.In Chapter 3, I consider the cost allocation problem arising from the construction andmaintenance of a tree enterprise, such as a cable-vision network. The game associatedwith this allocation problem, called a standard tree game, is again shown to be convex.By employing the reduced game property, that is satisfied by the nucleolus of this game, aChapter 1. Introduction and Preliminaries 10characterization of the nncleolus of a standard tree game by a set of equations is obtained.These equations are then used to construct an efficient (0(n2)) algorithm for computingthe nucleolus.As was demonstrated in Chapters 2 and 3, convex games have some desirable properties, which can be sometimes exploited in choosing and computing an appropriate costallocation scheme. This motivates the desire to characterize directed graphs which giverise to convex cost allocation games. (Another motivation of this characterization comesfrom vehicle routing problems and some problems arising from inventory/productionsystems.) A directed graph is said to be naturally submodular if the Steiner travelingsalesman tour, viewed as a function defined over subsets of the vertex set, is submodularregardless of the choice of the home vertex and of the arc weights. In Chapter 4, thefamily of naturally submodular digraphs and bi-digraphs is characterized. One of thecharacterizations for digraphs is in terms of forbidden digraph configurations, and theother one is in terms of graph decomposition. The latter one asserts that a digraph isnaturally submodular if and only if it is a 1-sum of outerplanar graphs in which the orientation of arcs therein satisfy some ‘harmonious’ property. Bi-digraphs are digraphs withsome symmetry restriction on arcs thereof. The characterizations of naturally submodnlar bi-digraphs developed are in terms of 1-sums of bi-directed cycles and bi-directedarcs, in terms of forbidden bi-digraph condigurations and in terms of the so called fixedorder property. The characterizations of naturally submodular digraphs and bi-digraphsobtained are also useful for a variety of vehicle routing and production/inventory problems.Motivated by the success in developing an 0(n3) algorithm for computing the nucleolus of a circular network game, a generic scheme for seeking an efficient algorithmfor computing the nucleolus of a general cooperative game is developed in Chapter 5.The generic scheme is based on the notion of a characterization set which represents theChapter 1. Introduction and Preliminaries 11‘minimum’ relevant information needed to characterize the nucleolus. Some sufficientconditions for a collection of subsets to be a characterization set of the nucleolus areprovided, and the usefulness of this notion for several classes of games is also demonstrated. It is further shown that if the nucleolus of a game has a characterization setof size polynomially bounded in the total number of players, then the nucleolus of thisgame can be computed in strongly polynomial time.In the final chapter, cost/revenue allocations through bargaining sets, especially, thereactive bargaining set, are considered. Two main results are developed there. First, it isshown that, for the class of simple network games, the reactive bargaining set coincideswith the core. Then, it is proved that, for a constant-sum, monotone simple game, thereactive bargaining set coincides with the kernel. The class of constant-sum weightedmajority games constitutes a subclass of the constant-sum, monotone simple games.Thus, the coincidence of the reactive bargaining set and the kernel is valid for constant-sum weighted majority games as well. Combining this with the computational resultsfor the kernel developed in Aumann, Peleg and Rabinowitz [1965], Aumann, Rabinowitzand Schmeidler [1966] and Kopelowitz [1967], we realize that an explicit description ofthe reactive bargaining set for all constant-sum weighted majority games with up to 7players is available in the literature.1.2 Notation and PreliminariesIn this section, we provide an overview of the background knowledge, including notation and definitions, used throughout this thesis. We will discuss general preliminaries(1.2.1), preliminaries on graph theory (1.2.2), on game theory (1.2.3) and on complexity theory (1.2.4). Other definitions, especially those original to this thesis, will beintroduced as required.Chapter 1. Introduction and Preliminaries 121.2.1 General PreliminariesSome general notation and terminology is as follows. The symbols Z, Q and R denotethe sets of integers, rationals and real numbers, respectively. Z, Q+ and R+ are therestrictions of these sets to the nonnegatives. If x is a real number, then [xj and Exldenote the lower integer part and the upper integer part, respectively, of x. For realnumbers x and y and for an integer n we denote x y (mod n) if and only if x—y isan integer multiple of n.We write f(x) = O(g(x)) for real-valued functions f and g, if there exists a constantC such that f(x) Cg(x) for all x in the domain.The cardinal number of a set S is denoted by ISI• We also allow set notation (braces)to be omitted when referring to singleton sets and in cases when such an omission willnot cause any confusion. For example, we will write N\i and c(1, 2) instead of N\{i}and c({1, 2}), respectively.‘Left-hand side’ and ‘right-hand side’ are sometimes abbreviated to LHS and RHS.1.2.2 Graph TheoryIn this subsection, we give a brief review of some elementary concepts and results in graphtheory which are needed in the sequel. The reader not familiar with general graph theoryconcepts is referred to, for example, Bondy and Murty [1976]. For proofs of elementaryresults quoted in this subsection, we also refer readers to Bondy and Murty [1976].Undirected GraphsAn (undirected) graph is a pair G=(V, E), where V, the vertex set of G, is a finite set,and E, the edge set of G, is a family of unordered pairs of elements of V. The elementsof V are called vertices or nodes of G, and the elements of E are called edges of G. If thevertex set and edge set of a graph G are not explicitly given, we write V(G) and E(G)Chapter 1. Introduction and Preliminaries 13for the vertex set and the edge set of G, respectively.The vertices v and vj are adjacent if there is an edge e connecting them. In this case,the edge e is said to be incident to the vertices v and v, and conversely. The number ofedges incident with a vertex v in a graph G is referred to as the degree or valency of v,usually denoted by dG(v).An edge occurring more than once in E is called a multiple edge. An edge connectingthe same vertex is called a loop. A graph is said to be simple if it does not have anymultiple edges and ioops.A simple graph is complete if its edge set is the set of all pairs of vertices. Thecomplete graph with n vertices is denoted by Ic. An empty graph, on the other hand,is one with no edges. A bipartite graph is one whose vertex set can be partitioned intotwo subsets X and Y, so that each edge has one end in X and one end in Y. A completebipartite graph is a simple bipartite graph with partition (X, Y) in which each vertex ofX is connected to each vertex of Y; if X = n and Y = m, such a graph is denoted byKn,m.A graph G’ = (V’,E’) is a subgraph of G = (V,B), denoted G’ c G, if V’ c V andç E. When G’ C but C’ G, C’ is said to be a proper subgraph of C, denotedC’ C C. A spanning subgraph of G is a subgraph G’ with V’ = V. Suppose V’ is anonempty subset of V. The subgraph of G whose vertex set is V’ and whose edge set isthe set of edges of G that have both ends in V’ is called the subgraph of C induced by V’and is denoted by G[V’]; we say that G[V’] is a vertex-induced subgraph of G. Similarly,the edge-induced subgraph of C by a nonempty subset E’ of E, denoted G[E’], is thesubgraph of G whose vertex set is the set of vertices which are incident to edges in E’and whose edge set is E’.A walk in G from a vertex v0 to a vertex Vk, or a (vo, vk)-walk, is defined to be afinite sequence W =v0e12. .. ekvk of alternating vertices and edges, such that forChapter 1. Introduction and Preliminaries 141 i k, the ends of e are vs_i and v. The vertices v0 and vk are called the origin andterminus of W, respectively, and all other vertices are its internal vertices. The lengthor the graphic length of W is k. If the edges e1,e2,. . . , e of a walk W are distinct, W iscalled a trail. If, in addition, the vertices vo, v1,v2,. . . , vj are distinct, W is called a path.A family of paths in G is said to be internally-disjoint if no vertex of G is an internalvertex of more than one path in the family. A walk W is closed if its origin and terminusare the same. If, further, the vertices v1,v2,. . . , vj, are distinct and k > 3, W is called acycle or a circuit.A graph is connected if each two vertices of the graph are connected by a path.Connectedness by paths induces an equivalence relation on the vertices. Its classes arecalled the (connected) components of the graph. A graph is k-connected if every pair ofvertices of the graph is connected by at least k internally-disjoint paths.A forest is a graph having no cycles, and a tree is a connected forest.Proposition 1.2.1 The following are equivalent:1. G is a tree;2. G contains no cycles and E = — 1;3. G is connected and E = — 1;4. Any two vertices of G are connected by exactly one simple path.A spanning forest of a graph G is a spanning subgraph of G which is a forest and hasas many edges as possible. This implies that a spanning forest of G has the same numberof components as G does. A graph G has a spanning tree if and only if C is connected.A vertex v of G is a cut vertex if removing v and all edges incident to it from Gwill increase the number of components by at least one. A 2-connected graph is called ablock. The following result is a special case of the well-known Menger’s Theorem.Chapter 1. Introduction and Preliminaries 15Proposition 1.2.2 A graph G with VI 3 is a block if and only if for any pair ofdistinct vertices in G there always exist at least two vertex disjoint paths connectingthem.A block of a graph C is a subgraph of G that is a block and is maximal with respectto this property. Every graph is the union of its blocks.Let G and H be two graphs with V(G) and V(H) their vertex sets, respectively. A1-sum of G and H is defined to be the graph derived from G and H by coalescing onevertex in C with another vertex in H. The newly formed vertex is called the 1 -sum vertex,or the link vertex. Clearly, with different choices of vertices being identified, different 1-sums of G and H may be produced. Inductively, we may define 1-sums of more than twographs. It is not hard to see that every connected graph is a 1-sum of its blocks.An edge e is said to be subdivided when it is deleted and replaced by a path of lengthtwo connecting its ends. A subdivision of a graph C is a graph that can be obtained fromC by a sequence of edge subdivisions.A graph is said to be planar if it can be drawn in the plane so that its edges intersectonly at their ends. Such a drawing of a planar graph G is called a planar embedding ofG. A planar graph G is outerplanar if it has a planar embedding in which all its verticeslie on the boundary of the outer region.Directed GraphsA directed graph or a digraph is a pair D=(V, A), where V, the vertex set, is a finiteset, and A, the arc set, is a set of ordered pairs of V. The elements of V are called thevertices or nodes of D, and the elements of A are called the arcs of D. The vertices vand w are called the tail and the head of the arc a = (v, w), respectively. We write V(D)and A(D) for the vertex set and the arc set of a digraph D if the vertex set and the arcset are not explicitly given. In a digraph D, the indegree of a vertex v is the number ofChapter 1. Introduction and Preliminaries 16arcs of D that have v as their head vertex. Similarly, the outdegree of v is the number ofarcs of D that have v as their tail vertex.Each directed graph gives rise to an underlying undirected graph, in which the orientation of the arcs is ignored. Sometimes, when there is no fear of misunderstanding, weuse ‘undirected’ terminology for directed graphs.The concepts of multiple arcs and loop for directed graphs can be defined in ananalogous way to those for undirected graphs. A directed walk from v0 to vk is a sequenceW =v0a12. .. akvk, such that for 1 k, the tail of a is vj1 and the head of ais v. The concepts of directed trail, directed path, and directed cycle for directed graphsare defined by analogy to the undirected graphs.A digraph D = (V, A) is said to be strongly connected if there exists a directed pathfrom i to j for each pair of vertices i and j in D.1.2.3 Game TheoryA cooperative game in characteristic function form is a pair I’ = (N; v), where N ={ 1, 2,.. . , n} is the set of players and v is the characteristic function which is a real-valued function defined on Subsets of N are called coalitions. One interpretationof v(S) is that it describes the best outcome that the coalition S can achieve, given themost unfavorable actions on the part of the complementary coalition N \ S. We assumethat v(O) = 0.As a notational convention, for any vector x=(x1,x2,. . .,x) define the additivefunction x(S) iES x for every S ç N.A payoff vector of a game I’ is a vector x indexed by the player set N. A pre-imputationor an efficient payoff vector of I’ is a payoff vector x satisfying x(N) = v(N). The set ofall pre-imputations of I’ is denoted by X*(Il). An imputation of P is a pre-imputationwhich also satisfies x v(i) for all i€N. The last condition is known as the individualChapter 1. Introduction and Preliminaries 17rationality. The set of all imputations for F is denoted by X(F).The core, C(F), of F is defined to be the set of pre-imputations that cannot beimproved upon by any subset of players which deviates from the grand coalition and actsalone. Formally, we have the following:C(F) {x X*(F): x(S) > v(S) for all S é 2N} (1.3)Geometrically, the core is a compact convex polyhedron bounded by no more than 21N1 —2hyperplanes of the form: x(S) v(S), S C N. A necessary and sufficient condition forthe nonemptiness of the core is due to Bondareva [1961] and Shapley [1967].Proposition 1.2.3 The core of a game F is nonempty if and only ifv(N) asv(S) (1.4)SEBfor every collection B for whichas = 1 for everyi E N. (1.5)SEB:iESA collection B which satisfies condition (1.5) is said to be a balanced collection. Agame F for which the characteristic function satisfies (1.4) is said to be a balanced game.A game is totally balanced if for every subset T the subgame (T; v), derived from F byrestricting v to 2T, is balanced.Proposition 1.2.3 is equivalent to the following proposition, which is due to Charnesand Kortanek [1967].Proposition 1.2.4 The core of the game F is not empty if and only ifmin{x(N): x(S) > v(S), S N} = v(N).Chapter 1. Introduction and Preliminaries 18Any allocation to the players according to a payoff vector in the core would removethe desire of any coalition S of players to secede from the grand coalition N. As longas the characteristic function v is superadditive, this is a desirable property, since thefragmentation of N typically implies an inefficient outcome in the game.An alternative approach to the solution theory postulates that the members of thegrand coalition have agreed to cooperate, but that they nevertheless will bargain amongthemselves over the distribution of the total payoff. Several solution concepts fall intothis paradigm. Among them are the bargaining sets proposed by Aumann and Maschler[1964] and Davis and Maschler [1967], the kernel proposed by Davis and Maschler [1965],and the prekernel proposed by Maschler, Peleg and Shapley [1972].All solution concepts can be defined for arbitrary coalition structures, consisting ofpartitions of the grand coalition. In this thesis, for simplicity, we will be concerned onlywith the grand coalition itself.For a game I’ = (N, v) and a payoff vector x, define the excess of coalition S withrespect to x as v(S) — x(S), which is denoted by e(S, x), or ev(S, x) if one wants toemphasize the characteristic function v. For i,j E N, the maximum excess, or thesurplus of i against j with respect to x iss(x) max{e(S,x): i E g s,s 2N} (1.6)The kernel, K(F), and pre-kernel, PK(1’), of I’ (for the grand coalition) are, respectively, given by,K(F) {x E X(F): either s(x) sjj(x) or x = c({j}),V i,j E N,i j}, (1.7)andPK(F) {x e X*(F): s(x) = s(x),Vi,j E N,i j}. (1.8)Maschler and Peleg [1966] proved that the kernel exists for every game whose imputation set is nonempty, and that its intersection with the core is nonempty whenever theChapter 1. Introduction and Preliminaries 19core is nonempty. The prekernel, which exists for all games, was first introduced as anauxiliary solution concept for the study of the kernel by Maschler, Peleg and Shapley[1972]. A detailed analysis of the structure of the prekernel and its geometrical characterization can be found in Maschler, Peleg and Shapley [1972],[1979], respectively.There are several versions of bargaining sets in the literature. Here, we only introducethe bargaining set proposed by Davis and Maschler [1967].Let x be a payoff vector of a game F. An objection of a player i against a playerj, with respect to x, is a pair (y, 5), where S is a coalition containing player i and notcontaining j and y is a real vector indexed by 5, satisfyingy(S) v(S), yk > Xk, k E 5. (1.9)A counter objection to this objection (from j to i) is a pair (z, Q), where Q is a coalitioncontaining player j and not containing i and z is a vector indexed by Q, satisfyingz(Q) = v(Q), zk Yk for k E Q fl S and zk xk for k e S \ Q. An imputation x issaid to belong to the Davis-Maschler bargaining set (for the grand coalition), denotedM(F), of the game F if for any objection of one player against another with respect tox there exists a counter objection.Davis-Maschler bargaining set contains the core, if the core is not empty, and thekernel (Davis and Maschler [1965]). Therefore, it is not empty as long as the imputationset is not empty.A possible disadvantage of the solution concepts introduced so far is that they mayrecommend of a large number of payoff vectors, so that additional criteria may be necessary in order to choose a unique allocation. Two single valued solutions that have beenwidely studied in the literature are Shapley value and the nucleolus. In order to defineShapley value, consider the set of permutations of the player set N. For a particularpermutation E , let P(t) = {ja4.(j) <w(i)} be the set of players which precede i inChapter 1. Introduction and Preliminaries 20w, where P(w) = 0 if player i is the first in the ordering of .‘. Define the marginal vectorby m(w) = v(P() U {i}) — v(P:(w)). Then, Shapley value, (v), of a game (N, v), isgiven by> (1/n!)m). (1.10)For each permutation w the marginal vector m() assigns to player i preciselythe incremental value that player brings into the game assuming players arrive accordingto w. Shapley value may therefore be thought of as the average contribution of a playerto the game under the assumption that each of the n! permutations is equally likely.Clearly, it exists and is single valued for all games. Shapley value may also be definedas the unique value function on the set of all possible solutions which satisfies a set ofreasonable a priori axioms.To define the nucleolus of a game F = (N; v), define, for each x E RN, the 2INLdimensional vector q(x; F) whose components are the values of the excesses e(S, x), forS E 2N, arranged in a decreasing order. Let denote the “lexicographically smallerthan” relationship between vectors of the same dimension. For X0 C R’, the nucleolus,N(f,X0) off with respect to X0 is given byN(F,X0) {x e X0: (x;f) <_j q(y;f),Vy € Xo}. (1.11)When X0 = X*(f), N(f,X0 is called the prenucleolus of F and is denoted by PN(f),while when X0 = X(F), N(F,X0 is called the nucleolus of I’ and is denoted by N(F).The definition of the nucleolus is due to Schmeidler [1969], who also demonstrated thatN(F) is a singleton set and is contained in K(F). Note also that if the core is nonempty,then there is an allocation x such that e(S, x) < 0 for every 5 E It follows that thenucleolus is necessarily contained in the core if the core is nonempty.A game F = (N; v) is superadditive if its characteristic function v is superadditive.That is v(S) + v(T) < v(S U T) whenever S fl T = 0. F is monotonic if v(S) < v(T)Chapter 1. Introduction and Preliminaries 21whenever S T, and 1’ is 0-monotonic if its 0-normalized game is monotonic. The0-normalized game of a game I’ = (N; v), denoted by 1’o = (N; vo), is defined by thefunction v0, where vo(S) v(S)— sv(i) for every S c N. F is convex if v issupermodular, that is v(S) + v(T) v(S fl T) + v(S U T) for any 5, T E 2N• It is easyto see that a superadditive game is 0-monotonic. The following results are well known(Maschler, Peleg and Shapley [1972,1979]).Proposition 1.2.5 For a convex game, the Davis-Maschler bargaining set coincides withthe core, and the kernel coincides with the prekernel and the nucleolus.Proposition 1.2.6 For a 0-monotonic game I’, K(I’) = PK(f).The solution concepts introduced above can be evaluated as allocation schemes forrevenue allocation problems that can be formulated as cooperative games. To apply theseconcepts to cost allocation problems, however, some natural modification and reinterpretation of these solution concepts are necessary, since in the latter case it is costs ratherthan benefits that are allocated. Formally, a cost game, F = (N, c), is a game whosecharacteristic function c is a cost function satisfying c(O) = 0. I’ is subadditive if c is sub-additive, that is c(S)+c(T) c(SUT) whenever SflT = 0. 1’ is convex ifcis submodular,that is c(S fl T) + c(S U T) c(S) + c(T) for any 5, T E The core, kernel, prekernel,nucleolus, prenucleolus, and bargaining sets for a cost game (N; c) are defined in termsof the corresponding solutions on the characteristic function game (N; —c). For example,the core of the cost game F is the set {x: x(N) = c(N) and x(S) c(S) for all S ç N}.In a cost game, the excess function is still defined as c(S)—x(S), but the maximum excessof i against j is replaced by the minimum excess of i against j. The results quoted abovewill still be valid for cost games after appropriate replacements of keywords, say, ‘convex’and ‘superadditive’ by ‘concave’ and ‘subadditive’, respectively, and ‘‘ is replaced byChapter 1. Introduction and Preliminaries 221.2.4 Algorithms and ComplexityThe complexity of algorithms will be one of the focuses of this dissertation. To studyalgorithm complexity, we should describe more or less precisely what is meant by concepts like ‘size’, ‘algorithm’, ‘running time’, etc. Here we shall however confine ourselvesto giving a brief introduction to complexity theory. For a more extensive and precisetreatment, see Aho, Hopcroft and Ullman [1974], or Carey and Johnson [1979].Complexity of AlgorithmsTo submit an instance of an optimization problem to an algorithm for solution bya computer, one must somehow represent it as a sequence of symbols over some fixedalphabet such as bits, or ASCII characters. Such an encoding is called the input of analgorithm. We define the size of the input to be the length of the encoding sequence, thatis, the number of symbols in it.The most widely accepted performance measure for an algorithm is the time it spendsbefore producing the final answer. This amount of time may however vary vastly fromone computer to another due to differences in computing environment. Thus, in theanalysis of algorithms, the time requirement or the complexity of an algorithm are often expressed in terms of the number of elementary steps required for the execution ofthe algorithm on a hypothetical computer. The elementary steps include arithmetic operations, comparisons, branching instructions, etc. We assume that all these kinds ofoperations require unit time. The complexity of an algorithm is measured as a functionof the size of the input of the algorithm. Hence, we can say ‘a linear time algorithm’, ‘an0(n3) algorithm’, ‘an exponential algorithm’, etc.An algorithm is called polynomial if its running time function is polynomially bounded(in terms of the size of its input). A problem is said to be solvable in polynomial time orpolynomially solvable if the problem can be solved by a polynomial-time algorithm.Chapter 1. Introduction and Preliminaries 23The Classes P and NPA problem that can be answered by yes or no is called a decision problem. Wedenote by P the class of decision problems that can be solved by a polynomial-timealgorithm. Another, possibly larger, class is the class NP (NP stands for ‘solvable bya Non-deterministic Turing machine in Polynomial time’). For a problem to be in NP,we do not require that every instance be solved in polynomial time by some algorithm.We simply require that, if x is a yes instance of the problem, then there exists a concise(that is, of length bounded by a polynomial in the size of x) certificate for x, which canbe checked in polynomial time for validity.NP-complete ProblemsA decision problem p is said to be reducible in polynomial time or Karp-reducible toanother decision problem P2 if there is a polynomial-time algorithm A such that if, forinput x, A outputs z then x is an instance of Pi if and only if z is an instance of P2 Wehave the following well-known result.Proposition 1.2.7 Ifp is polynomially reducible to P2 and P2 is polynomially solvable,then so is P1.A problem p is called NP-complete if it is in NP and each problem in NP is polynomially reducible to p. So if any NP-complete problem is polynomially solvable, then allproblems in NP are polynomially solvable. In some sense, an NP-complete problem is ahardest problems in the class NP.Strongly Polynomial AlgorithmsThe dimension of an input is the number of data items in the input (that is, eachnumber is considered to add one to the dimension of the input). An algorithm is said to bestrongly polynomial if (1) it consists of the elementary operations: additions, comparisons,Chapter 1. Introthiction and Preliminaries 24multiplications and divisions, (2) the elementary operations are carried out on rationalsof size polynomially bounded in the dimension of the input, and (3) the number of suchoperations is polynomially bounded in the dimension of the input. A problem is said tobe solvable in strongly polynomial time if there is a strongly polynomial algorithm forsolving the problem.Chapter 2Cost Allocation on Circular NetworksIn this chapter, we analyze two cost allocation problems arising from circular networks.Namely, the problem of allocating the cost of a travelling server among customers locatedin the vertices of a circular network, and the problem of allocating the construction costof a network among potential users that are located in vertices of a circular network.Game theoretical approach is used here to analyse these cost allocation problems. Gamesassociated with these cost allocation problems are called circular network (CN) games oftype I or type II. We investigate the structure and computation of four solution concepts:core, kernel, prekernel and nucleolus of CN games. Among other results, we provide alinear representation for the core polytope of a CN game, and show that the kernel,prekernel and nucleolus for both classes of CN games coincide. Furthermore, we developan 0(n3) algorithm for computing the nucleolus of a CN game, where n is the numberof nodes in the underlying circular network.The chapter is organized as follows: In Section 2.1 we define circular networks andcircular network (CN) games. In Section 2.2 we study the core, the kernel and theprekernel of CN games. We prove that the core of a CN game is nonempty and permitsa linear representation. We further show that the kernel and the prekernel of a CN gamecoincide and that both are contained in its core. Section 2.3 is devoted to the study ofthe nucleolus of CN games. We identify therein a characterization set for the nucleolusof a CN game, and provide a necessary and sufficient condition for a core element of aCN game to be its nucleolus. This latter characterization implies that for both classes of25Chapter 2. Cost Allocation on Circular Networks 26CN games the kernel, prekernel and nucleolus are identical. Section 2.4 is devoted to thedevelopment of an 0(n3) algorithm for computing the nucleolus of a CN game. Finally,in Section 2.5, we consider two possible extensions of our game models.2.1 Circular Networks and Associated GamesA circular network, by definition, is a four-tuple C (V, E, a, N), where (V, E) is asimple undirected cycle with V {O} U {v1,. . . , v,} and E = {e1,.. . ,e1} being itsnode set and edge set, respectively. Node 0 is called the root node, or the server node,and all other nodes are called customer nodes. A non-negative real-valued function, a, onE, is called the edge cost function, and N = {1, 2,. . . , m} (m n) is the set of players,or customers. Each player resides at a unique customer node, and each customer node isoccupied by at least one player. Players residing at the same node are called neighbors,and players residing at adjacent nodes are called adjacent players. We shall adopt thefollowing conventions and notation.Notation 2.1.1(1) Nodes and edges of (17, E) are indexed in such a way that: 0, e1,v1,e2,. . . , v, e+iis the order of nodes and edges encountered if the cycle is traversed starting from theroot node in one direction, say counter-clockwise.(2) Players are numbered in such a way that player i resides at node v for 1 <i <n.(3) The set of all players residing at node v is also denoted by v.*def . .(4) a = max{a(e): e E E} is the maximum edge cost in C.We study two cost games associated with two cost allocation problems defined on acircular network C. The first game is related to the following cost allocation problem:Customers residing at customer nodes require a service provided by a server located atthe root node. a(e), the cost of edge e, is interpreted as the one-way travelling cost onChapter 2. Cost Allocation on Circular Networks 27this edge. If a subset S ç N of customers decide to hire the server, then the server willmake a trip to these customers along the network and provide them with the service.The travelling cost of this trip, denoted by ci(S), will then have to be allocated to thecustomers in S. The game associated with this cost allocation problem is called a circularnetwork (CN) game of type I, and is denoted by 1 = (N; ci), where c1 is defined byc1 (5) = The minimum cost for the server to visit all customers in S andreturn to the root node through a closed walk in (V, E). (2.1)The cost of a walk in (V, E) is the sum of the costs of all edges in the walk. A closedwalk in (V, E) allowing the server to visit all customers in S and having the cost c1 (S) iscalled an optimal service plan for S. We use F1(S) to denote the edge set of an optimalservice plan for coalition S. Since the edge set of a walk uniquely defines the walk, wemay identify P’ (5) with its corresponding optimal service plan.In the second game, a(e) is interpreted as the cost of constructing edge e, and theobjective of every subset S N of customers is to connect all its members, perhapsthrough other members, to the root node. The cost of constructing such a connectionwill be denoted by c2(S), and this cost has to be allocated to the members in S. Thecost game associated with this cost allocation problem is called a circular network (CN)game of type II, and is denoted by I’ = (N; c2), where c2 is defined byc2(S) = The minimum cost needed to connect all players in S to node 0through a connected subgraph of (V, E). (2.2)The cost of a connected subgraph of (V, E) is the sum of the costs of all edges in thesubgraph. A subgraph which connects all players of S to the root node 0 and has thecost c2(S) is referred to as an optimal construction plan for S. Clearly, an optimalconstruction plan for a coalition S is a chain in the network which contains the root nodeChapter 2. Cost Allocation on Circular Networks 28and all other nodes in which customers in S reside. Similarly, we use F2(S) to denotethe edge set of an optimal construction plan and, by abuse of language, identify F2(S)with its corresponding optimal construction plan.Different as these two classes of games may be, we prove in the sequel that theyshare a few common properties. We use the generic term ‘a CN game’, or ‘CN games’,in statements or assertions which are applicable for CN games of both type I and typeII. In these situations we will also use Fc to denote a CN game defined on C (withoutspecifying the type of the game).For a coalition S of a CN game, let F(S) be an optimal service/construction plan for5, and let 5’ be the set of all players residing at end nodes of edges in F(S). Hereafter,5’ is referred to as the closure of S with respect to F(S), or simply a closure of S. Sis said to be connected if it is the closure of itself with respect to some of its optimalservice/construction plans.2.2 The Core, the Kernel and the Prekernel of a CN GameWe start by showing that F, the CN game of type I defined on a circular network C, is aconvex game. This, in turn, implies that I’ has a nonempty core (Shapley [1971]), andthat the kernel and prekernel of 1’ coincide (Maschler, Peleg and Shapley [1972]). Wethen show that f, the CN game of type II defined on C, is not convex. However, I’ isa spanning network game (see Granot and Maschler [1991]). As such, it has a nonemptycore and its characteritic function, c2, is subadditive. The subadditivity of c2 implies thatthe kernel and prekernel of 1’ coincide (Maschler et al. [1972]). Finally, we develop inthis section a linear representation for the core of a CN game, and prove that the kernelof a CN game is contained in its core.Chapter 2. Cost Allocation on Circular Networks 29Lemma 2.2.1 Let Pc = (N; c) be a CN game defined on C. Then,(1) Pc is monotone, that is, c(S) <c(T) whenever S C T.(2) If S, S C N, is a connected coalition in Fc, then, either S = A or A for some ior A U A for some i j, 1 i,j < n, where A = v1 U u vj and A = N \ A, for1<i<n.Proof (1) follows since all edge costs are nonnegative and any service/construction planfor T is also a service/construction plan for S whenever S T. (2) holds true since theunderlying network is circular.We will now prove that a CN game of type I is a convex game. To that end, we firstprove a lemma.Lemma 2.2.2 IfS T C N and ci(T) <ci(N), then F’(S) ç F’(T).Proof If a* < a(E) — a* (see Notation 2.1.1 for a*), ci(N) = a(E). Else, ci(N) =2(a(E) — a*) < a(E). Therefore, ci(T) < ci(N) implies that ci(T) < a(E). Suppose,on the contrary, that P1(S) P’(T). Then, since C is circular and S C T, E cP’(S) U P’(T). So, ci(S) + cj(T) 2a(E). This, in turn, implies that ci(T) > a(E),which contradicts the fact that ci(T) < a(E). .Theorem 2.2.3 A CN game of type I is convex, that is,ci(SUi)—c1( ) ci(TUi)—ci(T), forSçT andi S. (2.3)Proof If either ci(T) = ci(T U i) or ci(S U i) = ci(T U i), (2.3) follows from themonotonicity of c1. So we may assume that ci(T) < ci(T U i) and ci(S U i) < ci(T Ui) ci(N). From Lemma 2.2.2, this assumption implies that F1(S) P’(S U i) andP’(S) C P’(T). Thus if I = P1(S Ui) \P1(S), P’(T) U I is a feasible service plan forTUi. This means that a(I)+ci(T) ci(TUi), or, thatc1(SUi)—ci(S) ci(TUi)—ci(T).Chapter 2. Cost Allocation on Circular Networks 30Combining the above with Shapley [1971] and Maschler, Peleg and Shapley [1972],we obtain the following corollary.Corollary 2.2.4 A CN game of type I has a nonempty core. Moreover its kernel andprekernel coincide.A CN game of type II is not, in general, a convex game as demonstrated by thefollowing example.Example 2.2.5 Consider the circular network presented in Figure 1 below with thenumbers beside the edges being the edge costs. Assume that precisely one customerFigure 2.1: A CN game of type II that is not convexresides at each node. Let S = {2},c2(T U i) = 6, c2(T) = 5. Therefore,T = {2,3} and i = 1. Then,c2(SUi) = c2(S) = 4,c2(TUi)—cT) = 1> O=c2(SUi)—cS).It is easy to see that a CN game of type II in which there is precisely one customerat each node is a monotone minimum cost spanning tree game (Granot and Huberman[1981]). When there are possibly many customers at each node, a CN game of type II isChapter 2. Cost Allocation on Circular Networks 31a spanning network game (Granot and Maschler [1991]). Thus, the nonemptiness of thecore of a CN game of type II follows from the nonemptiness of the core of a spanningnetwork game with nonnegative data (ibid). For completeness, we prove the following,Lemma 2.2.6 The core of a CN game of type II, F, is not empty.Proof Let P2(N) be an optimal construction plan for the grand coalition. Each nodev of N is incident to a unique edge e in P2(N) which is on the unique path from vto node 0. Let & be the cost associated with e1, and consider the non-negative costallocation vector y, y E RN, such that y3 = for j e v. Then, using analogousarguments to those appearing in Granot and Huberman [1981] or Granot and Maschler[1991], one can prove that y C(F). For brevity, this part of the proof is omitted.Next, consider 5, T C N with S fl T = 0. Let P2(S) and P2(T) be some optimalconstruction plans for S and T, respectively. Then P2(S) U P2(T) constitutes a feasibleconstruction plan for S U T. Thus, since edge costs are nonnegative, we have that thecost function c2 is subadditive. That is, c2(S U T) c2(S) + c2(T) for all 5, T ç N,S fl T = 0. From Theorem 2.7 of Maschler, Peleg and Shapley [1972], the subadditivityof c2 implies the following corollary,Corollary 2.2.7 The kernel and prekernel of a CN game of type II coincide.The following theorem provides a unified representation for the core of CN games of bothtype I and type II.Theorem 2.2.8 (A Representation for the Core of a CN game) Let F = (N; c)be a CN game. Then,C(Fc)={x RN: x(A) <c(A),x(J4) <c(A),A=viU...Uv,A=N\A, i=1,2,...,n—1;Chapter 2. Cost Allocation on Circular Networks 32x 0, Vi N;x(N) = c(N).} (2.4)Proof Since Pc is monotone (Lemma 2.2.1), x > 0 for any x€ C(F). Therefore,it suffices to show that all other core constraints in (1.3) are implied by those in (2.4).To that end, consider first a constraint x(S) c(S) induced by an arbitrary subsetS E 2N which is not connected. Let S’ be a closure of S. Then, 5’ is connected andc(S) = c(S’). Further, since x, 0 for all i E N, x(S) x(S’) c(S’) = c(S). Thus, thecore constraints induced by non-connected subsets of N are implied by the constraintsinduced by connected subsets and the nonnegativity constraints. But in C, a connectedsubset is either A or or A U AJ for some i,j e {1,2,. . . ,n — 1},i < j (Lemma2.2.1(2)). Thus, to complete the proof it remains to show that constraints induced byA U A (i j) are implied by those included in (2.4).Indeed, if i=j, A U A = N. Else i < j, U A N, and it follows from theconnectivity of A U A that c(A U A) = c(A) + c(A). In this case, x(A) c(A) andc(A) imply x(A U A) c(A U A7) as claimed.Remark 2.2.9 (1) In general, (2.4) is not an efficient representation of C(Fc). Forexample, if c(A) = c(N), x(A) c(A) is implied by x(N) = c(N) and the nonnegativityconstraints. It is also worth mentioning that x 0 is implied by the monotonicity of c,x(N) = c(N) and the constraint induced by the subset N\i. Hence we could replace thenonnegativity constraints in (2.4) by the IN constraints induced by the subsets N\i fori e N.(2) Since (2.4) contains 2n — 1 + NI constraints, Theorem 2.2.8 provides an O(INI)representation for the core of a CN game.Lemma 2.2.10 Let P = (N; c) be a monotone cost game. If x e K(P) then x 0 forall i e N.Chapter 2. Cost Allocation on Circular Networks 33Proof Suppose, 011 the contrary, that there exists x E K(F) such that x 0. Let S bea subset of N satisfying(1) i e S such that x <0.(2) 5 minimizes e(T, x) among all subsets T satisfying (1).Consider the following two cases.Case 1. S 1. Then, S = {i} and e(S,x) = c(i) — x > 0. Choose j e N\i. Notethat such a j can be found since x(N) c(N) 0. Now,s(x)<e(N\i,x) c(N\i) — x(N\i) x < 0 < e(S,x)where the first and the last inequality follow from Equation (1.6), the second inequalityfollows from the monotonicity of c and the second to last inequality follows from thechoice of S. But s(x) > sj(x) together with x < 0 constitute a contradiction to theassumption that x E K(F).Case 2. S > 1. Let j E S\i, thens(x) e(S\i, x) = c(S\i) — x(S\i)c(S) — x(S) + x<e(S, x),where the second inequality follows from the monotonicity of c, and the last inequalityfollows since x < 0. As in Case 1, this leads to a contradiction. .Since CN games are monotone (Lemma 2.2.1(1)), it follows from Corollaries 2.2.4 and2.2.7 that:Corollary 2.2.11 Fora CNgamel’c, x 0 wheneverx e K(Fc) = PK(Fc).Theorem 2.2.12 For a CNgamel’c, K(F) c C(Pc).Proof For c = I’, the result follows directly from the convexity of F. (Maschler,Peleg and Shapley [1972]).Chapter 2. Cost Allocation on Circular Networks 34For Pc = F, we will prove this result by contradiction. Suppose, on the contrary,that x C(I’) for some x E K(F). Then, D E 2N such that e(D,x) <0. Let M1 bethe set of all subsets of N with minimum excess with respect to x. Let Q E M’, and Q’be a closure of Q. Clearly Q’ is connected. Further, we claim that Q’ e M1. Indeed, itfollows from Corollary 2.2.11 that e(Q’, x) e(Q, x), so the minimality of e(Q, x) impliese(Q’, x) = e(Q, x), namely, Q’ E M’. Therefore, there are connected coalitions in M’.Let T be a minimal connected coalition in M1 with respect to set inclusion and let F2(T)be an optimal construction plan for T. Clearly, e(T, x) e(D, x) <0.Let v be a leaf node for P2(T). Then, since T is connected, we have either A, =1 U c T or = v U••• U v.,, T. The remainder of the proof is analogousfor both cases, so for brevity we will only consider the case when A ç T. We claim thatx > 0. Indeed, if x = 0, then since a kernel point allocates equal cost to substituteplayers (Maschler and Peleg [1967]) we have x(v) = 0. But v, is a leaf node, whichimplies that e(T\v, x) e(T, x) and that T \ v is also connected. Hence, T \ v Ewhich contradicts the minimality of T.Now, s1(x) = s1(x) = e(T,x), for x E PK(F) and T e M’. Let S be amaximal coalition of N, with respect to set inclusion, among all subsets Q satisfyinge(Q,x) =s1(x), i+1 E Q and i Q. We claim that c2(S) < c2(S U i). Otherwiseif c2(S) c2(S U i), then e(S U i, x) = c2(S) — x(S) — x<e(S, x), which contradictsthe definition of M1 (note that S e M’, since e(S,x) = e(T,x) and T M1). Butc2(S) <c2(S U i) implies that i is not contained in any closure of S. So again from thechoice of S we conclude that S is connected and A S. Therefore, S U T = N (A C Tand A c 5). Let R = S fl T. As both S and T are connected and v1 T and v 5,we have the following,c2(S) +c2(T) = a(E) +c2(R) — a(eji)Chapter 2. Cost Allocation on Circular Networks 35= c2(N) + a* +c2(R) — a(e,)c2(N) +c2(R).Hence e(R, x) = c2(R) — x(R) c2(S) +c2(T) —c2(N) — x(R) = c2(S) +c2(T) — x(N) —x(R) = e(S, x) + e(T, x) <e(T, x). If R 0, e(R, x) < e(T, x), where the last inequalityfollows since e(S, x) = e(T, x) < 0. If R = 0, e(T, x) > 0 = e(0, x). Both cases constitutea contradiction to the choice of T. .2.3 The Nucleolus of a CN GameIn this section we identify a characterization set for the nucleolus of a CN game consistingof O(INI) coalitions, and provide a necessary and sufficient condition for a core elementof a CN game to be its nucleolus. As a corollary of the latter characterization, wedemonstrate that the coincidence of the kernel, the prekernel and the nucleolus holdstrue for all CN games.The sequential linear programming (LP) procedure’, also referred to as Kopelowitz’smethod, for computing the nucleolus of a game can be formalized as follows (see Granot,Granot and Zhu [1994]). Let T 2N, and denote by PT the following LP problemPT: Max{r: rc(S)—x(S), SeT;e X(I’)}. (2.5)The sequential LP process for PT, denoted by SLP(PT), is the process of solving a sequence of LP problems, {Pk: k 1}, led by Pi = PT and terminated with 1)which has a unique optimal solution or has only equality constraints. For the kth LPproblem, Pk, in this process, let rk be its optimal value, Xk be the projection of its1This method was implicitly suggested by Schmeidler [1969], formally tested by Kopelowitz [1967],and carefully analysed by Maschler, Peleg and Shapley [1979].Chapter 2. Cost Allocation on Circular Networks 36optimal solution set on RN, k = {S C N: e(S,x) = rj, for all x € Xk}. Then, Pk+1is derived from Fk by converting all constraints induced by subsets in k into equalitiesof the form, x(S) = c(S)—ri, S k. The projection, X,ç, of the optimal solution ofthe last LP of SLP(PT) on R”, is called the outcome of SLP(PT). With this notion,Kopelowitz’s result (Kopelowitz [1967]) can be stated as follows:Lemma 2.3.1 The outcome of SLP(F2N) is N(F).Definition 2.3.2 A subset T of 2N is called the characterization set, or the c-set forshort, for the nucleolus of a cost game P if the outcome of SLP(PT) is N(F).Intuitively, T is the c-set for N(F) if and only if the lexicographical order of qS(x; F)for x e X(F) is determined by their subvectors consisting of components e(S, x), forS€T. It is easy to see that if T is a c-set for N(F), then so is every superset of T.Next, we show that a CN game Pc has a characterization set consisting of no morethan O({N{) coalitions. Specifically, let{A,A, i = 1,2,... ,n —1; N\j, j e N}, (2.6)where A and A are as defined in (2.4).Theorem 2.3.3 T is the characterization set for P.Proof Granot, Granot and Zhu [1994] have proved that the class of irreducible connected coalitions (see definition therein) is a c-set for the nucleolus of a monotone costgame which has a nonempty core. Then, Theorem 2.3.3 follows from this result and thefact that T, given by (2.6), contains the class of irreducible connected coalitions for c.But, for completeness, we provide below a direct proof.Let Xi be the projection of the optimal solution set of P2N on RN. Then, sinceC(Fc) 54 0, Xi C(Fc).Chapter 2. Cost Allocation on Circular Networks 37Claim. For every S E 2N \ Tc there exists ‘T5, Ts C T, such that,(1) e(S,x) e(T,z), VT E ‘T,Vx E Xi;(2) es, the incidence vector2 of 5, is in the span of {eT: T e Ts}.Suppose the claim is true. Let S e 2N \ T. Then, from (1), constraints inducedby coalitions in Ts will be converted to equalities before the constraint induced by Sin SLP(P2N). Note that whenever the constraint induced by a coalition is converted toan equality the total cost allocated to that coalition under the nucleolus is determined.Hence, from (2), after all constraints induced by coalitions in Ts are converted to equalities, the total cost allocated to S under the nucleolus is determined. Therefore, deletingthe constraint induced by S in all LP problems in SLP(F2N) will not affect the outcomeof the process. So the outcome of SLP(PT) is the same as that of SLP(P2N), which isN(Pc). Hence, to complete the proof it remains to show the validity of the claim.Proof of the Claim. Since Pc is monotone and C(Pc) 0 we have that x > 0 forall x E C(I’).3 Therefore, x 0 for all x E X1. For any S E 2N \ Tc, let 5’ be a closureof S. So 5’ is connected, and thus 5’ either equals to A, or A, or A U A for some i,j,1 < i < j < n (Lemma 2.2.1(2)). Accordingly, let T5 = $ U {N\j,j e 5’ \ S}, where$ = {A} or {A} or {A,A}. Clearly, Ts defined this way satisfies condition (2) above.To complete the proof it remains to show that Ts satisfies (1). For j 5’ \ S and x E X1,e(N\j, x) = c(N\j) - c(N) + xxj, since Pc is monotone= (x(S U j) - x(S)) + (c(S) - c(S U j)), since c(S) = c(S U j)= e(S,x)—e(SUj,x)e(S, x), since x e X1 and thus e(S U j, x) 0.2The incidence vector for a subset S of N is the vector e, es E RN, such that e = 1 if i e S ande = 0 otherwise.3For x E C(rc), x(N\i) < c(N\i), thus, x = x(N) — x(N\i) > c(N) — c(N\i) > 0 for i E N.Chapter 2. Cost Allocation on Circular Networks 38Further, since x 0 for x E Xi and c(S) = c(S’), then e(S,x) > e(S’,x) for x X1. IfS’ is either A or A, for some 1 i < n, we are done. Otherwise, 5’ = A U A, for some1 <i < <n. ThenI c(N) ifi=jc(S’)=c(A) + c(A), otherwise.Thus1 o, ifi=je(S’,x)=e(A, x) + e(A, x), otherwise.Hence, for x E X1 c C(Fc), e(A,x) e(S’,x) e(S,x) and e(AJ,x) e(S’,x)e(S, x). This completes the proof of the Claim, and thus the proof of Theorem 2.3.3.The theorem below provides a necessary and sufficient condition for a core allocationof a CN game to be its nucleolus.Theorem 2.3.4 A vector x E C(Fc) is the nucleolus of Fc if and only if x satisfies:(a) .s(x) = s(x) for all pairs of adjacent players;(b) x = x3 if i and j are neighbors, i.e., residing at the same node.Proof The necessity follows from the fact that the nucleolus of Fc is contained in itsprekernel (Maschler and Peleg [1967]).To show the sufficiency, assume that x E C(Fc) and satisfies (a) and (b). PartitionTc into collections M1,M2,. . . , Mc such that: (1) all subsets in M1 (1 1 < k) havethe same excess function value ri with respect to x; (2) r1 < r < < rk.Let N(Fc) = {y}. To prove that x = y it suffices to show that any change in x willproduce a lexicographically inferior allocation to x. Or, equivalently, since T is the c-setfor N(Fc) and the incidence vectors of subsets S, S T, span RN, it suffices to showthat x(S) = y(S) for all S E Te. Thus, we only need to establish the following claimssuccessively:Chapter 2. Cost Allocation on Circular Networks 39Claim 1 (1 1 k). For any S E M1, any change in x(S) will produce alexicographically inferior allocation to x. Or, equivalently x(S) = y(S) for allSEM1.But, all these claims are implied by the following separation result:Claim 0. For any S E M1, 1 1 < k, there is a partition, {S,.. .,S,}, ofS such that N\ SE M’ U ... U M1, 1<i< p.Indeed, assume that Claim 0 holds and let S M1. Then, from Claim 0, 5 =S U... U Si,, and N\S E M’ for 1 <i <• Note that for any T e M’ any increase inx(T), with an equal decrease in x(N\T), will decrease the excess function value for T, andtherefore produce a lexicographically inferior allocation to x. Hence, for a fixed x(N), wecan neither increase x(S) nor can we decrease x(S) without producing a lexicographicallyinferior allocation to x. Indeed, a decrease in x(S) will increase x(N\S), and hence willincrease x(N\S) for some 1 i p, which will result with a lexicographically inferiorallocation to x since N\S E M’ for 1 p. Thus, since y is lexicographically optimal,x(S) = y(S) for all S e M’ and Claim 1 is implied by Claim 0. Suppose we havesuccessively established Claim 1 through Claim 1—1 (1 > 1) by using Claim 0, and thusx(S) y(S) for all S M’ U. U M’. To verify that Claim 0 also implies Claim 1, letS E M1. From Claim 0, Scan be partitioned into S1u• . •uS, with N\5 M1u. uM1for 1 < p. Again, we can neither increase x(S), nor can we decrease x(S) (sinceN\S e M’ U U M’ for 1 i p) without producing a lexicographically inferiorallocation to x. So any change in x(S) will produce a lexicographically inferior allocationto x, and x(S)=y(S) for all S E M’ U U M’. Hence Claim 1 is also implied by Claim0. Therefore, x(S)=y(S) for all S E Tc, which would imply that {x} {y} = N(Fc).Thus, to complete the proof, it remains to verify Claim 0.Chapter 2. Cost Allocation on Circular Networks 40Proof of Claim 0. Observe first that (b) in Theorem 2.3.4 implies,e(N\s, x) = e(N\t, x), if s and t are neighbors. (2.7)Suppose S E M1 for some 1 1 Ic. Thus, from (2.6), S is either of the form A, A,li<n,orN\j, jEN.Case 1. S is of the form A or A. By symmetry, it is sufficient to consider the casewhen S = A for some 1 <i <n.If N\k e M1 U M1 for all k 5, then {{k}, k E S} is a desired partition forS. Else, let j be the maximum index between 1 and i such that N\j M U ... U M1.Then, either j = i, and then we let Q = 5, or j < i and we choose Q = N\{j + 1}.Observe that if j <i thene(N\j, x) > ri and e(N\k, x) ri for j < k <i. (2.8)Now, for both cases when j = i or j <i we have that j e Q, j+1 Q aild e(Q, x) <ri.So, it follows from (1.6) and (b) of Theorem 2.3.4 that Sjji(X) = sjj(x) <ri. Therefore,e(N\j,x) > .si3(x). Let Sjij(X) = e(T,x) for some T ç N, i+1 e T, j T. Then,since c(N\j) c(N),> x + c(N\j) — c(N) = x + c(N\j) — x(N) = e(N\j, x) >s1(x) = e(T, x). (2.9)It follows thatc(TUj) x(TUj), sincexC(I’c)= x(T) + x3 > x(T) + e(T,x), by (2.9)= c(T).This implies that any optimal service/construction plan for T does not include node v3.Since x 0, we may assume that T is connected. That is, T is of the form A U Ar forChapter 2. Cost Allocation on Circular Networks 41some r <j and c(T) = c(A) + c(Ar). Since e(T, x) = e(A, x) + e(Ar, x) and x ee(T, x) e(A, x). Hence, A E M1 U U M’. Combining the latter result with (2.7)and (2.8), we conclude that {A, {t}, t e A \ A3} is a desired partition for S = A.Case 2. S = N\j for some j E N. Let .s = 0 if N\k e M1 U U M1 for all k,1 <k j, and otherwise let s be the maximum index between 1 and j such that N\sM’U UM1. Let t = n+1 if N\k E M’U UM1 for all k, j k n, and otherwise let tbe the minimumindex betweenj and n such that N\t M’u• . •uM1 Ifs> 1, it followsfrom (b) of Theorem 2.3.4 and (1.6) thats13(x) =s31(x) e(N\{s+1},x) r. Lets13(x) = e(T, x) for some T N, s+1 E T, s T. Then, as in Case 1, we can show thatT is of the form Au Ar for some r < s and that A3 M’ U . . U M1. Similarly, if twe can show that A_1 e M’ U ... U M1. Therefore, {A3, , {k}, k S \ (A3 U AZ)}is a desired partition for S = N\j (note that A3 = 0 if s = 0 and A = 0 if t = n+1). .Corollary 2.3.5 For a CN game Fc, K(I’c) = PK(Fc) = N(Fc).Proof By Corollaries 2.2.4 and 2.2.7, PK(I’) = K(Fc). By Theorem 2.2.12, K(Fc) çC(I’c). Thus, by Theorem 2.3.4, K(I’c) N(P). The proof follows since the nucleolusis containted in the kernel. .Observe that, if I’ = I’, Corollary 2.3.5 also follows from the convexity of 1 (seeMaschler et al. [1972]).2.4 An Algorithm for Computing the Nucleolus of a CN GameWe develop in this section an efficient algorithm for computing the nucleolus, N(1’),of a CN game Fe. Briefly, our approach is as follows. First, we normalize c. Thenormalized game F is strategically equivalent to Pc, but has the additional property thatthe LP problems encountered in the sequential LP method for computing its nucleolusChapter 2. Cost Allocation on Circular Networks 42have simpler structure. Indeed, it is shown that the optimal value and a ‘partial’ optimalsolution for any LP problem arised in the process can be computed efficiently. Combiningthese results and the sequential LP method yield an 0(n3) algorithm for computing thenucleolus of a CN game, where n is the number of nodes in the underlying circularnetwork. Unfortunately, the proofs of some of the results in this section are somewhatlengthy and involved.For a cost game F (N; c), define its marginal vector mr = (m)EN by m =,, def ,, def .c(N) — c(N\z). Let F = (N; c = c — mr). Clearly F is strategically equivalent toF. Since the nucleolus is covariant under strategic equivalence, N(I”) = N(F)—Tflp.Furthermore, the c-sets for N(F) and N(F’) coincide. Indeed, let T C 2N be a c-setfor I’. Then, for this game the lexicographical order of vectors (x; F), x e X(F), isdetermined by the excess function values e(S, x), for S E T. But q5(x; F) = q(x — m; F’)for all x E X(F) and X(F’) = {x — mr; x X(F)}, so T is also a c-set for the nucleolusof F’. We establish now some simple properties of F’ = (N; c’).Lemma 2.4.1 If C(F) 0 for some cost game F, then,(1) C(F’) 0,(2)x>OforanyxeC(F’),(3) c’(S) 0 for any S c N.Proof (1) follows from C(P’)={x—mp: x E C(F)}. To show (2), observe thatc’(N\i) = c(N\i)—mp(N\i) = c(N) — (c(N) — c(N\i))—mp(N\i) (2.10)c(N) — mp(N) = c’(N);and= x(N) — x(N\i) = c’(N) — x(N\i) = c’(N\i) — x(N\i). (2.11)Thus x > 0 if x e C(F’). (3) follows from (2) since x(S) c’(S) for any S N andx e C(F’). .Chapter 2. Cost Allocation on Circular Networks 43Consider now the game 1’. The first LP problem in the sequential LP procedure forcomputing its nucleolus is FTc (see (2.5)), which can be rewritten as follows,F1’: Max{r: r + x(S) c’(S),S {A,A;i = 1,2,... ,n — 1};ieN;x(N) c’(N)},where c’(S) = c(S)— mr(S). Indeed, from (2.10) and (2.11), the set of constraints,r < x for i E N, are induced by subsets in {N\i: i E N}. Further, from Lemma 2.4.1(1)and Theorem 2.2.8, the projection of the optimal solution of F1’ on RN is contained inC(P). Thus, the constraint x e X(I’) in FT can be replaced by x(N) = c’(N).Notation 2.4.2 A circular system defined on a finite set A is a four-tuple: V(A,V,A,b), where V = {vi,.. . ,v} is a partition of A, A = {A,A: 1 < i < n}, A =v1 U Uv, = A\A, and b is a nonnegative real-valued function on AU{A} satisfyingb(A) + b(A) b(A) for 1 <n. Let F(V) denote the following LP problem associatedwith the circular system V,F(V): Max{r: r + x(S) < b(s), S E A,rx, iSA,x(A) = b(A)},and let rv denote the optimal value of F(V).Suppose C = (V, E, a, N) is a circular network. Naturally, it induces a circular systemon N of the form, (N, V, A, c’ = c—mi-a), where c is the cost function for Pc. From Lemma2.4.1(3), c’ is nonnegative, and from the subadditivity of c, c’ satisfies c’(A) + c’(A) >c’(A) for 1 i < n. By abuse of language, we shall also denote this derived circularsystem by C. Clearly F(C) = F1.Chapter 2. Cost Allocation on Circular Networks 44Notation 2.4.3 Let V be a circular system defined on A. We adopt the followingnotation throughout this section:b(A)r—def b(A) j def b(A)r = , r = — , z=1,2,... n—1AI+1nj b(A)+b(A) — b(A) for 1 i i <n;rv = min{r; n, r , 1 z < n; 1 <i <j < n }.We sometimes omit the subscript in r if doing so will not cause confusion.In order to prove that r, is the optimal value for P(V), i.e., rv = r,, we need toprove several lemmas.Lemma 2.4.4 If b > O,i = 1,2,...,k, thenZ1a/Zbis a weighted average ofthe terms a/b with weights ,\ b, i = 1,2,. . . , k.Proof Clearly, )q(a/b) = ZL1 a/Z bk. •Lemma 2.4.5 Let V be a circular system, then rvProof Let (r, x) be feasile to F(V). Then, for all i in A,r= 1’by definition of rr+x(A) . .> since (r, x) is feasibe-> (Ai+1)rsince r x, Vj AChapter 2. Cost Allocation on Circular Networks 45Similarly,rb(A) > r+x(A) > (Ai+1)r= rIA+1 — A+1 —b(A) x(A) lAirTfl— iAi IAI _ ,— b(A) + b(A) - b(A)r,3— IAi—iAi+2>— iAi—iAi+2— x(A\A)+2r— iAi—iAi+2(A — iAi + 2)r —— lAi—IAi+2— r.Therefore, from the definition of r, rD r,.Lemma 2.4.6 Suppose r, = for some 1 <i < <n — 1. Then,(1) (b(A)— b(Ak))/(iAji — iAki) r for k = i,. ..,j —1;(2) (b(A)— b(Ak))/(iAki - iAi) r fork = i±1,. ,j.Proof (1) From the definition of we have— b(A) + b(A) — b(A)r3— iAi—iAi+2— (b(A)— b(Ak)) + (b(Ak) + b(A) — b(A))- (iAi - iAki) + (iAki - jAil + 2)Now, suppose that (b(A)— b(Ak))/(iAji — iAki) > r, for some k, i < k < j — 1. Bythe above equation, is a weighted sum of (b(A)— b(Ak))/(iAji — iAkl) and rk. Thus,rk < r3 = r, which contradicts the choice of r.(2) Similar to the proof of (1). .Lemma 2.4.7 Suppose r3 <r and r = rk or rc for some k. Let k1 be the maximuminteger between 1 and n — 1 such that r, = rk (If r > for all i, then k1 = 0 andChapter 2. Cost Allocation on Circular Networks 46A0 = 0), and let k2 be the minimum integer between 1 and n — 1 such that = r’ (If> r, for all i, then k2 = n and A = N). Then, k1 <k2.Proof If either k1 = 0 or k2 = ri, then k1 < k2 holds trivially. Assume thus that1 < k1,k2 <n. From the definition of rk, and r’2, we have that r = b(Ak,)/(lAkil+ 1)and r, = b()/(l + 1). Thus,b(Ak,) + b(Jf) = (lAk,l + IAICI + 2)r= (lAkil— lAk2 + 2)r, + jAlr, (2.12)where the last equality follows since Al = Ak2 + IA. Suppose, on the contrary, thatk1 > k2. Then, by definition of rk2k,, and since rk2k1 > r, we have,b(Ak,) + b(ç) (lAi2 — Ak21 + 2)r, + b(A). (2.13)Now, from (2.12) and (2.13), lAl4 b(A), or r b(A)/lAl = r. This contradicts theassumption that r > r.Theorem 2.4.8 For a circular system V, rv = r,.Proof For simplicity, we write r* for r in this proof. Since b is non-negative andb(A) + b(T4) b(A) for 1 i < n, it follows that r* 0. From Lemma 2.4.5, the proofwill follow if we show that F(V) has a feasible solution with r = r*. This is done byinduction.If n = 1, r* = r1 = b(A)/IAI, then the unique optimal solution for P(V) is r = =r*, Vi e A. Now, suppose n > 1, we consider separately the following three exhaustivecases:Case 1. r* = r;Case 2. r* <r and r* = for some i,j, 1 i j <n; andChapter 2. Cost Allocation on Circular Networks 47Case 3. r* < r,r* < r, Vi,j, 1 < i j < n, and r* = Tk or r for some k,1<k<n.Proof of Case 1 (r* = rn). In this case the unique optimal solution for P(V) isr = = r*, Vi e A.Proof of Case 2 (r* < r, and r* = rjj for some 1 i j < n). In this case weshow that r = r* and xk = r*, k A3 \ A, can be completed to a feasible solution toP(V). Indeed, in P(V), set xk = r* for k A\A (A\A is empty if i= j), convertthe constraints induced by A and A, into equalities by setting r* x(A) = b() andr* + x(A) = b(A,). Then the constraint system of P(V) may be written as:r+x(Ak) < b(Ak) k=1,...,i—1 (1)r + x(A) b(Ak) — (Ak — IAiDr* k = i,. ..,j — 1 (2)x(A1) = b(A)— (AI — + 1)r* (3)r+x(Ak\Aj)<b(Ak)_b(Aj)+r* k=j+1,...,n—1 (4)r+x(A)b(A) k=j+1,...,n—1 (5)(III) r + x(A) <— (iA — (6)=— (jAI — IA1 + 1)r* (7)r + x(A\A) <b(A)— b(A) + r* (8)x(A) + x(A) = b(A) — Aj\Ajr* (9)r<r* (10)x r i E N\(A\A). (11)For any k, i k <j, from Lemma 2.4.6(1),b(A)— b(Ak) (IAI — IAkDr*, or, b(A) — IAjIr* b(Ak) — IAkIr*.This impliesb(A) — — Aj)r* <b(Ak)— (AkI — IAiDr*, <k <j.Chapter 2. Cost Allocation on Circular Networks 48Upon combining the last set of inequalities with constraint (10), we conclude thatb(A)— (AI — AI + 1)r* b(Ak)— (Akl — AjI)r* — r, i < k <j.Thus the set of constraints (2) in (III) are implied by (3) and (10). Similarly, byapplying Lemma 2.4.6(2), it can be shown that (6) in (III) is implied by (7) and (10).Now, by adding (3) and (7) in (III) we obtainx(A) + x(A7) = b(A) + b(A) — 2(A—+ 1)r*, since AI — A1 = AI —= b(A) — —= b(A) — A \ Ajr*,where the second equality follows since r* = =Thus, (9) is implied by (3) and (7). Using now the fact that A \ A = A \ A3, afterdeleting redundant constraints and reordering, we can rewrite (III) asr+x(Ak)b(Ak) k=1,...,i—1 (1)r + x(A \ A) < b(A) — b(A) + r* (8)x(A) = b(A)— (AI — + 1)r* (3)x>r iEA (11)(IV) r < r* (10)r+x(A)b(A) k=j+1,...,n—1 (5)r+x(A\A)b(Ak)_b(Aj)+r* k=j+1,...,n—1 (4)x(A) = b(A)—(IAi—A + 1)r* (7)x>r iéA. (11)To complete the proof of Case 2 we need to introduce some notation and prove a lemma.To that end, denote by (TV)1 and (TV)2 the two systems consisting of the first four andthe last four sets of constraints of (IV), respectively.Chapter 2. Cost Allocation on Circular Networks 49Notation 2.4.9 Let V be the circular sub-system (of V) defined on A with a costfunction b: given by: b(Ak) = b(Ak) and b(A\Ak) = b(A)_b(A)+r*, k = 1,...,i1,b(A) = b(A)— (IAI— IA + 1)r*. (Compare this definition with the right hand side ofconstraints in (TV)1.) Similarly, let V’ be the circular sub-system (of V) defined onwith cost function b given by: &1(A) = b() and \A) = b(Ak) — b(A) +r*, k =j +1,. . . , n — 1, l, (AJ) = b(A)— (IAi— A1 + 1 )r*. (Compare this with the right handside of constraints in (TV)2.)Lemma 2.4.10(1) b and b satisfy all properties required in the definition of a circular system(Notation 2.4.2).(2) (IV)1 and (IV)2 are the constraint systems of P(V) and F(V) respectively.Proof We prove the case for b and P(V1). The other case is analogous, thus omitted.(1) Since b is nonnegative, b(Ak) = b(Ak) 0. For 1 k <i,b(A) + b(A) - b(A)=(b()- b(A)) + (b(A) + b(A)— b(A))= (jAj- Ak) +- AI + 2)so rk is a weighted average of and (b(4) —b(4))/(A— Ak). Hence r r impliesthat b(4)— b(A) 0. Thus, b(A \ A,) = b(A) — b(4) + r* 0 since r* 0. Finally,from r3 = b(A)/(IAI+1) it follows that b(A) = b(A)—(AI— Aj+1)r* > IAjr* 0.So b is nonnegative. Furthermore, b(Ak) + b(4) b(A) and — + 2)r* =b(A) + b(A) — b(A) (as r* = r) imply(b(Ak) - r*) + (b(A) - b + r*) > b(A)- (IA - A1 + 1)r*,which verifies b(Ak) + b(A \ A,) > b(A).(2) follows from the definition of b and P(D). aChapter 2. Cost Allocation on Circular Networks 50Let us return to the proof of Case 2 of Theorem 2.4.8 where we need yet to show thatr = r* and xk = r’, k E A \ A, can be completed to a feasible solution to P(V). Todo so it suffices to prove that (IV) has a feasible solution with r = or equivalently,that both (TV)1 and (TV)2 have feasible solutions with r = r*. Now observe that if (, x1)(resp., (, x)) is feasible to (TV)1 (resp., (TV)2), then (r, x’) (resp., (r, x2)) is feasible to(TV)1 (resp., (TV)2) for all r . Therefore, it is sufficient to show that the optimalvalues, rv and r73, of P(V) and P(VJ), respectively, are no less than r*.By Lemma 2.4.10, both V and V are smaller circular systems than V. Thus, by theinduction hypothesis, rv = r,. and mi = r,,. Therefore, to complete the proof of Case2, it remains to prove that r* and r*. We start by showing that r*.Indeed, for 1 k <i,b(Ak) = b(Ak), by Notation 2.4.9AkI+1 Akj+1= rj, by definition of rkr*, since r* rk.Further, for 1 s t <i,b(A) + b(A \ A8) — b(A) = b(A) + b(A) — b() + rK—b(A) + — + l)r*= b(A) + b(J4) —where the first equality follows from Notation 2.4.9 and the last equality follows from theassumption that r” = and from the definition of (see Notation 2.4.3). Therefore,(b(A) + b(A \ A8) — b(A))/(lAl — IASI +2) = r8t > m*.Finally, r = b(A)/(A + 1) r* implies b(A) — + 1)r* + IAir* IAV*,or (b(A) —— IA + 1)r*)/IAj r*. Thus, > r* by Notation 2.4.9.Therefore, from the definition of r. (see Notation 2.4.3 with V being replaced by Vi),Chapter 2. Cost Allocation on Circular Networks 51r. r* as claimed. The proof that r is similar, hence omitted. This completesthe proof of Case 2.Proof of Case 3. (r* < r,r* < r, Vi,j, 1 i <j < n, r* = rj or rc for some k.)In this case we show that r = r* and x3 = r* for j E Ak1 U A can be completed to afeasible solution to P(D), where k1 and k2 are as defined in Lemma 2.4.7.In P(V), set x3 r* for j U A, and convert the constraints induced byAk1 and A into equalities by setting r* + x(Ak1) = b(Ak1) and r* + x(A) = b(4).After removing trivial redundant constraints induced by A for 1 i k1 and A forj <n, the constraint system of P(V) can be written asr + x(A\Ak1)< b(A,) — b(Ak1)+ r* k1 + 1 < i < k2 (v.1)r + x(Ak2 \ A) < b(A) — b(Ak1)— — IAk2 — 1)r* k2 < i < n (v.2)+ x(A\A) <b(A) — b(A) + r k1 + 1 <i < k (v.3)(V) r+x(4\A) b(A) —b(A) — (A — — 1)r* 1< i < k1 (v.4)x(Ak2\A1)= b(A) — b(Ak1)— b(A) + 2r* (v.5)x > r i E Ak2\A1 (v.6)r < r*. (v.7)Observe first that (v.2) and (v.4) are implied by (v.5). Indeed, let k2 i < n. Then,ri2 r* impliesb(A) + b(A) — b(A) > — Ak2 + 2)r* = — Ak2 — 1)r* + 3r*Thus,b(A)— b(Ak1) —— IAk2 — 1)r* — r b(A) — b(Ak1)— b(A) + 3r* — rb(A)— b(Ak,) — b(A) + 2r*,where the last inequality follows since r r*. So (v.2) is implied by (v.5). Similarly,since Ak2 \Ak1=A\A, (v.4) is implied by (v.5). Denote by (V)” the system consistingof constraints (v.1), (v.3), (v.5) and (v.6).Chapter 2. Cost Allocation on Circular Networks 52Notation 2.4.11 Let Dkik2 be the circular sub-system (of V) given on Ak2 \ Ak1 withcost function b’ defined by: b’(A \ Ak,) = b(A) — b(Ak1)+ r* and b’(A \ = b(A) —b(A) + r*, k1 + 1 < k2, b’(Ak2 \ A1) = b(A) — b(Ak1)— b(Ak2)+ 2r*. (Compare thiswith the right hand side of (V)’.)As was shown in the proof of Lemma 2.4.10, one can easily obtain that:(1) b’ has the required properties for the cost function of a circular system; and(2) (V)’ is the constraint system for F(7k1k2).Moreover, Vk1k2 is a smaller circular system than V, therefore, by induction, rvkl k2 =r*‘-‘k1 k2To complete the proof of Case 3 of Theorem 2.4.8, as in Case 2, we need to justifythat rvkk > r*. Indeed,r= b(A) = b’(A \ A1) + b(Ak1)— r by Notation 2.4.11.AI+1 Aj\Akj+1+Ak,IThus r is a weighted average of (b(Ak1)— r*)/Akl and b’(A \Ak1)/(A \ A1 I + 1). But,since r* = rk1 = b(Ak1)/ IA + 1) we have that (b(Ak1)— r*)/IAkl = r*. Therefore,from r r* it follows that b’(A \ A1)/(IA \ Ai1 + 1) r*. Similarly, b’(A \ )/(iA\Aj + 1) r*. Finally,r= b(A) = b’(Ak2 \ A1) + (b(Ak1)— r*) + (b(42)— r*) by Notation 2.4.11.Al (lAk2 — Ak1) + lAkil - Ak21Thus r > r* and (b(Ak1) — r*)/lAkll = (b(A) — r*)/lAl = r* imply that b’(Ak2 \Akj/(Ak2I— Ak1 I) r*. Therefore rkk r* from the definition of rklkl (see Notation2.4.3 with V being replaced by Vk1k2). This completes the proof of Case 3, and thus theproof of Theorem 2.4.8.Remark 2.4.12 Observe that in the proof of Theorem 2.4.8 we have shown the following:Chapter 2. Cost Allocation on Circular Networks 53(1) If is realized by some then P(D) has an optimal solution, (ri, x*), whichsatisfies the constraints induced by A and A, as equalities and 4 = for k e A \ A.(2) If r, is realized by r or r for some i, 1 < i < n, let k1 and k2 be chosen as inLemma 2.4.7. Then P(V) has an optimal solution, (r,x*), which satisfies the constraintsinduced by Ak1 and A1 as equalities and 4 = 4 for k e Ak1 U A.We can further show thatTheorem 2.4.13 For a circular system V, let r, be the optimal value of P(V) as computed by the formula given in Notation 2.4.3, and let (4, x) be an arbitrary optimalsolution of P(V). Then,(1) If is realized by some then the constraints induced by A, A and r < xk,for k A, \ A, are all binding at (r,, x*);(2) If <r and r, is realized by rk or r’ for some k, 1 k < n, then the constraintsinduced by Ak1,A and r x, for i E Ak, U 4, are all binding at (4, x*), where k1and k2 are chosen as in Lemma 2.4.7.Proof (1) In P(D), upon adding the constraints induced by A and A, and subtractingthereof the constraint x(A) = b(A), we obtain that for every feasible solution (r, x),2r + x(A, \ A) < b(A) + b(A) — b(A) = (AI — AI + 2)r,. (2.14)So, if (4,x*) is an optimal solution for P(V), then,(2 + A \ A)4 24 + x*(A \ A), since r 4 and r— + 2)4, by (2.14) and since 4 =Therefore, 4 = 4, Vk E A \ A, and 4 + x*(S) = b(S) for S = A, A.Chapter 2. Cost Allocation on Circular Networks 54(2) From Lemma 2.4.7, k1 k2. Consider first Ak1. If rk = 4 and (4,x*) is anoptimal solution for P(V), then,(IAk1H + 1)4 < 4 + x*(Ak) since 6< b(A,1), by feasibility of (4,x*)= (Ak1I + 1)rk, by definition of rk1= (Ak1 + 1)4, since rk1= 4.Therefore, 4 = 4, k E Ak1 and 4 + x*(Akl) = b(Ak1). The proof for A is analogousand thus omitted. .We are now ready to present an algorithm for computing the nucleolus of a CN game.This algorithm is an implementation of the sequential LP method for computing thenucleolus of circular network games. For a given circular network, C, P(C) and all otherLP problems encountered in SLP(F(C)) are, or can be decomposed into, LP problems ofthe form P(V), where V is some circular system. At each iteration of the algorithm, an LPproblem P(V) is considered (where V = C at the first iteration). We compute its optimalvalue and a partial optimal solution, and identify some of its constraints which are bindingat all of its optimal solutions. Then, after converting these constraints found above andsome other related constraints into equalities in P(D), we decompose the resulting LPproblem into LP problems defined on smaller circular systems. Theorem 2.4.13 ensuresthat the partial solution computed at each iteration is also a partial nucleolus allocationfor F. Therefore, at each stage of the algorithm, a partial nucleolus allocation for F iskept and this partial allocation expands over the stages of the algorithm from a null setto the full allocation, N(I’). In this sense, this algorithm, like Megiddo’s algorithm forcomputing the nucleolus of the tree game (Megiddo [1978]) and Littlechild’s algorithmfor computing the nucleolus of the airport game (Littlechild [1974]), may be regarded asa dual algorithm.Chapter 2. Cost Allocation on Circular Networks 55An Algorithm for Computing the Nucleolus of a CN gameInput: a circular network C (V,E,a,N);Output: {x} = N(l’c).Step 0. Initiate by computing the marginal vector mp for Fc and by setting P ={F(C)}.defStep 1. If P = 0, output x = y + and terminate. Else choose P(V) E P, delete itfrom P. Compute r as defined in Notation 2.4.3.Step 2. If r, r. Set y = r for all i E A. Return to Step 1.Step 3. If 4 = rj for some 1 i j < n. Set yk = 4 for k E A3 \ A. Add P(Vj)and P(V3) to P. Return to Step 1.Step 4. If r, = r or r for some 1 i < n. Choose k1 and k2 as in Lemma 2.4.7. Setyk = 4 for k e Ak1 U. Add P(Dk1k2)to P. Return to Step 1.Theorem 2.4.14 The above Algorithm computes the nucloelus of a CN game Pc in0(n3) elementary operations4.Proof We start by showing that the Algorithm computes the nucleolus of a CN game.Considering the sequential LP procedure for computing the nucleolus, we conclude thatit is sufficient to show that the proposed Algorithm computes the outcome of SLP(P(D))for any circular system V = (A, V, A, b). Let {y} be the outcome of SLP(F(V)). Weprove this claim by induction on n, the number of elements in V. The claim clearly holdsfor n = 1. Suppose thus that n> 1, and let r* be the optimal value of P(D) as computedby the formula given in Notation 2.4.3.4The elementary (arithematic) operations are: addition, subtraction, multiplication, division andnumber comparison.Chapter 2. Cost Allocation on Circular Networks 56If rK = r, the algorithm will stop after Step 2, since in this case P1 = P(D) has aunique solution, r = r*, Vi E A. Hence, in this case, y = r for all i A.Else the Algorithm reaches Step 3. If r = for some 1 < i < j < n, then, fromTheorem 2.4.13(1), yk = r* for k e A3 \ A, and the constraints induced by J4,A andr xk, for k A3 \ A, are binding at all optimal solutions of P1 = P(V). The latterimplies that, for S = Ak, A, i k j, e(S, x) is constant at all optimal solutions ofP1. Let P2 be the LP problem derived from P1 by setting as equalities all the constraintsinduced by the subsets Ak[A, i k j, and the constraints r xk, k E A3 \ A.Substitute xk = r*, k E A \ A, in P2. Now, to compute y, the outcome of SLP(P1),it suffices to compute the outcome of SLP(P2). After removing redundant constraintsand reordering, P2 can be written as (see system (IV) in the proof of Case 2 of Theorem2.4.8),P2: Max{r: r + x(Ak) < b(Ak) k = 1,... ,i—1r + x(A\Ak) b(A) — b(A) + r*x(A) = b(A)—— + 1)r*r<x ieA;r+x(A)b(J4) k=j+1,...,ri—1r+x(i\)b(Ak)_b(Aj)+r* k=j+1,...,ri—1x(Ak) = b(A) — (AI — AI + 1)r*r<x iElj}.The first four sets of constraints form the constraint system of P(V), and the last foursets of constraints form the constraint system of P(Di) (see Notation 2.4.9 for D and V3).Since both D and D are smaller circular systems than V, by induction, the Algorithmcomputes the outcomes of SLP(F(D:)) and SLP(P(V)). But, since A nA = 0, solvingP2 or any other LP problem encountered in SLP(P2) is equivalent to solving an LPChapter 2. Cost Allocation on Circular Networks 57problem encountered in either SLP(F(V)) or SLP(P(DJ)). So the outcome of SLP(F2)isthe cartesian product of those of SLP(F(VZ)) and SLP(F(D2)) (a more detailed argumentcan be found in Granot, Granot and Zhu [1994bJ).If the algorithm reaches Step 4 at its first run, then r’ = r or rt for some 1 <From Theorem 2.4.13(2), y = r* for i E Ak1 UA, and the constraints induced by Ak1[Aand r x, i E Ak1 U A1, are binding at all optimal solutions of F1. The latter impliesthat, for S = A, A, i = 1,. . . , k1, Ic2,. . . ,n—1, e(S, x) is constant at all optimal solutionsof P1. Let P2 be the LP derived from Fi by setting as equalities all the constraints inducedby subsets S = i = 1,...,k,k2...,n— 1, and r x,i e uA. Substituter*, i E Ak1 uA, in P2. As in Case 2, we need to verify that the Algorithm computesthe outcome of SLP(F2). After removing redundant constraints, P2 can be written as(see system (V’) derived from (V) in the proof of Case 3 of Theorem 2.4.8),F2: Max{r: r + x(A \ A,1) < b(A) — b(Ak1)+ r* k1 < i < kr + x(A \ A) < b(A) — b(A) + r* k1 + 1 <i < k2x(Ak2 \ A1) = b(A) — b(Ak1)— b(ç) + 2r*r < x i E Ak2 \Ak1}.Clearly P2 coincides with P(Vk1k2)(see Notation 2.4.11 for Vk1k2). Therefore, since Vk1k2is a smaller system than V, the Algorithm computes the outcome of SLP(F2)as required.To derive the complexity of the algorithm, observe that at each iteration at least twoconstraints induced by subsets in A are converted into equalities. Therefore, the totalnumber of iterations of the algorithm is bounded by n — 1, where n is the number of nodesin the given circular network. At each iteration, computational effort is dominated bythe computation of and the latter is bounded by 0(n2) elementary operations. Wethus conclude that the nucleolus of a circular network game can be computed in 0(n3)elementary operations.Chapter 2. Cost Allocation on Circular Networks 582.5 Concluding Remarks and ExtensionsIn this chapter, we have considered two cooperative games, 1 and I’, defined on acircular network C. The game 1’ is associated with a travelling server who providesservice to customers located at vertices of C, while 1 is associated with constructinga network that would service all customers in the network. 1 is convex and therefore,by Maschler et al. [1972], its kernel, prekernel and nucleolus coincide. The game 1 isshown not to be convex. Nevertheless, we have demonstrated that the kernel, prekerneland nucleolus of F also coincide. Furthermore, by specializing and refining Kopelowitz’sgeneral approach for calculating the nucleolus of a cooperative game (Kopelowitz [1967])to circular network games, we were able to derive an 0(n3) algorithm which calculatesthe nucleoli of both games.We consider now two possible extensions to our game models. In the first extension,there is an additional cost, pj, for serving customer i, i E N, and the objective is tofind a fair method for distributing both travelling cost (or construction cost) and servicecost among the customers. One can easily show that these modified cost allocationproblems can be formulated as cost games which are strategically equivalent to the CNgames studied above. Therefore, all the results established in this paper are valid for themodified problems with only very minor modifications.In the second extension, we consider the case where the underlying cost structure isnot symmetric, that is, the cost of travelling (or constructing a connection) from nodev to node vj might be different from the travelling or construction cost from v to v.Specifically, we consider a directed circular network, C’, which consists of a directed graph,a cost function and a set of players (customers, users). The directed graph is derivedfrom an undirected cycle by replacing each edge (vi, v) with two directed arcs (vi, v)and (vi, vi), the cost function assigns a nonnegtive cost to each arc, and the set of playersChapter 2. Cost Allocation on Circular Networks 59is denoted by N. As in the undirected case, the arc cost is interpreted as either thetravelling cost or the construction cost.For the travelling service person cost allocation problem defined on a directed circularnetwork, the travelling cost of serving customers in S (S N) is the cost of a minimumcost directed cycle which allows the service person to visit every customer in S. The costgame defined by this cost function (with N being the player set) is denoted by F,.For the construction cost allocation problem defined on a directed circular network,the cost of constructing a connection for all users in S is the cost of a minimum costarborescence (with the root node of the network being the root of the arborescence) whichconnects the root node to all nodes in S. The cost game defined by this cost function isdenoted by F,.It can be shown that F, and F, satisfy all properties we proved above for F andF, respectively. In particular, we have the following result.Theorem 2.5.1 Let F1 and F, be as defined above. Then,(1) Theorem 2.2.8 provides a representation for the core polytopes of F, and F,.(2) The kernel, prekernel and nucleolus for both games coincide.(3) Display (2.6) defines a c-set for the nucleolus of both games.(4) The 0(n3) algorithm developed in Section 5 can be used to compute the nucleoliof F, and I’,.Chapter 3Cost Allocation on Standard Tree EnterprisesIn this chapter we consider cost allocation problems defined on a tree enterprise. Suchproblems were essentially considered by several authors (Bird [1976], Claus and Granot [1976], Megiddo [1978], Granot and Huberman [1981], [1984], Granot and Granot [1992]). A special case, when the tree is a chain,5 was studied by Littlechild [1974],Littlechild and Owen [1977], and Littlechild and Thompson [1977]. Megiddo [1978] produced an algorithm to compute the nucleolus of the tree enterprise6 in 0 (n3) operations, where n is the number of vertices of the tree. By using efficient mergeable heapsGaul [1980] has reduced the number of operations needed for Megiddo’s procedure toO(nlogn).We study here the structure of the nucleolus7 of the class of these enterprises anddevelop an algorithm for calculating it. Namely, we characterize the shape of the nucleolusin terms that are common to all the enterprises, and we develop a process for obtainingthe nucleolus which is based on the division of the “debt” at each vertex between theresidents at the vertex and the arcs leaving that vertex. Each resident is charged his partof the debt and the same part of the debt is added to the cost of each arc leaving thevertex, to form a new debt. All the above is coupled with a process called “eliminationof an arc”, which is performed at some arcs at which a player at the head of an arc is51.e., all arcs are located along a line.6Littlechild [1974], Littlechild and Owen [1977], and Littlechild and Thompson [1977] compute thenucleolus in the chain case.7Since the corresponding games are convex, the nucleolus coincides with the kernel of the treeenterprise.60Chapter 3. Cost Allocation on Standard Tree Enterprises 61charged more than a player at the tail of the arc. The hardest part of our analysis isto determine what arcs should be eliminated. This determination leads to a new andinteresting algorithm to compute the nucleolus, and sheds more light on its structure.The chapter is organized as follows: In section 3.1 we prepare the background andintroduce the necessary notation. In Section 3.2 we set up a system of equations andprove that they determine the nucleolus. One interesting aspect here is the fact that thenumber of equations is 0 (N), rather than 0 (N2), where IN! is the number of players.Section 3.3 provides a characterization of the nucleolus for the class of the tree enterprises.Section 3.4 provides examples which show that the above characterization is not sufficientin order to derive the nucleolus. One has to determine first which arcs to eliminate. Thisis done in Section 3.5, in which we also present our alternative algorithm to compute thenucleolus. In Section 3.6 we show that in some cases further improvements can still bemade in the algorithm. In particular, we show that in the case of a chain enterprise wecan compute the nucleolus in 0 (n) operations.3.1 The tree enterprise and its gamesIn this paper we consider a tree enterprise 8 (V, E, a, b, N). Here (V, E) is a finitedirected tree with vertex set V and arc set E. The set V contains a distinguishednode 0, called the root of the tree.8 The function a : E —* R, called the arc-cost-function, associates with each arc e a cost a(e), interpreted as the cost to construct e.The function b : V —* R, called the vertex-cost-function, associates with each vertexv a cost b(v), interpreted as the cost to construct v. All arcs are directed away fromo and the construction of arcs not in the tree are regarded infeasible (or too costly).Other interpretations are, of course, also possible. N = {1, 2,. . . , n} is a finite set of8By “a directed tree” we mean a directed graph such that to each vertex there is a unique path fromthe root to that vertex.Chapter 3. Cost Allocation on Standard Tree Enterprises 62players, each “located” at (“resides” at, “occupies”) a specific vertex. We denote by vthe vertex occupied by player i and we denote by e the arc entering v. We allow forseveral players to occupy the same vertex, in which case we call them neighbors. Wealso allow non-occupied vertices, in which case we call them public vertices. However,we assume that each player occupies exactly one vertex. Note that a and b may takenegative values, interpreted as proceeds paid to whoever constructs the correspondingarc, or vertex. The objective of the players is to connect themselves to the root (thinkof a cablevision network).With each enterprise E we can associate a cost game I’ (N; c), where, for eachcoalition S we definec(S) = minimal cost needed to join all members of S to the root via a connectedsubgraph of (V,E). (3.1)Remark 3.1.1 If a subgraph contains an arc, it is automatically assumed that it containsalso its endpoints, unless stated otherwise. Thus, when S chooses a subgraph it has topay all the costs of its arcs and their endpoints.Remark 3.1.2 As the costs are the costs to construct the arcs and vertices, if severalplayers “use” an arc, or a vertex, they have to pay only once for the construction.Remark 3.1.3 Since a and b may take negative values, the optimal subgraph for acoalition need not be unique, nor need it be the natural subgraph9 of S. It may beworthwhile for the members of S to construct additional arcs and vertices, in which casewe say that it is worthwhile for S to swallow these additional parts.We shall denote by (V’, Es) the optimal subgraph for coalition S and if there areseveral optimal subgraphs (because of subtrees that cost nothing, if added) then, unless9Namely, the subgraph consisting of those arcs and vertices that must be traversed in order to joinall members of S to the root.Chapter 3. Cost Allocation on Standard Tree Enterprises 63specified otherwise, (V5,Es) will denote the unique subgraph which is maximal underinclusion.Remark 3.1.4 The empty coalition need not have a zero worth. By convention, it hasto pay the cost of the root and, if it is worthwhile, it can swallow a connected subtree,connected to the origin.We shall encounter general trees as described above, but actually the main purposeof this chapter is to determine the structure of the kernel and nucleolus of a game corresponding to a standard tree enterprise, defined subsequently.’°Definition 3.1.5 A tree enterprise = (V, E, a, b, N) is called a standard tree enterpriseif(i) b(v) = 0 for each v in V,(ii) a(e) 0 for each e in E,(iii) The root is not occupied,(iv) All other vertices are occupied,(v) Only one arc leaves the root.Standard trees, in which every vertex except the root is occupied by exactly one playerwere discussed in Megiddo [1978] and Granot and Huberman [1981]. Because b(v) = 0,standard tree enterprises will be denoted = (V, E, a, N). The following theorem enablesus to deduce several facts, known from the literature.Theorem 3.1.6 “The game associated with a standard tree enterprise is a convexgame;’2 i.e.,c(T U {i}) - c(T) <c(S U {i}) - c(S), (3.2)10llenceforth, we shall refer to the kernel/nucleolus of the tree enterprise and mean the kernel/nucleolusof the corresponding game. A similar convention will apply to other solution concepts, such as the core.‘1This theorem was mentioned in Granot and Huberman [1982].12Actually, a concave game. We shall use the terminology which refer to the games (N; —c). Similarly,we shall say “core”, “nucleolus”, etc. instead of “anti-core”, “anti-nucleolus”, etc.Chapter 3. Cost Allocation on Standard Tree Enterprises 64whenever S C T and i T (see Shapley [1971]).Proof Let R be an arbitrary coalition. Because the tree is standard, c(R) is the costof the natural subgraph for R (Remark 3.1.3). We shall denote this subgraph’3 by(VR,ER). Thus, c(R) = a(ER).14 Let S C T and i T. Note that (VTu{i},ETu{i})contains (VT, ET), because in a directed tree, there is a unique path from the root toevery vertex. Similarly, (Vs’u{i}, Esu{i}) contains (Vs, Es). The set ETU{i} \ E’ is theset of additional arcs needed to connect i to the root, given that T is already connectedto the root. Thus,c(T U {i}) — c(T) = a(ET \ Er). (3.3)Similarly,c(S U {i}) — c(S) = a(ESU \ Es). (3.4)Relation (3.2) now follows from (3.1), because a> 0 and \ E D ETU{i} \ Es”.Corollary 3.1.7 A standard tree enterprise has a nonempty core — in fact, a regularcore (Shapley [1971]). Its kernel consists of a unique point in the core and thereforecoincides with its nucleolus.Remark 3.1.8 Of the Conditions in Definition 3.1.5, only the first and the second wereemployed; therefore, Theorem 3.1.6 holds for a wider class of trees, in which the otherconditions may be violated. In fact, it is enough to require that for each vertex v,b(v) + a(e) > 0.Remark 3.1.9 Conditions (iii) and (v) in Definition 3.1.5 are required only for simplification purpose. If the root is occupied, we can always add a zero-cost arc from a new13Contrary to the general convention, when the optimal subgraph is not unique.14a(ER)= e e ER).15Which is also its prekernel (see (1.8) and (1.6)), because a convex game is 0-monotonic (Maschlerand Peleg [1967]).Chapter 3. Cost Allocation on Standard Tree Enterprises 65unoccupied root to this root without changing the characteristic function. If several arcsleave the root, then, as has been observed by Megiddo [1978], the nucleolus is simply thecartesian product of the nucleoli of the various branches emanating from the root 163.2 The equations for the kernel/nucleolus of a standard treeWe shall achieve the task at the head of this section by employing the reduced gameproperty that is satisfied by the prekernel (see, e.g., Peleg [1986]), when applied to certain2-person reduced games. The reduced game property will help us get some equations. Wethen prove that these are sufficient. Later we shall construct an algorithm for computingthe kernel/nucleolus and prove its validity by showing that its outcome satisfies theseequations. (The reduced game property will again be employed during the developmentof the algorithm.)Notation 3.2.1 (1) An ordered pair of players (i,j) is a pair of adjacent’7players i andj, where j follows i. We shall denote by the arc from to v, and also refer to it asthe arc entering v.(2) Let (i,j) be a pair of adjacent players. We denote by B3 the subtree of (V, E)rooted at v and whose vertex set consists of j and all vertices of the tree, such thatthe paths from the root to these vertices contain B3 will be referred to as the branchat v, in the direction of j. We shall also denote by B1 the branch B1, if 1 is locatedsomewhere after j, where j is adjacent to i and is on the path from i to 1. We shall referto B1 as the branch at in the direction of 1.(3) We denote by [or by T1, see above] the subtree rooted at the original root,consisting of v and all the arcs and vertices not in B3. We shall refer to it as the trunk‘6This can also be proved with the he’p of Theorem 3.2.12. Granot and Huberman [1981] proved amore general result.17Namely, occupying the endpoints of an arc.Chapter 3. Cost Allocation on Standard Tree Enterprises 66at v, away from j [from 1].(4) For an arbitrary vertex v, we denote by x(v) the expression >{x: v resides at v}.For a subtree W, we denote by x(W) the expression >{x(v): v is a vertex in W}.(5) For a subtree W, we denote by a(W) the expression {a(e): e is an arc in W}.The following lemma is taken from Granot and Maschler [1991]. Essentially it appearedin Megiddo [1978] and Granot and Huberman [1984].Lemma 3.2.2 If x is a core point of a standard tree enterprise E (Definition 3.1.5), thenx > 0 and (see Notation 3.2.1) for a pair of adjacent players (i,j),x(B) — x(v) — a(B) > 0. (3.5)The left side of (3.5) is the amount the players residing in B3 and not in v pay, underx, above the cost of the branch. Thus, at a core point these players pay at least the costof the branch.The next lemma is a special case of a basic theorem in Granot and Maschler [1994a].Lemma 3.2.3 Let x be a core point of a game I’ corresponding to a standard treeenterprise E = (V,E,a,N). Let (i,j) be a pair of adjacent players and let ({i,j};})be the reduced game’8 on {i,j} at x. Then this reduced game is the game correspondingto the reduced enterprise 8 = (V,E,a,b,{i,j}), where7b(v) = —x(v), if i and j do not reside in v,b(v) = —x(v) + x, if i resides in v, (3.6)b(u) = —x(v) + x, if j resides in v.Remark 3.2.4 Lemmas 3.2.2 and 3.2.3 can be extended to general enterprises (V, E, a, b, N).18The reduced game on a coalition S, at a core point x, of a cost game (N; c) is a game (S; where= min{c(R U Q) — x(Q): Q C Sc}, all R C S.Chapter 3. Cost Allocation on Standard Tree Enterprises 67Thus, the reduced enterprise on {i,j}, at a core point x, is obtained from the originaltree enterprise by removing all the players other than i and j and reducing by x the(originally zero) cost of the vertex where p resides, p i,j. The reduced enterprise is nolonger a standard game.Lemma 3.2.5 Let x be a core point of a standard tree enterprise. Let (i,j) be a pairof adjacent players. The characteristic function of the reduced game on {i, j}, at x, isgiven by’9C{,}(i,j) = x + x,C{,}(i) = xi + x, (3.7)C{,}(i) = min{x1 + xj, a(T) — x(T) + x},= 0(see Notation 3.2.1).Note the simple structure of the reduced game: Two coalitions have the same worthand only two options are available to the third.Proof Both coalitions {i,j} and {j} have to pay the cost of the path from the root toj. By Lemmas 3.2.2 and 3.2.3, it is worth their while to swallow every arc and vertex ofthe tree; hence, their worth is c(N) — x(N \ {i,j}) = x + x3. As to coalition {i}, again,by Lemmas 3.2.2 and 3.2.3, we need to consider only two options: either to swallow v,knowing that xj will not be paid back, and then to continue and swallow all the tree, orswallow only the trunk T3. .Lemma 3.2.6 The prekernel ofa2-person cost game({i,j};c), wherec(ø) = 0, c(i) = a,c(j) = c(i,j) = b, consists of the unique point (, b —Proof The results follow from Equations (1.8) and (1.6). .‘9We sometimes omit curly braces that should surround members of a coalition.Chapter 3. Cost Allocation on Standard Tree Enterprises 68Lemma 3.2.7 Let x be the kernel/nucleolus point of a standard tree enterprise (Definition 3.1.5), then, for every pair of adjacent players (i, i) and every pair of neighbors{p, q}, x must satisfy= a(T) — x(T), if x3 a(T) —= x, if x3 a(T) —= Xq,x(N) = c(N).Proof By Corollary 3.1.7 x is also the prekernel point. The last equation followsfrom (1.8). The previous one follows from the fact that p and q are symmetric players(substitutes) (see Maschler and Peleg [1966]). The first two equations follow from (3.7)and from the reduced game property of the prekernel.2° Indeed, by Corollary 3.1.7,Lemma 3.2.6 and (3.7),f x = [a(T) — x(T) + xj/2, if x + x > a(T) — x(T) + x,( x [x + x]/2, if x + x <a(T) — x(T3)+Equations (3.8) are equivalent to (3.9).Corollary 3.2.8 If (i,j) is a pair of adjacent players in a standard tree game and xsatisfies (3.8), then x2 x.The last conclusion makes sense intuitively. Player j needs all the arcs that are usedby player i and an additional arc. She should therefore pay at least as much as player i.20Namely, if (S; E) is the reduced game on S, at x, where x is a prekernel point then x8is a prekernel point of the reduced game.Chapter 3. Cost Allocation on Standard Tree Enterprises 69Corollary 3.2.9 Equations (3.8) are equivalent to each of the following:= a(T3)— x(Tj) and x3 > a(T)— x(T), if x= xj andx3 <a(T)—x(T1), ifx3(3.10)Xp = Xq,x(N) = c(N).x(B) — a(B) — x(v) and x > x(B) — a(B,)—if x3 xj,= x and x <x(B3)— a(B3)— x(v), if x3 < x, (3.11)Xp = Xq,x(N) = c(N).Proof Suppose (3.8) holds. By Corollary 3.2.8, x < x cannot hold. If x > x then= a(T) — x(T) and x > a(T) — x(T). If x xj then x > a(T) — x(T)would imply x > x, which is a contradiction. Thus, (3.10) is satisfied. We omit theproof that (3.10) implies (3.8). Equations (3.11) follow since e(N) = a(B) +a(T) andx(N) + = x(B) + x(T). .Corollary 3.2.10 Let x be the kernel point of a tree enterprise E. Let (i,j) be a pairof adjacent players (Notation 3.2.1). Then< x(B,)— a(B3)— x(v); (3.12)i.e., a player residing at v never pays a higher amount than the players after him on abranch B3 pay above the cost of the branch.Proof Formula (3.11). .Lemma 3.2.11 A payoff vector x satisfying (3.8), or equivalently (3.10) or (3.11), isnonnegative.Chapter 3. Cost Allocation on Standard Tree Enterprises 70Proof Suppose not, then, by Corollary 3.2.8 x1 < 0, where v1 is adjacent to the rootand the charges zk to players along each path are negative until they start to becomenonnegative, if at all. The players i who pay a negative amount pay less than the costof the arcs e, because the cost function a is nonnegative. As soon as we arrive at a pair(i,j) of adjacent players, in which x, < 0,xj 0, by the first equation of (3.11), theplayers in B3 other than those residing at pay together less than the cost of theirbranch by the amount . This happens on every branch for which x < 0 andx 0 , so altogether, x(N) < c(N), in contradiction with (3.11). .Equations (3.8) (or (3.10), or (3.11)), express the fact that a prekernel point satisfiess(x) = s(x) for each pair of adjacent players and that it is a preimputation in whichneighbors pay the same amount. Equations (1.8), however, require that Skj(x) = slk(x)for each pair of distinct players. Fortunately, for a standard tree enterprise the additionalrequirements are satisfied automatically, as the following theorem shows.Theorem 3.2.12 If x satisfies (3.8) (or, equivalently (3.10), or (3.11)), then x is theprekernel point, and therefore, the kernel/nucleolus point of the standard tree enterprise.For the proof we need the following two lemmas.Lemma 3.2.13 If x satisfies (3.8), then for every k, 1, k 1, there exists a subset S,containing k but not 1, for which sk,1(x) := min{c(R)—x(R): k e R, 1 R} = c(S)—x(S),such that either S = N \ {l}, or (Vs, E5) = Tqi for some player q.Proof Let S be such a coalition, for which 8k1 is achieved. Formally, (Vs, Es) canemploy vertices not occupied by members of S, but since z 0 (Lemma 3.2.11), wemay assume that S contains every player i, when e V’’, with exception of 1, (even ifv1 e Vs). Suppose that q S and let Bqr be a branch not in the direction of 1. Since0 Xq x(Bqr) — a(Bqr) — x(v), we shall diminish the excess if we include Bqr flChapter 3. Cost Allocation on Standard Tree Enterprises 71(V5,Es). Thus, we can assume that S contains every Bqr, not in the direction of 1, if itcontains q. Moreover, if 1 E Vs then (V’s, E5) is the full tree and S = N \ {l}. If 1 V5then, in view of the above, and since (Vs, Es’) is a connected graph, connected to theroot, S must be of the form Tqi for some q in the path from the root to 1.Lemma 3.2.14 Let x satisfy (3.8). Consider a path from some v1 to some whosevertices are V1,V2,...,Vq, Vq+1,...,Vr,Vr+1 and let ml,m2,...,mq,mq+1...,mr,mr+1 beplayers located at the vertices of the path, respectively. Suppose that Xm, = Xm2 = ... =Xmq <Xmq1...Xm,. Xmr+i Under these conditions,a(Tmqmr)— x(Tmqmr) a(Tr,) — X(Tmamq), (3.13)a(Tmqmr)— X(Tmqmr) < a(Tmrmr+i)— X(Tmrmr+i). (3.14)Consequently, the minimum of a(Tmpm÷,) — X(Tmpmp1), 1 p r, along this path isachieved when Tmpmp+i Tmqmq1.Proof Since Xmq < Xmq, it follows from (3.11) that Xmq = 2’(Bmqmr) — a(Bmqmr)x(vm) and Xm1 x(Bmimq)— a(Bmimq) — X(Vml). Thus,a(Tmqmr) — x(Tmqmr) = a(Tm,mq) — X(Tmimq)+a(Bm,mq)— X(Bmimq) + (m1)—[a(Bmqmr)— x(Bmqmr) + x(’omO1= a(Tmimq) — x(Tmimq)+a(Bmjmq)— x(Bmimq) + (m1) + Xmqa(Tmimq) — X(Tmjmq)—Xm, + Xmq= a(Tmimq)— x(Tmimq).This proves (3.13).Chapter 3. Cost Allocation on Standard Tree Enterprises 72Again, by (3.11),a(Tmrmr+i) — X(Tmrmr+i) = a(Tmqmr) — X(Tmqmr)+a(Bmqmr) — x(Bmqmr) + x(vm)—[a(Bmrmr+i) — X(Bmrm +i) + x(vmj]= a(Tmqmr) — X(Tmqmr) — Xmq—[a(Bmrmr+i) — X(Bmrm+i) + x(vmj]a(T)— x(Tmqmr) — Xmq + Xmr> a(T)— X(Tmqmr),because Xmr > Xmq. This proves (3.14)Realizing that Vr could be any vertex beyond Vq and that v1 could be any vertex priorto Vq, we conclude that the minimum of a(Tmpmp+i) — X(Tmpmp1), 1 p r, along ourpath is indeed reached2’when p = q.Proof of Theorem 3.2.12 Let k and 1 be two distinct players. Consider the pathsfrom the root to v’ and to v1 and let m be the last vertex which is common to bothpaths. (We allow m = k, or m = 1.) We wish to determine a coalition S of lowest excessc(S) — x(S), containing k and not containing 1 and to determine its excess skj(x) (see(1.6)). This coalition certainly contains m, so, by Lemma 3.2.13, we can assume that(Vs, Es) is either the full tree, or (V5,Es) = Tqi, where q is a player located on the pathfrom m to 1, mq 1. Let ma := Vm,Vm2,. := v1 be the vertices of the path fromm to 1. If Xm1 = Xm2 = ... = Xm,. < ... x then, by Lemma 3.2.14, we canassume that q = mr. In this case, by (3.10), skl(x) = a(Tmri)— X(Tmri) = Xmr = Xm.If, Xm1 = Xm2 = ... = xl we claim that we can assume that (V5,E5) is the full tree.Indeed, if (V5,E5) = Tqi and we add to it the rest of the tree, then we subtract from21We remind the reader that Tmpm, and Tmpmp+i are the same trunk.Chapter 3. Cost Allocation on Standard Tree Enterprises 73the excess the amount x(Bqi)— a(Bqi) — x(v’) — xl, where x1 was subtracted, because,by definition, 1 S. By (3.11), this expression is not smaller than Xq— Xl 0. Itfollows that skl(x) c(N) — x(T) + Xl = Xl = Xm. We have proved that in both casesSkl(X) Xm. Interchanging k with 1 we obtain that also Slk(X) Xm. This proves that xis the prekernel point and therefore, the kernel/nucleolus point.3.3 The proto-nucleolus and the structure of the kernel/nucleolus of thestandard tree gameIn this section we shall modify the equations (3.11) and show that the modified versionhas a unique solution. We shall then show in what respect the nucleolus differs from thissolution.Theorem 3.3.1 Let 6 be a standard tree game. The system of equationsx = x(B) — a(B3)— x(v), for all pairs (i,j) of adjacent players,Xp = Xq, whenever p and q are neighbors, (3.15)x(N) = c(N),has a unique solution, called the proto-riucleolus of 6.Notation 3.3.2 We assume that the vertices of (V, E) are numbered v0 (the root), v1,v2,v,-, in such a way that the path from the root to a vertex vk in (V, E) does not passthrough a vertex of higher index. Figure 3.1 provides an example of such a labeling.For a vertex v, we denote by dv the number of residents at v plus the number of arcsleaving v. We call dv the degree of v. Clearly, dv 2 if v is not an endpoint and not theroot of (V, E). We denote by i(v) a player residing at v and by e(v) the arc entering v.We shall now describe an algorithm, and later prove that it yields the unique solutionto equations (3.15).Chapter 3. Cost Allocation on Standard Tree Enterprises 74Algorithm 3.3.3 (To calculate the proto-nucleolus) We process all vertices indepth first search order.Step 0. Initialize by charging each resident of v1 the amount Xj(v1) = a(e(vi))/dv1.Proceed to v2, if v2 exists; otherwise terminate.Step 1. Suppose vertex Vh has just been processed. If vertex Vk follows Vh (i.e., (Vh, vk) EE) then process vertex vk by charging each resident of vk the amount [xh+a(e(vk))]/dvk.If, on the other hand, vh is an endpoint of (V, E) then backtrack, to find a vertexvi, which has been processed and which has a follower vertex Vt that has not beenprocessed. Proceed to process vertex Vt by charging each resident of Vt the amount[xi + a(e(vt))]/dVt. If no such vertex Vi exists, terminate.Verbally, by this algorithm each resident of a vertex V 15 charged 1/dy of the “debt”and this same amount is added as a debt to the cost of each arc leaving V. Figure 3.1shows the resulting charges. In this and in the following figures, the residents of a vertexare encircled. The cost of arcs are placed near the arcs and the charges are noted besideeach vertex.V5 7Figure 3.1: Computing the proto-nucleolusProof of Theorem 3.3.1 Denote the expression x(B3)— a(B) — x(V) by s(B) andcall it the surplus of the branch B3 at x; for this is the amount that the players of B3,V45V3 21v13,3V0Chapter 3. Cost Allocation on Standard Tree Enterprises 75not residing at pay under x above the cost of the branch. Let T(v) be the subtreeof (V, E) consisting of v and all the vertices and arcs whose paths from the root do notcross v. Denote a(T(v)) — x(T(v)) + x(v) by deficit T(v) and call it the deficit of T(v)at x. This is the amount that the players of T(v), not residing at pay below the costof T(v); namely, the amount “pushed upward” by these players, that has to be paid inorder to cover the costs of the tree. By (3.15), all the surpluses of the branches rootedat v as well as the amounts charged to the residents of must add up to xdv, because= s(B1) for each branch B3. This sum must cover the deficit of T(v), at x, soxdvz= deficit T(v), (3.16)for each player i. Now, deficit T(vi) a(e(vi)), so Xj() = a(e(vi))/dvi, in accordancewith Step 0 of Algorithm 3.3.3. Consider now a vertex vk that follows a vertex vh.By (3.16),Xj(vk)dVk = deficit T(vk) = a(T(vk)) — x(T(vk)) + x(vk)= a(e(vk)) + deficit T(vh) — Xh[dVh—1]= a(e(vk)) + Xhdvh — XhdVh + Xh= Xh + a(e(vk)),in accordance with Step 1 of the algorithm. .In general, the proto-nucleolus is different from the nucleolus of the game. For example, the charges in Figure 3.1 violate Corollary 3.2.8. Accordingly we shall refer toarcs := (vi, v) for which x > x, as bad arcs. We shall now describe a procedurewhereby one eliminates a bad arc, or, equivalently, one condenses the players residing atthe endpoints of a bad arc.Chapter 3. Cost Allocation on Standard Tree Enterprises 76Definition 3.3.4 (Elimination of an arc/condensation of players) Let (V E,a, N) be a standard tree enterprise and let (i,j) be a pair of adjacent players. By eliminating the arc [condensing the players22 i and j] we mean a process whereby onedeletes the arc, adds its cost to the cost of e, places all the players of v at the vertex vand replaces every arc (vi, vk) by an arc (vi, vk), having the same cost. Formally, afterthe condensation we obtain a standard tree enterprise := (V, E, a, N), where(1) all residents of now reside at(2) V=V\{v}(3) B = E \ ek for all k’s adjacent to j} U{ek: (j, k) were adjacent players in 8},(4)a(e), if e E E fl E, eà(e) = a(e(v)) + a(e(v)), if e = e(v), (3.17)a(ek), if e = ek and (j, k) were adjacent players in 8.Note that if several arcs are eliminated consecutively, the resulting tree does notdepend on the order of elimination. The following theorem and corollary show that ifwe knew in advance which pairs of adjacent players are charged the same amount in thenucleoulus, we could have computed the nucleolus in 0 (n) steps.Theorem 3.3.5 Let I be a fixed set of pairs of adjacent players in a standard tree8 = (V, E, a, N). The system of equations= x(B) — a(B) —for all pairs of adjacent players (i, i), not in I,= xj, for all pairs (i,j) in I, (3.18)Xp = Xq, whenever p and q are neighbors,x(N) = c(N),22We are abusing the language: Actually we condense all the players in v with all the players in v.Chapter 3. Cost Allocation on Standard Tree Enterprises 77has a unique solution. It is the proto-nucleolus of the tree obtained by condensing all thepairs in I.Proof By Theorem 3.3.1, it is sufficient to show that the system (3.18) is replaced byan equivalent system if we eliminate just one arc for (i, i) E I and replace I byI\ {(i,j)}. Indeed, the equations in the last three rows remain unchanged and either thefirst equation, for a particular (i, i) in the first row remains unchanged or the equivalentequation (in view of the last one) x a(T) — x(T) remains unchanged.Theorem 3.3.6 If the proto-nucleolus of a standard tree enterprise is such that xx, whenever (i, j) are pairs of adjacent players, then the proto-nucleolus is the kernel/nucleolus point of the tree.Proof In this case equations (3.11) are satisfied. The result now follows from Theorem3.2.12. .Theorems 3.3.5 and 3.3.6 show that the structure of the nucleolus is the structure of aproto-nucleolus of a related tree, in which some pairs of adjacent players were condensed.Indeed, if I consists of all the adjacent pairs, which receive equal payments in the nucleolus, then, after condensing them, we obtain a tree whose proto-nucleolus charges (inboth games, by Theorem 3.3.5) are nondecreasing along the paths. By Theorem 3.3.6,this proto-nucleolus is the nucleolus of both games.Which pairs should be condensed— that will be studied in Sections 3.4—3.5. Forfuture applications let us draw the following conclusion:Corollary 3.3.7 If I is a subset of pairs of adjacent players that are charged equally atthe nucleolus,23 then the original tree and the tree obtained by condensing the pairs in Ihave the same kernel/nucleolus.23These need not be all the pairs with this property.Chapter 3. Cost Allocation on Standard Tree Enterprises 783.4 ExamplesIt seems from Theorem 3.3.6 and from the discussion in the previous section that it isenough to eliminate bad arcs (i.e., arcs, where x > x in the proto-nucleolus) untilone arrives at a game whose proto-nucleolus is equal to its nucleolus. Unfortunately, thisis not the case! In this section we shall provide some examples which show what can gowrong.Example 3.4.1 Consider the tree enterprise of Figure 3.2 below. The proto-nucleolus of2_2 Q2 02 1 0Figure 3.2: Good arcs may turn out badthis tree enterprise turns out to be (1,2,2,2,2, 1, 1, 1) and arc e56 is bad. By eliminatingthis arc we derive a new tree enterprise, whose proto-nucleolus is (1, 2, 2,2, 1.25, 1.25,1.25, 1.25). Now e43 is bad and after its elimination the proto-nucleolus becomes (1, 2, 2,1.4, 1.4, 1.4, 1.4, 1.4). Now e34 is a bad arc, and after its elimination the proto-nucleolus is(1, 2, 1.5, 1.5, 1.5, 1.5, 1.5, 1.5). Still, arc e23 has to be eliminated and the final outcome is(1, 1, 1, 1, 1, 1, 1, 1). This is the nucleolus of the resulting game (Theorem 3.3.6).It is also the nucleolus of the original game, because it satisfies, e.g., (3.11). This exampleshows that during the process of computing the proto-nucleolus, some calculations mayturn out to be in vain.Chapter 3. Cost Allocation on Standard Tree Enterprises 79Example 3.4.2 Consider the tree enterprise on the top left side of Figure 3.3, in whichwe also placed the proto-nucleolus.80c 104 79.7560 60 6020 4 6 44 19.75 4 7 104.511 60 11 6029 2 3 28 28.5 2 6\ 7” 2860(.j:) 30 1,3 29,299O 11679.9 5 7 104.4 G10211/1260 60 6019.9 4 6 44.4 J85 5/6 42 11/1211 60 \ 60/>—---( 25 5/6,25 5/6,1,2, 28.8,28.8,28.8 25 5/6,25 5/6Figure 3.3: Condensations that failWe see that arcs e12, e13 and e24 are bad. We proceed to eliminate e13 (top right) butstill e12 and e24 remain bad. So, we eliminate e12 (bottom left). Still, e14 is a bad arcand we eliminate it (bottom right). Finally we arrive at the nucleolus of the last tree,Chapter 3. Cost Allocation on Standard Tree Enterprises 80which is 102). This however is not the nucleolus of theoriginal tree, as can be checked by examining (3.9). The nucleolus of the original tree is(25.8,25.8,25.9,25.8,85.8,42.95,102.95). We shall show in the next section that it canbe obtain by an elimination first of e24, followed by an elimination of e12. The reader cantry these eliminations now and see how the previously bad arc e13 now becomes a goodone and should not be eliminated to begin with.This example shows that the order in which elimination of arcs (condensation ofplayers) is made plays an important role. In the next section we shall show that processingthe eliminations of bad arcs in a right order does indeed result with the nucleolus.3.5 An algorithm for computing the kernel/nucleolus of a standard treegameIn this section we characterize those arcs that should be eliminated in order to reachthe nucleolus. We employ our characterization to construct an algorithm for computing the nucleolus, which is different from the one constructed in Megiddo [1978]. Thecharacterization and the algorithm shed more insight into the structure of the nucleolus.Unlike many other algorithms, including Megiddo [1978], that compute the nucleolus of a game via successive minimizations of highest excesses (maximizations of lowestexcesses in a cost game), see e.g. Maschler [1992], our algorithm does nothing of thiskind. It starts with the proto-nucleolus, which is often a kind of approximation of thenucleolus, and it generates k successive cost allocation vectors, k n, the last one beingthe nucleolus.As was shown in the previous section, it all boils down to the question which playersshould be condensed. To make the right decision we shall have to study more deeply theprocess of condensation. The following well known lemma will prove useful.Chapter 3. Cost Allocation on Standard Tree Enterprises 81Lemma3.5.1 If thena1+ a2 + ... + atb+b...+bis a weighted average of the terms--; the weights being b1/ b3, i = 1, 2,. . . , t.Note that the weights are all positive, so, if min1r < max1r, the weightedaverage of r1,. . . , r is strictly between the minimum and the maximum.Notation 3.5.2 For adjacent players (i,j), we denote by h, the expressionh= dv—1’ (3.19)(see Notation 3.3.2 for the definition of dv).Note that h2 is not defined if is an endpoint occupied by a single player; otherwisethe denominator in (3.19) is a positive integer.Lemma 3.5.3 Let x be the proto-nucleolus of a standard tree enterprise. Let (i,j) bea pair of adjacent players, then x is a weighted average of x and h, whenever h3 isdefined.Proof By the construction of the proto-nucleolus,— x + a(e)—dvi— x + a(e)— 1+(dvi_1)’which is the average of x/1 and h, (Lemma 3.5.1). .Lemma 3.5.4 Let 1 be a successor of playeri, who is not a single residend of an endpoint(so that h1 is well defined). Let x be the proto-nucleolus of the standard tree enterprise.Then, xl is a weighted average of the numbers x and the hq ‘s, where q is taken over allvertices intermediate between i and 1, including 1, but not including i.Chapter 3. Cost Allocation on Standard Tree Enterprises 82Proof By induction on the number of arcs from i to 1. The case of one arc was proved inLemma 3.5.3. The passage from t — 1 arcs to t arcs follows from the fact that a weightedaverage of weighted averages is a weighted average. .Based on the previous lemma, we now show that the payments in the nucleolus areweighted averages of known quantities. Again, we shall be concerned with a standardtree enterprise 8 = (V, E, a, N) and its game 1’ = (N; c), but we shall assume thateach endpoint is occupied by at least two players. Such enterprises/games will be calledenterprises/games of class A. For these enterprises h3 is defined for each j. We denoteby 1 a player who resides at v’ — the son of the root.Lemma 3.5.5 Let x and z respectively be the proto-nucleolus and the nucleolus of astandard tree game F belonging to class A. Let i be an arbitrary player. With thisnotation, z is a weighted average of x1 and h3 ‘s, where j is taken over some, possibly all,players who do not reside at v1.Proof By Corollary 3.3.7, the nucleolus z is the proto-nucleolus of some tree game 8,obtained from 8 by condensing arcs of a set I, I C E, where I is the set of pairs ofadjacent players that are charged equally at the nucleolus. For an arbitrary player i,consider the vertex P in and let h be the quantity that corresponds to this player.Let J, J I, be the set of arcs in 8 that collapsed to t3. We consider two cases.Case 1. If i3 is not the son of the root, i.e., if then— a(e(v)) + ZejEJ a(e)dv1+ejj(dj1)’where j is a fixed player in vj, the tail node of e, for each e in J. Therefore, h is aweighted average of h and the hi’s, j E J (Lemma 3.5.1).Case 2. If i5 = ‘ then— a(e(v1)) + ZejEJ a(e)X1— dv’ + ejej@vj — 1)’Chapter 3. Cost Allocation on Standard Tree Enterprises 83which is a weighted average of x1 and the hi’s, J (Lemma 3.5.1).In each case, the proof concludes by referring to Lemma 3.5.4. .For the next lemma we adopt the notation:sx(B1) := x(B) — a(B)— x(v) = a(T)— x(T), (3.20)which holds for an imputation x and a pair of adjacent players (i,j).Lemma 3.5.6 Let x and z be the proto-nucleolus and the nucleolus, respectively, of astandard tree game F belonging to the class A. For any pair (i,j) of adjacent players,(1) z sz(B1), and x =(2) If z, <z3 then z = .sz(Bjj);(3) z1 < x1;(4) If h3 > x1 for all j not residing at v1, then z1 = x1 and z1 = ,sz(B1) for all j’sadjacent to 1.Proof (1) is a reformulation of (3.12) and (3.15). To prove (2) let E’ and I be as in theproof of the previous lemma. From z < z it follows that (vi, I (Corollary 3.3.7)and therefore (i,j) remain adjacent players in E. By (1), above, z = .sz(B), because thecondensations leading to E do not change sz(B). We shall prove (3) by contradiction.Suppose x1 <z1 then, since x1 = a(e(v1))/dv’, it follows from (1) that a(e(v1)) = x1dv <z1dv’ z(vl){sz(Bj):j adjacent to 1} z(N)—c(N)+a(e(v) a(e(v’)). This isa contradiction. Now (4) follows from Lemma 3.5.5. Indeed, z1 is a weighted average ofx1 and some hi’s, j not residing at v1. Thus, h3 x1 for all such j’s implies that z1 x1.But, by (3), z1 x1, so equality holds. To complete the proof, suppose that for some(1,j) in E, sz(B1,) is not equal to z1. Then, since z(N) must cover the cost of the tree,a(e(v’)) = z(v1) + {sz(Bi,j):j adjacent to 1} > z(v’) + z1 ( number of sons of v’) =dv’z1 = dv’x1 = a(e(v1)), which is a contradiction. .Chapter 3. Cost Allocation on Standard Tree Enterprises 84Lemma 3.5.7 Let x be the proto-nucleolus of a standard tree game. If arc is a badarc24 then x > xj > h3. (The last inequality holds oniy if h3 is defined.) Conversely, ifeither x > h, or xj > h2 for a pair of adjacent players then is a bad arc. If e3 is agood arc, then x h. (The last inequality holds only if h3 is defined.) Conversely,if(i,j) is a pair of adjacent players and either x h, or h, then is a good arc.Proof We know that x is an average of x and h,. If e is a bad arc then x > xj,hence, x > h3. Conversely, if x > h3 then x, > xj > h and the same holds if xj > h3.In either case is a bad arc.If e3 is a good arc then x xj, so h3. Conversely, if x, <h3 then x, <x3 <and the same holds if xj h3. In either case is a good arc. •We shall be interested in bad arcs for which h3 is minimal. It will turn out thatthese should be eliminated.Lemma 3.5.8 Let x be the proto-nucleolus of a standard tree game. Suppose(a) arc is a bad arc,(b) h, <h1 for all bad arcs epi.Then:(i) If v’ is a vertex for which xk h, all successors v1 of vV satisfy Xk < h1, providedthat h1 is defined.(ii) If is a vertex for which xk h, all successors v1 of satisfy h1 > h, providedthat h1 is defined.Proof (i) By contradiction. Suppose h1 < xk for some successor 1 of k. Without lossof generality we assume that 1 is a first such successor; i.e.,hq xk for all q strictly intermediate between k and 1. (3.21)241.e., (i,j) are adjacent players and x > x.Chapter 3. Cost Allocation on Standard Tree Enterprises 85Let p be the father of 1. If p = k then x = xk. If p k then, by Lemma 3.5.4, x is aweighted average of xk and the hq’s, for q intermediate between k and p. Thus, x, Xk,because of (3.21). In both cases, therefore, x, Xk. But xk > h1, so x > hi and epi is abad arc (Lemma 3.5.7). Nevertheless, h1 < xk h, in contradiction to the minimalityof h3 (condition (b)).(ii) By contradiction. Suppose h1 < h3 for some successor 1 of k. Again, we canassume that 1 is a first such player; i.e.,hq h for all q strictly intermediate between k and 1. (3.22)Let p be the father of 1. If p = k then x, = xk. If p k then x is a weighted averageof xk and the hq’s, for q intermediate between k and p. Now, xk h3 and hq h, by(3.22), so x, h3. But then x > h1, because h3 > h1, so, by Lemma 3.5.7, e is a badarc and again we get a contradiction to the minimality of h3.Notation 3.5.9 Let (i,j) be a pair of adjacent players in S. Let y be a positive scalar.We denote by S’ (B) an enterprise defined on whose cost function a’ satisfiesa’(e(v)) = a(e(v)) + y and a’(e) = a(e) for all other arces in and whose playerset is the set of the original players in except those residing at v. Denote the gameof this enterprise by y; c’). Note that c’ is a function of y.Lemma 3.5.10 Let z be the nucleolus point of a standard tree enterprise S. Let (i,j)be a pair of adjacent players. The game .sz(Bjj); c’) is the reduced game at z, of theoriginal game, reduced on the player set S consisting of the players in B3 that do notreside at v (see footnote 18).Proof Let R be a subset of S. Denote by TR the subtree of for which c’(R) isattained. Then, c’(R) = a’(TR) = a(TR)+sz(Bjj) = a(TR)+a(Tj)—z(T) = c(RUT)—Chapter 3. Cost Allocation on Standard Tree Enterprises 86z(T) = min{c(RU Q) — z(Q): Q T3)}. The last equality follows from Corollary 3.2.10and Lemma 3.2.11. Indeed, for Q c T3, TRUT, \ TRUQ, is a union of branches Bkj, thesurplus of each, at z, is non-negative, so c(R U Q) — z(Q) c(R U T) — z(T).Corollary 3.5.11 Let (i,j) be a pair of adjacent players in a standard tree enterprise Eand let z be its nucleolus. With this notation, the nucleolus of F’ := sz(B), c’) isthe restriction, zs, of the nucleolus of E to the player-set S consisting of the players inB3 that do not reside at v.Proof F is convex; hence, its nucleolus coincides with its prekernel (Maschler, Pelegand Shapley [1972]). By the reduced game property (footnote 20) and Lemma 3.5.10, zSis the prekernel of F’ and, therefore, its nucleolus, because E’ is also a convex game.Corollary 3.5.12 Let (i,j) be a pair of adjacent players in a standard tree enterprise E.Let x be the proto-nucleolus of E. With this notation, the proto-nucleolus of x, c’)is the restriction of x to the player-set S consisting of the players in that do not resideat v.Proof The proof is a direct consequence of Algorithm 3.3.3. In fact, the computation of the proto-nucleolus of x; c’) proceeds exactly along the same steps as thecomputation of the proto-nucleolus of E, done after reaching vt.The next theorem will identify an adjacent pair (i, j) for which z, = z in the nucleoluspoint z.Theorem 3.5.13 Let x and z be the proto-nucleolus and the nucleolus of a standardtree enterprise of the class A, respectively. If (i,j) is a pair of adjacent players suchthata. is a bad arc,b. h3 is minimal among all h1, for bad arcsChapter 3. Cost Allocation on Standard Tree Enterprises 87then zj = z3.Proof Assume that the vertices of E are indexed so that root, v1,v2,. . . , vk, Vk = v,is the unique path from the root to vertex v1. Since is a bad arc, x > x > h3(Lemma 3.5.7).Consider v1; if x1 < h3 then, by Lemma 3.5.8(i), all successors vi of vertex v1 satisfyx1 < h1. Thus, by Lemma 3.5.6(4), z1 = = .sz(B12). Now, by Corollaries 3.5.11and 3.5.12, the proto-nucleolus and the nucleolus of (B12,z1; c’) are the restrictions ofthe proto-nucleolus and the nucleolus of (N; c) to the player set consisting of playersin B12 that do not reside at v1, respectively. Thus, in order to prove that z = z, itis sufficient to prove it for the enterprise (B12,z1; c’). If in (B12,z1; c’) it happens thatx2 < h, we repeat the above arguments to conclude that z2 = x2 and that we can restrictourselves to (B23,z2; c’). However, since x > h, after k steps, k i, we end up with agame (Bk(k+1), zk; c’) in which xk h3 and for which we have to show that z = z forits nucleolus point z. Thus, without loss of generality, assume that x1 > h. Then, byLemma 3.5.8(u), it follows that at all successors of vj, h1 > h3. By Lemma 3.5.5, z is aweighted average of x1, and some h1’s. Since x1 > h, and h1 h3 at all vi, we concludethat z> h3.Suppose now, by contradiction that z z. Then, by Corollary 3.2.8, z < z, so thatby Lemma 3.5.6(2), z = .sz(B3). Consider now the smaller sub-tree game z; c’) andlet y be its proto-nucleolus, so— a(e(v)) + zy dv—1+1’which is a weighted average of z and h3. Since z > h, it follows that yj < z. Now,by Corollary 3.5.11, the nucleolus of z; c’) is the restriction of z to the players innot residing at v; therefore, by Lemma 3.5.6(1), zj z in contradiction to theassumption that z < z3. Thus z = z3.Chapter 3. Cost Allocation on Standard Tree Enterprises 88Corollary 3.5.14 One can remove from Theorem 3.5.13 the restiction which limits theenterprises to be from class A.Proof Suppose S is such that player k is a sole occupant of an endpoint. Let (p, k)be the pair of adjacent players ending at k. Then e is not a bad arc, because the costfunction is non-negative. Let S be an enterprise obtained from S by deleting the arcand placing player k at the previous vertex, vi’. We claim that S is strategically equivalentto l, because only costs of coalitions containing k were modified by a decrease of a(ek).Since the nucleolus is covariant under strategic equivalence, the two nucleoli are equal,except for zk that has been lowered by a(ek). Now k is no longer a sole occupant of anendpoint.Note that neither h nor x, changed during the passage from S to S because thenumber of arcs emanating from p decreased by 1, but the number of occupants in v°increased by 1. We can repeat this procedure for every player who is a sole occupant ofan endpoint until finally we obtain a game of class A. If the conditions of Theorem 3.5.13hold for the original game, they also hold for the last game so, by the theorem, z = z,because the same equality holds for the last game and player j did not move during theprocess. .We are now in a position to provide an algorithm for computing the nucleolus of astandard tree enterprise.Algorithm 3.5.15 This algorithm uses Algorithm 3.3.3 as a subroutine.Step 1. Compute the proto-nucleolus by Algorithm 3.3.3.Step 2. If there are no bad arcs, stop.Step 3. If there are bad arcs, choose a bad arc for which h, = a(e)/(dV— 1) isminimal and eliminate this arc (ties may be broken arbitrarily)(Definition 3.3.4).Chapter 3. Cost Allocation on Standard Tree Enterprises 89Step 4. Return to Step 1.Theorem 3.5.16 Algorithm 3.5.15 leads to the nucleolus of the original game.Proof At every iteration, the number of arcs is reduced by one, so the algorithm stopsafter at most n iterations. By Corollary 3.3.7, at each iteration we obain a tree enterprise,whose nucleolus coincides with the nucleolus of the previous tree enterprise. This istrue, because we only condense pairs (i, i) of adjacent players for which we know, byTheorem 3.5.13 and Corollary 3.5.14, that the players receive equal amounts in thenucleolus of this tree. Consequently, all iterations yield trees with the same nucleolus.The proof then concludes by observing that when the process terminates there are nobad arcs. Therefore, the proto-niicleolus of the final tree is its nucleolus (Theorem 3.3.6).3.6 Shortcuts in Algorithm 3.5.15: The case of a chain enterpriseMegiddo [1978] provides another algorithm to compute the nucleolus of a standard treegame. His algorithm calls for examinning all closed sets with respect to various veritces.25In contrast, Algorithm 3.5.15 examines only bad arcs with respect to the proto-nucleolus.Thus, for example, if there are no bad arcs, the proto—nucleolus is equal to the nucleolus,and since it is computed in 0(n) steps, we have here a fast method to get to the nucleolus.This situation occurs, for example, in a binary tree enterprise in which each vertex isoccupied by a single player and the costs are nonincreasing along paths.26 In many casesthere are only few bad arcs and only few condensations are required. In general, there isno need to recompute the proto-nucleolus from the beginning, since many of the entries25A set of vertices S is said to be closed wiih respect o a vertex v if it contains v, if every vertex in Sis a successor of v and for each vertex v1 in S, S contains all the vertices on the path from v to v1.26The verification of this fact is straightforward and we leave it to the reader.Chapter 3. Cost Allocation on Standard Tree Enterprises 90x, remain unchanged after a condensation. To identify a bad arc one does not have tocompute x3: It is enough to compare x3 with h3 (Lemma 3.5.7). Sometimes there is evenno need to search for a minimal h3. One such case is a chain27 enterprise, first studied inLittlechild [1974], in Littlechild and Thompson [1977] and in Littlechild and Owen [1977]for the airport game.Algorithm 3.6.1 (Computing the kernel/nucleolus of a chain enterprise)Compute the proto-nucleolus in accordance with Algorithm 3.3.3. Each time you reacha bad arc eliminate it and if this elimination turns an immediate previous arc a bad one,eliminate it too28, etc. By the time you have processed the last arc you have arrived atthe nucleolus.Proof The proof rests on the observation that the order of condensations is not important, as long as one condenses the same players. Now, suppose we proceed by Algorithm 3.5.15, compute the proto-nucleolus and eventually eliminate a bad arc leavingbehind a few other bad arcs. Before any condensation, the proto-nucleolus satisfies= xu + a(e)and = x + a(e) (3.23)dv dvwhere (u, i) is a pair of adjacent players. After the condensation, the resulting vectorsatisfies——x + a(e) + a(e) — x(dv — 1) + xdv——— (3.24)dv + dv — 1 (dvt — 1) + dvand we see that ij= j is a weighted average of x and x, strictly between them, becausex > x, dv > 2 and dv 1. This means that x decreased. Thus, if x_1 <x then, aftercondensation it may happen that x_1 > but if x_1 > x then, after condensation,xj_1 > . Thus, condensation may turn a previous good arc bad, but it can never27A chain is a tree whose arcs are located on a single path.28As we did in Example 3.4.1Chapter 3. Cost Allocation on Standard Tree Enterprises 91turn a previous bad arc good. This feature holds for all previous arcs. Thus, workingin accordance with Algorithm 3.5.15, we are sure that eventually we will eliminate allbad arcs prior to v (and, perhaps, additional arcs). If this is the case, we might as welleliminate a bad arc as soon as it is encountered, because by doing so we obtain a gamehaving the same nucleolus as the original game (Corollary 3.3.7).Theorem 3.6.2 Algorithm 3.6.1 can be performed in 0(n) operations, where n is thenumber of vertices.Proof Passing in the upward direction is carried out in n steps, each of which requiresa number of calculations which is constant, independent of n.29 (formula (3.23)). Eachmove in the downward direction involves a single comparison and possibly an eliminationof an arc. By (3.24), the number of calculations needed for each elimination is a constant,and at most n — 1 arcs are eliminated. If there is a comparison without elimination itis done just once, before proceeding in the upward direction. Thus, all calculations aredone in linear time in n. .29Fractions are maintained by storing separately the nominator and the denominator.Chapter 4Naturally Submodular Digraphs and Their CharacterizationsConsider the following cost allocation problem. A server has to travel in a network,which is depicted by a graph (or digraph), and provides some type of service to potentialcustomers located at vertices (of the network). Assume that the home base of the serveris vertex 0, where the server starts and terminates every service trip, and that the costof each trip has to be shared by all customers the server served during the trip. Theproblem is how the server should allocate the traveling cost to all the customers in a fairmanner. This problem was first studied by Fishburn and Pollak [1983]. Related researchincludes Kuipers [1991], Potters, Curiel and Tijs [1992], Derks and Kuipers [1992], andTamir [1989].In Chapter 2, we considered this problem for circular networks. Therein, we provedthat the associated cost games are convex. In this chapter, we would like to tackle adifferent type of question. Namely, how to characterize all networks, graphs and digraphs,which give rise to convex cost games when the above traveling server’s cost allocationproblem is considered?One motivation for this investigation, which fits in well with the theme of this dissertation, comes from the fact that a convex game has many desirable properties (Shapley[1971], Maschler, Peleg and Shapley [1972]). For example, the core of a convex gameis always non-empty, and its nucleolus coincides with its kernel and with its prekernel.The latter subscribes that if the game associated with a cost/revenue allocation problemis convex then the nucleolus is a prominant choice for the allocation scheme. Indeed,92Chapter 4. Naturally Submodular Digraphs and Their Characterizations 93this is the case in Chapter 2 and Chapter 3. Other examples of convex games includeLittlechild [1974], Littlechild and Owen [1977], Bird [1976], Megiddo [1978], Maschler,Granot, Owen and Zhu [1994], and Granot and Huberman [1982].A naturally submodular graph is, loosely speaking, a graph whose Steiner TSP tour,as a function of subsets of the vertex set of the graph, is submodular regardless of thechoice of the home vertex and arc lengths. There are some known classes of naturallysubmodular graphs. For example, in Herer [1990], graphs that are trees are shown tobe naturally submodular. Herer and Penn [1994] provide several characterizations ofnaturally submodular undirected graphs. Their characterizations are in terms of graphdecomposition and the so-called fixed-order property. However, their characterizationsare not valid for digraphs. In particular, the fixed order property is no longer a characteristic or a defining property for naturally submodutar digraphs.This chapter is mainly concerned with characterizations of all naturally submodulardigraphs and bi-digraphs (see next section for terminology). For each class, these characterizations include one in terms of forbidden digraph configurations and another in termsof graph decomposition. For the class of bi-directed graphs, an additional characterization in terms of the so-called fixed order property is also derived.The plan of this chapter is as follows. In Section 4.1, some notation and preliminariesare given. In Section 4.2, we characterize naturally submodular digraphs in terms offorbidden digraph configurations and graph decomposition. The fixed order property, asmentioned earlier, is not a defining property for naturally submodular digraphs. However,if we restrict our attention to bi-digraphs, a subclass of directed graphs, it becomes againa defining property. In Section 4.3, a characterization of all naturally submodular hidigraphs is given.Chapter 4. Naturally Subniodular Digraphs and Their Characterizations 944.1 Notation and PreliminariesLet G = (V, A) be a digraph and let S be a subset of vertices of V. An S-Steiner tour in Gis a closed directed walk, W, whose vertex set, V(W), contains S. We refer to a V-Steinertour in G as a Steiner tour or simply a tour of C. Observe that, in general, an S-Steinertour W may visit a vertex in V(W) more than once. A complete vertex description orsimply a complete description of an S-Steiner tour W lists the vertices of V(W) as theyare visited by W, and may contain some duplications. A condensed description of Wis obtained from its complete description by eliminating duplicate vertices, and thus isan ordered list of vertices of V(W) in which each vertex appears precisely once. Sinceduplications can be eliminated arbitrarily, one can associate more than one condenseddescription with an S-Steiner tour. In fact, a Steiner tour has a unique condenseddescription if and only if it is a directed cycle.A weight assignment, w, for a digraph C = (V, A) is a mapping w: A —* R, whereR+ is the set of all non-negative real numbers. Within different contexts of applications,weight assignments for G may have different interpretations. For example, in the contextof the traveling salesman problem (TSP), w(e) for arc e is the arc length; in the contextof commodity distribution or flow, w(e) stands for the cost of traveling or sending oneunit of the commodity along arc e. For a weight assignment, w, for C and a fixed locationof a central warehouse at v0, vo E V, one can associate a set function, f: 2V R, whichis defined by assigning every subset 5, S c V, the sum of weights of all arcs in an optimal(S U {vo})—Steiner tour of G (optimal in the sense that the sum of weights is minimalamong all (Su {vo})-Steiner tours). We refer to f as the Steiner tour function associatedwith w and vo. Since weight assignments are nonnegative, their associated Steiner tourfunctions must be monotone.A graph/digraph is said to be naturally submodular if the associated Steiner tourChapter 4. Naturally Submodular Digraphs and Their Characterizations 95function is submodular for any weight assignment and any choice of the central warehouse.Let G = (V, A) be a digraph, w a weight assignment of G, v0 E V a choice of thecentral warehouse, and let W be an optimal Steiner tour through V. The digraph Gis said to have the fixed order property with respect to the weight assignment w and thegiven choice of the central warehouse if for every S ç V there exists an optimal Steinertour W(S) of S U {vo} which visits the vertices in S in the same order as does W. Cis said to have the fixed order property if it has the fixed order property with respect toany weight assignment and any choice of the central warehouse.A digraph is said to be bi-directed if whenever an arc e = (i,j) is in the graph then so isthe reversed arc (j, i). Thus, a bi-directed graph, or a bi-digraph for short, can be derivedfrom an undirected graph by replacing each edge in the graph by two oppositely directedarcs joining the same pair of vertices. A bi-directed cycle is the bi-digraph derived froma cycle; and a bi-directed arc is the bi-digraph derived from i’2, the simple graph withtwo vertices and one edge joining them.4.2 Characterizations of Naturally Submodular DigraphsIn this section we develop characterizations for naturally submodular digraphs. Themain result of this section (Theorem 4.2.10) provides two characterizations for naturallysubmodular digraphs, one in terms of forbidden digraph configurations and the other interms of graph decomposition. We start by presenting some structural results of digraphs.Let G = (N, A) be a digraph and C a directed cycle in G. C is said to be a maximalcycle of G if there exists no other dicycle C’ in G such that V(C) C V(C’). We definetwo simple digraphs, F1 and F2, as shown in Figure 4.1 below.Lemma 4.2.1 Let G be a digraph which does not contain a subdivision of F1, and letC, C1 and C2 be maximal directed cycles of G. Then,Chapter 4. Naturally Submodular Digraphs and Their Characterizations 96Figure 4.1: The Digraph F1 and F2(1) For any two distinct vertices, v1, v2 E V(C), there does not exist a directed path,F, in G of length 2 or more connecting v1 and v2 which does not use any other verticesin C other than v1 and v2.(2) Either V(C1) = V(C2) or V(C1) fl V(C2)I 1.Proof (1) Suppose, on the contrary, that there exists a directed path F of length, say2, connecting two vertices v1 and v2 of C which does not use any other vertices in C.Assume first that v1 and v2 are adjacent in C, say (vi, v2) is an arc in C. Since, byassumption, C is a maximal cycle of G, it follows that P must be a directed path fromv2 to v1. Hence, since C contains at least 3 vertices, G must contain a subdivision of F1(see Figure 4.2(a)). If v1 and v2 are not adjacent in C, then G contains a subdivisionof F1 regardless of the direction of F (see Figure 4.2(b)). So in either case we reach acontradiction.(2) Suppose V(C1) V(C2) and V(C1) fl V(C2) > 2. Since both C1 and C2 aremaximal, it follows that V(C1) V(C2). Thus, there exists a vertex v such that vV(C1) and v V(C2). Let F be the section of C1, say from v1 to v2, which containsv and V(F) fl V(C2) = {v1,2}. Such a F clearly exists since V(C1) fl V(C2) 2.Moreover, since v E V(P), by using F and C2, we obtain a contradiction to the first partof the lemma. Hence, V(01) fl V(C2) 1 as claimed.Chapter 4. Naturally Submodular Digraphs and Their Characterizations 97V2(a) (b)Figure 4.2: The Layout of C and PLet C be a cycle of a digraph G. The subgraph of C induced by C, denoted by G(C),is the subgraph of G induced by the vertex set V(C).Lemma 4.2.2 Let G be a strongly connected digraph which does not contain a subdivision of F1. Let C= {C1,. . . , C, } be the family of all maximal cycles of G. Then, C isa 1-sum of all subgraphs induced by cycles in C.Proof This lemma follows from the following three assertions:(1) UG(C) is a 1-sum of G(C1),.. . , G(Ck);(2) V(UG(C)) = V; and(3) A(u1G(C)) = A.Since C is strongly connected, each vertex (resp., arc) of G belongs to at least onemaximal cycle of G. Thus (2) and (3) follow. We prove (1) by induction on k. For k = 1,(1) is trivial. Assume k > 1 and that (1) holds as long as the total number of maximalcycles is less than k. Consider G1 = UL2(G(C)). From the induction hypothesis, eachconnected component of C1 is a 1-sum of some of the G(C)’s. To show that G is a 1-sumof G(C1),. . . , G(Ck), it remains to show that G(C1) touches each connected componentof G1 at a unique vertex. To that end, suppose, on the contrary, that G(C1) touchesChapter 4. Naturally Submodular Digraphs and Their Characterizations 98some component of G1 at two distinct vertices, say, v1 and v2. From Lemma 4.2.1(2),v1 and v2 must be on two different maximal cycles, say, C and C, respectively. Now,there is a directed path P1 from v1 to v2 in G(C1), and a directed path P2 from v2 to v1in the connected component of G1 containing G(C) and G(C). Let C’ be the directedcycle consisting of Pi and P2. Now, C’ must be contained in a maximal cycle of G.However, C’ can not be contained in any cycle in {C2,. . . , Ck} since v1 and v2 are ontwo different cycles, nor can it be contained in C1 since P2, which connects two verticeson two different cycles, must contain at least one other vertex not in C1. Contradiction,and the proof follows. .Lemma 4.2.3 Let G be a digraph which does not contain a subdivision ofF2. If C is adirected cycle in C, then G(C), the subgraph induced by C, is outerplanar with C beingits outer cycle, i.e., on the boundary of its outer region.Proof Draw G(C) in such a way that C is on the outer boundary. (Note we do notmean a planar embedding of G(C) at this point, but at the end of this proof it willbecome clear that such a drawing of G(C) is indeed a planar embedding of G(C).) Tocomplete the proof, it suffices to show that there do not exist four vertices v1, v2, v3 andv4 on C, which are traversed by C in the order listed and such that both pairs v1 and v3,and v2 and v4 are each connected by an arc. The latter would not occur since otherwiseG(C) would contain a subdivision of F2, which contradicts our assumption. .Two directed cycles C1 and C2 in a digraph G, with V(C1) V(C2), are said to bein harmony if they visit their common vertices in the same order. A digraph G is saidto be harmonic if it does not contain two cycles which are not in harmony. Note that ahi-directed cycle is harmonic because the only two cycles (of more than two vertices) itcontains have the same vertex set.Chapter 4. Naturally Submodular Digraphs and Their Characterizations 99Lemma 4.2.4 If a digraph G does not contain a subdivision of F1 and F2, then everydirected cycle C of G induces a harmonic digraph.Proof Let C be any directed cycle in G. From Lemma 4.2.3, G(C) is an outerplanargraph with C being its outer cycle. Hence to prove G(C) is harmonic, it is sufficient toshow that every other directed cycle of G(C) is in harmony with C. Suppose, on thecontrary, that a cycle C1 in G(C) is not in harmony with C. Let V(C1) {v1,.. . , vk}and assume that C1 visits them in this given order. Since G(C) is outerplanar and acycle does not cross itself, C must traverse all vertices of V(C1) in a reversed order. Now,since V(C) V(C1) and V(C1) C V(C), there exists v e V(C) such that v V(C1).Without loss of generality, let us assume that v is on the segment of C which travelsfrom v2 to v1. Hence the layout of C and C1 is as depicted in Figure 4.3 below. But,CFigure 4.3: The Layout of C and Cclearly, the digraph in Figure 4.3 contains a subdivision of F1, which is a contradiction.Therefore, G(C) is harmonic as claimed. .Upon combining Lemma 4.2.2 and Lemma 4.2.4, we have the following theorem.Theorem 4.2.5 Let G be a strongly connected digraph. Then, G does not contain asubdivision ofF1 and F2 if and only if G is a 1-sum of harmonic digraphs, each of whichis outerplanar with a directed cycle on its outer boundary.Chapter 4. Naturally Submodular Digraphs and Their Characterizations 100Proof A harmonic outerplanar digraph which has a directed cycle on its outer boundarydoes not contain a subdivision of F1 and F2. Thus, the sufficiency follows, since if eachcomponent of a 1-sum does not contain a subdivision of F1 and F2, neither does the1-sum itself. The necessity is implied by Lemmas 4.2.2 and 4.2.4. .In the next three lemmas, we restrict our attention to an outerplanar digraph G whichhas a directed cycle C on its outer boundary. Lemma 4.2.6 is a structural result for G,while Lemmas 4.2.7 and 4.2.8 study the structure and properties of G when it is furtherassumed to be harmonic. For that purpose we need to introduce some notation. Namethe vertices of G, 1, 2,. . . , n, in the order the directed cycle C traverses them. For anyclosed directed walk, W, in G denote by Dw the lexicographically minimum condenseddescription of W. Then, W is called an ordered closed di-walk if vertices of V(W) appearin an increasing numerical order in Dw, and otherwise it is called an unordered di-walk. Adirected cycle in G is called a reversed cycle if it visits its vertices in a reversed numericalorder. Thus, if C is a reversed cycle and V(C) = {i1,... ,ik}, i1 < i2 < < i, then= (ii,ik,ik_i,. . . ,i2). Clearly, a reversed cycle contains at least three vertices.Suppose W is a directed walk and W1 and W2 are two non-overlapping segments ofW which have the same origin and terminus. Then, a swap of the segments W1 andW2 in W will result with another directed walk of the same length as W. A directedwalk in G is said to be inherently unordered if each directed walk derived from it bysegment swappings is unordered. As a further notational convention, for i < j we let[i,j]= {i,i+1,...,j—1,j}.Lemma 4.2.6 Let G be an outerplanar digraph with a directed cycle C on its outerboundary. Then, if G contains an inherently unordered closed di-walk, it contains areversed cycle.Proof Let W be the class of all inherently unordered closed di-waiks in G which are ofChapter 4. Naturally Submodular Digraphs and Their Characterizations 101the shortest graphic length. Let T E ¾) be such that DT is lexicographically smaller thanany other Dw, W € ¾). Suppose V(T) = {i1,. . . , ik} and i1 < i2 < ••. < ij. Startingfrom the vertex i1 and following the track of T, let i be the first vertex on T such thatthe next vertex visited by T is not i1, but rather a vertex t, t > .s + 1. Note that sucha vertex i5 does exist, since otherwise T must be ordered. Hence, (i5, t) is an arc in Cas shown in Figure 4.4 below. Since i1 < i2 < < i,, the first s entries in DT areii,... ,is.Figure 4.4: The Layout of C and TWe will show that T is a reversed cycle. Since T is assumed to be an inherentlyunordered closed di-walk of the shortest graphical length, to prove that T is a reversedcycle it suffices to show that T contains a reversed cycle. Now, if T contains a directedwalk P of length 2 or more from t to i5 such that all its internal vertices are in [i5+1,it_i],then clearly {(i5, t)} U P contains a reversed cycle. In the following, we suppose T doesnot contain such a directed walk, and complete the proof by showing that all other casesresult in a contradiction. We consider two cases, depending whether i is the (s+1)thentry in DT.Case 1. is the (.s+1)th entry in DT.Let P be the segment of T which starts with the vertex i5 and the arc (i3, t) and endsat i. We first observe that P1 must be a directed path. Otherwise, by deleting arcsiiChapter 4. Naturally Submodular Digraphs and Their Characterizations 102from Pi one can obtain a graphically shorter directed path from i5 to ii, and thus derivefrom T another inherently unordered closed di-walk which is graphically shorter than T,which is a contradiction. So the layout of P should be as shown in Figure 4.5(a). We1s-i-1Figure 4.5: The Layout of P1claim that in this case A(T) does not contain any arc which starts at i. and terminatesat some vertex in [ii,it_il. Indeed, suppose (i5,x) e A(T) for some x e [i9÷i,it_il. SinceG is outerplanar, x must be on P1. Then, replacing the segment of P1 from i5 to x by(i5, x) will shorten F1, and thus shorten T. This is a contradiction since the shortened Tis still inherently unordered.Therefore, all vertices in [i1,it_il, which are visited by T, must be visited by segmentsof T which are closed walks based at t and use only vertices in [i1, itl. The other verticesin [t+i, ikl visited by T must be visited by either segments of T which are closed walksbased at t or by a directed walk from t to i1, none of which uses vertices in [i1,it_il.Now, if T visits some vertex in [t+i, ikl before it visits some vertex in [i1,it_il, thenby swapping appropriate directed walks based at t, one can derive from T a tour ofthe same graphic length but with lexicographically smaller condensed description. Thisimplies that, by the choice of T, we can assume that it visits all vertices in [i1, it_ilbefore it visits any vertex in [t+i, ikl. Let W1 be the segment of T starting from tit(a) (b)Chapter 4. Naturally Submodular Digraphs and Their Characterizations 103when it is about to visit a vertex in [i1, it_il, ending at t when it finishes visiting allvertices in [i3÷1,it_i]. Let W2 be the remainder of T after W1 is removed. Clearly, W2 isa closed directed walk as well, and V(W2)= ([i1, is] U [it, ik]) fl V(T). Since both W1 andW2 are graphically shorter than T, by our assumption that T is inherently unorderedwith the minimum graphic length, they both must be ordered tours after some segmentswappings. But, since W1 and W2 have only one vertex, j, in common, it follows that Tis also ordered after some segment swappings. This is a contradiction.Case 2. i1 is not the (s+1)th entry in DT.Let ii,, p > s + 1, be the next vertex in DT after i. Clearly, p t. Let P1 be thesegment of T starting with i5 and the arc (i3, t) and ending at i. As in Case 1, P1 mustbe a directed path as shown in Figure 4.5(b), and A(T) does not contain any arc startingat i5 and terminating at a vertex on P1 other than t.Now, let Wi be the segment of T starting from t when it first visits t, and endingat t when it is about to visit some vertex outside of [i1, it_i] (recall that T is a closedwalk, and thus has to return to i1). W1 is a closed di-walk (possibly of graphical length0), and is graphically shorter than T, so it must be an ordered di-walk after, possibly,some segment swappings. This implies that i1 is not on W1. Otherwise, one can deriveby segment swappings a closed di-walk from T which has a condensed description like(i1,....), and which contradicts our assumption that DT is lexicographicallyminimum.Since i1 is on T, T must visit it. Since G is outerplanar and T does not containdirected walks from t to i whose internal vertices are all in [i1, it_i], there are onlythree ways for T to visit i51. Namely, either through a closed directed walk W2 based ator through a directed walk P2 starting at i5 and ending at a vertex x on P1, or througha closed directed walk W3 based at i5. By swapping W1 and W2 in the first case, andswapping P2 and the segment of P from i5 to x in the second case, and swapping W3 andChapter 4. Naturally Submodular Digraphs and Their Characterizations 104the empty segment of T (i.e., of graphical length 0) from i. to i5 after T first visits i3 inthe third case, one produces a tour of the same length as T but with a lexicographicallysmaller condensed description. This again is a contradiction to the choice of T. .Lemma 4.2.7 Suppose a digraph G is harmonic and outerplanar with a directed cycleC on its outer boundary. Then, the following holds:(1) If there does not exist in G an optimal Steiner tour of V(G), for some weightassignment and some choice of the central warehouse, which traverses vertices in thesame order as C does, then G is a bidirected cycle.(2) G has the fixed order property.Proof Assume, without loss of generality, that vertex 1 is the chosen central warehouse,since a tour of V(G) can start at any vertex of G.(1) Suppose G does not have an ordered optimal Steiner tour of V(G) for someweight assignment. Then, C contains inherently unordered tours. From Lemma 4.2.6,G contains a reversed cycle T. Thus, since G is harmonic, V(T) = V(G). Therefore, Gmust be a bi-directed cycle since it contains both an outer cycle and a reversed cycle.(2) A hi-directed cycle clearly has the fixed order property. So, we only need toconsider the case where G is not a hi-directed cycle. From the first part of this lemma,G has an ordered optimal tour of V(G) for any weight assignment and any choice of thecentral warehouse. Thus, to prove that G has the fixed order property, it suffices to showthat C has an ordered optimal S-Steiner tour for any proper subset S of V(G) and forany weight assignment. However, this follows from Lemma 4.2.6. Indeed, if G does nothave an ordered optimal S-Steiner tour for some S C V(G), then G contains inherentlyunordered tours. Thus, as in (1), Lemma 4.2.6 implies that G contains a reversed cycle,which contradicts the assumption that C is harmonic and is not a hi-directed cycle. .Chapter 4. Naturally Submodular Digraphs and Their Characterizations 105Lemma 4.2.8 Let G be a harmonic and outerplanar digraph with a directed cycle C onits outer boundary. Then G is naturally submodular.Proof Let f be the Steiner tour function associated with some (arbitrary) weight assignment and some (arbitrary) choice of the central warehouse. To prove that G isnaturally submodular, we need to show that f is submodular. That is, prove that forany S,T ç V(G),f(S n T) + f(S U T) f(S) + f(T). (4.1)As in the proof of Lemma 4.2.7, assume that vertex 1 is chosen to be the centralwarehouse. For any 5, T V(G), let m(S, T) = min{S \ T, T \ SI}. We prove thatinequality (4.1) is valid for any 5, T V(G) by induction on m(S, T). If m(S, T) = 0,that is either S ç T or T c S, then f(S fl T) + f(S U T) = f(S) + f(T). So, supposethat inequality (4.1) is valid for m(S, T) < k (k > 1), and let 5, T C V(G) be such thatm(S, T) = k. Assume S \ T = k, and i E S \ T. We consider two cases.Case 1. f(T U i) = f(T).LetT1 =TUi. Clearly,SflT=(SflT)Ui,SU —_SUT,rn(S,Ti)=k—1,andthus, by the inductive hypothesis, inequality (4.1) is valid for S and T1. Hence,f(S fl T) + f(S U T) f(S fl T1) + f(S U T1), since f is monotonicf(S) + f(T1), since inequality (4.1) is valid for S,T1= f(S) + f(T) since f(T1) = f(T).Case 2. f(T U i) f(T).In this case, i is not on any optimal (T U {1})-Steiner tour in G. Let W(S) (resp.,W(T)) be an optimal (S U {1})-Steiner tour (resp., (T U {1})-Steiner tour) in G. Further, let s = max{k E V(W(T)): k < i}, t = min{k E V(W(T)): k > i}, I ={k V(W(S)): s < k < t}, .s’ = max{k V(W(S)): k < j for all j I} andChapter 4. Naturally Submodular Digraphs and Their Characterizations 106min{k E V(W(S)): k > j for all j E I}. All these constants are well-defined ifwe assume n +1 = 1. Assume i1 and i2 are the maximum and the minimum elementsof I, respectively. Clearly, s’ s < ii i2 < t t’. Further, we claim that, withoutloss of generality, we may assume that s,t E T, s’, t’ E S and I c S. To see this, let5’ = S U I U {s’, t’} and T’ = T U {s, t}. Clearly, f(S’) f(S) and f(T’) = f(T). Thus,f(S fl T) + f(S U T) f(S’ fl T’) + f(S’ U T’), since f is monotone< f(S’) + f(T’), if inequality (4.1) is valid for 5’ and T’= f(S) + f(T), since f(S’) = f(S), f(T’) = f(T),which implies that establishing inequality (4.1) for S’ and T’ would imply that it is alsovalid for S and T.Now, let PS(5!,i1), pS(1,i2), and F9(i2,t’) be the segments of W(S) from s’ to i1,from i1 to i2, and from i2 to t’, respectively. Let PT(s,t) be the segment of W(T) froms to t. Further, let F0Pt(3,i1), poPt(j2,t) and P0Pt(s, t’) be shortest directed walks in G(with respect to the given weight assignment) from s to i1, from i2 to t and from s’ tot’, respectively. Since C is outerplanar, and since s’ s < i1 < t, pS(5.,i1) must crosspT(s,t) at some vertex. Suppose F(s’,ii) crosses PT(s,t) at vertex k1. Since V(W(S))contains no vertices in [s’ + 1, i1—1] U [i + 1 t’—1], it follows that either k1 < s’ ork1 t’. Thus, either k1 <i2 <t t’ or i2 <t t’ k1. In either case, again since G isouterplanar, P’(i2,t ) must cross the (ki,t)-segment of PT(s,t) at some vertex, say, k2.Observe that one can get a directed walk from s to i1 by joining the (s, ki)-segment ofpT(s,t) with the (ki,ii)-segment ofF9(s’,i1) a directed walk from i2 tot by joining the(i2,k)-segment of FS(2,t’) with the (k2, t)-segment of FT(3,t), and a directed walk froms’ to t’ by joining the (s’, ki)-segment of FS(3f,1)with the (k1,2)-segment of pT(s,t)and with the(k2,t’)-segment of pS(i2,t). Thus, if we use w(P) to denote the total arcChapter 4. Naturally Submodular Digraphs and Their Characterizations 107weights of all arcs in a walk F, we should have the following inequality,w(F°’(s, i1)) + w(P°t(i2,t)) + w(P°t(s’, t’)) <w(PS(s, i1)) + w(FS(i2,t’)) + w(PT(s, t)). (4.2)Next, let S1 = S\I. We have SflT = S1flT, SUT =S1UTUI, and S\T (S1\T)UI.Therefore, since G has the fixed order property (Lemma 4.2.7), we have,f(S) = f(S1) + w(FS(s, i1)) + w(Fs(i1,i2)) +w(FS(i2,t’)) — w(F°t(s’, t’)), (4.3)f(S U T) = f(S1 U T) + w(F°t(s,i1)) + w(Fs(ii, i2)) +w(F°t(i2,t)) — w(FT(s, t)). (4.4)Thus,f(SnT)+f(SUT)= f(S fl T) + f(S1 U T) + w(P°t(s,i1)) + w(FS(ii, i2)) + w(P°(i2,t))_w(PT(s, t)), by equation (4.4) and since S fl T = S fl Tf(Si) + f(T) + w(F°t(s,i1)) + w(Fs(i1,i2)) + w(F°t(i2,t))_w(FT(s, t)), since, by induction, inequality (4.1) is valid for S and Tf(Si) + f(T) + w(Ps(s, i1)) + w(Ps(ii, i2)) + w(FS(i2, t’))—w(P°t(8’,t’)), by inequality (4.2)= f(S)+f(T), byequation(4.3).This completes the inductive proof of the lemma. .Lemma 4.2.9 A 1-sum of two naturally submodular digraphs is also naturally submodular.Chapter 4. Naturally Submodular Digraphs and Their Characterizations 108Proof Let G1 and G2 be two naturally submodular digraphs, and let G be a 1-sum ofG1 and G2 with v being the link vertex. For any weight assignment, w, and an arbitrarychoice of the central warehouse, say v0, let f be the associated Steiner tour function. Ifv0 is in G1, then for any S C V,f(S)=f1(SnV+f2,where fi (resp., f2) is the Steiner tour function of G1 (resp., G2) associated with theweight assignment w and the central warehouse being located at v0 (resp., v). Similarly,if v0 is in G2, then,f(S) =f(SnV1)+f(S2,where f (resp., f) is the Steiner tour function of G1 (resp., G2) associated with theweight assignment w and the central warehouse being located at v (resp., vo). Therefore,f is submodular since fi, f2 and f, f are all submodular by assumption. .Now, we are ready to present and prove the main result of this section.Theorem 4.2.10 Let C be a strongly connected digraph. Then, the following are equivalent:(1) G is naturally submodular;(2) G does not contain a subdivision ofF1 and F2;(3) G isa 1-sum of harmonic digraphs, each of which is outerplanar with a directedcycle on its outer boundary.Proof To show that (1) implies (2), we only need to verify that both F1 and F2 arenot naturally submodular. To that end, consider the weight assignments for F1 and F2given by the numbers beside the arcs in Figure 4.6 below. Assume that for both graphsvertex 1 is chosen to be the central warehouse, and let f and f2 be their associatedChapter 4. Naturally Submodular Digraphs and Their Characterizations 109Figure 4.6: F1 and F2 are not naturally submodularSteiner tour functions, respectively. Let S = {2, 3} and T = {3, 4}. It is easy to checkthat1(S)=fTSflT)=3,f1(SUT) z-_6,f(S)=fTSflT)=3 andf2(SUT)=4. Then,(SnT)+fuT)=9>f+fT)—_6andf2(SflT)+fuT)—7>2(S)-i-fT =6.Therefore, both f and f2 are not submodular, which implies that both F1 and F2 arenot naturally submodular.Further, by Theorem 4.2.5, (2) implies (3), and by Lemmas 4.2.8 and 4.2.9, (3) implies(1).4.3 Characterizations of Naturally Submodular Bi-digraphsIn this section, we provide characterizations for naturally submodular bi-digraphs. Recall that bi-digraphs are digraphs with some symmetry restrictions on arcs containedtherein (see definition in §4.1). This additional restriction turns out to simplify thecharacterization of naturally submodular bi-digraphs.Chapter 4. Naturally Submodular Digraphs and Their Characterizations 110Theorem 4.3.1 Let G be a bi-digraph. Then, G is naturally submodular if and only ifG is a 1-sum of hi-directed cycles and hi-directed arcs.Proof The proof follows from Theorem 4.2.10 and the fact that a harmonic outerplanarbi-digraph with a directed cycle on its outer boundary is either a hi-directed arc or ahi-directed cycle. .Before proceeding to provide a second characterization of naturally submodular hidigraphs, consider an example of a bi-digraph which is not naturally submodular.Example 4.3.2 Consider the bi-digraph F3 defined in Figure 4.7 below. The numbersbeside the arcs indicate a weight assignment and node 0 is chosen to be the centralwarehouse. Let f be the associated Steiner tour function, and let S = {1, 2} and T =Figure 4.7: A bi—digraph which is not naturally submodular{2, 3}. It can be easily verified that f(S) = f(T) = f(S fl T) = 3 and f(S U T) = 4.Therefore,f(S U T) + f(S n T) = 4+3> f(S) + f(T) = 6,which implies that F3 is not naturally submodular.Furthermore, we can prove the following.Chapter 4. Naturally Submodular Digraphs and Their Characterizations 111Theorem 4.3.3 Let C be a strongly connected bi-digraph. Then, the following areequivalent:(1) G does not contain a subdivision ofF3;(2) G is a 1-sum of hi-directed cycles and hi-directed arcs;(3) G has the fixed order property.Proof A bi-digraph contains a subdivision of F3 if and oniy if it contains a subdivisionof F1. Thus, from Lemma 4.2.2, if G does not contain a subdivision of F3, then it is a1-sum of subgraphs (of G) induced by maximal (directed) cycles of C. But, a subgraphinduced by a directed cycle in a bi-digraph is either a bi-directed arc, or a hi-directedcycle, or a hi-directed graph which contains a subdivision of F3. Therefore, (1) implies(2).The implication that (2) implies (3) follows from the following two observations: First,hi-directed cycles and hi-directed arcs have the fixed order property. And second, a 1-sumof digraphs which have the fixed order property also has the fixed order property.Finally, to show (3) implies (1) it is sufficient to verify that F3 does not have the fixedorder property. Indeed, with the indicated weight assignment and with node 0 as thecentral warehouse, 0 —* 1 —* 2 —* 3 —* 0 is an optimal Steiner tour of V = {0, 1, 2, 3}.But, it is easy to verify that there is no optimal Steiner tour for {1, 2} which visits nodes1 and 2 in this given order. .By combining Theorems 4.3.1 and 4.3.3, we have the following corollary.Corollary 4.3.4 Let G be a bi-digraph. Then, the following are equivalent:(1) G is naturally submodular;(2) 0 does not contain a subdivision ofF3;(3) 0 is a 1-sum of bi-directed cycles and hi-directed arcs;(4) 0 has the fixed order property.Chapter 4. Naturally Submodular Digraphs and Their Characterizations 112Remark 4.3.5 From Lemma 4.2.7 and Theorem 4.2.10, we observe that a naturallysubmodular digraph necessarily has the fixed order property. But, unfortunately, thereverse does not hold. Indeed, the digraph F2 has the fixed order property for any weightassignment and any choice of the central warehouse. But, as shown in the proof ofTheorem 4.2.10, F2 is not naturally submodular.Chapter 5The Characterization Set for the NucleolusThe definition of the nucleolus of a cooperative game in characteristic function formentails comparisons between vectors of exponential length. Thus, if one attempts tocompute the nucleolus by simply following its definition, it would take an exponentialtime. However, it is well known that one can compute the nucleolus of many classes ofgames in polynomial time. Indeed, let n denote the total number of players in a game.Littlechild [1974] has developed an 0(n2) algorithm for computing the nucleolus of theairport game, Granot and Granot [1992] have developed a strongly polynomial algorithm for computing the nucleolus of fixed cost spanning network games, Solymosi andRaghavan [1994] have an 0(n4) algorithm for computing the nucleolus of an assignmentgame, Derks and Kuipers [1992] and Granot, Granot and Zhu [1994a] have developed0(n5) and 0(n3) algorithms, respectively, for computing the nucleolus of certain routinggames, and Megiddo [1978] and Granot, Maschler, Owen and Zhu [1994] have developedstrongly polynomial algorithms for computing the nucleolus of tree games. Most of theabove efficient algorithms for computing the nucleolus are based on the observation thatthe information needed for completely characterizing the nucleolus for some classes ofgames is much less than that dictated by the definition of the nucleolus.In this chapter, we formalize the above approach for general cooperative games. Weprovide a uniform scheme, or a general approach, for seeking efficient algorithms for computing the nucleolus. The concept of a characterization set (see Section 5.2 for definition)113Chapter 5. The Characterization Set for the Nucleolus 114embodies the notion of ‘minimum’ relevant information needed to characterize the nilcieolus of a class of games. The notion of a sequential linear programming (LP) process (seeSection 5.1 for definition), which is a formalization of Kopelowitz’s method (Kopelowitz[1967], Maschler, Peleg and Shapley [1979]), provides a generic algorithm for computingthe nucleolus. The input of a sequential LP process is a characterization set and a description of the cost function of a cost game. Its output is the prenucleolus/nucleolus ofthat game. The size of the first LP problem in a sequential LP process is proportionalto the size of the characterization set. Therefore, to develop an efficient algorithm forcomputing the nucleolus of a game, one attempts to find the smallest characterizationset for the nucleolus. Additional efficiency can be sometimes attained by making use ofthe structure of the characterizaton set and/or the characteristic function. In fact, mostof the papers cited above follow this line of development.In Section 5.1 we introduce the notion of a sequential LP process and use it to formalize Kopelowitz’s method for computing the nucleolus. The concept of a characterizationset for the nucleolus of a game is introduced in Section 5.2. Therein we provide sufficientconditions for a family of coalitions to form a characterization set for the nucleolus ofa game and prove some properties thereof. In Section 5.3 we prove that the class ofirreducible saturated coalitions (see definition therein) forms a characterization set forthe nucleolus of a monotone game having a nonempty core.Ill Section 5.4, we study the relationship between the size of a characterization setand the complexity of computing the nucleolus. We show that if the nucleolus of agame has a characterization set of size polynomially bounded in the total number ofplayers, then the nucleolus of this game can be computed in strongly polynomial time(see definition of .stronge polynomiality therein). Characterization sets for some classesof games, previously studied in the literature, are described in Section 5.5.Chapter 5. The Characterization Set for the Nucleolus 1155.1 Sequential LP ProcessesIn this section, we formalize Kopelowitz’s method (Kopelowitz [1967], Maschler, Pelegand Shapley [1979]) for computing the nucleolus of a cooperative game through the notionof a sequential LP process. We further prove some structural properties thereof.Let 1’ = (N; c) be a cooperative game in characteristic function form. Depending on ifit is the cost or the revenue that is allocated, the characteristic function is interpreted aseither the cost or the revenue function. In this chapter, we fix our interpretation of c as acost function. Thus, in the sequel we often refer to a cooperative game in characteristicfunction form as a cost game. We emphasize, however, that this assumption about theinterpretation of the characteristic function does not induce any loss of generality of theresults presented in this chapter, since analogous results are valid for revenue games.Let us briefly review a few notation. The set of all pre-imputations of F is denotedby X*(F). The set of all imputations of F is denoted by X(F).The excess of coalition S with respect to x e RN is defined by e(S, x) = c(S) —where x(S) = kESXk. For a game F = (N;c) and x E RN, let qf(x;F) be the 2-dimensional vector whose components are the values of the excess function e(S, x), fore arranged in a nondecreasing order. Let j be the “lexicographically greaterthan” relationship between vectors of the same dimension, and let X0 C RN. Thenucleolus of F with respect to Xo is given by,N(F,X0) {x E X0: (x;F) (y;F),Vy E X0}. (5.1)When X0 = X*(F), N(F,X0 is called the prenucleolus of F and is denoted by PN(F),and when Xo = X(F), N(F, X0) is called the nucleolus of F and is denoted by N(F).It is well known that if X0 is nonempty and compact then N(F, X0) 0, and if,furthermore, Xo is convex, then N(F, X0) consists of a single point (for proofs see, forexample, Schmeidler [1969] or Charnes and Kortanek [1970]). In this chapter, we areChapter 5. The Characterization Set for the Nucleolus 116mainly concerned with the prenucleolus and the nucleolus of a cost game F. Therefore,unless otherwise specified, Xo is taken to be either X*(F) or X(F). Note that both X*(F)and X(F) are polyhedrons.The following interpretation of the nucleolus is quoted from Aumann [1989]: “Theexcess function value e(S, x) measures the ‘satisfaction’ of a coalition S with respect tothe proposed cost allocation x. If we think of the loudness of S’s complaint against x asproportional to its dissatisfaction, which is the negation of satisfaction, then the nucleolusmay be considered as the result of the following process: the cost allocator minimizes theloudest complaint; subject to achieving this, he minimizes the second loudest complaint;and so forth.” Kopelowitz’s procedure3°for computing the nucleolus can be regarded asan LP realization of the process described by Aumann. To formalize this procedure forcomputing the nucleolus, let us adopt the following notation.Notation 5.1.1 Let T C 2N, c be a function defined on T, and X be a polyhedron inRN. Denote by P(T, c, X) the following LP problem:P(T, c, X): Max{r: r + x(S) c(S), S e 7;x é X}.The sequential LP process for P(T,c,X), denoted by SLP(P(T,c,X)), is the process ofsolving a sequence of LP problems, {Pk: k 1}, led by P1 = P(T, c, X) and terminatedwith P,ç(F 1) which has a unique optimal solution or has only equality constraints. Forthe kth LP problem Fk, let rk be its optimal value, Xk be the projection of its optimalsolution set on RN and Ek = {S N: e(S,x) = constant rj, on Xk}. Then, Fk+1 isderived from Fk by converting all constraints induced by subsets S e Zk into equalitiesof the form, x(S) = c(S) — e(S, y), where y is an arbitrary vector in Xk. We will refer30This procedure was formally tested by Kopelowitz [1967], and implicitly suggested in Schmeidler[1969]. Maschler, Peleg and Shapley [1979] have carried out a careful analysis of this procedure.Chapter 5. The Characterization Set for the Nucleolus 117to X,, the projection of the optimal solution for the last LP in SLP(F(T, c, X)) on RN,as the outcome of SLP(P(T,c,X)), and to p {X,X1,. ..,Xj as the trajectory ofSLP(P(T,c,X)). We also let E’ denote U... U.Remark 5.1.2 Equivalently, rk, X,, k and Pk+1 for k 1 can be defined as,(1) r1 = maxXEx mlnseT e(S, x) and rk = maxZexk_l minsET\Ek_1 e(S, x) for k> 1.(2) Xk = {x E X1: e(S,x) rk,VS e = {x X1: minsET\EJc_1 e(S,x) =rk }.(3) k is the set of all coalitions S in T such that e(S, x) is constant for all x E Xk.(4) Pk+1 is the LP problem derived from P1 by setting all constraints induced bysubsets in Ek into equalities of the form, x(S) = c(S)— e(S, y), where y is an arbitraryvector in Xk.The sequential LP process depicted in Notation 5.1.1 is slightly different from theprocess described in Maschler et al. [1979]. Indeed, therein they derive Pk+i from Pkby converting into equalities all constraints induced by coalitions in {S C N: e(S, x) =rk for all x E Xk}, which is a subset of k defined in Notation 5.1.1. But, as mentionedat Footnote 37 thereof, these two processes have the same outcome. Actually, we canprove the following:Lemma 5.1.3 The outcome of the process described in Notation 5.1.1 will not change ifin the derivation of Pk+1 from Pk at least one but not necessarily all constraints inducedby coalitions in k are converted into equalities.Proof It is sufficient to prove that any such modified process and SLP(F(T, c, X)) havethe same outcome. Such a proof follows the same line as the proof of Theorem 6.6 inMaschler et al. [1979]. After proving analagous results as Lemmas 6.3 and 6.5 therein,we can conclude that the modified process (in particular, SLP(P(T, c, X))) terminatesChapter 5. The Characterization Set for the Nucleolus 118after a finite number of steps with the following outcome,{x E X: g(x,c,T) q(y,c,T) for ally X},where q(x, c, T) is the T-dimensiona1 vector consisting of the components e(S, x), S eT, arranged in a non-decreasing order. (Remark 5.1.5 below contains a further discussionabout this set.) For brevity, we omit this part of the proof. .For a cost game F = (N; c), denote by P(T, F, X0) the LP problem P(T, c, X0), wherec is taken to be the characteristic function of F and Xo = X*(F) or X(F). With thenotion of a sequential LP process, Kopelowitz’s procedure for computing the nucleolus ofF with respect to Xo can be described as SLP(F(2N, F, Xo)), whose outcome is N(F, X0).Remark 5.1.4 For a game with a nonempty core, the prenucleolus coincides with thenucleolus and is contained in its core (Schmeidler [1969]). For such a game F, the optimalvalue r1 of F(T, F, X*(F)) is nonnegative. So the projection of the optimal solution setof P(T, F, X*(F)) on RN is contained in the core of F, which is contained in X(F).Therefore, if F has a nonempty core, the constraint x€Xo can be replaced by x(N) =or by x e C(F) in all LP problems encountered in Kopelowitz’s procedure forcomputing the prenucleolus/nucleolus of F.A geometrical interpretation for SLP(P(2N, F, X(F))), which dubs its outcome, N(F),as the lexicographical centre of the imputation set X(F), was given in Maschler, Pelegand Shapley [1979]. Analogously, a similar geometrical explanation can be producedfor SLP(P(T,F,X0))for any T ç 2N• For this reason, we refer to the outcome ofSLP(P(T, F, X0)), which is a non-empty compact convex subset of X0, the lexicographicalcenter of X0 with respect to T.Remark 5.1.5 Another explanation for the outcome of SLP(F(T, F, X0)) is as follows.Define a cost game with coalition formation restrictions to be a triple F’ (N, T, c),Chapter 5. The Characterization Set for the Nucleolus 119where N is the set of players, T is a family of subsets of N which consists of all permissiblecoalitions and c is the characteristic function of pT, which is a real-valued function definedon T U {{i},i E N} U {N}. Let Xo ç RN. Define the nucleolus of pT with respect toXo by,N(FT)= {x E X0: (x,c,T) i (y,c,T), Vy é X0},where q5(y, c, T) is the T-dimensional vector whose components are the excesses e(S, y),S e T, arranged in a nondecreasing order. Then, by Lemma 5.1.3, N(FT) is exactly theoutcome of SLP(P(T,F,X0)).In general, the outcome of SLP(P(T, F, X0)) might not be a singleton set. However,when T = 2N the outcome of SLP(F(T, F, Xo)) is the prenucleolus or nucleolus of F,and hence is a singleton set.Proposition 5.1.6 The outcome of SLP(F(T, F, Xo)) is a singleton set if and only ifthe set of incidence vectors3’of subsets in T spansThe proof is immediate, and thus omitted.Next, we present a decomposition result for sequential LP processes. Let {N,, N2}be a non-trivial partition of N, 7 2, i 1,2, and c be a function defined on T1 U 7.Let i = 1,2, be polyhedrons in RN:, and X = x where ‘x’ denotes thecartesian product. For i = 1,2, letF: Max{r: r + x(S) <c(S), S E 7;E x() }.Upon combining constraint sets for F and F, we obtainF,: Max{r: r + x(S) <c(S), S E 7 U 7;XE X }.31The incidence vector of a subset S of N is the vector es, e E RN, such that e = 1 if i S and= 0 otherwise.Chapter 5. The Characterization Set for the Nucleolus 120Consider now SLP(PI(Z)), i = 1,2, and SLP(P1). Let }, i = 1,2, and{X,X1,... } be their trajectories, respectively.Theorem 5.1.7 The outcome of SLP(Pi) is the cartesian product of those of SLP(FJ),i = 1,2.Proof For k 1, denote by and Ck the constraint systems for Fj and Fk, respectively. Suppose Ck = C1 U C for some k 1 and 1 k1, k2 k. Then, since p, andare relaxations of Pk, it follows that r rk and that r rj, where rk and r areoptimal values of Fk and F,, respectively. Further, let x = (xN1, xN2), where xN1 Eand xN2 Then, (re), xN1) satisfies all constraints in C’ and (r, xN2) satisfies allconstraints in and thus, (min{r, r}, x) satisfies all constraints in Ck. The latter,(1) (2) . . . (1) (2) (1) (2)together with ‘r1 rk and rk2 rk, implies rk = min{rk1 , r2 } and Xk1 x Xk2 c Xk.Now, if rj = < r, then the projection of Xk on RN1 is and Dk =where Ek (resp., E) consists of all coalitions whose excess are constant and no lessthan rk (resp., r) on Xk (resp., Xe)) (see Notation 5.1.1). Thus, in this case, Ck+1 =U C. Similarly, if rk = r < re), then, Ck+1 C’ U C,1. Finally, if= r = r, then Xk = xX and Ek = and thus Ck+1 =G1UCJin this case.In summary, we have proved that if Ck = CUC for some k 1 and 1 k1, k2then x ç Xk and Ck+1 = Cj) U G) for some 1 n1,n2 k + 1. Therefore,starting from the fact that C1 = U by induction, we can show that for anyk > 1 there exist k1, k2, n1 and n2 (1 k1, k2 k; 1 n1, n2 < k + 1) such thatx ç Xk and Ck+1 = Cj’1) U Thus, in particular, the cartesian product ofthe outcomes of SLP(F’) and SLP(F12)is contained in that of SLP(P1).The other direction of the inclusion follows from the fact that the outcome of SLP (F1)is either a singleton set or a subset of X over which e(S, x) is constant for all S E Tj U 7.Chapter 5. The Characterization Set for the Nucleolus 121In either case, for any x in the outcome of SLP(P1), its restriction to N must be in theoutcome of SLP(F1). •5.2 Characterization Sets for the NucleolusUsing the notion of a sequential LP process, we introduce the concept of a characterizationset for the nucleolus of a cooperative game.Definition 5.2.1 A subset T0f2N is called a characterization set, or a c-set for short, forthe nucleolus of a game F = (N; c) with respect to Xo, if the outcome of SLP(F(T, F, Xo))is N(P,X0).Theorem 5.2.2 T is a c-set for N(P, X0) if and only if the lexicographical order of4(x,F) for x E Xo is determined by the components e(S,x), S E T.Proof Recall first that from Remark 5.1.5, the outcome of SLP(F(T, F, Xc,)) is the set{x E X0: q(x,c,T) i q(y,c,T), for ally E X0}, where cb(x,c,T) is the TI-dimensionalvector consisting of the components e(S, x), S € T, arranged in a non-decreasing order.Now, suppose T, T ç 2N, is the c-set for N(F,Xc,). Then, the lexicographical orderof qS(x, F) for x€Xo is determined by the subvectors ç5(x, c, T) which consist of theexcess function values, e(S, x), for S E T. On the other hand, if the lexicographicalorder of q(x, F) is determined by the excess function values for coalitions in T, thenthe nucleolus of 1’ will be the same as that of the game induced from 1’ by imposingcoalition formation restrictions to T. Hence, again from Remark 5.1.5, the outcome ofSLP(P(T, F, Xc,)) coincides with that of SLP(F(2N, F, Xc,)), implying that T is a c-setfor F.Corollary 5.2.3 If T is a c-set for N(F), then, so is every superset of T.Chapter 5. The Characterization Set for the Nucleolus 122Two questions regarding c-sets naturally arise. The first one is how to verify, efficiently, whether a family of coalitions form a c-set for the nucleolus of a game (or for aclass of games). The second question is whether a smaller c-set would lead to a moreefficient algorithm for computing the nucleolus. For the remainder of this section andin the next section, we address the first question. We provide some sufficient conditionsfor a collection of coalitions to form a c-set , and derive some properties of c-sets. Thesecond question will be dealt with in Section §5.4.Theorems 5.2.4 and 5.2.6 below provide sufficient conditions for a class of coalitionsto form a c-set of the nucleolus of a game I’ = (N; c).Theorem 5.2.4 A proper subset T of 2” is a c-set for N(P,X0)if for everyS Ethere exists a T, T ç T, such that,(1) e(S,x) e(T,x), VT E Ts,Vx Xo;(2) es, the incidence vector of S, is in the span of {eT: T € Ts}.Proof Let p = {X0,X1,... , XK} and p’ = {X0,Xi,. . . , X} be the trajectories, rk, Ek,>k (1 < k K) and r, , (1 i) be other relevant entities (as defined inNotation 5.1.1) for SLP(P(2N, F, X0)) and SLP(F(T, F, Xo)), respectively. It is sufficientto prove that if T satisfies conditions (1) and (2) of Theorem 5.2.4, then Vj, 1 ‘,X’ =Xkforsomek, 1 kK.Suppose, on the contrary, that the latter does not hold. Let j (j 0) be an indexsuch that X,’€ p and X1 g p, and let k be the maximun index such that Xk = X3’(we assume that X = X0). If k= j = 0, since T c 2N, P1 is a relaxation ofP11. Otherwise, from Remark 5.1.2(4), Pj1 (resp., PJ1) is the LP problem derived fromP(2s,F,Xo) (resp., P(T,F,X0)) by setting all constraints induced by coalitions whoseexcess function values are constant on Xk (resp., X). Hence, since Xk = X and T C 2N,Chapter 5. The Characterization Set for the Nucleolus 123we still have that P1 is a relaxation of l+j. So,Tk+1 (5.2)Now, for any S 2N \ k, if there exists x E X’1 such that e(S, x) < thenfrom condition (1) of Theorem 5.2.4, Ts which, together with Remark 5.1.2(3)and condition (2) of Theorem 5.2.4, implies that e(S, x) is constant on X’ (= Xk). Butthe latter is not possible since Ec consists of all coalitions which have constant excesson Xk. Therefore, for any S E 2N \ Ek, e(S, x) r+i for any x E X1. By Remark5.1.2(1), rj4 r+1. Thus, from (5.2), Tk+1By r1 and the fact that is a relaxation of Fk+1, X 2 Xk+l. However,by assumption, X’ p, and so X1 D Xk+1. Let y e X÷1 \ Xk+l. y Xk+1 impliesthat e(R, y) <rk+1 (= r1) for some R, R E Ek+1 and 1? g T. Hence, from condition (1)of Theorem 5.2.4, 2 E’3, and then by condition (2), e(R, x) is constant on X’ (= Xk).Again this is a contradiction since Ek, which does not intersect with Ek÷1, contains allcoalitions which have a constant excess on Xk. aLet P = (N; c) be a cost game with a nonempty core. A family of coalitions, T, issaid to induce a representation of the core ifC(1’) = {x E R: x(S) c(S), VS E T; x(N) = c(N)}.In general, a family of coalitions which induces a representation of the core does notalways form a c-set for the nucleolus as demonstrated by the following example, which isessentially due to Maschler et al. [1979].Chapter 5. The Characterization Set for the Nucleolus 124Example 5.2.5 Let I’ be the game (N;c) with N = {1,2,3,4} and c defined by,c(N) = c({1,2,3}) = c({1,2,4}) = c({1,3,4}) c({2,3,4}) = 2,c({1,2}) = c({3,4}) = c({1,4}) = c({2,3}) = 1,c({1,3}) = 3/2, c({2,4}) = 2,c({i}) = 1 for alli EN,c(O)=0.Let 1” (N; c’) be the same as 1’ , except that c’({l, 2, 3}) = 15/8. It can be shownthat X(f’) X(F’) and that 0(1’) 0(1”) = {A (, , , ) + (1 — A) (0, 1,0,1): 0A 1}. Observe that P and F’ only differ by the cost of coalition {1, 2, 3}, and bothhyperplanes x({1,2,3}) = c({1,2,3}) and z({1,2,3}) c’({1,2,3}) do not intersect0(1’) = C(I”). Thus, one could easily verify that coalition {1, 2, 3} is not contained inany efficient representation for 0(1’) or 0(1”), and that any efficient representation for0(1’) is also an efficient representation for 0(1”). Therefore, if every family of coalitionswhich induces a representation of the core forms a c-set for the nucleolus, we should havethat N(P) N(1”). But, it can be verified thatN(P)=and N(P’)=Theorem 5.2.6 Suppose T, a proper subset of 2N, induces a representation of the corefor the cost game P = (N; c). Then, T is a c-set for N(F,X0)if for every S€2N \ Tthere exists a Ts, T T, such that,(1)’ e(S, x) e(T, x), VT€ ‘Ta, Vx E 0(1’);(2)’ es, the incidence vector of S, is in the span of {eT: T€ Ts}.Proof We use the same notation as was used in the proof of Theorem 5.2.4 for entitiesrelating to SLP(P(2N, F, X0)) and SLP(P(’T, F, X0)).Chapter 5. The Characterization Set for the Nucleolus 125Observe that condition (2)’ of Theorem 5.2.6 is the same as (2) of Theorem 5.2.4, and(1)’ of Theorem 5.2.6 is weaker than (1) of Theorem 5.2.4. In the proof of Theorem 5.2.4,we used condition (1) twice: once for deriving that T c E’3 if there exists x X1such that e(S, x) < and the other time when concluding that 7 E’3 sincee(R,y) < r4 for some y e Therefore, since X1 = X ( X0) if .1 = 0 andX otherwize, the proof of Theorem 5.2.4 is still valid here if we can prove that thestronger condition imposed on T in Theorem 5.2.6 ensures that X C(1’). The latterindeed holds. From C(F) 0, it follows that r 0. Therefore, by the assumption thatT induces a representation of C(F), X1 = {x E X0: e(S, x) r for all S e T} C C(I’).ITwo games 1’ = (N; ci) and F2 (N; c2) are said to be strategically equivalent ifthere exist a positive real number a and a constant vector a E R” such that c2(S) =cxci(S) + a(S) for all S N, where a(S) = ZkESak. The next result indicates that theconcept of a characterization set is covariant under strategical equivalence.Proposition 5.2.7 Suppose that F1 and F2 are strategically equivalent, and let T be ac-set for N(1’1), or for PN(F1). Then, T is also a c-set for N(F2), or for PN(I’2).Proof We only prove this statement for the nucleolus. The case for the prenucleolusis similar. From the definition of the imputation set, X(F2) = {ax + a: x E X(F1)}.From Theorem 5.2.2, if T is a c-set for N(I’1), the lexicographical order of 1(x, F1) forx E X(F1) is determined by the components e(S,x), S T. But, for any x E X(1’1),q(x, F1) = q(ax + a, F2). Thus, the lexicographical order of qf(y, F2) for y € X(I’2) isalso determined by components e(S, y) for S T. Therefore, by Theorem 5.2.2, T is ac-set for N(F2). .Let P = {N1,2}be a nontrivial partition of N. The game F = (N;c) is said to bedecomposable (with respect to F) if c is additive across the partition. That is, for eachChapter 5. The Characterization Set for the Nucleolus 126SE2N,c(S) = c(S fl N1) + c(S fl N2).The two smaller games l’, i 1,2, obtained by restricting c to the subsets of N, i = 1,2,respectively, are the components of the decomposition.It is easy to see that if I’ = (N; c) is decomposable with respect to {N1,N2} andT is a c-set for the prenucleolus/nucleolus of F, then, 2 T fl 2N is a c-set for theprenucleolus/nucleolus of l’, for i = 1,2. The converse is also true when C(F) 0.Theorem 5.2.8 Suppose 1’ is decomposable with respect to a partition {N1,N2} andC(F) 0. Let 1’s, j = 1,2, be the components of the decomposition, and let 7 and 7be some c-sets for the nucleolus of Fi and 1’2, respectively. Then, T = T1 U T is a c-setfor N(F).Proof Let T’ 2N1 U 2N, and for S E 2” \‘T’, define T = {S fl N1,Sn N2}. Clearly,Ts defined this way satisfies condition (2)’ of Theorem 5.2.6. Since F is decomposablewith respect to {N1,2}and C(F) 0, it follows that C(F) = C(1’1) x C(F2) (Shapley[1971132) and e(S,x) = e(S fl Ni,x) + e(S fl N2,x) for any x RN. Therefore, T’induces a representation of C(1’), and for any x € C(F), e(S fl Ni,x) < e(S,x) ande(S fl N2, x) e(S, x). Thus, from Theorem 5.2.6, T’ is a c-set for N(F). That is, N(F)is the outcome of SLP(P(T’,F,X(F))).By Remark 5.1.4 and since C(P) 0, the constraint x € X(F) in LP problems encountered in SLP(F(T’, F, X(1’))) can be replaced by x E C(F). Applying Theorem 5.1.7to SLP(P(T’, F, X(F))), we conclude that N(1’) is the cartesian product of the outcomes32A proof of this result for convex games can be found in Shapley [1971]. However, it is easy to seethat the same proof is also valid for non-convex games.Chapter 5. The Characterization Set for the Nucleolus 127of SLP(P()), i = 1,2, where p(t) is the following LP,p(:) Max{r: r + x(S) c(S), S E 2N;x€C(I’1) }.However, since the outcome of SLP(P()) is N(I’) and 7 is a c-set for N(I’), N(F) isthe cartesian product of the outcomes of SLP(F1()) for i 1,2, where F is the same asp(i) except that 2’ therein is replaced by 7. After applying Theorem 5.1.7 once more(this time to SLP(P1)for i = 1,2), we conclude that N(1’) is the outcome of SLP(P1),where P1 = P(T1 U 7;, F, C(1’)). Hence, T = 7; U 7; is a c-set for N(f). .Theorem 5.2.8 is equally true if N(f) is replaced by PN(f), since for a game witha nonempty core, the nucleolus coincides with the prenucleolus (Schmeidler [1969]). Acorollary of this theorem is the following well-known result (Megiddo [1973]).Corollary 5.2.9 Suppose C(f) 4 0 and 1’ is decomposable with l’, i = 1,2, being thecomponents of the decomposition. Then, N(1’) = N(1’1) x N(1’2).5.3 Saturated Coalitions for Monotone GamesIn this section, we restrict our attention to monotone cost games. A game (N; c) is said tobe monotone if c(S) c(T) whenever S C T. We will introduce the notion of saturatedcoalitions, and prove that the class of all irreducible saturated coalitions forms a c-setfor the nucleolus of a monotone game having a non-empty core. However, just like theconcept ‘monotonicity’, all concepts introduced in this section are not invariant underthe addition of additive games.Definition 5.3.1(1) A coalition S ofT’ = (N; c) is said to be saturated if i € S whenever c(SUi) = c(S).(2) A closure of S is a saturated coalition S such that S C S and c(S) = c(s).Chapter 5. The Characterization Set for the Nucleolus 128Lemma 5.3.2 Any non-saturated coalition has at least one closure.Proof This is demonstrated by adding players to a non-saturated coalition S until anyfurther addition will have to increase c(S). Since INI is finite, the process of addingplayers will stop after at most INI additions. From the definition of connectivity, theresulting coalition is saturated, hence, is a closure of S.Definition 5.3.3 A saturated coalition S is irreducible if there is no partition {S1,S,,} of S such that S are saturated and c(S) c(Si) + ... + c(S).For a cost game I’, let IS denote the class of all irreducible saturated coalitions, anddefine IS’ IS U {N\i: i N} U {N}.Lemma 5.3.4 A saturated coalition S is irreducible if and only if S has no partitionP = {Si,. . . ,S,j such that S e IS and c(S) c(S).Proof The sufficiency follows from the definition. To show the necessity, suppose asaturated coalition S is not irreducible. Then, from the definition of irreducibility, S hasa partition Pi = {S,. . .,S,} such that Se’s are saturated and >‘ c(S) <c(S). Sinceany refinement of Pi is still a partition of 5, the proof follows by applying inductivearguments to those subsets S which are not irreducible.Theorem 5.3.5 Let F = (N; c) be a monotone cost game with a nonempty core. ThenIS’ induces a representation of C(fl.Proof It is easy to see thatC(P) ç C’ {x e RN: x(S) c(S), S IS’; x(N) = c(N)}.To prove the other direction of the inclusion, we need to show that for all x E C’,x(S) <c(S) for any S E 2N \ IS’. Let S E 2N \ IS’. Clearly, S is either dissaturated, orChapter 5. The Characterization Set for the Nucleolus 129saturated but not irreducible. If S is saturated but not irreducible, then, by Lemma 5.3.4,S has a partition P {S,... ,Sk} such that S E IS and > c(S1) c(S). Thus,x(S)=x(S) Di c(S) c(S) for x € C’. If S is dissaturated, let S be a closureof S. Then, S c S, c(S) = c(S) and x() c(s). Now, observe that x 0 for allx€C’. Indeed, for any i E N and x € C’, x = x(N) — x(N\i) c(N) — c(N\i) 0.Thus, x(S) x(.) c(S) = c(S). .Theorem 5.3.6 Suppose I’ is a monotone cost game and C(1’) 0. Then, IS’ is a c-setfor N(1’).Proof By Theorem 5.3.5, IS’ induces a representation of C(1’). Let S E 2” \ 7J5’.Case 1. If S is saturated, then S is not irreducible and it follows from Lemma 5.3.4that S has a partition P {S1,. . .,S} such that S E IS and c(S) < c(S). LetT = P. Clearly, T defined this way satisfies condition (2)’ of Theorem 5.2.6. Further, forxE C(I’), e(S,x) >0 for all 1 k. Thus, for 1 j k, e(S3,x) e(S,x) <e(S, x), where the last inequality follows from c(SJ c(S). Hence, Ts also satisfiescondition (1)’ of Theorem 5.2.6.Case 2. If S is not saturated, let S be a closure of S. Define Tg = {N\i: i ES \ S} U {N} U 7, where 2 = {S} if E IS and otherwise T is defined as in Case1. Ts defined this way satisfies condition (2)’ of Theorem 5.2.6. To show that T alsosatisfies condition (1)’ of Theorem 5.2.6, let x E C(P). If = {S}, then e(, x) e(S, x)is implied by c(s) c(S) and x 0. Else, for T E T, e(T, x) e(S, x) follows as shownin Case 1. Fori€S\S,e(N\i, x) = c(N\i) — x(N\i) = c(N\i) — c(N) + x1x, since 1’ is monotone= (x(S U i) — x(S)) + (c(S) — c(S U i)), since c(S U i) = c(S)< e(S,x), since e(SUi,x) >0.Chapter 5. The Characterization Set for the Nucleolus 130Finally, 0 = e(N, x) < e(S, x) since x E C(I’). Hence, Ts satisfies both conditions ofTheorem 5.2.6, and by Theorem 5.2.6, IS’ is a c-set for N(1’) as claimed. .A coalition S is said to be essential for a game 1’ = (N; c) if for every partition,P = {S,. . . , S,}, of 5, c(S) c(S). By convention, single member coalitions areessential. Let E denote the class of all essential coalitions of 1’. The following result isessentially proved in Huberman [1980].Theorem 5.3.7 If C(T’) 0, then E is a c-set for N(I’).Theorem 5.3.7 follows trivially from Theorem 5.2.6. Indeed, clearly 4E induces arepresentation of C(F), and for S e 2N \ E, Ts can be chosen to be an arbitrary partitionP {S, . . . , S,} of 5, such that c(S) >D c(SJ. For such a partition, Condition(2)’ of Theorem 5.2.6 is trivially satisfied. Condition (1)’ therein is satisfied by such apartition since, by assumption, C(1’) 0.Remark 5.3.8 below relates Huberman’s essential coalitions to the collection of irreducible saturated coalitions introduced above.Remark 5.3.8(1) It follows from the definition of irreducibility that a saturated coalition is irreducible if and only if it is essential among the class of all saturated coalitions.(2) Let F = (N; c) be an arbitrary cost game. Then, for a sufficiently large vectord€RN, F = (N; c + d) is a monotone game with every subset of N therein beingsaturated. For such a game F’, the class of all irreducible saturated coalitions coincideswith the class of all essential coalitions.(3) In general, for an arbitrary game F, it may happen that neither 6 c IS norzscr.Chapter 5. The Characterization Set for the Nucleolus 1315.4 Polynomial Computability of the NucleolusIn this section, we study the relationship between the size of a c-set and the complexityof computing the nucleolus. Recall that the dimension of a cooperative game is definedto be the total number of players in the game. We will prove in this section that if thenucleolus of a cost game P has a c-set whose size is polynomially bounded in the numberof players, then N(P, X0) can be computed in strongly polynomial time.For a cost game P = (N; c), let T be a c-set for N(I’, X0). Recall that N(P, X0) isthe outcome of SLP(F(T, F, X0)), whereF(T, F, Xo): Max{r: r + x(S) c(S), S E T;xEX0}.We develop next an algorithm for computing the outcome of SLP(P(T, F, Xo)) and showthat the proposed algorithm is strongly polynomial if T has size polynomially bounded inINI. For brevity, we assume that X0 = X(F) in the sequel. The case where Xo X*(P)is similar. Recall that when X0 X(P) the constraint x X0 in F(T, F, Xo) can bereplaced by: x c(i) for i N, x(N) = c(N).Let {T1,T} be a partition of TU{N} with N E 7. Denote by P’r the LP problem,P7j,.: Max rs.t. r+x(S)c(S), SE2;x(S)=c(S)—rs, SeT2;xc(i), iEN;x(N) = c(N),where rs, for S T, are constants depending on S, and in particular, rN = 0. The dualChapter 5. The Characterization Set for the Nucleolus 132LP problem of FT1 ,‘T2 isDi: Mm ZSET1 c(S)7rS + ZsE(C(S) — rs)rs + iEN c(i),s.t. ZSET1 S = 1;S:iESS+’uiO, i€N;7rs,VSE7, )O,ViEN.Observe that all coefficients in the constraints of D are zero or one. Thus D iscombinatorial (see Tardos [1986] for definition), and by applying Tardos’ [1986] celebratedalgorithm for solving combinatorial LP problems, we conclude thatLemma 5.4.1 If T has size polynornially bounded in INI, then there is a strongly polynomial algorithm which computes the optimal value and an optimal solution for D.From Corollary 5.2.3, without loss of generality, we can assume in the sequel thatT {N\i: i N}. Algorithm A for computing the outcome of SLP(F(T, F, X0)) can bestated as follows.Algorithm 5.4.2Input: The c-set T for the nucleolus of a cost game F. Assume T {N\i: i N}.Output: y = N(F).Step 0. Set P1 = P(T,F,X0) 2j = T, {N}, k = 1 and çt = {N\i:i E N}.Step 1. Repeat the following until = 0,• Solve Djj,’j by applying Tardos’ algorithm. Let rk be its optimal value, 7r* be anoptimal solution, and let k {S T1: 1r 0}. Set T1 T1 \ k, 7 = 7 U ,= \ and k = k + 1.• For each i such that N\i E , set Yt = rk + c(N) — c(N\i).Step 2. Output y.Chapter 5. The Characterization Set for the Nucleolus 133Theorem 5.4.3 Let 0 be a class of games in which we can find for each game a c-setwhich is polynomially bounded in the number ofplayers. Then, Algorithm 5.4.2 computesN(I’) in strongly polynomial time for every P E 0.Proof Let P = (N; c)€G and T be the c-set that we find for I’. We start by showingthat Algorithm 5.4.2 computes the outcome of SLP(F(T, I’, X0)). Indeed, for each Fk(k 1), Algorithm 5.4.2 computes the optimal value and identifies some inequalityconstraints which are binding at all of its optimal solutions by finding the optimal valueand an optimal solution for the dual LP problem of Fk. Explicitly, in the first iterationof Step 1, Algorithm 5.4.2 computes the optimal value and an optimal solution of theLP problem DT,{N}, which is the dual LP problem of P1. Let r1 be its optimal valueand be an optimal solution. Then, by the duality theorem of linear programming,r1 is the optimal value of F1 and subsets in {S E T: ir O} induce constraintswhich are binding at all optimal solutions of P1. Let F2 be the LP problem derivedfrom P1 by converting some constraints induced by subsets in E1 into equalities as donein Notation 5.1.1. The dual of P2 is D7j,2, where T1 T \ and {N} U E.In general, in the kth iteration of Step 1, Algorithm 5.4.2 computes the optimal valueand an optimal solution of the dual LP problem of Pk, which has the form forsome partition {T1,7} of T U {N}. Let rk be its optimal value and 7r* be an optimalsolution. Then rk is the optimal value of Fk and subsets in k {S € T1: O}induce constraints which are binding at all optimal solutions of Fk. Derive P,÷1 from Fkby converting constraints induced by subsets in Ek into equalities, and note that the dualof P,1 is D\Ek,uEk.By the time constraints induced by all coalitions N\i, i€N, have been converted intoequalities, SLP(P(T, F, X0)) has come to its end. Indeed, when the latter has occuredthe values of all variables x, i€N, are fixed and thus the last LP problem solvedChapter 5. The Characterization Set for the Nucleolus 134must have a unique solution. Algorithm 5.4.2 tests this stopping criterion by checking if{N\i: i E N} T2 at the end of every iteration of Step 1. Whenever N\i, for some i E N,is moved from T1 to 7, Algorithm 5.4.2 sets y rk + c(N) — c(N\i), where k is chosensuch that N\i E Clearly, y defined this way is the outcome of SLP(F(T, F, Xo)).Algorithm 5.4.2 stops after finitely many iterations since, at each iteration of Step1, the optimal solution for D7, must satisfy ZSET1 = 1, so k is nonempty. Henceafter every iteration at least one inequality will be converted into an equality. Therefore,the algorithm will terminate after at most jT) iterations.To show that Algorithm 5.4.2 is strongly polynomial if T has size polynomiallybounded in INI, observe that, at each iteration, computations are dominated by thoseneeded for solving From Lemma 5.4.1, Tardos’ algorithm for solving isstrongly polynomial if IT! is polynomial in IN!. Since Algorithm A terminates after atmost IT! iterations, it follows that it computes the nucleolus in strongly polynomial time,completing the proof.We are led to conjecture that the converse of Theorem 5.4.3 is also valid. Indeed,suppose that the nucleolus of a game is computable in strongly polynomial time. Then, itmust be true that the amount of relevant information, which is contained in the description of its characteristic function and is used in computing the nucleolus, is polynomiallybounded.To illustrate this point, let us briefly consider the class of simple majority games. Ann-person simple majority game, F (N; v), is defined bylo, ifS<q;v(S)=1, otherwise,where N = {1, 2,. . .,n} and q= [j + 1 (note that Lxi denotes the largest integer whichis less than or equal to x). In this game, players are completely symmetric, therefore,Chapter 5. The Characterization Set for the Nucleolus 135K(I’,) = N(P)= {(,. , )} (Davis and Maschler [1965]). To identify a c-set forN(P), let us adopt the following notation: {i, i + 1,. . . , i + q — 1}, where i + kis taken to be i + k — n if i + k > n, T {i: i N} U {{1,3,q+1,q+2,.. .,n}}. Itcan he easily verified that the incidence vectors of the n + 1 coalitions in T span RN.Moreover, we claim that T forms a c-set for N(I’). Indeed, to verify this claim, we needto show that the outcome of SLP(F(T, F, X(1’))) (see Notation 5.1.1) is N(FN). Butthis follows from the fact that (r*,x*), where r* = 1 — and x = for i e N, is theunique solution toP(T, F, X(F)): Min{r: r + x(S) v(S), S E T;x 0;x(N)=1}.Note that since P is a revenue game, ‘Max’ is replaced by ‘Mm’ and ‘‘ is replaced by‘‘in the LP problem.In view of the above discussion, we pose the converse of Theorem 5.4.3 as a conjecture.Conjecture: If the prenucleolus/nucleolus of a class of games can be computed instrongly polynomial time, then for every game in this class there exists a c-set whosesize is polynomially bounded and that can be detected in polynomial time (in terms ofthe total number of players in the game).5.5 ExamplesTo illustrate their usefulness and prevalence, we briefly describe in this section c-sets forthe classes of minimum cost spanning tree games and assignment games5.5.1. Minimum cost spanning tree games. A minimum cost spanning tree (MCST)game, FQ is defined on a simple complete graph G=(V, E) with node set V = NU {0}.Node 0 is the supplier node and N = {1, 2,. . . , n} is the set of customer nodes. There isChapter 5. The Characterization Set for the Nucleolus 136a nonnegative real number associated with each edge of G called the edge cost. We usec3 to denote the cost for the edge joining nodes i and j. For S C N, let T5 (Vs, Es)represent a MOST for the induced subgraph of G with node set V8 = S U {O}. Inthe MOST game, the player set is identified with the set of customers N, and the costfunction is defined as c(O) = 0 and c(S) {c: (i,j) e Es} for S c N and S $ 0.The class of MCST games has been studied, for example, by Bird [1976], Granot andHuberman [1981,1984] and Megiddo [1978], and is known to have a nonempty core (see,e.g. Bird [1976] or Granot and Huberman [1981]).To describe a c-set for the nucleolus of a MOST game FG, we need some more notation.A subset S N will be called TN-connected if S induces a connected subgraph onTN = (N, TN). That is, if i and j are in S, then so are all other nodes on the uniquepath from i to j in TN. Let £ denote the class of coalitions S whose complements N\Sare TN-connected. Then, we have,Proposition 5.5.1(1) £ is a c-set for N(FG).(2) The core for PQ can be represented as,C(I’G) = {x RN: x(S) c(S) for all S E C; x(N) = c(N)}.Both statements in Proposition 5.5.1 are implied by results proved in Granot andHuberman [1984]. For an arbitrary graph G, C consists of an exponential number (interms of NI) of coalitions. Therefore, for general MOST games, the computation of thenucleolus may still require exponential time. For the special case when TN is a chain, Cconsists of n(n + 1)/2 coalitions. Thus, from Theorem 5.4.3, the nucleolus of this specialclass of MOST games can be computed in strongly polynomial time.An even more special case is obtained when G itself is restricted to be a chain. Gamesassociated with such chain graphs were first studied by Littlechild [1974], Littlechild andChapter 5. The Characterization Set for the Nucleolus 137Owen [1977] and Littlechild and Thompson [1977]. In Littlechild [1974], the author hasidentified a class of O(INI) coalitions which were shown to be the only relevant coalitionsfor calculating the nucleolus, and has essentially developed therein an O(1N12)algorithmfor computing the nucleolus. Galil [1980] and lately, Granot, Maschler, Owen and Zhu[1994] have derived a linear time algorithm for computing the nucleolus of this class ofgames.5.5.2. Assignment games. Assignment games were introduced by Shapley and Shubik[1972] as a model for a simple two-sided market. In such a market: (1) There aretwo disjoint sets of agents, say “producers” and “consumers”, denoted by N1 and N2,respectively. (2) The agents are constrained to conduct their bussiness under exclusivebilateral contracts, and for that purpose partnerships are formed. (3) All transactionsare limited to exchanges between partners. For i E N1 and j E N2 there is associated anumber 0, representing the potential profit of the partnership between i and j if itis formed.We denote a simple market by M = (N1,N2,A), where A = (a3) e RIN1IXIN2I. Theassignment game associated with M is the game FM = (N; v), where N = N1 U N2, andfor S c N, v(S) is the maximum profit that can be attained by matching producers inS fl N1 with consumers in S fl N2.For an assignment game FM = (N; v), Shapley and Shubik [1972] proved thatProposition 5.5.2 C(FM) and,C(FM)={x E RN: x,+x a3 for alli€ N1,j EN2; x 0; x(N)=v(N)}.LetT{S: S={i,j} for someiENi,j EN2 orS={k} for somekN}. Thefollowing result was essentially proved in Solymosi and Raghavan [1994].33Since assignment games are revenue games, we need to reverse the directions of inequalities in thedefinition of all solution concepts.Chapter 5. The Characterization Set for the Nucleolus 138Proposition 5.5.3 T is a c-set for N(FM).Since there are only N1 1N2 + Nil + 1N2 coalitions in 7, it follows from Theorem 5.4.3 that N(I’M) can be computed in strongly polynomial time. In fact, an O(1N14)algorithm to compute N(1’M) is developed in Solymosi and Raghavan [1994].Chapter 6Allocation through the Reactive Bargaining SetSo far in this thesis, we have mainly concentrated our attention on evaluating the possibleuse of the nucleolus as a cost/revenue allocation scheme and on its computation. Unlikethe nucleolus, which is a single-valued solution concept, set-valued solution concepts havethe disadvantage of providing more than one, sometimes countlessly many allocationschemes. Thus in order to choose a proper one out of the many suggested allocationschemes, some additional criteria are required. Nevertheless, a lot of research has beendevoted to the study of set-valued solution concepts, since they may provide us withinteresting structural information about the payoff space, and the bargaining that maytake place among the players.The most well-known set-valued solution concept is the core. The core of a gameconsists of all imputations which no player or a set of players can improve upon bysevering coopration with the rest of the players and acting alone. In other words, thecore is the set of payoff vectors to which there is no ‘objection’ from any player or anycoalition of players. Bargaining sets go a step further than the core. They distinguishbetween objections that are ‘valid’ from those that are ‘invalid’. The key idea is thefollowing. Suppose that with respect to a suggested allocation vector x, a coalition Shas an objection, represented by a vector y which is feasible for S. Thus, it seems thatplayers in S can demand more from the rest of the players by withdrawing from thecurrent coalition structure and from x and make themselves better off with a payoff y.However some players not in S may be able to counter this objection if they can form a139Chapter 6. Allocation through the Reactive Bargaining Set 140new coalition Q that can achieve a payoff z that allocates to every player j in Q no lessthan x3 and to any player k lured away from S, if any, no less than Ilk. If this is indeedthe case, then the original objection is not ‘valid’ or is ‘unjustified’, and thus should beignored.In this chapter, we investigate cost/revenue allocations through bargaining sets, especially, the reactive bargaining set. The definition of the reactive bargaining set andsome preliminary results are provided in §6.1. In §6.2, we investigate the class of simplenetwork games and prove that for this calss of games the reactive bargaining set coincideswith the core. §6.3 is devoted to the study of the reactive bargaining set for the class ofconstant-sum, monotone simple games. It is shown that for a constant-sum, monotonesimple game the reactive bargaining set coincides with the kernel. The class of constant-sum weighted majority games is a subclass of constant-sum, monotone simple games.Thus, the coincidence of the reactive bargaining set and the kernel is valid for constant-sum weighted majority games as well. Combining this with the computational resultsfor the kernel developed in Aumann, Peleg and Rabinowitz [1965], Aumann, Rabinowitzand Schmeidler [1966] and Kopelowitz [1967], we realize that an explicit description ofthe reactive bargaining set for all constant-sum weighted majority games with up to 7players is available in the literature.6.1 The Reactive Bargaining SetIn order to define the reactive bargaining set (Granot [1994]), we briefly review theconcept of an objection by a player with respect to a given payoff vector. Let x be apayoff vector of a game r = (N; v). An objection of player i against playerj, with respectto x, is a pair (y, 8), where S is a coalition containing player i and not containing j andChapter 6. Allocation through the Reactive Bargaining Set 141y is a real vector indexed by S, satisfyingy(S) = v(S), Yk > Xk, k € S. (6.1)We say that i has a justified objection against j (in the sense of the reactive bargainingset) if for every subset Q containing j but not i, there exists a subset S containing i butnot j and a vector y, indexed by S, satisfying (6.1) and there does not exist a vector z,indexed by Q, satisfyingz(Q) = v(Q), Zk Uk, k E Sn Q, Zk Xk, k E S \ Q. (6.2)The reactive bargaining set (for the grand coalition), denoted M’(F), of the game Fconsists of all imputations for which no player has a justified objection against anotherplayer.Intuitively, player i has a justified objection against player j with respect to x, if hecan demonstrate that player j can not sustain any coalition, containing player j and noti, and still maintain her current payoff, .xj. Conversely, player i does not have a justifiedobjection against player j, with respect to x, if player j can sustain at least one coalition,containing j but not i, and maintain her current payoff, x3, no matter how i forms hiscoalition and distributes the resulting proceeds. In the latter case, a coalition which juses to maintain her current payoff is called a protecting coalition for player j.Similar to the Davis-Maschler [1967] bargaining set, the reactive bargaining set alsocontains the core, if the core is not empty, and the kernel (Granot [1994]). Hence, it isnot empty as long as the imputation set is not empty. Furthermore, Granot [1994] provedthat the reactive bargaining set is contained in the Davis-Maschler bargaining set.It appears that for many games the reactive bargaining set is more intuitive than theclassical bargaining set in the sense that it eliminates some unintuitive and unreasonablepayoff vectors (Granot [1994], Granot and Maschler [1994b]). It is certainly simpler toChapter 6. Allocation through the Reactive Bargaining Set 142analyze and to compute. For example, it has been shown in Granot [1994] that for a.simple majority game the reactive bargaining set consists of the unique symmetric vector,and thus coincides with the kernel and the nucleolus for this class of games. By contrast,the classical bargaining set of a simple majority game contains nonsymmetric and whatappears to be unreasonable payoff vectors, and its structure for this class of games isunknown. Further, it was also shown (ibid) that for the class of assignment games thereactive bargaining set coincides with the core. In next two sections, we will develop twomore results about the reactive bargaining set which will yield additional support for itsattractiveness.6.2 Simple Network GamesConsider a single source single sink directed network Gu = (V, A; u) with a set of nodesV and a set of arcs A. Let s and t, s,t E V, denote the source and the sink nodes ofGu. Assume that each arc in C has a unit flow capacity, and let ua denote the revenuefrom a unit of flow through arc a, a E A. We do not impose any conditions on the signof Ua. In general, one may expect some of the components a to be negative (reflectingthe cost of flow), while others are positive (to account for the associated revenue). Sucha network CU = (‘4 A; u) is called a simple network.Now, suppose that each arc in G is owned by a different owner. Then, one naturallyencounters the problem of allocating the revenues, resulting from an optimal flow inGU, among the arc owners. The purpose of this section is to examine and investigatethe possible use of the reactive bargaining set as an allocation scheme for such revenueallocation problems.Let GU=(‘4A; u) be a simple network. For S A denote by G the subnetworkof G’t induced by the arcs in S. Define v(S) to be the optimal revenue (maximum withChapter 6. Allocation through the Reactive Bargaining Set 143respect to the objective value vector us (ua: a E S)) resulting from an optimal s to tflow in G. Clearly, the set function v and the arc set A define a cooperative game on A,denoted by [‘(C), which will be referred to as the simple network game (associated withthe simple network Gj.Kalai and Zemel [1982b] showed that a simple network game is totally balanced.Furthermore, for x e RA let Gu_ be the simple network obtained from C by replacingu with u — x. Then, the following criterion for a vector x to be contained in the core,C(F(G)), of P(G) is valid.Proposition 6.2.1 (Kalai and Zemel {1982b}) Let x e R. Then, x € C(F(G)) ifand only if ZJEA x3 = v(A) and the optimal value of an optimal flow in Gu_x is zero.Let v denote the characteristic function of the simple network game I(Gu_T) inducedby Gu_.Lemma 6.2.2 For x E R, let Gt be defined as above. ThenmaxscT{v(S) — x(S)} = v*(T), (6.3)for any subset T of A.Proof First, observe that the fact that all arcs have unit capacity implies that we mayassume that in an optimal flow in the subgraph induced by some arc set S, each arc inS has either 0 or 1 unit of flow. Thus, we may identify the optimal flow with the subsetof arcs in S which have unit flow. The rest of the proof follows from the definition of anoptimal flow, i.e., a flow inducing maximum revenue, and the fact that x 0. Indeed,suppose the LHS is realized at R, R T, then since x > 0, we may assume that allarcs in R have unit flow in an optimal flow of the subgraph induced by R. Therefore,Chapter 6. Allocation through the Reactive Bargaining Set 144v(R)—x(R) = u(R) — x(R). Further,LHS of (6.3) = (u — x)(R)v’(T) = max{(u —by the definition of an optimal flow= max{v(S)—x(S)}, sincex>O= LHS of (6.3)..We are ready now to present and prove the main result of this section.Theorem 6.2.3 For a simple network game T(G), M’(F(G)) = C(F(G)).Proof Since C(F(G)) c M’(F(G)) (Granot [1994]), we only need to prove here thatM’(F(G)) ç G(F(G)). Suppose, on the contrary, that there exists x € MT(1’(G)) suchthat x 0 C(F(G)). Then, from Proposition 6.2.1, v*(A) > 0, and from Lemma 6.2.2,v*(A) maxscA(v(S) — x(S)) > 0. Let w E C(F(GL_x)). Since v*(A) > 0, there existsan arc i€A such that w > 0. We have,v*(A) = w(A)=w(A\i)+w2v*(A \ i) + w, since w € C(F(GL_x))> v*(A \ i), since w > 0. (6.4)We claim that in the game F(G), i is contained in every S such that e”(S, x)v(S)—x(S) = v*(A). Indeed, if i OS for such an S thene”(S,x) < max etJ(R,x)—RCA\i= v*(A \ i), from Lemma 6.2.2< v*(A), from Inequality (6.4).Chapter 6. Allocation through the Reactive Bargaining Set 145Now, let S’ be the largest coalition (with respect to set inclusion) such that e(S*, x) =v*(A). Clearly, i E S and since v(A) — x(A) = 0, S A. Let j E A \ S*. Then, ihas an objection against j in I’(G) with respect to x by using, for example, coalition S.Since x E MT(Il(G)), j should have a protecting coalition, say Q,j E Q,i Q, such thatfor any objection (y, S) of i against j there exists a vector z, indexed by Q, satisfying(6.2). We first claim that S fl Q 0. Indeed, if S fl Q = 0, thenev(S*UQ,x) = t’(S*UQ)_x(S*UQ)v(S*) + v(Q) — x(S*) — x(Q), by the superadditivity of v= e(S*, x) + e’(Q, x)e”(S,x), since et1(Q,x) 0,which contradicts the maximality of S*. Hence,S fl Q 0 and e(S*,x) > e’(Q,x) 0, (6.5)where the strict inequality follows from the fact that i Q.Let qi = IS fl QI and q = s \ QI, and consider the vector I!, whereI xk+(eh1(S*,x)_E), kES*flQYk keS*\Q,where is small enough and 0 < < e(S*, x). Clearly, (y, S*) is an objection of i againstj. Now, since Q is a protecting coalition for j against i, there exists a vector z, indexedby Q, such that (6.2) is satisfied. Thus,z(Q) = z(S* fl Q) + z(Q \ S*)y(S* fl Q) + x(Q \ S*), by (6.2)= x(S*flQ)+et(S ,x _ E+X(Q\S*), by the definition ofyChapter 6. Allocation through the Reactive Bargaining Set 146=> x(Q) + ev(Q, x), by (6.5) and for e small enough= v(Q).This contradicts the requirement that z be feasible for Q, i.e., the first equation in (6.2).The proof follows.Combining Theorem 6.2.3 with Proposition 1 of Kalai and Zemel [1982b], one obtainsthe following corollary.Corollary 6.2.4 Let I’(G) be the simple network game induced by the simple networkGu. Then MT(I’(G)) consists of all vectors x E R satisfyingx(A) = v(A) and u(p) = v(p) for every p e F,iEpwhere P is the set of all simple paths from s to t in G.Finally, since the kernel is contained in the reactive bargaining set (Granot [1994]),we haveCorollary 6.2.5 The kernel of a simple network game is contained in the core of thisgame.6.3 Constant-sum, Monotone Simple GamesA cooperative game is simple if its characteristic function is a (0, 1)-function. A simplegamer = (N;v) with N {1,2,. . . ,n} is a weighted majority game if there exist nonnegative numbers: q, w1, . . . , w such that for every coalition 8, v(S) = 1 if and only ifZEs to, > q. P is constant-sum if v(S) + v(N\ S) = v(N) for every coalition S. A playeri in P is said to be a dictator if v(S) = 1 if and only if i E S. In this section, we restrictour attention to constant-sum, monotone simple games.Chapter 6. Allocation through the Reactive Bargaining Set 147Theorem 6.3.1 Let I’ be a constant-sum, monotone simple game. Then, M”(P) =K(P).Proof If 1’ has a dictator, say player 1, then 1 has all the bargaining power. Consquently, in this case it is easy to verify that Mr(F) K(I’) = {(1,0,. . .Now, assume 1’ does not have a dictator. Then, F is 0-normalized, and thus K(1’) =FK(I’) (see Proposition 1.2.6). Since K(F) c M”(F) (Granot [1994j), it is sufficient toshow that MT(F) K(F). Suppose, on the contrary, that there exists x e MT(I’) suchthat x K(F)(= PK(F)). Then, there exist i,j e N, such that s,(x) > s,(x) andx > 0. We claim that in this case i has a justified objection against j, which contradictsthe assumption that x€M”(F).Indeed, since 1’ is constant-sum, monotone and does not have a dictator, v(N\ i) = 1,and thus it follows from x 0 that s(x) v(N\i)—x(N\i) = X 0. Hence, s,(x) > 0.Assume sj(x) = e(S, x) for some coalition S with i E S and j ‘ S. Clearly, v(S) = 1(since s,(x) = e(S, x) > 0), and i can raise an objection against player j through S. Toshow that i has a justified objection against j, we need to show that j does not have aprotecting coalition. Indeed, for any coalition Q, j e Q, i ‘ Q, if e(Q, x) 0, then sincex3 > 0 we must have that v(Q) = 1. However, since 1’ is constant-sum and monotone,SnQ 0. Thus, since e(S,x) = .s,(x) > .s,(x) > e(Q,x) and Sn Q 0, player i canalways dissolve such a coalition Q by offering players in S fl Q more than player j canpossibly offer them and still offer the rest of the players in S, including himself, slightlymore than what they currently get according to x. .Clearly, a constant-sum weighted majority game is monotonic, thus, its kernel, itsprekernel and its reactive bargaining set coincide. Aumann, Peleg and Rabinowitz [1965]and Aumann, Rabinowitz and Schmeidler [1966] computed the kernel of all simple gameswith up to 5 players. Kopelowitz [1967] computed the kernel (and the nucleolus) ofChapter 6. Allocation through the Reactive Bargaining Set 148all superadditive weighted majority games with 6 players, and constant-sum weightedmajority games with 7 players. Thus, an explicit description of the reactive bargainingset of all constant-sum weighted majority games with up to 7 players is available in theliterature.Another constant-sum, monotone simple game is the seven-person projective game.This game was first introduced by von Neumann and Morgenstern [1953]. Therein,the player set is N = {1,... , 7} and the winning coalitions are the supersets of thefollowing 7 minimal winning coalitions: {1,2,4}, {2,3,5}, {3,4,6}, {4,5,7}, {5,6,1},{6, 7, 2} and {7, 1, 3}. It can be easily verified that this game is constant-sum. Thus,from Theorem 6.3.1, the reactive bargaining set of this game coincides with its kernel.The kernel of this game was studied by Maschler and Peleg [19671. It consists of sevenstraight line segments each emanating from the nucleolus point (, , , , , , ) to apoint where a minimal winning coalition shares its worth equally among its members(e.g., (, , 0, , 0,0,0)). A constructive proof of the last result can also be found inGranot and Maschler [1994a].Bibliography[1] Aho, A.V., Hopcroft, J.E. and Uliman, J.D. (1974): The Design and Analysis ofComputer Algorithms, Addison-Wesley, Reading, Mass.[2] Aumann, R.J. (1989): Lectures on Game Theory, (Underground Classics in Economics), Westview Press.[3] Aumann, R.J. and Maschler, M. (1964): “The bargaining set for cooperative games”,Advances in Game Theory, M. Dresher, L.S. Shapley and A. Tucker ed., Annals ofMath. Studies, 52, Princeton University Press, Princeton, 443—476.[4] Aumann, R.J., Peleg, B. and Rabinowitz, P. (1965): “A method for computing thekernel of n-person games”, Math. of Computing, 19, 531—551.[5] Aumann, R.J., Rabinowitz, P. and Schmeidler, D. (1966): “Kernels of superadditivesimple 5-person games that are not weighted majority games”, Research Program inGame Theory and Mathematical Economics, Dept. of Math., The Hebrew Universityof Jerusalem, RM 18.[6] Bird, C. G. (1976): “On cost allocation for a spanning tree: A game theoreticapproach”, Networks 6, 335—350.[7] Boiteux, M. (1971): “On the management of public monopolies subject to budgetaryconstraints”, J. of Econ. Theory, 3, 2 19—240.[8] Bondareva, O.N. (1961): “The core of an n-person game”, Vestnik Leningrad University, 17, 141—142.[9] Bondy, J.A. and Murty, U.S.R. (1976): Graph Theory with Applications, ElsevierScience Publishing Co., Inc., New York.[101 Charnes, A. and Kortanek, K.O. (1967): “On balanced sets, cores, and linear programming”, Cahiers du Centre d’Etudes de Recherche Operationnelle, Bruxelles, 9,32—43.[11] (1970): “On classes of convex and preemptive nuclei for n-person games”,in Proc. Princeton Symposium on Math. Frog., (ed. H.W.Kuhn), Princeton University Press, Princeton, NJ, 377—390.149Bibliography 150[12] Claus, A. and Granot, D. (1976): “Game theory application to cost allocation for aspanning tree”, Working paper no. 402, Faculty of Commerce and Business Administration, UBC, Vancouver.[13] Curiel, I.J., Pederzoli, C. and Tijs, S.H. (1989): “Sequencing games”, European J.of OR, 40, 344—351.[14] Curien, N. (1983): “Cost allocation and pricing policy: The case of French telecommunications”, in Cost Allocation: Methods, Principles, Applications (ed. by H.P.Young), Elseviers Science Publishers B.V., The Netherlands.[15] Davis, M. and Maschler, M. (1965): “The kernel of a cooperative game”, Naval Res.Logist. Quart., 12, 223—259.[16] (1967): “Existence of stable payoff configurations for cooperativegames”, in Essays in Mathematical Economics in Honor of Oskar Morgenstern, (M.Shubik, ed.), Princeton University Press, Princeton, New Jersey, 39—52.[17] Derks, J. and Kuipers, J. (1992): “On the core and nucleolus of routing games”, Report M 92-07, Department of Mathematics, University of Limburg, the Netherlands,to appear in mt. J. of GT.[18] Dubey, P. and Shapley, L.S. (1984): “Totally balanced games arising from controlledprogramming problems”, Math. Prog., 29, 245—267.[19] Federgruen, A., Queyranne, M. and Zheng, Y.S. (1989): “Simple Power of TwoPolices are Close to Optimal in a General Class of Production/Inventory Networkswith General Joint Setup Costs”, Math. of OR, 17, 95 1—963.[20] Fishburn, P.C. and Pollak, 11.0. (1983): “Fixed-route cost allocation”, AmericanMath. Monthly, 90, 366—378.[21] Gaul, Z. (1980): “Applications of efficient mergeable heaps for optimization problemson trees”, Acta Informatica, 13, 53—58.[22] Garey, M.R. and Johnson, D.S. (1979): Computers and Intractability: A Guide tothe Theory of NP-Completeness, Freeman, San Francisco.[23] Gately, D. (1974): “Sharing the gains from regional cooperation: a game theoreticapplication to planning investment in electric power”, International Economic Review, 15, 195—208.[24] Granot, D. (1986): “A generalized linear production model: A unifying model”,‘Iath. Prog. 34, 212—223.Bibliography 151[25] (1987): “On the role of cost allocation in locational models”, OperationsResearch, 35, 234—248.[26] (1994): “On a new bargaining set for cooperative games and on assignment games”, Working paper, Faculty of Commerce and Business Adminstration,UBC, Vancouver.[27] Granot, D. and Granot, F. (1992a): “On some network flow games”, Math. of OR,[28] (1992b): “Computational complexity of a cost allocation approach to afixed cost spanning forest problem”, Math. of OR, 17, 765—780.[29] Granot, D., Granot, F. and Zhu, W.R. (1994a): “Circular Network Games”, Workingpaper, Faculty of Commerce and Business Adminstration, UBC, Vancouver.[30] (1994b): “On the characterization set for the nucleolus”, Working paper,Faculty of Commerce and Business Adminstration, UBC, Vancouver.[31] (1994c): “Naturally submodular digraphs and forbidden digraph configurations”, Working paper, Faculty of Commerce and Business Adminstration, UBC,Vancouver.[32] Granot, D. and Hojati, M. (1990): “On cost allocation in communication networks”,Networks, 20, 209—229.[33] Granot, D. and Huberman, G. (1981): “Minimum cost spanning tree games”, Math.Prog. 21, 1—18.[34] (1982): “The relationship between convex games and minimum costspanning tree games: a case for permutationally convex games”, SIAM J. Aig. andDisc. Math., 3, 288—292.[35] (1984): “On the core and nucleolus of minimum cost spanning treegames”, Math. Prog. 29, 323—347.[36] Granot, D. and Maschler, M. (1994a): “Spanning network games”, Working paper,Faculty of Commerce and Business Adminstration, UBC, Vancouver.[37] (1994b): “The reactive bargaining set: structure, dynamics and extension to NTU games”, Working paper, Faculty of Commerce and Business Adminstration, UBC, Vancouver.1381 Granot, D., Maschler, M., Owen, G. and Zhu, W.R. (1994): “The kernel/nucleolusof a standard tree game”, to appear in mt. J. of GT.Bibliography 152[39] Herer, Y. (1990): “Submodularity and the traveling salesman problem”, Tech. Report No. 915, School of Operations Research and Industrial Engineering, CornellUniversity, Ithaca.[40] Herer, Y. and Penn, M. (1994): “Characterizations of naturally submodular graphs:A polynomial solvable class of the TSP”, to appear in Proc. of the AMS.[41] Herer, Y. and Roundy, R. (1990): “Heuristics for a one warehouse multi-retailerdistribution problem with performance bounds”, Tech. Report No. 916, School ofOperations Research and Industrial Engineering, Cornell University, Ithaca.[42] Huberman, G. (1980): “The nucleolus and essential coalitions”, Analysis and Optimization of Systems, Springer, Berlin, 4 16—422.[43] James, L.D. and Lee, R.R. (1971): Economics of Water Resources Planning, NewYork: McGraw-Hill.[44] Johnson, L. (1982): “Competition and cross-subsidization in the telephone industry”, Rand report R-2976-RC/NSF, Rand Corp., Santa Monica, CA.[45] Kalai, E. and Zemel, E. (1982a): “Totally balanced games and games of flow”, Math.of OR, 30, 476—478.[46] (1982b): “Generalized network problems yielding totally balancedgames”, Math. of OR. 30, 998—1008.[47] Kopelowitz, A. (1967): “Computation of the kernels of simple games and the nucleolus of n-person games”, RM-31, Math. Dept., The Hebrew University of Jerusalem.[48] Kuipers, J. (1991): “A note on the 5-person traveling salesman games”, Zeitschriftfür Operations Research, 21, 339—351.[49] Littlechild, S.C. (1970): “A game theoretic approach to public utility pricing”, Western Econ. J., 8(2), 162—166.[50] (1974): “A simple expression for the nucleolus in a special case”, mt. J.of GT, 3, 21—29.[51] Littlechild, S.C. and Owen, C. (1977): “A further note on the nucleolus of the‘airport game”, mt. J. of GT, 6, 91—95.[52] Littlechild, S.C. and Thompson, G.F. (1977): “Aircraft landing fees: a game theoryapproach”, The Bell J. of Ec. 8, 186—204.[53] Louderback, J.G. (1976): “Another approach to allocating joint costs: a comment”,Accounting Review, 50, 683—685.Bibliography 153[54] Manne, A. (1952): “Multipurpose public enterprises— criteria for pricing”, Economica, N.S.19, 322—326.[55] Maschler, M. (1994): “The bargaining set, kernel, and nucleolus”, in Handbook ofGame Theory, R.J. Aumann and S. Hart, eds., Elsevier Science Publishers B.V.,Amsterdam, North Holland, 591—667.[56] Maschler, M. and Peleg, B. (1966): “A characterization, existence proof and dimension bounds for the kernel of a game”, Pacific J. Math., 18, 289—328.[57] (1967): “The structure of the kernel of a cooperative game”, SIAM J.of App. Math. 15, 569—604.[58] Maschler, M., Peleg, B. and Shapley, L.S. (1972): “The kernel and bargaining set ofconvex games”, mt. J. of GT, 2, 73—93.[59] (1979): “Geometric properties of the kernel, nucleolus, and related solution concepts”, Math. OR, 4, 303—338.[60] Megiddo, N. (1978): “Computational complexity of the game theory approach tocost allocation for a tree”, Math. of OR, 3, 189—196.[61] Mitchell, B. (1979): “Pricing policies in selected Euporean telephone systems”, Proc.of the Sixth Annual Telecom. Policy Res. Conf., ed. by H.D. Dordick.[62] Moriarity, 5. (1975): “Another approach to allocating joint costs”, Accounting Review, 49, 791—795.[63] (1976): “Another approach to allocating costs: a reply”, AccountingReview, 50, 686—687.[64] Nova Scotia Provincial Government (1976): “Description of CATV microwave costsharing in the Maritimes”, Office of Communications Policy, P.O.Box 701, Halifax,Nova Scotia.[65] Owen, G. (1975): “On the core of linear production games”, Math. Prog. 9, 358—371.[66] Parker, T. (1943): “Allocation of the Tennessee Valley Authority projects”, Trans.of ASGE, 108, 174—187.[67] Peleg, B. (1986): “On the reduced game property and its converse”, mt. J. of GT,15, 187—200.[68] Potters, J.A.M., Curiel, I.J. and Tijs, S.H. (1992): “Travelling salesman games”,Math. Prog. 53, 199—211.Bibliography 154[69] Queyranne, M. (1985): “A polynomial-time, submodular extension to Roundy’s98%-effective heuristic for production/inventory systems”, Working paper NO. 1136,Faculty of commerce and Business Adiministration, University of British Columbia,Vancouver.[70] Ramsey, F. (1927): “A contribution to the theory of taxation”, Economic J., 37,47—61.[71] Ransmeier, J.S. (1942): The Tennessee Valley Authority: A Case Study in the Economics of Multiple Purpose Stream Planning, Vanderbilt University Press, Nashville,TN.[72] Rosenmüller, J. (1982): “LP games with sufficiently many players”, mt. J. of CT,11, 124—149.[73] Roundy, R. (1986): “A 98%-effective lot-sizing rule for multi-product, multi-stageproduction/inventory system”, Math. of OR, 11, 699—727.[74] Samet, D. and Zemel, E. (1984): “On the core and dual set of linear programminggames”, Math. of OR, 9, 309—3 16.[75] Schmeidler, D. (1969): “The nucleolus of a characteristic function game”, SIAM J.Appl. Math., 17, 1163—1170.[76] Shapley, L.S. (1967): “On balanced sets and cores”, Naval Res. Logist. Quart., 14,453—460.[77] (1971): “Cores of convex games”, mt. J. of GT, 1, 11—26.[78] Shapley, L.S. and Shubik, M. (1972): “The assignment game I: The core”, mt. J. ofGT, 1, 111—130.[79] Sharkey, W.W. (1982): “Suggestions for a game-theoretic approach to public utilitypricing and cost allocation”, Bell J. of Econ., 13, 57—68.[80] (1983): “Economic and game-theoretic issues associated with cost allocation in a telecommunications network”, in Cost Allocation: Methods, Principles,Applications (ed. by H.P. Young), Elseviers Science Publishers B.V., The Netherlands.[81] (1991): “Supportability of network cost functions”, Ann. of OR.[82] Solymosi, T. and Raghavan, T.E.S. (1994): “An algorithm for finding the nucleolusof assignment games”, mt. J. of GT, 23, 119—143.Bibliography 155[83] Straffin, P. and Heaney, J.P. (1981): “Game theory and the Tennessee Valley Authority”, mt. J. of GT, 10, 35—43.[84] Tamir, A. (1980): “On the core of cost allocation games defined on location problems”, Department of Statistics, Tel-Aviv University.[85] (1989): “On the core of a traveling salesman cost allocation game”,Oper. Res. Letters, 8, 31—34.[86] (1991): “On the core of network synthesis games”, Math. Prog. 50,123—135.[87] Tardos, E. (1986): “A strongly polynomial algorithm to solve combinatorial linearprograms”, Oper. Res. 34, 250-256.[88] Von Neumann, J. and Morgenstern, 0. (1953): Theory of Games and EconomicBehavior, (First edition in 1944), Princeton University Press, Princeton, New Jersey.[89] Young, H.P., Okada, N. and Hashimoto, T. (1981): “Cost allocation in water resource development”, Water Resource Research, 18, 463—475.[90] Zajac, E. (1978): Fairness or Efficiency: An Introduction to Public Utility Pricing,Ballinger, Cambridge, MA.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Cost/revenue allocation on networks
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Cost/revenue allocation on networks Zhu, Richard Weiping 1995
pdf
Page Metadata
Item Metadata
Title | Cost/revenue allocation on networks |
Creator |
Zhu, Richard Weiping |
Date Issued | 1995 |
Description | The thesis addresses some theoretical and computational issues arising from cost and revenue allocation problems in networks. It employs techniques from mathematical pro- gramming, combinatorial optimization and graph theory, as well as methodology devel- oped in game theory. In Chapter 2, two related cost allocation problems arising from circular networks, namely, traveling salesman cost allocation and construction cost allocation, are anal- ysed. In Chapter 3, the problem of allocating construction and maintenance cost of a tree enterprise, such as a telecommunication network or a cable-vision network, is stud- ied. In both chapters, the main solution concepts (core, kernel, prekernel and nucleolus) developed in cooperative game theory are evaluated as possible cost allocation schemes for the above allocation problems. Interesting geometric relationships among these so- lution concepts are derived and some characterizations of them are obtained. These characterizations suggest that the nucleolus is one of the most prominent choices as an allocation scheme for all the cost allocation problems considered in my thesis. Efficient, strongly polynomial algorithms are then developed for calculating the nucleolus of these games. Although the general approach in Chapters 2 and 3 is similar, the techniques used in each chapter for developing the computational algorithms are different. In the second part of the thesis, three related theoretical issues are investigated. In Chapter 4, a complete characterization of naturally submodular digraphs is derived in terms of forbidden digraph configurations and graph decomposition. One motivation for such a characterization is that naturally submodular digraphs have many desirable properties which are useful for analysing cost/revenue allocation problems and some other problems arising in logistics. In Chapter 5, a generic scheme for computing the nucleolus of a general cooperative game is developed. Finally, in Chapter 6 the possible use of the bargaining set as a cost allocation scheme is evaluated. In particular, it is shown therein that D.Granot’s bargaining set coincides with the core in simple network flow games, and it coincides with the kernel for simple, monotone, constant-sum games. |
Extent | 3087479 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
FileFormat | application/pdf |
Language | eng |
Date Available | 2009-06-05 |
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.0079978 |
URI | http://hdl.handle.net/2429/8831 |
Degree |
Doctor of Philosophy - PhD |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 1995-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_1995-983760.pdf [ 2.94MB ]
- Metadata
- JSON: 831-1.0079978.json
- JSON-LD: 831-1.0079978-ld.json
- RDF/XML (Pretty): 831-1.0079978-rdf.xml
- RDF/JSON: 831-1.0079978-rdf.json
- Turtle: 831-1.0079978-turtle.txt
- N-Triples: 831-1.0079978-rdf-ntriples.txt
- Original Record: 831-1.0079978-source.json
- Full Text
- 831-1.0079978-fulltext.txt
- Citation
- 831-1.0079978.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0079978/manifest