[Election-Methods] Challenge Problem
Jobst Heitzig
heitzig-j at web.de
Sat Jun 7 05:24:41 PDT 2008
Dear Forest,
there is another nice aspect to these methods, and that has to do with
constructing compromise options by using some sort of "utility transfer".
Consider this situation of sincere utility assessments of n voters:
a: A (1) > B (0)
b: B (1) > A (0)
where n > b=n-a > a > 0.
Now suppose it was possible - as Warren has suggested some time I think
- to "transfer" some of the utility from the A-voters to the B-voters,
e.g. using some kind of side payment.
More precisely, let us assume that there were some "utility tranfer
mechanism" T so that the combined option
C = A + T
gets these assessments of sincere utility:
a: A (1) > C (alpha) > B (0)
b: B (1) > C (beta) > A (0),
where a*(1-alpha) = b*beta.
The latter condition is equivalent to a*alpha + b*beta = a and means
that we assume the side payment can be made so that the total utility
received by the B-voters (=b*beta) is the same as the total utility
transferred by the A voters (=a*(1-alpha)).
Under the assumption that such a utility transfer mechanism was
possible, an obvious question is then whether the "compromise" option C
(=option A plus utility transfer) has a chance of actually being elected!
With D2MAC, full cooperation (i.e. all voters approving of C) is only an
equilirium in the above situation when both
alpha >= 1/2 + a/2n and
beta >= 1/2 + b/2n.
Together with the condition a*(1-alpha) = b*beta, this implies
a = a*alpha + b*beta
>= n/2 + (a²+(n-a)²)/2n
= n - a + a²/n
which is equivalent to
0 >= a² - 2na + n² = (n-a)²
and hence to
a = n
which is not what we assumed. So, under D2MAC such a compromise would
not be elected.
With the methods we discussed recently, however, the situation is much
better. For both discussed choices of the probability function f, namely
f = (degree of cooperation)^4, or
f = 1 / ( 5 - 4 * degree of cooperation),
we will have an equilibrium with full cooperation as long as
alpha >= 1/5 + 4a/5n and
beta >= 1/5 + 4b/5n.
Together with the condition a*(1-alpha) = b*beta, this now implies
a = a*alpha + b*beta
>= n/5 + 4(a²+(n-a)²)/5n
= n - 8a/5 + 8a²/5n
which is equivalent to
0 >= a² - 13na/8 + 5n²/8
and hence to
a >= 13n/16 - sqrt(169n²/256 - 160n²/256) = 5n/8.
This means: If the larger faction (a) is at least a 5/8-majority and has
a mechanism to "transfer" arbitrary amounts of "utility" to the smaller
faction (b), then
(i): there is a compromise option C which consists of implementing
their favourite (A) but having them transfer a total amount of utility
b*beta to the smaller faction as compensation, where beta = 1/5 + 4b/5n;
and (ii): our methods will make sure that this compromise option C is
actually elected with certainty since doing so is a strategic equilibrium.
More generally, if we use one of the the probability functions
f = (degree of cooperation)^M, or
f = 1 / ( 1 + M*(1 - degree of cooperation))
with M>1, then the above result is true for majorities of a size of at
least 1/2 + 1/2M.
What do you think about this?
Yours, Jobst
I wrote:
> 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
>> > >
>> > >
>> > >
>> > >
>> > >
>> >
>> >
>
> ----
> Election-Methods mailing list - see http://electorama.com/em for list info
>
More information about the Election-Methods
mailing list