'&$%CSE 303:Concepts and Tools for Software DevelopmentDan GrossmanWinter 2006Lecture 24— Societal Implications: Voting (Preferences and Security)Dan Grossman CSE303 Winter 2006, Lecture 24 1'&$%DiscussionA mix of discussion and some “fascinating things” about voting.Two pretty different issues:1. What should the rules for an election be?• beside political and philosophical issues, there are mathematicaland economic ones (and CS contributes a lot to discret e math)• locally relevant (e.g., new Washington primary system )2. What technology should we use to run elections well?• In particular, should we use computers to tally votes.• locally relevant (e.g., 2004 Washington governor election)The first is “more theory”,the second is “mostly systems with some theory”.Dan Grossman CSE303 Winter 2006, Lecture 24 2'&$%Elections in general• Individual preferences → community choice– the arrow is the “social-choice function”• There are m any questions even before we decide how preferencesare stated and the function is chosen:– Districts vs. proportional representation– Length of term, number of offices– Time between runoffs– Nomination process– ...• To stick to a simple setting, let’s assume n choices, exactly one ofwhich “wins”.Dan Grossman CSE303 Winter 2006, Lecture 24 3'&$%Some “bad” situationsSimple social-choice functions seem to do badly:• plurality, majority, two-party nominations– issues: “wasted votes”, clones, ...• voter’s paradoxesInstant run-off voting (political issue: no deliberation)• Still has shortcomingsArrow’s Theorem (a Nobel prize in Economics ): An impossibilityresult! (Cannot have a social-choice function that ranks ≥ 3 choicesamong ≥ 2 voters and allows any input, is deterministic, allows anyoutcome, disallows dictators, is monotonic (preferences only help), andis consistent for all subset sDan Grossman CSE303 Winter 2006, Lecture 24 4'&$%It’s worseAnd we’ve been assuming:• each voter’s vote is equally valuable (utilitarians would disagree)• voter’s preferences are “equally s paced”Does it help to give each person 100 votes ?Should it be easy or hard to vote?Bottom line: There is discrete m ath here; computational economics isa hot area.Also: Political elections may never change, but there is on-line voting(often by computers) ev erywhere!Dan Grossman CSE303 Winter 2006, Lecture 24 5'&$%Ballot Prope rtiesAfter deciding a voting method, there are still questions like “canvotes be sold”, “should ballots be secret”, etc.• Repudiation (secrecy)• Auditability• Accuracy• Transparency (know they are acc urate)• Robust to small errors• Robust to security attackThe paper-ballot method (properly executed) mee ts thes e goals,largely be cause we trust paper and physically observed locked boxes.Dan Grossman CSE303 Winter 2006, Lecture 24 6'&$%Electronic VotingWhy is going paperless dangerous?Why is handing people a receipt showing who they voted for not asolution?How are the security issues different than when writing desktopsoftware ?How are the security issues different than when writing airplane code?How are the security issues different than when writing banking code?Dan Grossman CSE303 Winter 2006, Lecture 24
View Full Document