Question

Consider the following school choice problem: there are four students (George, John, Thomas, and Quincy) and three schools (Washington, Adams, and Madison). Each school has a capacity of one student. The students' preference lists are as follows:

George: Washington, Adams, George, Madison

John: Madison, Adams, Washington, John

Thomas: Adams, Madison, Thomas, Washington

Quincy: Washington, Adams, Madison, Quincy

The schools' priority rankings are as follows:

Washington: John, Quincy, Thomas, George

Adams: John, George, Thomas, Quincy

Madison: George, Thomas, John, Quincy

What is the outcome of the Top Trading Cycles algorithm?

A.) Washington:Quincy, Adams:John, Madison:Thomas, George:George

B.) Washington:George, Adams:John, Madison:Thomas, Quincy:Quincy

C.) Washington:Quincy, Adams:Thomas, Madison:John, George:George

D.) Washington:John, Adams:George, Madison:Quincy, Thomas:Thomas

E.) Washington:George, Adams:Thomas, Madison:John, Quincy:Quincy

Answer 1

The Top Trading cycle algorithm is as follows:

1. Each students points to their most preferred school.
2. Each school tentatively offers a seat to its most preferred student.
3. A cycle is identified and each student is given the school it has pointed to.
4. The matched school and student are removed after allocation.
5. The cycle is repeated for the remaining schools and students.

Below is the graph with students are depicted on the left side and the schools are on the right. Each group points to the first preference. The red line shows the first preference by the student and the blue shows the first preference by a school.

A cycle has formed between George, Washington, John and Madison. This is depicted below:

Hence George will be allocated Washington and John will be allocated Adams. The pair is: (Washington: George), (Adams: John). These are then removed from the Graph. The remaining graph is as follows with the remaining agents points to their next best preference:

Another cycle is formed between Thomas and Madison. Hence Thomas will be allocated Madison. Therefore another pair is (Madison;Thomas). The remaining candidate Quincy will have himself. Thus (Quincy: Quincy).

Thus the answer is: B:  Washington:George, Adams:John, Madison:Thomas, Quincy:Quincy