[EM] Correspondences between PR and lottery methods (was Centrist vs. non-Centrists, etc.)

[fsimmons at pcc.edu]

----- Original Message -----
From: Kristofer Munsterhjelm 
Date: Monday, July 18, 2011 1:12 pm
Subject: Re: [EM] Centrist vs. non-Centrists (was A distance based method)
To: fsimmons at pcc.edu
Cc: election-methods at lists.electorama.com

> fsimmons at pcc.edu wrote:
> > 
> > ----- Original Message -----
> > From: Kristofer Munsterhjelm 
> > Date: Wednesday, July 13, 2011 2:12 pm
> > Subject: Re: [EM] Centrist vs. non-Centrists (was A distance 
> based method)
> > To: fsimmons at pcc.edu
> > Cc: Jameson Quinn , election-methods at lists.electorama.com
> 
> >> I think you said that these are related, even: that PR 
> methods and 
> >> stochastic single-winner methods are similar, seeking 
> >> proportionality (the former in seats, the latter in time).
> >>
> > 
> > Precisely. Andy Jennings was the one who hit on the key idea for
> > constructing a lottery directly from a PR method; just do an N-
> winner> PR method for large N, and treat the candidates like we 
> treat parties
> > in a party list method; keep the candidates in the running 
> after they
> > have already won a seat. Then the number of seats won by the
> > candidate divided by the total number of seats is the candidate's
> > probability in the lottery.
> 
> How would that work with combinatorial methods like PAV -- would 
> you 
> just clone each candidate a very large number of times? (I guess 
> the 
> question is academic because running a combinatorial method with 
> a very 
> large number of candidates would take too much time anyway.)

An interesting question here is whether PAV woould give the same proportions as sequential PAV in the 
limit.   Also, as usual, proposed slates (with repeats allowed) could be tested to see which gives the 
largest PAV score.

> 
> Also, is there any way of going in the reverse direction? I can 
> see how 
> one could turn the lottery into a party list PR allocation: just 
> give 
> each party a number of seats proportional to the chance they 
> have in the 
> lottery, resolving rounding problems by apportionment algorithm 
> of 
> choice. That works when the number of seats is large.

Right.  Also if the lottery is the Ultimate Lottery, it is the lottery that maximizes the product of ballot 
expectations, so for apportionment you can choose the apportionment that maximizes the 
corresponding product under the constraint that there are n candidates and each gets 1/n of the 
probability. This is more of an indirect conversion based on the method of getting the lottery instead of 
just the lottery probabilities themselves.

>There 
> might be too 
> little information to go to individual member multiwinner 
> methods from a 
> lottery, though.
> Perhaps something to the effect of, when picking n members, just 
> spin a 
> roulette wheel with zones of size proportional to the chances in 
> the 
> lottery. If the ball lands on a zone of an already elected 
> candidate, 
> spin again, otherwise elect the candidate in question. Repeat 
> until n 
> candidates have been elected. That is nondeterministic, however.

You could make it deterministic by using the conditional probabilities, i.e. the probabilities that are 
conditioned on the exclusion of the candidates that have already been chosen.

Another way is to amalgamate the factions by averaging the ballots that have the same top choice 
(weighted average if more than one candidate rated equal top).  The lottery then gives a certain weight to 
each faction that may or may not be equal to the random ballot lottery.  The factions with probability in 
excess of the quota can pass the excess down, just as the factions with a deficiency pass their entire 
probability down to lower rated candidates on their amalgamated rating ballots.  It seems like STV could 
be thought of as using the random ballot lottery probabilities in a similar way.

Andy and I were thinking mostly of Party Lists via RRV.  His question was that if we used RRV, either 
sequential or not, would we get the same result as the Ultimate Lottery Maximization.  I was able to 
show to our satisfaction, that at least in the non-sequential RRV version, the results would be the 
same.  It seems like the initial differences between sequential and non-sequential RRV would disappear 
in the limit as the number of candidates to be seated approached infinity.

Would that imply P=NP?    In other words, sequential RRV might be an efficient method of 
approximating a solution (for large n) of non-sequential RRV (which is undoubtedly NP hard).  What 
would be analogous in the Traveling Salesman Problem?  Don't hold your breath, but it would be 
interesting to sort out the analogy, if possible.