Cheating strategies for the Gale-Shapley algorithm with complete preference lists

DOI10.1007/s00453-009-9359-3zbMath1204.68147OpenAlexW2007568203MaRDI QIDQ1959731

Hirotatsu Kobayashi, Tomomi Matsui

Publication date: 7 October 2010

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-009-9359-3

zbMATH Keywords

graph theoryNP-completestable marriage

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Permutations, words, matrices (05A05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (6)

Preference profiles determining the proposals in the Gale-Shapley algorithm for stable matching problems ⋮ Subquadratic algorithms for succinct stable matching ⋮ Strategic issues in college admissions with score-limits ⋮ Stable matching games: manipulation via subgraph isomorphism ⋮ Coalitional permutation manipulations in the Gale-Shapley algorithm ⋮ Algorithmic Aspects of Equilibria of Stable Marriage Model with Complete Preference Lists

Cites Work

• Unnamed Item
• Unnamed Item
• Some remarks on the stable matching problem
• Gale-Shapley Stable Marriage Problem Revisited: Strategic Issues and Applications
• Ms. Machiavelli and the Stable Matching Problem
• The Economics of Matching: Stability and Incentives
• Depth-First Search and Linear Graph Algorithms
• College Admissions and the Stability of Marriage

This page was built for publication: Cheating strategies for the Gale-Shapley algorithm with complete preference lists