Assignment problem and kidney exchange

Question 1

How can an assignment be considered efficient

Answer 1

Each individual prefer what he has or is indifferent to it

there is at least one individuals who prefers a to b

Question 2

What are the steps to finding efficient assignments

Answer 2

Step 0: pick an order of the individuals ( not necessarily random)

Step 1: The first individual in the order is assigned her most preferred object

Step 2: The individual ranked k-th in the order is assigned her most preferred object among all objects except the ones taken by the first k − 1 individuals in the order.

End: Stops when all individuals has selected an object or when there’s no object left

Question 3

What is the top trading cycle algorithm

Answer 3

General principle of it is to draw a graph where individuals point to the object they want

Step 1: Each individual points to the individual owning the object she prefers the most (could be herself)

Remove from the problem all the agents (and their objects) who were part of a cycle

Step 2: Do like in step 1 and then remove

End: algorithm stops when all individuals have been removed or there are no acceptable objects left for any individual

Question 4

When is a kidney exchange mechanism efficient and strategy proof (have incentive to report truthfully)

Answer 4

When they are abiding by the rules a,d,e,f

Question 5

Name the different selection rules in TTC

Answer 5

A: Choose the smallest chains and remove from the problem the patients and kidneys in those chains once the assignment is determined.

D:Choose the chain that starts with the highest priority patient and remove from the problem the patients and kidneys in that chain

E: Choose the chain that starts with the highest priority patient and keep in the problem the patients and kidneys in that chain.

F: Prioritize patient-donor pairs so that pairs with a type O donor have a higher priority (than the pairs whose donor is not of type O). Then choose the chain that starts with the highest priority pair.
If the starting pair in the chain has a type O donor then
remove from the problem the patients and kidneys in that chain. Otherwise keep in the problem all the patients and donors that are in the chain.