# On the Problem of Resolvents

A Translation by Alexander J. Sutherland

##  1 Original Bibliographic Information

I thank Ignat Soroko for helpful comments on the bibliographic information.

###  1.1 Russian

  * •

Author: Г. Н. Чеботарев

  * •

Title: К Пpoблeмe Рeзoльвeнт

  * •

Year: 1954

  * •

Language: русский

  * •

Publisher: Учeныe Записки Казанского Государствeнного Унивeрситeта им. В. И.
Ульянова-Лeнина

###  1.2 English

  * •

Author: G.N. Chebotarev

  * •

Title: On the Problem of Resolvents

  * •

Year: 1954

  * •

Language: Russian

  * •

Publisher: Scientific Proceedings of the V.I. Ulyanov-Lenin Kazan State
University

This work was supported by the National Science Foundation under Grant No.
DMS-1944862.

##  2 The Translation

### On the Problem of Resolvents

111 Translator’s Note: This is a translation of the original mathematics. In
particular, errors in the text have not been fixed. The errors in question
come from considering intersections in affine spaces instead of in projective
spaces.

Consider an equation of $n^{th}$ degree

$f(x)=x^{n}+a_{1}x^{n-1}+\cdots+a_{n}=0$ (1)

whose coefficients $a_{1},\dotsc,a_{n}$ are indeterminates. Substituting

$\displaystyle y=t_{0}+t_{1}x+\cdots+t_{n-2}x^{n-2}+x^{n-1}$

into $f(x)=0$ yields an $n^{th}$ degree equation

$y^{n}+C_{1}y^{n-1}+C_{2}y^{n-2}+\cdots+C_{n}=0$ (2)

where the coefficients $C_{1},\dotsc,C_{n}$ depend rationally on
$a_{1},\dotsc,a_{n}$ and are polynomials in $t_{0},\dotsc,t_{n-2}$ of
respective degrees $1,\dotsc,n$.

Equation (2) is called an $s$-parameter resolvent of equation (1) if its
coefficients $C_{1},\dotsc,C_{n}$ are rational functions of $s$ parameters
$v_{1},\dotsc,v_{s}$ and the coefficients $t_{0},\dotsc,t_{n-2}$ of the
Tschirnhaus transformation depend rationally on $a_{1},\dotsc,a_{n}$ and the
roots of some auxiliary equations (secondary resolvents), which themselves
admit $s$-parameter resolvents.

It is easy to show that if one does not limit the degree of the secondary
resolvents, the $s$-parameter resolvent of equation (1) can be put in the
particular form

$y^{n}+C_{n-s}y^{s}+C_{n-s+1}y^{s-1}+\cdots+C_{n-1}y+1=0.$ (3)

In fact, let

$\displaystyle g(z)=z^{n}+B_{1}z^{n-1}+\cdots+B_{n}=0$

be an $s$-parameter resolvent of equation (1), i.e. $B_{1},\dotsc,B_{n}$ are
rational functions $s$ of parameters $v_{1},\dotsc,v_{s}$.

Take the new Tschirnhaus transformation

$\displaystyle y=\tau_{0}+\tau_{1}z+\cdots+\tau_{n-2}z^{n-2}+z^{n-1}.$

The coefficients $C_{1},\dotsc,C_{n}$ of the equation that $y$ satisfies are
polynomials of the corresponding degree in the $\tau_{0},\dotsc,\tau_{n-2}$
and, moreover, depend rationally on the coefficients $B_{1},\dotsc,B_{n}$ and
therefore on the parameters $v_{1},\dotsc,v_{s}$. Setting
$C_{1},\dotsc,C_{n-s-1}$ equal to zero and $C_{n}$ equal to 1 and composing
the results of these equations (in which $\tau_{0},\dotsc,\tau_{n-2}$ are
unknown), we obtain a chain of auxiliary equations whose coefficients depend
on $s$ parameters.

D. Hilbert (1) showed in his article ”On Equations of the Ninth Degree” that
an equation of the ninth degree admits a resolvent that depends on 4
parameters. His method of obtaining this resolvent is as follows.

The coefficients $t_{0},\dotsc,t_{n-2}$ of the Tschirnhaus transformation are
considered as the coordinates of a point in the space $T$ taking values from
the field of rational functions in $a_{1},\dotsc,a_{n}$ and its algebraic
extensions. The equations $C_{1}=0,C_{2}=0,C_{3}=0$ and $C_{4}=0$ determine
hypersurfaces in the space $T$ of degrees 1, 2, 3, and 4, respectively.
Finding a 4-parameter resolvent of an equation of $9^{th}$ degree reduces to
finding a common point of these hypersurfaces by solving a chain of algebraic
equations that admit $\leq 4$-parameter resolvents. Substituting
$y=\sqrt[n]{C_{n}}z$ makes the final term a unit.

This problem is solved by Hilbert as follows. A three-dimensional hyperplane
is found that entirely belongs to the hypersurfaces $C_{1}=0,C_{2}=0$. On it,
the surface $C_{3}=0$ cuts out a cubic surface, which, as you know, always
contains lines that lie entirely on it; to find these lines, one has to solve
an equation of the 27th degree which depends only on four parameters, since
the equation of the cubic surface allows a special technique based on the
subtle properties of cubic quarternary forms (by summing up five cubes that
are the roots of one equation of fifth-degree) which leads to a form that
depends on 4 parameters. The intersection of the line just found with the
hypersurface $C_{4}=0$ determines the desired point. Thus, to construct a
4-parameter resolvent of an equation of the $9^{th}$ degree, in addition to a
series of equations of degree between 2 and 5, it is necessary to solve an
equation of the $27^{th}$ degree, which is greater than the degree of the
original equation.

In the work ”On the Application of Tschirnhaus Transformations to the
Reduction of Algebraic Equations” (2), A. Wiman show that to obtain an
$(n-5)$-parameter resolvent of an equation of degree $n\geq 10$, it is
sufficient to solve several auxiliary one-parameter equations of degree no
higher than 4. To do this, he moves the origin to an intersection point of the
hypersurfaces $C_{1}=0,C_{2}=0,C_{3}=0$ and reduces the last two equations to
the form

$\displaystyle 0$ $\displaystyle=C_{2}=\phi_{2}$ $\displaystyle 0$
$\displaystyle=C_{3}=\psi_{2}+\psi_{3}$

where $\phi_{2}$ and $\psi_{2}$ are quadratic homogeneous forms and $\psi_{3}$
is a cubic homogeneous form, and using elegant geometric considerations,
searches for a two-dimensional plane that lies entirely in both the hypercones
$\phi_{2}=0$ and $\psi_{2}=0$. The intersection of this plane with the cubic
cone $\psi_{3}=0$ gives a straight line belonging to the surfaces $C_{1}=0$,
$C_{2}=0$, $C_{3}=0$.

For the case $n=9$, Wiman proves that in order to obtain a 4-parameter
resolvent, it is sufficient to only solve one auxiliary equation of 5th degree
(which has a one-parameter resolvent) in addition to the the equations of
degrees 1-4. To do this, he performs a linear transformation (which is
determined by solving an equation of fifth degree) which simultaneously
diagonalizes the forms $\phi_{2}=0$ and $\psi_{2}=0$ and defines a one-
parameter family of two-dimensional cones, all points of which belong to both
cones $\phi_{2}=0$ and $\psi_{2}=0$. By solving an equation of fourth degree,
we find the value of the parameter at which the cone of the family splits into
a pair of planes.

Applying the method of Wiman, we can find an $(n-6)$-parameter resolvent of an
equation of degree $n\geq 77$. In this article, an attempt is made to slightly
modify this method, as a result of which, the $(n-6)$-parameter resolvent can
be constructed for equations of degree $n\geq 21$.

Following Wiman, we consider the space $T_{n-1}$ of the parameters
$t_{0},\dotsc,t_{n-2}$ and the hypersurfaces
$C_{1}=0,C_{2}=0,C_{3}=0,C_{4}=0,C_{5}=0$ in this space. We move the origin to
a point common to the hypersurfaces $C_{1}=0,C_{2}=0,C_{3}=0$, which can be
determined by solving auxiliary equations of the second and third degree. Now,
in the equations of the first three surfaces, the free terms disappear and
these equations can be written as follows:

$\displaystyle 0$ $\displaystyle=C_{1}$ $\displaystyle 0$
$\displaystyle=C_{2}=\phi_{1}+\phi_{2}$ $\displaystyle 0$
$\displaystyle=C_{3}=\psi_{1}+\psi_{2}+\psi_{3}$

where $C_{1},\phi_{1},\psi_{1}$ are linear forms of the parameters $t_{i}$,
$\psi_{2},\phi_{2}$ are quadratic [forms], and $\psi_{3}$ is a cubic. The
equations $\phi_{1}=0$ and $\psi_{1}=0$ determine the hyperplanes tangent to
the hypersurfaces $C_{2}=0$ and $C_{3}=0$ at the origin. The intersection of
these hyperplanes with the hyperplane $C_{1}=0$ determines the space
$T_{n-4}$, in which the equations of the hypersurfaces cut out by $C_{2}=0$
and $C_{3}=0$ will have the form

$\displaystyle 0$ $\displaystyle=C_{2}^{\prime}=\phi_{2}^{\prime}$
$\displaystyle 0$
$\displaystyle=C_{3}^{\prime}=\psi_{2}^{\prime}+\psi_{3}^{\prime}.$

We show that for $n\geq 19$, there exists a two-dimensional plane belonging
entirely to the hypersurfaces $C_{2}^{\prime}=0$ and $C_{3}^{\prime}=0$ in the
space $T_{n-4}$.

######  Lemma 2.1.

Two $(3k-1)$-dimensional quadratic cones with a common vertex in
$3k$-dimensional space share a whole $k$-dimensional plane passing through the
vertex of the cones.

###### Proof.

We proceed by induction. Find straight-line generators common to both cones
(for this, it is enough to intersect both cones with any two-dimensional plane
that does not pass through their vertex, find the intersection point of the
two quadrics cut by the cones on the plane - which requires solving an
equation of fourth degree - and connect the found point to the vertex of the
cones). Take a plane of dimension $3k-1$ that does not pass through vertex of
the cones. On this hyperplane, our cones will cut out two hypersurfaces of
degree 2, the common point of which is rationally defined as the intersection
of the hyperplane and the previously found common [straight-line] generator of
the cones.

The intersection of the [original] hyperplane and the two [tangent]
hyperplanes touching these hypersurfaces at their common point defines a space
of $3k-3$ dimensions, in which out cones cut out a pair of cones of $3k-4$
dimensions with a common vertex, which contains a generic $k-1$ dimensional
linear space by the inductive hypothesis. The desired $k$-dimensional subspace
common to both cones is defined as the space passing through the
$(k-1)$-dimensional space and the vertex of the cones. ∎

######  Lemma 2.2.

A cubic four-dimensional cone in five-dimensional space contains a two-
dimensional plane passing through the top of the cone which lies entirely in
the cone.

###### Proof.

Intersect our cone with a four-dimensional plane that does not pass through
its top. The cone will cut out a three-dimensional cubic hypersurface on it.
We find a point on this surface (for which it is enough to solve one equation
of the third degree) and construct a three-dimensional hyperplane that is
tangent to the surface at this point. If, after moving the point to the
origin, the equation of the hypersurface has the form

$\displaystyle\phi_{1}+\phi_{2}+\phi_{3}=0,$

then the equation of the tangent hyperplane will be

$\displaystyle\phi_{1}=0.$

Consider the intersection of our surface with the given tangent hyperplane.
Obviously, the equation of this intersection will have the form

$\displaystyle\phi_{2}^{\prime}+\phi_{3}^{\prime}=0$

where $\phi_{2}^{\prime}$ and $\phi_{3}^{\prime}$ are forms of second and
third degree, respectively, in three variables. We consider the quadratic and
cubic cones

$\displaystyle\phi_{2}^{\prime}=0\text{ and }\phi_{3}^{\prime}=0$

with a common vertex in three-dimensional space. These cones have a common
straight line generator and it suffices to solve an equation of the sixth
degree to find it (determine the intersection point of the quadric and cubic
cut out by the cones on any two-dimensional plane not passing through their
vertex and connect it to the vertex of the cones). The two-dimensional plane
which passes through the [original] vertex and through the straight line just
found lies entirely in the original cubic cone. ∎

######  Theorem 2.3.

The general algebraic equation of degree $n\geq 21$ admits an
$(n-6)$-parameter resolvent.

###### Proof.

As above, consider the hypersurfaces

$\displaystyle C_{1}=0,\ C_{2}=0,\ C_{3}=0,\ C_{4}=0,\ C_{5}=0$

in the space $T_{n-1}$. We move the origin to a common point of the
hypersurfaces $C_{1}=0,\ C_{2}=0,\ C_{3}=0$. We construct tangent hyperplanes
to the hypersurfaces $C_{2}=0$ and $C_{3}=0$ at the origin and consider the
space $T_{n-4}$, which is the intersection of these hyperplanes with the
hyperplane $C_{1}=0$. In $T_{n-4}$, our surfaces $C_{2}^{\prime}=0$ and
$C_{3}^{\prime}=0$ are defined by equations of the form

$\displaystyle 0$ $\displaystyle=C_{2}^{\prime}=\phi_{2},$ $\displaystyle 0$
$\displaystyle=C_{3}^{\prime}=\psi_{2}+\psi_{3}.$

By virtue of Lemma 1 and as $n-4\geq 15$, the two cones

$\displaystyle\phi_{2}=0,\psi_{2}=0$

have a common 5-dimensional linear subspace. According to Lemma 2, the cubic
cone $\psi_{3}^{\prime}=0$ in this subspace contains a two-dimensional plane
and according to the above, we do not need to solve any equations above the
sixth degree to find one.

The hypersurfaces

$\displaystyle C_{4}=0\text{ and }C_{5}=0$

cut out curves of the $4^{th}$ and $5^{th}$ degree are cut out on this plane,
the intersection point of which can be found by solving an equation of the
$20^{th}$ degree, which, according to Wiman, has a resolvent that depends on
no more than 15 parameters. However, $n-6\geq 15$, which proves the theorem. ∎

This technique allows us to state the existence of $(n-7)$-parameter
resolvents of a general equation of degree $n\geq 121$.

### Literature

(1) D. Hilbert. Über die Gleichung neunten Grades. Ges. Abh., Bd. II, S. 393.
(2) A. Wiman. Über die Anwendung der Tschirnhausentransformationen auf die
Reduktion algebraischer Gleichungen. Nova Acta Regiae Societatis Scientiarum
Upsaliensis, volumen extra ordinem 1927.

Department of Algebra Received January 19, 1953.


# Tight Bounds on 3-Team Manipulations in Randomized Death Match

Atanas Dinev
Massachusetts Institute of Technology, Cambridge MA, USA  S. Matthew Weinberg
Princeton University, Princeton, USA

###### Abstract

Consider a round-robin tournament on $n$ teams, where a winner must be
(possibly randomly) selected as a function of the results from the
$\binom{n}{2}$ pairwise matches. A tournament rule is said to be
$k$-SNM-$\alpha$ if no set of $k$ teams can ever manipulate the $\binom{k}{2}$
pairwise matches between them to improve the joint probability that one of
these $k$ teams wins by more than $\alpha$. Prior work identifies multiple
simple tournament rules that are $2$-SNM-$1/3$ (Randomized Single Elimination
Bracket [SSW17], Randomized King of the Hill [SWZZ20], Randomized Death Match
[DW21]), which is optimal for $k=2$ among all Condorcet-consistent rules (that
is, rules that select an undefeated team with probability $1$).

Our main result establishes that Randomized Death Match is $3$-SNM-$(31/60)$,
which is tight (for Randomized Death Match). This is the first tight analysis
of any Condorcet-consistent tournament rule and at least three manipulating
teams. Our proof approach is novel in this domain: we explicitly find the
most-manipulable tournament, and directly show that no other tournament can be
more manipulable.

In addition to our main result, we establish that Randomized Death Match
disincentivizes Sybil attacks (where a team enters multiple copies of
themselves into the tournament, and arbitrarily manipulates the outcomes of
matches between their copies). Specifically, for any tournament, and any team
$u$ that is not a Condorcet winner, the probability that $u$ or one of its
Sybils wins in Randomized Death Match approaches $0$ as the number of Sybils
approaches $\infty$.

##  1 Introduction

Consider a tournament on $n$ teams competing to win a single prize via
$\binom{n}{2}$ pairwise matches. A tournament rule is a (possibly randomized)
map from these $\binom{n}{2}$ matches to a single winner. In line with several
recent works [AK10, APT10, SSW17, SWZZ20, DW21], we study rules that satisfy
some notion of fairness (that is, “better” teams should be more likely to
win), and non-manipulability (that is, teams have no incentive to manipulate
the matches).

More specifically, prior work identifies Condorcet-consistence (Definition
2.4) as one desirable property of tournament rules: whenever an undefeated
team exists, a Condorcet-consistent rule selects that team as the winner with
probability $1$. Another desirable property is monotonicity (Definition 2.6):
no team can unilaterally increase the probability that it wins by throwing a
single match. Arguably, any sensible tournament rule should at minimum satisfy
these two basic properties, and numerous such simple rules exist.

[APT10, AK10] further considered the following type of deviation: what if the
same company sponsors multiple teams in an eSports tournament, and wants to
maximize the probability that one of them wins the top prize?111Similarly,
perhaps there are multiple athletes representing the same country or
university in a traditional sports tournament. In principle, these teams might
manipulate the outcomes of the matches they play amongst themselves in order
to achieve this outcome. Specifically, they call a tournament rule
$k$-Strongly-Non-Manipulable ($k$-SNM, Definition 2.5), if no set of $k$ teams
can successfully manipulate the $\binom{k}{2}$ pairwise matches amongst
themselves to improve the probability that one of these $k$ teams wins the
tournament. Unfortunately, even for $k=2$, [APT10, AK10] establish that no
tournament rule is both Condorcet-consistent and $2$-SNM.

This motivated recent work in [SSW17, SWZZ20, DW21] to design tournament rules
which are Condorcet-consistent _as non-manipulable as possible_. Specifically,
[SSW17] defines a tournament rule to be $k$-SNM-$\alpha$ if no set of $k$
teams can manipulate the $\binom{k}{2}$ pairwise matches amongst themselves to
increase total probability that any of these $k$ teams wins _by more than
$\alpha$_ (see Definition 2.5). These works design several simple Condorcet-
consistent and $2$-SNM-$1/3$ tournament rules, which is optimal for $k=2$
[SSW17]. In fact, the state of affairs is now fairly advanced for $k=2$: each
of [SSW17, SWZZ20, DW21] proposes a new $2$-SNM-$1/3$ tournament rule.
[SWZZ20] considers a stronger fairness notion that they term Cover-consistent,
and [DW21] considers probabilistic tournaments (see Section 1.3 for further
discussion).

However, _significantly_ less is known for $k>2$. Indeed, only [SWZZ20]
analyzes manipulability for $k>2$. They design a rule that is $k$-SNM-$2/3$
for all $k$, but that rule is non-monotone, and it is unknown whether their
analysis of that rule is tight. Our main result provides a tight analysis of
the manipulability of Randomized Death Match [DW21] when $k=3$. We remark that
this is: a) the first tight analysis of the manipulability of any Condorcet-
consistent tournament rule for $k>2$, b) the first analysis establishing a
monotone tournament rule that is $k$-SNM-$\alpha$ for any $k>2$ and
$\alpha<1$, and c) the strongest analysis to-date of any tournament rule
(monotone or not) for $k=3$. We overview our main result in more detail in
Section 1.1 below.
Beyond our main result, we further consider manipulations through a _Sybil
attack_ (Definition 2.9). As a motivating example, imagine that a tournament
rule is used as a proxy for a voting rule to select a proposal (voters compare
each pair of proposals head-to-head, and this constitutes the pairwise matches
input to a tournament rule). A proposer may attempt to manipulate the protocol
with a Sybil attack, by submitting numerous nearly-identical clones of the
same proposal. This manipulates the original tournament, with a single node
$u_{1}$ corresponding to the proposal, into a new one with additional nodes
$u_{2},\ldots,u_{m}$ corresponding to the Sybils. Each node
$v\notin\\{u_{1},\ldots,u_{m}\\}$ either beats all the Sybils, or none of them
(because the Sybil proposals are essentially identical to the original). The
questions then become: Can the proposer profitably manipulate the matches
within the Sybils? Is it beneficial for a proposer to submit as many Sybils as
possible? We first show that, when participating in Randomized Death Match,
the Sybils can’t gain anything by manipulating the matches between them.
Perhaps more surprisingly, we show that Randomized Death Match is
_Asymptotically Strongly Sybil-Proof_ : as the number of Sybils approaches
$\infty$, the collective probability that a Sybil wins RDM approaches _zero_
(unless the original proposal is a Condorcet winner, in which case the
probability that a Sybil wins is equal to $1$, for any number of Sybils $>0$).

###  1.1 Our Results

As previously noted, our main result is a tight analysis of the manipulability
of Randomized Death Match (RDM) for coalitions of size $3$. Randomized Death
Match is the following simple rule: pick two uniformly random teams who have
not yet been eliminated, and eliminate the loser of their head-to-head match.

###### Informal Theorem 1.1

(See Theorem 4.1) RDM is 3-SNM-$\frac{31}{60}$. RDM is not 3-SNM-$\alpha$ for
$\alpha<\frac{31}{60}$.

Recall that this is the first tight analysis of any Condorcet-consistent
tournament rule for any $k>2$ and the first analysis establishing a monotone,
Condorcet-consistent tournament rule that is $k$-SNM-$\alpha$ for any $k>2$,
$\alpha<1$. Recall also that previously the smallest $\alpha$ for which a
$3$-SNM-$\alpha$ (non-monotone) Condorcet-consistent tournament rule is known
is $2/3$.

Our second result concerns manipulation by Sybil attacks. A Sybil attack is
where one team starts from a base tournament $T$, and adds some number $m-1$
of clones of their team to create a new tournament $T^{\prime}$ (they can
arbitrarily control the matches within their Sybils, but each Sybil beats
exactly the same set of teams as the cloned team) (See Definition 2.9). We say
that a tournament rule $r$ is _Asymptotically Strongly Sybil-Proof_
(Definition 2.10) if for any tournament $T$ and team $u_{1}\in T$ that is not
a Condorcet winner, the maximum collective probability that a Sybil wins
(under $r$) over all of $u_{1}$’s Sybil attacks with $m$ Sybils goes to 0 as
$m$ goes to infinity. See Section 2 for a formal definition.

###### Informal Theorem 1.2

(See Theorem 5.3) RDM is Asymptotically Strongly Sybil-Proof.

###  1.2 Technical Highlight

All prior work establishing that a particular tournament rule is $2$-SNM-$1/3$
follows a similar outline: for any $T$, cases where manipulating the
$\\{u,v\\}$ match could potentially improve the chances of winning are coupled
with two cases where manipulation cannot help. By using such a coupling
argument, it is plausible that one can show that RDM is
$3$-SNM-$(\frac{1}{2}+c)$ for a small constant $c$. However, given that
Theorem 4.1 establishes that RDM is $3$-SNM-$31/60$, it is hard to imagine
that this coupling approach will be tractable to obtain the exact answer.

Our approach is instead drastically different: we find a particular 5-team
tournament, and a manipulation by $3$ teams that gains $31/60$, and directly
prove that this must be the worst case. We implement our approach using a
first-step analysis, thinking of the first match played in RDM on an $n$-team
tournament as producing a distribution over $(n-1)$-team tournaments.

The complete analysis inevitably requires some careful case analysis, but is
tractable to execute fully by hand. Although this may no longer be the case
for future work that considers larger $k$ or more sophisticated tournament
rules, our approach will still be useful to limit the space of potential
worst-case examples.

###  1.3 Related Work

There is a vast literature on tournament rules, both within Social Choice
Theory, and within the broad CS community [Ban85, Fis77, FR92, GLM93, KSW17,
KW15, Mil80, SW11]. The Handbook of Computational Social Choice provides an
excellent survey of this broad field, which we cannot overview in its entirety
[Mou16]. Our work considers the model initially posed in [AK10, APT10], and
continued in [DW21, SSW17, SWZZ20], which we overview in more detail below.

[AK10, APT10] were the first to consider Tournament rules that are both
Condorcet-consistent and $2$-SNM, and proved that no such rules exist. They
further considered tournament rules that are $2$-SNM and approximately
Condorcet-consistent. [SSW17] first proposed to consider tournament rules that
are instead Condorcet-consistent and approximately $2$-SNM. Their work
establishes that Randomized Single Elimination Bracket is $2$-SNM-$1/3$, and
that this is tight.222Randomized Single Elimination Bracket iteratively places
the teams, randomly, into a single-elimination bracket, and then ‘plays’ all
matches that would occur in this bracket to determine a winner. [SWZZ20]
establish that Randomized King of the Hill (RKotH) is
$2$-SNM-$1/3$,333Randomized King of the Hill iteratively picks a ‘prince’, and
eliminates all teams beaten by the prince, until only one team remains. and
[DW21] establish that Randomized Death Match is $2$-SNM-$1/3$. [SWZZ20] show
further that RKotH satisfies a stronger fairness notion called Cover-
consistence, and [DW21] extends their analysis to probabilistic tournaments.
In summary, the state of affairs for $k=2$ is quite established: multiple
$2$-SNM-$1/3$ tournament rules are known, and multiple different extensions
beyond the initial model of [SSW17] are known.

For $k>2$, however, significantly less is known. [SSW17] gives a simple
example establishing that no rule is $k$-SNM-$\frac{k-1-\varepsilon}{2k-1}$
for any $\varepsilon>0$, but no rules are known to match this bound for any
$k>2$. Indeed, [SWZZ20] shows that this bound is not tight, and proves a
stronger lower bound for $k\rightarrow\infty$. For example, a corollary of
their main result is that no $939$-SNM-$1/2$ tournament rule exists. They also
design a non-monotone tournament rule that is $k$-SNM-$2/3$ for all $k$. Other
than these results, there is no prior work for manipulating sets of size
$k>2$. In comparison, our work is the first to give a tight analysis of any
Condorcet-consistent tournament rule for $k>2$, and is the first proof that
any monotone, Condorcet-consistent tournament rule is $k$-SNM-$\alpha$ for any
$k>2,\alpha<1$.
Regarding our study of Sybil attacks, similar clone manipulations have been
considered prior in Social Choice Theory under the name of _composition-
consistency_. [LLL96] introduces the notion of a _decomposition_ of the teams
in a tournament into components, where all the teams in a component are clones
of each other with respect to the teams not in the component. [LLL96] defines
a deterministic tournament rule to be _composition-consistent_ if it chooses
the best teams from the best components444For a full rigorous mathematical
definition see Definition 10, [LLL96]. In particular, composition-consistency
implies that a losing team cannot win by introducing clones of itself or any
other team. [LLL96] shows that the tournament rules Banks, Uncovered Set, TEQ,
and Minimal Covering Set are _composition-consistent_ , while Top Cycle, the
Slater, and the Copeland are not. Both computational and axiomatic aspects of
composition-consistency have been explored ever since. [EFS12] studies the
structural properties of clone sets and their computational aspects in the
context of voting preferences. In the context of probabilistic social choice,
[BBS16] gives probabilistic extensions of the axioms _composition-consistency_
and _population-consistency_ and uniquely characterize the probabilistic
social choice rules, which satisfy both. In the context of scoring rules,
[Özt20] studies the incompatibility of _composition-consistency_ and
_reinforcement_ (stronger than _population-consistency_) and decomposes
composition-consistency into four weaker axioms. In this work, we consider
Sybil attacks on Randomized Death Match. Our study of Sybil attacks differs
from prior work on the relevant notion of _composition-consistency_ in the
following ways: (i) We focus on a randomized tournament rule (RDM), (ii) We
study settings where the manipulator creates clones of themselves (i.e. not of
other teams), (iii) We explore the asymptotic behavior of such manipulations
(Definition 2.10, Theorem 5.3).

###  1.4 Roadmap

Section 2 follows with definitions and preliminaries, and formally defines
Randomized Death Match (RDM). Section 3 introduces some basic properties and
examples for the RDM rule as well as a recap of previous work for two
manipulators. Section 4 consists of a proof that the manipulability of 3 teams
in RDM is at most $\frac{31}{60}$ and that this bound is tight. Section 5
consists of our main results regarding Sybil attacks on a tournament. Section
6 concludes.

##  2 Preliminaries

In this section we introduce notation that we will use throughout the paper
consistent with prior work in [DW21, SSW17, SWZZ20].

######  Definition 2.1 (Tournament)

A (round robin) tournament $T$ on $n$ teams is a complete, directed graph on
$n$ vertices whose edges denote the outcome of a match between two teams. Team
$i$ beats team $j$ if the edge between them points from $i$ to $j$.

######  Definition 2.2 (Tournament Rule)

A tournament rule $r$ is a function that maps tournaments $T$ to a
distribution over teams, where $r_{i}(T):=\Pr(r(T)=i)$ denotes the probability
that team $i$ is declared the winner of tournament $T$ under rule $r$. We use
the shorthand $r_{S}(T):=\sum_{i\in S}r_{i}(T)$ to denote the probability that
a team in $S$ is declared the winner of tournament $T$ under rule $r$.

######  Definition 2.3 ($S$-adjacent)

Two tournaments $T,T^{\prime}$ are $S$-adjacent if for all $i,j$ such that
$\\{i,j\\}\not\subseteq S$, $i$ beats $j$ in $T$ if and only if $i$ beats $j$
in $T^{\prime}$.

In other words, two tournaments $T,T^{\prime}$ are $S$-adjacent if the teams
from $S$ can manipulate the outcomes of the matches between them in order to
obtain a new tournament $T^{\prime}$.

######  Definition 2.4 (Condorcet-Consistent)

Team $i$ is a Condorcet winner of a tournament $T$ if $i$ beats every other
team (under $T$). A tournament rule $r$ is Condorcet-consistent if for every
tournament $T$ with a Condorcet winner $i$, $r_{i}(T)=1$ (whenever $T$ has a
Condorcet winner, that team wins with probability 1).

######  Definition 2.5 (Manipulating a Tournament)

For a set $S$ of teams, a tournament $T$ and a tournament rule $r$, we define
$\alpha_{S}^{r}(T)$ be the maximum winning probability that $S$ can possibly
gain by manipulating $T$ to an $S$-adjacent $T^{\prime}$. That is:

$\alpha_{S}^{r}(T)=\max_{\textit{T': T' is S-adjacent to
T}}\\{r_{S}(T^{\prime})-r_{S}(T)\\}$

For a tournament rule $r$, define
$\alpha_{k,n}^{r}=\sup_{T,S:|S|=k,|T|=n}\\{\alpha_{S}^{r}(T)\\}$. Finally,
define

$\alpha_{k}^{r}=\sup_{n\in\mathbb{N}}\alpha_{k,n}^{r}=\sup_{T,S:|S|=k}\\{\alpha_{S}^{r}(T)\\}$

If $\alpha_{k}^{r}\leq\alpha$, we say that $r$ is $k$-Strongly-Non-Manipulable
at probability $\alpha$ or $k$-SNM-$\alpha$.

Intuitively, $\alpha_{k,n}^{r}$ is the maximum increase in collective winning
probability that a group of $k$ teams can achieve by manipulating the matches
between them over tournaments with $n$ teams. And $\alpha_{k}^{r}$ is the
maximum increases in winning probability that a group of $k$ teams can achieve
by manipulating the matches between them over all tournaments.

Two other naturally desirable properties of a tournament rule are monotonicity
and anonymity.

######  Definition 2.6 (Monotone)

A tournament rule $r$ is monotone if $T,T^{\prime}$ are $\\{u,v\\}$-adjacent
and $u$ beats $v$ in $T$, then $r_{u}(T)\geq r_{u}(T^{\prime})$

######  Definition 2.7 (Anonymous)

A tournament rule $r$ is anonymous if for every tournament $T$, and every
permutation $\sigma$, and all $i$, $r_{\sigma(i)}(\sigma(T))=r_{i}(T)$

Below we define the tournament rule that is the focus of this work.

######  Definition 2.8 (Randomized Death Match)

Given a tournament $T$ on $n$ teams the Randomized Death Match Rule (RDM)
picks two uniformly random teams (without replacement) and plays their match.
Then, eliminates the loser and recurses on the remaining teams for a total of
$n-1$ rounds until a single team remains, who is declared the winner.

Below we define the notions of Sybil Attack on a tournament $T$, and the
property of Asymptotically Strongly Sybil-Proof (ASSP) for a tournament rule
$r$, both of which will be relevant in our discussion in Section 5.

######  Definition 2.9 (Sybil Attack)

Given a tournament $T$, a team $u_{1}\in T$ and an integer $m$, define
$Syb(T,u_{1},m)$ to be the set of tournaments $T^{\prime}$ satisfying the
following properties:
1\. The set of teams in $T^{\prime}$ consists of $u_{2}\ldots,u_{m}$ and all
teams in $T$
2\. If $a,b$ are teams in $T$, then $a$ beats $b$ in $T^{\prime}$ if and only
if $a$ beats $b$ in $T$.
3\. If $a\neq u_{1}$ is a team in $T$ and $i\in[m]$, then $u_{i}$ beats $a$ in
$T^{\prime}$ if and only if $u_{1}$ beats $a$ in $T$
4\. The match between $u_{i}$ and $u_{j}$ can be arbitrary for each $i\neq j$

Intuitively, $Syb(T,u_{1},m)$ is the set of all Sybil attacks of $u_{1}$ at
$T$ with $m$ Sybils. Each Sybil attack is a tournament $T^{\prime}\in
Syb(T,u_{1},m)$ obtained by starting from $T$ and creating $m$ Sybils of
$u_{1}$ (while counting $u_{1}$ as a Sybil of itself). Each Sybil beats the
same set of teams from $T\setminus u_{1}$ and the matches between the Sybils
$u_{1},\ldots,u_{m}$ can be arbitrary. Every possible realization of the
matches between the Sybils gives rise to new tournament $T^{\prime}\in
Syb(T,u_{1},m)$ (implying $Syb(T,u_{1},m)$ contains $2^{\binom{m}{2}}$
tournaments).

######  Definition 2.10 (Asymptotically Strongly Sybil-Proof)

A tournament rule $r$ is Asymptotically Strongly Sybil-Proof (ASSP) if for any
tournament $T$, team $u_{1}\in T$ which is not a Condorcet winner,

$\lim_{m\to\infty}\max_{T^{\prime}\in
Syb(T,u_{1},m)}r_{u_{1},\ldots,u_{m}}(T^{\prime})=0$

Informally speaking, Definition 2.10 claims that $r$ is ASSP if the
probability that a Sybil wins in the most profitable Sybil attack on $T$ with
$m$ Sybils, goes to zero as $m$ goes to $\infty$.

##  3 Basic Properties of RDM and Examples

In this section we consider a few basic properties of RDM and several examples
on small tournaments. We will refer to those examples in our analysis later.
Throughout the paper we will denote RDM by $r$ and it will be the only
tournament rule we consider. We next state the first-step analysis observation
that will be central to our analysis throughout the paper. For the remainder
of the section let for a match $e$ denote by $T|_{e}$ the tournament obtained
from $T$ by eliminating the loser in $e$. Let $S|_{e}=S\setminus x$, where $x$
is the loser in $e$. Let $d_{x}$ denote the number of teams $x$ loses to and
$T\setminus x$ the tournament obtained after removing team $x$ from $T$.

######  Observation 3.1 (First-step analysis)

Let $S$ be a subset of teams in a tournament $T$. Then

$r_{S}(T)=\frac{1}{\binom{n}{2}}\sum_{e}r_{S|_{e}}(T|_{e})=\frac{1}{\binom{n}{2}}\sum_{x}d_{x}r_{S\setminus
x}(T\setminus x)$

(if $S=\\{v\\}$, then we define $r_{S\setminus v}(T\setminus v)=0$, and if
$x\not\in S$, then $S\setminus x=S$)

Proof. The first equality follows from the fact that after we play $e$ we are
left with the tournament $T|_{e}$ and we sum over all possible $e$ in the
first round. To prove the second equality, notice that for any $x$ the term
$r_{S\setminus x}(T\setminus x)$ appears exactly $d_{x}$ times in
$\sum_{e}r_{S|_{e}}(T|_{e})$ because $x$ loses exactly $d_{x}$ matches.

As a first illustration of first-step analysis we show that adding teams which
lose to every other team does not change the probability distribution of the
winner.

###### Lemma 3.2

Let $T$ be a tournament and $u\in T$ loses to everyone. Then for all $v\neq
u$, we have $r_{v}(T)=r_{v}(T\setminus u)$.

Proof. We prove the statement by induction on $|T|$. If $|T|=2$, then clearly
$r_{v}(T)=r_{v}(T\setminus u)=1$. Suppose it holds on all tournaments
$T^{\prime}$ such that $|T^{\prime}|<|T|=n$ and we will prove it for $T$. By
first-step analysis (Observation 3.1) we have that

$r_{v}(T)=\frac{1}{\binom{n}{2}}\sum_{e}r_{v}(T|_{e})=\frac{1}{\binom{n}{2}}\sum_{x\neq
v}d_{x}r_{v}(T\setminus x)$

where team $x$ loses $d_{x}$ matches in $T$. By the inductive hypothesis we
have that $r_{v}(T\setminus x)=r_{v}(T\setminus\\{x,u\\})$ for $x\neq u,v$ and
$d_{u}=n-1$. Thus,

$\displaystyle r_{v}(T)$ $\displaystyle=\frac{1}{\binom{n}{2}}\sum_{x\neq
v}d_{x}r_{v}(T\setminus x)=$
$\displaystyle=\frac{1}{\binom{n}{2}}(\sum_{x\notin\\{u,v\\}}d_{x}r_{v}(T\setminus\\{x,u\\})+(n-1)r_{v}(T\setminus
u))=$ $\displaystyle=\frac{1}{\binom{n}{2}}(\binom{n-1}{2}r_{v}(T\setminus
u)+(n-1)r_{v}(T\setminus u))=r_{v}(T\setminus u)$

where in the second to last line we used
$\sum_{x\notin\\{u,v\\}}d_{x}r_{v}(T\setminus\\{x,u\\})=\binom{n-1}{2}r_{v}(T\setminus
u)$, which follows from first-step analysis (Observation 3.1) and because $x$
loses $d_{x}$ matches in $T\setminus u$ as $u$ loses to every team in $T$

As a natural consequence of Lemma 3.2 we show that the most manipulable
tournament on $n+1$ teams is at least as manipulable as the most manipulable
tournament on $n$ teams.

###### Lemma 3.3

$\alpha_{k,n}^{r}\leq\alpha_{k,n+1}^{r}$

Proof. See Appendix A.1 for a proof.

We now show another natural property of RDM, which is a generalization of
Condorcet-consistent (Definition 2.4), namely that if a group of teams $S$
wins all its matches against the rest of teams, then a team from $S$ will
always win.

###### Lemma 3.4

Let $T$ be a tournament and $S\subseteq T$ a group of teams such that every
team in $S$ beats every team in $T\setminus S$. Then, $r_{S}(T)=1$.

Proof. See Appendix A.1 for a proof.

As a result of Lemma 3.4 RDM is Condorcet-Consistent. As expected, RDM is also
monotone (See Definition 2.6).

###### Lemma 3.5

RDM is monotone.

Proof. See Appendix A.1 for a proof.

Lemma 3.2 tells us that adding a team which loses to all other teams does not
change the probability distribution of the other teams winning. Lemmas 3.2,
3.3, 3.4, 3.5 will be useful in our later analysis in Sections 4 and 5. Now we
consider a few examples of tournaments and illustrate the use of first-step
analysis (Observation 3.1) to compute the probability distribution of the
winner in them.

  1. 1.

Let $T=\\{a,b,c\\}$, where $a$ beats $b$, $b$ beats $c$ and $c$ beats $a$. By
symmetry of RDM, we have $r_{a}(T)=r_{b}(T)=r_{c}(T)=\frac{1}{3}$.

  2. 2.

Let $T=\\{a,b,c\\}$ where $a$ beats $b$ and $c$. Then clearly, $r_{a}(T)=1$
and $r_{b}(T)=r_{c}(T)=0$.

  3. 3.

By Lemma 3.2, it follows that the only tournament on 4 teams whose probability
distribution cannot be reduced to a distribution on 3 teams is the following
one $T=\\{a_{1},a_{2},a_{3},a_{4}\\}$, where $a_{i}$ beats $a_{i+1}$ for
$i=1,2,3$, $a_{4}$ beats $a_{1}$, $a_{1}$ beats $a_{3}$ and $a_{2}$ beats
$a_{4}$. By using what we computed in (1) and (2) combined with Lemma 3.2 we
get by first step analysis

$\displaystyle r_{a_{1}}(T)$ $\displaystyle=\frac{1}{6}(r_{a_{1}}(T\setminus
a_{2})+2r_{a_{1}}(T\setminus a_{3})+2r_{a_{1}}(T\setminus
a_{4}))=\frac{1}{6}(\frac{1}{3}+\frac{2}{3}+2)=\frac{1}{2}$ $\displaystyle
r_{a_{2}}(T)$ $\displaystyle=\frac{1}{6}(r_{a_{2}}(T\setminus
a_{1})+2r_{a_{2}}(T\setminus a_{3})+2r_{a_{2}}(T\setminus
a_{4}))=\frac{1}{6}(1+\frac{2}{3})=\frac{5}{18}$ $\displaystyle r_{a_{3}}(T)$
$\displaystyle=\frac{1}{6}(r_{a_{3}}(T\setminus a_{1})+r_{a_{3}}(T\setminus
a_{2})+2r_{a_{3}}(T\setminus a_{4}))=\frac{1}{6}(\frac{1}{3})=\frac{1}{18}$
$\displaystyle r_{a_{4}}(T)$ $\displaystyle=\frac{1}{6}(r_{a_{4}}(T\setminus
a_{1})+r_{a_{4}}(T\setminus a_{2})+2r_{a_{4}}(T\setminus
a_{3}))=\frac{1}{6}(\frac{1}{3}+\frac{2}{3})=\frac{1}{6}$

The above examples are really important in our analysis because: a) we will
use them in later for our lower bound example in Section 4.1, and b) they are
a short illustration of first-step analysis.
In the following subsection, we review prior results for 2-team manipulations
in RDM, which will also be useful for our treatment of the main result in
Section 4.

###  3.1 Recap: Tight Bounds on 2-Team Manipulations in RDM

[DW21] (Theorem 5.2) proves that RDM is 2-SNM-$\frac{1}{3}$ and that this
bound is tight, namely $\alpha_{2}^{RDM}=\frac{1}{3}$. We will rely on this
result in Section 4.

###### Theorem 3.6

(Theorem 5.2 in [DW21]) $\alpha_{2}^{RDM}=\frac{1}{3}$

[SSW17] (Theorem 3.1) proves that the bound of $\frac{1}{3}$ is the best one
can hope to achieve for a Condorcet-consistent rule.

###### Theorem 3.7

(Theorem 3.1 in [SSW17]) There is no Condorcet-consistent tournament rule on
$n$ players (for $n\geq 3$) that is 2-SNM-$\alpha$ for $\alpha<\frac{1}{3}$

We prove the following useful corollary, which will be useful in Section 4.

###### Corollary 3.8

Let $T$ be a tournament and $u,v\in T$ two teams such that there is at most
one match in which a team in $\\{u,v\\}$ loses to a team in
$T\setminus\\{u,v\\}$. Then

$r_{u,v}(T)\geq\frac{2}{3}$

Proof. If $u$ and $v$ beat every team in $T\setminus\\{u,v\\}$, then by Lemma
3.4, $r_{u,v}(T)=1\geq\frac{2}{3}$. WLOG suppose that there is some team $t$
which beats $u$, loses to $v$ and all other teams lose to both $u$ and $v$.
Let $T^{\prime}$ be $\\{u,v\\}$-adjacent to $T$ such that $v$ is a Condorcet
winner in $T^{\prime}$. Clearly we have $r_{u,v}(T^{\prime})=1$ as RDM is
Condorcet-Consistent. By Theorem 3.6 we have
$r_{u,v}(T^{\prime})-r_{u,v}(T)\leq\frac{1}{3}$. This, implies that
$r_{u,v}(T)\geq\frac{2}{3}$ as desired.

##  4 Main Result: $\alpha^{RDM}_{3}=31/60$

The goal of this section is to prove that no 3 teams can improve their
probability of winning by more than $\frac{31}{60}$ and that this bound is
tight. We prove the following theorem

###### Theorem 4.1

$\alpha_{3}^{RDM}=\frac{31}{60}$

Our proof consists of two parts:

  * •

Lower bound: $\alpha_{3}^{RDM}\geq\frac{31}{60}$, for which we provide a
tournament $T$ and a set $S$ of size 3, which can manipulate to increase their
probability by $\frac{31}{60}$

  * •

Upper bound: $\alpha_{3}^{RDM}\leq\frac{31}{60}$, for which we provide a proof
that for any tournament $T$ no set $S$ of size 3 can increase their
probability of winning by more than $\frac{31}{60}$, i.e. RDM is
3-SNM-$\frac{31}{60}$

###  4.1 Lower Bound

Let $r$ denote RDM. Denote by $B_{x}$ the set of teams which team $x$ beats.
Consider the following tournament $T=\\{u,v,w,a,b\\}$ (shown in Fig 1):

$B_{a}=\\{u,v,b\\},B_{b}=\\{u,v\\},B_{u}=\\{v,w\\},B_{v}=\\{w\\},B_{w}=\\{a,b\\}$

The tournament is also shown in Figure 1. Let $S=\\{u,v,w\\}$. By first-step
analysis (Observation 3.1) and by using our knowledge in Section 3 for
tournaments on 4 teams we can write

$\displaystyle r_{u,v,w}(T)$ $\displaystyle=\frac{1}{10}(3r_{u,w}(T\setminus
v)+2r_{u,v}(T\setminus w)+2r_{u,v,w}(T\setminus b)+r_{u,v,w}(T\setminus
a)+2r_{v,w}(T\setminus u))=$
$\displaystyle=\frac{1}{10}(3\times(\frac{1}{2}+\frac{1}{6})+2\times
0+2\times(\frac{5}{18}+\frac{1}{18}+\frac{1}{6})+(\frac{5}{18}+\frac{1}{18}+\frac{1}{6})+2\times(\frac{1}{2}+\frac{1}{6}))=$
$\displaystyle=\frac{1}{10}(2+1+\frac{1}{2}+\frac{4}{3})=\frac{29}{60}$

Now suppose that $u$ and $v$ throw their matches with $w$. i.e. $T^{\prime}$
is $S$-adjacent to $T$, where in $T^{\prime}$, $w$ beats $u$ and $v$ and all
other matches have the same outcomes as in $T$. Then, since $w$ is a Condorcet
winner, $r_{u,v,w}(T^{\prime})=r_{w}(T^{\prime})=1$. Therefore,

$\alpha_{3}^{RDM}\geq
r_{u,v,w}(T^{\prime})-r_{u,v,w}(T)=1-\frac{29}{60}=\frac{31}{60}$

Thus, $\alpha_{3}^{RDM}\geq\frac{31}{60}$ as desired.

Figure 1: The tournament $T$ in which $S=\\{u,v,w\\}$ achieves a gain of
$\frac{31}{60}$ by manipulation.

###  4.2 Upper Bound

Suppose we have a tournament $T$ on $n\geq 3$ vertices and $S=\\{u,v,w\\}$ is
a set of 3 (distinct) teams, where $S$ will be the set of manipulator teams.
Let $I$ be the set of matches in which a team from $S$ loses to a team from
$T\setminus S$. Our proof for $\alpha^{RDM}_{k}\leq\frac{31}{60}$ will use the
following strategy

  * •

In Sections 4.2.1 and 4.2.2 we introduce the first-step analysis framework by
considering possible cases for the first played match. In each of these cases
the loser of the match is eliminated and we are left with a tournament with
one less team. We pair each match in $T$ with its corresponding match in
$T^{\prime}$ and we bound the gains of manipulation in each of the following
cases separately (these correspond to each of the terms $A,B$, and $C$
respectively in the analysis in Section 4.2.2).

    * –

The first match is between two teams in $S$ (there are 3 such matches).

    * –

The first match is between a team in $S$ and a team in $T\setminus S$ and the
team from $S$ loses in the match (there are $|I|$ such matches).

    * –

The first match is any other match not covered by the above two cases

  * •

In Section 4.2.3 we prove that if $|I|\leq 4$, then
$\alpha^{RDM}_{S}(T)\leq\frac{31}{60}$ (i.e. the set of manipulators cannot
gain more than $\frac{31}{60}$ by manipulating).

  * •

In Section 4.2.4 we prove that if $T$ is the most manipulable tournament on
$n$ vertices (i.e. $\alpha^{RDM}_{S}(T)=\alpha_{3,n}^{RDM}$), then
$\alpha^{RDM}_{S}(T)\leq\frac{|I|+7}{3(|I|+3)}$

  * •

In Section 4.2.5 we combine the above facts to finish the proof of Theorem 4.1

We first introduce some notation that we will use throughout this section.
Suppose that $T^{\prime}$ and $T$ are $S$-adjacent. Recall from Section 3 that
for a match $e=(i,j)$, $T|_{e}$ is the tournament obtained after eliminating
the loser in $e$. Also $d_{x}$ is the number of teams that a team $x$ loses to
in $T$. For $x\in S$, let $\ell_{x}$ denote the number of matches $x$ loses
against a team in $S$ when considered in $T$ and let $\ell^{\prime}_{x}$
denote the number of matches that $x$ loses against a team in $S$ when
considered in $T^{\prime}$. Let $d^{*}_{x}$ denote the number of teams in
$T\setminus S$ that $x$ loses to. Notice that since $T$ and $T^{\prime}$ are
$S$-adjacent, $x\in S$ loses to exactly $d^{*}_{x}$ teams in
$T^{\prime}\setminus S$ when considered in $T^{\prime}$. Let
$G=I\cup\\{uv,vw,uw\\}$ be the set of matches in which a team from $S$ loses.

####  4.2.1 The First Step Analysis Framework

Notice that in the first round of RDM, a uniformly random match $e$ from the
$\binom{n}{2}$ matches is chosen. If $e\in G$ then we are left with
$T\setminus x$ where $x$ loses in $e$ for some $x\in S$. If $e\not\in G$, we
are left with $T|_{e}$ and all teams in $S$ are still in the tournament. For
$x\in S$, there are $\ell_{x}$ matches in which they lose to a team from $S$
and $d^{*}_{x}$ matches in which they lose to a team from $T\setminus S$. By
considering each of these cases and using first-step analysis (Observation
3.1), we have

$\displaystyle r_{u,v,w}(T)$
$\displaystyle=\frac{1}{\binom{n}{2}}\Bigg{[}\sum_{x\in\\{u,v,w\\}}\ell_{x}r_{\\{u,v,w\\}\setminus
x}(T\setminus x)+d^{*}_{u}r_{v,w}(T\setminus u)+d^{*}_{v}r_{u,w}(T\setminus
v)+d^{*}_{w}r_{v,u}(T\setminus w)$ $\displaystyle+\sum_{e\notin
G}r_{u,v,w}(T|_{e})\Bigg{]}$

Since $T$ and $T^{\prime}$ are $S$-adjacent each $x\in S$ loses to exactly
$d^{*}_{x}$, teams form $T^{\prime}\setminus S$, and we can similarly write

$\displaystyle r_{u,v,w}(T^{\prime})$
$\displaystyle=\frac{1}{\binom{n}{2}}\Bigg{[}\sum_{x\in\\{u,v,w\\}}\ell^{\prime}_{x}r_{\\{u,v,w\\}\setminus
x}(T^{\prime}\setminus x)+d^{*}_{u}r_{v,w}(T^{\prime}\setminus
u)+d^{*}_{v}r_{u,w}(T^{\prime}\setminus
v)+d^{*}_{w}r_{v,u}(T^{\prime}\setminus w)$ $\displaystyle+\sum_{e\notin
G}r_{u,v,w}(T^{\prime}|_{e})\Bigg{]}$

By subtracting the above two expression we get

$\displaystyle r_{u,v,w}(T^{\prime})-r_{u,v,w}(T)=$
$\displaystyle=\frac{1}{\binom{n}{2}}\Bigg{[}\sum_{x\in\\{u,v,w\\}}\ell^{\prime}_{x}r_{\\{u,v,w\\}\setminus
x}(T^{\prime}\setminus x)-\ell_{x}r_{\\{u,v,w\\}\setminus x}(T\setminus
x)+d^{*}_{u}(r_{\\{v,w\\}}(T^{\prime}\setminus u)-r_{\\{v,w\\}}(T\setminus
u))$ $\displaystyle+d^{*}_{v}(r_{\\{u,w\\}}(T^{\prime}\setminus
v)-r_{\\{u,w\\}}(T\setminus v))+d^{*}_{w}(r_{\\{v,u\\}}(T^{\prime}\setminus
w)-r_{\\{v,u\\}}(T\setminus w))$ $\displaystyle+\sum_{e\notin
G}r_{u,v,w}(T^{\prime}|_{e})-r_{u,v,w}(T|_{e})\Bigg{]}$

Thus,

$r_{u,v,w}(T^{\prime})-r_{u,v,w}(T)=\frac{1}{\binom{n}{2}}(A+B+C)$ (1)

where

$\displaystyle A$
$\displaystyle=\sum_{x\in\\{u,v,w\\}}\ell^{\prime}_{x}r_{\\{u,v,w\\}\setminus
x}(T^{\prime}\setminus x)-\ell_{x}r_{\\{u,v,w\\}\setminus x}(T\setminus x)$
$\displaystyle B$ $\displaystyle=\sum_{x\in
S}d^{*}_{x}(r_{\\{u,v,w\\}\setminus x}(T^{\prime}\setminus
x)-r_{\\{u,v,w\\}\setminus x}(T\setminus x))$ $\displaystyle C$
$\displaystyle=\sum_{e\notin G}r_{u,v,w}(T^{\prime}|_{e})-r_{u,v,w}(T|_{e})$

####  4.2.2 Upper Bounds on $A,B$ and $C$

We now prove some bounds on the terms $A$, $B$ and $C$ (defined in Section
4.2.1) which will be useful later. Recall that $I$ denotes the set of matches
in which a team from $S$ loses from a team from $T\setminus S$. We begin with
bounding $A$ in the following lemma

###### Lemma 4.2

For all $S$-adjacent $T$ and $T^{\prime}$, we have $A\leq\frac{7}{3}$.
Moreover, if $|I|\leq 1$, then $A\leq 1$.

Proof. See Appendix A.2 for a proof.

Next, we show the following bound on the term $B$.

###### Lemma 4.3

For all $S$-adjacent $T,T^{\prime}$ we have

$B\leq\frac{d^{*}_{u}+d^{*}_{v}+d^{*}_{w}}{3}=\frac{|I|}{3}$

Moreover, if $|I|\leq 1$, then $B=0$

Proof. See Appendix A.2 for a proof.

We introduce some more notation. For $n\in\mathbb{N}$, define
$M_{n}(a_{1},a_{2},a_{3})$ as the maximum winning probability gain that three
teams $\\{u,v,w\\}$ can achieve by manipulation in a tournament $T$ of size
$n$, in which there are exactly $a_{i}$ teams in $T\setminus S$ each of which
beats exactly $i$ teams of $S$. Formally,

$\displaystyle M_{n}(a_{1},a_{2},a_{3})$
$\displaystyle=\max\Big{\\{}r_{S}(T^{\prime})-r_{S}(T)|T,T^{\prime}\text{ are
}S\text{-adjacent},|T|=n,|S|=3,$ $\displaystyle\text{ $a_{i}$ teams in
$T\setminus S$ beat exactly $i$ teams in $S$}\Big{\\}}$

Additionally, let $L_{i}$ be the set of teams in $T\setminus S$ each of which
beats exactly $i$ teams in $S$. Let $Q$ be the set of matches in which two
teams from $L_{i}$ play against each other or in which a team from $L_{i}$
loses to a team from $S$ for $i=1,2,3$. Notice that
$|Q|=2a_{1}+a_{2}+\binom{a_{1}}{2}+\binom{a_{2}}{2}+\binom{a_{3}}{2}$ if there
are $a_{i}$ teams in $S\setminus T$ each which beat $i$ teams from $S$.
With the new notation, we are now ready to prove a bound on the term $C$.
Recall that

$C=\sum_{e\notin G}r_{u,v,w}(T^{\prime}|_{e})-r_{u,v,w}(T|_{e})$

where $G=I\cup\\{uv,vw,uw\\}$ is the set of matches in which a team from $S$
loses. Then we have the following bound on $C$.

###### Lemma 4.4

For all $S$-adjacent $T$ and $T^{\prime}$ we have that $C$ is at most

$\displaystyle(2a_{1}+\binom{a_{1}}{2})M_{n-1}(a_{1}-1,a_{2},a_{3})+(a_{2}+\binom{a_{2}}{2})M_{n-1}(a_{1},a_{2}-1,a_{3})+\binom{a_{3}}{2}M_{n}(a_{1},a_{2},a_{3}-1)$
$\displaystyle+\sum_{e\notin G\cup
Q}r_{u,v,w}(T^{\prime}|_{e})-r_{u,v,w}(T|_{e})$

Proof. See Appendix A.2 for a proof.

####  4.2.3  The case $|I|\leq 4$

We summarize our claim when $|I|\leq 4$ in the following lemma

###### Lemma 4.5

Let $T$ be a tournament, and $S$ a set of 3 teams. Suppose that there are at
most 4 matches in which a team in $S$ loses to a team in $T\setminus S$ (i.e.
$|I|\leq 4$). Then $\alpha^{RDM}_{S}(T)\leq\frac{31}{60}$

Proof. We will show that $M_{n}(a_{1},a_{2},a_{3})\leq f(a_{1},a_{2},a_{3})$
by induction on $n\in\mathbb{N}$ for the values of $(a_{1},a_{2},a_{3})$ and
$f(a_{1},a_{2},a_{3})$ given in Table 1 below. Notice that when there are at
most 4 matches between a team in $S$ and a team in $T\setminus S$, in which
the teams from $S$ loses, then we fall into one of the cases shown in the
table for $(a_{1},a_{2},a_{3})$.

$(a_{1},a_{2},a_{3})$ |  $f(a_{1},a_{2},a_{3})$
---|---
(0,0,0) |  0
(1,0,0) |  $\frac{1}{6}$
(2,0,0) |  $\frac{23}{60}$
(3,0,0) |  $\frac{407}{900}$
(4,0,0) |  $\frac{4499}{9450}$
(0,1,0) |  $\frac{1}{2}$
(0,2,0) |  $\frac{31}{60}$
(1,1,0) |  $\frac{1}{2}$
(2,1,0) |  $\frac{131}{260}$
(0,0,1) |  0
(1,0,1) |  $\frac{11}{27}$
Table 1: Upper bounds on $M_{n}(a_{1},a_{2},a_{3})$

1\. Base case Our base case is when $n=3$. If we are in the case of 3 teams
then $S$ wins with probability 1, so the maximum gain $S$ can achieve by
manipulation is clearly 0, which satisfies all of the bounds in the table.
2\. Induction step Assume that $M_{k}(a_{1},a_{2},a_{3})\leq
f(a_{1},a_{2},a_{3})$ hold for all $k<n$ and $a_{1},a_{2},a_{3}$ as in Table
1. We will prove the statement for $k=n$. Notice that by Table 1 it is clear
that $f$ is monotone in each variable i.e. if $a^{\prime}_{i}\leq a_{i}$ for
$i=1,2,3$, then

$f(a^{\prime}_{1},a^{\prime}_{2},a^{\prime}_{3})\leq f(a_{1},a_{2},a_{3})$ (2)

Suppose that $e\notin G\cup Q$555Recall $G$ is the set of matches in which a
team from $S$ loses and $Q$ is the set of matches in between two teams from
$L_{i}$ or when a team from $L_{i}$ loses to a team from $S$ (see discussion
before Lemma 4.4). Then since $e\notin G$, $S$ remains in $T|_{e}$. Let for a
tournament $H$ define $t(H)=(a^{\prime}_{1},a^{\prime}_{2},a^{\prime}_{3})$,
where in $H$ there are exactly $a^{\prime}_{i}$ teams in
$H\setminus\\{u,v,w\\}$ that beat exactly $i$ out of $\\{u,v,w\\}$. Clearly,
we have $t(T|_{e})=(a^{\prime}_{1},a^{\prime}_{2},a^{\prime}_{3})$, where
$a^{\prime}_{i}\leq a_{i}$. By monotonicity of $f$ in (2) and the inductive
hypothesis it follows that

$r_{u,v,w}(T^{\prime}|_{e})-r_{u,v,w}(T|_{e})\leq
M_{n-1}(a^{\prime}_{1},a^{\prime}_{2},a^{\prime}_{3})\leq
f(a^{\prime}_{1},a^{\prime}_{2},a^{\prime}_{3})\leq f(a_{1},a_{2},a_{3})$

Since $|G\cup
Q|=3(1+a_{1}+a_{2}+a_{3})+\binom{a_{1}}{2}+\binom{a_{2}}{2}+\binom{a_{3}}{2}$,
we have that

$\sum_{e\notin G\cup
Q}r_{u,v,w}(T^{\prime}|_{e})-r_{u,v,w}(T|_{e})\leq(\binom{n}{2}-3(1+a_{1}+a_{2}+a_{3})-\binom{a_{1}}{2}-\binom{a_{2}}{2}-\binom{a_{3}}{2})f(a_{1},a_{2},a_{3})$

Also, by the inductive hypothesis we have

$\displaystyle M_{n-1}(a_{1}-1,a_{2},a_{3})$ $\displaystyle\leq
f(a_{1}-1,a_{2},a_{3})$ $\displaystyle M_{n-1}(a_{1},a_{2}-1,a_{3})$
$\displaystyle\leq f(a_{1},a_{2}-1,a_{3})$ $\displaystyle
M_{n-1}(a_{1},a_{2},a_{3}-1)$ $\displaystyle\leq f(a_{1},a_{2},a_{3}-1)$

Therefore, by Lemma 4.4, combined with the inequalities above we have

$\displaystyle C$
$\displaystyle\leq(2a_{1}+\binom{a_{1}}{2})f(a_{1}-1,a_{2},a_{3})+(a_{2}+\binom{a_{2}}{2})f(a_{1},a_{2}-1,a_{3})+\binom{a_{3}}{2}f(a_{1},a_{2},a_{3}-1)$
$\displaystyle+(\binom{n}{2}-3(1+a_{1}+a_{2}+a_{3})-\binom{a_{1}}{2}-\binom{a_{2}}{2}-\binom{a_{3}}{2})f(a_{1},a_{2},a_{3})$

By Lemma 4.3 we have

$B\leq\frac{d^{*}_{u}+d^{*}_{v}+d^{*}_{w}}{3}=\frac{a_{1}+2a_{2}+3a_{3}}{3}=\frac{|I|}{3}$

Combining the above with bounds and plugging into $(\ref{fsa:1})$ we get

$\displaystyle
r_{u,v,w}(T^{\prime})-r_{u,v,w}(T)\leq\frac{1}{\binom{n}{2}}(A+B+C)\leq$
$\displaystyle\leq\frac{1}{\binom{n}{2}}\Bigg{[}A^{\prime}+B^{\prime}+(2a_{1}+\binom{a_{1}}{2})f(a_{1}-1,a_{2},a_{3})+(a_{2}+\binom{a_{2}}{2})f(a_{1},a_{2}-1,a_{3})$
$\displaystyle+\binom{a_{3}}{2}f(a_{1},a_{2},a_{3}-1)+(\binom{n}{2}-3(1+a_{1}+a_{2}+a_{3})-\binom{a_{1}}{2}-\binom{a_{2}}{2}-\binom{a_{3}}{2})f(a_{1},a_{2},a_{3})\Bigg{]}$

where $A^{\prime}=1$ and $B^{\prime}=0$ if $|I|\leq 1$ and
$A^{\prime}=\frac{7}{3}$ and $B^{\prime}=\frac{|I|}{3}$ if $|I|\geq 2$ by
Lemma 4.2 and Lemma 4.3. As the RHS depends only on $(a_{1},a_{2},a_{3})$ we
can take the maximum over all tournaments on $n$ teams so we can get

$\displaystyle M_{n}(a_{1},a_{2},a_{3})$
$\displaystyle\leq\frac{1}{\binom{n}{2}}\Bigg{[}A^{\prime}+B^{\prime}+(2a_{1}+\binom{a_{1}}{2})f(a_{1}-1,a_{2},a_{3})+(a_{2}+\binom{a_{2}}{2})f(a_{1},a_{2}-1,a_{3})$
$\displaystyle+\binom{a_{3}}{2}f(a_{1},a_{2},a_{3}-1)$
$\displaystyle+(\binom{n}{2}-3(1+a_{1}+a_{2}+a_{3})-\binom{a_{1}}{2}-\binom{a_{2}}{2}-\binom{a_{3}}{2})f(a_{1},a_{2},a_{3})\Bigg{]}\text{
($\Delta$)}$

Now, apply the formula $(\Delta)$ to each of the cases in Table 1. We present
the computations for $(a_{1},a_{2},a_{3})\in\\{(0,0,0),(1,0,0),(0,2,0)\\}$ in
the body to illustrate the method and we defer the other cases from Table 1 to
Appendix A.2. Note the manipulators can achieve $\frac{31}{60}$ only when
$(a_{1},a_{2},a_{3})=(0,2,0)$.

Case 1 $(a_{1},a_{2},a_{3})=(0,0,0)$. By Lemma 3.4 it follows that
$M_{n}(0,0,0)=0=f(0,0,0)$ as a team from $S$ wins with probability 1
regardless of the matches within $S$.

Case 2 $(a_{1},a_{2},a_{3})=(1,0,0)$. In this case $|I|=1$. So by applying
$\Delta$ with $A^{\prime}=1$ and $B=0$ we obtain

$M_{n}(1,0,0)\leq\frac{1}{\binom{n}{2}}(1+2f(0,0,0)+(\binom{n}{2}-6)\frac{1}{6})=\frac{1}{6}=f(1,0,0)$

Case 3 $(a_{1},a_{2},a_{3})=(0,2,0)$. Applying $\Delta$, we get

$\displaystyle M_{n}(0,2,0)$
$\displaystyle\leq\frac{1}{\binom{n}{2}}(\frac{7}{3}+\frac{4}{3}+(2+1)f(0,1,0)+(\binom{n}{2}-10)f(0,2,0))$
$\displaystyle=\frac{1}{\binom{n}{2}}(\frac{11}{3}+\frac{3}{2}+(\binom{n}{2}-10)\frac{31}{60})$
$\displaystyle=\frac{31}{60}+\frac{1}{\binom{n}{2}}(\frac{22+9}{6}-\frac{31}{6})=\frac{31}{60}=f(0,2,0)$

Case 4 $(a_{1},a_{2},a_{3})=(2,0,0)$. See Appendix A.2.

Case 5 $(a_{1},a_{2},a_{3})=(3,0,0)$. See Appendix A.2.

Case 6 $(a_{1},a_{2},a_{3})=(4,0,0)$. See Appendix A.2.

Case 7 $(a_{1},a_{2},a_{3})=(0,1,0)$. See Appendix A.2.

Case 8 $(a_{1},a_{2},a_{3})=(1,1,0)$. See Appendix A.2.

Case 9 $(a_{1},a_{2},a_{3})=(2,1,0)$. See Appendix A.2.

Case 10 $(a_{1},a_{2},a_{3})=(0,0,1)$. See Appendix A.2.

Case 11 $(a_{1},a_{2},a_{3})=(1,0,1)$. See Appendix A.2.

This, finishes the induction and the proof for the bounds in Table 1. Note
that $f(a_{1},a_{2},a_{3})\leq\frac{31}{60}$ for all $a_{1},a_{2},a_{3}$ in
Table 1 and this bounds is achieved when $(a_{1},a_{2},a_{3})=(0,2,0)$ i.e.
there are 2 teams that beat exactly two of $S$ as is the case in the optimal
example in Section 4.1. Thus,we get that if there are at most 4 matches that a
team from $S$ loses from a team in $T\setminus S$, then
$\alpha^{RDM}_{S}(T)\leq\frac{31}{60}$. This finishes the proof of the lemma.

####  4.2.4 General Upper Bound for the Most Manipulable Tournament

###### Lemma 4.6

Suppose that $\alpha^{RDM}_{S}(T)=\alpha^{RDM}_{3,n}$. Let $I$ be the set of
matches a team of $S$ loses to a team from $T\setminus S$. Then

$\alpha^{RDM}_{3,n}=\alpha^{RDM}_{S}(T)\leq\frac{|I|+7}{3(|I|+3)}$

Proof. Let $T$ and $T^{\prime}$ be $S$-adjacent tournaments on $n$ vertices
such that $S=\\{u,v,w\\}$ and

$\alpha_{3,n}^{RDM}=\alpha^{RDM}_{S}(T)=r_{S}(T^{\prime})-r_{s}(T)$

I.e. $T$ is the ”worst” example on $n$ vertices. By (1) we have

$\alpha_{3,n}^{RDM}=\frac{1}{\binom{n}{2}}(A+B+C)$

where $A,B$ and $C$ were defined in Section 4.2.1. By Lemma 4.2 we have

$A\leq\frac{7}{3}$

and by Lemma 4.3

$B\leq\frac{d^{*}_{u}+d^{*}_{v}+d^{*}_{w}}{3}=\frac{|I|}{3}$

Let $e\notin G$. Notice that both $T^{\prime}|_{e}$ and $T|_{e}$ are
tournaments on $n-1$ vertices and by definition of $G$, $u,v,w$ are not
eliminated in both $T^{\prime}|_{e}$ and $T|_{e}$. Moreover, $T^{\prime}|_{e}$
and $T|_{e}$ are $S$-adjacent. Therefore, for every $e\notin G$, we have by
Lemma 3.3

$r_{u,v,w}(T^{\prime}|_{e})-r_{u,v,w}(T|_{e})\leq\alpha_{3,n-1}^{RDM}\leq\alpha_{3,n}^{RDM}$

By using the above on each term in $C$ and the fact that $|G|=3+|I|$, we get
that

$C\leq(\binom{n}{2}-(3+|I|))\alpha_{3,n}^{RDM}$

By using the above 3 bounds we get

$\displaystyle\alpha_{3,n}^{RDM}$
$\displaystyle\leq\frac{1}{\binom{n}{2}}(\frac{7}{3}+\frac{|I|}{3}+(\binom{n}{2}-(3+|I|))\alpha_{3,n}^{RDM})$
$\displaystyle\iff(|I|+3)\alpha_{3,n}^{RDM}$
$\displaystyle\leq\frac{|I|+7}{3}$
$\displaystyle\iff\alpha_{3,n}^{RDM}=\alpha^{RDM}_{S}(T)$
$\displaystyle\leq\frac{|I|+7}{3(|I|+3)}$

as desired.

####  4.2.5 Proof of Theorem 4.1

Suppose that $T$ is the most manipulable tournament on $n$ vertices i.e. it
satisfies $\alpha^{RDM}_{S}(T)=\alpha^{RDM}_{3,n}$. If $|I|\leq 4$, then by
Lemma 4.5, we have that

$\alpha_{3,n}^{RDM}=\alpha^{RDM}_{S}(T)\leq\frac{31}{60}$

If $|I|\geq 5$, then by Lemma 4.6

$\alpha_{3,n}^{RDM}=\alpha^{RDM}_{S}(T)\leq\frac{|I|+7}{3(|I|+3)}\leq\frac{5+7}{3(5+3)}=\frac{1}{2}$

where above we used that $\frac{x+7}{3(x+3)}$ is decreasing for $x\geq 5$.
Combining the above bounds, we obtain $\alpha_{3,n}^{RDM}\leq\frac{31}{60}$
for all $n\in\mathbb{N}$. Therefore,

$\alpha_{k}^{RDM}=\max_{n\in\mathbb{N}}\alpha_{k,n}^{RDM}\leq\frac{31}{60}$

which proves the upper bound and finishes the proof of Theorem 4.1.

##  5 Sybil Attacks on Tournaments

###  5.1 Main Results on Sybil Attacks on Tournaments

Recall our motivation from the Introduction. Imagine that a tournament rule is
used as a proxy for a voting rule to select a proposal. The proposals are
compared head-to-head, and this constitutes the pairwise matches in the
resulting tournament. A proposer can try to manipulate the protocol with a
Sybil attack and submit many nearly identical proposals with nearly equal
strength relative to the other proposals. The proposer can choose to
manipulate the outcomes of the head-to-head comparisons between two of his
proposals in a way which maximizes the probability that a proposal of his is
selected. In the tournament $T$ his proposal corresponds to a team $u_{1}$,
and the tournament $T^{\prime}$ resulting from the Sybil attack is a member of
$Syb(T,u_{1},m)$ (Recall Definition 2.9). The questions that we want to answer
in this section are: (1) Can the Sybils manipulate their matches to
successfully increase their collective probability of winning? and (2) Is it
beneficial for the proposer to create as many Sybils as possible?

The first question we are interested is whether any group of Sybils can
manipulate successfully to increase their probability of winning. It turns out
that that the answer is No. We first prove that the probability that a team
which is not a Sybil wins does not depend on the matches between the Sybils.

###### Lemma 5.1

There exists a function $q$ that takes in as input integer $m$, tournament
$T$, team $u_{1}\in T$, and team $v\in T\setminus u_{1}$ with the following
property. For all $T^{\prime}\in Syb(T,u_{1},m)$, we have

$r_{v}(T^{\prime})=q(m,T,u_{1},v)$

where the dependence on $u_{1}$ is encoded as the outcomes of its matches with
the rest of $T$.

Proof. See Appendix A.3 for a full proof.

Note that by Lemma 5.1 $r_{v}(T^{\prime})=q(m,T,u_{1},v)$ does not depend on
which tournament $T^{\prime}\in Syb(T,u_{1},m)$ is chosen. Now, we prove our
first promised result. Namely, that no number of Sybils in a Sybil attack can
manipulate the matches between them to increase their probability of winning.

###### Theorem 5.2

Let $T$ be a tournament, $u_{1}\in T$ a team, and $m$ and integer. Let
$T_{1}^{\prime}\in Syb(T,u_{1},m)$. Let $S=\\{u_{1},\ldots,u_{m}\\}$. Then

$\alpha_{S}^{RDM}(T_{1}^{\prime})=0$

Proof. Let $T_{1}^{\prime}$ and $T_{2}^{\prime}$ be $S$-adjacent. By
Definition 2.9, $T_{2}^{\prime}\in Syb(T,u_{1},m)$. Therefore by Lemma 5.1,
$r_{v}(T_{1}^{\prime})=r_{v}(T_{2}^{\prime})=q(m,T,u_{1},v)$ for all $v\in
T\setminus u_{1}$. Using this we obtain

$r_{S}(T_{1}^{\prime})=1-\sum_{v\in T\setminus
u_{1}}r_{v}(T_{1}^{\prime})=1-\sum_{v\in T\setminus
u_{1}}r_{v}(T_{2}^{\prime})=r_{S}(T_{2}^{\prime})$

Therefore, $r_{S}(T_{1}^{\prime})=r_{S}(T_{2}^{\prime})$ for all $S$-adjacent
$T_{1}^{\prime},T_{2}^{\prime}$, which implies the desired result.

Theorem 5.2 says that any number of Sybils cannot manipulate to increase their
collective probability of winning. This leaves the question whether it is
beneficial for the proposer to send many (nearly) identical proposals to the
tournament to maximize the probability that a proposal of his is selected. We
show that Randomized Death Match disincentivizes such behaviour. When $u_{1}$
is a Condorcet winner in $T$, then by Lemma 3.4 a Sybil will win with
probability one. We prove that if $u_{1}$ is not a Condorcet winner in $T$
then as $m$ goes to infinity, the maximum probability (over all Sybils attacks
of $u_{1}$) that any Sybil wins goes to 0. Or equivalently, RDM is
Asymptotoically Strongly Sybil-Proof (recall Definition 2.10).
Before we state our second main theorem let’s recall some notation. Let
$u_{1}\in T$ be a team (which is not a Condorcet winner). Let $A$ be the set
of teams in $T$ that $u_{1}$ beats, and $B$ the of teams $u_{1}$ loses to. Let
$T^{\prime}\in Syb(T,u_{1},m)$ and $v\in T\setminus u_{1}$. By Lemma 5.1,
$r_{v}(T^{\prime})=q(m,T,u_{1},v)$ for all $T^{\prime}\in Syb(T,u_{1},m)$.
Also, by Lemma 5.1,

$r_{u_{1},\ldots,u_{m}}(T^{\prime})=1-\sum_{v\in T\setminus
u_{1}}r_{v}(T^{\prime})=1-\sum_{v\in T\setminus u_{1}}q(m,T,u_{1},v)$ (3)

and

$r_{A}(T^{\prime})=\sum_{v\in A}q(m,T,u_{1},v)$ (4)

Note that the terms in the RHS of each of (3) and (4) depends only on
$T,u_{1}$ and $m$. Thus, we can define the functions

$h(m,T,u_{1})=r_{u_{1},\ldots,u_{m}}(T^{\prime})$
$g(m,T,u_{1})=r_{A}(T^{\prime})$

and

$p(m,T,u_{1})=h(m,T,u_{1})+g(m,T,u_{1})$

(here $p(m,T,u_{1})$ is the total collective probability that a Sybil or a
team from $A$ wins)
We are now ready to prove our second main result. Namely, that RDM is
Asymptotically Strongly Sybil-Proof (Definition 2.10). Before we present the
result (Theorem 5.3) we will try to convey some intuition for why RDM should
be ASSP. Observe that the only way a Sybil can win is when all the teams from
$B$ are eliminated before all the Sybils. The teams from $B$ can only be
eliminated by teams from $A$. However, as $m$ increases there are more Sybils
and, thus, the teams from $A$ are intuitively more likely to all lose the
tournament before the teams from $B$. When there are no teams from $A$ left
and at least one team from $B$ left, no Sybil can win. In fact, this intuition
implies something stronger than RDM being ASSP: the collective winning
probability of the Sybils and the teams from $A$ (denoted by $p(m,T,u_{1})$)
converges to 0 as $m$ converges to $\infty$ (or, equivalently, the probability
that a team from $B$ wins goes to $1$). This intuition indirectly lies behind
the technical details of the proof of Theorem 5.3.

###### Theorem 5.3

Randomized Death Match is Asymptotically Strongly Sybil-Proof. In fact a
stronger statement holds, namely if $u_{1}\in T$ is not a Condorcet winner,
then

$\lim_{m\to\infty}p(m,T,u_{1})=0$

Proof. See Appendix A.3 for a full proof.

###  5.2 On a Counterexample to an Intuitive Claim

We will use Theorem 5.3 to prove that RDM does not satisfy a stronger version
of the monotonicity property in Definition 2.6. First, we give a
generalization of the definition for monotonicity given in Section 3

######  Definition 5.4 (Strongly monotone)

Let $r$ be a tournament rule. Let $T$ and let $C\cup D$ be any splitting of
the teams in $T$ into two disjoint sets. A tournament rule $r$ is strongly
monotone for every $(u,v)\in C\times D$, if $T^{\prime}$ is
$\\{u,v\\}$-adjacent to $T$ such that $u$ beats $v$ in $T^{\prime}$ we have
$r_{C}(T^{\prime})\geq r_{C}(T)$

Intuitively, $r$ is Strongly monotone if whenever flipping a match between a
team from $C$ and a team from $D$ in favor of the team from $C$ makes $C$
better off. Notice that if $|C|=1$ this is the usual definition of
monotonicity (Definition 2.6), which is satisfied by RDM by Lemma 3.5.
However, RDM is not strongly monotone, even though strong monotonicity may
seem like an intuitive property to have.

###### Claim 5.5

RDM is not strongly monotone

Proof. Suppose the contrary i.e. RDM is strongly monotone. Start with a
3-cycle tournament $T$ where $a_{1}$ beats $b$, $b$ beats $c$, and $c$ beats
$a_{1}$. Let $T^{\prime}\in Syb(T,a_{1},m)$ be a Sybil attack of $a_{1}$ on
$T$ with $m$ Sybils. Let the Sybils be $C=\\{a_{1},a_{2},\ldots,a_{m}\\}$
where $a_{i}$ beats $a_{j}$ in $T^{\prime}$ for $i<j$. By Theorem 5.3 we can
take $m$ large enough so that $r_{C}(T^{\prime})<\frac{1}{6}$. Suppose all
Sybils in $C$ but $a_{1}$ throw all of their matches with $b$ and denote the
tournament resulting from that $T^{\prime\prime}$. Then, if RDM were strongly
monotone we would have $r_{C}(T^{\prime\prime})\leq
r_{C}(T^{\prime})<\frac{1}{6}$ (start with $T^{\prime\prime}$ and iteratively
apply strong monotonicity). Note that starting from $T^{\prime\prime}$ and
iteratively applying Lemma 3.2 to $a_{i}$ and removing $a_{i}$ from the
tournament for $i=m,m-1,\ldots,2$ we will obtain the tournament $T$, and the
probability distribution over the winner in $T^{\prime\prime}$ will be the
same as in $T$. Therefore, $r_{C}(T^{\prime\prime})\geq
r_{a}(T^{\prime\prime})=r_{a}(T)=\frac{1}{3}$, but
$r_{a}(T^{\prime\prime})<\frac{1}{6}$, a contradiction with our assumption
that RDM is strongly monotone.

##  6 Conclusion and Future Work

We use a novel first-step analysis to nail down the minimal $\alpha$ such that
RDM is $3$-SNM-$\alpha$. Specifically, our main result shows that
$\alpha^{RDM}_{3}=\frac{31}{60}$. Recall that this is the first tight analysis
of any Condorcet-consistent tournament rule for any $k>2$, and also the first
monotone, Condorcet-consistent tournament rule that is $k$-SNM-$\alpha$ for
any $k>2,\alpha<1$. We also initiate the study of manipulability via Sybil
attacks, and prove that RDM is Asymptotically Strongly Sybil-Proof.

Our technical approach opens up the possibility of analyzing the
manipulability of RDM (or other tournament rules) whose worst-case examples
are complicated-but-tractable. For example, it is unlikely that the elegant
coupling arguments that work for $k=2$ will result in a tight bound of
$31/60$, but our approach is able to drastically reduce the search space for a
worst-case example, and a tractable case analysis confirms that a specific
5-team tournament is tight. Our approach can similarly be used to analyze the
manipulability of RDM for $k>3$, or other tournament rules. However, there are
still significant technical barriers for future work to overcome in order to
keep analysis tractable for large $k$, or for tournament rules with a more
complicated recursive step. Still, our techniques provide a clear approach to
such analyses that was previously non-existent.

## References

  * [AK10] Alon Altman and Robert Kleinberg.  Nonmanipulable randomized tournament selections.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 24, 2010.
  * [APT10] Alon Altman, Ariel D Procaccia, and Moshe Tennenholtz.  Nonmanipulable selections from a tournament.  In Computational Foundations of Social Choice, 07.03. - 12.03.2010, volume 10101 of Dagstuhl Seminar Proceedings. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany, 2010.
  * [Ban85] J. S. Banks.  Sophisticated voting outcomes and agenda control.  Social Choice and Welfare, 1(4):295–306, 1985.
  * [BBS16] Florian Brandl, Felix Brandt, and Hans Georg Seedig.  Consistent probabilistic social choice.  Econometrica, 84(5):1839–1880, 2016.
  * [DW21] Kimberly Ding and S Matthew Weinberg.  Approximately strategyproof tournament rules in the probabilistic setting.  In 12th Innovations in Theoretical Computer Science Conference, ITCS, LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [EFS12] Edith Elkind, Piotr Faliszewski, and Arkadii Slinko.  Clone structures in voters’ preferences.  In Proceedings of the 13th ACM conference on electronic commerce, pages 496–513, 2012.
  * [Fis77] Peter C. Fishburn.  Condorcet social choice functions.  SIAM Journal on Applied Mathematics, 33(3):469–489, 1977.
  * [FR92] David C. Fisher and Jennifer Ryan.  Optimal strategies for a generalized ”scissors, paper, and stone” game.  The American Mathematical Monthly, 99(10):935–942, 1992.
  * [GLM93] Laffond G., Jean-François Laslier, and Le Breton M.  The bipartisan set of a tournament game.  Games and Economic Behavior, 5(1):182–201, 1993.
  * [KSW17] Michael P Kim, Warut Suksompong, and Virginia Vassilevska Williams.  Who can win a single-elimination tournament?  SIAM Journal on Discrete Mathematics, 31(3):1751–1764, 2017.
  * [KW15] Michael P Kim and Virginia Vassilevska Williams.  Fixing tournaments for kings, chokers, and more.  In Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015.
  * [LLL96] Gilbert Laffond, Jean Lainé, and Jean-François Laslier.  Composition-consistent tournament solutions and social choice functions.  Social Choice and Welfare, 13(1):75–93, 1996.
  * [Mil80] Nicholas R. Miller.  A new solution set for tournaments and majority voting: Further graph- theoretical approaches to the theory of voting.  American Journal of Political Science, 24(1):68–96, 1980.
  * [Mou16] Hervé Moulin.  Handbook of Computational Social Choice.  Cambridge University Press, 2016.
  * [Özt20] Z Emel Öztürk.  Consistency of scoring rules: a reinvestigation of composition-consistency.  International Journal of Game Theory, 49(3):801–831, 2020.
  * [SSW17] Jon Schneider, Ariel Schvartzman, and S Matthew Weinberg.  Condorcet-consistent and approximately strategyproof tournament rules.  In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS), 2017.
  * [SW11] Isabelle Stanton and Virginia Vassilevska Williams.  Rigging tournament brackets for weaker players.  In IJCAI Proceedings-International Joint Conference on Artificial Intelligence, volume 22, page 357, 2011.
  * [SWZZ20] Ariel Schvartzman, S Matthew Weinberg, Eitan Zlatin, and Albert Zuo.  Approximately strategyproof tournament rules: On large manipulating sets and cover-consistence.  11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12- 14, 2020, Seattle, Washington, USA, volume 151 of LIPIcs, pages 3:1–3:25. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.

##  Appendix A Omitted proofs

###  A.1 Omitted proofs from Section 3

##### Proof of Lemma 3.3.

Consider a tournament $T$, on $n$ vertices and a set $S$ of size $k$ such that
$S$ can manipulate the matches between them to a tournament $T^{\prime}$ so
that their probability of winning increases by $\alpha_{k,n}^{r}$, i.e.

$\alpha_{S}^{r}(T)=r_{S}(T^{\prime})-r_{S}(T)=\alpha_{k,n}^{r}$

Let $u$ be a new team which loses to all teams in $T$. By Lemma 3.2 it follows
that $r_{S}(T^{\prime})=r_{S}(T^{\prime}\cup u)$ and $r_{S}(T)=r_{S}(T\cup
u)$. Therefore,

$\alpha_{k,n+1}^{r}\geq r_{S}(T^{\prime}\cup u)-r_{S}(T\cup
u)=r_{S}(T^{\prime})-r_{S}(T)=\alpha_{k,n}^{r}$

$\square$

##### Proof of Lemma 3.4.

Suppose the contrary i.e. there is some $v\in T\setminus S$ which wins in some
execution of RDM. Consider the round in which the last team $u\in S$ is
eliminated by some team $u^{\prime}$. Clearly, $u^{\prime}\notin S$ and thus
it cannot eliminate $u$, i.e. a contradiction. $\square$

##### Proof of Lemma 3.5

If $u$ beats $v$ in $T^{\prime}$, then $r_{u}(T)=r_{u}(T^{\prime})$. Suppose
$v$ beats $u$ in $T^{\prime}$. Consider an execution $E$ of RDM in
$T^{\prime}$ in which $u$ wins. Notice that this execution cannot contain the
match $(u,v)$ since $u$ will get eliminated before $v$. Therefore, $E$ is also
a valid execution of RDM in $T$. This, provides an injective mapping from the
valid executions in $T^{\prime}$ where $u$ wins to the valid executions in $T$
where $u$ wins. Therefore, $r_{u}(T)\geq r_{u}(T^{\prime})$. $\square$

###  A.2 Omitted proofs from Section 4

##### Proof of Lemma 4.2

We claim that there exists some $x^{*}\in\\{u,v,w\\}$ such that
$\min(\ell_{x^{*}},\ell^{\prime}_{x^{*}})\geq 1$. Indeed the possible values
for $(\ell_{u},\ell_{v},\ell_{w})$ and
$(\ell^{\prime}_{u},\ell^{\prime}_{v},\ell^{\prime}_{w})$ are $(1,1,1)$ or
some permutation of $\\{2,1,0\\}$. Therefore, as there are least 2 non-zero
entries in each of $(\ell_{u},\ell_{v},\ell_{w})$ and
$(\ell^{\prime}_{u},\ell^{\prime}_{v},\ell^{\prime}_{w})$, there must be a
non-zero entry on which they overlap. This means that there is some
$x^{*}\in\\{u,v,w\\}$ such that $\min(\ell_{x^{*}},\ell^{\prime}_{x^{*}})\geq
1$. Let $\\{u,v,w\\}\setminus x^{*}=\\{y^{*},z^{*}\\}$. By Theorem 3.6, we
have

$r_{\\{u,v,w\\}\setminus x^{*}}(T^{\prime}\setminus
x^{*})-r_{\\{u,v,w\\}\setminus x^{*}}(T\setminus x^{*})\leq\frac{1}{3}$ (5)

By using the above results and the fact that
$\ell^{\prime}_{x^{*}}+\ell^{\prime}_{y^{*}}+\ell^{\prime}_{z^{*}}=3$ we get
the following bound

$\displaystyle A$
$\displaystyle=\sum_{x\in\\{u,v,w\\}}\ell^{\prime}_{x}r_{\\{u,v,w\\}\setminus
x}(T^{\prime}\setminus x)-\ell_{x}r_{\\{u,v,w\\}\setminus x}(T\setminus
x)\leq$ $\displaystyle\leq\ell^{\prime}_{x^{*}}r_{\\{u,v,w\\}\setminus
x^{*}}(T^{\prime}\setminus x^{*})-\ell_{x^{*}}r_{\\{u,v,w\\}\setminus
x^{*}}(T\setminus x^{*})+\ell^{\prime}_{y^{*}}r_{\\{u,v,w\\}\setminus
y^{*}}(T^{\prime}\setminus y^{*})$
$\displaystyle+\ell^{\prime}_{z^{*}}r_{\\{u,v,w\\}\setminus
z^{*}}(T^{\prime}\setminus z^{*})\leq$ $\displaystyle\leq
r_{\\{u,v,w\\}\setminus x^{*}}(T^{\prime}\setminus
x^{*})-r_{\\{u,v,w\\}\setminus x^{*}}(T\setminus
x^{*})+(\ell^{\prime}_{x^{*}}-1)r_{\\{u,v,w\\}\setminus
x^{*}}(T^{\prime}\setminus x^{*})$
$\displaystyle+\ell^{\prime}_{y^{*}}r_{\\{u,v,w\\}\setminus
y^{*}}(T^{\prime}\setminus y^{*})+\ell^{\prime}_{z^{*}}r_{\\{u,v,w\\}\setminus
z^{*}}(T^{\prime}\setminus z^{*})\leq$ $\displaystyle\leq
r_{\\{u,v,w\\}\setminus x^{*}}(T^{\prime}\setminus
x^{*})-r_{\\{u,v,w\\}\setminus x^{*}}(T\setminus
x^{*})+(\ell_{x^{*}}-1)+\ell_{y^{*}}+\ell_{z^{*}}\leq\text{ (by
(\ref{equation}))}$ $\displaystyle\leq\frac{1}{3}+3-1=\frac{7}{3}$

where in the second line, we used $\ell_{x^{*}}\geq 1$ to get
$-\ell_{x^{*}}r_{\\{u,v,w\\}\setminus x^{*}}(T\setminus x^{*})\leq-
r_{\\{u,v,w\\}\setminus x^{*}}(T\setminus x^{*})$ and in the in third line we
used $\ell^{\prime}_{x^{*}}\geq 1$ to get
$(\ell^{\prime}_{x^{*}}-1)r_{\\{u,v,w\\}\setminus x^{*}}(T^{\prime}\setminus
x^{*})\leq(\ell^{\prime}_{x^{*}}-1)$. Thus,

$A\leq\frac{7}{3}$

Suppose that $|I|\leq 1$. Then, for every $x\in S$, there is at most one match
in which a team in $\\{u,v,w\\}\setminus x$ loses from a team in $(T\setminus
x)\setminus(S\setminus x)$. Therefore, by Corollary 3.8,
$r_{\\{u,v,w\\}\setminus x}(T\setminus x)\geq\frac{2}{3}$. Also, we clearly
have that $r_{\\{u,v,w\\}\setminus x}(T^{\prime}\setminus x)\leq 1$. Thus,

$A=\sum_{x\in\\{u,v,w\\}}\ell^{\prime}_{x}r_{\\{u,v,w\\}\setminus
x}(T^{\prime}\setminus x)-\ell_{x}r_{\\{u,v,w\\}\setminus x}(T\setminus
x)\leq\ell^{\prime}_{u}+\ell^{\prime}_{v}+\ell^{\prime}_{w}-\frac{2}{3}(\ell_{u}+\ell_{v}+\ell_{w})=3-\frac{2}{3}\times
3=1$

Thus,

$A\leq 1$

when $|I|\leq 1$ as desired. $\square$

##### Proof of Lemma 4.3

By Theorem 3.6 we have that for all permutations $(x,y,z)$ of $\\{u,v,w\\}$

$r_{\\{z,y\\}}(T^{\prime}\setminus x)-r_{\\{z,y\\}}(T\setminus
x)=r_{\\{u,v,w\\}\setminus x}(T^{\prime}\setminus x)-r_{\\{u,v,w\\}\setminus
x}(T\setminus x)\leq\alpha^{RDM}_{2}=\frac{1}{3}$

By using the above for each of the 3 terms in the sum $B$ we get

$B=\sum_{x\in S}d^{*}_{x}(r_{\\{u,v,w\\}\setminus x}(T^{\prime}\setminus
x)-r_{\\{u,v,w\\}\setminus x}(T\setminus
x))\leq\frac{d^{*}_{u}+d^{*}_{v}+d^{*}_{w}}{3}=\frac{|I|}{3}$

Suppose $|I|\leq 1$. If $|I|=0$, then $d^{*}_{u}=d^{*}_{v}=d^{*}_{w}=0$, so
$B=0$. Suppose $|I|=1$ and WLOG team $a\notin S$ beats $u$ and $\\{u,v,w\\}$
win all other matches with teams outside of $S$ (in particular $v,w$ beat
$t$). Then $d^{*}_{v}=d^{*}_{w}=0$. Thus,

$B=d^{*}_{u}(r_{v,w}(T^{\prime}\setminus u)-r_{v,w}(T\setminus u))=0$

since $r_{v,w}(T^{\prime}\setminus u)=r_{v,w}(T\setminus u)=1$ by Lemma 3.4,
as $v,w$ beat every team outside of $\\{v,w\\}$ in both $T^{\prime}\setminus
u$ and $T\setminus u$. $\square$

##### Proof of Lemma 4.4

For a tournament $H$, where $u,v,w\in H$, define
$t(H)=(a^{\prime}_{1},a^{\prime}_{2},a^{\prime}_{3})$, where in $H$ there are
exactly $a^{\prime}_{i}$ teams in $H\setminus\\{u,v,w\\}$ each of which beats
exactly $i$ teams out of $\\{u,v,w\\}$ for $i=1,2,3$. Suppose that $e\in Q$.
Then we have 3 cases for $e$:

  * •

Suppose $e$ is a match between two teams from $L_{1}$ or between some team
from $L_{1}$ and one of the two teams in $\\{u,v,w\\}$ to which it loses. Then
clearly, $t(T|_{e})=(a_{1}-1,a_{2},a_{3})$ and thus

$r_{u,v,w}(T^{\prime}|_{e})-r_{u,v,w}(T|_{e})\leq
M_{n-1}(a_{1}-1,a_{2},a_{3})$

Notice that there are $\binom{a_{1}}{2}+2a_{1}$ such matches.

  * •

Suppose now that $e$ is a match between two teams from $L_{2}$ or between some
team from $L_{2}$ the the unique team in $\\{u,v,w\\}$ to which it loses.
Then, clearly, $t(T|_{e})=(a_{1},a_{2}-1,a_{3})$. Thus,

$r_{u,v,w}(T^{\prime}|_{e})-r_{u,v,w}(T|_{e})\leq
M_{n-1}(a_{1},a_{2}-1,a_{3})$

There are $\binom{a_{2}}{2}+a_{2}$ such matches.

  * •

Finally, if $e$ is a match between two teams in $L_{3}$, then
$t(T|_{e})=(a_{1},a_{2},a_{3}-1)$. Thus,

$r_{u,v,w}(T^{\prime}|_{e})-r_{u,v,w}(T|_{e})\leq
M_{n-1}(a_{1},a_{2},a_{3}-1)$

There are $\binom{a_{3}}{2}$ such matches.

Therefore, by applying the the above 3 bounds we get

$\displaystyle C$ $\displaystyle=\sum_{e\notin
G}r_{u,v,w}(T^{\prime}|_{e})-r_{u,v,w}(T|_{e})\leq$
$\displaystyle\leq(2a_{1}+\binom{a_{1}}{2})M_{n-1}(a_{1}-1,a_{2},a_{3})+(a_{2}+\binom{a_{2}}{2})M_{n-1}(a_{1},a_{2}-1,a_{3})$
$\displaystyle+\binom{a_{3}}{2}M_{n}(a_{1},a_{2},a_{3}-1)+\sum_{e\notin G\cup
Q}r_{u,v,w}(T^{\prime}|_{e})-r_{u,v,w}(T|_{e}))$

as desired. Notice that
$|Q|=2a_{1}+a_{2}+\binom{a_{1}}{2}+\binom{a_{2}}{2}+\binom{a_{3}}{2}$.
$\square$

###### Remark A.1

Notice that in Lemma 4.4 one can obtain an even better bound for $C$ by also
considering the matches between two different sets $L_{i}$ and $L_{j}$ for
$i\neq j$. This could potentially be helpful in getting more precise upper
bounds in Table 1. However, for our purposes the above bounds suffice.

##### Omitted cases from the proof of Lemma 4.5

Case 4: $(a_{1},a_{2},a_{3})=(2,0,0)$. Applying $\Delta$, we get

$\displaystyle M_{n}(2,0,0)$
$\displaystyle\leq\frac{1}{\binom{n}{2}}(\frac{7}{3}+\frac{2}{3}+(4+1)f(1,0,0)+(\binom{n}{2}-10)f(2,0,0))=$
$\displaystyle=\frac{1}{\binom{n}{2}}(3+\frac{5}{6}+(\binom{n}{2}-10)\frac{23}{60})=\frac{23}{60}=f(2,0,0)$

Case 5:  $(a_{1},a_{2},a_{3})=(3,0,0)$. Applying $\Delta$, we get

$\displaystyle M_{n}(3,0,0)$
$\displaystyle\leq\frac{1}{\binom{n}{2}}(\frac{7}{3}+\frac{3}{3}+(6+3)f(2,0,0)+(\binom{n}{2}-15)f(3,0,0))=$
$\displaystyle=\frac{1}{\binom{n}{2}}(\frac{10}{3}+9\times\frac{23}{60}+(\binom{n}{2}-15)\frac{407}{900})=$
$\displaystyle=\frac{407}{900}+\frac{1}{\binom{n}{2}}(\frac{200+207}{60}-\frac{407}{60})=\frac{407}{900}=f(3,0,0)$

Case 6 $(a_{1},a_{2},a_{3})=(4,0,0)$. Applying $\Delta$, we get

$\displaystyle M_{n}(4,0,0)$
$\displaystyle\leq\frac{1}{\binom{n}{2}}(\frac{7}{3}+\frac{4}{3}+(2\times
4+6)f(3,0,0)+(\binom{n}{2}-21)f(4,0,0))=$
$\displaystyle=\frac{1}{\binom{n}{2}}(\frac{11}{3}+14\times\frac{407}{900}+(\binom{n}{2}-21)\frac{4499}{9450})=$
$\displaystyle=\frac{4499}{9450}+\frac{1}{\binom{n}{2}}(\frac{3300+4098+1600}{900}-\frac{8998}{900})=\frac{4499}{9450}=f(4,0,0)$

Case 7 $(a_{1},a_{2},a_{3})=(0,1,0)$. Applying $\Delta$, we get

$\displaystyle M_{n}(0,1,0)$
$\displaystyle\leq\frac{1}{\binom{n}{2}}(\frac{7}{3}+\frac{2}{3}+f(0,0,0)+(\binom{n}{2}-6)f(0,1,0))=$
$\displaystyle=\frac{1}{\binom{n}{2}}(\frac{7}{3}+\frac{2}{3}+(\binom{n}{2}-6)\frac{1}{2})=\frac{1}{2}=f(0,1,0)$

Case 8 $(a_{1},a_{2},a_{3})=(1,1,0)$. Applying $\Delta$, we get

$\displaystyle M_{n}(1,1,0)$
$\displaystyle\leq\frac{1}{\binom{n}{2}}(\frac{7}{3}+\frac{3}{3}+2f(0,1,0)+f(1,0,0)+(\binom{n}{2}-9)f(1,1,0))=$
$\displaystyle=\frac{1}{\binom{n}{2}}(\frac{10}{3}+\frac{2}{2}+\frac{1}{6}+(\binom{n}{2}-9)\frac{1}{2})=$
$\displaystyle=\frac{1}{2}+\frac{1}{\binom{n}{2}}(\frac{27}{6}-\frac{9}{2})=\frac{1}{2}=f(1,1,0)$

Case 9 $(a_{1},a_{2},a_{3})=(2,1,0)$. Applying $\Delta$, we get

$\displaystyle M_{n}(2,1,0)$
$\displaystyle\leq\frac{1}{\binom{n}{2}}(\frac{7}{3}+\frac{4}{3}+(4+1)f(1,1,0)+f(2,0,0)+(\binom{n}{2}-13)f(2,1,0))=$
$\displaystyle=\frac{1}{\binom{n}{2}}(\frac{11}{3}+\frac{5}{2}+\frac{23}{60}+(\binom{n}{2}-13)\frac{131}{260})=$
$\displaystyle=\frac{131}{260}+\frac{1}{\binom{n}{2}}(\frac{393}{60}-\frac{131}{20})=\frac{131}{260}=f(2,1,0)$

Case 10 $(a_{1},a_{2},a_{3})=(0,0,1)$. In this case a vertex $t$ beats $u,v,w$
and they lose to everyone else. By symmetry the probability a team from
$u,v,w$ wins is the same no matter what the matches between them are. Thus,
$M(0,0,1)=0=f(0,0,0)$.

Case 11 $(a_{1},a_{2},a_{3})=(1,0,1)$. Applying $\Delta$, we get

$\displaystyle M_{n}(1,0,1)$
$\displaystyle\leq\frac{1}{\binom{n}{2}}(\frac{7}{3}+\frac{4}{3}+f(0,0,1)(\binom{n}{2}-9)f(1,0,1))=$
$\displaystyle=\frac{1}{\binom{n}{2}}(\frac{7}{3}+\frac{4}{3}+(\binom{n}{2}-9)\frac{11}{27})=\frac{11}{27}+\frac{1}{\binom{n}{2}}(\frac{11}{3}-\frac{11}{3})=\frac{11}{27}=f(1,0,1)$

$\square$

###  A.3 Omitted proofs from Section 5

##### Proof of Lemma 5.1

We will construct $q$ and prove the statement by induction on the quantity
$|T|+m$. As a base case suppose $|T|+m\leq 3$. In order to define $q$, we need
$|T|\geq 2$ and this implies $m=1$ and $|T|=2$. In this case there is a single
tournament in $T^{\prime}=T\in Syb(T,u_{1},1)$. One can simply define
$q(1,T,u_{1},v)=r_{v}(T)$. Suppose that we have defined $q(m,T,u_{1},v)$ for
all $T,u_{1}\in T,v\in T\setminus u_{1}$ and $m$ that satisfy $|T|+m<N$ and
that $r_{v}(T^{\prime})=q(m,T,u_{1},v)$ for all $T^{\prime}\in Syb(T,u_{1},m)$
when the parameters satisfy the former constraints.
We will now construct $q$ and show the statement of the Lemma simultaneously
for all settings which satisfy $m+|T|=N$. Let $T,u_{1}\in T,v\in T\setminus
u_{1},m\in\mathbb{N}$ satisfy $m+|T|=N$. If $m=1$ the statement is clear
because there is a single tournament $T^{\prime}=T\in Syb(T,u_{1},m)$ and thus
$q(1,u_{1},T,v)=r_{v}(T)=r_{v}(T^{\prime})$. Suppose $m\geq 2$ and
$T^{\prime}\in Syb(T,u_{1},m)$. Let $A$ be the set of teams in $T\setminus
u_{1}$ that $u_{1}$ beats and $B$ the set of teams in $T\setminus u_{1}$ that
$u_{1}$ loses to. Suppose $|A|=a\geq 0$ and $|B|=b\geq 0$. If the first match
is between a team from $B$ and a Sybil or between two Sybils, then a Sybil is
eliminated and the resulting tournament is a member of $Syb(T,u_{1},m-1)$
(possibly after relabeling $u_{1}$). By the induction hypothesis, $v$ wins
with probability $q(m-1,T,u_{1},v)$. There are $\binom{m}{2}+bm$ such matches.
If a match in which a team $t\in T\setminus\\{v,u_{1}\\}$ loses is played,
then the resulting tournament is a member of $Syb(T\setminus t,u_{1},m)$.
Thus, by the induction hypothesis $v$ wins in the resulting tournament with
probability $q(m,T\setminus t,u_{1},v)$. If $d_{t}$ is the number of teams $t$
loses to in $T$, there are $d_{t}+m-1$ such matches if $t\in A$ and $d_{t}$
such matches if $t\in B$. If $v$ loses then, it clearly wins with probability
0. Thus, by first-step analysis we have that

$\displaystyle r_{v}(T^{\prime})$
$\displaystyle=\frac{\binom{m}{2}+bm}{\binom{m+a+b}{2}}q(m-1,T,u_{1},v)+\sum_{t\in
A\setminus v}\frac{d_{t}+m-1}{\binom{m+a+b}{2}}q(m,T\setminus t,u_{1},v)$
$\displaystyle+\sum_{t\in B\setminus
v}\frac{d_{t}}{\binom{m+a+b}{2}}q(m,T\setminus t,u_{1},v)$

Notice that $d_{t}$ depends only on the matches within $T$. Therefore, all
terms in the RHS only depend on $T,u_{1},m$ and $v$, which finishes the
induction and gives us a way to define $q(m,T,u_{1},v)$ as the above
expression. Also, since $T^{\prime}\in Syb(T,u_{1},m)$ was arbitrary we get
$r_{v}(T^{\prime})=q(m,T,u_{1},v)$ for all $T^{\prime}\in Syb(T,u_{1},m)$.

$\square$

##### Proof of Theorem 5.3

Let $T$ be a tournament and $u_{1}\in T$ a team, which is not a Condorcet
winner. As in Definition 2.10, we need to show that

$\lim_{m\to\infty}\max_{T^{\prime}\in
Syb(T,u_{1},m)}r_{u_{1},\ldots,u_{m}}(T^{\prime})=0$

Notice that

$\max_{T^{\prime}\in
Syb(T,u_{1},m)}r_{u_{1},\ldots,u_{m}}(T^{\prime})=h(m,T,u_{1})$

and that $h(m,T,u_{1})\leq p(m,T,u_{1})$ so it suffices to show the stronger
claim $\lim_{m\to\infty}p(m,T,u_{1})=0$
Recall that $A$ ($B$) denotes the set of teams $u_{1}$ beats (loses to) in
$T$. We prove the statement by induction on $|A|$. If $|A|=0$, then clearly
$T\setminus u_{1}$ consists of only teams of $B$, which beat
$u_{1},\ldots,u_{m}$ and thus, $p(m,T,u_{1})=0$ for all $m$ by Lemma 3.4. Let
$|A|=a\geq 1$ and $|B|=b\geq 1$ ($u_{1}$ is not a Condorcet winner). Suppose
that the statement is true for all $T$ and $u_{1}$ with $|A|=a^{\prime}<a$. By
above $|T|\geq 3$. Let for a team $v$ denote by $d_{v}$ the number of teams to
which it loses in $T$. Similarly to the proof of Lemma 5.1 by first-step
analysis we have the following relation

$p(m,T,u_{1})=\frac{\binom{m}{2}+bm}{\binom{m+a+b}{2}}p(m-1,T,u_{1})+\sum_{v\in
B}\frac{d_{v}}{\binom{n+a+b}{2}}p(m,T\setminus v,u_{1})+\sum_{v\in
A}\frac{d_{v}+m-1}{\binom{m+a+b}{2}}p(m,T\setminus v,u)$

Notice that if $v\in B$, then $d_{v}\leq a+b$ as $v$ beats the Sybils of
$u_{1}$, $|B|\leq b$, and $p(m,T\setminus v,u_{1})\leq 1$. Therefore,

$\sum_{v\in B}\frac{d_{v}}{\binom{m+a+b}{2}}p(m,T\setminus
v,u_{1})\leq\frac{b(a+b)}{\binom{m+a+b}{2}}\leq\frac{C}{m^{2}}$

for some $C=C(a,b)$. Also we know that for every $v\in A$, $u_{1}$ loses to at
least one team in $T\setminus v$ (a team in $B$). Therefore, by the inductive
hypothesis $\lim_{m\to\infty}p(m,T\setminus v,u_{1})=0$ for all $v\in A$. Let
$\epsilon>0$ and as $A$ does not depend on $m$, we can choose $N$ such that
for $m>N$, $p(m,T\setminus v,u_{1})<\epsilon$ for all $v\in A$. Also notice
that $\sum_{v\in A}d_{v}+m-1\leq ma+\binom{a+b+1}{2}\leq Dm$, where $D$ is
some constant depending on $a$ and $b$. Thus, collecting the above
observations we get for all $n$ big enough that

$p(m,T,u)\leq\frac{\binom{m}{2}+bm}{\binom{m+a+b}{2}}p(m-1,T,u_{1})+\frac{mD}{\binom{m+a+b}{2}}\epsilon+\frac{C}{m^{2}}$

By Lemma A.2 the function $\frac{\binom{m}{2}+bm}{\binom{m+1+b}{2}}$ is
decreasing in $b$ for $b\geq 1$. We use this, fact together with $a\geq 1$ to
show
$\frac{\binom{m}{2}+bm}{\binom{m+a+b}{2}}\leq\frac{\binom{m}{2}+m}{\binom{m+2}{2}}$.
We also use that $\frac{mD}{\binom{m+a+b}{2}}\epsilon\leq\frac{F}{m}\epsilon$
for some constant $F$. Therefore, by upper bounding the above we get

$p(m,T,u_{1})\leq\frac{\binom{m}{2}+m}{\binom{m+2}{2}}p(m-1,T,u)+\frac{F}{m}\epsilon+\frac{C}{m^{2}}=\frac{\binom{m+1}{2}}{\binom{m+2}{2}}p(m-1,T,u_{1})+\frac{F}{m}\epsilon+\frac{C}{m^{2}}$

Therefore,

$\binom{m+2}{2}p(m,T,u_{1})\leq\binom{m+1}{2}p(m-1,T,u_{1})+Sm\epsilon+Q$

where $S,Q$ are some constants that depend only on the tournament $T$ and the
above holds for $m>N$ sufficiently large. Repeating the above inequality $m-N$
times and adding them up as a telescoping sum we get that

$\binom{m+2}{2}p(m,T,u_{1})\leq\binom{N+1}{2}p(N-1,T,u_{1})+S^{\prime}\epsilon
m^{2}+Q(m-N)$

and thus

$p(m,T,u_{1})\leq\frac{\binom{N+1}{2}p(N-1,T,u)}{\binom{m+2}{2}}+\frac{S^{\prime}\epsilon
m^{2}}{\binom{m+2}{2}}+\frac{Q(m-N)}{\binom{m+2}{2}}$

The first and the third term go to 0 as $m\to\infty$, and the second term goes
to $2S^{\prime}\epsilon$. Therefore,

$\lim_{m\to\infty}p(m,T,u_{1})\leq 2S^{\prime}\epsilon$

Now, letting $\epsilon\to 0$, we get the desired result. $\square$

###### Lemma A.2

The function $\frac{\binom{m}{2}+bm}{\binom{m+1+b}{2}}$ is decreasing in
$b\in\mathbb{Z}$ for $b\geq 1$

Proof. Indeed, one can show that for $b\geq 1$

$\displaystyle\frac{\binom{m}{2}+bm}{\binom{m+1+b}{2}}$
$\displaystyle\geq\frac{\binom{m}{2}+(b+1)m}{\binom{m+2+b}{2}}$
$\displaystyle\iff\frac{m-1+2b}{(m+b+1)(m+b)}$
$\displaystyle\geq\frac{m-1+2b+2}{(m+2+b)(m+b+1)}$
$\displaystyle\iff(m-1+2b)(m+2+b)$ $\displaystyle\geq(m+b)(m+2b+1)$
$\displaystyle\iff 2b$ $\displaystyle\geq 2$

which holds for $b\geq 1$.