> 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 ---- Election-Methods mailing list - see http://electorama.com/em for list info
