D. Skorin-Kapov, J. Skorin-Kapov
We investigate the cost allocation strategy associated with the problem of providing service/communication between all pairs of network nodes. There is a cost associated with each link and the communication between any pair of nodes can be delivered via paths connecting those nodes. The example of a cost efficient solution which could provide service for all node pairs is a (non-rooted) minimum cost spanning tree. The cost of such a solution should be distributed among users who might have conflicting interests. The objective of this paper is to formulate the above cost allocation problem as a cooperative game, to be referred to as a Network Connectivity (NC) game, and develop a stable and efficient cost allocation scheme. We formulate Network Connectivity (NC) game and construct an efficient cost allocation algorithm which finds some points in the core of the NC game. Finally, we discuss the Egalitarian Network Cost Allocation (ENCA) rule and demonstrate that it finds an additional core point.
Keywords: networks, cost allocation, cooperative games, mathematical programmingScheduled
TD3 Game Theory and Multicriteria Decision
June 10, 2021 2:45 PM
3 - TC Koopmans