DOI: https://doi.org/10.1016/j.cosrev.2025.100835
تاريخ النشر: 2026-02-11
المؤلف: Jiehua Chen وآخرون
الموضوع الرئيسي: نظرية الألعاب وأنظمة التصويت
نظرة عامة
في هذه الدراسة، نحقق في التعقيد المعتمد على المعلمات لمشكلتين هامتين في الاختيار الاجتماعي الحاسوبي (COMSOC): تحديد الفائزين المتعددين والألعاب الهيدونية. تكشف نتائجنا أن المعلمات الطبيعية، مثل عدد البدائل أو الناخبين، غالبًا ما تسمح بخوارزميات قابلة للحل بمعلمات ثابتة (FPT) من خلال التعداد بالقوة الغاشمة. ومع ذلك، فإن المعلمات مثل حجم اللجنة $k$ أو الدرجة القصوى $\Delta$ في رسومات الصداقة تؤدي غالبًا إلى عدم القدرة على الحل المعتمد على المعلمات، والتي تصنف على أنها W[1]-صعبة، W[2]-صعبة، أو NP-صعبة. بالإضافة إلى ذلك، بينما تحتفظ التخصيصات الفردية غالبًا بالصعوبة، يمكن أن تعزز التخصيصات المجمعة القابلية للحل، مما يبرز الطبيعة متعددة المتغيرات للتحديات الحاسوبية في COMSOC.
نلاحظ أيضًا أن تقييد التفضيلات إلى مجالات منظمة، مثل الملفات ذات القمة الواحدة أو التقاطعات الفردية، يؤدي عمومًا إلى خوارزميات زمنية متعددة الحدود. علاوة على ذلك، أظهرت التخصيصات التي تقيم “المسافة إلى القابلية للحل” كل من القوة النظرية والأهمية العملية. تستخدم تحليلاتنا مجموعة متنوعة من تقنيات الإثبات، بما في ذلك تقنيات النواة والبرمجة الديناميكية، والتي قد تفيد في تنفيذ الخوارزميات العملية. بخلاف مجالات التركيز الرئيسية، نعترف بالتقدم الكبير في التعقيد المعتمد على المعلمات ضمن المطابقة تحت التفضيلات وتخصيص الموارد، مما يشير إلى مستقبل حيوي للبحث في هذه المجالات. من المتوقع أن يحفز ندوة داجشتول القادمة حول حدود خوارزميات المعلمات المزيد من التطورات في هذا المجال سريع التطور.
مقدمة
تقدم مقدمة ورقة البحث حول الاختيار الاجتماعي الحاسوبي (COMSOC) الطبيعة متعددة التخصصات لهذا المجال، الذي يدمج مفاهيم من علوم الكمبيوتر، والاقتصاد، والعلوم السياسية، والذكاء الاصطناعي. تبرز مجموعة متنوعة من المشكلات التي يتم تناولها ضمن COMSOC، بما في ذلك تحديد الفائز، والتلاعب بالتصويت، وتشكيل الائتلافات، وتخصيص الموارد. العديد من هذه المشكلات تمثل تحديات حاسوبية، وغالبًا ما تصنف على أنها NP-صعبة، مثل تحديد الفائز الفردي وفقًا لقواعد دودجسون وكيمين، ووجود تخصيصات خالية من الحسد للسلع غير القابلة للتقسيم.
تؤكد الورقة على أهمية التعقيد المعتمد على المعلمات في تحليل هذه المشكلات، وهو منظور رائد من قبل مايك فيلوز وزملائه. لقد أدى عملهم إلى ازدهار البحث في هذا المجال، مع العديد من الدراسات والاستطلاعات التي تركز على خوارزميات المعلمات الثابتة لمشكلات COMSOC المختلفة. يركز المؤلفون بشكل خاص على موضوعين نشطين في البحث – تحديد الفائزين المتعددين والألعاب الهيدونية – بسبب زخم البحث الأخير، والمناظر المعقدة التكميلية، والأهمية العملية، والقدرة على تقديم رؤى هيكلية يمكن أن تفيد التحديات الأوسع في COMSOC. تختتم المقدمة بسؤال مفتوح يتعلق بقابلية الحل المعتمد على المعلمات لتحديد ملفات تفضيل الموافقة المحددة، مما يشير إلى فرص البحث المستمرة في هذا المجال.
نقاش
تحدد قسم النقاش في ورقة البحث الهيكل والنتائج المتعلقة بتحديد الفائزين المتعددين والألعاب الهيدونية، مع التركيز على تعقيدات اختيار اللجان بناءً على تفضيلات الناخبين. تنقسم الدراسة إلى جزئين رئيسيين، حيث يتناول كل جزء المفاهيم الأساسية، والمعلمات الرئيسية، ونتائج التعقيد، مما يؤدي إلى مناقشات حول مواضيع إضافية واتجاهات البحث المستقبلية. يبرز القسم التحديات الحاسوبية المرتبطة بقواعد التصويت المختلفة، مثل قواعد مونرو وقواعد تشامبرلين-كورانت، التي تهدف إلى تقليل التمثيل الخاطئ بين الناخبين وممثليهم المعينين.
في سياق تحديد الفائزين المتعددين، تقدم الورقة تعريفات رسمية لملفات التفضيل، مميزة بين التفضيلات الخطية وتفضيلات الموافقة. تبرز أهمية مجالات التفضيل المنظمة، وخاصة التفضيلات ذات القمة الواحدة والتفضيلات ذات التقاطع الفردي، التي يمكن أن تبسط المهام الحاسوبية. يناقش المؤلفون أيضًا نتائج التعقيد المعتمد على المعلمات، موضحين قابلية الحل لبعض المشكلات بينما يحددون حواجز الصعوبة. من الجدير بالذكر أن الورقة تقدم تقنيات إثبات متنوعة، بما في ذلك الأساليب القوية وتقنيات التخفيض المعتمدة على المعلمات، لتحليل مشهد تعقيد مشكلات تحديد الفائزين المتعددين، مما يساهم في فهم أعمق للتحديات الخوارزمية في هذا المجال.
DOI: https://doi.org/10.1016/j.cosrev.2025.100835
Publication Date: 2026-02-11
Author(s): Jiehua Chen et al.
Primary Topic: Game Theory and Voting Systems
Overview
In this survey, we investigate the parameterized complexity of two significant problems in Computational Social Choice (COMSOC): MULTI-WINNER DETERMINATION and HEDONIC GAMES. Our findings reveal that natural parameters, such as the number of alternatives or voters, often allow for fixed-parameter tractable (FPT) algorithms through brute-force enumeration. However, parameters like committee size $k$ or maximum degree $\Delta$ in friendship graphs frequently lead to parameterized intractability, categorized as W[1]-hard, W[2]-hard, or NP-hard. Additionally, while single parameterizations often retain hardness, combined parameterizations can enhance tractability, highlighting the multivariate nature of computational challenges in COMSOC.
We also note that restricting preferences to structured domains, such as single-peaked or single-crossing profiles, generally results in polynomial-time algorithms. Furthermore, parameterizations that assess “distance to tractability” have shown both theoretical robustness and practical relevance. Our analysis employs a diverse array of proof techniques, including kernelization and dynamic programming, which may inform practical algorithmic implementations. Beyond the primary focus areas, we acknowledge significant advancements in parameterized complexity within MATCHING UNDER PREFERENCES and RESOURCE ALLOCATION, suggesting a vibrant future for research in these domains. The upcoming Dagstuhl Seminar on Frontiers of Parameterized Algorithmics is anticipated to further stimulate developments in this rapidly evolving field.
Introduction
The introduction to the research paper on Computational Social Choice (COMSOC) outlines the interdisciplinary nature of the field, which integrates concepts from computer science, economics, political science, and artificial intelligence. It highlights the diverse range of problems addressed within COMSOC, including winner determination, voting manipulation, coalition formation, and resource allocation. Many of these problems are computationally challenging, often classified as NP-hard, such as single-winner determination under Dodgson’s and Kemeny’s rules, and the existence of envy-free allocations of indivisible goods.
The paper emphasizes the significance of parameterized complexity in analyzing these problems, a perspective pioneered by Mike Fellows and colleagues. Their work has led to a flourishing of research in this area, with numerous surveys and studies focusing on fixed-parameter algorithms for various COMSOC problems. The authors specifically focus on two active research topics—multi-winner determination and hedonic games—due to their recent research momentum, complementary complexity landscapes, practical significance, and the potential for structural insights that can inform broader COMSOC challenges. The introduction concludes with an open question regarding the fixed-parameter tractability of determining specific approval preference profiles, indicating ongoing research opportunities in the field.
Discussion
The discussion section of the research paper outlines the structure and findings related to multi-winner determination and hedonic games, focusing on the complexities of selecting committees based on voter preferences. The survey is divided into two main parts, with each part detailing foundational concepts, key parameters, and complexity results, culminating in discussions of additional topics and future research directions. The section emphasizes the computational challenges associated with various voting rules, such as the Monroe and Chamberlin-Courant rules, which aim to minimize misrepresentation between voters and their assigned representatives.
In the context of multi-winner determination, the paper introduces formal definitions of preference profiles, distinguishing between linear and approval preferences. It highlights the significance of structured preference domains, specifically single-peaked and single-crossing preferences, which can simplify computational tasks. The authors also discuss parameterized complexity results, illustrating the tractability of certain problems while identifying hardness barriers. Notably, the paper presents various proof techniques, including brute force approaches and parameterized reductions, to analyze the complexity landscape of multi-winner determination problems, ultimately contributing to a deeper understanding of the algorithmic challenges in this domain.