TY - JOUR AU - Brill, Markus AU - Schmidt-Kraepelin, Ulrike AU - Suksompong, Warut PY - 2020/04/03 Y2 - 2024/03/28 TI - Refining Tournament Solutions via Margin of Victory JF - Proceedings of the AAAI Conference on Artificial Intelligence JA - AAAI VL - 34 IS - 02 SE - AAAI Technical Track: Game Theory and Economic Paradigms DO - 10.1609/aaai.v34i02.5554 UR - https://ojs.aaai.org/index.php/AAAI/article/view/5554 SP - 1862-1869 AB - <p>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 <em>margin of victory (MoV)</em> 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.</p> ER -