The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Cet article traite d'une question stratégique dans le modèle de mariage stable avec des listes de préférences complètes (c'est-à-dire qu'une liste de préférences d'un agent est une permutation de tous les membres du sexe opposé). Étant donné les listes complètes de préférences de n les hommes finis n femmes, et un mariage µ, nous considérons le problème de la recherche de listes de préférences de n les femmes finies n hommes de telle sorte que l'algorithme d'acceptation différée proposé par les hommes (algorithme de Gale-Shapley) adopté pour les listes produit µ. Nous montrons une condition simple, nécessaire et suffisante, pour l’existence d’un ensemble de listes de préférences des femmes par rapport aux hommes. Notre condition donne directement un O(n2) algorithme temporel pour trouver un ensemble de listes de préférences, s'il existe.
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.
Copier
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
Copier
@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},}
Copier
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 -