Successful Manipulation in Stable Marriage Model with Complete Preference Lists
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E92-D No.2 pp.116-119
- Publication Date
- 2009/02/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E92.D.116
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Hirotatsu KOBAYASHI, Tomomi MATSUI, "Successful Manipulation in Stable Marriage Model with Complete Preference Lists" in IEICE TRANSACTIONS on Information,
vol. E92-D, no. 2, pp. 116-119, February 2009, doi: 10.1587/transinf.E92.D.116.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E92.D.116/_p
Copy
@ARTICLE{e92-d_2_116,
author={Hirotatsu KOBAYASHI, Tomomi MATSUI, },
journal={IEICE TRANSACTIONS on Information},
title={Successful Manipulation in Stable Marriage Model with Complete Preference Lists},
year={2009},
volume={E92-D},
number={2},
pages={116-119},
abstract={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.},
keywords={},
doi={10.1587/transinf.E92.D.116},
ISSN={1745-1361},
month={February},}
Copy
TY - JOUR
TI - Successful Manipulation in Stable Marriage Model with Complete Preference Lists
T2 - IEICE TRANSACTIONS on Information
SP - 116
EP - 119
AU - Hirotatsu KOBAYASHI
AU - Tomomi MATSUI
PY - 2009
DO - 10.1587/transinf.E92.D.116
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E92-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2009
AB - 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.
ER -
English
