Proportional Winner Determination Decision Problem

Definition

Proportional Winner Determination Decision Problem

Given an approval election with candidate set , voters , approval sets , a committee size , and a rational score threshold , the proportional winner determination decision problem asks whether some size- committee reaches the threshold under Proportional Approval Voting (PAV).

Let

be the th harmonic number. For a committee , its PAV score is

Question: does

hold?

Certificate

A size- committee is a certificate. Compute for every voter and add . The resulting rational score can be compared with the binary-encoded threshold in polynomial time. For example, all denominators can be bounded by a common denominator built from , whose binary length is polynomial in .

Complexity

The problem belongs to NP. It is NP-hard by the reduction from Independent Set, and is therefore NP-complete.

The associated search problem asks for an optimal committee rather than merely asking whether a given score threshold is attainable.