ifaamas [AAMAS ’21]Proc. of the 20th International Conference on Autonomous
Agents and Multiagent Systems (AAMAS 2021)May 3–7, 2021OnlineU. Endriss, A.
Nowé, F. Dignum, A. Lomuscio (eds.) 2021 2021 393 Cardiff University Cardiff
Cardiff University Cardiff

# Rankings for Bipartite Tournaments via Chain Editing

Joseph Singleton<EMAIL_ADDRESS>and  Richard Booth
<EMAIL_ADDRESS>
###### Abstract.

Ranking the participants of a tournament has applications in voting, paired
comparisons analysis, sports and other domains. In this paper we introduce
_bipartite tournaments_ , which model situations in which two different kinds
of entity compete indirectly via matches against players of the opposite kind;
examples include education (students/exam questions) and solo sports
(golfers/courses). In particular, we look to find rankings via _chain graphs_
, which correspond to bipartite tournaments in which the sets of adversaries
defeated by the players on one side are nested with respect to set inclusion.
Tournaments of this form have a natural and appealing ranking associated with
them. We apply _chain editing_ – finding the minimum number of edge changes
required to form a chain graph – as a new mechanism for tournament ranking.
The properties of these rankings are investigated in a probabilistic setting,
where they arise as maximum likelihood estimators, and through the axiomatic
method of social choice theory. Despite some nice properties, two problems
remain: an important anonymity axiom is violated, and chain editing is NP-
hard. We address both issues by relaxing the minimisation constraint in chain
editing, and characterise the resulting ranking methods via a greedy
approximation algorithm.

¡ccs2012¿ ¡concept¿ ¡concept_id¿10002950.10003624.10003633¡/concept_id¿
¡concept_desc¿Mathematics of computing Graph theory¡/concept_desc¿
¡concept_significance¿300¡/concept_significance¿ ¡/concept¿ ¡concept¿
¡concept_id¿10002950.10003624.10003625.10003630¡/concept_id¿
¡concept_desc¿Mathematics of computing Combinatorial
optimization¡/concept_desc¿ ¡concept_significance¿300¡/concept_significance¿
¡/concept¿ ¡/ccs2012¿

##  1\. Introduction

A tournament consists of a finite set of players equipped with a _beating
relation_ describing pairwise comparisons between each pair of players.
Determining a ranking of the players in a tournament has applications in
voting in social choice Brandt et al. (2016) (where players represent
alternatives and $x$ beats $y$ if a majority of voters prefer $x$ over $y$),
paired comparisons analysis González-Díaz et al. (2014) (where players may
represent products and the beating relation the preferences of a user), search
engines Slutzki and Volij (2006), sports tournaments Bozóki et al. (2016) and
other domains.

In this paper we introduce _bipartite tournaments_ , which consist of two
disjoint sets of players $A$ and $B$ such that comparisons only take place
between players from opposite sets. We consider ranking methods which produce
two rankings for each tournament – one for each side of the bipartition. Such
tournaments model situations in which two different kinds of entity compete
_indirectly_ via matches against entities of the opposite kind. The notion of
competition may be abstract, which allows the model to be applied in a variety
of settings. An important example is education Jiao et al. (2017), where $A$
represents students, $B$ exam questions, and student $a$ ‘beats’ question $b$
by answering it correctly. Here the ranking of students reflects their
performance in the exam, and the ranking of questions reflects their
_difficulty_. The simultaneous ranking of both sides allows one ranking to
influence the other; e.g. so that students are rewarded for correctly
answering difficult questions. This may prove particularly useful in the
context of crowdsourced questions provided by students themselves, which may
vary in their difficulty (see for example the PeerWise system Denny et al.
(2008)).

A related example is _truth discovery_ Li et al. (2016); Singleton and Booth
(2020): the task of finding true information on a number of topics when faced
with conflicting reports from sources of varying (but unknown) reliability.
Many truth discovery algorithms operate iteratively, alternately estimating
the reliability of sources based on current estimates of the true information,
and obtaining new estimates of the truth based on source reliability levels.
The former is an instance of a bipartite tournament; similar to the education
example, $A$ represents data sources, $B$ topics of interest, and $a$ defeats
$b$ by providing true information on topic $b$ (according to the current
estimates of the truth). Applying a bipartite tournament ranking method at
this step may therefore facilitate development of _difficulty-aware_ truth
discovery algorithms, which reward sources for providing accurate information
on difficult topics Galland et al. (2010). Other application domains include
the evaluation of generative models in machine learning Olsson et al. (2018)
(where $A$ represents generators and $B$ discriminators) and solo sports
contests (e.g. where $A$ represents golfers and $B$ golf courses).

In principle, bipartite tournaments are a special case of _generalised_
tournaments González-Díaz et al. (2014); Slutzki and Volij (2005); Csató
(2019), which allow intensities of victories and losses beyond a binary win or
loss (thus permitting draws or multiple comparisons), and drop the requirement
that every player is compared to all others. However, many existing ranking
methods in the literature do not apply to bipartite tournaments due to the
violation of an _irreducibility_ requirement, which requires that the
tournament graph be strongly connected. In any case, bipartite tournament
ranking presents a unique problem – since we aim to rank players with only
indirect information available – which we believe is worthy of study in its
own right.

In this work we focus particularly on ranking via _chain graphs_ and _chain
editing_. A chain graph is a bipartite graph in which the neighbourhoods of
vertices on one side form a chain with respect to set inclusion. A (bipartite)
tournament of this form represents an ‘ideal’ situation in which the
capabilities of the players are perfectly nested: weaker players defeat a
subset of the opponents that stronger players defeat. In this case a natural
ranking can be formed according to the set of opponents defeated by each
player. These rankings respect the tournament results in an intuitive sense:
if a player $a$ defeats $b$ and $b^{\prime}$ ranks worse than $b$, then $a$
must defeat $b^{\prime}$ also. Unfortunately, this perfect nesting may not
hold in reality: a weak player may win a difficult match by coincidence, and a
strong player may lose a match by accident. With this in mind, Jiao et al.
(2017) suggested an appealing ranking method for bipartite tournaments: apply
_chain editing_ to the input tournament – i.e. find the minimum number of edge
changes required to form a chain graph – and output the corresponding
rankings. Whilst their work focused on algorithms for chain editing and its
variants, we look to study the properties of the ranking method itself through
the lens of computational social choice.

Contribution. Our primary contribution is the introduction of a class of
ranking mechanisms for bipartite tournaments defined by chain editing. We also
provide a new probabilistic characterisation of chain editing via maximum
likelihood estimation. To our knowledge this is the first in-depth study of
chain editing as a ranking mechanism. Secondly, we introduce a new class of
‘chain-definable’ mechanisms by relaxing the minimisation constraint of chain
editing in order to obtain tractable algorithms and to resolve the failure of
an important anonymity axiom.

Paper outline. In Section 2 we define the framework for bipartite tournaments
and introduce chain graphs. Section 3 outlines how one may use chain editing
to rank a tournament, and characterises the resulting mechanisms in a
probabilistic setting. Axiomatic properties are considered in Section 4.
Section 5 defines a concrete scheme for producing chain-editing-based
rankings. Section 6 introduces new ranking methods by relaxing the chain
editing requirement. Related work is discussed in Section 7, and we conclude
in Section 8. Note that some proofs are omitted in the body of the paper and
can be found in the appendix.

##  2\. Preliminaries

In this section we define our framework for bipartite tournaments, introduce
chain graphs and discuss the link between them.

###  2.1. Bipartite Tournaments

Following the literature on generalised tournaments González-Díaz et al.
(2014); Slutzki and Volij (2005); Csató (2019), we represent a tournament as a
matrix, whose entries represent the results of matches between participants.
In what follows, $[n]$ denotes the set $\\{1,\ldots,n\\}$ whenever
$n\in\mathbb{N}$.

######  Definition .

A _bipartite tournament_ – hereafter simply a _tournament_ – is a triple
$(A,B,K)$, where $A=[m]$ and $B=[n]$ for some $m,n\in\mathbb{N}$, and $K$ is
an $m\times n$ matrix with $K_{ab}\in\\{0,1\\}$ for all $(a,b)\in A\times B$.
The set of all tournaments will be denoted by $\mathcal{K}$.

Here $A$ and $B$ represent the two sets of players in the tournament.111 Note
that $A$ and $B$ are not disjoint as sets: $1$ is always contained in both $A$
and $B$, for instance. This poses no real problem, however, since we view the
number $1$ merely a _label_ for a player. It will always be clear from context
whether a given integer should be taken as a label for a player on the $A$
side or the $B$ side.  An entry $K_{ab}$ gives the result of the match between
$a\in A$ and $b\in B$: it is 1 if $a$ defeats $b$ and 0 otherwise. Note that
we do not allow for the possibility of draws, and every $a\in A$ faces every
$b\in B$. When there is no ambiguity we denote a tournament simply by $K$,
with the understanding that $A=[\text{rows}(K)]$ and $B=[\text{columns}(K)]$.

The _neighbourhood_ of a player $a\in A$ in $K$ is the set $K(a)=\\{b\in B\mid
K_{ab}=1\\}\subseteq B$, i.e. the set of players which $a$ defeats. The
neighbourhood of $b\in B$ is the set $K^{-1}(b)=\\{a\in A\mid
K_{ab}=1\\}\subseteq A$, i.e. the set of players defeating $b$.

Given a tournament $K$, our goal is to place a ranking on each of $A$ and $B$.
We define a ranking _operator_ for this purpose.

######  Definition .

An _operator_ $\varphi$ assigns each tournament $K$ a pair
$\varphi(K)=({\preceq_{K}^{\varphi}},{\sqsubseteq_{K}^{\varphi}})$ of total
preorders on $A$ and $B$ respectively.222 A total preorder is a transitive and
complete binary relation.

For $a,a^{\prime}\in A$, we interpret $a\preceq_{K}^{\varphi}a^{\prime}$ to
mean that $a^{\prime}$ is ranked _at least as strong_ as $a$ in the tournament
$K$, according to the operator $\varphi$ (similarly,
$b\sqsubseteq_{K}^{\varphi}b^{\prime}$ means $b^{\prime}$ is ranked at least
as strong as $b$). The strict and symmetric parts of ${\preceq_{K}^{\varphi}}$
are denoted by ${\prec_{K}^{\varphi}}$ and ${\approx_{K}^{\varphi}}$,

As a simple example, consider ${\varphi_{\mathsf{count}}}$, where
$a\preceq_{K}^{\varphi_{\mathsf{count}}}a^{\prime}$ iff
$|K(a)|\leq|K(a^{\prime})|$ and
$b\sqsubseteq_{K}^{\varphi_{\mathsf{count}}}b^{\prime}$ iff
$|K^{-1}(b)|\geq|K^{-1}(b^{\prime})|$. This operator simply ranks players by
number of victories. It is a bipartite version of the _points system_
introduced by Rubinstein (1980), and generalises _Copeland’s rule_ Brandt et
al. (2016).

###  2.2. Chain Graphs

Each bipartite tournament $K$ naturally corresponds to a bipartite graph
$G_{K}$, with vertices $A\sqcup B$ and an edge between $a$ and $b$ whenever
$K_{ab}=1$.333 $A\sqcup B$ is the _disjoint union_ of $A$ and $B$, which we
define as $\\{(a,\mathcal{A})\mid a\in A\\}\cup\\{(b,\mathcal{B})\mid b\in
B\\}$, where $\mathcal{A}$ and $\mathcal{B}$ are constant symbols.  The task
of ranking a tournament admits a particularly simple solution if this graph
happens to be a _chain graph_.

######  Definition  (Yannakakis (1981)).

A bipartite graph $G=(U,V,E)$ is a _chain graph_ if there is an ordering
$U=\\{u_{1},\ldots,u_{k}\\}$ of $U$ such that
$N(u_{1})\subseteq\cdots\subseteq N(u_{k})$, where $N(u_{i})=\\{v\in
V\mid(u_{i},v)\in E\\}$ is the neighbourhood of $u_{i}$ in $G$.

$u_{1}$$u_{2}$$u_{3}$$v_{4}$$v_{3}$$v_{2}$$v_{1}$

Figure 1. An example of a chain graph

An example of a chain graph

In other words, a chain graph is a bipartite graph where the neighbourhoods of
the vertices on one side can be ordered so as to form a chain with respect to
set inclusion. It is easily seen that this nesting property holds for $U$ if
and only if it holds for $V$. Figure 1 shows an example of a chain graph.

Now, as our terminology might suggest, the neighbourhood $K(a)$ of some player
$a\in A$ in a tournament $K$ coincides with the neighbourhood of the
corresponding vertex in $G_{K}$. If $G_{K}$ is a chain graph we can therefore
enumerate $A$ as $\\{a_{1},\ldots,a_{m}\\}$ such that $K(a_{i})\subseteq
K(a_{i+1})$ for each $1\leq i<m$. This indicates that each $a_{i+1}$ has
performed _at least as well_ as $a_{i}$ in a strong sense: every opponent
which $a_{i}$ defeated was also defeated by $a_{i+1}$, and $a_{i+1}$ may have
additionally defeated opponents which $a_{i}$ did not.444 Note that this is a
more robust notion of performance than comparing the neighbourhoods of $a_{i}$
and $a_{i+1}$ by _cardinality_ , which may fail to account for differences in
the strength of opponents when counting wins and losses.  It seems only
natural in this case that one should rank $a_{i}$ (weakly) below $a_{i+1}$.
Appealing to transitivity and the fact that each $a\in A$ appears as _some_
$a_{i}$, we see that any tournament $K$ where $G_{K}$ is a chain graph comes
pre-equipped with a natural total preorder on $A$, where $a^{\prime}$ ranks
higher than than $a$ if and only if $K(a)\subseteq K(a^{\prime})$. The duality
of the neighbourhood-nesting property for chain graphs implies that $B$ can
also be totally preordered, with $b^{\prime}$ ranked higher than $b$ if and
only if $K^{-1}(b)\supseteq K^{-1}(b^{\prime})$.555 Note that the ordering of
the $B$s is reversed compared to the $A$s, since the larger $K^{-1}(b)$ the
_worse_ $b$ has performed.  Moreover, these total preorders relate to the
tournament results in an important sense: if $a$ defeats $b$ and $b^{\prime}$
ranks worse than $b$, then $a$ must defeat $b^{\prime}$ also. That is, the
neighbourhood of each $a\in A$ is _downwards closed_ w.r.t the ranking of $B$,
and the neighbourhood of each $b\in B$ is _upwards closed_ in $A$.

Tournaments corresponding to chain graphs will be said to satisfy the _chain
property_ , and will accordingly be called _chain tournaments_. We give a
simpler (but equivalent) definition which does not refer to the underlying
graph $G_{K}$. First, define relations
${\leqslant^{\mathcal{A}}_{K}},{\leqslant^{\mathcal{B}}_{K}}$ on $A$ and $B$
respectively by $a\leqslant^{\mathcal{A}}_{K}a^{\prime}$ iff $K(a)\subseteq
K(a^{\prime})$ and $b\leqslant^{\mathcal{B}}_{K}b^{\prime}$ iff
$K^{-1}(b)\supseteq K^{-1}(b^{\prime})$, for any tournament $K$.

######  Definition .

A tournament $K$ has the _chain property_ if $\leqslant^{\mathcal{A}}_{K}$ is
a total preorder.

According to the duality principle mentioned already, the chain property
implies that $\leqslant^{\mathcal{B}}_{K}$ is also a total preorder. Note that
the relations $\leqslant^{\mathcal{A}}_{K}$ and $\leqslant^{\mathcal{B}}_{K}$
are analogues of the _covering relation_ for non-bipartite tournaments Brandt
et al. (2016).

###### Example

Consider $K=\left[\begin{smallmatrix}1&0&0&0\\\ 1&1&0&0\\\
1&1&1&1\end{smallmatrix}\right]$. Then $K(1)\subset K(2)\subset K(3)$, so $K$
has the chain property. In fact, $K$ is the tournament corresponding to the
chain graph $G$ from Figure 1.

##  3\. Ranking via Chain Editing

We have seen that chain tournaments come equipped with natural rankings of $A$
and $B$. Such tournaments represent an ‘ideal’ situation, wherein the
abilities of the players on both sides of the tournament are perfectly nested.
Of course this may not be so in reality: the nesting may be broken by some
$a\in A$ winning a match it ought not to by chance, or by losing a match by
accident.

One idea for recovering a ranking in this case, originally suggested by Jiao
et al. (2017), is to apply _chain editing_ : find the minimum number of edge
changes required to convert the graph $G_{K}$ into a chain graph. This process
can be seen as correcting the ‘noise’ in an observed tournament $K$ to obtain
an ideal ranking. In this section we introduce the class of operators
producing rankings in this way.

###  3.1. Chain-minimal Operators

To define chain-editing in our framework we once again present an equivalent
definition which does not refer to the underlying graph $G_{K}$: the number of
edge changes between graphs can be replaced by the _Hamming distance_ between
tournament matrices.

######  Definition .

For $m,n\in\mathbb{N}$, let $\mathcal{C}_{m,n}$ denote the set of all $m\times
n$ chain tournaments. For an $m\times n$ tournament $K$, write
$\operatorname{\mathcal{M}}\left({K}\right)=\operatorname*{arg\
min}_{K^{\prime}\in\mathcal{C}_{m,n}}{d(K,K^{\prime})}\subseteq\mathcal{K}$
for the set of chain tournaments closest to $K$ w.r.t the Hamming distance
$d(K,K^{\prime})=|\\{(a,b)\in A\times B\mid K_{ab}\neq K^{\prime}_{ab}\\}|$.
Let $m({K})$ denote this minimum distance.

Note that chain editing, which is NP-hard in general Jiao et al. (2017),
amounts to finding a single element of
$\operatorname{\mathcal{M}}\left({K}\right)$.666 The decision problem
associated with chain editing – which in tournament terms is the question of
whether $m({K})\leq k$ for a given integer $k$ – is NP-complete Drange et al.
(2015).  We comment further on the computational complexity of chain editing
in Section 7. The following property characterises chain editing-based
operators $\varphi$.

######  (chain-min)

For every tournament $K$ there is
$K^{\prime}\in\operatorname{\mathcal{M}}\left({K}\right)$ such that
$\varphi(K)=({\leqslant^{\mathcal{A}}_{K^{\prime}}},{\leqslant^{\mathcal{B}}_{K^{\prime}}})$.

That is, the ranking of $K$ is obtained by choosing the neighbourhood-subset
rankings for some closest chain tournament $K^{\prime}$. Operators satisfying
chain-min will be called _chain-minimal_.

###### Example

Consider $K=\left[\begin{smallmatrix}1&0&1&0\\\ 1&1&0&0\\\
0&1&1&1\end{smallmatrix}\right]$. $K$ does not have the chain property, since
neither $K(1)\subseteq K(2)$ nor $K(2)\subseteq K(1)$. The set
$\operatorname{\mathcal{M}}\left({K}\right)$ consists of four tournaments a
distance of 2 from $K$:

$\operatorname{\mathcal{M}}\left({K}\right)=\left\\{\left[\begin{smallmatrix}1&\bm{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1}}&1&0\\\
1&1&0&0\\\
\bm{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1}}&1&1&1\end{smallmatrix}\right],\left[\begin{smallmatrix}1&0&\bm{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0}}&0\\\
1&1&0&0\\\
\bm{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1}}&1&1&1\end{smallmatrix}\right],\left[\begin{smallmatrix}1&0&1&0\\\
1&\bm{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0}}&0&0\\\
\bm{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1}}&1&1&1\end{smallmatrix}\right],\left[\begin{smallmatrix}1&0&1&0\\\
1&1&\bm{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1}}&0\\\
\bm{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1}}&1&1&1\end{smallmatrix}\right]\right\\}$

The corresponding rankings are $(213,\\{12\\}34)$, $(123,12\\{34\\})$,
$(213,13\\{24\\})$ and $(123,\\{13\\}24)$.777 Here $a_{1}a_{2}a_{3}$ is
shorthand for the ranking $a_{1}\prec a_{2}\prec a_{3}$ of $A$, and similar
for $B$. Elements in brackets are ranked equally.

Section 3.1 shows that there is no unique chain-minimal operator, since for a
given tournament $K$ there may be several closest chain tournaments to choose
from. In Section 5 we introduce a principled way to single out a _unique_
chain tournament and thereby construct a well-defined chain-minimal operator.

###  3.2. A Maximum Likelihood Interpretation

So far we have motivated chain-min as a way to fix errors in a tournament and
recover the ideal or _true_ ranking. In this section we make this notion
precise by defining a probabilistic model in which chain-minimal rankings
arise as maximum likelihood estimates. The maximum likelihood approach has
been applied for (non-bipartite) tournaments (e.g. the Bradley-Terry model
Bradley and Terry (1952); González-Díaz et al. (2014)), voting in social
choice theory Elkind and Slinko (2016), truth discovery Wang et al. (2012),
belief merging Everaere et al. (2020) and other related problems.

In this approach we take an epistemic view of tournament ranking: it is
assumed there exists a true ‘state of the world’ which determines the
tournament results along with objective rankings of $A$ and $B$. A given
tournament $K$ is then seen as a _noisy observation_ derived from the true
state, and a _maximum likelihood estimate_ is a state for which the
probability of observing $K$ is maximal.

More specifically, a state of the world is represented as a vector of _skill
levels_ for the players in $A$ and $B$.888 For simplicity we use numerical
skill levels here, although it would suffice to have a partial preorder on
$A\sqcup B$ such that each $a\in A$ is comparable with every $b\in B$.

######  Definition .

For a fixed size $m\times n$, a _state of the world_ is a tuple
$\theta=\langle{\bm{x},\bm{y}}\rangle$, where $\bm{x}\in\mathbb{R}^{m}$ and
$\bm{y}\in\mathbb{R}^{n}$ satisfies the following properties:

$\forall a,a^{\prime}\in A\quad(x_{a}<x_{a^{\prime}}\implies\exists b\in
B:x_{a}<y_{b}\leq x_{a^{\prime}})$ (1) $\forall b,b^{\prime}\in
B\quad(y_{b}<y_{b^{\prime}}\implies\exists a\in A:y_{b}\leq
x_{a}<y_{b^{\prime}})$ (2)

where $A=[m]$, $B=[n]$. Write $\Theta_{m,n}$ for the set of all $m\times n$
states.

For $a\in A$, $x_{a}$ is the _skill level_ of $a$ in state $\theta$ (and
similarly for $y_{b}$). These skill levels represent the true capabilities of
the players in $A$ and $B$ in state $\theta$: $a$ is capable of defeating $b$
if and only if $x_{a}\geq y_{b}$. Note that 1 suggests a simple form of
_explainability_ : $a^{\prime}$ can only be strictly more skilful than $a$ if
there is some $b\in B$ which _explains_ this fact, i.e. some $b$ which
$a^{\prime}$ can defeat but $a$ cannot (2 is analogous for the $B$s). These
conditions are intuitive if we assume that skill levels are relative to the
sets $A$ and $B$ currently under consideration (i.e. they do not reflect the
abilities of players in future matches against new contenders outside of $A$
or $B$). Finally note that our states of the world are _richer_ than the
output of an operator, in contrast to other work in the literature Bradley and
Terry (1952); González-Díaz et al. (2014); Elkind and Slinko (2016).
Specifically, a state $\theta$ contains extra information in the form of
comparisons between $A$ and $B$.

Noise is introduced in the observed tournament $K$ via _false positives_
(where $a\in A$ defeats a more skilled $b\in B$ by accident) and _false
negatives_ (where $a\in A$ is defeated by an inferior $b\in B$ by
mistake).999Note that a false positive for $a$ is a false negative for $b$ and
vice versa. The noise model is therefore parametrised by the false positive
and false negative rates
$\bm{\alpha}=\langle{\alpha_{+},\alpha_{-}}\rangle\in[0,1]^{2}$, which we
assume are the same for all $a\in A$.101010 This is a strong assumption, and
it may be more realistic to model the false positive/negative rates as a
function of $x_{a}$. We leave this to future work.  We also assume that noise
occurs independently across all matches.

######  Definition .

Let $\bm{\alpha}=\langle{\alpha_{+},\alpha_{-}}\rangle\in[0,1]^{2}$. For each
$m,n\in\mathbb{N}$ and $\theta=\langle{\bm{x},\bm{y}}\rangle\in\Theta_{m,n}$,
consider independent binary random variables $X_{ab}$ representing the outcome
of a match between $a\in[m]$ and $b\in[n]$, where

$P_{\bm{\alpha}}(X_{ab}=1\mid\theta)=\begin{cases}\alpha_{+},&x_{a}<y_{b}\\\
1-\alpha_{-},&x_{a}\geq y_{b}\end{cases}$ (3)
$P_{\bm{\alpha}}(X_{ab}=0\mid\theta)=\begin{cases}1-\alpha_{+},&x_{a}<y_{b}\\\
\alpha_{-},&x_{a}\geq y_{b}\end{cases}$ (4)

This defines a probability distribution $P_{\bm{\alpha}}({\cdot}\mid\theta)$
over $m\times n$ tournaments by

$P_{\bm{\alpha}}(K\mid\theta)=\prod_{(a,b)\in[m]\times[n]}{P_{\bm{\alpha}}(X_{ab}=K_{ab}\mid\theta)}$

Here $P_{\bm{\alpha}}(K\mid\theta)$ is the probability of observing the
tournament results $K$ when the false positive and negative rates are given by
$\bm{\alpha}$ and the true state of the world is $\theta$. Note that the four
cases in 3 and 4 correspond to a false positive, true positive, true negative
and false negative respectively. We can now define a maximum likelihood
operator.

######  Definition .

Let $\bm{\alpha}\in[0,1]^{2}$ and $m,n\in\mathbb{N}$. Then
$\theta\in\Theta_{m,n}$ is a _maximum likelihood estimate_ (MLE) for an
$m\times n$ tournament $K$ w.r.t $\bm{\alpha}$ if
$\theta\in\operatorname*{arg\
max}_{\theta^{\prime}\in\Theta_{m,n}}{P_{\bm{\alpha}}(K\mid\theta^{\prime})}$.
An operator $\varphi$ is a _maximum likelihood operator_ w.r.t $\bm{\alpha}$
if for any $m,n\in\mathbb{N}$ and any $m\times n$ tournament $K$ there is an
MLE $\theta=\langle{\bm{x},\bm{y}}\rangle\in\Theta_{m,n}$ for $K$ such that
$a\preceq_{K}^{\varphi}a^{\prime}$ iff $x_{a}\leq x_{a^{\prime}}$ and
$b\sqsubseteq_{K}^{\varphi}b^{\prime}$ iff $y_{b}\leq y_{b^{\prime}}$.

Now, consider the tournament $K_{\theta}$ associated with each state
$\theta=\langle{\bm{x},\bm{y}}\rangle$, given by $[K_{\theta}]_{ab}=1$ if
$x_{a}\geq y_{b}$ and $[K_{\theta}]_{ab}=0$ otherwise. Note that $K_{\theta}$
is the unique tournament with non-zero probability when there are no false
positive or false negatives. Expressed in terms of $K_{\theta}$, the MLEs take
a particularly simple form if $\alpha_{+}=\alpha_{-}$, i.e. if false positives
and false negatives occur at the same rate.

###### Lemma

Let $\bm{\alpha}=\langle{\beta,\beta}\rangle$ for some $\beta<\frac{1}{2}$.
Then $\theta$ is an MLE for $K$ if and only if $\theta\in\operatorname*{arg\
min}_{\theta^{\prime}\in\Theta_{m,n}}{d(K,K_{\theta^{\prime}})}$.

###### Proof (sketch).

Let $K$ be an $m\times n$ tournament. It can be shown (and we do so in the
appendix) that for any $\theta\in\Theta_{m,n}$

$\begin{split}P_{\bm{\alpha}}(K\mid\theta)=\Big{(}\prod_{a\in
A}&\alpha_{+}^{|K(a)\setminus K_{\theta}(a)|}(1-\alpha_{-})^{|K(a)\cap
K_{\theta}(a)|}\\\ &\quad(1-\alpha_{+})^{|B\setminus(K(a)\cup
K_{\theta}(a))|}\alpha_{-}^{|K_{\theta}(a)\setminus K(a)|}\Big{)}\end{split}$

Plugging in $\alpha_{+}=\alpha_{-}=\beta$ and simplifying, one can obtain

$\displaystyle P_{\bm{\alpha}}(K\mid\theta)$ $\displaystyle=c\prod_{a\in
A}{\left(\frac{\beta}{1-\beta}\right)^{|K(a)\mathrel{\triangle}K_{\theta}(a)|}}$

where $X\mathrel{\triangle}Y=(X\setminus Y)\cup(Y\setminus X)$ is the
symmetric difference of two sets $X$ and $Y$, and $c=(1-\beta)^{|A|\cdot|B|}$
is a positive constant that does not depend on $\theta$. Now,
$P_{\bm{\alpha}}(K\mid\theta)$ is positive, and is maximal when its logarithm
is. We have

$\displaystyle\log{P_{\bm{\alpha}}(K\mid\theta)}$
$\displaystyle=\log{c}+\log{\left(\frac{\beta}{1-\beta}\right)}\sum_{a\in
A}{|K(a)\mathrel{\triangle}K_{\theta}(a)|}$
$\displaystyle=\log{c}+\log{\left(\frac{\beta}{1-\beta}\right)}d(K,K_{\theta})$

Since $\log{c}$ is constant and $\beta<1/2$ implies
$\log{\left(\frac{\beta}{1-\beta}\right)}<0$, it follows that
$\log{P_{\bm{\alpha}}(K\mid\theta)}$ is maximised exactly when
$d(K,K_{\theta})$ is minimised, which proves the result. ∎

This result characterises the MLE states for $K$ as those for which
$K_{\theta}$ is the closest to $K$. As it turns out, the tournaments
$K_{\theta}$ that arise in this way are exactly those with the chain property.

###### Lemma

An $m\times n$ tournament $K$ has the chain property if and only if
$K=K_{\theta}$ for some $\theta\in\Theta_{m,n}$.

The proof of Section 3.2 relies crucially on 1 and 2 in the definition of a
state. Combining all the results so far we obtain our first main result: the
maximum likelihood operators for $\bm{\alpha}=\langle{\beta,\beta}\rangle$ are
exactly the chain-minimal operators.

Let $\bm{\alpha}=\langle{\beta,\beta}\rangle$ for some $\beta<\frac{1}{2}$.
Then $\varphi$ is a maximum likelihood operator w.r.t $\bm{\alpha}$ if and
only if $\varphi$ satisfies chain-min.

###### Proof (sketch).

First note that by Section 3.2, a state $\theta$ is an MLE for an $m\times n$
tournament $K$ iff $K_{\theta}$ is closest to $K$ amongst all other
tournaments $\\{K_{\theta^{\prime}}\mid\theta^{\prime}\in\Theta_{m,n}\\}$. But
by Section 3.2, this set is exactly the $m\times n$ tournaments with the chain
property. It follows from the definition of
$\operatorname{\mathcal{M}}\left({K}\right)$ that $\theta$ is an MLE if and
only if $K_{\theta}\in\operatorname{\mathcal{M}}\left({K}\right)$.
Consequently, $K^{\prime}\in\operatorname{\mathcal{M}}\left({K}\right)$ if and
only if $K^{\prime}=K_{\theta}$ for some MLE $\theta$ for $K$. We see that
chain-min can be equivalently stated as follows: for all $K$ there exists an
MLE $\theta$ such that
$\varphi(K)=({\leqslant^{\mathcal{A}}_{K_{\theta}}},{\leqslant^{\mathcal{B}}_{K_{\theta}}})$.
Using properties 1 and 2 in Section 3.2 for $\theta$ it is straightforward to
show that $a\leqslant^{\mathcal{A}}_{K_{\theta}}a^{\prime}$ iff $x_{a}\leq
x_{a^{\prime}}$ and $b\leqslant^{\mathcal{B}}_{K_{\theta}}b^{\prime}$ iff
$y_{b}\leq y_{b^{\prime}}$ for all $a,a^{\prime}\in A$, $b,b^{\prime}\in B$
(where $\theta=\langle{\bm{x},\bm{y}}\rangle$). This means that the above
reformulation of chain-min coincides with the definition of a maximum
likelihood operator, and we are done. ∎

Similar results can be obtained for other limiting values of $\bm{\alpha}$. If
$\alpha_{+}=0$ and $\alpha_{-}\in(0,1)$ then the MLE operators correspond to
_chain completion_ : finding the minimum number of edge _additions_ required
to make $G_{K}$ a chain graph. This models situations where false positives
never occur, although false negatives may (e.g. numerical entry questions in
the case where $A$ represents students and $B$ exam questions Jiao et al.
(2017)). Similarly, the case $\alpha_{-}=0$ and $\alpha_{+}\in(0,1)$
corresponds to _chain deletion_ , where edge additions are not allowed.

##  4\. Axiomatic analysis

Chain-minimal operators have theoretical backing in a probabilistic sense due
to the results of Section 3.2, but are they appropriate ranking methods in
practise? To address this question we consider the _normative_ properties of
chain-minimal operators via the axiomatic method of social choice theory. We
formulate several axioms for bipartite tournament ranking and assess whether
they are compatible with chain-min. It will be seen that an important
_anonymity_ axiom fails for all chain-minimal operators; later in Section 5 we
describe a scenario in which this is acceptable and define a class of concrete
operators for this case, and in Section 6 we relax the chain-min requirement
in order to gain anonymity.

###  4.1. The Axioms

We will consider five axioms – mainly adaptations of standard social choice
properties to the bipartite tournament setting.

Symmetry Properties. We consider two symmetry properties. The first is a
classic _anonymity_ axiom, which says that an operator $\varphi$ should not be
sensitive to the ‘labels’ used to identify participants in a tournament.
Axioms of this form are standard in social choice theory; a tournament version
goes at least as far back as Rubinstein (1980).

We need some notation: for a tournament $K$ and permutations $\sigma:A\to A$,
$\pi:B\to B$, let $\sigma(K)$ and $\pi(K)$ denote the tournament obtained by
permuting the rows and columns of $K$ by $\sigma$ and $\pi$ respectively, i.e.
$[\sigma(K)]_{ab}=K_{\sigma^{-1}(a),b}$ and $[\pi(K)]_{ab}=K_{a,\pi^{-1}(b)}$.
Note that in the statement of the axioms we omit universal quantification over
$K$, $a,a^{\prime}\in A$ and $b,b^{\prime}\in B$ for brevity.

######  (anon)

Let $\sigma:A\to A$ and $\pi:B\to B$ be permutations. Then
$a\preceq_{K}^{\varphi}a^{\prime}$ iff
$\sigma(a)\preceq_{\pi(\sigma(K))}^{\varphi}\sigma(a^{\prime})$.

Our second axiom is specific to bipartite tournaments, and expresses a
_duality_ between the two sides $A$ and $B$: given the two sets of
conceptually disjoint entities participating in a bipartite tournament, it
should not matter which one we label $A$ and which one we label $B$. We need
the notion of a _dual tournament_.

######  Definition .

The _dual tournament_ of $K$ is
${{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}=\bm{1}-K^{\top}$,
where $\bm{1}$ denotes the matrix consisting entirely of 1s.

$\textstyle\overline{K}$ is essentially the same tournament as $K$, but with
the roles of $A$ and $B$ swapped. In particular,
$A_{K}=B_{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}$,
$B_{K}=A_{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}$
and $K_{ab}=1$ iff
${{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}_{ba}=0$.
Also note that
${{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}$}}{\leavevmode\hbox{$\textstyle\overline{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}$}}{\leavevmode\hbox{$\scriptstyle\overline{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}$}}}}=K$.
The duality axiom states that the ranking of the $B$s in $K$ is the same as
the $A$s in $\textstyle\overline{K}$.

######  (dual)

$b\sqsubseteq_{K}^{\varphi}b^{\prime}$ iff
$b\preceq_{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}^{\varphi}b^{\prime}$.

Whilst dual is not necessarily a universally desirable property – one can
imagine situations where $A$ and $B$ are not fully abstract and should not be
treated symmetrically – it is important to consider in any study of bipartite
tournaments. Note that dual implies $a\preceq_{K}^{\varphi}a^{\prime}$ iff
$a\sqsubseteq_{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}^{\varphi}a^{\prime}$,
so that a dual-operator can be defined by giving the ranking for one of $A$ or
$B$ only, and defining the other by duality. This explains our choice to
define anon (and subsequent axioms) solely in terms of the $A$ ranking: the
analogous anonymity constraint for the $B$ ranking follows from anon together
with dual.

An Independence Property. _Independence axioms_ play a crucial role in social
choice. We present a bipartite adaptation of a classic axiom introduced in
Rubinstein (1980), which has subsequently been called _Independence of
Irrelevant Matches_ González-Díaz et al. (2014).

######  (IIM)

If $K_{1},K_{2}$ are tournaments of the same size with identical $a$-th and
$a^{\prime}$-th rows, then $a\preceq_{K_{1}}^{\varphi}a^{\prime}$ iff
$a\preceq_{K_{2}}^{\varphi}a^{\prime}$.

IIM is a strong property, which says the relative ranking of $a$ and
$a^{\prime}$ does not depend on the results of any match not involving $a$ or
$a^{\prime}$. This axiom has been questioned for generalised tournaments
González-Díaz et al. (2014), and a similar argument can be made against it
here: although each player in $A$ faces the same opponents, we may wish to
take the _strength_ of opponents into account, e.g. by rewarding victories
against highly-ranked players in $B$. Consequently we do not view IIM as an
essential requirement, but rather introduce it to facilitate comparison with
our work and the existing tournament literature.

Monotonicity Properties. Our final axioms are monotonicity properties, which
express the idea that _more victories are better_. The first axiom follows our
original intuition for constructing the natural ranking associated with a
chain graph; namely that $K(a)\subseteq K(a^{\prime})$ indicates $a^{\prime}$
has performed at least as well as $a$.

######  (mon)

If $K(a)\subseteq K(a^{\prime})$ then $a\preceq_{K}^{\varphi}a^{\prime}$.

Note that mon simply says ${\preceq_{K}^{\varphi}}$ extends the (in general,
partial) preorder ${\leqslant^{\mathcal{A}}_{K}}$. Yet another standard axiom
is _positive responsiveness_.

######  (pos-resp)

If $a\preceq_{K}^{\varphi}a^{\prime}$ and $K_{a^{\prime},b}=0$ for some $b\in
B$, then $a\prec_{K+\bm{1}_{a^{\prime},b}}^{\varphi}a^{\prime}$, where
$\bm{1}_{a^{\prime},b}$ is the matrix with 1 in position $(a^{\prime},b)$ and
zeros elsewhere.

That is, adding an extra victory for $a$ should only improve its ranking, with
ties now broken in its favour. This version of positive responsiveness was
again introduced in Rubinstein (1980), where together with anon and IIM it
characterises the _points system_ ranking method for round-robin tournaments,
which simply ranks players according to the number of victories. The analogous
operator in our framework is ${\varphi_{\mathsf{count}}}$, and it can be shown
that ${\varphi_{\mathsf{count}}}$ is uniquely characterised by anon, IIM, pos-
resp and dual. Finally, note that pos-resp also acts as a kind of
_strategyproofness_ : $a$ cannot improve its ranking by deliberately losing a
match. Specifically, if $K_{ab}=1$ and $a\preceq_{K}^{\varphi}a^{\prime}$,
then pos-resp implies $a\prec_{K-\bm{1}_{ab}}^{\varphi}a^{\prime}$.

###  4.2. Axiom Compatibility with chain-min

We come to analysing the compatibility of chain-min with the axioms. First,
the negative results.

There is no operator satisfying chain-min and any of anon, IIM or pos-resp.

The counterexample for anon is particularly simple: take
$K=\left[\begin{smallmatrix}1&0\\\ 0&1\end{smallmatrix}\right]$. Swapping the
rows and columns brings us back to $K$, so anon implies $1,2\in A$ rank
equally. However, it is easily seen for every
$K^{\prime}\in\operatorname{\mathcal{M}}\left({K}\right)$, either $K(1)\subset
K(2)$ or $K(2)\subset K(1)$, i.e no chain-minimal operator can rank 1 and 2
equally.

The MLE results of Section 3.2 provides informal explanation for this result.
For $K$ above to arise in the noise model of Section 3.2 there must have been
two ‘mistakes’ (false positives or false negatives). This is less likely than
a single mistake from just one of $1,2\in A$, but the likelihood maximisation
forces us to choose one or the other. A similar argument explains the pos-resp
failure.

It is also worth noting that anon only fails at the last step of chain
editing, where a single element of
$\operatorname{\mathcal{M}}\left({K}\right)$ is chosen. Indeed, the set
$\operatorname{\mathcal{M}}\left({K}\right)$ itself _does_ exhibit the kind of
symmetry one might expect: we have
$\operatorname{\mathcal{M}}\left({\pi(\sigma(K))}\right)=\\{\pi(\sigma(K^{\prime}))\mid
K^{\prime}\in\operatorname{\mathcal{M}}\left({K}\right)\\}$. This means that
an operator which aggregates the rankings from _all_
$K^{\prime}\in\operatorname{\mathcal{M}}\left({K}\right)$ – e.g. any anonymous
social welfare function – would satisfy anon. The other axioms are compatible
with chain-min.

For each of dual and mon, there exists an operator satisfying chain-min and
the stated property.

Despite the simplicity of mon, Section 4.2 is deceptively difficult to prove.
We describe operators satisfying chain-def and dual or mon non-constructively
by first taking an _arbitrary_ chain-minimal operator $\varphi$, and using
properties of the set $\operatorname{\mathcal{M}}\left({K}\right)$ to produce
$\varphi^{\prime}$ satisfying dual or mon. Note also that we have not yet
constructed an operator satisfying dual, mon and chain-min simultaneously,
although we conjecture that such operators do exist.

##  5\. Match-preference operators

The counterexample for chain-min and anon suggests that chain-minimal
operators require some form of tie-breaking mechanism when the tournaments in
$\operatorname{\mathcal{M}}\left({K}\right)$ cannot be distinguished while
respecting anonymity. While this limits the use of chain-minimal operators as
general purpose ranking methods, it is not such a problem if additional
information is available to guide the tie-breaking. In this section we
introduce a new class of operators for this case.

The core idea is to single out a unique chain tournament close to $K$ by
paying attention to not only the _number_ of entries in $K$ that need to be
changed to produce a chain tournament, _which_ entries. Specifically, we
assume the availability of a total order on the set of matrix indices
$\mathbb{N}\times\mathbb{N}$ (the _matches_) which indicates our willingness
to change an entry in $K$: the higher up $(a,b)$ is in the ranking, the more
acceptable it is to change $K_{ab}$ during chain editing.

This total order – called the _match-preference relation_ – is fixed for all
tournaments $K$; this means we are dealing with extra information about how
tournaments are _constructed in matrix form_ , not extra information about any
specific tournament $K$.

One possible motivation for such a ranking comes from cases where matches
occur at distinct points in time. In this case the matches occurring more
recently are (presumably) more representative of the players’ _current_
abilities, and we should therefore prefer to modify the outcome of old matches
where possible.

For the formal definition we need notation for the _vectorisation_ of a
tournament $K$: for a total order ${\trianglelefteq}$ on
$\mathbb{N}\times\mathbb{N}$ and an $m\times n$ tournament $K$, we write
$\operatorname{vec}_{\trianglelefteq}(K)$ for the vector in $\\{0,1\\}^{mn}$
obtained by collecting the entries of $K$ in the order given by
${\trianglelefteq}\upharpoonright(A\times B)$,111111 This denotes the
restriction of ${\trianglelefteq}$ to $A\times B$, i.e.
${\trianglelefteq}\cap((A\times B)\times(A\times B))$.  starting with the
minimal entry. That is,
$\operatorname{vec}_{\trianglelefteq}(K)=(K_{a_{1},b_{1}},\ldots,K_{a_{mn},b_{mn}})$,
where $(a_{1},b_{1}),\ldots,(a_{mn},b_{mn})$ is the unique enumeration of
$A\times B$ such that $(a_{i},b_{i})\trianglelefteq(a_{i+1},b_{i+1})$ for each
$i$.

The operator corresponding to $\trianglelefteq$ is defined using the notion of
a _choice function_ : a function $\alpha$ which maps any tournament $K$ to an
element of $\operatorname{\mathcal{M}}\left({K}\right)$. Any such function
defines a chain-minimal operator $\varphi$ by setting
$\varphi(K)=({\leqslant^{\mathcal{A}}_{\alpha(K)}},{\leqslant^{\mathcal{B}}_{\alpha(K)}})$.

######  Definition .

Let $\trianglelefteq$ be a total order on $\mathbb{N}\times\mathbb{N}$. Define
an operator $\varphi_{\trianglelefteq}$ according to the choice function

$\alpha_{\trianglelefteq}(K)=\operatorname*{arg\
min}_{K^{\prime}\in\operatorname{\mathcal{M}}\left({K}\right)}{\operatorname{vec}_{\trianglelefteq}(K\oplus
K^{\prime})}$ (5)

where $[K\oplus K^{\prime}]_{ab}=|K_{ab}-K_{ab}^{\prime}|$, and the minimum is
taken w.r.t the lexicographic ordering on $\\{0,1\\}^{|A|\cdot|B|}$.121212
Note that $K\oplus K^{\prime}$ is 1 in exactly the entries where $K$ and
$K^{\prime}$ differ.  Operators generated in this way will be called _match-
preference operators_.

###### Example

Let $\trianglelefteq$ be the lexicographic order131313 That is,
$(a,b)\trianglelefteq(a^{\prime},b^{\prime})$ iff $a<a^{\prime}$ or
($a=a^{\prime}$ and $b\leq b^{\prime}$).  on $\mathbb{N}\times\mathbb{N}$ so
that $\operatorname{vec}_{\trianglelefteq}(K\oplus K^{\prime})$ is obtained by
collecting the entries of $K\oplus K^{\prime}$ row-by-row, from top to bottom
and left to right. Take $K$ from Section 3.1. Writing $K_{1},\ldots,K_{4}$ for
the elements of $\operatorname{\mathcal{M}}\left({K}\right)$ in the order that
they appear in Section 3.1 and setting
$v_{i}=\operatorname{vec}_{\trianglelefteq}(K\oplus K_{i})$, we have

$\displaystyle
v_{1}=(0\bm{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1}}00\
0000\
\bm{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1}}0000);$
$\displaystyle\quad\quad
v_{2}=(00\bm{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1}}0\
0000\
\bm{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1}}0000)$
$\displaystyle v_{3}=(0000\
0\bm{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1}}00\
\bm{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1}}0000);$
$\displaystyle\quad\quad v_{4}=(0000\
00\bm{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1}}0\
\bm{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1}}0000)$

The lexicographic minimum is the one with the 1 entries as far right as
possible, which in this case is $v_{4}$. Consequently
$\varphi_{\trianglelefteq}$ ranks $K$ according to $K_{4}$, i.e.
$1\prec_{K}^{\varphi_{\trianglelefteq}}2\prec_{K}^{\varphi_{\trianglelefteq}}3$
and
$1\approx_{K}^{\varphi_{\trianglelefteq}}3\sqsubset_{K}^{\varphi_{\trianglelefteq}}2\sqsubset_{K}^{\varphi_{\trianglelefteq}}4$.

To conclude the discussion of match-preference operators, we note that one can
compute $\alpha_{\trianglelefteq}(K)$ as the unique closest chain tournament
to $K$ w.r.t a _weighted_ Hamming distance, and thereby avoid the need to
enumerate $\operatorname{\mathcal{M}}\left({K}\right)$ in full as per eq. 5.

Let $\trianglelefteq$ be a total order on $\mathbb{N}\times\mathbb{N}$. Then
for any $m,n\in\mathbb{N}$ there exists a function
$w:[m]\times[n]\to\mathbb{R}_{\geq 0}$ such that for all $m\times n$
tournaments $K$:

$\operatorname*{arg\
min}_{K^{\prime}\in\mathcal{C}_{m,n}}{d_{w}(K,K^{\prime})}=\\{\alpha_{\trianglelefteq}(K)\\}$
(6)

where
$d_{w}(K,K^{\prime})=\sum_{(a,b)\in[m]\times[n]}{w(a,b)\cdot|K_{ab}-K^{\prime}_{ab}|}$.

For example, the weights corresponding to $\trianglelefteq$ from Section 5 and
$m=2$, $n=3$ are $w=\left[\begin{smallmatrix}1.5&1.25&1.125\\\
1.0625&1.03125&1.015625\end{smallmatrix}\right]$.

##  6\. Relaxing chain-min

Having studied chain-minimal operators in some detail, we turn to two
remaining problems: chain-min is incompatible with anon, and computing a
chain-minimal operator is NP-hard. In this section we obtain both anonymity
and tractability by relaxing the chain-min requirement to a property we call
_chain-definability_. We go on to characterise the class of operators with
this weaker property via a greedy approximation algorithm, single out a
particularly intuitive instance, and revisit the axioms of Section 4.

###  6.1. Chain-definability

The source of the difficulties with chain-min lies in the minimisation aspect
of chain editing. A natural way to retain the spirit of chain-min without the
complications is to require that $\varphi(K)$ corresponds to _some_ chain
tournament, not necessarily one closest to $K$. We call this property _chain-
definability_.

######  (chain-def)

For every $m\times n$ tournament $K$ there is $K^{\prime}\in\mathcal{C}_{m,n}$
such that
$\varphi(K)=({\leqslant^{\mathcal{A}}_{K^{\prime}}},{\leqslant^{\mathcal{B}}_{K^{\prime}}})$.

Clearly chain-min implies chain-def. ‘Chain-definable’ operators can also be
cast in the MLE framework of Section 3.2 as those whose rankings correspond to
_some_ (not necessarily MLE) state $\theta$.

At first glance it may seem difficult to determine whether a given pair of
rankings correspond to a chain tournament, since the number of such
tournaments grows rapidly with $m$ and $n$. Fortunately, chain-def can be
characterised without reference to chain tournaments by considering the number
of _ranks_ of ${\preceq_{K}^{\varphi}}$ and ${\sqsubseteq_{K}^{\varphi}}$. In
what follows $\mathsf{ranks}({\preceq})$ denotes the number of ranks of a
total preorder $\preceq$, i.e. the number of equivalence classes of its
symmetric part.

$\varphi$ satisfies chain-def if and only if
$|\mathsf{ranks}({\preceq_{K}^{\varphi}})-\mathsf{ranks}({\sqsubseteq_{K}^{\varphi}})|\leq
1$ for every tournament $K$.

###  6.2. Interleaving Operators

According to Section 6.1, to construct a chain-definable operator it is enough
to ensure that the number of ranks of $\preceq_{K}^{\varphi}$ and
$\sqsubseteq_{K}^{\varphi}$ differ by at most one. A simple way to achieve
this is to iteratively select and remove the top-ranked players of $A$ and $B$
simultaneously, until one of $A$ or $B$ is exhausted. We call such operators
_interleaving operators_. Closely related ranking methods have been previously
introduced for non-bipartite tournaments by Bouyssou (2004).

Formally, our procedure is defined by two functions $f$ and $g$ which select
the next top ranks given a tournament $K$ and subsets $A^{\prime}\subseteq A$,
$B^{\prime}\subseteq B$ of the remaining players.

######  Definition .

An $\mathcal{A}$-_selection function_ is a mapping $f:\mathcal{K}\times
2^{\mathbb{N}}\times 2^{\mathbb{N}}\to 2^{\mathbb{N}}$ such that for any
tournament $K$, $A^{\prime}\subseteq A$ and $B^{\prime}\subseteq B$:  (i)
$f(K,A^{\prime},B^{\prime})\subseteq A^{\prime}$;  (ii) If
$A^{\prime}\neq\emptyset$ then $f(K,A^{\prime},B^{\prime})\neq\emptyset$;
(iii) $f(K,A^{\prime},\emptyset)=A^{\prime}$ .

Similarly, a $\mathcal{B}$-_selection function_ is a mapping
$g:\mathcal{K}\times 2^{\mathbb{N}}\times 2^{\mathbb{N}}\to 2^{\mathbb{N}}$
such that  (i) $g(K,A^{\prime},B^{\prime})\subseteq B^{\prime}$;  (ii) If
$B^{\prime}\neq\emptyset$ then $g(K,A^{\prime},B^{\prime})\neq\emptyset$;
(iii) $g(K,\emptyset,B^{\prime})=B^{\prime}$ .

The corresponding interleaving operator ranks players according to how soon
they are selected in this way; the earlier the better.

######  Definition .

Let $f$ and $g$ be selection functions and $K$ a tournament. Write $A_{0}=A$,
$B_{0}=B$, and for $i\geq 0$:

$A_{i+1}=A_{i}\setminus f(K,A_{i},B_{i});\quad B_{i+1}=B_{i}\setminus
g(K,A_{i},B_{i})$

For $a\in A$ and $b\in B$, write $r(a)=\max{\\{i\mid a\in A_{i}\\}}$ and
$s(b)=\max{\\{i\mid b\in B_{i}\\}}$.141414 We show in the appendix that the
recursive procedure eventually terminates with $A_{i}$ and $B_{i}$ becoming
empty (and remaining so) after finitely many iterations, so $r$ and $s$ are
well-defined.  We define the corresponding _interleaving operator_
$\varphi={\varphi_{f,g}^{\mathsf{int}}}$ by $a\preceq_{K}^{\varphi}a^{\prime}$
iff $r(a)\geq r(a^{\prime})$ and $b\sqsubseteq_{K}^{\varphi}b^{\prime}$ iff
$s(b)\geq s(b^{\prime})$.

Note that $A_{i}$ and $B_{i}$ are the players left remaining after $i$
applications of $f$ and $g$, i.e. after removing the top $i$ ranks from both
sides. Before giving a concrete example, we note that interleaving is not just
_one_ way to satisfying chain-def, it is the _only_ way.

An operator $\varphi$ satisfies chain-def if and only if
$\varphi={\varphi_{f,g}^{\mathsf{int}}}$ for some selection functions $(f,g)$.

Section 6.2 justifies our study of interleaving operators, and provides a
different perspective on chain-definability via the selection functions $f$
and $g$. We come to an important example.

###### Example

Define the _cardinality-based interleaving operator_
${\varphi_{\mathsf{CI}}}={\varphi_{f,g}^{\mathsf{int}}}$ where
$f(K,A^{\prime},B^{\prime})=\operatorname*{arg\ max}_{a\in
A^{\prime}}{|K(a)\cap B^{\prime}|}$ and
$g(K,A^{\prime},B^{\prime})=\operatorname*{arg\ min}_{b\in
B^{\prime}}{|K^{-1}(b)\cap A^{\prime}|}$, so that the ‘winners’ at each
iteration are the $A$s with the most wins, and the $B$s with the least losses,
when restricting to $A^{\prime}$ and $B^{\prime}$ only. We take the
$\operatorname*{arg\ min}$/$\operatorname*{arg\ max}$ to be the emptyset
whenever $A^{\prime}$ or $B^{\prime}$ is empty.

Table 1 shows the iteration of the algorithm for a $4\times 5$ tournament $K$.
In each row $i$ we show $K$ with the rows and columns of $A\setminus A_{i}$
and $B\setminus B_{i}$ greyed out, so as to make it more clear how the $f$ and
$g$ values are calculated.151515 Note that while $f$ and $g$ for
${\varphi_{\mathsf{CI}}}$ are independent of the greyed out entries, we do not
require this property for selection functions in general.  For brevity we also
write $f$ and $g$ in place of $f(K,A_{i},B_{i})$ and $g(K,A_{i},B_{i})$
respectively.

The $r$ and $s$ values can be read off as 0, 2, 1, 3 for $A$ and 0, 3, 1, 1, 2
for $B$, giving the ranking on $A$ as $4\prec 2\prec 3\prec 1$, and the
ranking on $B$ as $2\sqsubset 5\sqsubset 3\approx 4\sqsubset 1$. Note also
that each $f(K,A_{i},B_{i})$ is a rank of $\preceq_{K}^{\varphi}$ (and similar
for $g(K,A_{i},B_{i})$), so the rankings can in fact be read off by looking at
the $f$ and $g$ columns of Table 1.

Table 1. Iteration of the interleaving algorithm for ${\varphi_{\mathsf{CI}}}$ $i$ | $K$ | $A_{i}$ | $B_{i}$ | $f$ | $g$ | $K^{\prime}_{i}$
---|---|---|---|---|---|---
$0$ | $\left[\begin{smallmatrix}1&1&1&1&0\\\ 0&1&0&0&1\\\ 0&1&0&1&1\\\ 0&1&1&0&0\\\ \end{smallmatrix}\right]$ | $\\{1,2,3,4\\}$ | $\\{1,2,3,4,5\\}$ | $\\{1\\}$ | $\\{1\\}$ | $\left[\begin{smallmatrix}1&1&1&1&\bm{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1}}\\\ 0&1&0&0&1\\\ 0&1&0&1&1\\\ 0&1&1&0&0\\\ \end{smallmatrix}\right]$
$1$ | $\left[\begin{smallmatrix}{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color@gray@fill{.75}1}&{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color@gray@fill{.75}1}&{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color@gray@fill{.75}1}&{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color@gray@fill{.75}1}&{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color<EMAIL_ADDRESS>{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color<EMAIL_ADDRESS>{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color<EMAIL_ADDRESS>{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color<EMAIL_ADDRESS>\end{smallmatrix}\right]$ | $\\{2,3,4\\}$ | $\\{2,3,4,5\\}$ | $\\{3\\}$ | $\\{3,4\\}$ | $\left[\begin{smallmatrix}1&1&1&1&\bm{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1}}\\\ 0&1&0&0&1\\\ 0&1&\bm{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1}}&1&1\\\ 0&1&\bm{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0}}&0&0\\\ \end{smallmatrix}\right]$
$2$ | $\left[\begin{smallmatrix}{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color@gray@fill{.75}1}&{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color@gray@fill{.75}1}&{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color@gray@fill{.75}1}&{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color@gray@fill{.75}1}&{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color<EMAIL_ADDRESS>{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color@gray@fill{.75}0}&1&{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color@gray@fill{.75}0}&{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color<EMAIL_ADDRESS>{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color@gray@fill{.75}0}&{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color@gray@fill{.75}1}&{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color@gray@fill{.75}0}&{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color@gray@fill{.75}1}&{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color<EMAIL_ADDRESS>{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color@gray@fill{.75}0}&1&{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color@gray@fill{.75}1}&{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color<EMAIL_ADDRESS>\end{smallmatrix}\right]$ | $\\{2,4\\}$ | $\\{2,5\\}$ | $\\{2\\}$ | $\\{5\\}$ | -
$3$ | $\left[\begin{smallmatrix}{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color@gray@fill{.75}1}&{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color@gray@fill{.75}1}&{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color@gray@fill{.75}1}&{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color@gray@fill{.75}1}&{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color<EMAIL_ADDRESS>{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color@gray@fill{.75}0}&{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color@gray@fill{.75}1}&{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color@gray@fill{.75}0}&{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color@gray@fill{.75}0}&{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color<EMAIL_ADDRESS>{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color@gray@fill{.75}0}&{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color@gray@fill{.75}1}&{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color@gray@fill{.75}0}&{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color@gray@fill{.75}1}&{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color<EMAIL_ADDRESS>{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color@gray@fill{.75}0}&1&{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color@gray@fill{.75}1}&{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color@gray@fill{.75}0}&{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color<EMAIL_ADDRESS>\end{smallmatrix}\right]$ | $\\{4\\}$ | $\\{2\\}$ | $\\{4\\}$ | $\\{2\\}$ | -
$4$ | - | $\emptyset$ | $\emptyset$ | $\emptyset$ | $\emptyset$ | -

The interleaving algorithm can also be seen as a greedy algorithm for
converting $K$ into a chain graph directly. Indeed, by setting the
neighbourhood of each $a\in f(K,A_{i},B_{i})$ to $B_{i}$, and removing each
$b\in g(K,A_{i},B_{i})$ from the neighbourhoods of all $a\in A_{i+1}$, we
eventually obtain a chain graph. We show this process in the $K^{\prime}_{i}$
column of Table 1, where only three entries need to be changed.161616 In this
example $\operatorname{\mathcal{M}}\left({K}\right)$ contains a single
tournament a distance of 2 from $K$, so ${\varphi_{\mathsf{CI}}}$ makes one
more change than necessary.  The selection functions $f$ and $g$ can therefore
be seen as _heuristics_ with the goal of finding a chain graph ‘close’ to $K$.

The operator ${\varphi_{\mathsf{CI}}}$ from Section 6.2 uses simple
cardinality-based heuristics, and can be seen as a chain-definable version of
${\varphi_{\mathsf{count}}}$ (which is not chain-definable). It is also the
bipartite counterpart to repeated applications of Copeland’s rule Bouyssou
(2004). Note that $f(K,A_{i},B_{i})$ and $g(K,A_{i},B_{i})$ can be computed in
$O(N^{2})$ time at each iteration $i$, where $N=|A|+|B|$. Since there cannot
be more than $N$ iterations, it follows that the rankings of
${\varphi_{\mathsf{CI}}}$ can be computed in $O(N^{3})$ time.

###  6.3. Axiom Compatibility

We now revisit the axioms of Section 4 in relation to chain-definable
operators in general and ${\varphi_{\mathsf{CI}}}$ specifically. Firstly, the
weakening of chain-min pays off: chain-def is compatible with all our axioms.

For each of anon, dual, IIM, mon and pos-resp, there exists an operator
satisfying chain-def and the stated property.

Unfortunately, these cannot all hold at the same time. Indeed, taking
$K=\left[\begin{smallmatrix}0&0&1&1\\\ 0&1&0&1\end{smallmatrix}\right]^{\top}$
and assuming anon and pos-resp, the ranking on $A$ is fully determined as
$1\prec 2\approx 3\prec 4$, and $\mathsf{ranks}({\preceq_{K}^{\varphi}})=3$.
However, anon with dual implies the ranking of $B$ is flat, i.e.
$\mathsf{ranks}({\sqsubseteq_{K}^{\varphi}})=1$. This contradicts chain-def by
Section 6.1, yielding the following impossibility result.

There is no operator satisfying chain-def, anon, dual and pos-resp.

For the specific operator ${\varphi_{\mathsf{CI}}}$ we have the following.

${\varphi_{\mathsf{CI}}}$ satisfies chain-def, anon, dual and mon, and does
not satisfy IIM or pos-resp.

Note that anon _is_ satisfied. This makes ${\varphi_{\mathsf{CI}}}$ an
important example of a well-motivated, tractable, chain-definable and
anonymous operator, meeting the criteria outlined at the start of this
section.

##  7\. Related Work

On chain graphs. Chain graphs were originally introduced by Yannakakis (1981),
who proved that _chain completion_ – finding the minimum number of edges that
when added to a bipartite graph form a chain graph – is NP-complete. Hardness
results have subsequently been obtained for chain _deletion_ Natanzon et al.
(2001) (where only edge deletions are allowed) and chain _editing_ Drange et
al. (2015) (where both additions and deletions are allowed). We refer the
reader to the work of Jiao et al. (2017) and Drange et al. (2015) for a more
detailed account of this literature. Outside of complexity theory, chain
graphs have been studied for their spectral properties in Anđelić et al.
(2015); Ghorbani (2017), and the more general notion of a _nested colouring_
was introduced in Cook II (2015).

On tournaments in social choice. Tournaments have important applications in
the design of voting rules, where an alternative $x$ beats $y$ in a pairwise
comparison if a majority of voters prefer $x$ to $y$. Various _tournament
solutions_ have been proposed, which select a set of ‘winners’ from a given
tournament.171717Note that a ranking, such as we consider in this paper,
induces a set of winners by taking the maximally ranked players. Of particular
relevance to our work are the _Slater set_ and _Kemeney’s rule_ Brandt et al.
(2016), which find minimal sets of edges to invert in the tournament graph
such that the beating relation becomes a total order.181818 Note that like
chain editing, Kemeny’s rule also admits a maximum likelihood characterisation
Elkind and Slinko (2016).  These methods are intuitively similar to chain
editing: both involve making minimal changes to the tournament until some
property is satisfied. A rough analogue to the Slater set in our framework is
the union of the top-ranked players from each
$K^{\prime}\in\operatorname{\mathcal{M}}\left({K}\right)$. Solutions based on
the covering relation – such as the _uncovered_ and _Banks_ set Brandt et al.
(2016) – also bear similarity to chain editing.

Finally, note that directed versions of chain graphs (obtained by orienting
edges from $A$ to $B$ and adding missing edges from $B$ to $A$) correspond to
_acyclic tournaments_ , and a topological sort of $A$ becomes a linearisation
of the chain ranking $\leqslant^{\mathcal{A}}_{K}$. This suggests a connection
between chain deletion and the standard _feedback arc set_ problem for
removing cycles and obtaining a ranking.

On generalised tournaments. A _generalised_ tournament González-Díaz et al.
(2014) is a pair $(X,T)$, where $X=[t]$ for some $t\in\mathbb{N}$ and
$T\in\mathbb{R}_{\geq 0}^{t\times t}$ is a non-negative $t\times t$ matrix
with $T_{ii}=0$ for all $i\in X$. In this formalism each encounter between a
pair of players $i$ and $j$ is represented by _two_ numbers: $T_{ij}$ and
$T_{ji}$. This allows one to model both intensities of victories and losses
(including draws) via the difference $T_{ij}-T_{ji}$, and the case where a
comparison is not available (where $T_{ij}=T_{ji}=0$).

Any $m\times n$ bipartite tournament $K$ has a natural generalised tournament
representation via the $(m+n)\times(m+n)$ _anti-diagonal block matrix_
$T=\left[\begin{smallmatrix}0&K\\\
{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}&0\end{smallmatrix}\right]$,
where the top-left and bottom-right blocks are the $m\times m$ and $n\times n$
zero matrices respectively. However, such anti-diagonal block matrices are
often excluded in the generalised tournament literature due to an assumption
of _irreducibility_ , which requires that the directed graph corresponding to
$T$ is strongly connected. This is not the case in general for $T$ constructed
as above, which means not all existing tournament operators (and tournament
axioms) are well-defined for bipartite inputs.191919 We note that Slutzki and
Volij (2005) side-step the reducibility issue by decomposing $T$ into
irreducible components and ranking each separately, although their methods may
give only _partial_ orders.  Consequently, bipartite tournaments are a special
case of generalised tournaments _in principle_ , but not in practise.

##  8\. Conclusion

Summary. In this paper we studied chain editing, an interesting problem from
computational complexity theory, as a ranking mechanism for bipartite
tournaments. We analysed such mechanisms from a probabilistic viewpoint via
the MLE characterisation, and in axiomatic terms. To resolve both the failure
of an important anonymity axiom and NP-hardness, we weakened the chain editing
requirement to one of _chain definability_ , and characterised the resulting
class of operators by the intuitive interleaving algorithm.

Limitations and future work. The hardness of chain editing remains a
limitation of our approach. A possible remedy is to look to one of the
numerous variant problems that are polynomial-time solvable Jiao et al.
(2017); determining their applicability to ranking is an interesting topic for
future work. One could develop approximation algorithms for chain editing,
possibly based on existing approximations of chain completion Natanzon et al.
(2000). The interleaving operators of Section 6.2 go in this direction, but we
did not yet obtain any theoretical or experimental bounds on the approximation
ratio.

A second limitation of our work lies in the assumptions of the probabilistic
model; namely that the true state of the world can be reduced to vectors of
numerical skill levels which totally describe the tournament participants.
This assumption may be violated when the competitive element of a tournament
is _multi-faceted_ , since a single number cannot represent multiple
orthogonal components of a player’s capabilities. Nevertheless, if skill
levels are taken as _aggregations_ of these components, chain editing may
prove to be a useful, albeit simplified, model.

Finally, there is room for more detailed axiomatic investigation. In this
paper we have stuck with fairly standard social choice axioms and performed
preliminary analysis. However, the indirect nature of the comparisons in a
bipartite tournament presents unique challenges; new axioms may need to be
formulated to properly evaluate bipartite ranking methods in a normative
sense.

We thank the anonymous AAMAS reviewers for their helpful comments.

## References

  * (1)
  * Anđelić et al. (2015) Milica Anđelić, Enide Andrade, Domingos M. Cardoso, Carlos M. da Fonseca, Slobodan K. Simić, and Dejan V. Tošić. 2015\.  Some new considerations about double nested graphs.  _Linear Algebra Appl._ 483 (2015), 323 – 341.
  * Bouyssou (2004) Denis Bouyssou. 2004\.  Monotonicity of ‘ranking by choosing’: A progress report.  _Social Choice and Welfare_ 23, 2 (2004), 249–273.
  * Bozóki et al. (2016) Sándor Bozóki, László Csató, and József Temesi. 2016.  An application of incomplete pairwise comparison matrices for ranking top tennis players.  _European Journal of Operational Research_ 248, 1 (2016), 211–218.
  * Bradley and Terry (1952) Ralph Allan Bradley and Milton E. Terry. 1952.  Rank Analysis of Incomplete Block Designs: I. The Method of Paired Comparisons.  _Biometrika_ 39, 3/4 (1952), 324–345.
  * Brandt et al. (2016) Felix Brandt, Markus Brill, Paul Harrenstein, and Hervé Moulin. 2016.  Tournament Solutions.  In _Handbook of Computational Social Choice_ , Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia (Eds.). Cambridge University Press, 57–84.
  * Cook II (2015) David Cook II. 2015\.  Nested colorings of graphs.  _Australasian Journal of Combinatorics_ 62, 1 (2015), 100–127.
  * Csató (2019) László Csató. 2019\.  An impossibility theorem for paired comparisons.  _Central European Journal of Operations Research_ 27, 2 (2019), 497–514.
  * Denny et al. (2008) Paul Denny, John Hamer, Andrew Luxton-Reilly, and Helen Purchase. 2008.  PeerWise: Students Sharing Their Multiple Choice Questions. In _Proceedings of the Fourth International Workshop on Computing Education Research_ _(ICER ’08)_. ACM, New York, 51–58.
  * Drange et al. (2015) Pål Grønås Drange, Markus Sortland Dregi, Daniel Lokshtanov, and Blair D. Sullivan. 2015.  On the threshold of intractability.  In _Algorithms-ESA 2015_. Springer, 411–423.
  * Elkind and Slinko (2016) Edith Elkind and Arkadii Slinko. 2016.  Rationalizations of voting rules.  In _Handbook of Computational Social Choice_ , Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia (Eds.). Cambridge University Press, 169–196.
  * Everaere et al. (2020) Patricia Everaere, Sebastien Konieczny, and Pierre Marquis. 2020.  Belief Merging Operators as Maximum Likelihood Estimators. In _Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20_ , Christian Bessiere (Ed.). International Joint Conferences on Artificial Intelligence Organization, 1763–1769.
  * Galland et al. (2010) Alban Galland, Serge Abiteboul, Amélie Marian, and Pierre Senellart. 2010.  Corroborating Information from Disagreeing Views. In _Proceedings of the Third ACM International Conference on Web Search and Data Mining_ _(WSDM ’10)_. ACM, New York, 131–140.
  * Ghorbani (2017) Ebrahim Ghorbani. 2017\.  Some spectral properties of chain graphs.  (2017).  arXiv:math.CO/1703.03581
  * González-Díaz et al. (2014) Julio González-Díaz, Ruud Hendrickx, and Edwin Lohmann. 2014\.  Paired comparisons analysis: an axiomatic approach to ranking methods.  _Social Choice and Welfare_ 42, 1 (2014), 139–169.
  * Jiao et al. (2017) Yang Jiao, R Ravi, and Wolfgang Gatterbauer. 2017.  Algorithms for automatic ranking of participants and tasks in an anonymized contest. In _International Workshop on Algorithms and Computation_. Springer, 335–346.
  * Li et al. (2016) Yaliang Li, Jing Gao, Chuishi Meng, Qi Li, Lu Su, Bo Zhao, Wei Fan, and Jiawei Han. 2016.  A Survey on Truth Discovery.  _SIGKDD Explor. Newsl._ 17, 2 (Feb. 2016), 1–16.
  * Natanzon et al. (2000) Assaf Natanzon, Ron Shamir, and Roded Sharan. 2000\.  A polynomial approximation algorithm for the minimum fill-in problem.  _SIAM J. Comput._ 30, 4 (2000), 1067–1079.
  * Natanzon et al. (2001) Assaf Natanzon, Ron Shamir, and Roded Sharan. 2001\.  Complexity classification of some edge modification problems.  _Discrete Applied Mathematics_ 113, 1 (2001), 109–128.
  * Olsson et al. (2018) Catherine Olsson, Surya Bhupatiraju, Tom Brown, Augustus Odena, and Ian Goodfellow. 2018.  Skill Rating for Generative Models.  (2018).  arXiv:stat.ML/1808.04888
  * Rubinstein (1980) Ariel Rubinstein. 1980\.  Ranking the participants in a tournament.  _SIAM J. Appl. Math._ 38, 1 (1980), 108–111.
  * Singleton and Booth (2020) Joseph Singleton and Richard Booth. 2020.  An Axiomatic Approach to Truth Discovery. In _Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems_ _(AAMAS ’20)_. International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 2011–2013.
  * Slutzki and Volij (2005) Giora Slutzki and Oscar Volij. 2005.  Ranking participants in generalized tournaments.  _International Journal of Game Theory_ 33, 2 (2005), 255–270.
  * Slutzki and Volij (2006) Giora Slutzki and Oscar Volij. 2006.  Scoring of web pages and tournaments—axiomatizations.  _Social Choice and Welfare_ 26, 1 (2006), 75–92.
  * Wang et al. (2012) Dong Wang, Lance Kaplan, Hieu Le, and Tarek Abdelzaher. 2012\.  On Truth Discovery in Social Sensing: A Maximum Likelihood Estimation Approach. In _Proceedings of the 11th International Conference on Information Processing in Sensor Networks_ _(IPSN ’12)_. ACM, New York, 233–244.
  * Yannakakis (1981) Mihalis Yannakakis. 1981\.  Computing the minimum fill-in is NP-complete.  _SIAM Journal on Algebraic Discrete Methods_ 2, 1 (1981), 77–79.

##  Appendix A Proofs

This appendix contains proofs that were omitted (or only sketched) in the main
paper.

###  A.1. Proof of Section 3.2

The proof of Section 3.2 requires a lemma of its own.

###### Lemma

Let $K$ be an $m\times n$ tournament, $\bm{\alpha}\in[0,1]^{2}$ and
$\theta\in\Theta_{m,n}$. Then

$\begin{split}P_{\bm{\alpha}}(K\mid\theta)=\prod_{a\in
A}&\alpha_{+}^{|K(a)\setminus K_{\theta}(a)|}(1-\alpha_{-})^{|K(a)\cap
K_{\theta}(a)|}\\\ &\quad(1-\alpha_{+})^{|B\setminus(K(a)\cup
K_{\theta}(a))|}\alpha_{-}^{|K_{\theta}(a)\setminus K(a)|}\end{split}$

###### Proof.

Write $p_{ab,K}$ for $P_{\bm{\alpha}}(X_{ab}=K_{ab}\mid\theta)$. Expanding the
product in section 3.2, we have

$P_{\bm{\alpha}}(K\mid\theta)=\prod_{a\in A}{\prod_{b\in B}{p_{ab,K}}}$

Let $a\in A$. Note that $B$ can be written as the disjoint union $B=B_{1}\cup
B_{2}\cup B_{3}\cup B_{4}$, where

$\displaystyle B_{1}$ $\displaystyle=K(a)\setminus K_{\theta}(a)$
$\displaystyle B_{2}$ $\displaystyle=K(a)\cap K_{\theta}(a)$ $\displaystyle
B_{3}$ $\displaystyle=B\setminus(K(a)\cup K_{\theta}(a))$ $\displaystyle
B_{4}$ $\displaystyle=K_{\theta}(a)\setminus K(a)$

Recall that $b\in K_{\theta}(a)$ iff $x_{a}\geq y_{b}$ (where
$\theta=\langle{\bm{x},\bm{y}}\rangle$). It follows that

  * •

$b\in B_{1}$ iff $K_{ab}=1$ and $x_{a}<y_{b}$

  * •

$b\in B_{2}$ iff $K_{ab}=1$ and $x_{a}\geq y_{b}$

  * •

$b\in B_{3}$ iff $K_{ab}=0$ and $x_{a}<y_{b}$

  * •

$b\in B_{4}$ iff $K_{ab}=0$ and $x_{a}\geq y_{b}$

Note that this correspond exactly to the four cases in 3 and 4 which define
$p_{ab,K}$; we have

$p_{ab,K}=\begin{cases}\alpha_{+},&b\in B_{1}\\\ 1-\alpha_{-},&b\in B_{2}\\\
1-\alpha_{+},&b\in B_{3}\\\ \alpha_{-},&b\in B_{4}\end{cases}$

Consequently

$\displaystyle\prod_{b\in B}{p_{ab,K}}$ $\displaystyle=\left(\prod_{b\in
B_{1}}{\alpha_{+}}\right)\left(\prod_{b\in
B_{2}}{(1-\alpha_{-})}\right)\left(\prod_{b\in
B_{3}}{(1-\alpha_{+})}\right)\left(\prod_{b\in B_{4}}{\alpha_{-}}\right)$
$\displaystyle=\alpha_{+}^{|B_{1}|}(1-\alpha_{-})^{|B_{2}|}(1-\alpha_{+})^{|B_{3}|}\alpha_{-}^{|B_{4}|}$
$\displaystyle=\alpha_{+}^{|K(a)\setminus
K_{\theta}(a)|}(1-\alpha_{-})^{|K(a)\cap K_{\theta}(a)|}$
$\displaystyle\quad\quad(1-\alpha_{+})^{|B\setminus(K(a)\cup
K_{\theta}(a))|}\alpha_{-}^{|K_{\theta}(a)\setminus K(a)|}$

Taking the product over all $a\in A$ we reach the desired expression for
$P_{\bm{\alpha}}(K\mid\theta)$. ∎

###### Proof of Section 3.2.

Let $\theta\in\Theta_{m,n}$. From section A.1 we get

$\displaystyle P_{\bm{\alpha}}(K\mid\theta)=\prod_{a\in A}$
$\displaystyle\beta^{|K(a)\setminus K_{\theta}(a)|+|K_{\theta}(a)\setminus
K(a)|}$ $\displaystyle\quad(1-\beta)^{|K(a)\cap
K_{\theta}(a)|+|B\setminus(K(a)\cup K_{\theta}(a))|}$

Note that

$|K(a)\setminus K_{\theta}(a)|+|K_{\theta}(a)\setminus
K(a)|=|K(a)\mathrel{\triangle}K_{\theta}(a)|$ $|K(a)\cap
K_{\theta}(a)|+|B\setminus(K(a)\cup
K_{\theta}(a))|=|B|-|K(a)\mathrel{\triangle}K_{\theta}(a)|$

and so

$\displaystyle P_{\bm{\alpha}}(K\mid\theta)$ $\displaystyle=\prod_{a\in
A}{\beta^{|K(a)\mathrel{\triangle}K_{\theta}(a)|}(1-\beta)^{|B|-|K(a)\mathrel{\triangle}K_{\theta}(a)|}}$
$\displaystyle=\prod_{a\in
A}{\left(\frac{\beta}{1-\beta}\right)^{|K(a)\mathrel{\triangle}K_{\theta}(a)|}(1-\beta)^{|B|}}$
$\displaystyle=\underbrace{(1-\beta)^{|A|\cdot|B|}}_{=c}\prod_{a\in
A}{\left(\frac{\beta}{1-\beta}\right)^{|K(a)\mathrel{\triangle}K_{\theta}(a)|}}$
$\displaystyle=c\prod_{a\in
A}{\left(\frac{\beta}{1-\beta}\right)^{|K(a)\mathrel{\triangle}K_{\theta}(a)|}}$

where $c$ is a positive constant that does not depend on $\theta$. Now,
$P_{\bm{\alpha}}(K\mid\theta)$ is positive, and is maximal when its logarithm
is. We have

$\displaystyle\log{P_{\bm{\alpha}}(K\mid\theta)}$
$\displaystyle=\log{c}+\sum_{a\in
A}{|K(a)\mathrel{\triangle}K_{\theta}(a)|\log{\left(\frac{\beta}{1-\beta}\right)}}$
$\displaystyle=\log{c}+\log{\left(\frac{\beta}{1-\beta}\right)}\sum_{a\in
A}{|K(a)\mathrel{\triangle}K_{\theta}(a)|}$
$\displaystyle=\log{c}+\log{\left(\frac{\beta}{1-\beta}\right)}d(K,K_{\theta})$

Noting that $\beta<1/2$ implies $\log{\left(\frac{\beta}{1-\beta}\right)}<0$,
it follows that for any $\theta,\theta^{\prime}\in\Theta_{m,n}$:

$\displaystyle P_{\bm{\alpha}}(K\mid\theta)\geq
P_{\bm{\alpha}}(K\mid\theta^{\prime})$
$\displaystyle\iff\log{P_{\bm{\alpha}}(K\mid\theta)}-\log{P_{\bm{\alpha}}(K\mid\theta^{\prime})}\geq
0$
$\displaystyle\iff\underbrace{\log{\left(\frac{\beta}{1-\beta}\right)}}_{<0}\left[d(K,K_{\theta})-d(K,K_{\theta^{\prime}})\right]\geq
0$ $\displaystyle\iff d(K,K_{\theta})\leq d(K,K_{\theta^{\prime}})$

which proves the result. ∎

###  A.2. Proof of Section 3.2

We need a preliminary result.

###### Lemma

Let $\theta=\langle{\bm{x},\bm{y}}\rangle\in\Theta_{m,n}$. Then for all
$a,a^{\prime}\in A$ and $b,b^{\prime}\in B$:

  1. (1)

$K_{\theta}(a)\subseteq K_{\theta}(a^{\prime})$ iff $x_{a}\leq x_{a^{\prime}}$

  2. (2)

$K_{\theta}^{-1}(b)\supseteq K_{\theta}^{-1}(b^{\prime})$ iff $y_{b}\leq
y_{b^{\prime}}$.

###### Proof.

We prove (1); (2) is shown similarly. Let $a,a^{\prime}\in A$. First suppose
$x_{a}\leq x_{a^{\prime}}$. Let $b\in K_{\theta}(a)$. Then $y_{b}\leq
x_{a}\leq x_{a^{\prime}}$, so $b\in K_{\theta}(a^{\prime})$ also. This shows
$K_{\theta}(a)\subseteq K_{\theta}(a^{\prime})$.

Now suppose $K_{\theta}(a)\subseteq K_{\theta}(a^{\prime})$. For the sake of
contradiction, suppose $x_{a}>x_{a^{\prime}}$. By 1 in the definition of a
state (section 3.2), there is $b\in B$ such that $x_{a^{\prime}}<y_{b}\leq
x_{a}$. But this means $b\in K_{\theta}(a)\setminus K_{\theta}(a^{\prime})$,
which contradicts $K_{\theta}(a)\subseteq K_{\theta}(a^{\prime})$. Thus (1) is
proved. ∎

###### Proof of Section 3.2.

The “if” direction follows from section A.2 part (1): if
$\theta=\langle{\bm{x},\bm{y}}\rangle$ and $a,a^{\prime}\in A$ then either
$x_{a}\leq x_{a^{\prime}}$ – in which case $K_{\theta}(a)\subseteq
K_{\theta}(a^{\prime})$ – or $x_{a^{\prime}}<x_{a}$ – in which case
$K_{\theta}(a^{\prime})\subseteq K_{\theta}(a)$. Therefore $K_{\theta}$ has
the chain property.

For the “only if” direction, suppose $K$ has the chain property. Define
$\theta=\langle{\bm{x},\bm{y}}\rangle$ by

$\displaystyle x_{a}$ $\displaystyle=|\\{a^{\prime}\in A\mid
K(a^{\prime})\subseteq K(a)\\}|$ $\displaystyle y_{b}$
$\displaystyle=\begin{cases}\min\\{x_{a}\mid a\in
K^{-1}(b)\\},&K^{-1}(b)\neq\emptyset\\\ 1+|A|,&K^{-1}(b)=\emptyset\end{cases}$

It is easily that since the neighbourhood-subset relation
${\leqslant^{\mathcal{A}}_{K}}$ is a total preorder, we have $K(a)\subseteq
K(a^{\prime})$ if and only if $x_{a}\leq x_{a^{\prime}}$. First we show that
$K_{\theta}=K$ by showing that $K_{ab}=1$ if and only if
$[K_{\theta}]_{ab}=1$. Suppose $K_{ab}=1$. Then $a\in K^{-1}(b)$, so
$y_{b}=\min\\{x_{a^{\prime}}\mid a^{\prime}\in K^{-1}(b)\\}\leq x_{a}$ and
consequently $[K_{\theta}]_{ab}=1$.

Now suppose $[K_{\theta}]_{ab}=1$. Then $x_{a}\geq y_{b}$. We must have
$K^{-1}(b)\neq\emptyset$; otherwise $y_{b}=1+|A|>|A|\geq x_{a}$. We can
therefore take $\hat{a}\in\operatorname*{arg\ min}_{a^{\prime}\in
K^{-1}(b)}{x_{a^{\prime}}}$. By definition of $y_{b}$, $x_{\hat{a}}=y_{b}\leq
x_{a}$. But $x_{\hat{a}}\leq x_{a}$ implies $K(\hat{a})\subseteq K(a)$; since
$\hat{a}\in K^{-1}(b)$ this gives $b\in K(\hat{a})$ and $b\in K(a)$, i.e.
$K_{ab}=1$. This completes the claim that $K=K_{\theta}$.

It only remains to show that $\theta$ satisfies conditions 1 and 2 of section
3.2. For 1, suppose $x_{a}<x_{a^{\prime}}$. Then $K(a)\subset K(a^{\prime})$,
i.e there is $b\in K(a^{\prime})\setminus K(a)=K_{\theta}(a^{\prime})\setminus
K_{\theta}(a)$. But $b\in K_{\theta}(a^{\prime})$ gives $y_{b}\leq
x_{a^{\prime}}$, and $b\not\in K_{\theta}(a)$ gives $x_{a}<y_{b}$; this shows
that 1 holds.

For 2, suppose $y_{b}<y_{b^{\prime}}$. Clearly $K^{-1}(b)\neq\emptyset$
(otherwise $y_{b}=1+|A|$ is maximal). Thus there is $a\in K^{-1}(b)$ such that
$y_{b}=x_{a}$. This of course means $x_{a}<y_{b^{\prime}}$; in particular we
have $y_{b}\leq x_{a}<y_{b^{\prime}}$ as required for 2.

We have shown that $K=K_{\theta}$ and that $\theta\in\Theta_{m,n}$, and the
proof is complete. ∎

###  A.3. Proof of Section 3.2

###### Proof.

First we show that for any $m,n\in\mathbb{N}$ and any $m\times n$ tournament
$K$ it holds that $\theta$ is an MLE state for $K$ if and only if
$K_{\theta}\in\operatorname{\mathcal{M}}\left({K}\right)$.

Indeed, fix some $m,n$ and $K$. Write
$\mathcal{K}_{\Theta_{m,n}}=\\{K_{\theta}\mid\theta\in\Theta_{m,n}\\}$. By
section 3.2, $\theta$ is an MLE if and only if $d(K,K_{\theta})\leq
d(K,K_{\theta^{\prime}})$ for all $\theta^{\prime}\in\Theta_{m,n}$, i.e.
$K_{\theta}\in\operatorname*{arg\
min}_{K^{\prime}\in\mathcal{K}_{\Theta_{m,n}}}{d(K,K^{\prime})}$. But by
section 3.2, $\mathcal{K}_{\Theta_{m,n}}$ is just $\mathcal{C}_{m,n}$, the set
of all $m\times n$ tournaments with the chain property. We see that
$\operatorname*{arg\
min}_{K^{\prime}\in\mathcal{K}_{\Theta_{m,n}}}{d(K,K^{\prime})}=\operatorname*{arg\
min}_{K^{\prime}\in\mathcal{C}_{m,n}}{d(K,K^{\prime})}=\operatorname{\mathcal{M}}\left({K}\right)$
by definition of $\operatorname{\mathcal{M}}\left({K}\right)$. This shows that
$\theta$ is an MLE iff
$K_{\theta}\in\operatorname{\mathcal{M}}\left({K}\right)$.

Now, by definition, $\varphi$ satisfies chain-min iff for every tournament $K$
there is $K^{\prime}\in\operatorname{\mathcal{M}}\left({K}\right)$ such that
$\varphi(K)=({\leqslant^{\mathcal{A}}_{K^{\prime}}},{\leqslant^{\mathcal{B}}_{K^{\prime}}})$.
Using section 3.2 and the above result,
$K^{\prime}\in\operatorname{\mathcal{M}}\left({K}\right)$ if and only if
$K^{\prime}=K_{\theta}$ for some MLE $\theta$ for $K$. We see that chain-min
can be equivalently stated as follows: for all tournament $K$ there exists an
MLE $\theta$ such that
$\varphi(K)=({\leqslant^{\mathcal{A}}_{K_{\theta}}},{\leqslant^{\mathcal{B}}_{K_{\theta}}})$.
But by section A.2 we have $a\leqslant^{\mathcal{A}}_{K_{\theta}}a^{\prime}$
iff $x_{a}\leq x_{a^{\prime}}$ and
$b\leqslant^{\mathcal{B}}_{K_{\theta}}b^{\prime}$ iff $y_{b}\leq
y_{b^{\prime}}$ (where $\theta=\langle{\bm{x},\bm{y}}\rangle$). The above
reformulation of chain-min now coincides with the definition of a maximum
likelihood operator, and we are done. ∎

###  A.4. Proof of Section 4.2

###### Proof.

We take each axiom in turn. Let $\varphi$ be any operator satisfying chain-
min.

anon: Consider $K=\left[\begin{smallmatrix}1&0\\\
0&1\end{smallmatrix}\right]$, and define permutations $\sigma=\pi=(1\ 2)$,
i.e. the permutations which simply swap 1 and 2. It is easily seen that
$\pi(\sigma(K))=K$. Supposing $\varphi$ satisfied anon, we would get
$1\preceq_{K}^{\varphi}2$ iff
$\sigma(1)\preceq_{\pi(\sigma(K))}^{\varphi}\sigma(2)$ iff
$2\preceq_{K}^{\varphi}1$, which implies $1\approx_{K}^{\varphi}2$. On the
other hand, we have

$\operatorname{\mathcal{M}}\left({K}\right)=\left\\{\left[\begin{smallmatrix}1&\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{1}\\\
0&1\end{smallmatrix}\right],\left[\begin{smallmatrix}1&0\\\
\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{1}&1\end{smallmatrix}\right],\left[\begin{smallmatrix}1&0\\\
0&\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{0}\end{smallmatrix}\right],\left[\begin{smallmatrix}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{0}&0\\\
0&1\end{smallmatrix}\right]\right\\}$

Since $\varphi$ satisfies chain-min and $1,2\in A$ rank equally in
${\preceq_{K}^{\varphi}}$, there must be
$K^{\prime}\in\operatorname{\mathcal{M}}\left({K}\right)$ such that 1 and 2
rank equally in ${\leqslant^{\mathcal{A}}_{K^{\prime}}}$, i.e.
$K^{\prime}(1)=K^{\prime}(2)$. But clearly there is no such $K^{\prime}$; all
tournaments in $\operatorname{\mathcal{M}}\left({K}\right)$ have distinct
first and second rows. Hence $\varphi$ cannot satisfy anon.

IIM: Suppose $\varphi$ satisfies chain-min and IIM. Write

$K_{1}=\left[\begin{smallmatrix}1&0&0\\\ 0&1&0\\\
0&1&1\end{smallmatrix}\right],\quad K_{2}=\left[\begin{smallmatrix}1&0&0\\\
0&1&0\\\ 1&0&1\end{smallmatrix}\right]$

Note that the first and second rows of $K_{1}$ and $K_{2}$ are identical, so
by IIM we have $1\preceq_{K_{1}}^{\varphi}2$ iff
$1\preceq_{K_{2}}^{\varphi}2$. Both tournaments have a unique closest chain
tournament requiring changes to only a single entry:

$\operatorname{\mathcal{M}}\left({K_{1}}\right)=\left\\{\left[\begin{smallmatrix}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{0}&0&0\\\
0&1&0\\\
0&1&1\end{smallmatrix}\right]\right\\},\quad\operatorname{\mathcal{M}}\left({K_{2}}\right)=\left\\{\left[\begin{smallmatrix}1&0&0\\\
0&\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{0}&0\\\
1&0&1\end{smallmatrix}\right]\right\\}$

Write ${K_{1}}^{\prime}$ and ${K_{2}}^{\prime}$ for these nearest chain
tournaments respectively. By chain-min, we must have
$\varphi(K_{i})=({\leqslant^{\mathcal{A}}_{{K_{i}}^{\prime}}},{\leqslant^{\mathcal{B}}_{{K_{i}}^{\prime}}})$.
In particular, $1\prec_{K_{1}}^{\varphi}2$ and $2\prec_{K_{2}}^{\varphi}1$.
But this contradicts IIM, and we are done.

pos-resp: Suppose $\varphi$ satisfies chain-min and pos-resp, and consider

$K=\left[\begin{smallmatrix}1&1&1\\\ 1&1&0\\\ 0&0&1\\\
0&0&1\end{smallmatrix}\right]$

$K$ has a unique closest chain tournament $K^{\prime}$:

$\operatorname{\mathcal{M}}\left({K}\right)=\\{K^{\prime}\\}=\left\\{\left[\begin{smallmatrix}1&1&1\\\
1&1&\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{1}\\\
0&0&1\\\ 0&0&1\end{smallmatrix}\right]\right\\}$

chain-min therefore implies
$\varphi(K)=({\leqslant^{\mathcal{A}}_{K^{\prime}}},{\leqslant^{\mathcal{B}}_{K^{\prime}}})$.
Note that $K^{\prime}(1)=K^{\prime}(2)$, so we have $1\approx_{K}^{\varphi}2$.
In particular, $1\preceq_{K}^{\varphi}2$. Since $K_{23}=0$, we may apply pos-
resp to get $1\prec_{K+\bm{1}_{23}}^{\varphi}2$. But $K+\bm{1}_{23}$ is just
$K^{\prime}$. Since the chain property already holds for $K^{\prime}$, we have
$\operatorname{\mathcal{M}}\left({K^{\prime}}\right)=\\{K^{\prime}\\}$ and
consequently

$\varphi(K+\bm{1}_{23})=\varphi(K^{\prime})=({\leqslant^{\mathcal{A}}_{K^{\prime}}},{\leqslant^{\mathcal{B}}_{K^{\prime}}})=\varphi(K)$

so in fact $1\approx_{K+\bm{1}_{23}}^{\varphi}2$, contradicting pos-resp. ∎

###  A.5. Proof of Section 4.2

For ease of presentation we establish the compatibility of chain-min with dual
and mon separately.

###### Proposition

There exists an operator $\varphi$ satisfying chain-min and dual.

###### Proposition

There exists an operator $\varphi$ satisfying chain-min and mon.

It is clear that these two propositions will together prove Section 4.2. For
Section A.5 we use the following result.

###### Lemma

Let $K$ be a tournament. Then

  1. (1)

${\leqslant^{\mathcal{B}}_{K}}={\leqslant^{\mathcal{A}}_{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}}$

  2. (2)

$K^{\prime}\in\operatorname{\mathcal{M}}\left({K}\right)$ if and only if
${{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\textstyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\scriptstyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K^{\prime}}$}}}}\in\operatorname{\mathcal{M}}\left({{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}\right)$

###### Proof.

Fix an $m\times n$ tournament $K$.

(1) Note that for any $b\in B$, we have
$K^{-1}(b)=A\setminus{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}(b)$.
Indeed, for any $a\in
A=A_{K}=B_{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}$,

$\displaystyle a\in K^{-1}(b)$ $\displaystyle\iff K_{ab}=1$ $\displaystyle\iff
1-K_{ab}=0$
$\displaystyle\iff{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}_{ba}=0$
$\displaystyle\iff
a\notin{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}(b)$

This means that for any $b,b^{\prime}\in B$,

$\displaystyle b\leqslant^{\mathcal{B}}_{K}b^{\prime}$ $\displaystyle\iff
K^{-1}(b)\supseteq K^{-1}(b^{\prime})$ $\displaystyle\iff
A\setminus{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}(b)\supseteq
A\setminus{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}(b^{\prime})$
$\displaystyle\iff{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}(b)\subseteq{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}(b^{\prime})$
$\displaystyle\iff
b\leqslant^{\mathcal{A}}_{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}b^{\prime}$

so
${\leqslant^{\mathcal{B}}_{K}}={\leqslant^{\mathcal{A}}_{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}}$.

(2) (⇒) Suppose $K^{\prime}\in\operatorname{\mathcal{M}}\left({K}\right)$.
First we show that $\textstyle\overline{K^{\prime}}$ has the chain property.
It is sufficient to show that ${\leqslant^{\mathcal{B}}_{K^{\prime}}}$ is a
total preorder,202020 Note that we claim this holds for any $K^{\prime}$ with
the chain property in the body of the paper, but this has not yet been proven.
since part (1) then implies
${\leqslant^{\mathcal{A}}_{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\textstyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\scriptstyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K^{\prime}}$}}}}}}$
is a total preorder and $\textstyle\overline{K^{\prime}}$ has the chain
property by definition.

Since ${\leqslant^{\mathcal{B}}_{K^{\prime}}}$ always has reflexivity and
transitivity, we only need to show the totality property. Let $b,b^{\prime}\in
B$ and suppose $b\not\leqslant^{\mathcal{B}}_{K^{\prime}}b^{\prime}$. We must
show $b^{\prime}\leqslant^{\mathcal{B}}_{K^{\prime}}b$, i.e.
$(K^{\prime})^{-1}(b^{\prime})\supseteq(K^{\prime})^{-1}(b)$. To that end, let
$a\in(K^{\prime})^{-1}(b)$.

Since $(K^{\prime})^{-1}(b)\not\supseteq(K^{\prime})^{-1}(b^{\prime})$, there
is some $\hat{a}\in(K^{\prime})^{-1}(b^{\prime})$ with
$\hat{a}\notin(K^{\prime})^{-1}(b)$. That is, $b^{\prime}\in
K^{\prime}(\hat{a})$ but $b\notin K^{\prime}(\hat{a})$. Since $b\in
K^{\prime}(a)$, we have $K^{\prime}(a)\not\subseteq K^{\prime}(\hat{a})$. By
the chain property for $K^{\prime}$, we get $K^{\prime}(\hat{a})\subset
K^{\prime}(a)$. Finally, this means $b^{\prime}\in
K^{\prime}(\hat{a})\subseteq K^{\prime}(a)$, i.e
$a\in(K^{\prime})^{-1}(b^{\prime})$. This shows
$b^{\prime}\leqslant^{\mathcal{B}}_{K^{\prime}}b$ as required.

It remains to show that
$d({{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}},{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\textstyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\scriptstyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K^{\prime}}$}}}})$
is minimal. Since every tournament is the dual of its dual, any $n\times m$
chain tournament is of the form $\textstyle\overline{K^{\prime\prime}}$ for an
$m\times n$ tournament $K^{\prime\prime}$. The above argument shows that the
chain property is preserved by taking the dual, so that $K^{\prime\prime}$ has
the chain property also. Since
$K^{\prime}\in\operatorname{\mathcal{M}}\left({K}\right)$, we have
$d(K,K^{\prime\prime})\geq d(K,K^{\prime})$. It is easily verified that the
Hamming distance is also preserved under duals, so

$d({{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}},{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\textstyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\scriptstyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K^{\prime}}$}}}})=d(K,K^{\prime})\leq
d(K,K^{\prime\prime})=d({{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}},{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K^{\prime\prime}}$}}{\leavevmode\hbox{$\textstyle\overline{K^{\prime\prime}}$}}{\leavevmode\hbox{$\scriptstyle\overline{K^{\prime\prime}}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K^{\prime\prime}}$}}}})$

We have shown that $\textstyle\overline{K^{\prime}}$ is as close to
$\textstyle\overline{K}$ as any other $n\times m$ tournament with the chain
property, which shows
${{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\textstyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\scriptstyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K^{\prime}}$}}}}\in\operatorname{\mathcal{M}}\left({{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}\right)$
as required.

(⇐) Suppose
${{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\textstyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\scriptstyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K^{\prime}}$}}}}\in\operatorname{\mathcal{M}}\left({{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}\right)$.
By the ‘only if’ statement above, we have
${{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\textstyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\scriptstyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K^{\prime}}$}}}}}$}}{\leavevmode\hbox{$\textstyle\overline{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\textstyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\scriptstyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K^{\prime}}$}}}}}$}}{\leavevmode\hbox{$\scriptstyle\overline{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\textstyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\scriptstyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K^{\prime}}$}}}}}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\textstyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\scriptstyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K^{\prime}}$}}}}}$}}}}\in\operatorname{\mathcal{M}}\left({{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}$}}{\leavevmode\hbox{$\textstyle\overline{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}$}}{\leavevmode\hbox{$\scriptstyle\overline{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}$}}}}}\right)$.
But
${{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}$}}{\leavevmode\hbox{$\textstyle\overline{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}$}}{\leavevmode\hbox{$\scriptstyle\overline{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}$}}}}=K$
and
${{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\textstyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\scriptstyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K^{\prime}}$}}}}}$}}{\leavevmode\hbox{$\textstyle\overline{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\textstyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\scriptstyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K^{\prime}}$}}}}}$}}{\leavevmode\hbox{$\scriptstyle\overline{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\textstyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\scriptstyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K^{\prime}}$}}}}}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\textstyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\scriptstyle\overline{K^{\prime}}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K^{\prime}}$}}}}}$}}}}=K^{\prime}$,
so $K^{\prime}\in\operatorname{\mathcal{M}}\left({K}\right)$ as required. ∎

###### Proof of Section A.5.

Let $\varphi$ be an arbitrary operator satisfying chain-min. Then there is a
function $\alpha:\mathcal{K}\to\mathcal{K}$ such that
$\varphi(K)=({\leqslant^{\mathcal{A}}_{\alpha(K)}},{\leqslant^{\mathcal{B}}_{\alpha(K)}})$
and $\alpha(K)\in\operatorname{\mathcal{M}}\left({K}\right)$ for all
tournaments $K$. We will construct a new function $\alpha^{\prime}$, based on
$\alpha$, such that
$\alpha^{\prime}({{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}})={{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{\alpha^{\prime}(K)}$}}{\leavevmode\hbox{$\textstyle\overline{\alpha^{\prime}(K)}$}}{\leavevmode\hbox{$\scriptstyle\overline{\alpha^{\prime}(K)}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{\alpha^{\prime}(K)}$}}}}$.

Let $\ll$ be a total order on the set of all tournaments $\mathcal{K}$.212121
Note that $\mathcal{K}$ is countable, so such an order can be easily
constructed. Alternatively, one could use the axiom of choice and appeal to
the well-ordering theorem to obtain $\ll$.  Write

$T=\\{K\in\mathcal{K}\mid
K\ll{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}\\}$

Note that since
$K\neq{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}$
for all $K$, exactly one of $K$ and $\textstyle\overline{K}$ lies in $T$.
Informally, we view the tournaments in $T$ as somehow ‘canonical’, and those
in $\mathcal{K}\setminus T$ as the dual of a canonical tournament. We use this
notion to define $\alpha^{\prime}$:

$\alpha^{\prime}(K)=\begin{cases}\alpha(K),&K\in T\\\
{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{\alpha({{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}})}$}}{\leavevmode\hbox{$\textstyle\overline{\alpha({{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}})}$}}{\leavevmode\hbox{$\scriptstyle\overline{\alpha({{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}})}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{\alpha({{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}})}$}}}},&K\notin
T\end{cases}$

First we claim
$\alpha^{\prime}(K)\in\operatorname{\mathcal{M}}\left({K}\right)$ for all $K$.
Indeed, if $K\in T$ then
$\alpha^{\prime}(K)=\alpha(K)\in\operatorname{\mathcal{M}}\left({K}\right)$ by
the assumption on $\alpha$. Otherwise,
$\alpha({{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}})\in\operatorname{\mathcal{M}}\left({{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}\right)$,
so Section A.5 part (2) implies
$\alpha^{\prime}(K)={{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{\alpha({{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}})}$}}{\leavevmode\hbox{$\textstyle\overline{\alpha({{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}})}$}}{\leavevmode\hbox{$\scriptstyle\overline{\alpha({{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}})}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{\alpha({{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}})}$}}}}\in\operatorname{\mathcal{M}}\left({{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}$}}{\leavevmode\hbox{$\textstyle\overline{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}$}}{\leavevmode\hbox{$\scriptstyle\overline{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}$}}}}}\right)=\operatorname{\mathcal{M}}\left({K}\right)$.

Next we show
${{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{\alpha^{\prime}(K)}$}}{\leavevmode\hbox{$\textstyle\overline{\alpha^{\prime}(K)}$}}{\leavevmode\hbox{$\scriptstyle\overline{\alpha^{\prime}(K)}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{\alpha^{\prime}(K)}$}}}}=\alpha^{\prime}({{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}})$.
First suppose $K\in T$. Then $\alpha^{\prime}(K)=\alpha(K)$ and
${{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}\notin
T$, so
$\alpha^{\prime}({{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}})={{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{\alpha({{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}$}}{\leavevmode\hbox{$\textstyle\overline{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}$}}{\leavevmode\hbox{$\scriptstyle\overline{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}$}}}})}$}}{\leavevmode\hbox{$\textstyle\overline{\alpha({{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}$}}{\leavevmode\hbox{$\textstyle\overline{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}$}}{\leavevmode\hbox{$\scriptstyle\overline{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}$}}}})}$}}{\leavevmode\hbox{$\scriptstyle\overline{\alpha({{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}$}}{\leavevmode\hbox{$\textstyle\overline{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}$}}{\leavevmode\hbox{$\scriptstyle\overline{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}$}}}})}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{\alpha({{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}$}}{\leavevmode\hbox{$\textstyle\overline{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}$}}{\leavevmode\hbox{$\scriptstyle\overline{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}$}}}})}$}}}}={{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{\alpha(K)}$}}{\leavevmode\hbox{$\textstyle\overline{\alpha(K)}$}}{\leavevmode\hbox{$\scriptstyle\overline{\alpha(K)}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{\alpha(K)}$}}}}={{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{\alpha^{\prime}(K)}$}}{\leavevmode\hbox{$\textstyle\overline{\alpha^{\prime}(K)}$}}{\leavevmode\hbox{$\scriptstyle\overline{\alpha^{\prime}(K)}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{\alpha^{\prime}(K)}$}}}}$
as required. Similarly, if $K\notin T$ then
${{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}\in
T$, so
$\alpha^{\prime}({{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}})=\alpha({{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}})$,
and
$\alpha^{\prime}(K)={{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{\alpha({{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}})}$}}{\leavevmode\hbox{$\textstyle\overline{\alpha({{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}})}$}}{\leavevmode\hbox{$\scriptstyle\overline{\alpha({{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}})}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{\alpha({{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}})}$}}}}={{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{\alpha^{\prime}({{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}})}$}}{\leavevmode\hbox{$\textstyle\overline{\alpha^{\prime}({{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}})}$}}{\leavevmode\hbox{$\scriptstyle\overline{\alpha^{\prime}({{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}})}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{\alpha^{\prime}({{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}})}$}}}}$.
Taking the dual of both sides, we get
${{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{\alpha^{\prime}(K)}$}}{\leavevmode\hbox{$\textstyle\overline{\alpha^{\prime}(K)}$}}{\leavevmode\hbox{$\scriptstyle\overline{\alpha^{\prime}(K)}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{\alpha^{\prime}(K)}$}}}}=\alpha^{\prime}({{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}})$.

Finally, define a new operator $\varphi^{\prime}$ by
$\varphi^{\prime}(K)=({\leqslant^{\mathcal{A}}_{\alpha^{\prime}(K)}},{\leqslant^{\mathcal{B}}_{\alpha^{\prime}(K)}})$.
Since $\alpha^{\prime}(K)\in\operatorname{\mathcal{M}}\left({K}\right)$ for
all $K$, $\varphi^{\prime}$ satisfies chain-min. Moreover, using Section A.5
part (1) and the fact that
${{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{\alpha^{\prime}(K)}$}}{\leavevmode\hbox{$\textstyle\overline{\alpha^{\prime}(K)}$}}{\leavevmode\hbox{$\scriptstyle\overline{\alpha^{\prime}(K)}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{\alpha^{\prime}(K)}$}}}}=\alpha^{\prime}({{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}})$,
for any tournament $K$ and $b,b^{\prime}\in B$ we have

$\displaystyle b\sqsubseteq_{K}^{\varphi^{\prime}}b^{\prime}$
$\displaystyle\iff b\leqslant^{\mathcal{B}}_{\alpha^{\prime}(K)}b^{\prime}$
$\displaystyle\iff
b\leqslant^{\mathcal{A}}_{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{\alpha^{\prime}(K)}$}}{\leavevmode\hbox{$\textstyle\overline{\alpha^{\prime}(K)}$}}{\leavevmode\hbox{$\scriptstyle\overline{\alpha^{\prime}(K)}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{\alpha^{\prime}(K)}$}}}}}b^{\prime}$
$\displaystyle\iff
b\leqslant^{\mathcal{A}}_{\alpha^{\prime}({{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}})}b^{\prime}$
$\displaystyle\iff
b\sqsubseteq_{{{\mathchoice{\leavevmode\hbox{$\displaystyle\overline{K}$}}{\leavevmode\hbox{$\textstyle\overline{K}$}}{\leavevmode\hbox{$\scriptstyle\overline{K}$}}{\leavevmode\hbox{$\scriptscriptstyle\overline{K}$}}}}}^{\varphi^{\prime}}b^{\prime}$

which shows $\varphi^{\prime}$ also satisfies dual. ∎

Next we prove Section A.5. We will proceed in three stages. First, Section A.5
shows that if $K(a_{1})\subseteq K(a_{2})$ and
$K^{\prime}\in\operatorname{\mathcal{M}}\left({K}\right)$ is some closest
chain tournament with the reverse inclusion $K^{\prime}(a_{2})\subseteq
K^{\prime}(a_{1})$, then swapping $a_{1}$ and $a_{2}$ in $K^{\prime}$ yields
obtain another closest chain tournament
$K^{\prime\prime}\in\operatorname{\mathcal{M}}\left({K}\right)$. Next, we show
in Section A.5 that by performing successive swaps in this way, we can find
$K^{\prime}\in\operatorname{\mathcal{M}}\left({K}\right)$ such that
$K^{\prime}(a_{1})\subseteq K^{\prime}(a_{2})$ whenever $K(a_{1})\subset
K(a_{2})$ (note the strict inclusion). Finally, we modify this $K^{\prime}$ in
Section A.5 to additionally satisfy $K^{\prime}(a_{1})=K^{\prime}(a_{2})$
whenever $K(a_{1})=K(a_{2})$. This shows that there always exist an element of
$\operatorname{\mathcal{M}}\left({K}\right)$ extending the neighbourhood-
subset relation $\leqslant^{\mathcal{A}}_{K}$, and consequently it is possible
to satisfy chain-min and mon simultaneously.

######  Definition .

Let $K$ be a tournament and $a_{1},a_{2}\in A$. We denote by
$\mathsf{swap}({K};{a_{1}},{a_{2}})$ the tournament obtained by swapping the
$a_{1}$ and $a_{2}$-th rows of $K$, i.e.

$[\mathsf{swap}({K};{a_{1}},{a_{2}})]_{ab}=\begin{cases}K_{a_{1},b},&a=a_{2}\\\
K_{a_{2},b},&a=a_{1}\\\ K_{a,b},&a\notin\\{a_{1},a_{2}\\}\end{cases}$

###### Lemma

Suppose $K(a_{1})\subseteq K(a_{2})$ and
$K^{\prime}\in\operatorname{\mathcal{M}}\left({K}\right)$ is such that
$K^{\prime}(a_{2})\subseteq K^{\prime}(a_{1})$. Then
$\mathsf{swap}({K^{\prime}};{a_{1}},{a_{2}})\in\operatorname{\mathcal{M}}\left({K}\right)$.

$X$$Y$$X^{\prime}$$Y^{\prime}$ (a) $X\mathrel{\triangle}(X^{\prime}\cup
Y^{\prime})$

$X$$Y$$X^{\prime}$$Y^{\prime}$ (b) $(X\cup Y)\mathrel{\triangle}X^{\prime}$

$X$$Y$$X^{\prime}$$Y^{\prime}$ (c) $X\mathrel{\triangle}X^{\prime}$

$X$$Y$$X^{\prime}$$Y^{\prime}$ (d) $(X\cup
Y)\mathrel{\triangle}(X^{\prime}\cup Y^{\prime})$ Figure 2. Depictions of the
sets in Equation 7

Depictions of the sets in Equation 7

###### Proof.

Write $K^{\prime\prime}=\mathsf{swap}({K^{\prime}};{a_{1}},{a_{2}})$. It is
clear that $K^{\prime\prime}$ has the chain property since $K^{\prime}$ does.
Since $K^{\prime}\in\operatorname{\mathcal{M}}\left({K}\right)$, we have
$d(K,K^{\prime\prime})\geq d(K,K^{\prime})$. We will show that
$d(K,K^{\prime\prime})\leq d(K,K^{\prime})$ also, which implies
$d(K,K^{\prime\prime})=d(K,K^{\prime})=m({K})$ and thus
$K^{\prime\prime}\in\operatorname{\mathcal{M}}\left({K}\right)$.

To that end, observe that for any tournament $\hat{K}$,

$d(K,\hat{K})=\sum_{a\in A}{|K(a)\mathrel{\triangle}\hat{K}(a)|}$

Noting that $K^{\prime}(a)=K^{\prime\prime}(a)$ for $a\notin\\{a_{1},a_{2}\\}$
and $K^{\prime\prime}(a_{1})=K^{\prime}(a_{2})$,
$K^{\prime\prime}(a_{2})=K^{\prime}(a_{1})$, we have

$\displaystyle d(K,K^{\prime})-d(K,K^{\prime\prime})$
$\displaystyle=\sum_{i\in\\{1,2\\}}{\left(|K(a_{i})\mathrel{\triangle}K^{\prime}(a_{i})|-|K(a_{i})\mathrel{\triangle}K^{\prime\prime}(a_{i})|\right)}$
$\displaystyle=|K(a_{1})\mathrel{\triangle}K^{\prime}(a_{1})|-|K(a_{1})\mathrel{\triangle}K^{\prime}(a_{2})|$
$\displaystyle\quad+|K(a_{2})\mathrel{\triangle}K^{\prime}(a_{2})|-|K(a_{2})\mathrel{\triangle}K^{\prime}(a_{1})|$

To simplify notation, write $X=K(a_{1})$, $X^{\prime}=K^{\prime}(a_{2})$,
$Y=K(a_{2})\setminus K(a_{1})$ and $Y^{\prime}=K^{\prime}(a_{1})\setminus
K^{\prime}(a_{2})$ so that

$\displaystyle K(a_{1})=X;$ $\displaystyle\quad\quad K(a_{2})=X\cup Y$
$\displaystyle K^{\prime}(a_{1})=X^{\prime}\cup Y^{\prime};$
$\displaystyle\quad\quad K^{\prime}(a_{2})=X^{\prime}$

and $X\cap Y=X^{\prime}\cap Y^{\prime}=\emptyset$. Rewriting the above we have

$\displaystyle d(K,K^{\prime})-d(K,K^{\prime\prime})$
$\displaystyle=|K(a_{1})\mathrel{\triangle}K^{\prime}(a_{1})|+|K(a_{2})\mathrel{\triangle}K^{\prime}(a_{2})|$
$\displaystyle\quad-|K(a_{1})\mathrel{\triangle}K^{\prime}(a_{2})|-|K(a_{2})\mathrel{\triangle}K^{\prime}(a_{1})|$
$\displaystyle=|X\mathrel{\triangle}(X^{\prime}\cup Y^{\prime})|+|(X\cup
Y)\mathrel{\triangle}X^{\prime}|$
$\displaystyle\quad-|X\mathrel{\triangle}X^{\prime}|-|(X\cup
Y)\mathrel{\triangle}(X^{\prime}\cup Y^{\prime})|$ (7)

Each of the symmetric differences in eq. 7 are depicted in Figure 2d. Note
that each of these sets can be expressed as a union of the 8 disjoint subsets
of $X\cup Y\cup X^{\prime}\cup Y^{\prime}$ shown in the figure. Expanding the
symmetric differences in eq. 7 and consulting Figure 2d, it can be seen that
most terms cancel out, and in fact we are left with

$d(K,K^{\prime})-d(K,K^{\prime\prime})=2|Y\cap Y^{\prime}|\geq 0$

This shows that $d(K,K^{\prime\prime})\leq d(K,K^{\prime})$, and the proof is
complete. ∎

######  Notation.

For a relation $R$ on a set $X$ and $x\in X$, write

$U(x,R)=\\{y\in X\mid x\mathrel{R}y\\}$ $L(x,R)=\\{y\in X\mid
y\mathrel{R}x\\}$

for the upper- and lower-sets of $x$ respectively.

###### Lemma

For any tournament $K$ there is
$K^{\prime}\in\operatorname{\mathcal{M}}\left({K}\right)$ such that for all
$a\in A$:

$U(a,{<^{\mathcal{A}}_{K}})\subseteq
U(a,{\leqslant^{\mathcal{A}}_{K^{\prime}}})$

That is, $K(a)\subset K(a^{\prime})$ implies $K^{\prime}(a)\subseteq
K^{\prime}(a^{\prime})$ for all $a,a^{\prime}\in A$.

###### Proof.

Write $A=\\{a_{1},\ldots,a_{m}\\}$, ordered such that
$|L(a_{1},{\leqslant^{\mathcal{A}}_{K}})|\leq\cdots\leq|L(a_{m},{\leqslant^{\mathcal{A}}_{K}})|$.
We will show by induction that for each $0\leq i\leq m$ there is
$K_{i}\in\operatorname{\mathcal{M}}\left({K}\right)$ such that:

$1\leq j\leq i\implies U(a_{j},{<^{\mathcal{A}}_{K}})\subseteq
U(a_{j},{\leqslant^{\mathcal{A}}_{K_{i}}})$

The result follows by taking $K^{\prime}=K_{m}$.

The case $i=0$ is vacuously true, and we may take $K_{0}$ to be an arbitrary
member of $\operatorname{\mathcal{M}}\left({K}\right)$. For the inductive
step, suppose A.5 holds for some $0\leq i<m$. If
$U(a_{i+1},{<^{\mathcal{A}}_{K}})=\emptyset$ then we may set $K_{i+1}=K_{i}$,
so assume that $U(a_{i+1},{<^{\mathcal{A}}_{K}})$ is non-empty. Take some
$\hat{a}\in\min(U(a_{i+1},{<^{\mathcal{A}}_{K}}),{\leqslant^{\mathcal{A}}_{K_{i}}})$.
Then $\hat{a}$ has (one of) the smallest neighbourhoods in $K_{i}$ amongst
those in $A$ with a strictly larger neighbourhood than $a_{i+1}$ in $K$.