[EM] Some chance for consensus (was: Buying Votes)

[Jobst Heitzig]

Dear Raph and Forest,

I have a new idea which might be monotonic, generalizing the 2-voter-marriage idea to larger groups of voters. 

I will define it as an optimization problem: basically, the idea is to find the "socially best" lottery which can 

be produced by starting from the Random Ballot lottery and allowing for one set of voters to reach a contract in which they transfer their share of the 

winning probability from their favourite options to other options. More precisely, the suggested method is this:


1. Each voter submits a cardinal rating for each option.

2. Amoung all possible lotteries that assign winning probabilities to the options, we determine the "feasible" ones. In order to determine whether a given 

lottery L is "feasible", we do the following:

a) Compare L with the Random Ballot lottery, RB, and find the set S of options which have a lower winning probability under L than under RB. Mathematically:

   S = { options X with L(X) < RB(X) },

   where L(X) = probability of option X in lottery L.

b) For each option X in S, determine the number N1(X) of voters who favour X and like L at least as much as RB, judging from their submitted ratings. 

Mathematically:

   N1(X) = no. of voters V with V(L) >= V(RB),

   where V(L) = sum of V(X)*L(X) over all options X
   and V(X) = rating voter V assigned to option X.

c) Also, determine the number N2 of those voters who favour X which must agree to transfer their share of the winning probability from X to other options in 

order to produce L. Mathematically:

   N2(X) = (RB(X)-L(X)) * N,

   where N is the no. of all voters.
  
d) Then check whether N2(X)<=N1(X) for all X in S. If this is fulfilled, then this means that a group of voters exists who have both the means and the 

incentices to change RB into L by transferring winning probability from their respective favourite options to other options. So, if the condition is 

fulfilled, L is considered "feasible".

3. Finally, find amoung the feasible lotteries the one that maximizes a given measure of social utility, e.g. total utility or Gini welfare function or 

median voter utility or whatever. Apply this "socially optimal feasible" lottery to determine the winner.


With sincere voters, the method achieves what we desire:

1. With 55 having A(100)>C(70)>B(0) and 45 having B(100)>C(70)>A(0), the optimal lottery L would be L(A/B/C)=0/0/1. This is feasible since it has S={A,B}, N1(A)=N2(A)=55, and N2(B)=N2(B)=45.

2. With 25 having A1(100)>A(90)>A2(70)>B(0), 25 having A2(100)>A(90)>A1(70)>B(0), and 50 having B(100)>A,A1,A2(0), the optimal lottery L would be L(A/A1/A2/B)=.5/0/0/.5 with S={A1,A2}, N1(A1)=N2(A1)=N1(A2)=N2(A2)=25.


I did not yet analyse the strategic implications, though. So we need to check that and the hoped-for monotonicity. The crucial point for the latter will be what happens when some voter changes her favourite, I guess.

Some final notes: 
- There are always feasible lotteries since the Random Ballot lottery itself is feasible by definition (with the set S being empty). 
- For the same reason, the method gives no lower social utility than Random Ballot.
- Geometrically, the set of "feasible" lotteries is a closed, star-shaped polyeder, but it is usually not convex. (It would be convex if more than one 

contracting group of voters were allowed.)


What do you think?

Jobst


> -----Ursprüngliche Nachricht-----
> Von: "Raph Frank" <raphfrk at gmail.com>
> Gesendet: 31.10.08 15:35:30
> An: "Jobst Heitzig" <heitzig-j at web.de>
> CC: fsimmons at pcc.edu, election-methods at lists.electorama.com,  gregory.nisbet at gmail.com, jacobltaylor at gmail.com
> Betreff: Re: Some chance for consensus (was: [EM] Buying Votes)


> On Fri, Oct 31, 2008 at 11:17 AM, Jobst Heitzig <heitzig-j at web.de> wrote:
> > Dear Raph,
> >
> > you wrote:
> >> I was thinking of a 'stable marriage problem' like solution.
> >
> > Good idea! If it works, the main difficulty will be to make the whole process monotonic, I guess...
> >
> > Yours, Jobst
> 
> I think the method which eliminates the lowest probability candidate
> will be non-monotonic.
> 
> In the single run case, the fundamental problem is that bilateral
> monopolies can exist.  You can gain by not offering compromises.
> However, assuming competition, you might be 'outbid' by another
> voter/party if you do that.
> 

> -----Ursprüngliche Nachricht-----
> Von: "Raph Frank" <raphfrk at gmail.com>
> Gesendet: 31.10.08 15:35:30
> An: "Jobst Heitzig" <heitzig-j at web.de>
> CC: fsimmons at pcc.edu, election-methods at lists.electorama.com,  gregory.nisbet at gmail.com, jacobltaylor at gmail.com
> Betreff: Re: Some chance for consensus (was: [EM] Buying Votes)


> On Fri, Oct 31, 2008 at 11:17 AM, Jobst Heitzig <heitzig-j at web.de> wrote:
> > Dear Raph,
> >
> > you wrote:
> >> I was thinking of a 'stable marriage problem' like solution.
> >
> > Good idea! If it works, the main difficulty will be to make the whole process monotonic, I guess...
> >
> > Yours, Jobst
> 
> I think the method which eliminates the lowest probability candidate
> will be non-monotonic.
> 
> In the single run case, the fundamental problem is that bilateral
> monopolies can exist.  You can gain by not offering compromises.
> However, assuming competition, you might be 'outbid' by another
> voter/party if you do that.
>