# Private Blotto: Viewpoint Competition with Polarized Agents

Kate Donahue Department of Computer Science, Cornell University Jon Kleinberg
Departments of Information and Computer Science, Cornell University

###### Abstract

Colonel Blotto games are one of the oldest settings in game theory, originally
proposed over a century ago in [Borel(1921)]. However, they were originally
designed to model two centrally-controlled armies competing over zero-sum
“fronts”, a specific scenario with limited modern-day application. In this
work, we propose and study Private Blotto games, a variant connected to
crowdsourcing and social media. One key difference in Private Blotto is that
individual agents act independently, without being coordinated by a central
“Colonel”. This model naturally arises from scenarios such as activist groups
competing over multiple issues, partisan fund-raisers competing over elections
in multiple states, or politically-biased social media users labeling news
articles as misinformation. In this work, we completely characterize the Nash
Stability of the Private Blotto game. Specifically, we show that the outcome
function has a critical impact on the outcome of the game: we study whether a
front is won by majority rule (median outcome) or a smoother outcome taking
into account all agents (mean outcome). We study how this impacts the amount
of “misallocated effort”, or agents whose choices doesn’t influence the final
outcome. In general, mean outcome ensures that, if a stable arrangement
exists, agents are close to evenly spaced across fronts, minimizing
misallocated effort. However, mean outcome functions also have chaotic
patterns as to when stable arrangements do and do not exist. For median
outcome, we exactly characterize when a stable arrangement exists, but show
that this outcome function frequently results in extremely unbalanced
allocation of agents across fronts.

##  1 Introduction

Over a century ago, before modern game theory was fully established, Émile
Borel proposed a family of zero-sum games inspired by two armies competing
over multiple battlefields [Borel(1921)].

######  Definition 1 (Colonel Blotto).

Two players, $A$ and $B$, are competing over $M$ different _fronts_. The
players have $N_{a},N_{b}$ units of effort at their disposal respectively.
Each player wins a front if they allocate more effort to the front than their
opponent does, and each player wishes to win as many fronts as possible. Are
there Nash stable arrangements of effort over fronts, and if so, which are
they?

The name “Colonel Blotto” derives from the fact that a colonel controls
multiple individual soldiers, which they are able to allocate across the
battlefields in order to serve their overall objective. The Colonel Blotto
game has been the focus of extensive exploration, including variants that
allow for battlefields to have different values, for effort to be allocated
probabalistically, and for smoother utility functions [Golman and Page(2009),
Hart(2008), Osorio(2013)].

The game has also found application in areas far removed from warfare [Merolla
et al.(2005)]. For example, in national politics, two political parties must
decide how to allocate campaign budgets across multiple contested states; in
marketing competition, two competing national retail chains must decide where
to locate individual stores across different metropolitan areas [Merolla et
al.(2005)]. Such situations have the structure of a Colonel Blotto game, with
the political parties or retail chains as the colonels, and the geographic
locations as the front where the competition takes place. Despite the
different contexts, these scenarios all share a fundamental structure, with
two centralized entities organizing effort over multiple fronts.

##### Decentralized conflicts.

By contrast, modern-day conflicts often involve players that may share common
goals, but are not organized by a single actor. Focusing on political
competition, which will be one of our primary motivating domains, there are
many agents interested in influencing voters in an election — activists, local
organizers, political bloggers, everyday voters with large social media
presences — and while they may be collectively backing one of two political
parties, many of them are not being explicitly directed in their actions by
these parties. (A similar type of decentralization can take place in warfare
itself, with guerrilla warfare involving allied groups that nevertheless
choose their actions separately.)

How might we model this type of political viewpoint competition? We could
imagine that there is a large collection of agents, each of whom is interested
in taking part in a conflict with $M$ “fronts.” Each agent controls only one
unit of effort, and can choose to devote that effort to one of the fronts.
There is no centralized “colonel” to direct the agents, but there is an
underlying structure that determines which agents are more or less closely
aligned. In particular, each agent $i$ has a type, which we can think of as a
viewpoint, bias, or political position; this type is represented by a real
number $\beta_{i}$. After each agent chooses a front to participate in, the
outcome of the conflict on each given front is determined by an outcome
function that takes the multiset of types at that front and determines a real-
valued outcome.

We can think of the fronts as issues, for example; each agent can devote
effort to influencing public opinion on one of these issues, and the resulting
value of public opinion on an issue is some aggregation of the viewpoints of
the agents who devote effort to this issue. We will be particularly interested
in two of the most natural outcome functions for aggregating viewpoints in
this setting: the median (in which the outcome on a front is the median of the
types there) and the mean (in which the outcome is the mean of the types).
Agents want the outcomes on each front (even the ones where they don’t
participate) to match their types; thus, each agent experiences a cost equal
to a weighted average of the distances between the outcome on each front and
the agent’s type. (The agent’s payoff is simply the negative of this cost.)
Here the weights in this average can be viewed as representing the relativel
importance of the different fronts.

We will refer to this type of game as Private Blotto; like Colonel Blotto, it
involves conflict over multiple fronts, but it is fundamentally different
because it is designed to model decentralized conflict where each individual
agent makes their own choice about which front to participate in.111In the
military, a _private_ is an enlisted soldier at the base of the hierarchy.
This reflects our setting, which views the individual soldiers as the
strategic actors, rather than the coordinating colonel who commands the army.
We summarize the discussion above in the following definition.

######  Definition 2 (Private Blotto).

Multiple agents are competing as the players in a game over $M$ different
“fronts”. Each agent can choose exactly one front to compete in, and each
agent has a type corresponding to a real number. An outcome function (for
example, the median or mean) determines the outcome value on each front. An
agent’s cost is equal to a weighted average distance between the outcome on
each front and the agent’s type.

For this class of games, we can ask a number of basic questions. Given a set
of agents specified by their types, and a number of fronts, are there Nash
stable arrangements of agents over fronts? And how does the choice of outcome
function affect the existence of stable arrangements?

We will see that these questions are already rich and complex even when all
agents belong to one of two types, just as Colonel Blotto games already
exhibit rich structure with just two colonels. Thus, we will focus much of our
attention on this two-type case, when there are real numbers $\beta_{a}$ and
$\beta_{b}$, and each agent has a type equal to either $\beta_{a}$ or
$\beta_{b}$. In this case, the median outcome function is simply majority
rule: the type with more agents on a given front becomes the outcome for that
front. The mean outcome for a front lies somewhere in the interval between
$\beta_{a}$ and $\beta_{b}$, at a weighted average of these two endpoints
determined by the number of agents of each type at this front.

We now provide some more detail on settings that can be modeled by the Private
Blotto game, and then we give an overview of our results.

###  1.1 Motivating examples

Our Private Blotto formulation finds applicability in numerous modern-day
settings. Here, we will describe a few key application areas in more detail.

Political contests and issue-based activism has historically been an
application area for Colonel Blotto, such as [Merolla et al.(2005)]. We argue
that Private Blotto might even be a more natural fit for this setting. Here,
the $M$ fronts might represent issues or political campaigns, while the agents
might be activist groups or donors, which might share similar goals, but are
unable (for logistical or legal reasons) to coordinate their actions.
Differing types would reflect differing political leanings, which could
reflect a continuum of preferences among groups.

Crowdsourcing on social media has become a growing area of societal and
academic interest in recent years [Yasseri and Menczer(2021), Wojcik et
al.(2022), Allen et al.(2022), Pröllochs(2022)]. Typically, this setting
involves asking social media users to provide labels on different items, such
as whether certain news articles are misinformation or not. In this setting,
the $M$ fronts might be news articles or items that need to be labeled. Each
agent would be a social media user choosing which front to label. Here, player
types might reflect partisan bias, which has been shown to affect how users
select which news articles some users choose to fact-check in Twitter’s
Birdwatch tool [Wojcik et al.(2022), Allen et al.(2022), Pröllochs(2022)]). In
this setting, our model explores dynamics in how voluntary, biased users might
label multiple fronts.

Finally, Private Blotto can also be used in modeling military engagements, the
most traditional application of Colonel Blotto games. In the Private Blotto
formulation, we assume that each agent might be an individual soldier,
guerrilla member, or other actor that is acting without coordination from some
central organizer. In this way, Private Blotto might naturally model more
modern types of asymmetric warfare conflicts. Agents on the same “side”
militarily are of the same type. Agent types allow us to model interactions
between three or more militaries or combatant groups, as it reflects potential
alliances or more nuanced conflicts between different agents.

###  1.2 Overview of results

We are interested in which instances of Private Blotto admit stable
arrangements, by which we mean a choice of front by each agent that forms a
pure Nash equilibrium of the game: no agent has an incentive to unilaterally
change fronts. We also prove results characterizing the properties of stable
arrangements.

We will find it useful to divide our analysis of the model into two main
cases, depending on whether the number of agents is smaller or larger than the
number of fronts. In the motivation from political viewpoint competition,
these cases correspond to different settings, each meaningful: a small number
of fronts relative to the number of agents can correspond to a large
collection of political actors dividing their influence over a small number of
key issues, while a large number of fronts relative to the number of agents
arises in the crowdsourced settings discussed above, where individuals are
asked to label a large universe of news articles or social media posts for
misinformation.

When the number of fronts is small compared to the number of agents, we focus
on the setting in which there are two types $\beta_{a}$ and $\beta_{b}$. Here,
let $N$ be the number of agents of type $\beta_{a}$, and $N_{b}$ be the number
of agents of type $\beta_{b}$. For both the median and the mean outcome
functions, it is natural to ask: for which pairs $(N_{a},N_{b})$ must there
always exist a stable arrangement, and for which pairs is there no stable
arrangement? In the case of the median outcome function, we find that for
every number of fronts $M$, the set of pairs $(N_{a},N_{b})$ that fail to
yield a stable arrangement is finite, and we can exactly characterize this set
of pairs for each $M$ as a certain median-critical region in the
$N_{a}$-$N_{b}$ plane. In the case of the mean outcome function, we show
computationally that the subset of the $N_{a}$-$N_{b}$ plane admitting stable
arrangements has a complex structure that seems to lack a closed-form
description, even with just two fronts with equal weights; we also show that
with two fronts, when a stable arrangement does exist, it must divide the
agents in an almost-proportional fashion.

We prove additional results about the structure of stable arrangements — how
the agents divide across fronts in these arrangements — through the lens of
misallocated effort. If we adopt the normative principle that fronts
(representing issues for public debate) should receive a number of agents
proportional to their weights, then our result for the mean outcome function
shows that there is very little misallocation of effort relative to this
proportionality principle. In contrast, we find that for the median outcome
function, there can be very high levels of misallocation, with stable
arrangements in which large numbers of agents choose fronts with relatively
low weight.

Finally, we consider the case in which there are more fronts than agents;
intuitively, these are settings where the agents have the ability to spread
out arbitrarily thinly across fronts if they so choose, and where some fronts
will inevitably be left empty. Here we identify sufficient conditions for
stable arrangements to exist, and characterize the smallest number of agents
$N$ for which there are instances without stable arrangements. With more
fronts than agents, our results for median and mean are more similar to each
other than they were for small numbers of fronts; this connects intuitively
with the fact that each front will tend to have relatively few agents, leading
to less of a distinction between the behavior of the median and mean. One
difference between the functions is that $N=4$ is the minimum number of agents
for which there can be instances lacking stable arrangements for the mean
outcome function — every instance with at most three agents has a stable
outcome — whereas $N=3$ is the corresponding minimum for the median outcome
function.

##  2 Related works

###  2.1 Colonel Blotto

Colonel Blotto games (first proposed in [Borel(1921)]) is a game theoretic
model where two different players, $A$ and $B$, compete to allocate effort
across multiple “fronts” or “fronts”, which may vary in how much each player
values them. Typically, an player wins a front if they exert more effort
there, and one main question of interest is when Nash equilibria of this
system exist. The literature on Colonel Blotto games is extremely broad, so
will focus on a few of the most relevant papers. Recently, [Ahmadinejad et
al.(2019)] included a polynomial time algorithm for computing equilibria of
the standard Colonel Blotto game, as well as related zero-sum games.

First, we will highlight some of the most commonly-studied variants of Colonel
Blotto games. [Golman and Page(2009)] proposes the “General Blotto” game,
which generalizes Colonel Blotto to permit multiple player types which have
smooth utility functions over fronts and over combinations of fronts.
[Hart(2008)] proposes the “General Lotto” game where each player selects a
probabilistic distribution of effort over each fronts and gets utility given
by the probability that a randomly drawn level of their effort beats their
opponents’ random draw. Separately, [Osorio(2013)] proposes the “Lottery
Blotto” game, where players allocate effort deterministically, but the player
that allocates greater effort to a front doesn’t win deterministically, but
rather probabalistically. This formulation is related to Tullock Contests
Success functions (originally proposed in [Tullock(2001)], also studied in
[Osorio(2013)], [Skaperdas(1996)]) where two players are competing over
contests where they win probabalistically related to their effort (similar to
our mean outcome function). [Goyal and Vigier(2014)] similarly studies contest
functions where fronts are connected in a network and an asymmetric “attacker”
and “defender” are allocating resources across these fronts.

Next, we will highlight the papers that are closest to ours. [Schwartz et
al.(2014a)] gives Nash stability results for the Colonel Blotto game where
players vary in their strength (amount of resources) and fronts vary in their
value, so long as there are at least three fronts with each value. [Kovenock
and Roberson(2012)] studies a limited form of coalitions where exactly two
players $A$ and $B$ may form an alliance before playing a common opponent $C$.
[Boix-Adserà et al.(2020)] proposes and studies the “multi-player Colonel
Blotto game”, which extends the classical Colonel Blotto structure to more
than 2 players. [Anbarcı et al.(2020)] studies a variant of Colonel Blotto
with more than two competing forces, but where fronts are presented
sequentially, rather than simultaneously. [Mazur(2017)] studies Nash
equilibria of Colonel Blotto games with exactly 2 fronts, but where outcome
functions are constrained to be a polynomial function of the difference of
each type’s allocation across the fronts.

In general, Colonel Blotto games and their variants differ from ours in a few
ways. First, rather than assuming the player can control multiple agents, we
assume each agent acts independently (a private citizen as opposed to a
soldier). Because any of these agents could “win”, this dramatically increases
the number of potential outcomes. However, in our second main difference, we
assume that agents have some degree of similarity in their goals: agent $A$
may be more closely aligned with $B$ than $C$, for example. Finally, we study
a more general class of settings than is typically studied in Colonel Blotto,
allowing for arbitrary numbers and valuations of fronts, as well as more
general notions of winning (all or nothing, as well as a more smooth
fractional utility).

###  2.2 Crowdsourcing

The area of crowdsourcing has been studied experimentally and theoretically in
a wide range of papers. Again, we will focus on summarizing those that are
most closely related to ours. Some papers, such as [Hettiachchi et al.(2022)],
[Zhang et al.(2017)] study how to assign different crowd workers to multiple
tasks in order to maximize the expected accuracy of labels.

A more nascent branch of crowdsourcing considers the case where crowd workers
may have agency over which fronts they choose to label. [Zhang and van der
Schaar(2012)] studies reputation-based mechanisms to incentivize crowd workers
to exert effort on fronts that they are assigned. Our model is especially
relevant to fact-checking on social media sites that allow voluntary labels by
(potentially biased) users, such as on Facebook, Wikipedia and Twitter
[Yasseri and Menczer(2021)], especially Twitter’s BirdWatch tool [Wojcik et
al.(2022)]. [Allen et al.(2022)][Pröllochs(2022)] study how partisan
affiliation, among other facts, affects how users on Twitter choose which
tweets to fact check. [Saeed et al.(2022)] compares the accuracy of labels
produced by voluntary, biased crowdsource workers to expert labels.

Our paper differs from most crowdsourcing papers in how it allows crowdsource
workers to act as voluntary, potentially biased agents with some agency over
which fronts they choose to label. Our work also differs stylistically in that
we focus primarily on Nash Equilibria of such systems, an area that has
typically not been explored previously.

##  3 Model

In this section, we make our theoretical model more precise. We assume there
are $M$ _fronts_ that $N$ total _agents_ are competing over. We allow each
front to have different weights or _values_ $w_{i}\in[M]$, which are common
values to each agent. Each agent controls exactly 1 unit of effort: they may
choose which front to compete in, but may not coordinate with other players.
However, agents come in $T$ _types_. Two agents of the same type have
perfectly aligned incentives: when present on the same front, they work
towards the same outcome, and when on different fronts, two agents of the same
type are interchangeable. Each type has a real-valued _bias_
$\beta_{t}\in\mathbb{R}$ that describes how similar or dissimilar it is to
other types. For example, an agent of type $\beta_{1}=1$ is closer to an agent
of $\beta_{2}=-1$ than to $\beta_{3}=5$.

###  3.1 Outcome functions

Once agents are arrayed on a front, the outcome of the battle is governed by
an _outcome function_ $f(\cdot)$. In this paper, we will focus on two types of
outcome functions: _median_ outcome and _proportional_ outcome. Given a set of
agents $S_{i}$ on front $i$, the median outcome function returns the median of
the biases $\text{med}(\\{\beta_{t}\\}\ |\ t\in S_{i})$. If there are an even
number of players on a particular front, then the median function averages
together the middle two biases. Note that for the traditional $T=2$ two-player
Colonel Blotto game, the median outcome function is equivalent to “winner-
take-all”, where whichever type dominates the front wins. For $T>2$ types, the
median outcome means that the front’s outcome is equivalent to the median
$\beta_{j}$, for some $j\in S_{i}$. Every other agent $k$ would experience a
cost given by $\left|\beta_{j}-\beta_{k}\right|$: the magnitude of difference
between their biases.

On the other hand, the mean outcome function returns the mean of the biases:
$\frac{1}{\left|S_{i}\right|}\sum_{t\in S_{i}}\beta_{t}$. This models a
scenario where the final outcome of the front depends on the distribution of
agent biases, not solely the median agent. Again, every agent experiences cost
given by their distance to the final outcome:
$\left|\frac{1}{\left|S_{i}\right|}\sum_{t\in
S_{i}}\beta_{t}-\beta_{k}\right|$.

###  3.2 Agent cost

Even though each agent only participates in a single front, they still have
preferences over all of the fronts. An agent of type $t$ will weight the cost
of each front according to weights $\\{w_{i}\\}$ satisfying
$\sum_{i\in[M]}w_{i}=1$. If a front has no agents on it ($S_{i}=\emptyset$),
then we assume each agent experiences a cost $c\geq 0$ for leaving the front
empty. This cost is independent of agent bias, but is influenced by the
weight. We include this feature to model settings where agents may choose to
leave a front empty (potentially to join a more heavily-weighted or contested
front), but suffer some non-zero cost in doing so. We can write the total cost
as:

$\sum_{i\in[M],\left|S_{i}\right|>0}w_{i}\cdot\left|f(S_{i})-\beta_{t}\right|+\sum_{i\in[M],\left|S_{i}\right|=0}w_{i}\cdot
c$

We will say that an arrangement of agents onto fronts is _stable_ if it
satisfies Nash stability (no agent can unilaterally decrease its cost):

######  Definition 3 (Nash stability).

An arrangement of players on fronts is (Nash) stable in the Private Blotto
game if no agent can reduce its cost by switching from competing in one front
to begin competing in another. Written in notation, this corresponds to
requiring that for every agent of type $t$ with $\beta_{t}\in S_{j}$ on front
$j$ and every other front $k\neq j$,

$\displaystyle w_{j}\cdot\left|f(S_{j})-\beta_{t}\right|+$ $\displaystyle
w_{k}\cdot\left(\left|f(S_{k})-\beta_{t}\right|\cdot\mathbbm{1}[\left|S_{k}\right|>0]+c\cdot\mathbbm{1}[\left|S_{k}\right|=0]\right)$
$\displaystyle\leq
w_{j}\cdot\left(\left|f(S_{j}\setminus\beta_{t})-\beta_{t}\right|\cdot\mathbbm{1}[\left|S_{j}\right|>1]+c\cdot\mathbbm{1}[\left|S_{j}\right|=1]\right)+$
$\displaystyle w_{k}\cdot\left|f(S_{k}\cup\beta_{t})-\beta_{t}\right|$

Nash stability is a natural definition of stability to study in this case
because agents are assumed to model self-interested actors with the ability to
move between fronts in order to reduce their cost. However, Nash stable
solutions are not (in general) guaranteed to exist. In this paper, our main
focus will be characterizing possible Nash stable arrangements.

##  4 More agents than fronts: $N\geq M$

In analyzing the Private Blotto game, we will find it helpful to divide our
analysis into two main regimes: when there are more agents than fronts (this
section), and when there are fewer agents than fronts (Section 5). The setting
where there are more agents than fronts models the case of numerous small
agents competing over a limited set of fronts. As related to the examples in
Section 1.1, it might model the case where there is a small number of physical
fronts in combat, for example, where the number of combatants is much larger.
For political issues, it could represent the case where there is a relatively
small subset of major divisive issues that multiple political actors are
debating. In this section, we will make one assumption in our analysis:

######  Assumption 1.

For the $N\geq M$ setting, we assume agents come in $T=2$ types, $A$ and $B$,
with biases $\beta_{a},\beta_{b}$.

Traditionally, Colonel Blotto games have mainly focused on the two-player
case, which is analogous to our two-type case in Private Blotto [Borel(1921)].
We choose to present the two-type case in this section because it already
admits a surprising amount of richness and complexity, while still being
relatively clean. We relax this assumption in our analysis of the $N<M$ case
in Section 5. Exploring further relaxations of these assumptions would be an
interesting avenue for further analysis of the Private Blotto game. Without
loss of generality, we will always name the two types so that $N_{a}\geq
N_{b}$ (there are more type $A$ than type $B$ players).

Lemma 1 shows why Assumption 1 is helpful. So long as it holds and given
sufficiently high cost for leaving a front empty, agents’ incentives become
independent of bias values $\beta_{a},\beta_{b}$.

######  Lemma 1.

Given Assumption 1, so long as

$c\geq\frac{\max_{i\in M}w_{i}}{\min_{j\in
M}w_{j}}\cdot\left|\beta_{a}-\beta_{b}\right|\cdot\frac{1}{2}$

then no agent wishes to leave a front empty. As a result, agent strategy
becomes independent of biases $\beta_{a},\beta_{b}$ and relies solely on the
number of agents of each type on each front, $\\{a_{i},b_{i}\\},\ i\in[M]$.

Proofs for Lemma 1, as well as for other proofs in this paper, are found in
Appendix A.

Given Lemma 1, all of our results for the remainder of the section hold for
every possible value of biases. For the rest of this section, unless stated
otherwise, we will assume that the preconditions of Lemma 1 hold, which
ensures that no front will be left empty. This assumption is mainly made for
cleanness of analysis: if it is relaxed, then the value of $c$ causes minor
changes in the stable arrangements, primarily for small numbers of agents $N$.

###  4.1 Median outcome

First, in this section we explore Private Blotto with $N\geq M$ with median
outcome function. We can view this setting as exploring the $N_{a},N_{b}$
plane, studying for which values of $N_{a},N_{b}$ a Nash stable arrangement
exists, as well as constructively producing an example of a stable
arrangement. Our results will be a function of the total number of fronts,
$M$, the common weights $\\{w_{i}\\}$ on each of these fronts, as well as
$N_{a},N_{b}$, the number of agents of types $A$ and $B$ respectively. (Recall
that given Lemma 1 all of our results will be independent of the biases
$\beta_{a},\beta_{b}$. )

The first question we will ask is whether the number of unstable “points”
($(N_{a},N_{b})$ pairs) is infinite or finite. Lemma 2 addresses this question
by showing that whenever there are more than twice as many agents as there are
fronts, there always exists a stable arrangement. This directly implies that,
holding the number of fronts $M$ constant, there must only be a finite number
of unstable points.

######  Lemma 2.

If $N_{a}+N_{b}\geq 2\cdot M+1$ (or $N_{a}+N_{b}=2\cdot M$ with $N_{a},N_{b}$
even), then there always exists a stable arrangement.

###### Proof.

We will prove this result constructively by producing an algorithm that always
arrives at a stable arrangement.

Informally, this algorithm works by putting 2 type $B$ players on every front,
stopping once either a) front $M-1$ is reached, or b) all of the type $B$
players have been assigned, or c) there are 3 type $B$ players left (which are
then all assigned to the current front). Then, the algorithm places at least 2
type $A$ players on each item, again stopping once a) front $M$ is reached, or
b) all of the type $A$ players have been allocated, or c) there are 3 type $A$
players left. This is a stable arrangement because for each front, each type
wins by at least 2, so no single agent acting alone can change the outcome.
For a formal description, see Algorithm 1.

If $N_{a}+N_{b}=2\cdot M$ and both $N_{a},N_{b}$ are even, then this algorithm
will put exactly 2 agents on each front. If $N_{a}+N_{b}\geq 2\cdot M+1$ and
both $N_{a},N_{b}$ are even, then this will put at least 2 agents on each
front. If $N_{a}+N_{b}\geq 2\cdot M+1$ and both $N_{a},N_{b}$ are odd, then
$\frac{N_{b}-1}{2}$ fronts will have type $B$ agents and $\frac{N_{a}-1}{2}$
fronts will have type $A$ agents. In total, this covers
$\frac{N_{a}+N_{b}-2}{2}=\frac{N_{a}+N_{b}}{2}-1\geq\frac{2\cdot M+1}{2}-1=M$
fronts, as desired. ∎

Set $a_{i}=b_{i}=0\ \forall i\in[M]$

while  _$\sum_{i\in[M]}b_{i} <N_{b}$_ do

for  _$j\in[M-1]$_ do

if  _$j=M-1$_ then $b_{j}=N_{b}-\sum_{i\in[M]}b_{i},\ j^{*}=j$;

If on last front, allocate all remaining players else if
_$N_{b}-\sum_{i\in[M]}b_{i}\geq 3$_ then $b_{j}=2$;

If at least 3 players left, allocate 2 per front else $b_{j}=3$, $j^{*}=j$;

If there are exactly 3 left, allocate them all and stop

end for

end while

while  _$\sum_{i\in[M]}a_{i} <N_{a}$_ do

for  _$j\in[j^{*}+1,M]$_ do Start with the next front after type $B$ is
allocated

if  _$j=M$_ then $a_{i}=N_{a}-\sum_{i\in[M]}a_{i}$;

If on last front, allocate all remaining players else if
_$N_{a}-\sum_{i\in[M]}a_{i}\geq 3$_ then $a_{j}=2$;

If at least 3 players left, allocate 2 per front else $a_{j}=3$;

If there are exactly 3 left, allocate them all and stop

end for

end while

ALGORITHM 1 Algorithm for stable arrangement, not in median-critical region,
given $N_{a}+N_{b}\geq 2\cdot M+1$ or $N_{a}+N_{b}=2\cdot M$ with
$N_{a},N_{b}$ even.

Lemma 2 described conditions where a stable arrangement exists, but left open
the question of whether it might be possible to be more specifically
characterize when stable arrangements fail to exist, a question that we will
address next. In order to do so, we will need a more specific definition:

######  Definition 4 (Median-critical region).

A set of parameters $(N_{a},N_{b})$ is in the median-critical region if they
satisfy:

$N_{a}+N_{b}\leq 2\cdot M\text{ and }M<N_{a}\text{ and }N_{b}<N_{a}-M$

and symmetrically if the roles of $N_{a},N_{b}$ are reversed.

Lemma 3 immediately shows the importance of this definition: any set of
parameters within the median-critical region must always result in an unstable
arrangement.

######  Lemma 3.

For any set of parameters within the median-critical region with median
outcome function and cost satisfying Lemma 1, there is never a stable
arrangement of agents onto fronts, no matter the weights.

###### Proof sketch.

To start out with, we will describe a few arrangements where a deviation is
always possible. The second half of this proof will show that if we have any
arrangement satisfying the preconditions (parameters within the median-
critical region), then at least one of these cases must occur, meaning that
the arrangement must be unstable.

For notation, we will use $\\{a_{1}\geq b_{1}\\}$ to denote an arrangement
where there are at least as many type $A$ players as type $B$ on front 1, for
example. We will only refer to fronts 1 and 2 for convenience, but these
results hold for any fronts.

$C1:\quad\\{a_{1}=b_{1}-1\\},\\{a_{2}\geq b_{2}+2\\}\text{ or
}\\{b_{1}=a_{1}-1\\},\\{b_{2}\geq a_{2}+2\\}$

This gives an arrangement where type $A$ loses by 1 on front 1 and wins by at
least 2 on front 2. This gives a deviation because any $a$ player from front 2
could move to compete in front 1 and strictly reduce their cost (they now tie
in the first and still win in the second). Similar reasoning holds for the
other case: the type $B$ player from front 2 could move to compete in front 1
and strictly reduce their cost.

$C2:\quad\\{a_{1}=b_{1}\\},\\{a_{2}\geq b_{2}+2\\}\text{ or
}\\{a_{1}=b_{1}\\},\\{b_{2}\geq a_{2}+2\\}$

Here, the players tie on front 1 and type $A$ wins by at least 2 on front 2.
This gives a deviation because any $a$ player from front 2 could move to
compete in front 1 and strictly reduce their cost (they now win front 1 and
still win front 2). Similar reasoning holds for the second case.

$C3:\quad\\{a_{1}\geq b_{1}+1\\},\\{a_{2}=b_{2}+1\\}\text{ or }\\{b_{1}\geq
a_{1}+1\\},\\{b_{2}=a_{2}+1\\}$

Here, type $A$ wins by at least one on front 1 and wins by exactly one on
front 2. This gives a deviation because type $B$ is losing in front 1, and can
move to front 2 where it will tie (and still lose front 1). Similar reasoning
holds for the second case.

The full proof concludes by proving that any $N_{a},N_{b}$ within the median-
critical region must satisfy one of the cases, meaning that the arrangement
must be unstable. ∎

Finally, we address the question of $(N_{a},N_{b})$ pairs with
$N_{a}+N_{b}\leq 2\cdot M$ (so that they are not addressed by Lemma 2), but
which also do not fall in the median-critical region (so they are not
addressed by Lemma 3). Lemma 4 examines this case and constructively shows
that it is always possible to find a stable arrangement of agents onto fronts,
assuming fronts have equal weights.

######  Lemma 4.

Any other number of agents ($N_{a},N_{b}$) with $N_{a}+N_{b}\leq 2\cdot M$
(besides those in the median-critical region) always has a stable arrangement,
_given equal weights_ and cost satisfying Lemma 1.

###### Proof sketch.

We will show constructively that it is possible to create an arrangement
satisfying the following criteria:

  * •

For every front where there is more than 1 agent, type $A$ and type $B$ tie
exactly.

  * •

Every other front has exactly one agent, which can be either type $A$ or type
$B$.

This type of construction is stable by the following reasoning: None of the
single agents can move (they can’t leave an front empty). Additionally, no
agent on an front with multiple agents wishes to leave - they would go from
winning a single front and losing another, to losing on that front and tying
on another, which gives equal costs when weights are equal.

Informally, we will describe how this algorithm works. If $N_{a}+N_{b}=M$,
then we place exactly one agent on each front, which satisfies the
construction criteria.

If $N_{a}+N_{b}>M$, and $N_{a}+N_{b}-M$ is odd, then the algorithm places
equal numbers of players on front 1, and places exactly one player on every
remaining front. On the other hand, if $N_{a}+N_{b}-M$ is even, then the
algorithm places equal numbers of players on fronts 1, places exactly 1 of
each player type on item 2, and then places exactly one player on every
remaining front. The distinction between whether $N_{a}+N_{b}-M$ is even or
odd is necessary to ensure that the total number of players placed sums up to
$N_{a}+N_{b}$. Algorithm 2 describes this algorithm formally. ∎

Set $a_{i}=b_{i}=0\ \forall i\in[M]$

if  _$N_{a}+N_{b}=M$_ then Put exactly 1 player per front

$a_{i}=1\ \forall i\in[N_{a}],b_{i}=1\ \forall i\in[N_{a}+1,M]$

end if

else if  _$N_{a}+N_{b}-M$ is odd_ then

$x=0.5\cdot(N_{a}+N_{b}-M)+1$

$a_{1}=b_{1}=x$ Exact tie on first front

$a_{i}=1\ \forall i\in[2,N_{a}-x+1]$ Put remaining $N_{a}-x$, $N_{b}-x$
players each on a single front.

$b_{i}=1\ \forall i\in[N_{a}-x+2,M]$

else

$x=0.5\cdot(N_{a}+N_{b}-M)$

$a_{1}=b_{1}=x$ Exact tie on first and second front.

$a_{2}=b_{2}=1$

$a_{i}=1\ \forall i\in[3,N_{a}-x+2]$ Put remaining $N_{a}-x-1,N_{b}-x-1$
agents each on a single front.

$b_{i}=1\ \forall i\in[N_{a}-x+3,M]$

ALGORITHM 2 Algorithm for stable arrangement, not in median-critical region,
given $N_{a}+N_{b}\leq 2\cdot M$

Lemma 5, below, demonstrates why the equal weights condition in Lemma 4 is
necessary. If even the weight of one front is even slightly higher than the
weight in another, there exist conditions where no stable arrangement exists.

######  Lemma 5.

Set $M=3,N_{a}=N_{b}=3$, with $w_{1}=w_{2}+\epsilon$ and $w_{2}=w_{3}=w_{4}$,
and and cost satisfying Lemma 1. Then, the arrangement proposed by Lemma 4 is
not stable, and moreover, there is no possible stable arrangement.

###### Proof sketch.

In this proof, we will use the notation

$\\{a,b\\},\\{a,b\\},\\{a\\},\\{b\\}$ (1)

to illustrate that there are 4 fronts in total, two of which with exactly 2
players on it (one of each type), and two fronts with exactly one player (one
front with a single type $A$ player, and one front with a single type $B$
player). Lemma 4 would suggest that the arrangement in Equation 1 would be
stable. If $w_{1}=w_{2}$, then this would be satisfied: none of the singleton
players could move, and none of the $\\{a,b\\}$ players wish to move. If a
player of type $A$ from front 2 moved to compete in front 1, they would go
from experiencing cost $0.5\cdot w_{1}+0.5\cdot w_{2}+w_{3}$ to experiencing
cost: $w_{2}+w_{3}$ which is identical when $w_{1}=w_{2}$. However, when
$w_{1}>w_{2}$, then this move does reduce cost, meaning that the original
arrangement was unstable. The full proof, in Appendix A, completes the proof
by showing that no other possible arrangement is stable. ∎

Finally, Lemma 6 extends Lemma 4 by relaxing the requirement that the front
weights be exactly equal. Instead, this proof shows that it is sufficient to
have the two fronts with highest weight be equal, while no other two fronts
differ in weight by more than a factor of 2. Taken together, these lemmas
characterize the stability of the Private Blotto game with median outcome
function and more agents than fronts.

######  Lemma 6.

[Extension of Lemma 4] Any other number of agents ($N_{a},N_{b}$) with
$N_{a}+N_{b}\leq 2\cdot M$ (besides those in the median-critical region)
always has a stable arrangement, given cost satisfying Lemma 1 and weights in
descending order satisfying $w_{0}=w_{1}\text{ and }w_{i}\leq 2\cdot w_{j}\
\forall i,j\in[M]$.

###  4.2 Mean outcome

Next, in this section we will explore the setting where again there are more
agents than fronts ($N\geq M$), but where instead the mean outcome function is
used. In Section 4.1 we were able to completely (constructively) classify the
stable arrangements for median outcome. By contrast, in this section we will
show that the pattern of stable arrangements is much more chaotic.

First, we explore the most direct question of when a stable arrangement
exists. Even this question turns out to be surprisingly challenging. Figure 1
numerically explores when a stable arrangement exists for $M=2$ fronts222Code
to reproduce figures and numerical examples is available at
https://github.com/kpdonahue/private_blotto. . The axes represent the total
number of type $A$ and type $B$ agents that are present, with a red dot
appearing at point $(N_{a},N_{b})$ if no possible stable arrangement involving
that number of agents exists. The plots in different panels of the figure vary
in the weights given to each of the $M=2$ items. Note that the patterns across
each of the plots seem to vary wildly. For equal weights ($w_{0}=w_{1}=0.5$),
there appears to be a structured pattern in when a stable arrangement exists
and when one does not. As the weights become imbalanced, this pattern
immediately disintegrates, resulting in a series of chaotic clusters.

Figure 1: Figures illustrating when stable arrangements of agents onto fronts
exist for mean outcome. Within each figure, the x-axis gives the total number
of type $A$ players ($N_{a}$), while the y-axis gives the total number of type
$B$ players ($N_{b}$). For clarify, we restrict our attention to $N_{a}\geq
N_{b}$, but identical results would hold for the opposite case. At each point,
a red dot indicates that no stable arrangement exists, otherwise a stable
arrangement does exist. Each figure describes different weights between the
$M=2$ items (e.g. $[0.5,0.5]$ indicates equal weights, $[0.6,0.4$] indicates a
weight of 0.6 on the first item and 0.4 on the second, etc). While the first
figure with equal weights seems to show a specific pattern, this rapidly
disintegrates into a more chaotic picture once weights become even slightly
uneven (see $[0.51,0.49]$ and higher).

However, the unpredictable patterns in Figure 1 actually obscures a deeper
symmetry within the model. As Theorem 1 below shows, if players were allowed
to be allocated fractionally over fronts, then the stable arrangement would
always be exactly equal to proportional allocation over fronts (according to
each front’s weight):

######  Theorem 1.

For $M$ fronts with two types of agents, $A$ and $B$ with mean outcome and $c$
satisfying the conditions of Lemma 1, if players are allowed to be allocated
fractionally over fronts, then the stable arrangement is always given by
$a_{i}=w_{i}\cdot N_{a},b_{i}=w_{i}\cdot N_{b}$.

Note that, in general, Theorem 1 does _not_ imply that stable arrangement for
the standard (integer-valued) Private Blotto games will be close to
proportional. While Theorem 1 can be extended to show that the fractional
Private Blotto game convex, it is known that in general, the minimum of a
convex function, when restricted to integer values may be arbitrarily far from
the minimum of the same convex function over real numbers. However, it turns
out that, for the Private Blotto game with equal weights, it _is_ true that
integer-valued stable arrangements are “close” to proportional. This idea is
formalized in Theorem 2:

######  Theorem 2.

Assume $M$ fronts with equal weights and two types of agents, $A$ and $B$ with
mean outcome and $c$ satisfying the conditions of Lemma 1. Then, any
arrangement that is stable must be “close” to proportional:
$\left|a_{i}-w_{i}\cdot N_{a}\right|\leq 1,\left|b_{i}-w_{i}\cdot
N_{b}\right|\leq 1$ for $i\in[M]$.

###### Proof sketch.

In order to prove this result, we will show that any arrangement that is not
“close” to proportional must have at least one agent that wishes to move. An
arrangement is “close” to proportional if:

$\left|a_{i}-w_{i}\cdot N_{a}\right|\leq 1,\left|b_{i}-w_{i}\cdot
N_{b}\right|\leq 1\ \forall i\in[M]$

At a high level, our proof technique involves finding a “large” front (with
more agents) and a “small” front (with fewer agents). We will then pick
whichever agent type is more represented in the larger front, and move exactly
one agent to the smallest front. We will then give three sets of sufficient
conditions so that this strictly reduces cost for the agent type that moves.
We will then show that if none of the three sufficient conditions are met, all
fronts must be “close” to proportional.

Selecting the fronts: First, we will consider all pairs of fronts $j,k$ such
that $a_{j}+b_{j}\geq a_{k}+b_{k}$. One feature of this pair that we will
consider is the _gap in type prevalence_ , which is given by:

$\text{ type A:
}\frac{a_{j}}{a_{j}+b_{j}}-\frac{a_{k}}{a_{k}+b_{k}}\quad\text{ type B:
}\frac{b_{j}}{a_{j}+b_{j}}-\frac{b_{k}}{a_{k}+b_{k}}$

Note that if one type has positive gap in type prevalence, then the other has
negative gap in type prevalence, because:

$\frac{a_{j}}{a_{j}+b_{j}}-\frac{a_{k}}{a_{k}+b_{k}}=-1+\frac{a_{j}}{a_{j}+b_{j}}+1-\frac{a_{k}}{a_{k}+b_{k}}=\frac{-b_{j}}{a_{j}+b_{j}}+\frac{b_{k}}{a_{k}+b_{k}}$

WLOG, we will assume that type $A$ has positive or 0 gap in type prevalence.
If the gap in type prevalence is 0 (both fronts have exactly equal proportions
of player types), then we will again WLOG assume that type $A$ makes up a
larger share of players, or
$\frac{a_{j}}{a_{j}+b_{j}}=\frac{a_{k}}{a_{k}+b_{k}}\geq\frac{b_{j}}{a_{j}+b_{j}}=\frac{b_{k}}{a_{k}+b_{k}}$.
Given this assumption, we will show that players of type $A$ could always
reduce its cost by moving a single agent from front $j$ to front $k$ (unless
all fronts are _close_ to proportional).

Costs: Type $A$’s cost associated with the fronts $j$ and $k$ is:

$\frac{b_{j}}{a_{j}+b_{j}}+\frac{b_{k}}{a_{k}+b_{k}}$

Its cost associated with these fronts after moving a single agent from $a_{j}$
is given by:

$\frac{b_{j}}{a_{j}+b_{j}-1}+\frac{b_{k}}{a_{k}+b_{k}+1}$

which implies that its cost decreases with this move whenever:

$\frac{b_{j}}{a_{j}+b_{j}}+\frac{b_{k}}{a_{k}+b_{k}}-\frac{b_{j}}{a_{j}+b_{j}-1}-\frac{b_{k}}{a_{k}+b_{k}+1}>0$

Or:

$b_{k}\cdot(a_{j}+b_{j})\cdot(a_{j}+b_{j}-1)>b_{j}\cdot(a_{k}+b_{k})\cdot(a_{k}+b_{k}+1)$
(2)

Equation 2 is the central condition we will be studying in this proof. First,
we will present several sufficient conditions for when Equation 2 is
satisfied, so a player wishes to move. Then, we will show that whenever none
of those sufficient conditions are satisfied, all fronts must be “close” to
proportional.

Sufficient condition 1: Fronts differ by at least 2, positive gap in type
prevalence There are a few conditions where we can immediately see that
Equation 2 is satisfied. First, we divide this equation into two separate
components. The first is given by:

$b_{k}\cdot(a_{j}+b_{j})\geq
b_{j}\cdot(a_{k}+b_{k})\quad\Rightarrow\quad\frac{b_{k}}{a_{k}+b_{k}}\geq\frac{b_{j}}{a_{j}+b_{j}}$
(3)

By prior reasoning, this is satisfied by the assumption that
$\frac{a_{j}}{a_{j}+b_{j}}\geq\frac{a_{k}}{a_{k}+b_{k}}$ as given by type $A$
having positive gap in type prevalence.
Next, we will consider the second component of Equation 2:

$a_{j}+b_{j}-1\geq a_{k}+b_{k}+1\quad\Rightarrow\quad a_{j}+b_{j}\geq
a_{k}+b_{k}+2$ (4)

Note that this is _not_ required by how we selected fronts (all we require is
$a_{j}+b_{j}\geq a_{k}+b_{k}$). However, in the event that both Equation 4
holds, and either Equation 3 or Equation 4 is satisfied strictly, then
Equation 2 holds strictly and type $A$ players have an incentive to move from
front 1 to front 2.
In the full proof, we consider other sufficient conditions where Equation 4
and 3 are not both strictly satisfied, and yet a type $A$ player still wishes
to move from front $j$ to $k$. Finally, we conclude by showing that any
arrangement that fails to satisfy one of the sufficient conditions must have
all fronts having arrangements that are “close” to proportional. ∎

Theorem 2 suggests the following hypothesis, which is that the integer-valued
Private Blotto game with _arbitrary_ weights over fronts still results in
arrangements that are “close” to proportional.

######  Hypothesis 1.

Any stable arrangement in the integer Private Blotto game with mean outcome
function must be “close” to proportional: $\left|a_{i}-w_{i}\cdot
N_{a}\right|\leq 1,\left|b_{i}-w_{i}\cdot N_{b}\right|\leq 1$ for $i\in[M]$.

From numerical simulations Hypothesis 1 appears to hold for our functional
form; we have not found counter-examples computationally, and we conjecture
that it always holds.

###  4.3 Misallocated effort

Finally, in this section we will compare the stable arrangements given either
median or mean outcome functions. In particular, we will consider the question
of how “bad” stable arrangements might be. This question has been formalized
in a variety of ways in previous papers, including Price of Anarchy or Price
of Stability [Koutsoupias and Papadimitriou(2009), Anshelevich et al.(2008)].
For example, in a congestion routing game, Price of Anarchy would measure the
total congestion for all players in the worst-case stable arrangement, as
compared to the arrangement that minimizes total congestion.

However, Private Blotto is modeling a fundamentally different game. In the
political debate scenario, for example, Private Blotto is modeling different
political actors competing over topics for which they have truly different
viewpoints. In this case, society doesn’t necessarily have a concept of which
outcome is “right”. However, we might have normative preferences over how we
wish these debates to unfold. One concrete example might be something like
“political topics should be debated in rough proportion to how important they
are to all actors”. For example, if a legislative body spends a week debating
the naming of a bridge and only a morning debating the contents of a vital
spending bill, we might view that allocation of effort as wasteful. This
intuition of “misallocated effort” is formalized below:

######  Definition 5.

Given an arrangement of agents onto fronts, we say it has “misallocated
effort” given by the amount of agents that is above or below allocation equal
to the weights. That is, misallocated effort is given by:

$\sum_{i\in[M]}\left|w_{i}\cdot N_{a}-a_{i}\right|+\left|w_{i}\cdot
N_{b}-b_{i}\right|$

One question we will explore is the maximum possible misallocated effort,
among any stable arrangements. The results of Lemma 1 require that each front
has at least one agent, which Lemma 7 uses to give an immediate upper bound to
misallocated effort.

######  Lemma 7.

Given $c$ satisfying Lemma 1, each front to have at least one agent, which
means that (regardless of the outcome function used), misallocated effort is
upper bounded by $N_{a}+N_{b}-M$.

Next, we will obtain tighter bounds for mean and median outcome functions,
respectively. First, Lemma 8 shows that a much tighter bound on misallocated
effort is possible for mean outcome functions.

######  Lemma 8.

For mean outcomes, if Hypothesis 1 holds then misallocated effort is upper
bounded by $2\cdot M$.

###### Proof.

This is a direct consequence of Hypothesis 1:

$\sum_{i\in[M]}\left|w_{i}\cdot N_{a}-a_{i}\right|+\left|w_{i}\cdot
N_{b}-b_{i}\right|\leq\sum_{i\in[M]}2=2\cdot M$

∎

Next, Lemma 9 shows that worst-case misallocated effort can be much higher for
the median outcome function, especially in the case where there are many more
agents than fronts. Lemma 7 tells us that misallocated effort is likely to be
highest for large $N_{a},N_{b}$. Lemma 9 looks at this specific case and shows
that misallocated effort could be as high as
$N_{a}\cdot\left(1-\frac{1}{M}\right)$, which can be much greater than the
$2\cdot M$ bound given in Lemma 8.

######  Lemma 9.

For median outcomes, worst-case misallocated effort is _lower_ -bounded by
$0.25\cdot N$, given $N=N_{a}+N_{b}\geq 2\cdot M$.

###### Proof.

We rely on the stable arrangements found in the proof of Lemma 4. For
$N_{a}+N_{b}\geq 2\cdot M$, the arrangement starts by placing 2 of each of
type $B$ players on each front, up until either we run out of type $B$ players
or reach the $M-1$st front. We then place the type $A$ on the remaining
fronts. In the case that $\frac{N_{b}}{2}\geq M-1$, this implies that a single
front has $N_{a}$ type $A$ agents. The preconditions of Lemma 4 assume equal
weights $w_{i}$, which means that misallocated effort is lower bounded by
$N_{a}-\frac{N_{a}}{M}=N_{a}\cdot\left(1-\frac{1}{M}\right)$ Because we have
required $N_{a}\geq N_{b}$ and $M\geq 2$, this bound is at least: $0.5\cdot
N\cdot\left(1-0.5\right)=0.25\cdot N$. ∎

Overall, the results of this analysis imply that mean outcome functions,
rather than median ones, give sharper guarantees that any stable arrangement
that exists will result in agents roughly arranging themselves across fronts
in proportion to their overall value.

##  5 Fewer agents than fronts: $N<M$

In Section 4, we examined the case with more agents than fronts: $N\geq M$. In
this section, we will explore the other possibility, with fewer agents than
fronts. A motivating example for this scenario could be voluntary
crowdsourcing on a social media platform, such as Twitter’s BirdWatch [Wojcik
et al.(2022)]. [Allen et al.(2022)][Pröllochs(2022)]. Here, there might be
many more relevant items (e.g. news articles or tweets) than there are active
labelers. Our goal here is to model the set of stable arrangements, again
comparing median and mean outcome functions.

In this section, we will drop Assumption 1, as all of our results extend
easily to arbitrary numbers of agent types $T>2$. Because $N<M$, some fronts
will inevitably need to be left empty. Because of this, we will drop the lower
bound in Lemma 1 and allow the cost for leaving a front empty $c$ to be set
arbitrarily. Since Lemma 1 no longer applies, in this section we will see that
agent biases $\\{\beta_{i}\\}$ are relevant for agents’ strategies.

At a high level, Section 4 showed a wide divergence in behavior between median
and mean outcome functions. In this section, we will show that the setting of
$N<M$ gives much more similar results between the two outcome functions,
though with some differences. The intuition is that both median and mean
outcome functions behave identically for fronts with only 1 or 2 agents
present. Because there are relatively few agents, compared to the number of
fronts, most arrangements will have 1 or 2 agents per front, unless $c$ is
very small or differences in biases between types is very large.

First, we analyze the most natural arrangement: where there is exactly one
agent on each of the most valuable $N$ fronts, with the remaining ones left
empty. Lemma 10 gives conditions where this type of arrangement is stable,
showing that these conditions are identical for both median and mean outcome
functions.

######  Lemma 10.

Assume that $N<M$. WLOG, relabel the fronts in descending order of weight, so
$w_{1}\geq w_{2}\geq\ldots w_{M}$. Then, arrange each agent on each front in
descending order of $\left|\beta_{i}\right|$: that is, absolute value of bias,
so that
$\left|\beta_{1}\right|\geq\left|\beta_{2}\right|\ldots\left|\beta_{N}\right|$.
Define $\beta_{i^{*}}$ to be the first element that has an opposite sign from
$\beta_{1}$. (If they are all the same sign, then set $i^{*}=N$). Then, place
exactly one agent on each front in descending order of bias magnitude and
weight. This arrangement is stable (for either median or mean outcome
functions) so long as:

$\left|\beta_{1}-\beta_{i*}\right|\leq 2\cdot\frac{w{{}_{N}}}{w_{1}}\cdot c$

Next, Lemma 11 studies another natural scenario: where there are exactly two
players and at least two fronts. Here, the lemma shows that for both median
and mean outcome functions, players either both prefer to compete in the same
front, or else both prefer to compete in separate fronts.

######  Lemma 11.

For $N=2$, $M\geq 2$ with equal weights and either median or mean outcome
functions, the two players either both prefer competing on the same front or
both prefer each competing on separate fronts. Because their preferences are
perfectly aligned, this implies that one of the two arrangements is always
stable.

###### Proof.

Consider two players with bias $\beta_{a},\beta_{b}$. The player of type $A$
get lower cost when competing in separate fronts whenever:

$\displaystyle\left|f(\\{\beta_{a},\beta_{b}\\})-\beta_{a}\right|+c$
$\displaystyle\leq 0+\left|f(\beta_{b})-\beta_{a}\right|$ $\displaystyle c$
$\displaystyle\leq 0.5\cdot\left|\beta_{b}-\beta_{a}\right|$

On the other hand, the player of type $B$ gets lower cost when competing in
separate fronts whenever:

$\displaystyle\left|f(\\{\beta_{a},\beta_{b}\\})-\beta_{b}\right|+c$
$\displaystyle\leq\left|f(\beta_{a})-\beta_{b}\right|+0$ $\displaystyle
0.5\cdot\left|\beta_{b}-\beta_{a}\right|+c$
$\displaystyle\leq\left|\beta_{b}-\beta_{a}\right|$

These terms are exactly equivalent, proving the result. ∎

###  5.1 Median outcome

The previous section described specific conditions for when a Nash stable
arrangement exists. Next, we will explore the complementary condition by
showing when (for median outcome functions), no stable arrangement exists.
Lemma 12 gives a constructive example of settings where any possible
arrangement of agents onto fronts is unstable.

######  Lemma 12.

For any $N,M$ with such that $2<N<M$, with median outcome, there exists biases
$\\{\beta_{i}\\}$ and costs $c$ such that no NE exists.

###### Proof sketch.

Set parameters as follows:

  * •

$M$ fronts, all with equal weight.

  * •

$N$ players, with given biases: 1 with bias $1$, and $N-1$ with bias $-0.5$.

  * •

Cost of 0.3 for leaving an front empty.

The full proof considers any possible arrangement of these players, at least
one can reduce its total cost by moving. ∎

###  5.2 Mean outcome

Next, we will consider the case with mean outcome function. Lemma 13 follows a
similar approach to Lemma 12, showing constructively that there exist
parameters where no stable arrangement exists. However, as compared to Lemma
12, it has the added requirement of $N\geq 4$.

######  Lemma 13.

For any $N,M$ such that $4\leq N<M$, with mean outcome, there exists
parameters such that no NE exists.

###### Proof sketch.

The parameters are set identically to in Lemma 12, except with a cost of
$c_{u}\in(0.125,0.25)$ for leaving an front empty. The proof follows similarly
to that for Lemma 12, exploring multiple possible arrangements and showing
that none can be stable. ∎

The mean outcome function case explored in Lemma 13 is not exactly analogous
to the median case in Lemma 12: there is a gap at $N<4$ players. Lemma 14
complete this gap by showing that the gap in Lemma 13 is inevitable: any
possible set of $N=3$ agents must have a stable arrangement, given mean
outcomes and equal weights. Note that the case with equal weights is the most
interesting one: if weights are allowed to differ, then a stable arrangement
can easily be found by setting one front to have extremely high weight,
resulting in all agents competing in that front.

######  Lemma 14.

For $N=3,M\geq 4$ with mean outcome and equal weights, there is always a
stable point.

###### Proof sketch.

There are five possible arrangements of 3 agents:

$\\{a\\},\\{b\\},\\{c\\}\quad\\{a,b\\},\\{c\\}\quad\\{a,c\\},\\{b\\}\quad\\{b,c\\},\\{a\\}\quad\\{a,b,c\\}$

We will use the notation

$\\{a,b\\},\\{\\}\rightarrow_{a}\\{a\\},\\{b\\}$

to mean that a player of type $A$ gets strictly lower cost when it leaves a
front it is competing in with type $B$ to compete in an empty front. We will
say $\\{a,b\\},\\{\\}\not\rightarrow_{a}\\{a\\},\\{b\\}$ when the player of
type $A$ does not get strictly lower cost in $\\{a\\},\\{b\\}$ and say
$\\{a\\},\\{b\\}\rightarrow_{a}\\{a,b\\},\\{\\}$ when the player of type $A$
gets strictly lower cost in $\\{a,b\\}$. Often, to be concise, we will drop
$\\{\\}$ terms and simply write $\\{a,b\\}\rightarrow_{a}\\{a\\},\\{b\\}$ as
the second front is left empty on the lefthand side.

In this proof, we will use the results of Lemma 11 to show that for any pair
of agents, they either would both prefer to be competing in the same front or
else both prefer to be competing in different fronts. Next, we will show that
if any two pairs of agents prefer competing in the same front (as opposed to
competing in different fronts), then it is the two agents with most dissimilar
biases (e.g. $i,j$ given
$\max_{i,j\in\\{a,b,c\\}}\left|\beta_{i}-\beta_{j}\right|$). In order to show
this, we will write out the cost that an agent of type $A$ gets for every
possible arrangement. Because agents are interchangeable, this gives costs for
every other agent in different arrangements, up to relabeling.

$\displaystyle\\{a\\},\\{b\\},\\{c\\}\quad$
$\displaystyle\left|\beta_{b}-\beta_{a}\right|+\left|\beta_{c}-\beta_{a}\right|$
$\displaystyle\\{a,b\\},\\{c\\}\quad$ $\displaystyle
0.5\cdot\left|\beta_{b}-\beta_{a}\right|+\left|\beta_{c}-\beta_{a}\right|+c$
$\displaystyle\\{a,c\\},\\{b\\}\quad$ $\displaystyle
0.5\cdot\left|\beta_{a}-\beta_{c}\right|+\left|\beta_{b}-\beta_{a}\right|+c$
$\displaystyle\\{b,c\\},\\{a\\}\quad$ $\displaystyle
0.5\cdot\left|\beta_{b}+\beta_{c}-2\cdot\beta_{a}\right|+c$
$\displaystyle\\{a,b,c\\}\quad$
$\displaystyle\frac{1}{3}\cdot\left|\beta_{b}+\beta_{c}-2\cdot\beta_{a}\right|+2\cdot
c$

The second and third lines in the equations above show us that

$\\{a,b\\},\\{c\\}\rightarrow_{a}\\{a,c\\},\\{b\\}$

exactly whenever:

$0.5\cdot\left|\beta_{b}-\beta_{a}\right|+\left|\beta_{c}-\beta_{a}\right|+c>0.5\cdot\left|\beta_{a}-\beta_{c}\right|+\left|\beta_{c}-\beta_{a}\right|+c$
$\left|\beta_{c}-\beta_{a}\right|>\left|\beta_{b}-\beta_{a}\right|$

which is whenever $\beta_{c}$ is further from $\beta_{a}$ than $\beta_{b}$ is.
In this analysis, WLOG we will say that $\beta_{b},\beta_{c}$ are the most
dissimilar (because agents are interchangeable, this is true up to
relabeling). Note that this implies that $\\{a,c\\},\\{b\\}$ and
$\\{a,b\\},\\{c\\}$ can never be stable, because both $b,c$ would prefer being
together to being with $a$.

Next, we can analyze some cases:
Case 1: If the $\\{b,c\\},\\{a\\}\rightarrow_{b,c}\\{a\\},\\{b\\},\\{c\\}$,
then $\\{a\\},\\{b\\},\\{c\\}$ is stable.
We know from our prior reasoning that if the two most dissimilar players do
not wish to compete in the same front, then no other pair of players do. This
means that the arrangement with one agent per front is stable.

Case 2: If:

$\\{a\\},\\{b\\},\\{c\\}\rightarrow_{b,c}\\{b,c\\},\\{a\\}\text{ and
}\\{b,c\\},\\{a\\}\not\rightarrow_{a}\\{a,b,c\\}$

then $\\{b,c\\},\\{a\\}$ is stable. This is because the $\\{b,c\\}$ pair
doesn’t wish to split up and the type $A$ player doesn’t wish to join.

Case 3: If no player wishes to leave $\\{a,b,c\\}$ to compete in an empty
front, then $\\{a,b,c\\}$ is stable.
This is true simply by the statement: if no player wishes to move, then this
arrangement must be stable.

Case 4: In this case, we will assume that:

$\\{a\\},\\{b\\},\\{c\\}\rightarrow_{b,c}\\{b,c\\},\\{a\\}\text{ and
}\\{b,c\\},\\{a\\}\rightarrow_{a}\\{a,b,c\\}$

We will also assume that at least one of $b,c$ wishes to leave $\\{a,b,c\\}$.
WLOG, we will assume it is $c$ (up to relabeling). Note that this implies none
of these arrangements can be stable:

$\\{a\\},\\{b\\},\\{c\\}\quad\\{b,c\\},\\{a\\}\quad\\{a,b,c\\}$

Additionally, by our prior reasoning, if players $b,c$ prefer competing
together to separate, then we know that no other pair can be stable:

$\\{a,b\\},\\{c\\}\quad\\{a,c\\},\\{b\\}$

The cycle that is given by this set of patterns is given by:

$\\{b,c\\},\\{a\\}\rightarrow_{a}\\{a,b,c\\}\rightarrow_{c}\\{a,b\\},\\{c\\}\rightarrow_{b,c}\\{a\\},\\{b,c\\}$

We will show that this type of cycle cannot exist.

Note that the first move occurs when:

$\displaystyle\left|\frac{\beta_{b}+\beta_{c}}{2}-\beta_{a}\right|$
$\displaystyle>\left|\frac{\beta_{b}+\beta_{c}+\beta_{a}}{3}-\beta_{a}\right|+c$
$\displaystyle\frac{1}{6}\cdot\left|\beta_{b}+\beta_{c}-2\beta_{a}\right|$
$\displaystyle>c$

The second move occurs when:

$\displaystyle\left|\frac{\beta_{a}+\beta_{b}+\beta_{c}}{3}-\beta_{c}\right|+c$
$\displaystyle>\left|\frac{\beta_{a}+\beta_{b}}{2}-\beta_{c}\right|$
$\displaystyle c$
$\displaystyle>\frac{1}{6}\cdot\left|\beta_{a}+\beta_{b}-2\beta_{c}\right|$

And the third move occurs when:

$\displaystyle
0.5\cdot\left|\beta_{a}-\beta_{b}\right|+\left|\beta_{c}-\beta_{b}\right|$
$\displaystyle>\left|\beta_{a}-\beta_{b}\right|+0.5\cdot\left|\beta_{c}-\beta_{b}\right|$
$\displaystyle 0.5\cdot\left|\beta_{b}-\beta_{c}\right|$
$\displaystyle>0.5\cdot\left|\beta_{a}-\beta_{b}\right|$

Putting these together, this implies:

$\left|\beta_{a}+\beta_{b}-2\beta_{c}\right|<\left|\beta_{b}+\beta_{c}-2\beta_{a}\right|$
(5) $\left|\beta_{a}-\beta_{b}\right|<\left|\beta_{b}-\beta_{c}\right|$ (6)

In the full proof, we complete our analysis by showing that it is impossible
to set $\beta_{a},\beta_{b},\beta_{c}$ so as to satisfy both of these
inequalities simultaneously. ∎

##  6 Discussion

In this paper, we have proposed and analyzed the Private Blotto game, a multi-
player game involving competition over fronts with different values. We
focused on the impact of the outcome function on whether Nash stable
arrangements exist. For the case with more agents than fronts, in Section 4 we
showed the existence of a median-critical set of parameters such that no
stable arrangement is possible within this set. We additionally showed
constructively that a stable arrangement is always possible for any set of
parameters outside of the median-critical set (assuming weights on fronts that
are equal or bounded in difference). However, stable arrangements may involve
high degrees of “misallocated effort” where agents are distributed across
fronts in ways that are far proportional to the front’s value. For mean
outcome rules, we showed that any stable arrangement must involve bounded
misallocated effort, but patterns in which stable arrangement exist and fail
to exist do not have a clean theoretical characterization. In Section 5 we
analyzed the complementary case with fewer agents than fronts. In this case,
median and mean outcome functions have much more similar results. For both, we
constructively show conditions for the existence of a stable solution, as well
as showing that there exist parameters such that no stable arrangement can
exist.

While in this work we addressed the primary question of Nash stability, there
are multiple interesting extensions into the Private Blotto game. One natural
extension could be to explore a combined Colonel Blotto and Private Blotto
game, with some of the “types” being centrally-coordinated Colonel Blotto with
others being distributed Private Blotto. The Private Blotto players would be
strictly weaker than the Colonel Blotto ones, but might be able to perform
competitively given increased numbers of agents. Another generalization of
Private Blotto could allow agents to coordinate with up to $N\geq 1$ other
agents. For example, for $N=2$, an arrangement would fail to be Nash stable if
two agents, working together, could move and improve both of their utility.
This modification would only make Nash stability harder to achieve, but could
be interesting to analyze. Finally, some Colonel Blotto games allow for
players to differ in their subjective valuations or weights for each front -
if, for example, certain issues are more valuable to certain political groups
than to others [Schwartz et al.(2014b)]. Extending this model could allow for
interesting variations in patterns of Nash stability.

#### Acknowledgements

This work was supported in part by a Simons Investigator Award, a Vannevar
Bush Faculty Fellowship, MURI grant W911NF-19-0217, AFOSR grant
FA9550-19-1-0183, ARO grant W911NF19-1-0057, a Simons Collaboration grant, a
grant from the MacArthur Foundation, and NSF grant DGE-1650441. We are
extremely grateful to Maria Antoniak, Sarah Dean, Jason Gaitonde, and the AI,
Policy, and Practice working group at Cornell for invaluable discussions.

## References

  * [1]
  * [Ahmadinejad et al.(2019)] AmirMahdi Ahmadinejad, Sina Dehghani, MohammadTaghi Hajiaghayi, Brendan Lucier, Hamid Mahini, and Saeed Seddighin. 2019.  From duels to battlefields: Computing equilibria of Blotto and other games.  _Mathematics of Operations Research_ 44, 4 (2019), 1304–1325.
  * [Allen et al.(2022)] Jennifer Allen, Cameron Martel, and David G Rand. 2022\.  Birds of a Feather Don’t Fact-Check Each Other: Partisanship and the Evaluation of News in Twitter’s Birdwatch Crowdsourced Fact-Checking Program. Association for Computing Machinery, New York, NY, USA.  https://doi.org/10.1145/3491102.3502040
  * [Anbarcı et al.(2020)] Nejat Anbarcı, Kutay Cingiz, and Mehmet S Ismail. 2020\.  Proportional resource allocation in dynamic n-player Blotto games.  _arXiv preprint arXiv:2010.05087_ (2020).
  * [Anshelevich et al.(2008)] Elliot Anshelevich, Anirban Dasgupta, Jon Kleinberg, Éva Tardos, Tom Wexler, and Tim Roughgarden. 2008.  The price of stability for network design with fair cost allocation.  _SIAM J. Comput._ 38, 4 (2008), 1602–1623.
  * [Boix-Adserà et al.(2020)] Enric Boix-Adserà, Benjamin L Edelman, and Siddhartha Jayanti. 2020.  The multiplayer colonel blotto game. In _Proceedings of the 21st ACM Conference on Economics and Computation_. 47–48.
  * [Borel(1921)] Emile Borel. 1921\.  La théorie du jeu et les équations intégralesa noyau symétrique.  _Comptes rendus de l’Académie des Sciences_ 173, 1304-1308 (1921), 58.
  * [Golman and Page(2009)] Russell Golman and Scott E Page. 2009.  General Blotto: games of allocative strategic mismatch.  _Public Choice_ 138, 3 (2009), 279–299.
  * [Goyal and Vigier(2014)] Sanjeev Goyal and Adrien Vigier. 2014.  Attack, Defence, and Contagion in Networks.  _The Review of Economic Studies_ 81, 4 (07 2014), 1518–1542.  https://doi.org/10.1093/restud/rdu013 arXiv:https://academic.oup.com/restud/article-pdf/81/4/1518/18393865/rdu013.pdf
  * [Hart(2008)] Sergiu Hart. 2008\.  Discrete Colonel Blotto and general lotto games.  _International Journal of Game Theory_ 36, 3 (2008), 441–460.
  * [Hettiachchi et al.(2022)] Danula Hettiachchi, Vassilis Kostakos, and Jorge Goncalves. 2022.  A survey on task assignment in crowdsourcing.  _ACM Computing Surveys (CSUR)_ 55, 3 (2022), 1–35.
  * [Koutsoupias and Papadimitriou(2009)] Elias Koutsoupias and Christos Papadimitriou. 2009.  Worst-case equilibria.  _Computer science review_ 3, 2 (2009), 65–69.
  * [Kovenock and Roberson(2012)] Dan Kovenock and Brian Roberson. 2012.  Coalitional Colonel Blotto games with application to the economics of alliances.  _Journal of Public Economic Theory_ 14, 4 (2012), 653–676.
  * [Mazur(2017)] Kostyantyn Mazur. 2017\.  A Partial Solution to Continuous Blotto.  _arXiv preprint arXiv:1706.08479_ (2017).
  * [Merolla et al.(2005)] Jennifer Merolla, Michael Munger, and Michael Tofias. 2005\.  In play: A commentary on strategies in the 2004 us presidential election.  _Public Choice_ 123 (2005), 19–37.
  * [Osorio(2013)] Antonio Osorio. 2013\.  The lottery Blotto game.  _Economics Letters_ 120, 2 (2013), 164–166.  https://doi.org/10.1016/j.econlet.2013.04.012
  * [Pröllochs(2022)] Nicolas Pröllochs. 2022\.  Community-based fact-checking on Twitter’s Birdwatch platform. In _Proceedings of the International AAAI Conference on Web and Social Media_ , Vol. 16. 794–805.
  * [Saeed et al.(2022)] Mohammed Saeed, Nicolas Traub, Maelle Nicolas, Gianluca Demartini, and Paolo Papotti. 2022\.  Crowdsourced Fact-Checking at Twitter: How Does the Crowd Compare With Experts?. In _Proceedings of the 31st ACM International Conference on Information & Knowledge Management_. 1736–1746.
  * [Schwartz et al.(2014a)] Galina Schwartz, Patrick Loiseau, and Shankar S Sastry. 2014a.  The heterogeneous colonel blotto game. In _2014 7th international conference on NETwork Games, COntrol and OPtimization (NetGCoop)_. IEEE, 232–238.
  * [Schwartz et al.(2014b)] Galina Schwartz, Patrick Loiseau, and Shankar S. Sastry. 2014b.  The heterogeneous Colonel Blotto game. In _2014 7th International Conference on NETwork Games, COntrol and OPtimization (NetGCoop)_. 232–238.
  * [Skaperdas(1996)] Stergios Skaperdas. 1996\.  Contest success functions.  _Economic theory_ 7 (1996), 283–290.
  * [Tullock(2001)] Gordon Tullock. 2001\.  _Efficient Rent Seeking_.  Springer US, Boston, MA, 3–16.  https://doi.org/10.1007/978-1-4757-5055-3_2
  * [Wojcik et al.(2022)] Stefan Wojcik, Sophie Hilgard, Nick Judd, Delia Mocanu, Stephen Ragain, MB Hunzaker, Keith Coleman, and Jay Baxter. 2022\.  Birdwatch: Crowd Wisdom and Bridging Algorithms can Inform Understanding and Reduce the Spread of Misinformation.  _arXiv preprint arXiv:2210.15723_ (2022).
  * [Yasseri and Menczer(2021)] Taha Yasseri and Filippo Menczer. 2021.  Can the Wikipedia moderation model rescue the social marketplace of ideas?  (2021).
  * [Zhang et al.(2017)] Jing Zhang, Victor S Sheng, Qianmu Li, Jian Wu, and Xindong Wu. 2017.  Consensus algorithms for biased labeling in crowdsourcing.  _Information Sciences_ 382 (2017), 254–273.
  * [Zhang and van der Schaar(2012)] Yu Zhang and Mihaela van der Schaar. 2012.  Reputation-based incentive protocols in crowdsourcing applications. In _2012 Proceedings IEEE INFOCOM_. 2140–2148.  https://doi.org/10.1109/INFCOM.2012.6195597

##  Appendix A Proofs

See 1

###### Proof.

In other words, we want to ensure that for any player $t$, the cost of
competing in any front $i$ (leaving any other front $j$ empty) is higher than
the cost of leaving front $i$ to competing in front $j$ alone:

$w_{i}\cdot\left|f(S_{i})-\beta_{t}\right|+w_{j}\cdot c\geq
w_{i}\cdot\left|f(S_{i}\setminus\beta_{t})\right|+w_{j}\cdot 0$

First, we will analyze the case with mean outcome function. For an agent of
type $A$, the cost it experiences from a front with $a$ agents of type $A$ and
$b$ agents of type $B$ is given by:

$\left|\frac{a\cdot\beta_{a}+b\cdot\beta_{b}}{a+b}-\beta_{a}\right|=\left|\frac{a\cdot\beta_{a}+b\cdot\beta_{b}-(a+b)\cdot\beta_{a}}{a+b}\right|=\frac{b}{a+b}\cdot\left|\beta_{a}-\beta_{b}\right|$

By identical reasoning, the cost to an agent of type $B$ is:

$\frac{a}{a+b}\cdot\left|\beta_{a}-\beta_{b}\right|$

Note that this construction immediately tells us that agent strategy must be
independent of biases. For every front with $a+b>0$, an agent’s cost is solely
a function of $a$ and $b$, scaled by a constant factor of
$\left|\beta_{a}-\beta_{b}\right|$.

Next, we will work on determining $c$ so that no front will ever be left
empty. Again, we wish to show that:

$w_{i}\cdot\left|f(S_{i})-\beta_{t}\right|+w_{j}\cdot c\geq
w_{i}\cdot\left|f(S_{i}\setminus\beta_{t})\right|+w_{j}\cdot 0$

The worst-case scenario (where this inequality is hardest to satisfy) occurs
when the empty front has very low weight, relative to the front it is
competing in ($w_{i}>>w_{j}$). If we consider a reference player of type $A$,
with $a$ players of type $A$ on front $i$ and $b$ of type $B$, then this
becomes:

$w_{i}\cdot\left|\beta_{a}-\beta_{b}\right|\cdot\frac{b}{a+b}+w_{j}\cdot c\geq
w_{i}\cdot\left|\beta_{a}-\beta_{b}\right|\cdot\frac{b}{a+b-1}+0$ $w_{j}\cdot
c\geq w_{i}\cdot\left|\beta_{a}-\beta_{b}\right|\cdot
b\cdot\left(\frac{1}{(a+b-1)}-\frac{1}{(a+b)}\right)$

$w_{j}\cdot c\geq w_{i}\cdot\left|\beta_{a}-\beta_{b}\right|\cdot
b\cdot\frac{b}{(a+b-1)\cdot(a+b)}$

Next, we’ll upper bound the term on the RHS. The RHS shrinks with $a$, so we
can lower bound this by setting $a=1$. We know that $a\geq 1$ because we have
assumed there is at least one player of type $A$ that wishes to move from the
given front. The condition simplifies to:

$c\cdot w_{j}\geq
w_{i}\cdot\left|\beta_{a}-\beta_{b}\right|\cdot\frac{1}{1+b}$

We similarly must have $b\geq 1$ (or else we’re just modeling a single player
of type $A$ move from one front to another). If we set $b=1$, then this goes
to 1/2, which gives the desired condition. Intuitively, this tells us that we
need that the cost of leaving something unlabeled is greater than half the
distance between the two biases.

Next, we will consider the case where the outcome function is equal to the
median. Again, we wish to show that:

$w_{i}\cdot\left|f(S_{i})-\beta_{t}\right|+w_{j}\cdot c\geq
w_{i}\cdot\left|f(S_{i}\setminus\beta_{t})\right|+w_{j}\cdot 0$

We will analyze multiple different cases for the potential outcome functions
$f(S_{i})$ and $\left|f(S_{i}\setminus\beta_{t})\right|$. Again, we will look
from the perspective of a type $A$ agent on front $i$ considering moving to
another front $j$ that is empty:

  * •

$f(S_{i})=\beta_{a}$ and $\left|f(S_{i}\setminus\beta_{t})\right|=\beta_{a}$.
The inequality becomes:

$w_{i}\cdot 0+w_{j}\cdot c\geq w_{i}\cdot 0+w_{j}\cdot 0$

which is satisfied automatically.

  * •

$f(S_{i})=\beta_{a}$ and
$\left|f(S_{i}\setminus\beta_{t})\right|=\frac{1}{2}\cdot(\beta_{a}+\beta_{b})$.
The inequality becomes:

$w_{i}\cdot 0+w_{j}\cdot c\geq 0.5\cdot
w_{i}\cdot\left|\beta_{a}-\beta_{b}\right|+w_{j}\cdot 0$ $c\geq
0.5\cdot\frac{w_{i}}{w_{j}}\cdot\left|\beta_{a}-\beta_{b}\right|$

  * •

$f(S_{i})=\frac{1}{2}\cdot(\beta_{a}+\beta_{b})$ and
$\left|f(S_{i}\setminus\beta_{t})\right|=\beta_{b}$. The inequality becomes:

$0.5\cdot w_{i}\cdot\left|\beta_{a}-\beta_{b}\right|+w_{j}\cdot c\geq
w_{i}\cdot\left|\beta_{a}-\beta_{b}\right|+w_{j}\cdot 0$ $c\geq
0.5\cdot\frac{w_{i}}{w_{j}}\cdot\left|\beta_{a}-\beta_{b}\right|$

  * •

$f(S_{i})=\frac{1}{2}\cdot\beta_{b}$ and
$\left|f(S_{i}\setminus\beta_{t})\right|=\beta_{b}$. The inequality becomes:

$w_{i}\cdot\left|\beta_{a}-\beta_{b}\right|+w_{j}\cdot c\geq
w_{i}\cdot\left|\beta_{a}-\beta_{b}\right|+w_{j}\cdot 0$

which is always satisfied.

The only inequality that isn’t automatically satisfied is $c\geq
0.5\cdot\frac{w_{i}}{w_{j}}\cdot\left|\beta_{a}-\beta_{b}\right|$, which is
the same inequality as for the mean outcome function, and satisfied by the
same reasoning.

Finally, we will show that agents’ incentives are independent of biases
$\beta_{a},\beta_{b}$. For any agent with bias $\beta_{a}$ and any set
$S_{i}$, the outcome function has three possible values: $\beta_{a}$ (giving
cost to agent $a$ of 0), $0.5\cdot(\beta_{a}+\beta_{b})$ in the event of ties
(giving cost to agent $a$ of $0.5\cdot\left|\beta_{a}-\beta_{b}\right|$), or
$\beta_{b}$ (giving cost to agent $a$ of $\left|\beta_{a}-\beta_{b}\right|$).
All of these are simply scaled values of $\left|\beta_{a}-\beta_{b}\right|$,
which means incentives are independent of the values $\beta_{a},\beta_{b}$. ∎

See 3

###### Proof.

Note that if we have $N=M$, then the last criteria gives us $N_{b}<0$, which
isn’t achievable.

To start out with, we will describe a few arrangements where a deviation is
always possible. For notation, we will use $\\{a_{1}\geq b_{1}\\}$ to denote
an arrangement where there are at least as many type $A$ players as type $B$
on front 1, for example. We will only refer to fronts 1 and 2 for convenience,
but these results hold for any labeled fronts.

$C1:\quad\\{a_{1}=b_{1}-1\\},\\{a_{2}\geq b_{2}+2\\}\text{ or
}\\{b_{1}=a_{1}-1\\},\\{b_{2}\geq a_{2}+2\\}$

This gives an arrangement where type $A$ loses by 1 on front 1 and wins by at
least 2 on front 2. This gives a deviation because any $a$ player from front 2
could move to label the front 1 and strictly reduce their cost (they now tie
in the first and still win in the second). Similar reasoning holds for the
other case: the type $B$ player from front 2 could move to label front 1 and
strictly reduce their cost.

$C2:\quad\\{a_{1}=b_{1}\\},\\{a_{2}\geq b_{2}+2\\}\text{ or
}\\{a_{1}=b_{1}\\},\\{b_{2}\geq a_{2}+2\\}$

Here, the players tie on front 1 and type $A$ wins by at least 2 on front 2.
This gives a deviation because any $a$ player from front 2 could move to label
front 1 and strictly reduce their cost (they now win front 1 and still win
front 2). Similar reasoning holds for the second case.

$C3:\quad\\{a_{1}\geq b_{1}+1\\},\\{a_{2}=b_{2}+1\\}\text{ or }\\{b_{1}\geq
a_{1}+1\\},\\{b_{2}=a_{2}+1\\}$

Here, type $A$ wins by at least one on front 1 and wins by exactly one on
front 2. This gives a deviation because type $B$ is losing in front 1, and can
move to front 2 where it will tie (and still lose front 1). Similar reasoning
holds for the second case.

Next, we will show that if we have any arrangement satisfying the
preconditions ($N_{a}+N_{b}\leq 2M,M<N_{a},N_{b}<N_{a}-M$), then at least one
of these cases must occur, meaning that the arrangement must be unstable.

First, let’s suppose that we have at least one tie somewhere:
$\\{a_{1}=b_{1}\\}$. By Case 2, we know that we can’t have any player types
win by 2 elsewhere (or else one of the agents could move and win at front 1,
while still winning elsewhere). That means that we need:

$b_{i}\leq a_{i}+1\text{ and }a_{i}\leq b_{i}+1\ \forall i\neq 1$

We will show that satisfying the second condition is impossible. First,
summing over all of the fronts gives:

$\sum_{i\neq 1}a_{i}\leq\sum_{i\neq 1}b_{i}+(M-1)$ $N_{a}-a_{1}\leq
N_{b}-b_{1}+(M-1)$

Recall that $a_{1}=b_{1}$ (there’s a tie), so this reduces to:

$N_{a}\leq N_{b}+(M-1)$ $N_{a}-(M-1)\leq N_{b}$

However, we also have $N_{b}<N_{a}-M$, so this becomes:

$N_{a}-(M-1)\leq N_{b}<N_{a}-M$ $1<0$

which is a contradiction. This implies that no arrangement where players tie
can be stable (and satisfy the preconditions).

Next, let’s consider the case where we have $a_{1}=b_{1}-1$ (type $A$ loses
front 1 by exactly 1). Case 1 tells us that we cannot have $a_{i}\geq b_{i}+2$
elsewhere (cannot have that type $A$ wins by at least two elsewhere), so we
must have $a_{i}\leq b_{i}+1$. Again, we can sum:

$\sum_{i\neq 1}a_{i}\leq\sum_{i\neq 1}b_{i}+1$ $N_{a}-a_{1}\leq
N_{b}-b_{1}+(M-1)$

Substituting in for $a_{1}=b_{1}-1$ gives us:

$N_{a}-b_{1}+1\leq N_{b}-b_{1}+M-1$ $N_{a}\leq N_{b}+M-2$ $N_{a}-M+2\leq
N_{b}$

which again contradicts $N_{b}<N_{a}-M$.

Finally, let’s consider where we have $b_{1}=a_{1}-1$ or $b_{1}+1=a_{1}$. By
Case 1, we must have $b_{i}\leq a_{i}+1$ for all $i\neq 1$. However, we will
show that this implies a contradiction with other stability analayses.

First, let’s consider the case where $b_{i}=a_{i}+1$ for all $i\neq M$, so
type $B$ wins every front by one except the first one, which it loses by
exactly one. We will show that this violates the preconditions of this lemma:

$b_{i}=a_{i}+1\forall i\neq 0$ $\sum_{i\neq 1}b_{i}=\sum_{i\neq 1}a_{i}+1$
$N_{b}-b_{1}=N_{a}-a_{1}+M-1$ $N_{b}-(a_{1}-1)=N_{a}-a_{1}+M-1$
$N_{b}+1=N_{a}+M-1$ $N_{b}=N_{a}+M-2$

If we combine this with our $N_{b}<N_{a}-M$ condition, we get:

$N_{a}+M-2<N_{a}-M$ $2M<2$ $M<1$

which cannot be satisfied because we need at least one front.

Next, we’ll consider the case where $b_{i}<a_{i}+1$ for at least one front.
From our previous analysis of Case 2, we know that we cannot have an exact tie
($a_{i}=b_{i}$).

This implies that we must have at least one front $i$ such that $b_{i}\leq
a_{i}-1$, along with front 1 which has $b_{1}=a_{1}-1$. Equivalently, we can
write this as $a_{1}=b_{1}+1,a_{i}\geq b_{i}+1$. However, this exactly implies
the condition in Case 3, which is also unstable. ∎

See 4

###### Proof.

We will show constructively that it is possible to create an arrangement
satisfying the following criteria:

  * •

For every front where there is more than 1 agent, type $A$ and type $B$ tie
exactly.

  * •

Every other front has exactly one agent, which can be either type $A$ or type
$B$.

This type of construction is stable by the following reasoning:

  * •

None of the single agents can move (they can’t leave an front empty).

  * •

No agent on an front with multiple agents wishes to leave - they would go from
winning a single front and losing another, to losing on that front and tying
on another, which gives equal costs when weights are equal.

Algorithm 2 considers this case. Informally, we will describe how it works.

If $N_{a}+N_{b}\leq M$, then we place at most one agent on each front, which
satisfies the construction criteria.

Next, we consider the case where $N_{a}+N_{b}-M$ is even. We calculate
$\frac{N_{a}+N_{b}-M}{2}=x$ and place $x$ of type $A$ and type $B$ players
each on front 0. By the assumptions of this lemma, we know that $N_{b}\geq
N_{a}-M$, which means that $x=\frac{N_{a}+N_{b}-M}{2}\leq\frac{2N_{a}-2\cdot
M}{2}=N_{a}-M>0$. Then, we place exactly 1 of type $A$ and type $B$ on front
1. For every other front, have $N_{a}-x-1$ with exactly one type $A$ agent,
exactly $N_{b}-x-1$ with exactly one type $B$ agent. The total number of
fronts:

$1+1+N_{a}-x-1+N_{b}-x-1=N_{a}+N_{b}-2x=N_{a}+N_{b}-N_{a}-N_{b}+M=M$

as desired.

Next, if $N_{a}+N_{b}-M$ is odd, we know that $N_{a}+N_{b}-(M-1)$ is even. We
then calculate $\frac{N_{a}+N_{b}+1-M}{2}=x$. Then, set $a_{0}=x,b_{0}=x$ (we
address the case where $N_{b}<x$ at the end of this proof). Every other front
has exactly one agent, with $N_{a}-x$ of them having type $A$, and $N_{b}-x$
having type $B$. Note that the total number of agents adds up to the right
amount and that (by construction) every front is labeled. 1 front has many
players, $N_{a}-x$ have type $A$ only, $N_{b}-x$ have type $B$ only, and
together this sums to:

$1+N_{a}-x+N_{b}-x=1+N_{a}+N_{b}-2\cdot x=1+N_{a}+N_{b}-(N_{a}+N_{b}-(M-1))=M$

Finally, we consider the case where $x=\frac{N_{a}+N_{b}+1-M}{2}>N_{b}$, which
means $N_{a}+1-M>N_{b}$. By assumptions of this lemma, we know that $N_{b}\geq
N_{a}-M$. Taken together, this tells us that:

$N_{a}-M\leq N_{b}<N_{a}-M+1$

This can only be satisfied by setting $N_{b}=N_{a}-M$. However, this means
that:

$N_{a}+N_{b}-M=2\cdot N_{a}-2\cdot M=2\cdot(N_{a}-M)$

However, this conflicts with the assumption that $N_{a}+N_{b}-M$ is odd, which
means this situation can never occur.

∎

See 5

###### Proof.

In this proof, we will use the notation

$\\{a,b\\},\\{a,b\\},\\{a\\},\\{b\\}$

to illustrate that there are 4 fronts in total, two of which with exactly 2
players on it (one of each type), and two fronts with exactly one player (one
front with a single type $A$ player, and one front with a single type $B$
player). Lemma 4 would suggest that the arrangement

$\\{a,b\\},\\{a,b\\},\\{a\\},\\{b\\}$

would be stable. If $w_{1}=w_{2}$, then this would be satisfied: none of the
singleton players could move, and none of the $\\{a,b\\}$ players wish to
move. If a player of type $A$from front 2 moved to label front 1, they would
go from experiencing cost

$0.5\cdot w_{1}+0.5\cdot w_{2}+w_{3}$

to experiencing cost:

$w_{2}+w_{3}$

which is identical when $w_{1}=w_{2}$. However, when $w_{1}>w_{2}$, then this
move does reduce cost, meaning that the original arrangement was unstable.

We will further show that no possible arrangement is stable. Note that fronts
$2,3,4$ have identical weight and are therefore interchangable. Because
$N_{a}+N_{b}=6$ and $M=4$, if no front can be left empty, then no front can
have more than 3 players. We will consider each case based on the maximum
number of agents on a front.

  * Case 1

No more than 3 agents on one front: The arrangement
$\\{a\\},\\{b,b,b\\},\\{a\\},\\{a\\}$ goes to
$\\{a\\},\\{b,b\\},\\{a,b\\},\\{a\\}$ because type $B$’s cost goes from
$w_{1}+w_{3}+w_{4}$ to $w_{1}+0.5\cdot w_{3}+w_{4}$. (Type $B$ continues to
win on item 2 and now also ties on item 3). Identical reasoning holds for any
symmetrical case with 3 players of the same type on any item.

  * Case 2

No more than 3 agents on one front: The arrangement
$\\{a,a,b\\},\\{b\\},\\{a\\},\\{b\\}$ moves to
$\\{a,a\\},\\{b\\},\\{a,b\\},\\{b\\}$: the type $B$ player on front 1 can move
to compete in front 3, which takes its cost from $w_{1}+w_{3}$ to
$w_{1}+0.5\cdot w_{3}$. (Type $B$ continues to lose item 1 and now ties on
item 3). Identical reasoning holds for the symmetric case with type $A$, as
well as for arrangements where player $i>1$ has 3 players: for example, the
arrangement $\\{a\\},\\{a,a,b\\},\\{a\\},\\{b\\}$ goes to
$\\{a\\},\\{a,a\\},\\{a,b\\},\\{b\\}$ because the type $B$ players cost goes
from $w_{1}+w_{2}+w_{3}$ to $w_{1}+w_{2}+0.5\cdot w_{3}$.

  * Case 3

No more than 2 agents on a front: Given the arrangement
$\\{a,b\\},\\{a,b\\},\\{a\\},\\{b\\}$, as described above, either type $A$ or
type $B$ players from front 1 would wish to move to compete in front 1. This
is the case analyzed at the beginning of the proof, where we showed this is
unstable for $w_{1}>w_{2}$.

  * Case 4

No more than 2 agents on a front: The arrangement
$\\{a,a\\},\\{b\\},\\{a,b\\},\\{b\\}$ goes to
$\\{a\\},\\{a,b\\},\\{a,b\\},\\{b\\}$ because player type $A$’s cost goes from
$w_{2}+0.5\cdot w_{3}+w_{4}$ to $0.5\cdot(w_{2}+w_{3})+w_{4}$. Similarly, any
arrangement with exactly 2 agent of the same type on an front must leave at
least one other front with exactly 1 agent of the opposite type, and will be
unstable for the same reasons.

This description is exhaustive: If there is a maximum of 3 agents on a front,
then they must all be of the same type (Case 1) or two of the same type, and
one of another type (Case 2). If there is a maximum of 2 agents on a front,
then if one front has exactly one agent of each type, then another front must
have exactly one agent of each type (Case 3) or must have exactly 2 agents of
one type (Case 4). ∎

See 6

###### Proof.

This proof is very similar to that of Lemma 4, so we will simply note key
differences in the analysis. Throughout, we will assume that $w_{i}\geq w_{j}$
for $i<j$ (the fronts are organized in descending order of weight).

First, we will suppose that either:

$N_{a}+N_{b}\geq 2\cdot M+1\text{ or }N_{a}+N_{b}=2\cdot M\text{ with
}N_{a},N_{b}\text{ even }$

Again, we will allocate agents according to Algorithm 1. This arrangement is
stable by identical reasoning: for each front, each type wins by at least 2,
so no single agent acting alone can change the outcome, regardless of weights.

  * •

For every item where there is more than 1 labeler, type $A$ and type $B$ tie
exactly.

  * •

Every other item has exactly one labeler, which can be either type $A$ or type
$B$.

  * •

Any item where players tie has higher or equal weight to any item where a
single player wins.

Next, we consider the case where $N_{a}+N_{b}\leq 2\cdot M$. We will show
constructively that it is possible to create an arrangement satisfying the
following criteria:

  * •

For every front where there is more than 1 agent, type $A$ and type $B$ tie
exactly.

  * •

Every other front has exactly one agent, which can be either type $A$ or type
$B$.

  * •

Any front where players tie has higher or equal weight to any front where a
single player wins.

This type of construction is stable by the following reasoning:

  * •

None of the single agents can move (they can’t leave an front empty).

  * •

No agent on an front with multiple agents wishes to leave - they would go from
winning a single front and losing another, to losing on that front and tying
on another, which gives equal costs when weights are equal.

  * •

No agent on a front with multiple agents wishes to leave: they would go from
tying on front $i$ and losing on front $j$ to losing on front $i$ and tying on
front $j$. This gives higher or equal cost when $w_{i}\geq w_{j}$, which is
satisfied by construction.

Note that we require $w_{1}=w_{2}$ by the example given in Lemma 5. ∎

See 1

###### Proof.

In order to show this, we will look at a relaxed (continuous) version of this
problem. In this relaxed version of the problem, we will assume that, instead
of agents coming in integer units, they can be allocated fractionally across
items.

The cost to player of type $A$ is given by
$\sum_{i=1}^{M}w_{i}\cdot\frac{b_{i}}{a_{i}+b_{i}}$. The partial derivative of
this with respect to $a_{i}$ is:

$\frac{\partial}{\partial
a_{i}}\sum_{i=1}^{M}w_{i}\cdot\frac{b_{i}}{a_{i}+b_{i}}=-w_{i}\cdot\frac{b_{i}}{(a_{i}+b_{i})^{2}}$

In order for us to be at a stable point, we need that the derivative wrt
$a_{i}$ must be equal to the derivative wrt $a_{j}$ for any $i\neq j$ and
$\sum_{i=1}^{M}a_{i}=N_{a}$ (identical criteria for $B$). If the first is not
satisfied, then type $A$ could strictly reduce its cost by changing its
allocations between fronts, and if the second is not satisfied, then type $A$
could again reduce its cost by allocating more agents onto fronts. We can
enforce both of these by setting:

$w_{i}\cdot\frac{b_{i}}{(a_{i}+b_{i})^{2}}=w_{M}\cdot\frac{N_{b}-\sum_{i\neq
M}b_{i}}{(N_{a}-\sum_{i\neq M}a_{i}+N_{b}-\sum_{i\neq M}b_{i})^{2}}$
$\frac{b_{i}}{N_{b}-\sum_{i\neq
M}b_{i}}=\frac{w_{M}}{w_{i}}\cdot\frac{(a_{i}+b_{i})^{2}}{(N_{a}-\sum_{i\neq
M}a_{i}+N_{b}-\sum_{i\neq M}b_{i})^{2}}$

By identical reasoning, this means that for player $B$, the derivative of its
cost wrt $b_{i}$ is:

$\frac{a_{i}}{N_{a}-\sum_{i\neq
M}a_{i}}=\frac{w_{M}}{w_{i}}\cdot\frac{(a_{i}+b_{i})^{2}}{(N_{a}-\sum_{i\neq
M}a_{i}+N_{b}-\sum_{i\neq M}b_{i})^{2}}$

Setting these equal to each other gives:

$\frac{a_{i}}{N_{a}-\sum_{i\neq M}a_{i}}=\frac{b_{i}}{N_{b}-\sum_{i\neq
M}b_{i}}$ $N_{b}-\sum_{i\neq
M}b_{i}=\frac{b_{i}}{a_{i}}\cdot\left(N_{a}-\sum_{i\neq M}a_{i}\right)$

Substituting in for the overall derivative gives us that:

$\displaystyle\frac{a_{i}}{N_{a}-\sum_{i\neq M}a_{i}}$
$\displaystyle=\frac{w_{M}}{w_{i}}\cdot\frac{(a_{i}+b_{i})^{2}}{(N_{a}-\sum_{i\neq
M}a_{i}+N_{b}-\sum_{i\neq M}b_{i})^{2}}$
$\displaystyle=\frac{w_{M}}{w_{i}}\cdot\frac{(a_{i}+b_{i})^{2}}{\left(N_{a}-\sum_{i\neq
M}a_{i}+\frac{b_{i}}{a_{i}}\cdot\left(N_{a}-\sum_{i\neq
M}a_{i}\right)\right)^{2}}$
$\displaystyle=\frac{w_{M}}{w_{i}}\cdot\frac{(a_{i}+b_{i})^{2}}{\left(N_{a}-\sum_{i\neq
M}a_{i}\right)^{2}\cdot\left(1+\frac{b_{i}}{a_{i}}\right)^{2}}$
$\displaystyle=\frac{w_{M}}{w_{i}}\cdot\frac{a_{i}^{2}\cdot(a_{i}+b_{i})^{2}}{\left(N_{a}-\sum_{i\neq
M}a_{i}\right)^{2}\cdot\left(a_{i}+b_{i}\right)^{2}}$
$\displaystyle=\frac{w_{M}}{w_{i}}\cdot\frac{a_{i}^{2}}{\left(N_{a}-\sum_{i\neq
M}a_{i}\right)^{2}}$

Cancelling common factors on each side of the equality gives:

$\frac{N_{a}-\sum_{i\neq M}a_{i}}{w_{M}}=\frac{a_{i}}{w_{i}}$

Or $\frac{a_{M}}{w_{M}}\cdot w_{i}=a_{i}$. We can apply the equality
$\sum_{i=0}^{M}a_{i}=N_{a}$ to obtain:

$\sum_{i=0}^{M}\frac{a_{M}}{w_{M}}\cdot w_{i}=N_{a}\quad\Rightarrow\quad
a_{M}=w_{M}\cdot N_{a}$

which implies $a_{i}=w_{i}\cdot\frac{w_{M}\cdot N_{a}}{w_{M}}=w_{i}\cdot
N_{a}$ and $b_{i}=N_{b}\cdot w_{i}$ symmetrically. This tells us that the only
possible equilibrium is when both $A$ and $B$ players have set $a_{i},b_{i}$
exactly proportional to the weight each front has. ∎

See 2

###### Proof.

In order to prove this result, we will show that any arrangement that is not
“close” to proportional must have at least one agent that wishes to move. An
arrangement is “close” to proportion if:

$\left|a_{i}-w_{i}\cdot N_{a}\right|\leq 1,\left|b_{i}-w_{i}\cdot
N_{b}\right|\leq 1\ \forall i\in[M]$

For any arrangement falling outside of these parameters, we will give a move
that reduces cost for at least one player type. At a high level, this will
involve finding a “large” front (with more agents) and a “small” front (with
fewer agents). We will then pick whichever agent type is more represented in
the larger front, and move exactly one agent to the smallest front. We will
show that, almost always, this strictly reduces cost for the agent type that
moves. In the cases where such a move would not strictly reduce cost, we show
that all fronts must be “close” to proportional.

First, we will consider all pairs of fronts $j,k$ such that $a_{j}+b_{j}\geq
a_{k}+b_{k}$. One feature of this pair that we will consider is the _gap in
type prevalence_ , which is given by:

$\text{ type A:
}\frac{a_{j}}{a_{j}+b_{j}}-\frac{a_{k}}{a_{k}+b_{k}}\quad\text{ type B:
}\frac{b_{j}}{a_{j}+b_{j}}-\frac{b_{k}}{a_{k}+b_{k}}$

Note that if one type has positive gap in type prevalence, then the other has
negative gap in type prevalence, because:

$\frac{a_{j}}{a_{j}+b_{j}}-\frac{a_{k}}{a_{k}+b_{k}}=-1+\frac{a_{j}}{a_{j}+b_{j}}+1-\frac{a_{k}}{a_{k}+b_{k}}=\frac{-b_{j}}{a_{j}+b_{j}}+\frac{b_{k}}{a_{k}+b_{k}}$

WLOG, we will assume that type $A$ has positive or 0 gap in type prevalence.
If the gap in type prevalence is 0 (both fronts have exactly equal proportions
of player types), then we will again WLOG assume that type $A$ makes up a
larger share of players, or
$\frac{a_{j}}{a_{j}+b_{j}}=\frac{a_{k}}{a_{k}+b_{k}}\geq\frac{b_{j}}{a_{j}+b_{j}}=\frac{b_{k}}{a_{k}+b_{k}}$.
Given this assumption, we will show that players of type $A$ could always
reduce its cost by moving a single agent from front $j$ to front $k$ (unless
all fronts are _close_ to proportional).

Costs: Type $A$’s cost is:

$\frac{b_{j}}{a_{j}+b_{j}}+\frac{b_{k}}{a_{k}+b_{k}}$

Its cost after moving a single agent from $a_{j}$ is given by:

$\frac{b_{j}}{a_{j}+b_{j}-1}+\frac{b_{k}}{a_{k}+b_{k}+1}$

So, its cost decreases whenever:

$\frac{b_{j}}{a_{j}+b_{j}}+\frac{b_{k}}{a_{k}+b_{k}}-\frac{b_{j}}{a_{j}+b_{j}-1}-\frac{b_{k}}{a_{k}+b_{k}+1}>0$

Or:

$b_{k}\cdot(a_{j}+b_{j})\cdot(a_{j}+b_{j}-1)>b_{j}\cdot(a_{k}+b_{k})\cdot(a_{k}+b_{k}+1)$
(2)

Equation 2 is the central condition we will be studying in this proof. First,
we will present several sufficient conditions for when Equation 2 is
satisfied, so a player wishes to move. Then, we will show that whenever none
of those sufficient conditions are satisfied, all fronts must be “close” to
proportional.

Sufficient condition 1: Fronts differ by at least 2, positive gap in type
prevalence There are a few conditions where we can immediately see that
Equation 2 is satisfied. First, we divide this equation into two separate
components. The first is given by:

$b_{k}\cdot(a_{j}+b_{j})\geq b_{j}\cdot(a_{k}+b_{k})$
$\frac{b_{k}}{a_{k}+b_{k}}\geq\frac{b_{j}}{a_{j}+b_{j}}$ (3)

By prior reasoning, this is satisfied by the assumption that
$\frac{a_{j}}{a_{j}+b_{j}}\geq\frac{a_{k}}{a_{k}+b_{k}}$ as given by type $A$
having positive gap in type prevalence.
Next, we will consider the second component of Equation 2:

$a_{j}+b_{j}-1\geq a_{k}+b_{k}+1$

which is satisfied exactly whenever:

$a_{j}+b_{j}\geq a_{k}+b_{k}+2$ (4)

Note that this is _not_ required by how we selected fronts (all we require is
$a_{j}+b_{j}\geq a_{k}+b_{k}$). However, in the event that both Equation 4
holds, and either Equation 3 or Equation 4 is satisfied strictly, then
Equation 2 hold strictly and type $A$ players have an incentive to move from
front 1 to front 2.
Next, we will consider other cases where Equation 4 and 3 are not both
strictly satisfied, and yet a type $A$ player still wishes to move from front
$j$ to $k$.

Sufficient condition 2: Larger and smaller front have same number of players,
$a_{j}\geq a_{k}+2$ First, we will consider the case where
$a_{j}+b_{j}=a_{k}+b_{k}$ (the two fronts have equal numbers of players).
Equation 2 simplifies to

$b_{k}\cdot(a_{j}+b_{j}-1)>b_{j}\cdot(a_{k}+b_{k}+1)$

We will show that so long as $a_{j}\geq a_{k}+2$, then this inequality must
hold. Note that this condition implies $b_{k}\geq b_{j}+2$. Substituting in
for $a_{j}+b_{j}=a_{k}+b_{k}$ and $b_{k}\geq b_{j}+2$ tells us that we wish to
show:

$(b_{j}+2)\cdot(a_{j}+b_{j}-1)>b_{j}\cdot(a_{j}+b_{j}+1)$
$b_{j}\cdot(a_{j}+b_{j})-b_{j}+2\cdot(a_{j}+b_{j})-2>b_{j}\cdot(a_{j}+b_{j})+b_{j}$
$-b_{j}+2\cdot(a_{j}+b_{j})-2>b_{j}$ $2\cdot a_{j}+2\cdot b_{j}>2\cdot
b_{j}+2$ $a_{j}\geq 1$

Because $a_{j}\geq a_{k}+2$, we know that $a_{j}\geq 1$, as desired.
When this sufficient condition is not met, we have that $a_{j}\leq a_{k}+1$.
Because we assume that type $A$ has positive gap in type prevalence, this
means that $a_{j}=a_{k}+1$ and $b_{j}=b_{k}-1$ in order to ensure
$a_{j}+b_{j}=a_{k}+b_{k}$.

Sufficient condition 3: Larger front has exactly 1 more agent than smaller,
$a_{j}\geq a_{k}+2$ Next, we will consider the case where the larger front has
exactly 1 more player than the smaller front, or $a_{j}+b_{j}=a_{k}+b_{k}+1$.
Then, the condition for a player of type A wanting to move (Equation 2)
becomes:

$b_{k}\cdot(a_{k}+b_{k}+1)\cdot(a_{k}+b_{k})>b_{j}\cdot(a_{k}+b_{k})\cdot(a_{k}+b_{k}+1)$

which simplifies down to:

$b_{k}>b_{j}$

If we have $a_{j}\geq a_{k}+2$, then we must have:

$a_{k}+b_{k}=a_{j}+b_{j}-1>a_{k}+2+b_{j}-1=a_{k}+b_{j}+1$

which implies that:

$b_{k}\geq b_{j}+1$

as desired.
When this sufficient condition is not met, we have that $a_{j}\leq a_{k}+1$.
Because we assume that type $A$ has positive gap in type prevalence, this
means that $a_{j}=a_{k}+1$ and $b_{j}=b_{k}$ in order to ensure
$a_{j}+b_{j}=a_{k}+b_{k}+1$.
In absence of sufficient conditions, all fronts are “close” to proportional
Finally, we will consider the case where none of the sufficient conditions
hold. By taking the negative of previous cases, we know that:

  1. 1.

By sufficient condition 1, there is no pair of fronts $j,k$ with
$a_{j}+b_{j}>a_{k}+b_{k}+2$.

  2. 2.

By sufficient condition 1 for any pair of fronts with
$a_{j}+b_{j}=a_{k}+b_{k}+2$, we must have zero gap in type prevalence.

  3. 3.

By sufficient condition 2, for any pair of fronts with
$a_{j}+b_{j}=a_{k}+b_{k}$, we must have $a_{j}=a_{k}+1,b_{j}=b_{k}-1$.

  4. 4.

By sufficient condition 3, for any pair of fronts with
$a_{j}+b_{j}=a_{k}+b_{k}+1$, we must have $a_{j}=a_{k}+1,b_{j}=b_{k}$.

Each of these cases (except for item 2) results in an arrangement where for
any pair of fronts $j,k$, we have

$\left|a_{j}-a_{k}\right|\leq 1\quad\left|b_{j}-b_{k}\right|\leq 1$

If we are also able to show that this holds for item 2 (when
$a_{j}+b_{j}=a_{k}+b_{k}+2$), then we will know that _any_ pair of fronts
differs in $a,b$ by at most 1. This would mean that every front has either
$a_{i}=a^{*}$ or $a^{*}+1$ and $b_{i}=b^{*}$ or $b^{*}+1$. The average number
of players per fronts must lie somewhere between
$[a^{*},a^{*}+1],[b^{*},b^{*}+1]$, which means that every front is “close” to
proportional.

We will conclude our proof by showing that examining item 2 and showing that
we must also have $\left|a_{j}-a_{k}\right|\leq 1,\left|b_{j}-b_{k}\right|\leq
1$.

In this case, we assume that $a_{j}+b_{j}=a_{k}+b_{k}+2$. Note that by our
analysis of Case 1, a type $A$ player wishes to move automatically if Equation
3 holds strictly. In this case, we will assume that it does _not_ hold
strictly and derive additional conditions on $a_{j},b_{j},a_{k},b_{k}$.
Equation 3 becomes an equality:

$\frac{b_{k}}{a_{k}+b_{k}}=\frac{b_{j}}{a_{j}+b_{j}}$

This implies that fronts $j,k$ have exactly the same proportion of type $A$
and type $B$ players (a zero gap in type prevalence). This means that we can
write $a_{j}=c\cdot b_{j},a_{k}=c\cdot b_{k}$. In how we selected fronts, we
assumed WLOG that in the case that the gap in type prevalence is 0, players of
type $A$ make up a greater share of players on both fronts. This implies that
$c\geq 1$. We can then write:

$a_{j}+b_{j}=a_{k}+b_{k}+2$

Substituting in for $a_{j}=c\cdot b_{j}$ gives:

$b_{j}\cdot(c+1)=b_{k}\cdot(c+1)+2$ $b_{j}=b_{k}+\frac{2}{c+1}$

The only value $c$ for which this results in an integer $b_{j},b_{k}$ is
$c=1$, which implies $b_{j}=b_{k}+1$, $a_{k}=b_{k}$ and $a_{j}=b_{j}=a_{k}+1$,
or $\left|a_{j}-a_{k}\right|\leq 1,\left|b_{j}-b_{k}\right|\leq 1$ as desired.
∎

See 10

###### Proof.

For simplicity, we will say that front $i$ is labeled by player with bias
$\beta_{i}$. In order for this arrangement to be stable, we need to know that
no player $i$ wishes to label a different front $j$.

First, we can immediately see that no player $i$ would wish to label an front
$j$ that is currently empty. By the way we have arranged players, we know that
$w_{i}\leq w_{j}$ for $i\geq j$, so labeling that front would have less impact
on overall cost.

Next, we need to show that no player $i$ wishes to label a different front $j$
that already has a label on it.

No player $j\in[N]$ wishes to move to another front $k$ that already has a
label so long as so long as:

$\sum_{i=1}^{N}w_{i}\cdot\left|\beta_{i}-\beta_{j}\right|+c\cdot\sum_{i=N+1}^{M}w_{i}\leq\sum_{i\in[N],i\neq
k,j}w_{i}\cdot\left|\beta_{i}-\beta_{j}\right|+0.5\cdot
w_{k}\cdot\left|\beta_{k}-\beta_{j}\right|+c\cdot\sum_{i=N+1}^{M}w_{i}+w_{j}\cdot
c$ $w_{k}\cdot\left|\beta_{k}-\beta_{j}\right|\leq 0.5\cdot
w_{k}\cdot\left|\beta_{j}-\beta_{k}\right|+w_{j}\cdot c$ $0.5\cdot
w_{k}\cdot\left|\beta_{k}-\beta_{j}\right|\leq w_{j}\cdot c$ $0.5\cdot
w_{k}\cdot\left|\beta_{k}-\beta_{j}\right|\leq\frac{w_{j}}{w_{k}}\cdot c$

The RHS is lower bounded by setting $w_{j}=w_{M},w_{k}=w_{0}$. The LHS is
upper bounded by plugging in for $\beta_{0}$ (the largest magnitude) and
$\beta_{i^{*}}$ (the next largest magnitude with an opposite sign), meaning
that the LHS will be equal to $\left|\beta_{0}\right|+\left|\beta_{i}\right|$
rather than $\left|\beta_{0}\right|-\left|\beta_{i}\right|$). This gives us:

$0.5\cdot\left|\beta_{0}-\beta_{i*}\right|\leq\frac{w_{M}}{w_{0}}\cdot c$

∎

See 12

###### Proof.

Set parameters as follows:

  * •

$M$ fronts, all with equal weight.

  * •

$N$ players, with given biases: 1 with bias $1$, and $N-1$ with bias $-0.5$.

  * •

Cost of 0.3 for leaving an front empty.

First, we will note that any arrangement where 3 or more players are labeling
a single front (front $i$) must fail to be stable. Because $N<M$, we know that
every arrangement must leave at least one front empty, for a cost of 0.3.

  * •

First, suppose that the front in question has only players with bias $-0.5$
labeling it. Then, any player can leave front $i$ and instead label an empty
front $j$. The median of front $i$ remains the same and the median of $j$
becomes $-0.5$ (eliminating empty cost), which reduces the cost for players
with bias $-0.5$.

  * •

Next, consider the other case where the front in question is labeled by the
player with bias 1. We know that there are at least 2 players with bias
$-0.5$, since there are at least 3 players total. If the player with bias 1
leaves $i$ and instead labels $j$, then the median remains -0.5. However,
again, this now eliminates the penalty for leaving $j$ empty.

Now, we consider all arrangements where there are no more than 2 players
labeling an front. We similarly know that if there are 2 players of bias
$-0.5$ labeling an front, then they can reduce their cost by having one leave
to label an empty front (maintaining the same median and eliminating empty
cost). Therefore, we can focus on how the player with bias $1$ is arranged. We
will find that considering only the first 3 fronts will be sufficient. For
conciseness, we will use the notation $\\{1\\}$ $\\{-0.5\\},\\{-0.5\\}$ to
mean that three players are all labeling a single front each (one player with
bias 1, two players with bias $-0.5$).

  * •

$\\{1\\}$ $\\{-0.5\\},\\{-0.5\\}$ goes to $\\{1,-0.5\\},\\{\\},\\{-0.5\\}$.
Originally, the -0.5 players have cost $1.5+0+0=1.5$. The $-0.5$ player wishes
to move, which produces medians $0.25,-0.5,-0.5$, which gives it cost become
$0.75+0.3+0=0.75<1.5$.

  * •

$\\{1,-0.5\\},\\{\\},\\{-0.5\\}$ goes to $\\{1,-0.5,-0.5\\},\\{\\},\\{\\}$.
The $-0.5$ player wishes to move again. Before, the medians are
$0.25,\text{n/a},-0.5$, giving it a cost of $0.75+0.3+0=1.05$. After it moves,
the medians are $-0.5,\text{n/a},\text{n/a}$, which gives it a cost of
$0+0.3\cdot 2=0.6$.

  * •

$\\{1,-0.5,-0.5\\},\\{\\},\\{\\}$ goes to $\\{-0.5,-0.5\\},\\{1\\},\\{\\}$.
The 1 player wishes to move. Before, the medians are
$-0.5,\text{n/a},\text{n/a}$, which gives it a cost of $1.5+0.3\cdot 2=2.1$.
After it moves, the medians are $-0.5,1,\text{n/a}$, which gives it a cost of
$1.5+0+0.3=1.8<2.1$.

  * •

$\\{-0.5,-0.5\\},\\{1\\},\\{\\}$ goes to $\\{-0.5,\\},\\{1\\},\\{-0.5\\}$. The
$-0.5$ player wishes to move. Before, the medians are $-0.5,1,\text{n/a}$,
which gives it cost $0+1.5+0.3=1.8$. After it moves, the medians are
$-0.5,1,-0.5$, which gives it cost $0+1.5+0=1.5<1.8$.

∎

See 13

###### Proof.

Set parameters as follows:

  * •

$M$ fronts, all with equal weight.

  * •

$N$ players, with given biases: 1 with bias $1$, and $N-1$ with bias $-0.5$.

  * •

Cost of $c_{u}\in(0.125,0.25)$ for leaving an front empty.

Because $N<M$, we know that every arrangement must leave at least one front
empty, for a cost of $c_{u}$. First, we will consider the case where at least
one front $j$ has 3 or more agents on it.

  * •

First, suppose that the front with 3 or more players labeling it has only
players with bias $-0.5$ labeling it. Then, any player can leave front $i$ and
instead label an empty front $j$. The mean of front $i$ remains the same and
the mean of $j$ becomes $-0.5$ (eliminating empty cost), which reduces the
cost for players with bias $-0.5$.

  * •

Next, consider the other case where the front in question is labeled by the
player with bias 1. Say that there are $a_{i}$ players with bias -0.5. We know
that there $a_{i}\geq 2$ since there are at least 3 players total.

    * –

Currently, the cost to players of type $A$ is:

$\left|\frac{-0.5\cdot
a_{i}+1}{a_{i}+1}+0.5\right|+c_{u}=\left|\frac{-0.5\cdot a_{i}+1+0.5\cdot
a_{i}+0.5}{a_{i}+1}\right|+c_{u}=\frac{1.5}{a_{i}+1}+c_{u}$

If one player of type $A$ goes to label the empty front, the cost becomes:

$\left|\frac{-0.5\cdot(a_{i}-1)+1}{a_{i}}+0.5\right|=\left|\frac{-0.5\cdot
a_{i}+0.5+1+0.5\cdot a_{i}}{a_{i}}\right|=\frac{1.5}{a_{i}}$

The type $A$ player wishes to move whenever:

$\frac{1.5}{a_{i}+1}+c_{u}>\frac{1.5}{a_{i}}$
$c_{u}>1.5\cdot\frac{1}{a_{i}\cdot(a_{i}+1)}\geq 1.5\cdot\frac{1}{2\cdot
3}=0.25$

Note that the lefthand side is decreasing in $a_{i}$, which is where the lower
bound comes from. Note that if $a_{i}\geq 3$, the lower bound becomes
$c_{u}\geq\frac{3}{2}\cdot\frac{1}{3\cdot 4}=\frac{1}{8}=0.125$.

    * –

Currently, the cost to players of type $B$ is:

$\left|\frac{-0.5\cdot a_{i}+1}{a_{i}+1}-1\right|+c_{u}=\left|\frac{-0.5\cdot
a_{i}+1-\cdot a_{i}-1}{a_{i}+1}\right|+c_{u}=\frac{1.5\cdot
a_{i}}{a_{i}+1}+c_{u}$

If one player of type $B$ goes to label the empty front, the cost becomes:

$\left|-0.5-1\right|=1.5$

The type $B$ player wishes to move whenever:

$\frac{1.5\cdot a_{i}}{a_{i}+1}+c_{u}>1.5$
$c_{u}>\frac{1.5}{a_{i}+1}\geq\frac{1.5}{3}=0.5$

    * –

We are in the scenario where $j$ with $a_{i}\geq 2,b_{i}=1$ (the sole type $B$
player is on front $i$). Suppose that there exists another front $j$ with
$a_{j}=1$. Then, the type $B$ player can reduce its cost by moving from front
$i$ to front $j$ whenever:

$\left|\frac{-0.5\cdot
a_{i}+1}{a_{i}+1}-1\right|+\left|-0.5-1\right|>\left|-0.5-1\right|+\left|\frac{-0.5+1}{2}-1\right|$
$\left|\frac{-0.5\cdot
a_{i}+1}{a_{i}+1}-1\right|>\left|\frac{-0.5+1}{2}-1\right|$

For $a_{i}\geq 2$, the term inside the absolute value is given by:

$\left|\frac{-0.5\cdot a_{i}+1}{a_{i}+1}-1\right|=\frac{0.5\cdot
a_{i}-1}{a_{i}+1}$

which is increasing in $a_{i}$, meaning that the inequality is always
satisfied.

Now, we consider all arrangements where there are no more than 2 players
labeling an front. We similarly know that if there are 2 players of bias
$-0.5$ labeling an front, then they can reduce their cost by having one leave
to label an empty front (maintaining the same mean and eliminating empty
cost). Therefore, we can focus on how the player with bias $1$ is arranged. We
will find that considering only the first 3 fronts will be sufficient. For
conciseness, we will use the notation $\\{1\\}$ $\\{-0.5\\},\\{-0.5\\}$ to
mean that three players are all labeling a single front each (one player with
bias 1, two players with bias $-0.5$).

  * •

$\\{1\\}$ $\\{-0.5\\},\\{-0.5\\}$ goes to $\\{1,-0.5\\},\\{\\},\\{-0.5\\}$.
Originally, the -0.5 players have cost $1.5+0+0=1.5$. The $-0.5$ player wishes
to move, which produces means $0.25,\emptyset,-0.5$. (The second front has
undefined mean, given that it has no labels). This gives the $-0.5$ players
cost $0.75+c_{u}+0$. This is lower if $0.75+c_{u}<1.5$, which is satisfied for
$c_{u}<0.75$.

  * •

$\\{1,-0.5\\},\\{\\},\\{-0.5\\}$ goes to $\\{1,-0.5,-0.5\\},\\{\\},\\{\\}$.
The $-0.5$ player wishes to move again. Before, the means are
$0.25,\emptyset,-0.5$, giving it a cost of $0.75+c_{u}+0$. After it moves, the
means are $0,\emptyset,\emptyset$, which gives it a cost of $0.5+2\cdot
c_{u}$. This is lower if $0.5+2\cdot c_{u}<0.75+c_{u}$, or $c_{u}<0.25$.

  * •

$\\{1,-0.5,-0.5\\},\\{\\},\\{\\}$ goes to $\\{-0.5,-0.5\\},\\{1\\},\\{\\}$.
The 1 player wishes to move. Before, the means are $-0.5,\emptyset,\emptyset$,
which gives it a cost of $1.5+c_{u}\cdot 2$. After it moves, the means are
$-0.5,1,\text{n/a}$, which gives it a cost of $1.5+0+c_{u}<1.5+2\cdot c_{u}$,
which is always satisfied.

  * •

$\\{-0.5,-0.5\\},\\{1\\},\\{\\}$ goes to $\\{-0.5,\\},\\{1\\},\\{-0.5\\}$. The
$-0.5$ player wishes to move. Before, the means are $-0.5,1,\emptyset$, which
gives it cost $0+1.5+c_{u}$. After it moves, the medians are $-0.5,1,-0.5$,
which gives it cost $0+1.5+0=1.5<1.5+c_{u}$, which is always satisfied.

These cases cover all possible arrangements, showing that there always exists
a agent that wishes to move. ∎

See 14

###### Proof.

There are five possible arrangements of 3 agents:

$\\{a\\},\\{b\\},\\{c\\}\quad\\{a,b\\},\\{c\\}\quad\\{a,c\\},\\{b\\}\quad\\{b,c\\},\\{a\\}\quad\\{a,b,c\\}$

We will use the notation

$\\{a,b\\},\\{\\}\rightarrow_{a}\\{a\\},\\{b\\}$

to mean that a player of type $A$ gets strictly lower cost when it leaves a
front it is competing in with type $B$ to compete in an empty front. We will
say $\\{a,b\\},\\{\\}\not\rightarrow_{a}\\{a\\},\\{b\\}$ when the player of
type $A$ does not get strictly lower cost in $\\{a\\},\\{b\\}$ and say
$\\{a\\},\\{b\\}\rightarrow_{a}\\{a,b\\},\\{\\}$ when the player of type $A$
gets strictly lower cost in $\\{a,b\\}$. Often, to be concise, we will drop
$\\{\\}$ terms and simply write $\\{a,b\\}\rightarrow_{a}\\{a\\},\\{b\\}$ as
the second front is left empty on the lefthand side.

First, we claim that:

$\\{a,b\\}\rightarrow_{a}\\{a\\},\\{b\\}\quad\Leftrightarrow\quad\\{a,b\\}\rightarrow_{b}\\{a\\},\\{b\\}$
(7)

Note that the lefthand term of Equation 7 is satisfied whenever:

$\left|f(\\{\beta_{a},\beta_{b}\\})-\beta_{a}\right|+c\leq
0+\left|f(\beta_{b})-\beta_{a}\right|$
$0.5\cdot\left|\beta_{b}-\beta_{a}\right|+c\leq\left|\beta_{b}-\beta_{a}\right|$

The righthand term of Equation 7 is satisfied whenever:

$\left|f(\\{\beta_{a},\beta_{b}\\})-\beta_{b}\right|+c\leq\left|f(\beta_{a})-\beta_{b}\right|+0$
$0.5\cdot\left|\beta_{b}-\beta_{a}\right|+c\leq\left|\beta_{b}-\beta_{a}\right|$

These terms are exactly equivalent, showing Equation 7 is satisfied. We will
use this result in the following analysis.

Next, we will show that if any two pairs of agents prefer competing in the
same front (as opposed to competing in different fronts), then it is the two
agents with most dissimilar biases (e.g. $i,j$ given
$\max_{i,j\in\\{a,b,c\\}}\left|\beta_{i}-\beta_{j}\right|$). In order to show
this, we will write out the cost that an agent of type $A$ gets for every
possible arrangement. Because agents are interchangable, this gives costs for
every other agent in different arrangements, up to relabeling.

$\displaystyle\\{a\\},\\{b\\},\\{c\\}\quad$
$\displaystyle\left|\beta_{b}-\beta_{a}\right|+\left|\beta_{c}-\beta_{a}\right|$
$\displaystyle\\{a,b\\},\\{c\\}\quad$ $\displaystyle
0.5\cdot\left|\beta_{b}-\beta_{a}\right|+\left|\beta_{c}-\beta_{a}\right|+c$
$\displaystyle\\{a,c\\},\\{b\\}\quad$ $\displaystyle
0.5\cdot\left|\beta_{a}-\beta_{c}\right|+\left|\beta_{b}-\beta_{a}\right|+c$
$\displaystyle\\{b,c\\},\\{a\\}\quad$ $\displaystyle
0.5\cdot\left|\beta_{b}+\beta_{c}-2\cdot\beta_{a}\right|+c$
$\displaystyle\\{a,b,c\\}\quad$
$\displaystyle\frac{1}{3}\cdot\left|\beta_{b}+\beta_{c}-2\cdot\beta_{a}\right|+2\cdot
c$

The second and third lines in the equations above show us that

$\\{a,b\\},\\{c\\}\rightarrow_{a}\\{a,c\\},\\{b\\}$

exactly whenever:

$0.5\cdot\left|\beta_{b}-\beta_{a}\right|+\left|\beta_{c}-\beta_{a}\right|+c>0.5\cdot\left|\beta_{a}-\beta_{c}\right|+\left|\beta_{c}-\beta_{a}\right|+c$
$\left|\beta_{c}-\beta_{a}\right|>\left|\beta_{b}-\beta_{a}\right|$

which is whenever $\beta_{c}$ is further from $\beta_{a}$ than $\beta_{b}$ is.
In this analysis, WLOG we will say that $\beta_{b},\beta_{c}$ are the most
dissimilar (because agents are interchangable, this is true up to relabeling).
Note that this implies that $\\{a,c\\},\\{b\\}$ and $\\{a,b\\},\\{c\\}$ can
never be stable, because both $b,c$ would prefer being together to being with
$a$.

Next, we can analyze some cases:
Case 1:
If the $\\{b,c\\},\\{a\\}\rightarrow_{b,c}\\{a\\},\\{b\\},\\{c\\}$, then
$\\{a\\},\\{b\\},\\{c\\}$ is stable.
We know from our prior reasoning that if the two most dissimlar players do not
wish to compete in the same front, then no other pair of players do. This
means that the arrangement with one agent per front is stable.

Case 2:
If:

$\\{a\\},\\{b\\},\\{c\\}\rightarrow_{b,c}\\{b,c\\},\\{a\\}\text{ and
}\\{b,c\\},\\{a\\}\not\rightarrow_{a}\\{a,b,c\\}$

then $\\{b,c\\},\\{a\\}$ is stable. This is because the $\\{b,c\\}$ pair
doesn’t wish to split up and the type $A$ player doesn’t wish to join.

Case 3:
If no player wishes to leave $\\{a,b,c\\}$ to compete in an empty front, then
$\\{a,b,c\\}$ is stable.
This is true simply by the statement: if no player wishes to move, then this
arrangement must be stable.

Case 4:
In this case, we will assume that:

$\\{a\\},\\{b\\},\\{c\\}\rightarrow_{b,c}\\{b,c\\},\\{a\\}\text{ and
}\\{b,c\\},\\{a\\}\rightarrow_{a}\\{a,b,c\\}$

We will also assume that at least one of $b,c$ wishes to leave $\\{a,b,c\\}$.
WLOG, we will assume it is $c$ (up to relabeling). Note that this implies none
of these arrangements can be stable:

$\\{a\\},\\{b\\},\\{c\\}\quad\\{b,c\\},\\{a\\}\quad\\{a,b,c\\}$

Additionally, by our prior reasoning, if players $b,c$ prefer competing
together to separate, then we know that no other pair can be stable:

$\\{a,b\\},\\{c\\}\quad\\{a,c\\},\\{b\\}$

The cycle that is given by this set of patterns is given by:

$\\{b,c\\},\\{a\\}\rightarrow_{a}\\{a,b,c\\}\rightarrow_{c}\\{a,b\\},\\{c\\}\rightarrow_{b,c}\\{a\\},\\{b,c\\}$

We will show that this type of cycle cannot exist.

Note that the first move occurs when:

$\left|\frac{\beta_{b}+\beta_{c}}{2}-\beta_{a}\right|>\left|\frac{\beta_{b}+\beta_{c}+\beta_{a}}{3}-\beta_{a}\right|+c$
$\left|\frac{\beta_{b}+\beta_{c}-2\beta_{a}}{2}\right|>\left|\frac{\beta_{b}+\beta_{c}+\beta_{a}-3\beta_{a}}{3}\right|+c$
$\frac{1}{6}\cdot\left|\beta_{b}+\beta_{c}-2\beta_{a}\right|>c$

The second move occurs when:

$\left|\frac{\beta_{a}+\beta_{b}+\beta_{c}}{3}-\beta_{c}\right|+c>\left|\frac{\beta_{a}+\beta_{b}}{2}-\beta_{c}\right|$
$\left|\frac{\beta_{a}+\beta_{b}-2\beta_{c}}{3}\right|+c>\left|\frac{\beta_{a}+\beta_{b}-2\beta_{c}}{2}\right|$
$c>\frac{1}{6}\cdot\left|\beta_{a}+\beta_{b}-2\beta_{c}\right|$

And the third move occurs when:

$0.5\cdot\left|\beta_{a}-\beta_{b}\right|+\left|\beta_{c}-\beta_{b}\right|>\left|\beta_{a}-\beta_{b}\right|+0.5\cdot\left|\beta_{c}-\beta_{b}\right|$
$0.5\cdot\left|\beta_{b}-\beta_{c}\right|>0.5\cdot\left|\beta_{a}-\beta_{b}\right|$

Putting these together, this implies:

$\left|\beta_{a}+\beta_{b}-2\beta_{c}\right|<\left|\beta_{b}+\beta_{c}-2\beta_{a}\right|$
(8) $\left|\beta_{a}-\beta_{b}\right|<\left|\beta_{b}-\beta_{c}\right|$ (9)

We will show that these pairs of inequalities cannot be simultaneously
satisfied. Set:

$x=\beta_{b}-\beta_{a}\quad y=\beta_{c}-\beta_{b}$

Then, Equation 9 becomes

$\left|-x\right|<\left|-y\right|$ $\left|x\right|<\left|y\right|$

For Equation 8 note that the LHS is given by:

$\left|\beta_{a}-\beta_{c}+\beta_{b}-\beta_{c}\right|=\left|-x-y-y\right|=\left|x+2y\right|$

where the equality is because:

$\left|-\beta_{b}+\beta_{a}-2\beta_{c}+2\beta_{b}\right|=\left|\beta_{a}+\beta-b-2\beta_{c}\right|$

as desired. The RHS is given by:

$\left|2\cdot x+y\right|$

Which is given by:

$\left|2\cdot(\beta_{b}-\beta_{a})+\beta_{c}-\beta_{b}\right|=\left|\beta_{b}+\beta_{c}-2\cdot\beta_{a}\right|$

So together, Equations 8 and 9 become:

$\left|x+2\cdot y\right|<\left|2\cdot x+y\right|$ (10)
$\left|x\right|<\left|y\right|$ (11)

Note that if both $x,y$ are positive, Eq. 10 becomes:

$x+2\cdot y<2\cdot x+y$ $y<x$

which directly contradicts Eq. 11 ($\left|x\right|=x<\left|y\right|=y$).
Similarly, if both $x,y$ are negative, then Eq. 10 becomes:

$-x-2\cdot y<-2\cdot x-y$ $-y<-x$

which contradicts Eq. 11 which has become

$-x<-y$

Finally, let’s consider the case where one of $x,y$ is positive and one is
negative. WLOG, say $x<0<y$. Then, we know that the LHS of Eq. 10 is positive
(because $\left|x\right|<\left|y\right|$ so $\left|x\right|<2\left|y\right|$,
which makes the overall $x+2\cdot y$ positive). This means that the RHS of Eq.
10 must be positive. If $2\cdot x+y>0$, then this becomes:

$x+2\cdot y<2\cdot x+y$ $y<x$

which is violated because $x<0<y$. If $2\cdot x+y<0$, then this becomes:

$x+2\cdot y<-2\cdot x-y$ $3\cdot x+3\cdot y<0$

which again violates $x<0<y$, with $\left|x\right|<\left|y\right|$ given by
Eq. 11.

Taken together, these cases cover all possible combination of stable
relations, showing that there can never be a cycle (and must always have a
stable point).

∎