[Election-Methods] D(n)MAC/RB

[fsimmons at pcc.edu]

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. AI 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 amSubject: Re: [english 94%] Re: D(n)MACTo: fsimmons at pcc.eduCc: 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> >>>> >>> > > > 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20080527/852f6f1e/attachment-0003.htm>