Successful Manipulation in Stable Marriage Model with Complete Preference Lists

Hirotatsu KOBAYASHI  Tomomi MATSUI  

IEICE TRANSACTIONS on Information and Systems   Vol.E92-D   No.2   pp.116-119
Publication Date: 2009/02/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E92.D.116
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)
stable marriage,  Gale-Shapley algorithm,  graph theory,  strategic manipulation,  

Full Text: PDF(136.3KB)>>
Buy this Article

This paper deals with a strategic issue in the stable marriage model with complete preference lists (i.e., a preference list of an agent is a permutation of all the members of the opposite sex). Given complete preference lists of n men over n women, and a marriage µ, we consider the problem for finding preference lists of n women over n men such that the men-proposing deferred acceptance algorithm (Gale-Shapley algorithm) adopted to the lists produces µ. We show a simple necessary and sufficient condition for the existence of a set of preference lists of women over men. Our condition directly gives an O(n2) time algorithm for finding a set of preference lists, if it exists.