On the Online Coalition Structure Generation Problem

Michele Flammini, Gianpiero Monaco, Luca Moscardelli, Mordechai Shalom, Shmuel ZaksJAIR 2021 · DOI

TL;DR

This paper tackles the challenge of forming optimal coalitions among agents arriving sequentially in an online setting. The authors analyze the problem of maximizing social welfare (sum of coalition values) under various constraints, establishing tight bounds on the performance of online algorithms and introducing new theoretical results for this complex problem.

What Problem Does This Paper Address?

The core problem is Coalition Structure Generation (CSG), which involves partitioning a set of agents into groups (coalitions) to maximize their collective value. Traditionally, CSG assumes all agents and their relationships are known upfront (offline setting). However, many real-world scenarios involve agents arriving over time, requiring decisions to be made without complete information. This paper addresses the online version of CSG, where agents appear one by one, and an online algorithm must decide whether to assign the new agent to an existing coalition or form a new one, with irrevocable decisions. The goal is to maximize the total value of all coalitions formed, a concept known as utilitarian social welfare. The paper considers two main ways to define coalition value: the sum of edge weights within a coalition (total weight) and the sum of edge weights divided by coalition size (fractional weight).

Methods

The authors employ competitive analysis to evaluate online algorithms. This involves comparing the performance of an online algorithm to an optimal offline algorithm that knows the entire sequence of agent arrivals in advance. They analyze two primary coalition value functions:

  • Maximum Weight Coalition Structure Generation (MAXW-CSG): Maximizing the sum of edge weights within coalitions.
  • Maximum Fractional Weight Coalition Structure Generation (MAXFW-CSG): Maximizing the sum of edge weights divided by coalition size.

They investigate various scenarios based on:

  • Coalition size bounds: Unbounded vs. bounded (up to size a).
  • Number of coalitions bounds: Unbounded vs. bounded (up to k).
  • Edge weights: General (positive and negative), positive, and unweighted.

Key algorithmic approaches include a greedy algorithm (GREEDY) for MAXW-CSG and an algorithm called MAXIMALMATCHING for MAXFW-CSG. They also establish lower bounds using adversarial strategies to demonstrate the inherent difficulty of the online problem.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis using graph structures and adversarial inputs rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Impossibility of perfect online solutions: The paper demonstrates that for general value functions, no online algorithm can achieve a bounded competitive ratio, highlighting the inherent challenge of online decision-making.
  • The power of greedy for MAXW-CSG: The greedy algorithm (GREEDY) is shown to be nearly optimal for MAXW-CSG under certain conditions, achieving tight or near-tight competitive ratios.
  • Fractional weight is trickier: MAXFW-CSG, even with positive weights, presents greater challenges, with algorithms like MAXIMALMATCHING providing competitive ratios that depend on the maximum edge weight (W) or the number of agents (n).
  • The impact of bounds: The presence of bounds on coalition size (a) and the number of coalitions (k) significantly influences the achievable competitive ratios, with tighter bounds generally leading to better performance guarantees.
  • Adversarial construction is key: The proofs for lower bounds heavily rely on constructing specific adversarial sequences of agent arrivals and edge weights to challenge online algorithms.

Key Results

The paper provides a comprehensive analysis of competitive ratios for various settings:

  • MAXW-CSG:
    • Unbounded coalition size: Lower bound of $\Omega(W(n-2))$ for strict competitive ratio. The GREEDY algorithm achieves a competitive ratio of $\Theta(\max\{W(n-2), n-1\})$.
  • Bounded coalition size (a): GREEDYa achieves a competitive ratio of $O(W(a-1))$ for general weights and $O(aW)$ for positive weights.
  • MAXFW-CSG:
    • Unbounded coalition size: A lower bound of $\Omega(W)$ for positive weights. MAXIMALMATCHING is a $4W$-approximation for general weights and $4$-competitive for unweighted graphs.
  • Unbounded coalition size, positive weights: A lower bound of $\Omega(\log^2 W)$ is established, and a matching upper bound is provided by the CLASSIFY algorithm.
  • Bounded number of coalitions (k): Impossibility results show no competitive algorithms exist for general weights and strict competitive ratios.

Limitations and Future Work

The authors acknowledge several limitations and suggest future research directions:

  • General non-strict competitive ratio: While tight bounds are provided for strict competitive ratios, further work could explore lower bounds for the more general non-strict competitive ratio.
  • More complex value functions: The current model uses simple edge-based values. Future work could explore value functions that incorporate costs, topological properties (like diameter or average distance), or centrality indices.
  • Dynamic environments: Extending the model to scenarios where agents can migrate between coalitions (with associated costs) or leave the graph would increase realism.
  • Randomized algorithms: Investigating whether randomized algorithms can achieve better performance than deterministic ones is a promising avenue.
  • Directed graphs: While the paper argues that directed graphs don't fundamentally change the problem for global utilities, exploring this explicitly could be beneficial.
  • Uncertainty: Incorporating uncertainty regarding edge weights or agent availability would lead to more robust models.

Summary updated

BibTeX
@article{flammini2021online,
  author = {Michele Flammini and Gianpiero Monaco and Luca Moscardelli and Mordechai Shalom and Shmuel Zaks},
  title = {{On the Online Coalition Structure Generation Problem}},
  journal = {J. Artif. Intell. Res.},
  year = {2021},
  doi = {10.1613/jair.1.12989},
}
Figure