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

[Jobst Heitzig]

Dear Forest,

a quick calculation for your suggestion (please check!) gives:

Winning probability for A under full cooperation of the A1 and A2 voters:
(16+4*8)/81 + 8/27*1/2*2/3 = 56/81 = approx. 70% (OK)

Gain in expected utility for the A1 voters when reducing their 
cooperation by an infinitesimal epsilon:
epsilon*(
   4*3*(2/3)²*1/3*(
      1/2*1/3*(alpha1-alpha)
      + 1/2*1/3*(alpha2-alpha)
      + 2/3*(beta-alpha) )
   + 8/27*1/2*(
      (alpha1-alpha)
      + 1/3*1/(2/3)*(alpha1-alpha) )
)
= epsilon/27*(14alpha1+8alpha2+16beta-38alpha)

In this, alpha[1|2] and beta are the utilities of A[1|2] and B for the 
A1 voters. We may assume that alpha1=1 and beta=0.

The A1 voters have no incentive to reduce their cooperation as long as 
the above gain is <0, i.e. when alpha>(7+4alpha2)/19. The latter is 
always true when alpha>58%. Similarly, the A2 voters will fully 
cooperate when they rate A at least at 58% the way from B to their 
favourite A2.

This is good, however with pure Random Approval as fallback it is even 
better, it seems: The gain then changes to
epsilon*(
   4*3*(2/3)²*1/3*(
      2/3*(beta-alpha) )
   + 8/27*(
      (alpha1-alpha)
      + 1/3*1/(2/3)*(alpha1-alpha) )
)
= epsilon/27*(12alpha1+16beta-28alpha)
which is negative even when alpha>3/7 only!

(Please double-check these calculations!)

Yours, Jobst


fsimmons at pcc.edu schrieb:
> Jobst,
> 
> After thinking about your recent example:
> 
>  >  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. A
> 
> I have two ideas for incremental improvement:
> 
> 1.  For the fall back method, flip a coin to decide between Random 
> Ballot and Random Approval Ballot.
> 
> Note that if Random Approval Ballot were used exclusively, then there 
> could be insufficient incentive for the first two factions to give 
> unanimous support to A.
> 
> 2.  Reduce the approval requirement from 4 of 4 to 3 out of 4 matches.  
> The the fall back method would be used less frequently, since the 3 of 4 
> requirement is more feasible for a candidate approved on two thirds of 
> the ballots.
> 
> Of course, this doesn't solve the general problem, and I'm afraid that 
> any attempt to automate these kinds of adjustments might be vulnerable 
> to manipulation by insincere ballots.
> 
> 
> ----- Original Message -----
> From: Jobst Heitzig
> Date: Saturday, May 24, 2008 10:04 am
> Subject: Re: [english 94%] Re: D(n)MAC
> To: fsimmons at pcc.edu
> Cc: election-methods at lists.electorama.com
> 
>  > 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
>  > >
>  > > pC=(x+y)^n - when(X+Y>P, 0, else x^n) - when(X+Y
>  > >
>  > > 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
>  > >>>
>  > >>
>  > >
>  >
>  >