TY - JOUR
T1 - An efficient characterization of submodular spanning tree games
AU - Koh, Zhuan Khye
AU - Sanità, Laura
PY - 2020/9/1
Y1 - 2020/9/1
N2 - Cooperative games 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 submodularity (or convexity). 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 the spanning tree game. 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.
AB - Cooperative games 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 submodularity (or convexity). 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 the spanning tree game. 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.
KW - 05C05 Trees
KW - 05C57 Games on graphs (graph-theoretic aspects)
KW - 91A12 Cooperative games
UR - http://www.scopus.com/inward/record.url?scp=85084128922&partnerID=8YFLogxK
U2 - 10.1007/s10107-020-01499-w
DO - 10.1007/s10107-020-01499-w
M3 - Article
C2 - 32863434
AN - SCOPUS:85084128922
VL - 183
SP - 359
EP - 377
JO - Mathematical Programming
JF - Mathematical Programming
SN - 0025-5610
IS - 1-2
ER -