2024-03-29T14:22:39Z
https://tsukuba.repo.nii.ac.jp/oai
oai:tsukuba.repo.nii.ac.jp:00028146
2022-04-27T08:56:12Z
152:311
3:62:5592:2037
Preference profiles determining the proposals in the Gale–Shapley algorithm for stable matching problems
山本, 芳嗣
Sukegawa, Noriyoshi
Yamamoto, Yoshitsugu
©The JJIAM Publishing Committee and Springer 2012.
The original publication is available at www.springerlink.com
Concerning the strategic manipulability of the stable matching produced by the Gale–Shapley algorithm, Kobayashi and Matsui recently considered the existence problem of a preference profile of women, that is, given a preference profile of men, find a preference profile of women that makes the Gale–Shapley algorithm produce the prescribed complete matching of men and women. Reformulating this problem by introducing the set of proposals to be made through the execution of the algorithm, and switching the roles of men and women, we consider the existence problem of a preference profile of men and show that the problem is reduced to a problem of checking if a directed graph is a rooted tree and it is solvable in polynomial time. We also show that the existence problem of preference profiles of both sexes when a set of proposals is given is solvable in polynomial time.
Springer
2012-10
eng
journal article
http://hdl.handle.net/2241/118158
https://tsukuba.repo.nii.ac.jp/records/28146
10.1007/s13160-012-0077-x
0916-7005
AA10799861
Japan journal of industrial and applied mathematics
29
3
547
560
https://tsukuba.repo.nii.ac.jp/record/28146/files/JJIAM_29-3.pdf
application/pdf
114.5 kB
2013-12-25