CS代考 Lecture 1: Introduction – cscodehelp代写
Lecture 1: Introduction
Social choice
1
Motivating example: Placing charging points
There is demand for public electric vehicle charging points to be installed, but each installation costs
People prefer points nearer their homes, work, etc.
How might a city distribute an affordable amount of charging points that best meets residents’ demands?
If citizens vote on locations, what is a fair way to decide?
Slide ‹#› out of 63
Today
Social choice theory = making group decisions
Voting protocols
Desirable properties for voting protocols as agreement mechanisms
Slide ‹#› out of 63
Social choice theory
Social choice theory is about how to make group decisions.
Specifically, it provides a range of voting protocols that can be used to account for the preferences of a group of agents.
As always, agents are self-interested and so want to influence the outcome of the decision to match their preferences.
Slide ‹#› out of 63
Domain definition
We assume a set of voters. These are agents who will express their preferences over the set of possible outcomes.
Voters make group decisions with respect to a set of outcomes (or candidates).
Each voter has a preference ordering over the set of possible outcomes .
Slide ‹#› out of 63
Preferences
We assume that voters’ preferences are complete:
For every pair of distinct alternatives and , each voter either prefers to , or they prefer to .
We assume that voters’ preferences are transitive:
If a voter prefers to and they prefer to , then they must also prefer to .
This means we can capture a voter’s preference as a ranked list.
Slide ‹#› out of 63
Preferences example
Five agents are trying to decide what colour to paint a room, either green, blue or orange. The agents’ preferences are given below.
denotes agent ’s preference order.
Slide ‹#› out of 63
Preference aggregation
The fundamental problem of social choice theory is one of preference aggregation:
given a collection of preference orders, one for each voter, how do we combine these to derive a group decision, that reflects as closely as possible the preferences of the voters?
There are two variants of preference aggregation:
Social welfare functions
Social choice functions
Slide ‹#› out of 63
Social welfare and social choice
Let be a set of preference orderings over .
A social welfare function takes the voter preferences and produces a social preference order:
We let denote the outcome of a social welfare function.
A social choice function takes the voter preferences and selects a single outcome:
Slide ‹#› out of 63
Plurality voting
Plurality voting is a social choice function, i.e. it selects a single outcome.
Each voter submits their preferences. Each candidate gets one point for every preference order that ranks them first. The winner is the one with largest number of points.
Exercise
and .
40 agents have the preference .
30 agents have the preference .
30 agents have the preference .
Which outcome is selected?
Slide ‹#› out of 63
Strategic voting
Using strategic voting, if we have knowledge of other agents’ preferences, we can sometimes communicate false a preference order to get a preferred candidate chosen.
Exercise
Suppose your preferences are .
You believe 49% of the voters have preferences .
You believe 49% of the voters have preferences .
What would you do?
Slide ‹#› out of 63
Condorcet principle
The Condorcet winner is an outcome that beats every other outcome in pairwise majority contests.
Exercise
and .
40 agents have the preference .
30 agents have the preference .
30 agents have the preference .
Which candidate is the Condorcet winner?
Slide ‹#› out of 63
Condorcet’s paradox
Suppose and with
For every possible candidate, there is another candidate that is preferred by the majority of the voters!
This is Condorcet’s paradox. There are situations in which, no matter which outcome we choose, a majority of voters will prefer another candidate.
Slide ‹#› out of 63
13
Linear sequential majority elections
Linear sequential majority is a variant of plurality voting.
Players play in a series of rounds. A pair of outcomes face each other in a pairwise election, the winner goes on to the next round. The order in which the outcomes face each other is determined by an agenda.
For example, if the agenda is then the first election is between and , the winner of that goes onto an election with , and the winner of that goes onto an election with .
Slide ‹#› out of 63
14
Linear sequential majority elections
We can represent voter preferences with a majority graph.
Nodes represent the candidates and there is an edge from node to if and only if would beat in a simple majority election.
A problem is that the outcome selected might depend not just on voter preferences but also on the agenda
Exercise
33 voters have preference
33 voters have preference
33 voters have preference
What is the majority graph?
How do we fix the agenda so that wins?
Slide ‹#› out of 63
15
Instant runoff rule
In instant run-off, a series of mini-elections are held in which the candidate with the fewest votes in each round is eliminated.
Each round:
votes are counted for everyone’s first choice and the one with the fewest votes is eliminated;
any voter who had the eliminated option as their first choice, the votes for their second choice are now counted and we go again.
The last candidate remaining is the winner.
Slide ‹#› out of 63
16
Exercise
Who is the winner if we use instant run-off voting?
Slide ‹#› out of 63
17
Copeland rule
Under voting, all candidates face pairwise majority contest against all other candidates.
Each candidate receives 1 point for every pairwise majority contest that they win, loses 1 point for every pairwise majority contest that they lose, or no points for a tie.
The candidate with the most points is the winner.
Slide ‹#› out of 63
18
Exercise
Who is the winner under voting?
Slide ‹#› out of 63
19
Borda Count
In a Borda Count, each candidate receives points for each voter that lists them as their first choice, points for each voter that lists them as their second choice etc. (where is the number of candidates).
The candidate with the most points is the winner.
Slide ‹#› out of 63
20
Exercise
Who is the winner under the Borda Count?
Slide ‹#› out of 63
21
Spoiler effect
Suppose we have 2 candidates and and 5 voters.
3 voters prefer , the other 2 prefer , so would win.
A third candidate is introduced.
The 3 voters who preferred have the following preference
The 2 voters who preferredhave the following preference
Who wins using Borda count?
gets (3*2) = 6 points
gets (3*1)+(2*2) = 7 points
gets (2*1) = 2 points
This is the spoiler effect: an outcome can depend on the presence of alternatives that intuitively seem irrelevant. Spoilers shift the outcome from one highly ranked candidate to another.
Slide ‹#› out of 63
22
Positional scoring rules
More generally, under positional scoring rules, candidates are given scores according to their positions in preference orderings.
Scoring vector:
0 (not negative and the sequence never increases)
(the sequence must decrease somewhere)
Each candidate receives points for each voter that lists them as their first choice, points for each voter that lists them as their second choice, etc.
The candidate with most points is the winner
Slide ‹#› out of 63
23
Positional scoring rules violate Condorcet principle
A vs B: 6/5
A vs C: 6/5
The Condorcet winner is A.
Using positional scoring, the scores are:
We know that , so , or
We know that and that
So and , from which it follows that .
And so , or
so B is winner under positional scoring regardless of the scoring
Slide ‹#› out of 63
24
Anonymity
A voting rule is said to be anonymous if all voters are treated symmetrically.
No voter is more influential than any others.
Example
The following sets of voter preferences will lead to the same outcome when using an anonymous voting rule.
Slide ‹#› out of 63
25
Voting rule properties
A voting rule is said to be:
resolute if there is always a unique winner (no ties)
surjective if for every candidate there is some profile of voter preferences such that the candidate will win (every candidate has a chance of winning)
a dictatorship if there is some voter such that the winner is the first choice of (the dictator always picks the winner)
strategy-proof for a particular voter if there is no profile , … , such that prefers the outcome determined by , … , to the outcome determined by , … , , where is an untruthful ballot cast by ( does not have any incentive to misrepresent their true preferences)
strategy-proof if it is strategy-proof for all voters: no one has any incentive to misrepresent their preference
weakly Pareto if it does not elect some candidate whenever there is some other candidate such that all voters prefer to
Slide ‹#› out of 63
26
Gibbard-Satterthwaite Theorem
Any resolute voting rule for candidates that is surjective and strategy-proof is a dictatorship
While it might, in principle, be possible to manipulate a voting mechanism by falsely representing your preferences, working out how to falsely report your preferences can be computationally very complex.
Slide ‹#› out of 63
27
Independence of irrelevant alternatives
“ decides to order dessert. The waitress tells him he has two choices: apple pie and blueberry pie. Sidney orders the apple pie. After a few minutes the waitress returns and says that they also have cherry pie at which point Morgenbesser says ‘In that case I’ll have the blueberry pie.’”
The independence of irrelevant alternatives (IIA) principle says the following.
Consider two different profiles of voter preferences:
If the social preference given is that , and if and only if , then it ought to also be the case that the social preference given is that .
The social preferences between candidates and depend only on the individual preferences between and .
If the set of candidates contains only and and , then introducing a third option must not make .
As we saw earlier, Borda Count does not satisfy IIA
Slide ‹#› out of 63
28
Arrow’s impossibility theorem
When we have candidates, any voting rule that is surjective and independent of irrelevant alternatives is a dictatorship
Slide ‹#› out of 63
29
Domain restrictions and single-peaked preferences
Can we find a way to circumvent these negative results?
We have been making a universal domain assumption, i.e. that voters are allowed to list their candidates in any order, but this is often unrepresentative of reality: it is unlikely that every possible ordering will be chosen
If we restrict the domain (the preference orders the voters are able to select from) then these negative results don’t hold.
Slide ‹#› out of 63
30
Domain restrictions and single-peaked preferences
A domain has a single-peaked preference if there is a “left-to-right” ordering on the candidates such that implies and implies
This can be interpreted as: candidates that are more similar to your first choice are preferred.
It can be quite a natural assumption in some applications, e.g., left to right political spectrum, legal drinking age, speed limit.
Slide ‹#› out of 63
31
Median voter rule
In the median voter rule, candidates are given a fixed “left-to-right” order
Each person votes for a single candidate.
The winner is determined by the median voter’s ballot.
It’s assumed that voters will prefer similar candidates according to .
Slide ‹#› out of 63
32
Exercise
Suppose we have the following “left-to-right” ordering
Each person votes for their favourite candidate
Who wins under the median voting rule?
Slide ‹#› out of 63
33
Median voter rule properties
If an odd number of voters submit single-peaked ballots, then there is a Condorcet winner that is elected by the median voter rule.
The median voter rule is strategy-proof
The median-voter rule is weakly Pareto
Slide ‹#› out of 63
34
Summary
How to make group decisions: social choice theory
We looked at a range of different voting protocols
Saw that it is impossible to design voting protocols that in all cases have certain desirable properties
But it can be possible if we restrict the domain from which voters can select their preferences
Slide ‹#› out of 63
/docProps/thumbnail.jpeg
