资源论文The Tractability of the Shapley Value over Bounded Treewidth Matching Games

The Tractability of the Shapley Value over Bounded Treewidth Matching Games

2019-10-29 | |  42 |   34 |   0
Abstract Matching games form a class of coalitional games that attracted much attention in the literature. Indeed, several results are known about the complexity of computing over them solution concepts. In particular, it is known that computing the Shapley value is intractable in general, formally #P-hard, and feasible in polynomial time over games defined on trees. In fact, it was an open problem whether or not this tractability result holds over classes of graphs properly including acyclic ones. The main contribution of the paper is to provide a positive answer to this question, by showing that the Shapley value is tractable for matching games defined over graphs having bounded treewidth. The proposed polynomial-time algorithm has been implemented and tested on classes of graphs having different sizes and treewidth up to three

上一篇:The Many Benefits of Annotator Rationales for Relevance Judgments

下一篇:Verification of Broadcasting Multi-Agent Systems against an Epistemic Strategy Logic

用户评价
全部评价

热门资源

  • Learning to Predi...

    Much of model-based reinforcement learning invo...

  • Stratified Strate...

    In this paper we introduce Stratified Strategy ...

  • The Variational S...

    Unlike traditional images which do not offer in...

  • Learning to learn...

    The move from hand-designed features to learned...

  • A Mathematical Mo...

    Direct democracy, where each voter casts one vo...