Question

Consider the TA assignment problem where n Teaching Assistants
(TAs) are to be assigned to n courses with one course having exactly
one TA. Each course ranks all of the TAs, and each TA ranks all the
courses, from most to least desirable.
Can you provide an example of an assignment and preference lists such
that every TA and course forms an unstable pair? (Yes/No). If Yes,
present the assignment. If No, justify your answer.
note: gale shapley algorithm

Answer 1

No there doesn't exist an unstable assignment. The gale shapley algorithm generate stable pairs. In this case Course are assigned to  TA.

Algorithm : 
    In algorithm below Course_Pref_list is given by each TA and TA_Rank_list is provided by each Course.

  

1. Set all courses_list and TA_list to be assigned null
2. Repeat step 3 and 4 until all TA is assigned course from courses_list
3. if TA T_p is not assigned any course.
4. Search course_Pref_list of TA T_p and  assign a course
   1. which is still assigned null.
   2. if no such course is null .Repeat
      1. Choose one C_q course in the TA T_p Course_pref_list in given order.
      2. In that course C_q find TA T_p. and see if T_p ranked higher than current assigned TA.
      3. Assign that course C_q to TA T_p.
5. At the end every TA is assigned a course by which both are satisfied according to  given preference than any other possible assignment.

Proof:

Every TA T_i  must have listed  the Course C_j  at some number(according to desirability)  and Similarly C_j must have ranked T_i at some number (ranking order).

The proof by contradiction.

Assume :   After the algorithm termination, T_i   and C_j are assigned to some other C_x and T_y. T_i and C_j both prefer each other more than their current allocation (Already provided with the problem).

If C_j ranks T_i higher-up than current assigned T_y , the assignment is only possible

1. if C_j was assigned T_i(by looking from T_i preference list ) and C_j (by looking from Course ranking TA list) was then assigned to T_y. This shows that T_y is more preferred than T_i. It tells us that T_i was not higher in the preference list than T_y.
2. T_i was assigned C_j(by looking from Course ranking TA list) and T_i (by looking from Ti preference list) was then assigned to C_x. This shows that C_x is more preferred than C_j. It tells us that C_j was not higher in the preference list than C_x.

In  both the above cases it is shows either Ti or Cj have conflict with their preference. Which contradicts our assumption that Ti and Cj are both preferred then current assignment.