COMP326 Assignment 2 (15% of the final mark)
Due 18th April 2023
Please submit your solutions electronically (in PDF format) on Canvas
Please be aware of the University guidelines on plagiarism and collusion. The marks for late
submissions will be affected in accordance with the University’s Code of Practice on Assessment.
Total: 100 marks
1. (25 marks): Let us assume we have a greedy landlord with a house to rent near the
university. The house has r rooms available (rooms are different, some are big, some
have large windows...). The landlord needs the total rent to be at least C (to pay back
the morgage). He would like for the total rent to be higher. Due to its location, many
students are interested in renting a room in the house. The total number of student is n.
Most students agree that C is an acceptable minimum rent for the whole house. (Some
students may even consider that the total rent should be higher). Students are busy with
their coursework and social life. They do not want to waste time negotiating amongst
themselves who will get which room for which rent and which students will not be able
to get a room at all. In contrast the landlord is happy to deal with as many possible
tenants as he can. As such the landlord would like to make a simple app that would allow
students to bid on rooms. 1 week before the start of the semester starts bidding will end
and the rooms allocation and rent will be fixed for each student. They can move in.
The app should respect the following:
A student can bid on more than one room and are encouraged to bid on all rooms.
A student should be able to bid different values for different rooms.
The app should assume no students benefits from being allocated more than one
room even if they gave high bids to all the rooms.
A student can add, change or remove their bid at any time until the beginning of the
semester.
A student should never lose anything from changing their bid to their valuation of
the room.(they may however not gain anything either).
A student should not have to pay more rent than what they suggested in their bid.
A student should be able to see whether the room is currently allocated to them.
A student should be able to see the rent currently allocated to the room.
The total rent should be at least C if enough students that bid agree that C is an
acceptable minimum rent for the whole house.
The landlord should be getting the maximum possible rent assuming all the previous
is true.
We will use the following notations. The set of students is N and the set of rooms is R.
There are n students and r rooms (with n > r). The valuation of a student i for room J is
vi(J). We denote vi = (v1(1), . . . , vr(r)) tulpe containing the valuation that i has for each
room and v = (v1, . . . , vn) the valuation profile containing the valuations of each student.
Similarly, the bid of a student for a room J is bi(J) and we define bi and b. (b′i, b?i)
represents a bidding profile where student i changed his bid to b′i. You can consider that
the app only accepts non-negative bids. (?i, J : bi(J) ≥ 0) and that valuations are also
non-negative.
(a) Describe the set of possible allocations of the rooms? We denote this set X . (Hints:
you can use a mapping, vectors or matrices to describe an allocation, there should
be a total of rn possible allocations or r(n+1) if you assume it is possible for a room
not to be allocated.) (2 pt)
(b) What is the valuation each student gives to each allocation? (Hint: Students only
need one bed to sleep in.) (2pt)
(c) Given the previous, why can we assume that the app will not assign 2 rooms to a
single student? (Hint: There are more students than rooms.) (3pt)
(d) Give a pseudo-code for the room allocation and rent allocation algorithm of the app.
(Hint: You may wish to comment the pseudo-code. You do not need to give the rest
of the algorithm to build the app.) (5pts)
(e) What do we mean by ”if enough students that bid agree that C is an acceptable
minimum rent for the whole house.”? (Hint your answer should contain
∑
J∈R vi(J).)
(3pts)
(f) Show that the condition given in 1e implies that the social welfare maximum is at
least C. (Hint : Use induction to find an allocation were social welfare is at least
C. At each step consider for all students i that have not yet been allocated a room
the sum si = vi(I) +
∑
J∈S vi(J) were S is the set of rooms that have already been
allocated and I is the room that is being allocated. You then allocate I to the student
with the largest si.)(5pts)
(g) Show that the condition given in 1e results in the minimum total rent being C when
the students bid their valuations. (Hint: You may wish to consider a student k that
agrees that C is an acceptable rent but did not get a room. When considering how
much pi is worth consider what would happen if k got the room that was initially
intended for i.)(5pts)
2
2. (25 marks) Let us assume that 1000￡ has been allocated to creating and taking care of
2 new bee hives in Liverpool. A group of n bee lovers are asked to say how much they
believe should be allocated to each hive. These are true bee lovers and they do not want
money to go to waste. Any amount that is not allocated to the bee hive A, they wish to
be allocated to the bee hive B. Each bee lover will therefore have a value ai such that
they believe that ai should be allocated to A and 1000 ? ai should be allocated to B.
There bid is therefore a tuple (ai, 1000? ai). Assuming that the final allocation is (x, y)
then the utility of bee lover i is ui(x, y) = 1000?max(0, ai ? x)?max(0, 1000? ai ? y).
In other words the bee lover is completly satisfied with the allocation given to A (resp. B)
so long as it is more than ai (resp. more than 1000? ai), if not the further away we are
from the ideal allocation the worse the outcome is from bee lover i’s perspective. We are
interested in creating an anonymous, Pareto-optimal, incentive compatible mechanisms
to decide on the allocation of the budget to protect these bees.
Let f(L) be the social choice function that takes the utility functions of the bee lovers
and returns the budget allocation. Suppose that f is anonymous, Pareto-optimal and
incentive compatible.
(a) Why can we assume that a1 ≤ a2 ≤ ... ≤ an? (2pts)
(b) Why can we be certain the outcome f(L) = (x, y) verifies y = 1000? x. (3pts)
(c) Reduce our problem to the facility location problem. Deduce the set of all Pareto
Optimal, incentive compatible and anonymous social choice functions that can be
used to allocate the budget for the bee hives. (5pts)
(d) Find the incentive compatible, mechanism that maximizes social welfare. (Hint you
should distinguish the case where n is even from the one where n is odd). (5pts)
(e) How much is allocated to each bee hive if a1 =50￡, a2 =150￡, a3 =300￡ ,a4 =450￡
and a5=500￡.What about is we add a bee lover such that a6=1000￡? (3pts)
(f) The bee lovers are very enthusiastic with this project. They decide that to make up
for their disagreements a VCG mechanism should be implemented so that those that
got the most from the budget allocation should contribute the most to the next bee
hives built in Liverpool. Using the previous example with 5 bee lovers, how much
should they each pay? Does the use of a VCG mechanism seem fair to you in this
situation? (4pts)
(g) We say that a bee lover is single-minded if he wants all the budget to go to one of
the two bee hives. f is proportional if when all the bee lovers are single-minded then
the budget of a bee hive is allocated proportionally to the number of bee lovers that
favor the bee hive. Provide a proportional, incentive compatible, Pareto-Optimal,
anonymous mechanism to allocate the budget. Justify your answer. (3 pts) (Hint:
You need to find the yk values.)
3
3. (25 marks)
We have n sport team coaches (t1, . . . tn) that must decide on their players amongst the
m players (p1 . . . pm). Each team will have r players (we assume that nr ≤ m. Each team
leader has ranked his options and each player ranked the team leaders.
Which of the famous algorithms we have seen should you use as a model? (5pts)
Give the pseudo-code for an algorithm that provides stable teams. If there is more
then one possible stable team then the chosen stable teams should be the optimal
from the perspective of the team leaders. (10pts)
Run your algorithm on the following instance with 3 teams coaches and 10 players.
The teams size should be 3. (10 pts)
4. (25 marks) Suppose that your grandmother has kidney failure. You offer to give her
your kidney but the doctors say that your kidney isn’t a good match. They suggest you
enter the UK Living Kidney Sharing Scheme1 as a donor/patient pair. You will be giving
your kidney to a stranger who you are a match for if someone that is a better match then
you offer’s their kidney to your grandmother.
(a) Assuming that all donors are part of the UK Living Kidney Sharing Scheme, modelize
the problem of kidney exchange. (Hint the preferences over the kidneys should be
considered strict.) (3 pts)
(b) What algorithm you were taught in the module can be (and is) used to get the best
kidneys for everyone. (2pts)
(c) The UK allows generous anonymous donors that do not have a relative in need to
join the program as well. How can you adapt the algorithm accordingly in order
to remain stable and incentive compatible? Provide a pseudo-code (Hint: Consider
that the patients are ordered according to how urgent there situation is.)(10pts)
(d) Justify why the changes you made to the algorithm you knew ensures that the out-
come remains stable. The definition of stable here is : Let a be the outcome of your
algorithm. There is no allocation z such that there exists a donor/patient i with
zi >i ai and all other donor/patients j have zj ≥j aj . (Hint you do not need to
reprove that the initial algorithm provides a stable outcome) (3pts)
(e) Justify why the changes you made to the algorithm you knew ensures that the out-
come remains incentive compatible. (Hint you do not need to reprove that the initial
algorithm is incentive compatible) (3pts)
(f) Run your algorithm on the following example where players 1 to 4 are part of a
donor/patient pair and 5 is a generous donor. (4pts)
References
[1] D. Gale and L. S. Shapley. College admissions and the stability of marriage. The American
Mathematical Monthly, 69(1):9–15, 1962.
[2] N. Nisan, T. Roughgarden, E. Tardos, and V.V. Vazirani. Algorithmic Game Theory. Cam-
bridge University Press, 2007.
[3] B. Lehmann, D. J. Lehmann and N. Nisan. Combinatorial auctions with decreasing marginal
utilities. Games and Economic Behavior 55(2): 270-296 (2006).