Samenvatting Multi-Agent Systems
Social Computational Choice
Collective decision making: a situation that arises when a group needs to make a decision. The
views of the individual members of that group should be aggregated into a single collective view that
adequately reflects the ‘will of the people’.
• Forms of collective decision making:
o Voting
o Matching
o Fair division
o Judgement aggregation:
▪ Judges have to reach a verdict based on their opinions. Make a group decision
about several different but related issues
Voting
How to choose the ‘appropriate’ voting rule?
• Which kind of preferences are the agents allowed to have?
o Do they prefer something over something else, or are the choices equally good?
o Do they need to be compared to all other alternatives (like Borda)?
• What do we do in case of ties?
• Do we want a set of ‘winners’(social choice function) or a full ‘collective’ preference (social
welfare function)?
• Do we have computational complexity constraints?
• Do we want some ‘consistency’?
• Which aggregation requirements (properties) should the rule satisfy? (important)
o Anonymity: the names of the voters do not matter (i.e. if two voters exchange
preferences, the outcome is unaffected)
o Neutrality: the names of the options do not matter (i.e. if two options are exchanged
in ranking, the outcome changes accordingly)
o Participation, monotonicity, strategyproofness, Condorcet principle, Pareto principle
▪ Explained in the section with all voting rules
o Reinforcement: if an alternative wins in two disjoint subgroups, then it should also win
when the groups are put together
Basic setting
,Voting rules
• Majority
o + Works perfectly when |X| = 2 and n is odd
o – For |X| > 2 it might not exist
o – When used pairwise to get a social welfare function, it might result in cycles
• Plurality
o + Works well with 2 candidates
o – Only considers the favorite candidates, allowing very disliked winners:
▪ A > B > C (x20)
▪ B > C > A (x19)
▪ C > B > A (x19)
• A is the best for 20, but the worst for 38
• Single transferable vote (STV)
o If an alternative is selected by majority, it wins
o Otherwise, eliminate the ‘plurality loser’ from the preferences and repeat the
procedure
o + The full preference ordering is used
▪ Various options for how to deal with ties during elimination
▪ Variations
• Plurality with run-off: eliminate all but a designated number of
candidates
• Coombs, Baldwin, Nanson (different elimination criteria)
o – In some cases, it is better to abstain than to vote
▪ Not voting for a preference B > C gives a better result than voting does for B
▪ This violates participation: voting truthfully should not be worse than
abstaining
o – If the winner gets further support, she might lose
▪ This violates monotonicity: if the selected get additional support, they are still
selected
• Borda
o Each agent submits her full ordering; her best choice gets m-1 points, her second-best
choice gets m-2, and her worst choice gets 0 points
o Points are added. Winner: alternative with most points
o + The full preference ordering is used
▪ Different formulas for assigning points might be used
o – It is sensitive to discarding non-winning options
, ▪ C is not winning, but if it is removed, the winner changes
o – It is very sensitive to adding Borda-worst options
o – It is susceptible to manipulation
▪ Switching the preference of A and C for 3 people that actually prefer B the
most causes B to win after this manipulation
▪ This violates strategyproofness: no voter has ever an incentive to submit false
preferences
o – An alternative other than the winner might beat every other in pairwise majority
▪ This violates the Condorcet principle: an alternative that wins pairwise
majority against all other candidates (Condorcet winner) should be the only
winner when it exists
• Copeland
o Do pairwise majority contests. Each alternative gets +1 for a win and -1 for a loss
o Winner: alternative with the most points
o + Satisfies the Condorcet principle
o – Very likely to produce ties
o – Too much emphasis on quantity of victories and defeats, forgetting about their
magnitudes
▪ A would win with Copeland’s rule, but when you look at with how much A
wins and how much B wins, B has a much greater victory
• Positional scoring rules
o
Social Computational Choice
Collective decision making: a situation that arises when a group needs to make a decision. The
views of the individual members of that group should be aggregated into a single collective view that
adequately reflects the ‘will of the people’.
• Forms of collective decision making:
o Voting
o Matching
o Fair division
o Judgement aggregation:
▪ Judges have to reach a verdict based on their opinions. Make a group decision
about several different but related issues
Voting
How to choose the ‘appropriate’ voting rule?
• Which kind of preferences are the agents allowed to have?
o Do they prefer something over something else, or are the choices equally good?
o Do they need to be compared to all other alternatives (like Borda)?
• What do we do in case of ties?
• Do we want a set of ‘winners’(social choice function) or a full ‘collective’ preference (social
welfare function)?
• Do we have computational complexity constraints?
• Do we want some ‘consistency’?
• Which aggregation requirements (properties) should the rule satisfy? (important)
o Anonymity: the names of the voters do not matter (i.e. if two voters exchange
preferences, the outcome is unaffected)
o Neutrality: the names of the options do not matter (i.e. if two options are exchanged
in ranking, the outcome changes accordingly)
o Participation, monotonicity, strategyproofness, Condorcet principle, Pareto principle
▪ Explained in the section with all voting rules
o Reinforcement: if an alternative wins in two disjoint subgroups, then it should also win
when the groups are put together
Basic setting
,Voting rules
• Majority
o + Works perfectly when |X| = 2 and n is odd
o – For |X| > 2 it might not exist
o – When used pairwise to get a social welfare function, it might result in cycles
• Plurality
o + Works well with 2 candidates
o – Only considers the favorite candidates, allowing very disliked winners:
▪ A > B > C (x20)
▪ B > C > A (x19)
▪ C > B > A (x19)
• A is the best for 20, but the worst for 38
• Single transferable vote (STV)
o If an alternative is selected by majority, it wins
o Otherwise, eliminate the ‘plurality loser’ from the preferences and repeat the
procedure
o + The full preference ordering is used
▪ Various options for how to deal with ties during elimination
▪ Variations
• Plurality with run-off: eliminate all but a designated number of
candidates
• Coombs, Baldwin, Nanson (different elimination criteria)
o – In some cases, it is better to abstain than to vote
▪ Not voting for a preference B > C gives a better result than voting does for B
▪ This violates participation: voting truthfully should not be worse than
abstaining
o – If the winner gets further support, she might lose
▪ This violates monotonicity: if the selected get additional support, they are still
selected
• Borda
o Each agent submits her full ordering; her best choice gets m-1 points, her second-best
choice gets m-2, and her worst choice gets 0 points
o Points are added. Winner: alternative with most points
o + The full preference ordering is used
▪ Different formulas for assigning points might be used
o – It is sensitive to discarding non-winning options
, ▪ C is not winning, but if it is removed, the winner changes
o – It is very sensitive to adding Borda-worst options
o – It is susceptible to manipulation
▪ Switching the preference of A and C for 3 people that actually prefer B the
most causes B to win after this manipulation
▪ This violates strategyproofness: no voter has ever an incentive to submit false
preferences
o – An alternative other than the winner might beat every other in pairwise majority
▪ This violates the Condorcet principle: an alternative that wins pairwise
majority against all other candidates (Condorcet winner) should be the only
winner when it exists
• Copeland
o Do pairwise majority contests. Each alternative gets +1 for a win and -1 for a loss
o Winner: alternative with the most points
o + Satisfies the Condorcet principle
o – Very likely to produce ties
o – Too much emphasis on quantity of victories and defeats, forgetting about their
magnitudes
▪ A would win with Copeland’s rule, but when you look at with how much A
wins and how much B wins, B has a much greater victory
• Positional scoring rules
o
