Expository Articles about Elections, Voting and Two-Side Markets
Department of Mathematics and Computer Studies
York College (CUNY)
Jamaica, New York
I have written several expository articles for the American Mathematical Society Feature Column that deal with voting, elections and two-side market issues. These columns are shown below with direct links.
1. A survey of modeling aspects of elections including descriptions of some of the appealing election methods discovered and rediscovered many times.
2. A survey of election methods, including data about a controversial presidential election, where the candidate who became President did not win the popular vote.
3. The Gale-Shapley deferred acceptance algorithm for pairing n men and n women is described. An earlier way of using graph theory to pair men and women or workers and jobs, known as the Philip Hall Marriage Theorem is also discussed. This result involves the ideas of systems of distinct representatives and finding matchings (disjoint collections of edges) in graphs.
4. Gale-Shapley ideas have proved very useful in getting insight into designing school choice programs. The idea is to improve schools by having them compete with each other for students rather than forcing parents to use a particular school. Alvin Roth and his doctoral students have pioneered the use of adaptive systems which take into account local issues but incorporating ideas from mechanism design which try to get parents to provide honest private information so that the system will have both good behavior for individual parents and the society as a whole.
The most important sources of information about Gale-Shapley models are the following books though there are huge numbers of papers on this topic, and new insights are being generated regularly.
Gusfield, D., and R. Irving, The Stable Marriage Problem, MIT Press, Cambridge, 1989.
Knuth, D., Mariages Stables, Les Presses de lUniversité de Montreal, Montréal, 1976.
Knuth, D. Stable Marriage and Its Relation to other Combinatorial Problems, American Mathematical Society, Providence, 1997.
Roth, A., and M. Sotomayor, Two-Sided Matching, Cambridge U. Press, New York, 1990.
A larger bibliography is available here:
Gale-Shapley models are one of my favorite examples of the interplay of beautiful theoretical mathematics and applications.