Matching

Question 1

Deferred Acceptance Algorithm (School & Student)

Answer 1

1) Each school/student proposed to its qs top choices
2) Each Student/school reject any not individual rational proposals and holds the most preferred one
3) Any school/student that was rejected proposes to new remaining tops
4) Algorithm stops after no rejection was made

Question 2

Central Solution Concept for Matching

Answer 2

Stability
–> iff a matching is individually rational

–> iff there is no blocking agent (that would rather not be matched with his mate)

AND

–> iff there is no blocking pair (a school - student pair that would to be preferred to be matched with each other rather)

Stable matching can always be found through deferred acceptance mechanism

Question 3

Theorems about school matching

Answer 3

• There is no stablea nds trategy-proof college admissions mechanism.
• It is a weakly dominant strategy forstudents to tell the truth under thestudent-optimal stable mechanism

There existsno stablemechanism that makes it a dominant strategyfor each school to state its preferences over the students truthfully..

hestudent-andschool-proposing DA algorithmeachconverge to astablematching in afinite number of steps.