Describe how Plurality rule works.
15/06/2021
Voting rules:
- Plurality:
- Voting: each voter provides the most preferred decision
- Selection: the decision preferred by the largest number of voters
- Majority: like plurality, over 2 options
- Approval: (m options)
- Voting: each voter approves any number of options
- Selection: option with most votes
- Borda:
- Voting: each voter provides a rank over all options
- Score of an option: number of options that it dominates.
- Selection: option with greatest sum of the scores
Describe how Borda rule works. Is it possible to manipulate it?
Voting rules:
- Plurality:
- Voting: each voter provides the most preferred decision
- Selection: the decision preferred by the largest number of voters
- Majority: like plurality, over 2 options
- Approval: (m options)
- Voting: each voter approves any number of options
- Selection: option with most votes
- Borda:
- Voting: each voter provides a rank over all options
- Score of an option: number of options that it dominates.
- Selection: option with greatest sum of the scores
Desirable properties of voting rules:
- Unanimity (efficiency): If all voters have the same top choice, it is selected.
- Non-dictatorship: There is no dictator (Dictator: voter such that his top choice always wins, regardless of the votes of other voters)
- Non-manipulability: There is no incentive for agents to misrepresent the preferences.
Impossibility results:
- Arrow’s theorem: Totally ordered preferences. It is impossible to find a voting rule with some desirable properties including both unanimity and non-dictatoriality
- Gibbard-Sattherwaite’s theorem: Totally ordered preferences. it is impossible to have a reasonable voting rule that is both non-dictatorial and non-manipulable.
These impossibility results holds also when we allow partially ordered preferences.
Quale tipo di preferenze possono modellare i vincoli soft? Quale tipo di preferenze possono modellare le CP-net?
Kind of preferences:
- Unconditional: I prefer taking the bus
- Conditional: I prefer taking the bus if it’s raining
- Multi-agent: I like blue, my husband likes green, what color for the new car?
- Quantitative: Numbers or ordered set of objects. My preference for ice cream is 0.8, and for cake is 0.6
- Qualitative: Pairwise comparisons, Ice cream is better than cake
Ways to model preferences:
- Soft constraints: for modeling quantitative and unconditional preferences. (Ex., My preference for ice cream is 0.8, and for cake is 0.6)
- CP-nets: for modeling qualitative and conditional preferences. (Ex., Red wine is better than white wine if there is meat)
What are the main differences between soft constraint formalism and CP-nets?
Ways to model preferences:
- Soft constraints: for modeling quantitative and unconditional preferences. (Ex., My preference for ice cream is 0.8, and for cake is 0.6)
- CP-nets: for modeling qualitative and conditional preferences. (Ex., Red wine is better than white wine if there is meat)
Soft constraint formalism (the c-semiring framework)
- The agent expresses his preferences over partial assignments of the decision variables.
- From these preferences the preference ordering over the solution space is generated
Soft constraints model quantitative and unconditional preferences but it is difficult to elicitate quantitative preferences from the user.
CP-net formalism: compactly represent qualitative and conditional preferences.
- Variables {X1,…,Xn} with domains
What is a conditional preference table in a CP-net?
15/06/2021
Dependent variable: a total order for each combination of values of some other variables (conditional preference table, aka CP-table)
Descrivere l’algoritmo per trovare una soluzione ottima in una CP-net aciclica.
Finding an optimal solution in acyclic CP-nets: forward sweep algorithm.
- First consider independent variables: Assign them their most preferred values.
- Then consider dependent variables, that directly depend on the assigned variables: Assign them their most preferred values that are consistent with the values previously assigned to their parents.
- And so on until we assign a value to all the variables.
