Koh Zhuan Khye, Sanità Laura
Department of Mathematics, London School of Economics and Political Science, London, UK.
Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Canada.
Math Program. 2020;183(1):359-377. doi: 10.1007/s10107-020-01499-w. Epub 2020 Apr 25.
form an important class of problems in game theory, where a key goal is to distribute a value among a set of players who are allowed to cooperate by forming coalitions. An outcome of the game is given by an allocation vector that assigns a value share to each player. A crucial aspect of such games is (or ). Indeed, convex instances of cooperative games exhibit several nice properties, e.g. regarding the existence and computation of allocations realizing some of the most important solution concepts proposed in the literature. For this reason, a relevant question is whether one can give a polynomial-time characterization of submodular instances, for prominent cooperative games that are in general non-convex. In this paper, we focus on a fundamental and widely studied cooperative game, namely . An efficient recognition of submodular instances of this game was not known so far, and explicitly mentioned as an open question in the literature. We here settle this open problem by giving a polynomial-time characterization of submodular spanning tree games.
在博弈论中构成了一类重要的问题，其中一个关键目标是在一组玩家中分配一个值，这些玩家可以通过形成联盟来进行合作。博弈的结果由一个分配向量给出，该向量为每个玩家分配一个值份额。此类博弈的一个关键方面是（或）。实际上，合作博弈的凸实例展现出若干良好性质，例如关于实现文献中提出的一些最重要解概念的分配的存在性和计算。出于这个原因，一个相关问题是对于通常非凸的著名合作博弈，是否能给出次模实例的多项式时间特征描述。在本文中，我们关注一个基础且被广泛研究的合作博弈，即。到目前为止，尚未得知对该博弈的次模实例的有效识别，并且在文献中明确作为一个开放问题提及。我们在此通过给出次模生成树博弈的多项式时间特征描述来解决这个开放问题。
