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 programming

Scheduled

TD3 Game Theory and Multicriteria Decision
June 10, 2021  2:45 PM
3 - TC Koopmans


Other papers in the same session

On reward-penalty-selection games

T. Heller, S. O. Krumke

Ordinal cost coefficients in matroid optimization

J. Sudhoff, K. Klamroth, M. Stiglmayr


Latest news

  • 6/5/21
    Conference abstract book

Cookie policy

We use cookies in order to be able to identify and authenticate you on the website. They are necessary for the correct functioning of it, and therefore they can not be disabled. If you continue browsing the website, you are agreeing with their acceptance, as well as our Privacy Policy.

Additionally, we use Google Analytics in order to analyze the website traffic. They also use cookies and you can accept or refuse them with the buttons below.

You can read more details about our Cookie Policy and our Privacy Policy.