Chamberlin-Courant Approval Voting Rule (COMSOC)

Definition

Chamberlin-Courant Approval Voting Rule (COMSOC)

The Chamberlin-Courant approval voting rule selects a committee maximising the total voter satisfaction by representing each voter through their most-preferred committee member, i.e.,

Complexity

The Chamberlin-Courant approval voting rule is NP-complete.

Justified Representation

Justified Representation by Chamberlin-Courant Approval Voting Rule

The Chamberlin-Courant approval voting rule yields a justified representation.

Justified Representation by Chamberlin-Courant Approval Voting Rule

Let be a committee selected by the Chamberlin-Courant approval voting rule. Suppose, for contradiction, that does not satisfy justified representation.

Then there exists a cohesive voter group that is not represented by . Since is cohesive, by definition,

Since is not represented,

Hence none of the voters is represented by . Therefore at most

voters outside are represented.

Assign every represented voter to one committee member in that they approve. Since , these at most represented voters are distributed among committee members. By the generalised pigeonhole principle, some is assigned at most

voters.

Because ,

Thus there is a committee member whose removal can make fewer than voters unrepresented.

Since

choose some candidate

Moreover, , since otherwise every voter in would already be represented.

Consider the committee

Removing makes at most previously represented voters unrepresented, while adding represents all voters, because every voter in approves .

Since

the committee represents strictly more voters than .

This contradicts the assumption that maximises the Chamberlin-Courant score. Therefore every Chamberlin-Courant winning committee satisfies justified representation