Question $7$

$6/24$ pts

Consider the following preference tables for three university hospitals and three medical students.

$\backslash$table$[[,1$st$,2$nd$,3$rd$],[$DUKE$,$Cam,Ada,Bea$],[$NYU$,$Ada,Cam,Bea$],[$UIUC$,$Cam,Bea,Ada$]]$

$\backslash$table$[[,1$st$,2$nd$,3$rd$],[$Ada$,$DUKE,UIUC,NYU$],[$Bea$,$UIUC,DUKE,NYU$],[$Cam$,$UIUC,NYU,DUKE$]]$

$($i$)$ Which of the following is the output of the Gale$-$Shapley algorithm?

DUKE$-$Ada, NYU$-$Bea, UIUC$-$Cam

$($ii$)$ Which of the following is a stable matching that assigns each student to their best valid partner?

$($iii$)$ Which of the following is an unstable pair with respect to the matching $($DUKE$-$Ada, NYU$-$Cam, UIUC$-$Bea$)?$

DUKE$-$Cam

$($iv$)$ Which student $($if any$)$ can improve his$/$her$/$their match in the Gale$-$Shapley output by lying?