Introduction
Agent-based modeling (ABM) is a frequently used paradigm for social simulation (Axtell 2000; Epstein & Axtell 1997; 2008); however, there is little evidence of its use in coalition formations, especially strategic coalition formations. There are few models that explore coalition formation (Collins & Frydenlund 2018; Sie, Sloep, & Bitter-Rijpkema 2014) and even fewer that validate their results against an expected outcome (Abdollahian, Yang, & Nelson 2013). Cooperative game theory is often used to study strategic coalition formation, but solving games involving a significant number of players (agents) is computationally intractable (Chalkiadakis, Elkind, & Wooldridge 2011a). The ABM paradigm provides a platform in which simple rules and interactions between agents can produce a macro-level effect without the large computational requirements. As such, it has the potential to be an effective means for approximating cooperative game solutions for large numbers of agents. In this paper, we intend to show one possible approach to approximating strategic coalition formations in an agent-based model. The model is validated through a comparison of its outputs to those from cooperative game theory.
We present an agent-based model (ABM) for finding core stable coalition structures; that is, coalition structures that are members of the core. The core is a stability solution concept used in cooperative game theory. Our model's algorithm considers a number of different ways to test a coalition structure by considering possible other coalitions that could form. It tests mergers of coalitions, adding an agent to a coalition, dividing a coalition, removing an agent from a coalition, agents breaking away to form a new coalition, and the individual rationality of being in the coalition. Agents examine each potential new coalition to determine if their utility is improved; if the utility is improved for all agents, the new coalition is accepted. Based on the cooperative game theory underpinnings, these procedures allow for the efficient estimation of a stable coalition structure and bring a strategic component to the ABM.
To determine the effectiveness of our ABM's algorithm, an experiment was designed. The experiment uses a Monte Carlo approach that involves comparing the output of the algorithm to the actual core solutions of randomly generated games. The type of game considered is the glove game. The glove game is a simple type of market economy game that is commonly used to exemplify phenomena in cooperative game theory (Hart 1985). There are a number of computational issues that had to be overcome with this experimental approach, including finding the actual core of each generated game. Our results focus on how often our algorithm converges to the core solution.
The remainder of this paper is structured in the following manner. The background section provides an introduction to hedonic games, a discussion on the background of our ABM and its algorithm, and an introduction to the case study. The methods section describes our experimental approach, the "brute-force" method of solving cooperative games, and the experimental design. Finally, the results and conclusions are given with a summary of our work.
Background
The research presented in this paper involves concepts from cooperative game theory, specifically, hedonic game version of the glove game, a simple market economy game. In this section, we provide a brief overview of cooperative game theory, hedonic games, and the glove game. We then provide a discussion on attempts to approximate a cooperative game theory concepts, i.e., core stability, in ABM. This background provides some of the theoretical foundations for the model used in this research that is discussed in the method section of this paper.
Cooperative game theory
Game theory is "the study of mathematical models of conflict and cooperation between intelligent, rational decision-makers" (Myerson 2013, p. 1). Game theory can be split into non-cooperative and cooperative games. Non-cooperative games usually involve only two rational players, and they are well studied (Eatwell, Milgate, & Newman 1987; Von Neumann & Morgenstern 1947). Prisoner's dilemma, named by Albert Tucker in 1950, is possibly the best known non-cooperative game (Flood 1952). Games involving more than two players are usually studied using n-person game theory, which is also known as cooperative games (Chakravarty, Mitra, & Sarkar 2015). In non-cooperative games, both parties know the potential payoff based on the choices made, but they do not have the ability to create a binding agreement before a course of action is selected. Cooperative games, on the other hand, are games in which players can enter into contracts or binding agreements that allow them to form strategic coalitions (Peleg & Sudhölter 2007).
Cooperative games are generally divided into two types: games with transferrable utilities (TU) (also known as characteristic function games) and games with non-transferrable utilities (NTU) (Thomas 2003). Characteristic function games allow a coalition to subdivide the payoff obtained by the coalition, in any possible way (Peleg & Sudhölter 2007); this introduces a two-stage problem for the game; namely, you need to determine which coalitions will form first and how those coalitions will subdivide the payoff amongst the coalition's members. In contrast, NTU games have fixed distributions of the payoff dependent upon the coalition; for example, a member of coalitions payoff might be their preference for being in one coalition and, as such, this payoff cannot be transferred to another player (e.g., I cannot give my joy of being admitted to an exclusive club to another member of that club). Hedonic games are a specific type of NTU game where players have a preference relation over all possible coalitions (Aziz & Savani 2016).
Hedonic games
Cooperative game theory provides an analytic framework for the study of strategic coalition formation (Chalkiadakis, Elkind, & Wooldridge 2011b). Given a situation where a decision-maker must evaluate which coalitions they wish to join, cooperative game theory can aid in this evaluation. Games that are expressed in terms of the decision-makers' (or players') preferences for different coalitions are called hedonic games. In game theory, the term "players" refers to agents; as such, we use these terms interchangeably throughout the paper. A common example of a hedonic game is the roommate problem (Aziz 2013; Gale & Shapley 1962). Here is a simple example of a classic roommate problem: Campus housing is expensive, so students might seek a roommate rather than live alone; a group of three students (A, B, and C) has found a two-bedroom apartment. Student A prefers to room with student B over student C. Student B prefers student C over student A. Student C prefers student A over student B. No student wants to share the apartment with two roommates as one would have to sleep in the living room. Each student demonstrates a preference for a different coalition leading to a cycle of dissatisfaction. Hedonic coalitions, the term originally credited to Dreze & Greenberg (1980), describes how and why various groups, clubs, and communities form and persist (Iehlé 2007). Technically, a coalition in an NTU game could have multiple choices of action to determine their payoff; a hedonic game is an NTU game when there is only one course of action for each coalition (Chalkiadakis et al. 2011b). Since payoffs are fixed for a hedonic game, solving is only a one-stage problem, i.e., you just need to determine which coalitions will form as a player's payoff is fixed for a given coalition.
The outcome of a cooperative game, including hedonic games, is a coalition structure and a payoff vector. A coalition structure is a partition of the players in the game, which is equivalent to a collection of disjoint coalitions that covers all players; the payoff vector is the utility received by the players. In a hedonic game, the utility, for a given player, is a function of the identity of the members in the coalition (Iehlé 2007). There are several ways the solution set of cooperative games can be defined. We will use core stability as our solution concept (Bogomolnaia & Jackson 2002). "A coalition structure is called stable if there is no group of individuals who can all be better off by forming a new deviating coalition. The core of a hedonic game is the collection of all stable coalition structures" (Sung & Dimitrov 2007). Determining the core of a hedonic game is NP-complete (Ballester 2004); for all but the smallest number of agents, it requires an unreasonable amount of computational time to solve. Additionally, if the core exists, it may contain any number of coalition structures. Therefore, a complementary problem for determining the core is to test whether a coalition structure is a member of the core. Testing core membership requires selection of a candidate coalition structure and determining whether the coalition structure fits the criteria to be a part of the core. Core membership testing is co-NP complete (Faigle et al. 1997; Sung & Dimitrov 2007); that is, it is equally as challenging to determine core membership as it is to find the core.
Mathematical notation of hedonic games
The formal structure of a hedonic game is defined as \(G = (N, \succeq_{1}, \dots, \succeq_{n})\) where \(N = \{1, \dots, n\}\) is the non-empty set of players in the game, and \(\succeq_{i}\) is the preference relationship of possible coalitions containing \(i \in N\). \citet{chalkiadakis2011a} define the preference relation as a binary function with the properties of completeness, reflexivity, and transitivity. Completeness denotes that for every pair of coalitions containing \(i\), \( c_{j}^{i}, c_{k}^{i} \subseteq N\), there is a relationship of \( c_{j}^{i} \succeq_{i} c_{k}^{i} \) or \( c_{k}^{i} \succeq_{i} c_{j}^{i} \) . Reflexivity represents the fact that \( c_{j}^{i} \succeq_{i} c_{j}^{i} \). The transitivity properties state that for \(c_{l}^{i} \subseteq N\), if \(c_{j}^{i} \succeq_{i} c_{k}^{i}\) and \(c_{k}^{i} \succeq_{i} c_{l}^{i}\), then \(c_{j}^{i} \succeq_{i} c_{l}^{i}\). The outcome of a hedonic game is a coalition structure. A coalition structure is a partition of all players of the game; that is, it is a set of coalitions that contains every player in exactly one coalition; the union of the coalitions in the coalition structure is \(N\), and the intersection of any pair is the null set. The number of possible coalition structures is combinatorial to the number of players \(n\). For example, a game with 15 players results in over 1.3 billion possible coalition structures (Rahwan et al. 2009). Since a coalition structure is equivalent to partition, the number of coalition structures is a Bell number (Bell 1938).
Not all coalition structures are equally desirable. Game theorists have developed solution concepts for cooperative games that identify sets of coalition structures with distinct properties. Bogomolnaia & Jackson (2002) define solution concepts for hedonic games: core stability, individual stability, Nash stability, and contractually individual stability.
We focus on core stability; a coalition structure that is core stable is called a core partition (Banerjee, Konishi, & Sönmez 2001). The foundation for the core stability concepts lies in Gillies (1959) definition of the core. The core partition is the set of coalition structures that are not dominated by any other coalitions. A coalition \(C \subseteq N\) dominates (or blocks) a coalition structure \(CS\) if, for all \(i \in C\), \(C \succ_{i} CS_{i}\), where \(CS_{i}\) is the coalition in \(CS\) that contains player \(i\) (Chalkiadakis et al. 2011a). The core partition, therefore, represents the set of coalition structures in which there is no incentive for any subset of players to create a new coalition. The core partition "has the same requirement as the core with coalition structure studied in standard cooperative game" (Iehlé 2007); hence we use the terms interchangeably within this paper. A game is core stable if it has a non-empty core.
There are a number of other possible solution concepts that can have been used, namely: individual stability, Nash stability, and contractual individual stability (Bogomolnaia & Jackson 2002). A coalition structure is individually stable if there is not a coalition in which all members would be better off by having another player join the coalition, including that new player. A coalition structure is Nash stable if no player would want to join an alternate coalition, in the current coalition structure, or be a coalition unto themself. Contractual individual stability exists if there is no coalition change that a player can make that is preferable to the coalition the player left and the coalition the player joins (Bogomolnaia & Jackson 2002; Chalkiadakis et al. 2011a).
The solution concepts provide an approach to evaluating coalition formation. Foundationally, it provides the analytic framework for determining which coalition structures are stable. However, a challenge remains. There are a finite number of coalitions, \(2^{N}-1\), but the number of coalition structures and the number of comparisons required is computationally infeasible for a large number of agents. From our example above, a game of 15 players has 33,000 possible coalitions but 1.3 billion potential coalition structures; to determine the core of such a game requires 43 trillion comparisons to be made. This would take 3.5 hours on a single 3.50 GHz core computer, assuming the check can be completed in a single computational step (which is unlikely). If there were 20 agents, this would take 500 years. Determining the core of a hedonic game with arbitrary preferences, preferences that allow ties, is NP-complete (Ballester 2004). Hence, the analytical solution of the core is computationally intensive, and stochastically guessing whether a coalition structure is or is not a member of the core is akin to finding a needle in a haystack. Hence the desire to have heuristical methods. This Computational intractable of solving cooperative games is one of the driving forces behind our agent-based model and its embedded coalition formation algorithm. Our agent-based simulation runs in less than an hour.
However, our approach is a heuristic, and there is no guarantee that it will find a core partition, if one exists, for a given game. The purpose of this paper is to outline an experiment to understand how effective our algorithm is at finding a core partition. To this end, we focus on a use case that we analyze to determining the effectiveness of our ABM. Gloves games are the underlying game type of our use case.
Use Case – The Glove Game
Our use case is a modified version of a simple market economy called the glove game (Hart 1985). This game was chosen because of its simplicity, the core is known to exist, and it can be represented as a hedonic game; however, for our purposes, we represent the glove games using players' payoff allocations as opposed to preferences for ease of understanding. In the glove game, players attempt to create pairs of gloves. Each player is endowed with initial resources – a random number of left gloves and a random number of right gloves. Players form coalitions and determine the number of pairs of gloves that are created by their coalition, the coalition’s value. This value is then divided equally between the players to determine each player’s payoff or preference for the coalition. Each player attempts to maximize their individual payoff. Since the payoff for each player is fixed, this is an NTU game.
Figure 1 is an example of the glove game with three players: a, b, and c. The first table shows the initial resources of each of the players. The second table enumerates each possible coalition and the utility each player in the coalition receives if that coalition is formed; the third table list all possible coalition structures and the individual values a player would receive in that coalition structure. Examining each possibility shows that player b receives the highest value when not combining with any other player. Without the possibility of forming a coalition with b, players a and c both obtain the greatest value by forming a coalition. Thus, [(a, c) (b)] is a core partition. This is the only coalition structure that is in the core.
The glove game has had a number of applications over the years (Hart & Kurz 1983); it is also known as the shoe game (Murnighan & Roth 1977). Hart & Kurz (1983) and Hart (1985) used the glove game to exemplify the different solution mechanisms to cooperative game theory. It has also been used in human experiments in Murnighan & Roth (1977) and Murnighan & Roth (1980). In Murnighan and Roth's first experiment, they only considered three human players and were looking at the effects of communication openness; they concluded that if a player in a weak situation controls that the flow of information, then they can increase the payoff they receive; this is an expected result. In their second experiment, they consider up to seven players in the "shoe" game; this time, they looked at the impacts of veto power; their experiment involved 250 participants. We believe that this paper represents the first time the glove game has been used in an agent-based model.
ABM heuristic coalition structure selection
Coalition formation represents the willingness of players to interact and/or cooperate with one another. Cooperative game theory provides a strategic approach to evaluating coalition formation, but it is computationally infeasible for large numbers of players. Agent-based modeling (ABM) provides a platform for evaluating interactions of many heterogeneous agents but is often found to be lacking the strategic component (Collins & Frydenlund 2018). Agents can be considered players and vice versa; throughout this paper, we use these terms interchangeably. Combining the strategic nature of cooperative games with the interaction paradigm of ABM will create a more computationally efficient way in which to explore coalition formation. Game-theoretic results can be enhanced by ABM (De Marchi & Page 2008).
ABM is a modeling paradigm particularly well suited to handle the interactive nature of coalition formation and to, stochastically, surmise a feasible coalition structure. It is a computation method in which researchers can build and analyze models comprised of agents (players) that interact in an environment (Gilbert 2008). While cooperative game theory mathematically evaluates the formation of every possible coalition, our ABM approach stochastically explores coalitions generated from agent interactions. The benefit of exploring stochastically-generated coalitions is the reduction of computational complexity. Generating every possible coalition structure for cooperative game theory analysis using dynamic programming has a computational complexity of O(3n) (Rothkopf, Pekeč, & Harstad 1998; Yeh 1986) with the actual finding of the core set being NP-Complete for hedonic games (Ballester 2004) while our ABM approach magnitude is linear per time-step, so the computational complexity is determined by the number of time-steps allowed. We implement six basic coalition formation behaviors, with each selecting one player as the focal point, thus reducing the computational complexity by not tying the algorithm run time to an exhaustive search. In this paper, we validate the success of our algorithm by solving the core of cooperative games using a 'brute-force' method, then comparing the results to those generated by the ABM algorithm for the same games. Our ABM algorithm produces core members over 95% of the time.
Both cooperative game theory and agent-based modeling involve modeling multiple agents that are interacting; as such, it might be expected that there would be an overlap of the approaches, i.e., hybrid modeling (Mustafee et al. 2015). However, there is very little in the literature showing a combination of these modeling methods. Abdollahian et al. (2013) incorporated cooperative game theory concepts into an agent-based model of location sites for sustainable energy; they employ the Shapley value (Shapley 1953) as their solution concept, whereas we use the core (Gillies 1959). Ohdaira & Terano (2009) discuss cooperation in an agent-based simulation of the classic Prisoner’s dilemma, but they are focused on non-cooperative game theory. Sie et al. (2014) discuss coalition formation in the context of social networks; they employ the Shapley value. Of the extant literature, the work presented in this paper relates to Collins & Frydenlund (2018), who created a hybrid model of cooperative game theory and agent-based modeling; their work will be discussed later in this paper.
Janovsky & DeLoach (2016) claim to have found a heuristic for solving cooperative games using agent-based modeling. Their approach focuses on a particular form of a characteristic function used in Transferrable Utility (TU) games. Our approach focuses on hedonic games, which are a type of non-transferrable Utility (NTU) game.
The brute-force algorithm, described in the next section, allows us to generate the entire core set of a hedonic game from which we can ascertain if the ABM produced a coalition structure that is a member of that core. The drawback of the brute-force method is that it can only be done for a limited number of agents due to computational requirements. Hence our approach is limited to around nine agents.
Methods
We have conducted a Monte Carlo computational experiment to determine the effectiveness of our ABM approach to coalition formation. To determine effectiveness, we compare the output (i.e., final coalitions structure) generated by our ABM to see if it is a member of the core partition set. Effectiveness is the percentage of trials that this is true. Each trial represents a single simulation run from a glove game.
Each instance of the glove game was created by varying the number of players and randomly generating gloves allocations. For each game, its core partition set is determined using a brute force computational approach. The game was inputted into our ABM, and multiple stochastics runs were completed. This section first describes the ABM and then the brute force algorithm.
Agent-based model
An agent-based model was constructed to replicate coalition formation in a glove game. A full description of our model is given in Appendix A; this description is written following the guides of the Overview, Design Concepts, and Details (ODD) protocol, which is advocated as a standard way to describe ABM (Grimm et al. 2020). The full Netlogo models can be found at Collins (2020). This section briefly describes the major mechanism of our model, including how coalitions are suggested.
Interactions, or opportunities to form coalitions, can occur between individual players, existing coalitions, players, and existing coalitions or within coalitions. Rules of coalition formation within the interaction platform are defined by the hedonic game solution concept: for a new coalition to form, each player in the coalition must prefer the new coalition to its existing coalition. In this way, each coalition change should result in a more stable coalition structure than the predecessor. This, theoretically, should produce a coalition structure that is a member of the core, if the core is non-empty, without an exhaustive search of the solution space. The heuristic presented here advances the coalition formation algorithm developed by Collins & Frydenlund (2018).
Our ABM algorithm is strategic in its determination of whether to change coalitions, i.e., agents will only join a newly formed coalition if it increases their utility; however, it is also a heuristic as it stochastically selects which coalitions to test. Our algorithm consists of six routines for choosing a coalition to test: (1) Join coalitions; (2) Exit coalition; (3) Create pair coalition; (4) Defect coalition; (5) Split coalition; and (6) Return to an individual coalition. Each of these routines is talked about in turn.
- Join coalition: Two agents from different coalitions are chosen randomly. The payoffs of the merged coalitions are calculated. If the payoffs improve for all members of both coalitions, a new coalition is formed, which is the merged coalition.
- Exit coalition: An agent from a coalition whose size is greater than one, i.e., not a singleton coalition, is randomly selected. The payoff of the coalition minus the agent is calculated. If all agents in the remaining coalition improve their payoff by removing the selected agent, the agent is removed from the coalition and forms a singleton coalition.
- Create a pair coalition: Two agents are randomly selected. The payoff for the coalition containing just both agents is calculated. If the payoff of both agents is improved in this new coalition, both agents exit the current coalition in favor of the new one.
- Defect coalition: A randomly chosen agent selects a coalition to which he does not belong. If joining this coalition improves his payoff and the payoff of all members of the coalition, the agent defects from his payoff and the payoff of all members of the coalition, the agent defects from his current coalition and joins the new coalition.
- Split coalition: A coalition is randomly chosen, and a random subset of agents from the coalition are selected to form a separate coalition. If the members of the new coalition improve their payoff or the coalition that remained improve their payoff, the coalition splits into the two coalitions.
- Return to an individual coalition: An agent is randomly chosen. If that agent would be better off on their own, i.e., they prefer the singleton coalition to their current coalition; then, they leave their current coalition to form the singleton coalition. This is known as the individual rationality concept (Thomas 2003).
Players in the game are assumed to be self-interested and individually rational (Chalkiadakis et al. 2011a); that is, they are driven by achieving their preferred coalition and will not join a coalition that does not at least provide satisfaction equal to what they receive being on their own. The final routine ensures that players will only remain in a coalition that is preferable to being alone. In our simulation runs, all agents start on their own.
The six routines are iterative; they are repeated until the coalition structure becomes stable. Normally, stable would be defined as no additional changes occurring to the coalitions for a certain number of time-steps; however, in our experiment, the number of time-steps run is fixed for consistency between trials. The repetition allows players to attempt to migrate into higher preferred coalitions. However, the algorithm arriving at a stable state with respect to coalition structure does not guarantee core membership. It should be noted that not every player and coalition is considered at each time-step, which is a departure from the algorithm from which ours is based because it considered every player at every time-step (Collins & Frydenlund 2018).
The Collins’ and Frydenlund’s algorithm was never formally compared to the actual cooperative game theory core set, though a primary analysis shows that it is not proficient at achieving core partitions (in some cases, it only reach the core solution 4% of the time, which is vastly worse than the results presented for our new algorithm). It examines all agents at every time-step and only considers a subgroup split and supergroup group formation. This original algorithm approach was applied to several areas, including economic minority games (Collins 2017, 2019), generic neighborhood alliances (Collins & Frydenlund 2016b), and refugee movement (Collins & Frydenlund 2016a). Our algorithm is designed with the intent of creating a coalition structure that is a member of the core, i.e., produces results that are comparable to those found by cooperative game theory methods. We, therefore, will validate our algorithm by comparing it to a computational “brute force” mechanism for determining the core. Validation of agent-based models is generally challenging. Several methods of validation are discussed in Gore, Lynch, and Kavak (2016); Klügl (2008); Windrum et al. (2007); Xiang et al. (2005). For our purpose, black box validation, or comparison of inputs and outputs between models, will suffice.
Brute force algorithm
To be able to determine the accuracy of our heuristic algorithm, we must solve the games using another method first so that the solutions of the two approaches can be compared. To do this, we use the brute force method. A naïve or brute-force method for determining the core requires three primary steps: (1) generating every possible coalition structure; (2) generate and evaluate every possible coalition; and (3) comparing every possible coalition to each coalition structure to determine if the coalition blocks the coalition structure. The number of potential coalitions that can be formed is \(n = 20\); the number of possible coalition structures for \(n = 20\) agents exceeds 51 trillion, for example (Rahwan et al. 2009).
The brute-force algorithm is used for two reasons: (1) the complete core is guaranteed to be found; (2) the complete individual checks allow for simpler verification of the algorithm. The downside is that the number of agents for which the algorithm can be used is limited. By the nature of the glove game, the core is guaranteed to exist, i.e., the core is a non-empty set for glove games.
A description of the brute force algorithm is given below. We have chosen not to use the ODD protocol to describe it because we feel a simpler format is adequate. The algorithm has several steps to finding the core.
1. Generate all possible coalition structures.
Djokić et al. (1989) present an iterative algorithm shown in Figure 2 for generating all possible set partitions. This algorithm is executed in a Python program for coalition structure generation. The pseudocode for the algorithm is given in Figure 2.
2. Generate all possible coalitions and determine the payoff for each.
There are 2n – 1 possible coalition and iteratively generated using its binary representation. Agent membership, to a given coalition, is determined by a Boolean number. Each “1” bit signifies that the agent is a member of coalition C. The payoffs are calculated for each coalition.
In the coalition structure of a non-cooperative game, the marginal contribution is not a factor. The payoff for each agent is purely determined by which agents are a member of its coalition. For the glove game, the payoffs are either determined by the number of pairs of gloves the coalition has. The payoff division, amongst the agents, is a function of the cardinality of the agent i’s coalition (Ci) and the agent i’s utility function. The possible payoff function, for a given agent i in coalition Ci, is defined as follows:
| $$u_{i} (C_{i}) = \frac{min (\sum_{x \in C_{i}}L(x),\sum_{x \in C_{i}}R(x))}{|C_{i}|}$$ |
L(x) stands for the number of left gloves agent x has, and R(x) is the number of right gloves. A detailed discussion on the glove game is given below.
3. Test each coalition structure against every coalition payoff to determine if the coalition structure is blocked.
Determining if the coalition structure (CS) is blocked is a simple but computationally expensive process depicted in Figure 3. The approach requires three iterative loops. The outer loop is structured as in step 2 with the loop executing 2n – 1 times, with the number of each pass being converted to a binary value to represent each agent that exists in the coalition (C). A second (nested) loop then iterates through every possible CS. If the CS is not blocked, a third (nested) loop iterates over the number of agents (length of the binary string) to test if the agent is a member of C and if the payoff of the agent in C is in is greater than the payoff the agent receives in CS. If all agents in the tested C can improve their position over the CS, then CS is marked as blocked.
4. Store all coalition structures that are not blocked in the core file.
A final pass is made through the coalition structures to denote that any CS that is not blocked is part of the core. The core of the game is static. Execution of the brute force algorithm provides a complete listing of the coalition structures that are in the core. These outputs will be used to determine the effectiveness of the ABM by providing a solution set for the ABM results to be compared.
Experimental design
The ABM was deployed in NetLogo, an agent-based simulation development platform (Wilensky 1999). For game instance, each agent was randomly assigned between zero and nine left gloves and right gloves. Each game involved three to nine agents; for each game size, ten unique games were designed, and a complete list is given in Appendix B. Due to the stochastic nature of the algorithm, each game had 50 instances run (so a total of 3500 runs were completed). Each game is executed for 100,000 time-steps to ensure convergence, if possible. In every game, each agent starts in the grand coalition. Collins and Frydenlund's algorithm was converted to execute the glove game under the same circumstances to test whether the algorithm improved upon the original. Both models were executed and compared to the results from the brute force algorithm to see if the agents had found a core partition.
The exact nature of the search space is not clear; however, the brute force algorithm considers all possible coalition structures, so optimality is ensured; that is, it guarantees that the core is found.
Results and Analysis
This section discusses the results of the simulation runs. The results focus on the comparison of the effectiveness of the two algorithms (the original Collins-Frydenlund algorithm and the new one presented in this paper). Figure 4 shows the percentage of times the original Collins-Frydenlund algorithm reached a coalition structure that is a member of the core solution set (i.e., a core partition). Figure 5 shows the results of our algorithm. A summary of the key differences is given below:
| Collins-Frydenlund Algorithm | New Algorithm | |
| Overall average convergence to core partition of simulation trial | 69% | 96% |
| Run-time speed, using Collins-Frydenlund as base | 1 | 0.5 |
The new algorithm significantly outperforms the old algorithm, approximately halving the run-time (run-time varies depending on the number of agents and computer used). Also, the new algorithm has a high rate of finding a core member as its solution. Overall, 96.1% of the games resulted in finding a core member, under the new algorithm; that is, out of the 3500 games executed, the resulting coalition structure was a member of the core 3363 times. Games with three-agents, four-agents, and seven-agents always found a core member; 488 out of 500 five-agent games found a core member; 498 of the six-agent games resulted in a core coalition structure, and 499 games played with nine-agents achieved a core result.
The only concerning result from this experiment is the eight agent games. The eight-player games, by contrast, significantly underperformed. Almost 25% of the time (122 out of 500), the eight-agent game failed to conclude with a coalition structure that could not be dominated. The details of these games are shown in Figure 6. An examination of the games that failed to reach a core solution showed that these games reached a local maximum. The algorithm used for the ABM belongs to a group known as “greedy algorithms.” These algorithms are based on achieving local optimal decisions with the hope of a global solution. However, the global solution is not actually represented or considered. Therefore, it is possible for a coalition to reach a value in which it is unwilling to reconsider given the rules for a change. That is, the game stalls at a local maximum. The following table, and resultant discussion, attempts to explain why this occurred with an example.
The first part (a) shows the initial resources for each of the eight agents. The core coalition section of the second part (b) is the set of coalition structures and their payoff values within the core. Obviously, each player would like to obtain the highest payoff. Part (b) also contains an example of a “sub-optimal” coalition structure that was achieved by the algorithm. To understand why a core partition was never achieved, we need to consider the linchpin coalition. The linchpin coalition in the core, in the game under consideration, consists of agents two, three, and four. A linchpin coalition is a coalition that occurs in all core partitions. Technically, the singleton coalition of agent seven is also a linchpin coalition, so is agent six’s singleton group. Thus, for a core partition to evolve, under our algorithm, from a given coalition structure, the linchpin coalition must be able to form. Unfortunately, in the example given above, this is not possible from the coalition structure achieved because of the limitation of the algorithm.
The coalition consisting of agents two, three, and four represents the highest payoff value that those agents could realistically achieve, and it would be expected that they would always be together. However, during the simulation, the coalition structure forms a coalition consisting of agents one and four prior to achieving the two, three, four combinations. As a group, neither agent one nor four improves their position by isolating themselves, and agents one or four do not improve their position by joining any core member coalition structure. Therefore, agents one or four are not willing to change coalitions. Also, the coalition does not benefit from merging with any other existing coalition. Hence, under our algorithm, there is no possibility that the coalition of player one and player four will change. In fact, there is no incentive for any coalition in the coalition structure to change, given the rules of the algorithm. This leads to a local maximum being reached.
The local maximum is not a member of the core and purely an artifact of the algorithm. This is due to the pair-wise nature of the algorithm; that is, at most, only two agents or coalitions are considered at any one time. For the linchpin coalition to form from the local maximum, the three agents, two, three, and four would need to be considered at the same time, within the algorithm step, which is not possible because they are in three different coalitions. Our heuristic algorithm is, in this respect, limited. However, the results demonstrate that, within a margin of error, it is possible to arrive at highly probable stable coalition structures that may or may not be in the core.
Why this phenomenon occurs regularly in games of eight players is not clear. We have chosen not to speculate here and leave this investigation to further research. This problem of being trapped in a local maximum could be overcome by using approaches like simulated annealing (Van Laarhoven & Aarts 1987) or swarm optimization (Shi 2001), which we also leave for further research as the exact nature of the search space is not clear. However, we suspect that the search space is highly non-linear.
These results demonstrate that the ABM is effective in achieving a stable coalition structure in which the players have no incentive to move to another coalition (at least under the algorithm restrictions). However, it does not identify every member of the core set; that is, not every possible core partition was reached by the algorithm. The ABM results tended to be biassed towards one core partition over all others in the core. Figure 7 shows that only 36% of the possible core partitions were achieved. Further, there is a significant decrease in the average percentage of possible coalition structures reached when the number of players increases from 6 to 7. This is most likely due to the size of the core increasing with little to no change in the number of unique coalition structures achieved. Specifically, for the ten games with six players, there are a total of 61 coalition structures in all their cores; this increases to 174 when there are seven players. However, the number of unique coalition structures reached in the simulation is 15 and 16 for 6 and 7 players, respectively.
We cannot conclude that certain coalition structures cannot be reached by our algorithm because only a limited number of runs were completed for each game, i.e., fifty per game. Further research could be conducted to see if this percentage of covered core partitions increases significantly with an increase in the number of runs. However, if it turns out to not be the case, then another interesting direction of research is to investigate the properties of the reached core partition; for example, do they hold the trembling hand property required for a unique Nash Equilibrium to be selected in normal-form game theory (Harsanyi & Selten 1988). The benefit of the ABM algorithm is the ability to, with computational ease, determine a coalition structure that is a core stable. The predetermined run-length of the simulation ensures that the resolution occurs within polynomial time. It is shown to have greater than a 99% effective rate overall, with the lowest level exceeding 93%. The limitation of the algorithm is its narrowness in the solution set and its potential to locked into a local maximum.
Discussion
Beyond the reasons behind the non-convergence of the trial runs, there are a number of other concerns with our algorithm and our experimental approach. These concerns include the focus on only one game type, one solution mechanism, the hyperparameter impact, and the applicability of the algorithm. We will discuss each of these concerns in turn.
The experiment only considers one type of hedonic game, namely, the glove game. This limited focus limits the generalisability of our claims about the algorithm. Determining the performance of our algorithm for any generic hedonic game is the next step for the research. Our intent is to apply the algorithm to randomly-generated hedonic games with strict preferences. We have already begun by creating a generic hedonic game generator and brute force solver, and succinct matrix form representation for hedonic games (Collins, Etemadidavan, & Khallouli 2020). If this new research is fruitful, we will then apply the algorithm to several standard cooperative games for insight.
Since the principles of our algorithm design are based around the core, the algorithm is not expected to perform well at finding other solution concepts unless they coincide with the core, e.g., if the core exists, the nucleolus is a member (Schmeidler 1969). However, there are some interesting phenomena that could be explored in future work, e.g., if the core does not exist, does the algorithm reach the nucleolus? This research is left to future work.
There are not any explicit hyperparameters in the algorithm; however, there are several implicit hyperparameters. For example, the ordering of the coalition searches and the number of each search type each round. We believe that understanding the effects of these hyperparameters is the next step for improving the effectiveness of the algorithm.
Finding core members in a hedonic game is useful in several disciplines and domains, including political science, ecology, and economics. The algorithm is intended to aid researchers that would like to apply the principles of cooperative game theory without its computation complexity. Additionally, using an ABM algorithm provides a simple means to incorporate different variables into the players’ utility or preference structure without the consequence of trying to solve, analytically, a more complex game.
A possible example application of our algorithm can be found in the systems engineering domain. Grigoryan & Collins (2020) suggest that combining agent-based modeling and cooperative game theory could help in determining the performance of large design programs, which include multiple interacting teams. Agent-based modeling is emerging as a new approach to modeling design teams (Grogan & de Weck 2016; Lapp, Jablokow, & McComb 2019), and our algorithm has the potential to account for informal strategic group formation, especially when dealing with Multiple Team Membership (Mortensen, Woolley, & O’Leary 2007).
Another potential application is the advancement of social simulations. For example, Epstein’s famous Sugarscape model predetermines group membership (Epstein & Axtell 1996); if our algorithm was incorporated into Sugarscape, then maybe groups could be organically developed as in Collins & Frydenlund (2018).
Conclusion
There are often comparisons made between the value of game theory and simulation in social sciences (Balzer, Brendel, & Hofmann 2001). However, agent-based simulation can be used as a complementary process to cooperative game theory. Using the game-theoretic structure and solution concepts, we designed an algorithm that produces a stable coalition structure in over 96% of the runs during our experiment, which involved the glove game with varying numbers of players. This was tested against a computational “brute-force" algorithm that determines the entire core, i.e., all stable coalition structures of a game.
While the brute-force method determines the complete core, it is computationally intractable for a large number of players; the ABM algorithm requires significantly less computational resources. However, there are limitations to the algorithm. The ABM solutions only accounted for 35% of the core partition solutions, with a sharp decrease in this number as the number of players increased. This is most likely due to the structure of the algorithm that tends towards local maxima and only focuses on pair-wise comparisons. In computer terms, our solution is a “greedy algorithm”, which maximizes its value at each step thus focuses purely on exploitation over exploration of the solution space. Our algorithm mimics traditional ABM structures in that it is a bottom-up design without centralized coordination. However, it can limit the formation of a better coalition if the individuals do not immediately prosper (as demonstrated in the eight-player game example given in the Results section). One further limitation is that the algorithm will not recognize when the core is empty. Determining whether the core of a hedonic game is empty is NP-complete (Ballester 2004). Our “greedy algorithm” will always select a value and create a coalition structure even when the core is empty.
Future work on this algorithm will examine ways to reach a greater number of coalition structures with core members. The limited coverage of core members creates a bias and limits its use. Expanding the scope of core members achievable by the algorithm will represent a significant advancement. However, understanding why the algorithm is limited to certain types of core partitions might give insight into the nature of those core partitions. Another piece of future work is to consider more general hedonic games than the glove game presented here.
Model Documentation
The agent-based model was written and simulated in NetLogo (Wilensky 1999) and is able to be run in the latest release (6.1.1). A detailed description of the model is provided in Appendix A, using the ODD protocol (Grimm et al. 2020). The different games’ descriptions, used for input into the experimental runs, are given in Appendix B. The brute force algorithm was created in Python. The original random-number-generator (RNG) seeds were not recorded at the time of the experiment. Copies of the Netlogo models used in the paper can be found at https://www.comses.net/codebases/59dda8fe-b0c0-4703-ac95-c0fc57bd48d3/releases/1.0.0/.Appendix
A. ODD Protocol
This appendix gives an ODD (Overview, Design concepts, Details) description of our ABM, specifically, the coalition formation algorithm. The ODD protocol is used for describing agent-based models (Grimm et al. 2006), and it was updated by Grimm et al. (2020). Other descriptive approaches to representing ABM exist (Bersini 2012), but the authors felt that ODD was the most appropriate for this context (Collins, Petty, Vernon-Bido, & Sherfey 2015).
Purpose and patterns
The purpose of the model is to generate coalition structures of different glove games, using a specially designed algorithm. The coalition structures are later analyzed by comparing them to core partitions of the game used. Core partitions are coalition structures where no subset of players has an incentive to form a new coalition.
Patterns: The coalition structures generated by the simulation are expected to converge to a core partition if one exists for a given game. The simulation is the model implemented over time.
Entities, state variables, and scales
The simulation model is a representation of a cooperative game theory game known as a glove game. The glove game involves players combining their endowment of gloves to create pairs, which they can sell. The focus of the game is which coalitions of players form. The main agents of this model are the players. The gloves are not considered agents since they are inert.
Agents: players
Environment: Abstract social environment where all agents are assumed to be able to communicate with each other with complete information.
State variables: All variables are associated with the players.
| Variable | Type, Range | Owner | Temporal |
| Coalition Membership | Integer, [0, # players] | Players | Dynamic |
| Left Gloves | Integer, [0, ∞) | Players | Static |
| Right Gloves | Integer, [0, ∞) | Players | Static |
Coalition Membership: It gives the index number of the coalition that that player is a member. If a player is not a member of a coalition, it is assumed to be in a singleton coalition, and an index number is still assigned.
Left Gloves: This variable indicates the number of left gloves that a player has in its initial endowment. Gloves are used to work out a coalition’s value.
Right Gloves: This variable indicates the number of right gloves that a player has in its initial endowment.
All other variables are calculated from these variables.
Scales
The temporal scales within the model are arbitrary. Each round represents an opportunity for several coalitions to be suggested to the agents and, if necessary, the updating of the coalition structure.
Process overview and scheduling
The game is played over a number of rounds. Each round represents an opportunity for the players to propose new coalitions, and, if acceptable to all potential members of that coalition, they form a new coalition. The players’ proposed coalitions are created by the algorithm.
The main loop of the simulation is as follows:
- This is the algorithm subloop. The algorithm suggests six types of coalition each turn. The coalition suggestions are discussed in the submodel section. At each step of this subloop, one of the randomly selected coalition types is suggested. First, all the computerized agents in the proposed coalitions are asked if they wish to join.
- If any agent rejects the proposed coalition, then nothing changes, and the algorithm moves on to suggest the next type of coalition.
- If all computerized agents agree to join the proposed coalition, then the proposed coalition forms, and computerized players update their membership. The algorithm moves on to suggest the next type of coalition
- All agents’ internal values are updated to reflect the new coalition situation if they have not already been done so. This includes all agents who have lost other agents because those other agents are moved to another coalition.
- Loop to next Round.
The critical point is that the algorithm will suggest several coalitions that are proposed to the agents. This algorithm is discussed in the sub-model section below. A flow diagram of the main loop is given below:
Design concepts
Basic principles
The underlying game of the model is a variation of the glove game, a classic game in cooperative game theory (Hart & Kurz 1983). The computerized agents are assumed to be utility maximizers, which is consistent with game theory standards. Their utility is the sole driver for the computerized agent’s decision-making, and complete information is assumed. The utility value that a player gets is called its payoff.
Emergence
The main expected emergent behavior is that the final coalition structure, the collection of disjoint coalitions covering all players, is a core partition. A core partition is a covering set of disjoint coalitions where no subset of players has an incentive to form a new coalition (Banerjee et al. 2001; Bogomolnaia & Jackson 2002). It is related to the core concept, introduced by Gillies (1959), but, strictly speaking, is not precisely the same. The core partition is an appropriate solution mechanism because it focuses on coalition membership instead of coalition values and imputations. A core partition is not necessarily unique for a given instance of a game nor is it guaranteed to exist. We only consider games with a non-empty core.
Adaptation
The ability of an agent to accept suggested new coalitions to join is the adaptive part of the model. The agents are only able to change to a coalition that is suggested to them by the algorithm. Further, a new coalition only forms if all potential members of that suggested coalition choose to join that coalition. This means that every agent has the veto power to stop a new coalition, which includes them, from forming. The agents will choose to join a new coalition if it increases their utility.
Note that agents might find themselves in a new coalition because other members of their coalition have decided to leave that agent’s coalition. Agents cannot stop other members from leaving; they can only stop a new coalition forming that includes them. We do not assume a complete collapse of the remaining coalitions into singleton coalitions as others have (Hart & Kurz 1983).
Objectives
The objective of all the computerized agents is to join the coalition that maximizes their utility. The agent’s utility is quantified as a reward. In the glove game, the reward of a given agent ‘a’ in coalition ‘S’ is:
| $$R(a,S)=\frac{min(\sum_{b \in S} L(b) ,\sum_{b \in S} R(b))}{|S|}$$ |
Learning
There is no learning incorporated into this model.
Prediction
There is no prediction incorporated in this model.
Sensing
There is no agent sensing incorporated in this model for the computerized agents.
Interaction
All agent interactions are mediated. That is, the agents do not directly interact with each other, but their actions do affect each other. These effects are due to the decision that they make with regard to coalition membership. If an agent leaves or joins a coalition, then the value of that coalition might change, which, in turn, affects the utility of coalition members. The value of a coalition is the number of glove pairs it can generate, and the reward of its members is this value divided by the coalition size.
Stochasticity
The only stochastic element of the model is the random determination of which coalitions are suggested by the algorithm. The algorithm generates six different suggested coalitions during this step of the model; each of the six suggested coalitions is derived by a different coalition formation approach. An example of a coalition formation approach would be combining two randomly chosen coalitions to create a suggested coalition. The different coalition approaches are discussed in the submodel section below.
In all cases, the uniform distribution is used when selecting an agent or coalition. That is, all agents or coalitions will have the same probability of selection in a given coalition formation approach.
Collectives
The model has a have focus on coalitions, which are a form of collective. The coalitions determine the payoff that each agent would get, and, in turn, this payoff drives the computerized agent decision to join any proposed coalition. The coalitions are explicitly represented in the model as a number; each agent has a coalition number assigned to it. Note that the set containing only one agent is still a coalition; it is known in cooperative game theory as the singleton coalition.
Observation
The final coalition structure is recorded after the game has completed 100,000 time-steps.
Initialization
All agents are assumed to start in a grand coalition, i.e., they start in a coalition of all agents. The number of players and their glove endowments is determined by which game is being considered. The different games being considered are shown in Appendix B. Note that a player's glove endowments do not change over the course of the game.
Input data
All variables are determined by the initial glove endowments and the algorithm mechanics. This includes the random number generator that is used for the stochastic processes, which is determined internally by the simulation programming platform.
Submodels
There are three submodels used within the model: coalition selection, coalition evaluation, and coalition updating. These three submodels control the changes to the coalition structure, which is the main output of the model.
Coalition Selection
There are six coalition suggestions (S) that are made at each round of the game. They are suggested in the order given below. A description in prose and mathematical notation is given for each. The six suggestion types are:
Join coalition
Two agents from different coalitions (U,V) in the current coalition structure (CS) are chosen randomly. The payoffs of the merged coalitions are calculated. If the payoffs improve for all members of both coalitions, a new coalition is formed, which is the merged coalition. If the grand coalition (N) has formed, this suggestion is ignored.
| $$if \; N \not\in CS: S = U\cup V s.t. U \neq V, \{U,V\} \subseteq CS$$ |
Exit coalition
An agent from a coalition whose size is greater than one, i.e., not a singleton coalition, is randomly selected. The payoff of the coalition minus the agent is calculated. If all agents in the remaining coalition improve their payoff by removing the selected agent, the agent is removed from the coalition and forms a singleton coalition.
| $$if \; \exists U\in CS \; s.t. \; |{U}| > 1: S = U\backslash\{i\}, i \in U$$ |
Create a pair coalition
Two agents are randomly selected. The payoff for the coalition containing just both agents is calculated. If the payoff of both agents is improved in this new coalition, both agents exit the current coalition in favor of the new one.
| $$S = \{i\} \cup \{j\}, \; i \neq j, \; \{i,j\} \subseteq N$$ |
Defect coalition
A randomly chosen agent selects a coalition to which he does not belong. If joining this coalition improves his payoff and the payoff of all members of the coalition, the agent defects from his current coalition and joins the new coalition.
| $$S = \{i\} \cup U, \; i \in N, \; U \in CS \cup \emptyset$$ |
Split coalition
A coalition is randomly chosen, and a random subset of agents from the coalition are selected to form a separate coalition. If the members of the new coalition improve their payoff or the coalition that remained improve their payoff, the coalition splits into the two coalitions.
| $$S_{1} = X, \; S_{2} = Y, X \cap Y = \emptyset, \; X \cup Y = U, \; U \in CS$$ |
Return to an individual coalition
An agent is randomly chosen. If that agent would be better off on their own, i.e., they prefer the singleton coalition to their current coalition; then, they leave their current coalition to form the singleton coalition. This is known as the individual rationality concept (Thomas 2003).
| $$S = \{i\}, \; i \in N$$ |
Coalition Evaluation
Each of the six suggestions is evaluated to determine if they are acceptable to members of the coalition (or either coalition is the case of a split). For each effect agent, their current payoff (utility) is compared to the payoff (utility) of the suggested coalition. If all the affected agents would experience an increase in payoff, then the suggested coalition forms. That is:
| $$if \; \forall i \in S, \; u_{i}(S) > u_{i}(C_{i}) \; then \; C_{i} := S, \; \forall i \in S$$ |
The payoff that each player gets is the number of glove pairs divided by the number of players in their coalition. That is:
| $$u_{i} (C_{i}) = \frac{min (\sum_{x \in C_{i}}L(x),\sum_{x \in C_{i}}R(x))}{|{C_{i}}|}$$ |
Coalition Updating
If a new coalitions form, then the agents of that coalition simply change their Coalition Membership number to a unique identification number assigned to the new coalition. The forming of new coalitions will affect the payoffs of many of the agents, but this information is updated when needed.
B. Glove Games
| # Players (N) | Left Gloves | Right Gloves | # Players (N) | Left Gloves | Right Gloves |
| 3 | [3, 2, 1] | [3, 3, 2] | 7 | [1, 2, 9, 6, 1, 8, 2] | [8, 6, 6, 6, 8, 3, 0] |
| 3 | [2, 2, 2] | [1, 0, 0] | 7 | [6, 4, 8, 6, 7, 6, 5] | [4, 5, 5, 8, 8, 1, 1] |
| 3 | [4, 4, 3] | [3, 4, 4] | 7 | [1, 2, 0, 3, 5, 9, 0] | [8, 5, 6, 3, 3, 5, 8] |
| 3 | [4, 3, 1] | [3, 3, 3] | 7 | [6, 9, 9, 3, 6, 7, 4] | [5, 9, 3, 4, 9, 6, 4] |
| 3 | [3, 0, 2] | [0, 0, 3] | 7 | [2, 4, 1, 1, 7, 8, 6] | [6, 4, 0, 7, 7, 0, 0] |
| 3 | [0, 0, 3] | [3, 2, 1] | 7 | [4, 6, 2, 4, 4, 2, 0] | [0, 8, 8, 5, 8, 3, 8] |
| 3 | [0, 6, 1] | [9, 9, 0] | 7 | [3, 6, 4, 9, 7, 6, 3] | [5, 9, 3, 0, 0, 4, 8] |
| 3 | [2, 5, 8] | [4, 4, 1] | 7 | [0, 9, 8, 3, 2, 3, 3] | [6, 3, 0, 8, 2, 4, 5] |
| 3 | [7, 2, 0] | [3, 6, 4] | 7 | [8, 2, 9, 5, 4, 6, 9] | [4, 6, 3, 7, 0, 2, 3] |
| 3 | [1, 0, 4] | [0, 4, 6] | 7 | [6, 2, 6, 1, 7, 0, 8] | [5, 2, 7, 7, 3, 6, 5] |
| 4 | [0, 1, 9, 6] | [4, 5, 0, 6] | 8 | [0, 2, 9, 0, 6, 2, 3, 7] | [4, 4, 4, 8, 3, 1, 5, 9] |
| 4 | [9, 8, 8, 1] | [8, 5, 1, 0] | 8 | [7, 3, 8, 4, 0, 0, 1, 5] | [6, 7, 2, 1, 5, 2, 6, 2] |
| 4 | [3, 9, 6, 0] | [7, 3, 4, 4] | 8 | [9, 4, 6, 0, 6, 2, 4, 8] | [1, 8, 4, 0, 1, 9, 7, 8] |
| 4 | [4, 1, 6, 9] | [1, 4, 7, 2] | 8 | [9, 1, 5, 5, 5, 7, 6, 5] | [4, 6, 3, 1, 9, 5, 5, 0] |
| 4 | [2, 2, 1, 2] | [8, 0, 2, 9] | 8 | [3, 6, 1, 8, 2, 6, 6, 3] | [9, 0, 2, 7, 1, 6, 6, 7] |
| 4 | [1, 6, 2, 0] | [3, 5, 8, 8] | 8 | [0, 3, 6, 0, 1, 0, 7, 8] | [0, 0, 7, 5, 4, 1, 9, 0] |
| 4 | [4, 4, 7, 8] | [9, 0, 6, 9] | 8 | [8, 2, 3, 0, 6, 6, 2, 5] | [9, 5, 4, 1, 8, 5, 3, 5] |
| 4 | [0, 0, 7, 8] | [7, 7, 9, 5] | 8 | [7, 8, 5, 5, 4, 4, 9, 5] | [0, 8, 3, 5, 5, 6, 3, 4] |
| 4 | [4, 0, 2, 0] | [7, 8, 0, 1] | 8 | [4, 0, 8, 8, 6, 9, 5, 7] | [0, 4, 7, 7, 1, 5, 5, 9] |
| 4 | [4, 3, 1, 7] | [3, 6, 0, 1] | 8 | [8, 4, 6, 1, 1, 1, 7, 7] | [6, 3, 2, 1, 2, 6, 3, 6] |
| 5 | [7, 2, 2, 7, 0] | [6, 7, 1, 8, 6] | 9 | [4, 1, 1, 1, 6, 0, 5, 1, 4] | [0, 7, 7, 4, 2, 0, 6, 0, 0] |
| 5 | [7, 7, 1, 3, 8] | [3, 5, 1, 3, 1] | 9 | [1, 9, 8, 5, 4, 4, 7, 9, 9] | [1, 3, 9, 9, 4, 9, 9, 6, 5] |
| 5 | [7, 0, 3, 5, 3] | [1, 6, 6, 2, 7] | 9 | [5, 4, 9, 0, 7, 1, 8, 0, 8] | [4, 1, 8, 6, 6, 5, 8, 1, 7] |
| 5 | [1, 7, 1, 6, 3] | [0, 8, 0, 2, 9] | 9 | [5, 4, 6, 5, 0, 3, 4, 6, 7] | [1, 2, 2, 9, 5, 1, 3, 9, 7] |
| 5 | [4, 1, 8, 7, 2] | [6, 3, 6, 1, 1] | 9 | [1, 1, 2, 5, 2, 3, 4, 2, 8] | [9, 2, 6, 7, 4, 8, 4, 2, 0] |
| 5 | [9, 2, 5, 4, 0] | [3, 6, 6, 4, 1] | 9 | [3, 2, 5, 2, 7, 8, 1, 6, 4] | [4, 7, 6, 5, 1, 3, 4, 8, 2] |
| 5 | [2, 9, 5, 4, 5] | [8, 7, 0, 7, 4] | 9 | [2, 4, 3, 4, 5, 9, 2, 3, 2] | [7, 5, 5, 8, 1, 9, 6, 5, 3] |
| 5 | [2, 2, 2, 0, 7] | [0, 1, 8, 6, 0] | 9 | [0, 4, 5, 5, 5, 1, 7, 8, 9] | [3, 8, 2, 3, 0, 3, 1, 6, 6] |
| 5 | [5, 0, 1, 0, 6] | [4, 0, 4, 7, 2] | 9 | [8, 9, 8, 4, 7, 5, 2, 8, 2] | [9, 9, 9, 5, 0, 6, 5, 2, 3] |
| 5 | [8, 0, 2, 9, 1] | [2, 8, 2, 0, 3] | 9 | [1, 4, 1, 4, 8, 0, 5, 0, 9] | [5, 0, 8, 6, 4, 2, 8, 0, 0] |
| 6 | [9, 5, 4, 6, 1, 8] | [3, 8, 9, 3, 5, 7] | |||
| 6 | [7, 9, 1, 0, 6, 5] | [3, 2, 3, 5, 1, 8] | |||
| 6 | [9, 6, 7, 8, 5, 8] | [0, 9, 7, 2, 0, 1] | |||
| 6 | [8, 9, 3, 5, 4, 0] | [4, 1, 8, 0, 5, 1] | |||
| 6 | [3, 2, 4, 2, 3, 7] | [4, 0, 8, 7, 2, 7] | |||
| 6 | [1, 0, 0, 3, 8, 7] | [6, 8, 1, 3, 3, 8] | |||
| 6 | [4, 1, 1, 3, 8, 6] | [4, 8, 1, 1, 5, 9] | |||
| 6 | [9, 2, 4, 4, 4, 7] | [8, 8, 1, 1, 3, 0] | |||
| 6 | [8, 9, 5, 2, 1, 4] | [4, 3, 1, 3, 8, 1] | |||
| 6 | [5, 2, 5, 0, 9, 0] | [6, 3, 2, 0, 3, 7] |
References
ABDOLLAHIAN, M., Yang, Z., & Nelson, H. (2013). Techno-social energy infrastructure siting: sustainable energy modeling programming (SEMPro). Journal of Artificial Societies and Social Simulation, 16(3), 6: https://www.jasss.org/16/3/6.html. [doi:10.18564/jasss.2199]
AXTELL, R. (2000). Why agents?: on the varied motivations for agent computing in the social sciences. Report available at: https://www.brookings.edu/research/why-agents-on-the-varied-motivations-for-agent-computing-in-the-social-sciences.
AZIZ, H. (2013). Stable marriage and roommate problems with individual-based stability. Paper presented at the Proceedings of the 2013 international conference on Autonomous agents and multi-agent systems, St. Paul, MN, USA.
AZIZ, H., & Savani, R. (2016). 'Hedonic Games.' In F. Brandt, V. Conitzer, U. Endriss, J. Lang, & A. D. Procaccia (Eds.), Handbook of Computional Social Choice (pp. 356-376). New York, NY: Cambridge University Press. [doi:10.1017/cbo9781107446984.016]
BALLESTER, C. (2004). NP-completeness in hedonic games. Games and Economic Behavior, 49(1), 1-30. [doi:10.1016/j.geb.2003.10.003]
BALZER, W., Brendel, K. R., & Hofmann, S. (2001). Bad arguments in the comparison of game theory and simulation in social studies. Journal of Artificial Societies and Social Simulation, 4(2), 1: https://www.jasss.org/4/2/1.html.
BANERJEE, S., Konishi, H., & Sönmez, T. (2001). Core in a simple coalition formation game. Social Choice and Welfare, 18(1), 135-153. [doi:10.1007/s003550000067]
BELL, E. T. (1938). The iterated exponential integers. Annals of Mathematics, 539-557.
BERSINI, H. (2012). UML for ABM. Journal of Artificial Societies and Social Simulation, 15(1), 9: https://www.jasss.org/15/1/9.html. [doi:10.18564/jasss.1897]
BOGOMOLNAIA, A., & Jackson, M. O. (2002). The stability of hedonic coalition structures. Games and Economic Behavior, 38(2), 201-230. [doi:10.1006/game.2001.0877]
CHAKRAVARTY, S. R., Mitra, M., & Sarkar, P. (2015). A Course on Cooperative Game Theory: Cambridge, MA: Cambridge University Press.
CHALKIADAKIS, G., Elkind, E., & Wooldridge, M. (2011a). Computational aspects of cooperative game theory. Synthesis Lectures on Artificial Intelligence and Machine Learning, 5(6), 1-168. [doi:10.2200/s00355ed1v01y201107aim016]
CHALKIADAKIS, G., Elkind, E., & Wooldridge, M. (2011b). Computational Aspects of Cooperative Game Theory (Vol. 5). London: Morgan & Claypool.
COLLINS, A. J. (2017, October). Strategically Forming Groups in the El Farol Bar Problem. In Proceedings of the 2017 International Conference of The Computational Social Science Society of the Americas (pp. 1-6). [doi:10.1145/3145574.3145575]
COLLINS, A. J. (2019). 'Strategic group formation in the El Farol bar problem.' In T. Carmichael & A. J. Collins (Eds.), Complex Adaptive Systems: Views from the Physical, Natural, and Social Sciences (pp. 199-212). Cham, Switzerland: Springer. [doi:10.1007/978-3-030-20309-2_9]
COLLINS, A. J. (2020). Heuristic Algorithm for Generating Strategic Coalition Structures. Version 1.0.0. Retrieved from https://www.comses.net/codebases/59dda8fe-b0c0-4703-ac95-c0fc57bd48d3/releases/1.0.0/.
COLLINS, A. J., Etemadidavan, S., & Khallouli, W. (2020). Generating empirical core size distributions of hedonic games using a Monte Carlo Method. Retrieved from: https://arxiv.org/abs/2007.12127.
COLLINS, A. J., & Frydenlund, E. (2016a). Agent-Based Modeling and Strategic Group Formation: A Refugee Case Study. Paper presented at the Proceedings of the 2016 Winter Simulation Conference, Arlington, VA, USA. [doi:10.1109/wsc.2016.7822184]
COLLINS, A. J., & Frydenlund, E. (2016b). Strategic Group Formation in Agent-based Simulation. Paper presented at the 2016 Spring Simulation Multi-conference, Pasadena, CA.
COLLINS, A. J., & Frydenlund, E. (2018). Strategic Group Formation in Agent-based Simulation. Simulation, 94(3), 179-193. [doi:10.1177/0037549717732408]
COLLINS, A. J., Petty, M., Vernon-Bido, D., & Sherfey, S. (2015). Call to Arms: Standards for Agent-based Modeling and Simulation. Journal of Artificial Societies and Social Simulation, 18(3), 12: https://www.jasss.org/18/3/12.html. [doi:10.18564/jasss.2838]
DE MARCHI, S., & Page, S. E. (2008). 'Agent‐Based Modeling.' In J. M. Box-Steffensmeier, H. E. Brady & D. Collier (Eds.), The Oxford Handbook of Political Methodology. Oxford: Oxford University Press. [doi:10.1093/oxfordhb/9780199286546.003.0004]
DJOKIĆ, B., Miyakawa, M., Sekiguchi, S., Semba, I., & Stojmenović, I. (1989). Short Note: A Fast Iterative Algorithm for Generating Set Partitions. The Computer Journal, 32(3), 281-282.
DREZE, J. H., & Greenberg, J. (1980). Hedonic coalitions: Optimality and stability. Econometrica: Journal of the Econometric Society, 48(4), 987-1003. [doi:10.2307/1912943]
EATWELL, J., Milgate, M., & Newman, P. (1987). The New Palgrave: Game Theory. London: Macmillan Press.
EPSTEIN, J. M., & Axtell, R. (1997). Artificial societies and generative social science. Artificial Life and Robotics, 1(1), 33-34. [doi:10.1007/bf02471109]
EPSTEIN, J. M., & Axtell, R. L. (1996). Growing Artificial Societies: Social Science from the Bottom Up (First Edition ed.). Cambrydge, MA: The MIT Press. [doi:10.7551/mitpress/3374.001.0001]
FAIGLE, U., Kern, W., Fekete, S. P., & Hochstättler, W. (1997). On the complexity of testing membership in the core of min-cost spanning tree games. International Journal of Game Theory, 26(3), 361-366. [doi:10.1007/bf01263277]
FLOOD, M. M. (1952). Some Experimental Games (RM-789). Retrieved from Santa Monica, CA.: https://www.rand.org/pubs/research_memoranda/RM789-1.html.
GALE, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9-15. [doi:10.2307/2312726]
GILBERT, N. (2008). Agent-Based Models. Thousand Oaks, CA: Sage Publications, Inc.
GILLIES, D. B. (1959). Solutions to general non-zero-sum games. Contributions to the Theory of Games, 4(40), 47-85. [doi:10.1515/9781400882168-005]
GORE, R. J., Lynch, C. J., & Kavak, H. (2016). Applying statistical debugging for enhanced trace validation of agent-based models. Simulation, 0037549716659707. [doi:10.1177/0037549716659707]
GRIGORYAN, G., & Collins, A. J. (2020). Game Theory for Systems Engineering: A Survey. International Journal of System of Systems Engineering, forthcoming.
GRIMM, V., Berger, U., Bastiansen, F., Eliassen, S., Ginot, V., Giske, J., Goss-Custard, J., Grand, T., Heinz, S. K., Huse, G., Huth, A., Jepsen, J. U., Jørgensen, C., Mooij, W. M., Müller, B., Pe’er, G., Piou, C., Railsback, S. F., Robbins, A. M., Robbins, M. M., Rossmanith, E., Rüger, N., Strand, E., Souissi, S., Stillman, R. A., Vabø, R., Visser, U. & DeAngelis, D. L. (2006). A standard protocol for describing individual-based and agent-based models. Ecological Modelling, 198(1-2), 115-126. [doi:10.1016/j.ecolmodel.2006.04.023]
GRIMM, V., Railsback, S. F., Vincenot, C. E., Berger, U., Gallagher, C., DeAngelis, D. L., Groeneveld, J., Edmonds, B., Ge, J., Giske, J., Johnston, A. S. A., Milles, A., Nabe-Nielsen, A., Polhill, J. G., Radchuk, V., Rohwäder, M. S., Stillman, R. A., Thiele, J. C. & Ayllon, D. (2020). The ODD Protocol for Describing Agent-Based and Other Simulation Models: A Second Update to Improve Clarity, Replication, and Structural Realism. Journal of Artificial Societies and Social Simulation, 23(2), 7: https://www.jasss.org/23/2/7.html. [doi:10.18564/jasss.4259]
GROGAN, P. T., & de Weck, O. L. (2016). Collaboration and complexity: an experiment on the effect of multi-actor coupled design. Research in Engineering Design, 27(3), 221-235. [doi:10.1007/s00163-016-0214-7]
HARSANYI, J. C., & Selten, R. (1988). A General Theory of Equilibrium Selection in Games. London: MIT Press.
HART, S. (1985). Nontransferable utility games and markets: some examples and the Harsanyi solution. Econometrica, 53(6), 1445-1450. [doi:10.2307/1913218]
HART, S., & Kurz, M. (1983). Endogenous formation of coalitions. Econometrica: Journal of the Econometric Society, 51(4), 1047-1064. [doi:10.2307/1912051]
IEHLÉ, V. (2007). The core-partition of a hedonic game. Mathematical Social Sciences, 54(2), 176-185. [doi:10.1016/j.mathsocsci.2007.05.007]
JANOVSKY, P., & DeLoach, S. A. (2016). Multi-agent simulation framework for large-scale coalition formation. Paper presented at the 2016 IEEE/WIC/ACM International Conference on Web Intelligence (WI). [doi:10.1109/wi.2016.0055]
KLÜGL, F. (2008). A validation methodology for agent-based simulations. Paper presented at the Proceedings of the 2008 ACM symposium on Applied computing. [doi:10.1145/1363686.1363696]
LAPP, S., Jablokow, K., & McComb, C. (2019). KABOOM: an agent-based model for simulating cognitive style in team problem solving. Design Science, 5(E13), 1-34. [doi:10.1017/dsj.2019.12]
MORTENSEN, M., Woolley, A. W., & O’Leary, M. (2007). Conditions enabling effective multiple team membership Virtuality and Virtualization (pp. 215-228). Berlin Heidelberg: Springer. [doi:10.1007/978-0-387-73025-7_16]
MURNIGHAN, J. K., & Roth, A. E. (1977). The effects of communication and information availability in an experimental study of a three-person game. Management Science, 23(12), 1336-1348. [doi:10.1287/mnsc.23.12.1336]
MURNIGHAN, J. K., & Roth, A. E. (1980). Effects of group size and communication availability on coalition bargaining in a veto game. Journal of Personality and Social Psychology, 39(1), 92. [doi:10.1037/0022-3514.39.1.92]
MUSTAFEE, N., Powell, J., Brailsford, S. C., Diallo, S., Padilla, J., & Tolk, A. (2015). Hybrid simulation studies and hybrid simulation systems: definitions, challenges, and benefits. Paper presented at the Proceedings of the 2015 Winter Simulation Conference, Huntington Beach, CA. [doi:10.1109/wsc.2015.7408287]
MYERSON, R. B. (2013). Game Theory. Cambridge, MA: Harvard University Press.
OHDAIRA, T., & Terano, T. (2009). Cooperation in the Prisoner's dilemma game based on the second-best decision. Journal of Artificial Societies and Social Simulation, 12(4), 7: https://www.jasss.org/12/4/7.html.
PELEG, B., & Sudhölter, P. (2007). Introduction to theTheory of Cooperative Games (Vol. 34). Berlin Heidelberg: Springer Science & Business Media.
RAHWAN, T., Ramchurn, S. D., Jennings, N. R., & Giovannucci, A. (2009). An anytime algorithm for optimal coalition structure generation. Journal of Artificial Intelligence Research, 34, 521-567. [doi:10.1613/jair.2695]
ROTHKOPF, M. H., Pekeč, A., & Harstad, R. M. (1998). Computationally manageable combinational auctions. Management Science, 44(8), 1131-1147. [doi:10.1287/mnsc.44.8.1131]
SCHMEIDLER, D. (1969). The nucleolus of a characteristic function game. SIAM Journal on applied mathematics, 17(6), 1163-1170. [doi:10.1137/0117107]
SHAPLEY, L. (1953). 'A Value of n-person Games.' In H. W. Kuhn & A. W. Tucker (Eds.), Contributions to the Theory of Games (Vol. II, pp. 307-317). Princeton: Princeton University Press.
SHI, Y. (2001). Particle swarm optimization: developments, applications and resources. Paper presented at the evolutionary computation, 2001. Proceedings of the 2001 Congress on.
SIE, R., Sloep, P. B., & Bitter-Rijpkema, M. (2014). If We Work Together, I Will Have Greater Power: Coalitions in Networked Innovation. Journal of Artificial Societies and Social Simulation, 17(1), 3: https://www.jasss.org/17/1/3.html. [doi:10.18564/jasss.2410]
SUNG, S. C., & Dimitrov, D. (2007). On core membership testing for hedonic coalition formation games. Operations Research Letters, 35(2), 155-158. [doi:10.1016/j.orl.2006.03.011]
THOMAS, L. C. (2003). Games, Theory and Applications. Mineola, NY: Dover Publications.
VAN LAARHOVEN, P. J., & Aarts, E. H. (1987). Simulated Annealing. Berlin Heidelberg: Springer.
VON NEUMANN, J., & Morgenstern, O. (1947). Theory of Games and Economic Behavior, 2nd rev. Princeton, NJ: Princeton University Press.
WILENSKY, U. (1999). NetLogo. Evanston, IL: center for connected learning and computer-based modeling, Northwestern University.
WINDRUM, P., Fagiolo, G., & Moneta, A. (2007). Empirical Validation of Agent-Based Models: Alternatives and Prospects. Journal of Artificial Societies and Social Simulation, 10(2), 8: https://www.jasss.org/10/2/8.html.
XIANG, X., Kennedy, R., Madey, G., & Cabaniss, S. (2005). Verification and validation of agent-based scientific simulation models. Paper presented at the Agent-directed simulation conference.
YEH, D. Y. (1986). A dynamic programming approach to the complete set partitioning problem. BIT Numerical Mathematics, 26(4), 467-474.