election-methods@mailman.electorama.com

Technical discussion of election methods

View all threads

Some typos fixed, otherwise same as last post

FS
Forest Simmons
Sat, Dec 5, 2015 12:48 AM

I have tweaked things slightly in order to make things slightly simpler and
to make sure that when Range style ballots are used the method reduces to
standard Range in the one winner case.

The general method takes any proportional lottery based on score/range
(including approval) style ballots and converts it into a PR election
method.

Recall that a lottery method is a system of assigning probabilities to
candidates.  A lottery method is "proportional" if it assigns probabilities
in proportion to the respective faction sizes when all faction members vote
with single-minded and exclusive loyalty in favor of their favorite.

Let's suppose that we are in the context of an election where w>0
candidates are to be elected, and that there is at least one subset of
candidates W of size w, such that when our lottery method is applied to W,
all members of W are assigned positive probabilities.

If there is only one such subset, then that is the subset selected by our
method.

Otherwise, for each subset W of candidates of the requisite size w, we do
the following steps:

(1) Partition the ballots into sets S and S' that do and don't,
respectively, give at least one candidate of W a positive rating.

(2) Let p be the probability that a randomly drawn ballot would be a member
of the set S.  Let q = 1 - p. [Note this is a change; the definitions of p
and q have been switched, for esthetic reasons.]

(3) Let p1, p2, ... be the respective probabilities assigned to the members
of W by our lottery method, when that method is restricted to the ballot
set S.

(4) Let a1, a2, ... be the respective averages of the candidate ballot
scores over the respective ballots that rate the respective candidates
positively. [In case of approval, all of these averages will be ones]

Having completed these four steps for each candidate set W of size w, elect
the set W that maximizes the value of the expression

min(a1p1, a2p2, ...)*(p),

Now I will show you the reason for the tweaks:  suppose that w=1.  Then the
value of p1 is 1, and the value of a1 is the average rating of W's only
candidate over the ballots in the set S,  The average rating of W's (only)
member (over the ballots of S') is zero, so the average score over the
union of S and S' is the weighted average  a1p1p + 0q, which simplifies
to a1
p1*p  .  Therefore in the case w=1, the standard range winner wins!

We have mentioned several of the various random ballot lotteries.  More
variations are possible.  Ordinal ballots can be used via the "Implicit
approval cutoff," or with the help of an explicit one.  If the lottery is
random ballot, the only step needing an approval measure is step (4)
above.  There are other possible ways to adapt to ordinal ballots (ranked
preference ballots).

There are other proportional lotteries besides the random ballot ones.  One
is the so called Ultimate Lottery, a restricted version of which is called
the Nash Lottery.  The Nash Lottery Method picks the lottery that maximizes
the product of the ballot expectations based on the lottery.  It turns out
that the crucial factor that makes this lottery proportional is the
"homogeneity" of the ballot expectations in the probabilities.  So if we
widen the admissible ballots to include any homogeneous functions of the
probabilities (along with the natural requirement that such functions not
be decreasing in any of their arguments), then we get the Ultimate Lottery
Method.

Jobst Heitzig has come up with many lotteries, with special attention to
those with low entropy, which makes those lotteries useful in single winner
elections.  Why would we want to use a lottery in single winner elections?
It turns out that the element of chance, when skillfully incorporated, can
(more or less) remove incentives for insincere voting.  The best known
example of this is the "benchmark" standard random ballot lottery.  In that
method there is no incentive for insincere voting, but the resulting
lotteries tend to be high entropy lotteries, hence not good for single
winner elections.

One of Jobst's best methods has two stages.

The first stage generates a set of approval ballots from "thresh-hold"
information supplied by the voters on their ballots.  I won't go into the
details of this stage, but the voters give tentative approvals that allow
the method to automatically build approval ballots that would back-fire on
defectors.

The second stage calculates the total approvals for the respective
candidates and assigns each ballot B to the candidate with the greatest
total approval of any candidate approved on ballot B.  The lottery
probabilities are proportional to the number of ballots assigned to the
respective candidates.

For multi-winner purposes we can replace the first stage with direct use of
approval ballots or by conversion of range ballots into approval ballots
via Toby's idea or by other ideas, including the "sincere approval
strategy" technique, for example.

Where else can we find suitable proportional lotteries?

Andy Jennings found that he could take any sequential PR method and convert
it into a proportional lottery by cloning all of the candidates as many
times as needed, and allowing a huge number of winners.  Then the candidate
lottery probabilities are proportional to the number of clones they have in
the winning circle.

In fact, Andy's first application of that technique (to Warren Smith's RRV,
a version of sequential PAV adapted to range ballots) turned out to be
another way of generating the Nash Lottery.

More recently, Andy and I have seen that there are many ways to convert
practlcally any single winner method into a sequential PR method.

Putting all of this together we have the following diagram:

single winner -> sequential PR -> Lottery -> multi-winner PR

So in a standard way we can convert any single winner method into a
multi-winner PR method that retains some of the flavor of the single winner
method.  Why not just stop at the sequential PR stage?  That's always a
possibility, but sequential methods tend to generate an hierarchy among the
winners in order of election.  It is sometimes better philosophically to
have a method that compares (many if not all) possible winning sets
(including the winning sets generated by various sequential PR methods)
against each other.

In this regard, Jameson Quinn has just invented (and posted to the EM list)
a method that compares candidate subsets on the basis of squared "envy"
summed over the ballots.

Thanks for your patience!

I have tweaked things slightly in order to make things slightly simpler and to make sure that when Range style ballots are used the method reduces to standard Range in the one winner case. The general method takes any proportional lottery based on score/range (including approval) style ballots and converts it into a PR election method. Recall that a lottery method is a system of assigning probabilities to candidates. A lottery method is "proportional" if it assigns probabilities in proportion to the respective faction sizes when all faction members vote with single-minded and exclusive loyalty in favor of their favorite. Let's suppose that we are in the context of an election where w>0 candidates are to be elected, and that there is at least one subset of candidates W of size w, such that when our lottery method is applied to W, all members of W are assigned positive probabilities. If there is only one such subset, then that is the subset selected by our method. Otherwise, for each subset W of candidates of the requisite size w, we do the following steps: (1) Partition the ballots into sets S and S' that do and don't, respectively, give at least one candidate of W a positive rating. (2) Let p be the probability that a randomly drawn ballot would be a member of the set S. Let q = 1 - p. [Note this is a change; the definitions of p and q have been switched, for esthetic reasons.] (3) Let p1, p2, ... be the respective probabilities assigned to the members of W by our lottery method, when that method is restricted to the ballot set S. (4) Let a1, a2, ... be the respective averages of the candidate ballot scores over the respective ballots that rate the respective candidates positively. [In case of approval, all of these averages will be ones] Having completed these four steps for each candidate set W of size w, elect the set W that maximizes the value of the expression min(a1*p1, a2*p2, ...)*(p), Now I will show you the reason for the tweaks: suppose that w=1. Then the value of p1 is 1, and the value of a1 is the average rating of W's only candidate over the ballots in the set S, The average rating of W's (only) member (over the ballots of S') is zero, so the average score over the union of S and S' is the weighted average a1*p1*p + 0*q, which simplifies to a1*p1*p . Therefore in the case w=1, the standard range winner wins! We have mentioned several of the various random ballot lotteries. More variations are possible. Ordinal ballots can be used via the "Implicit approval cutoff," or with the help of an explicit one. If the lottery is random ballot, the only step needing an approval measure is step (4) above. There are other possible ways to adapt to ordinal ballots (ranked preference ballots). There are other proportional lotteries besides the random ballot ones. One is the so called Ultimate Lottery, a restricted version of which is called the Nash Lottery. The Nash Lottery Method picks the lottery that maximizes the product of the ballot expectations based on the lottery. It turns out that the crucial factor that makes this lottery proportional is the "homogeneity" of the ballot expectations in the probabilities. So if we widen the admissible ballots to include any homogeneous functions of the probabilities (along with the natural requirement that such functions not be decreasing in any of their arguments), then we get the Ultimate Lottery Method. Jobst Heitzig has come up with many lotteries, with special attention to those with low entropy, which makes those lotteries useful in single winner elections. Why would we want to use a lottery in single winner elections? It turns out that the element of chance, when skillfully incorporated, can (more or less) remove incentives for insincere voting. The best known example of this is the "benchmark" standard random ballot lottery. In that method there is no incentive for insincere voting, but the resulting lotteries tend to be high entropy lotteries, hence not good for single winner elections. One of Jobst's best methods has two stages. The first stage generates a set of approval ballots from "thresh-hold" information supplied by the voters on their ballots. I won't go into the details of this stage, but the voters give tentative approvals that allow the method to automatically build approval ballots that would back-fire on defectors. The second stage calculates the total approvals for the respective candidates and assigns each ballot B to the candidate with the greatest total approval of any candidate approved on ballot B. The lottery probabilities are proportional to the number of ballots assigned to the respective candidates. For multi-winner purposes we can replace the first stage with direct use of approval ballots or by conversion of range ballots into approval ballots via Toby's idea or by other ideas, including the "sincere approval strategy" technique, for example. Where else can we find suitable proportional lotteries? Andy Jennings found that he could take any sequential PR method and convert it into a proportional lottery by cloning all of the candidates as many times as needed, and allowing a huge number of winners. Then the candidate lottery probabilities are proportional to the number of clones they have in the winning circle. In fact, Andy's first application of that technique (to Warren Smith's RRV, a version of sequential PAV adapted to range ballots) turned out to be another way of generating the Nash Lottery. More recently, Andy and I have seen that there are many ways to convert practlcally any single winner method into a sequential PR method. Putting all of this together we have the following diagram: single winner -> sequential PR -> Lottery -> multi-winner PR So in a standard way we can convert any single winner method into a multi-winner PR method that retains some of the flavor of the single winner method. Why not just stop at the sequential PR stage? That's always a possibility, but sequential methods tend to generate an hierarchy among the winners in order of election. It is sometimes better philosophically to have a method that compares (many if not all) possible winning sets (including the winning sets generated by various sequential PR methods) against each other. In this regard, Jameson Quinn has just invented (and posted to the EM list) a method that compares candidate subsets on the basis of squared "envy" summed over the ballots. Thanks for your patience!