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

[Jobst Heitzig]

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 relative to the lack 
> of approval (on the remaining ballots) can be played with to get 
> variations of this method.

True, but I guess as long as you use a monotonic transformation for this, the result will be equivalent. Except that the order in which the options are processed would vary. It is charming to be able to simply explain it this way: "If you rate C at R, your vote will not be transferred to C whenever R or more voters rate C less than R".

> 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.

Right. With this interpretation, options are considered in order of decreasing "partial approval score". It is important not to use the rating sum instead since then there would be a conflict between the necessity of using a small score to be safe and using a larger score to make sure the compromise is considered before the polar favourite options!
 
> *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.

When no ballot rates X high enough, then R must be considered to be infinity, hence no ballots get transferred and the next option is considered.

As for ties, I usually think of them late. However: Ties are only relevant for the order in which the options get processes here. The natural tiebreaker would be this: If two options have the minimum number of zero ratings, consider the number of 1-ratings next, then (if still equal) the number of 2-ratings and so on.

What do you think of the following name for this method: 

EC6 
(Equal Chances Choice with Controlled Cooperation for Consensus or Compromise)

Is this silly or smart?

Yours, 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: fsimmons at pcc.edu
> Cc: gregory.nisbet at gmail.com, election-methods at 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(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 
> > sure not to give others an incentive to reduce their rating and 
> > thereby 
> > lessen the compromise's winning probability...
> > 
> > What do you make of this?
> > 
> > Yours, Jobst
> > 
> 
>