Efficient Coalition Structure Generation via Approximately Equivalent Induced Subgraph Games.

Area of Science:

• Game Theory
• Computational Economics
• Operations Research

Background:

• Characteristic function games (CFGs) are fundamental in cooperative game theory but often suffer from computational intractability.
• Existing methods for coalition structure generation (CSG) in CFGs can be inefficient and lack theoretical guarantees.
• Induced subgraph games (ISGs) offer a more tractable representation for certain game structures.

Purpose of the Study:

• To develop a transformation method (AE-ISG) for converting any CFG into an approximately equivalent ISG.
• To propose a novel graph clustering-based CSG approach for ISGs that leverages optimization solvers.
• To provide theoretical guarantees for the quality of approximate CSG solutions derived from CFGs via ISGs.

Main Methods:

• Transformation of CFGs to ISGs using a norm approximation problem solution (AE-ISG).
• Development of a coalition structure generation (CSG) method for ISGs based on graph clustering.
• Utilizing off-the-shelf optimization solvers for the proposed CSG approach.

Main Results:

• The AE-ISG transformation successfully creates approximately equivalent ISGs from any CFG.
• The novel graph clustering-based CSG for ISGs demonstrates superior performance compared to existing methods.
• Theoretical guarantees are established for the quality of CSG solutions computed for CFGs through the ISG approximation.

Conclusions:

• The AE-ISG approach enhances the tractability of solving CFGs by enabling approximate CSG with quality guarantees.
• The proposed CSG method for ISGs is efficient and effective, outperforming domain-specific algorithms in real-world applications.
• This work provides a valuable framework for computing approximate CSG solutions for a broad class of games.