Reproduce “Cooperative Games with Overlapping Coalitions” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Georgios Chalkiadakis, Edith Elkind, Evangelos Markakis, Maria Polukarov, Nicholas Robert Jennings

A formal model for cooperative games with overlapping coalitions (OCF-games) is introduced, where agents can contribute fractional resources to multiple simultaneous tasks. The work defines three distinct core stability concepts (c-core, r-core, o-core) for this setting, proving their hierarchical relationship and analyzing their computational complexity for Threshold Task Games.

Key insights

  • The interpretation of "deviation" in overlapping coalition settings significantly impacts stability, leading to a hierarchy of core concepts (o-core ⊆ r-core ⊆ c-core) with strict containments.
  • Allowing overlapping coalitions can lead to higher social welfare and a different stability landscape compared to traditional disjoint coalition models or fuzzy game approaches.
  • While c-core membership and non-emptiness can be tractable for certain input representations (unary weights) in Threshold Task Games, r-core and o-core membership remain computationally hard, highlighting fundamental differences in their tractability.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.