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