Agenda Manipulation in Voting Systems Revealed
Discover the intricacies of rigging elections and competitions through imperfect information manipulation. Explore the challenges, solutions, and implications of agenda rigging in voting protocols.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
How to Rig Elections and Competitions Noam Hazon*, Paul E. Dunne+, Sarit Kraus*, Michael Wooldridge+ *Dept. of Computer Science Bar Ilan University Israel +Dept. of Computer Science University of Liverpool United Kingdom
Outline A common way to aggregate agents preferences - voting But it can be manipulated! Current models assume perfect information We analyzed a model of imperfect information Theoretically, manipulation is hard: NP-Complete proofs Practically it is not: Heuristics and experimental evaluation Conclusion, Future work
Why Voting? Preference aggregation - to a socially desirable decision Not only agents Human decisions among a collection of alternatives Sport tournaments But it can be manipulated if we have perfect information By a single voter or a coalition of voters By the election officer
Our Model - Imperfect Information Agenda rigging by the election officer Linear order Tree order Complexity results Verifying an agenda is in P Finding a perfect agenda seems to be hard Empirical results Easy-to-implement heuristics performed well Tested against random and real data Motivation - better design of voting protocols
Basic Definitions = { , ,..., } Set of outcomes/candidates, 1 2 n Imperfect information ballot matrix M, Voting trees A C B A C B A C A B C D C D
Linear Order Tree Verifying an agenda is O(n2) - with dynamic programming A candidate can only benefit by going late in an order And this is not true for general trees! Finding an order for a particular candidate to win: With a non-zero probability - O(n2) With at least a certain probability
Weak Version of Rigged Agenda A run - An order agenda together with the intended outcomes P[r | M] - a probability that the run will result in our candidate WIIRA Problem - Set of candidates, Imperfect information matrix, M A favored candidate, * A probability p Is there a run in which the winner is *, s.t. P[r | M] p ? NP-C, from the k-HCA problem on tournaments
Balanced Tree Order Verifying an agenda is O(n2) Finding an order for a particular candidate to win: With a non-zero probability - open problem [Lang07] With at least a certain probability - NP-C [Vu08]
From Theory to Practice Concern: It might be that there are effective heuristics to manipulate an election, even though manipulation is NP-complete. Discussion: True. The existence of effective heuristics would weaken any practical import of our idea. It would be very interesting to find such heuristics. [Bartholdi89]
Linear Order Conversion Probabilistic data deterministic data Simple convert Threshold convert 1 - 0.3 0.4 2 0.7 - 0.3 3 0.6 0.7 - 1 - 0 0 2 1 - 0 3 0 1 - 1 1 2 2 3 3 Not better than random order
General Approach Heuristics: Far adversary . . . . Best win Local search Random order 1 2 m-2 m-1 * Two data sets: Random data- uniform and normal distribution Real data - 29 teams from the NBA, top 13 tennis players
Linear Order- Normal Distribution 1 0.9 0.8 0.7 winning probability 0.6 0.5 0.4 optimal far adversary best win simple convert threshold covert local search random order 0.3 0.2 0.1 0 2 10 18 26 34 42 50 # of candidates
Linear Order- 13 Tennis Players 1 0.9 winning probability 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 NADAL, Rafael HAAS, Tommy RODDICK, Andy FERRER, David ANCIC, Mario FEDERER, Roger DAVYDENKO, Nikolay far adversary LJUBICIC, Ivan BLAKE, James BERDYCH, Tomas ROBREDO, Tommy HEWITT, Lleyton GONZALEZ, Fernando optimal best win local search random order
Balanced Tree- Normal Distribution 0.6 optimal far adversary best win local search random 0.5 winning probability 0.4 0.3 0.2 0.1 0 2 6 10 14 18 22 26 30 34 38 42 46 50 54 58 62 66 70 # of candidates
Balanced Tree- 13 Tennis Players 1 winning probability 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 NADAL, Rafael HAAS, Tommy RODDICK, Andy FERRER, David ANCIC, Mario FEDERER, Roger LJUBICIC, Ivan DAVYDENKO, Nikolay BLAKE, James BERDYCH, Tomas ROBREDO, Tommy HEWITT, Lleyton GONZALEZ, Fernando best win optimal far adversary local search random order
Balanced Tree- 29 NBA Teams 0.3 far adversary best win local search random order winning probability 0.2 0.1 0 Bulls Hawks Bucks Suns Knickerbockers Lakers Spurs Nuggets Celtics Kings Cavaliers Clippers Blazers Supersonics Grizzlies Heat 76ers Nets Hornets Jazz Mavericks Pistons Rockets Pacers Wizards Timberwolves Warriors Magic Raptors
Conclusion Two voting protocols with incomplete information Agenda verification is in P Manipulation by the officer seems to be hard Far adversary, best win and local search can help a lot! Future: other voting protocols {hazonn,sarit}@cs.biu.ac.il , {mjw,ped}@csc.liv.ac.uk
