[EM] A modified Random Ballot that supports compromising

[Jobst Heitzig]

Dear folks!

This post is about the question how Random Ballot can be modified so
that compromising is easy.

Why is this important?

Although pure Random Ballot is only interesting for theoretical reasons,
it is a very useful *ingredient* in the  construction
(non-deterministic) of methods that are both highly strategy-proof and
fair.

When it comes to the election of compromise candidates, Random Ballot
fails, however, and this is what I attempt here to repair in order to
get a "Random Ballot"-like method that supports compromising.

To be more specific, assume we have two factions of sizes  a  and  b
and with favourite candidates A and B, respectively, and having a common
compromise candidate C:

a times A>C>>B
b times B>C>>A

Given these sincere votes, Random Ballot will elect A, B and C with
probabilities a/n, b/n and 0, respectively. In order to give C positive
winning probability, some voters have to order-reverse and vote C
instead of A or B.

But this leads to a prisoners' dilemma, as we can clearly see when we
assume a model with measurable utilies A:1, C:alpha, B:0 for the first
faction and B:1, C:beta, A:0 for the second, with  alpha>a/n  and
beta>b/n.  Let us call voting C "cooperation". Then no matter how many
voters cooperate, the optimal strategy for any voter is *not* to
cooperate, although for everybody mutual cooperation would give a better
expected utility than mutual non-cooperation.

The problem is of course that unilateral cooperation is worse than
mutual non-cooperation, so that only few voters will take the risk and
vote insincerely C hoping that the others will do the same.

Can we modify Random Ballot so that (i) it will not be necessary to vote
insincerely to elect a compromise, and (ii) it is no risk to
unilaterally cooperate in this undertaking?

My favourite solution at the moment is this:

APPROVAL-PRIORITIZED RANDOM BALLOT (AP-RB)
------------------------------------------
1. Ballots are approval-only.
2. Begin the following with all ballots and all candidates.
3. Determine the approval winner among the remaining candidates, using
only the remaining ballots. On all of these ballots which approve this
candidate, mark this candidate and put these ballots aside.
4. Repeat step 3 as long as there are some remaining ballots.
5. From all ballots, draw one at random. The winner is the candidate
marked on that ballot.

For example:

10 A,D
10 A
40 A,C
30 B,C
10 B

C is most approved, so on the middle 70 ballots C is marked and they are
put aside. Remaining:

10 A,D
10 A
10 B

A is most approved, so on the first 20 ballots A is marked and they are
put aside. On the remaining 10 ballots, B is marked. In all:

10 *A*,D
10 *A*
40 A,*C*
30 B,*C*
10 *B*

Consequently the winning probabilities for A,B,C,D are 20,10,70,0 here.

This method, AP-RB, is monotonic, cloneproof, Pareto-efficient, and
always gives the largest probability to the approval winner.

Now back to our original situation:

a times  A:1 > C:alpha >> B:0
b times  B:1 > C:beta  >> A:0

When most voters cooperate and approve C in addition to their favourite,
then C will get the most approval and will thus be marked first on their
ballots, leading to a correspondingly high winning probability for C.
For example:

10 A
45 A,C
40 B,C
05 B
--> 85 C, 10 A, 5 B.

But if only one faction cooperates, they won't loose anything since then
their favourite is marked before C:

10 A
45 A,C
45 B
--> 55 A, 45 B.

However, there is still some risk when too many of the first faction
cooperate, since the other faction could vote like this:

10 A
45 A,C
11 B,C
34 B
--> 56 C, 34 B, 10 A.

In this situations the expected utilities would be
  .10 + .56alpha for the first faction and
  .34 + .56beta  for the second,
compared to
  .55 for the first and
  .45 for the second
when only few cooperate. The former is better for B and worse for A when
  alpha < 45/56 and
  beta  > 11/56.

What would be a safe strategy for the A-supporters? Surely, when only
  a*alpha
many of them approve C, then their expected utility is either
  a/n
when less than  max(a,b)-a*alpha  of the others approve C, and at least
    a*(1-alpha)/n * utility 1
  + (max(a,b)+1)/n * utility alpha
  > a/n
when more than  max(a,b)-a*alpha  of the others approve C.

In other words, the A-supporters take no risk when each of them approves
C with probability alpha. Likewise, the B-supporters take no risk when
each of them approves C with probability beta. With these risk-free
strategies, compromising is successful when
  a*alpha + b*beta > max(a,b).
In that case the winning probabilities are
  A: a*(1-alpha)/n
  B: b*(1-beta)/n
  C: (a*alpha + b*beta)/n.
In particular, C has the largest winning probability then.

So, I'm tempted to claim that also in general, the natural strategy
under "approval-prioritized random ballot" is the following:

THE "PROPORTIONAL" STRATEGY FOR AP-RB
-------------------------------------
Approve candidate X with that probability p for which you would consider
the following two lotteries equally desirable:
a) X is elected with certainty, or
b) your favourite is elected with probability p and your least favourite
otherwise.

Perhaps it turns out that this strategy occurs with ordinary Approval
Voting also?