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: [email protected]
> 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 n>10, 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: A>C>>B q: B>C>>A
> >
> > Here's the method:
> >
> > 0. The ballots are approval with favorite indicated.
> >
> > 1. First the total approvals are counted and the candidates
> listed in
> > order of approval.
> >
> > 2. For each ballot B, let f(B) be the approval score (as a
> percentage> of the number of ballots cast) of the highest
> candidate on the list
> > approved by B.
> >
> > 3. Let doc (for "degree of cooperation") be the average value
> of f(B)
> > over all ballots.
> >
> > 4. Determine the winner with the lottery RB*doc^M +
> > RABMAC*(1-doc^M), i.e. decide whether to use Random Ballot or
> "Random> Approval Ballot Most Approved Candidate" on the basis
> of the lottery
> > (doc^M, 1-doc^M), where M will be specified below.
> >
> > In the challenge problem, let's suppose that C is rated at R
> and S in
> > the respective factions, with R > p and S >q, and that the approvals
> > are
> >
> > x: AC x': A only y: BC y': B only
> >
> > with x + x' = p, and y + y' = q.
> >
> > Then as long as x + y > max(p, q) we have
> >
> > doc = (x')^2 + (x+y)^2 + (y')^2, and
> >
> > Prob(A wins) = doc^M*x'+ (1-doc^M)*p, Prob(B wins) = doc^M*y' +
> > (1-doc^M)*q, Prob(C wins) = doc^M*(x+y).
> >
> > For later use, note that doc=1 @ (x, y) = (p, q),
> >
> > and that the partial derivative of doc w.r.t. x or y @ (p, q)
> is 2,
> >
> > so that the partial of doc^M w.r.t. x or y @ (p, q) is simply 2*M.
> >
> > The "utility" expectation for the first faction is
> >
> > E1 = P(A wins) + R*P(C wins)
> >
> > If we evaluate the partial derivative w.r.t. x of E1 at the full
> > cooperation point (x, y) = (p, q), we get
> >
> > -1 - 2*M*p + R*(1 + 2*M) = 2*M*(R - p) - (1 - R)
> >
> > which is greater than zero when M is sufficiently large, since
> R > p.
> >
> >
> >
> > Similarly the partial derivative of E2 w.r.t. y at the same
> point is
> >
> >
> > 2*M*(S - q) - (1 - S),
> >
> > which is greater than zero when M is sufficiently large.
> >
> > Therefore, local unilateral defection from full cooperation
> won't pay
> > if M is sufficiently large.
> >
> > If I am not mistaken, the method is monotone and satisfies your
> > property about proportional probability for those factions that
> > steadfastly approve only their favorite.
> >
> > On a technical note, if we replace the lottery (doc^M, 1-
> doc^M) for
> > deciding which kind of random ballot to use with the lottery
> (g(doc),> 1 - g(doc)), where g(t)=1 - (1 - t)^(1/2), then we
> don't have to
> > worry about M.
> >
> > This works because (no matter how large M) the slope of g(t)
> > eventually dominates the slope of t^M as t approaches 1.
> >
> > Nevertheless, for the sake of simplicity I suggest using t^5 instead
> > of g(t).
> >
> > My Best,
> >
> > Forest
> >
> >
> >
> >
> >
>
>
----
Election-Methods mailing list - see http://electorama.com/em for list info
