[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