Re: What is Data Model FOR?

From: Arthur Keller <arthur_at_kellers_dot_org>
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