A quality function for creating multiwinner voting systems ===============Warren D. Smith=====Feb 2014=============== One way to design a multiwinner voting system is to define a "quality function" which examines the votes, voters, candidates, and winners, and outputs a number. Then the voting system could simply be to choose the winner-set yielding maximum quality. (Finding that best subset might be computationally infeasible, but we ignore computational complexity issues for the moment.) We here will propose a quite general class of possible quality functions, which immediately yields an infinite set of new PR (proportional representation) multiwinner voting systems. OPEN QUESTIONS: A. Which among our functions is "the best"? B. Is it possible to generalize this still further in some reasonable way so that not only PR, but also TPC (Toby Pereira's Condition, see below) is satisfied? ----- Let C=#candidates, V=#voters, W=#winners, 0<W<C<V, and let S[v,c] be the real-valued score given by voter v to candidate c on her ballot. Then here is a highly general class of quality measures Q: Q = SUM(v=1..V) F( SUM(j=1..W) (jth greatest S[v,c] among winning c) * A[j] ) where A[1], A[2], A[3], ... are real numbers specified by voting system designer, and F(x) is a function specified by voting system designer. [Incidentally if F(x)=x, and A[1]=1 and A[j]=0 for j>1, then this quality measure would be maximizable in polynomial time.] If F(x)=x, then "proportional representation" (PR) will be assured by choosing A[j] = 1/(j+RealConstant). PR means: if all voters and candidates are different "colors" and each voter scores each same-color candidate 1, rest 0, then the proportion of color-X winners will come out the same as the proportion of color-X voters, for all X, up to at most constant additive errors in #winners. If A[j]=1 for all j, then we can instead obtain PR by using F(x)=K1+K2*log(x+K3) where K1,K2,K3 are any real constants with K2>0. But those were only two special cases. More generally, we can assure PR by choosing the A[j]>0 and F() such that SUM(j=1..m) F(A[j]) = K1+K2*log(m+K3) to good enough approximation. It seems intuitively preferable for the A[j] to be nonincreasing with j and F(x) to be increasing with x so below I'll only give examples obeying those. Then an infinite number of further examples include: 1. A[j] = j^(-P) for any fixed real P with 0<=P<1, and F(x) = log(x). 2. A[j] = j^(-1) and F(x) = x. 3. A[j] = 1/(j*ln(j+1)) and F(x) = exp(x) 4. A[j] = (1/j)*ln(j+1)^(P-1) for any fixed real P with 0<P, and F(x) = x^(1/P). Can any argument be made that some one among the above is "best" or anyhow better than others? But none of these examples, and apparently no quality function of this class, satisfies Toby Pereira's condition (TPC): AFTER universally-liked candidates win, then there must be proportionality about the remaining winners. So I think there is a theorem lurking here (conjecture for present) that no quality function of this quite-wide-seeming class, is capable of both PR and Pereira's post-universally-liked-winners criterion TPC. Which leads us to the question: is it even possible for ANY quality measure, or ANY voting system, to satisfy both criteria? (Pereira thinks he has one, but I doubt it.) One crude try would be something like this. 2-stage voting system. In its first stage, essentially you use a single-winner voting system like range voting to elect winners one at a time. You keep going until the next proposed winner drops below some threshold ("not universally liked enough"). Then you switch to a PR voting system for all the remaining candidates (who have not yet won). BUT this idea would still clearly fail a more-refined form of Toby Pereira's condition: After candidates universally liked among Pink voters only win, then the subfactions of the Pinks should then get proportional representation about future Pink winners. Another try (which technically works) would be to observe that the definition of "PR" is very silly and only applies when voters & candidates are split exactly into disjoint factions; and Pereira's definition of "universal winner" also is very silly ("silly" meaning, in reality, these requirements would essentially never be satisfied) and it is possible to exploit/abuse that silliness because the silly situations where these definitions apply do not overlap and hence cannot contradict. But the kind of quality measure Q proposed above does not exploit this silliness and hence cannot particularly abuse it, and then we conjecturally get a contradiction & impossibility. Can we generalize somehow Q further to try to satisfy TPC? One attempt might involve summation over PAIRS of candidates (and/or voters), not just single ones.