Rankings for bipartite tournaments via chain editing

Singleton, Joseph and Booth, Richard ORCID: https://orcid.org/0000-0002-6647-6381 2021. Rankings for bipartite tournaments via chain editing. Presented at: 20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2021), Virtual, 3-7 May 2021. AAMAS '21: Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems. IFAAMAS, pp. 1236-1244.

Preview

PDF - Published Version Download (1MB) | Preview

Abstract

Ranking the participants of a tournament has applications in voting, paired comparisons analysis, sports and other domains. In this paper we introduce bipartite tournaments, which model situations in which two different kinds of entity compete indirectly via matches against players of the opposite kind; examples include education (students/exam questions) and solo sports (golfers/courses). In particular, we look to find rankings via chain graphs, which correspond to bipartite tournaments in which the sets of adversaries defeated by the players on one side are nested with respect to set inclusion. Tournaments of this form have a natural and appealing ranking associated with them. We apply chain editing – finding the minimum number of edge changes required to form a chain graph – as a new mechanism for tournament ranking. The properties of these rankings are investigated in a probabilistic setting, where they arise as maximum likelihood estimators, and through the axiomatic method of social choice theory. Despite some nice properties, two problems remain: an important anonymity axiom is violated, and chain editing is NP-hard. We address both issues by relaxing the minimisation constraint in chain editing, and characterise the resulting ranking methods via a greedy approximation algorithm

Item Type:	Conference or Workshop Item (Paper)
Date Type:	Published Online
Status:	In Press
Schools:	Computer Science & Informatics
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Publisher:	IFAAMAS
ISBN:	9781450383073
ISSN:	2523-5699
Date of First Compliant Deposit:	4 March 2021
Date of Acceptance:	17 December 2020
Last Modified:	09 Nov 2022 10:23
URI:	https://orca.cardiff.ac.uk/id/eprint/139311

Actions (repository staff only)

Edit Item