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

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 [Formula: see text] satisfies a weak (resp. strong) Condorcet criterion–i.e., if [Formula: see text] 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.