[EM] Some chance for consensus (was: Buying Votes)

[fsimmons at pcc.edu]

Perhaps the equilibrium could be made stable by use of two ballots instead of one.  This would probably entail some cost in performance, but it might beat our previous record.How about this, for example?For each candidate X, let r(X) be the average rating of X over all ballots.Draw two ratings ballots at random.For each candidate X let m(X) be the minimum rating of candidate X on the two drawn ballots.Let M be the max over X (in the set of candidates) of min(X).If M>0, then elect a candidate X such that min(X)=M. (Use a tie breaker if this equation has more than one solution.)Else elect the favorite of the first drawn ballot.Perhaps the last step could be replaced byElse elect the candidate with the highest value of v(X)*r(X), where v is the first drawn ballot.But that is a lot to wish for.Best,Forest----- Original Message -----From: Jobst Heitzig Date: Saturday, November 1, 2008 8:26 pmSubject: Re: [EM] Some chance for consensus (was:  Buying Votes)To: fsimmons at pcc.eduCc: gregory.nisbet at gmail.com, election-methods at lists.electorama.com, jacobltaylor at gmail.com> Hello again,> > maybe it *is* possible after all to have a monotonic method > which > provides for strategic equilibria in which C is elected with > 100%, 55%, > and 100% probability, respectively, in the following situations:> > Situation 1:>    55% A(100)>C(70)>B(0)>    45% B(100)>C(70)>A(0)> > Situation 2:>    30% A(100)>C(70)>B,D(0)>    25% B(100)>C(70)>A,D(0)>    45% D(100)>A,B,C(0)> > Situation 3:>    32% A(100)>C(40)>B,D(0)>    33% B(100)>C(40)>A,D(0)>    35% D(100)>C(40)>A,B(0)> > (All these being sincere utilities)> > > The method is surprisingly simple:> > 1. Each voters assigns a rating between 0 and 1 to each option.> 2. For each option, the mean rating is determined.> 3. A ballot is drawn at random.> 4. For each option, the "score" of the option is the option's > rating on > the drawn ballot times its mean rating determined in step 2.> 5. The winner is the option with the highest score. In case of > ties, the > mean rating is used to decide between the tied options.> > First of all, the method is obviously monotonic by definition > since both > the mean and product operations are monotonic.> > Also, if a faction of p% bullet-votes for some option X (giving > it 100 > and all others 0), that option gets at least p% winning > probability > since whenever one of those ballots is drawn, X gets a score >0 > and all > others get a score of 0.> > Now let us analyse the equilibria in the above situations.> > Situation 1:>    55% A(100)>C(70)>B(0)>    45% B(100)>C(70)>A(0)> Put>    a = .55>    b = .45>    x = a / sqrt(a²+b²)>    y = b / sqrt(a²+b²)> The claimed equilibrium is this:>    The first 55% of the voters rate A(1)>C(x)>B(0),>    the other 45% of the voters rate B(1)>C(y)>A(0).> The mean ratings are>    A: a*1+b*0 = a>    B: a*0+b*1 = b>    C: a*x+b*y = sqrt(a²+b²)> If one of the first 55% ballots is drawn, the scores are>    A: 1*a           = a>    B: 0*b           = 0>    C: x*sqrt(a²+b²) = a> so C wins since it has a larger mean rating than A.> Likewise, if one of the other 45% ballots is drawn, the scores are>    A: 0*a           = 0>    B: 1*b           = b>    C: y*sqrt(a²+b²) = b> so C wins since it has also a larger mean rating than B.> No voter has an incentive to change her rating of C: increasing > it > doesn't change a thing; decreasing it would make C's score > smaller than > the favourite's score no matter what ballot is drawn, so the > resulting > winning probabilities become A(.55), B(.45), C(0) which is not > preferred > to A(0), B(0), C(1) by anyone.> > Situation 2:>    30% A(100)>C(70)>B,D(0)>    25% B(100)>C(70)>A,D(0)>    45% D(100)>A,B,C(0)> Put>    a = .30>    b = .25>    x = a / sqrt(a²+b²)>    y = b / sqrt(a²+b²)> The claimed equilibrium is this:>    30% rate A(1)>C(x)>B,D(0)>    25% rate B(1)>C(y)>A,D(0)>    45% rate D(1)>A,B,C(0)> The mean ratings are>    A: a*1     = a>    B: b*1     = b>    C: a*x+b*y = sqrt(a²+b²)>    D: .45> If one of the first 30% ballots is drawn, the scores are>    A: 1*a           = a>    B: 0*b           = 0>    C: x*sqrt(a²+b²) = a>    D: 0*.45         = 0> so again C wins since it has a larger mean rating than A.> It's similar for the 25%. When one of the 45% is drawn, D is elected.> Again, no voter can gain anything by increasing or decreasing > her C-rating.> > Situation 3:>    32% A(100)>C(40)>B,D(0)>    33% B(100)>C(40)>A,D(0)>    35% D(100)>C(40)>A,B(0)> Put>    a = .32>    b = .33>    d = .35>    x = a / sqrt(a²+b²+d²)>    y = b / sqrt(a²+b²+d²)>    z = d / sqrt(a²+b²+d²)> The claimed equilibrium is this:>    32% rate A(1)>C(x)>B,D(0)>    33% rate B(1)>C(y)>A,D(0)>    35% rate D(1)>C(z)>A,B(0)> The mean ratings are>    A: a*1         = a>    B: b*1         = b>    C: a*x+b*y+d*z = sqrt(a²+b²+d²)>    D: d*1         = d> If one of the first 32% ballots is drawn, the scores are>    A: 1*a              = a>    B: 0*b              = 0>    C: x*sqrt(a²+b²+d²) = a>    D: 0*d              = 0> so still C wins since it has a larger mean rating than A.> It's again similar for the other voters, and still no voter can > gain > anything by increasing or decreasing her C-rating.> > > Problems:> > (a) The stated equilibria are not exactly stable since already a > deviation on the part of one faction gives a different faction > the means > to manipulate the scores so that C wins when a ballot from the > first > faction is drawn but not when a ballot from their own faction is > drawn. > This problem might be bigger or smaller when faction don't know > their > respective sizes.> > (b) The meaning of the asked-for ratings is not clear. Maybe > their > meaning can only be defined operational by pointing out how they > are > used in the method. It seems they cannot naively be interpreted > as > utilities. All this makes it difficult to tell what a "sincere" > rating > would be.> > (c) It would be nice if the score formula could somehow be > changed so > that the equilibrium ratings would not include the normalization > factor > 1/sqrt(...). But I fear that this is not possible. I tried to > use the > minimum of the individual and the mean score instead of their > product, > but that did not result in any equilibria at all. Using a sum or > maximum > instead of the product would destroy the bullet-voting property. > Also, > using (individual rating)^(some exponent) * (mean rating) does > not help. > More ideas I did not have yet. Perhaps the mean rating must be > replaced > by some other location statistic such as the median rating. Or > perhaps > we somehow include the Q-quantile of the ratings, where Q is the > rating > on the drawn ballot...> > > Any thoughts?> > Jobst> > > Jobst Heitzig schrieb:> > Hi folks,> > > > I think I know what the problem is with the idea of somehow > > automatically match pairs or larger groups of voters who will > all > > benefit from a probability transfer: It cannot be monotonic > when it > > requires that the ballots of all members of the matched group > indicate > > that the respective voter profits from the transfer.> > > > Look at the simplest version where we have only two voters who > submit > > favourite and approved information:> > > > Situation I:> > Voter 1: A favourite, C also approved> > Voter 2: B favourite, C also approved> > > > If we interpret the approval information as an indication that > the > > voters like C better than tossing a coin between A and B, we > would be > > tempted to let the method match these voters and transfer both > their > > winning probabilities from their favourites to C. So C will > win with > > certainty.> > > > But if we want monotonicity also, C must still win with > certainty in the > > following situation:> > > > Situation II:> > Voter 1: C favourite, A also approved> > Voter 2: B favourite, C also approved> > > > But in this situation, a matching algorithm would *not* match > the voters > > since voter 2 obviously does not seem to profit from such a > transfer.> > > D2MAC and FAWRB don't have this problem: they are not based on > matching > > and *do* elect C with certainty in situation II. For this > reason, voter > > 2 would have incentive *not* to approve of C in situation II > when D2MAC > > or FAWRB is used. It seems the monotonicity is paid for by a > need for a > > bit more of information in order to vote strategically efficient.> > > > A similar argument shows why it is so difficult to solve the > following > > situation:> > > > Situation III:> > Voter 1: A1 favourite, A also approved> > Voter 2: A2 favourite, A also approved> > Voter 3: B favourite> > > > Suppose we want our method to give A a winning probability of > 2/3 in > > this situation. Then we have a problem in the following situation:> > > > Situation IV:> > Voter 1: A favourite, D also approved> > Voter 2: B favourite, D also approved> > Voter 3: C favourite, D also approved> > > > Here each of the three voters would have an incentive to > change her > > ballot and *not* approve of D, since that would move 1/3 of > the winning > > probability from D to her favourite. So, the strategic > equilibria in > > situation IV will be> > > > Voter 1: A favourite> > Voter 2: B favourite, D also approved> > Voter 3: C favourite, D also approved> > > > or> > > > Voter 1: A favourite, D also approved> > Voter 2: B favourite> > Voter 3: C favourite, D also approved> > > > or> > > > Voter 1: A favourite, D also approved> > Voter 2: B favourite, D also approved> > Voter 3: C favourite> > > > each of which won't result in D being elected with certainty.> > > > So, it seems we can't have efficient cooperation in both > situations III > > and IV!> > > > Situation IV seems to be the more important, and D2MAC and > FAWRB both > > make sure that in situation IV full cooperation is both an > equilibrium > > and efficient. But for this they need to give A less than 2/3 > in > > situation III, however.> > > > Yours, Jobst> > > > > > > > fsimmons at pcc.edu schrieb:> >> What do I think?  All of these ideas are better than what I > have come > >> up with, and have great potential, whether or not they might > need some > >> tweaking or even major over haul.> >>  > >> I'll try to digest them more in the mean time, to get a > better feel > >> for their strengths and potential weaknesses.> >>  > >> Marriage and matching procedures certainly seem natural in > this setting.> >>  > >> Thanks,> >>  > >> Forest> >>> >>> >>> > ----> > Election-Methods mailing list - see http://electorama.com/em > for list info> 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20081105/ef9c9785/attachment-0003.htm>