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<Q, 0, else y^n) pC=(x+y)^n - when(X+Y>P, 0, else x^n) - when(X+Y<Q, y^n, else 0). 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: [EMAIL PROTECTED] Cc: [email protected] > 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 > > > > [EMAIL PROTECTED] 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 > > > > ---- Election-Methods mailing list - see http://electorama.com/em for list info
