The American Mathematical Society has a column by David Austin on The Stable Marriage Problem and School Choice
He writes:
"This column will present the game-theoretic results contained in the original Gale-Shapley paper along with Roth's subsequent analysis. Pathak calls the deferred acceptance algorithm "one of the great ideas in economics," and Roth and Shapley were awarded the 2012 Nobel Prize in economics for this work...
He gives a straightforward mathematical treatment of some of the main theoretical results, in context:
"Using ideas described in this column, economists Atila Abdulkadiroglu, Parag Pathak, and Alvin Roth designed a clearinghouse for matching students with high schools, which was first implemented in 2004. This new computerized algorithm places all but about 3000 students each year and results in more students receiving offers from their first-choice schools. As a result, students now submit lists that reflect their true preferences, which provides school officials with public input into the determination of which schools to close or reform. For their part, schools have found that there is no longer an advantage to underrepresenting their capacity.
The key to this new algorithm is the notion of stability, first introduced in a 1962 paper by Gale and Shapley. We say that a matching of students to schools is stable if there is not a student and a school who would prefer to be matched with each other more than their current matches. Gale and Shapley introduced an algorithm, sometimes called deferred acceptance, which is guaranteed to produced a stable matching. Later, Roth showed that when the deferred acceptance algorithm is applied, a student can not gain admittance into a more preferred school by strategically misrepresenting his or her preferences."
- See more at: http://www.ams.org/samplings/feature-column/fc-2015-03#sthash.LoiUEphE.dpuf
He writes:
"This column will present the game-theoretic results contained in the original Gale-Shapley paper along with Roth's subsequent analysis. Pathak calls the deferred acceptance algorithm "one of the great ideas in economics," and Roth and Shapley were awarded the 2012 Nobel Prize in economics for this work...
He gives a straightforward mathematical treatment of some of the main theoretical results, in context:
"Using ideas described in this column, economists Atila Abdulkadiroglu, Parag Pathak, and Alvin Roth designed a clearinghouse for matching students with high schools, which was first implemented in 2004. This new computerized algorithm places all but about 3000 students each year and results in more students receiving offers from their first-choice schools. As a result, students now submit lists that reflect their true preferences, which provides school officials with public input into the determination of which schools to close or reform. For their part, schools have found that there is no longer an advantage to underrepresenting their capacity.
The key to this new algorithm is the notion of stability, first introduced in a 1962 paper by Gale and Shapley. We say that a matching of students to schools is stable if there is not a student and a school who would prefer to be matched with each other more than their current matches. Gale and Shapley introduced an algorithm, sometimes called deferred acceptance, which is guaranteed to produced a stable matching. Later, Roth showed that when the deferred acceptance algorithm is applied, a student can not gain admittance into a more preferred school by strategically misrepresenting his or her preferences."
- See more at: http://www.ams.org/samplings/feature-column/fc-2015-03#sthash.LoiUEphE.dpuf
Posts
No comments:
Post a Comment