WEKO3
アイテム
Cheating Strategies for the Gale-Shapley Algorithm with Complete Preference Lists
https://ipsj.ixsq.nii.ac.jp/records/62459
https://ipsj.ixsq.nii.ac.jp/records/62459481be4ab-b882-471d-8781-63c9ae2efd1b
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL09125006.pdf (129.1 kB)
|
Copyright (c) 2009 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2009-07-14 | |||||||
| タイトル | ||||||||
| タイトル | Cheating Strategies for the Gale-Shapley Algorithm with Complete Preference Lists | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Cheating Strategies for the Gale-Shapley Algorithm with Complete Preference Lists | |||||||
| 言語 | ||||||||
| 言語 | eng | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| Chuo University | ||||||||
| 著者所属 | ||||||||
| Chuo University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Chuo University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Chuo University | ||||||||
| 著者名 |
Hirotatsu, Kobayashi
× Hirotatsu, Kobayashi
|
|||||||
| 著者名(英) |
Hirotatsu, Kobayashi
× Hirotatsu, Kobayashi
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 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 all the men, a partial marriage, and complete preference lists of unmatched women, we consider the problem of finding preference lists of matched women such that the men-proposing Gale-Shapley algorithm applied to the lists produces a (perfect) marriage which is an extension of a given partial marriage. We propose a polynomial time algorithm for finding a desired set of preference lists, if theses exist. We also deal with the case that complete preference lists of all the men and a partial marriage are given. In this case, we consider a problem of the existence of preference lists of all the women such that the men-proposing Gale-Shapley algorithm produces a marriage including a given partial marriage. We show NP-completeness of this problem. | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 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 all the men, a partial marriage, and complete preference lists of unmatched women, we consider the problem of finding preference lists of matched women such that the men-proposing Gale-Shapley algorithm applied to the lists produces a (perfect) marriage which is an extension of a given partial marriage. We propose a polynomial time algorithm for finding a desired set of preference lists, if theses exist. We also deal with the case that complete preference lists of all the men and a partial marriage are given. In this case, we consider a problem of the existence of preference lists of all the women such that the men-proposing Gale-Shapley algorithm produces a marriage including a given partial marriage. We show NP-completeness of this problem. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
研究報告アルゴリズム（AL） 巻 2009-AL-125, 号 6, p. 1-8, 発行日 2009-07-14 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
