DOI: https://doi.org/10.1145/3839240
تاريخ النشر: 2026-09-11
المؤلف: Christine T. Cheng وآخرون
الموضوع الرئيسي: نظرية الألعاب وأنظمة التصويت
نظرة عامة
في مشكلة زملاء السكن المستقرين (SR)، الهدف هو العثور على تطابق مستقر بين 2𝑛 وكيلًا يقومون بتقييم بعضهم البعض، مع ضمان عدم تفضيل وكيلين لبعضهما البعض على شركائهما المعينين. يقدم هذا البحث مفهوم الحد الأدنى من مسافة العبور، وهو معلمة تقيس التشابه الهيكلي بين حالات SR وحالات الزواج المستقر (SM). عندما تكون مسافة العبور الدنيا صفرًا، يمكن حل حالة SR بكفاءة باستخدام خوارزميات قابلة للتطبيق على حالات SM. بشكل أكثر عمومية، يوضح المؤلفون أنه بالنسبة لحالة SR مع مسافة عبور دنيا قدرها 𝑘، يمكن حساب تطابق مستقر مثالي في وقت $2^{O(k)} n^{O(1)}$، مما يثبت أن المشكلة قابلة للحل بمعلمة ثابتة (FPT) بالنسبة لهذه المسافة.
تربط النتائج الفجوة بين قابلية الحل المتعددة الحدود لحالات SM وصعوبة NP لحالات SR، مما يشير إلى أنه كلما كانت حالة SR أقرب إلى حالة SM، أصبحت الخوارزمية أكثر كفاءة. كما يحدد البحث اتجاهات البحث المستقبلية، مثل التحقيق في مسافات العبور الدنيا النموذجية في حالات SR العملية واستكشاف حدود أكثر دقة لحدود العبور في الهياكل ذات الصلة. بالإضافة إلى ذلك، يثير أسئلة حول التحول المحتمل لخوارزميات الوقت المتعدد الحدود لحالات SM إلى خوارزميات FPT لحالات SR، مما يعزز الفهم للعلاقة بين هياكل التفضيل وتعقيد الحساب في مشاكل المطابقة.
مقدمة
في عملهم الأساسي، قدم غايل وشابلي مشكلة الزواج المستقر (SM) ونظيرتها غير الثنائية، مشكلة زملاء السكن المستقرين (SR). تتضمن SM مجموعتين من الوكلاء (تقليديًا الرجال والنساء) الذين يقيمون أعضاء المجموعة المعاكسة، بهدف العثور على تطابق مستقر حيث لا يفضل وكيلان بعضهما البعض على شركائهما المعينين. أظهر غايل وشابلي أن كل حالة SM تضمن تطابقًا مستقرًا من خلال خوارزمية فعالة. على العكس من ذلك، في SR، حيث يقوم الوكلاء بتقييم جميع الآخرين داخل مجموعة واحدة، لا توجد الاستقرار دائمًا، كما أظهر غايل وشابلي. قدم العمل اللاحق من إيرفينغ خوارزمية فعالة لتحديد قابلية حل حالات SR، والتي تم إثبات أنها مثالية.
تستكشف هذه الفقرة المزيد من الاختلافات الهيكلية بين تطابقات SM وSR، مشيرة إلى أنه بينما تشكل تطابقات SM شبكة موزعة بسبب طبيعتها الثنائية، يتم تمثيل تطابقات SR بواسطة الرسوم البيانية الوسيطة، التي تفتقر إلى ترتيب طبيعي. ومع ذلك، من خلال تعيين تطابق مستقر كجذر، يمكن إنشاء هيكل موجه يعرف باسم مخطط هاسي لشبكة وسيطة، وهو أكثر عمومية من شبكة موزعة. يبرز المؤلفون أنه، على الرغم من التشابه في هياكل التطابقات المستقرة، لا تزال التحديات الحسابية قائمة في SR التي لا تنشأ في SM. على وجه التحديد، يمكن حل مشاكل مثل العثور على تطابقات مستقرة متساوية أو ذات ترتيب أقصى بكفاءة في SM ولكنها صعبة NP في SR. تحفز هذه الملاحظة تطوير خوارزمية قابلة للحل بمعلمة ثابتة (FPT) لتطابقات SR المستقرة المثلى، باستخدام الحد الأدنى من مسافة العبور كمعلمة لقياس التشابه الهيكلي لحالات SR مع حالات SM.
نقاش
في هذا القسم، يناقش المؤلفون مساهماتهم في مشكلة التطابق المستقر المثالي، مع التركيز على دالة التكلفة \( C(a, b) \) التي تقيس تكلفة مطابقة الوكلاء \( a \) و \( b \). يعرفون التطابقات المستقرة من حيث تقليل التكلفة، مقدمين مفاهيم مثل التطابقات المستقرة المتساوية، والتطابقات المستقرة ذات الترتيب الأقصى والسخية. يقدم المؤلفون النظرية 4.7، التي توضح أن التقنيات من الأعمال السابقة يمكن تكييفها لحساب التطابقات المستقرة المثلى محليًا بكفاءة في سياق زملاء السكن المستقرين (SR). يصفون خوارزمية تحسب تطابقًا مستقرًا مثاليًا في وقت \( O(r \cdot n^4 \log n) \)، حيث \( r \) هو عدد العناصر القصوى في الشبكة الوسيطة المستمدة من التطابق المستقر.
يستكشف المؤلفون أيضًا العلاقة بين هيكل مجموعات المرآة ومشكلة التطابق المستقر المثالي. يقدمون مشكلة الحد الأدنى من توجيه العبور (MCO)، مثبتين صعوبتها NP ومؤسسين خوارزمية قابلة للحل بمعلمة ثابتة (FPT) لحالات ذات مسافة عبور دنيا \( k \). النتيجة الرئيسية، النظرية 1.1، تؤكد أنه يمكن العثور على تطابق مستقر مثالي في وقت \( 2^{O(k)} n^{O(1)} \)، مما يربط تعقيد مشكلة التطابق المستقر المثالي في حالات SR بقربها من حالات الزواج المستقر (SM). يقترح المؤلفون أن نهجهم قد يمتد إلى هياكل تركيبة أخرى، مما يشير إلى آثار أوسع لدراسة التطابقات المستقرة والمشاكل ذات الصلة.
DOI: https://doi.org/10.1145/3839240
Publication Date: 2026-09-11
Author(s): Christine T. Cheng et al.
Primary Topic: Game Theory and Voting Systems
Overview
In the Stable Roommates Problem (SR), the objective is to find a stable matching among 2𝑛 agents who rank each other, ensuring no two agents prefer each other over their assigned partners. This paper introduces the concept of minimum crossing distance, a parameter that quantifies the structural similarity between SR and Stable Marriage (SM) instances. When the minimum crossing distance is zero, the SR instance can be solved efficiently using algorithms applicable to SM instances. More generally, the authors demonstrate that for an SR instance with a minimum crossing distance of 𝑘, an optimal stable matching can be computed in time $2^{O(k)} n^{O(1)}$, establishing that the problem is fixed-parameter tractable (FPT) with respect to this distance.
The findings bridge the gap between the polynomial solvability of SM instances and the NP-hardness of SR instances, indicating that the closer an SR instance is to an SM instance, the more efficient the algorithm becomes. The paper also outlines future research directions, such as investigating typical minimum crossing distances in practical SR instances and exploring tighter bounds for crossing edges in related structures. Additionally, it raises questions about the potential transformation of polynomial-time algorithms for SM into FPT algorithms for SR, thereby enhancing the understanding of the relationship between preference structures and computational complexity in matching problems.
Introduction
In their foundational work, Gale and Shapley introduced the Stable Marriage Problem (SM) and its non-bipartite counterpart, the Stable Roommates Problem (SR). The SM involves two groups of agents (traditionally men and women) who rank members of the opposite group, with the objective of finding a stable matching where no two agents would prefer each other over their assigned partners. Gale and Shapley demonstrated that every SM instance guarantees a stable matching through an efficient algorithm. Conversely, in SR, where agents rank all others within a single group, stability does not always exist, as shown by Gale and Shapley. Subsequent work by Irving provided an efficient algorithm for determining the solvability of SR instances, which has been proven optimal.
The section further explores the structural differences between SM and SR matchings, noting that while SM matchings form a distributive lattice due to their bipartite nature, SR matchings are represented by median graphs, which lack a natural ordering. However, by designating a stable matching as a root, one can create a directed structure known as the Hasse diagram of a median semilattice, which is more general than a distributive lattice. The authors highlight that, despite the similarities in the structures of stable matchings, computational challenges persist in SR that do not arise in SM. Specifically, problems such as finding egalitarian or rank-maximal stable matchings can be efficiently solved in SM but are NP-hard in SR. This observation motivates the development of a fixed-parameter tractable (FPT) algorithm for optimal SR stable matchings, using minimum crossing distance as a parameter to measure the structural similarity of SR instances to SM instances.
Discussion
In this section, the authors discuss their contributions to the optimal stable matching problem, focusing on the cost function \( C(a, b) \) that quantifies the cost of matching agents \( a \) and \( b \). They define stable matchings in terms of cost minimization, introducing concepts such as egalitarian stable matchings, rank-maximal and generous stable matchings. The authors present Theorem 4.7, which demonstrates that techniques from previous work can be adapted to efficiently compute locally optimal stable matchings in the stable roommates (SR) context. They describe an algorithm that computes an optimal stable matching in time \( O(r \cdot n^4 \log n) \), where \( r \) is the number of maximal elements in the median semilattice derived from the stable matching.
The authors further explore the relationship between the structure of mirror posets and the optimal stable matching problem. They introduce the Minimum Crossing Orientation (MCO) problem, proving its NP-hardness and establishing a fixed-parameter tractable (FPT) algorithm for instances with a minimum crossing distance \( k \). The main result, Theorem 1.1, asserts that an optimal stable matching can be found in time \( 2^{O(k)} n^{O(1)} \), linking the complexity of the optimal stable matching problem in SR instances to their proximity to stable marriage (SM) instances. The authors suggest that their approach may extend to other combinatorial structures, indicating broader implications for the study of stable matchings and related problems.
