A survey on the complexity of tournament solutions

Olivier Hudry

Mathematical Social Sciences, 2009, vol. 57, issue 3, 292-303

Abstract: In voting theory, the result of a paired comparison method such as the one suggested by Condorcet can be represented by a tournament, i.e.,a complete asymmetric directed graph. When there is no Condorcet winner, i.e.,a candidate preferred to any other candidate by a majority of voters, it is not always easy to decide who is the winner of the election. Different methods, called tournament solutions, have been proposed for defining the winners. They differ in their properties and usually lead to different winners. Among these properties, we consider in this survey the algorithmic complexity of the most usual tournament solutions: some are polynomial, some are NP-hard, while the complexity status of others remains unknown.

Keywords: Voting; theory; Tournament; solutions; Majority; tournament; Complexity (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (30)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0165-4896(08)00124-8
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:matsoc:v:57:y:2009:i:3:p:292-303

Access Statistics for this article

Mathematical Social Sciences is currently edited by J.-F. Laslier

More articles in Mathematical Social Sciences from Elsevier
Bibliographic data for series maintained by Catherine Liu ().