Machiavelli and the Gale-Shapley Algorithm

1981/08/01 by L. E. Dubins, Lester E. Dubins, D. A. Freedman +1 · 581 citations
Decision Sciences · Economics, Econometrics and Finance · Mathematics · #Algorithm #Artificial intelligence #Auction Theory and Applications #Computer science #Game Theory and Applications #Game Theory and Voting Systems #Lying #Mathematical economics #Mathematics #Mathematics education #Object (grammar) #Operations research #State (computer science)

paper · doi:10.1080/00029890.1981.11995301

published in American Mathematical Monthly 88(7), 485-494 (Taylor & Francis)

openalex publication_date 1981/08/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30

Abstract

SummaryGale and Shapley have an algorithm for assigning students to universities which gives each student the best university available in a stable system of assignments. The object here is to prove that students cannot improve their fate by lying about their preferences. Indeed, no coalition of students can simultaneously improve the lot of all its members if those outside the coalition state their true preferences.

Cited by

• School Admissions Reform in Chicago and England: Comparing Mechanisms by their Vulnerability to Manipulation
• Manipulability in school choice
• Market Design, Human Behavior, and Management
• Of Stable Marriages and Graphs, and Strategy and Polytopes
• Coalitional Permutation Manipulations in the Gale-Shapley Algorithm
• Manipulation of Stable Matchings using Minimal Blacklists
• WMDecompose: A Framework for Leveraging the Interpretable Properties of\n Word Mover's Distance in Sociocultural Analysis
• On the existence of a strictly strong Nash equilibrium under the student-optimal deferred acceptance algorithm
• Partial Network Alignment with Anchor Meta Path and Truncated Generic Stable Matching
• Two-Sided Fairness in Many-to-One Matching
• Eyes on the Prize: Improved Biological Surface Registration via Forward Propagation
• Matching for the Israeli "Mechinot" Gap-Year Programs: Handling Rich Diversity Requirements
• Constrained School Choice with Incomplete Information
• On the Susceptibility of the Deferred Acceptance Algorithm
• Approximate optimality with bounded regret in dynamic matching models
• Manipulation and gender neutrality in stable marriage procedures
• Rawlsian equity: a new notion of fairness for the assignment problem
• Choix d'écoles en France
• Reciprocating Preferences Stablize Matching: College Admissions Revisited
• Joint User Association and Beamforming Design for ISAC Networks with Large Language Models
• Truncation Strategies in Matching Markets
• Two-Sided Manipulation Games in Stable Matching Markets
• Strategy-Proof Approximation Algorithms for the Stable Marriage Problem with Ties and Incomplete Lists
• Competing Bandits in Matching Markets
• Towards Federated Learning in UAV-Enabled Internet of Vehicles: A Multi-Dimensional Contract-Matching Approach
• The Large Core of College Admission Markets: Theory and Evidence
• Deferred acceptance algorithms: history, theory, practice, and open questions
• Deep Learning for Two-Sided Matching
• The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory
• Some remarks on the stable matching problem
• The Influence of One Strategic Agent on the Core of Stable Matchings
• The Machiavellian frontier of top trading cycles
• Toward market design in practice: a progress report. [europepmc]
• Strategyproof and fair matching mechanism for union of symmetric m-convex constraints. [europepmc]

Related

• Sophisticated Students in Boston Mechanism and Gale-Shapley Algorithm for School Choice Problem
• What Pareto-Efficiency Adjustments Cannot Fix
• Reciprocating Preferences Stablize Matching: College Admissions Revisited
• Improving the Deferred Acceptance with Minimal Compromise
• Local non-bossiness