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

Area of Science:

• Computational Social Choice
• Decision Theory
• Voting Theory

Background:

• Assessing the quality of committees based on individual preferences is a key challenge in social choice theory.
• Existing methods often rely on specific voting rules, but their computational complexity is not fully understood.

Purpose of the Study:

• To establish the computational complexity of deciding committee quality.
• To analyze the efficiency of determining if a committee satisfies weak or strong Condorcet criteria.
• To differentiate between computationally tractable and intractable instances across various voting rules.

Main Methods:

• Analyzing computational complexity using individual preferences over alternatives.
• Adapting scoring functions from classic voting rules for pairwise committee comparisons.
• Investigating the conditions for weak and strong Condorcet criterion satisfaction.

Main Results:

• Identified a sharp separation between computationally tractable and intractable instances for different voting rules.
• Demonstrated that deciding on committee quality under weak and strong Condorcet criteria is computationally hard.
• Showcased the complexity of determining the existence of a Condorcet-satisfying committee.

Conclusions:

• The problem of determining committee quality and the existence of committees satisfying Condorcet criteria is computationally challenging.
• The complexity varies significantly depending on the specific voting rule employed.
• Further research is needed to develop efficient algorithms or understand the inherent limitations for specific voting scenarios.