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: election-methods@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
[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
