Re: [Election-Methods] Challenge Problem
Dear Jobst, Yes, great fun, and simple to boot! This method should be called the Magnanimous Method. The voter of the first drawn ballot is not punished for not going along with everybody else, and there's still plenty of prior incentive to cooperate, because chances are small for getting the first drawn ballot. Is that the way you see it? Forest Election-Methods mailing list - see http://electorama.com/em for list info
Re: [Election-Methods] Challenge Problem
Hi again. There is still another slight improvement which might be useful in practice: Instead of using the function 1/(5-4x), use the function (1 + 3x + 3x^7 + x^8) / 8. This is only slightly smaller than 1/(5-4x) and has the same value of 1 and slope of 4 for x=1. Therefore, it still encourages unanimous cooperation in our benchmark situation 50: A(1) C(gamma) B(0) 50: B(1) C(gamma) A(0) whenever gamma (1+1/(1+(slope at x=1)))/2 = 0.6, just as the other methods did. The advantage of using (1 + 3x + 3x^7 + x^8) / 8 is that then there is a procedure in which you don't need any calculator or random number generator, only three coins: ** ** Method 3-coin-FAWRB ** - ** Ballots: Approval with one option marked favourite. ** Tally: ** 1. Determine the approval winner, X. ** 2. Draw a ballot at random; ** if it does not approve of X, its favourite, Y, wins. ** 3. Otherwise, toss three coins; ** if they show no heads, X wins. ** 4. If it's one head, draw one further ballot; ** if it's two heads, draw another seven ballots; ** if all three show heads, draw another eight ballots. ** 5. If all drawn ballots approve of X, she wins; ** otherwise, Y wins. ** Isn't this guaranteed fun? Jobst I wrote: Dear Forest, well - thanks. Anyway, there is still room for improvement. Our last version was this: Let x be the highest approval rate (=approval score divided by total number of voters). Draw a ballot at random. With probability 1/(5-4x), the option with the highest approval score amoung those approved on the drawn ballot wins. Otherwise the favourite of that ballot wins. We saw that this method performs well in a large number of situations. But it seems to me that, with more than three options, it can be hard to find the optimal strategies because approving a non-approval-winner can be bad. For example, consider this case: 33: A B C=D=E 34: C B=D A=E 33: E D A=B=C Here the C faction can either cooperate with the A faction to give B a high probability of winning, or with the E faction to give D a high probability of winning. But when the A faction approves of B but the C and E factions approve D, it would have been better for the A faction to have bullet-voted. The following even simpler method, however, makes it safe to approve of an option which does not turn out the approval winner: ** ** Method FAWRB (Favourite-or-Approval-Winner Random Ballot): ** - ** Everyone marks a favourite and may mark any number of also approved ** options. The approval winner X and her approval rate x are ** determined. A ballot is drawn at random. If the ballot approves of X, ** X wins with probability 1/(5-4x). Otherwise, or if the ballot does ** not approve of X, its favourite option wins. ** FAWRB is again monotonic and solves the original challenge problem in the same way as the other methods we discussed recently. But in the above situation it makes it safe for the A and C factions to approve of B and D since only one of the two factions will actually partially transfer their winning probability from their favourite to the compromise option. I guess it should be possible to analyse FAWRBs strategic implications in detail since the method is so extremely simple! I'm pretty sure already that with FAWRB you will never have an incentive to misrepresent your favourite, and seldom or never to approve of one option while not approving of all more preferred options as well. With the other methods these variations of order reversal would occur more often I think. Yours, Jobst PS: I have not yet thought much about your most recent proposals. Only it seems that they won't elect any compromise option that's not the favourite of anyone, right? [EMAIL PROTECTED] schrieb: Jobst wrote ... What do you think about this? I think you have the golden touch! Forest Election-Methods mailing list - see http://electorama.com/em for list info Election-Methods mailing list - see http://electorama.com/em for list info
Re: [Election-Methods] Challenge Problem
Dear Forest, well - thanks. Anyway, there is still room for improvement. Our last version was this: Let x be the highest approval rate (=approval score divided by total number of voters). Draw a ballot at random. With probability 1/(5-4x), the option with the highest approval score amoung those approved on the drawn ballot wins. Otherwise the favourite of that ballot wins. We saw that this method performs well in a large number of situations. But it seems to me that, with more than three options, it can be hard to find the optimal strategies because approving a non-approval-winner can be bad. For example, consider this case: 33: A B C=D=E 34: C B=D A=E 33: E D A=B=C Here the C faction can either cooperate with the A faction to give B a high probability of winning, or with the E faction to give D a high probability of winning. But when the A faction approves of B but the C and E factions approve D, it would have been better for the A faction to have bullet-voted. The following even simpler method, however, makes it safe to approve of an option which does not turn out the approval winner: ** ** Method FAWRB (Favourite-or-Approval-Winner Random Ballot): ** - ** Everyone marks a favourite and may mark any number of also approved ** options. The approval winner X and her approval rate x are ** determined. A ballot is drawn at random. If the ballot approves of X, ** X wins with probability 1/(5-4x). Otherwise, or if the ballot does ** not approve of X, its favourite option wins. ** FAWRB is again monotonic and solves the original challenge problem in the same way as the other methods we discussed recently. But in the above situation it makes it safe for the A and C factions to approve of B and D since only one of the two factions will actually partially transfer their winning probability from their favourite to the compromise option. I guess it should be possible to analyse FAWRBs strategic implications in detail since the method is so extremely simple! I'm pretty sure already that with FAWRB you will never have an incentive to misrepresent your favourite, and seldom or never to approve of one option while not approving of all more preferred options as well. With the other methods these variations of order reversal would occur more often I think. Yours, Jobst PS: I have not yet thought much about your most recent proposals. Only it seems that they won't elect any compromise option that's not the favourite of anyone, right? [EMAIL PROTECTED] schrieb: Jobst wrote ... What do you think about this? I think you have the golden touch! Forest Election-Methods mailing list - see http://electorama.com/em for list info
Re: [Election-Methods] Challenge Problem
Dear Forest, there is another nice aspect to these methods, and that has to do with constructing compromise options by using some sort of utility transfer. Consider this situation of sincere utility assessments of n voters: a: A (1) B (0) b: B (1) A (0) where n b=n-a a 0. Now suppose it was possible - as Warren has suggested some time I think - to transfer some of the utility from the A-voters to the B-voters, e.g. using some kind of side payment. More precisely, let us assume that there were some utility tranfer mechanism T so that the combined option C = A + T gets these assessments of sincere utility: a: A (1) C (alpha) B (0) b: B (1) C (beta) A (0), where a*(1-alpha) = b*beta. The latter condition is equivalent to a*alpha + b*beta = a and means that we assume the side payment can be made so that the total utility received by the B-voters (=b*beta) is the same as the total utility transferred by the A voters (=a*(1-alpha)). Under the assumption that such a utility transfer mechanism was possible, an obvious question is then whether the compromise option C (=option A plus utility transfer) has a chance of actually being elected! With D2MAC, full cooperation (i.e. all voters approving of C) is only an equilirium in the above situation when both alpha = 1/2 + a/2n and beta = 1/2 + b/2n. Together with the condition a*(1-alpha) = b*beta, this implies a = a*alpha + b*beta = n/2 + (a²+(n-a)²)/2n = n - a + a²/n which is equivalent to 0 = a² - 2na + n² = (n-a)² and hence to a = n which is not what we assumed. So, under D2MAC such a compromise would not be elected. With the methods we discussed recently, however, the situation is much better. For both discussed choices of the probability function f, namely f = (degree of cooperation)^4, or f = 1 / ( 5 - 4 * degree of cooperation), we will have an equilibrium with full cooperation as long as alpha = 1/5 + 4a/5n and beta = 1/5 + 4b/5n. Together with the condition a*(1-alpha) = b*beta, this now implies a = a*alpha + b*beta = n/5 + 4(a²+(n-a)²)/5n = n - 8a/5 + 8a²/5n which is equivalent to 0 = a² - 13na/8 + 5n²/8 and hence to a = 13n/16 - sqrt(169n²/256 - 160n²/256) = 5n/8. This means: If the larger faction (a) is at least a 5/8-majority and has a mechanism to transfer arbitrary amounts of utility to the smaller faction (b), then (i): there is a compromise option C which consists of implementing their favourite (A) but having them transfer a total amount of utility b*beta to the smaller faction as compensation, where beta = 1/5 + 4b/5n; and (ii): our methods will make sure that this compromise option C is actually elected with certainty since doing so is a strategic equilibrium. More generally, if we use one of the the probability functions f = (degree of cooperation)^M, or f = 1 / ( 1 + M*(1 - degree of cooperation)) with M1, then the above result is true for majorities of a size of at least 1/2 + 1/2M. What do you think about this? Yours, Jobst I wrote: Dear Forest, I think the following modification of your method is both monotonic and performs better in the 33/33/33-situation: 1. We use approval ballots with favourite option indicated. We determine all approval scores. Assume the highest approval score divided by the number of voters is x. 2. One ballot is drawn. 3. With a probability of P=f(x), that option which has the highest approval score amoung those approved on this ballot wins, otherwise the favourite of that ballot wins. In other words: Perform Random Approval Ballot with a probability of P=f(highest approval rate), else perform Random Ballot. The function f(x) is chosen so that in important reference situations full cooperation is encouraged. Let us assume we want to encourage full cooperation in the following situation: 50: A (1) C (gamma) B (0) 50: B (1) C (gamma) A (0) Here full cooperation is an equilibrium when the expected utility of the A-voters given that all B voters cooperate, is maximal for x=1, and vice versa. As this expected utility is f(x)*(x*gamma + (1-x)*1) + (1-f(x))*1/2, which equals gamma for x=1, the condition on f is this: f(x) = (2gamma-1) / (1 - (2-2gamma)*x) E.g., for gamma=0.6 we can choose f(x) = 1/(5-4x). Let's compare this choice f1(x)=1/(5-4x) with the function f2(x)=x^4 which you used in your method and which will also encourage full cooperation in the above situation with gamma=0.6. More precisely, let's look how they perform in this different situation: 33: A1 A A2 B 33: A2 A A1 B 33: B A1=A2=A If all A-voters cooperate (i.e. approve of A), A will win with a probability of 2/3 * f(2/3) which is 2/7 if f=f1 but only 32/243 if f=f2. It seems f1 will usually give the compromise a larger probability than f2. Finally, why is the above method monotonic? (i) If noone changes approvals but someone marks a different option as
Re: [Election-Methods] Challenge Problem
Dear Forest, I think the following modification of your method is both monotonic and performs better in the 33/33/33-situation: 1. We use approval ballots with favourite option indicated. We determine all approval scores. Assume the highest approval score divided by the number of voters is x. 2. One ballot is drawn. 3. With a probability of P=f(x), that option which has the highest approval score amoung those approved on this ballot wins, otherwise the favourite of that ballot wins. In other words: Perform Random Approval Ballot with a probability of P=f(highest approval rate), else perform Random Ballot. The function f(x) is chosen so that in important reference situations full cooperation is encouraged. Let us assume we want to encourage full cooperation in the following situation: 50: A (1) C (gamma) B (0) 50: B (1) C (gamma) A (0) Here full cooperation is an equilibrium when the expected utility of the A-voters given that all B voters cooperate, is maximal for x=1, and vice versa. As this expected utility is f(x)*(x*gamma + (1-x)*1) + (1-f(x))*1/2, which equals gamma for x=1, the condition on f is this: f(x) = (2gamma-1) / (1 - (2-2gamma)*x) E.g., for gamma=0.6 we can choose f(x) = 1/(5-4x). Let's compare this choice f1(x)=1/(5-4x) with the function f2(x)=x^4 which you used in your method and which will also encourage full cooperation in the above situation with gamma=0.6. More precisely, let's look how they perform in this different situation: 33: A1 A A2 B 33: A2 A A1 B 33: B A1=A2=A If all A-voters cooperate (i.e. approve of A), A will win with a probability of 2/3 * f(2/3) which is 2/7 if f=f1 but only 32/243 if f=f2. It seems f1 will usually give the compromise a larger probability than f2. Finally, why is the above method monotonic? (i) If noone changes approvals but someone marks a different option as favourite, then this doesn't affect x, so monotonicity follows from the monotonicity of Random Ballot in this case. (ii) If noone changes the favourite but someone adds an approval of some option A which has not the maximal approval score, again x is unaffected and monotonicity follows from the monotonicity of Random Approval Ballot this time. (iii) If, finally, noone changes the favourite but someone adds an approval of some option A which already has the maximal approval score, then all of the three values x, f(x), and the winning probability of A under Random Approval Ballot are increased. Thus, some probability is shifted from Random Ballot towards Random Approval Ballot. But since A is an Approval winner, her winning probability under Random Approval Ballot exceeds the one under Random Ballot, so her overall winning probability is increasing as required by monotonicity. QED. Yours, Jobst [EMAIL PROTECTED] schrieb: Dear Jobst, Yes, I meant for more RABMAC probability as the doc increases. If doc were just the max approval (as a percentage of the voters) would the monotonicity problem go away? But then that does nothing to encourage the lesser factions to cooperate. I think you got the essence of the idea here: Looks like a good idea to make the probability of using Random Ballot depend on some degree of cooperation. Perhaps we can salvage it. Forest - Original Message - From: Jobst Heitzig Date: Sunday, June 1, 2008 2:57 pm Subject: Re: [english 90%] Re: Challenge Problem To: [EMAIL PROTECTED] Cc: election-methods@lists.electorama.com Dear Forest, glad you find time to delve somewhat deeper into these questions. Looks like a good idea to make the probability of using Random Ballot depend on some degree of cooperation. Two notes as of now: I guess you meant RABMAC*doc^M + RB*(1-doc^M) instead of RB*doc^M + RABMAC*(1-doc^M), right? And I'm not so optimistic about monotonicity: Consider n voters with these ballots: n-3: A favourite B also approved 2: B favourite 1: C favourite With large n, RB elects A almost surely while RABMAC elects B almost surely. When the last voters switches to approving A also, this is still the case, but the degree of cooperation you defined will increase by almost 1/n. So your method will move probability from the RB- winner A to the RABMAC-winner B while monotonicity demands an increase in A's probability. Details: Before: doc = ((n-3)²+2(n-1)+1)/n² = 1 - 4/n + 8/n² P(A) = 0*doc^M + (n-3)/n*(1-doc^M) After: doc' = ((n-2)²+2(n-1))/n² = 1 - 2/n + 2/n² P(A)' = 1/n*doc'^M + (n-3)/n*(1-doc^M) For M=1: P(A)'-P(A) = 1/n - 2/n² + 2/n³ + (1-3/n)*(-2/n+6/n²) = -1/n + 10/n² - 16/n³ which is negative for n10, right? Maybe this can be fixed somehow be altering the definition of degree of cooperation? Yours, Jobst [EMAIL PROTECTED] schrieb: Dear Jobst, I have a another solution to the challenge problem: p: ACB q: BCA
