Composition Games for Distributed Systems: The EU Grant Games

Shay Kutten, Ron Lavi, Amitabh TrehanAAAI 2013 · DOI

Introduction

In distributed systems, from peer-to-peer file sharing to international research consortia like the EU’s Framework Programmes, agents must navigate the complex dynamics of group formation. This "Goldilocks" problem involves balancing two opposing forces: the Force of Cooperation, where agents join groups to meet eligibility thresholds (e.g., resource requirements), and the Force of Dilution, where oversized groups suffer from overhead or the splitting of a fixed prize among too many participants. This paper investigates how protocol design and network topology influence the quality of these groups when agents act selfishly.

Game Theoretic Framework

The authors model group formation as a non-cooperative game. To evaluate the efficiency of different protocols, they utilize the Price of Anarchy (PoA) and the Strong Price of Anarchy (SPOA). While PoA measures the inefficiency of the worst-case Nash Equilibrium, SPOA focuses on "Strong Equilibria"—states where no subset of players can collectively deviate to improve their individual utilities. This is particularly relevant for collaborative environments where agents can coordinate their actions.

Protocol Comparison

The study compares three distinct "consortium" protocols:

  1. The Gold-Rush Game: A low-barrier system where agents join groups by simple declaration. This leads to a "tragedy of the commons" with a disastrous PoA proportional to the number of agents ($n$), as low-value agents crowd out quality.
  2. Consensual Consortium Composition (CCC): Requires unanimous agreement among all group members. While more stable, it introduces a "Gatekeeper" problem.
  3. The MAGNET CCC Game: An extension of CCC that includes an appeals process. If a group forms, external agents can appeal to join if their inclusion improves the group's average quality.

The Gatekeeper Problem and Network Topology

In the CCC game, existing members may selfishly block high-value researchers to avoid sharing the prize, even if the newcomer would increase the group's average quality. On general (non-clique) networks, this behavior can lead to an SPOA as high as 3, meaning the resulting group is only one-third as good as the social optimum.

Figure 3: An illustration of the "Gatekeeper" problem in a general network. A group (red) might exclude a high-value member (green) to maximize individual shares, resulting in a suboptimal social outcome.

The Power of Appeals in MAGNET

The MAGNET protocol mitigates the gatekeeper problem by mandating the inclusion of any agent whose presence raises the average quality. This mechanism ensures that the SPOA never exceeds 2, regardless of the network topology. For specific topologies like Line Networks, the authors provide tighter bounds, showing the SPOA is approximately $1 + (k-1)/k$, where $k$ is the size of the optimal group.

Figure 2: A line network construction used to analyze the Strong Price of Anarchy, illustrating how restricted connectivity impacts the formation of optimal consortia.

Key Results and Connectivity

The research highlights a critical link between network connectivity and efficiency:

  • Cliques: High connectivity naturally lowers anarchy. In a clique, the MAGNET protocol's SPOA approaches 1 (the social optimum) as group size increases.
  • General Networks: The MAGNET protocol provides a robust guarantee, keeping SPOA $\le 2$.

Conclusion

By introducing a simple appeals process, distributed systems can significantly improve the quality of self-organized groups. While network structure plays a role in limiting efficiency, protocol design—specifically mechanisms that prevent selfish exclusion—is the primary driver in reaching near-optimal social outcomes.

Summary updated

BibTeX
@inproceedings{kutten2013composition,
  author = {Shay Kutten and Ron Lavi and Amitabh Trehan},
  title = {{Composition Games for Distributed Systems: The EU Grant Games}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2013},
  doi = {10.1609/aaai.v27i1.8636},
}
Figure