Re: [Election-Methods] D(n)MAC/RB
Back to the initial set-up. Who should win in this example? If the A group is going to win in any case then they could agree that A is a good compromise candidate (and make his probabilities high). On the other hand A1 is the Condorcet winner, which would make him a good compromise candidate. At least A1 could have higher probabilities than A2 due to the fact that the B group unanimously prefers A1 to A2. The random ballot based methods however put high weight to the first preferences. In this example the lower preferences of the B group don't seem to matter much. The deterministic methods that I proposed (as solutions for the challenge of electing compromise candidates even against a majority opinion) on the other hand did put quite a lot of weight on the last preferences. Their philosophy was roughly to allow all groupings (that are large enough) to eliminate candidates that they like least. If one follows this idea, then the 33 B supporters of this example do form a big enough group to have the right to eliminate A (that they all consider to be the worst candidate). Juho On May 28, 2008, at 0:19 , [EMAIL PROTECTED] wrote: Jobst, After thinking about your recent example: 33: A1AA2 B 33: A2AA1 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: [EMAIL PROTECTED] Cc: election-methods@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 n2, 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: ACB Q: BCA 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 n2: 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: A1AA2 B 33: A2AA1 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 [EMAIL PROTECTED] 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 2QPQ0, P+Q=100, and factions P: ACB Q: BCA 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%,
Re: [Election-Methods] D(n)MAC/RB
Jobst,After thinking about your recent example: 33: A1AA2 B 33: A2AA1 B 33: B A1,A2,Aand 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: [EMAIL PROTECTED]: election-methods@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 n2, 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: ACB Q: BCA 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 n2: 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: A1AA2 B 33: A2AA1 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 [EMAIL PROTECTED] 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 2QPQ0, P+Q=100, and factionsP: ACB Q: BCA 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, sothe global equilibrium strategy is for both to approve C on 40 ballots, yielding the winning probabilities20%, 0, and 80%, respectively, so that the expectations areEA= 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 haveEA=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 formulag = 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
Re: [Election-Methods] D(n)MAC/RB
Dear Jobst, I think you are right: Plain random ballot (as fall back) induces full cooperation at lower values of alpha than does a mixture of plain and approval random ballot, since the penalty is greater for failing to cooperate in the former case. However, given a value of alpha for which both fall back methods (plain and mixed) induce full cooperation, it seems to me that the fallback mixture will give a higher probability of the compromise candidate A being elected, since the probabilities only differ in case of fallback, where random ballot favors A1 and A2, while random approval ballot favors the compromise A. My Best, Forest - Original Message - From: Jobst Heitzig Date: Tuesday, May 27, 2008 3:40 pm Subject: Re: [english 94%] Re: D(n)MAC/RB To: [EMAIL PROTECTED] Cc: election-methods@lists.electorama.com 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 alpha58%. 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 alpha3/7 only! (Please double-check these calculations!) Yours, Jobst [EMAIL PROTECTED] schrieb: Jobst, After thinking about your recent example: 33: A1AA2 B 33: A2AA1 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. Election-Methods mailing list - see http://electorama.com/em for list info