The search functionality is under construction.

The search functionality is under construction.

The family of stable matching problems have been well-studied across a wide field of research areas, including economics, mathematics and computer science. In general, an instance of a stable matching problem is given by a set of participants who have expressed their preferences of each other, and asks to find a “stable” matching, that is, a pairing of the participants such that no unpaired participants prefer each other to their assigned partners. In the case of the Stable Roommates Problem (SR), it is known that given an even number *n* of participants, there might not exist a stable matching that pairs all of the participants, but there exist efficient algorithms to determine if this is possible or not, and if it is possible, produce such a matching. Common extensions of SR allow for the participants' preference lists to be incomplete, or include indifference. Allowing indifference in turn, gives rise to different possible definitions of stability, super, strong, and weak stability. While instances asking for super and strongly stable matching can be efficiently solved even if preference lists are incomplete, the case of weak stability is NP-complete. We examine a restricted case of indifference, introducing the concept of *unranked* entries. For this type of instances, we show that the problem of finding a weakly stable matching remains NP-complete even if each participant has a complete preference list with at most two unranked entries, or is herself unranked for up to three other participants. On the other hand, for instances where there are *m* acceptable pairs and there are in total *k* unranked entries in all of the participants' preference lists, we propose an *O*(2^{k}n^{2})-time and polynomial space algorithm that finds a stable matching, or determines that none exists in the given instance.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E101-A No.9 pp.1412-1419

- Publication Date
- 2018/09/01

- Publicized

- Online ISSN
- 1745-1337

- DOI
- 10.1587/transfun.E101.A.1412

- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

- Category

Hiroaki SUTO

Kyoto University

Aleksandar SHURBEVSKI

Kyoto University

Hiroshi NAGAMOCHI

Kyoto University

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.

Copy

Hiroaki SUTO, Aleksandar SHURBEVSKI, Hiroshi NAGAMOCHI, "The Stable Roommates Problem with Unranked Entries" in IEICE TRANSACTIONS on Fundamentals,
vol. E101-A, no. 9, pp. 1412-1419, September 2018, doi: 10.1587/transfun.E101.A.1412.

Abstract: The family of stable matching problems have been well-studied across a wide field of research areas, including economics, mathematics and computer science. In general, an instance of a stable matching problem is given by a set of participants who have expressed their preferences of each other, and asks to find a “stable” matching, that is, a pairing of the participants such that no unpaired participants prefer each other to their assigned partners. In the case of the Stable Roommates Problem (SR), it is known that given an even number *n* of participants, there might not exist a stable matching that pairs all of the participants, but there exist efficient algorithms to determine if this is possible or not, and if it is possible, produce such a matching. Common extensions of SR allow for the participants' preference lists to be incomplete, or include indifference. Allowing indifference in turn, gives rise to different possible definitions of stability, super, strong, and weak stability. While instances asking for super and strongly stable matching can be efficiently solved even if preference lists are incomplete, the case of weak stability is NP-complete. We examine a restricted case of indifference, introducing the concept of *unranked* entries. For this type of instances, we show that the problem of finding a weakly stable matching remains NP-complete even if each participant has a complete preference list with at most two unranked entries, or is herself unranked for up to three other participants. On the other hand, for instances where there are *m* acceptable pairs and there are in total *k* unranked entries in all of the participants' preference lists, we propose an *O*(2^{k}n^{2})-time and polynomial space algorithm that finds a stable matching, or determines that none exists in the given instance.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E101.A.1412/_p

Copy

@ARTICLE{e101-a_9_1412,

author={Hiroaki SUTO, Aleksandar SHURBEVSKI, Hiroshi NAGAMOCHI, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={The Stable Roommates Problem with Unranked Entries},

year={2018},

volume={E101-A},

number={9},

pages={1412-1419},

abstract={The family of stable matching problems have been well-studied across a wide field of research areas, including economics, mathematics and computer science. In general, an instance of a stable matching problem is given by a set of participants who have expressed their preferences of each other, and asks to find a “stable” matching, that is, a pairing of the participants such that no unpaired participants prefer each other to their assigned partners. In the case of the Stable Roommates Problem (SR), it is known that given an even number *n* of participants, there might not exist a stable matching that pairs all of the participants, but there exist efficient algorithms to determine if this is possible or not, and if it is possible, produce such a matching. Common extensions of SR allow for the participants' preference lists to be incomplete, or include indifference. Allowing indifference in turn, gives rise to different possible definitions of stability, super, strong, and weak stability. While instances asking for super and strongly stable matching can be efficiently solved even if preference lists are incomplete, the case of weak stability is NP-complete. We examine a restricted case of indifference, introducing the concept of *unranked* entries. For this type of instances, we show that the problem of finding a weakly stable matching remains NP-complete even if each participant has a complete preference list with at most two unranked entries, or is herself unranked for up to three other participants. On the other hand, for instances where there are *m* acceptable pairs and there are in total *k* unranked entries in all of the participants' preference lists, we propose an *O*(2^{k}n^{2})-time and polynomial space algorithm that finds a stable matching, or determines that none exists in the given instance.},

keywords={},

doi={10.1587/transfun.E101.A.1412},

ISSN={1745-1337},

month={September},}

Copy

TY - JOUR

TI - The Stable Roommates Problem with Unranked Entries

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 1412

EP - 1419

AU - Hiroaki SUTO

AU - Aleksandar SHURBEVSKI

AU - Hiroshi NAGAMOCHI

PY - 2018

DO - 10.1587/transfun.E101.A.1412

JO - IEICE TRANSACTIONS on Fundamentals

SN - 1745-1337

VL - E101-A

IS - 9

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - September 2018

AB - The family of stable matching problems have been well-studied across a wide field of research areas, including economics, mathematics and computer science. In general, an instance of a stable matching problem is given by a set of participants who have expressed their preferences of each other, and asks to find a “stable” matching, that is, a pairing of the participants such that no unpaired participants prefer each other to their assigned partners. In the case of the Stable Roommates Problem (SR), it is known that given an even number *n* of participants, there might not exist a stable matching that pairs all of the participants, but there exist efficient algorithms to determine if this is possible or not, and if it is possible, produce such a matching. Common extensions of SR allow for the participants' preference lists to be incomplete, or include indifference. Allowing indifference in turn, gives rise to different possible definitions of stability, super, strong, and weak stability. While instances asking for super and strongly stable matching can be efficiently solved even if preference lists are incomplete, the case of weak stability is NP-complete. We examine a restricted case of indifference, introducing the concept of *unranked* entries. For this type of instances, we show that the problem of finding a weakly stable matching remains NP-complete even if each participant has a complete preference list with at most two unranked entries, or is herself unranked for up to three other participants. On the other hand, for instances where there are *m* acceptable pairs and there are in total *k* unranked entries in all of the participants' preference lists, we propose an *O*(2^{k}n^{2})-time and polynomial space algorithm that finds a stable matching, or determines that none exists in the given instance.

ER -