Introduction

The 2013 video game Armed Assault 3 (usually shortened to ArmA 3) by Bohemia Interactive is a realistic military simulation game, or MilSim, which gives players an online sandbox to role-play in military settings. Realistic MilSim communities in ArmA 3 have large organizational structures which emulate real-life chain of command, but these communities often have difficulty assigning players to different in-game roles. This process, called billeting, is especially difficult in large MilSim communities because they, especially in ArmA 3, often have hundreds of members, with anywhere from 50 to 100 people trying to play in a cooperative game instance all at once. The first author reports that it takes several days for billeting, and that process often leads to acrimonious disputes, in part driven by interpersonal tensions between players who do or do not wish to interact with each other in fire teams or in adjacent roles in the chain of command. In order to form stable teams, i.e., teams where no players have incentive to change their assignment, we define this more formally in the section on coalition formation games. community leadership has to spend a lot of time and energy on team formation, often with mixed success. Given the time and effort required to find these solutions, utilizing algorithmic methods for finding stable teams would greatly reduce the burden on community leadership.

In this paper, we explore how algorithms for forming stable coalitions in coalition formation games can be applied to team formation in ArmA 3. Using stability as a measure of goodness or utility, we examine a number of coalition formation algorithms and evaluate them based on the overall utility (stability) of the billets that they generate. Specifically, we explore how various simulated annealing and local search methods can be used to billet a set of synthetic ArmA 3 users based on a set of known preferences.

The remainder of the paper is organized as follows. In Section 2 we describe related work about coalition formation, and about other games with similar billeting/assignment problems. In Section 3 we provide an overview of both ArmA 3 and the billeting process. We then describe the coalition formation algorithms that we will investigate in this paper and outline our experiments and results.

Related Works

We observe billeting problems arising in large-scale online community games, most notably in roleplay settings which require individuals to be divided into teams with a clear structural hierarchy. One example case is for the game EveOnline (https://www.eveonline.com/), in which players and their ships are assigned to fleet formations based on the intrinsic rank and skills of their in-game character. Outside of strictly video games, we note billeting problems being relevant for many other large-community structures, such as coordinating text-based roleplay communities.

A coalition formation game is a cooperative multi-game agent game. The input is a set of agents and their preferences or utilities over coalitions they might be assigned to; the output is a partition of agents into coalitions. The computational goal of a coalition game problem might be to find an optimal or near-optimal partition, as we do here, or to find a stable partition for some notion of stability, or to determine if such a stable partition exists. We are particularly interested, here, in hedonic coalition formation games [1,2], also known as hedonic games, where agents' preferences or utilities are defined only over each coalition they might be assigned to. If we interpret the billeting problem for ArmA 3 as the problem of finding a single (or "grand") coalition with optimal total utility, we do not consider the effects of other teams' billeting, so we are in the hedonic setting.

ArmA 3

In this section we describe ArmA 3, and mention the ways in which we codify rules that are left to individual gaming communities.

Overview

ArmA 3 is a highly diverse community with many different play-styles, game-modes, and levels of realism. For the purpose of this paper, we construct a coalition formation game for a "realism"-focused MilSim community. 1 Like many popular communities, we will primarily base our coalition game's structure off of North American Treaty Organization (NATO) protocol and procedure.

There are no formal rules from the game developers, as each community gets to choose their own organizational rules. Most realistic ArmA 3 units attempt to follow the standard NATO ORBAT that is used by modern Western militaries. (https://web.archive.org/web/20070826233341/http: //\orbat.com/site/toe/toe/usa/platoontoe.html) We therefore mimic this structure as well.

Billeting

The formation of an instance of an ArmA 3 mission (henceforth for simplicity just "mission") first requires each player to be assigned a role for that mission's "billet" before the mission is hosted at some fixed time. The role a player is assigned is based on several factors, including but not limited to:

1. Player preferences towards working with certain individuals. 2. The player's rank in the unit. 3. The player's qualifications earned from training.

The billet is constructed as a tree of players, where each player node has command and authority over every player in each child branch, and has most direct authority over the immediate children to the player. The tree is composed of different nested coalitions, in which players are part of these coalitions depending on where in the tree they are located. For the purpose of this research, we ignore any attached "support companies" with their own parallel but separate command, and instead focus on the main tree of standard infantry. We do this because this main tree is the largest and most complex.

Tree Structure

The billet hierarchy tree is composed of the following nested coalitions:

A Fireteam is a small team of infantrymen (players) and is the lowest in the hierarchy at the leaf nodes of the tree. A Fireteam is a strict unit composition that must adhere to the following criteria to be considered valid:

1. Must be made of exactly 4 players. 22. The Fireteam consists of four roles, of which each member must have the proper qualifications to be assigned the role. These roles are: a) Team Leader (TL) b) Autorifleman (AR) c) Grenadier (GRN) d) Rifleman (RFL) 3. The Team Leader is a special role, and requires players to have a high enough rank (e.g. Corporal or Sergeant) in order to occupy.

A Squad is the next level above a Fireteam. Squads are composed of a Squad Leader and exactly 2 distinct Fireteams. The Squad Leader must have a higher minimum rank and additional leadership qualifications.

A Platoon is the next level above a Squad. Platoons are led by a Platoon Leader and a Platoon Sergeant, the latter acts as the second-in-command to the former. Both must have additional rank and training qualifications. Platoons are themselves composed of anywhere from 1 to 4 Squads, offering some flexibility to the command structure.

At the highest level is the Company, which consists of the Company Leader, and they are in charge of all Platoons under their command. In practice, there is little reason to go higher than this as ArmA 3 servers usually do not have enough player slots to necessitate larger structures, but actual NATO unit organization can be expanded much further if needed.

Ranks

A player agent will have a rank that represents their time, experience, and recognition of merit within a community. The ranks that we use in this paper are based on the list of ranks used by the United States Army. Each role within the hierarchy tree has a minimum rank requirement, and players cannot be assigned a role outside their rank. Players usually are assigned to the highest-ranking role that they are qualified for in order that individuals best qualified to lead may do so. However, players of a higher rank can choose to move down the hierarchy tree. This is an action we call self-demotion, and happens in some uncommon circumstances to fill in gaps lower in the tree, or to fulfill a player's preferences if they would rather not lead for the day.

Qualifications

Each role within the hierarchy tree has its own set of skill or training qualifications that a player must have in order to be assigned that role. For example, an Autorifleman must have the training necessary to use their machine gun, and a Team Leader must have some basic leadership training. These qualifications are tracked for every player, and a player must possess all of the prerequisite qualifications in order to be assigned to a role. These qualifications are Boolean, as players will either have a given qualification or they will not.

Many ArmA 3 realistic MilSim communities have a large number of available qualifications to train for, many of which require prerequisite qualifications themselves. In general, the leadership of many ArmA communities elect to have simple skill trees with no more than one prerequisite per qualification whenever possible. This is to keep progression simple for players to understand and for leadership to keep track of. Our algorithms allow for the dynamic creation of a qualification tree with any number of prerequisites to explore more complicated assignments.

Gaming-based or game-inspired coalition formation games has been explored. We mention a few here, from which AACFGs take elements. The first are Anchored Team Formation Games [3,4], which (a) assigns players to coalitions to play TTRPGs, and (b) also makes use of roles (GM and players). More relevant, perhaps, are Role Based Hedonic Games [5,6], introduced to model preferences of League of Legends players, in which players express preferences over their own champion (role) and the champions that make up the team. In addition, Tiered Coalition Formation Games (TCFGs) [7], introduced to model the stratification of Pokémon by the fan site Smogon, has some of the flavor of the role hierarchy of AACFGs. We later give a formal definition of TCFGs and of the related notion of socially conscious stability, as we build on that stability notion.

In summary: each player has a maximum rank they can be assigned, and a set of qualifications that enable particular billets. Each player has utilities for each other player, though the inter-player utility within a given billet is scaled so that it decreases geometrically with the branch distance in the hierarchy tree. Players on separate branches do not contribute to each other's utility.

Armed Assault Coalition Formation Games (AACFGs) are similar to Anchored Team Formation Games (ATFGs), which were designed to capture table formation for table-top roleplaying games [3,4]. AACFGs and ATFGs are both extensions of Additvely Separable Hedonic Games, in which each agent has utility assigned to every other agent. The agent's total utility for a coalition is the sum of the assigned utilities to each other member of that coalition. Definition 1. [1] Additively Separable Hedonic Games (ASHG) are a class of hedonic game where each player 𝑖 ∈ 𝑁 assigns values to each player 𝑗 ∈ 𝑁 , expressed as 𝑣𝑖(𝑗); for all 𝑖, 𝑣𝑖(𝑖) is 0. The utility a player 𝑎𝑖 derives from each coalition 𝑆 ∈ 𝒩𝑖 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 utility in coalition(s) other than those assigned. Notions of stability in coalition formation games [8] vary in the number of agents that can move, which agents' utilities are considered, and whether those utilities have to be strictly improved or merely non-decreasing. The two most common notions of stability are Nash and core stability. The simplest notion, Nash Stability [? ], holds if no single agent can increase its utility by joining a different coalition than the one to which it is assigned. An assignment is core stable [1] if no group of agents can create a new coalition of their own such that each agent in the new coalition improves their utility.

Note that Nash stability is not meaningful in games in which coalitions have fixed sizes, or have structures driven by fixed positions and roles; in such settings, an individual agent typically cannot deviate to or from a coalition without invalidating that coalition. Similarly, core stability has limited usefulness for settings with fixed positions and roles, as there may be valid core deviations under the definition of core stability which would cause agents outside of those deviations to no longer belong to a legitimate coalition. A related game, Roles and Teams Hedonic Games, models League of Legends teams of fixed size and considers swaps of agents between coalitions as the driver of stability [5,9].

Swap exchange stability has a rich history, well surveyed in [10], for instance. We mention a few additional applications: kidney exchanges [11] (there is a huge literature there), in which biologically incompatible donor-recipient pairs are placed in a cycle or chain 3 where donors are swapped so recipients receive compatible kidneys; marriage markets where mates are similarly exchanged, perhaps in sequence [12]; other matching markets [13]; roommate assignment problems [14,12,15]. 3 Kidney exchange chains start with a kidney donor who has died.

We now formally define AACFGs. Informally, an instance consists of the baseline preferences agents have over each other, and the factors that define agents' utilities for given assignments (or billets -we use the terms interchangeably), namely the structure of the hierarchy, or tree of roles. We also include the requirements of each role, namely qualifications.

Definition 2. An instance of an ArmA Coalition Formation Game (AACFG) consists of

• a preference matrix 𝑃 that implicitly defines the number of players; • an array of qualifications for those players;

• a discount 1/𝑠 for utilities as a function of distance in the assignment tree, or billet; • the structure of the assignment tree (depth of the tree, qualifications for each role).

We are interested in assignments, or billets, for AACFGs.

Definition 3.

A billet is a mapping from players to roles. A valid billet is one in which the assigned players each have the qualifications necessary for their assigned role. The utility for player 𝑎 for billet 𝐵 depends on 𝑎's utility for its descendants, ancestors, and (if 𝑎 is assigned to a Fireteam) those in its Fireteam. We define 𝐷 𝐵 (𝑎) to be those players, and 𝑢𝑎(𝐵) = ∑︁ 𝑐∈𝐷𝑎 (𝐵)𝑥𝑎(𝑐).

We define 𝑢(𝐵) = Σ𝑎𝑢𝑎(𝐵).

We borrow heavily from the work on Tiered Coalition Formation Games to define our notion of stability.

Definition 4. [7]

A tiered coalition formation game (TCFG) is a coalition formation game (𝑁, ⪰), where 𝑁 = {𝑎1, 𝑎2, ..., 𝑎𝑛}; an outcome, or tier list, is a totally ordered spanning set of disjoint coalitions [𝑇1, 𝑇2, ..., 𝑇 𝑘 ]; Seen(𝑎𝑖, 𝑇 ) for tier list 𝑇 denotes the set of all agents that are in the same tier as 𝑎𝑖 or are in a lower (prior) tier; and the preferences for each agent 𝑎𝑖 in each possible tier list 𝑇 are determined solely by the set of agents 𝑎𝑖 "sees" in 𝑇 [7].

Note that TCFGs are not hedonic, in that an agent affected by the assignment of all seen agents, even those not in its own tier. Thus, when an agent moves from one tier to another, it potentially affects the utilities of agents in any intervening tiers.

We are interested in billets that are not only valid, but stable. We consider two notions of stability based on swaps.

Definition 5. Given an instance 𝐼 of AACFG and valid billet

𝐵 for 𝐼, 𝐵 is swap stable if there is no pair of agents 𝑎, 𝑏 that are assigned to different roles by 𝐵, such that swapping 𝑎 and 𝑏 leaves the billet valid, and improves the utilities for both.

The notion of swap stability is appealing, but may not be achievable.

Lemma 1. Not all instances of AACFGs have swap stable billets.

Proof. We define an instance 𝐼 = 𝑃, 𝑄, 𝑠 of an AACFG, and a valid billet 𝐵. Let all players have all qualifications for Fireteam roles, and let there be sufficient other qualified players to have a valid billet. Let 𝑎 and 𝑏 have no qualifications for higher ranks. We define the preference matrix 𝑃 Thus, 𝑎 wants to be in a Fireteam with 𝑏, but 𝑏 does not want to be in a Fireteam with 𝑎. If 𝑎 and 𝑏 are billeted in the same Fireteam, and any player billeted in another Fireteam (with utility 0) can improve their utility by swapping with 𝑏. If 𝑎 and 𝑏 are in separate Fireteams, any player in 𝑏's Fireteam (with utility -1) can improve their utility by swapping with 𝑎. Thus, 𝑎 will chase 𝑏 and 𝑏 will run away, ad infinitum.

The problem that arises in our counterexample is that 𝑎 is allowed to join 𝑏's Fireteam, to the detriment of 𝑏's utility. There are a variety of notions of stability that extend consideration of utility beyond that of the blocking agents. To help us think about this, we define a notion of stability particular to TCFGs. Definition 6. A socially consciously stable tier list is a tier list 𝑇 in which there exists no agent 𝑎𝑖 that can improve its utility by moving to a new position in the tier list without decreasing the total utility of all other agents [16,17].

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 (which requires that an agent leaving a coalition must leave behind other agents whose utility is not lowered -"permission to leave") and individual stability (which requires that an agent joining a coalition cannot lower the utility of any agent in that coalition -"permission to enter") [2]. We define a notion of stability that is similar to contractually individual stability, but is defined in terms of agents trading coalitions, or swapping. Definition 7. An assignment 𝐵 is Socially Conscious Swap Stable (SCSS) if there is no pair of agents 𝑎 and 𝑏 assigned to roles 𝐵(𝑎), 𝐵(𝑏) such that swapping them creates a new assignment 𝐵 ′ with

• 𝑢 𝐵 ′ 𝑎 > 𝑢 𝐵 𝑎 ; • 𝑢 𝐵 ′ 𝑏 > 𝑢 𝐵 𝑏 ; • ∀𝑥 / ∈ {𝑎, 𝑏} 𝑢 𝐵 ′ 𝑥 ≥ 𝑢 𝐵 𝑥 .

Computational Complexity of AACFGs

We note that AACFGs generalize Additively Separable Hedonic Games with Fixed-Size Coalitions (AS-HGFSCs) [10].

In particular, given an AS-HGFSCs, we can construct an AACFG instance by adding players and assigning the unique roles above the Fireteam level, while treating the input agents from the AS-HGPSC instance as players fully qualified for Fireteams. (Note that we need to loosen our restriction of Fireteams having exactly four members.) From this observation, we get all of the hardness results for AA-HGFSCs and some inspiration for algorithms. For instance, in what Bilo, et al. [10] call SSS (strictly swap stability) and what we call SCSS, there is always an SCSS billet. For our work, this assumes that there is some valid billet. In the current formulation, it is easy to check for a valid billet, so we can limit our attention to instances that have them. However, for their version of the problem (which fixes the number of coalitions rather than the size, but can also specify the sizes of those coalitions), finding the socially-optimal assignment of maximal utility is NP-hard.

Heuristic Algorithms

We used local search and simulated annealing. Note that local search, also know as "hill climbing" [18], can only take improving moves, which tends to get stuck in local, nonglobal optima. Simulated annealing allows for occasional random "jumps, " which have the possibility of jumping away from sub-optimal hills. Given that the range of values of pairwise utilities is polynomially bounded in the number of agents, there is a polynomial upper bound on the utility of an assignment. Note that, for SCSS, each local improvement from the local search strictly increases the social welfare (total utility). Furthermore, finding an improving swap, if one exists, takes polynomial time. Thus, each run of local search has a polynomial time bound. For simulated annealing, we used a pre-set cut-off to deal with the possibility of super-long runs.

In the simulated annealing, we used the parameter 𝑘 to determine the probability a random swap is accepted weighted by a temperature value 𝑇 . 𝑇 decays from 1 to .001 by 𝑇 ′ = 𝑇 /1.001. This probability is given by

𝑃 (𝑢(𝐵), 𝑢(𝐵 ′ ), 𝑇 ) = 𝑒 𝑢(𝐵 ′ )−𝑢(𝐵) 𝑘*𝑇 .

Note that the problem of finding valid billets, ones where all agents have the qualifications for their assigned roles, is nontrivial, though we can easily find one such billet. For the local search and simulated annealing algorithms, we start all runs from the same initial assignment. The simulated annealing variants use random number generators, so each run may find a different stable assignment. However, local search is deterministic, thus it was only run once.

Experiments

Generator

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 the size of the qualifications small, allowing each agent to hold anywhere from zero to five qualifications.

Runs

Twenty 50-player structures were generated. The discount value 𝑠 is set to 2 and the utility one player has for another is in the interval [0,1]. For each instance, we checked if a valid billet exists by iteratively assigning the highest ranked player to the highest remaining position, irrespective of inter-player preferences. From this initial billet we ran the deterministic local search, then 500 iterations of simulated annealing with 𝑘 = 10 and simulated annealing with 𝑘 = 1.

Results

For all instances we were able to find stable assignments. Tables 1, 2, and 3 show the results from running 500 iterations of each algorithm on the 20 instances. The mean values of the 𝑘 = 10 and 𝑘 = 1 simulated annealing algorithms were significantly different than the local search values (𝑝 = 4.368𝑒 −5 , 𝑝 = 3.893𝑒 −5 ).

We observe in Table 1 that the local search algorithm falls slightly short of the average utility found through the simulated annealing algorithms in Tables 2 and 3. This is expected, as the local search executes in a single pass, and thus does not necessarily find a global optimum. This is a fair trade-off compared to simulated annealing, however, as local search is significantly faster, particularly if it's only run once.

We also observe that the simulated annealing algorithm does not significantly vary for different values of 𝑘. We see in Table 4 that the simulated annealing algorithms for 𝑘 = 10 and 𝑘 = 1 performed extremely similarly across 100 instances, with a very small improvement for 𝑘 = 10, but not enough that we believe to be statistically significant.

Toy Example

One question that is not answered in the previous section is whether the maximum-utility billets found by simulated annealing are actually optimal. To test this, we generated a 21-agent instance with an initial billet utility of 34.906. Then, using a branch and bound algorithm, we were able to compute the global maximum of 41.153, which ran in 3018.43 seconds and checked 24,567,994 nodes. The local search algorithm converged at a value of 39.826 after seven swaps. Afterwards, we ran 100 iterations of simulated annealing k=10 and k=1. Given the global maximum, 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 4) in a portion of the runs (G Max(%)).

Although the mean value of the 𝑘 = 10 algorithm is 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 lowest utility found by either of the simulated annealing algorithms was the highest value found by the standard local 3 shows the results from running 500 iterations of the k=1 simulated annealing algorithm. The columns from left to right represent the instance number, the local maximum with the lowest total utility, the local maximum with the highest utility, the mean utility, and the standard deviation of the local maxima for each instance.

search algorithm. This is unsurprising as a smaller instance size would make the search space for simulated annealing smaller.

Conclusions

ArmA 3 is a popular MilSim that requires a manual billeting process, which involves assigning 50-100 players into a set of roles before the game begins. This process can be quite time consuming, and often involves much trial and error.

In this paper we explore how this problem can be cast as a coalition formation problem, which enables the use of coalition formation algorithms to perform billeting automatically. Specifically, we show how simulated annealing and local search can be used to generate stable billets in polynomial time.

To our knowledge, this is the first example of using coalition formation algorithms to automate role assignment in a hierarchical game. We were able to show that simple heuristics do surprisingly well. Future work will entail scaling up the methods and developing both game-specific and general methods for billeting, and related activities.