ABMSCORE: a heuristic algorithm for forming strategic coalitions in agent-based simulation

ABSTRACT

Integrating human behavior into agent-based models has been challenging due to its diversity. An example is strategic coalition formation, which occurs when an individual decides to collaborate with others because it strategically benefits them, thereby increasing the expected utility of the situation. An algorithm called ABMSCORE was developed to help model strategic coalition formation in agent-based models. The ABMSCORE algorithm employs hedonic games from cooperative game theory and has been applied to various situations, including refugee egress and smallholder farming cooperatives. This paper discusses ABMSCORE, including its mechanism, requirements, limitations, and application. To demonstrate the potential of ABMSCORE, a new application example is given, which is based on a complex version of the Thomas Schelling’s segregation model. The intent of the paper is to provide the potential user with enough information so that they can apply ABMSCORE to their simulation products.

KEYWORDS:

• Agent-based simulation
• coalition formation
• strategic cooperation
• cooperative game theory

1. Introduction

The integration of models of human behaviour within agent-based modelling and simulation (ABMS) is an important advancement for simulation (Cheng et al., 2016), especially when modelling human decision-making (An et al., 2020). Modelling human behaviour is not a one-size-fits-all endeavour. There have been several attempts to include aspects of it within ABMS (or simulation as a whole), for example, Bratman’s theory of intention (Bratman, 1987) in Belief-Desire-Intent (BDI) models (Rao & Georgeff, 1995) or the Rescorla-Wagner’s model of learning (Rescorla & Wagner, 1972) in Agent_Zero (Epstein, 2014). A more recent attempt considered strategic coalition (or group) formation using the ABMSCORE algorithm (Collins & Frydenlund, 2018; Vernon-Bido & Collins, 2021).

The purpose of this paper is to bring together the work on the ABMSCORE algorithm to provide a clear and detailed description of the generic version of it. This description is achieved using the latest version of Overview, Design concepts and Details (ODD) protocol (Grimm et al., 2020); a standard approach for describing agent-based models. The intent of this description is to provide potential users with an easy-to-use guide for using the ABMSCORE algorithm. To this end, several applications of the ABMSCORE are discussed, as well as the application requirements. These applications include a new application specially designed to demonstrate the usage of the ABMSCORE algorithm, which is based on Schelling’s famous segregation model (Schelling, 1971).

The ABMSCORE algorithm attempts to model strategic coalition formation by emulating a solution mechanism from cooperative game theory, specifically, the core partition from hedonic games. A coalition is a subset of agents that come together for some purpose, it is assumed, in this work, that agents can only be a member of one coalition at any given time, which is a standard assumption in the field of cooperative game theory (Thomas, 2003). Hedonic games are a form of non-transferable utility cooperative games where each agent has a preference relation over the coalitions (Banerjee et al., 2001; Bogomolnaia & Jackson, 2002); a core partition is a collect of stable disjoint covering coalitions of agents; by stable, it is meant no subset of agents has an incentive to form a new coalition, based on their preferences in the hedonic game (Banerjee et al., 2001).

The algorithm works by dynamically allowing the agents to suggest new coalitions to fellow agents, with the affected agents determining if they would form that coalition. Some example suggestions include merging two existing coalitions, forming sub-coalitions of an existing coalition, or other splitting of the coalitions. The intent of the ABMSCORE algorithm is to emulate human coalition formation as outlined by Grigoryan et al. (2022) and eventually find the core partition (Vernon-Bido & Collins, 2021).

Cooperation is fundamental to the success of the human race. This point was highlighted by the Nobel prize winning economist Milton Friedman, who once observed that no one individual would make a modern pencil from scratch; this tasks requires thousands of autonomous individuals or groups (Friedman & Friedman, 1980). They followed this observation with the following quote:

It is even more astounding that the pencil was ever produced. No one sitting in a central office gave orders to these thousands of people. No military police enforced the orders that were not given. These people live in many lands, speak different languages, practice different religions, may even hate one another - yet none of these differences prevented them from cooperating to produce a pencil.

Without centralised control, who cooperates with whom? What coalitions form between these autonomous agents? It is these types of questions that the ABMSCORE algorithm was designed to explore and provide insights.

This paper first discusses the lead-up and demand for developing the ABMSCORE algorithm. This is followed by a detailed description of the algorithm. Prior work that explored ABMSCORE, include the El Farol bar problem (Collins, 2019), the refugee movement (Collins & Frydenlund, 2016), small-hold farming cooperatives (Collins & Krejci, 2020), and our new colour segregation model described in this paper. The paper then discusses the modelling scenario requirements for using the ABMSCORE algorithm. Finally, the paper finishes with a discussion on future development and conclusions.

2. Background

This section provides a brief introduction to agent-based modelling and simulation (ABMS). This is followed by a discussion on modelling strategic group formation, which is traditionally modelled by game theory. A discussion on the hybrid combination of ABMS and game theory is provided before the ABMSCORE background and history are introduced.

2.1. Agent-based modeling and simulation (ABMS)

ABMS is a simulation modelling paradigm that focuses on modelling autonomous, heterogeneous agents and their interactions. The power of ABMS comes from emergent macro-level phenomena (or system-level) being observed from the micro-level interactions of the agents (Miller & Page, 2007). This simulation paradigm allows the modeller to create simulations that help explain and discover system-level behaviour (Epstein, 2008; Macal, 2016), which might not be apparent from empirically observing the system. ABMS can provide insight into systems that might not exist, or it can provide an understanding of the effects of potential interventions in a system, i.e., governmental policy changes (Wilensky & Rand, 2015).

Unlike other modelling methods, it does not aggregate or assume homogeneity amongst the population under consideration. Aggregation can result in erroneous conclusions about the systems’ behaviour, for example, Miller and Page (2007) discuss this issue through examples of modelling standing ovations at a theatre performance and bees defending their hive. Thus, the strength of ABMS comes from autonomous, heterogeneous agents without a centralised controller (Wilensky & Rand, 2015) because a phenomenon can emerge that was not hard-coded into the simulation model. As such, ABMS has been used to model various large systems because it is difficult to collect empirical observations about them due to scale, ethical, or temporal constraints. For example, ABMS has been used to model historical events (Hill et al., 2004), economic systems (Axtell, 2005; Farmer & Foley, 2009; Tesfatsion, 2002), organisation structures (Tsvetovat & Carley, 2004), social systems (Schelling, 1971), evacuations (Helbing et al., 2000), or biological systems (Reynolds, 1987). More recently, ABMS has been used to model team performance (Lapp et al., 2019), the spread of the COVID-19 pandemic (Kerr et al., 2021), and many more. Critically, traditional agent-based modelling has not incorporated strategic group formation behaviour (Vernon-Bido & Collins, 2021).

2.2. Modeling strategic coalition formation

However, the autonomous individualism of agent-based modelling has its limitations. As already alluded to, humans cooperate and collude to achieve mutually beneficial goals, be it a sports team or hunter-gatherer tribes. We would argue that humans have been so successful as a species because of their ability to cooperate and form groups; as such, there is merit in trying to model humans acting in a group. However, it becomes difficult to model groups of agents acting together while still maintaining their autonomy. That is, how do you model groups of rational actors moving towards a common goal but still have each individual retain control over their own actions and destiny? What if the group is no longer of benefit to the individual agent? Can it leave? Can it join a different group? These strategic questions and more led us to develop the ABMSCORE algorithm.

Previously, various applications of ABMSCORE were explored (Collins et al., 2017; Collins, Jayanetti, et al., 2023; Elzie et al., 2014; Roberts & Collins, 2018). The primary emphasis of this paper lies in delving into the intricacies of the ABMSCORE algorithm itself, accompanied by the exploration of a novel application. Before we introduce the ABMSCORE algorithm, it is necessary to introduce the cooperative game theory on which it is based.

The main method used to model strategic group formation, or as it is more commonly known, strategic coalition formation, is cooperative game theory. Game theory is the mathematical modelling of situations of more than one decision-maker, and it is a critical modelling approach in economics (Eatwell et al., 1987). Normal-form game theory is the dominant method of applying game theory, which involves solution mechanisms like the Nash Equilibrium (Fudenberg & Tirole, 1991; Nash, 1951). However, the normal-form game theory and the Nash Equilibrium become unwieldy in situations that involve more than two players (agents); as such, cooperative game theory was proposed as an alternative modelling approach. Technically, cooperative game theory was introduced by von Neumann and Morgenstern (1944) in their canonical book “Theory of Games and Economic Behavior”, however, Lloyd Shapley (1953) was the individual who demonstrated it as a serious technique.

Nash Equilibrium quickly becomes computational complex for games as the number of players increases. As such, alternative solution mechanisms need to consider, for example, the Shapley value (Shapley, 1953) and the Core (Gillies, 1959). The Shapley value assumes superadditivity, which means the grand coalition (the coalition that includes all players) will form; however, we were interested in a variety of different coalition structures (covering sets of disjoint coalitions over the players), so it is the core that is the inspiration for the ABMSCORE algorithm.

In its essence, the core of a cooperative game represents the coalition structure of the players, where no subgroup of players has an incentive to form a new coalition. Like the Nash Equilibrium, there can be more than one solution that fits the core’s criteria, or even none. Strictly speaking, this work considers the core partition (Banerjee et al., 2001); the core partition is the core equivalent for hedonic games (Iehlé, 2007).

Cooperative game theory is, technically, a two-part problem: (1) which coalitions will form among the decision-makers (agents/players) and (2) how the payoffs will be distributed amongst the coalition members (Chakravarty et al., 2015). To simplify finding the solution, we remove the second problem by only considering non-transferable utility (NTU) games, specifically hedonic games (Banerjee et al., 2001; Bogomolnaia & Jackson, 2002; Collins et al., 2019). Unsurprisingly, due to them reducing the complexity of the problem considered, hedonic games have grown in popularity over the last 20 years (Chalkiadakis et al., 2011; Collins et al., 2022). However, even with a reduction in the complexity of games, there is difficulty in solving hedonic games. Ballester (2004) showed that finding the solution to a hedonic game is NP-complete. Since proving p = NP is beyond the authors’ capability, we are driven to develop a heuristic approach to finding appropriate solutions; the effectiveness of our approach to do this is discussed in Section 6.2.3. Our focus was on integrating this heuristic within an ABMS so that strategic coalition formation could be included in that modelling paradigm. Others have combined ABMS and game theory in previous applications, which we will discuss in the next section. A detailed review about the application of cooperative game theory can be found in Grigoryan and Collins (2021), and for agent-based modelling the work by Gilbert (2019).

2.3. Game theory and ABMS

Our approach to using the ABMSCORE algorithm is not the first application of game theory within an ABMS context. For example, Hill et al. (2004) connects game theory and agent-based modelling by combining a search game (another game theory type) and ABMS to simulate the search for U-boats in the Second World War. Szilagyi (2012) attempts to solve simplified versions of famous agent-based models using game theory approaches.

Specifically focusing on cooperative game theory, there have been several attempts to connect it with ABMS. Bonnevay et al. (2005) used agent-based modelling to simulate a cooperative game, whereas our ABMSCORE approach incorporates cooperative game theory concepts into ABMS. More related to our approach, Janovsky and DeLoach (2016) created a heuristic for finding the core in a multi-agent environment; this has similarities to the ABMSCORE approach but is focused purely on algorithm development as opposed to its application. Finally, Taywade et al. (2018) created decentralised heuristics for solving a particular type of hedonic game (i.e., additively separable games); the ABMSCORE approach can be applied to all hedonic games.

As previously mentioned, both game theory and ABMS have weaknesses as modelling paradigms, i.e., cooperative game theory is computationally intensive, and agent-based models cannot model strategic group formation. A hybrid simulation is a modern approach to trying to overcome a modelling paradigm’s weaknesses by incorporating another modelling approach into the model (Brailsford et al., 2019). The ABMSCORE approach described in this paper is an attempt to do just that; enriching agent-based modelling by incorporating cooperative game theory elements within it to model strategic group formation.

The obvious initial question is, why create a hybrid model? ABMS is used to model lots of humans, and when humans come together, they form mutually beneficial groups (Graeber & Wengrow, 2021); however, traditional ABMS does not take into account this grouping effect; as such, if we are going to better improve the modelling of human behaviour in ABMS (Cheng et al., 2016), then there is a need to incorporate strategic group formation (Collins & Frydenlund, 2018). Hence, there is a need for the ABMSCORE algorithm.

2.4. ABMSCORE algorithm

In this section, we present the history of ABMSCORE usage over time. Also, the scenarios that employed ABMSCORE are briefly presented to provide examples of the t algorithm’s application. More details about the example scenarios can be found in the application section of this paper; the intent of this section is to provide a timeline and a brief introduction to the applications.

In 2015, the first version of theABMSCORE algorithm was demonstrated in a presentation at the 2015 Swarmfest conference at the University of South Florida, Colombia (Collins, Frydenlund, et al., 2015). The intention of this presentation was to introduce the concept of strategic group formation in the context of ABMS. Swarmfest participants were mainly academics that used ABMS in their research; hence, a sensible audience for this presentation.

ABMSCORE algorithm’s first application studied agents interacting in a Von Neumann neighbourhood (Collins and Frydenlund, 2016b). The goal of this application was to explore the coalition formation behaviour between agents that are homogeneous (keeping agents’ strengths constant) or heterogeneous (varying agents’ strengths). The results focused on the size of the emergent coalition sizes, with a dominant coalition of approximately 60% of agents emerging. Collins and Frydenlund (2018) have further extended this scenario to describe the possible group formation configurations, and new ways to represent the simulation runs due to the complexity of the output.

In 2016, another scenario related to refugee flight employed the ABMSCORE algorithm (Collins & Frydenlund, 2016). Collins and Frydenlund (2016b) analysed the coalition formation of the refugees, varying their speed levels and estimating the variation effect on agents’ coalition formation decisions. The simulation results indicated that the refugees ended up in a grand coalition when the pace to reach the destination was not their primary focus, but “safety in numbers” was the focus. As the importance of pace increased, sub-coalitions formed because the agents could move relatively fast while enjoying the benefits of being part of a coalition. Finally, if the pace was the most important factor, the agents all end up in their singleton coalitions, representing sheer panic.

In 2018, a classic ABMS problem, the EL Farol bar problem has incorporated the ABMSCORE (Collins, 2017). The EL Farol Bar problem focuses on the rates of overcrowding when patrons are trying to avoid an overcrowded bar. The main objective of deploying the ABMSCORE algorithm to this problem was to study how coalition formation affects the overcrowding of the bar. The results showed that allowing agent coalitions results in an undesirable scenario for everyone.

Collins and Krejci (2018) used the AMSCORE algorithm to explore small-hold farming cooperatives in regional food systems. The authors analysed the trade-off of farmers joining transportation cooperatives at the cost of their autonomy of decision (a trait that farmers have been shown to highly value). This problem prevails especially for small-scaled and mid-sized farmers who struggle with logistic activities to transport goods from rural areas to distant urban sites. The results of the analysis demonstrated that the farmer agents form singleton coalitions when either their preference for autonomy is too high, or they consider the impact of distance between farms is too significant.

In 2021 Collins and Etemadidavan (2021) adopted ABMSCORE to study human behaviour by incorporating human subject experiments. Understanding human behaviour has always been an essential but challenging question to investigate due to humans’ constantly evolving behaviour. This work (Collins & Etemadidavan, 2021) uses the glove game, a classic game, to create an interactive simulation to conduct a coalition formation experiment. The work tested if having game theory experience affects humans’ decisions when forming coalitions in an interactive simulated environment. The results showed no association between experiment participants’ game theory experience and their coalition formation decisions. More importantly, it showed that the human subjects did not always form the coalition structures predicted by cooperative game theory.

2.4.1. Advanced version of the ABMSCORE algorithm

The ABMSCORE algorithm is split into three parts: coalition suggestion, coalition evaluation, and coalition updating. Suggestions to the agents are made each round of the algorithm; the form of these suggestions is a new coalition. The agents, that would be members of this new coalition, all evaluate the new coalition and if they all decide it is beneficial for them to move to it. If all affected agents would benefit, then it is signalled that this new coalition is acceptable and should form. If the new coalition is formed, its members are removed from their existing coalitions; this means that several new coalitions will be created: the suggested one plus the coalitions formed from the remaining agents after the removal of agents from their old coalition to create the suggested coalition. For example, consider the case of four agents that are currently in the grand coalition (1234), if coalition (12) was suggested and accepted by agents 1 and 2, then it would form; this would mean that the coalition structure of the agents would be the two coalitions: (12)(34).

In the original ABMSCORE algorithm, presented in Collins and Frydenlund (2018), the suggested coalitions were randomly generated subsets of the agent pool. Vernon-Bido and Collins (2021) advanced this approach by incorporating various coalition suggestion types, including joint coalitions, exit coalitions, pair coalitions, defect coalitions, split coalitions, and singleton coalitions. They showed that these new coalition suggestions helped speed up the process of finding a stable solution. The original (Von Neumann Neighborhood), refugee, and El Farol models were all created using the original algorithm. The farming and glove game models used the advance version; so is the colour segregation model presented in this paper. The next section provides a detailed overview of the ABMSCORE approach.

3. Model

It has been advocated that there is a need for standardisation in the way agent-based models are presented (Angus & Hassani-Mahmooei, 2015; Collins, Petty, et al., 2015). One defacto standard is the Overview, Design concepts, Details (ODD) protocol, presented by Grimm et al. (2006). They suggested the ODD protocol to describe agent-based model attributes from various descriptive angles to help facilitate model replication. The protocol was further advanced by Grimm et al. (2020), and it is this newer version that we describe the structure, dynamics, and workflow of the ABMSCORE algorithm. ODD consists of seven elements and we will be described in turn. Each element serves a different purpose in describing the algorithm to have a more holistic description.

3.1. Purpose and patterns

ABMSCORE algorithm aims to model strategic coalition formation and the situations or conditions associated with the coalition formation within a particular ABMS modelled scenario. We call the resultant simulation “the parent simulation”, with which the ABMSCORE algorithm is part. The algorithm, as indicated previously, employs cooperative game theory concepts, which can be used to determine the effect of coalition formation on the problem of interest. For example, Collins and Frydenlund (2016) used the ABMSCORE to study coalition formation in the refugee flight problem. Different coalition formation preferences are possible, such as being in a singleton coalition, subcoalitions, or a grand coalition.

Patterns: Patterns explored are the agents’ actions to remain or leave the coalition given some utility functions. The utility of joining or leaving the coalition is associated with benefits gained from a coalition.

3.2. Entities, state variables, and scales

The algorithm uses a cooperative game theory solution concept called core, which is the set of all possible payoff allocations that cannot be improved upon by any other coalition. The core is well-defined but can be empty, and it is not always unique. Core not being unique means that there may be multiple coalition structures satisfying the core requirements. Strictly speaking, core partitions are considered in the algorithm, which is the hedonic game equivalent to the core (Iehlé, 2007) and focuses on coalition structures.

Agents: Members, also called players, are the simulated agents.

Environment: Abstract location where agents can communicate and interact.

State variables: Each modelled scenario will have specific variables that describe different factors, traits, or conditions in varying amounts or forms. Specifically, to the ABMSCORE algorithm is the current coalition structure; that is, the covering collection of coalitions of the agents.

3.2.1. Scales

The model scales are arbitrary and depend on the modelled scenario. Several updates, such as coalition formation, can coincide at every iteration.

3.3. Process overview and scheduling

The specific modelled scenario will have its own processes. It is assumed that the simulation will run over several iterations. Specifically related to ABMSCORE is coalition formation. Each iteration is an opportunity for the agents to improve their utilities by joining new coalitions. New coalitions form if all the proposed coalition members would obtain a higher payoff. The algorithm structure for selecting, evaluating, and updating coalitions is as follows:

At each iteration, several new coalitions are selected and suggested to the agents. The form of these coalitions is determined by their suggestion type, which is discussed in more detail in the Submodel section below. Each agent that would be in the new suggested coalition determines if they would improve their payoff (utility) by being part of this new coalition; if all agent would improve their payoff, then the new coalition forms. This means that all the agents, in the new coalition, leave their old coalitions, resulting in new coalitions (and new payoffs) for their old coalition partners. This process is repeated, each iteration, until a stable coalition structure is found.

3.4. Design concepts

3.4.1. Basic principles

The ABMSCORE algorithm assumes the simulation’s agents can play a hedonic game, which is a type of game from cooperative game theory. Hedonic games are games where the agents (players) are self-interested, trying to maximise their utilities, which are deterministically determined by their current coalition, and the utility is not transferrable (Bogomolnaia & Jackson, 2002); most importantly, the players in hedonic games have a (strict) preference relation over the coalitions. This means that given any two possible coalitions for a given player, that player has a preference to be in one of the coalitions over the other. Classic examples of hedonic games are matching games (Gale & Shapley, 1962), which include the modelling of finding a spouse (marriage problem), a roommate, or college admissions (Aziz, 2013). Their preferences are the primary driver for the agent’s decision-making, which can be represented as a utility value by simply inverse-ranking the coalitions available and assigning its rank as utility (for strict preferences only). Also, agents are assumed to have complete information with regard to their evaluation of a suggested coalition. The utility that the agent gets is called a payoff.

3.4.2. Emergence

Expected emergence is related to the final coalition structure achieved due to simulation-specified conditions and variable perturbations. A coalition structure is the collection of disjoint coalitions, and the algorithm focuses on finding stable coalition structures, which are called core partitions. A core partition refers to disjoint coalitions where no subset of agents has the incentive to form a new coalition (Banerjee et al., 2001; Bogomolnaia & Jackson, 2002). The core partition is an appropriate solution mechanism for ABMS because it focuses on the coalition membership of each agent, whereas the core focuses on coalition values and imputations. A core partition is not necessarily unique and might not exist for a given game scenario. The scenarios that have applied the ABMSCORE algorithm only consider the games where the core exists.

3.4.3. Adaptation

The agents adapt due to their ability to form a new coalition because of coalition splitting or merging. The algorithm specifies the conditions when the agents can change their coalitions. A new coalition forms if existing or potential members accept the new member’s suggestion to join the coalition. This implies that agents have veto power to refuse or approve a new coalition being formed. However, the agents cannot influence or stop other agents’ decisions to leave the coalition. The agents’ main objective when making decisions is to improve their utilities.

3.4.4. Objectives

The objective for all agents is to join a coalition that maximises their utility, which is measured as their payoff.

3.4.5. Learning

Learning is not integrated into this model setting.

3.4.6. Prediction

Prediction is not integrated into this model setting.

3.4.7. Sensing

Agent sensing is not integrated into this model setting.

3.4.8. Interaction

In the ABMSCORE algorithm, the agents do not directly interact. However, their decisions influence other agents’ actions. Agents’ decisions are about joining or leaving the coalition, directly affecting the coalition value and other agents’ utilities. In the parent simulation, the agents might interact with each other due to another non-ABMSCORE process in that simulation.

3.4.9. Stochasticity

The algorithm randomly creates coalition suggestions for agent evaluation. The probability of a particular coalition being suggested depends on the method for generating the suggested coalition. Uniform distribution is applied when selecting a suggested coalition.

3.4.10. Collectives

Cooperative game theory is used to study coalition formation, which is a form of collective. The agents are part of this collective, i.e., the coalitions. The algorithm assigns numbers to the coalitions. The coalition that contains all the agents is called a grand coalition, while the coalition that includes a single agent is called a singleton coalition.

3.4.11. Observation

The final coalition structure is observed after specified time steps. The coalition structure is the main output of the ABMSCORE algorithm.

3.5. Initialization

Initially, all agents are assumed to start in a grand coalition. Each agent’s evaluation of a given coalition does not change throughout the game, i.e., the utility an agent assigns a coalition is constant.

3.6. Input data

The utility function, associated with a given agent’s evaluation of a given coalition, is either specified by an inputted look-up table or a pre-determined function. A random number generator is required for coalition suggestions. The parent simulation might use input data beyond that used by the ABMSCORE algorithm.

3.7. Submodels

There are three submodels used within the ABMSCORE algorithm: coalition suggestion selection, coalition evaluation, and coalition updating. The submodels manage the formation of the coalition structure.

3.7.1. Coalition suggestion selection

Different coalitions are suggested at each time step. There are six suggestion type mechanisms: join coalitions, exit coalition, pair coalition, defect coalition, split coalition, and individual coalition.

Join coalition: Two different coalitions (S, T) are randomly chosen from the current coalition structure (CS). Then the algorithm computes the payoffs of the joined coalition. A new coalition (represented by a C or D below) will form if the utilities are improved for all the coalition members. This suggestion will be disregarded if the grand coalition (N) that contains all the agents has already formed.

$\mathit{If}\mathit{\hspace{0.17em}}\mathit{N}\notin \mathit{CS}:\mathit{C}=\mathit{S}\mathit{\hspace{0.17em}}\cup \mathit{T}\mathit{\hspace{0.17em}}\mathit{s}.\mathit{t}.\mathit{\hspace{0.17em}}\mathit{S}\ne \mathit{T},\mathit{\hspace{0.17em}}\left\{\mathit{S},\mathit{T}\right\}\mathit{\hspace{0.17em}}\subseteq \mathit{CS}$

Exit coalition: The suggested coalition is an existing member of the CS with one of its members randomly removed, namely agent s. An agent will be permanently removed from a coalition if the remaining coalition members are better off without that agent. The removed agent will form a singleton coalition. This suggestion type is only permitted if there exist a coalition, in the current coalition structure that has more than one agent.

$\mathit{if}\mathit{\hspace{0.17em}}\mathrm{\exists S}\in \mathit{CS}\mathit{\hspace{0.17em}}\mathit{s}.\mathit{t}.\mathit{\hspace{0.17em}}\left|\mathit{S}\right|>1:\mathit{\hspace{0.17em}}\mathit{C}=\mathit{S}\mathrm{\setminus }\left\{\mathit{s}\right\},\mathit{\hspace{0.17em}}\mathit{s}\in \mathit{S}$

Create a pair coalition: A suggestion pair coalition is formed between two randomly selected agents, a and b. The pair will form if there is an improvement in payoff for both agents.

$\mathit{C}=\left\{\mathit{a}\right\}\cup \left\{\mathit{b}\right\},\mathit{a}\ne \mathit{b},\left\{\mathit{a},\mathit{b}\right\}\subseteq \mathit{N}$

Defect coalition: A suggested coalition is formed by including another randomly selected agent d into an existing coalition S that it is not already a member. Since the existing coalition could be the empty set, it does not matter if the grand coalition has already formed; in this case, this suggested coalition will be a singleton coalition.

$\mathit{C}=\mathit{\hspace{0.17em}}\left\{\mathit{d}\right\}\cup \mathit{S},\mathit{\hspace{0.17em}}\mathit{d}\mathit{\hspace{0.17em}}\in \mathit{N}\mathrm{\setminus S},\mathit{\hspace{0.17em}}\mathit{S}\in \mathit{CS}\cup \mathrm{\varnothing }$

Split coalition: A coalition S will split if two randomly selected disjoint coalitions C and D. Note in this case, two coalitions will be separately evaluated, if either is preferred by its member, then the split will occur.

$\mathrm{C}\cap \mathrm{D}=\mathrm{\varnothing },\mathit{\hspace{0.17em}}\mathit{C}\cup \mathrm{D}=\mathit{S},\mathit{\hspace{0.17em}}\mathit{S}\in \mathit{CS}$

Individual coalition: An individual coalition, i.e., the singleton coalition, forms if a randomly selected agent a is better off herself than joining any other coalition.

$\mathit{C}=\left\{\mathit{a}\right\},\mathit{\hspace{0.17em}}\mathit{a}\in \mathit{N}$

Coalition Evaluation: Coalition evaluation is performed by determining if the payoff change is acceptable to the coalition members. Their current payoff is compared to the new payoff, and if the new payoff exceeds the current one, then the agents will form a new coalition leaving their current coalition (C_i).

$\mathit{if}\mathrm{\forall i}\in \mathit{C},u_i\left(\mathit{C}\right)>u_i\left(C_i\right)\mathit{then}{C}_i:=\mathit{C},\mathrm{\forall i}\in \mathit{S}$

Coalition Updating: The coalition membership number is updated to a unique identification number when new coalitions are formed. With new coalitions being formed, the information about payoffs will be updated as well.

4. Applications

The section below discusses applications and situations that have employed the ABMSCORE algorithm. Most of these situations have a major characteristic in common: involving multiple interacting agents who might benefit from forming a coalition.

4.1. Von Neumann neighborhood

ABMSCORE algorithm was first adopted by Collins and Frydenlund (2016b) to study agents interacting in a Von Neumann neighbourhood, which is the set of all cells that are orthogonally adjacent to the region of interest. This scenario focused on splitting common resources with adjacent neighbours. Agents are described with varying levels of strength that introduce model heterogeneity. The agent with the highest strength gets the resource. In case there is a tie between the agents, the resource is shared evenly. For simplicity in the homogeneous case, the authors assigned the value of the resource to be 1, and when the agents stay in their singleton coalition, then each agent gets two resources, 0.5 for each of its neighbours. Agents can form coalitions with other neighbouring agents. Adjacent coalition members equally divide resources. Agents also have an incentive to form a coalition as they benefit from additional strength when splitting resources with neighbours outside the coalition; that is, coalition members exert group pressure on an outsider to obtain more resources through extortion.

Since coalitions can obtain more resources through this extortion, there is almost no incentive to form the grand coalition as that will mean there are no non-coalition members to extort. There is also little incentive for agents to remain in a singleton coalition due to the strength they can gain by being part of a coalition and avoiding resource loss from the coalition around them. As such, in this scenario, there is an incentive to form coalitions that are proper subsets of agents.

Varying levels of agents’ strengths have been introduced to determine the effect on the results found from the homogeneous analysis. The results show that the coalitions will still form; however, in the heterogeneous case, the stronger agents may dominate the weaker agents.

Figure 2 shows a screenshot from two versions of the game. Each static agent is represented by a single circle, with the colour representing which coalition it is a member. The first version of the game shows all agents with equal strength (homogeneous), whereas the second shows agents of unequal strength (heterogeneous). The agents interact with their neighbours, as described above, and a torus space is assumed (i.e., the sides wrap). As Figure 2(a), the agents are split into two groups, which was common in the homogeneous case. This occurred, instead of the grand coalition, because of the malicious nature of the agents as there was an incentive for the groups to kick out an agent they surrounded so that they could take all of the surrounded agent’s resources with extortion (colloquially, the agents inhabit a dog-eat-dog world). In the heterogenous case, this extortion can be seen on a lone turquoise (weak) agent in the centre of Figure 1(b).

Figure 1. Flow diagram of the ABMSCORE process within the context of the parent simulation; a suggestion coalition is generated of a particular type, it is evaluated by each affected agent, and, if acceptable, then this new coalition forms.

Figure 2. Screenshot example of the Von Neumann neighborhood problem with (a) homogeneous and (b) heterogenous agents; the static agent are represented as circles and their colors represents the coalition they are a member. Strength is represented by size. The color choice is arbitrary.

The authors have employed analytical and empirical analysis approaches to study the scenario. The analytical approach revealed general patterns in strategic coalition formation. However, the analysis was limited to a small number of agents only. The empirical approach developed a Monte Carlo simulation and collected data to study the dynamic version of the scenario. How the coalitions formed over time was of interest, especially any emergent processes about coalition development. The simulation modelled coalition formation (suggestion, evaluation, updating) using a simplified version of the ABMSCORE algorithm described in this paper, with only random coalitions being considered.

Collins and Frydenlund (2018) have further investigated the results of this scenario to reveal more information about coalition formation behaviour. The authors run several scenarios of homogeneous agents ranging from 4 to 36 agents to estimate the number of coalitions formed and the size of the largest coalitions. The analysis showed that as the size of the game increased, the number of possible final coalition configurations increased. For example, two coalition configurations were observed with four agents, while with 16 agents, three. An interesting result was observed that the larger group has approximately 50–60% of agents. Finally, transition matrices were used to show the transitions from one coalition to another, and an increase in coalition size was generally observed.

The analysis and results are interesting to understand the coalition formation dynamics better. The author suggested that organisational coalition formation or coalitions between different sectors of society can be explored using a similar scenario.

4.2. Refugee egress simulation

Another adaptation of the ABMSCORE algorithm was by Collins and Frydenlund (2016) to study the refugee flight problem. This problem is crucial for the safety of the persecuted and for understanding where to deploy reception sites. Refugees travel long distances to reach safety, and these travels result in different refugee flight outcomes; most of the research work studies how to anticipate, assist, or prevent these refugee flight outcomes (Apodaca, 1998; Jensen et al., 2019; Kunz, 1973). The simulation tried to understand the different outcomes.

The basic version of the ABMSCORE algorithm was applied to explore the arrivals of refugees to reception sites. Their paper concentrates on two main aspects. The first aspect examines long-distance migration, and the second one refers to the en-route coalition formation based on individuals’ utility functions. In the model, at each time step, the individual agent looks for a sub-coalition within its coalition that makes it better off. The utility to join or leave a coalition is associated with protection gained from a coalition versus the speed of reaching the destination. Note that the agents were heterogeneous with regard to their speed.

It is possible agents move as a whole coalition, which means no coalition member is left behind because of their slow speed. However, it may take longer to reach the destination with the entire coalition, as the coalition accommodates the speed of its slowest member. When the agents want to reach the destination faster, they usually act in a singleton coalition. Agents can form small coalitions, allowing some agents to move more quickly while maintaining some of the benefits of being part of the coalition. The figure below shows a screenshot from the model (Figure 3(a)) and when the importance of speed is increased (Figure 3(b)).

Figure 3. Screenshot example of the refugee problem. The agents (circles) are moving from left to right. (a) occurs when there is a strong desire for safety and (b) when speed is more desirable. The color of the agents shows which coalition they are currently a member.

In Figure 3, the agents representing refugees move from the origin (left) to safety (right). Figure 3(a)shows the grand coalition formed, while in Figure 3(b), the maximum coalition size is three. The highlighted points indicate the slowest agents in a given scenario. The agents are purposely randomly scattered vertically, to give a better view of the coalitions that form. Numerous coalition sizes and distributions are possible due to the coalition formation mechanisms, i.e., kicked out, coalition split, and super coalitions, which were simpler forms of the mechanisms described in Section 3.7. The “kicked out” behaviour allows coalitions to remove members that are too slow or fall too far behind and consequently decreases the rest of the coalition members’ utilities relating to reaching safety in a timely fashion. The “coalition split” behaviour occurs when sub-coalitions of faster members split from the main coalition that has slower members. “Super coalition” allows smaller coalitions in close proximity to join together.

The analysis of the model especially focused on the effects of the preference for speed as opposed to safety in numbers. With a low preference, agents tend to form coalitions over rushing to get to the destination. With a higher preference, most agents do not form coalitions as they put very high weight on reaching the site on their own without someone slowing them down. Though this result is obvious, what was interesting was how the dynamics of coalitions changed over time. In the beginning of a simulation run, the agents will pair up with anyone – even slow agents; however, as the coalition sizes increase, these slow individuals may be kicked out.

What was interesting is that the model showed there tended to be a large gap between the main group of refugees arriving to safety and the arrival of the slowest (i.e., probably most vulnerable) refugees. Further investigation incorporating real-world challenges such as individuals’ health (O’Neill et al., 1997), security (Vernon-Bido et al., 2018), cultural barriers (Sotirov & Winkel, 2016) could help to better understand the conditions and motivations of coalition formation.

4.3. El Farol bar problem

The algorithm was also used to study the El Farol bar problem. This problem was proposed by Brain Arthur (Arthur, 1994), and it describes a situation with multiple decision-makers who try to attend a bar when it is not too crowded. The decision-makers use different strategies based on historical data published in the newspaper to determine whether to go or not to attend the bar. Arthur (1994) suggests that most humans do not act rationally but act inductively in a bounded rational way due to the complexities, the human logical ability ceases to cope. Minority games are a generalisation of the El Farol bar problem and are of interest to economists and financial analysts due to their implications for financial market investment (Challet & Zhang, 1997).

Collins (2017) applied the ABMSCORE algorithm to the El Farol bar problem situation to see if agents acting in strategically formed coalitions had an effect on the outcome. The purpose of the adaptations was to assess the effect of coalition decision-making and the availability of a larger strategy pool on the final decision to attend the bar and the eventual overcrowding that comes as a result of the grouping agents.

The adaptation ABMSCORE version introduced the following changes to the original model. First, the agents can choose the best strategy from the coalition’s pool of strategies instead of just using their own strategy. This change could increase the agents’ payoffs, i.e., attending the bar when the bar is not overcrowded. If all the agents remained in their singleton coalition, this would effectively be the same as the original model developed by Arthur.

For the coalition formation, there needs to be a rationale to join or leave the coalition, which the ABMSCORE algorithm accounts for coalition splitting/joining as well as individual agents leaving. In the El Farol bar problem with strategic coalition formation, the agent may join the coalition to gain the ability to use the coalition’s best strategy. Here, coalition size could play an essential role in the agent’s decision to join the coalition because the larger the coalition, the more it contributes to the overcrowding (because the whole coalition will all attend or not). With a sub-coalition split, the coalition might have a reduced coalition size and could perhaps avoid overcrowding. Overcrowding is one of the main reasons to leave the coalition. Note that if a coalition attends an overcrowded night, members may kick out an individual with the worst best strategy (with the highest total absolute error).

In a strategic coalition, the whole coalition follows the same strategy that was identified as the best strategy by the coalition. This can be a problem when the grand coalition forms, which would cause overcrowding in the bar. The figure below shows the model, where the same colours represent agents from the same coalition, and the blue square on the top right corner shows the bar.

Figure 4 shows an example of the adapted version of the El Farol bar problem. In this example, there are a hundred agents, and each timestep represents a night the bar is open. The agent coalition all act together; for example, there is a coalition of 11 agents (which are coloured green) that attended that bar on the night shown in the screenshot. Since the bar is not shown to be overcrowded, this was a wise decision by this green coalition; however, they may make a bad decision the next night.

Figure 4. Screenshot example of the El Farol model when coalition formation is allowed. The blue area represents the El Farol bar, with the remaining area representing agent not attending the bar that time-step. Agents’ color represents which coalition they are a member.

Collins (2017) has compared and shown that the two cases, i.e., coalition formation allowed and not, are statistically different. The work also has concluded that coalition formation was not always ideal for establishing the optimal strategy due to the reduced number of decision-makers in the system (because each coalition makes a decision in turn, not each individual). The results suggest that individuals should not form coalitions when wishing to be in the minority. This, intuitively, makes sense because even though a coalition has access to more potential strategies than an individual, them attending as a coalition contributes to overcrowding more than a single individual attending. In contrast, if agents act individually, their singular decision might not influence the final outcome of overcrowding.

The results obtained from modelling the El Farol bar problem using strategic coalition formation imply that people may be worse off being in a coalition when trying to avoid overcrowding situations. Coalition decision-making may pose more challenges to coordinate and select the best decision due to increased uncertainty and opinion differences within the coalition. Overall, we believe ABMSCORE provides the necessary adaption to the model needed to explore the El Farol problem in contexts where coalitions need to self-organise, cooperate, and predict some outcomes. This approach could be adapted to explore other situations where too many people using a service degrades quality, e.g., choosing an internet provider.

4.4. Small-hold farming cooperatives

Regional food supply systems refer to the systems that involve the movement of local foods from the farm to the consumer. The demand for these systems has increased due to the economic, environmental, and social benefits it brings to the urban as well as the rural communities. However, it is challenging to deal with the large competitors in the region and manage the financial costs.

One way to address these challenges is to consider collaborative transportation methods to reduce costs. However, the collaboration will mean reduced autonomy, which farmers highly value. To better understand the benefit of collaboration and the desire for autonomy, Collins and Krejci (2018) have employed the ABMSCORE algorithm. In this scenario, the small-scale farmers are represented by autonomous agents. The farmer agents determined to form coalitions for coordinated food transport by comparing the value of the coordination with the estimated value of her autonomy.

The model is comprised of n number of farmer agents. The grand coalition will include all the farmer agents, and when a farmer acts alone will be considered a singleton coalition. The agents cooperate based on some utility function, consisting of the following three aspects. The first aspect is the farmer’s dislike of large groups and their desire to stay independent. The second aspect is their desire to maximise profit. The final aspect refers to the adverse effects of geographic distance on a coalition’s ability to function. This includes the increased transportation expenses and the varying logistical preparation.

The simulation generated the following observations: when the preference towards autonomy (a) and the distance between farmers increases, the number of singleton groups increases. Farmers choose to form coalitions with other farmers that are close by when the negative impact of distance is increased. This reduces the number of coalitions that might form. Figure 5 shows the several coalitions being formed between agents that are close by (circles with the same colour).

Figure 5. Screenshot of the small hold farmer’s location with some coalitions being formed (which are shown by coloring the white agents). The farms are shown as circles, with the size of the circle indicating the size (production capability) of a given farm.

Figure 5 shows an aerial perspective of the location of the different small hold farms. Farms where the farmers have formed transportation coalitions are coloured. A white farm indicates that that farmer has not joined a coalition (i.e., they remain in their singleton coalition). Most coalitions are formed with close neighbouring farms, as such, there can be overlap in the coalitions farm circle (shown in the case of the red, green, yellow, and turquoise coalitions). In the example shown in Figure 5, only coalition pairs of farms formed.

The results revealed that the average group size formed under the different scenarios considered was 17 out of 100 farmers, and the maximum group size the authors observed was 27, indicating explicitly that the grand coalition was not formed. These findings provide an interesting evaluation of strategic coalition formation of regional food supply systems, considering the AMBSCORE algorithm. This scenario and the results could be helpful for professionals and stakeholders from the transportation field who work on resource sharing and coordinating logistic activities.

4.5. Human subject experiments

Another scenario that considered ABMSCORE is the glove game study with human subject experiments. The glove game is a non-transferable utility cooperative game-theoretic model which has previously been used in human subject experiments. Understanding human behaviour has been an important but challenging research area due to the personality, preferences, and other discrepancies, as a result of which they act differently in different situations. In a glove game, players have a different number of right-hand and left-hand gloves. The players try to form coalitions to increase their payoff when only the pairs of gloves have values; a right-hand glove is paired with a left-hand glove.

A human experiment was conducted where there was one human player and the rest computerised agents. The computerised agents were controlled by the ABMSCORE algorithm. During each trial, a human subject would play with other computerised agents different glove games. At each round of the game, the players suggest new coalitions to the other players, and the result of the game is a coalition structure.

This scenario investigates two main aspects. The first aspect is if the ABMSCORE algorithm controlled computerised agents’ behaviour was consistent with the human behaviour (Collins et al., 2020). The second aspect evaluated is whether game theory experience affects human behaviour in an interactive simulation with regard to strategic coalition formation (Collins & Etemadidavan, 2021). Various human subject participants were recruited to participate in the game trials. The authors have considered only one human per trial to prevent the complexities that can develop from human interactions. The authors’ experimental approach was correlational research. Two different game settings were analysed, one single-core and the next one multiple-core. The single-core game has a single coalition structure, while the multiple-core has more than one solution. A snapshot of the model is presented in Figure 6.

Figure 6. Screenshot example of glove game using human subject experiment. The agents are represented by the numbered circles, with their color representing which coalition they are a member. The gloves below each agent present the number of gloves they have: left-hand gloves (red) and right-hand gloves (blue).

In the example glove game (Figure 6), shows that three different coalitions have formed. Agents 4 and 6 have formed a coalition, resulting in a total of five pairs being able to sold (2.5 reward for each agent in the coalition) because, in total, they have collectively five left (red) gloves and five (blue) gloves. Agents 0, 2, 3, and 5 also form a coalition; resulting in seven pairs of gloves being sold (4/7 reward for agents in that coalition). Agent 1 is in their singleton coalition, with only one glove pair being formed.This experiment generated two sets of data; one described the demographic information about the participants, and the next one was the simulation output. In total, 31 trials were recorded. The analysis has shown that 8 out of 31 had some experience in game theory. Also, the results have shown that 42% of the human’s final coalition is a member of the core. The human participants’ final payoff 60% of the time was a core payoff or higher. The results highlighted the participants’ tendency to maximise their profit, even though perhaps they were not in the stable coalition structure. Game theory experience showed no statistically significant association with the participants’ final coalition being in the core. Overall, the outcome of the simulation analysis showed that the ABMSCORE algorithm controlled computerised agents’ behaviour was consistent. However, the human participants did not seem to be motivated to find a stable coalition structure and tended to give up, while the computerised agents were (Grigoryan et al., 2022).

This scenario can be adopted to further explore human behaviour and decision-making procedures in simulated and experimental environments. For example, actual incentives can be provided to the participants, and estimate the impact of these incentives.

5. Color segregation model

The original and arguably most famous agent-based model is Schelling’s segregation model (Schelling, 1971). In the Schelling model, he demonstrates that segregation can occur over time, even when the population has a relatively high tolerance for the proportion of their neighbours that are different from them (i.e., they remain happy even when 60% or more of their neighbours are not like them). The model only considered two types of individuals (which Schelling called “zero” and “stars”). An example of model output from the Schelling model can be seen in Figure 7; here, you can see clusters of the two types; this type of segregation clustering reflects the racial segregation that occurs in US cities (Wilensky & Rand, 2015).

Figure 7. Screenshot from the computerized version of Schelling’s segregation model. The squares represent the living location of the agents. The color of the squares indicates the type of agent living there; there are blue and orange agents. Empty locations are represented by white squares. The simulated world is assumed to be a torus.

Figure 7 shows a screenshot from Schelling’s segregation simulation. In the simulation, each agent lives in the squares, and they all have the maximum tolerance threshold for its Moore’s neighbours that are a different type from them; if is threshold is breached, then they will move to a different location. This moving of agents results in the agents becoming segregated into two groups.

In the model discussed in this section, we increase the number of types to 20 and, instead of physical location, we apply the ABMSCORE algorithm to investigate coalition formation (thus, the coalition are equivalent to the clusters seen in Schelling’s Segregation Model). Others have considered this segregation model with more than two types: Schelling (1978) discusses cases involving multiple types, and Wilensky and Rand (2015) demonstrate a version of Schelling’s segregation model with up to five types. Their work focused on the segregation of types, whereas our model focuses on the coalition of different types.

There are several other changes that we make to the segregation model. Firstly, we remove the dichotomous construct of similar or not and replace it with a spectrum of preferences. The different agent types can be considered ordered; a given type prefers the other types that are closer to it on a spectrum of types. For example, looking at Figure 8, the “cows” prefer to be in a group with the “turtles” over the “airplanes”. Secondly, having preferences means that the agents can choose strategically which coalitions to join or leave; thus, we create a hedonic game. We are not the first to include strategic behaviour in Schelling model (Chauhan et al., 2018); they allowed agents to choose where they want to move as opposed to it being randomly selected.

Figure 8. A screenshot from the Color Segregation model which shows the 20 different types and their relation to each other. This is also an example of a model outcome when 100 agents have a tolerance only for their type. The color shows the which coalition an agent is a member, and the shape shows the type.

Figure 8 shows the coalition split when the agents will only tolerate being in a coalition with those of the same type. Each coalition has its own colour. The type of an agent is shown by its shape, e.g., triangle, airplane, happy face, etc. The simulation disperses the coalitions around a 2-D map in a clock-like pattern. This clock-like pattern is also used to show who close different types are to each other; for example, planes are most similar to their neighbouring types truck and stars. Though we represent the types on a circle in the diagram for aesthetic reasons, the type preferences do not wrap; that is, trees and triangles are not neighbouring types.

The use of a colour wheel to segregate agents was also used by Salamanca and Núñez-Corrales (2019). In their agent-based model, they were investigating social viscosity in regards to the self-organising group and were using agent colour as a proxy for social identity. In their model, colour ordering mattered, whereas, in our model, the colour of the coalitions is arbitrary.

5.1. Model

In Schelling’s original segregation model, agents would relocate (or have a desire to relocate) when a certain percentage of their neighbours were dissimilar to them. In our model, the agents leave their coalition when the average type in their coalition is farther away from their type by some threshold. We call this threshold the “tolerance distance” and represent it with a lambda. The tolerance constant is used in determining the value of a coalition (payoff) to an agent. The agents are assumed to be rational and desire to be in a coalition that maximises their payoff. The payoff of a coalition, C, that agent, i, belongs to is:

(1) $V_i\left(\mathit{C}\right)=\left|\mathit{C}\right|\ast \left(\mathit{\lambda }-\left|\mathit{g}\left(\mathit{i}\right)-\frac{1}{\left|\mathit{S}\right|}\sum _{\mathit{j}\in \mathit{S}}\mathit{g}\left(\mathit{j}\right)\right|\right)$(1)

Where $\mathit{\lambda }\in \left\{0,1,\dots ,20\right\}$ is a tolerance distance, and $\mathit{g}\left(.\right)$ Is a function that determines the type of an agent; in our model, types are $\mathit{g}\left(.\right)\in \left\{0,1,\dots ,19\right\}$. We assume that the agents what to be in the largest group possible if the average type is acceptable (i.e., the left-hand part of the equation is positive). Thus, the agents must balance, in choosing their coalition, the existing size of the coalition with its average type; that is, given two coalitions of the same average type, the agent would prefer to join the larger one. The agents must, thus, balance between choosing to join a coalition with a large number of agents with how close they are to the average type of that coalition.

We can examine the payoff function closer by considering its extremes. When Lambda = 0, the agents gain no utility from joining a coalition with any other agent; this results in every agent remaining in their singleton coalition, which achieves the highest payoff of zero (all payoffs, in this case, are non-positive). The situation is simpler when Lambda = 1, agents do care about coalition size; in this case, the agents will look for coalitions of agents of the same type or similar type; however, it is feasible that the agent would join a large mixed coalition if the average coalition type is close to their type. At the other extreme, when Lambda = 20, the agents have a positive payoff for all coalitions; this makes the size coefficient more important than in cases when lambda is smaller. From our simulation runs, this large lambda value always resulted in the grand coalition forming.

A critical aspect of the ABMSCORE algorithm is that it should be possible for an agent to want to leave (or join) a coalition. Reason to Join: The agents want to be in as large a coalition as possible, assuming the average type of that coalition is acceptable. The more agents in the coalition, the higher $\left|C_i\right|$ will be and, as such, the higher the value to an agent (assuming the average type of the coalition stays the same). Reason to leave: The agents want to be in a coalition that the average type is as like them as much as possible, if their current coalition’s average type moves away from their type value significantly, they will leave.

Figure 9 shows the results from two different simulation runs is shown, for different lambda values. For (a) lower lambda value of two, an agent cannot deviate too much from a coalitions average type before its value payoffs becomes negative; hence, there are more coalitions present in (a) than (b), which has a higher lambda value. There are a few interesting phenomena that occur in both cases. For the coalition at the top of the screenshot for (a), you will notice a single differently coloured cow (type 5) (so it is in its singleton coalition); this cow would benefit from joining the nearby coalition; however, due to the payoff functions dynamics, that coalitions single happy face (type 7) has blocked its membership. Similarly, this is the way the tree (type 0) has been exclude in (b).

Figure 9. Screenshots from the simulation showing examples of the number of coalitions that form when lambda is (a) two and (b) seven. Coalition membership is shown by both colour and position.

We conducted 100 simulation runs for each value of lambda for a total of 2,100. The batch runs were conducted on a standard Windows 10 machine, and the simulation was created in the NetLogo software package (Wilensky, 1999). Symbols graphically represented the different types of agents, and the coalitions were uniquely coloured to help distinguish them from each other. To further help distinguish the coalition, the agents moved to a point on the circle, which represented the average type of their group (average type multiplied by 18 to determine the angle on the circle for the focal point). Each run contained 100 agents, who were randomly assigned a type at initialisation.

5.2. Worked example

To give the reader a better understanding of the algorithm and its mechanism, we consider a very simplified example. In this example, we are assuming that only three agents are present: a car (type 13), truck (type 14), and plane (type 15). We assume that lambda is two, and each agent starts in their singleton coalition. Based on Equation (1)(1) $V_i\left(\mathit{C}\right)=\left|\mathit{C}\right|\ast \left(\mathit{\lambda }-\left|\mathit{g}\left(\mathit{i}\right)-\frac{1}{\left|\mathit{S}\right|}\sum _{\mathit{j}\in \mathit{S}}\mathit{g}\left(\mathit{j}\right)\right|\right)$(1) , each agent has a current value of two. Now we consider what happens when coalitions are suggested.

Imagine during the first round, a join coalition is first suggested. Randomly, the car and the plane singleton coalitions are selected to be evaluated. First, we create a suggested coalition of the car and plane. Evaluating this suggested coalition for both agents, we notice that they would both obtain a value of two under this dyad coalition. Since this value is not an improvement on their current value (of two), both agents reject this suggestion.

The next type of coalition suggestion considered by the algorithm is the ’exit suggestion’. Since all agents are currently in their singleton coalition, this suggestion has no impact on the coalition structure no matter which agent is selected. The next type is the “pair suggest”. Consider the car and the truck agent being chosen randomly. Again, we created a suggested coalition of the car and the truck this time. The suggested dyad coalition results in a value of three for both agents. Since this improves their current payoffs, both agents choose the suggested coalition and are both placed in that dyad coalition. This coalition structure, {car, truck}{plane}, is stable, and all other coalition suggestions will not result in a change to the coalition structure.

Note that under the ABMSCORE algorithm, the grand coalition will never form in this example, even though it is weakly Pareto optimal stable solution. The reason is that it is not possible to form the grand coalition from a coalition structure with an existing pair under the ABMSCORE algorithm, and once a pair is formed, one of the agents (either car or plane) does not gain any further benefit from joining the grand coalition so will block its formation.

6. Results

This section presents the results from the 2,100 colour-segregation model runs. Each run was complete until steady-state had been reached or 10,000 time-steps had passed (though steady-state was always reached well in advance of this). The focus of the discussion is on the effects of varying the tolerance distance on the final number of coalitions formed. Figure 6 shows a “fuzzed” scatter graph of the results. By “fuzzed”, it is meant that the data points were slightly randomly perturbed (by adding a small random amount to their values); otherwise, they would be on top of each other, making it difficult to visualise (Everitt & Dunn, 2010; Lynch et al., 2021).

Figure 10 shows a scatter plot where the data has been slightly perturbed (fuzzed) for better clarity. As the graph shows, there is a rapid decline in the number of coalitions formed as the tolerance ratio is increased from zero.

Figure 10. Fuzzed scatter plot depicting the number of coalitions formed in relation to the tolerance weight variable. The best fit lines are also included.

The graph indicates what might be expected. That is, when the agent’s tolerance is high, then large coalitions form, and when it is low, a large number of coalitions, with smaller sizes each, form. At the extreme, when every type is tolerated by the agents (i.e., it is not possible to have a negative utility), we find that the grand coalition forms, so there is one coalition (which contacts all the agents). When the tolerance distance is zero, then the agents will stay on their own or stay within an already formed coalition that contains only their type; they will not actively seek others of their own type (i.e., the best utility they can obtain is zero, which is the same whether they are on their own or in a coalition of their own type). When the tolerance distance is one, then the agent’s activity seeks to form coalitions with their own type (since they increase their utility by adding more same-type individuals to their coalition); this results in 20 coalitions being formed, which is reflective of the 20 types.

Fitting a line to the graph resulted in the following equation:

$\mathit{f}\left(\mathit{x}\right)=1+100/{\left(\mathit{x}+1\right)}^2$

This line is shown in red in Figure 6. The dotted lines represent when the power of the denominator is varied to 1.5 and 2.5, respectively.

There are several variations that could be conducted to further investigate the emergent phenomenon of the colour-segregation model. For example, we could vary the number of types and agents to see if that impacts the results. We could also vary our initial conditions. In the runs presented, all the agents started in the grand coalition, and the coalitions split from there; conducting the runs when every agent started in their singleton coalition resulted in similar results but with less spread within a fixed tolerance distance value, i.e., at lambda equals zero, all runs resulted in 100 coalitions being formed. We presented the results from a grand coalition start consistent with prior research efforts (i.e., Vernon-Bido and Collins (2021)).

6.1. Difference to the original Schelling’s segregation model

The main difference from Schelling’s segregation model is that our model can achieve stability under any tolerance distance. Under certain circumstances (especially when the number of available empty spaces is relatively low), Schelling’s segregation exhibits instability when there is a low tolerance threshold, i.e., the simulation never has a situation when all agents do not want to move. In the colour-segregation model, both extremes of coalition formation (the grand coalition and the set of singleton coalitions) can be achieved by varying the tolerance distance to its extremes, and, more importantly, this formation is stable. Thus, our model provides a stable final solution output (assuming adequate simulation rounds completed).

Another important distinction between the two models is that our colour-segregation model is not location dependent, meaning that coalition formation can occur irrespective of the agent’s location. This is important when modelling situations of type-based coalition formation that is not restricted by physical location, i.e., coalitions of political parties or coalitions formed over the Internet. In our model, the agent’s payoff is dependent on whole coalition (type average) as opposed to just its neighbours, meaning that the whole coalition is considered in decisions to join or leave a coalition. However, in situations where the agents are not fully aware of their own coalition, Schelling’s approach is more appropriate or variations of it; for example, Agarwal et al. (2020).

7. Discussion

In this section, we discuss the application requirements of ABMSCORE, practical application considerations, and an evaluation of the algorithm. In the application requirements section, we discuss some of the requirements of the modelling situation that might make it worthwhile to apply ABMSCORE. In the practical application section, we discuss some of the modelling decisions and activities that a developer might need to consider when applying the algorithm. Finally, this section provides some of the details of the evaluation of the algorithm, especially, how it compares to the theorised core partition and actual human behaviour.

7.1. Application requirements

In this section, we discuss some of the potential requirements for the application of the ABMSCORE approach. These requirements discussed in this section are only suggestions by the authors, and their appropriateness will depend on the modelling situation being developed. Initially, we discussed some of the general requirements with regards to the simuland (the system to be simulated) and the purpose of simulation before discussing some more technical requirements.

Obviously, the ABMSCORE could be used for situations that include group or coalition formation or with situations where existing groups may dynamically change. For this section, we are assuming the formation of groups of humans, but the approach could be applied to situations that involve any entities or components coming together to form a group. However, the law of parsimony implies that incorporation of unnecessary components should be avoided and, as such, we advocate that the ABMSCORE approach should only be incorporated if strategic group formation is an essential and/or important part of the system under study (called the simuland by Petty (2010) and others), for the given purpose that the simulation is being built. For example, imagine the student body of a high school; if a simulation is being built to understand the formation of cliché over a school year, then ABMSCORE might help; however, if a simulation is being built to understand the evacuation of the high school, we would advocate that changes to the cliché will be minimal and do not affect the evacuation time, so group formation modelling is not needed in this scenario.

Another reason not to include the ABMSCORE algorithm is when strategic group formation is not well-understood. That is, the mechanism and motivations of the simuland regarding the strategic group formation are not well understood. Unless the purpose of the simulation is to explore and understand these mechanisms and motivations, we would advocate that theory (about the simuland’s strategic group formation) first needs to be developed and tested before the simulation model can be built. In the next couple of subsections, we discuss some points with regard to understanding the simuland’s mechanisms that might be required to implement ABMSCORE.

7.1.1. Fixed coalition payoff

Almost all the applications of ABMSCORE algorithms assume that the coalition’s payoff vector is fixed. That is, the payoffs an individual gets are purely dependent on a coalition with which they are a member. This means that once a coalition forms, the payoff a member receives is fixed. Hedonic games model this situation.

The only application described above where the coalition’s payoff is dependent on coalitions formed was the El Farol model. Instead of a hedonic game, the El Farol model is closer to a canonical coalition game (Saad et al., 2009). Canonical coalition games are a form of a cooperative game where the value of the coalition is dependent on the other coalitions. The El Farol model is not precisely a canonical coalition game because it is clearly not superadditive, as the grand coalition clearly has the worst value, not the best.

The El Farol model was also the model with the most concerning results, i.e., introductory coalitions made the situation worse for the agents, not better. As such, this could be an indicator that ABMSCORE method is not appropriate for canonical coalition games. We believe that it has been effective in modelling hedonic games because once a coalition has formed, its payoff does not fluctuate due to the actions of agents outside the coalition; and it only changes once an agent(s) joins or leaves the coalition. Thus, we believe that the canonical coalition game environment is too unstable for the ABMSCORE algorithm. In previous research, there were problems of instability when artificial intelligence was introduced, i.e., reinforcement learning, into an agent-based model (Collins et al., 2014).

This issue of impact in determining the value of a coalition due to events outside the coalition is also why we do not believe that the ABMSCORE algorithm will be effective if applied to transferable utility (TU) games. The payoff vector, or imputation, of a coalition in TU games is dependent on what other coalitions could form; agents use these potential coalitions as bargaining chips when determining how the coalition’s value will be split amongst agents. Hence, whether a coalition forms and the resultant payoff vector is dependent on what other coalitions have formed. There might also be concerns with other forms of NTU since, in the strictest sense of an NTU game, an individual’s payoff is not fixed in a given coalition, and internal bargaining must occur (Chalkiadakis et al., 2011). Hence, we have concerns about applying ABMSCORE beyond hedonic games.

7.1.2. Benefit

Another requirement of the scenario being modelled for ABMSCORE to be useful, is that there must be a possibility that, under the right conditions, an agent would want to leave a coalition and that, under probably different conditions, an agent would want to join a coalition. That is, sometimes there are conditions where the agents desire to leave the coalitions they are in, and sometimes they desire to join a new coalition. In a super-additive hedonic game, there is never a situation where an agent or group of agents would want to leave the coalition to form a smaller one (assuming the V(.) in equation (1)(1) $V_i\left(\mathit{C}\right)=\left|\mathit{C}\right|\ast \left(\mathit{\lambda }-\left|\mathit{g}\left(\mathit{i}\right)-\frac{1}{\left|\mathit{S}\right|}\sum _{\mathit{j}\in \mathit{S}}\mathit{g}\left(\mathit{j}\right)\right|\right)$(1) is a vector, as would be appropriate for a hedonic game). Super-additive games always result in the grand coalition forming. Similarly, if there is never a reason to join a coalition, then the agents would remain in their singleton coalitions or degrade into them (because they are individually rational). Table 1 shows the expected outcomes from having some, or none, of these requirements.

Table 1. Expected results from having, or not, different characteristics of the modeled scenario.

Potential beneficial reasons	To leave coalition	None
To join coalition	Dynamic situation that could be modeled with ABMSCORE	Grand coalition
None	Singleton coalitions	Static

Beyond the requirement of needing these two desires in the agent, there is also a requirement to have a balance of these two desires. If one desire is far stronger or far more common, then we will just end up in a situation of either the grand coalition or all singleton coalitions. However, this imbalance could be used to help verify and validate the simulation as well. By setting the desires to extremes, we would expect the grand coalition, or all singleton coalitions, to be observed. If this is not the case, then it should be questioned why. This approach was used in both the refugee model and the farming model.

7.2. Practical application

One of the main motivations behind this paper comes from discussions with potential users of ABMSCORE; who are interested in the approach but do not know where to start or whether it is completely appropriate for their situation. Some of the requirements for ABMSCORE are discussed above, and the model section gives a detailed overview of technical specifications. The code for the Color Segregation model was written so that a user could, hopefully easily swap out their modelling requirements within the code structure. However, these technical specifications do not answer all the questions that a user might have; this section provides more details on the actual practical application of ABMSCORE. This includes a discussion on extreme input testing, initialisation, and convergence.

7.2.1. Extreme input testing

Extreme Input Testing is a method used in software testing to tell whether the software behaves as expected at the boundaries of the input domain (Balci, 1998). It is a form of boundary value analysis, though it is discussed here from an assertion-checking standpoint. Simply point out, if the expected behaviour is known at the extremes of the input values (i.e., minimum and maximum), then the model should behave as expected at these extremes. In our models, we consider the extremes to be the desire to leave or join a coalition.

Earlier, it was discussed how the model would behave under different desires to leave or join a coalition; the outcome of these desires is shown in Table 1. If these different desires are explicitly included numerically as independent aspects of the utility function, then they can be weighted, and the extremes can be investigated. Ideally, for conducting this type of testing, if your utility to agent “i” of being part of coalition “s”, can be put in the form:

$\mathit{U}\left(\mathit{i},\mathit{\hspace{0.17em}}\mathit{s}\right)=\mathit{\lambda }{U}_{\mathit{Join}}\left(\mathit{i},\mathit{s}\right)+\left(1-\mathit{\lambda }\right)U_{\mathit{leave}}\left(\mathit{i},\mathit{s}\right)$

This is where $U_{\mathit{Join}}$ is a utility function that deals with the reason an agent might join the coalition. $U_{\mathit{leave}}$ is a utility function that deals with the reason an agent might leave a coalition. $\mathit{\lambda }$ is the exponential weight; when it is zero you should observe, in your simulation, no agents joining a new coalition and, probably, the singleton coalitions forming; when it is one, you should observe no agents leaving a new coalition and probably, the grand coalition forming.

The refugee egress model, discussed in Section 4.2, is used here as an example to give you a better understanding of this utility split. In the refugee movement model, the agents gain benefit from being in a larger group (safer in numbers); as such, their $U_{\mathit{Join}}$ is determined by coalition size. Slightly more complicated is their $U_{\mathit{leave}}$. The agents want to move as fast as they can, and their coalition moves at the average speed of its members; thus, they have an incentive to leave a slow coalition, or form a sub-coalition of faster members and split the coalition. In Figure 11, you can see how the agents have split into various coalitions, with the larger coalitions being slower than, the smaller ones.

Figure 11. Screenshot from refuge movement model, with agents moving from right to left. The color and location of the agents shows which coalition they are currently a member.

Other models discussed in the applications section also have this split in utility. For example, in the small-hold farming collaboration, the agents must weigh autonomy with cost savings. Determining whether your model acts as expected at the extremes can be part of the validation process for the simulation.

7.2.2. Initialization

When applying the ABMSCORE approach, the developer must consider the agents’ initial coalitions. Unless the modeller has collected detailed data on the initial coalitions of the system, it is unlikely that initial coalitions will be known (as knowing which coalitions will form is likely part of the reason for using the ABMSCORE approach in the first place). As such, we advocate again for the extremes: either all agents start in their singleton set or all agents start in the grand coalition. Obviously, if you expect your agents to end up in the grand coalition (singleton coalitions), we would suggest that you use initialise in the singleton coalitions (grand coalition).

In some cases, it has been shown not to matter whether you start in either extreme (Vernon-Bido, 2022); analysis of the refugee movement model also found that initial starting groups do not matter. However, it is not difficult to imagine situations where it does matter, especially if the benefits of joining and leaving are not balanced In case simulation results are sensitive to the initial coalition structure, sensitivity analysis could be conducted by considering variations in the start-up structure or even considering the other extreme. This would be part of a wider validation plan as, if the simulation is sensitive to the startup conditions, one will need to be able to justify that sensitivity.

In some simulations, a warm-up period can be used to mitigate the effects of inaccurate initialisation. A warm-up period allows the simulation to run for a certain number of rounds before any results data is collected. A warm-up period allows the simulation to compensate for any extremities in parameter value, from inaccurate initialisation, through the simulation’s dynamic negative feedback loops. Determining how long a warm-up period should be is non-trivial. Robinson (2007) provides a discussion on a statistical approach to determining the warm-up period. From an experienced viewpoint, Bandyopadhyay and Datta (1990) suggest that you double any estimate you create for the warm-up period.

7.2.3. Convergence

A common focus of academic simulations is on their ability to reach steady-state (Law, 2015). However, many real-world systems of interest, especially human systems, are not in a steady state and will probably never be. Salt (2008) calls the academic obsession with steady-state the “dead fish fallacy”. However, understanding the steady-state of simulation can be useful in understanding the system. Ideally, the simulation converges to a known solution. For hedonic games, this could be one of several different solutions based on the stability criteria considered, e.g., core partition, Nash stable solution, individually stable solution, etc (Bogomolnaia & Jackson, 2002). Our research has predominantly focused on the core partition, which we call a stable solution, due to its prevalence in the literature. In this section, it is discussed the difficulties of convergence to a known solution or even approximations of that solution.

Convergence of the ABMSCORE algorithm to the core partition is not guaranteed for every conceivable game. It is possible to construct games that will never converge, as Bonifaco et al. (2020) constructed a series of cooperative games in which the ABMSCORE algorithm, or any similar algorithms, would never converge to a core partition. In fact, a stable solution was found for the neighbourhood strength problem, which could never be reached by the algorithm; this solution involved two coalitions that had members interlaced with each other (Collins & Frydenlund, 2018). A simple example is as follows: consider a game such that being in a pair is the worst situation and being in a set of three is the best. This can be represented, mathematically, as follows:

$\text{V}\left(\left\{\text{i}\right\}\right)=1,\text{V}\left(\left\{\text{i},\text{j}\right\}\right)=0,\text{V}\left(\left\{\text{i},\text{j},\text{k}\right\}\right)=3,\forall \text{i},\text{j},\text{k}\in \text{N}$

$\mathrm{V}\left(\mathrm{S}\right)=1\mathit{\hspace{0.17em}}\mathrm{\forall }\mathrm{S}\subseteq \mathrm{N}\mathrm{s}.\mathrm{t}.\mathit{\hspace{0.17em}}\left|\mathrm{S}\right|>3$

If the agents start in their singleton sets, they will never reach the grand coalition using the ABMSCORE algorithm (because, at most, two existing coalitions are considered in any potential updates, but you need three coalitions to be considered to get over the lower pair value).

There might not even be a stable solution in the first place. Collins et al. (2022) has shown that 6% of hedonic games do not have a core. We suspect that the application of the ABMSCORE algorithm to the El Farol algorithm does not have a stable solution.

Given these difficulties, there is no guarantee that the ABMSCORE algorithm will find a stable solution. In a simulation experiment on glove games, Vernon-Bido and Collins (2021) found that over 90% of their simulation runs found a core partition (stable solution) after 100,000 time-steps. However, their work found an eight-player glove that failed to converge 25% of the time; the reason for this lack of convergence is due to the particular complexities of that game.

An obvious question is how “close” the output of the simulation runs that did not find the stable solution. Unfortunately, there is not a simple answer to this issue since the output of the algorithm is a partition and what is meant by “close” is difficult to define. In other problems that have a single value or vector as an output, closeness can be easily defined by standard metric measures. However, our output is a partition; it is not clear what is meant by close, as it could be one of several ideas, e.g., the number of agents in the “wrong” coalition, similar coalition structure, number of coalition agents moves required to reach core partition, etc. A possible means to resolve this issue is discussed in Collins (2020), which includes a novel approach of comparison using Hamming distances. Some have employed hamming distances to compare partitions (Mirkin & Chernyi, 1970; Rossi, 2015). These distances do not take into account the complexities of the game. For example, consider the partition (12)(34)(5) which is only two joins away from the (12345); this might seem relatively close; however, if subsets (1234), (125), and (345) all have bad payoffs for their members, then they will never form so (12)(34)(5) will never be morphed into (12345). As such, with regards to the ABMSCORE algorithm, we have avoided defining closeness.

7.2.4. Validation

Validation is an important step for any development of simulation, as it helps provide creditability of the simulation’s results to the simulation’s customer (Petty, 2010). Agent-based models are a particular simulation paradigm and have certain nuances when it comes to validation (Collins, Koehler, et al., in press; Hill et al., 2006; Macal, 2016). There is one aspect of validation that we will discuss here is the concepts of microvalidation and macro validation (Moss & Edmonds, 2005). The latter is concerned with ensuring the modelled systems behave as the real-world system does. Microvalidation is ensuring that the computerised agents in an ABMS behave like real-world actors. We would argue, if possible, to focus on macro validation, with regards to ABMSCORE because data on actual human strategic coalition formation is very limited. We have conducted some limited experiments on human behaviour, as it compares to the ABMSCORE’s behaviour, but the results are limited (Grigoryan et al., 2022). The ABMSCORE algorithm, itself, has been compared in several ways.

7.3. Evaluation of algorithm

We have conducted several studies to evaluate the algorithm. These range from comparing the algorithms to an idealised solution, the core, to actual human behaviour. These evaluations are not a validation of the algorithm because they are not for a specific real-world purpose; a simulation can only be validated for a purpose; you cannot just generally validate a simulation (Petty, 2010).

Comparing the outcomes of the algorithm to an obvious modelling alternative, known as docking (Axtell et al., 1996), is one evaluation approach. The obvious model to compare to is cooperative game theory, specifically the core. As discussed, finding the core of a game is NP-complete (Ballester, 2004); as such, there is a limitation on size that can be compared. As already mentioned, Vernon-Bido and Collins (2021) compared the ABMSCORE algorithm for a particular type of cooperative game, known as the glove game, for games with up to nine agents and found the algorithm found a core solution, which is stable, over 90% of the time. The core is actually a collection of core partitions, for hedonic games, and Vernon-Bido and Collins research also showed that only a fraction of the core partitions were reached, implying that some core partitions are easier to find than others. The number of agents considered was increased to 15, with similar results (Vernon-Bido, 2022).

Comparing to other models is one means of evaluation. Another approach is to comparison is to compare to actual human behaviour. Humans are not generic, and you would expect different people to play the game in different ways. From Collins and Etemadidavan (2021) it was shown that some demographics, like education level, did not matter; however, the review of the demographics was not comprehensive. Again, using a glove game, it was shown the agents were consistent with the algorithm at the individual agent decision level (Collins et al., 2020), and the rate of finding a core solution was consistent (Grigoryan et al., 2022), but only 42% of the time did the human players find the macro-level core partition.

The low rate of human players finding the core partition might seem concerning. However, it should be remembered that a core partition is an outcome of cooperative game theory. This implies that the cooperative game theory solution is not reflective of actual human play. This problem has been discussed within the literature and is the reason for the rise of behavioural game theory (Camerer, 2011). Given this discrepancy between the theoretical solutions and real-world solutions, it would be impossible for ABMSCORE to be comparable to both.

7.3.1. Weakness of the algorithm

The discussion earlier in this section has discussed many of the weaknesses of the ABMSCORE modelling approach. These are: it is not guaranteed to converge, it does not necessarily reflect human behaviour, and it requires several criteria of the simuland to be useful. There are others, i.e., it is stochastic, so there is no guarantee the same result will be reached if the simulation experiment is completed; however, all modelling approaches are limited, but interesting results have been achieved, in the past, with the algorithm. To put this another way, as George Box says “all models are wrong, some are useful” (Box, 1979).

8. Future development

There are two areas of future advancement for ABMSCORE. Firstly, the algorithm has been improved once, so it potentially could be improved again. Secondly, new application areas can be derived.

8.1. Future advancement

Vernon-Bido and Collins (2021) were able to improve the original algorithm, presented in Collins and Frydenlund (2018), from as little as 34% to 90%, in terms of finding a core partition in a glove game. This was achieved by introducing new procedures to the algorithm that specifically replicated certain behaviours in the coalition suggestions each round, e.g., pairing, splitting, etc. It is feasible that further improvements could be made.

Vernon-Bido (2022) investigated several different improvements including the ordering of the coalition suggestions and using grand coalition starts. Neither case resulted in an improvement to the algorithm. Other possibilities for change could be how the “left over” coalition is handle (i.e., the coalitions that have had members leave to join better coalitions); at present, they still remain a coalition, but they could disintegrate into singleton coalitions, as suggested in Bonifaco et al. (2020) and used in Murnighan and Roth (1980). However, small scaling testing of this idea did not result in any improvement.

One promising idea is for the agents to use a simulated annealing-like approach, where they are willing to accept a slightly worse coalition for the purposes of exploring the solution space. Simulated annealing is a heuristic method used in Monte Carlo simulation to find optimal solutions to given numeric problems (Van Laarhoven & Aarts, 1987). Simulated annealing has successfully been applied in an ABMS environment previously (Lapp et al., 2019).

8.2. Future application

There are several different directions we would like to explore with the ABMS core algorithm, especially within the human modelling arena. One application would be to advance the famous sugarscape model (Epstein & Axtell, 1996) to include coalition formation; it would be interesting to see what groupings would form. Another application is to introduce coalition formation into ABMS the organisation of businesses, especially project-based team environments (Tsvetovat & Carley, 2004; Zhao et al., 2022). The purpose of the introduction could be to investigate the events of coalition formation on the output of the organisations, i.e., design output from large design teams (Lapp et al., 2019).

Cooperative game theory has a long history of modelling political situations, including voting games and coalition formation in legislative bodies (Chalkiadakis et al., 2011). An obvious application of ABMSCORE algorithm is to model legislative bodies, especially those that involve hundreds of members as finding the core solution of such large games is beyond our current computational capability. The ABMSCORE algorithm is embedded in an agent-based model (ABM) and the strength of that modelling approach is that it can incorporate: modelling high levels of complexity, heterogeneity, and autonomy. This means that ABMSCORE might be useful in providing insight the formation of coalitions in legislative bodies or even insight into the voting outcome of proposed legislative. The authors do not believe that ABMSCORE could be used to predicate the outcome of such a process; however, prediction is only one reason to model (Epstein, 2008), and other reasons might be appropriate like insight into the system and to illuminate core dynamics of the system. More importantly, modelling provides a safe means to examine scenarios when the system breaks down.

9. Conclusions

This paper provides an overview of the application of the ABMSCORE algorithm in agent-based models. The paper provides a detailed introduction to the algorithm as well as descriptions of past applications. The purpose of discussing the different applications is to show the veristically of ABMSCORE applications. It introduces the colour segregation model, which is based on Schelling’s famous segregation model. The paper also provides a detailed discussion of the application requirements for the algorithm and some practical considerations.

The algorithm can be considered under certain circumstances to be useful. It must be possible for the agents in the systems to have some benefit from joining a coalition. similar, it must be feasible that the agents might want to leave a coalition under certain circumstances. Each agent must have a fixed utility for a given coalition; otherwise, the coalition structure would be in constant flux.

The paper intends to provide researchers with all the tools they need to apply the ABMSCORE algorithm to their appropriate modelling problem. We will continue advancing the algorithm and applying it to new situations like organisational structures.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This work was supported by the National Science Foundation [2333570].