[Election-Methods] [english 94%] Re: D(n)MAC

Jobst Heitzig heitzig-j at web.de
Sat May 24 10:03:44 PDT 2008


Dear Forest,

your analysis was right from the beginning while mine in the last 
message was wrong unfortunately: I claimed that already your D(2)MAC/RB 
would elect a 52%-compromise, but I got the numbers wrong!

So, we really need n>2, as you said, and I think that perhaps n=4 could 
be a good choice.

However, another similar but slightly different method really needs only 
n=2, but that method is again non-monotonic like AMP, and therefore 
sometimes gives incentive to order-reverse.

Anyway, here's that variant: Each voter marks one favourite and at most 
one compromise. Two ballots are drawn. If they have the same option 
marked as compromise (not favourite!), that option is the winner. 
Otherwise the favourite of a third drawn ballot is the winner.

Under that method, full cooperation is indeed an equilibrium in our 
example situation
   P: A>C>B
   Q: B>C>A
as long as everyone prefers C to the Random Ballot lottery. This is 
because when everyone else marks C as compromise, my not marking her as 
compromise changes the outcome exactly in those situations in which mine 
is one of the first two ballots, in which case it takes the win from C 
and gives it to the Random Ballot lottery. QED.


One point still troubles me with n>2: In situations where not the whole 
electorate but a subgroup seeks to cooperate, such a method performs 
badly. For example, when n=4, the preferences are
   33: A1>A>A2 >> B
   33: A2>A>A1 >> B
   33: B >> A1,A2,A
and the 66 A-voters try to cooperate to elect A by unanimously approving 
of her, then they still get A only with a low probability of 16/81 
(approx. 20%) while A1 and A2 keep a probability of 64/243 (approx. 25%) 
each. AMP performs better here in giving A the complete 66% probability, 
but AMP is considerably more complex and non-monotonic...

Yours, Jobst


fsimmons at pcc.edu schrieb:
> 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
>>>
>>
> 




More information about the Election-Methods mailing list