How hard is it to tell which is a Condorcet committee?

Andreas Darmann

Mathematical Social Sciences, 2013, vol. 66, issue 3, 282-292

Abstract: This paper establishes the computational complexity status for a problem of deciding on the quality of a committee. Starting with individual preferences over alternatives, we analyse when it can be determined efficiently if a given committee C satisfies a weak (resp. strong) Condorcet criterion–i.e., if C is at least as good as (resp. better than) every other committee in a pairwise majority comparison. Scoring functions used in classic voting rules are adapted for these comparisons. In particular, we draw the sharp separation line between computationally tractable and intractable instances with respect to different voting rules. Finally, we show that deciding if there exists a committee which satisfies the weak (resp. strong) Condorcet criterion is computationally hard.

Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0165489613000565
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:66:y:2013:i:3:p:282-292

DOI: 10.1016/j.mathsocsci.2013.06.004

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 ().