程序代写代做代考 algorithm AI game graph C Social Choice

Social Choice
COMP4418 Knowledge Representation and Reasoning
Haris Aziz1
1School of Computer Science and Engineering, UNSW Australia
1

How to rank and make recommendations?
2

How to aggregate scheduling preferences?
3

How to agree on a budget?
4

Introduction
Voting Rules
Formal Framework
The Axiomatic Approach Tournament Solutions Important Results Domain Restrictions Randomization
Some Other Rules
Approval-based Committee Voting Further Reading
5

Outline
Introduction
Voting Rules
Formal Framework
The Axiomatic Approach Tournament Solutions
Important Results
Domain Restrictions Randomization
Some Other Rules
Approval-based Committee Voting Further Reading
6

Social Choice
Social Choice is the theory of aggregating preferences of agents into a socially desirable outcome.
• Mostly studied in Economics and Political Science
• Now also studied within Computer Science (computational
social choice)
Applications
• Search Engines: to determine the most important sites
based on links.
• Recommender Systems: to recommend a product to a user based on ratings by users.
7

Social Choice (cont.)
• Multiagent Systems: to coordinate the actions of groups of autonomous software agents.
8

Social Choice
• Plurality is the most common voting rule — it selects the alternative that is ranked first by most voters.
• Why do we study different voting rules when we have the plurality voting rule?
4voters :a≻b≻c≻d 4voters :a≻c≻b≻d 7voters :b≻d≻c≻a 7voters :c≻b≻d≻a
Alternative a is the plurality winner. However plurality may not be the best rule. Why?
10

Social Choice (cont.)
• a majority of voters think a is the worst alternative.
• b, c, and d are better than a in pairwise majority comparisons.
This motivates a study of different voting rules.
12

Voting Rules
• Plurality: alternatives that are ranked first by most voters win.
• Borda: Most preferred alternative gets m − 1 points, the second most-preferred m − 2 points, etc. Alternatives with highest total score win.
• Plurality with runoff: Two alternatives that are ranked first by most voters are short-listed. Then among the shortlisted alternatives, the alternative which is preferred by a majority wins.
• Instant Runoff: Alternatives that are ranked first by the lowest number of voters are removed from consideration. Repeat until no more alternatives can be deleted.
13

Voting Rules (cont.)
33%voters: a≻b≻c≻d≻e 16%voters: b≻d≻c≻e≻a 3%voters: c≻d≻b≻a≻e 8%voters: c≻e≻b≻d≻a 18%voters: d≻e≻c≻b≻a 22%voters: e≻c≻b≻d≻a
• Plurality winner: a
• Borda winner: b
• Plurality with runoff: e (after beating a) • Instant Runoff: d (removal: c, b, e, a)
15

Outline
Introduction
Voting Rules
Formal Framework
The Axiomatic Approach Tournament Solutions Important Results Domain Restrictions Randomization
Some Other Rules
Approval-based Committee Voting Further Reading
16

Formal Framework
Setting:
• Set of agents/voters N = {1,…,n}
• Set of alternatives A = {a1,…,am}
• ≻= (≻1, . . . , ≻n) profile of preferences where each preference ≻i is a linear order over A.
We denote by L(A) the set of linear orders over A.
We denote by Pk(A) as the set of subsets of A of size k.
17

Formal Framework (cont.)
Outcome:
• single selected alternative
• collective preference (linear order)
• set of collective preferences linear orders • a subset of selected alternatives
• probability distribution over alternatives
18

Formal Framework (cont.)
Example (Voting Setting)
N = {1,2,3}, A = {a,b,c,d}
.
1 : a ≻1 b ≻1 c ≻1 d 2 : a ≻2 c ≻2 b ≻2 d 3 : b ≻3 d ≻3 c ≻3 a
20

• Social Welfare Function (SWF): aggregates individual preferences into a collective preference.
F : L(A)n → L(A)
• Social Choice Function (SCF): aggregates individual preferences
into a single selected alternative.
F :L(A)n →A
• Social Choice Correspondence (SCC): aggregates individual preferences into a subset of selected alternatives.
F :L(A)n →2A
21

Formal Framework (cont.)
• Committee Voting Rule: aggregates individual preferences into a subset of selected alternatives of a given size (k).
F : L(A)n → Pk(A)
• Social Decision Scheme (SDS): aggregates individual preferences
into a probability distribution over alternatives. F : L(A)n → ∆(A)
22

Formal Framework
Voting rule is an informal term used for social choice functions, social welfare functions etc.
• A social welfare function can be used as a social choice function: select the first alternative of the output ranking.
• A social choice correspondence can be used as a social choice function: use some tie-breaking rule over the set of alternatives selected.
• A committe voting rule can be used as a social choice function: use it for k = 1.
23

Some classes of Voting Rules
• Based on majority pairwise comparisons
• Decision are made based on pairwise majority comparisons. • An alternative x wins a pairwise majority comparison against
alternativeyif|{i∈N|x≻i y}|>|{i∈N|y≻i x}|. • Based on weighted majority pairwise comparisons
• Decision are made based on weighted pairwise majority comparisons.
• For any two alternatives x , y ∈ A, the weighted majority pairwise comparison for (x,y) is
|{i ∈N |x ≻i y}|−|{i ∈N |y ≻i x}|.
• Positional scoring rules (next slide).
24

Positional Scoring Rules
A positional scoring rule (PSR) is given by a scoring vector s=(s1,…,sm)withs1 ≥s2···≥sm ands1 >sm. Whenavoter puts alternative a in position j, a gets score sj. Alternatives with the maximum total score win.
• Borda rule: PSR with scoring vector (m−1,m−2,…,0)
• Plurality rule: PSR with scoring vector (1, 0, . . . , 0)
• Antiplurality rule: PSR with scoring vector (1, 1, . . . , 1, 0)
• k approval rule: PSR with scoring vector (1,…,1,0,…,0) 􏰅 􏰄􏰃 􏰆
k
25

Outline
Introduction
Voting Rules
Formal Framework
The Axiomatic Approach Tournament Solutions Important Results Domain Restrictions Randomization
Some Other Rules
Approval-based Committee Voting Further Reading
26

Axioms of Voting Rules
• Anonymity: The voting rule treats voters equally: the outcome remains the same as long as the set of votes is the same.
• Neutrality: The voting rule treats alternatives equally: F is neutral if F (π(≻)) = π(F (≻)) where π is a permutation
π : A −→ A.
• Monotonicity: A chosen alternative will still be chosen when it rises in individual preference rankings (while leaving everything else unchanged).
• Pareto optimality: An alternative will not be chosen if there exists another one that all voters prefer the latter to the former.
27

Axioms of Voting Rules (cont.)
• Independence of Irrelevant Alternatives (IIA): If alternative a is socially preferred to b, then this should not change when a voter changes her ranking of c ̸= a, b.
• Non-dictatorial: there exists no voter such that the outcome is always identical to the preference supplied by the dictator.
• Condorcet-extension: if an alternative is pairwise preferred by a majority of voters over every other alternative, then that alternative is selected.
• Strategyproof: A voter cannot misreport his/her preference to select a more preferred alternative.
28

Axioms of Voting Rules
• Anonymity: The voting rule treats voters equally: the outcome remains the same as long as the set of votes is the same. F is anonymous if F (≻) = F (π(≻)) where π(≻) is a profile (≻π(1), . . . , ≻π(n)).
29

Axioms of Voting Rules (cont.)
Example
N = {1,2,3}, A = {a,b,c,d}
1 : a ≻1 b ≻1 c ≻1 d 2 : a ≻2 c ≻2 b ≻2 d 3 : b ≻3 d ≻3 c ≻3 a
3 : a ≻1 b ≻1 c ≻1 d 2 : a ≻2 c ≻2 b ≻2 d 1 : b ≻3 d ≻3 c ≻3 a
An anonymous voting rule should have the same output for both preference profiles.
30

Axioms of Voting Rules
• Neutrality: The voting rule treats alternatives equally: F is neutral if F (π(≻)) = π(F (≻)) where π is a permutation
π : A −→ A.
31

Axioms of Voting Rules (cont.)
Example
N = {1,2,3}, A = {a,b,c,d}
1 : a ≻1 b ≻1 c ≻1 d 2 : a ≻2 c ≻2 b ≻2 d 3 : b ≻3 d ≻3 c ≻3 a
3 : b ≻3 c ≻3 d ≻3 a 2 : b ≻2 d ≻2 c ≻2 a 1 : c ≻1 a ≻1 d ≻1 b
If a neutral voting rule returns a for the first profile, it should return b for the second one.
32

Axioms of Voting Rules
• Monotonicity: A chosen alternative will still be chosen when it rises in individual preference rankings (while leaving everything else unchanged).
33

Axioms of Voting Rules (cont.)
Example
N = {1,2,3}, A = {a,b,c,d}
1 : a ≻1 b ≻1 c ≻1 d 2 : a ≻2 c ≻2 b ≻2 d 3 : b ≻3 d ≻3 c ≻3 a
1 : a ≻1 b ≻1 c ≻1 d 2 : a ≻2 c ≻2 b ≻2 d 3 : b ≻3 d ≻3 a ≻3 c
If a monotonic voting rule returns a for the first profile, it should return a for the second one.
34

Axioms of Voting Rules
• Pareto optimality: An alternative will not be chosen if there exists another one that all voters prefer the latter to the former.
Example
N = {1,2,3}, A = {a,b,c,d}
1 : a ≻1 b ≻1 c ≻1 d 2 : a ≻2 c ≻2 b ≻2 d 3 : c ≻3 d ≻3 a ≻3 b
A Pareto optimal voting rule will not select b because b is Pareto dominated by a.
35

Axioms of Voting Rules
• Independence of Irrelevant Alternatives (IIA): If alternative a is socially preferred to b, then this should not change when a voter changes her ranking of c ̸= a, b.
36

Axioms of Voting Rules (cont.)
Example
N = {1,2,3}, A = {a,b,c,d}
1 : a ≻1 b ≻1 c ≻1 d 2 : a ≻2 c ≻2 b ≻2 d 3 : c ≻3 d ≻3 a ≻3 b
1 : a ≻1 b ≻1 d ≻1 c 2 : a ≻2 c ≻2 b ≻2 d 3 : d ≻3 c ≻3 a ≻3 b
If a is socially preferred over b, then it should still be socially preferred over b, if ranking of d is changed.
37

Axioms of Voting Rules
• Condorcet-extension: if an alternative is pairwise preferred by a majority of voters over every other alternative, then that alternative is selected.
Example
N = {1,2,3}, A = {a,b,c,d}
1 : a ≻1 b ≻1 c ≻1 d 2 : a ≻2 c ≻2 b ≻2 d 3 : c ≻3 d ≻3 a ≻3 b
A Condorcet-extension voting rule should select a.
38

Axioms of Voting Rules
• Strategyproof: A voter cannot misreport his/her preference to select a more preferred alternative.
39

Axioms of Voting Rules (cont.)
Example
N = {1,2,3}, A = {a,b,c,d}
1 : a ≻1 b ≻1 c ≻1 d 2 : c ≻2 a ≻2 b ≻2 d 3 : c ≻3 d ≻3 a ≻3 b
1 : a ≻1 b ≻1 c ≻1 d 2 : c ≻2 b ≻2 d ≻2 a 3 : c ≻3 d ≻3 a ≻3 b
If the voting rule selects a for the first profile and c for the second profile, it is not strategyproof because 2 can manipulate. 40

Condorcet’s Paradox
Condorcet winner: an alternative that is pairwise preferred by a majority of voters over every other alternative.
A Condorcet winner may not exist.
41

Condorcet’s Paradox (cont.)
Example (Condorcet’s Paradox)
1:a≻1 b≻1 c 2 : b ≻2 c ≻2 a 3 : c ≻3 a ≻3 b
c
b
a
42

Axiomatic method
Formal approach
• Characterisation Theorems: show that a particular (class of) rules is the only one satisfying a given set of axioms.
• Impossibility Theorems: show which sets of axioms are incompatible.
43

Outline
Introduction
Voting Rules
Formal Framework
The Axiomatic Approach Tournament Solutions Important Results Domain Restrictions Randomization
Some Other Rules
Approval-based Committee Voting Further Reading
44

Majority Graph
Given (N, A, ≻), the corresponding majority graph is a directed graph(V,E)whereV =Aandinwhich(x,y)∈E ifandonlyifx is preferred over y by a majority of voters. If (x,y) ∈ E, we say that x dominates y. We will denote D(x) = {y | (x,y) ∈ E}.
Assuming there is an odd number of voters, the pairwise majority graph is a tournament (complete and asymmetric graph).
45

Majority Graph (cont.)
Example (Tournament)
N = {1,2,3}, A = {a,b,c,d}.
1:a≻1 b≻1 c≻1 d 2:a≻2 c≻2 b≻2 d 3:b≻3 d≻3 c≻3 a
What is the induced majority tournament?
46

Majority Graph
Example (Tournament)
N = {1,2,3}, A = {a,b,c,d}.
1:a≻1 b≻1 c≻1 d
2:a≻2 c≻2 b≻2 d 3:b≻3 d≻3 c≻3 a
c
b
d
a
47

Copeland Rule
The Copeland rule selects alternatives based on the number of other alternatives they dominate. Define the Copeland score of an alternative x in tournament T = (V , E ) as the outdegree of the alternative.
The set of Copeland winners CO(T) then consists of all alternatives that have maximal Copeland score.
The Copeland rule is a Condorcet-extension.
48

Copeland Rule (cont.)
Example (Tournament)
CO(T) =?
d
a
c
b
50

Copeland Rule (cont.)
Example (Tournament)
CO(T) = {a}.
d
a
c
b
52

Top Cycle
A non-empty subset X ⊆ V of alternatives in a tournament (V , E ) is dominant if every alternative in X dominates every alternative outside X.
The top cycle of a tournament T = (V,E), denoted by TC(T), is the unique minimal dominant subset of V .
Alternative characterization: An alternative is in the top cycle iff it can reach every other alternative by a path in the tournament.
The top cycle rule is a Condorcet-extension.
53

Top Cycle (cont.)
Example (Tournament)
Top cycle=?
d
a
c
b
55

Top Cycle (cont.)
Example (Tournament)
Top cycle: {a,c,d}
d
a
c
b
57

Uncovered Set
The Uncovered Set of a tournament T = (V , E ), denoted by UC(T), is the set of alternative that can reach every other alternative in at most two steps.
The alternatives in the uncovered set are also referred to as kings. The uncovered set rule is a Condorcet-extension.
58

Uncovered Set (cont.)
Example (Tournament)
Uncovered Set: {a,c,d}
d
a
c
b
60

Banks
Under the Banks rule, an alternative x is a Banks winner if it is a top element in a maximal acyclic vertex-induced subgraph of the tournament. The set of Banks winners of a tournament T is denoted by BA(T).
The Bank rule is a Condorcet-extension.
Computing some Banks winner is easy: grow the set of alternative as long as the graph is acyclic. The top element of the set is a Banks winner.
61

Banks (cont.)
Theorem (Woeginger, 2003 )
Checking whether a certain alternative is a Banks winner is NP-complete.
62

Relations between Tournament Solutions
Theorem
Any Copeland winner is a member of the uncovered set. CO(T) ⊆ UC(T)
63

Relations between Tournament Solutions (cont.)
Proof.
• Supposed that an alternative x is a Copeland winner but not a member of the uncovered set.
• This means that x ∪ D(x) ∪ D(D(x)) ̸= A.
• Hence there exists some y ∈ A \ ({x} ∪ D(x) ∪ D(D(x))).
• Thus, D(y) = {x} ∪ D(x) so that Copeland score of y is more than that of x.
64

Relations between Tournament Solutions
Theorem
Any member of the uncovered set is a member of the top cycle. UC(T) ⊆ TC(T).
Proof.
If an alternative is a member of the uncovered set, then it can reach each other alternative in at most two steps so it reaches all other alternatives.
65

Relations between Tournament Solutions
Theorem
Any member of the Banks set is a member of the uncovered set. BA(T) ⊆ UC(T)
66

Relations between Tournament Solutions (cont.)
Proof.
• Consider a Banks winner b which is the the top element of a maximal acyclic subgraph of the tournament with vertex set V ′. Note that b dominates each vertex in V ′ \ {b}.
• Consideranyvertexv∈V\V′.
• Then the graph induced by V ′ ∪ {v } is not acyclic which means that there exist x,y ∈ V′ such that (x,y) ∈ E, (y,v)∈E and(v,x)∈E.
• Ifb=y,thenbdominatesy.
• If b ̸= y, b dominates y which dominates v.
In either case, b reaches v in at most two steps.
67

Outline
Introduction
Voting Rules
Formal Framework
The Axiomatic Approach Tournament Solutions Important Results Domain Restrictions Randomization
Some Other Rules
Approval-based Committee Voting Further Reading
68

May’s Theorem
• Positive reinforcement: A voting rule satisfies positive responsiveness if, whenever some voter reinforces a (possibly tied) winner x in her list, then x will become the unique winner.
Theorem (May, 1952)
A voting rule for two alternatives satisfies anonymity, neutrality, and positive responsiveness if and only if it is the plurality rule.
69

Positional Scoring Rules are not Condorcet-extensions
Theorem (Condorcet, 1785)
Borda’s rule is not a Condorcet-extension when there are 3 or more alternatives.
Theorem (Fishburn, 1973)
No positional scoring rule is a Condorcet-extension when there are 3 or more alternatives.
Consider the following profile:
6voters :a≻b≻c 3voters :c≻a≻b 4voters :b≻a≻c 4voters :b≻c≻a
70

Positional Scoring Rules are not Condorcet-extensions (cont.)
• Score of a: 6s1 +7s2 +4s3 • Score of b: 8s1 +6s2 +3s3 • Score of c: 3s1 +4s2 +10s3
Alternative b is the winner under every PSR. However a is the Condorcet winner.
71

Arrow’s Theorem
Theorem (Arrow’s Theorem)
Any social welfare function (SWF) for three or more alternatives cannot satisfy all the three axioms:
1. Pareto optimality
2. Independence of Irrelevant Alternatives (IIA) 3. Non-dictatorship
72

Arrow’s Theorem (cont.)
73

Muller-Satterthwaite Theorem
• Strong Monotonicity: requires that if an alternative x is a winner in a preference profile P and if a preference profile Q is constructed so that x’s position remains the same or improves with respect to all other alternatives, then x is the winner in Q as well.
Theorem (Muller and Satterthwaite, 1977)
Any social choice function for 3 or more alternatives that is onto and strongly monotonic must be a dictatorship.
74

Gibbard–Satterthwaite Theorem
Theorem (Gibbard–Satterthwaite Theorem)
Any social choice function for three or more alternatives cannot satisfy all the three axioms:
1. Onto
2. Strategyproofness 3. Non-dictatorship
75

Young’s characterization of positional scoring rules
• Reinforcement: A voting rule satisfies reinforcement if, whenever we split the electorate into two groups and some alternative would win in both groups, then it will also win for the full electorate.
• Continuity: A voting rule is continuous if, whenever electorate N elects a unique winner x, then for any other electorate N′ there exists a number k s.t. N′ together with k copies of N will also elect only x.
76

Young’s characterization of positional scoring rules (cont.)
Theorem (Young, 1975)
A voting rule satisfies anonymity, neutrality, reinforcement, and continuity iff it is a positional scoring rule.
77

Outline
Introduction
Voting Rules
Formal Framework
The Axiomatic Approach Tournament Solutions Important Results Domain Restrictions Randomization
Some Other Rules
Approval-based Committee Voting Further Reading
78

Domain Restriction
A preference profile has single-peaked preferences if there exists a left to right ordering > on the alternatives such that any voter prefers a to b if a is between b and her top alternative. We say that the preferences are single-peaked with respect to the ordering >.
Examples
• Airconditioner temperature. • Political spectrum.
79

Domain Restriction (cont.)
Theorem (Bartholdi, III and Trick [1986])
It can be checked in polynomial time whether a given preference profile is single-peaked or not.
80

Domain Restriction
Given a left-to-right ordering >, the median voter rule asks each voter for their top alternative and elects the alternative proposed by the voter corresponding to the median with respect to >.
81

Domain Restriction
Given a left-to-right ordering > such that the preferences are single-peaked with the respect to the ordering, the median voter rule asks each voter for their top alternative and elects the alternative proposed by the voter corresponding to the median top alternative with respect to >.
Theorem (Black’s Theorem, 1948)
If an odd number of voters submit single-peaked preferences, then there exists a Condorcet winner and it will get elected by the median voter rule.
82

Domain Restriction (cont.)
1:A≻B≻C≻D≻E 2:B≻C≻D≻E≻A 3:C≻B≻D≻A≻E
83

Outline
Introduction
Voting Rules
Formal Framework
The Axiomatic Approach Tournament Solutions Important Results Domain Restrictions Randomization
Some Other Rules
Approval-based Committee Voting Further Reading
84

Social Decision Schemes
Social Decision Scheme: aggregates individual preferences into a probability distribution over alternatives.
F : L(A)n → ∆(A)
85

Social Decision Schemes
Random Dictatorship: probability of an alternative is proportional to its plurality score.
Example (Random Dictatorship)
1: a≻b≻c 2: b≻a≻c 3: b≻c≻a
86

Social Decision Schemes
Random Dictatorship: probability of an alternative is proportional to its plurality score.
Example (Random Dictatorship)
1: a≻b≻c 2: b≻a≻c 3: b≻c≻a
p(a) = 1/3, p(b) = 2/3, p(c) = 0.
87

Social Decision Schemes
Random Dictatorship: probability of an alternative is proportional to its plurality score.
Theorem
Random dictatorship is the only social decision scheme that is anonymous, strategyproof, and has Pareto optimal alternatives in the support.
88

Social Decision Schemes
Borda Proportional: probability of an alternative is proportional to its Borda score.
Example (Borda Proportional)
1: a≻b≻c 2: b≻a≻c 3: b≻c≻a
Borda score of a is 3; Borda score of b is 5; Borda score of c is 1; p(a) = 3/9, p(b) = 5/9, p(c) = 1/9.
89

Social Decision Schemes
Borda Proportional: probability of an alternative is proportional to its Borda score.
Theorem
Borda Proportional is strategyproof but may give Pareto dominated alternatives non-zero probability.
90

Outline
Introduction
Voting Rules
Formal Framework
The Axiomatic Approach Tournament Solutions Important Results Domain Restrictions Randomization
Some Other Rules
Approval-based Committee Voting Further Reading
91

Kemeny
• A Kemeny ranking is
argmin 􏰂 |{i∈N|y≻ix}|
>∈L x,y∈A,x>y
• A Kemeny winner is the maximal alternative of a Kemeny ranking.
The Kemeny rule is a Condorcet-extension.
Theorem (Bartholdi et al., 1989)
Finding a Kemeny ranking and a Kemeny winner is NP-hard.
92

Other Voting Rules
• Approval Voting: Each voter approves a subset of alternatives. Alternatives that are approved by most voters win.
• Range Voting: Voters assign up to 100 points to each alternative. Alternatives with the highest total scores win.
• Sequential majority comparisons: Alternatives that win a sequence of pairwise comparisons win.
93

Borda versus Condorcet
• Jean-Charles, chevalier de Borda (1733 – February 1799): French mathematician, physicist, political scientist, and sailor.
• Marquis de Condorcet (1743 – 1794): French philosopher, mathematician, and early political scientist
Combining Borda and Condorcet:
• Black’s rule: Return the Condorcet winner if one exists and the Borda winner otherwise.
• Nanson’s rule: Runoff rule in which alternatives with alternatives with less than the average Borda score are deleted until no more deletions are possible.
94

Summary
• There are many interesting voting rules with relative merits.
• An axiomatic study of voting rules helps understand the
relative merits.
• Voting rules have different computational complexity as well.
• Social choice has many famous impossibility results.
• Considering restricted domains and randomisation are two possible ways to avoid impossibility results.
95

Outline
Introduction
Voting Rules
Formal Framework
The Axiomatic Approach Tournament Solutions Important Results Domain Restrictions Randomization
Some Other Rules
Approval-based Committee Voting
Further Reading
96

Approval Voting
97

Approval Voting
• N = {1, . . . , n}
• A = {a1,…,am}
• (A1,…,An) where Ai ⊂ A is the approval set of voter i.
98

Approval-based Committee Voting
• N = {1, . . . , n}
• A = {c1,…,cm}
• (A1,…,An) where Ai ⊂ A is the approval set of voter i.
Goal: Select specified number of k alternatives. The outcome is called a committee or winning set.
Applications
• Selecting a set of movies
• Ordering some food dishes
• Generalisation of parliamentary apportionment.
99

Approval-based Committee Voting
• N = {1, . . . , n}
• A = {c1,…,cm}
• (A1,…,An) where Ai ⊂ A is the approval set of voter i.
Goal: Select specified number of k alternatives.
• Why not simply use AV (return the k alternatives with the
most approvals)?
• AV used used by American Mathematical Society (AMS), the Institute of Electrical and Electronics Engineers (IEEE), and the International Joint Conference on Artificial Intelligence (IJCAI).
100

Approval-based Committee Voting (cont.)
Example
• N = {1,…,100}, A = {a,b,c,d}, k = 2 • 49 voters approve of c and d.
• 51 voters approve of a and b.
The solution of {a, b} is unfair to the minority.
101

Other Rules for Approval Voting Committee Voting
• S. J. Brams and D. M. Kilgour. Satisfaction approval voting. Voting Power and Procedures, Studies in Choice and Welfare, Springer, 2014.
• S. J. Brams, D. M. Kilgour, and R. M. Sanver. A minimax procedure for electing committees. Public Choice, 132(3-4), 2007.
• D. M. Kilgour. Approval balloting for multi-winner elections. In Handbook on Approval Voting, chapter 6. Springer, 2010.
• D. M. Kilgour and E. Marshall. Approval balloting for fixed-size committees. Electoral Systems, Studies in Choice and Welfare, Springer.
102

Approval-based voting rules
• SAV (Satisfaction Approval Voting) [Brams & Kilgour 2014]
• Voter i gives committee W score |Ai ∩ W |/|Ai |
• Return committee arg maxW ∈Pk (A) 􏰁i ∈N (|Ai ∩ W |/|Ai |)
103

Approval-based voting rules (cont.)
Example
• N = {1,…,100}, A = {a,b,c,d}, k = 2 • 49 voters approve of c and d
• 51 voters approve of a and b
• {a,c} gets score 1100 = 50. 2
• {a, b} gets score 51
104

Approval-based voting rules
• MinimaxAV (Minimax Approval Voting) [Brams, Kilgour & Sanver 2007]:
• DistanceofAi fromW isd(Ai,W)=|Ai \W|+|W\Ai|.
• Select a k-sized committee: argminW∈Pk(A)(maxi∈N d(Ai,W))
105

Approval-based voting rules (cont.)
Example
• N = {1,…,100}, A = {a,b,c,d}, k = 2 • 49 voters approve of c and d
• 51 voters approve of a and b
The outcome is any committee that represents each voter once.
106

Approval-based voting rules
• PAV (Proportional Approval Voting) [Thiele 1895, Simmons 2001]
j=1 j • ui(W)=H(|W∩Ai|)
• Select a size k committee W that is arg maxW ∈Pk (A) 􏰁i∈N ui (W ).
• Let H be a function defined on integers such that H(p) = 0 for p = 0 and H(p) = 􏰁p 1 otherwise.
107

Approval-based voting rules (cont.)
Example
• N={1,…,9},A={a,b,c},k=2 • A1,…,A5 = {a,b}
• A6,…,A9 ={c}.
• The outcome of AV is {a, b}
• The outcome of PAV is {a, c} or {b, c}.
108

Approval-based voting rules
• SeqPAV (Sequential Proportional Approval Voting) [Thiele 1895]
• Sequential version of PAV in which keep selecting alternatives until k are selected.
• w(i)=1foreachi∈NinitiallyandW=∅
• add an alternative to W with maximum approval weight
w(c)=􏰁c∈Ai w(i)
• Updateweightofeachvotertow(i)=1/(1+(|Ai ∩W|)).
109

Approval-based voting rules (cont.)
Example
• N={1,…,9},A={a,b,c},k=2 • A1,…,A5 = {a,b}
• A6,…,A9 ={c}.
• The outcome of AV is {a, b}
• The outcome of SeqPAV is {a, c} or {b, c}.
110

Approval-based voting rules
• AV: select k alternatives with the highest number of approvals.
• SAV (Satisfaction Approval Voting) [Brams & Kilgour 2014]
• Voter i gives committee W score |Ai ∩ W |/|Ai |
• Committee with the highest total score is selected.
• MinimaxAV (Minimax Approval Voting) [Brams, Kilgour & Sanver 2007]
• DistanceofAi fromW isd(Ai,W)=|Ai \W|+|W\Ai|.
• Select a k-sized committee W that minimizes maxi d(Ai,W).
• PAV (Proportional Approval Voting) [Thiele 1895, Simmons 2001]
111

Approval-based voting rules (cont.)
• ui(W)=H(|W∩Ai|)whereH(p)=0forp=0and H(p)=􏰁p 1 otherwise.
j=1 j
• Select a size k committee W that maximizes 􏰁i∈N ui(W).
• SeqPAV (Sequential Proportional Approval Voting) [Thiele 1895]
• Sequential version of PAV
• w(i)=1initiallyandW =∅
• add an alternative to W with maximum approval weight
w(c) = 􏰁i approves c w(i)
• Update weight of each voter to w(i) = 1/(1+(1+|Ai ∩W|)).
112

Generalized PAV and SeqPAV
PAV and SeqPAV use weights 1, 1/2, 1/3….
We can use general weights (w1, w2, . . . , ) to define
(w1,w2,…,)-PAV and (w1,w2,…,)-SeqPAV.
• GreedyAV = (1, 0, . . . , )-SeqPAV chooses alternatives one by one to cover as many unrepresented voters.
113

Approval Voting Committee Voting
• N = {1, . . . , n}
• A = {c1,…,cm}
• (A1,…,An) where Ai ⊂ A is the approval set of voter i.
Goal: Select specified number of k alternatives.
Question: All the rules seem to have the goal of being ‘fair’ or ‘representative’. Can we formalize a reasonable representation axiom?
114

Justified Representation
Idea: if a group of voters have no representation but the group is large enough, then the group deserves some representation.
115

Justified Representation (cont.)
116

Justified Representation
Idea: if a group of voters have no representation but the group is large enough, then the group deserves some representation.
Definition (Justified representation (JR))
Given a ballot profile (A1, . . . , An) over an alternative set A and a target committee size k, we say that a set of alternatives W of size |W | = k provides justified representation for (A, k ) if
∀X ⊆ N : |X | ≥ n and | ∩i ∈X Ai | ≥ 1 =⇒ (|W ∩ (∪i ∈X Ai )| ≥ 1) k
• k = 1: JR is satisfied unless there exists an alternative approved by all, but we pick an alternative not approved by anyone
117

Justified Representation
Example
• N = {1,2,3,4,5,6,7,8,9}, A = {c1,c2,c3,c4,c5}, k = 3
A1 =A2 =A3 =A4 =A5 :{c1,c2,c3} A6 =A7 =A8 :{c4}
JR requires that c4 is selected.
A9 :{c4,c5}
118

Is there a rule that satisfies Justified Representation?
Theorem
GreedyAV ((1,0,0,..)-SeqPAV) always returns a committee that satisfies JR.
Proof: Recall the rule: GreedyAV = (1, 0, . . . , )-SeqPAV chooses alternatives one by one to cover as many unrepresented voters.
• Suppose after k steps we have n/k uncovered voters who all approve a
• a’s weight is n/k
• then at each step we chose an alternative that covered n/k
uncovered voters
• thus we should have covered all n voters
PAV also satisfies JR.
119

Rules that fail JR
• AVfailsJRfork≥3
• SAVfailsJRfork≥2
• MinimaxAV fails JR for k ≥ 2 • SeqPAV fails JR for k ≥ 6
120

Satisfying Justified Representation (JR)
Rule
JR
AV – SAV – MinimaxAV – SeqPAV – GreedyAV 􏰇 PAV 􏰇
Table 1: Satisfaction of JR.
121

Extended Justified Representation
Definition (Justified representation (JR)1)
Given a ballot profile (A1, . . . , An) over an alternative set A and a
target committee size k, we say that a set of alternatives W of size |W | = k provides justified representation for (A, k ) if
∀X ⊆ N : |X | ≥ n and |∩i ∈X Ai | ≥ 1 =⇒ (∃i ∈ X : |W ∩Ai | ≥ 1). k
1Haris Aziz, Markus Brill, Vincent Conitzer, Edith Elkind, Rupert Freeman, Toby Walsh: Justified representation in approval-based committee voting. Soc. Choice Welf. 48(2): 461-485 (2017)
122

Complexity of PAV and finding an EJR committee
• PAV is the only known natural rule that satisfies EJR. • However PAV outcome is NP-hard to compute.3
• even if each agent approves of 2 alternatives.
• Checking if a committee provides EJR is coNP-complete
3Aziz, H., Gaspers, S., Gudmundsson, J., Mackenzie, S., Mattei, N., Walsh, T., 2015. Computational aspects of multi-winner approval voting. In: Proceedings of the 14th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS).
124

Satisfying JR and related notions
Rule
JR PJR EJR Complexity
AV –––inP SAV –––inP MinimaxAV – – – NP-hard SeqPAV – – – inP GreedyAV 􏰇 – – in P PAV 􏰇 􏰇 􏰇 NP-hard
Table 2: Satisfaction of JR, PJR, and EJR and computational complexity of approval-based voting rules.
125

PAV
PAV proposed by Danish polymath Thorvald N. Thiele (1838–1910).4
126

PAV (cont.)
• PAV is the only known natural rule that satisfies EJR.
4Svante Janson. Phragmen’s and Thiele’s Election Methods. Working Paper 2016.
127

Satisfying EJR
• GreedyAV fails PJR and EJR
• PAV satisfies PJR and EJR
• (w1, w2 . . . , )-PAV fails EJR and PJR for any weights not equal to (1, 1/2, 1/3, . . .)
Theorem (Characterisation of PAV)
PAV is the only (w1, w2 . . . , )-PAV rule that satisfies EJR and PJR.
128

Summary
Rule
Complexity of Achieving in P Complexity of Testing in P
JR
PJR
in P coNP-complete
EJR
in P coNP-complete
Table 3: Complexity
129

Outline
Introduction
Voting Rules
Formal Framework
The Axiomatic Approach Tournament Solutions Important Results Domain Restrictions Randomization
Some Other Rules
Approval-based Committee Voting Further Reading
130

Reading
Social choice chapters of the following books:
• Y. Shoham and K. Leyton-Brown. Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. 2009. http://www.masfoundations.org
• N. Nisan, T. Roughgarden, E. Tardos, and V.V. Vazirani. Algorithmic Game Theory. Cambridge University Press, 2007. www.cambridge.org/journals/nisan/downloads/Nisan_ Non-printable.pdf
131

References
J. Bartholdi, III and M. Trick. Stable matching with preferences derived from a psychological model. Operations Research Letters, 5(4):165–169, 1986.
132

Related Posts