...NP-hard
A problem is said to be NP-hard if it cannot be solved in polynomial time. If n is a variable describing the complexity of the problem (for example, number of voters or number of alternatives), we say that the problem can be solved in polynomial time if we can solve it in n, 6#6, 7#7, or another power of n steps. On the other hand, if the problem requires 8#8, 9#9, or another number raised to the 10#10 power steps to solve, it becomes quite intractable as n increases and is thus NP-hard [53]
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...scale.
The concept of utilities is theoretically grounded in the Von Neumann-Morgenstern method of determining cardinal measures of preference [104] However, in reality many people are unable to understand this method or use it to determine their utilities. Less precise estimates of utilities will often suffice.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...``chad'' 
The New Hacker Hacker's Dictionary explains a possible origin for the word chad:
One correspondent believes chad ... derives from the Chadless keypunch (named for its inventor), which cut little u-shaped tabs in the card to make a hole when the tab folded back, rather than punching out a circle/rectangle; it was clear that if the Chadless keypunch didn't make them, then the stuff that other keypunches made had to be `chad' [84].
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...cryptography
Public-key cryptographic algorithms use a pair of cryptographic keys: a public key and a private key. A message encrypted with a public key can only be decrypted with the corresponding private key and vice versa. In addition to protecting secrets, public key cryptography can also serve as a digital signature to authenticate electronic documents.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...signatures
Blind signatures allow a document to be signed without revealing its contents. The effect is similar to placing a document and a sheet of carbon paper inside an envelope. If somebody signs the outside of the envelope, they also sign the document inside. The signature remains attached to the document, even when it is removed from the envelope. Chaum [29] and Schneier [95] provide more background information on public-key cryptography, digital signatures, and blind signatures.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...pamphlet
Dodgson's unpublished pamphlet ``A method of taking votes on more than two issues,'' is reproduced as an appendix to [13].
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...HREF="node13.html#figblack">gif.
Note that the example assumes that the predicted outcome ranks candidate 1 in first place, 2 in second place, and 3 in third place. If this predicted ranking does not match the voter's preference ranking, the appropriate substitutions must be made. For example, if the voter had the preference ranking 3 over 2 over 1, the voter's 50#50 would refer to the probability of a tie between candidates 2 and 3.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...approximation
Thanks to Professor Edward Spitznagel for suggesting this approximation.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

lorrie@acm.org