2025-11-23T02:22:15.133554

Single-Deviation Stability in Additively Separable Hedonic Games with Constrained Coalition Sizes

Bullinger, Dunajski, Elkind et al.

We study stability in additively separable hedonic games when coalition sizes have to respect fixed size bounds. We consider four classic notions of stability based on single-agent deviations, namely, Nash stability, individual stability, contractual Nash stability, and contractual individual stability. For each stability notion, we consider two variants: in one, the coalition left behind by a deviator must still be of a valid size, and in the other there is no such constraint. We provide a full picture of the existence of stable outcomes with respect to given size parameters. Additionally, when there are only upper bounds, we fully characterize the computational complexity of the associated existence problem. In particular, we obtain polynomial-time algorithms for contractual individual stability and contractual Nash stability, where the latter requires an upper bound of 2. We obtain further results for Nash stability and contractual individual stability, when the lower bound is at least 2.

academic

सीमित गठबंधन आकारों के साथ योजक रूप से वियोज्य हेडोनिक खेलों में एकल-विचलन स्थिरता

बुनियादी जानकारी

पेपर ID: 2510.12641
शीर्षक: Single-Deviation Stability in Additively Separable Hedonic Games with Constrained Coalition Sizes
लेखक: Martin Bullinger (University of Bristol), Adam Dunajski (University of Edinburgh), Edith Elkind (Northwestern University), Matan Gilboa (University of Oxford)
वर्गीकरण: cs.GT (खेल सिद्धांत), cs.DS (डेटा संरचनाएं और एल्गोरिदम)
प्रकाशन तिथि: 14 अक्टूबर 2025 (arXiv प्रीप्रिंट)
पेपर लिंक: https://arxiv.org/abs/2510.12641

सारांश

यह पेपर गठबंधन आकार के निर्धारित सीमा बाधाओं के तहत योजक रूप से वियोज्य हेडोनिक खेलों (ASHG) में स्थिरता की समस्या का अध्ययन करता है। लेखकों ने एकल एजेंट विचलन पर आधारित चार शास्त्रीय स्थिरता अवधारणाओं पर विचार किया है: नैश स्थिरता (Nash stability), व्यक्तिगत स्थिरता (individual stability), संविदात्मक नैश स्थिरता (contractual Nash stability) और संविदात्मक व्यक्तिगत स्थिरता (contractual individual stability)। प्रत्येक स्थिरता अवधारणा के लिए, लेखकों ने दो प्रकार पर विचार किया है: एक जो विचलनकर्ताओं द्वारा छोड़े गए गठबंधन को वैध आकार बनाए रखने की आवश्यकता करता है, दूसरा इस बाधा के बिना। पेपर दिए गए आकार मापदंडों के तहत स्थिर परिणामों के अस्तित्व की संपूर्ण तस्वीर प्रदान करता है और केवल ऊपरी सीमा बाधा के साथ संबंधित अस्तित्व समस्याओं की कम्प्यूटेशनल जटिलता को पूरी तरह से चिन्हित करता है।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या की महत्ता

गठबंधन निर्माण बहु-एजेंट प्रणालियों में एक मूल समस्या है, जिसका व्यापक अनुप्रयोग है:

छात्र समूह परियोजनाओं में समूह विभाजन
विभाग कार्यालयों में सीट आवंटन
बाहरी गतिविधियों में समूह संगठन
सम्मेलन रात्रिभोज में सीट व्यवस्था

ये सभी व्यावहारिक परिदृश्य एक सामान्य विशेषता साझा करते हैं: गठबंधन आकार को ऊपरी और निचली सीमा बाधाओं को पूरा करना चाहिए, साथ ही विभाजन योजना को एजेंटों के विचलन व्यवहार के प्रति स्थिर रहना चाहिए।

मौजूदा अनुसंधान की सीमाएं

निचली सीमा बाधा पर विचार की कमी: पूर्ववर्ती कार्य मुख्य रूप से ऊपरी सीमा बाधाओं पर केंद्रित है, निचली सीमा पर अनुसंधान अपर्याप्त है
अधूरी स्थिरता अवधारणाएं: बाधा परिस्थितियों में विभिन्न स्थिरता अवधारणाओं का व्यवस्थित विश्लेषण नहीं है
अस्पष्ट कम्प्यूटेशनल जटिलता: बाधा परिस्थितियों में विभिन्न स्थिरता अवधारणाओं की कम्प्यूटेशनल जटिलता पूरी तरह से चिन्हित नहीं है

अनुसंधान प्रेरणा

यह पेपर इन अनुसंधान अंतराल को भरने का लक्ष्य रखता है, गठबंधन आकार बाधाओं के तहत हेडोनिक खेल स्थिरता के लिए एक संपूर्ण सैद्धांतिक ढांचा प्रदान करता है।

मुख्य योगदान

संपूर्ण अस्तित्व चिन्हांकन: सभी विचारित स्थिरता अवधारणाओं के लिए दिए गए आकार मापदंडों के तहत अस्तित्व की संपूर्ण तस्वीर प्रदान करता है
कम्प्यूटेशनल जटिलता का संपूर्ण विश्लेषण: केवल ऊपरी सीमा बाधा (λ=1) के साथ, सभी स्थिरता अवधारणाओं की कम्प्यूटेशनल जटिलता को पूरी तरह से चिन्हित करता है
बहुपद समय एल्गोरिदम:
- संविदात्मक व्यक्तिगत स्थिरता (CIS) के लिए बहुपद समय एल्गोरिदम प्रदान करता है
- ऊपरी सीमा 2 होने पर संविदात्मक नैश स्थिरता (CNS) के लिए बहुपद समय एल्गोरिदम प्रदान करता है
- निचली सीमा कम से कम 2 होने पर CIS* के लिए बहुपद समय एल्गोरिदम प्रदान करता है
NP-पूर्णता परिणाम: कई परिस्थितियों में स्थिरता निर्णय समस्या की NP-पूर्णता को साबित करता है
एल्गोरिदम सुधार: Aziz et al. (2013) एल्गोरिदम में त्रुटि को सुधारता है

विधि विवरण

कार्य परिभाषा

इनपुट:

एजेंट सेट N
योजक वियोज्य उपयोगिता फ़ंक्शन v = (va)a∈N, जहां va: N{a} → ℝ
गठबंधन आकार बाधा λ ≤ μ (λ निचली सीमा है, μ ऊपरी सीमा है)

आउटपुट:

(λ,μ)-विभाजन: आकार बाधाओं को संतुष्ट करने वाला गठबंधन विभाजन
स्थिरता निर्णय: क्या यह विभाजन विशिष्ट स्थिरता अवधारणा को संतुष्ट करता है

बाधा शर्तें:

प्रत्येक गठबंधन C λ ≤ |C| ≤ μ को संतुष्ट करता है
विचलन (λ,μ)-अनुमेय या (λ,μ)-व्यवहार्य होना चाहिए

स्थिरता अवधारणा ढांचा

बुनियादी परिभाषाएं

गठबंधन C में एजेंट a की उपयोगिता के लिए: $u_a(C) = \sum_{b \in C\setminus\{a\}} v_a(b)$

चार मानक स्थिरता अवधारणाएं

नैश स्थिरता (NS): कोई एजेंट विचलन से अपनी उपयोगिता में सुधार नहीं कर सकता
व्यक्तिगत स्थिरता (IS): नैश विचलन + लक्ष्य गठबंधन सदस्य सहमति
संविदात्मक नैश स्थिरता (CNS): नैश विचलन + मूल गठबंधन सदस्य सहमति
संविदात्मक व्यक्तिगत स्थिरता (CIS): IS और CNS दोनों शर्तों को संतुष्ट करता है

व्यवहार्यता प्रकार

प्रत्येक मानक अवधारणा के पास संबंधित व्यवहार्यता प्रकार है (चिन्ह * से चिन्हित), जो विचलन के बाद मूल गठबंधन को आकार बाधा को संतुष्ट करने की आवश्यकता करता है।

मुख्य एल्गोरिदम

एल्गोरिदम 1: CIS एल्गोरिदम (संशोधित संस्करण)

इनपुट: ASHG (N,v), पैरामीटर μ
आउटपुट: (1,μ)-विभाजन

1. आरंभीकरण: i←0, A←N
2. जबकि A ≠ ∅:
3.   एजेंट a ∈ A चुनें
4.   नया गठबंधन बनाने की उपयोगिता h की गणना करें
5.   k ∈ [i] के लिए:  // मौजूदा गठबंधन में शामिल होने पर विचार करें
6.     गठबंधन k में शामिल होने की उपयोगिता h' की गणना करें
7.     यदि h < h': सर्वोत्तम विकल्प को अपडेट करें
8.   सर्वोत्तम विकल्प के अनुसार गठबंधन बनाएं/शामिल हों
9.   उपलब्ध एजेंट सेट A को अपडेट करें

एल्गोरिदम 3: CIS* एल्गोरिदम (गैर-शून्य मूल्यांकन)

निचली सीमा λ≥2 की परिस्थिति के लिए, दो-चरण विधि के माध्यम से:

चरण I: प्रत्येक नेता के लिए सर्वोत्तम न्यूनतम आकार गठबंधन बनाएं
चरण II: शेष एजेंटों को विपरीत क्रम में भरें

प्रायोगिक सेटअप

सैद्धांतिक विश्लेषण ढांचा

पेपर मुख्य रूप से सैद्धांतिक विश्लेषण करता है, जिसमें शामिल हैं:

अस्तित्व प्रमाण: रचनात्मक प्रमाण और प्रतिउदाहरण
जटिलता विश्लेषण: कमी प्रमाण और एल्गोरिदम डिजाइन
एल्गोरिदम सही होना: औपचारिक सत्यापन

जटिलता विश्लेषण विधि

NP-पूर्णता प्रमाण: 3-SAT, X3C आदि शास्त्रीय समस्याओं से कमी
बहुपद एल्गोरिदम: रचनात्मक एल्गोरिदम डिजाइन
निचली सीमा विश्लेषण: प्रतिउदाहरणों के माध्यम से अस्तित्व का प्रमाण

प्रायोगिक परिणाम

अस्तित्व परिणाम

स्थिरता अवधारणा	सममित मूल्यांकन	सामान्य मूल्यांकन	सरल सममित मूल्यांकन
NS*	✓अस्तित्व	?अनिश्चित	✓अस्तित्व
IS, CNS	✓अस्तित्व	✗अस्तित्व नहीं	✓अस्तित्व
CIS*	✓अस्तित्व	✓अस्तित्व	✓अस्तित्व
NS, IS, CNS, CIS	✗अस्तित्व नहीं	✗अस्तित्व नहीं	✗अस्तित्व नहीं

मुख्य निष्कर्ष:

सममित मूल्यांकन सबसे मजबूत व्यवहार्य स्थिरता अवधारणा (NS*) के अस्तित्व की गारंटी देता है
यहां तक कि सरल सममित मूल्यांकन के लिए भी, मानक स्थिरता अवधारणाएं अस्तित्व में नहीं हो सकती हैं
CIS* किसी भी परिस्थिति में अस्तित्व में है (जब व्यवहार्य विभाजन अस्तित्व में है)

कम्प्यूटेशनल जटिलता परिणाम (λ=1)

स्थिरता अवधारणा	μ=2	μ≥3
CIS	P	P
CNS	P	NP-पूर्ण
NS, IS	NP-पूर्ण	NP-पूर्ण

विशिष्ट एल्गोरिदम जटिलता:

CIS: O(n³) समय जटिलता के साथ बहुपद एल्गोरिदम
CNS (μ=2): O(n²) समय जटिलता के साथ बहुपद एल्गोरिदम
NS/IS: न्यूनतम अधिकतम मिलान समस्या से कमी के माध्यम से NP-पूर्णता को साबित करता है

निचली सीमा λ≥2 के परिणाम

शर्त	परिणाम
μ≥4, λ<μ	NS NP-पूर्ण है
गैर-शून्य मूल्यांकन	CIS* P है
गैर-नकारात्मक मूल्यांकन	CIS* P है

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

अस्तित्व द्विभाजन: व्यवहार्य स्थिरता अवधारणाएं और मानक स्थिरता अवधारणाएं अस्तित्व में मौलिक अंतर दिखाती हैं
जटिलता सीढ़ी: CIS की बहुपद सॉल्वेबिलिटी से NS की NP-पूर्णता तक, स्पष्ट जटिलता पदानुक्रम प्रस्तुत करता है
बाधा का प्रभाव: निचली सीमा बाधा स्थिरता के अस्तित्व और संगणनीयता को महत्वपूर्ण रूप से प्रभावित करती है

सीमाएं

खुली समस्याएं: λ=2, μ=3 होने पर NS की जटिलता अभी भी अनिर्धारित है
व्यावहारिक अनुप्रयोग: सैद्धांतिक परिणामों और व्यावहारिक अनुप्रयोग परिदृश्यों के बीच पुल को आगे के अनुसंधान की आवश्यकता है
एल्गोरिदम दक्षता: कुछ बहुपद एल्गोरिदम के स्थिरांक कारक बड़े हो सकते हैं

भविष्य की दिशाएं

अन्य खेल प्रकार: भिन्नात्मक हेडोनिक खेलों आदि अन्य मॉडलों तक विस्तार
सन्निकटन एल्गोरिदम: NP-कठिन परिस्थितियों के लिए सन्निकटन एल्गोरिदम डिजाइन करना
ऑनलाइन एल्गोरिदम: गतिशील वातावरण में गठबंधन निर्माण पर विचार करना

गहन मूल्यांकन

शक्तियां

सैद्धांतिक पूर्णता: बाधित गठबंधन हेडोनिक खेल स्थिरता के लिए व्यवस्थित सैद्धांतिक ढांचा प्रदान करता है
तकनीकी नवाचार:
- चतुर कमी निर्माण (जैसे X3C से CNS तक की कमी)
- नवीन एल्गोरिदम डिजाइन (दो-चरण CIS* एल्गोरिदम)
- त्रुटि सुधार (Aziz et al. एल्गोरिदम का सुधार)
परिणाम गहराई: न केवल अस्तित्व देता है, बल्कि रचनात्मक एल्गोरिदम भी प्रदान करता है
लेखन स्पष्टता: अवधारणा परिभाषाएं स्पष्ट हैं, प्रमाण संरचना संपूर्ण है

कमियां

प्रायोगिक सत्यापन की कमी: शुद्ध सैद्धांतिक कार्य, वास्तविक डेटा पर सत्यापन की कमी
सीमित अनुप्रयोग मार्गदर्शन: व्यावहारिक अनुप्रयोग परिदृश्यों के लिए मार्गदर्शन का अर्थ आगे की खोज की आवश्यकता है
कुछ प्रमाण लंबे: कुछ NP-पूर्णता प्रमाण जटिल हैं, पठनीयता में सुधार की आवश्यकता है

प्रभाव

शैक्षणिक मूल्य: बाधित गठबंधन खेल सिद्धांत के लिए महत्वपूर्ण सैद्धांतिक आधार प्रदान करता है
व्यावहारिक मूल्य: वास्तविक गठबंधन निर्माण समस्याओं के लिए एल्गोरिदम उपकरण प्रदान करता है
पुनरुत्पादनीयता: एल्गोरिदम विवरण स्पष्ट हैं, कार्यान्वयन और सत्यापन में आसान

लागू परिदृश्य

शिक्षा क्षेत्र: छात्र समूहीकरण, पाठ्यक्रम व्यवस्था
संगठनात्मक प्रबंधन: टीम गठन, संसाधन आवंटन
सामाजिक चयन: मतदान गठबंधन, हित समूह निर्माण
कंप्यूटर विज्ञान: वितरित प्रणालियों में नोड क्लस्टरिंग

संदर्भ

Bogomolnaia, A., & Jackson, M. O. (2002). The stability of hedonic coalition structures. Games and Economic Behavior, 38(2), 201-230.
Aziz, H., Brandt, F., & Seedig, H. G. (2013). Computing desirable partitions in additively separable hedonic games. Artificial Intelligence, 195, 316-334.
Sung, S. C., & Dimitrov, D. (2010). Computational complexity in additive hedonic games. European Journal of Operational Research, 203(3), 635-639.
Levinger, C., Hazon, N., Simola, S., & Azaria, A. (2024). Coalition formation with bounded coalition size. In Proceedings of AAMAS 2024.

समग्र मूल्यांकन: यह सैद्धांतिक कंप्यूटर विज्ञान का एक उच्च गुणवत्ता वाला पेपर है, जो बाधित गठबंधन खेल सिद्धांत में महत्वपूर्ण योगदान देता है। पेपर की सैद्धांतिक गहराई और तकनीकी नवाचार दोनों ही बहुत उत्कृष्ट हैं, इस क्षेत्र के आगामी अनुसंधान के लिए एक दृढ़ आधार प्रदान करते हैं। यद्यपि प्रायोगिक सत्यापन की कमी है, लेकिन इसके सैद्धांतिक प्रकृति को देखते हुए, यह सीमा समझदारी से भरी है। यह कार्य खेल सिद्धांत, एल्गोरिदम डिजाइन और बहु-एजेंट प्रणालियों सहित कई क्षेत्रों के लिए महत्वपूर्ण शैक्षणिक मूल्य रखता है।