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

This paper addresses the optimization problem to maximize the total coststhat can be shared among a group of agents, while maintaining stability in thesense of the core constraints of a cooperative transferable utility game, or TUgame. When maximizing total shareable costs, the cost shares must satisfy allconstraints that define the core of a TU game, except for being budgetbalanced. The paper first gives a fairly complete picture of the computationalcomplexity of this optimization problem, its relation to optimiztion over thecore itself, and its equivalence to other, minimal core relaxations that havebeen proposed earlier. We then address minimum cost spanning tree (MST) gamesas an example for a class of cost sharing games with non-empty core. Whilesubmodular cost functions yield efficient algorithms to maximize shareablecosts, MST games have cost functions that are subadditive, but generally notsubmodular. Nevertheless, it is well known that cost shares in the core of MSTgames can be found efficiently. In contrast, we show that the maximization ofshareable costs is NP-hard for MST games and derive a 2-approximationalgorithm. Our work opens several directions for future research.

Algorithmic Solutions for Maximizing Shareable Costs