Sharing Rewards in Cooperative Connectivity Games

Yoram Bachrach, Ely Porat, and Jeffrey S. Rosenschein

Abstract

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.

Details

Publication typeArticle
Published inArtificial Intelligence Research
> Publications > Sharing Rewards in Cooperative Connectivity Games