Margin of victory for tournament solutions
From MaRDI portal
Publication:2060724
Abstract: 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.
Recommendations
Cites work
- A Constructive Solution to a Tournament Problem
- A note on the McKelvey uncovered set and Pareto optimality
- A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems
- A refinement of the uncovered set in tournaments
- A survey on the complexity of tournament solutions
- Banks winners in tournaments are difficult to recognize
- Bounds on the disparity and separation of tournament solutions
- Choosing from a large tournament
- Combinatorial optimization. Theory and algorithms.
- Control and bribery in voting
- Extending tournament solutions
- Finding minimum-cost circulations by canceling negative cycles
- Fixing balanced knockout and double elimination tournaments
- scientific article; zbMATH DE number 806748 (Why is no real title available?)
- scientific article; zbMATH DE number 3353312 (Why is no real title available?)
- Length-bounded cuts and flows
- Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
- Manipulating Tournaments in Cup and Round Robin Competitions
- Margin of victory for tournament solutions
- Max flow and min cut with bounded-length paths: complexity, algorithms, and approximation
- Maximal Flow Through a Network
- NON-NULL RANKING MODELS. I
- On a Problem in Graph Theory
- On finding a minimum dominating set in a tournament
- On limited nondeterminism and the complexity of the V-C dimension
- On the complexity of bribery and manipulation in tournaments with uncertain information
- On the discriminative power of tournament solutions
- On the evaluation of election outcomes under uncertainty
- On the structure of stable tournament solutions
- Possible and necessary winners of partial tournaments
- Possible winner problems on partial tournaments: a parameterized study
- Robust bounds on choosing from large tournaments
- The minimal covering set in large tournaments
- Tournament games and positive tournaments
- Tournament solutions
- Tournament solutions and majority voting
- Who can win a single-elimination tournament?
Cited in
(7)- Margin of victory for tournament solutions
- Tournament solutions based on cooperative game theory
- Fixing knockout tournaments with seeds
- Query complexity of tournament solutions
- On the parameterized complexity of controlling amendment and successive winners
- Smallest tournaments not realizable by \({\frac{2}{3}}\)-majority voting
- On the complexity of bribery and manipulation in tournaments with uncertain information
This page was built for publication: Margin of victory for tournament solutions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2060724)
