Jobst,<br><br>After thinking about your recent example:<br><br><font face="'PrimaSans BT,Verdana,sans-serif'"> >  33: A1>A>A2 >> B<br>  > 33: A2>A>A1 >> B<br>  > 33: B >> A1,A2,A<br>>and the 66 A-voters try to cooperate to elect A by unanimously approving <br>>of her, then they still get A only with a low probability of 16/81 <br>>(approx. 20%) while A1 and A2 keep a probability of 64/243 (approx. 25%) <br>>each. A<br><br>I have two ideas for incremental improvement:<br><br>1.  For the fall back method, flip a coin to decide between Random Ballot and Random Approval Ballot.<br><br>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.<br><br>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.<br><br>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.<br><br></font><br>----- Original Message -----<br>From: Jobst Heitzig <heitzig-j@web.de><br>Date: Saturday, May 24, 2008 10:04 am<br>Subject: Re: [english 94%] Re: D(n)MAC<br>To: fsimmons@pcc.edu<br>Cc: election-methods@lists.electorama.com<br><br>> Dear Forest,<br>> <br>> your analysis was right from the beginning while mine in the <br>> last <br>> message was wrong unfortunately: I claimed that already your <br>> D(2)MAC/RB <br>> would elect a 52%-compromise, but I got the numbers wrong!<br>> <br>> So, we really need n>2, as you said, and I think that perhaps <br>> n=4 could <br>> be a good choice.<br>> <br>> However, another similar but slightly different method really <br>> needs only <br>> n=2, but that method is again non-monotonic like AMP, and <br>> therefore <br>> sometimes gives incentive to order-reverse.<br>> <br>> Anyway, here's that variant: Each voter marks one favourite and <br>> at most <br>> one compromise. Two ballots are drawn. If they have the same <br>> option <br>> marked as compromise (not favourite!), that option is the <br>> winner. <br>> Otherwise the favourite of a third drawn ballot is the winner.<br>> <br>> Under that method, full cooperation is indeed an equilibrium in <br>> our <br>> example situation<br>>   P: A>C>B<br>>   Q: B>C>A<br>> as long as everyone prefers C to the Random Ballot lottery. This <br>> is <br>> because when everyone else marks C as compromise, my not marking <br>> her as <br>> compromise changes the outcome exactly in those situations in <br>> which mine <br>> is one of the first two ballots, in which case it takes the win <br>> from C <br>> and gives it to the Random Ballot lottery. QED.<br>> <br>> <br>> One point still troubles me with n>2: In situations where not <br>> the whole <br>> electorate but a subgroup seeks to cooperate, such a method <br>> performs <br>> badly. For example, when n=4, the preferences are<br>>   33: A1>A>A2 >> B<br>>   33: A2>A>A1 >> B<br>>   33: B >> A1,A2,A<br>> and the 66 A-voters try to cooperate to elect A by unanimously <br>> approving <br>> of her, then they still get A only with a low probability of <br>> 16/81 <br>> (approx. 20%) while A1 and A2 keep a probability of 64/243 <br>> (approx. 25%) <br>> each. AMP performs better here in giving A the complete 66% <br>> probability, <br>> but AMP is considerably more complex and non-monotonic...<br>> <br>> Yours, Jobst<br>> <br>> <br>> fsimmons@pcc.edu schrieb:<br>> > Dear Jobst,<br>> > <br>> > Thanks for your encouragement.  And D(n)MAC/RB it shall be!<br>> > <br>> > I also wanted to speak my admiration of your outline of a <br>> computationally effective way of carrying out <br>> > your trading method: quite a tour d'force with many beautiful <br>> mathematical ideas elegantly applied.<br>> > <br>> > Here's a further partial result, that might interest you.<br>> > <br>> > Suppose that we have 2Q>P>Q>0, P+Q=100, and factions<br>> > <br>> > P: A>C>B<br>> > Q: B>C>A<br>> >  with C rated at R% by all voters.<br>> > <br>> > If R = Q/2^(n-1) + P, then (under D(n)MAC/RB) the common <br>> strategy of each faction approving C on <br>> > exactly Q ballots is a global equilibrium , so that the <br>> winning probabilities for A, B, C become<br>> > 1-2Q%, 0, and 2Q%, respectively.<br>> > <br>> > This can be thought of as implicit trading, since the second <br>> faction moves C up to equal-first on all Q of <br>> > its ballots, while the first faction moves C up to equal-first <br>> on Q of its ballots, as well.<br>> > <br>> > The expected "utilities" for the two factions are<br>> > <br>> > EA = (100-2Q)+R*(2Q)%, and<br>> > EB = R*(2Q)%.<br>> > <br>> > For example, if P=60, Q=40, n=3, and R=70, the equation <br>> R=Q/2^(n-1)+P is satisfied, so<br>> > <br>> > the global equilibrium strategy is for both to approve C on 40 <br>> ballots, yielding the winning probabilities<br>> > <br>> > 20%, 0, and 80%, respectively, <br>> > <br>> > so that the expectations are<br>> > <br>> > EA= 76, and EB=56,<br>> > <br>> > compared with the benchmarks of 60 and 40, respectively.<br>> > <br>> > With these values of P, Q, and R, the number  n would have to <br>> be  4 (or more) in order to get unanimous <br>> > support for C.<br>> > <br>> > In that case we would have<br>> > <br>> > EA=EB=70.<br>> > <br>> > Here's the key to my calculations:<br>> > <br>> > Let X and Y be the number of ballots on which C is approved in <br>> the respective factions.<br>> > <br>> > Then the probability that no candidate is approved on all n of <br>> the drawn ballots is given by the formula<br>> > <br>> > g = 1 - q^n - p^n - (x+y)^n + x^n + y^n, <br>> > <br>> > where p=P/(P+Q), q=Q/(P+Q), x=X/(P+Q), y=Y/(P+Q).<br>> > <br>> > So g is the probability that an additional random ballot will <br>> have to be drawn to decide the winner.<br>> > <br>> > Then the respective probabilities for wins (under D(n)MAC/RB) <br>> by A, B, and C are ...<br>> > <br>> > pA = p^n+g*p - when(X+Y>P, x^n, else 0)<br>> > <br>> > pB= q^n+g*q - when(X+Y<Q, 0,="" else="" y^n)=""><br>> > <br>> > pC=(x+y)^n - when(X+Y>P, 0, else x^n) - when(X+Y<Q, y^n,="" else="" 0).=""><br>> > <br>> > Miraculously, these probabilities add up to 1 !<br>> > <br>> > The two faction expectations are <br>> > <br>> > EA = pA + R*pC,  and<br>> > EB = pB + R*pC<br>> > <br>> >>From there, it's all downhill.<br>> > <br>> > My Best,<br>> > <br>> > Forest<br>> > <br>> > <br>> > ----- Original Message -----<br>> > From: Jobst Heitzig <br>> > Date: Thursday, May 22, 2008 3:45 pm<br>> > Subject: Re: ID(n)MAC<br>> > To: fsimmons@pcc.edu<br>> > Cc: election-methods@lists.electorama.com<br>> > <br>> >> Dear Forest,<br>> >><br>> >> your's is the honour of having solved the method design <br>> >> challenge in the <br>> >> most convincing way!<br>> >><br>> >> To see this, one can also look at it a little differently and <br>> >> perhaps <br>> >> even simpler than in your reasoning:<br>> >><br>> >> First of all, let's keep in mind that your class of methods <br>> is <br>> >> not <br>> >> really a direct generalization of D2MAC since in D2MAC, when <br>> the <br>> >> two <br>> >> drawn ballots have no compromise, the deciding ballot is not <br>> >> drawn <br>> >> freshly but is simply the first of the two already drawn.<br>> >><br>> >> For original D2MAC, this had two effects: First, a faction of <br>> p% <br>> >> size <br>> >> has complete control over p% of the winning probability <br>> (which <br>> >> is not <br>> >> true with your class of methods, but anyway that was not part <br>> of <br>> >> the <br>> >> challenge's goal). Second, in the situation of two almost <br>> >> equally sized <br>> >> factions, the compromise has to be at least "75% good" for <br>> both <br>> >> factions <br>> >> in order to be elected with certainty under original D2MAC. <br>> >> Actually, <br>> >> this latter observation was the very reason for the method <br>> >> design <br>> >> challenge in which, let's recall, a method was sought under <br>> >> which even a <br>> >> compromise that is just above "50% good" for everyone will be <br>> >> elected <br>> >> for sure.<br>> >><br>> >><br>> >> The methods you suggest do solve this task!<br>> >><br>> >> I think this is not because you increase the number of <br>> ballots <br>> >> from 2 to <br>> >> N, but simply because the "deciding" ballot which is used in <br>> >> case the <br>> >> first N drawn ballots have no common compromise is a *newly* <br>> >> drawn <br>> >> ballot (instead of the first of the earlier drawn ballots)!<br>> >><br>> >> To see this, consider your method D(N)MAC with N=2, two <br>> factions <br>> >> of <br>> >> relative size P and Q=1-P with favourites A and B, <br>> respectively, <br>> >> and <br>> >> assume that everybody prefers some compromise C to the Random <br>> >> Ballot <br>> >> solution. (In your example, any situation with R>P is such a <br>> >> situation). <br>> >> Then full cooperation (the voting behaviour where everybody <br>> >> marks C as <br>> >> approved) is an equilibrium in the sense that no single voter <br>> >> and no <br>> >> "small" group of voters has an incentive to deviate from that <br>> >> voting <br>> >> behaviour. (Only a large group of A-voters consisting of more <br>> >> than Q <br>> >> voters could perhaps have such an incentive.)<br>> >><br>> >> More precisely, let's assume that the true "utilities" are<br>> >><br>> >> P: A (1) > C (R) > B (0)<br>> >> Q: B (1) > C (S) > A (0)<br>> >><br>> >> with R>P and S>Q, that all of the Q B-voters mark C as <br>> approved <br>> >> and that <br>> >> at least X>P-Q of the P A-voters do likewise. Then each A-<br>> >> voter has an <br>> >> expected "utility" of<br>> >><br>> >> (Q+X)²R + (1-(Q+X)²)P = (R-P)X² + 2Q(R-P)X + const.<br>> >><br>> >> which is monotonic in X for X>P-Q since R-P>0. Hence the <br>> optimal <br>> >> X for <br>> >> the A-voters is X=P, that is, full cooperation is optimal for <br>> >> the <br>> >> A-voters and similarly for the B-voters.<br>> >><br>> >><br>> >> The same analysis for the original D2MAC gives an expected <br>> >> "utility" of<br>> >><br>> >> (Q+X)²R + P-X + X(P-X) = (R-1)X² + (2QR-1+P)X + const.<br>> >><br>> >> which may not be monotonic in X for X>P-Q. In particular, when<br>> >><br>> >> 2(R-1)P + (2QR-1+P) < 0,<br>> >><br>> >> which is equivalent to<br>> >><br>> >> R < (P+1)/2<br>> >><br>> >> it has a negative derivative at X=P which means that each <br>> single <br>> >> A-voter <br>> >> has an incentive to deviate from cooperation. For the case of <br>> >> P=1/2 <br>> >> (that is, equal sized factions), this gives the familiar <br>> value <br>> >> of 3/4 <br>> >> (that is, the compromise must be at least 75% good to be <br>> elected <br>> >> for sure).<br>> >><br>> >><br>> >> So, your suggestion is indeed a major improvement already for <br>> >> N=2! It <br>> >> meets the goal of the challenge while being both <br>> conceptiually <br>> >> very <br>> >> simple and monotonic!<br>> >><br>> >><br>> >> But because of the difference to original D2MAC, I suggest <br>> not <br>> >> to call <br>> >> your class of methods D(N)MAC since then D(2)MAC could be <br>> >> confused with <br>> >> D2MAC too easily. Perhaps we could call them<br>> >><br>> >> D(N)MAC/RB<br>> >><br>> >> instead since the "fallback" method when the N drawn ballots <br>> >> show no <br>> >> compromise is indeed Random Ballot?<br>> >><br>> >> Yours, Jobst<br>> >><br>> >><br>> >><br>> >> fsimmons@pcc.edu schrieb:<br>> >>> Dear Jobst (and other open minded EM list participants),<br>> >>><br>> >>> Consider the case of two factions<br>> >>><br>> >>> P: A>C>B<br>> >>> Q: B>C>A,<br>> >>><br>> >>> where P>Q>0 and P+Q=100%.<br>> >>><br>> >>> Also suppose that there is a percentage R between 50% and <br>> >> 100%, such that<br>> >>> all voters in the first faction prefer C to the lottery<br>> >>> R*A+(100%-R)*B, <br>> >>> and all voters in the second faction prefer C to the lottery<br>> >>> R*B+(100%-R)*A.<br>> >>><br>> >>> [Range voters can assume that sincere ratings for C are at R <br>> >> or above on all<br>> >>> ballots.]<br>> >>><br>> >>> It turns out that if the exponent "n" in the following <br>> formula <br>> >> is chosen so that<br>> >>> P+Q*P^(n-1) is less than or equal to R,<br>> >>><br>> >>> then the lottery method D(n)MAC that generalizes Jobst's <br>> >> D2MAC method<br>> >>> has a stable equilibrium in which C is the sure winner.<br>> >>><br>> >>> Here's what I mean by D(n)MAC:<br>> >>><br>> >>> 1. Ballots are approval style with favorites marked.<br>> >>><br>> >>> 2. Draw n ballots at random (with replacement, if the ballot <br>> >> set is small).<br>> >>> 3. If there is at least one candidate that is approved on <br>> all <br>> >> of the drawn<br>> >>> ballots, then (among those) elect the one that is approved <br>> on <br>> >> the most ballots<br>> >>> in the total collection of ballots.<br>> >>><br>> >>> 4. Otherwise, elect the favorite candidate on another <br>> >> randomly drawn ballot.<br>> >>> Example:<br>> >>><br>> >>> 51% A>C>B<br>> >>> 49% B>C>A<br>> >>><br>> >>> with R(C)=52%.<br>> >>><br>> >>> Since .51+..49*51^7<.52, the method D7MAC has a stable <br>> >> equilibrium in which C<br>> >>> is the sure winner.<br>> >>><br>> >>> Note also that if P=Q=50%, then the relation simplifies to <br>> >> 1/2^n+1/2 < R .<br>> >>> So for example, if we cannot be certain which of the two <br>> >> factions is larger, <br>> >>> then for R > 62.5%, candidate C is a stable D3MAC winner.<br>> >>><br>> >>> As Always,<br>> >>><br>> >>> Forest<br>> >>><br>> >><br>> > <br>> <br>> </Q,></Q,></heitzig-j@web.de>