Alex Small | 6 Jun 06:08 2006
Picon

Question about a criterion for ballot counting

I'm still working on a paper that I alluded to in a post to the list a few weeks ago.  In my work, I imposed a condition on election methods that is innocuous for public elections but mathematically somewhat arbitrary:  I assumed that the ballot counting rules can be specified with a finite number of linear inequalities:
 
In practical terms, this is fairly innocuous.  For every election method that's been discussed on this forum you have a short list of rules that can be stated as simple inequalities.  For instance, with IRV:
 
1)  If a candidate's tally of first-place votes is greater than half the number of ballots cast then elect him.
 
2)  Otherwise, eliminate a candidate, transfer votes, and then see if there is a candidate whose tally of votes is grea ter than half the number of ballots cast.
 
And so forth.  (I think we could get into some semantic issues about "ballots cast" and truncation and whatnot, but let's leave that aside.)
 
The rules outlined above are a simple list of statements saying "If [some linear inequality] is true then elect [whichever candidate]."  And there's only a finite number of steps in the process.
 
Mathematically, of course, this is arbitrary.  Mathematically you could define all sorts of arbitrary election rules.  For instance, in a 2-way race the candidate with an odd number of votes could win.  Or you could do something like Borda count, but you could square the number of first-place ballots received by each candidate and then tally up the points from the rest of the ballots in the normal manner.
 
These would be ridiculous, of cou rse, but mathematically admissable.  And the problem is that I'm doing math. Is there a simple criterion that is widely invoked in the literature, one that I could impose to get rid of weird non-linear methods, or methods with an infinite number of "if-then" statements?  I want something that would be understandable by social scientists, not some criterion that uses lots of fancy language from topology or real analysis or whatever.
 
Thanks for any recommendations that anybody can offer.
 

Alex Small

__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com

----
election-methods mailing list - see http://electorama.com/em for list info
Jan Kok | 6 Jun 09:14 2006
Picon

Re: Question about a criterion for ballot counting

I'm not sure I even understand your question! But it sounds like a
very interesting one!

Are the "list of rules" actually procedures? For example, is "if
[condition] then go to step 3" a valid rule?

Are you allowed to set and change variables, e.g. let i=1, let i=i+1 ?

Are you willing to restrict the number of candidates to some small
number, like 4, in order to avoid the need for looping?

As you may know, and I vaguely remember, a Turing Machine (TM) is a
very simple kind of computer. It has only a small handful of
instructions. And yet a TM can do anything that our most powerful
computers can do (if you don't mind waiting, or the TM runs very
fast). So, if the "language" or the "instruction set" that you use to
build your "lists of rules" is sufficient to emulate a TM, then you
can't prevent anyone from computing arbitrary mathematical functions
like square, sine, etc.

So, it seems you must be careful to not make your language as capable
as a Turing Machine! But then, how can it handle arbitrary numbers of
candidates and ballots?

Perhaps you could provide a limited number of loops in a standard
template, such as:

for c = 1 to number_of_candidates
 /* user-supplied instructions allowed here (to initialize candidate
information) */
end for
for b = 1 to number_of_ballots
 /* user-supplied instructions allowed here (to initialize ballot
information) */
end for
for c = 1 to number_of_candidates
 /* user-supplied instructions allowed here */
 for b = 1 to number_of_ballots
  /* user-supplied instructions allowed here */
 end for
 /* user-supplied instructions allowed here */
end for
/* user-supplied instructions allowed here */

Loops and backward jumps would not be allowed in the user-supplied instructions.

My guess is that most voting methods can be described with the above
program template, and some very simple operations such as add a
constant, get the nth element of an array, and get the index in an
array of the nth-largest element.

Am I on the right track?

Cheers,
- Jan
----
election-methods mailing list - see http://electorama.com/em for list info

Jonathan Lundell | 6 Jun 16:25 2006
Picon

Re: Question about a criterion for ballot counting

At 1:14 AM -0600 6/6/06, Jan Kok wrote:
>Loops and backward jumps would not be allowed in the user-supplied 
>instructions.
>
>My guess is that most voting methods can be described with the above
>program template, and some very simple operations such as add a
>constant, get the nth element of an array, and get the index in an
>array of the nth-largest element.

Meek's method (and Warren's) for STV are iterative.
--

-- 
/Jonathan Lundell.
----
election-methods mailing list - see http://electorama.com/em for list info

Alex Small | 6 Jun 17:05 2006
Picon

Re: Question about a criterion for ballot counting

Jan-
 
I imagine something like this:
 
If (condition A1 and condition A2 and...) OR (condition A3 and condition A4 and...) OR ()...  Then elect A
Else If (condition B1 and condition B2 and...) or (condition B3 and condition B4 and...) or ()... Then elect B
 
And so forth.  That's how ordinary voting methods work.  For instance, Plurality:

If (A has more votes than B And A has more votes than C) Then Elect A
Else If (B has more votes than A And B has more votes than C) Then Elect B
Else If (C has more votes than A And C has more votes than B) Then Elect C.
 
For IRV it's a little more complicated:
 
If (A has a majority) OR (C is eliminated and A beats B pairwise) Then Elect A
 
And so forth.
 
For both of those methods, and for any other election method that I can think of, 2 conditions hold:
 
1)  There is only a finite list of conditions to check, and the same list of conditions can be used for any number of ballots cast.
2)  Each condition involves a linear inequality.  When I say "linear", I mean that it's a linear function of the number of ballots cast of each type.  You don't have to, say, take the square of the number of ballots that list A>B>C and add to it the square of the number of ballots that list A>C>B or whatever.  It's all linear.
 
I assumed that the method meets these criteria in my work.  They are perfectly reasonable criteria, and any public election proposal would meet these criteria.  However, mathematically you could construct methods that do n't meet these criteria.  Since I'm doing a mathematical proof I need to exclude methods that involve squares and cube roots and sines and all sorts of other nonlinear stuff, as well as methods that have an infinite number of conditions or whatever.  I would like to be able to just invoke some criterion that's already established in the literature, rather than spend a few paragraphs of the paper digressing on the importance of a list of linear inequalities.
 
Consider that I spent a few paragraphs explaining myself in my first post and you weren't entirely sure that you understood me, and now I've spent a few more paragraphs and I'm still not sure if my point is clear.  I don't want to have to do that in a paper.  I want to be able to say "Look, we have a simple list of rules, with 'simple list' defined in the same way that everybody else defines it (see this reference" and then move on.

Can anybody help me out?


Alex

Jan Kok <jan.kok.5y <at> gmail.com> wrote:
I'm not sure I even understand your question! But it sounds like a
very interesting one!

Are the "list of rules" actually procedures? For example, is "if
[condition] then go to step 3" a valid rule?

Are you allowed to set and change variables, e.g. let i=1, let i=i+1 ?

Are you willing to restrict the number of candidates to some small
number, like 4, in order to avoid the need for looping?

As you may know, and I vaguely remember, a Turing Machine (TM) is a
very simple kind of computer. It has only a small handful of
instructions. And yet a TM can do anything that our most powerful
computers can do (if you don't mind waiting, or the TM runs very
fast). So, if the "language" or the "instruction set" that you use to
build you r "lists of rules" is sufficient to emulate a TM, then you
can't prevent anyone from computing arbitrary mathematical functions
like square, sine, etc.

So, it seems you must be careful to not make your language as capable
as a Turing Machine! But then, how can it handle arbitrary numbers of
candidates and ballots?

Perhaps you could provide a limited number of loops in a standard
template, such as:

for c = 1 to number_of_candidates
/* user-supplied instructions allowed here (to initialize candidate
information) */
end for
for b = 1 to number_of_ballots
/* user-supplied instructions allowed here (to initialize ballot
information) */
end for
for c = 1 to number_of_candidates
/* user-supplied instructions allowed here */
for b = 1 to number_of_ballots
/* user-supplied instructions allowed here */
end for
/* user-supplied instructions allowed here */
end for
/* user-supplied instructions allowed he re */

Loops and backward jumps would not be allowed in the user-supplied instructions.

My guess is that most voting methods can be described with the above
program template, and some very simple operations such as add a
constant, get the nth element of an array, and get the index in an
array of the nth-largest element.

Am I on the right track?

Cheers,
- Jan

__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com

----
election-methods mailing list - see http://electorama.com/em for list info
Kevin Venzke | 6 Jun 18:23 2006
Picon

Re: Question about a criterion for ballot counting

Alex,

The only thing similar that occurs to me is some features Woodall has used.
For instance:

Homogeneous - the result depends only on the proportion of each type of
ballot
Discriminating - the proportion of elections that result in a tie tends to
zero 
as the number of voters in the election tends to infinity
Continuous - if the result isn't a tie, then there's some value greater
than zero
by which every ballot type proportion can be adjusted which will still
result in
the same winner

Don't quote me on these.

Kevin Venzke

	

	
		
___________________________________________________________________________ 
Faites de Yahoo! votre page d'accueil sur le web pour retrouver directement vos services préférés :
vérifiez vos nouveaux mails, lancez vos recherches et suivez l'actualité en temps réel. 
Rendez-vous sur http://fr.yahoo.com/set
----
election-methods mailing list - see http://electorama.com/em for list info

Alex Small | 6 Jun 23:33 2006
Picon

Re: Question about a criterion for ballot counting

Kevin-
 
I have looked at one or two of Woodall's papers.  Do you have a reference for that "continuous" criterion?  It's not quite what I'm looking for, but it's close.
 
Thanks.
 
 
 
Alex

Kevin Venzke wrote:
Date: Tue, 6 Jun 2006 18:23:17 +0200 (CEST)
From: Kevin Venzke
Subject: Re: [EM] Question about a criterion for ballot counting
To: election-methods <at> electorama.com
Message-ID: <20060606162317.36120.qmail <at> web26803.mail.ukl.yahoo.com>
Content-Type: text/plain; charset=iso-8859-1

Alex,

The only thing similar that occurs to me is some features Woodall has used.
For instance:

<snip>
Continuous - if the result isn't a tie, then there's some value greater than zero by which every ballot type proportion can be adjusted which will still result in the same winner
<snip>

Kevin Venzke

__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com

----
election-methods mailing list - see http://electorama.com/em for list info
bql | 7 Jun 00:06 2006

Re: Question about a criterion for ballot counting

This discussion sounds like what I encountered in Computer Science under 
the topics of computability and computational complexity.

I think we can safely say that a good election method is an algorithm that 
executes in bounded time. An election method should not be an exercise in 
solving the Halting Problem.

Almost all election methods I've seen have compuational complexity linear 
in proportion to the number of voters. The Gini Welfare function recently 
discussed here is O(n^2) with the number of voters.

I wrote this up for worst-case asymptotic algorithmic complexity for 
various election methods:
http://bolson.org/voting/bigo.html

It could be argued that to truly scale up, an election method must be 
linear with votes. It could also be argued that any laptop computer is 
good enough to run an election of a million votes, and a $10,000 computer 
could run a billion votes.

Anyway, that's just what I thought of. Maybe it's still not the direction 
you were trying to go.

Brian Olson
http://bolson.org/
----
election-methods mailing list - see http://electorama.com/em for list info

Simmons, Forest | 7 Jun 03:26 2006

Three Stage Approval Election

It's pretty obvious that under Approval you should approve your favorite candidate, and that you should
leave unapproved the candidate that you despise the most.  But it isn't always so obvious which of the
remaining candidates to approve.

A rule of thumb is to approve the candidate that you would vote for under Plurality along with every
candidate that you like better.  This shows that reasonable approval strategy is no harder than Plurality
strategy, but Plurality strategy can be hard sometimes, too.

In general, if you can rank the candidates, but cannot assign relative utilities to them, the optimal
strategy is this:

For each candidate X, approve X if and only if it is more likely that X will end up in a tie for first place with a
candidate that you rank below X than with a candidate that you rank above X.

This strategy maximizes the probability that your ballot will improve the election result from what it
would be if you did not vote.

The hard part is getting reliable estimates of those probabilities.

That is the motivation for this Three Stage Approval approach:

1.  Have a randomly chosen ten percent of the voters submit their approval ballots.

This first ten percent of the voters have a disadvantage in that they must rely on polls, expert opinions,
and their sincere gut feelings to decide their approval cutoffs.

Before the next ten percent of the voters vote, publish the distribution of approvals, including
correlations, from the first ten percent, so that the needed probabilities for optimum approval
strategy can be calculated.

2.  The next ten percent of the voters have the advantage of this additional information.

After the second ten percent casts their approval ballots, update the distribution information.

If this posterior distribution predicts a winning candidate with 99.9 percent certainty, then spare the
remaining 80% the trouble of voting.

3.  Else allow the remaining voters to vote on the basis of the probabilities computed from this new distribution.

Let W1, W2, and W3 be the winners of the respective stages, i.e. the candidates that received the most
approval from the voters in the respective stages.

If  the same candidate wins all three stages, then that candidate is the winner.

Otherwise, have a random number generator pick a number  k  from the set  {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} with equal likelihood.

If  k=1, then W1 is the winner.  If  k=2, then W2 is the winner.  If  K>2, then W3 is the winner.

This method has the potential of saving lots of voters from trips to the polls, when the race is not close.

If the race is close, then at least 80 percent of the voters will have reliable probabilities on which to base
their approval strategies.

Giving W1 and W2 positive probabilities, in proportion to the size of the random sample of voters in the
stages that they won, is a way of discouraging the voters in these samples from voting insincerely in an
effort to manipulate the probabilities for the final stage.

I'm sure that you can think of many variations on these ideas.  But how's that for starters?

Forest

 

Attachment (winmail.dat): application/ms-tnef, 8 KiB
----
election-methods mailing list - see http://electorama.com/em for list info
Abd ul-Rahman Lomax | 7 Jun 04:40 2006

Re: Three Stage Approval Election

I find this staging of polling for Approval interesting. It does 
allow for substantial refinement of voter understanding of the 
situation prior to casting their votes. It would also be exciting to watch.....

The hardest part to sell would be, however, the random selection of 
stage to determine winner. Yes, I understand it and think it might be 
a good idea. Certainly it would be better than what we have!

----
election-methods mailing list - see http://electorama.com/em for list info

Jobst Heitzig | 7 Jun 09:59 2006
Picon

Re: Question about a criterion for ballot counting

Dear Brian!

You wrote:
> The Gini Welfare function recently 
> discussed here is O(n^2) with the number of voters.

No, it's not. It's only O(n*log(n)): Sort the n individual values
x_1,...,x_n to get x(1)>x(2)>...>x(n), then compute the sum of
(2*i-1)*x(i) for i from 1 to n.

Jobst

----
election-methods mailing list - see http://electorama.com/em for list info


Gmane