[Election-Methods] [english 90%] Re: Challenge Problem
Jobst Heitzig
heitzig-j at web.de
Sun Jun 1 14:57:31 PDT 2008
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
fsimmons at pcc.edu 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
>
>
>
>
>
More information about the Election-Methods
mailing list