From: Arthur Keller <arthur_at_kellers_dot_org>

Date: Thu Apr 29 2004 - 14:48:30 CDT

Date: Thu Apr 29 2004 - 14:48:30 CDT

At 2:28 PM -0500 4/29/04, Douglas W. Jones wrote:

*>On Apr 29, 2004, at 11:25 AM, Arthur Keller wrote:
*

*>
*

*>>Mark, I'm confused by your answer.
*

*>>
*

*>>Since ranked preference voting says: A, B, C is different than B,
*

*>>A, C, there are more than 6 possible vote combinations for 3
*

*>>candidates. (ABC, ACB, BAC, BCA, CAB, CBA are the full ones; also
*

*>>A, B, C, AB, BA, AC, CA, BC, CB, and no choices selected. Wow,
*

*>>that's 16 choices. Does someone have a formula in closed form for
*

*>>the number of possible rankings for n candidates? For the full
*

*>>ones, its the number of permutations of n candidates, or n! (n
*

*>>factorial).)
*

*>
*

*>This works, if you're willing to allocate n! bins for your ranked preference
*

*>ballot. Imagine doing that with the California Recall election with 140
*

*>or so candidates.
*

Since few people will rank all 136 or so candidates, it appear likely

that there will be far, far fewer actual bins. For in memory, a Trie

is actually a nice data structure. My other discussion talks about

how to do it with a relational database. If people rank preferences

among at most 3 candidates out of the 140, when we're talking about

at most few million bins, and more likely a lot fewer, which is

tractable.

*>But, with weighted preference, there are simple reconciliation schemes.
*

*>If you have 3 candidates, A, B and C, you give your first candidate 3
*

*>votes, your second choice candidate 2 votes, and your third choice candidate
*

*>1 vote. In sum, you have 6 votes to distribute over 3 candidates, so your
*

*>reconciliation scheme can be based on making sure that the number of votes
*

*>adds up to 6 times the number of ballots counted (and if I only vote for two
*

*>candidates, I have 3 undervotes, while if I only vote for one, I have one
*

*>undervote). This reconciliation rule is computationally more tractable than
*

*>the n! rule.
*

*>
*

*>Similarly, for STV/IRV systems, you treat the ABC race as 3 races, one for
*

*>first place, one for second place, and one for third place, and reconcile
*

*>votes that way as you're carrying votes forward from the precinct to the
*

*>center. These numbers aren't the overall winners, just a convenient
*

*>reconciliation rule. Again, cheaper than n!
*

That's true you have easier ways to reconcile. However, since you

already have to tabulate the actual results in order to do IRV (for

example), you might as well reconcile the actual results. The

computational process for a few thousand votes in a precinct isn't

that large (particularly since you have the actual ballot IDs and can

compare the electronic and paper version of the same ballot ID). As

you roll up, you can still reconcile the same way you tabulate.

What advantages are there to reconciling using a simpler process than

tabulation?

*> Doug Jones
*

*> jones@cs.uiowa.edu
*

Best regards,

Arthur

-- ------------------------------------------------------------------------------- Arthur M. Keller, Ph.D., 3881 Corina Way, Palo Alto, CA 94303-4507 tel +1(650)424-0202, fax +1(650)424-0424 ================================================================== = The content of this message, with the exception of any external = quotations under fair use, are released to the Public Domain ==================================================================Received on Fri Apr 30 23:17:24 2004

*
This archive was generated by hypermail 2.1.8
: Fri Apr 30 2004 - 23:17:29 CDT
*