We consider how selfish agents are likely to share revenues derived from maintaining connectivity between important network servers. We model a network where a failure of
one node may disrupt communication between other nodes as a cooperative game called
the vertex Connectivity Game (CG). In this game, each agent owns a vertex, and controls
all the edges going to and from that vertex. A coalition of agents wins if it fully connects
a certain subset of vertices in the graph, called the primary vertices.
Power indices measure an agent’s ability to affect the outcome of the game. We show
that in our domain, such indices can be used to both determine the fair share of the
revenues an agent is entitled to, and identify significant possible points of failure affecting
the reliability of communication in the network. We show that in general graphs, calculating
the Shapley and Banzhaf power indices is #P-complete, but suggest a polynomial algorithm
for calculating them in trees.
We also investigate finding stable payoff divisions of the revenues in CGs, captured
by the game theoretic solution of the core, and its relaxations, the ǫ-core and least core.
We show a polynomial algorithm for computing the core of a CG, but show that testing
whether an imputation is in the epsilon-core is coNP-complete. Finally, we show that for trees, it is possible to test for epsilon-core imputations in polynomial time.