Theoretical Foundations of Team Matchmaking

∗ †
Josh Alman Dylan McKay
Computer Science and Artificial Intelligence Laboratory Computer Science and Artificial Intelligence Laboratory
Massachusetts Institute of Technology Massachusetts Institute of Technology
Cambridge, Massachusetts Cambridge, Massachusetts
jalman@mit.edu dmmckay@mit.edu

ABSTRACT are multiplayer games in which two teams face each other.
Online team games need matchmaking systems which can League of Legends has over 100 million players who play for
handle a high throughput of players and form fair teams over one billion hours each month, Dota 2 has over 10 mil-
to play matches together. We study this problem from a lion players per month, and Counter Strike: Global Offensive
theoretical perspective, by defining and analyzing a broad has 3 million players who play for over 250 million hours per
model which captures many applications. In the most ba- month. These are three of the five most played online games
sic formulation, we desire a data structure which supports today, and a match in one of these games is played between
adding and removing players, and extracting the best pos- two teams which typically consist of five players each [25].
sible games. We design an efficient solution, where with In this paper, we undertake the first theoretical study of
n players in the structure, operations can be performed in team matchmaking, to the best of our knowledge. While we
O(log n) time. We then consider a natural extension one focus on applications to online games, our model and results
might want in a team game setting, where each team has are very general and apply to other natural settings where
different roles, and each player is only willing to play in individual agents are divided into teams, such as designing
some of these roles. We show that this extension is com- clinical trials and other experiments, dorm room assignment,
putationally intractable, conditioned on the popular 3SUM and recreational sports.
conjecture; nevertheless, we are able to design an efficient 1.1 Role-restricted queues
constant-factor approximate solution. Our results help ex-
We were inspired to study team matchmaking from a theo-
plain recent practical issues with the matchmaking systems
in some of the most popular online games. We also prove retical perspective by recent practical issues with the match-
similar results in an offline setting, which has many applica- making systems in some of the most popular online games.
tions to matching and partitioning beyond online games. In most games, players enter a ‘queue’ to be put into a
match, and the matchmaking system creates pairs of teams
to play against each other. However, many of these games
Keywords have different ‘roles’ that players might play on their team.
Cooperative games: theory & analysis; Game theory for For instance, one may be a tank character, while another is
practical applications a healer, and another is a sniper. It can be problematic if a
team is formed where everyone wants to play the same role.
1. INTRODUCTION To solve this issue, many games recently moved to a ‘role-
restricted queue’, in which players pick some desired roles
Matchmaking is one of the most important aspects of on- when they enter the queue, and teams are formed where
line games. No matter how well-designed a game is, being each player can play in a desired role. However, these role-
matched against an opponent with significantly more or less restricted queues have been widely unsuccessful in practice.
skill and familiarity with the game can ruin the experience. In late 2015, League of Legends made such a switch, which
Meanwhile, the experience may never even begin if match- widely angered players, as queue times went up, and game
making takes too long and players get bored waiting in queue balance went down [22, 23]. Another popular game, Heroes
to play. Hence, matchmaking systems need to be computa- of the Storm, also had much longer queue times when they
tionally efficient, and rapidly create balanced matches. restricted which characters could be together in a team [2].
The matchmaking problem for two-player games like Chess, Our results help explain this issue. Our main results show
Hearthstone, or Street Fighter, has been studied recently that the basic formulation of team matchmaking has a sim-
[14, 5]. However, many of today’s most popular games ple and efficient solution, but that the role-restricted queue-
∗Supported by NSF DGE-114747. ing problem is computationally intractable (given a popular
†Supported by NSF CCF-1552651 (CAREER). assumption from complexity theory). Hence, it is impossible
to implement a role-restricted queue with short queue times
which makes fair matches.
Appears in: Proc. of the 16th International Conference on
Autonomous Agents and Multiagent Systems (AAMAS 2017), 1.2 Model
S. Das, E. Durfee, K. Larson, M. Winikoff (eds.), An important ingredient of a matchmaking system is a
May 8–12, 2017, São Paulo, Brazil. well-defined measure to determine the best matches to form.
Copyright c 2017, International Foundation for Autonomous Agents
and Multiagent Systems (www.ifaamas.org). All rights reserved. Most online games only release vague information about

1073
what measures they optimize. We therefore consider a broad The p-fairness of a game is a nonnegative real value, with 0
class of imbalance functions, which capture the known pri- being the most fair.
orities of the three most popular games mentioned above by When we pick p = 1, we get the simple choice from above
an appropriate choice of parameters. In these games [4, 28, that the skill of a team is the sum of the skills of the team
29], a game is informally said to be balanced if the following members. In the limit as p → ∞, we get that s∞ is simply
two properties are satisfied: equal to the skill of the most skilled player on the team,
• Fairness: the two teams have roughly equal chance of s∞ (X) = max sx .
winning, and x∈X
• Uniformity: there is not much deviation between the Choices of p in-between interpolate between these two op-
best and worst players in the game. tions.
Each player has a skill rating which is maintained similar to
the ELO rating system [13, 17, 19], and these skill ratings 1.2.2 Uniformity
can be used to determine how well a game satisfies these two Even though a game is fair, it might still not be fun for
requirements. all the players involved. If a game involves players with a
Formally, the matchmaking problem is as follows. Given wide variety of skill levels, the less skilled players might feel
a set R of n players, a game is a pair of disjoint sets X and that they are just being strung along by the more skilled
Y of k players each. The parameter k should be thought of players rather than controlling the flow of the game and en-
as a constant, for instance k = 5. joying themselves. Similarly, an unskilled player in a game of
Each player r ∈ R has an associated skill level sr , which is mostly skilled players might feel demoralized, or anger their
a nonnegative real number. An imbalance function f maps teammates. As mentioned above, the most popular games
games to nonnegative real numbers, where games mapping have identified this issue, and their matchmaking systems
closer to zero are more desirable. Given an imbalance func- aim to avoid games with a large deviation between the best
tion f , a game (X, Y ) minimizing f among all those which and worst players in the game.
can be formed with the n players is called a best game. As The natural choice to measure the deviation of a set Z =
described above, imbalance functions will have a fairness X ∪ Y of player skills is the standard deviation,
component and a uniformity component. s
1 X
v(Z) := (sz − µZ )2 ,
1.2.1 Fairness |Z| z∈Z
In order to determine whether a game is fair, we need a P
measure of the skill of a team. A simple choice would be the where µZ := z∈Z sz /|Z| is the mean skill of Z. But again,
sum of the skills of the team members, this might not be tuned well to all applications. In some
X settings, having some players with much more or less skill
s(X) = sx . can be fine, as long as most players’ skill levels are around
x∈X the mean. In others, a single player whose skill level devi-
ates substantially from the mean can be a big issue. (How
However, this choice might not be sufficient to capture the important it is to minimize deviation in the first place also
team dynamics in many applications. Depending on how varies between applications. This is a separate issue which
much of an impact a highly-skilled player can have on a we discuss soon.)
team, a team with one skilled player and many unskilled Just as with fairness, choosing a different norm or mean
players might have a good chance or almost no chance of to take of the vector of deviations from µZ captures this
winning against a team of moderately-skilled players. This distinction well, and it is a standard technique in statistics.
same idea is captured by the standard notion of the p-norm We introduce a real parameter q ≥ 1 to measure this, and
of a vector1 , where we can select higher values of p to mean define the q-uniformity, denoted vq , to be the q-norm of the
that large entries have a bigger impact on the total norm. deviations from the mean,
Hence, for real parameter p ≥ 1, we define the p-skill of a !1/q
team, denoted sp , to be the p-norm of the team’s vector of 1 X
player skills, vq (Z) := |sz − µ|q .
|Z| z∈Z
!1/p
The q-uniformity of a game is, again, a nonnegative real
X p
sp (X) := sx ,
x∈X
value, with 0 being the most uniform.
When q = 2, we recover the standard deviation. But,
and the p-fairness of a game, denoted dp , to be the difference for other choices of q, this is the qth root of the qth central
of p-skills, moment 2 from statistics of the set of skill levels. When
dp (X, Y ) : = |sp (X) − sp (Y )| q = 1, vq is the average deviation from the mean, and so
!1/p !1/p many skill levels must be far from the mean to decrease the
X p X uniformity substantially. As q → ∞, we get that v∞ is just
= sx − spy . the farthest value from the mean,
x∈X y∈Y
v∞ (Z) = max |sz − µ|,
z∈Z
1
Recall that for a vector v = (v1 , v2 , . . . , vn ), its p-norm, 2
parameterized by a real value p ≥ 1, is defined as ||v||p := Actually our definition only agrees with central moments
Pn p 1/p

when q is an even integer, since the typical definition uses
i=1 |vi | . It is sometimes also called the `p norm. For sz − µZ rather than |sz − µZ |. Taking absolute values makes
p = 1 it is sometimes called the Manhattan distance, and more sense in our application, where having skill less than
for p = 2 it is also called the Euclidean distance. the mean should lead to less uniformity, not more.

1074
and so a single player whose skill level is far from the mean long in the matchmaking queue. By finding a game min-
makes the uniformity low on their own. Again, choices of q imizing g rather than minimizing f , we are allowing more
in-between interpolate between these options. leniency in how imbalanced a game is when it includes a
player who has been waiting for a long time. It is worth
1.2.3 Imbalance Function noting that with this definition of g, if a player r has been
We consider imbalance functions, parameterized by three waiting a long time in the queue, and we make a game in-
positive real constants α, p, q with p, q ≥ 1, of the form volving r as a result of this, we are still making the game of
least imbalance that includes r.
f (X, Y ) := α · dp (X, Y ) + vq (X ∪ Y ),
where dp is the p-fairness, and vq is the q-uniformity, as de- 1.2.6 Role-Restricted Queueing Problem
fined above. The imbalance of a game is a nonnegative real An important aspect of many team games, including League
number, with 0 being the most balanced. The parameter α of Legends and Dota 2, is that a team will consist of players
can be picked depending on how important fairness is rel- taking on a variety of different roles. For instance, one may
ative to uniformity in the particular application. A large be a tank character, while another is a healer, and another
α means that fairness is more important, while a small α is a sniper. It can be problematic if a team is formed where
means that more weight is put on uniformity. Hence, for in- everyone wants to play the same role. This can be solved
stance, if uniformity has little importance in one application, by including an option for players to select which roles they
a larger choice of α can reflect this. are willing to play when they enter the queue, and then only
In the data structures we design, we also allow for the creating games where each player can play a desirable role.
choices p = ∞ or q = ∞ as discussed earlier. Throughout We model this via the role-restricted queueing problem.
our results, we use the convention that if p = ∞ then 1/p = A role-restricted player p has a skill score sp and also a
0, and similarly for q. subset rp ⊆ {1, . . . , k} of roles they are willing to play. A
game g = (X, Y, m) in a role-restricted queue consists of two
1.2.4 Queueing Problem sets, X and Y , of k players, along with a map m : X ∪ Y →
Now that we have defined imbalance functions, we need a {1, . . . , k} from players to roles such that each team has
model of how a matchmaking system will process tasks. The one player in each role, and each player p is mapped to a
matchmaking systems in popular online games have large role from rp . All the other notions are the same, including
numbers of players constantly entering the matchmaking the definition of the time-sensitive role-restricted queueing
queue, and so they also need to be making new games at problem.
a consistently high rate. We model this problem as a data
structure problem, where players can be added to and re- 1.2.7 Offline Partitioning Problem
moved from the data structure as they come and go, and In applications like dorm room assignment or recreational
the game host can query for the best new game to make as sports, it is more natural to consider the offline partitioning
frequently as they can support it. problem where, given n players, we would like to partition
A game queue with imbalance function f is a data struc- them into n/(2k) games. There are many sensible options
ture which stores a collection of players and supports the for what objective to optimize for in this partitioning. For
following operations: illustration in our results, we choose to minimize the imbal-
ance of the most imbalanced game we create. However, we
• Insertion: insert a new player into the queue
later discuss other alternative options.
• Deletion: remove a player from the queue Using data structures for the queueing problem can give
suboptimal results for the partitioning problem, since re-
• Query: find a best 2k-player game (X, Y ) amongst the moving the best game might leave the remaining players in
players in the queue a very imbalanced game. We will nonetheless see that we
can get similar results for the partitioning problem as for
Our results apply to reasonable variants on this model as the queueing problem, using almost the same techniques.
well.
1.2.8 Further Extensions
1.2.5 Time-sensitive Queueing Problem
Although we define many variants on the queueing prob-
In most applications, we are also interested in making sure lem, a unifying property that we will see is that the same
no player waits for too long in the queue. A time-sensitive main ideas work, both to design data structures and to prove
game queue additionally stores, for each player r, the time lower bounds, in each regime. The extensions we focus on
tr which that player was inserted into the queue. The goal model the matchmaking systems for the applications we dis-
now is not necessarily to pick the best game, but also to cuss, but other extensions to imbalance functions of the
ensure no player is waiting for too long. queueing problem should also be amenable to our methods;
There are various mechanisms for this which all of our we discuss this further in the future work section.
results support. One example is to augment the imbalance
function f by defining a new time-sensitive priority function
g defined by
1.3 Other Applications
Our model and results are very general and apply to many
g(X, Y ) := f (X, Y ) + β · min tr , natural settings outside of online games where individual
r∈X∪Y
agents are divided into teams, such as:
where β is an appropriate positive real parameter which dic- Designing clinical trials: human participants volunteer
tates how important it is that players do not wait for too and are put in a queue, from which we wish to extract con-

1075
trol and experiment groups for trials which are ‘balanced’ in Theorem 4. The offline partitioning problem requires time
terms of parameters relevant to the trial (age, health, etc) n2−o(1) when k ≥ 3 assuming the 3SUM conjecture.
Other marketing or scientific experiments: the queueing
and partitioning problem can similarly be used to design We then design a constant-factor approximation algorithm
unbiased experiments in many areas, including partitioning which runs in near-linear time.
subjects either online or offline in A/B testing
Dorm room assignment: many schools divide students Theorem 5. For any constant k, there is a O(n log n)
into dorms in ‘fair’ or evenly distributed ways which could time ρ-approximation algorithm for the offline partitioning
be modeled by our imbalance functions problem.
Recreational sports: players need to be partitioned into
balanced teams for games other than online games, like in 3. RELATED WORK
recreational sports leagues Matching problems have been among the most important
problems in combinatorial optimization since the seminal
2. OUR RESULTS work of Edmonds [11, 12]. Matchmaking for two-player
First, we give an efficient data structure for the queueing games in an online setting was recently studied in [14]. The
problem. offline setting for two-player games might be most reason-
ably modeled as a maximum-weight bipartite matching prob-
Theorem 1. For any constant k, there is a data struc-
lem, which can be computed exactly in subcubic time [27]
ture for the queueing problem which takes O(log n) time per
and approximated in linear time [10]. The problem of dy-
insertion, deletion, or query.
namically maintaining a maximum weight bipartite match-
In contrast, we give strong evidence that there is no ef- ing also has lower bounds conditioned on the 3SUM conjec-
ficient data structure for the role-restricted queueing prob- ture and other popular conjectures [1].
lem. We give a lower bound conditioned on the popular Much work has focused on devising systems for rating how
3SUM conjecture from theoretical computer science. Given skilled players are, in order to predict whether a two-player
a multiset S of n integers, the KSUM problem asks to find or team game is fair, such as [17, 19]. We largely abstract
K elements of S which sum to zero. The 3SUM conjecture this problem away in this paper. There has also been sub-
states that any algorithm solving this problem with K = 3 stantial research on whether the parameters of the match-
requires time n2−o(1) . This conjecture is widely believed making systems in particular games are tuned correctly; a
and has been used to prove lower bounds in many areas sample includes [8, 18, 30].
like computational geometry, graph algorithms, and pattern Our data structures have a fixed-parameter tractability
matching [16, 24, 20]. We will use it to prove lower bounds (FPT) flavor to them. The big-O notation in the times per
for team matchmaking problems. operation hides large, exponential factors in the team size
parameter k. In most applications, k is such a small con-
Theorem 2. Any data structure for the role-restricted
stant that these factors do not preclude our data structures
queueing problem must require n1−o(1) time per insertion or
from being practical. FPT algorithms have been designed
n2−o(1) time per query when k ≥ 3, assuming the 3SUM
for numerous other matching, partitioning, and optimization
conjecture.
problems; see [6] for a survey.
Assuming the more general KSUM conjecture, which as-
serts that the current best known algorithms for KSUM 4. EFFICIENT DATA STRUCTURE FOR
are essentially optimal, we can improve the lower bounds to
nk−2−o(1) time per insertion or nk−1−o(1) time per query. MATCHMAKING
On the scale of the most popular online games, even linear In this section, we prove Theorem 1 by designing an effi-
time per query is computationally intractable. cient game queue data structure. We then discuss the prac-
With Theorem 2 in mind, we look towards approxima- ticality of our data structure.
tions. Since skill ratings are only an approximation of a
Restatement of Theorem 1. There exists a game queue
player’s skill in the first place, an approximation algorithm
which performs insertions and deletions in time ((1+α)k)O(k) ·
is sufficient for many applications. We are able to construct
log(n) and queries in time O(k).
an efficient data structure which achieves a constant factor
approximation for the role-restricted queueing problem. For Our data structure relies on the relationship between the
notational convenience, we define ρ := 2k1/q (1 + α). Notice fairness component dp and the uniformity component vq
that ρ > 1 is a constant defined in terms of the parameters which compose the imbalance function. While games with
of the imbalance function. high values of vq might have high or low values of dp , games
with low values of vq must also have low values of dp . In-
Theorem 3. For any constant k, there is a data struc- tuitively, if there is not much deviation in the skill levels of
ture which achieves a ρ-approximation for the role-restricted a set of players, then it shouldn’t be hard to partition them
queueing problem and takes O(log n) time per operation. into two teams in a fair way. Lemma 1 formalizes this idea.
All of the above results, including the upper bounds, hold (The proofs of Lemmas 1 and 2 can be found in Appendix
for time-sensitive queues as well. We also emphasize that A).
these results hold for any choice of the parameters defining
the imbalance function. Lemma 1. Let S and T be collections of 2k players such
We are able to prove similar types of results for the offline that
 
partitioning problem. We find that the problem is already −1 maxT − minT
(1 + α)(maxS − minS ) < k q ,
hard to solve exactly, even without any role-restriction. 2

1076
where maxS := maxr∈S sr , and similarly for minS , maxT , 5. HARDNESS OF ROLE-RESTRICTED
and minT . Then S can be partitioned into two teams to MATCHMAKING
form a game whose imbalance is less than the imbalance of
In this section, we give the main ideas behind Theorem
any game formed by a partition of T .
2, a lower bound against data structures for role-restricted
queueing. A key ingredient of our lower bound is a stan-
Hence, our data structure can limit its search space to
dard assumption about the hardness of 3SUM. However,
games which are fairly uniform and guarantee that it is look-
this assumption is actually stronger than we need to prove
ing at some of the best games. Lemma 2 shows exactly how
intractability; we will prove the following generalization in-
to limit the search space without eliminating the best games
stead.
from consideration.
Restatement of Theorem 2. Any data structure for
Lemma 2. Let P = {p1 , ..., pn } be a collection of n play-
the role-restricted queueing problem must require nc−1−o(1)
ers such that for all i ∈ [1, n − 1], spi ≤ spi+1 . Then, there
time per insertion or nc−o(1) time per query, assuming the
exists a best game (X, Y ) over the imbalance function with
(2k − 2)SUM problem requires nc−o(1) time to solve.
parameters α, p, and q such that
1 The standard assumption is that 3SUM requires n2−o(1)
1+ q
max (i) − min (i) ≤ 4(1 + α)k . time, but weaker assumptions still prove intractability re-
pi ∈X∪Y pi ∈X∪Y
sults. For instance, even the substantially more modest
Lemma 2 shows that, for each player p in our queue, if p is assumption that 8SUM requires n1.5−o(1) time is sufficient
in the best game, then this game can be found by searching a to prove that the problem is intractable in our applica-
small set of games containing p, and any insertion or deletion tion with k = 5. The fastest known algorithm for (2k −
of a player changes this set of games for only a small number 2)SUM uses a folklore meet-in-the-middle approach and runs
of other players. in O(nk−1 log n) time. Hence, for example, a data structure
for the role-restricted queueing problem for k = 5 where
Proof of Theorem 1. The main idea is to keep a list each operation takes O(n2.99 ) time would already imply a
l = [p1 , ..., pn ] of all players sorted by skill, and a min-heap faster algorithm for 8SUM than is known.
containing one game gpi = (Xpi , Ypi ) per player pi , prior-
itized by f (Xpi , Ypi ). The game gpi will be the most bal- Proof of Theorem 2. (2k − 2)SUM is known to be
anced possible game containing pi such that if pj is in gpi , equivalent to the following problem: given 2k − 2 multi-
1+ 1 sets `1 , . . . , `2k−2 of integers, determine whether there is a
then i ≤ j ≤ i + 4(1 + α)k q . Hence, by Lemma 2, gpi
choice of one from each list which sums to zero [15]. We give
is the best game in which pi is the least skilled player, and
a reduction from this to the offline role-restricted queue-
since we do this for each player, our min-heap is guaranteed
ing problem: given n players, find the best game among
to contain the overall best game. To retrieve a best game,
them. The reduction will be such that if we can solve the
we will simply query the top of the heap.
offline role-restricted queueing problem in T time, then we
To insert a player p into the game queue, simply insert
can solve (2k −2)SUM in O(T ) time. The result then follows
p into l and recompute the new optimal game gpi for the
1+ 1
from noting that if we can solve the role-restricted queueing
4(1+α)k q players pi whose game could have been affected problem in P time per insertion and Q time per query, then
by this insertion. Each of these updates can be done in time we can solve the offline role-restricted queueing problem in
1+ 1
! ! ! O(n · P + Q) time.
4(1 + α)k q 2k We first further transform the (2k − 2)SUM problem. By
O · · 2k = kO(k)
2k k appropriately translating each list, we can assume that `i
only consists of positive integers when i is even, and only
by simply testing all possible games which can be formed consists of negative integers when i is odd, and that the
1+ 1
by each pi and the 4(1 + α)k q players after pi in l. This target sum is still zero. Let m1 , . . . , mk−1 be the first k − 1
1+ 1
yields a total runtime of 4(1 + α)k q (log(n) + kO(k) ) = odd primes. For each 1 ≤ i ≤ k − 1, let bi be the integer
((1 + α)k)O(k) log(n). between 0 and m1 · m2 · · · mk−1 which is 1 (mod mi ) and
Player deletions are performed nearly identically and can 0 (mod mj ) for j 6= i. Multiply every element of all of
be carried out in the same time ((1 + α)k)O(k) log(n). 2 the multisets by m1 · m2 · · · mk−1 , and then add bi to every
element of `2i for each 1 ≤ i ≤ k−1. Finally, create two more
Our data structure as given also works in the time-sensitive
lists `2k−1 and `2k , where `2k−1 consists of only theP number
setting with the same runtime guarantees.
−M , and `2k−1 consists of only the number M − k−1 i=1 bi ,
Notice that while the time bounds given in Theorem 1
where M is a large value to be determined.
grow quickly as a function of k, in practice k tends to be
We now create merged lists for each 1 ≤ i ≤ k defined as
a small constant like 5, and so even the exponential factor
in k is fairly insignificant. Furthermore, parts of the game
`0i := {(a)1/p | a ∈ `2i } ∪ {(−a)1/p | a ∈ `2i−1 }.
optimization step of insertions and deletions to our data
structure have a simple reduction to the PARTITION prob- Now we can interpret these lists as an offline role-restricted
lem3 , which is NP-hard but known to be efficiently solvable queueing instance: Each player is only willing to play one
in practice [21], so an implementation without great worst- role, and list `0i consists of the skill levels of players who
case guarantees but with good practical results is possible. are only willing to play role i. Note that there is a solution
3
The PARTITION problem asks whether a collection of n (X, Y ) with dp (X, Y ) = 0 if and only if the original (2k −
real numbers can be partitioned into two collections of size 2)SUM was an accept instance. Because of our choice of
n/2 with the same sum. the bi s, if dp (X, Y ) = 0, then one team must consist only of

1077
players from `i for i even, and the other must consist only Deletion. The structure supports deleting an object p
of players from `i for i odd. from a list li containing p.
Finally, we need to pick M large enough so that vq (X, Y ) Query. The structure supports a query for a shortest in-
must be very large for any valid choice of X, Y , and dif- terval containing distinct representatives.
ferent choices of which players from `01 , . . . , `0k−1 to pick for In order for these structures to be useful in tracking candi-
the teams hardly change vq (X, Y ), so that the best team date games, we are specifically interested in structures aug-
choice must have dp (X, Y ) = 0 if possible. It is sufficient to mented to have the following property which we call the can-
pick M to be polynomially large in the maximum element didate property. Let ≺ be some ordering of objects by rank
of `1 , . . . , `k−1 . 2 with ties broken consistently. Then, the candidate property
In the hard instance we constructed, each player is only says that, for each permutation of the lists l10 , ..., lk0 , each ob-
willing to play in one role. We note that a modification of ject q1 ∈ l10 contains pointers to objects q2 , ..., qk such that
this proof also gives hard instances when, for instance, each q1 ≺ q2 ≺ ... ≺ qk , each qi ∈ li0 , and sqk − sq1 is mini-
player is willing to play in two roles. mal, unless there exists a q10 , ..., qk−1
0
where qi0 ∈ li0 such that
The hard instances we design involve situations where the q1 ≺ q10 ≺ q20 ≺ ... ≺ qk−1
0
≺ qk , in which case q1 will, in
set of players willing to play in one role looks very different place of a pointer to qk , have a pointer to void.
from the set of players willing to play in the other roles. Intuitively, the candidate property says that the structure
We emphasize that situations like this are not necessarily maintains a collection of k-tuples (q1 , ..., qk ) where each qi
unrealistic, and actually occur in many popular online games in the tuple is distinct and comes from a distinct list. Each
like League of Legends, where some roles are more popular of these tuples represents some interval with distinct rep-
than others among the players at certain skill levels [26]. resentatives, and the specific set of tuples required by the
candidate property will dictate that one of these intervals
6. EFFICIENT APPROXIMATE ROLE- is the smallest interval with distinct representatives. While
it is worth noting that there are other properties one might
RESTRICTED MATCHMAKING consider which offer this guarantee, the candidate property
In the previous section we gave strong evidence that there has the benefit of being simple to maintain in our inductive
is no efficient data structure for the role-restricted queueing construction.
problem. We now present an efficient data structure for the
approximate problem instead. Lemma 3. There is data structure solving the dynamic
Restatement of Theorem 3. There is a data struc- shortest interval containing distinct representatives problem
ture which achieves a ρ-approximation for the role-restricted performing insertions and deletion in time O((k +1)! log(n))
queueing problem and takes time kO(k) log n for insertions and queries in time O(1) and has the candidate property.
and deletions and O(k) time for queries.
At a high level, our data structure is similar to that of The- Our strategy will be to maintain the collections of pointers
orem 1. We will still maintain a heap of candidate games, required by the candidate property and store these collec-
with the guarantee that a game within a ρ factor of opti- tions in a min-heap which prioritizes by sqk − sq1 where for
mal must appear in our heap. Whereas before we kept a some permutation of lists l10 , ..., lk0 , q1 points to q2 , ..., qk and
candidate game for each small window players, now we will q1 ≺ ... ≺ qk .
keep a small collection of candidate games for each player Given this, queries are simple. We need only query the
minimizing the difference in skill between the most and least top of the min-heap to retrieve a shortest interval containing
skilled players while ensuring every role can be filled. In or- distinct representatives, which can be done in O(1) time.
der to do this, we give an efficient datastructure solving the We need only describe how to maintain the collection of
problem we call the dynamic shortest interval with distinct intervals admitting the candidate property upon insertions
representatives problem, and then show how to modify this and deletions in time O((k + 1)! log(n)).
structure in order to solve the approximate role-restricted To maintain insertions and deletions in our structure S,
queueing problem. we will recursively keep k interval structures S1 , ..., Sk each
on a different set of k − 1 of our k lists (assume Si does not
6.1 The Shortest Interval Problem contain li ). Then for each permutation of lists l10 , ..., lk−1 0
in
0
The shortest interval problem is as follows: given k lists Si and each object q1 ∈ l1 which points to q2 , ..., qk−1 for
l1 , ..., lk of n integers, find a pair (a, b) such that for every the given permutation, none of which are void, we keep a
list li , there exists xi ∈ li such that a ≤ xi ≤ b and b − a is pointer to least qk ∈ li satisfying q1 ≺ ... ≺ qk or we point
minimal. to void if some q10 such that q1 ≺ q10 could instead point to
As a slight generalization, the shortest interval containing qk in li for the given permutation of lists.
distinct representatives problem is as follows: given k lists It is straightforward case-work and induction to show that
l1 , ..., lk of n objects p with associated rank sp , find a pair these new pointers can be maintained in time kO(k) log(n)
(a, b) such that there exists distinct objects q1 , ..., qk where upon insertions and deletions. First, observe that by in-
each object’s rank is contained in [a, b], for each i, qi ∈ li , duction, for each permutation of the lists l10 , ..., lk0 and each
and b−a is minimal. We call such an [a, b] a shortest interval q1 ∈ l10 , the q2 , ..., qk pointer to by q1 are each the least pos-
containing distinct representatives. sible choice which q1 could point to and therefore, for each
We consider the dynamic version of this second prob- permutation and list li0 , each qi ∈ li can only be pointed to
lem. That is, we consider data structures maintaining k once. From this and simple case work, we can conclude that
lists l1 , ..., lk with the following operations: for each permutation of lists l10 , ..., lk0 , at most one q1 ∈ l10
Insertion. The structure supports inserting an object p will change its collection of pointers to other players and at
with rank s into a list li . most one q1 ∈ l10 will change any of its pointers to void.

1078
 We can then conclude that during insertions and deletions, we actually need to include all players in a game. Suppose
the number of pointers updated is O(k!k), each requiring we take a (2k − 2)SUM instance and then turn it into an
time at most O(log(n)) to update the heap. This yields the offline partitionining problem instance by converting each
desired runtime of O((k + 1)! log(n)). number into a player with that skill. Then, we add in two
players with skill M , where M is a very large value we pick
6.2 Applying Shortest Intervals later. These two players must be put in the same game, one
We will use a simple modification of the data structure on each team, or else the games they are in will have too
from Lemma 3 to construct our approximation data struc- high a value of dp . Then, since the presence of these players
ture for Theorem 3. makes vq so high, this game will be the game of maximum
Proof of Theorem 3. To approximate the role-restricted imbalance. Hence, we need to assign the remaining players
game queue problem for team size k, we keep a dynamic to minimize dp . A (2k − 2)SUM solution would achieve the
shortest interval containing distinct representatives struc- minimum value dp = 0 if possible.
ture on 2k lists l1 , l10 , ..., lk , lk0 where the objects in li are the Theorem 4 has implications from a parameterized com-
players willing to play role ri and their ranks are their skills. plexity theory perspective which further support that the
li0 will be a copy of li . Observe now that the collections offline partitioning problem is a difficult problem. Parame-
of pointers admitted by the candidate property each repre- terized complexity theory studies the difficulty of problems
sent a collection of players which could form a role-restricted with respect to parameters which are part of the problem
game, as there must be a distinct representative from li and definition or input; see for instance [3] for the relevant no-
li0 for each i, and further more one of these collections is tions.
a collection M minimizing c = maxp∈M (sp ) − minp∈M (sp ). Our proof of Theorem 4 gives a reduction from the (2k −
Lemma 6 (found in Appendix A) shows that for any game 2)SUM problem to the offline partitioning problem. But, the
−1
(X, Y ), we have f (X, Y ) ≥ k q ( 2c ) and Lemma 5 (found in KSUM problem is known to be hard for the complexity class
Appendix A) shows that there is some role-restricted game W [1] from parameterized complexity theory [9]. Our reduc-
(X, Y, m) in M such that f (X, Y ) ≤ (1 + α)c. From this, tion therefore implies that the offline partitioning problem
we see there is some game (X, Y, m) which can be formed is also hard for W [1]. It is widely believed that if a prob-
from M such that f (X, Y ) ≤ 2k1/q (1 + α)OP T = ρ · OP T , lem is W [1]-hard, then it does not have a fixed-parameter
where OP T is the imbalance of a best role-restricted game. tractable algorithm [7]. To illustrate, this means there is
To take advantage of this, we simply store in a min-heap the no constant a such that we could find an algorithm running
O(1)
best game for each collection of pointers. We just showed in time na · 2k for the offline partitioning problem; the
that at least one of the games has imbalance at most ρ·OP T , exponent of n must be growing with k. By comparison, all
so the game at the top of the heap will have imbalance at of the efficient data structure and algorithm running times
most ρ·OP T , showing that queries can be performed in time in this paper are of this form.
O(k). An interesting contrast between the offline partitioning
To perform insertions and deletions, we simply perform problem and the queueing problems is that, in the offline
insertions and deletions into the interval structure and re- partitioning problem, we already get a hardness result with-
compute the optimal game for any collection of pointers that out including role-restrictions, whereas the queueing prob-
changes. This yields a runtime of O((2k+1)! log(n)+O((2k+ lem without role-restrictions has an efficient data structure
1)!4k /k) which is kO(k) log(n). 2 solution. Pesky outlier players in the offline partitioning
Like in the unrestricted case, the dependence on k should problem can make the problem much harder, since we need
not be considered overwhelming, since k is a small constant, to partition every player into a game. Nonetheless, similar to
and the game optimization steps are known to be efficiently the online setting, we can design an efficient approximation
solvable, in practice. algorithm for the offline problem.
Restatement of Theorem 5. For any constant k, there is
7. OFFLINE PARTITIONING PROBLEM a O(n log n) time ρ-approximation algorithm for the offline
Most applications outside of online games are best mod- partitioning problem.
eled as an offline partitioning problem rather than a high-
throughput data structure problem. It seems difficult to Proof. (Sketch) We will find a partition which minimizes
apply results about the queueing problems to the offline par- the maximum value of vq (X ∪ Y ) over all formed games
titioning problem in a black-box way, since finding the ab- (X, Y ). The same argument as in the proof of Theorem 1
solute best games might not be the best way to partition all shows that such a partition will also give a ρ-approximation
of the players. Interestingly, our results in this setting nev- for the offline partitioning problem. We simply order all the
ertheless follow from almost the same ideas as the results players by skill, then partition the players into intervals of
about the queueing problems. Indeed, Theorems 4 and 5 length 2k in this order, and divide each interval into two
follow very quickly from the ideas in the proofs of Theorems teams X, Y in order to minimize dp (X, Y ). It follows from a
2 and 3, respectively, so we just sketch the main ideas. convexity argument that this minimizes the maximum value
of vq . The total runtime is only O(n log n).
Restatement of Theorem 4. The offline partitioning
problem requires time nc−o(1) assuming the (2k − 2)SUM
8. FUTURE WORK
problem requires nc−o(1) time to solve.
Proof. (Sketch) The property that we can take advan- 8.1 Dependences on k
tage of in proving a lower bound for the partitioning prob- The runtimes of all our data structures have exponential
lem, which did not exist for the queueing problem, is that dependences on the team size parameter k. These factors

1079
seem inherent to our approach, which involves solving the Acknowledgments
NP-hard PARTITION problem on many sets of 2k player skill This research was conducted while the authors were at Stan-
levels. Perhaps we could achieve a better dependence on k ford University. The authors thank Amir Abboud, Tim
using a different approach instead. It would be a big break- Roughgarden, Greg Valiant, Virginia Vassilevska Williams,
through to achieve a subexponential dependence on k while and Ryan Williams for heplful conversations.
maintaining a small dependence on n, since when k = n/2,
each query to a game queue is solving the PARTITION prob-
lem. As discussed earlier, the offline partitioning problem is A. IMBALANCE FUNCTION PROPERTIES
hard for the class W [1] from parameterized complexity the- We present several Lemmas about imbalance functions,
ory, which gives further evidence that a much better depen- with the goal of proving Lemmas 1 and 2. We only provide
dence on k is unlikely for these team matchmaking problems. sketches of some more straightforward proofs; full proofs will
Nonetheless, a smaller exponential factor might be possible. appear in the full version.
A big area of current research concerns fixed-parameter
Lemma 4. Let S be a multiset of integers of size 2k, max =
tractable (FPT) algorithms, in which one seeks to reduce the
max(S), and min = min(S). For all p, there exists a parti-
dependence of different parameters in the runtimes of algo-
tion X ∪ Y = S such that dp (X, Y ) ≤ max − min.
rithms. See, for instance, [6] for a survey. Perhaps the tech-
niques from FPT algorithms could be useful here. It is also Actually, we prove a generalization of Lemma 4 which we
worth noting, as we discussed earlier, that the PARTITION will also be able to use in the role-restricted queue setting.
problem can be solved much more quickly in practice than
its exponential runtime suggests. Lemma 5. Let S1 , . . . , Sk be k multisets of two integers
each, and let max = max{S1 ∪· · ·∪Sk } and min = min{S1 ∪
8.2 Objectives in Offline Partitioning · · · ∪ Sk }. Then there is a partition X ∪ Y = S1 ∪ · · · ∪ Sk
such that for each i, one element of Si goes to X and the
In the offline partitioning problem, we choose to minimize
other goes to Y , and such that dp (X, Y ) ≤ max − min.
the imbalance of the most imbalanced game we form. How-
ever, there are other natural objectives we could choose to Proof. We design our partition greedily. Initially X and
minimize instead. One choice would be the sum of the im- Y are empty. For i from 1 up to k, if currently
balances of all the games we form. Another would be the X p X p
x ≤ y , (1)
maximum unhappiness of any player, where unhappiness is
x∈X y∈Y
defined as the ratio of the imbalance of the game they are
assigned, to the imbalance of the best game one could form then we add the bigger of the two elements of Si to X and
which includes them. Analogues of Theorems 4 and 5 should the smaller to Y , and otherwise we add the bigger to Y and
hold for these and other similar objectives as well. smaller to X. Throughout this process, we will always have
!1/p !1/p
8.3 Further Extensions of our Model X p
sx −
X p
sy ≤ max − min
Our model was designed to be very general and capture a x∈X y∈Y
wide variety of applications. Nonetheless, it would be inter-
esting to see what other additional components of imbalance by a straightforward inductive argument, as desired.
functions, or additional constraints on valid games, could
Given a collection of role-restricted players which form a
be included such that the queueing problem can still be ef-
game (X, Y ), Lemma 5 gives us an upper bound on d(X, Y )
ficiently solved. For instance, one might consider a model
as a function of the highest and lowest skills among the
where a player’s skill level changes depending on how many
players. A convexity argument can be used to prove the
of their teammates they have played with before, or even
following lemma, which gives us similar upper and lower
a model where players are not allowed to be matched with
bounds on v(X ∪ Y ).
other players they have played with recently.
Our results still hold for many possible extensions with Lemma 6. Let S be a set of players of size 2k, max =
only minor modifications to the proofs, like extending our max(sp ), and min = min(sp ). Then for all q,
p∈S p∈S
measure of a player’s skill to a multidimensional measure.
For other extensions, like adding in constraints about players
 
1
−q max − min
not being matched together on a team too many times in k ≤ vq (S) ≤ max − min.
2
a row, it may require more work to design efficient data
structures. We note that our lower bounds still hold for any Combining Lemmas 5 and 6 yields almost immediately
extension of imbalance functions or our model, as long as the Lemma 1 from Section 4. It shows that, when k, α, and
most basic formulation of team matchmaking, against which q are fixed constants, there exists a constant c such that
we proved lower bounds, is a special case of the extension. finding a best game for the queueing problem only requires
One component of matchmaking systems for two-player considering games formed from players contained in windows
games that we intentionally do not consider here is net- of c consecutive players sorted by skill. This is formalized
work latency between players. In most team-games, unlike by Lemma 2 in Section 4.
in many two-player games, a central server hosts all matches, Proof of Lemma 2. For any game G consisting of players
and players communicate with this server rather than with 1+ 1
who come from a window of size greater than 4(1 + α)k q ,
each other. This means that latency between players is not 1

an issue. High latency to the server might impact a player, we can create at least 2(1 + α)k q different games consisting
but if it does, this impact is typically consistent between of disjoint players in intervals of the window. Lemma 1
games and is already reflected in the player’s skill level. implies that one of these must be better than G. 2

1080
REFERENCES [16] A. Gajentaan and M. H. Overmars. On a class of
[1] A. Abboud and V. Vassilevska Williams. Popular o(n2 ) problems in computational geometry.
conjectures imply strong lower bounds for dynamic Computational geometry, 5(3):165–185, 1995.
problems. In FOCS 2014, pages 434–443, 2014. [17] M. E. Glickman. The glicko system. Boston
[2] Blizzard Entertainment. The current state of University, 1995.
matchmaking. In Heroes of the Storm Blog, [18] Y. Guo, S. Shen, O. Visser, and A. Iosup. An analysis
http://us.battle.net/heroes/en/blog/20034041/the- of online match-based games. In IEEE International
current-state-of-matchmaking-2-17-2016, Workshop on Haptic Audio Visual Environments and
2016. Games (HAVE) 2012, pages 134–139, 2012.
[3] J. F. Buss and T. Islam. Simplifying the weft [19] R. Herbrich, T. Minka, and T. Graepel. Trueskill(tm):
hierarchy. Theoretical Computer Science, A bayesian skill rating system. In NIPS 2006, pages
351(3):303–313, 2006. 569–576, 2007.
[4] T. Cadwell. Lol matchmaking explained. In League of [20] T. Kopelowitz, S. Pettie, and E. Porat. Higher lower
Legends Forum, http://forums.na. bounds from the 3sum conjecture. In SODA 2016,
leagueoflegends.com/board/showthread.php?t=12029, pages 1272–1287, 2016.
2009. [21] R. E. Korf. Multi-way number partitioning. In IJCAI
[5] S. Cooper, C. S. Deterding, and T. Tsapakos. Player 2009, pages 538–543, 2009.
rating systems for balancing human computation [22] Y. LeJacq. League of legends is fixing one key
games: Testing the effect of bipartiteness. In matchmaking tool. In Kotaku,
International Joint Conference of DiGRA and FDG http://kotaku.com/league-of-legends-is-fixing-one-key-
2016, 2016. matchmaking-tool-1707296218,
[6] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, 2015.
D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. [23] C. Marshall. The dynamic queue conundrum: why riot
Parameterized algorithms, volume 4. Springer, 2015. is wrestling with their community. In PC Gamer,
[7] S. Dantchev, B. Martin, and S. Szeider. Parameterized http://www.pcgamer.com/the-dynamic-queue-
proof complexity. Computational Complexity, conundrum-why-riot-is-wrestling-with-their-
20(1):51–85, 2011. community/,
[8] O. Delalleau, E. Contal, E. Thibodeau-Laufer, R. C. 2016.
Ferrari, Y. Bengio, and F. Zhang. Beyond skill rating: [24] M. Patrascu. Towards polynomial lower bounds for
Advanced matchmaking in ghost recon online. IEEE dynamic problems. In STOC 2010, pages 603–610,
Transactions on Computational Intelligence and AI in 2010.
Games, 4(3):167–177, 2012. [25] J. Paul. By the numbers: Most popular online games
[9] R. G. Downey and M. R. Fellows. Fixed-parameter right now. In Now Loading,
tractability and completeness ii: On completeness for https://nowloading.co/posts/3916216, 2016.
w [1]. Theoretical Computer Science, 141(1-2):109–131, [26] Riot Games. Dynamic queue and the future of league.
1995. In League of Legends Game Updates,
[10] R. Duan and S. Pettie. Linear-time approximation for http://oce.leagueoflegends.com/en/news/game-
maximum weight matching. Journal of the ACM updates/features/dynamic-queue-and-future-league,
(JACM), 61(1):1, 2014. 2016.
[11] J. Edmonds. Maximum matching and a polyhedron [27] P. Sankowski. Maximum weight bipartite matching in
with 0, l-vertices. J. Res. Nat. Bur. Standards B, matrix multiplication time. Theoretical Computer
69(1965):125–130, 1965. Science, 410(44):4480–4488, 2009.
[12] J. Edmonds. Paths, trees, and flowers. Canadian [28] Valve. Competitive skill groups faq. In Counter Strike
Journal of mathematics, 17(3):449–467, 1965. Blog, http://blog.counter-
[13] A. E. Elo. The rating of chessplayers, past and strike.net/index.php/2012/10/5565/,
present. Arco Pub., 1978. 2012.
[14] Y. Emek, S. Kutten, and R. Wattenhofer. Online [29] Valve. Matchmaking. In Dota 2 Blog,
matching: haste makes waste! In STOC 2016, pages http://blog.dota2.com/2013/12/matchmaking/, 2013.
333–344, 2016. [30] M. Véron, O. Marin, and S. Monnet. Matchmaking in
[15] A. Gajentaan and M. H. Overmars. On a class of o multi-player on-line games: studying user traces to
(n2) problems in computational geometry. improve the user experience. In Network and
Computational geometry, 5(3):165–185, 1995. Operating System Support on Digital Audio and Video
Workshop 2014, page 7, 2014.

1081