2025-11-12T03:19:33.205062

EFX Allocations and Orientations on Bipartite Multi-graphs: A Complete Picture

Afshinmehr, Danaei, Kazemi et al.
We consider the fundamental problem of fairly allocating a set of indivisible items among agents having valuations that are represented by a multi-graph -- here, agents appear as vertices and items as edges between them and each vertex (agent) only values the set of its incident edges (items). The goal is to find a fair, i.e., envy-free up to any item (EFX) allocation. This model has recently been introduced by Christodoulou et al. (EC-23) where they show that EFX allocations always exist on simple graphs for monotone valuations, i.e., where any two agents can share at most one edge (item). A natural question arises as to what happens when we go beyond simple graphs and study various classes of multi-graphs? We answer the above question affirmatively for the valuation class of bipartite multi-graphs and multi-cycles. The main contribution of this work is to establish the existence of EFX allocations on bipartite multi-graphs for monotone valuations and on multi-cycles for MMS-feasible valuations. We also present pseudo-polynomial time algorithms to compute EFX allocations for the above settings. Furthermore, we show that for bipartite multi-graphs with cancelable valuations, EFX allocations can be computed in polynomial time. We thus widen the spectrum where EFX allocations are guaranteed to exist. Next, we study EFX orientations (allocations where every item is assigned to one of its two endpoint agents) and provide a complete characterization of their existence on bipartite multi-graphs in terms of two key parameters: (i) the number of edges shared between any two agents and (ii) the diameter of the graph. Finally, we prove that it is NP-complete to determine whether a given fair division instance on a bipartite multi-graph admits an EFX orientation, even with a constant number of agents.
academic

EFX आवंटन और द्विपक्षीय बहु-ग्राफ पर अभिविन्यास: एक संपूर्ण चित्र

मूल जानकारी

  • पेपर ID: 2410.17002
  • शीर्षक: EFX Allocations and Orientations on Bipartite Multi-graphs: A Complete Picture
  • लेखक: Mahyar Afshinmehr, Alireza Danaei, Mehrafarin Kazemi, Kurt Mehlhorn, Nidhi Rathi
  • वर्गीकरण: cs.GT (खेल सिद्धांत), cs.DS (डेटा संरचना और एल्गोरिदम)
  • प्रकाशन समय: अक्टूबर 2024 (arXiv प्रीप्रिंट)
  • पेपर लिंक: https://arxiv.org/abs/2410.17002

सारांश

यह पेपर बहु-ग्राफ द्वारा प्रतिनिधित्व किए गए मूल्यांकन कार्यों के तहत अविभाज्य वस्तुओं के न्यायसंगत आवंटन की समस्या का अध्ययन करता है। इस मॉडल में, एजेंट ग्राफ के शीर्षों के अनुरूप हैं, वस्तुएं किनारों के अनुरूप हैं, और प्रत्येक एजेंट केवल अपने संबंधित किनारों के लिए सकारात्मक मूल्यांकन रखता है। लक्ष्य एक न्यायसंगत आवंटन खोजना है, अर्थात् EFX (envy-free up to any item) शर्त को संतुष्ट करने वाला आवंटन। पेपर Christodoulou et al. (2023) के कार्य पर आधारित है, जिन्होंने साधारण ग्राफ पर एकरस मूल्यांकन कार्यों के लिए EFX आवंटन के अस्तित्व को साबित किया। यह पेपर अनुसंधान को बहु-ग्राफ की विभिन्न श्रेणियों तक विस्तारित करता है, मुख्य योगदान में शामिल हैं: (1) द्विपक्षीय बहु-ग्राफ पर एकरस मूल्यांकन और बहु-चक्र पर MMS-feasible मूल्यांकन के लिए EFX आवंटन के अस्तित्व को साबित करना; (2) संबंधित छद्म-बहुपद समय एल्गोरिदम प्रदान करना; (3) EFX अभिविन्यास समस्या के लिए संपूर्ण लक्षण वर्णन देना; (4) EFX अभिविन्यास के अस्तित्व को निर्धारित करने की NP-पूर्णता को साबित करना।

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

समस्या की पृष्ठभूमि

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

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

  1. सैद्धांतिक चुनौती: चार या अधिक एजेंटों के लिए, EFX आवंटन का अस्तित्व अभी भी एक प्रमुख खुली समस्या है
  2. मॉडल विस्तार: Christodoulou et al. ने साधारण ग्राफ पर EFX आवंटन के अस्तित्व को साबित किया, स्वाभाविक प्रश्न यह है कि बहु-ग्राफ के मामले में क्या होता है
  3. व्यावहारिक अनुप्रयोग: यह मॉडल भौगोलिक वातावरण में एजेंटों के लिए लागू होता है जो केवल पास के संसाधनों की परवाह करते हैं, जैसे व्यापार गलियारे, प्राकृतिक गैस पाइपलाइन आदि

मौजूदा दृष्टिकोण की सीमाएं

  • मौजूदा परिणाम मुख्य रूप से साधारण ग्राफ तक सीमित हैं (किसी भी दो एजेंटों के बीच अधिकतम एक वस्तु साझा)
  • बहु-ग्राफ (दो एजेंट कई वस्तुओं को साझा कर सकते हैं) के मामले में व्यवस्थित अनुसंधान की कमी है
  • EFX अभिविन्यास के अस्तित्व और कम्प्यूटेशनल जटिलता को अभी तक पूरी तरह से चिह्नित नहीं किया गया है

मुख्य योगदान

  1. अस्तित्व प्रमेय: द्विपक्षीय बहु-ग्राफ पर एकरस मूल्यांकन कार्यों के लिए EFX आवंटन हमेशा मौजूद होता है, बहु-चक्र पर MMS-feasible मूल्यांकन के लिए EFX आवंटन हमेशा मौजूद होता है
  2. एल्गोरिदम डिजाइन: EFX आवंटन की गणना के लिए छद्म-बहुपद समय एल्गोरिदम प्रदान करता है, कम्प्यूटेबल मूल्यांकन कार्यों के लिए बहुपद समय में गणना की जा सकती है
  3. संपूर्ण लक्षण वर्णन: दो मुख्य पैरामीटर (q और d(G)) के आधार पर द्विपक्षीय बहु-ग्राफ पर EFX अभिविन्यास के अस्तित्व का संपूर्ण लक्षण वर्णन देता है
  4. जटिलता विश्लेषण: EFX अभिविन्यास के अस्तित्व को निर्धारित करने की समस्या की NP-पूर्णता को साबित करता है, यहां तक कि स्थिर संख्या में एजेंटों के लिए भी
  5. सन्निकटन परिणाम: उन मामलों के लिए जहां EFX अभिविन्यास मौजूद नहीं है, साबित करता है कि कम से कम ⌈n/2⌉ एजेंट EFX को संतुष्ट करते हैं और शेष एजेंट 1/2-EFX को संतुष्ट करते हैं

विधि विवरण

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

इनपुट:

  • बहु-ग्राफ G = (V,E), जहां V = n n एजेंटों को दर्शाता है, E m वस्तुओं को दर्शाता है
  • मूल्यांकन कार्य {vi}i∈n, जो vi(S) = vi(S ∩ E(i)) को संतुष्ट करते हैं, जहां E(i) एजेंट i के संबंधित किनारों का समूह है

आउटपुट:

  • संपूर्ण आवंटन X = (X1,...,Xn), जो EFX शर्त को संतुष्ट करता है
  • या EFX अभिविन्यास (प्रत्येक वस्तु को इसके अंतिम बिंदु एजेंटों में से एक को आवंटित किया जाता है)

बाधाएं:

  • EFX: किसी भी एजेंट i,j और वस्तु g ∈ Xj के लिए, vi(Xi) ≥ vi(Xj \ {g})
  • मूल्यांकन कार्य प्रकार: एकरस, कम्प्यूटेबल, MMS-feasible आदि

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

मुख्य अवधारणाएं

  1. T-cut कॉन्फ़िगरेशन: आसन्न एजेंट i ∈ S और j ∈ T के लिए, एजेंट j को E(i,j) को दो पैकेज C1 और C2 में विभाजित करने दें, जैसे कि दोनों j के लिए EFX-feasible हों
  2. उपलब्ध समूह: एजेंट i के लिए वर्तमान आवंटन X के तहत E(i,j) से उपलब्ध किनारों के समूह को Ai,j(X) के रूप में परिभाषित करें
  3. सुरक्षित समूह: ईर्ष्या करने वाले एजेंट i के लिए, इसके सुरक्षित समूह को Si(X) के रूप में परिभाषित करें

मुख्य गुण

एल्गोरिदम छह मुख्य गुणों को बनाए रखता है:

  1. X एक EFX अभिविन्यास है
  2. E(i,j) में वस्तुएं j-cut कॉन्फ़िगरेशन के अनुसार आवंटित की जाती हैं
  3. प्रत्येक एजेंट को इसका सबसे पसंदीदा उपलब्ध पैकेज मिलता है
  4. गैर-ईर्ष्या करने वाले एजेंटों का उपलब्ध समूह खाली है
  5. गैर-ईर्ष्या करने वाले एजेंटों के अनुसार उनके अनआवंटित संबंधित किनारों का मूल्यांकन वर्तमान पैकेज से अधिक नहीं है
  6. ईर्ष्या करने वाले एजेंटों के ईर्ष्या करने वाले उनके सुरक्षित समूह में हैं

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

1. कॉन्फ़िगरेशन तंत्र डिजाइन

T-cut कॉन्फ़िगरेशन अवधारणा को नवीन रूप से पेश करता है, जो दो-व्यक्ति कट चयन प्रोटोकॉल के विचारों को जोड़ता है, बहु-ग्राफ में कई किनारों को संभालने के लिए एक व्यवस्थित विधि प्रदान करता है।

2. चरणबद्ध एल्गोरिदम ढांचा

पांच एल्गोरिदम डिजाइन किए गए हैं जो क्रमिक रूप से छह मुख्य गुणों को संतुष्ट करते हैं:

  • Algorithm 1: लालची अभिविन्यास गुण (1)-(3) को संतुष्ट करता है
  • Algorithm 2: गैर-ईर्ष्या करने वाले एजेंटों को संभालता है गुण (4) को संतुष्ट करता है
  • Algorithm 3: गैर-ईर्ष्या करने वाले एजेंटों का मूल्यांकन बढ़ाता है गुण (5) को संतुष्ट करता है
  • Algorithm 4: सुरक्षित समूह का निर्माण करता है गुण (6) को संतुष्ट करता है
  • Algorithm 5: शेष वस्तुओं का अंतिम आवंटन करता है

3. द्विपक्षीय ग्राफ संरचना का उपयोग

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

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

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

यह पेपर मुख्य रूप से एक सैद्धांतिक कार्य है, प्रायोगिक सत्यापन के बजाय गणितीय प्रमाण के माध्यम से परिणाम प्रदान करता है। विश्लेषण ढांचे में शामिल हैं:

  1. अस्तित्व प्रमाण: रचनात्मक प्रमाण दिखाता है कि शर्तों को संतुष्ट करने वाला आवंटन कैसे खोजें
  2. एल्गोरिदम जटिलता विश्लेषण: विभिन्न एल्गोरिदम चरणों की समय जटिलता का विश्लेषण करता है
  3. प्रतिउदाहरण निर्माण: विशिष्ट उदाहरणों के माध्यम से साबित करता है कि कुछ मामलों में EFX अभिविन्यास मौजूद नहीं है

मूल्यांकन मेट्रिक्स

  • EFX संतुष्टि: क्या सभी एजेंट EFX शर्त को संतुष्ट करते हैं
  • समय जटिलता: एल्गोरिदम चलने का समय (बहुपद बनाम छद्म-बहुपद)
  • सन्निकटन अनुपात: उन मामलों के लिए जहां सटीक समाधान मौजूद नहीं है, सन्निकटन समाधान की गुणवत्ता

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

मुख्य परिणाम

1. अस्तित्व प्रमेय

प्रमेय 4.11: द्विपक्षीय बहु-ग्राफ पर एकरस मूल्यांकन के लिए, EFX आवंटन हमेशा मौजूद होता है और छद्म-बहुपद समय में गणना की जा सकती है; कम्प्यूटेबल मूल्यांकन के लिए बहुपद समय में गणना की जा सकती है।

प्रमेय 5.1: बहु-चक्र पर MMS-feasible मूल्यांकन के लिए, EFX आवंटन हमेशा मौजूद होता है और छद्म-बहुपद समय में गणना की जा सकती है।

2. EFX अभिविन्यास का संपूर्ण लक्षण वर्णन

पैरामीटर q (किसी भी दो एजेंटों के बीच अधिकतम किनारों की संख्या) और d(G) (ग्राफ व्यास) के आधार पर संपूर्ण लक्षण वर्णन:

पैरामीटर शर्तEFX अभिविन्यास अस्तित्व
चक्र रहित, q=2, d(G)≤4मौजूद है
चक्र रहित, q=2, d(G)>4संभवतः मौजूद नहीं है
चक्र रहित, q>2, d(G)≤2मौजूद है
चक्र रहित, q>2, d(G)>2संभवतः मौजूद नहीं है
चक्र सहित, q≥2, d(G)≥2संभवतः मौजूद नहीं है

3. जटिलता परिणाम

प्रमेय 3.6: यह निर्धारित करना कि क्या द्विपक्षीय बहु-ग्राफ पर EFX अभिविन्यास मौजूद है, NP-पूर्ण है, यहां तक कि स्थिर संख्या में एजेंटों के लिए भी।

4. सन्निकटन परिणाम

प्रमेय 4.12: द्विपक्षीय बहु-ग्राफ पर योगात्मक मूल्यांकन के लिए, हमेशा एक अभिविन्यास मौजूद होता है जैसे कि कम से कम ⌈n/2⌉ एजेंट EFX को संतुष्ट करते हैं, शेष एजेंट 1/2-EFX को संतुष्ट करते हैं।

केस विश्लेषण

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

  • चित्र 7-10 विशिष्ट द्विपक्षीय बहु-ग्राफ पर एल्गोरिदम के चरणबद्ध निष्पादन को दिखाते हैं
  • प्रतिउदाहरण निर्माण (जैसे चित्र 1-5) कुछ मामलों में EFX अभिविन्यास की अनुपस्थिति को साबित करते हैं

सैद्धांतिक निष्कर्ष

  1. द्विपक्षीय संरचना की महत्वपूर्ण भूमिका: द्विपक्षीय ग्राफ संरचना सुनिश्चित करती है कि ईर्ष्या करने वाले शीर्ष केवल एक विभाजन में दिखाई दे सकते हैं, यह एल्गोरिदम की सफलता की कुंजी है
  2. कॉन्फ़िगरेशन तंत्र की प्रभावशीलता: T-cut कॉन्फ़िगरेशन कई किनारों को संभालने के लिए एक एकीकृत ढांचा प्रदान करता है
  3. पैरामीटरीकृत जटिलता: q और d(G) दो पैरामीटर EFX अभिविन्यास के अस्तित्व को पूरी तरह से चिह्नित करते हैं

संबंधित कार्य

EFX अनुसंधान की वर्तमान स्थिति

  • दो एजेंट: Plaut और Roughgarden ने एकरस मूल्यांकन के तहत अस्तित्व को साबित किया
  • तीन एजेंट: विभिन्न मूल्यांकन प्रकारों के तहत अस्तित्व को साबित करने वाले कार्यों की एक श्रृंखला
  • विशेष मूल्यांकन: समान मूल्यांकन, द्विमान मूल्यांकन आदि विशेष मामलों में अस्तित्व

ग्राफ पर न्यायसंगत विभाजन

  • Christodoulou et al. ने पहली बार साधारण ग्राफ पर EFX आवंटन मॉडल प्रस्तावित किया
  • बाद के कार्यों ने EF1 अभिविन्यास, मिश्रित वस्तुएं आदि विस्तार का अध्ययन किया
  • यह पेपर बहु-ग्राफ के मामले का व्यवस्थित रूप से अध्ययन करने वाला पहला कार्य है

समानांतर कार्य

दो स्वतंत्र समानांतर कार्य भी बहु-ग्राफ पर EFX का अध्ययन करते हैं:

  • Sgouritsa और Sotiriou (2025): द्विपक्षीय बहु-ग्राफ पर एकरस मूल्यांकन के लिए EFX अस्तित्व को साबित करता है
  • Bhaskar और Pandit (2024): विशिष्ट बहु-ग्राफ श्रेणियों पर EFX का अध्ययन करता है

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

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

  1. सैद्धांतिक योगदान: द्विपक्षीय बहु-ग्राफ पर EFX आवंटन के अस्तित्व का पहली बार संपूर्ण लक्षण वर्णन देता है, मौजूदा सैद्धांतिक ढांचे को विस्तारित करता है
  2. एल्गोरिदम योगदान: व्यावहारिक छद्म-बहुपद समय एल्गोरिदम प्रदान करता है, विशिष्ट मूल्यांकन प्रकारों के लिए बहुपद समय तक पहुंच सकता है
  3. जटिलता लक्षण वर्णन: EFX अभिविन्यास समस्या की कम्प्यूटेशनल जटिलता का संपूर्ण विश्लेषण करता है

सीमाएं

  1. ग्राफ श्रेणी प्रतिबंध: परिणाम मुख्य रूप से द्विपक्षीय बहु-ग्राफ पर केंद्रित हैं, सामान्य बहु-ग्राफ के लिए अभी भी खुली समस्या है
  2. मूल्यांकन कार्य प्रतिबंध: हालांकि कई मूल्यांकन प्रकारों को शामिल करता है, लेकिन अभी भी सबसे सामान्य मामले तक नहीं पहुंचा है
  3. एल्गोरिदम दक्षता: सामान्य एकरस मूल्यांकन के लिए केवल छद्म-बहुपद समय जटिलता तक पहुंच सकता है

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

  1. सामान्य बहु-ग्राफ: लेखक अनुमान लगाते हैं कि EFX आवंटन किसी भी बहु-ग्राफ पर मौजूद है, लेकिन प्रमाण के लिए अभी भी नई तकनीकों की आवश्यकता है
  2. एल्गोरिदम अनुकूलन: अधिक कुशल एल्गोरिदम खोजना, विशेष रूप से बहुपद समय एल्गोरिदम
  3. सामाजिक कल्याण: EFX आवंटन और दक्षता के बीच व्यापार-बंद संबंध का अध्ययन करना

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

शक्तियां

  1. सैद्धांतिक गहराई: संपूर्ण अस्तित्व प्रमाण और जटिलता विश्लेषण प्रदान करता है, सैद्धांतिक योगदान महत्वपूर्ण है
  2. तकनीकी नवाचार: T-cut कॉन्फ़िगरेशन तंत्र और चरणबद्ध एल्गोरिदम ढांचे में नवाचार है
  3. परिणाम पूर्णता: EFX अभिविन्यास के अस्तित्व का संपूर्ण पैरामीटरीकृत लक्षण वर्णन देता है
  4. लेखन स्पष्टता: पेपर संरचना स्पष्ट है, प्रमाण विस्तृत हैं, समझने और सत्यापित करने में आसान हैं

कमियां

  1. प्रायोगिक सत्यापन की कमी: शुद्ध सैद्धांतिक कार्य के रूप में, वास्तविक डेटा पर एल्गोरिदम प्रदर्शन मूल्यांकन की कमी है
  2. सीमित अनुप्रयोग परिदृश्य: बहु-ग्राफ मॉडल के व्यावहारिक अनुप्रयोग परिदृश्य अपेक्षाकृत सीमित हैं
  3. तकनीकी सीमाएं: सामान्य बहु-ग्राफ तक विस्तार अभी भी तकनीकी चुनौतियों का सामना करता है

प्रभाव

  1. शैक्षणिक मूल्य: न्यायसंगत विभाजन सिद्धांत के लिए महत्वपूर्ण सैद्धांतिक प्रगति प्रदान करता है, EFX अनुसंधान के विकास को आगे बढ़ाता है
  2. पद्धति योगदान: प्रस्तावित तकनीकी ढांचा अन्य ग्राफ पर न्यायसंगत विभाजन समस्याओं के लिए प्रेरणा दे सकता है
  3. खुली समस्याएं: सामान्य बहु-ग्राफ पर EFX अस्तित्व समस्या के लिए महत्वपूर्ण तकनीकी संचय प्रदान करता है

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

  1. सैद्धांतिक अनुसंधान: न्यायसंगत विभाजन सिद्धांत अनुसंधान करने वाले शोधकर्ताओं के लिए महत्वपूर्ण संदर्भ प्रदान करता है
  2. एल्गोरिदम डिजाइन: कॉन्फ़िगरेशन तंत्र अन्य न्यायसंगत विभाजन एल्गोरिदम डिजाइन के लिए उपयोग किया जा सकता है
  3. जटिलता सिद्धांत: NP-पूर्णता परिणाम कम्प्यूटेशनल जटिलता अनुसंधान के लिए मूल्यवान है

संदर्भ

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

  • Christodoulou et al. 2023: साधारण ग्राफ पर EFX आवंटन का अग्रणी कार्य
  • Plaut और Roughgarden 2020: दो एजेंट EFX अस्तित्व प्रमाण
  • Chaudhury et al. 2020: तीन एजेंट स्थिति में महत्वपूर्ण प्रगति
  • Caragiannis et al. 2016: EFX अवधारणा का पहली बार प्रस्ताव

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