Refining tournament solutions via margin of victory
Tournament solutions are frequently used to select winners from a set of alternatives based on pairwise comparisons between alternatives. 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 prop...
| Main Authors: | , , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
Association for the Advancement of Artificial Intelligence
2020
|
| _version_ | 1797082791993671680 |
|---|---|
| author | Brill, M Schmidt-Kraepelin, U Suksompong, W |
| author_facet | Brill, M Schmidt-Kraepelin, U Suksompong, W |
| author_sort | Brill, M |
| collection | OXFORD |
| description | Tournament solutions are frequently used to select winners from a set of alternatives based on pairwise comparisons between alternatives. 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 (MoV) for tournament solutions. MoV is a robustness measure for individual alternatives: For winners, the MoV 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 MoV and provide worst-case bounds on the MoV for both winners and non-winners. Our results can also be viewed from the perspective of bribery and manipulation. |
| first_indexed | 2024-03-07T01:32:52Z |
| format | Conference item |
| id | oxford-uuid:942e766c-44a9-48c5-9616-73efc2c8d489 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T01:32:52Z |
| publishDate | 2020 |
| publisher | Association for the Advancement of Artificial Intelligence |
| record_format | dspace |
| spelling | oxford-uuid:942e766c-44a9-48c5-9616-73efc2c8d4892022-03-26T23:37:37ZRefining tournament solutions via margin of victoryConference itemhttp://purl.org/coar/resource_type/c_5794uuid:942e766c-44a9-48c5-9616-73efc2c8d489EnglishSymplectic Elements at OxfordAssociation for the Advancement of Artificial Intelligence2020Brill, MSchmidt-Kraepelin, USuksompong, WTournament solutions are frequently used to select winners from a set of alternatives based on pairwise comparisons between alternatives. 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 (MoV) for tournament solutions. MoV is a robustness measure for individual alternatives: For winners, the MoV 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 MoV and provide worst-case bounds on the MoV for both winners and non-winners. Our results can also be viewed from the perspective of bribery and manipulation. |
| spellingShingle | Brill, M Schmidt-Kraepelin, U Suksompong, W Refining tournament solutions via margin of victory |
| title | Refining tournament solutions via margin of victory |
| title_full | Refining tournament solutions via margin of victory |
| title_fullStr | Refining tournament solutions via margin of victory |
| title_full_unstemmed | Refining tournament solutions via margin of victory |
| title_short | Refining tournament solutions via margin of victory |
| title_sort | refining tournament solutions via margin of victory |
| work_keys_str_mv | AT brillm refiningtournamentsolutionsviamarginofvictory AT schmidtkraepelinu refiningtournamentsolutionsviamarginofvictory AT suksompongw refiningtournamentsolutionsviamarginofvictory |