skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Faster Optimal Coalition Structure Generation via Offline Coalition Selection and Graph-Based Search
Coalition formation is a key capability in multi-agent systems. An important problem in coalition formation is coalition structure generation: partitioning agents into coalitions to optimize the social welfare. This is a challenging problem that has been the subject of active research for the past three decades. In this paper, we present a novel algorithm, SMART, for the problem based on a hybridization of three innovative techniques. Two of these techniques are based on dynamic programming, where we show a powerful connection between the coalitions selected for evaluation and the performance of the algorithms. These algorithms use offline phases to optimize the choice of coalitions to evaluate. The third one uses branch-and-bound and integer partition graph search to explore the solution space. Our techniques bring a new way of approaching the problem and a new level of precision to the field. In experiments over several common value distributions, we show that the hybridization of these techniques in SMART is faster than the fastest prior algorithms (ODP-IP, BOSS) in generating optimal solutions across all the value distributions.  more » « less
Award ID(s):
2312342
PAR ID:
10588992
Author(s) / Creator(s):
; ; ; ;
Publisher / Repository:
International Joint Conferences on Artificial Intelligence Organization
Date Published:
ISBN:
978-1-956792-04-1
Page Range / eLocation ID:
238 to 248
Format(s):
Medium: X
Location:
Jeju, South Korea
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; ; (, Proceedings of the AAAI Conference on Artificial Intelligence)
    Coalition structure generation (CSG), i.e. the problem of optimally partitioning a set of agents into coalitions to maximize social welfare, is a fundamental computational problem in multiagent systems. This problem is important for many applications where small run times are necessary, including transportation and disaster response. In this paper, we develop SALDAE, a multiagent path finding algorithm for CSG that operates on a graph of coalition structures. Our algorithm utilizes a variety of heuristics and strategies to perform the search and guide it. It is an anytime algorithm that can handle large problems with hundreds and thousands of agents. We show empirically on nine standard value distributions, including disaster response and electric vehicle allocation benchmarks, that our algorithm enables a rapid finding of high-quality solutions and compares favorably with other state-of-the-art methods. 
    more » « less
  2. ; ; ; ; (, AAMAS24)
    Coalition Structure Generation (CSG) involves dividing agents into coalitions in such a way as to coordinate them into solving problems together efficiently. In this paper, we revisit the CSG problem and propose a new search method that introduces an offline phase to speed up the search process, where the best coalition sets to search are preprocessed. These sets are calculated only once regardless of the coalition values and can be reused each time a CSG instance is to be solved. Then our search in the online phase combines dynamic programming with integer partition-based search in a novel way. 
    more » « less
  3. ; ; (, Proceedings of the AAAI Conference on Artificial Intelligence)
    Coalitions naturally exist in many real-world systems involving multiple decision makers such as ridesharing, security, and online ad auctions, but the coalition structure among the agents is often unknown. We propose and study an important yet previously overseen problem -- Coalition Structure Learning (CSL), where we aim to carefully design a series of games for the agents and infer the underlying coalition structure by observing their interactions in those games. We establish a lower bound on the sample complexity -- defined as the number of games needed to learn the structure -- of any algorithms for CSL and propose the Iterative Grouping (IG) algorithm for designing normal-form games to achieve the lower bound. We show that IG can be extended to other succinct games such as congestion games and graphical games. Moreover, we solve CSL in a more restrictive and practical setting: auctions. We show a variant of IG to solve CSL in the auction setting even if we cannot design the bidder valuations. Finally, we conduct experiments to evaluate IG in the auction setting and the results align with our theoretical analysis. 
    more » « less
  4. ; ; ; ; ; ; ; (, Philosophical Transactions of the Royal Society B: Biological Sciences)
    In social species, individuals may be able to overcome competitive constraints on cooperation by leveraging relationships with familiar, tolerant partners. While strong social ties have been linked to cooperation in several social mammals, it is unclear the extent to which weak social ties can support cooperation, particularly among non-kin. We tested the hypothesis that weakly affiliative social relationships support cooperative coalition formation using 10 years of behavioural data on wild female chimpanzees. Female chimpanzees typically disperse and reside with non-kin as adults. Their social relationships are differentiated but often relatively weak, with few dyads sharing strong bonds. Females occasionally form aggressive coalitions together. Three measures of relationship quality—party association, five-metre proximity and whether a dyad groomed—positively predicted coalitions, indicating that relationship quality influenced coalition partnerships. However, dyads that groomed frequently did not form more coalitions than dyads that groomed occasionally, and kin did not cooperate more than expected given their relationship quality. Thus, strong bonds and kinship did not bolster cooperation. We conclude that cooperative coalitions among female chimpanzees depend on social tolerance but do not require strong bonds. Our findings highlight social tolerance as a distinct pathway through which females can cultivate cooperative relationships. This article is part of the theme issue ‘Cooperation among women: evolutionary and cross-cultural perspectives’. 
    more » « less
  5. ; ; ; ; (, AAMAS24)
    Coalition structure generation (CSG) is a critical problem in multiagent systems, involving the optimal partitioning of agents into disjoint coalitions to maximize social welfare. This paper introduces SALDAE, a novel multiagent path finding algorithm for CSG on a coalition structure graph. SALDAE employs various heuristics and strategies for efficient search, making it an anytime algorithm suitable for handling large-scale problems 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email