PhD Notes

Contents:

\[\gdef{\phi}{\varphi} \gdef{\null}{\bot} \gdef{\bnle}{\leqslant^\mathcal{B}} \gdef{\minch}{\mathcal{M}} \gdef{\N}{\mathbb{N}} \gdef{\R}{\mathbb{R}} \gdef{\T}{\mathcal{T}} \gdef{\L}{\mathcal{L}} \gdef{\ext}{\mathcal{E}} \gdef{\games}{G} \gdef{\gamesa}{G^\mathcal{A}} \gdef{\gamesb}{G^\mathcal{B}} \gdef{\chain}{\mathcal{C}} \gdef{\partial}{\mathcal{P}} \gdef{\rankings}{R} \gdef{\ale}{\preceq} \gdef{\alt}{\prec} \gdef{\aeq}{\approx} \gdef{\anle}{\leqslant^\mathcal{A}} \gdef{\aneq}{\approx^\mathcal{A}} \gdef{\anlt}{<^\mathcal{A}} \gdef{\bnle}{\leqslant^\mathcal{B}} \gdef{\ble}{\sqsubseteq} \gdef{\blt}{\sqsubset} \gdef{\beq}{\approx} \gdef{\anlep}{\preccurlyeq^\mathcal{A}} \gdef{\anltp}{\prec^\mathcal{A}} \gdef{\bnlep}{\preccurlyeq^\mathcal{B}} \gdef{\bnltp}{\prec^\mathcal{B}} \gdef{\normal}{\mathsf{Normal}} \gdef{\ranks}{\mathsf{ranks}} \gdef{\rows}{\mathsf{rows}} \gdef{\columns}{\mathsf{columns}} \gdef{\dual}#1{{\overline{#1}}} \gdef{\transp}{\top} \gdef{\one}{\mathbf{1}} \gdef{\zero}{\mathbf{0}}\]

Generalising the chain graph paper

In the AAMAS paper, each player in \(A\) faced each player in \(B\), and match outcomes were decisive. We generalise this framework first to allow match outcomes to take any value in \([0, 1]\) – with values close to 1 representing better outcomes for the player in \(A\), and values close to 0 representing better outcomes for the player in \(B\) – and then to remove the requirement that a match takes place between every pair of players.

Non-binary match outcomes

Definition 1

A tournament is a tuple \((A, B, T)\), where \(A = \{1,\ldots,n\}\) and \(B = \{1,\ldots,m\}\) for some \(n, m \in \N\), and \(T\) is a matrix in \([0,1]^{n \times m}\).

When no ambiguity arises we denote a tournament simply by \(T\), where \(A\) is understood to be the set \(\{1,\ldots,\rows(T)\}\) and \(B\) is \(\{1,\ldots,\columns(T)\}\). Write \(\T_{nm}\) for the set of \(n \times m\) tournaments. A tournament \(T\) with \(T_{ab} \in \{0, 1\}\) for all \(a, b\) will be called a binary tournament.

Chain tournaments

Definition 2

For \(T \in \T_{nm}\), define relations \(\anle_T\) and \(\bnle_T\) on \(A\) and \(B\), respectively, by

\[\begin{aligned} a \anle_T a' &\iff \forall b \in B: T_{ab} \le T_{a'b} \\ b \bnle_T b' &\iff \forall a \in A: T_{ab} \ge T_{ab'} \end{aligned} \]

Note that these relations generalise the neighbourhood-inclusion relations introduced in the AAMAS paper for binary tournaments. Write \(\rankings(T) = ({\anle_T}, {\bnle_T})\) for any tournament \(T\).

Definition 3

\(T\) is a chain tournament if both \(\anle_T\) and \(\bnle_T\) are total preorders.

Write \(\chain_{nm}\) for the set of \(n \times m\) chain tournaments.

Some differences between binary and general chain tournaments are immediate:

  1. \(\anle_T\) being a total preorder does not imply the same for \(\bnle_T\). For example, with

    \[T = \begin{bmatrix} .1 & .2 \\ .4 & .3 \end{bmatrix}\]

    one can easily see that \(\anle_T\) is total (with \(1 \anle_T 2\)) but \(1\) and \(2\) are incomparable wrt \(\bnle_T\).

  2. For any pair of total preorders \(({\ale}, {\ble})\) on \(A\) and \(B\) respectively, there is a chain tournament \(T\) such that \(\rankings(T) = ({\ale}, {\ble})\). 1 This is in contrast to the situation with binary tournaments, where a pair of tpos are only “chain-definable” when \(|\ranks({\ale}) - \ranks({\ble})| \le 1\).

We introduce the dual of a tournament.

Definition 4

For \(T \in \T_{nm}\), the dual of \(T\) is the \(m \times n\) tournament \(\dual{T} = \one_{mn} - T^\transp\), where \(\one_{mn}\) denotes the matrix consisting entirely of ones, and \(T^\transp\) denotes the tranpose of \(T\).

The rankings of \(T\) are linked to the rankings of \(\dual{T}\) in the same way as for binary tournaments.

Lemma 1

For \(T \in \T_{nm}\), with \(A = \{1,\ldots,n\}\) and \(B=\{1,\ldots,m\}\),

  1. \({\anle_T} = {\bnle_{\dual{T}}}\) and \({\bnle_T} = {\anle_{\dual{T}}}\).

  2. \(T \in \chain_{nm}\) iff \(\dual{T} \in \chain_{mn}\).

Proof. The proof of (1) is trivial, and (2) follows from (1).

Chain editing

We define chain editing for non-binary tournaments with respect to a distance metric \(d\) on \(\T_{nm}\): for \(T \in \T_{nm}\), write

\[\minch_d(T) = \argmin_{T' \in \chain_{nm}}d(T, T')\]

Problem 1 (Chain-editing)

Input: \(T \in \T_{nm}\), distance metric \(d\)

Output: \(T' \in \minch_d(T)\)

Example 1. Some possible metrics include:

  • The Euclidean distance \(d_2\):

    \[d_2(T, T') = \sqrt{\sum_{a,b}(T_{ab} - T'_{ab})^2}\]

  • The “Manhattan distance” \(d_1\):

    \[d_1(T, T') = \sum_{a,b}|T_{ab} - T'_{ab}|\]

  • The Hamming distance \(d_H\):

    \[d_H(T, T') = |\{(a, b) \in A \times B \mid T_{ab} \ne T'_{ab}\}|\]

  • For \(p \ge 1\), the \(L_p\) distance \(d_p\):

    \[d_p(T, T') = \left(\sum_{a,b}|T_{ab} - T'_{ab}|^p\right)^{\frac{1}{p}}\]

    Note that the Euclidean and Manhattan distances are special cases of \(d_p\), for \(p = 2\) and \(p = 1\) respectively.

  • The “maximum distance” or \(L_\infty\) distance \(d_\infty\):

    \[d_\infty(T, T') = \max_{a, b}|T_{ab} - T'_{ab}|\]

    This is the limit of \(d_p\) as \(p \to \infty\). 2

Note that chain-editing is not well-defined for all choices of metric \(d\), since \(\minch_d(T)\) may be empty. This is illustrated by the following (highly contrived) example.

Example 2. Fix \(n, m \in \N\). Fix a tournament \(\hat{T} \in \T_{nm} \setminus \chain_{nm}\). Let \(A \subseteq \chain_{nm}\) be a countably infinite subset of \(n \times m\) chain tournaments. 3 Enumerate the tournaments of \(A\) as \((T^*_k)_{k \in \N}\). Letting \(\zero\), \(\one\) and \(\mathbf{2}\) denote the \(n \times m\) matrices of 0s, 1s and 2s respectively, define a function \(\gamma: \T_{nm} \to \R^{n \times m}\) by

\[\gamma(T) = \begin{cases} \zero,& T = \hat{T} \\ \frac{1}{k}\one,& T = T^*_k \\ \mathbf{2} + T,& \text{ otherwise} \end{cases}\]

Now define a metric \(d\) by

\[d(T, T') = d_2(\gamma(T), \gamma(T'))\]

It is easily checked that \(d\) inherits symmetry and the triangle inequality from the Euclidean distance \(d_2\). Moreover, \(\gamma\) is injective, so \(d(T, T') = 0\) iff \(T = T'\). Thus \(d\) is indeed a metric.

We will show that chain-editing is ill-defined wrt \(d\) by showing that \(\minch_d(\hat{T}) = \emptyset\). Let \(T \in \chain_{nm}\). If \(T \in A\), then \(T = T^*_k\) for some \(k \in \N\). In this case

\[d(\hat{T}, T) = d_2\left(\zero, \frac{1}{k}\one\right) = \sqrt{\sum_{a,b}{\left(\frac{1}{k}\right)^2}} = \frac{\sqrt{nm}}{k}\]

If \(T \notin A\), then

\[d(\hat{T}, T) = d_2(\zero, \mathbf{2} + T) = \sqrt{ \sum_{ab}{ \left( \underbrace{2 + T_{ab}}_{\ge 2} \right)^2 } } \ge 2\sqrt{nm}\]

We see that all tournaments in \(A\) are closer to \(\hat{T}\) than those chain tournaments outside \(A\). Moreover, \(d(\hat{T}, T^*_k) > 0\) for all \(k\), but \(d(\hat{T}, T) \to 0\) as \(k \to \infty\). That is, there are chain tournaments arbitrary close to \(\hat{T}\), but there is no closest chain tournament. Consequently, \(\minch_d(\hat{T}) = \emptyset\).

Fortunately, chain-editing is well-defined for “better-behaved” choices of metric, as will be shown. In what follows we treat \(n \times m\) tournaments as living in the space \(\R^{nm}\), equipped with its usual topology induced by the Euclidean distance \(d_2\).

Lemma 2

\(\chain_{nm}\) is a closed subset of \(\R^{nm}\).

Proof.

Write \(N = nm\). Recall that \(S \subseteq \R^N\) is closed if and only if for every convergent sequence \((x_k)_{k \in \N}\) with \(x_k \in S\) for all \(k \in \N\), we have \(\lim_{k \to \infty}{x_k} \in S\).

Let \((T_k)_{k \in \N}\) be a sequence of tournaments in \(\chain_{nm}\) with limit \(T^*\). Since \([0, 1]^N\) is closed, it is clear that \(T^* \in \T_{nm}\), i.e. \(T^*\) is a tournament. We will show that \(T^*\) is a chain tournament.

By definition, \(\anle_T\) and \(\bnle_T\) are reflexive and transitive, so we only need to check totality. Take \(a, a' \in A\), and suppose \(a \not\anle_{T^*} a'\). Then there is \(\hat{b} \in B\) such that \({T^*}_{a\hat{b}} > {T^*}_{a'\hat{b}}\). Hence 4

\[\begin{aligned} 0 &< {T^*}_{a\hat{b}} - {T^*}_{a'\hat{b}} \\ &= \lim_{k \to\infty}[{T_k}]_{a\hat{b}} - \lim_{k \to\infty}[{T_k}]_{a'\hat{b}} \\ &= \lim_{k \to\infty}{([T_k]_{a\hat{b}} - [T_k]_{a'\hat{b}})} \end{aligned}\]

Since this limit is strictly positive, there is \(K \in \N\) such that \([T_k]_{a\hat{b}} - [T_k]_{a'\hat{b}} > 0\) for all \(k \ge K\). Since each \(T_k\) is a chain tournament, this must mean \(a' \anlt_{T_k} a\) for all such \(k\). Now take any \(b \in B\). Then \([T_k]_{ab} \ge [T_k]_{a'b}\) for all \(k \ge K\), so

\[T^*_{ab} - T^*_{a'b} = \lim_{k \to \infty}{( \underbrace{[T_k]_{ab} - [T_k]_{a'b}}_{\ge 0 \text{ for } k \ge K} )} \ge 0\]

i.e. \(T^*_{a'b} \le T^*_{ab}\). Since \(b\) was arbitrary, this shows \(a' \anle_{T^*} a\), and hence \(\anle_T\) is total.

That \(\bnle_{T^*}\) is total follows by duality. Applying the above argument to \(\dual{{T^*}}\), we have that \(\anle_{\dual{{T^*}}}\) is total. By Lemma 1, \(\bnle_{T^*}\) is total. Thus \(T^* \in \chain_{nm}\), and we are done.

Lemma 3

Let \(d\) be a metric on \(\T_{nm}\) and \(\hat{T} \in \T_{nm}\). If the function \(f: \chain_{nm} \to \R\) given by \(T \mapsto d(\hat{T}, T)\) is continuous, then \(\minch_d(\hat{T}) \ne \emptyset\).

Proof.

Since tournament matrix entries are constrained to lie in \([0, 1]\), it is clear that \(\chain_{nm}\) is a bounded subset of \(\R^{nm}\). By Lemma 2, \(\chain_{nm}\) is closed and bounded. The Heine–Borel theorem states that a subset of \(\R^{l}\) is closed and bounded if and only if it is compact. Hence \(\chain_{nm}\) is compact, as a subspace of \(\R^{nm}\). It is a theorem of topology that the image of a continuous mapping with compact domain is also compact. 5 Hence \(f(\chain_{nm}) \subseteq \R\) is compact. By the Heine-Borel theorem again, \(f(\chain_{nm})\) is closed and bounded, and thus contains a minimum element \(r\). 6 Consequently there is \(T \in \chain_{nm}\) such that \(f(T) = r\), i.e.

\[d(\hat{T}, T) = f(T) = r = \min f(\chain_{nm}) = \min_{T' \in \chain_{nm}}d(\hat{T}, T')\]

i.e. \(T \in \argmin_{T' \in \chain_{nm}}d(\hat{T}, T') = \minch_d(\hat{T})\).

Lemma 4

Let \(d\) be a metric on \(\T_{nm}\). If there is a constant \(K > 0\) such that \(d(T, T') \le Kd_2(T, T')\) for all \(T, T' \in \T_{nm}\), then for any fixed \(\hat{T} \in \T_{nm}\) the function \(f(T) = d(\hat{T}, T)\) is continuous on \(\T_{nm}\).

Proof.

We use the \(\epsilon\)-\(\delta\) formulation of continuity; we show that for all \(T \in \T_{nm}\) and for all \(\epsilon > 0\), there is \(\delta > 0\) such that \(d_2(T, T') < \delta\) implies \(|f(T) - f(T')| < \epsilon\). Note that we specify \(d_2\) here, since we aim to show continuty of \(f\) with respect to the Euclidean topology \(\T_{nm}\), which is induced by \(d_2\).

So, fix \(T \in \T_{nm}\) and let \(\epsilon > 0\). Take \(\delta = \frac{\epsilon}{K} > 0\). Suppose \(d_2(T, T') < \delta\). Note that by the triangle inequality,

\[\begin{aligned} f(T) - f(T') &= d(\hat{T}, T) - f(T') \\ &\le d(\hat{T}, T') + d(T', T) - f(T') \\ &= f(T') + d(T', T) - f(T') \\ &= d(T', T) \\ &= d(T, T') \end{aligned}\]

By symmetry, we have

\[f(T') - f(T) \le d(T, T')\]

and thus

\[-d(T, T') \le f(T) - f(T') \le d(T, T')\]

Hence

\[|f(T) - f(T')| \le d(T, T') \le Kd_2(T, T') < K\delta = \epsilon\]

as required.

Theorem 1

Chain-editing is well-defined with respect to each of the distance metrics \(d\) in Example 1, i.e. \(\minch_d(T) \ne \emptyset\) for all \(T \in \T_{nm}\).

Proof.

The result is clear for \(d_2\) by Lemma 4 (with \(K = 1\)) and Lemma 3.

Next, consider \(d_1\). We use Lemma 4 again. Let \(T, T' \in \T_{nm}\). By the Cauchy-Schwarz inequality

\[\left(\sum_i u_i v_i\right)^2 \le \left(\sum_i u_i^2\right) \left(\sum_i v_i^2\right)\]

for \(u_i, v_i \in \R\), we have

\[\begin{aligned} d_1(T, T')^2 &= \left(\sum_{a,b} |T_{ab} - T'_{ab}|\right)^2 \\ &\le \left(\sum_{a,b}1^2 \right) \left(\sum_{a,b}|T_{ab} - T'_{ab}|^2 \right) \\ &= nm \cdot d_2(T, T')^2 \end{aligned}\]

so

\[d_1(T, T') \le \sqrt{nm} \cdot d_2(T, T')\]

Taking \(K = \sqrt{nm}\) and applying Lemma 4, Lemma 3, we have \(\minch_{d_1}(T) \ne \emptyset\) for all \(T\).

The Hamming distance \(d_H\) clearly permits chain-editing, since it takes values in \(\N_0\). For any \(T\), the set

\[\{d_H(T, T') \mid T' \in \chain_{nm}\} \subseteq \N_0\]

is a non-empty set of integers bounded below, so admits a minimum. Consequently there is \(T' \in \chain_{nm}\) such that \(d(T, T')\) is minimal, i.e. \(T' \in \minch_{d_H}(T)\).

For \(d_p\), let \(p \ge 1\). It can be shown that, for \(1 \le p_1 \le p_2\), 7

\[d_{p_2}(T, T') \le d_{p_1}(T, T')\]

In particular,

\[d_p(T, T') \le d_1(T, T') \le \sqrt{nm} \cdot d_2(T, T')\]

and we conclude by Lemma 4 as with the \(d_1\) distance.

Finally, for \(d_\infty\) we clearly have \(d_\infty(T, T') \le d_1(T, T')\) and the result follows similarly.

Note that the proof of Lemma 2 can be adapted to show that for each \(T \in \T_{nm}\) the sets

\[\begin{aligned} \chain_{nm}^{T, +} &= \{T' \in \chain_{nm} \mid \forall a, b: T_{ab} \le T'_{ab}\} \\ \chain_{nm}^{T, -} &= \{T' \in \chain_{nm} \mid \forall a, b: T_{ab} \ge T'_{ab}\} \end{aligned}\]

are also closed, and therefore chain-addition and chain-deletion are also well-defined with respect to the metrics of Example 1.

Allowing abstentions

We extend the model to allow abstentions. Let \(\null\) be a constant value which represents no match.

Definition 5

A partial tournament is a tuple \((A, B, P)\), with \(A\) and \(B\) as in Definition 1, where \(P\) is a mapping \(A \times B \to [0, 1] \cup \{\null\}\).

Notation. Write \(\partial_{nm}\) for the set of \(n \times m\) partial tournaments. Say a (complete) tournament \(T\) is an extension of \(P\) if, for all \(a, b\), \(P_{ab} \ne \null\) implies \(T_{ab} = P_{ab}\), and write \(\ext(P)\) for the set of such extensions. Write \(\gamesa_P(a) = \{b \in B \mid P_{ab} \ne \null\}\) for the set of opponents in \(B\) that \(a \in A\) has faced in \(P\). Similarly, write \(\gamesb_P(b) = \{a \in A \mid P_{ab} \ne \null\}\).

We generalise the relations of Definition 2 to partial tournaments.

Definition 6

For \(P \in \partial_{nm}\), define relations \(\anlep_P\) and \(\bnlep_P\) on \(A\) and \(B\), respectively, by

\[\begin{aligned} a \anlep_P a' &\iff \forall b \in \gamesa_P(a) \cap \gamesa_P(a'): P_{ab} \le P_{a'b} \\ b \bnlep_P b' &\iff \forall a \in \gamesb_P(b) \cap \gamesb_P(b'): P_{ab} \ge P_{ab'} \end{aligned}\]

Note that for each pair \(a, a'\), we compare \(P_{ab}\) with \(P_{a'b}\) only for the common opponents of \(a\) and \(a'\). Unlike in the case of complete tournaments, these relations are no longer guaranteed to be transitive; e.g. for

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

we have a cycle with \(1 \anltp_P 2 \anltp_P 3 \anltp_T 1\).

1

Indeed, set

\[\begin{aligned} x(a) &= |\{a' \in A \mid a' \ale a\}| \\ y(b) &= |\{b' \in B \mid b' \ble a\}| \end{aligned}\]

Then one can easily check that \(a \ale a'\) iff \(x(a) \le x(a')\) and \(b \ble b'\) iff \(y(b) \le y(b')\). Note \(x(a), y(b) \ge 1\) by reflexivity. Define \(T\) by

\[T_{ab} = \frac{x(a)}{x(a) + y(b)}\]

Then \(T_{ab} \in (0, 1)\), so \(T\) is a tournament. It is easy to check that \(a \anle_T a'\) iff \(x(a) \le x(a')\) and \(b \ble_T b'\) iff \(y(b) \le y(b')\), since the function \((x, y) \mapsto \frac{x}{x+y}\) is strictly increasing in the first argument and strictly decreasing in the second (for \(x, y > 0\)). Since the rankings coming from \(x(\cdot)\) and \(y(\cdot)\) coincide with \(\ale\) and \(\ble\), this shows that \(T\) is a chain tournament and \(\rankings(T) = ({\ale}, {\ble})\).

2

https://en.wikipedia.org/wiki/Lp_space#Definition

3

For example, let \(A\) be the set of chain tournaments with entries in \(\mathbb{Q}\).

4

Here we use the fact that if \(x_n \to x^* \in \R^N\), then for each \(i \in \{1,\ldots,N\}\), \([x_n]_i \to x^*_i\).

5

See [Cro05], Proposition 4.27.

6

To see this, let \(S \subseteq \R\) be closed, bounded and non-empty. Then \(\alpha = \inf S\) is finite. Using properties of the infimum, there is a sequence \((x_n)_{n \in \N}\) in \(S\) with limit \(\alpha\). But since \(S\) is closed, this limit must also lie in \(S\). Hence \(\alpha = \min S\).

7

See https://en.wikipedia.org/wiki/Lp_space#Relations_between_p-norms