[Election-Methods] Challenge Problem

[Jobst Heitzig]

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


fsimmons at pcc.edu 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: fsimmons at pcc.edu
> Cc: election-methods at lists.electorama.com
> 
>  > 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
>  > >
>  > >
>  > >
>  > >
>  > >
>  >
>  >