Allocation (Part 1) Flashcards
What is the serial dictatorship mechamism?
1) A priority ordering is made of players
2) Each agent picks their top choice (of the remaining houses) one by one, based on the priority ordering (one by one dictatorship
What is Gale’s top trading cycles algorithm?
1) Each agent points towards their top choice
2) Each house points towards their owner
3) Remove all cycles from the problem by assigning each agent the house they are pointing to
4) Redirect arrows that point to removed houses based on the agents second choices
5) Continue until no agents and houses remain
What is the YRMH-IGYT algorithm?
1) Assign a priority ranking to newcomers and add the existing players to the back
2) Let all houses point towards existing owners
3) The first agent points towards their top choice. Assign this if empty and remove agent/house. and move on to next one
4) When an agent points towards a house that is already occupied, move the existing tenant to the front of the line and let them point.
What is the TTCC algorithm with the chain selection rule?
1) Write up all kidney/patient pairs, and let kidneys point to its paired patient
2) Each remaining active patient points towards the best remaining unassigned kidney or to waiting list w
3) There is a cycle or w-chain or both, remove those
4) Proceed the steps
What is the deffered acceptance (DA) algorithm? (school-proposing)
1) Everyone lines up their preferences (both students and schools)
2) The schools send out their first invites to their preferred students
3) Students accept, hold or reject the invitation based on their preferences
4) Repeat until all are matched
What is the deffered acceptance (DA) algorithm? (student-proposing)
1) Everyone lines up their preferences (both students and colleges)
2) The students send out their first applications to their preferred colleges
3) Schools accept, hold or reject the invitation based on their preferences
4) Repeat until all are matched
What is the multi-category serial dictatorship?
1) JOKER
What is the boston school choice mechanism?
1) A priority order is made for students
2) Each student submits a preference ranking of the schools
3) In step 1, only top choices of the students are considered. For each school, students who have listed it as their top choice are placed based on priority order
4) The remaining students are assigned to second, third choices etc.
What are the weaknesses of the boston school choice mechanism?
1) It is not strategy proof. Even if a student has a very high priority at the school, unless they have it as their top ranked, they are likely not selected due to the slots being filled by students who have it as their stop choice
2) Also doesn’t eliminate justified envy
What is the school choice TTC Mechanism?
1) Each school lists their preferences for students, and each student lists their preferences for schools
2) Each student points towards their most preferred school available
3) Each school points towards the student at the top of their remaining list
4) Cycles are identified; students and school slots are eliminated
5) Process repeats until all students are assigned or no cycles are found
What are the properties of the school choice TTC mechanism?
1) Efficiency and Pareto Optimality: The TTC mechanism ensures that the allocation is efficient in the sense that no other allocation would make some students better off without making others worse off.
2) Envy-Freeness: Each student gets their top choice among the available schools considering the preferences of others, hence no student envies another’s assignment.
3) Strategy-Proof: Students are incentivized to list their true preferences as misrepresenting preferences does not provide a benefit.
