Computational Social Choice: Algorithmic, Strategic, and ...

Computational Social Choice: Algorithmic, Strategic, and ...

1 Introduction to Social Choice Lirong Xia Jan 29, 2016 Last class: Two goals for social choice GOAL1: democracy GOAL2: truth 3 Change the world: 2011 UK Referendum The second nationwide referendum in UK history The first was in 1975

Member of Parliament election: Plurality rule Alternative vote rule 68% No vs. 32% Yes In 10/440 districts more voters said yes 6 in London, Oxford, Cambridge, Edinburgh Central, and Glasgow Kelvin Why change? Why failed? Which voting rule is the best? 4 Todays schedule: memory challenge Topic: Voting We will learn How to aggregate preferences? A large variety of voting rules

How to evaluate these voting rules? Democracy: A large variety of criteria (axioms) Truth: an axiom related to the Condorcet Jury theorem Characterize voting rules by axioms impossibility theorems Home 1 out 5 Social choice: Voting Profile D R1 R2* R2

Rn* Rn R1* Voting rule Outcome Agents: n voters, N={1,,n} Alternatives: m candidates, A={a1,,am} or {a, b, c, d,} Outcomes: - winners (alternatives): O=A. Social choice function - rankings over alternatives: O=Rankings(A). Social welfare function Preferences: Rj* and Rj are full rankings over A Voting rule: a function that maps each profile to an outcome

6 Popular voting rules (a.k.a. what people have done in the past two centuries) 7 The Borda rule { P= > > 4

> > 2 , , > > 3 > > 2

Borda(P)= Borda scores : 24+4=12 : 2*2+7=11 : 2*5=10 } Positional scoring rules Characterized by a score vector s1,...,sm in non-increasing order For each vote R, the alternative ranked in the i-th position gets si points The alternative with the most total points is the winner Special cases Borda: score vector (m-1, m-2, ,0) [French academy of

science 1784-1800, Slovenia, Naru] } k-approval: score vector (11, 00) k Plurality: score vector (1, 00) [UK, US] Veto: score vector (1...1, 0) 9 Example { P= > >

4 > > 2 Borda , , > > 3

> > 2 Plurality (1- approval) } Veto (2-approval) Off topic: different winners for the same profile? 11 Research 101

Lesson 1: generalization Conjecture: for any m3, there exists a profile P such that for different km-1, k-approval chooses a different winner 12 Research 102 Lesson 2: open-mindedness If we knew what we were doing, it wouldn't be called research, would it? ---Albert Einstein Homework: Prove or disprove the conjecture 13 Research 103

Lesson 3: inspiration in simple cases Hint: look at the following example for m=3 3 voters: a1 > a2 > a3 2 voters: a2 > a3 > a1 1 voter: a3 > a1 > a2 14 It never ends! You can apply Lesson 1 again to generalize your observation, e.g. If the conjecture is true, then can you characterize the smallest number of votes in P? How about adding Borda? How about any combination of voting rules? If the conjecture is false, then can you characterize the set of k-approvals to make it true? 15 Plurality with runoff

The election has two rounds First round, all alternatives except the two with the highest plurality scores drop out Second round, the alternative preferred by more voters wins [used in France, Iran, North Carolina State] 16 Example: Plurality with runoff { P= > >

4 > > 2 First round: Second round: , , > > 3

> > 2 } drops out defeats Different from Plurality! 17 Single transferable vote (STV) Also called instant run-off voting or alternative vote The election has m-1 rounds, in each round,

The alternative with the lowest plurality score drops out, and is removed from all votes The last-remaining alternative is the winner [used in Australia and Ireland] a > b > cc > > dd dd >> aa >> b > c c > d > aa >b 10 7 6 a b > c > d >aa 3 18 Other multi-round voting

rules Baldwins rule Borda+STV: in each round we eliminate one alternative with the lowest Borda score break ties when necessary Nansons rule Borda with multiple runoff: in each round we eliminate all alternatives whose Borda scores are below the average [Marquette, Michigan, U. of Melbourne, U. of Adelaide] 19 Weighted majority graph Given a profile P, the weighted majority graph WMG(P) is a weighted directed complete graph (V,E,w) where V=A for every pair of alternatives (a, b) w(ab) = #{a > b in P} - #{b > a in P}

w(ab) = -w(ba) WMG (only showing positive edges} be cyclic Condorcet cycle: { a>b>c, b>c>a, c>a>b} 1 b a might 1 1 c 20 Example: WMG

{ P= > > 4 > > 2 WMG(P) = 1

, , > > 3 > > 2 } 1 (only showing positive edges)

1 21 WGM-based voting rules A voting rule r is based on weighted majority graph, if for any profiles P1, P2, [WMG(P1)=WMG(P2)] [r(P1)=r(P2)] WMG-based rules can be redefined as a function that maps {WMGs} to {outcomes} Example: Borda is WMG-based Proof: the Borda winner is the alternative with the highest sum over outgoing edges. 22 The Copeland rule The Copeland score of an alternative is its total pairwise wins the number of positive outgoing edges in the WMG

The winner is the alternative with the highest Copeland score WMG-based 23 Example: Copeland { P= > > 4 >

> 2 , , > > 3 > > 2 }

Copeland score: :2 :1 :0 24 The maximin rule A.k.a. Simpson or minimax The maximin score of an alternative a is MSP(a)=minb #{a > b in P} the smallest pairwise defeats The winner is the alternative with the highest maximin score WMG-based 25

Example: maximin { P= > > 4 > > 2 , ,

> > 3 > > 2 } Maximin score: :6 :5

:5 26 Ranked pairs Given the WMG Starting with an empty graph G, adding edges to G in multiple rounds In each round, choose the remaining edge with the highest weight Add it to G if this does not introduce cycles Otherwise discard it The alternative at the top of G is the winner 27 Example: ranked pairs WMG 20 a

12 6 c G b b c d 16 14 8

a d Q1: Is there always an alternative at the top of G? Q2: Does it suffice to only consider positive edges? 28 Kemenys rule Kendall tau distance K(R,W)= # {different pairwise comparisons} K( b c a , a b c ) = 12 Kemeny(D)=argminW K(D,W)=argminW RDK(R,W) For single winner, choose the top-ranked alternative in Kemeny(D) [reveals the truth]

29 Popular criteria for voting rules (a.k.a. what people have done in the past 60 years) 30 How to evaluate and compare voting rules? No single numerical criteria Utilitarian: the joint decision should maximize the total happiness of the agents Egalitarian: the joint decision should maximize the worst agents happiness Axioms: properties that a good voting rules should satisfy measures various aspects of preference aggregation 31

Fairness axioms Anonymity: names of the voters do not matter Fairness for the voters Non-dictatorship: there is no dictator, whose top-ranked alternative is always the winner, no matter what the other votes are Fairness for the voters Neutrality: names of the alternatives do not matter Fairness for the alternatives 32 A truth-revealing axiom Condorcet consistency: Given a profile, if there exists a Condorcet winner, then it must win The Condorcet winner beats all other alternatives in pairwise comparisons The Condorcet winner only has positive outgoing

edges in the WMG Why this is truth-revealing? why Condorcet winner is the truth? 33 The Condorcet Jury theorem [Condorcet 1785] Given two alternatives {a,b}. a: liable, b: not liable 0.5

Then, as n, the probability for the majority of agents preferences is the ground truth goes to 1 34 Condorcets model [Condorcet 1785] Given a ground truth ranking W and p>1/2, generate each pairwise comparison in R independently as follows (suppose c d in W) p c d in R 1-p d c in R c d in W

Pr( b c a | a b c ) = rule [Young JEP-95] Its MLE is Kemenys p (1-p)2 (1-p) 35 Truth revealing Extended Condorcet Jury theorem Given A ground truth ranking W 0.5

the randomly generated profile has a Condorcet winner The Condorcet winner is ranked at the top of W If r satisfies Condorcet criterion, then as n, r will reveal the correct winner with probability that 1. 36 Other axioms Pareto optimality: For any profile D, there is no alternative c such that every voter prefers c to r(D) Consistency: For any profiles D1 and D2, if r(D1)=r(D2), then r(D1D2)=r(D1) Monotonicity: For any profile D1, if we obtain D2 by only raising the position of r(D1) in one vote, then r(D1)=r(D2) In other words, raising the position of the winner wont hurt it 37 Which axiom is more

important? Condorcet criterion Consistency Anonymity/neutrality, non-dictatorship, monotonicity Plurality N Y Y STV (alternative vote)

Y N Y Some axioms are not compatible with others Which rule do you prefer? 38 An easy fact Theorem. For voting rules that selects a single winner, anonymity is not compatible with neutrality proof: Alice > >

Bob > > W.O.L.G. Anonymity Neutrality 39 Another easy fact [Fishburn APSR- 74]

Theorem. No positional scoring rule satisfies Condorcet criterion: suppose s1 > s2 > s3 > 2 Voters > > 1 Voter > > 1 Voter

> > CisOthe Condorcet winner NT RA DI : 3s1 + 2s2 + C 2sT3 IO N < 3 Voters >

: 3s1 + 3s2 + 1s3 40 Arrows impossibility theorem Recall: a social welfare function outputs a ranking over alternatives Arrows impossibility theorem. No social welfare function satisfies the following four axioms Non-dictatorship Universal domain: agents can report any ranking Unanimity: if a>b in all votes in D, then a>b in r(D) Independence of irrelevant alternatives (IIA): for two profiles D1= (R1, ,Rn) and D2=(R1',,Rn') and any pair of alternatives a and b if for all voter j, the pairwise comparison between a and b in Rj is the same as that in Rj' then the pairwise comparison between a and b are the same in r(D1) as in r(D2)

41 Other Not-So-Easy facts Gibbard-Satterthwaite theorem Later in the hard to manipulate class Axiomatic characterization Template: A voting rule satisfies axioms A1, A2, A2 if it is rule X If you believe in A1 A2 A3 are the most desirable properties then X is optimal (unrestricted domain+unanimity+IIA) dictatorships [Arrow] (anonymity+neutrality+consistency+continuity) positional scoring rules [Young SIAMAM-75] (neutrality+consistency+Condorcet consistency) Kemeny [Young&Levenglick SIAMAM-78] 42 Remembered all of these?

Impressive! Now try a slightly larger tip of the iceberg at wiki 43 Change the world: 2011 UK Referendum The second nationwide referendum in UK history The first was in 1975 Member of Parliament election: Plurality rule Alternative vote rule 68% No vs. 32% Yes Why people want to change? Why it was not successful? Which voting rule is the best? 44

Wrap up Voting rules positional scoring rules multi-round elimination rules WMG-based rules A Ground-truth revealing rule (Kemenys rule) Criteria (axioms) for good rules Fairness axioms A ground-truth-revealing axiom (Condorcet consistency) Other axioms Evaluation impossibility theorems Axiomatic characterization 45 The reading questions What is the problem?

social choice Why we want to study this problem? How general it is? It is very general and important How was problem addressed? by designing voting rules for aggregation and axioms for evaluation and comparisons Appreciate the work: what makes the paper nontrivial? No single numerical criterion for evaluation Critical thinking: anything you are not very satisfied with? evaluation of axioms, computation, incentives 46 Looking forward How to apply these rules? never use without justification: democracy or truth?

Preview of future classes Strategic behavior of the voters Game theory and mechanism design Computational social choice Basics of computation Easy-to-compute axiom Hard-to-manipulate axiom You can start to work on the first homework! 47

Recently Viewed Presentations

  • Universidade Federal De Santa Maria Centro De Tecnologia ...

    Universidade Federal De Santa Maria Centro De Tecnologia ...

    Programming the PLC PLC Scan Cycle Ladder Logic Execution Rungs of Ladder diagram are solved from Left to right and top to bottom Branches within rungs are solved top left to bottom right Basic Ladder Programming Basic Ladder Programming Basic...
  • electronics fundamentals circuits, devices, and applications THOMAS L.

    electronics fundamentals circuits, devices, and applications THOMAS L.

    Three-phase transformers are wired in either a wye or a delta configuration or a combination of both. The names refer to the typical schematic representation of the windings. This transformer is a wye-to-delta configuration, which is generally used in step...
  • Diapositiva 1

    Diapositiva 1

    A) DEFINICIÓN: ¿Cómo se define? 1º Etimología 2º Paráfrasis 3º Estructura de la definición ( concepto - ubicación en una clase, propiedades del concepto ) 4º Énfasis en determinados aspectos del concepto: función, composición, propiedades, localización. 5º Inversión de la...
  • Anaerobic Respiration - Fermentation KEY CONCEPT Fermentation allows

    Anaerobic Respiration - Fermentation KEY CONCEPT Fermentation allows

    The process of lactic acid fermentationreplaces the process of aerobic respiration so that the cell can have a continual source of energy, even in the absence of oxygen.
  • CSE 202 -

    CSE 202 -

    We might round each of the first two to 10, and each of the. Last 4 to 20. Then we can view sizes in units of 10, And solve the problem with 1,1,2,2,2,2. The optimal solution for this is: 1,...
  • Inequalities, inequalities….. - World Bank

    Inequalities, inequalities….. - World Bank

    Main points. Global inequality (between world citizens) is some 70 Gini point today. This is the result obtained using new (2005) PPPs . About 9 percent of world population receives one-half of global income (or consumes ½ of goods and...
  • Use of ICT in the Polish health care system, Benefits for ...

    Use of ICT in the Polish health care system, Benefits for ...

    Use of ICT inthePolish health care system . Benefits. for . patients. Magdalena . Gaj. ... Registered users check their medical treatment history (2008-2013) Over 300 . 000. Poles register. e. ... Use of ICT in the Polish health care...
  • שקופית 1 - המכללה העסקית

    שקופית 1 - המכללה העסקית

    צו תעריף המכס והפטורים ומס- קניה התשע"ב - 2012 סיווג - כימיה ופלסטיק מבוא כללי לתעריף המכס ולסיווג