Re: [EM] Some chance for consensus (was: Buying Votes)
Dear Jobst, Thanks for your clarifications, especially the key words, "...that do not approve X at least as strongly." Can we summarize the operational meaning of a rating R for X more simply than the following? If you rate option X at a level R, then, provided X is the option with the "greatest potential for compromise" (among those options that remain to be considered) you certify your willingness to give your vote to X as long as no more than R of the remaining ballots fail to give their vote to X. "Greatest Potential for Compromise" is to be measured by the number of (remaining?) ballots that give partial approval. Alternatively, we could say that option X has the maximum potential for compromise when R(X) (defined below) is minimal: For each option X, let R(X) be the minimum of the set of R such that at most R of the (remaining?) ballots approve X at a level of R or below. Would any of these variations (remaining vs original or R(X) vs partial approval) in defining max potential for compromise, destroy monotonicity? EC6 is good, or perhaps FC6, for Fair Chance Choice with Controlled Cooperation for Consensus or Compromise. Thanks, Forest - Original Message - From: Jobst Heitzig Date: Saturday, November 8, 2008 5:45 pm Subject: Re: [EM] Some chance for consensus (was: Buying Votes) To: [EMAIL PROTECTED] Cc: election-methods@lists.electorama.com, [EMAIL PROTECTED], Kristofer Munsterhjelm , Raph Frank > Dear Forest, > > you wrote: > > This reminds me of your two urn method based on approval ballots: > > Initialize with all ballots in the first urn. > > While any ballots are left in the first urn ... > > find the approval winner X of these remaining ballots > > circle candidate X on all of the ballots in the first urn > that > > approve candidate X, and then transfer them to the second urn. > > End While > > Elect the circled candidate on a randomly drawn ballot from > the > > second urn. > > Yes, it's inspired by that method which was due not to me but to > someone else, I think. > The important difference is, though, that in the above method > there will never be full cooperation since as long as the two > largest approval scores are more than 1 point apart, every voter > approving but not favouring the approval winner has an incentive > to remove her approval for the approval winner. In particular, > the equilibria in our 55/45 situation would look like the > following, with x+y=56: > 55-x: A > x: A+C > y: B+C > 45-x: B > So with the above method, C would win only with probability 56%. > > In the new suggestion, in contrast, the voters can make sure > that the "contract" to elect C only becomes effective when all > voters cooperate: Knowing that everybody prefers C to the Random > Ballot lottery, they can all rate C at 1. > > > It looks like your newest method is a variation where > "Approval" is > > interpreted as "positive rating," > > "partial approval" I would call it. The rating can be > interpreted not as a utility value but as a "limit on non- > cooperation". Or, the other way around, the value 100 minus the > rating can be interpreted as a "cooperation threshold". I got > the idea for this when reading the Wikipedia article on the > National Popular Vote Interstate Compact which has a very > similar provision making sure that signing the contract is > "safe" even when it is not known in advance who exactly the > other participants will be! > > > and X is circled only on those > > ballots that rate X sufficiently high* relative to the number > of ( > > remaining) ballots that do not approve X. > > ...That do not approve X *at least as strongly*. This is > important! Otherwise there would alway be an incentive to use > only the values 100 (for the favourite only), 1, and 0: Rating > an option 1 would then lead to other voters who have a higher > rating transfer their probability, without me transferring it, > too. Therefore the requirement is that a voter with rating R > only transfers her probability if more than 100-R percent of all > voters do so, too! This gives me a possibility to specify a > "safe" rating without exactly knowing who will be the other > cooperating voters. > > > If 99% of the (remaining) ballots do not approve X, then X is > circled > > only on those ballots that rate X above 99%. If less than 1% > of the ( > > remaining) ballots do not approve X, then even a ballot that > rates X > > at a mere 1% would get a circle around X. > > Right! > > > The exact relation between the required rating
Re: [EM] Some chance for consensus (was: Buying Votes)
, Jobst > Does that capture the idea? > > Forest > > > - Original Message - > From: Jobst Heitzig > Date: Thursday, November 6, 2008 3:37 pm > Subject: Re: [EM] Some chance for consensus (was: Buying Votes) > To: [EMAIL PROTECTED] > Cc: [EMAIL PROTECTED], election-methods@lists.electorama.com, > Raph Frank , Kristofer Munsterhjelm > > > Hi again, > > > > here's another, somewhat more stable method which also achieves > > the > > following: > > > > > ... > > > 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 idea is that for each possible compromise option C, a voter > > indicates, by a rating on her ballot, how many voters she > > requires to > > transfer their winning probability to C before she will do so, too. > > > > > > This is the method: > > > > 1. Each of the N voters rates on her ballot each option between > > 0 and 100. > > > > 2. For each option X, put > > s(X) = no. of ballots rating X at zero. > > > > 3. Put all ballots into a first urn labelled U1, and have > > another urn > > labelled U2, initially empty. > > > > 4. For each option X, in order of ascending s(X), do the following: > > > > 4.1 Find the smallest number R for which f(R) >= 100, where > > f(R) = R + 100 * (no. of ballots in U1 rating X above R) / N. > > > > 4.2 For each ballot in U1 rating X above R: Mark X on that > > ballot and > > move the ballot from U1 to U2. > > > > 5. On each of the ballots that remained in U1, mark the option > > with the > > highest rating on that ballot and also put the ballot into U2. > > > > 6. Draw one ballot at random. The option marked on that ballot wins. > > > > > > (By "above", we mean strictly above and not equal, of course.) > > > > If there is only one compromise option C besides some polar > > favourite > > options A,B,... , the method essentially simplifies to this: > > - Find the smallest R such that at least 100-R percent of the > > ballots > > rate C above R. > > - Then draw a ballot at random. If it rates C above R, C wins, > > otherwise > > the option with the largest rating of that ballot wins. > > > > > > Let's look at the three example situations: > > > > Situation 1 (sincere utilities): > > 55: A(100)>C(70)>B(0) > > 45: B(100)>C(70)>A(0) > > > > Take any pair of numbers x,y such that > > > > 0 <= x <= 55, > > 0 <= y <= 45, > > x + y > 55, > > x > 3y/7, and > > y > 3x/7. > > > > It is easy to check from the above true ratings that then all > > voters > > would gain if x of the A-voters and y of the B-voters > > transferred their > > winning probability to C. The voters can make sure this happens > > in the > > suggested method by voting this way: > > > > 55-x: A(100)>C(0)=B(0) > > x: A(100)>C(101-x-y)>B(0) > > y: B(100)>C(101-x-y)>A(0) > > 45-y: B(100)>C(0)=A(0) > > > > The method would begin with C (receiving the smallest numbers of > > 0-rates), find R=100-x-y, and mark C on all the x+y ballots, > > resulting > > in these winning probabilities: A:55-x, B:45-y, C:x+y. > > > > No voter has an incentive to reduce her C-rating since that > > would > > immediately move R to 100 and C's winning probability to 0. > > > > So, for each such pair (x,y), the above way of voting is a > > strategic > > equilibrium, the socially best of whose is the one where x=55 > > and y=45, > > C wins with certainty, and the ballots look like this: > > > > 55: A(100)>C(1)>B(0) > > 45: B(100)>C(1)>A(0) > > > > > > Situation 2 (sincere utilities): > > 30: A(100)>C(70)>B,D(0) > > 25: B
Re: [EM] Some chance for consensus (was: Buying Votes)
Jobst, This reminds me of your two urn method based on approval ballots: Initialize with all ballots in the first urn. While any ballots are left in the first urn ... find the approval winner X of these remaining ballots circle candidate X on all of the ballots in the first urn that approve candidate X, and then transfer them to the second urn. End While Elect the circled candidate on a randomly drawn ballot from the second urn. It looks like your newest method is a variation where "Approval" is interpreted as "positive rating," and X is circled only on those ballots that rate X sufficiently high* relative to the number of (remaining) ballots that do not approve X. If 99% of the (remaining) ballots do not approve X, then X is circled only on those ballots that rate X above 99%. If less than 1% of the (remaining) ballots do not approve X, then even a ballot that rates X at a mere 1% would get a circle around X. The exact relation between the required rating relative to the lack of approval (on the remaining ballots) can be played with to get variations of this method. In this method there is no need to rate any candidate that the voter cannot conceive of as a compromise. Therefore it seems quite natural to consider positive rating as some level of approval. *Some provision must be made for ties and for the case where no ballot rates the current X high enough to get transfered into the second urn. Does that capture the idea? Forest - Original Message - From: Jobst Heitzig Date: Thursday, November 6, 2008 3:37 pm Subject: Re: [EM] Some chance for consensus (was: Buying Votes) To: [EMAIL PROTECTED] Cc: [EMAIL PROTECTED], election-methods@lists.electorama.com, Raph Frank , Kristofer Munsterhjelm > Hi again, > > here's another, somewhat more stable method which also achieves > the > following: > > > ... > > 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 idea is that for each possible compromise option C, a voter > indicates, by a rating on her ballot, how many voters she > requires to > transfer their winning probability to C before she will do so, too. > > > This is the method: > > 1. Each of the N voters rates on her ballot each option between > 0 and 100. > > 2. For each option X, put > s(X) = no. of ballots rating X at zero. > > 3. Put all ballots into a first urn labelled U1, and have > another urn > labelled U2, initially empty. > > 4. For each option X, in order of ascending s(X), do the following: > > 4.1 Find the smallest number R for which f(R) >= 100, where > f(R) = R + 100 * (no. of ballots in U1 rating X above R) / N. > > 4.2 For each ballot in U1 rating X above R: Mark X on that > ballot and > move the ballot from U1 to U2. > > 5. On each of the ballots that remained in U1, mark the option > with the > highest rating on that ballot and also put the ballot into U2. > > 6. Draw one ballot at random. The option marked on that ballot wins. > > > (By "above", we mean strictly above and not equal, of course.) > > If there is only one compromise option C besides some polar > favourite > options A,B,... , the method essentially simplifies to this: > - Find the smallest R such that at least 100-R percent of the > ballots > rate C above R. > - Then draw a ballot at random. If it rates C above R, C wins, > otherwise > the option with the largest rating of that ballot wins. > > > Let's look at the three example situations: > > Situation 1 (sincere utilities): > 55: A(100)>C(70)>B(0) > 45: B(100)>C(70)>A(0) > > Take any pair of numbers x,y such that > > 0 <= x <= 55, > 0 <= y <= 45, > x + y > 55, > x > 3y/7, and > y > 3x/7. > > It is easy to check from the above true ratings that then all > voters > would gain if x of the A-voters and y of the B-voters > transferred their > winning probability to C. The voters can make sure this happens > in the > suggested method by voting this way: > > 55-x: A(100)>C(0)=B(0) > x: A(100)>C(101-x-y)>B(0) > y: B(100)>C(101-x-y)>A(0) > 45-y: B(100)>
Re: [EM] Some chance for consensus (was: Buying Votes)
Hi again, here's another, somewhat more stable method which also achieves the following: > ... > 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 idea is that for each possible compromise option C, a voter indicates, by a rating on her ballot, how many voters she requires to transfer their winning probability to C before she will do so, too. This is the method: 1. Each of the N voters rates on her ballot each option between 0 and 100. 2. For each option X, put s(X) = no. of ballots rating X at zero. 3. Put all ballots into a first urn labelled U1, and have another urn labelled U2, initially empty. 4. For each option X, in order of ascending s(X), do the following: 4.1 Find the smallest number R for which f(R) >= 100, where f(R) = R + 100 * (no. of ballots in U1 rating X above R) / N. 4.2 For each ballot in U1 rating X above R: Mark X on that ballot and move the ballot from U1 to U2. 5. On each of the ballots that remained in U1, mark the option with the highest rating on that ballot and also put the ballot into U2. 6. Draw one ballot at random. The option marked on that ballot wins. (By "above", we mean strictly above and not equal, of course.) If there is only one compromise option C besides some polar favourite options A,B,... , the method essentially simplifies to this: - Find the smallest R such that at least 100-R percent of the ballots rate C above R. - Then draw a ballot at random. If it rates C above R, C wins, otherwise the option with the largest rating of that ballot wins. Let's look at the three example situations: Situation 1 (sincere utilities): 55: A(100)>C(70)>B(0) 45: B(100)>C(70)>A(0) Take any pair of numbers x,y such that 0 <= x <= 55, 0 <= y <= 45, x + y > 55, x > 3y/7, and y > 3x/7. It is easy to check from the above true ratings that then all voters would gain if x of the A-voters and y of the B-voters transferred their winning probability to C. The voters can make sure this happens in the suggested method by voting this way: 55-x: A(100)>C(0)=B(0) x:A(100)>C(101-x-y)>B(0) y:B(100)>C(101-x-y)>A(0) 45-y: B(100)>C(0)=A(0) The method would begin with C (receiving the smallest numbers of 0-rates), find R=100-x-y, and mark C on all the x+y ballots, resulting in these winning probabilities: A:55-x, B:45-y, C:x+y. No voter has an incentive to reduce her C-rating since that would immediately move R to 100 and C's winning probability to 0. So, for each such pair (x,y), the above way of voting is a strategic equilibrium, the socially best of whose is the one where x=55 and y=45, C wins with certainty, and the ballots look like this: 55: A(100)>C(1)>B(0) 45: B(100)>C(1)>A(0) Situation 2 (sincere utilities): 30: A(100)>C(70)>B,D(0) 25: B(100)>C(70)>A,D(0) 45: D(100)>A,B,C(0) Here the only difference is that we require x+y>30 instead of 55. For each pair (x,y) with... 0 <= x <= 30, 0 <= y <= 25, x + y > 30, x > 3y/7, and y > 3x/7. ...the following is an equilibrium way of voting which gives C a winning probability of x+y: 30-x: A(100)>B,C,D(0) x:A(100)>C(101-x-y)>B,D(0) y:B(100)>C(101-x-y)>A,D(0) 25-y: B(100)>A,C,D(0) 45: D(100)>A,B,C(0) Here, the method starts with either X=C or X=D since one of them has the smallest s(X). Both ways, C will eventually be marked on the x+y ballots (at R=100-x-y) and D on the 45 ballots (at R=55). In particular, the socially optimal equilibrium is 30: A(100)>C(46)>B,D(0) 25: B(100)>C(46)>A,D(0) 45: D(100)>A,B,C(0), resulting in the winning probabilities 55% for C and 45% for D. Situation 3 (sincere utilities): 32: A(100)>C(40)>B,D(0) 33: B(100)>C(40)>A,D(0) 35: D(100)>C(40)>A,B(0) Here we consider triples of numbers x,y,z such that 0 <= x <= 32, 0 <= y <= 33, 0 <= z <= 35, x + y + z > 35, x + y > 3z/2, y + z > 3x/2, and z + x > 3y/2. In that case, the following is a voting equilibrium: x:A(100)>C(101-x-y-z)>B,D(0) y:B(100)>C(101-x-y-z)>A,D(0) z:D(100)>C(101-x-y-z)>A,B(0) 32-x: A(100)>B,C,D(0) 33-y: B(100)>A,C,D(0) 35-z: D(100)>A,B,C(0) As in situation 1, the socially best equilibrium is when all voters cooperate by rating C at 1, making C the sure winner. It seem the advantage of this method is that it is more stable than the first one, having a lot more desirable equilibria which. However, the socially optimal equilibria require a somewhat strange way of voting in which you understate your true rating of the compromise in order to make su
Re: [EM] Some chance for consensus (was: Buying Votes)
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: [EMAIL PROTECTED]: [EMAIL PROTECTED], election-methods@lists.electorama.com, [EMAIL PROTECTED]> 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)&g
Re: [EM] Some chance for consensus (was: Buying Votes)
On Sat, Nov 1, 2008 at 1:43 PM, Jobst Heitzig <[EMAIL PROTECTED]> wrote: > 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. I wonder if you could do something like a blind auction. In effect, your winning probability is assigned based only on agreement. For example, Randomly pair up the voters with a randomly assigned compromise. Each voter offers to switch pair for a compromise that is better than current pair This causes a reassignment of the pairs The process is repeated until stable This means that a voter doesn't have to say who is their favourite. Ofc, offers near the start would likely use their favourite as compromise and slowly backtrack if it isn't accepted. Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Some chance for consensus (was: Buying Votes)
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 maxim
Re: [EM] Some chance for consensus (was: Buying Votes)
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 [EMAIL PROTECTED] 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
Re: [EM] Some chance for consensus (was: Buying Votes)
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
Re: [EM] Some chance for consensus (was: Buying Votes)
Dear Raph and Forest,
I have a new idea which might be monotonic, generalizing the 2-voter-marriage
idea to larger groups of voters.
I will define it as an optimization problem: basically, the idea is to find the
"socially best" lottery which can
be produced by starting from the Random Ballot lottery and allowing for one set
of voters to reach a contract in which they transfer their share of the
winning probability from their favourite options to other options. More
precisely, the suggested method is this:
1. Each voter submits a cardinal rating for each option.
2. Amoung all possible lotteries that assign winning probabilities to the
options, we determine the "feasible" ones. In order to determine whether a
given
lottery L is "feasible", we do the following:
a) Compare L with the Random Ballot lottery, RB, and find the set S of options
which have a lower winning probability under L than under RB. Mathematically:
S = { options X with L(X) < RB(X) },
where L(X) = probability of option X in lottery L.
b) For each option X in S, determine the number N1(X) of voters who favour X
and like L at least as much as RB, judging from their submitted ratings.
Mathematically:
N1(X) = no. of voters V with V(L) >= V(RB),
where V(L) = sum of V(X)*L(X) over all options X
and V(X) = rating voter V assigned to option X.
c) Also, determine the number N2 of those voters who favour X which must agree
to transfer their share of the winning probability from X to other options in
order to produce L. Mathematically:
N2(X) = (RB(X)-L(X)) * N,
where N is the no. of all voters.
d) Then check whether N2(X)<=N1(X) for all X in S. If this is fulfilled, then
this means that a group of voters exists who have both the means and the
incentices to change RB into L by transferring winning probability from their
respective favourite options to other options. So, if the condition is
fulfilled, L is considered "feasible".
3. Finally, find amoung the feasible lotteries the one that maximizes a given
measure of social utility, e.g. total utility or Gini welfare function or
median voter utility or whatever. Apply this "socially optimal feasible"
lottery to determine the winner.
With sincere voters, the method achieves what we desire:
1. With 55 having A(100)>C(70)>B(0) and 45 having B(100)>C(70)>A(0), the
optimal lottery L would be L(A/B/C)=0/0/1. This is feasible since it has
S={A,B}, N1(A)=N2(A)=55, and N2(B)=N2(B)=45.
2. With 25 having A1(100)>A(90)>A2(70)>B(0), 25 having
A2(100)>A(90)>A1(70)>B(0), and 50 having B(100)>A,A1,A2(0), the optimal lottery
L would be L(A/A1/A2/B)=.5/0/0/.5 with S={A1,A2},
N1(A1)=N2(A1)=N1(A2)=N2(A2)=25.
I did not yet analyse the strategic implications, though. So we need to check
that and the hoped-for monotonicity. The crucial point for the latter will be
what happens when some voter changes her favourite, I guess.
Some final notes:
- There are always feasible lotteries since the Random Ballot lottery itself is
feasible by definition (with the set S being empty).
- For the same reason, the method gives no lower social utility than Random
Ballot.
- Geometrically, the set of "feasible" lotteries is a closed, star-shaped
polyeder, but it is usually not convex. (It would be convex if more than one
contracting group of voters were allowed.)
What do you think?
Jobst
> -Ursprüngliche Nachricht-
> Von: "Raph Frank" <[EMAIL PROTECTED]>
> Gesendet: 31.10.08 15:35:30
> An: "Jobst Heitzig" <[EMAIL PROTECTED]>
> CC: [EMAIL PROTECTED], election-methods@lists.electorama.com, [EMAIL
> PROTECTED], [EMAIL PROTECTED]
> Betreff: Re: Some chance for consensus (was: [EM] Buying Votes)
> On Fri, Oct 31, 2008 at 11:17 AM, Jobst Heitzig <[EMAIL PROTECTED]> wrote:
> > Dear Raph,
> >
> > you wrote:
> >> I was thinking of a 'stable marriage problem' like solution.
> >
> > Good idea! If it works, the main difficulty will be to make the whole
> > process monotonic, I guess...
> >
> > Yours, Jobst
>
> I think the method which eliminates the lowest probability candidate
> will be non-monotonic.
>
> In the single run case, the fundamental problem is that bilateral
> monopolies can exist. You can gain by not offering compromises.
> However, assuming competition, you might be 'outbid' by another
> voter/party if you do that.
>
> -Ursprüngliche Nachricht-
> Von: "Raph Frank" <[EMAIL PROTECTED]>
> Gesendet: 31.10.08 15:35:30
> An: "Jobst Heitzig" <[EMAIL PROTECTED]>
> CC: [EMAIL PROTECTED], election-methods@lists.electorama.com, [EMAIL
> PROTECTED], [EMAIL PROTECTED]
> Betreff: Re: Some chance for consensus (was: [EM] Buying Votes)
> On Fri, Oct 31, 2008 at 11:17 AM, Jobst Heitzig <[EMAIL PROTECTED]> wrote:
> > Dear Raph,
> >
> > you wrote:
> >> I was thinking of a 'stable marriage problem' like solution.
> >
> > Good idea! If it works, the main difficulty will be to make the whole
> > process monotonic, I guess...
> >
> > Yours, J
Re: [EM] Some chance for consensus (was: Buying Votes)
On Fri, Oct 31, 2008 at 11:17 AM, Jobst Heitzig <[EMAIL PROTECTED]> wrote: > Dear Raph, > > you wrote: >> I was thinking of a 'stable marriage problem' like solution. > > Good idea! If it works, the main difficulty will be to make the whole process > monotonic, I guess... > > Yours, Jobst I think the method which eliminates the lowest probability candidate will be non-monotonic. In the single run case, the fundamental problem is that bilateral monopolies can exist. You can gain by not offering compromises. However, assuming competition, you might be 'outbid' by another voter/party if you do that. Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Some chance for consensus (was: Buying Votes)
Dear Raph, you wrote: > I was thinking of a 'stable marriage problem' like solution. Good idea! If it works, the main difficulty will be to make the whole process monotonic, I guess... Yours, Jobst > > Each voter rates all the candidates. > > Each voter will assign his winning probability to his highest choice > (probably split equally if he ties 2 candidates for first). > > If 2 voters 'marry', then the candidate with the highest score sum is > the compromise candidate. > > Solve the stable marriage problem. It might be necessary to randomly > split the ballots into 2 'genders' to guarantee that a stable solution > exists. > > Using the above example: > > G1: A1(100) A(70) A2(0) > G2: A1(0) A(70) A2(100) > G3: B(100) > G4: C(100) > > (unnamed options are rated zero) > > If a member of G1 'marries', then the compromises are > G1: A1 (+0) > G2: A (+40), i.e. 100->70 (-30) and 0->70 (+70) > G3: A1 and B tie (+0) .. effectively not a 'marriage' > G4: A1 and C tie (+0) .. effectively not a 'marriage' > > Thus rankings are > G1: G2>G1=G3=G4 > > Similarly > G2: G1>G2=G3=G4 > G3: all equal > G4: all equal > > Thus the 25 G1s will 'marry' the 25 G2s and compromise on A. > > The result being > > A: 50% > B: 25% > C: 25% > > Also, what about an iterative method. If the candidate with the > lowest probability has less than 1/3 probability, eliminate him and > re-run the calculations (and probably rescale the ratings). This is > kind of similar to the requirement that a candidate has 1/3 approval > before being considered. > > As an added complication, in the above, it might be worth doing a > second pass. Once all the marriages are stable, you could have > 'suitors' propose to 'engaged' voters and make an offer with a > different compromise candidate. > > For example, if two voters has ratings, > > A1(100) A2(90) A3(75) A4(55) A5(0) > A1(0) A2(55) A3(75) A4(90) A5(100) > > The possible compromises are A2, A3 and A4. However, A2 favours the > first voter and A4 favours the 2nd voter. It might be the case that > after being refused, a 'suitor' could sweeten the deal by offering a > better option. > Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Some chance for consensus (was: Buying Votes)
Dear Forest, good to hear from you again! You said: > Not quite as important, but still valuable, is achieving partial cooperation > when that is the best that can be > done: > > 25 A1>A>>A2 > 25 A2>A>>A1 > 25 B > 25 C > > Here there isn't much hope for consensus, but it would be nice if the first > two factions could still cooperate > on gettiing A elected, say 25% of the time. (50% seems too much to hope for) That's absolutely true! We both tried to achieve this during the last year. But it is very difficult to make this happen with strategic voters. Perhaps I find the time this weekend to write a summary of what we tried in this respect, so that perhaps someone can build on that an come up with a new idea. > It seems to me that if we require our method to accomplish the potential > cooperation in this scenario while > achieving consensus where possible, the ballots would have to have more > levels, and there would have to be > an intermediate fall back between the consensus test and the random ballot > default. That could work, but I wouldn't bet on it yet. Yours, Jobst Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Some chance for consensus (was: Buying Votes)
On Thu, Oct 30, 2008 at 12:16 AM, <[EMAIL PROTECTED]> wrote: > Jobst, > > That was a great exposition of how to find the consensus candidate when there > is one. > > Not quite as important, but still valuable, is achieving partial cooperation > when that is the best that can be > done: > > 25 A1>A>>A2 > 25 A2>A>>A1 > 25 B > 25 C > > Here there isn't much hope for consensus, but it would be nice if the first > two factions could still cooperate > on gettiing A elected, say 25% of the time. (50% seems too much to hope for) > > It seems to me that if we require our method to accomplish the potential > cooperation in this scenario while > achieving consensus where possible, the ballots would have to have more > levels, and there would have to be > an intermediate fall back between the consensus test and the random ballot > default. > > What do you think? I was thinking of a 'stable marriage problem' like solution. Each voter rates all the candidates. Each voter will assign his winning probability to his highest choice (probably split equally if he ties 2 candidates for first). If 2 voters 'marry', then the candidate with the highest score sum is the compromise candidate. Solve the stable marriage problem. It might be necessary to randomly split the ballots into 2 'genders' to guarantee that a stable solution exists. Using the above example: G1: A1(100) A(70) A2(0) G2: A1(0) A(70) A2(100) G3: B(100) G4: C(100) (unnamed options are rated zero) If a member of G1 'marries', then the compromises are G1: A1 (+0) G2: A (+40), i.e. 100->70 (-30) and 0->70 (+70) G3: A1 and B tie (+0) .. effectively not a 'marriage' G4: A1 and C tie (+0) .. effectively not a 'marriage' Thus rankings are G1: G2>G1=G3=G4 Similarly G2: G1>G2=G3=G4 G3: all equal G4: all equal Thus the 25 G1s will 'marry' the 25 G2s and compromise on A. The result being A: 50% B: 25% C: 25% Also, what about an iterative method. If the candidate with the lowest probability has less than 1/3 probability, eliminate him and re-run the calculations (and probably rescale the ratings). This is kind of similar to the requirement that a candidate has 1/3 approval before being considered. As an added complication, in the above, it might be worth doing a second pass. Once all the marriages are stable, you could have 'suitors' propose to 'engaged' voters and make an offer with a different compromise candidate. For example, if two voters has ratings, A1(100) A2(90) A3(75) A4(55) A5(0) A1(0) A2(55) A3(75) A4(90) A5(100) The possible compromises are A2, A3 and A4. However, A2 favours the first voter and A4 favours the 2nd voter. It might be the case that after being refused, a 'suitor' could sweeten the deal by offering a better option. Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Some chance for consensus (was: Buying Votes)
Jobst, That was a great exposition of how to find the consensus candidate when there is one. Not quite as important, but still valuable, is achieving partial cooperation when that is the best that can be done: 25 A1>A>>A2 25 A2>A>>A1 25 B 25 C Here there isn't much hope for consensus, but it would be nice if the first two factions could still cooperate on gettiing A elected, say 25% of the time. (50% seems too much to hope for) It seems to me that if we require our method to accomplish the potential cooperation in this scenario while achieving consensus where possible, the ballots would have to have more levels, and there would have to be an intermediate fall back between the consensus test and the random ballot default. What do you think? My Best, Forest - Original Message - From: Jobst Heitzig Date: Sunday, October 26, 2008 6:33 am Subject: Some chance for consensus (was: [EM] Buying Votes) To: Raph Frank Cc: Greg Nisbet , election-methods@lists.electorama.com, Jacob Taylor , Forest W Simmons > Hello folks, > > I know I have to write another concise exposition to the recent > non-deterministic methods I promote, in particular FAWRB and D2MAC. > > Let me do this from another angle than before: from the angly of > reaching consensus. We will see how chance processes can > help overcome the flaws of consensus decision making. > > I will sketch a number of methods, give some pros and cons, > starting > with consensus decision making. > > Contents: > 1. Consensus decision making > 2. Consensus or Random Ballot > 3. Approved-by-all or Random Ballot > 4. Favourite or Approval Winner Random Ballot: 2-ballot-FAWRB > 5. Calibrated FAWRB > 6. 4-slot-FAWRB > 7. 5-slot-FAWRB > > > > 1. Consensus decision making > > The group gathers together and tries to find an option which > everyone > can agree with. If they fail (within some given timeframe, say), > the > status quo option prevails. > > Pros: Ideally, this method takes everybody's preferences into > account, > whether the person is in a majority or a minority. > > Cons: (a) In practice, those who favour the status quo have 100% > power > since they can simply block any consensus. (b) Also, there are > problems > with different degrees of eloquence and with all kinds of group- > think. > (c) Finally, the method is time-consuming, and hardly applicable > in > large groups or when secrecy is desired. > > > Let us address problem (a) first by replacing the status quo > with a > Random Ballot lottery: > > > 2. Consensus or Random Ballot > - > Everybody writes her favourite option on a ballot and gives it > into an > urn. The ballots are counted and put back into the urn. The > number of > ballots for each option is written onto a board. The group then > tries to > find an option which everyone can agree with. If they fail > within some > given timeframe, one ballot is drawn at random from the urn and > the > option on that ballot wins. > > Pros: Since the status quo has no longer a special meanining in > the > process, its supporters cannot get it by simply blocking any > consensus - > they would only get the Random Ballot result then. If there is > exactly > one compromise which everybody likes better than the Random > Ballot > lottery, they will all agree to that option and thus reach a > good consensus. > > Cons: Problems (b) and (c) from above remain. (d) Moreover, it > is not > clear whether the group will reach a consensus when there are > more than > one compromise options which everybody likes better than the > Random > Ballot lottery. (e) A single voter can still block the > consensus, so the > method is not very stable yet. > > > Next, we will address issues (b), (c) and (d) by introducing an > approval > component: > > > 3. Approved-by-all or Random Ballot > --- > Each voter marks one option as "favourite" and any number of > options as > "also approved" on her ballot. If some option is marked either > favourite > or also approved on all ballots, that option is considered the > "consensus" and wins. Otherwise, one ballot is drawn at random > and the > option marked "favourite" on that ballot wins. > > Pros: This is quick, secret, scales well, and reduces problems > related > to group-think. A voter has still full control over an equal > share of > the winning probability by bullet-voting (=not mark any options > as "also > approved"). > > Cons: (b') Because of group-think, some voters might abstain > from using > their bullet-vote power and "also approve" of options they > consider > well-supported even when they personally don't like them better > than the > Random Ballot lottery. Also, (e) from above remains a problem, > in > particular it is not very likely in larger groups that some > options is > really approved by everyone. > > > Now com
