Hierarchical Coalition Formation in Multi-agent Systems
Coalition formation has been addressed in multi-agent systems for a long time. Quite surprisingly, hierarchical structures, that often naturally occur in the real-world, have barely been investigated. I propose to consider organisational hierarchies of co
- PDF / 262,869 Bytes
- 5 Pages / 439.37 x 666.142 pts Page_size
- 57 Downloads / 226 Views
School of Technology, Pontifical Catholic University of Rio Grande do Sul, Porto Alegre, Brazil [email protected] 2 Department of Informatics, Clausthal University of Technology, Clausthal-Zellerfeld, Germany
Abstract. Coalition formation has been addressed in multi-agent systems for a long time. Quite surprisingly, hierarchical structures, that often naturally occur in the real-world, have barely been investigated. I propose to consider organisational hierarchies of coalition structures. Both the complexity as well as suitable algorithms have to be investigated for this more general setting. Keywords: Hierarchical coalition formation
1
· Multi-agent systems
Introduction
Hierarchies naturally occur or are used in companies, agencies, or organisations in the real-world. For instance in rescue or disaster response operations, or in military operations, we have a high-stake environment, in which deliberation to reach a consensus is impractical, and therefore hierarchical command structures are defined [5]. Besides hierarchies, I also introduce constraints and allow overlapping coalitions: This helps to combine a horizontal dimension (e.g., interaction graph) with a vertical dimension (e.g., a hierarchy) to represent a robust organisational structure.
2
Related Work
A simple approach to address constraints in the coalition formation process is by considering interaction graphs [1,8], where agents are represented by vertices. The edges between them establish a relation (e.g., trust, synergy, etc). Another well-defined framework for representing constraints is Constrained Coalition Formation (CCF) [6]. The basic form of CCF defines the permitted sizes for coalitions as well as the agents that should be together (i.e., positive constraints) and the ones who must not be together in the same coalition (i.e., negative constraints). c The Editor(s) (if applicable) and The Author(s), under exclusive license to Springer Nature Switzerland AG 2021 S. Rodr´ıguez Gonz´ alez et al. (Eds.): DCAI 2020, AISC 1242, pp. 210–214, 2021. https://doi.org/10.1007/978-3-030-53829-3_23
Hierarchical Coalition Formation in Multi-agent Systems
211
The negative constraints from CCF are introduced in a valuation structure [4] in the form of pivotal agents, which are then evaluated by a valuation function in a particular way. Pivotal agents are said to be incompatible and should stay in different coalitions. Apart from those features, none of the previous approaches that take constraints into account deal with overlaps between coalitions [3].
3
Hierarchical Coalition Formation
I introduce a new Game where I look for a hierarchy of coalition structures as a solution. This hierarchical setting is important for many scenarios in which a coalition structure is strongly related with different levels of a hierarchy. As an example, suppose a school is organising an excursion to an environmental park. Two buses were rented for taking kids from the school to the park and arrive at different sides of the park. At the park, four trucks,
Data Loading...
