=Paper=
{{Paper
|id=Vol-3926/paper4
|storemode=property
|title=ArmA 3 Billeting as a Coalition Formation Game
|pdfUrl=https://ceur-ws.org/Vol-3926/paper4.pdf
|volume=Vol-3926
|authors=Pearson Garner,Aaron Lin,Ruby Harris,Brent Harrison,Judy Goldsmith
|dblpUrl=https://dblp.org/rec/conf/exag/GarnerLHHG24
}}
==ArmA 3 Billeting as a Coalition Formation Game==
https://ceur-ws.org/Vol-3926/paper4.pdf
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.