Bipartite Tournaments¶

Introduction to partial tournaments¶

González-Díaz et. al define a weighted partial tournament (which they call a ranking problem) as follows.

A ranking method should rank players according to their performance in the ‘matches’ that comprise the tournament, whilst taking into account the quality of the opponents. That is, a player should be rewarded for beating highly ranked players. This implies some kind of recursive aspect to the ranking methods, reminiscent of our Coherence properties for truth discovery.

A number of axioms to express this (and other desirable properties) are given in [GonzalezDiazHL14].

Special case: bipartite tournaments¶

Consider the special case where \(N\) is the union of two disjoint sets of players \(X = \{x_1,\ldots,x_m\}\) and \(Y = \{y_1,\ldots,y_n\}\), and players in \(X\) do not compete against those in \(Y\) and vice versa. Moreover, suppose that we are only interested in comparing players in \(X\) against other players in \(X\), and similarly for \(Y\).

The fact that players to be ranked only indirectly compete with each other might make the bipartite case an interesting one to study: we want to rank objects in \(X\) (and in \(Y\)) but without any direct comparisons between them.

This special case has some practical applications:

• Education: \(X\) consists of students and \(Y\) consists of exam questions. We aim to rank the students according to their exam performance whilst taking the difficulty of the questions into account.

  Here a ‘match’ occurs when a student attempts a question: 1 the student wins if they correctly answer the question (i.e. they successfully ‘beat’ the question), and the question wins if they answer incorrectly (i.e. the question successfully ‘tricks’ the student).

• Supervised truth discovery: very similar to the education example: \(X\) consists of sources and \(Y\) of objects for which the truth is already known.

• Machine learning evaluation: \(X\) consists of models for some particular problem, and \(Y\) consists of test datasets against which the models can be evaluated. We wish to rank the models according to their accuracy whilst considering the difficulty of the test datasets, i.e. the degree to which it is easy or hard to achieve high accuracy.

  A version of this is the focus of [OBB+18], where generative models compete in a tournament against discriminators in order to evaluate the models.

• Judged competitions (?): Consider a solo-sport where players are given scores by a number of judges (Diving? Show-jumping? I don’t know…). \(X\) consists of the participants, and \(Y\) the judges. Here \(x_i\) ‘beats’ judge \(y_j\) when receiving a high score from that judge. The ranking of judges then represents how hard the judges are to please. The players are then ranked such that receiving a high score from a difficulty-to-please judge counts for more than a judge who often gives high scores. 2

  In a sense the game of golf fits into this scheme too, where each hole acts as a judge. A bipartite-tournament-based ranking system would account for the difficulty of each hole when ranking players. 3

  This whole example might be a bit of a stretch…

Whilst we could define a bipartite tournament directly as a special case of the definition above, the matrix \(A\) would contain redundant \(m \times m\) and \(n \times n\) blocks of zeros since players in \(X\) do not play each other (and similar for \(Y\)).

Additionally, note that in the general case there are two numbers associated with each pair of players: \(A_{ij}\) (the score of \(i\) against \(j\)) and \(A_{ji}\) (the score of \(j\) against \(i\)). This seems fine when the two players are the same kind of entity, but less so in the bipartite case. To me the asymmetry between pairs of competing players suggests we should have a single score from the perspective of one side, say \(X\).

This leads to the following (tentative) definition.

One problem with this definition is that we cannot distinguish between a draw between \(x_i\) and \(y_j\) and the case where no match occurred. Both cases are represented by \(A_{ij}=0\).

A cooperative version¶

The tournament setting is adversarial in nature, but a cooperative version also has applications. Consider that instead of a ‘match’ between \(x\) and \(y\) (with a result in favour of either \(x\) or \(y\)), we have a degree of cooperation between \(x\) and \(y\). Then we wish to find rankings so that \(x\) is highly ranked if it cooperates with highly ranked elements of \(Y\), and vice versa. We have at least the following instances of this problem.

• Journal rankings: \(X\) consists of scientific journals and \(Y\) consists of authors. Journal \(x \in X\) should rank highly if it publishes papers from influential authors, and an author is influential if they publish in high-ranking journals.

  (This idea comes from footnote 4 in [GonzalezDiazHL14])

• Truth discovery: \(X\) consists of sources and \(Y\) consists of facts: sources are ranked in terms of trustworthiness and facts in terms of believability. As we know, a source should rank highly if its facts rank highly and vice versa.

• Hubs and authorities: [Kle99] Although this model of the web may no longer be accurate after 20 years, the premise is that a ‘hub’ web page is of good quality if it links to good ‘authority’ pages, and vice versa.

Implementation of some ranking methods for partial tournaments¶

The following implements all the ranking methods from [GonzalezDiazHL14], except for Maximum Likelihood (need to write the code for this) and Least squares, which gives the same rankings as Recursive Buchholz.

The background colours indicate the rankings of the players for each ranking method: the lowest ranked players are red and the highest are green.

It is difficult/impossible to try out the bipartite tournaments discussed above in this implementation. The main problem is the irreducibility requirement on the results matrix: we need that for each pair of players \(i\) and \(j\) there is a sequence of players \(k_0,\ldots,k_p\) such that \(k_0 = i\), \(k_p = j\) and each \(k_t\) scores against \(k_{t+1}\).

Number of players: Reset to zeros Randomise

Go

Still to do¶