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

সংযোজনীয়ভাবে বিভাজনযোগ্য হেডোনিক গেমে একক-বিচ্যুতি স্থিতিশীলতা সীমাবদ্ধ জোট আকারের সাথে

মৌলিক তথ্য

পেপার আইডি: 2510.12641
শিরোনাম: Single-Deviation Stability in Additively Separable Hedonic Games with Constrained Coalition Sizes
লেখক: মার্টিন বুলিঞ্জার (ব্রিস্টল বিশ্ববিদ্যালয়), অ্যাডাম ডুনাজস্কি (এডিনবার্গ বিশ্ববিদ্যালয়), এডিথ এলকিন্ড (নর্থওয়েস্টার্ন বিশ্ববিদ্যালয়), মাতান গিলবোয়া (অক্সফোর্ড বিশ্ববিদ্যালয়)
শ্রেণীবিভাগ: cs.GT (গেম তত্ত্ব), cs.DS (ডেটা কাঠামো এবং অ্যালগরিদম)
প্রকাশনা তারিখ: ২০২৫ সালের ১৪ অক্টোবর (arXiv প্রাক-প্রিন্ট)
পেপার লিঙ্ক: https://arxiv.org/abs/2510.12641

সারসংক্ষেপ

এই পেপারটি জোট আকারের উপর নির্ধারিত সীমাবদ্ধতা সহ সংযোজনীয়ভাবে বিভাজনযোগ্য হেডোনিক গেম (ASHG) এ স্থিতিশীলতার সমস্যা অধ্যয়ন করে। লেখকরা একক এজেন্ট বিচ্যুতির উপর ভিত্তি করে চারটি ধ্রুপদী স্থিতিশীলতা ধারণা বিবেচনা করেছেন: ন্যাশ স্থিতিশীলতা (Nash stability), ব্যক্তিগত স্থিতিশীলতা (individual stability), চুক্তিবদ্ধ ন্যাশ স্থিতিশীলতা (contractual Nash stability) এবং চুক্তিবদ্ধ ব্যক্তিগত স্থিতিশীলতা (contractual individual stability)। প্রতিটি স্থিতিশীলতা ধারণার জন্য, লেখকরা দুটি রূপান্তর বিবেচনা করেছেন: একটি যা বিচ্যুতিকারীদের দ্বারা পরিত্যক্ত জোটকে বৈধ আকার বজায় রাখতে প্রয়োজন করে, এবং অন্যটি এই সীমাবদ্ধতা ছাড়াই। পেপারটি প্রদত্ত আকার পরামিতির অধীনে স্থিতিশীল ফলাফলের অস্তিত্ব সম্পর্কে একটি সম্পূর্ণ চিত্র প্রদান করে এবং শুধুমাত্র উপরের সীমাবদ্ধতা থাকলে প্রাসঙ্গিক অস্তিত্ব সমস্যার গণনামূলক জটিলতা সম্পূর্ণভাবে চিহ্নিত করে।

গবেষণা পটভূমি এবং প্রেরণা

সমস্যার গুরুত্ব

জোট গঠন বহু-এজেন্ট সিস্টেমে একটি মূল সমস্যা, যা ব্যাপকভাবে প্রয়োগ করা হয়:

শিক্ষার্থী গ্রুপ প্রকল্পে দলের বিভাজন
বিভাগীয় অফিসে আসন বরাদ্দ
বহিরঙ্গন কার্যক্রমে গ্রুপ সংগঠন
সম্মেলন সন্ধ্যায় আসন ব্যবস্থা

এই সমস্ত বাস্তব পরিস্থিতিতে সাধারণ বৈশিষ্ট্য রয়েছে: জোট আকারের উপরে এবং নিচের সীমাবদ্ধতা পূরণ করতে হবে, এবং বিভাজন স্কিমগুলি এজেন্টদের বিচ্যুতি আচরণের প্রতি স্থিতিশীল থাকতে হবে।

বিদ্যমান গবেষণার সীমাবদ্ধতা

১. নিম্ন সীমাবদ্ধতা বিবেচনার অভাব: পূর্ববর্তী কাজ প্রধানত উপরের সীমাবদ্ধতার উপর দৃষ্টি নিবদ্ধ করেছে, নিম্ন সীমাবদ্ধতার গবেষণা অপর্যাপ্ত ২. স্থিতিশীলতা ধারণা অসম্পূর্ণ: সীমাবদ্ধ শর্তে বিভিন্ন স্থিতিশীলতা ধারণার পদ্ধতিগত বিশ্লেষণের অভাব ३. গণনামূলক জটিলতা অস্পষ্ট: সীমাবদ্ধ শর্তে বিভিন্ন স্থিতিশীলতা ধারণার গণনামূলক জটিলতা সম্পূর্ণভাবে চিহ্নিত করা হয়নি

গবেষণা প্রেরণা

এই পেপারটি এই গবেষণা ফাঁক পূরণ করার লক্ষ্য রাখে, জোট আকার সীমাবদ্ধতার অধীনে হেডোনিক গেম স্থিতিশীলতার একটি সম্পূর্ণ তাত্ত্বিক কাঠামো প্রদান করে।

মূল অবদান

१. সম্পূর্ণ অস্তিত্ব চিহ্নিতকরণ: সমস্ত বিবেচিত স্থিতিশীলতা ধারণার জন্য প্রদত্ত আকার পরামিতির অধীনে সম্পূর্ণ অস্তিত্ব চিত্র প্রদান করে २. গণনামূলক জটিলতার সম্পূর্ণ বিশ্লেষণ: শুধুমাত্র উপরের সীমাবদ্ধতা (λ=1) থাকলে, সমস্ত স্থিতিশীলতা ধারণার গণনামূলক জটিলতা সম্পূর্ণভাবে চিহ্নিত করে ३. বহুপদী সময় অ্যালগরিদম:

চুক্তিবদ্ধ ব্যক্তিগত স্থিতিশীলতার (CIS) জন্য বহুপদী সময় অ্যালগরিদম প্রদান করে
উপরের সীমা ২ হলে চুক্তিবদ্ধ ন্যাশ স্থিতিশীলতার (CNS) জন্য বহুপদী সময় অ্যালগরিদম প্রদান করে
নিম্ন সীমা কমপক্ষে ২ হলে CIS* এর জন্য বহুপদী সময় অ্যালগরিদম প্রদান করে ४. NP-সম্পূর্ণতা ফলাফল: একাধিক ক্ষেত্রে স্থিতিশীলতা সিদ্ধান্ত সমস্যার NP-সম্পূর্ণতা প্রমাণ করে ५. অ্যালগরিদম সংশোধন: আজিজ এবং অন্যদের (২০१३) অ্যালগরিদমে ত্রুটি সংশোধন করে

পদ্ধতি বিস্তারিত

কাজের সংজ্ঞা

ইনপুট:

এজেন্ট সেট N
সংযোজনীয় বিভাজনযোগ্য উপযোগিতা ফাংশন v = (va)a∈N, যেখানে va: N{a} → ℝ
জোট আকার সীমাবদ্ধতা λ ≤ μ (λ নিম্ন সীমা, μ উপরের সীমা)

আউটপুট:

(λ,μ)-partition: আকার সীমাবদ্ধতা সন্তুষ্ট করে এমন জোট বিভাজন
স্থিতিশীলতা সিদ্ধান্ত: এই বিভাজন নির্দিষ্ট স্থিতিশীলতা ধারণা পূরণ করে কিনা

সীমাবদ্ধতা:

প্রতিটি জোট C সন্তুষ্ট করে λ ≤ |C| ≤ μ
বিচ্যুতি অবশ্যই (λ,μ)-permissible বা (λ,μ)-feasible হতে হবে

স্থিতিশীলতা ধারণা কাঠামো

মৌলিক সংজ্ঞা

জোট C তে এজেন্ট a এর উপযোগিতার জন্য: $u_a(C) = \sum_{b \in C\setminus\{a\}} v_a(b)$

চারটি মান স্থিতিশীলতা ধারণা

१. ন্যাশ স্থিতিশীলতা (NS): কোনো এজেন্ট বিচ্যুতির মাধ্যমে নিজের উপযোগিতা উন্নত করতে পারে না २. ব্যক্তিগত স্থিতিশীলতা (IS): ন্যাশ বিচ্যুতি + লক্ষ্য জোট সদস্যদের সম্মতি ३. চুক্তিবদ্ধ ন্যাশ স্থিতিশীলতা (CNS): ন্যাশ বিচ্যুতি + মূল জোট সদস্যদের সম্মতি ४. চুক্তিবদ্ধ ব্যক্তিগত স্থিতিশীলতা (CIS): IS এবং CNS উভয় শর্ত সন্তুষ্ট করে

সম্ভাব্যতা রূপান্তর

প্রতিটি মান ধারণার সংশ্লিষ্ট সম্ভাব্যতা রূপান্তর রয়েছে (চিহ্নিত *), যা বিচ্যুতির পরে মূল জোটকে আকার সীমাবদ্ধতা পূরণ করতে প্রয়োজন করে।

মূল অ্যালগরিদম

অ্যালগরিদম १: CIS অ্যালগরিদম (সংশোধিত সংস্করণ)

ইনপুট: ASHG (N,v), পরামিতি μ
আউটপুট: (1,μ)-partition

१. আরম্ভ: i←0, A←N
२. যখন A ≠ ∅:
३.   এজেন্ট a ∈ A নির্বাচন করুন
४.   নতুন জোট তৈরির উপযোগিতা h গণনা করুন
५.   k ∈ [i] এর জন্য:  // বিদ্যমান জোটে যোগদান বিবেচনা করুন
६.     জোট k তে যোগদানের উপযোগিতা h' গণনা করুন
७.     যদি h < h': সর্বোত্তম পছন্দ আপডেট করুন
८.   সর্বোত্তম পছন্দ অনুযায়ী জোট তৈরি/যোগদান করুন
९.   উপলব্ধ এজেন্ট সেট A আপডেট করুন

অ্যালগরিদম ३: CIS* অ্যালগরিদম (অ-শূন্য মূল্যায়ন)

নিম্ন সীমা λ≥२ এর ক্ষেত্রে, দুই-পর্যায়ের পদ্ধতির মাধ্যমে: १. পর্যায় I: প্রতিটি নেতার জন্য সর্বোত্তম ন্যূনতম আকারের জোট গঠন করুন २. পর্যায় II: বিপরীত ক্রমে অবশিষ্ট এজেন্ট পূরণ করুন

পরীক্ষামূলক সেটআপ

তাত্ত্বিক বিশ্লেষণ কাঠামো

এই পেপারটি প্রধানত তাত্ত্বিক বিশ্লেষণ পরিচালনা করে, যার মধ্যে রয়েছে: १. অস্তিত্ব প্রমাণ: গঠনমূলক প্রমাণ এবং পাল্টা উদাহরণ २. জটিলতা বিশ্লেষণ: হ্রাস প্রমাণ এবং অ্যালগরিদম ডিজাইন ३. অ্যালগরিদম সঠিকতা: আনুষ্ঠানিক যাচাইকরণ

জটিলতা বিশ্লেষণ পদ্ধতি

NP-সম্পূর্ণতা প্রমাণ: ३-SAT, X३C ইত্যাদি ধ্রুপদী সমস্যা থেকে হ্রাস
বহুপদী অ্যালগরিদম: গঠনমূলক অ্যালগরিদম ডিজাইন
নিম্ন সীমা বিশ্লেষণ: পাল্টা উদাহরণের মাধ্যমে অ-অস্তিত্ব প্রমাণ

পরীক্ষামূলক ফলাফল

অস্তিত্ব ফলাফল

স্থিতিশীলতা ধারণা	সমরূপ মূল্যায়ন	সাধারণ মূল্যায়ন	সরল সমরূপ মূল্যায়ন
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-সম্পূর্ণতা প্রমাণ করা হয়েছে

নিম্ন সীমা λ≥२ এর ফলাফল

শর্ত	ফলাফল
μ≥4, λ<μ	NS হল NP-সম্পূর্ণ
অ-শূন্য মূল্যায়ন	CIS* হল P
অ-নেতিবাচক মূল্যায়ন	CIS* হল P

উপসংহার এবং আলোচনা

প্রধান উপসংহার

१. অস্তিত্ব দ্বিভাজন: সম্ভাব্য স্থিতিশীলতা ধারণা এবং মান স্থিতিশীলতা ধারণার মধ্যে অস্তিত্বে মৌলিক পার্থক্য রয়েছে २. জটিলতা সিঁড়ি: CIS এর বহুপদী সমাধানযোগ্যতা থেকে NS এর NP-সম্পূর্ণতা পর্যন্ত, স্পষ্ট জটিলতা স্তর উপস্থাপন করে ३. সীমাবদ্ধতার প্রভাব: নিম্ন সীমাবদ্ধতা স্থিতিশীলতার অস্তিত্ব এবং গণনাযোগ্যতাকে উল্লেখযোগ্যভাবে প্রভাবিত করে

সীমাবদ্ধতা

१. খোলা প্রশ্ন: λ=२, μ=३ হলে NS এর জটিলতা এখনও অনির্ধারিত २. ব্যবহারিক প্রয়োগ: তাত্ত্বিক ফলাফল এবং বাস্তব প্রয়োগ পরিস্থিতির মধ্যে সেতু নির্মাণের প্রয়োজন আরও গবেষণা ३. অ্যালগরিদম দক্ষতা: কিছু বহুপদী অ্যালগরিদমের ধ্রুবক ফ্যাক্টর বড় হতে পারে

ভবিষ্যত দিকনির্দেশনা

१. অন্যান্য গেম প্রকার: ভগ্নাংশ হেডোনিক গেম ইত্যাদি অন্যান্য মডেলে সম্প্রসারণ २. আনুমানিক অ্যালগরিদম: NP-কঠিন ক্ষেত্রের জন্য আনুমানিক অ্যালগরিদম ডিজাইন করুন ३. অনলাইন অ্যালগরিদম: গতিশীল পরিবেশে জোট গঠন বিবেচনা করুন

গভীর মূল্যায়ন

শক্তি

१. তাত্ত্বিক সম্পূর্ণতা: সীমাবদ্ধ জোট হেডোনিক গেম স্থিতিশীলতার পদ্ধতিগত তাত্ত্বিক কাঠামো প্রদান করে २. প্রযুক্তিগত উদ্ভাবন:

চতুর হ্রাস নির্মাণ (যেমন X३C থেকে CNS এ হ্রাস)
উদ্ভাবনী অ্যালগরিদম ডিজাইন (দুই-পর্যায়ের CIS* অ্যালগরিদম)
ত্রুটি সংশোধন (আজিজ এবং অন্যদের অ্যালগরিদমের সংশোধন) ३. ফলাফল গভীরতা: শুধুমাত্র অস্তিত্ব নয়, গঠনমূলক অ্যালগরিদমও প্রদান করে ४. লেখার স্পষ্টতা: ধারণা সংজ্ঞা স্পষ্ট, প্রমাণ কাঠামো সম্পূর্ণ

অসুবিধা

१. পরীক্ষামূলক যাচাইকরণের অভাব: খাঁটি তাত্ত্বিক কাজ, বাস্তব ডেটায় যাচাইকরণের অভাব २. প্রয়োগ নির্দেশনা সীমিত: বাস্তব প্রয়োগ পরিস্থিতিতে নির্দেশনার অর্থ আরও খনন করা প্রয়োজন ३. কিছু প্রমাণ দীর্ঘ: কিছু NP-সম্পূর্ণতা প্রমাণ জটিল, পাঠযোগ্যতা উন্নতির জন্য অপেক্ষা করছে

প্রভাব

१. একাডেমিক মূল্য: সীমাবদ্ধ জোট গেম তত্ত্বের জন্য গুরুত্বপূর্ণ তাত্ত্বিক ভিত্তি প্রদান করে २. ব্যবহারিক মূল্য: বাস্তব জোট গঠন সমস্যার জন্য অ্যালগরিদম সরঞ্জাম প্রদান করে ३. পুনরুৎপাদনযোগ্যতা: অ্যালগরিদম বর্ণনা স্পষ্ট, বাস্তবায়ন এবং যাচাইকরণ সহজ

প্রযোজ্য পরিস্থিতি

१. শিক্ষা ক্ষেত্র: শিক্ষার্থী গ্রুপিং, কোর্স সময়সূচী २. সংস্থা ব্যবস্থাপনা: দল গঠন, সম্পদ বরাদ্দ ३. সামাজিক পছন্দ: ভোটিং জোট, স্বার্থ গোষ্ঠী গঠন ४. কম্পিউটার বিজ্ঞান: বিতরণকৃত সিস্টেমে নোড ক্লাস্টারিং

সংদর্ভ

१. Bogomolnaia, A., & Jackson, M. O. (२००२). The stability of hedonic coalition structures. Games and Economic Behavior, 38(2), 201-230.

२. Aziz, H., Brandt, F., & Seedig, H. G. (२०१३). Computing desirable partitions in additively separable hedonic games. Artificial Intelligence, 195, 316-334.

३. Sung, S. C., & Dimitrov, D. (२०१०). Computational complexity in additive hedonic games. European Journal of Operational Research, 203(3), 635-639.

४. Levinger, C., Hazon, N., Simola, S., & Azaria, A. (२०२४). Coalition formation with bounded coalition size. In Proceedings of AAMAS 2024.

সামগ্রিক মূল্যায়ন: এটি তাত্ত্বিক কম্পিউটার বিজ্ঞানের একটি উচ্চ-মানের পেপার, যা সীমাবদ্ধ জোট গেম তত্ত্বে গুরুত্বপূর্ণ অবদান রাখে। পেপারটির তাত্ত্বিক গভীরতা এবং প্রযুক্তিগত উদ্ভাবন উভয়ই অসাধারণ, এই ক্ষেত্রে পরবর্তী গবেষণার জন্য একটি দৃঢ় ভিত্তি স্থাপন করে। যদিও পরীক্ষামূলক যাচাইকরণের অভাব রয়েছে, তার তাত্ত্বিক প্রকৃতি বিবেচনা করে এই সীমাবদ্ধতা বোধগম্য। এই কাজটি গেম তত্ত্ব, অ্যালগরিদম ডিজাইন এবং বহু-এজেন্ট সিস্টেম সহ একাধিক ক্ষেত্রের জন্য গুরুত্বপূর্ণ একাডেমিক মূল্য রাখে।