ArmA 3 Billeting as a Coalition Formation Game Pearson Garner1,* , Aaron Lin1,* , Ruby Harris1,* , Brent Harrison1 and Judy Goldsmith1,* 1 University of Kentucky, 329 Rose St. Lexington KY 40506, United States of America Abstract The video game Armed Assault 3 (often shortened to ArmA 3) is part of a popular series of online military simulation role-playing games by Bohemia Interactive. Many players take part in cooperative organizations, with larger communities hosting 50–100 players simultaneously on dedicated servers. Prior to hosting a game session, players are assigned to roles corresponding to positions in a rank-based tree structure. Assigning players (“billeting") to the game-specific hierarchy happens before play, but billeting can take enormous effort and time to satisfy individual players’ preferences over roles, levels of the command hierarchy, and individuals with whom they will interact. A stable assignment of players to their teams is integral both for their enjoyment of the game and the overall effectiveness of the team. Inspired by the existing coalition formation literature, we re-cast that pre-play activity as a coalition formation game and explore how various coalition formation algorithms perform on the billeting process using synthetic data. Keywords Coalition Formation, Team Assignment, Stable Teams 1. Introduction and about other games with similar billeting/assignment problems. In Section 3 we provide an overview of both The 2013 video game Armed Assault 3 (usually shortened to ArmA 3 and the billeting process. We then describe the ArmA 3) by Bohemia Interactive is a realistic military simula- coalition formation algorithms that we will investigate in tion game, or MilSim, which gives players an online sandbox this paper and outline our experiments and results. to role-play in military settings. Realistic MilSim communi- ties in ArmA 3 have large organizational structures which emulate real-life chain of command, but these communities 2. Related Works often have difficulty assigning players to different in-game roles. This process, called billeting, is especially difficult in We observe billeting problems arising in large-scale online large MilSim communities because they, especially in ArmA community games, most notably in roleplay settings which 3, often have hundreds of members, with anywhere from 50 require individuals to be divided into teams with a clear to 100 people trying to play in a cooperative game instance structural hierarchy. One example case is for the game all at once. The first author reports that it takes several days EveOnline (https://www.eveonline.com/), in which players for billeting, and that process often leads to acrimonious and their ships are assigned to fleet formations based on the disputes, in part driven by interpersonal tensions between intrinsic rank and skills of their in-game character. Outside players who do or do not wish to interact with each other of strictly video games, we note billeting problems being in fire teams or in adjacent roles in the chain of command. relevant for many other large-community structures, such In order to form stable teams, i.e., teams where no players as coordinating text-based roleplay communities. have incentive to change their assignment, we define this A coalition formation game is a cooperative multi-game more formally in the section on coalition formation games. agent game. The input is a set of agents and their prefer- community leadership has to spend a lot of time and energy ences or utilities over coalitions they might be assigned to; on team formation, often with mixed success. Given the the output is a partition of agents into coalitions. The com- time and effort required to find these solutions, utilizing putational goal of a coalition game problem might be to find algorithmic methods for finding stable teams would greatly an optimal or near-optimal partition, as we do here, or to reduce the burden on community leadership. find a stable partition for some notion of stability, or to de- In this paper, we explore how algorithms for forming sta- termine if such a stable partition exists. We are particularly ble coalitions in coalition formation games can be applied interested, here, in hedonic coalition formation games[1, 2], to team formation in ArmA 3. Using stability as a measure also known as hedonic games, where agents’ preferences or of goodness or utility, we examine a number of coalition for- utilities are defined only over each coalition they might be mation algorithms and evaluate them based on the overall assigned to. If we interpret the billeting problem for ArmA utility (stability) of the billets that they generate. Specifi- 3 as the problem of finding a single (or “grand") coalition cally, we explore how various simulated annealing and local with optimal total utility, we do not consider the effects of search methods can be used to billet a set of synthetic ArmA other teams’ billeting, so we are in the hedonic setting. 3 users based on a set of known preferences. The remainder of the paper is organized as follows. In Sec- 3. ArmA 3 tion 2 we describe related work about coalition formation, In this section we describe ArmA 3, and mention the ways 11th Experimental Artificial Intelligence in Games Workshop, November in which we codify rules that are left to individual gaming 19, 2024, Lexington, Kentucky, USA. communities. * Corresponding author: Pearson Garner, Aaron Lin, and Judy Goldsmith $ pearson.neal.garner@gmail.com (P. Garner); ayli22@uky.edu (A. Lin); roo.harris@proton.me (R. Harris); brent.harrison@uky.edu 3.1. Overview (B. Harrison); goldsmit@cs.uky.edu (J. Goldsmith)  0009-0007-0375-1650 (P. Garner); 0009-0009-3317-4545 (A. Lin); ArmA 3 is a highly diverse community with many different 0009-0006-0915-8084 (R. Harris); 0000-0002-9421-8566 (B. Harrison); play-styles, game-modes, and levels of realism. For the pur- 0000-0002-9421-8566 (J. Goldsmith) pose of this paper, we construct a coalition formation game © 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR ceur-ws.org Workshop ISSN 1613-0073 Proceedings for a “realism"-focused MilSim community.1 Like many A Squad is the next level above a Fireteam. Squads are popular communities, we will primarily base our coalition composed of a Squad Leader and exactly 2 distinct Fireteams. game’s structure off of North American Treaty Organization The Squad Leader must have a higher minimum rank and (NATO) protocol and procedure. additional leadership qualifications. There are no formal rules from the game developers, as A Platoon is the next level above a Squad. Platoons are each community gets to choose their own organizational led by a Platoon Leader and a Platoon Sergeant, the latter rules. Most realistic ArmA 3 units attempt to follow the acts as the second-in-command to the former. Both must standard NATO ORBAT that is used by modern Western mil- have additional rank and training qualifications. Platoons itaries. (https://web.archive.org/web/20070826233341/http: are themselves composed of anywhere from 1 to 4 Squads, //\orbat.com/site/toe/toe/usa/platoontoe.html) We therefore offering some flexibility to the command structure. mimic this structure as well. At the highest level is the Company, which consists of the Company Leader, and they are in charge of all Platoons 3.2. Billeting under their command. In practice, there is little reason to go higher than this as ArmA 3 servers usually do not The formation of an instance of an ArmA 3 mission (hence- have enough player slots to necessitate larger structures, forth for simplicity just “mission") first requires each player but actual NATO unit organization can be expanded much to be assigned a role for that mission’s “billet" before the further if needed. mission is hosted at some fixed time. The role a player is as- signed is based on several factors, including but not limited 3.4. Ranks to: A player agent will have a rank that represents their time, 1. Player preferences towards working with certain experience, and recognition of merit within a community. individuals. The ranks that we use in this paper are based on the list 2. The player’s rank in the unit. of ranks used by the United States Army. Each role within 3. The player’s qualifications earned from training. the hierarchy tree has a minimum rank requirement, and The billet is constructed as a tree of players, where each players cannot be assigned a role outside their rank. Play- player node has command and authority over every player ers usually are assigned to the highest-ranking role that in each child branch, and has most direct authority over they are qualified for in order that individuals best qualified the immediate children to the player. The tree is composed to lead may do so. However, players of a higher rank can of different nested coalitions, in which players are part of choose to move down the hierarchy tree. This is an action these coalitions depending on where in the tree they are we call self-demotion, and happens in some uncommon cir- located. For the purpose of this research, we ignore any cumstances to fill in gaps lower in the tree, or to fulfill a attached “support companies" with their own parallel but player’s preferences if they would rather not lead for the separate command, and instead focus on the main tree of day. standard infantry. We do this because this main tree is the largest and most complex. 3.5. Qualifications Each role within the hierarchy tree has its own set of skill or 3.3. Tree Structure training qualifications that a player must have in order to be The billet hierarchy tree is composed of the following nested assigned that role. For example, an Autorifleman must have coalitions: the training necessary to use their machine gun, and a Team A Fireteam is a small team of infantrymen (players) and Leader must have some basic leadership training. These is the lowest in the hierarchy at the leaf nodes of the tree. qualifications are tracked for every player, and a player A Fireteam is a strict unit composition that must adhere to must possess all of the prerequisite qualifications in order the following criteria to be considered valid: to be assigned to a role. These qualifications are Boolean, as players will either have a given qualification or they will 1. Must be made of exactly 4 players.2 not. 2. The Fireteam consists of four roles, of which each Many ArmA 3 realistic MilSim communities have a large member must have the proper qualifications to be number of available qualifications to train for, many of assigned the role. These roles are: which require prerequisite qualifications themselves. In a) Team Leader (TL) general, the leadership of many ArmA communities elect to b) Autorifleman (AR) have simple skill trees with no more than one prerequisite c) Grenadier (GRN) per qualification whenever possible. This is to keep progres- d) Rifleman (RFL) sion simple for players to understand and for leadership to 3. The Team Leader is a special role, and requires play- keep track of. Our algorithms allow for the dynamic creation ers to have a high enough rank (e.g. Corporal or of a qualification tree with any number of prerequisites to Sergeant) in order to occupy. explore more complicated assignments. Gaming-based or game-inspired coalition formation games has been explored. We mention a few here, from 1 The official ArmA 3 community website, units.arma3.com, allows com- which AACFGs take elements. The first are Anchored Team munities to identify with the tags of “realism", “semi-realism," and Formation Games [3, 4], which (a) assigns players to coali- “relaxed." The latter of these two are much less likely to have a rigid tions to play TTRPGs, and (b) also makes use of roles (GM billet structure, so we will not consider them for this paper. and players). More relevant, perhaps, are Role Based Hedo- 2 In practice, team sizes can vary to account for different organizations or numbers of players, but for this paper we are only interested in the nic Games [5, 6], introduced to model preferences of League case where team sizes and roles are fixed. of Legends players, in which players express preferences over their own champion (role) and the champions that We now formally define AACFGs. Informally, an instance make up the team. In addition, Tiered Coalition Formation consists of the baseline preferences agents have over each Games (TCFGs) [7], introduced to model the stratification other, and the factors that define agents’ utilities for given of Pokémon by the fan site Smogon, has some of the flavor assignments (or billets — we use the terms interchangeably), of the role hierarchy of AACFGs. We later give a formal namely the structure of the hierarchy, or tree of roles. We definition of TCFGs and of the related notion of socially also include the requirements of each role, namely qualifi- conscious stability, as we build on that stability notion. cations. In summary: each player has a maximum rank they can be assigned, and a set of qualifications that enable particular Definition 2. An instance of an ArmA Coalition Forma- billets. Each player has utilities for each other player, though tion Game (AACFG) consists of the inter-player utility within a given billet is scaled so that • a preference matrix 𝑃 that implicitly defines the num- it decreases geometrically with the branch distance in the ber of players; hierarchy tree. Players on separate branches do not contribute • an array of qualifications for those players; to each other’s utility. • a discount 1/𝑠 for utilities as a function of distance in Armed Assault Coalition Formation Games (AACFGs) are the assignment tree, or billet; similar to Anchored Team Formation Games (ATFGs), which were designed to capture table formation for table-top role- • the structure of the assignment tree (depth of the tree, playing games [3, 4]. AACFGs and ATFGs are both exten- qualifications for each role). sions of Additvely Separable Hedonic Games, in which each We are interested in assignments, or billets, for AACFGs. agent has utility assigned to every other agent. The agent’s total utility for a coalition is the sum of the assigned utilities Definition 3. A billet is a mapping from players to roles. A to each other member of that coalition. valid billet is one in which the assigned players each have the qualifications necessary for their assigned role. Definition 1. [1] Additively Separable Hedonic Games The utility for player 𝑎 for billet 𝐵 depends on 𝑎’s utility for (ASHG) are a class of hedonic game where each player 𝑖 ∈ 𝑁 its descendants, ancestors, and (if 𝑎 is assigned to a Fireteam) assigns values to each player 𝑗 ∈ 𝑁 , expressed as 𝑣𝑖 (𝑗); for all those in its Fireteam. We define 𝐷𝐵 (𝑎) to be those players, 𝑖, 𝑣𝑖 (𝑖) is 0. The utility a player 𝑎𝑖 derives from each ∑︀ coalition and 𝑆 ∈ 𝒩𝑖 such that 𝑖 ∈ 𝑆 is defined as 𝑢𝑖 (𝑆) = 𝑗∈𝑆 𝑣𝑖 (𝑗). ∑︁ 𝑢𝑎 (𝐵) = (𝐵)𝑥𝑎 (𝑐). 𝑐∈𝐷𝑎 An assignment of agents (or here, players) to coalitions is stable if there is no agent or agents that would have higher We define 𝑢(𝐵) = Σ𝑎 𝑢𝑎 (𝐵). utility in coalition(s) other than those assigned. Notions of stability in coalition formation games [8] vary in the We borrow heavily from the work on Tiered Coalition number of agents that can move, which agents’ utilities are Formation Games to define our notion of stability. considered, and whether those utilities have to be strictly Definition 4. [7] A tiered coalition formation game improved or merely non-decreasing. The two most common (TCFG) is a coalition formation game (𝑁, ⪰), where 𝑁 = notions of stability are Nash and core stability. The simplest {𝑎1 , 𝑎2 , ..., 𝑎𝑛 }; an outcome, or tier list, is a totally or- notion, Nash Stability [? ], holds if no single agent can dered spanning set of disjoint coalitions [𝑇1 , 𝑇2 , ..., 𝑇𝑘 ]; increase its utility by joining a different coalition than the Seen(𝑎𝑖 , 𝑇 ) for tier list 𝑇 denotes the set of all agents that one to which it is assigned. An assignment is core stable [1] are in the same tier as 𝑎𝑖 or are in a lower (prior) tier; and the if no group of agents can create a new coalition of their own preferences for each agent 𝑎𝑖 in each possible tier list 𝑇 are such that each agent in the new coalition improves their determined solely by the set of agents 𝑎𝑖 “sees" in 𝑇 [7]. utility. Note that Nash stability is not meaningful in games in Note that TCFGs are not hedonic, in that an agent affected which coalitions have fixed sizes, or have structures driven by the assignment of all seen agents, even those not in its by fixed positions and roles; in such settings, an individual own tier. Thus, when an agent moves from one tier to agent typically cannot deviate to or from a coalition with- another, it potentially affects the utilities of agents in any out invalidating that coalition. Similarly, core stability has intervening tiers. limited usefulness for settings with fixed positions and roles, We are interested in billets that are not only valid, but as there may be valid core deviations under the definition stable. We consider two notions of stability based on swaps. of core stability which would cause agents outside of those deviations to no longer belong to a legitimate coalition. A re- Definition 5. Given an instance 𝐼 of AACFG and valid billet lated game, Roles and Teams Hedonic Games, models League 𝐵 for 𝐼, 𝐵 is swap stable if there is no pair of agents 𝑎, 𝑏 that of Legends teams of fixed size and considers swaps of agents are assigned to different roles by 𝐵, such that swapping 𝑎 and between coalitions as the driver of stability [5, 9]. 𝑏 leaves the billet valid, and improves the utilities for both. Swap exchange stability has a rich history, well surveyed The notion of swap stability is appealing, but may not be in [10], for instance. We mention a few additional appli- achievable. cations: kidney exchanges [11] (there is a huge literature there), in which biologically incompatible donor-recipient Lemma 1. Not all instances of AACFGs have swap stable pairs are placed in a cycle or chain3 where donors are billets. swapped so recipients receive compatible kidneys; marriage markets where mates are similarly exchanged, perhaps in Proof. We define an instance 𝐼 = 𝑃, 𝑄, 𝑠 of an AACFG, sequence [12]; other matching markets [13]; roommate as- and a valid billet 𝐵. Let all players have all qualifications signment problems [14, 12, 15]. for Fireteam roles, and let there be sufficient other qualified players to have a valid billet. Let 𝑎 and 𝑏 have no qualifica- 3 Kidney exchange chains start with a kidney donor who has died. tions for higher ranks. We define the preference matrix 𝑃 by 𝑃 [𝑎, 𝑏] = 5 and 𝑃 [𝑏, 𝑎] = −5. For all other players 𝑥, 4. Heuristic Algorithms 𝑃 [𝑥, 𝑎] = 1 and 𝑃 [𝑥, 𝑏] = −1, and otherwise 𝑃 [𝑥, 𝑦] = 0. Thus, 𝑎 wants to be in a Fireteam with 𝑏, but 𝑏 does not want We used local search and simulated annealing. Note that to be in a Fireteam with 𝑎. If 𝑎 and 𝑏 are billeted in the same local search, also know as “hill climbing" [18], can only take Fireteam, and any player billeted in another Fireteam (with improving moves, which tends to get stuck in local, non- utility 0) can improve their utility by swapping with 𝑏. If 𝑎 global optima. Simulated annealing allows for occasional and 𝑏 are in separate Fireteams, any player in 𝑏’s Fireteam random “jumps," which have the possibility of jumping away (with utility -1) can improve their utility by swapping with 𝑎. from sub-optimal hills. Given that the range of values of Thus, 𝑎 will chase 𝑏 and 𝑏 will run away, ad infinitum. pairwise utilities is polynomially bounded in the number of agents, there is a polynomial upper bound on the utility of The problem that arises in our counterexample is that an assignment. Note that, for SCSS, each local improvement 𝑎 is allowed to join 𝑏’s Fireteam, to the detriment of 𝑏’s from the local search strictly increases the social welfare utility. There are a variety of notions of stability that extend (total utility). Furthermore, finding an improving swap, if consideration of utility beyond that of the blocking agents. one exists, takes polynomial time. Thus, each run of local To help us think about this, we define a notion of stability search has a polynomial time bound. For simulated anneal- particular to TCFGs. ing, we used a pre-set cut-off to deal with the possibility of super-long runs. Definition 6. A socially consciously stable tier list is a tier In the simulated annealing, we used the parameter 𝑘 list 𝑇 in which there exists no agent 𝑎𝑖 that can improve its to determine the probability a random swap is accepted utility by moving to a new position in the tier list without weighted by a temperature value 𝑇 . 𝑇 decays from 1 to .001 decreasing the total utility of all other agents [16, 17]. by 𝑇 ′ = 𝑇 /1.001. This probability is given by We can understand socially conscious stability (SCS) to 𝑢(𝐵 ′ )−𝑢(𝐵) require permission from all affected agents before an agent 𝑃 (𝑢(𝐵), 𝑢(𝐵 ′ ), 𝑇 ) = 𝑒 𝑘*𝑇 . can move. It generalizes the notions of contractual stability Note that the problem of finding valid billets, ones where (which requires that an agent leaving a coalition must leave all agents have the qualifications for their assigned roles, is behind other agents whose utility is not lowered — “per- nontrivial, though we can easily find one such billet. For the mission to leave") and individual stability (which requires local search and simulated annealing algorithms, we start that an agent joining a coalition cannot lower the utility of all runs from the same initial assignment. The simulated any agent in that coalition — “permission to enter") [2]. We annealing variants use random number generators, so each define a notion of stability that is similar to contractually run may find a different stable assignment. However, local individual stability, but is defined in terms of agents trading search is deterministic, thus it was only run once. coalitions, or swapping. Definition 7. An assignment 𝐵 is Socially Conscious Swap 5. Experiments Stable (SCSS) if there is no pair of agents 𝑎 and 𝑏 assigned to roles 𝐵(𝑎), 𝐵(𝑏) such that swapping them creates a new 5.1. Generator assignment 𝐵 ′ with ′ The generator consists of 𝑛 player structures, each with • 𝑢𝐵 𝐵 𝑎 > 𝑢𝑎 ; their own rank stored as a uniformly-random integer using 𝐵′ • 𝑢𝑏 > 𝑢 𝐵𝑏 ; the std::rand() function. For the skill qualifications of each • ∀𝑥 ∈/ {𝑎, 𝑏} 𝑢𝐵 ′ 𝐵 𝑥 ≥ 𝑢𝑥 . player, each agent runs a series of coinflips against a global list of qualifications. Each qualification in the list requires the agent to possess all of the prior qualifications. We kept 3.6. Computational Complexity of AACFGs the size of the qualifications small, allowing each agent to We note that AACFGs generalize Additively Separable He- hold anywhere from zero to five qualifications. donic Games with Fixed-Size Coalitions (AS-HGFSCs) [10]. In particular, given an AS-HGFSCs, we can construct an 5.2. Runs AACFG instance by adding players and assigning the unique roles above the Fireteam level, while treating the input Twenty 50-player structures were generated. The discount agents from the AS-HGPSC instance as players fully quali- value 𝑠 is set to 2 and the utility one player has for another fied for Fireteams. (Note that we need to loosen our restric- is in the interval [0,1]. For each instance, we checked if a tion of Fireteams having exactly four members.) valid billet exists by iteratively assigning the highest ranked From this observation, we get all of the hardness results player to the highest remaining position, irrespective of for AA-HGFSCs and some inspiration for algorithms. For inter-player preferences. From this initial billet we ran the instance, in what Bilo, et al. [10] call SSS (strictly swap deterministic local search, then 500 iterations of simulated stability) and what we call SCSS, there is always an SCSS annealing with 𝑘 = 10 and simulated annealing with 𝑘 = 1. billet. For our work, this assumes that there is some valid billet. In the current formulation, it is easy to check for 6. Results a valid billet, so we can limit our attention to instances that have them. However, for their version of the problem For all instances we were able to find stable assignments. (which fixes the number of coalitions rather than the size, Tables 1, 2, and 3 show the results from running 500 iter- but can also specify the sizes of those coalitions), finding the ations of each algorithm on the 20 instances. The mean socially-optimal assignment of maximal utility is NP-hard. values of the 𝑘 = 10 and 𝑘 = 1 simulated annealing al- gorithms were significantly different than the local search values (𝑝 = 4.368𝑒−5 , 𝑝 = 3.893𝑒−5 ). We observe in Table 1 that the local search algorithm Table 2 falls slightly short of the average utility found through the Simulated Annealing (k = 10) simulated annealing algorithms in Tables 2 and 3. This is Instance Min Max Mean Std Dev expected, as the local search executes in a single pass, and 1 111.286 118.065 114.748 1.032 thus does not necessarily find a global optimum. This is a 2 112.962 119.673 116.303 1.105 fair trade-off compared to simulated annealing, however, as 3 113.826 119.556 116.825 1.066 local search is significantly faster, particularly if it’s only 4 112.885 119.241 116.138 1.065 run once. 5 115.544 121.312 118.327 1.056 We also observe that the simulated annealing algorithm 6 115.212 122.779 119.589 1.283 does not significantly vary for different values of 𝑘. We 7 114.306 120.111 117.15 1.05 see in Table 4 that the simulated annealing algorithms for 8 108.672 113.863 111.156 0.954 9 114.477 120.098 117.485 1.089 𝑘 = 10 and 𝑘 = 1 performed extremely similarly across 10 113.471 120.537 117.453 1.064 100 instances, with a very small improvement for 𝑘 = 10, 11 112.601 118.827 115.579 1.12 but not enough that we believe to be statistically significant. 12 111.261 118.539 115.899 1.038 13 114.528 121.563 118.374 1.33 Table 1 14 114.71 121.152 117.759 1.121 Local Search 15 114.721 121.833 118.512 1.125 16 114.38 121.413 117.723 1.031 Instance Value 17 116.094 121.983 119.206 0.984 1 112.252 18 114.061 120.354 117.346 1.06 2 114.603 19 116.305 122.427 119.51 1.143 3 116.402 20 114.041 121.191 118.102 1.137 4 115.416 - 113.767 120.226 117.159 1.093 5 117.228 Table 2 shows the results from running 500 iterations of the k=10 6 115.788 simulated annealing algorithm. The columns from left to right repr- 7 115.678 esent the instance number, the local maximum with the lowest total 8 111.833 utility, the local maximum with the highest utility, the mean utility, 9 115.508 and the standard deviation of the local maxima for each instance. 10 114.291 11 113.775 12 114.92 Table 3 13 115.663 Simulated Annealing (k = 1) 14 116.937 Instance Min Max Mean Std Dev 15 118.35 1 111.132 117.636 114.859 1.07 16 116.643 2 113.49 119.131 116.409 1.016 17 116.479 3 113.25 119.6 116.831 1.054 18 114.154 4 113.108 119.272 116.043 1.034 19 117.611 5 115.327 121.287 118.331 1.043 20 119.229 6 115.249 122.797 119.399 1.387 - 115.638 7 113.73 119.99 117.182 1.028 Table 1 shows the results from running local search on every insta- 8 108.302 113.57 111.138 0.952 nce. The value is the total utility of the billet after the local search 9 114.604 120.547 117.462 1.048 algorithm converges to a local maximum 10 114.606 120.641 117.416 1.084 11 112.738 118.57 115.632 1.106 12 112.906 118.735 115.946 1.071 13 114.543 122.06 118.374 1.28 7. Toy Example 14 114.53 120.506 117.782 1.056 15 115.226 122.188 118.451 1.196 One question that is not answered in the previous section 16 114.618 120.463 117.655 0.943 is whether the maximum-utility billets found by simulated 17 116.3 122.001 119.346 0.993 annealing are actually optimal. To test this, we generated 18 114.582 120.461 117.423 1.02 a 21-agent instance with an initial billet utility of 34.906. 19 116.326 123.495 119.65 1.181 Then, using a branch and bound algorithm, we were able 20 115.126 121.122 118.179 1.017 to compute the global maximum of 41.153, which ran in - 113.985 120.204 117.175 1.079 3018.43 seconds and checked 24,567,994 nodes. Table 3 shows the results from running 500 iterations of the k=1 simulated annealing algorithm. The columns from left to right repr- The local search algorithm converged at a value of 39.826 esent the instance number, the local maximum with the lowest total after seven swaps. Afterwards, we ran 100 iterations of sim- utility, the local maximum with the highest utility, the mean utility, ulated annealing k=10 and k=1. Given the global maximum, and the standard deviation of the local maxima for each instance. we can conclude that the local search converged at a local but not global maximum, while the simulated annealing algorithms were able to find the global maximum (see Table search algorithm. This is unsurprising as a smaller instance 4) in a portion of the runs (G Max(%)). size would make the search space for simulated annealing Although the mean value of the 𝑘 = 10 algorithm is smaller. slightly higher than the 𝑘 = 1 algorithm, there was no significant difference between the two algorithms in terms of their utility (𝑝 = 0.784) We also observe that the low- 8. Conclusions est utility found by either of the simulated annealing algo- ArmA 3 is a popular MilSim that requires a manual billeting rithms was the highest value found by the standard local process, which involves assigning 50–100 players into a set Table 4 [13] J. Alcalde, Exchange-proofness or divorce-proofness?, Toy Example Simulated Annealing Economic Design (1995) 275––287. k Min Max Mean G Max(%) [14] K. Cechlárová, On the complexity of exchange-stable 10 39.699 41.153 40.844 21 roommates, Discrete Applied Mathematics 116 (2002) 1 39.826 41.153 40.83 17 279–287. Table 4 shows the results from running 100 iterations of simulated [15] J. Chen, A. Chmurovic, F. Jogl, M. Sorge, On (coali- annealing. k represents the k value used for the accept function. G tional) exchange-stable matching, in: Algorithmic Max is the number of times the algorithm found the global maxim- Game Theory: 14th International Symposium, SAGT um value out of 100. 2021, Aarhus, Denmark, September 21–24, 2021, Pro- ceedings 14, Springer, 2021, pp. 205–220. of roles before the game begins. This process can be quite [16] N. Arnold, J. Goldsmith, S. Snider, Extensions to tiered time consuming, and often involves much trial and error. coalition formation games, The International FLAIRS In this paper we explore how this problem can be cast as Conference Proceedings 35 (2022). doi:https://doi. org/10.32473/flairs.v35i.130708. a coalition formation problem, which enables the use of coalition formation algorithms to perform billeting auto- [17] N. Arnold, S. Snider, J. Goldsmith, Socially conscious matically. Specifically, we show how simulated annealing stability for tiered coalition formation games, Annals and local search can be used to generate stable billets in of Math and Artificial Intelligence (2024). https://link. polynomial time. springer.com/article/10.1007/s10472-023-09897-4. To our knowledge, this is the first example of using coali- [18] C. H. Papadimitriou, K. Steiglitz, Combinatorial Opti- tion formation algorithms to automate role assignment in a mization: Algorithms and complexity, Courier Corpo- hierarchical game. We were able to show that simple heuris- ration, 2013. tics do surprisingly well. Future work will entail scaling up the methods and developing both game-specific and general methods for billeting, and related activities. References [1] S. Banerjee, H. Konishi, T. Sonmez, Core in a simple coalition formation game, Social Choice and Welfare 18 (2001) 135–153. [2] A. Bogomolnaia, M. O. Jackson, The stability of hedo- nic coalition structures, Games and Economic Behav- ior 38 (2002) 201–230. [3] J. Schlueter, C. Addington, J. Goldsmith, Anchored team formation games, in: The International FLAIRS Conference Proceedings, volume 34, 2021. [4] J. Schlueter, Novel Hedonic Games and Stability No- tions, Ph.D. thesis, University of Kentucky, 2021. [5] M. Spradling, J. Goldsmith, X. Liu, C. Dadi, Z. Li, Roles and teams hedonic game, in: International Conference on Algorithmic DecisionTheory, Springer, 2013, pp. 351–362. [6] M. Spradling, Role Based Hedonic Games, Ph.D. thesis, University of Kentucky, 2015. [7] C. Siler, Tiered coalition formation games, The In- ternational FLAIRS Conference Proceedings 30 (2017) 210–214. [8] R. J. Aumann, J. H. Dreze, Cooperative games with coalition structures, International Journal of game theory 3 (1974) 217–237. [9] M. Spradling, J. Goldsmith, Stability in role based hedonic games., The International FLAIRS Conference Proceedings 28 (2015) 85–90. [10] V. Bilo, G. Monaco, L. Moscardelli, Hedonic games with fixed-size coalitions, in: AAAI Conference on Artificial Intelligence, volume 36(9), 2022, pp. 9287–9295. doi:https://doi.org/10.1609/aaai. v36i9.21156. [11] A. E. Roth, T. Sönmez, M. U. Ünver, Kidney exchange, The Quarterly journal of economics 119 (2004) 457– 488. [12] K. Cechlárová, D. F. Manlove, The exchange-stable marriage problem, Discrete Applied Mathematics 152 (2005) 109–122.