[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

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