The Library
Margin of victory for tournament solutions
Tools
Brill, Markus, Schmidt-Kraepelin, Ulrike and Suksompong, Warut (2022) Margin of victory for tournament solutions. Artificial Intelligence, 302 . 103600. doi:10.1016/j.artint.2021.103600 ISSN 0004-3702.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1016/j.artint.2021.103600
Abstract
Tournament solutions are frequently used to select winners from a set of alternatives based on pairwise comparisons between them. Prior work has shown that several common tournament solutions tend to select large winner sets and therefore have low discriminative power. In this paper, we propose a general framework for refining tournament solutions. In order to distinguish between winning alternatives, and also between non-winning ones, we introduce the notion of margin of victory () for tournament solutions. is a robustness measure for individual alternatives: For winners, the captures the distance from dropping out of the winner set, and for non-winners, the distance from entering the set. In each case, distance is measured in terms of which pairwise comparisons would have to be reversed in order to achieve the desired outcome. For common tournament solutions, including the top cycle, the uncovered set, and the Banks set, we determine the complexity of computing the and provide bounds on the for both winners and non-winners. We then reveal a number of structural insights on the by investigating fundamental properties such as monotonicity and consistency with respect to the covering relation. Furthermore, we provide experimental evidence on the extent to which the notion refines winner sets in tournaments generated according to various stochastic models. Our results can also be viewed from the perspective of bribery and manipulation.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||
Journal or Publication Title: | Artificial Intelligence | ||||||||
Publisher: | Elsevier | ||||||||
ISSN: | 0004-3702 | ||||||||
Official Date: | January 2022 | ||||||||
Dates: |
|
||||||||
Volume: | 302 | ||||||||
Article Number: | 103600 | ||||||||
DOI: | 10.1016/j.artint.2021.103600 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |