Proportional Approval Voting Rule (COMSOC)

Definition

Proportional Approval Voting Rule (COMSOC)

The proportional approval voting rule selects a committee maximising the total voter satisfiaction while giving diminishing returns for each additional approved committee member

Complexity

The proportional approval voting rule is NP-complete.

Justified Representation

Justified Representation by Proportional Approval Voting Rule

The proportional approval voting rule yields a justified representation.

Justified Representation by Proportional Approval Voting Rule

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

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

Since is not represented,

For every voter , let

denote the number of approved committee members. If an elected candidate is removed, the PAV contribution of decreases from

to

Hence removing such a candidate decreases the score of by exactly

For each , let denote the total PAV score lost by removing :

Consider the sum of these losses over all committee members. A represented voter approves exactly members of and therefore contributes

to

An unrepresented voter contributes . Since none of the voters in is represented, at most voters contribute. Therefore

Since , the generalised pigeonhole principle implies that some satisfies

Because ,

Hence,

Since is cohesive,

so choose

Since is not represented by , we have .

Now consider the committee

Removing decreases the PAV score by . Adding gives every voter in their first approved committee member, so each gains PAV score

Therefore adding increases the PAV score by at least

Since

we obtain

contradicting the optimality of .

Therefore every committee selected by proportional approval voting satisfies justified representation

Extended Justified Representation

Extended Justified Representation by Proportional Approval Voting Rule

The proportional approval voting rule yields a extended justified representation.