PhD Notes

Contents:

\[\gdef{\ch}{\mathcal{C}} \gdef{\minch}#1{\operatorname{\mathcal{M}}\left({#1}\right)} \gdef{\minchw}#1#2{\operatorname{\mathcal{M}_{#1}}({#2})} \gdef{\mindist}#1{m({#1})} \gdef{\phi}{\varphi} \gdef{\K}{\mathcal{K}} \gdef{\N}{\mathbb{N}} \gdef{\R}{\mathbb{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{\tr}{\top} \gdef{\dual}#1{{\overline{#1}}} \gdef{\v}{\operatorname{vec}} \gdef{\argmin}{\operatorname*{argmin}} \gdef{\argmax}{\operatorname*{argmax}} \gdef{\rs}{\upharpoonright} \gdef{\dotprod}{\bullet} \gdef{\tpos}#1{\operatorname{\mathcal{L}}({#1})} \gdef{\expectation}#1#2{\operatorname*{\mathbb{E}}_{#1}{#2}} \gdef{\orderings}#1{\operatorname*{\mathcal{L}}({#1})} \gdef{\cherr}{\varepsilon} \gdef{\position}#1#2{\operatorname{pos}({#1},{#2})} \gdef{\avgmin}{\text{avg}} \gdef{\symdiff}{\mathrel{\triangle}} \gdef{\phicardint}{{\phi_{\text{CI}}}} \gdef{\tuple}#1{\langle{#1}\rangle}\]

Bipartite tournament ranking via chain graphs: Paper outline

A list of all the stuff we’ve done

  • Defined core framework (tournaments, dual, operator)

  • Chain graph basics (definition, \(\minch{K}\), chain-definability)

  • Axioms

    • sym, dual, inv-rev

    • chain-def, chain-min, k-chain, count-chain

    • mon, strict-mon, weak-mon, pos-resp, non-neg-resp, IIM

    • win-coherence, loss-coherence, ceteris-paribus

    • improvement, extension, concat

    • sub-matrix-independence (interleaving operators only), rank-removal

  • chain-min axioms:

    • Incompatible: sym, pos-resp, strict-mon, IIM, {win,loss}-coherence, ceteris-paribus

    • Compatible: chain-def, chain-min, dual, inv-rev (?), k-chain, extension, improvement (?)

    • Can probably prove compatibility: mon, non-neg-resp, weak-mon

    • Haven’t looked at: count-chain, concat

  • Match-preference operators:

    • Temporal ordering motivation and definition

    • Result: there exists a family of weightings such that \(\phi(K)\) is defined by closest chain-tournaments with respect to the weighted Hamming distance

    • Axioms: Maybe can have extension. Cannot have dual for basic row-by-row or column-by-column match-preference relations

  • Maximum likelihood characterisation:

    • Basic model (states of the world, probability distribution over tournaments)

    • Result: states correspond to chain tournaments Result: MLE states correspond to closest chain tournaments when \(\alpha_+ = \alpha_- < 1/2\)

    • Result: rankings of \(\phi\) correspond to MLE states on all inputs iff \(\phi\) has chain-min

    • Result: If \(\alpha_+ = 0\) corresponds to chain-addition, \(\alpha_- = 0\) corresponds to chain-deletion

  • Relaxing symmetry:

    • Chain error result: there exists symmetric operators that are chain-optimal on all inputs

    • Sketch of a method to remove symmetry in \(K\) before ranking (but may give a non-integer tournament)

  • Chain-inspired operators:

    • Average of closest chain rankings (has sym, dual, extends intersection, does not have chain-def)

    • Interleaving:

      • Greedy chain-def algorithm motivation, definitions

      • Result: interleaving iff chain-def

      • Result: sub-matrix-independence operators are completely specified by the top ranks only

      • Result: chain-def and rank-removal iff interleaving and sub-matrix-independence

      • \(\phicardint\):

        • Satisfies: sym, dual, mon, sub-matrix-independence, rank-removal

        • Does not satisfy: pos-resp, IIM, extension, inv-rev

        • Result: \(\phicardint\) is unique operator with argmax, chain-def, rank-removal, dual

  • Impossibility results:

    • sym, b-sym, strict-mon, chain-def

    • win-coherence, loss-coherence, chain-min

    • win-coherence, loss-coherence, dual, pos-resp

    • win-coherence, inv-rev, dual, pos-resp

    • loss-coherence, inv-rev, dual, pos-resp

  • Preliminary experimental results:

    • Generated true states \(\theta\) and noisy tournaments \(K\) as per the MLE model

    • Looked at Kemeny distance between \(\phi(K)\) and the true ranking, for different operators \(\phi\)

    • \(\phi_\text{count}\) seems to be the best (!) But it fails chain-definability

  • Existing tournament methods: considered whether methods from González-Díaz are applicable in the bipartite case

What’s the story?

  • We look at using chain graphs, an interesting concept from graph theory and computational complexity theory, to rank participants in bipartite tournaments

  • First we look at a class of optimisation-based ranking methods which use chain-editing to find the closest chain graph to a given tournament. Such rankings arise as maximum likelihood estimates in a compelling probabilistic model

  • We investigate the properties of such ranking methods via the axiomatic method of social choice theory

  • Can have some nice properties, but there are two major problems: cannot have symmetry – which may be essential in some scenarios – and computing the rankings is NP-complete

  • We address both these issues by relaxing the minimal distance constraint, and describe a class of greedy approximation algorithms which characterise this relaxed property. We single out a particularly intuitive algorithm, study some of its properties and provide an axiomatic characterisation

Stuff that is left out if going with this:

  • Removing symmetry in \(K\) (results in non-integer tournaments)

  • Stuff about “chain-error”; we don’t have any example of a chain-optimal operator

  • Average chain-min operator

  • Coherence axioms

  • Impossibility results

  • Experimental analysis

More detailed paper sketch

  • Introduction

    • Ranking participants in a tournament finds applications in voting, sports, paired comparisons and other areas

    • Many generalisations exist; most importantly, non-integer tournaments (allows for intensities of victories or draws) and partial tournaments (not all participants face each other).

    • Bipartite tournaments are a special case of partial tournaments, where participants are partitioned into two sets \(A\) and \(B\) such that no player from \(A\) (resp. \(B\)) competes against another in \(A\) (resp. \(B\)). Nevertheless we may wish to rank the \(A\)s and \(B\)s against each other. Some examples:

      • Education (student/questions, MOOCs, c.f. Jiao).

      • Iterative truth discovery algorithms (sources/objects)

      • Machine learning evaluation (models/datasets, c.f. that paper about GAN evaluation)

      • Solo sports (golfers/courses)

      • Non-monotonic reasoning (sentences/worlds)

    • Not all existing partial tournament methods are well-defined in this setting. In any case, we believe the bipartite special case is worthy of study in its own right.

    • Bipartite tournaments have natural rankings associated with them in the case of a chain graph. Chain graphs have been studied for their graph-theoretic properties, and the problem of chain editing – finding the minimum number of edge changes such that a graph has the chain property – has been studied in computational complexity theory.

    • This suggests a method for ranking bipartite tournaments: perform chain editing and output the natural ordering associated with the closest chain graph

    • <Summarise story for rest of paper>

  • Preliminaries

    • Give matrix definition of bipartite tournament

      • Example: graph representation of a matrix tournament

    • Define an operator

    • Define chain property

      • Example: chain matrix vs chain graph

  • Chain-minimal operators

    • Define chain-min property for operators

    • Informal justification for chain-min: mistakes made from the true ranking in the process of tournament

    • More precise justification: MLE characterisation

    • Emphasise that chain-def is an essential property to have in our context; chain-min operators are the best chain-def ones

  • Axiomatic analysis

    • Intro: chain-min operators have theoretical backing in a probabilistic sense, but what about its normative properties?

    • Define most important axioms

    • Symmetry fails for all chain-min operators. This could be acceptable if tie-breaking information is available (introduce match-preference idea)

    • Go through other axioms. Give compatible/incompatible result for chain-min in general and match-preference operators specifically (or just one concrete MP?)

  • Relaxing chain-min

    • Chain-min requirement has two standout problems: cannot have symmetry, and computing rankings is NP-complete.

    • A natural solution that maintains the spirit of chain graphs is to relax minimality constraint (introduce chain-definability)

    • Give characterisation of chain-def in terms of number of ranks

    • Motivate interleaving procedure: due to the above result, and easy way to get a chain-definable ranking is to select the ranks one-by-one until either \(A\) or \(B\) is exhausted.

    • Define interleaving and give \(\phicardint\) example. Mention how this can be seen as a greedy algorithm for finding a chain graph. Cardinality-based selection functions just act as a heuristic. Mention computational complexity of interleaving.

      • (question: would it be better to motivate interleaving as a way of modifying K to become a chain tournament? I.e. fill in 1s in rows for \(a\)s which were selected, remove 1s for those which were not. This would make clear the link with chain-editing. Problem is that I have not written up what the interleaving chain graphs look like, or got any results about them.)

    • Turns out that interleaving is not just one way to get chain-definability, it is the only way. Give chain-def characterisation.

    • Characterisation means we can see which axioms are compatible with chain-def by looking at properties of f and g

    • Lemma on sufficient conditions on (f, g) for the corresponding interleaving operator to satisfy various axioms (todo: try to make these iffs if easy)

    • Go through axioms results for chain-def/interleaving in general and \(\phicardint\) specifically (so as to mirror axiom section for chain-min/MP)

      • Sneak in chain-def, sym, dual/b-sym, strict-mon, chain-def impossibility here? It could be used as a way to show \(\phicardint\) does not have strict-mon, since it has sym, dual and chain-def.

    • Remark that we can only get the chain-def characterisation because the selection functions f and g are not very constrained: \(f(K, A', B')\) is allowed to depend on parts of \(K\) outside of \(A'\) and \(B'\) (i.e. greyed-out columns in interleaving example). To be precise: they fail sub-matrix-independence

    • SMI is much more restrictive: the whole pair of rankings is determined just by the top ranks (give result)

    • SMI also has a straightforward characterisation in purely ordinal terms. Define rank-removal and give result (question: could rename rank-removal to something like ‘rank-independence’ so as to emphasise the independence link)

    • Give \(\phicardint\) characterisation (todo: try to improve this by replacing argmax with other axioms which are less heavy-handed)

  • Related work

    • Partial tournaments:

      • Define partial tournaments, bipartite block tournaments

      • Mention ranking methods from González-Díaz and elsewhere and whether they work in the bipartite case

      • Look at our axioms for a few such methods in the bipartite case?

    • Peer grading is related to (but maybe the opposite) of the student/question scenario.

  • Future work

    • Jiao paper gives polynomial time algorithms for variants of chain-editing. Some of these variants might be applicable to ranking.

    • Approximation algorithms for chain-min

    • Experimental results