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?¹¹1Similarly, 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.²²2Randomized 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$ ,³³3Randomized 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 components⁴⁴4For 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.

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.

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$ .

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.

Refer to caption — 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$ ⁵⁵5Recall $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$ .

	$\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)}$

	$\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}$

Tight Bounds on 3-Team Manipulations in Randomized Death Match

Abstract

1 Introduction

1.1 Our Results

Informal Theorem 1.1

Informal Theorem 1.2

1.2 Technical Highlight

1.3 Related Work

1.4 Roadmap

2 Preliminaries

Definition 2.1 (Tournament)

Definition 2.2 (Tournament Rule)

Definition 2.3 (SS-adjacent)

Definition 2.4 (Condorcet-Consistent)

Definition 2.5 (Manipulating a Tournament)

Definition 2.6 (Monotone)

Definition 2.7 (Anonymous)

Definition 2.8 (Randomized Death Match)

Definition 2.9 (Sybil Attack)

Definition 2.10 (Asymptotically Strongly Sybil-Proof)

3 Basic Properties of RDM and Examples

Observation 3.1 (First-step analysis)

Lemma 3.2

Lemma 3.3

Lemma 3.4

Lemma 3.5

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

Theorem 3.6

Theorem 3.7

Corollary 3.8

4 Main Result: α3R​D​M=31/60\alpha^{RDM}_{3}=31/60

Theorem 4.1

4.1 Lower Bound

4.2 Upper Bound

4.2.1 The First Step Analysis Framework

4.2.2 Upper Bounds on A,BA,B and CC

Lemma 4.2

Lemma 4.3

Lemma 4.4

4.2.3 The case |I|≤4|I|\leq 4

Lemma 4.5

4.2.4 General Upper Bound for the Most Manipulable Tournament

Lemma 4.6

4.2.5 Proof of Theorem 4.1

5 Sybil Attacks on Tournaments

5.1 Main Results on Sybil Attacks on Tournaments

Lemma 5.1

Theorem 5.2

Theorem 5.3

5.2 On a Counterexample to an Intuitive Claim

Definition 5.4 (Strongly monotone)

Claim 5.5

6 Conclusion and Future Work

References

Appendix A Omitted proofs

A.1 Omitted proofs from Section 3

Proof of Lemma 3.3.

Proof of Lemma 3.4.

Proof of Lemma 3.5

A.2 Omitted proofs from Section 4

Proof of Lemma 4.2

Proof of Lemma 4.3

Proof of Lemma 4.4

Remark A.1

Omitted cases from the proof of Lemma 4.5

A.3 Omitted proofs from Section 5

Proof of Lemma 5.1

Proof of Theorem 5.3

Lemma A.2

Definition 2.3 ( $S$ -adjacent)

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

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

4.2.3 The case $|I|\leq 4$