Skoči na glavni sadržaj

Izvorni znanstveni članak

https://doi.org/10.20532/cit.2020.1005188

Network Connectivity Game

Darko Skorin-Kapov ; Robert B. Willumstad School of Business, Adelphi University, Garden City, New York, United States
Jadranka Skorin-Kapov orcid id orcid.org/0000-0001-6926-5355 ; Robert B. Willumstad School of Business, Adelphi University, Garden City, New York, United States


Puni tekst: engleski pdf 959 Kb

str. 73-87

preuzimanja: 166

citiraj


Sažetak

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. The NC game is related to the Minimum Cost Spanning Tree games and to the Shortest Path games. The profound difference is that in those games the service is delivered from some common source node to the rest of the network, while in the NC game there is no source and the service is established through the two-way interaction among all pairs of participating nodes. 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.

Ključne riječi

networks, cost allocation, cooperative games, mathematical programming

Hrčak ID:

259327

URI

https://hrcak.srce.hr/259327

Datum izdavanja:

11.6.2021.

Posjeta: 452 *