This paper addresses the optimization problem to maximize the total costs that can be shared among a group of agents, while maintaining stability in the sense of the core constraints of a cooperative transferable utility game, or TU game. This means that all subsets of agents have an outside option at a certain cost, and stability requires that the cost shares are defined so that none of the outside options is preferable. When maximizing total shareable costs, the cost shares must satisfy all constraints that define the core of a TU game, except for being budget balanced. The paper gives a fairly complete picture of the computational complexity of this optimization problem, in relation to classical computational problems on the core. We also show that, for games with an empty core, the problem is equivalent to computing minimal core relaxations for several relaxations that have been proposed earlier. As an example for a class of cost sharing games with non-empty core, we address minimum cost spanning tree games. While it is known that cost shares in the core can be found efficiently, we show that the computation of maximal cost shares is NP-hard for minimum cost spanning tree games. We also derive a 2-approximation algorithm. Our work opens several directions for future work.

翻译：本文探讨优化问题,以最大限度地增加一组代理商可以分担的总费用,同时保持合作可转让公用事业游戏或TU游戏核心限制的稳定性。这意味着所有代理商子集有一定成本的外部选择,而稳定要求成本分成的定义是,任何外部选择都不可取。在最大限度地增加总可分摊成本时,成本份额必须满足所有制约,这些制约定义了TU游戏的核心,但预算平衡除外。该文件相当完整地描述了这一优化问题在核心经典计算问题方面的计算复杂性。我们还表明,对于一个空核心游戏,问题相当于计算先前提出的若干放松的最低限度核心放松。作为非空白核心成本分担游戏类别的一个范例,我们处理的是最小成本分担成本覆盖树类游戏。虽然人们知道核心中的成本份额是可以高效率找到的,但我们表明,对于最小成本跨越树类游戏而言,最大成本份额的计算是很难的。我们还为未来工作制定了一些方向。</s>