"The Cost of Stability in Network Flow Games"

Speaker: Ezra Resnick, The Hebrew University
Date: Wednesday, 4 February 2009
Time: 12noon
Place: Ross 201

Abstract:

Cooperative game theory solution concepts define ways of dividing a
coalition's gains among its members ("imputations"). A prominent
solution concept is the core, focusing on stable imputations where no
subset of agents has an incentive to leave the grand
coalition. However, some games have empty cores.

We consider stabilizing cooperative games by having an external party
offer a supplemental payment to the grand coalition. The adjusted
gains, the sum of this payment and the original gains of the
coalition, may be divided among agents in a stable manner. We call a
division of the adjusted gains a super-imputation, and the minimal sum
of payments that stabilizes a game the cost of stability (CoS).

We examine the CoS in threshold network flow games, where each agent
controls an edge in the network and a coalition of agents succeeds if
the maximal flow it can send from the source to the sink exceeds a
certain threshold. We show that it is CoNP-complete to determine
whether a given super-imputation in such a game is stable. We give
bounds on the CoS in general network flow games, and provide efficient
algorithms for computing the CoS and finding stable super-imputations
in several restricted cases.

Joint work with Yoram Bachrach and Jeff Rosenschein.