Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
The Cost of Stability in Network Flow Games

Ezra Resnick, Yoram Bachrach, Reshef Meir, and Jeff Rosenschein

Abstract

The core of a cooperative game contains all stable distributions of a coalition’s gains among its members. However, some games have an empty core, with every distribution being unstable. We allow an external party to offer a supplemental payment to the grand coalition, which may stabilize the game, if the payment is sufficiently high. We consider the cost of stability (CoS)—the minimal payment that stabilizes the game.

We examine the CoS in threshold network flow games (TNFGs), where each agent controls an edge in a flow network, and a coalition wins if the maximal flow it can achieve exceeds a certain threshold. We show that in such games, it is coNP-complete to determine whether a given distribution (which includes an external payment) is stable. Nevertheless, we show how to bound and approximate the CoS in general TNFGs, and provide efficient algorithms for computing the CoS in several restricted cases.

Details

Publication typeInproceedings
Published inMFCS 2009
> Publications > The Cost of Stability in Network Flow Games