代写COMP326、代写Java，c++编程

日期：2023-04-09 11:09

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).