Chamberlin-Courant Winner Determination Search Problem

Definition

Chamberlin-Courant Winner Determination Search Problem

Given an approval election with candidate set , voters , approval sets , and a committee size , output a size- committee that maximises the Chamberlin-Courant score:

If several committees attain the maximum, outputting any one of them is valid. Thus the output is one committee tied for the maximum score, not necessarily the complete set of tied committees.

Evaluating a Committee

For a proposed committee , the score is the number of voters whose approval set intersects :

where when the predicate is true and otherwise. Hence evaluating one proposed committee is polynomial; the difficulty is finding a committee with maximum score.

Complexity

The search problem is NP-hard when is part of the input. A polynomial-time algorithm for it would also solve the decision problem: compute an optimal committee and compare its score with the requested threshold.

An exhaustive algorithm examines all committees. With and , scoring every committee by scanning all approval sets takes

time under an explicit representation of the approval sets. This is polynomial for fixed , but not when varies with the input.