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 efort 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 efectiveness 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.
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 dificulty assigning players to diferent in-game roles. This process, called billeting, is especially dificult 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 efort 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, 11th Experimental Artificial Intelligence in Games Workshop, November 19, 2024, Lexington, Kentucky, USA. * 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 (B. Harrison); goldsmit@cs.uky.edu (J. Goldsmith)
0009-0007-0375-1650 (P. Garner); 0009-0009-3317-4545 (A. Lin); 0009-0006-0915-8084 (R. Harris); 0000-0002-9421-8566 (B. Harrison); 0000-0002-9421-8566 (J. Goldsmith) © 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). 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.
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
ifnd 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[
ArmA 3 is a highly diverse community with many diferent 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 of 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.
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 diferent 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.
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.2 2. 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. 1The oficial ArmA 3 community website, units.arma3.com, allows communities to identify with the tags of “realism", “semi-realism," and “relaxed." The latter of these two are much less likely to have a rigid billet structure, so we will not consider them for this paper. 2In practice, team sizes can vary to account for diferent organizations or numbers of players, but for this paper we are only interested in the case where team sizes and roles are fixed.
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, ofering 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. 3.4. 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.
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 [
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 [
Definition 1. [
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 [
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 [
Swap exchange stability has a rich history, well surveyed
in [
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. [
Note that TCFGs are not hedonic, in that an agent afected 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 afects 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 diferent 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 suficient other qualified players to have a valid billet. Let and have no qualifications for higher ranks. We define the preference matrix by [, ] = 5 and [, ] = − 5. For all other players , [, ] = 1 and [, ] = − 1, and otherwise [, ] = 0. 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 [
We can understand socially conscious stability (SCS) to
require permission from all afected 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") [
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 • ′ > ; • ′ > ; • ∀ ∈/ {, } ′ ≥ .
We note that AACFGs generalize Additively Separable
Hedonic Games with Fixed-Size Coalitions (AS-HGFSCs) [
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. [
We used local search and simulated annealing. Note that
local search, also know as “hill climbing" [
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 diferent stable assignment. However, local search is deterministic, thus it was only run once.
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.
5.2. 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 [
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 diferent 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-of 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 diferent 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.
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 diference 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
ArmA 3 is a popular MilSim that requires a manual billeting process, which involves assigning 50–100 players into a set k Min Max Mean G Max(%) 10 39.699 41.153 40.844 21 1 39.826 41.153 40.83 17 Table 4 shows the results from running 100 iterations of simulated annealing. k represents the k value used for the accept function. G Max is the number of times the algorithm found the global maximum value out of 100. 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.