[Election-Methods] D(n)MAC

[fsimmons at pcc.edu]

Dear Jobst,

Thanks for your encouragement.  And D(n)MAC/RB it shall be!

I also wanted to speak my admiration of your outline of a computationally effective way of carrying out 
your trading method: quite a tour d'force with many beautiful mathematical ideas elegantly applied.

Here's a further partial result, that might interest you.

Suppose that we have 2Q>P>Q>0, P+Q=100, and factions

P: A>C>B
Q: B>C>A
 with C rated at R% by all voters.

If R = Q/2^(n-1) + P, then (under D(n)MAC/RB) the common strategy of each faction approving C on 
exactly Q ballots is a global equilibrium , so that the winning probabilities for A, B, C become
1-2Q%, 0, and 2Q%, respectively.

This can be thought of as implicit trading, since the second faction moves C up to equal-first on all Q of 
its ballots, while the first faction moves C up to equal-first on Q of its ballots, as well.

The expected "utilities" for the two factions are

EA = (100-2Q)+R*(2Q)%, and
EB = R*(2Q)%.

For example, if P=60, Q=40, n=3, and R=70, the equation R=Q/2^(n-1)+P is satisfied, so

the global equilibrium strategy is for both to approve C on 40 ballots, yielding the winning probabilities

20%, 0, and 80%, respectively, 

so that the expectations are

EA= 76, and EB=56,

compared with the benchmarks of 60 and 40, respectively.

With these values of P, Q, and R, the number  n would have to be  4 (or more) in order to get unanimous 
support for C.

In that case we would have

EA=EB=70.

Here's the key to my calculations:

Let X and Y be the number of ballots on which C is approved in the respective factions.

Then the probability that no candidate is approved on all n of the drawn ballots is given by the formula

g = 1 - q^n - p^n - (x+y)^n + x^n + y^n, 

where p=P/(P+Q), q=Q/(P+Q), x=X/(P+Q), y=Y/(P+Q).

So g is the probability that an additional random ballot will have to be drawn to decide the winner.

Then the respective probabilities for wins (under D(n)MAC/RB) by A, B, and C are ...

pA = p^n+g*p - when(X+Y>P, x^n, else 0)

pB= q^n+g*q - when(X+Y<Q, 0, else y^n)

pC=(x+y)^n - when(X+Y>P, 0, else x^n) - when(X+Y<Q, y^n, else 0).

Miraculously, these probabilities add up to 1 !

The two faction expectations are 

EA = pA + R*pC,  and
EB = pB + R*pC

>From there, it's all downhill.

My Best,

Forest


----- Original Message -----
From: Jobst Heitzig 
Date: Thursday, May 22, 2008 3:45 pm
Subject: Re: ID(n)MAC
To: fsimmons at pcc.edu
Cc: election-methods at lists.electorama.com

> Dear Forest,
> 
> your's is the honour of having solved the method design 
> challenge in the 
> most convincing way!
> 
> To see this, one can also look at it a little differently and 
> perhaps 
> even simpler than in your reasoning:
> 
> First of all, let's keep in mind that your class of methods is 
> not 
> really a direct generalization of D2MAC since in D2MAC, when the 
> two 
> drawn ballots have no compromise, the deciding ballot is not 
> drawn 
> freshly but is simply the first of the two already drawn.
> 
> For original D2MAC, this had two effects: First, a faction of p% 
> size 
> has complete control over p% of the winning probability (which 
> is not 
> true with your class of methods, but anyway that was not part of 
> the 
> challenge's goal). Second, in the situation of two almost 
> equally sized 
> factions, the compromise has to be at least "75% good" for both 
> factions 
> in order to be elected with certainty under original D2MAC. 
> Actually, 
> this latter observation was the very reason for the method 
> design 
> challenge in which, let's recall, a method was sought under 
> which even a 
> compromise that is just above "50% good" for everyone will be 
> elected 
> for sure.
> 
> 
> The methods you suggest do solve this task!
> 
> I think this is not because you increase the number of ballots 
> from 2 to 
> N, but simply because the "deciding" ballot which is used in 
> case the 
> first N drawn ballots have no common compromise is a *newly* 
> drawn 
> ballot (instead of the first of the earlier drawn ballots)!
> 
> To see this, consider your method D(N)MAC with N=2, two factions 
> of 
> relative size P and Q=1-P with favourites A and B, respectively, 
> and 
> assume that everybody prefers some compromise C to the Random 
> Ballot 
> solution. (In your example, any situation with R>P is such a 
> situation). 
> Then full cooperation (the voting behaviour where everybody 
> marks C as 
> approved) is an equilibrium in the sense that no single voter 
> and no 
> "small" group of voters has an incentive to deviate from that 
> voting 
> behaviour. (Only a large group of A-voters consisting of more 
> than Q 
> voters could perhaps have such an incentive.)
> 
> More precisely, let's assume that the true "utilities" are
> 
> P: A (1) > C (R) > B (0)
> Q: B (1) > C (S) > A (0)
> 
> with R>P and S>Q, that all of the Q B-voters mark C as approved 
> and that 
> at least X>P-Q of the P A-voters do likewise. Then each A-
> voter has an 
> expected "utility" of
> 
> (Q+X)²R + (1-(Q+X)²)P = (R-P)X² + 2Q(R-P)X + const.
> 
> which is monotonic in X for X>P-Q since R-P>0. Hence the optimal 
> X for 
> the A-voters is X=P, that is, full cooperation is optimal for 
> the 
> A-voters and similarly for the B-voters.
> 
> 
> The same analysis for the original D2MAC gives an expected 
> "utility" of
> 
> (Q+X)²R + P-X + X(P-X) = (R-1)X² + (2QR-1+P)X + const.
> 
> which may not be monotonic in X for X>P-Q. In particular, when
> 
> 2(R-1)P + (2QR-1+P) < 0,
> 
> which is equivalent to
> 
> R < (P+1)/2
> 
> it has a negative derivative at X=P which means that each single 
> A-voter 
> has an incentive to deviate from cooperation. For the case of 
> P=1/2 
> (that is, equal sized factions), this gives the familiar value 
> of 3/4 
> (that is, the compromise must be at least 75% good to be elected 
> for sure).
> 
> 
> So, your suggestion is indeed a major improvement already for 
> N=2! It 
> meets the goal of the challenge while being both conceptiually 
> very 
> simple and monotonic!
> 
> 
> But because of the difference to original D2MAC, I suggest not 
> to call 
> your class of methods D(N)MAC since then D(2)MAC could be 
> confused with 
> D2MAC too easily. Perhaps we could call them
> 
> D(N)MAC/RB
> 
> instead since the "fallback" method when the N drawn ballots 
> show no 
> compromise is indeed Random Ballot?
> 
> Yours, Jobst
> 
> 
> 
> fsimmons at pcc.edu schrieb:
> > Dear Jobst (and other open minded EM list participants),
> > 
> > Consider the case of two factions
> > 
> > P: A>C>B
> > Q: B>C>A,
> > 
> > where P>Q>0 and P+Q=100%.
> > 
> > Also suppose that there is a percentage R between 50% and 
> 100%, such that
> > all voters in the first faction prefer C to the lottery
> > R*A+(100%-R)*B, 
> > and all voters in the second faction prefer C to the lottery
> > R*B+(100%-R)*A.
> > 
> > [Range voters can assume that sincere ratings for C are at R 
> or above on all
> > ballots.]
> > 
> > It turns out that if the exponent "n" in the following formula 
> is chosen so that
> > 
> > P+Q*P^(n-1) is less than or equal to R,
> > 
> > then the lottery method D(n)MAC that generalizes Jobst's 
> D2MAC method
> > has a stable equilibrium in which C is the sure winner.
> > 
> > Here's what I mean by D(n)MAC:
> > 
> > 1. Ballots are approval style with favorites marked.
> > 
> > 2. Draw n ballots at random (with replacement, if the ballot 
> set is small).
> > 
> > 3. If there is at least one candidate that is approved on all 
> of the drawn
> > ballots, then (among those) elect the one that is approved on 
> the most ballots
> > in the total collection of ballots.
> > 
> > 4. Otherwise, elect the favorite candidate on another 
> randomly drawn ballot.
> > 
> > Example:
> > 
> > 51% A>C>B
> > 49% B>C>A
> > 
> > with R(C)=52%.
> > 
> > Since .51+..49*51^7<.52, the method D7MAC has a stable 
> equilibrium in which C
> > is the sure winner.
> > 
> > Note also that if P=Q=50%, then the relation simplifies to 
> 1/2^n+1/2 < R .
> > 
> > So for example, if we cannot be certain which of the two 
> factions is larger, 
> > then for R > 62.5%, candidate C is a stable D3MAC winner.
> > 
> > As Always,
> > 
> > Forest
> > 
> 
>