Samenvatting
Samenvatting Foundations of Multi-Agent Systems
Dit is een samenvatting van het tentamen van het vak Foundations of Multi-Agent Systems van de Universiteit van Amsterdam. De samenvatting is op volgorde van de colleges.
[Meer zien]Voorbeeld 3 van de 26 pagina's
Voorbeeld 3 van de 26 pagina's
In winkelwagengesponsord bericht van onze partner
Voorbeeld van de inhoud
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
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper kimgouweleeuw. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €4,99. Je zit daarna nergens aan vast.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 75632 samenvattingen verkocht
Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen