Description
Question 1 (20 marks) Consider the following preference profile of voters.
1 : c d b a
2 : d c b a
3 : a d c b
1. Prove or disprove that the preference profile is single-peaked with respect to some
order of alternatives.
2. Prove or disprove that a Condorcet winner exists for the preference profile.
3. Compute the pairwise majority graph for the preference profile.
4. Compute the Top Cycle set for the preference profile.
Question 2 (20 marks) Consider a resource allocation setting in which n agents have
positive additive utilities over m > n indivisible items. Prove or disprove the following
statements.
• The allocation that maximizes utilitarian welfare is Pareto optimal.
• If an allocation is Pareto optimal, it is envy-free.
• If n = 2, envy-freeness and proportionality are equivalent.
• The sequential allocation algorithm, in which agents arrive in order (1,2,3,…,n)
∗
and are given a most preferred unallocated item, is strategyproof.
Question 3 (20 marks) Consider the following school choice problem with five students
1, 2, 3, 4, 5 and five schools a, b, c, d, and e with each school having exactly one seat. The
preferences of the students are as follows from left to right in decreasing order of preference.
1 : e,b,a, c,d
2 : b,a, c,d, e
3 : a,b, c,d, e
4 : a,b, c,d, e
5 : d,b, c,a, e
The priorities of the schools are as follows from left to right in decreasing order of
priority.
a : 2,4,3,5,1
b : 3,2,4,5,1
c : 3,2,4,5,1
d : 5,2,4,3,1
e : 1,2,3,4,5
1. Find the outcome matching of the student proposing deferred acceptance algorithm,
showing working out. Prove or disprove that the resultant matching is Pareto optimal
for the students.
2. Suppose that initially, student 1 is allocated to school a, student 2 is allocated to
school b, student 3 is allocated to school c, student 4 is allocated to school d, and
student 5 is allocated to school e. Apply the Top Trading Cycles (TTC) Algorithm
with respect to the students’ preferences here and find the output, showing working
out. Note that we ignore the schools’ priorities here.
3. Give three reasons, with examples if necessary, why the deferred acceptance algorithm is preferred for school choice over the TTC algorithm.
4. Give a reason, using an example if necessary, why TTC may be preferred for this
school choice setting over the deferred acceptance algorithm.
Question 4 (40 marks) Consider the standard social choice setting where a set of n voters
have strict preferences over a set of m alternatives.
1. We can define the rank/3 predicate, where rank(i,a,k) indicates voter i ranks
outcome a as its kth most preferred outcome in his/her vote. Write down the ASP
encoding for the preference profile in Question 1.
2. Write an ASP program condorcet.lp that takes in a preference profile as input,
and outputs the Condorcet winner in the predicate condorcetWinner/1. If there
is no Condorcet winner, there should be no instance of this predicate/the predicate
should be empty.
3. Write an ASP program condorcetborda.lp that takes in a preference profile
as input, and outputs the Condorcet winner if one exists, or the Borda winner if no
Condorcet winner exists. If no Condorcet winner exists and there are multiple alternatives with a tied winning Borda score, the program should output the alternative
that comes first in alphabetical order.
4. Consider the voting rule from the previous subquestion that selects the Condorcet
winner if one exists, or the Borda winner if no Condorcet winner exists, breaking ties
by alphabetical order. Write an ASP program cbmanipulation.lp that takes
in a preference profile as input, and returns a different preference ordering that a
voter can report to achieve a better outcome under the aforementioned voting rule.
The program should additionally return the misreporting voter’s original (truthful)
preference ordering. If no such misreport exists for any voter, the program should
return UNSATISFIABLE.