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}{E} \gdef{\games}{G} \gdef{\chain}{\mathcal{C}} \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{\normal}{\mathsf{Normal}}\]

Generalising the chain graph paper (temp)

Draws, abstensions and non-binary match outcomes

In the AAMAS paper, each player in \(A\) faced each player in \(B\), and match outcomes were decisive. We generalise this framework to allow match outcomes to take values in \(V = [0,1] \cup \{\null\}\); values close to 1 represent better outcomes for the player in \(A\), values close to 0 represent better outcomes for the player in \(B\), and \(\null\) represents that no match took place.

Definition 1

A partial tournament is a triple \((A, B, T)\), where \(A = \{1,\ldots,n\}\) and \(B = \{1,\ldots,m\}\) for some \(n, m \in \N\) and \(T: A \times B \to V = [0, 1] \cup \{\null\}\).

When no ambiguity ensues we denote a partial tournament simply by \(T\), and write \(T\) as a matrix. Let \(\T_{nm}\) denote the set of partial tournaments with \(A = \{1,\ldots,n\}\) and \(B = \{1,\ldots,m\}\) (henceforth referred to as “\(n \times m\)” tournaments).

Write \(\games(T) = \{(a, b) \in A \times B \mid T_{ab} \ne \null\}\). Say \(T\) is complete if \(G(T) = A \times B\). The complete extensions of \(T \in \T_{nm}\) are

\[\ext(T) = \{T' \in \T_{nm} \mid T' \text{ complete, } \forall (a, b) \in \games(T): T'_{ab} = T_{ab} \}\]

Ranking methods

Rankings methods are the same as in the AAMAS paper.

Definition 2

A ranking method \(\phi\) maps any tournament \(T\) to a pair of total preorders \(({\ale_T^\phi}, {\ble_T^\phi})\) on \(A\) and \(B\) respectively.

Complete chain tournaments

For a complete tournament \(T\), define relations \(\anle_T\), \(\bnle_T\) on \(A\) and \(B\) respectively by

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

Say that \(T\) is a (complete) chain tournament if both relations are total preorders. Note this reduces to the AAMAS definition if \(T_{ab} \in \{0, 1\}\) for all \(a, b\). Let \(\chain_{nm}\) denote the set of complete \(n \times m\) chain tournaments.

Remark 1

When outcomes are restricted to 0 or 1, the totality of \(\anle_T\) implies the totality of \(\bnle_T\). This is no longer true once values in \((0, 1)\) are allowed; for example in

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

\(\anle_T\) is total but \(\bnle_T\) is not.

We define chain editing for \(n \times m\) tournaments with respect to a distance function \(d\) on \(\T_{nm}\): for \(T \in \T_{nm}\), set

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

We introduce the chain editing axiom for ranking methods.

  • (d-chain-min) For all \(T\) there is \(T' \in \minch_d(T)\) such that \(a \ale_T^\phi a'\) iff \(a \anle_{T'} a'\), and \(b \ble_T^\phi\) iff \(b \bnle_{T'} b'\).

Example 1. Let \(d_2\) denote the “masked” Euclidean distance between tournaments, which ignores entries in which either tournament has \(\null\) values:

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

Note that \(d_2(T, T') = 0\) does not imply \(T = T'\) (e.g. \(T = \left[\begin{smallmatrix}1 & 0\end{smallmatrix}\right]\) and \(T' = \left[\begin{smallmatrix}1 & \null\end{smallmatrix}\right]\)), and \(d_2\) does not even satisfy the triangle inequality (e.g. consider \(T_1 = \left[\begin{smallmatrix}1 & \null\end{smallmatrix}\right]\), \(T_2 = \left[\begin{smallmatrix}\null & 1\end{smallmatrix}\right]\) and \(T_3 = \left[\begin{smallmatrix}0 & \null\end{smallmatrix}\right]\); we have \(d_2(T_1, T_3) = 1 \not\le 0 = d_2(T_1, T_2) + d_2(T_2, T_3)\)). But is this a problem?

Remark 2

The set \(\chain_{nm}\) is not in general convex. For example, consider \(T_1 = \left[\begin{smallmatrix}0 & .5 \\ 1 & 1\end{smallmatrix}\right]\) and \(T_2 = \left[\begin{smallmatrix}1 & 1 \\ .5 & 0\end{smallmatrix}\right]\). Then both \(T_1, T_2 \in \chain_{22}\), but \(\frac{1}{2}T_1 + \frac{1}{2}T_2 = \left[\begin{smallmatrix}.5 & .75 \\ .75 & .5\end{smallmatrix}\right]\) is not.

Probabilistic model

We aim to obtain a similar result to the AAMAS paper: a probability distribution over tournaments, parametrised by values \(\theta\), such that for each \(T\), \(\phi\) outputs rankings according to some ML estimate \(\theta\) if and only if \(T\) satisfies (d-chain-min).

Gaussian noise model

Write \(\Theta_{nm} = \R_{>0}^n \times \R_{>0}^m\) for the parameter space of the model; \(\theta = (\vec{x}, \vec{y}) \in \Theta_{nm}\) contains positive skill ratings \(x_a\), \(y_b\) for each \(a \in A\) and \(b \in B\).

For \(\theta \in \Theta_{nm}\), write

\[\mu^\theta_{ab} = \frac{x_a}{x_a + y_b} \in (0, 1] \]

We suppress \(\theta\) from the notation when clear from context. This value represents the “ideal” outcome of a match between \(a\) and \(b\). Note that \(\mu_{ab} < \frac{1}{2}\) if \(x_a < y_b\), \(\mu_{ab} = \frac{1}{2}\) if \(x_a = y_b\), and \(\mu_{ab} > \frac{1}{2}\) if \(x_a > y_b\). We allow for “mistakes” to be made with some probability, by drawing the actual match result between \(a\) and \(b\) from a normal distribution centred at \(\mu_{ab}\).

To that end, fix \(\sigma > 0\) and let \(Z\) be a random \(n \times m\) matrix with

\[Z_{ab} \sim \normal(\mu_{ab}, \sigma^2)\]

Let \(f_Z(\cdot; \theta)\) denote the probability density function for \(Z\):

\[f_Z(M; \theta) = \prod_a \prod_b \frac{1}{\sigma\sqrt{2\pi}} \exp\left( -\frac{1}{2}\left( \frac{M_{ab} - \mu_{ab}}{\sigma} \right)^2 \right) > 0\]

for \(M \in \R^{n \times m}\).

Note that the random process \(Z\) does not necessarily produce a complete tournament, since \(Z_{ab}\) is not restricted to lie in \([0, 1]\). For an arbitrary partial tournament \(T \in \T_{nm}\), we take the best-case likelihood of a complete extension of \(T\) as a proxy for the likelihood of \(T\); set

\[\L_T(\theta) = \sup_{T' \in \ext(T)}f_Z(T'; \theta)\]

We can now introduce a MLE-like axiom for ranking methods:

  • (noise-MLE) For all \(n \times m\) tournaments \(T\) there is \(\theta = (\vec{x}, \vec{y}) \in \argmax_{\theta' \in \Theta_{nm}}{\L_T(\theta')}\) such that \(a \ale_T^\phi a'\) iff \(x_a \le x_{a'}\) and \(b \ble_T^\phi b'\) iff \(y_b \le y_{b'}\).

Notation. For \(\theta \in \Theta_{nm}\), let \(T_{\theta}\) be the complete tournament given by \([T_\theta]_{ab} = \mu_{ab}\).

Lemma 1

For \(T \in \T_{nm}\),

\[\argmax_{\theta \in \Theta_{nm}}{\L_T(\theta)} = \argmin_{\theta \in \Theta_{nm}}{d_2(T, T_\theta)}\]
Proof.

Note that \(\L_T(\theta) > 0\) for all \(\theta\). Hence \(\L_T(\theta)\) is maximised exactly when \(\log\L_T(\theta)\) is. Since \(\log(\cdot)\) is continuous and strictly increasing, we have

\[\begin{aligned} \log\L_T(\theta) &= \log\sup_{T' \in \ext(T)}{f_Z(T'; \theta)} \\ &= \sup_{T' \in \ext(T)}{\log f_Z(T'; \theta)} \\ \end{aligned} \]

Note that

\[\begin{aligned} \log f_Z(T'; \theta) &= \log \prod_a \prod_b \frac{1}{\sigma\sqrt{2\pi}} \exp\left( -\frac{1}{2}\left( \frac{T'_{ab} - \mu_{ab}}{\sigma} \right)^2 \right) \\ &= \sum_a \sum_b \left[ \log\frac{1}{\sigma\sqrt{2\pi}} - \frac{1}{2}\left(\frac{T'_{ab} - \mu_{ab}}{\sigma}\right)^2 \right] \\ &= nm\log\frac{1}{\sigma\sqrt{2\pi}} - \frac{1}{2\sigma^2}\sum_a \sum_b (T'_{ab} - \mu_{ab})^2 \\ &= c - k\sum_a \sum_b (T'_{ab} - \mu_{ab})^2 \end{aligned}\]

where \(c\) and \(k\) are constants independent of \(T'\) and \(\theta\), with \(k > 0\). Therefore

\[\log\L_T(\theta) = c - k\inf_{T' \in \ext(T)}\sum_a \sum_b (T'_{ab} - \mu_{ab})^2\]

Now, if \(T' \in \ext(T)\) then \(T'_{ab} = T_{ab}\) for all \((a, b) \in \games(T)\). Hence

\[\begin{aligned} \sum_a \sum_b (T'_{ab} - \mu_{ab})^2 &= \sum_{(a, b) \in \games(T)}(T_{ab} - \mu_{ab})^2 + \sum_{(a,b) \notin \games(T)}(T'_{ab} - \mu_{ab})^2 \\ &= d_2(T, T_\theta)^2 + \underbrace{\sum_{(a,b) \notin \games(T)}(T'_{ab} - \mu_{ab})^2}_{(*)} \end{aligned} \]

where we use \(\games(T_\theta) = A \times B\). Note that only the \((*)\) term depends on \(T'\), and \((*) \ge 0\) for any choice of \(T' \in \ext(T)\). Moreover, the lower bound of 0 is achieved by setting \(T' = \mu^{ab}\) for \((a,b) \notin \games(T)\). Hence

\[\begin{aligned} \inf_{T' \in \ext(T)}\sum_a \sum_b (T'_{ab} - \mu_{ab})^2 &= \inf_{T' \in \ext(T)}\left[ d_2(T, T_\theta)^2 + \sum_{(a,b) \notin \games(T)}(T'_{ab} - \mu_{ab})^2 \right] \\ &= d_2(T, T_\theta)^2 + \underbrace{\inf_{T' \in \ext(T)} \sum_{(a,b) \notin \games(T)}(T'_{ab} - \mu_{ab})^2}_{=0} \\ &= d_2(T, T_\theta)^2 \end{aligned}\]

and so

\[\log\L_T(\theta) = c - kd_2(T, T_\theta)^2\]

Finally, using \(k > 0\) and \(d_2(T, T_\theta) \ge 0\) we have

\[\begin{aligned} \L_T(\theta) \text{ maximised} &\iff \log\L_T(\theta) \text{ maximised} \\ &\iff c - kd_2(T, T_\theta)^2 \text{ maximised} \\ &\iff d_2(T, T_\theta)^2 \text{ minimised} \\ &\iff d_2(T, T_\theta) \text{ minimised} \\ \end{aligned} \]

which proves the result.

Lemma 2

Let \(\theta = (\vec{x}, \vec{y}) \in \Theta_{nm}\). Then, for all \(a, a' \in A\) and \(b, b' \in B\),

\[\begin{aligned} x_a \le x_{a'} &\iff a \anle_{T_\theta} a' \\ y_b \le y_{b'} &\iff b \bnle_{T_\theta} b' \end{aligned} \]
Proof.

It is sufficient to note that the function \(g: \R_{>0} \times \R_{>0} \to \R\),

\[(s, t) \mapsto \frac{s}{s+t}\]

is strictly increasing in the first argument and strictly decreasing in the second, since \([T_\theta]_{ab} = g(x_a, y_b)\).

Corollary 1

\(T_\theta \in \chain_{nm}\) for all \(\theta \in \Theta_{nm}\).

Proof. From Lemma 2 it easily follows that \(\anle_{T_\theta}\) and \(\bnle_{T_\theta}\) are total preorders.

Lemma 3

For all \(T \in \chain_{nm}\) there is \(\theta \in \Theta_{nm}\) such that \({\anle_T} = {\anle_{T_\theta}}\) and \({\bnle_T} = {\bnle_{T_\theta}}\).

Proof. Take \(T \in \chain_{nm}\). Define \(\theta = (\vec{x}, \vec{y})\) by

\[\begin{aligned} x_a &= |\{a' \in A \mid a' \anle_T a\}| \ge 1 \\ y_b &= |\{b' \in B \mid b' \anle_T b\}| \ge 1 \end{aligned}\]

Since \({\anle_T}\) and \({\bnle_T}\) are total preorders, we have \(a \anle_T a'\) iff \(x_a \le x_{a'}\) and \(b \bnle_T b'\) iff \(y_b \le y_{b'}\). The result now follows from Lemma 2.