Summary
Samenvatting Foundations of Multi-Agent Systems
- Course
- Institution
This is a summary of the exam of the course Foundations of Multi-Agent Systems of the University of Amsterdam. The summary is in order of the lectures.
[Show more]
Seller
Follow
kimgouweleeuw
Reviews received
Content preview
Samenvatting Multi-Agent SystemsSocial 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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller kimgouweleeuw. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $5.42. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
75632 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now