[Election-Methods] ID(n)MAC

[Jobst Heitzig]

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
>