2025-11-16T13:10:12.550115

Online MMS Allocation for Chores

Song, Tao, Wang et al.

We study the problem of fair division of indivisible chores among $n$ agents in an online setting, where items arrive sequentially and must be allocated irrevocably upon arrival. The goal is to produce an $Î±$-MMS allocation at the end. Several recent works have investigated this model, but have only succeeded in obtaining non-trivial algorithms under restrictive assumptions, such as the two-agent bi-valued special case (Wang and Wei, 2025), or by assuming knowledge of the total disutility of each agent (Zhou, Bai, and Wu, 2023). For the general case, the trivial $n$-MMS guarantee remains the best known, while the strongest lower bound is still only $2$. We close this gap on the negative side by proving that for any fixed $n$ and $\varepsilon$, no algorithm can guarantee an $(n - \varepsilon)$-MMS allocation. Notably, this lower bound holds precisely for every $n$, without hiding constants in big-$O$ notation, thereby exactly matching the trivial upper bound. Despite this strong impossibility result, we also present positive results. We provide an online algorithm that applies in the general case, guaranteeing a $\min\{n, O(k), O(\log D)\}$-MMS allocation, where $k$ is the maximum number of distinct disutilities across all agents and $D$ is the maximum ratio between the largest and smallest disutilities for any agent. This bound is reasonable across a broad range of scenarios and, for example, implies that we can achieve an $O(1)$-MMS allocation whenever $k$ is constant. Moreover, to optimize the constant in the important personalized bi-valued case, we show that if each agent has at most two distinct disutilities, our algorithm guarantees a $(2 + \sqrt{3}) \approx 3.7$-MMS allocation.

academic

ऑनलाइन MMS आवंटन घरेलू कामों के लिए

मूल जानकारी

पेपर ID: 2507.14039
शीर्षक: Online MMS Allocation for Chores
लेखक: Jiaxin Song (University of Illinois Urbana-Champaign), Biaoshuai Tao (Shanghai Jiao Tong University), Wenqian Wang (Shanghai Jiao Tong University), Yuhao Zhang (Shanghai Jiao Tong University)
वर्गीकरण: cs.GT (कंप्यूटर विज्ञान - गेम थ्योरी)
प्रकाशन तिथि: 25 अक्टूबर 2025 (arXiv v2)
पेपर लिंक: https://arxiv.org/abs/2507.14039

सारांश

यह पेपर ऑनलाइन वातावरण में n एजेंटों के बीच अविभाज्य घरेलू कामों (chores) के न्यायसंगत वितरण की समस्या का अध्ययन करता है। इस सेटअप में, वस्तुएं क्रमिक रूप से आती हैं और आने पर तुरंत किसी एजेंट को अपरिवर्तनीय रूप से आवंटित की जानी चाहिए, जिसका लक्ष्य अंततः α-MMS आवंटन प्राप्त करना है। हालांकि हाल के कार्य प्रतिबंधात्मक मान्यताओं के तहत प्रगति कर रहे हैं, सामान्य स्थिति के लिए, ज्ञात सर्वोत्तम गारंटी अभी भी तुच्छ n-MMS है, जबकि सबसे मजबूत निचली सीमा केवल 2 है। यह पेपर यह साबित करके नकारात्मक परिणामों में अंतर को बंद करता है कि किसी भी निश्चित n और ε के लिए, कोई भी एल्गोरिदम (n-ε)-MMS आवंटन की गारंटी नहीं दे सकता है। साथ ही, यह पेपर एक ऑनलाइन एल्गोरिदम प्रस्तुत करता है जो min{n, O(k), O(log D)}-MMS आवंटन की गारंटी देता है, जहां k सभी एजेंटों में विभिन्न नकारात्मक उपयोगिता मानों की अधिकतम संख्या है, और D किसी भी एजेंट की अधिकतम और न्यूनतम नकारात्मक उपयोगिता के बीच का अधिकतम अनुपात है।

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

1. समस्या की परिभाषा

यह पेपर अविभाज्य घरेलू कामों (chores) के ऑनलाइन न्यायसंगत वितरण की समस्या का अध्ययन करता है। पारंपरिक वस्तुओं (goods) के वितरण के विपरीत, घरेलू कामों की नकारात्मक उपयोगिता होती है, और एजेंट यथासंभव कम कामों को संभालना चाहते हैं। ऑनलाइन सेटअप में, घरेलू कामें क्रमिक रूप से आती हैं, और एल्गोरिदम को प्रत्येक काम के आने पर तुरंत उसे किसी एजेंट को आवंटित करना चाहिए, और आवंटन निर्णय अपरिवर्तनीय है।

2. अनुसंधान का महत्व

यह समस्या वास्तविकता में व्यापक अनुप्रयोग रखती है, जैसे:

ऑनलाइन सेवा प्लेटफॉर्म पर कर्मचारियों को कार्य कार्य आवंटित करना
सिस्टम लोड संतुलन समस्याएं
संसाधन शेड्यूलिंग में न्यायसंगतता की गारंटी

3. मौजूदा विधियों की सीमाएं

मौजूदा अनुसंधान में निम्नलिखित सीमाएं हैं:

केवल बहुत प्रतिबंधात्मक मान्यताओं के तहत गैर-तुच्छ परिणाम (जैसे दो एजेंट दोहरे-मूल्य स्थिति)
प्रत्येक एजेंट की कुल नकारात्मक उपयोगिता को पहले से जानने की आवश्यकता
सामान्य स्थिति के लिए, सर्वोत्तम ज्ञात एल्गोरिदम केवल तुच्छ n-MMS की गारंटी दे सकता है

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

यह पेपर निम्नलिखित का लक्ष्य रखता है:

ऑनलाइन MMS वितरण समस्या की सैद्धांतिक सीमाओं को निर्धारित करना
सामान्य स्थिति के लिए लागू एल्गोरिदम डिजाइन करना
व्यावहारिक पैरामीटर बाधाओं के तहत बेहतर प्रदर्शन गारंटी प्रदान करना

मुख्य योगदान

सैद्धांतिक निचली सीमा का सटीक लक्षण वर्णन: यह साबित करता है कि किसी भी निश्चित n और ε > 0 के लिए, कोई भी एल्गोरिदम (n-ε)-MMS आवंटन की गारंटी नहीं दे सकता है, जो सैद्धांतिक अंतर को पूरी तरह बंद करता है
सार्वभौमिक ऑनलाइन एल्गोरिदम: सामान्य स्थिति के लिए लागू एल्गोरिदम प्रस्तुत करता है जो min{n, O(k), O(log D)}-MMS आवंटन की गारंटी देता है
पैरामीटरीकृत विश्लेषण: जब k (विभिन्न नकारात्मक उपयोगिता मानों की संख्या) स्थिर हो, तो एल्गोरिदम O(1)-MMS गारंटी प्राप्त कर सकता है
अनुकूलित दोहरे-मूल्य स्थिति: व्यक्तिगत दोहरे-मूल्य स्थिति के लिए, (2+√3) ≈ 3.7-MMS की सुधारी गई गारंटी प्रदान करता है
नई विश्लेषण तकनीकें: "Stacking Game" ढांचा पेश करता है, जो समस्या को विशेष अंतर न्यूनीकरण समस्या में परिवर्तित करता है

विधि विवरण

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

इनपुट: n एजेंट, m घरेलू कामें जो क्रमिक रूप से आती हैं
बाधा: प्रत्येक काम j का एजेंट i के लिए व्यक्तिगत नकारात्मक उपयोगिता di(j) है, नकारात्मक उपयोगिता फ़ंक्शन योगात्मक है
आउटपुट: आवंटन A = (A1, ..., An), जहां Ai एजेंट i को आवंटित कामों का समुच्चय है
लक्ष्य: α-MMS आवंटन प्राप्त करना, अर्थात सभी i के लिए, di(Ai) ≤ α · MMSi

मॉडल आर्किटेक्चर

1. सामान्यीकृत राउंड-रॉबिन एल्गोरिदम ढांचा

एल्गोरिदम राउंड-रॉबिन (round-robin) विचार के विस्तार पर आधारित है:

प्रत्येक एजेंट i के प्रत्येक नकारात्मक उपयोगिता प्रकार θ के लिए दबाव पैरामीटर Hθi को बनाए रखता है
दबाव पैरामीटर आदर्श आवंटन के सापेक्ष एजेंट के "अधिभार" को मापता है
लालची रणनीति: नई आने वाली काम को संबंधित प्रकार के सबसे कम दबाव वाले एजेंट को आवंटित करता है

2. मूल्य गोलाई तकनीक

प्रत्येक आने वाली काम की नकारात्मक उपयोगिता को 2 की निकटतम घात तक गोल करता है
विभिन्न नकारात्मक उपयोगिता प्रकारों की संख्या को कम करता है
प्रतिस्पर्धा अनुपात को O(k²) से O(k) में सुधारता है

3. दबाव अपडेट तंत्र

जब काम j आता है:

यदि एजेंट i को काम j (प्रकार θ) प्राप्त होता है, तो Hθi में 1 जोड़ा जाता है
अन्य एजेंटों i' के संबंधित दबाव Hθi' में से 1/(n-1) घटाया जाता है

तकनीकी नवाचार बिंदु

1. Stacking Game अमूर्तता

ऑनलाइन आवंटन समस्या को निरंतर सममित "स्टैकिंग गेम" में अमूर्त करता है:

अंतराल (-1/2, 1/2] पर गैर-घटते फ़ंक्शन f को बनाए रखता है
प्रतिद्वंद्वी कुल माप 1/k के अंतराल संघ को चुनता है
एल्गोरिदम लालची रूप से निचले भागों को ऊपर उठाता है, उच्च भागों को कम करता है
साबित करता है कि प्रतिद्वंद्वी फ़ंक्शन मान को O(k) से अधिक नहीं बना सकता है

2. पुनरावर्ती निर्माण की निचली सीमा प्रमाण

पुनरावर्ती कठिन उदाहरण निर्माण डिजाइन करता है:

T(n', ε) को n' एजेंटों के लिए (n-ε)-MMS तक पहुंचने के लिए आवश्यक राउंड के रूप में परिभाषित करता है
T(n') से T(n'+1) के कठिन उदाहरण का निर्माण करता है
चतुर "सफाई" तंत्र जो पिछले आवंटन को नगण्य बनाता है

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

यह पेपर मुख्य रूप से सैद्धांतिक कार्य है, जिसमें पारंपरिक अर्थ में प्रायोगिक मूल्यांकन नहीं है, बल्कि गणितीय प्रमाण के माध्यम से सैद्धांतिक परिणामों को सत्यापित करता है।

सैद्धांतिक सत्यापन विधि

निर्माणात्मक प्रमाण: कठिन उदाहरणों के निर्माण के माध्यम से निचली सीमा साबित करता है
आगमनात्मक प्रमाण: एल्गोरिदम के प्रदर्शन गारंटी को साबित करने के लिए गणितीय आगमन का उपयोग करता है
द्वैत विश्लेषण: Stacking Game की द्वैत समस्या के माध्यम से एल्गोरिदम प्रदर्शन का विश्लेषण करता है

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

मुख्य सैद्धांतिक परिणाम

1. सटीक असंभवता परिणाम

प्रमेय 5: किसी भी n और ε > 0 के लिए, कोई भी ऑनलाइन एल्गोरिदम (n-ε)-MMS आवंटन की गारंटी नहीं दे सकता है।

यह परिणाम सटीक है, बड़े O संकेतन में कोई छिपा हुआ स्थिरांक नहीं है, और तुच्छ ऊपरी सीमा से पूरी तरह मेल खाता है।

2. सार्वभौमिक एल्गोरिदम प्रदर्शन

प्रमेय 1: एल्गोरिदम 1 min{n, O(k), O(log D)}-MMS आवंटन की गारंटी देता है, जहां:

k सभी एजेंटों में विभिन्न नकारात्मक उपयोगिता मानों की अधिकतम संख्या है
D किसी भी एजेंट की अधिकतम और न्यूनतम नकारात्मक उपयोगिता का अधिकतम अनुपात है

3. दोहरे-मूल्य स्थिति का अनुकूलन

प्रमेय 6: व्यक्तिगत दोहरे-मूल्य स्थिति के लिए, एक एल्गोरिदम min{n, 2+√3}-MMS आवंटन की गारंटी देता है, जहां 2+√3 ≈ 3.7।

तकनीकी विश्लेषण परिणाम

1. Stacking Game की सीमाएं

प्रमेय 3: Stacking Game में, प्रतिद्वंद्वी 2k से अधिक लाभ नहीं प्राप्त कर सकता है।

यह परिणाम एल्गोरिदम विश्लेषण का मूल है, जो सीधे O(k) की प्रतिस्पर्धा अनुपात की ओर ले जाता है।

2. दबाव पैरामीटर का नियंत्रण

Stacking Game विश्लेषण के माध्यम से, यह साबित करता है कि सभी दबाव पैरामीटर Hθi O(k) सीमा के भीतर बनाए रखे जा सकते हैं, जिससे एल्गोरिदम के प्रदर्शन की गारंटी मिलती है।

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

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

सैद्धांतिक सीमाओं का पूर्ण लक्षण वर्णन: यह साबित करता है कि n-MMS ऑनलाइन घरेलू काम वितरण समस्या की सटीक सैद्धांतिक सीमा है
व्यावहारिक एल्गोरिदम डिजाइन: पैरामीटर बाधाओं के तहत अच्छे प्रदर्शन वाले सार्वभौमिक एल्गोरिदम प्रदान करता है
तकनीकी पद्धति योगदान: Stacking Game ढांचा इस तरह की समस्याओं के लिए नई विश्लेषण उपकरण प्रदान करता है

सीमाएं

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

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

स्थिरांक कारक में सुधार: विशेष स्थितियों में प्रतिस्पर्धा अनुपात के स्थिरांक को और अनुकूलित करना
अन्य न्यायसंगतता अवधारणाएं: अन्य न्यायसंगतता अवधारणाओं जैसे ईर्ष्या-मुक्तता तक विस्तार करना
व्यावहारिक अनुप्रयोग: सैद्धांतिक परिणामों को विशिष्ट लोड संतुलन और कार्य शेड्यूलिंग परिदृश्यों में लागू करना

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

शक्तियां

सैद्धांतिक पूर्णता: एक महत्वपूर्ण खुली समस्या को पूरी तरह हल करता है, सटीक सैद्धांतिक सीमाएं प्रदान करता है
तकनीकी नवाचार: Stacking Game अमूर्तता विभिन्न पैरामीटरों के तहत विश्लेषण को सुंदरता से एकीकृत करता है
व्यावहारिक मूल्य: उचित पैरामीटर सीमा के भीतर तुच्छ एल्गोरिदम से काफी बेहतर प्रदर्शन गारंटी प्रदान करता है
विश्लेषण गहराई: पुनरावर्ती निर्माण की निचली सीमा प्रमाण उच्च तकनीकी स्तर प्रदर्शित करता है

कमियां

प्रायोगिक सत्यापन की कमी: शुद्ध सैद्धांतिक कार्य के रूप में, वास्तविक डेटा पर सत्यापन की कमी है
पैरामीटर निर्भरता: एल्गोरिदम प्रदर्शन k और D के मानों पर गंभीरता से निर्भर है
जटिलता विश्लेषण: एल्गोरिदम की समय और स्थान जटिलता का विस्तृत विश्लेषण नहीं है

प्रभाव

सैद्धांतिक योगदान: ऑनलाइन न्यायसंगत वितरण सिद्धांत के लिए महत्वपूर्ण सैद्धांतिक आधार प्रदान करता है
पद्धति मूल्य: Stacking Game तकनीक अन्य संबंधित समस्याओं पर लागू हो सकती है
व्यावहारिक मार्गदर्शन: वास्तविक सिस्टम डिजाइन के लिए सैद्धांतिक मार्गदर्शन प्रदान करता है

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

ऑनलाइन कार्य शेड्यूलिंग: न्यायसंगतता गारंटी की आवश्यकता वाली कार्य आवंटन प्रणालियों के लिए लागू
लोड संतुलन: बहु-सर्वर लोड संतुलन परिदृश्य में लागू किया जा सकता है
संसाधन आवंटन: विभिन्न ऑनलाइन संसाधन आवंटन समस्याओं के लिए लागू

संदर्भ

पेपर संबंधित कार्यों के समृद्ध संदर्भ उद्धृत करता है, जिनमें शामिल हैं:

Budish (2010): MMS अवधारणा का प्रस्ताव
Zhou et al. (2023): ऑनलाइन MMS आवंटन का प्रारंभिक कार्य
Wang and Wei (2025): दो एजेंट दोहरे-मूल्य स्थिति के परिणाम
Garg et al. (2025): ऑफलाइन MMS आवंटन की नवीनतम प्रगति

यह पेपर सैद्धांतिक कंप्यूटर विज्ञान और एल्गोरिदमिक गेम थ्योरी के क्षेत्र में महत्वपूर्ण योगदान देता है, न केवल एक महत्वपूर्ण खुली समस्या को पूरी तरह हल करता है, बल्कि व्यावहारिक एल्गोरिदम डिजाइन और नई विश्लेषण तकनीकें भी प्रदान करता है। हालांकि मुख्य रूप से सैद्धांतिक कार्य है, लेकिन इसके परिणाम व्यावहारिक अनुप्रयोगों के लिए महत्वपूर्ण मार्गदर्शन मूल्य रखते हैं।