Probability Bounds for Overlapping Coalition Formation

Michail Mamakos, Georgios ChalkiadakisIJCAI 2017 · DOI

TL;DR

This paper introduces novel methods for agents to form overlapping coalitions under uncertainty about others' resource contributions. By deriving probability bounds, agents can make more informed decisions about coalition formation, leading to improved task completion rates compared to simpler baseline approaches.

What Problem Does This Paper Address?

In many real-world scenarios, agents need to collaborate to achieve goals that are beyond their individual capabilities. This often involves forming coalitions. While cooperative game theory has extensively studied coalition formation, most existing work assumes that agents can only belong to a single coalition at a time (disjoint coalitions) and that agents have perfect knowledge of each other's resources.

This paper tackles two key challenges:

  1. Overlapping Coalitions: Agents may need to participate in multiple coalitions simultaneously to maximize their utility. This is known as overlapping coalition formation (OCF).
  2. Uncertainty: Agents typically don't know the exact amount of resources others are willing to contribute. They only have private beliefs about these contributions. This uncertainty makes it difficult to reliably assess whether a coalition will succeed in completing a task.

The authors aim to provide agents with tools to reason probabilistically about coalition success under these conditions, enabling them to make better decisions about which coalitions to join or form.

Methods

The paper proposes three novel methods for agents to derive probability bounds on the success of a coalition, given their private beliefs about other agents' resource investments. These methods are designed to be computationally efficient, avoiding the need to compute exact probability distributions.

  • IPZY Method: This method is based on an improved version of the Paley-Zygmund inequality. It provides a lower bound on the probability that a coalition's total resource contribution exceeds a certain threshold.
  • CH2S Method: This approach manipulates the two-sided Chebyshev's inequality. Similar to IPZY, it offers a lower bound on the probability of successful task completion.
  • HF Method: This method leverages Hoeffding's inequality, which is applicable to sums of independent random variables with bounded ranges. It also provides a probability bound.

All three methods allow agents to specify a desired confidence level for the coalition's success. The paper also introduces a generic protocol for iterated overlapping coalition formation. In this protocol, agents act as proposers for tasks, sample potential coalition members, use one of the proposed methods (IPZY, CH2S, or HF) to select the best coalition based on the desired confidence level, and then submit proposals. Agents respond to proposals, and beliefs are updated based on responses and task outcomes.

Datasets

The authors evaluate their methods using two types of graphs:

  1. Erdős-Rényi Random Graph: A synthetic graph with 300 nodes (agents) and an edge probability of 0.03.
  2. Facebook Snapshot Graph: A real-world social network graph with 4039 nodes (agents), representing a snapshot of Facebook connections.

These graphs represent the social network structure influencing agent cooperation. The tasks generated for experiments had thresholds sampled from a normal distribution and utilities set as a multiple of the threshold.

Key Insights and Ideas

  • Probabilistic Reasoning is Crucial: In uncertain environments, relying solely on expected resource contributions (a common baseline) is insufficient. Deriving probability bounds allows for more robust decision-making.
  • Overlapping Coalitions are Feasible and Beneficial: The proposed protocol and methods demonstrate that agents can effectively form and operate within overlapping coalition structures, leading to higher task completion rates.
  • Social Network Structure Matters: The distance between agents in the social network influences the likelihood of cooperation, with closer agents being more likely to be included in proposals.
  • Confidence Levels Trade-off with Success: Higher confidence levels (e.g., 0.9) lead to fewer completed tasks but also a higher chance of "confidence fails" (where the desired confidence level isn't met). This highlights a critical trade-off for agents.
  • Computational Efficiency: The proposed methods are designed to be computationally efficient, operating in polynomial time with respect to the number of agents and resource quantities, making them practical for real-world applications.

Key Results

The proposed methods (IPZY, CH2S, and HF) consistently outperformed a baseline method (EV) that selects coalitions based solely on expected resource value.

  • Task Completion: Across both the Erdős-Rényi and Facebook graphs, the novel methods achieved significantly more completed tasks than the baseline, especially at higher confidence levels. For instance, on the Erdős-Rényi graph with c=0.9, IPZY and CH2S completed over 2300 tasks compared to EV's 637.
  • Confidence Levels: The methods allowed agents to achieve their desired confidence levels (c) with a relatively low number of "confidence fails," particularly for c up to 0.8. For c=0.9, confidence fails increased significantly, indicating the challenge of guaranteeing high confidence in uncertain environments.
  • Group Size: The average size of the selected coalitions (bgs) was generally larger for the novel methods compared to the baseline, but the increase in task completion justified this.
  • Method Comparison: CH2S generally performed slightly better than IPZY, and both outperformed HF in terms of the number of completed tasks relative to the best group size. HF, however, was the fastest method.
  • Robustness: The methods showed robustness to increases in demanded confidence levels.

Limitations and Future Work

  • Independence Assumption: The current methods assume independence among agents' resource contributions. The authors acknowledge that this is a simplification and that dependent variables would require more complex belief modeling.
  • Resource Depletion: The current protocol assumes resources are replenished each round. Future work could explore scenarios where resources are depleted over time, necessitating long-term strategic planning.
  • Alternative Protocols: The paper suggests testing the methods with alternative coalition formation protocols.
  • Agent Behavior Modeling: The belief update mechanism allows for modeling agent behavior (e.g., observing who an agent accepts proposals from). Studying such phenomena is a direction for future research.
  • Complex Environments: Extending the methods to handle multiple resource types and more complex task structures is also a potential avenue for future work.

Summary updated

BibTeX
@inproceedings{mamakos2017probability,
  author = {Michail Mamakos and Georgios Chalkiadakis},
  title = {{Probability Bounds for Overlapping Coalition Formation}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/47},
}
Figure