0
喜欢
0
书签
声明论文
The Cost of Stability in Network Flow Games   
摘  要:   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 distri- bution (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.
发  表:   Mathematical Foundations of Computer Science  2009

论文统计图
共享有6个版本
 [展开全部版本] 

Bibtex
创新指数 
阅读指数 
重现指数 
论文点评
还没有人点评哦

Feedback
Feedback
Feedback
我想反馈:
排行榜