[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/

Election-Methods mailing list - see http://electorama.com/em for list info

Re: [EM] Multiwinner Election Algorithm

[peter barath]

 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.


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


Let's try it. Let's take the simplest situation where there are
non-adjacent sets. The minimum for this is 4 candidates (ABCD),
2 seats.

For the simplicity, we suppose the rating can be between
0 to 1. Our voters will all vote approval-style, that is all
0 and 1 ratings. And each of them will vote for exactly two
candidates.

For example, AB and CD are non-adjacent sets. Let's try it
with 2 voters, one votes AB, one CD.

The situation is quite simmetrical, so we just compare
sets AB and BC for the example. The utility for the AB set
is  ln(1+2)  from the AB voter and zero from the CD voter.
The utility for the BC set is  ln(1+1)  from the AB voter
and another  ln(1+1)  from the CD voter.

That is, the utility for the AB set is  ln(3)  and the
utility for the BC set is  2*ln(2) = ln(4)  so this is not
a counter-example, the non-adjacent AB and CD are not local
maxima; the principle of many dwarfs are stronger than a
few giants worked.

So let's try it ortogonally. Now let's have all kind of
voters except AB and CD. So we have four voters, each of
them votes for one candidate from the AB group and one from
the CD group.

So we have voters  AC,AD,BC,BD.

Now, for example the AB group means partial utility for all
four voters, while for example BC means more utility for
the BC voter, but nothing for the AD voter.

The AB set means  ln(1+1)  for all four voters, so its full
utility is  4*ln(1+1) = ln(16)

The BC set means  ln(1+2)  for the BC voter,  ln(1+1)  for
the AC voter, also  ln(1+1)  for the BD voter and zero
for the AD voter.

All together  ln(3) + 2*ln(2) = ln(3) + ln(4) = ln(12)

Similarly for the others, so the utilities for the sets:

AB ln(16)
AC ln(12)
AD ln(12)
BC ln(12)
BD ln(12)
CD ln(16)

The non-adjacent AB and CD are local maxima.

Peter Barath

brElindult a Genertel 
lakásbiztosítása!brSzámítsa ki díját, kösse meg lakásbiztosítását online, 
néhány perc alatt.br1 év lakás assistance szolgáltatást most ingyen 
adunk!brhttp://ad.adverticum.net/b/cl,1,6022,340633,421168/click.prm



Election-Methods mailing list - see http://electorama.com/em for list info

Re: [EM] Redistricting, now with racial demographics

[Aaron Armitage]

--- On Mon, 7/20/09, Raph Frank raph...@gmail.com wrote:

  I would think that presetting the desired boundaries
 would avoid that.
 
 Pre-set boundaries have the disadvantage that the lead to
 imbalances
 in the voter to seat ratios.
 
 A 5 seat district could have a population of anywhere
 between 4.5 and
 5.5 of the national average (roughly).  This gives a
 potential
 imbalance of +/- 10%.
 

I didn't mean presetting the entire shape of any district, just the line
along whatever geographic or cultural divide we think districts shouldn't
cross. The program will draw the other lines to equalize population and
maximize whichever value (compactness, distance from the geographical
center, travel time, etc.) we make our standard for good districts.

 Ofc, if the districts are very large, then this is less of
 an issue.
 Also, the elimination of gerrymandering might be worth the
 slight
 imbalance.
 
 The imbalance is worst when the districts are small. 
 One option is to
 have a process for combining smaller districts.
 
 For example, any district which has less than 5 seats is
 combined with
 a neighbour.  Once that is done, any district with
 more than 12 seats
 is split in 2 so that each part has at least 5 seats.
 
 Ofc, that would like not be acceptable in the US, assuming
 by
 district, you mean State.
 

I mean geographical divisions that exist solely to designate which voters
will fill a seat or set of seats. A state may also serve that function,
but that's not the reason it exists. Your intuition is right: merging and
splitting states to create a desired magnitude (in the House elections,
presumably) wouldn't be acceptable to the general public, because that's
not what states are for. Actually, I don't really see much to be gained
from it even in situations where the designer has a free hand to set
district lines. It seems better to me to equalize the magnitudes and
adjust the lines (or draw them de novo after every census) to keep them
equal. In the context of House elections in America that's complicated by
the fact that each state is apportioned a number of Representatives based
on population, but within each state the districts could be of the same
magnitude, with any remainder elected at-large. (Although at the current
size of the House most states won't even need districts to use standard
STV.)

  [if both used PR-STV] I see no reason for having two
 houses, in that case.
 
 It probably depends on how you do it.
 
 In the US, you could in principle elect the 2 Senators
 using PR-STV
 and the N Representatives using PR-STV.
 
 This would mean that there is still an imbalance between
 the 2 Houses,
 due to the population imbalance between the States.
 
 Another option is longer terms.
 
 For example, you could expand the terms for the
 Senate.  If you
 elected 5 Senators by PR-STV, every 2 years, for a 20 year
 term, then
 that would give you a 50 member Senate.
 
 The House could also be elected by PR-STV, but as a single
 block.
 
 The effect would be that the Senate is more stable (as it
 is the
 average viewpoint over a 20 year period), while the House
 would be a
 snap-shot.  Also, at any time at most 10% of the
 Senate would be
 seeking re-election, so it would be less subject to short
 terrm
 election planning.  Ofc, with 20 year terms, many
 Senators would
 probably just seek 1 term.
 
 This may lead to the Senate being considered old and wise
 or maybe
 just massively corrupt due to the lack of having to stand
 for
 re-election.
 
 In Ireland, the Seanad doesn't have veto powers over
 legislation.  It
 only has the ability to delay legislation for 180
 days.  It isn't
 actually very powerful anyway, as the Government has the
 right to
 appoint 11 members (out of 60), so they always have a
 majority in the
 Seanad (though at the moment, their majority is zero, so
 they rely on
 the Chairman's casting vote).
 
 I would also add a rule that Senators and Representatives
 can't become
 members of the other House for at least 5 years after they
 have left
 their original house.  This is to try to encourage
 different types of
 people to stand for each House.


That's an interesting idea, although I doubt many American voters would
be willing to accept such long terms. Perhaps something like that,
combined with a power to veto legislation or at least call early
elections for Commons, would be a suitable reform (or replacement) for
the the House of Lords in the UK.


  

Election-Methods mailing list - see http://electorama.com/em for list info