Optimal Preferential Voting System & Game Theory Analysis
Explore an optimal preferential voting system based on game theory, focused on determining a good voting rule, comparing different approaches, and defining metrics for voting rule comparison. Dive into the quantitative approach, notation, and a unique game between two voting rules to determine superiority.
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
An Optimal Preferential Voting System Based on Game Theory Ronald L. Rivest Emily Shen MIT CSAIL COMSOC 2010 September 16, 2010
Voting rules Vote: ranking of candidates Voting rule: given a profile of votes, output single winner Question: What makes a good voting rule?
Outline Quantitative approach Optimal voting rule (GT) from game theory Relation to prior work Simulation results Open problems
Traditional approach: axiomatic Long list of well-studied properties: Condorcet Majority Consistency Participation Monotonicity Impossible to satisfy all these criteria Axiomatic approach can give inconclusive advice, depending on perceived relative importance of various criteria
Our approach: quantitative A voting rule F is better than G if voters tend to prefer the outcome of F to the outcome of G Ultimately, a voting rule aims to satisfy voters preferences We will make this precise...
Quantitative approach We define a metric to compare any two voting rules Using this metric, we define a notion of optimality (achievable using game theory) Similar to decision-theoretic approach of [Lu, Boutilier 10] GT is closely related to prior work more on this later
Notation 40 A>B>C>D 30 B>C>A>D 20 C>A>B>D 10 C>B>A>D Profile R = collection of voters rankings of candidates A 0 40 60 0 B 60 0 30 0 C 40 70 0 0 D Preference matrix N: N(x,y) = # voters preferring x to y A B C D 100 100 100 0 Margin matrix M: M(x,y) = N(x,y) N(y,x) A 0 B 20 0 -40 C D A B C D -20 40 0 100 100 100 0 -20 20 -100 -100 -100
Game between two voting rules A voting rule F is better than G if voters tend to prefer the outcome of F to the outcome of G D = distribution on profiles Choose a profile R from D Play a game GR between F and G: F and G choose their outcomes x = F(R), y = G(R) F wins N(x,y) points, G wins N(y,x) points Net: F wins M(x,y) points, G wins M(y,x) points
Relative advantage and optimality Relative advantage AdvD(F,G) = E[M(x,y) / (# voters)] = expected value of average net fraction of voters won by F over G F is at least as good as G (wrt D) if AdvD(F,G) 0 F is optimal if it is at least as good as every other voting rule G wrt any distributionD Equivalently, F is optimal if it is at least as good as every other voting rule G on every profile R
An optimal voting rule (GT) from game theory Use zero-sum two-player game theory to define an optimal voting rule Payoffs = margins Compute optimal mixed strategy Choose winner according to optimal mixed strategy 40 A>B>C>D 30 B>C>A>D 20 C>A>B>D 10 C>B>A>D p(A) = 1/2 p(B) = 1/4 p(C) = 1/4 p(D) = 0
An optimal voting rule must be randomized When there is a Condorcet winner, we don t need randomization If there is a Condorcet cycle, any deterministic rule is sub-optimal Condorcet cycle can be thought of as generalized tie Cave Creek, AZ 09: broke tie for city council seat by drawing cards from a shuffled deck Deterministic variant: GTD Choose candidate with highest probability in optimal mixed strategy
Related work GT is a special case of maximal lottery methods (Fishburn 84) GT support ~ bipartisan set for tournament game (LLL 93) GT game corresponds to plurality game (LLL 94)
Properties of GT Optimality Condorcet winner/loser Pareto efficiency Independence of clones* Reversal symmetry* No monotonicity
Simulated election comparisons Randomly generated 10,000 profiles for 5 candidates, 100 voters, full ballots Spherical distribution 64% had Condorcet winner 77% had unique optimal mixed strategy (Also tried impartial culture distribution)
How does GT perform against other voting rules? Relative Advantage of GT Over Other Voting Rules 3.5 2.998 preferring GT winner Average net % voters 3 2.5 2 1.387 1.5 1 0.252 0.5 0.017 0.008 -0.001 0 plurality IRV Borda minimax Schulze GTD
How often is winner contained in GT support? Agreement of Other Voting Rules with GT Support Proportion of election winners 1.2 1 0.9915 0.9951 contained in GT support 0.8913 1 0.7299 0.8 0.5515 0.6 0.4 0.2 0 plurality IRV Borda minimax Schulze GTD
GTD does slightly better than GT against other common rules Relative Advantage of GT and GTD Over Other Voting Rules Average net % voters preferring GT 3.5 3 or GTD winner 2.5 2 GT 1.5 GTD 1 0.5 0 plurality IRV Borda minimax Schulze
Open problems Is it possible to modify Schulze so it always chooses a winner in GT support? Can one analytically determine AdvD(F,G) for some F,G,D? How sensitive are GT probabilities to input votes? How hard is it to manipulate GT? Can one lower bound the penalty paid for being deterministic, monotonic, etc. for some D?
