Open Collections

Cost/revenue allocation on networks

University of British Columbia

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.

Thesis/Dissertation

application/pdf

2009-06-05

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.

http://hdl.handle.net/2429/8831

Mathematics

University of British Columbia

UBCV

DSpace