English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Cooperative games provide a framework to study cooperation amongself-interested agents. They offer a number of solution concepts describing howthe outcome of the cooperation should be shared among the players.Unfortunately, computational problems associated with many of these solutionconcepts tend to be intractable---NP-hard or worse. In this paper, weincorporate complexity measures recently proposed by Feige and Izsak (2013),called dependency degree and supermodular degree, into the complexity analysisof cooperative games. We show that many computational problems for cooperativegames become tractable for games whose dependency degree or supermodular degreeare bounded. In particular, we prove that simple games admit efficientalgorithms for various solution concepts when the supermodular degree is small;further, we show that computing the Shapley value is always in FPT with respectto the dependency degree. Finally, we note that, while determining thedependency among players is computationally hard, there are efficientalgorithms for special classes of games.

Cooperative Games with Bounded Dependency Degree