'&$%CSE 303:Concepts and Tools for Software DevelopmentHal PerkinsAutumn 2007Lecture 20— Societal Implications: Voting (Preferences and Security)CSE303 Autumn 2007, Lecture 20 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 discrete math)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”.CSE303 Autumn 2007, Lecture 20 2'&$%Elections in general• Individual preferences → community choice– the arrow is the “social-choice function”• There are many 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”.CSE303 Autumn 2007, Lecture 20 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 subsetsCSE303 Autumn 2007, Lecture 20 4'&$%It’s worseAnd we’ve been assuming:• each voter’s vote is equally valuable (utilitarians would disagree)• voter’s preferences are “equally spaced”Does it help to give each person 100 votes?Should it be easy or hard to vote?Bottom line: There is discrete math here; computational economics isa hot area.Also: Political elections may never change, but there is on-line voting(often by computers) everywhere!CSE303 Autumn 2007, Lecture 20 5'&$%Ballot PropertiesAfter 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 accurate)• Robust to small errors• Robust to security attackThe paper-ballot method (properly executed) meets these goals,largely because we trust paper and physically observed locked boxes.CSE303 Autumn 2007, Lecture 20 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?CSE303 Autumn 2007, Lecture 20
View Full Document