Chain graph paper¶

Symmetry¶

Notation. For a matrix \(K\) and permutations \(\sigma: A \to A\), \(\pi: B \to B\), let \(\sigma(K)\) and \(\pi(B)\) denote the matrices obtained by permuting the rows and columns of \(K\) by \(\sigma\) and \(\pi\) respectively:

• sym: Fix a tournament \(K\) and let \(\sigma:A \to A\) and \(\pi:B \to B\) be permutations. Write \(K' = \pi(\sigma(K))\). Then \(a \ale_K^\phi a' \iff \sigma(a) \ale_{K'}^\phi \sigma(a')\)

• dual: \(b \ble_K^\phi b'\) iff \(b \ale_\dual{K}^\phi b'\)

• inv-rev: \(a \ale_K^\phi a'\) iff \(a' \ale_{\mathbf{1} - K}^\phi a\)

Remarks.

• dual implies that \(a \ale_K^\phi a'\) iff \(a \ble_\dual{K}^\phi a'\). This means an operator can be defined by specifying the ranking for only one of \(A\) or \(B\), and defining the other ranking by duality.

• sym, dual and inv-rev each represent a kind of symmetry. sym says that players should be treated symmetrically: the ‘names’ of the players (in \(A\)) should not matter. dual says that the two sides \(A\) and \(B\) should be treated symmetrically: the choice of which side is \(A\) and which side is \(B\) should not matter. Finally, inv-rev says that wins and losses are treated symmetrically.

  In fact, dual and inv-rev are related to each other and the following property:

  • transpose: \(a \ale_K^\phi a'\) iff \(a' \ble_{K^\tr}^\phi a\)

  It is easily verified that any two of dual, inv-rev and transpose imply the third. However, neither of dual or inv-rev implies the other. 3

Chain-related properties¶

Notation. Let \(\phi_\text{count}\) be the ‘counting’ operator given by the rating vectors \(r_{\phi_\text{count}}(K) = K\mathbf{e}\), \(s_{\phi_\text{count}}(K) = \dual{K}\mathbf{e}\), where \(e\) is the vector consisting entirely of ones (in \(\R^{|A|}\) in the first case and \(\R^{|B|}\) in the second).

• chain-def: \(\phi(K)\) is chain-definable

• chain-min: \(\phi(K)\) is chain-definable by some \(\hat{K} \in \minch{K}\)

• k-chain: if \(K\) has the chain property then \(\phi(K) = ({\anle_K}, {\bnle_K})\)

• count-chain: If \(\phi_\text{count}(K)\) is chain definable then \(\phi(K) = \phi_\text{count}(K)\)

Remarks.

• k-chain is equivalent to saying that \(\phi(K) = \phi_\text{count}(K)\) whenever \(K\) has the chain property.

• Clearly chain-min implies chain-def and k-chain.

Standard ranking properties¶

• mon: If \(K(a) \subseteq K(a')\) then \(a \ale_K^\phi a'\).

• pos-resp: Suppose \(a \ale_K^\phi a'\) and \(K_{a',b} = 0\) for some \(b \in B\). Then \(a \alt_{K + \mathbf{1}_{a', b}}^\phi a'\), where \(\mathbf{1}_{a', b}\) is the matrix with a 1 in entry \((a', b)\) and zeros elsewhere.

• IIM (Independence of Irrelevant Matches): If \(K_1, K_2\) are tournaments of the same size with identical \(a\)-th and \(a'\)-th rows, \(a \ale_{K_1}^\phi a'\) iff \(a \ale_{K_2}^\phi a'\).

• extension: Let us say that a vector \(v \in \{0,1\}^m\) is compatible with a total preorder \(\le\) on \([m]\) if for all \(a \in [m]\) we have \(v_a = 0\) whenever there is \(a'\) with \(a < a'\) and \(v_{a'} = 0\). Also, for an \(m \times n\) tournament \(K\), let \([K \mid v]\) denote the \(m \times (n+1)\) matrix obtained by extending \(K\) to add \(v\) as the final column.

  Then whenever \(v\) is compatible with \({\ale_K^\phi}\) we have

  \[a \ale_{[K \mid v]}^\phi a' \iff a \ale_K^\phi a' \text{ and } v_a \le v_{a'}\]

Remarks.

• mon just says that \(\ale_K^\phi\) extends the (in general, partial) preorder \(\anle_K\). Together with dual, the following ‘strict’ version of mon implies k-chain:

  • strict-mon: \(K(a) \subset K(a')\) implies \(a \alt_K^\phi a'\)

  Also note that sym and pos-resp imply strict-mon.

• pos-resp and IIM are adaptations of classic axioms from [Rub80]. Note that these properties – as well as sym and mon – are presented only in terms of the \(A\) ranking; the corresponding properties for \(B\) are implied in combination with dual.

• 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 \ale_K^\phi a'\), then pos-resp implies \(a \alt_{K - \mathbf{1}_{ab}}^\phi a'\).

• sym, dual, IIM and pos-resp uniquely characterise \(\phi_\text{count}\) (see here and [Rub80]). These properties without pos-rep characterise the wider class of ‘cardinality’ based operators.

• extension is inspired by postulates for iterated belief revision [DP97]. It says that whenever \(v\) is compatible with an existing ranking \({\ale_K^\phi}\) (in the sense that any element of \(A\) ranked strictly higher than \(a\) must perform at least as well as \(a\) in \(v\)), the ranking for \([K \mid v]\) is a refinement of the ranking for \(K\), obtained by splitting the ranks of \({\ale_K^\phi}\) according to \(v\). This is made clearer by writing the condition \((a \ale_K^\phi a' \text{ and } v_a \le v_{a'})\) in the equivalent form

  \[a \alt_K^\phi a' \text{ or } ( a \aeq_K^\phi a' \text{ and } v_a \le v_{a'} )\]

  Note also that if \(v\) is constant then it is compatible with any total preorder. In particular, extension implies that we can add (or remove) a final column full of 1s or 0s without affecting the \(A\)-ranking.

  Finally, note that if we have sym as well, \(v\) can be added to \(K\) in any position, not just as the final column.

Coherence-like properties¶

• win-coherence: Suppose there is an injective function \(f: K(a) \to K(a')\) such that \(b \ble_K^\phi f(b)\) for all \(b \in K(a)\). Then \(a \ale_K^\phi a'\).

  Moreover, if \(f\) is not surjective or if there is \(b\) with \(b \blt_K^\phi f(b)\), then \(a \alt_K^\phi a'\).

• loss-coherence: Suppose there is an injective function \(g: B \setminus K(a') \to B \setminus K(a)\) such that \(g(b) \ble_K^\phi b\) for all \(b \in B \setminus K(a')\). Then \(a \ale_K^\phi a'\).

  Moreover, if \(g\) is not surjective or if there is \(b\) with \(g(b) \blt_K^\phi b\), then \(a \alt_K^\phi a'\).

• ceteris-paribus: Suppose \(K(a) = N \cup \{b\}\) and \(K(a') = N \cup \{b'\}\), for some \(N \subseteq B \setminus \{b,b'\}\). Then \(a \ale_K^\phi a'\) iff \(b \ble_K^\phi b'\).

Remarks.

• The central idea behind these properties is to ensure there is some connection between the ranking of \(A\) and \(B\), with respect to the tournament \(K\). They are very close to self-consistent monotonicity, a property that has already been extensively studied for partial tournaments [CS99][GonzalezDiazHL14].

• win-coherence says that players in \(A\) should rank highly when beating players in \(B\) which rank highly themselves (i.e. we should reward difficult wins).

• loss-coherence says that players in \(A\) should rank poorly when losing to lowly-ranked players in \(B\) (i.e. we should penalise losses in easy matches).

• The win and loss versions are related by the dual version of inv-rev (which I will call b-inv-rev):

  • (win-coherence and b-inv-rev) iff (loss-coherence and b-inv-rev)

• The ‘win’ and ‘loss’ versions of coherence seem to fit nicely with the ideas behind chain-addition versus chain-deletion. Is there anything we can say about this?

• We reach peak levels of pretentiousness with the ceteris-paribus property, whose name is a Latin phrase meaning “all other things being equal”. It says that if the only difference between \(a\) and \(a'\) is that \(a\) defeats \(b\) whereas \(a'\) defeats \(b'\), then the player defeating the ‘best’ of \(b, b'\) should rank highest.

  This axiom is inspired both in name and in its form by ideas from the problem of social ranking from coalitions [HKMO18][AEMO20].

  Its statement here is similar to win-coherence, in that it focuses on wins rather than losses. It would also be possible to define a loss version.

• ceteris-paribus is strictly weaker than win-coherence.

• Both coherence properties imply mon and strict-mon.

• It may be possible to combine win-coherence and loss-coherence to get a more cautious property that only applies when \(a'\) achieves more difficult wins and \(a\) suffers easier losses.

• The basic counting operator \(\phi_{\text{count}}\) fails to satisfy any of these properties. Indeed, consider

  \[K = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 0 & 1 \end{bmatrix}\]

  Note that \(1 \aeq_K^{\phi_{\text{count}}} 2\) in the \(A\) ranking, and \(2 \blt_K^{\phi_{\text{count}}} 1\) in the \(B\) ranking. win-coherence would imply \(2 \alt_K^{\phi_{\text{count}}} 1\), so \({\phi_{\text{count}}}\) cannot satisfy it. loss-coherence on the other hand implies the reverse ranking \(2 \alt_K^{\phi_{\text{count}}} 1\), so also cannot hold for \({\phi_{\text{count}}}\).

  ceteris-paribus with \(N = \emptyset\) would also imply \(2 \alt_K^{\phi_{\text{count}}} 1\), so does not hold.

• chain-min operators also violate these properties, as will be shown in the section on chain-min operators.

Miscellaneous other properties¶

• improvement: Fix a tournament \(K\) and let \(a, a' \in A\). Let \(\mathbf{e}_a \in \{0,1\}^m\) be the vector with a 1 in the \(a\)-th position and zeros elsewhere. Additionally, write \(K^{(0)} = K\) and \(K^{(t+1)} = [K^{(t)} \mid \mathbf{e}_a]\).

  Then there exists \(t \in \N_0\) such that \(a' \alt_{K^{(t)}}^\phi a\).

• concat: For total preorders \({\le_1}, {\le_2}\) on a set \(X\), let us say that \({\le_1}\) is compatible with \({\le_2}\) if \(x <_1 y\) implies \(x \le_2 y\). 4

  Let \(K_1, K_2\) be \(m \times n_1\) and \(m \times n_2\) tournaments respectively. Then whenever \({\ale_{K_1}^\phi}\) is compatible with \({\ale_{K_2}^\phi}\) we have

  \[a \ale_{[K_1 \mid K_2]}^\phi a' \iff a \ale_{K_1}^\phi a' \text{ and } a \ale_{K_2}^\phi a'\]

Remarks.

• improvement comes from improvement operators in iterated belief revision [KPerez08].

• concat is in a sense a generalisation of extension, which allows for side-by-side concatenation of arbitrary tournaments (provided they have the same number of rows).

Symmetry properties¶

The failure of sym for chain-minimal operators suggests that some kind of tie-breaking rule is required when none of the closest chain tournaments can be distinguished whilst respecting symmetry. One possibility for such a tie-breaking mechanism is to fix a total order \(\trianglelefteq\) on the set of all tournaments \(\K\), and define a choice function \(\alpha\) by \(\alpha(K) = \min(\minch{K}, {\trianglelefteq})\). 5 We give an example.

We move on to look at dual for chain-minimal operators.

Remark. A very similar proof shows that a chain-minimal operator satisfying inv-rev is also possible: we write \(T = \{K \in \K \mid K \vartriangleleft \mathbf{1} - K\}\) and construct \(\alpha\) such that \(\alpha(\mathbf{1} - K) = \mathbf{1} - \alpha(K)\).

Monotonicity properties¶

While not enough to show that there exists a chain-minimal operator satisfying mon, the following results point in that direction.

Proposition 5 shows that we can find a minimal chain tournament with \(\hat{K}(a) \subseteq \hat{K}(a')\) for each pair \((a, a')\) whenever \(K(a) \subseteq K(a')\). To conclude that chain-min and mon can be satisfied simultaneously, we need to be able to find \(\hat{K}\) with this property for all such pairs \((a, a')\) at the same time.

The following shows that this can at least be done for the pairs such that \(K(a) = K(a')\).

Note that \(K(a) = K(a')\) does not imply that \(\hat{K}(a) = \hat{K}(a')\) for all \(\hat{K} \in \minch{K}\). However it does appear that the following might be true: 8

If true, this would imply that every chain minimal operator has the following (weaker) monotonicity property:

• weak-mon: If \(K(a) \subset K(a')\) then \(a \ale_K^\phi a'\).

When combined with Proposition 6, it feels like this might be enough to show that chain-min and mon are compatible.

More can be said about pos-resp.

Remark. The failure of pos-resp can be explained by thinking about the probabilistic model in which chain-min operators arise as maximum likelihood estimates (see here, although that page uses different notation…). For \(K\) from Proposition 7, the most likely reason for failure of the chain property is that \(2 \in A\) lost an ‘easy’ match against \(3 \in B\) ‘by accident’. This means the 0 at position \((2, 3)\) is switched to a 1 to construct the rankings for \(K\) anyway; switching this entry in the input consequently has no affect and we do not see the strict improvement in the ranking of \(2 \in A\) as pos-resp would require.

Remark. The pos-resp failure above was the result of chain addition: we added a 1 to find the nearest chain tournament. The result still holds if we consider only chain deletion operators, though. Indeed, the closest chain tournament to \(\mathbf{1} - K\), considering deletion only, is \(\mathbf{1} - \tilde{K}\), and we have \(1 \aeq 2\) in both tournaments. However, \((\mathbf{1} - \tilde{K}) + \mathbf{1}_{23} = \mathbf{1} - K\), so this contradicts pos-resp by the same argument as above.

The obvious next question is whether chain-minimal operators can satisfy a weaker version of pos-resp:

• nonneg-resp: Suppose \(a \ale_K^\phi a'\) and \(K_{a',b} = 0\) for some \(b \in B\). Then \(a \ale_{K + \mathbf{1}_{a',b}}^\phi a'\).

Let us first note that it is possible for a chain-minimal operator to fail nonneg-resp. Indeed, consider

\(\minch{K}\) contains 8 tournament at a distance of 2 from \(K\). In particular, \(\minch{K}\) contains \(K'\) given by

Suppose \(\phi\) is some chain-minimal operator such that \(\phi(K)\) is chain-definable by \(K'\). Then clearly \(2 \ale_K^\phi 4\) and \(K_{41} = 0\). nonneg-resp would imply that \(2 \ale_{K + \mathbf{1}_{41}}^\phi 4\); however it is easily seen that \(K + \mathbf{1}_{41} = \left[\begin{smallmatrix}0&1&1&1\\1&0&1&0\\0&1&0&0\\1&0&0&0 \end{smallmatrix}\right]\) has a unique closest chain tournament \(K''\):

in which \(K''(2) \supset K''(4)\). Consequently \(4 \alt_{K + \mathbf{1}_{41}}^\phi 2\).

Despite this example, it seems likely that there exists some chain-minimal operator which satisfies nonneg-resp. This remains to be proven.

Independence¶

Extension¶

Remark. Incidentally, parts (1) and (2) tell us that extension implies k-chain in combination with dual and the following (very weak) property, which just says that counting wins is the only sensible ranking when there is only one element of \(B\): 9

• single-b: If \(|B| = 1\) then \(a \ale_K^\phi a'\) iff \(|K(a)| \le |K(a')|\)

We come to the main result of this subsection.

Remark. The above proof takes any chain-minimal operator \(\phi\) and ‘converts’ it to one satisfying extension. But in fact, this level of generality is unnecessary: the chain-minimal operator from example Example 1 already satisfies extension.

Indeed, let \(\alpha(K) = \min(\minch{K}, \trianglelefteq)\) with \({\trianglelefteq}\) defined as before, and let \(\phi\) be the chain-minimal operator corresponding to \(\alpha\). To show extension, suppose \(v\) is compatible with \({\ale_K^\phi} = {\anle_{\alpha(K)}}\). Combining Lemma 3 parts (2) and (3) as in the above proof, we get that \([\alpha(K) \mid v] \in \minch{[K \mid v]}\) and therefore \(\mindist{[K \mid v]} = \mindist{K}\). But this implies that any element of \(\minch{[K \mid v]}\) has \(v\) as its final column: if \([K' \mid v'] \in \minch{[K \mid v]}\) then \(K'\) has the chain property, so \(d(K, K') \ge \mindist{K}\) and

Hence \(v = v'\). Moreover we see that \(d(K, K') = \mindist{K}\), so \(K' \in \minch{K}\). In other words, any element of \(\minch{[K \mid v]}\) is of the form \([K' \mid v]\) for some \(K' \in \minch{K}\).

Finally, recall that \({\trianglelefteq}\) ranks tournaments lexicographically based on their column-by-column vectorisation. This ensures that \([\alpha(K) \mid v] \vartriangleleft [K' \mid v]\) for all \(K' \in \minch{K}\), and therefore \(\alpha([K \mid v]) = [\alpha(K) \mid v]\). The extension property follows from part (1) of the lemma by the same argument as in the proof of Proposition 9. Note that had we instead defined \({\trianglelefteq}\) by the row-by-row vectorisation, extension might not hold.

Coherence properties¶

Remark. The proof above shows that chain-minimal operators fail even the ‘weak’ versions of the coherence properties (which incidentally are satisfied even by \(\phi_{\text{count}}\)!).

Match-preference operators¶

Note: The examples here could probably replace Example 1 if making this document into a paper.

The core idea behind chain-minimal operators is to modify the ‘noisy’ matrix of tournament results \(K\) so that it satisfies the chain property. By using the Hamming distance to find the minimum change required, we have so far given equal weight to changes in any position in the matrix. That is, we assume errors occur in \(K\) with equal probability in any position. This leads to non-uniqueness of the closest chain tournament, as seen in several examples.

In this section we consider a family of chain-min operators which single out a unique chain tournament by removing this equal-weight assumption. Specifically, we assume a total order over the set of matrix indices \(\N \times \N\) (the matches), which indicates the cost associated with changing an entry in \(K\): the lower down \((a, b)\) is in the ranking, the higher the cost for changing \(K_{ab}\).

One possible motivation for such a ranking comes from cases where matches in the tournament 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.

Notation. For a relation \(R\) on a set \(X\) and \(S \subseteq X\), write \(R \rs S = R \cap (S \times S)\) for the restriction of \(R\) to \(S\).

Notation. Write \(K \oplus K' = (K + K') \mod 2\). Note that \(K \oplus K'\) is 1 in exactly the entries where \(K\) and \(K'\) differ.

TODO: think of a better name?

Clearly any match-preference operator satisfies chain-min.

One might be tempted to generalise Definition 8 so that \(\trianglelefteq\) is allowed to depend on \(K\). However, it can be shown that every chain-minimal operator is of this form, and we would therefore no longer be looking at a specific subclass of operators. 11 The idea here is that, given a choice function \(\alpha\) for an arbitrary chain-minimal operator \(\phi\), we can construct a total order \(\trianglelefteq_K\) such that the positions of the zeros in \(K \oplus \alpha(K)\) are minimal, which guarantees that the corresponding (generalised) match-preference operator agrees with \(\phi\) on all inputs. Formally, we have the following proposition.

Match-preference operators can also be viewed as a generalisation of chain-minimal operators where we use a weighted Hamming distance function.

Remark. Clearly the ordinary Hamming distance just corresponds to \(w_{m,n} \equiv 1\) for all \(m, n \in \N\).

Remark. If we abuse notation and consider \(w_{m,n}\) to be a matrix, it holds that \(d_W(K, K') = \v_{\trianglelefteq}(w_{m,n}) \dotprod \v_{\trianglelefteq}(K \oplus K')\) for any total order \(\trianglelefteq\), where \({\dotprod}\) denotes the dot product.

The set \(\minchw{W}{K}\) is a straightforward generalisation of \(\minch{K}\) which uses the weighted distance \(d_W\) to find the closest chain tournaments. Let us say that \(W\) is resolute if \(|\minchw{W}{K}|=1\) for all \(K\). Any resolute weighting \(W\) induces an operator \(\phi_W\) by letting \(\phi_W(K)\) be chain-definable by the unique element of \(\minchw{W}{K}\).

Next we show that any match-preference operator corresponds to a resolute weighting.

A maximum likelihood interpretation¶

In this section we show that chain-minimal operators arise naturally as maximum likelihood estimators in a particular probabilistic model. Throughout the section we fix \(m, n \in \N\) and write \(A = [m]\), \(B = [n]\).

In the maximum likelihood approach we take an epistemic view of tournament ranking: we assume 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\). 14

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 \ge y_b\). Note that condition \((*)\) simply says that \(a'\) can only be strictly more skilful than \(a\) if there is a good reason for it, i.e. if there is some \(b \in B\) which \(a'\) can defeat but \(a\) cannot (condition \((**)\) is analogous for the \(B\)s). These conditions are intuitive – and necessary for technical reasons later – if we assume that skill levels are relative to the sets \(A\) and \(B\) currently under consideration (for example, they do not reflect the abilities of players in future matches against new contenders outside of \(A\) or \(B\)).

TO COMMENT ON: Skill levels need not have the same meaning for the \(A\)s and \(B\)s in bipartite tournaments. E.g. in the educational setting, the ‘skill’ of a question \(b\) might represent its difficulty, and the skill of a student \(a\) would represent the level of the most difficult question they are capable of answering.

Now, the capabilities of players in principle may not align with what is observed in reality. Noise may be 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). 15 The noise model is therefore parametrised by the false positive and false negative rates \(\mathbf{\alpha} = \tuple{\alpha_+, \alpha_-} \in [0,1]^2\), which we assume are the same for all \(a \in A\).

\(P_{\mathbf{\alpha}}(K \mid \theta)\) is the probability of observing the tournament results \(K\) when the false positive and negative rates are given by \(\alpha\) and the true state of the world is \(\theta\). Note that the four cases in \(p_{ab}\) correspond to a false positive, false negative, true positive and true negative respectively.

TODO: Do I have \(\alpha_+\) and \(\alpha_-\) the wrong way around in the last two cases?! Need to fix this here and throughout.

We can now define a maximum likelihood operator.

In order to calculate the maximum likelihood estimates for a given \(K\), consider the tournament \(K_\theta\) associated with each state \(\theta = \tuple{\mathbf{x}, \mathbf{y}}\) given by

Note that \(K_\theta\) is the unique tournament with non-zero probability in \(P_{\tuple{0,0}}(\cdot \mid \theta)\), i.e. when there are no false positive or false negatives.

The maximum likelihood estimates take a particularly simple form if \(\alpha_+ = \alpha_-\), i.e. if false positives and false negatives occur at the same rate.

Proposition 13 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.

TODO:

• Go back through this section and remove dependence on a specific \(m\) and \(n\): have definitions be with respect to some \(m, n\), and an operator has the MLE property iff it gives an \((m,n)\)-MLE ranking for every \(m \times n\) tournament, for any \(m, n \in \N\). Then we can say that the MLE property is equivalent to chain-min.

• Give the other results about chain-addition and chain-deletion

Symmetry and chain rankings¶

Before actually considering relaxations of chain-min, it will be useful to collect some symmetry-related properties of chain tournaments. Indeed, while there is no chain-minimal operator satisfying symmetry, the set of chain tournaments \(\minch{K}\) (and the induced chain-definable rankings) do satisfy the expected symmetry properties.

Notation. For a relation \(R \subseteq X \times X\) and a permutation \(\tau: X \to X\), write \(\tau(R) = \{(\tau(x), \tau(y)) \mid (x, y) \in R\}\).

Note that (3) implies symmetry within \(\minch{K}\) when \(K\) is ‘symmetric’ itself: if there is a (non-trivial) permutation which maps \(K\) onto itself, then \(\minch{K}\) is closed under this permutation. 16

This can account for the non-uniqueness of the closest chain tournament for ‘symmetric’ tournaments (such as \(K\) from the proof of Proposition 3). However, it is not the case that non-uniqueness arises only in this way. For example, consider

There is no non-trivial permutation mapping \(K\) onto itself, and yet \(|\minch{K}| = 8\). 17

Approximating chain rankings¶

The idea of this subsection is the following: instead of requiring an operator \(\phi\) to output rankings corresponding to some closest chain tournament \(K'\), let us instead only require that \(\phi\) minimises the distance from these rankings, with the minimum taken over some set of operators \(\Phi\).

If \(\Phi\) is the set of all operators then there is clearly no restriction, and we arrive back at chain-min. However, limiting \(\Phi\) to the set of symmetric operators, say, allows us to consider symmetric operators which are the ‘closest’ to satisfying chain-min.

To this end, let \(\orderings{X}\) denote the set of total preorders on a set \(X\), and let \(d_{m,n}\) be a distance metric on \(\orderings{[m]} \times \orderings{[n]}\), for each \(m,n \in \N\). We drop the subscripts when no ambiguity arises. 18 We will also assume that \(d\) satisfies the following symmetry properties:

where \(\sigma\) and \(\pi\) are permutations on \([m]\) and \([n]\) respectively.

Note that since \(\minch{K}\) is finite and each \(\phi(K)\) takes one of finitely many values (there are a finite number of rankings of \(A\) and \(B\)), there always exists a chain-optimal operator for any non-empty set \(\Phi\).

Interestingly, we can construct a symmetric operator which is chain optimal for all \(K\), amongst those operators satisfying sym and the ‘dual’ version for the ranking on \(B\): 19

• b-sym: For any permutations \(\sigma: A \to A\) and \(\pi: B \to B\), \(b \ble_K^\phi b' \iff \pi(b) \ble_{\pi(\sigma(K))}^\phi \pi(b')\)

Unfortunately, Proposition 15 is another non-constructive proof which does not help us single out a unique sym-operator. The problem still remains that we need to choose which closest chain tournament \(K'\) we want to approximate with a symmetry-respecting ranking. It would be interesting to see if a chain choice function \(\alpha\) is sufficient for this purpose, i.e. whether we can construct a chain-optimal operator \(\hat{\phi} \in \hat{\Phi}\) as above such that the chain error \(\cherr_{\phi,K}\) is minimised at \(\alpha(K)\), for each \(K\).

Removing symmetry in K¶

Note that sym only places a restriction on the rankings \(\phi(K)\) when \(K\) itself has some kind of symmetry (i.e. there exists a non-trivial permutation mapping \(K\) onto itself). One possibility for ensuring sym, then, is to ‘remove’ this symmetry by merging together \(A\)s and \(B\)s that necessarily rank equally, thus reducing \(K\) to a (smaller) tournament \(\hat{K}\). One could then apply a chain-minimal operator to \(\hat{K}\) and unmerge the rows and columns of \(\hat{K}\) to get a ranking of \(K\).

Some concrete operators¶

This subsection puts forth some concrete proposals for symmetric operators which are somehow inspired by chain-minimality.

Existing operators¶

Write \(\mathcal{B}\) for the set of all anti-diagonal block matrices \(T\) formed from some bipartite tournament \(K\). We consider which ranking methods from [GonzalezDiazHL14] are well-defined on \(\mathcal{B}\), and what the corresponding operators look like in our restricted binary bipartite context.

• Scores. This method reduces to the ‘counting’ operator \(\phi_{\text{count}}\) in our setting.

• Maximum likelihood (also known as the Bradley-Terry model). It appears that the irreducibility assumption is key in the proof of existence and uniqueness of the maximum likelihood estimate [For57], so we cannot guarantee that this ranking method is well-defined on \(\mathcal{B}\).

  There do exist modifications to the Bradley-Terry model which remove the irreducibility requirement, however (e.g. [Yan16]), so following these methods might be an option.

• Neustadtl. Well-defined on \(\mathcal{B}\). In general this method takes into account the number of matches played by each player; since in our case this is more or less constant (\(|B|\) for the elements of \(A\) and \(|A|\) for the elements of \(B\)), the corresponding operator \(\phi_{\text{neu}}\) takes a simplified form, given by the rating vectors \(r_{\phi_{\text{neu}}}(K) = K\dual{K}\mathbf{e}\) and \(s_{\phi_{\text{neu}}}(K) = \dual{K}Ke\). That is,

  \[\begin{aligned} [r_{\phi_{\text{neu}}}(K)]_{a} &= \sum_{b \in K(a)}{ |\dual{K}(b)| } \\ [s_{\phi_{\text{neu}}}(K)]_{b} &= \sum_{a \in \dual{K}(b)}{ |K(a)| } \end{aligned}\]

  The idea here is that when ranking the \(A\)s, for instance, it is better to have defeated those \(b \in B\) who have themselves defeated many players in \(A\).

  It is clear that \(\phi_{\text{neu}}\) satisfies dual.

• Fair bets. This method is not well-defined on all of \(\mathcal{B}\). Most obviously, the Fair bets ranking does not exist when there exists some \(a \in A\) with \(K(a) = B\), or some \(b \in B\) with \(K^{-1}(b) = \emptyset\). These cases are easily resolved by just rankings the relevant \(A\)s and \(B\)s maximally, however, so there is still hope for a version of this method in the bipartite context.

  In [SV05] the authors generalise Fair bets to reducible tournaments using the aforementioned decomposition into maximally irreducible components, but it is possible for the resulting operator to only give partial orders.

• Buchholz. Well-defined on \(\mathcal{B}\). In the full partial tournament setting this method takes into account both the number of victories and the average strength of one’s opponents. However in our case each \(a, a' \in A\) faces exactly the same opponents. This means the ranking reduces to simply counting victories, i.e. \(\phi_{\text{count}}\).

• Recursive Buchholz (also known as Least squares). Again, this method coincides with \(\phi_{\text{count}}\).

• Recursive performance. This method comes from [BVazquezCCDiazRGonzalezDiaz08], wherein the authors remark that it is not well-defined for anti-diagonal block tournaments (see assumption A2 in that paper).

• Generalised row sum. Quite a complicated ranking method, but I think it also collapses to \(\phi_{\text{count}}\) in our setting.

Whilst it is interesting that Buchholz, Recursive Buchholz and Generalised row sum each reduce to \(\phi_{\text{count}}\) in the case of anti-diagonal block matrices, it may be unsurprising given that each method satisfies the following property:

• score-consistency: ([GonzalezDiazHL14]) A ranking method should coincide with the Scores ranking for round-robin tournaments

Here the Scores ranking assigns each player \(i\) their average score \(s_i = \sum_{j}{\frac{T_{ij}}{m_i}}\) where \(m_i = \sum_{j}{(T_{ij} + T_{ji})}\) represents the matches played by player \(i\), and \(T\) is round-robin if \(T_{ij} + T_{ji} = 1\) for all \(i \ne j\).

Now our anti-diagonal block tournaments are not round-robin, but it does hold that \(T_{ij} + T_{ji} = 1\) whenever \(i \le m\) and \(j > m\). Thus there is a sort of ‘round-robinnes’ when considering matches between the \(A\)s and \(B\)s.

1

Indeed, if \(K = \dual{K}\) then \(K_{11} = 1 - K^\tr_{11}\) and \(K_{11} = 1/2\), which is not possible.

2

To borrow the terminology of González-Díaz et. al…

3

For an operator that satisfies dual but not inv-rev, consider \(\phi\) which always outputs the fixed rankings \(1 \alt \cdots \alt m\) and \(1 \blt \cdots \blt n\). For an operator satisfiying inv-rev but not dual, consider \(\phi\) whose output rankings are the same as \(\phi_\text{count}\) but with the \(B\) ranking reversed.

4

Despite the asymmetry in the definition, \({\le_1}\) is compatible with \({\le_2}\) iff \({\le_2}\) is compatible with \({\le_1}\).

5

Note that a full total order on \(\K\) is not necessary here; it would suffice to have a total order \(\trianglelefteq_K\) on \(\minch{K}\) for each \(K\). However, having a concrete example of a total order on \(\K\) will be useful in what follows.

6

Defining \(\v(K)\) as the vectorisation alone would not be injective: consider \(K_1 = \left[\begin{smallmatrix}1 & 1\end{smallmatrix}\right]\) and \(K_2 = \left[\begin{smallmatrix}1 \\ 1\end{smallmatrix}\right]\). This is why we include the size of \(K\) in \(\v(K)\).

7

Note that there are several choices for how vectors of different sizes should be ordered. In this application, however, \(\trianglelefteq\) is only actually used to compare between elements of \(\minch{K}\) which do have the same size, so the choice is irrelevant.

8

I wrote a small test in the Haskell code to try to find counterexamples to the conjecture. It seems there are none for \(|A| \le 4\) and \(|B| \le 3\).

9

A proof sketch: first show that \({\ale_K^\phi} = {\anle_K}\) for all \(K\) with the chain property by induction on \(|B|\). single-b covers the base case \(|B| = 1\), and Lemma 3 parts (1) and (2) together with extension provide the inductive step. Now an appeal to dual and Proposition 2 part (2) shows that \({\ble_K^\phi} = {\bnle_K}\) for all \(K\) with the chain property, so we have shown that \(\phi\) satisfies k-chain.

10

Although note that any tournament with \(|A| = 1\) or \(|B| = 1\) automatically has the chain property, so we must have \(\alpha_\phi(K) = K\) anyway.

11(1,2)

Another possible generalisation is to let \(\trianglelefteq\) depend on the size of \(K\): have a total order \(\trianglelefteq_{m,n}\) for each \(m, n \in \N\). I think this does place a restriction over chain-minimal operators.

12

Here \(\alpha_{\trianglelefteq_K}\) is as defined in Definition 8.

13

Note that we abuse notation by using the symbol \(d_W\) for all the distance functions defined for tournaments of different sizes.

14

For simplicity we use numerical skill levels here, although it would suffice to have a partial preorder on \(A \cup B\) such that each \(a \in A\) is comparable with every \(b \in B\).

15

Note that a false positive for \(a\) is a false negative for \(b\) and vice versa.

16

Specifically, if there are \(\sigma\) and \(\pi\) such that \(\pi(\sigma(K)) = K\) (and at least one permutation is not the identity mapping), then \(\tilde{K} \in \minch{K}\) implies \(\pi(\sigma(\tilde{K})) \in \minch{K}\) also.

17

It may be of minor interest to note that this \(K\) is one of the ‘smallest’ examples of ‘asymmetric’ tournaments with multiple closest chain tournaments. That is, no size smaller than \(3 \times 4\) (or \(4 \times 3\)…) exhibits such examples, and moreover there are no \(3 \times 4\) examples with fewer than 6 ones.

18

It should be clear from context whether \(d\) refers to the distance between pairs of rankings or the Hamming distance between tournaments.

19

Note that b-sym is strictly weaker than the conjunction of sym and dual.

20

I think we also have that \(K \sim K'\) if the bipartite graphs corresponding to \(K\) and \(K'\) are isomorphic.

21

In fact we could instead find the closest non-integer chain tournaments, where \(K\) has the chain property if \({\anle_K}\) is total, with \(a \anle_K a'\) iff \(K_{ab} \le K_{a',b}\) for all \(b \in B\). I think in this case this actually means \(\hat{K}\) has a unique closest chain-tournament \(\left[\begin{smallmatrix}0&1&\frac{1}{2}\\1&{\color{red}1}&1\\0&0&0 \end{smallmatrix}\right]\).

22

Here \(\max(Z, {\le}) = \{z \in Z \mid \not\exists z' \in Z : z < z'\}\), for any set \(Z\) and a total preorder \({\le}\) on \(Z\) (with strict part \({<}\)).

23

We omit a detailed proof of this, which would be similar to the “if” direction of the present proof, where sub-matrix-independence is applied to a sub-matrix \(K^{--}\) of \(K^-\) and so on.

24

An easy example is a tournament in which some \(a \in A\) has \(K(a) = B\); in this case \(a\) has no incoming edge in the graph corresponding to \(T\), so this graph is not strongly connected and thus \(T\) is reducible.

For a non-trivial example which does not have an immediate ‘obvious’ ranking, consider \(\left[\begin{smallmatrix}1&1&0&1\\1&0&1&1\\0&0&0&1 \\1&0&0&0\end{smallmatrix}\right]\).