[EM] Multiwinner Election Algorithm

[Greg Nisbet]

Reweighted Range Voting http://rangevoting.org/RRV.html does not check every
possible combination of candidates. However there may be a way to determine
the optimal candidate quickly.

Set X and set Y are adjacent if it is possible to create one group by
changing a single candidate in the other. …in other words, all the members
are identical but one.

Set X is a local maximum if the utility of every adjacent set is less than
Set X’s utility.

The utility function is rather simple.


for each voter, the utility is ln(1+score_sum/max)

 with score_sum being the score they gave each candidate individually and
max being the maximum rating allowable for a single candidate.

This is taken from the D'hondt divisors 1+1/2+1/3..., but integrated rather
than summed.

presumably ln(1+2*score_sum/max) would work as well.


>From a few tests I’ve run, it seems as if there’s never more than one local
maximum. Naturally, this single local maximum would be the optimal candidate
set.

This suggests that a simple iterative procedure will determine the optimal
candidate set without examining all of them. (Perhaps using Reweighted Range
Voting or Naive Multiwinner Range as a starting point)

I, however, lack the expertise to prove whether it is possible for multiple
local maxima to occur. I was wondering if anyone could.

This method is called Proportional Range Voting due to its resemblance to
Proportional Approval Voting
http://www.knowledgerush.com/kr/encyclopedia/Proportional_approval_voting/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20090721/0e5b6f6c/attachment-0002.htm>