Hi again,
here's another, somewhat more stable method which also achieves the
following:
> ...
> provides for strategic equilibria in which C is elected with 100%, 55%,
and 100% probability, respectively, in the following situations:
Situation 1:
55% A(100)>C(70)>B(0)
45% B(100)>C(70)>A(0)
Situation 2:
30% A(100)>C(70)>B,D(0)
25% B(100)>C(70)>A,D(0)
45% D(100)>A,B,C(0)
Situation 3:
32% A(100)>C(40)>B,D(0)
33% B(100)>C(40)>A,D(0)
35% D(100)>C(40)>A,B(0)
(All these being sincere utilities)
...
The idea is that for each possible compromise option C, a voter
indicates, by a rating on her ballot, how many voters she requires to
transfer their winning probability to C before she will do so, too.
This is the method:
1. Each of the N voters rates on her ballot each option between 0 and 100.
2. For each option X, put
s(X) = no. of ballots rating X at zero.
3. Put all ballots into a first urn labelled U1, and have another urn
labelled U2, initially empty.
4. For each option X, in order of ascending s(X), do the following:
4.1 Find the smallest number R for which f(R) >= 100, where
f(R) = R + 100 * (no. of ballots in U1 rating X above R) / N.
4.2 For each ballot in U1 rating X above R: Mark X on that ballot and
move the ballot from U1 to U2.
5. On each of the ballots that remained in U1, mark the option with the
highest rating on that ballot and also put the ballot into U2.
6. Draw one ballot at random. The option marked on that ballot wins.
(By "above", we mean strictly above and not equal, of course.)
If there is only one compromise option C besides some polar favourite
options A,B,... , the method essentially simplifies to this:
- Find the smallest R such that at least 100-R percent of the ballots
rate C above R.
- Then draw a ballot at random. If it rates C above R, C wins, otherwise
the option with the largest rating of that ballot wins.
Let's look at the three example situations:
Situation 1 (sincere utilities):
55: A(100)>C(70)>B(0)
45: B(100)>C(70)>A(0)
Take any pair of numbers x,y such that
0 <= x <= 55,
0 <= y <= 45,
x + y > 55,
x > 3y/7, and
y > 3x/7.
It is easy to check from the above true ratings that then all voters
would gain if x of the A-voters and y of the B-voters transferred their
winning probability to C. The voters can make sure this happens in the
suggested method by voting this way:
55-x: A(100)>C(0)=B(0)
x: A(100)>C(101-x-y)>B(0)
y: B(100)>C(101-x-y)>A(0)
45-y: B(100)>C(0)=A(0)
The method would begin with C (receiving the smallest numbers of
0-rates), find R=100-x-y, and mark C on all the x+y ballots, resulting
in these winning probabilities: A:55-x, B:45-y, C:x+y.
No voter has an incentive to reduce her C-rating since that would
immediately move R to 100 and C's winning probability to 0.
So, for each such pair (x,y), the above way of voting is a strategic
equilibrium, the socially best of whose is the one where x=55 and y=45,
C wins with certainty, and the ballots look like this:
55: A(100)>C(1)>B(0)
45: B(100)>C(1)>A(0)
Situation 2 (sincere utilities):
30: A(100)>C(70)>B,D(0)
25: B(100)>C(70)>A,D(0)
45: D(100)>A,B,C(0)
Here the only difference is that we require x+y>30 instead of 55. For
each pair (x,y) with...
0 <= x <= 30,
0 <= y <= 25,
x + y > 30,
x > 3y/7, and
y > 3x/7.
...the following is an equilibrium way of voting which gives C a winning
probability of x+y:
30-x: A(100)>B,C,D(0)
x: A(100)>C(101-x-y)>B,D(0)
y: B(100)>C(101-x-y)>A,D(0)
25-y: B(100)>A,C,D(0)
45: D(100)>A,B,C(0)
Here, the method starts with either X=C or X=D since one of them has the
smallest s(X). Both ways, C will eventually be marked on the x+y ballots
(at R=100-x-y) and D on the 45 ballots (at R=55).
In particular, the socially optimal equilibrium is
30: A(100)>C(46)>B,D(0)
25: B(100)>C(46)>A,D(0)
45: D(100)>A,B,C(0),
resulting in the winning probabilities 55% for C and 45% for D.
Situation 3 (sincere utilities):
32: A(100)>C(40)>B,D(0)
33: B(100)>C(40)>A,D(0)
35: D(100)>C(40)>A,B(0)
Here we consider triples of numbers x,y,z such that
0 <= x <= 32,
0 <= y <= 33,
0 <= z <= 35,
x + y + z > 35,
x + y > 3z/2,
y + z > 3x/2, and
z + x > 3y/2.
In that case, the following is a voting equilibrium:
x: A(100)>C(101-x-y-z)>B,D(0)
y: B(100)>C(101-x-y-z)>A,D(0)
z: D(100)>C(101-x-y-z)>A,B(0)
32-x: A(100)>B,C,D(0)
33-y: B(100)>A,C,D(0)
35-z: D(100)>A,B,C(0)
As in situation 1, the socially best equilibrium is when all voters
cooperate by rating C at 1, making C the sure winner.
It seem the advantage of this method is that it is more stable than the
first one, having a lot more desirable equilibria which. However, the
socially optimal equilibria require a somewhat strange way of voting in
which you understate your true rating of the compromise in order to make
sure not to give others an incentive to reduce their rating and thereby
lessen the compromise's winning probability...
What do you make of this?
Yours, Jobst
(The former method was this:)
The method is surprisingly simple:
1. Each voters assigns a rating between 0 and 1 to each option.
2. For each option, the mean rating is determined.
3. A ballot is drawn at random.
4. For each option, the "score" of the option is the option's rating on
the drawn ballot times its mean rating determined in step 2.
5. The winner is the option with the highest score. In case of ties, the
mean rating is used to decide between the tied options.
First of all, the method is obviously monotonic by definition since both
the mean and product operations are monotonic.
Also, if a faction of p% bullet-votes for some option X (giving it 100
and all others 0), that option gets at least p% winning probability
since whenever one of those ballots is drawn, X gets a score >0 and all
others get a score of 0.
Now let us analyse the equilibria in the above situations.
Situation 1:
55% A(100)>C(70)>B(0)
45% B(100)>C(70)>A(0)
Put
a = .55
b = .45
x = a / sqrt(a²+b²)
y = b / sqrt(a²+b²)
The claimed equilibrium is this:
The first 55% of the voters rate A(1)>C(x)>B(0),
the other 45% of the voters rate B(1)>C(y)>A(0).
The mean ratings are
A: a*1+b*0 = a
B: a*0+b*1 = b
C: a*x+b*y = sqrt(a²+b²)
If one of the first 55% ballots is drawn, the scores are
A: 1*a = a
B: 0*b = 0
C: x*sqrt(a²+b²) = a
so C wins since it has a larger mean rating than A.
Likewise, if one of the other 45% ballots is drawn, the scores are
A: 0*a = 0
B: 1*b = b
C: y*sqrt(a²+b²) = b
so C wins since it has also a larger mean rating than B.
No voter has an incentive to change her rating of C: increasing it
doesn't change a thing; decreasing it would make C's score smaller than
the favourite's score no matter what ballot is drawn, so the resulting
winning probabilities become A(.55), B(.45), C(0) which is not preferred
to A(0), B(0), C(1) by anyone.
Situation 2:
30% A(100)>C(70)>B,D(0)
25% B(100)>C(70)>A,D(0)
45% D(100)>A,B,C(0)
Put
a = .30
b = .25
x = a / sqrt(a²+b²)
y = b / sqrt(a²+b²)
The claimed equilibrium is this:
30% rate A(1)>C(x)>B,D(0)
25% rate B(1)>C(y)>A,D(0)
45% rate D(1)>A,B,C(0)
The mean ratings are
A: a*1 = a
B: b*1 = b
C: a*x+b*y = sqrt(a²+b²)
D: .45
If one of the first 30% ballots is drawn, the scores are
A: 1*a = a
B: 0*b = 0
C: x*sqrt(a²+b²) = a
D: 0*.45 = 0
so again C wins since it has a larger mean rating than A.
It's similar for the 25%. When one of the 45% is drawn, D is elected.
Again, no voter can gain anything by increasing or decreasing her C-rating.
Situation 3:
32% A(100)>C(40)>B,D(0)
33% B(100)>C(40)>A,D(0)
35% D(100)>C(40)>A,B(0)
Put
a = .32
b = .33
d = .35
x = a / sqrt(a²+b²+d²)
y = b / sqrt(a²+b²+d²)
z = d / sqrt(a²+b²+d²)
The claimed equilibrium is this:
32% rate A(1)>C(x)>B,D(0)
33% rate B(1)>C(y)>A,D(0)
35% rate D(1)>C(z)>A,B(0)
The mean ratings are
A: a*1 = a
B: b*1 = b
C: a*x+b*y+d*z = sqrt(a²+b²+d²)
D: d*1 = d
If one of the first 32% ballots is drawn, the scores are
A: 1*a = a
B: 0*b = 0
C: x*sqrt(a²+b²+d²) = a
D: 0*d = 0
so still C wins since it has a larger mean rating than A.
It's again similar for the other voters, and still no voter can gain
anything by increasing or decreasing her C-rating.
Problems:
(a) The stated equilibria are not exactly stable since already a
deviation on the part of one faction gives a different faction the means
to manipulate the scores so that C wins when a ballot from the first
faction is drawn but not when a ballot from their own faction is drawn.
This problem might be bigger or smaller when faction don't know their
respective sizes.
(b) The meaning of the asked-for ratings is not clear. Maybe their
meaning can only be defined operational by pointing out how they are
used in the method. It seems they cannot naively be interpreted as
utilities. All this makes it difficult to tell what a "sincere" rating
would be.
(c) It would be nice if the score formula could somehow be changed so
that the equilibrium ratings would not include the normalization factor
1/sqrt(...). But I fear that this is not possible. I tried to use the
minimum of the individual and the mean score instead of their product,
but that did not result in any equilibria at all. Using a sum or maximum
instead of the product would destroy the bullet-voting property. Also,
using (individual rating)^(some exponent) * (mean rating) does not help.
More ideas I did not have yet. Perhaps the mean rating must be replaced
by some other location statistic such as the median rating. Or perhaps
we somehow include the Q-quantile of the ratings, where Q is the rating
on the drawn ballot...
Any thoughts?
Jobst
Jobst Heitzig schrieb:
Hi folks,
I think I know what the problem is with the idea of somehow
automatically match pairs or larger groups of voters who will all
benefit from a probability transfer: It cannot be monotonic when it
requires that the ballots of all members of the matched group indicate
that the respective voter profits from the transfer.
Look at the simplest version where we have only two voters who submit
favourite and approved information:
Situation I:
Voter 1: A favourite, C also approved
Voter 2: B favourite, C also approved
If we interpret the approval information as an indication that the
voters like C better than tossing a coin between A and B, we would be
tempted to let the method match these voters and transfer both their
winning probabilities from their favourites to C. So C will win with
certainty.
But if we want monotonicity also, C must still win with certainty in
the following situation:
Situation II:
Voter 1: C favourite, A also approved
Voter 2: B favourite, C also approved
But in this situation, a matching algorithm would *not* match the
voters since voter 2 obviously does not seem to profit from such a
transfer.
D2MAC and FAWRB don't have this problem: they are not based on
matching and *do* elect C with certainty in situation II. For this
reason, voter 2 would have incentive *not* to approve of C in
situation II when D2MAC or FAWRB is used. It seems the monotonicity is
paid for by a need for a bit more of information in order to vote
strategically efficient.
A similar argument shows why it is so difficult to solve the following
situation:
Situation III:
Voter 1: A1 favourite, A also approved
Voter 2: A2 favourite, A also approved
Voter 3: B favourite
Suppose we want our method to give A a winning probability of 2/3 in
this situation. Then we have a problem in the following situation:
Situation IV:
Voter 1: A favourite, D also approved
Voter 2: B favourite, D also approved
Voter 3: C favourite, D also approved
Here each of the three voters would have an incentive to change her
ballot and *not* approve of D, since that would move 1/3 of the
winning probability from D to her favourite. So, the strategic
equilibria in situation IV will be
Voter 1: A favourite
Voter 2: B favourite, D also approved
Voter 3: C favourite, D also approved
or
Voter 1: A favourite, D also approved
Voter 2: B favourite
Voter 3: C favourite, D also approved
or
Voter 1: A favourite, D also approved
Voter 2: B favourite, D also approved
Voter 3: C favourite
each of which won't result in D being elected with certainty.
So, it seems we can't have efficient cooperation in both situations
III and IV!
Situation IV seems to be the more important, and D2MAC and FAWRB both
make sure that in situation IV full cooperation is both an equilibrium
and efficient. But for this they need to give A less than 2/3 in
situation III, however.
Yours, Jobst
[EMAIL PROTECTED] schrieb:
What do I think? All of these ideas are better than what I have come
up with, and have great potential, whether or not they might need
some tweaking or even major over haul.
I'll try to digest them more in the mean time, to get a better feel
for their strengths and potential weaknesses.
Marriage and matching procedures certainly seem natural in this setting.
Thanks,
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
----
Election-Methods mailing list - see http://electorama.com/em for list info
