निष्पक्ष विभाजन: Difference between revisions
No edit summary |
No edit summary |
||
(24 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
'''निष्पक्ष विभाजन''' [[ खेल सिद्धांत |गेम थ्योरी]] में [[संसाधन|संसाधनों]] के समुच्चय को कई व्यक्तियों के बीच विभाजित करने की समस्या है। जिनके पास समुच्चय का अधिकार प्राप्त होता है। जिससे कि प्रत्येक व्यक्ति को उनका उचित भाग प्राप्त हो सके। यह समस्या रियल वर्ल्ड सेटिंग में उत्पन्न होती है। जैसे विरासत का विभाजन, साझेदारी का विघटन, विवाह विच्छेद की व्यवस्था, इलेक्ट्रॉनिक आवृत्ति आवंटन, हवाई अड्डा यातायात प्रबंधन और पृथ्वी अवलोकन उपग्रहों का शोषण। यह गणित, [[अर्थशास्त्र]] (विशेष रूप से [[सामाजिक पसंद सिद्धांत|सोशल च्वाइस थ्योरी]] ), [[विवाद समाधान|वाद-विवाद समाधान]] आदि में एक सक्रिय अनुसंधान क्षेत्र है। '''निष्पक्ष विभाजन''' का केंद्रीय सिद्धांत यह है कि इस प्रकार के विभाजन को खिलाड़ियों द्वारा संभवतः [[मध्यस्थता]] का उपयोग करते हुए स्वयं किया जाना चाहिए। किन्तु निश्चित रूप से मध्यस्थता नहीं होनी चाहिए। जैसा कि केवल खिलाड़ी ही वास्तविक रूप से जानते हैं कि वे सामानों को कैसे महत्व देते हैं। | |||
आर्किटेपल फेयर डिवीजन [[कलन विधि]] [[विभाजित करें और चुनें]]। यह प्रदर्शित करता है कि | आर्किटेपल फेयर डिवीजन [[कलन विधि|एल्गोरिदम]] [[विभाजित करें और चुनें]]। यह प्रदर्शित करता है कि विभिन्न प्रकार के टेस्ट वाले दो एजेंट एक केक को इस प्रकार से विभाजित कर सकते हैं कि उनमें से प्रत्येक का मानना है कि उसे सबसे अच्छा टुकड़ा प्राप्त हुआ। निष्पक्ष विभाजन में अनुसंधान को इस प्रक्रिया के विस्तार के रूप में देखा जा सकता है। जो कि कॉम्प्ले्क्स सेटिंग के लिए अधिक कठिन होती है। | ||
विभाजित करने के लिए | विभाजित करने के लिए सामान की प्रकृति, निष्पक्षता के मानदंड, खिलाड़ियों की प्रकृति और उनकी प्राथमिकताओं और विभाजन की गुणवत्ता के मूल्यांकन के लिए अन्य मानदंडों के आधार पर निष्पक्ष विभाजन की विभिन्न प्रकार की समस्याएं संज्ञान में आती हैं। | ||
== | == विभाजित की जाने वाली वस्तुएँं == | ||
औपचारिक रूप से | औपचारिक रूप से एक निष्पक्ष विभाजन समस्या को समुच्चय <math>C</math> (अधिकांशतः केक कहा जाता है) और <math>n</math> खिलाड़ियों के एक समूह द्वारा परिभाषित किया जाता है। एक विभाजन <math>C</math> में <math>n</math> असंयुक्त उपसमुच्चय का विभाजन है : <math>C = X_1 \sqcup X_2 \sqcup\cdots \sqcup X_n</math>, प्रति खिलाड़ी एक उप-समुच्चय। | ||
समुच्चय <math>C</math> विभिन्न प्रकार के हो सकते हैं: | समुच्चय <math>C</math> विभिन्न प्रकार के भी हो सकते हैं: | ||
* <math>C</math> अविभाज्य वस्तुओं का एक परिमित समूह हो सकता | * <math>C</math> अविभाज्य वस्तुओं का एक परिमित समूह हो सकता है। उदाहरण के लिए: <math>C = \{piano, car, apartment\}</math>, जैसे कि प्रत्येक वस्तु एक ही व्यक्ति को दी जानी चाहिए। | ||
* <math>C</math> एक विभाज्य संसाधन का प्रतिनिधित्व करने वाला एक अनंत समुच्चय हो सकता | * <math>C</math> एक विभाज्य संसाधन का प्रतिनिधित्व करने वाला एक अनंत समुच्चय हो सकता है। उदाहरण के लिए: पैसा या केक। गणितीय रूप से एक विभाज्य संसाधन को अधिकांशतः वास्तविक स्थान के उप-समुच्चय के रूप में तैयार किया जाता है। उदाहरण के लिए खंड [0,1] एक लंबे संकीर्ण केक का प्रतिनिधित्व कर सकता है। जिसे समानांतर टुकड़ों में विभाजित किया जाना है। [[यूनिट डिस्क]] एक सेब पाई का प्रतिनिधित्व कर सकती है। | ||
इसके अतिरिक्त विभाजित किया जाने वाला समुच्चय हो सकता है: | |||
* होमोजीनियस - जैसे पैसा, जहाँ केवल राशि का प्रतिनिधित्व होती है, या | |||
* हेट्रोजीनियस - जैसे एक केक, जिसमें विभिन्न प्रकार की सामग्री और विभिन्न प्रकार के टुकड़े आदि भी हो सकते हैं। | |||
अंत में इस विषय में कुछ धारणाएँ बनाना सामान्य हैे कि क्या वस्तुओं को विभाजित किया जाना है: | |||
* अच्छाइयाँ - जैसे कार या केक या | |||
*बुराइयाँ - जैसे घर के काम। | |||
अंत में | |||
* | |||
* | |||
इन भेदों के आधार पर, निष्पक्ष विभाजन की कई सामान्य प्रकार की समस्याओं का अध्ययन किया गया है: | इन भेदों के आधार पर, निष्पक्ष विभाजन की कई सामान्य प्रकार की समस्याओं का अध्ययन किया गया है: | ||
* [[उचित आइटम असाइनमेंट]] - अविभाज्य और विषम वस्तुओं के एक समुच्चय को विभाजित करना। | * [[उचित आइटम असाइनमेंट|निष्पक्ष मद असाइनमेंट -]] - अविभाज्य और विषम वस्तुओं के एक समुच्चय को विभाजित करना। | ||
* उचित संसाधन आवंटन - विभाज्य और सजातीय वस्तुओं के एक समुच्चय को विभाजित करना। एक विशेष | * उचित संसाधन आवंटन - विभाज्य और सजातीय वस्तुओं के एक समुच्चय को विभाजित करना। एक विशेष स्थिति [[एकल सजातीय संसाधन का उचित विभाजन|एकल सजातीय संसाधन का निष्पक्ष विभाजन]] है। | ||
* [[निष्पक्ष केक काटना]] - एक विभाज्य, विषम | * [[निष्पक्ष केक काटना]] - एक विभाज्य, विषम को विभाजित करना। एक विशेष स्थिति तब प्राप्त होती है। जब केक एक गोले के रूप में बना हुआ होता है। तब समस्या को [[ निष्पक्ष पाई-कटिंग |निष्पक्ष पाई-कटिंग]] कहा जाता है। | ||
* | * निष्पक्ष [[घर का काम विभाजन]] - एक विभाज्य, विजातीय को विभाजित करना। | ||
संयोजन और विशेष | संयोजन और विशेष स्थितियाँ भी सामान्य होती हैं: | ||
* | * रेंटल हार्मनी (हाउसमेट्स प्रॉब्लम) - अविभाज्य विजातीय वस्तुओं (जैसे एक अपार्टमेंट में कमरे) के एक समुच्चय को विभाजित करना और साथ ही एक सजातीय को विभाजित करना सही नहीं है (अपार्टमेंट पर किराया)। | ||
* | * फेयर रिवर शेयरिंग - एक अंतरराष्ट्रीय नदी में बहने वाले पानी को उसकी धारा के साथ उन देशों के बीच विभाजित करना। | ||
* | * [[उचित यादृच्छिक असाइनमेंट]]- विशेष रूप से अविभाज्य वस्तुओं को आवंटित करते समय लॉटरी को डिवीजनों में विभाजित करना सामान्य है। | ||
== निष्पक्षता की परिभाषा == | == निष्पक्षता की परिभाषा == | ||
सामान्यतः जिसे निष्पक्ष विभाजन कहा जाता है। उसमें से अधिकांशतः मध्यस्थता के उपयोग के कारण सिद्धांत द्वारा ऐसा नहीं माना जाता है। इस प्रकार की स्थिति अधिकांश वास्तविक जीवन की समस्याओं के नाम पर रखे गए गणितीय सिद्धांतों के साथ होती है। जब एक संपत्ति [[दिवालिया]] होती है। जिससे पात्रता (निष्पक्ष विभाजन) पर [[तल्मूड]] में निर्णय निष्पक्षता के विषय में कुछ अधिक जटिल विचारों को प्रदर्शित करता है<ref>{{cite journal | last1 = Aumann | first1 = Robert J. | last2 = Maschler | first2 = Michael | year = 1985 | title = तल्मूड से दिवालियेपन की समस्या का खेल सैद्धांतिक विश्लेषण| url = http://www.elsevier.com/framework_aboutus/Nobel/Nobel2005/nobel2005pdfs/aum16.pdf | journal = Journal of Economic Theory | volume = 36 | issue = 2 | pages = 195–213 | doi = 10.1016/0022-0531(85)90102-4 | url-status = dead | archive-url = https://web.archive.org/web/20060220022042/http://www.elsevier.com/framework_aboutus/Nobel/Nobel2005/nobel2005pdfs/aum16.pdf | archive-date = 2006-02-20 }}</ref> और अधिकांशतः व्यक्ति उन्हें निष्पक्ष मानेंगे। चूंकि वे अधिकारी के मूल्यांकन के अनुसार विभाजन के अतिरिक्त रब्बियों द्वारा नियमों के वाद-विवाद का परिणाम हैं। | |||
मूल्य के व्यक्तिपरक सिद्धांत के अनुसार | मूल्य के व्यक्तिपरक सिद्धांत के अनुसार प्रत्येक वस्तु के मूल्य का एक वस्तुनिष्ठ माप नहीं हो सकता है। इसलिए निष्पक्षता संभव नहीं है क्योंकि विभिन्न प्रकार के व्यक्ति प्रत्येक वस्तु के लिए विभिन्न मान निर्दिष्ट कर सकते हैं। व्यक्ति निष्पक्षता की अवधारणा को कैसे परिभाषित करते हैं। इस पर अनुभवजन्य प्रयोग<ref>{{Cite journal | last1 = Yaari | first1 = M. E. | last2 = Bar-Hillel | first2 = M. | doi = 10.1007/BF00297056 | title = न्यायोचित विभाजन करने पर| journal = Social Choice and Welfare | volume = 1 |page=1 | year = 1984 | s2cid = 153443060 }}</ref> अनिर्णायक परिणाम की ओर ले जाते हैं। | ||
इसलिए | इसलिए निष्पक्षता पर अधिकांशतः वर्तमान शोध व्यक्तिपरक निष्पक्षता की अवधारणाओं पर केंद्रित है। प्रत्येक <math>n</math> लोगों को व्यक्तिगत, व्यक्तिपरक उपयोगिता कार्य या मूल्य कार्य <math>V_i</math> माना जाता है। जो प्रत्येक उप-समुच्चय <math>C</math> के लिए एक संख्यात्मक मान प्रदान करता है। अधिकांश फलनों को सामान्यीकृत मान लिया जाता है। जिससे प्रत्येक व्यक्ति संवृत समुच्चय को 0 (<math>V_i (\empty) = 0</math> सभी i के लिए) के रूप में मान दे और 1 के रूप में आइटम का पूरा समुच्चय (<math>V_i (C) = 1</math> सभी के लिए i)। यदि आइटम वांछनीय हैं और -1 यदि आइटम अवांछनीय हैं। उदाहरण हैं: | ||
* | * यदि <math>C</math> अविभाज्य वस्तुओं {पियानो, कार, अपार्टमेंट} का समुच्चय है। जिससे [[ऐलिस और बॉब]] प्रत्येक आइटम के लिए 1/3 का मान निर्दिष्ट कर सकते हैं। जिसका अर्थ है कि प्रत्येक आइटम उसके लिए किसी भी अन्य आइटम के समान ही महत्वपूर्ण है। ऐलिस और बॉब समुच्चय {कार, अपार्टमेंट} के लिए 1 का मान और X को छोड़कर अन्य सभी समुच्चयों के लिए मान 0 निर्दिष्ट कर सकते हैं। इसका अर्थ यह है कि वह केवल कार और अपार्टमेंट एक साथ प्राप्त करना चाहता है। केवल कार या केवल अपार्टमेंट या उनमें से प्रत्येक पियानो के साथ उसके लिए निरर्थक है। | ||
* | * यदि <math>C</math> एक लंबा संकीर्ण केक है (अंतराल [0,1] के रूप में तैयार किया गया है)। जिससे ऐलिस प्रत्येक उप-समुच्चय को उसकी लंबाई के अनुपात में एक मान निर्दिष्ट कर सकती है। जिसका अर्थ है कि वह आइसिंग की देखरेख किए बिना जितना संभव हो उतना केक चाहती है। बॉब केवल [0.4, 0.6] के उप-समुच्चय को मान दे सकता है। उदाहरण के लिए क्योंकि केक के इस भाग में चेरी होती है और बॉब केवल चेरी को पसंद करता है। | ||
इन व्यक्तिपरक मूल्य कार्यों के आधार पर | इन व्यक्तिपरक मूल्य कार्यों के आधार पर निष्पक्ष विभाजन के लिए व्यापक रूप से उपयोग किए जाने वाले कई मानदंड हैं। इनमें से कुछ एक दूसरे के साथ संघर्ष करते हैं। किन्तु अधिकाशतः उन्हें जोड़ा जा सकता है। यहां वर्णित मानदंड केवल तभी हैं, जब प्रत्येक खिलाड़ी समान राशि का अधिकारी सिद्ध होता हो: | ||
* एक [[आनुपातिक विभाजन]] का अर्थ है कि प्रत्येक व्यक्ति को अपने स्वयं के मूल्य | * एक [[आनुपातिक विभाजन]] का अर्थ है कि प्रत्येक व्यक्ति को अपने स्वयं के मूल्य फलन के अनुसार कम से कम उसका उचित भाग प्राप्त होता है। उदाहरण के लिए यदि तीन व्यक्ति एक केक बांटते हैं। जिससे प्रत्येक को कम से कम एक तिहाई अपने स्वयं के मूल्यांकन से मिलता है। अर्थात् प्रत्येक n लोगों को एक उप-समुच्चय <math>C</math> प्राप्त होता है। जिसे वह कुल मूल्य का कम से कम 1/n मानते हैं: | ||
** <math>V_i(X_i) \ge V_i(C)/n</math> सभी के लिए | ** <math>V_i(X_i) \ge V_i(C)/n</math> सभी के लिए i में, | ||
* एक [[सुपर-आनुपातिक विभाजन]] वह होता | * एक [[सुपर-आनुपातिक विभाजन]] वह होता है। जहां प्रत्येक खिलाड़ी को 1/n से अधिक कठिनता से प्राप्त होता है (ऐसा विभाजन केवल तभी उपस्थित होता है। जब खिलाड़ियों के विभिन्न प्रकार के मूल्यांकन होते हैं): | ||
** <math>V_i(X_i) > V_i(C)/n</math> सभी के लिए | ** <math>V_i(X_i) > V_i(C)/n</math> सभी के लिए i में, | ||
* एक | * एक इन्वे-फ्री विभाजन यह आश्वासन देता है कि कोई भी व्यक्ति किसी दूसरे के भाग को स्वयं से अधिक नहीं चाहेगा। अर्थात् प्रत्येक व्यक्ति को एक भाग प्राप्त होता है। जिसे वह कम से कम उतना ही महत्व देता है, जितना कि अन्य सभी शेयर को महत्व देता है: | ||
** <math>V_i(X_i) \ge V_i(X_j)</math> सभी i और j के लिए। | ** <math>V_i(X_i) \ge V_i(X_j)</math> सभी i और j के लिए। | ||
* एक समूह- | * एक समूह-इन्वे-फ्री विभाजन आश्वासन देता है कि एजेंटों का कोई भी उप-समुच्चय समान आकार के दूसरे उपसमुच्चय से उसका कोई भी संबंध नहीं। यह ईर्ष्या-निडरता से बहुत अधिक शक्तिशाली है। | ||
* एक [[इक्विटी (अर्थशास्त्र)]] डिवीजन का | * एक [[इक्विटी (अर्थशास्त्र)]] डिवीजन का अर्थ यह है कि प्रत्येक व्यक्ति बिल्कुल एक ही प्रकार की प्रसन्नता का अनुभव करता है, अर्थात् एक खिलाड़ी को स्वयं के मूल्यांकन से प्राप्त होने वाले केक का अनुपात प्रत्येक खिलाड़ी के लिए समान होता है। यह एक कठिन लक्ष्य है क्योंकि खिलाड़ियों से उनके मूल्यांकन के विषय में पूछे जाने पर उन्हें सही होने की आवश्यकता नहीं होती है: | ||
** <math>V_i(X_i) = V_j(X_j)</math> सभी i और j के लिए। | ** <math>V_i(X_i) = V_j(X_j)</math> सभी i और j के लिए। | ||
* एक [[सटीक विभाजन]] ( | * एक [[सटीक विभाजन|निष्पक्ष विभाजन]] (सर्वसम्मति विभाजन) वह है, जहां सभी खिलाड़ी प्रत्येक शेयर के मूल्य पर सहमत होते हैं और स्वीकृति प्रदान करते हैं: | ||
** <math>V_i(X_i) = V_j(X_i)</math> सभी i और j के लिए। | ** <math>V_i(X_i) = V_j(X_i)</math> सभी i और j के लिए। | ||
उपरोक्त सभी मानदंड मानते हैं कि प्रतिभागियों के पास समान पात्रता (निष्पक्ष विभाजन) है। यदि | उपरोक्त सभी मानदंड मानते हैं कि प्रतिभागियों के पास समान पात्रता (निष्पक्ष विभाजन) प्राप्त होती है। यदि विभिन्न प्रतिभागियों की अलग-अलग पात्रताएँ हैं (उदाहरण के लिए, एक साझेदारी में जहाँ प्रत्येक भागीदार ने एक अलग राशि का निवेश किया है), जिससे निष्पक्षता मानदंड को तदनुसार अनुकूलित किया जाना चाहिए। विभिन्न अधिकारों के साथ आनुपातिक केक-कटिंग देखें। | ||
== अतिरिक्त आवश्यकताएं == | == अतिरिक्त आवश्यकताएं == | ||
निष्पक्षता के | निष्पक्षता के अतिरिक्त कभी-कभी यह वांछित होता है कि विभाजन [[पेरेटो इष्टतम|पेरेटो ऑप्टिमल]] हो। अर्थात् कोई अन्य आवंटन किसी दूसरे को खराब किए बिना किसी को उत्कृष्ट नहीं बनाता है। दक्षता शब्द [[कुशल बाजार]] के अर्थशास्त्र के विचार से आता है। एक विभाजन जहां एक खिलाड़ी को सब कुछ प्राप्त होता है। इस परिभाषा से ऑप्टिमल है। इसलिए यह स्वयं में एक उचित भाग का आश्वासन भी नहीं देता है। [[कुशल केक काटने]] और [[निष्पक्षता की कीमत|निष्पक्षता का मूल्य]] भी देखें। | ||
[[File:Berlin Blockade-map.svg|thumb|200px|right|[[पॉट्सडैम सम्मेलन]] द्वारा विभाजित बर्लिन]] | [[File:Berlin Blockade-map.svg|thumb|200px|right|[[पॉट्सडैम सम्मेलन]] द्वारा विभाजित बर्लिन]]यथार्थतः विश्व में संभवतः व्यक्तियों को बहुत स्पष्ट अनुमान होता है कि दूसरे खिलाड़ी सामान को कितना महत्व प्रदान करते हैं और वे इसकी बहुत देखरेख करते हैं। ऐसी स्थिति जहां उन्हें एक-दूसरे के मूल्यांकन का सम्पूर्ण ज्ञान प्राप्त होता है। यह गेम थ्योरी द्वारा तैयार किया जा सकता है। आंशिक ज्ञान को मॉडल करना बहुत कठिन होता है। निष्पक्ष विभाजन के व्यावहारिक पक्ष का एक बड़ा भाग ऐसी प्रक्रियाओं का विकास और अध्ययन है। जो इस प्रकार के आंशिक ज्ञान या छोटी त्रुटियों के बाद भी अच्छी प्रकार से कार्य करती हैं। | ||
एक अतिरिक्त आवश्यकता यह है कि निष्पक्ष विभाजन प्रक्रिया एक | एक अतिरिक्त आवश्यकता यह है कि निष्पक्ष विभाजन प्रक्रिया एक ट्रुथफुल मैकेनिज्म हो, अर्थात् प्रतिभागियों के लिए उनके वास्तविक मूल्यांकन की रिपोर्ट करने के लिए यह एक प्रमुख रणनीति होनी चाहिए। निष्पक्षता और पारेटो-दक्षता के संयोजन में इस आवश्यकता को पूरा करना सामान्यतः बहुत कठिन होता है। | ||
== प्रक्रियाएं == | == प्रक्रियाएं == | ||
एक | एक निष्पक्ष विभाजन एल्गोरिथम दृश्य डेटा और उनके मूल्यांकन के संदर्भ में खिलाड़ियों द्वारा की जाने वाले कार्यों को सूचीबद्ध करता है। इसकी एक वैध प्रक्रिया यह है कि जो प्रत्येक खिलाड़ी के लिए निष्पक्ष विभाजन की आश्वासन देती है। जो अपने मूल्यांकन के अनुसार तर्कसंगत रूप से कार्य करता है। जहां एक प्रक्रिया एक खिलाड़ी के मूल्यांकन पर निर्भर करती है। जिससे प्रक्रिया उस [[रणनीति]] का वर्णन कर रही है। जिसका एक तर्कसंगत खिलाड़ी पालन करेगा। एक खिलाड़ी इस प्रकार कार्य कर सकता है। जैसे कि एक टुकड़े का एक अलग मूल्य था। किन्तु वह संगत होना चाहिए। उदाहरण के लिए यदि एक प्रक्रिया यह वर्णन करती है कि पहला खिलाड़ी केक को दो बराबर भागों में विभाजित करता है। जिससे दूसरा खिलाड़ी एक टुकड़ा चुनता है, जिससे पहला खिलाड़ी यह दावा नहीं कर सकता कि दूसरे खिलाड़ी को अधिक प्राप्त हुआ है। | ||
खिलाड़ी क्या करते हैं: | खिलाड़ी क्या करते हैं: | ||
* निष्पक्ष विभाजन के लिए उनके मानदंड पर सहमत | * निष्पक्ष विभाजन के लिए उनके मानदंड पर सहमत हों। | ||
* एक मान्य प्रक्रिया का चयन करें और उसके नियमों का पालन | * एक मान्य प्रक्रिया का चयन करें और उसके नियमों का पालन करें। | ||
यह माना जाता है कि प्रत्येक खिलाड़ी का लक्ष्य उन्हें मिलने वाली न्यूनतम राशि को अधिकतम करना है | यह माना जाता है कि प्रत्येक खिलाड़ी का लक्ष्य उन्हें मिलने वाली न्यूनतम राशि को अधिकतम करना है या दूसरे शब्दों में न्यूनतम राशि प्राप्त करना है। | ||
प्रक्रियाओं को असतत | प्रक्रियाओं को असतत या निरंतर प्रक्रियाओं में विभाजित किया जा सकता है। उदाहरण के लिए एक असतत प्रक्रिया में एक समय में केवल एक व्यक्ति को केक काटने या चिह्नित करना सम्मिलित होगा। निरंतर प्रक्रियाओं में एक खिलाड़ी के चाकू चलने की प्रक्रिया और दूसरे के कहने पर रोक देना आदि जैसी वस्तुएँ सम्मिलित होती हैं। एक अन्य प्रकार की सतत प्रक्रिया में केक के प्रत्येक भाग के लिए व्यक्ति को मूल्य निर्दिष्ट करना सम्मिलित होता है। | ||
निष्पक्ष विभाजन प्रक्रियाओं की सूची के लिए देखें :श्रेणी:निष्पक्ष विभाजन प्रोटोकॉल। | |||
कोई परिमित प्रोटोकॉल ( | कोई परिमित प्रोटोकॉल (तथापि असीमित हो) तीन या अधिक खिलाड़ियों के बीच एक केक के इन्वे-फ्री विभाजन की आश्वासन प्रदान कर सकता है। यदि प्रत्येक खिलाड़ी को एक जुड़ा हुआ टुकड़ा प्राप्त करना है।<ref>{{cite journal |last=Stromquist |first=Walter |date=2008 |title=एन्वी-फ्री केक डिवीजनों को परिमित प्रोटोकॉल द्वारा नहीं पाया जा सकता है|url=https://eudml.org/doc/129749 |journal=The Electronic Journal of Combinatorics |volume=15 |access-date=October 26, 2022 |doi=10.37236/735|doi-access=free }}</ref> उदाहरण के लिए चूंकि यह परिणाम केवल उस कार्य में प्रस्तुत मॉडल पर संचालित होता है और उन स्थितियों के लिए नहीं, जहां एक मध्यस्थ के पास खिलाड़ियों के मूल्यांकन फलनों की सम्पूर्ण जानकारी होती है और इस जानकारी के आधार पर एक विभाजन का प्रस्ताव करता है।<ref>{{cite conference |url=https://link.springer.com/chapter/10.1007/978-3-642-17572-5_3 |title=कनेक्टेड पीसेज के साथ फेयर डिवीजन की दक्षता|last1=Aumann |first1=Yonatan |last2=Dombb |first2=Yair |date=2010 |publisher=Springer |book-title=Internet and Network Economics |pages=26–37 |doi=10.1007/978-3-642-17572-5_3 |conference=International Workshop on Internet and Network Economics}}</ref> | ||
== एक्सटेंशन == | == एक्सटेंशन == | ||
वर्तमान समय में निष्पक्ष विभाजन के मॉडल को व्यक्तिगत एजेंटों से लेकर एजेंटों के फैमली (पूर्व-निर्धारित समूहों) तक बढ़ाया गया है। [[समूहों के बीच उचित विभाजन|समूहों के बीच निष्पक्ष विभाजन]] देखें। | |||
== इतिहास == | == इतिहास == | ||
[[सोल गारफंकेल]] के अनुसार | [[सोल गारफंकेल]] के अनुसार केक काटने की समस्या 20वीं सदी के गणित की सबसे महत्वपूर्ण संवृत समस्याओं में से एक थी।<ref>Sol Garfunkel. More Equal than Others: Weighted Voting. For All Practical Purposes. COMAP. 1988</ref> जब 1995 में [[स्टीवन ब्राम्स]] और एलन डी. टेलर द्वारा [[ब्रैम-टेलर प्रक्रिया]] के साथ समस्या का सबसे महत्वपूर्ण रूप अंततः हल किया गया था। | ||
विभाजन करने और चुनाने की उत्पत्ति को लिखित रूप से वर्णित नहीं किया गया था। वस्तुओं के मूल्य को कम कराना और वस्तु विनिमय की संबंधित गतिविधियाँ भी प्राचीन हैं। दो से अधिक लोगों को सम्मिलित करने वाली [[बातचीत|वार्तालाप]] भी अधिक सामान्य है। पॉट्सडैम सम्मेलन एक उल्लेखनीय वर्तमान समय का उदाहरण है। | |||
निष्पक्ष विभाजन का सिद्धांत | निष्पक्ष विभाजन का सिद्धांत का निर्माण द्वितीय विश्व युद्ध के समय हुआ है। यह [[पोलैंड]] के गणितज्ञों, [[ह्यूगो स्टीनहॉस]], ब्रॉनिस्लाव नस्टर और [[स्टीफन बानाच|स्टीफन बनाच]] के एक समूह द्वारा तैयार किया गया था। जो लावोव (तब पोलैंड में) में स्कॉटिश कैफे में प्राप्त होते थे। 1944 में 'अंतिम-मंदक' कहे जाने वाले खिलाड़ियों की किसी भी संख्या के लिए एक आनुपातिक (निष्पक्ष विभाजन) विभाजन तैयार किया गया था। इसका श्रेय स्टीनहॉस द्वारा बनच और नास्टर को दिया गया था। जब उन्होंने [[ अर्थमितीय समाज |अर्थमितीय समाज]] की बैठक में 17 सितंबर 1947 को वाशिंगटन डी.सी में पहली बार समस्या को सार्वजनिक किया था। उस बैठक में उन्होंने इस प्रकार के विभाजनों के लिए आवश्यक कमी की सबसे छोटी संख्या खोजने की समस्या का भी प्रस्ताव रखा। | ||
इन्वे-फ्री केक काटने के इतिहास के लिए इन्वे-फ्री केक-कटिंग देखें। | |||
== लोकप्रिय संस्कृति में == | == लोकप्रिय संस्कृति में == | ||
* 17-जानवरों की विरासत पहेली में 17 ऊंटों | * 17-जानवरों की विरासत पहेली में 17 ऊंटों या हाथी या घोड़ों के निष्पक्ष विभाजन को 1/2, 1/3 और 1/9 के अनुपात में सम्मिलित किया गया है। यह एक प्रचलित [[गणितीय पहेली]] है। जिसका अधिकांशतः एक प्राचीन मूल होने का दावा प्रस्तुत किया जाता है। किन्तु इसका पहला प्रलेखित प्रकाशन 18वीं शताब्दी के ईरान में हुआ था।<ref>{{cite journal | ||
| last = Ageron | first = Pierre | | last = Ageron | first = Pierre | ||
| issue = 1 | | issue = 1 | ||
Line 107: | Line 104: | ||
| volume = 19 | | volume = 19 | ||
| year = 2013}}; see in particular pp. 13–14.</ref> | | year = 2013}}; see in particular pp. 13–14.</ref> | ||
* [[Numb3rs]] सीज़न 3 के एपिसोड वन आवर में | * [[Numb3rs]] सीज़न 3 के एपिसोड "वन आवर" में चार्ली केक काटने की समस्या के विषय में वार्तालाप करता है। जो उस राशि पर संचालित होती है। जो एक अपहरणकर्ता मांग रहा था। | ||
* ह्यूगो स्टीनहॉस ने अपनी पुस्तक मैथमैटिकल स्नैपशॉट्स में निष्पक्ष विभाजन के कई प्रकारों के | * ह्यूगो स्टीनहॉस ने अपनी पुस्तक मैथमैटिकल स्नैपशॉट्स में निष्पक्ष विभाजन के कई प्रकारों के विषय में उल्लेख किया है। उन्होंने अपनी पुस्तक में कहा है कि फेयर डिवीजन का एक विशेष तीन-व्यक्ति संस्करण 1944 में बेर्देचो में जी. क्रोचमैनी द्वारा तैयार किया गया था और इसका दूसरा संस्करण श्रीमती एल कोट्ट द्वारा तैयार किया गया था।<ref>Mathematical Snapshots. H.Steinhaus. 1950, 1969 {{ISBN|0-19-503267-5}}</ref> | ||
* [[मार्टिन गार्डनर]] और [[इयान स्टीवर्ट (गणितज्ञ)]] दोनों ने समस्या के | * [[मार्टिन गार्डनर]] और [[इयान स्टीवर्ट (गणितज्ञ)]] दोनों ने इस समस्या के विषय में कई भागों वाली पुस्तकें प्रकाशित की हैं।<ref>aha! Insight. Martin. Gardner, 1978. {{ISBN|978-0-7167-1017-2}}</ref><ref>How to cut a cake and other mathematical conundrums. Ian Stewart. 2006. {{ISBN|978-0-19-920590-5}}</ref> मार्टिन गार्डनर ने समस्या का कोर डिवीजन फॉर्म प्रस्तुत किया। इयान स्टीवर्ट ने [[ अमेरिकी वैज्ञानिक |अमेरिकी वैज्ञानिक]] और [[ नए वैज्ञानिक |नए वैज्ञानिक]] में अपने लेखों के साथ निष्पक्ष विभाजन की समस्या को प्रचलित बनाया है। | ||
* [[डायनासोर कॉमिक्स]] की पट्टी केक काटने की समस्या पर आधारित है।<ref>{{Cite web|url=http://www.qwantz.com/index.php?comic=1345|title=Dinosaur Comics!}}</ref> | * [[डायनासोर कॉमिक्स]] की पट्टी केक काटने की समस्या पर आधारित है।<ref>{{Cite web|url=http://www.qwantz.com/index.php?comic=1345|title=Dinosaur Comics!}}</ref> | ||
* इजरायली फिल्म [[सेंट क्लारा (फिल्म)]] में एक रूसी अप्रवासी | * इजरायली फिल्म [[सेंट क्लारा (फिल्म)]] में एक रूसी अप्रवासी इजरायली गणित शिक्षक से पूछता है कि एक गोलाकार केक को 7 लोगों के बीच निष्पक्ष रूप से कैसे बांटा जा सकता है? उसका उत्तर इसके मध्य से 3 सीधे कट के चिन्ह बनाना है। जिससे 8 बराबर टुकड़ों में विभाजित किया जा सके। चूंकि केवल 7 व्यक्ति उपस्थित हैं। इसमें साम्यवाद की भावना में एक टुकड़ा त्याग दिया जाना चाहिए। | ||
== यह भी देखें == | == यह भी देखें == | ||
* [[ ऑनलाइन मेले का विभाजन ]] | * [[ ऑनलाइन मेले का विभाजन |ऑनलाइन निष्पक्ष विभाजन]] निष्पक्ष विभाजन का एक प्रकार है। जिसमें विभाजन के समय सभी आइटम या एजेंट उपलब्ध नहीं होते हैं। | ||
* इक्विटी (अर्थशास्त्र) | * इक्विटी (अर्थशास्त्र) | ||
* [[अंतर्राष्ट्रीय व्यापार]] | * [[अंतर्राष्ट्रीय व्यापार]] | ||
* [[न्याय (अर्थशास्त्र)]] | * [[न्याय (अर्थशास्त्र)]] | ||
* [[बस्ता समस्या]] | * [[बस्ता समस्या|बैग समस्या]] | ||
* | * निष्पक्ष विभाजन में अनसुलझी समस्याओं की सूची | ||
* [[नैश सौदेबाजी का खेल]] | * [[नैश सौदेबाजी का खेल|नैश मध्यस्थता का खेल]] | ||
* [[पिज्जा प्रमेय]] | * [[पिज्जा प्रमेय]] | ||
* निष्पक्षता की | * निष्पक्षता की मूल्य | ||
* [[ स्पाईट (गेम थ्योरी) ]] | * [[ स्पाईट (गेम थ्योरी) ]] | ||
* [[सामरिक निष्पक्ष विभाजन]] | * [[सामरिक निष्पक्ष विभाजन]] | ||
* [[एंटीकॉमन्स की त्रासदी]] | * [[एंटीकॉमन्स की त्रासदी]] | ||
* [[सामान्य लोगों की त्रासदी]] | * [[सामान्य लोगों की त्रासदी|सामान्य व्यक्तियों की त्रासदी]] | ||
== संदर्भ == | == संदर्भ == | ||
Line 150: | Line 147: | ||
* [https://link.springer.com/chapter/10.1007/978-90-481-9097-3_12 फेयर डिवीजन] क्रिश्चियन क्लैमलर द्वारा - ग्रुप डिसिजन एंड नेगोशिएशन पीपी 183-202 की हैंडबुक में। | * [https://link.springer.com/chapter/10.1007/978-90-481-9097-3_12 फेयर डिवीजन] क्रिश्चियन क्लैमलर द्वारा - ग्रुप डिसिजन एंड नेगोशिएशन पीपी 183-202 की हैंडबुक में। | ||
* [https://link.springer.com/chapter/10.1007/978-3-662-47904-9_7 केक-कटिंग: फेयर डिवीजन ऑफ डिविजिबल गुड्स] क्लाउडिया लिंडनर और जॉर्ग रोथ द्वारा - अर्थशास्त्र और संगणना में पीपी 395-491 . | * [https://link.springer.com/chapter/10.1007/978-3-662-47904-9_7 केक-कटिंग: फेयर डिवीजन ऑफ डिविजिबल गुड्स] क्लाउडिया लिंडनर और जॉर्ग रोथ द्वारा - अर्थशास्त्र और संगणना में पीपी 395-491 . | ||
* [https://link.springer.com/chapter/10.1007/978-3-662-47904-9_8 अविभाज्य वस्तुओं का | * [https://link.springer.com/chapter/10.1007/978-3-662-47904-9_8 अविभाज्य वस्तुओं का निष्पक्ष विभाजन] जेरोम लैंग और जोर्ग रोथ द्वारा - अर्थशास्त्र और संगणना पीपी 493-550 में। | ||
== बाहरी संबंध == | == बाहरी संबंध == | ||
Line 159: | Line 156: | ||
{{game theory}} | {{game theory}} | ||
{{DEFAULTSORT:Fair Division}} | {{DEFAULTSORT:Fair Division}} | ||
[[Category: | [[Category:CS1 English-language sources (en)|Fair Division]] | ||
[[Category:Created On 01/05/2023]] | [[Category:CS1 français-language sources (fr)]] | ||
[[Category:Collapse templates|Fair Division]] | |||
[[Category:Created On 01/05/2023|Fair Division]] | |||
[[Category:Machine Translated Page|Fair Division]] | |||
[[Category:Navigational boxes| ]] | |||
[[Category:Navigational boxes without horizontal lists|Fair Division]] | |||
[[Category:Pages with script errors|Fair Division]] | |||
[[Category:Sidebars with styles needing conversion|Fair Division]] | |||
[[Category:Template documentation pages|Documentation/doc]] | |||
[[Category:Templates Vigyan Ready|Fair Division]] | |||
[[Category:Templates generating microformats|Fair Division]] | |||
[[Category:Templates that are not mobile friendly|Fair Division]] | |||
[[Category:Templates using TemplateData|Fair Division]] | |||
[[Category:Wikipedia metatemplates|Fair Division]] | |||
[[Category:कल्याणकारी अर्थशास्त्र|Fair Division]] | |||
[[Category:खेल सिद्धांत|Fair Division]] | |||
[[Category:मेला विभाग| मेला विभाग]] |
Latest revision as of 16:29, 9 June 2023
निष्पक्ष विभाजन गेम थ्योरी में संसाधनों के समुच्चय को कई व्यक्तियों के बीच विभाजित करने की समस्या है। जिनके पास समुच्चय का अधिकार प्राप्त होता है। जिससे कि प्रत्येक व्यक्ति को उनका उचित भाग प्राप्त हो सके। यह समस्या रियल वर्ल्ड सेटिंग में उत्पन्न होती है। जैसे विरासत का विभाजन, साझेदारी का विघटन, विवाह विच्छेद की व्यवस्था, इलेक्ट्रॉनिक आवृत्ति आवंटन, हवाई अड्डा यातायात प्रबंधन और पृथ्वी अवलोकन उपग्रहों का शोषण। यह गणित, अर्थशास्त्र (विशेष रूप से सोशल च्वाइस थ्योरी ), वाद-विवाद समाधान आदि में एक सक्रिय अनुसंधान क्षेत्र है। निष्पक्ष विभाजन का केंद्रीय सिद्धांत यह है कि इस प्रकार के विभाजन को खिलाड़ियों द्वारा संभवतः मध्यस्थता का उपयोग करते हुए स्वयं किया जाना चाहिए। किन्तु निश्चित रूप से मध्यस्थता नहीं होनी चाहिए। जैसा कि केवल खिलाड़ी ही वास्तविक रूप से जानते हैं कि वे सामानों को कैसे महत्व देते हैं।
आर्किटेपल फेयर डिवीजन एल्गोरिदम विभाजित करें और चुनें। यह प्रदर्शित करता है कि विभिन्न प्रकार के टेस्ट वाले दो एजेंट एक केक को इस प्रकार से विभाजित कर सकते हैं कि उनमें से प्रत्येक का मानना है कि उसे सबसे अच्छा टुकड़ा प्राप्त हुआ। निष्पक्ष विभाजन में अनुसंधान को इस प्रक्रिया के विस्तार के रूप में देखा जा सकता है। जो कि कॉम्प्ले्क्स सेटिंग के लिए अधिक कठिन होती है।
विभाजित करने के लिए सामान की प्रकृति, निष्पक्षता के मानदंड, खिलाड़ियों की प्रकृति और उनकी प्राथमिकताओं और विभाजन की गुणवत्ता के मूल्यांकन के लिए अन्य मानदंडों के आधार पर निष्पक्ष विभाजन की विभिन्न प्रकार की समस्याएं संज्ञान में आती हैं।
विभाजित की जाने वाली वस्तुएँं
औपचारिक रूप से एक निष्पक्ष विभाजन समस्या को समुच्चय (अधिकांशतः केक कहा जाता है) और खिलाड़ियों के एक समूह द्वारा परिभाषित किया जाता है। एक विभाजन में असंयुक्त उपसमुच्चय का विभाजन है : , प्रति खिलाड़ी एक उप-समुच्चय।
समुच्चय विभिन्न प्रकार के भी हो सकते हैं:
- अविभाज्य वस्तुओं का एक परिमित समूह हो सकता है। उदाहरण के लिए: , जैसे कि प्रत्येक वस्तु एक ही व्यक्ति को दी जानी चाहिए।
- एक विभाज्य संसाधन का प्रतिनिधित्व करने वाला एक अनंत समुच्चय हो सकता है। उदाहरण के लिए: पैसा या केक। गणितीय रूप से एक विभाज्य संसाधन को अधिकांशतः वास्तविक स्थान के उप-समुच्चय के रूप में तैयार किया जाता है। उदाहरण के लिए खंड [0,1] एक लंबे संकीर्ण केक का प्रतिनिधित्व कर सकता है। जिसे समानांतर टुकड़ों में विभाजित किया जाना है। यूनिट डिस्क एक सेब पाई का प्रतिनिधित्व कर सकती है।
इसके अतिरिक्त विभाजित किया जाने वाला समुच्चय हो सकता है:
- होमोजीनियस - जैसे पैसा, जहाँ केवल राशि का प्रतिनिधित्व होती है, या
- हेट्रोजीनियस - जैसे एक केक, जिसमें विभिन्न प्रकार की सामग्री और विभिन्न प्रकार के टुकड़े आदि भी हो सकते हैं।
अंत में इस विषय में कुछ धारणाएँ बनाना सामान्य हैे कि क्या वस्तुओं को विभाजित किया जाना है:
- अच्छाइयाँ - जैसे कार या केक या
- बुराइयाँ - जैसे घर के काम।
इन भेदों के आधार पर, निष्पक्ष विभाजन की कई सामान्य प्रकार की समस्याओं का अध्ययन किया गया है:
- निष्पक्ष मद असाइनमेंट - - अविभाज्य और विषम वस्तुओं के एक समुच्चय को विभाजित करना।
- उचित संसाधन आवंटन - विभाज्य और सजातीय वस्तुओं के एक समुच्चय को विभाजित करना। एक विशेष स्थिति एकल सजातीय संसाधन का निष्पक्ष विभाजन है।
- निष्पक्ष केक काटना - एक विभाज्य, विषम को विभाजित करना। एक विशेष स्थिति तब प्राप्त होती है। जब केक एक गोले के रूप में बना हुआ होता है। तब समस्या को निष्पक्ष पाई-कटिंग कहा जाता है।
- निष्पक्ष घर का काम विभाजन - एक विभाज्य, विजातीय को विभाजित करना।
संयोजन और विशेष स्थितियाँ भी सामान्य होती हैं:
- रेंटल हार्मनी (हाउसमेट्स प्रॉब्लम) - अविभाज्य विजातीय वस्तुओं (जैसे एक अपार्टमेंट में कमरे) के एक समुच्चय को विभाजित करना और साथ ही एक सजातीय को विभाजित करना सही नहीं है (अपार्टमेंट पर किराया)।
- फेयर रिवर शेयरिंग - एक अंतरराष्ट्रीय नदी में बहने वाले पानी को उसकी धारा के साथ उन देशों के बीच विभाजित करना।
- उचित यादृच्छिक असाइनमेंट- विशेष रूप से अविभाज्य वस्तुओं को आवंटित करते समय लॉटरी को डिवीजनों में विभाजित करना सामान्य है।
निष्पक्षता की परिभाषा
सामान्यतः जिसे निष्पक्ष विभाजन कहा जाता है। उसमें से अधिकांशतः मध्यस्थता के उपयोग के कारण सिद्धांत द्वारा ऐसा नहीं माना जाता है। इस प्रकार की स्थिति अधिकांश वास्तविक जीवन की समस्याओं के नाम पर रखे गए गणितीय सिद्धांतों के साथ होती है। जब एक संपत्ति दिवालिया होती है। जिससे पात्रता (निष्पक्ष विभाजन) पर तल्मूड में निर्णय निष्पक्षता के विषय में कुछ अधिक जटिल विचारों को प्रदर्शित करता है[1] और अधिकांशतः व्यक्ति उन्हें निष्पक्ष मानेंगे। चूंकि वे अधिकारी के मूल्यांकन के अनुसार विभाजन के अतिरिक्त रब्बियों द्वारा नियमों के वाद-विवाद का परिणाम हैं।
मूल्य के व्यक्तिपरक सिद्धांत के अनुसार प्रत्येक वस्तु के मूल्य का एक वस्तुनिष्ठ माप नहीं हो सकता है। इसलिए निष्पक्षता संभव नहीं है क्योंकि विभिन्न प्रकार के व्यक्ति प्रत्येक वस्तु के लिए विभिन्न मान निर्दिष्ट कर सकते हैं। व्यक्ति निष्पक्षता की अवधारणा को कैसे परिभाषित करते हैं। इस पर अनुभवजन्य प्रयोग[2] अनिर्णायक परिणाम की ओर ले जाते हैं।
इसलिए निष्पक्षता पर अधिकांशतः वर्तमान शोध व्यक्तिपरक निष्पक्षता की अवधारणाओं पर केंद्रित है। प्रत्येक लोगों को व्यक्तिगत, व्यक्तिपरक उपयोगिता कार्य या मूल्य कार्य माना जाता है। जो प्रत्येक उप-समुच्चय के लिए एक संख्यात्मक मान प्रदान करता है। अधिकांश फलनों को सामान्यीकृत मान लिया जाता है। जिससे प्रत्येक व्यक्ति संवृत समुच्चय को 0 ( सभी i के लिए) के रूप में मान दे और 1 के रूप में आइटम का पूरा समुच्चय ( सभी के लिए i)। यदि आइटम वांछनीय हैं और -1 यदि आइटम अवांछनीय हैं। उदाहरण हैं:
- यदि अविभाज्य वस्तुओं {पियानो, कार, अपार्टमेंट} का समुच्चय है। जिससे ऐलिस और बॉब प्रत्येक आइटम के लिए 1/3 का मान निर्दिष्ट कर सकते हैं। जिसका अर्थ है कि प्रत्येक आइटम उसके लिए किसी भी अन्य आइटम के समान ही महत्वपूर्ण है। ऐलिस और बॉब समुच्चय {कार, अपार्टमेंट} के लिए 1 का मान और X को छोड़कर अन्य सभी समुच्चयों के लिए मान 0 निर्दिष्ट कर सकते हैं। इसका अर्थ यह है कि वह केवल कार और अपार्टमेंट एक साथ प्राप्त करना चाहता है। केवल कार या केवल अपार्टमेंट या उनमें से प्रत्येक पियानो के साथ उसके लिए निरर्थक है।
- यदि एक लंबा संकीर्ण केक है (अंतराल [0,1] के रूप में तैयार किया गया है)। जिससे ऐलिस प्रत्येक उप-समुच्चय को उसकी लंबाई के अनुपात में एक मान निर्दिष्ट कर सकती है। जिसका अर्थ है कि वह आइसिंग की देखरेख किए बिना जितना संभव हो उतना केक चाहती है। बॉब केवल [0.4, 0.6] के उप-समुच्चय को मान दे सकता है। उदाहरण के लिए क्योंकि केक के इस भाग में चेरी होती है और बॉब केवल चेरी को पसंद करता है।
इन व्यक्तिपरक मूल्य कार्यों के आधार पर निष्पक्ष विभाजन के लिए व्यापक रूप से उपयोग किए जाने वाले कई मानदंड हैं। इनमें से कुछ एक दूसरे के साथ संघर्ष करते हैं। किन्तु अधिकाशतः उन्हें जोड़ा जा सकता है। यहां वर्णित मानदंड केवल तभी हैं, जब प्रत्येक खिलाड़ी समान राशि का अधिकारी सिद्ध होता हो:
- एक आनुपातिक विभाजन का अर्थ है कि प्रत्येक व्यक्ति को अपने स्वयं के मूल्य फलन के अनुसार कम से कम उसका उचित भाग प्राप्त होता है। उदाहरण के लिए यदि तीन व्यक्ति एक केक बांटते हैं। जिससे प्रत्येक को कम से कम एक तिहाई अपने स्वयं के मूल्यांकन से मिलता है। अर्थात् प्रत्येक n लोगों को एक उप-समुच्चय प्राप्त होता है। जिसे वह कुल मूल्य का कम से कम 1/n मानते हैं:
- सभी के लिए i में,
- एक सुपर-आनुपातिक विभाजन वह होता है। जहां प्रत्येक खिलाड़ी को 1/n से अधिक कठिनता से प्राप्त होता है (ऐसा विभाजन केवल तभी उपस्थित होता है। जब खिलाड़ियों के विभिन्न प्रकार के मूल्यांकन होते हैं):
- सभी के लिए i में,
- एक इन्वे-फ्री विभाजन यह आश्वासन देता है कि कोई भी व्यक्ति किसी दूसरे के भाग को स्वयं से अधिक नहीं चाहेगा। अर्थात् प्रत्येक व्यक्ति को एक भाग प्राप्त होता है। जिसे वह कम से कम उतना ही महत्व देता है, जितना कि अन्य सभी शेयर को महत्व देता है:
- सभी i और j के लिए।
- एक समूह-इन्वे-फ्री विभाजन आश्वासन देता है कि एजेंटों का कोई भी उप-समुच्चय समान आकार के दूसरे उपसमुच्चय से उसका कोई भी संबंध नहीं। यह ईर्ष्या-निडरता से बहुत अधिक शक्तिशाली है।
- एक इक्विटी (अर्थशास्त्र) डिवीजन का अर्थ यह है कि प्रत्येक व्यक्ति बिल्कुल एक ही प्रकार की प्रसन्नता का अनुभव करता है, अर्थात् एक खिलाड़ी को स्वयं के मूल्यांकन से प्राप्त होने वाले केक का अनुपात प्रत्येक खिलाड़ी के लिए समान होता है। यह एक कठिन लक्ष्य है क्योंकि खिलाड़ियों से उनके मूल्यांकन के विषय में पूछे जाने पर उन्हें सही होने की आवश्यकता नहीं होती है:
- सभी i और j के लिए।
- एक निष्पक्ष विभाजन (सर्वसम्मति विभाजन) वह है, जहां सभी खिलाड़ी प्रत्येक शेयर के मूल्य पर सहमत होते हैं और स्वीकृति प्रदान करते हैं:
- सभी i और j के लिए।
उपरोक्त सभी मानदंड मानते हैं कि प्रतिभागियों के पास समान पात्रता (निष्पक्ष विभाजन) प्राप्त होती है। यदि विभिन्न प्रतिभागियों की अलग-अलग पात्रताएँ हैं (उदाहरण के लिए, एक साझेदारी में जहाँ प्रत्येक भागीदार ने एक अलग राशि का निवेश किया है), जिससे निष्पक्षता मानदंड को तदनुसार अनुकूलित किया जाना चाहिए। विभिन्न अधिकारों के साथ आनुपातिक केक-कटिंग देखें।
अतिरिक्त आवश्यकताएं
निष्पक्षता के अतिरिक्त कभी-कभी यह वांछित होता है कि विभाजन पेरेटो ऑप्टिमल हो। अर्थात् कोई अन्य आवंटन किसी दूसरे को खराब किए बिना किसी को उत्कृष्ट नहीं बनाता है। दक्षता शब्द कुशल बाजार के अर्थशास्त्र के विचार से आता है। एक विभाजन जहां एक खिलाड़ी को सब कुछ प्राप्त होता है। इस परिभाषा से ऑप्टिमल है। इसलिए यह स्वयं में एक उचित भाग का आश्वासन भी नहीं देता है। कुशल केक काटने और निष्पक्षता का मूल्य भी देखें।
यथार्थतः विश्व में संभवतः व्यक्तियों को बहुत स्पष्ट अनुमान होता है कि दूसरे खिलाड़ी सामान को कितना महत्व प्रदान करते हैं और वे इसकी बहुत देखरेख करते हैं। ऐसी स्थिति जहां उन्हें एक-दूसरे के मूल्यांकन का सम्पूर्ण ज्ञान प्राप्त होता है। यह गेम थ्योरी द्वारा तैयार किया जा सकता है। आंशिक ज्ञान को मॉडल करना बहुत कठिन होता है। निष्पक्ष विभाजन के व्यावहारिक पक्ष का एक बड़ा भाग ऐसी प्रक्रियाओं का विकास और अध्ययन है। जो इस प्रकार के आंशिक ज्ञान या छोटी त्रुटियों के बाद भी अच्छी प्रकार से कार्य करती हैं।
एक अतिरिक्त आवश्यकता यह है कि निष्पक्ष विभाजन प्रक्रिया एक ट्रुथफुल मैकेनिज्म हो, अर्थात् प्रतिभागियों के लिए उनके वास्तविक मूल्यांकन की रिपोर्ट करने के लिए यह एक प्रमुख रणनीति होनी चाहिए। निष्पक्षता और पारेटो-दक्षता के संयोजन में इस आवश्यकता को पूरा करना सामान्यतः बहुत कठिन होता है।
प्रक्रियाएं
एक निष्पक्ष विभाजन एल्गोरिथम दृश्य डेटा और उनके मूल्यांकन के संदर्भ में खिलाड़ियों द्वारा की जाने वाले कार्यों को सूचीबद्ध करता है। इसकी एक वैध प्रक्रिया यह है कि जो प्रत्येक खिलाड़ी के लिए निष्पक्ष विभाजन की आश्वासन देती है। जो अपने मूल्यांकन के अनुसार तर्कसंगत रूप से कार्य करता है। जहां एक प्रक्रिया एक खिलाड़ी के मूल्यांकन पर निर्भर करती है। जिससे प्रक्रिया उस रणनीति का वर्णन कर रही है। जिसका एक तर्कसंगत खिलाड़ी पालन करेगा। एक खिलाड़ी इस प्रकार कार्य कर सकता है। जैसे कि एक टुकड़े का एक अलग मूल्य था। किन्तु वह संगत होना चाहिए। उदाहरण के लिए यदि एक प्रक्रिया यह वर्णन करती है कि पहला खिलाड़ी केक को दो बराबर भागों में विभाजित करता है। जिससे दूसरा खिलाड़ी एक टुकड़ा चुनता है, जिससे पहला खिलाड़ी यह दावा नहीं कर सकता कि दूसरे खिलाड़ी को अधिक प्राप्त हुआ है।
खिलाड़ी क्या करते हैं:
- निष्पक्ष विभाजन के लिए उनके मानदंड पर सहमत हों।
- एक मान्य प्रक्रिया का चयन करें और उसके नियमों का पालन करें।
यह माना जाता है कि प्रत्येक खिलाड़ी का लक्ष्य उन्हें मिलने वाली न्यूनतम राशि को अधिकतम करना है या दूसरे शब्दों में न्यूनतम राशि प्राप्त करना है।
प्रक्रियाओं को असतत या निरंतर प्रक्रियाओं में विभाजित किया जा सकता है। उदाहरण के लिए एक असतत प्रक्रिया में एक समय में केवल एक व्यक्ति को केक काटने या चिह्नित करना सम्मिलित होगा। निरंतर प्रक्रियाओं में एक खिलाड़ी के चाकू चलने की प्रक्रिया और दूसरे के कहने पर रोक देना आदि जैसी वस्तुएँ सम्मिलित होती हैं। एक अन्य प्रकार की सतत प्रक्रिया में केक के प्रत्येक भाग के लिए व्यक्ति को मूल्य निर्दिष्ट करना सम्मिलित होता है।
निष्पक्ष विभाजन प्रक्रियाओं की सूची के लिए देखें :श्रेणी:निष्पक्ष विभाजन प्रोटोकॉल।
कोई परिमित प्रोटोकॉल (तथापि असीमित हो) तीन या अधिक खिलाड़ियों के बीच एक केक के इन्वे-फ्री विभाजन की आश्वासन प्रदान कर सकता है। यदि प्रत्येक खिलाड़ी को एक जुड़ा हुआ टुकड़ा प्राप्त करना है।[3] उदाहरण के लिए चूंकि यह परिणाम केवल उस कार्य में प्रस्तुत मॉडल पर संचालित होता है और उन स्थितियों के लिए नहीं, जहां एक मध्यस्थ के पास खिलाड़ियों के मूल्यांकन फलनों की सम्पूर्ण जानकारी होती है और इस जानकारी के आधार पर एक विभाजन का प्रस्ताव करता है।[4]
एक्सटेंशन
वर्तमान समय में निष्पक्ष विभाजन के मॉडल को व्यक्तिगत एजेंटों से लेकर एजेंटों के फैमली (पूर्व-निर्धारित समूहों) तक बढ़ाया गया है। समूहों के बीच निष्पक्ष विभाजन देखें।
इतिहास
सोल गारफंकेल के अनुसार केक काटने की समस्या 20वीं सदी के गणित की सबसे महत्वपूर्ण संवृत समस्याओं में से एक थी।[5] जब 1995 में स्टीवन ब्राम्स और एलन डी. टेलर द्वारा ब्रैम-टेलर प्रक्रिया के साथ समस्या का सबसे महत्वपूर्ण रूप अंततः हल किया गया था।
विभाजन करने और चुनाने की उत्पत्ति को लिखित रूप से वर्णित नहीं किया गया था। वस्तुओं के मूल्य को कम कराना और वस्तु विनिमय की संबंधित गतिविधियाँ भी प्राचीन हैं। दो से अधिक लोगों को सम्मिलित करने वाली वार्तालाप भी अधिक सामान्य है। पॉट्सडैम सम्मेलन एक उल्लेखनीय वर्तमान समय का उदाहरण है।
निष्पक्ष विभाजन का सिद्धांत का निर्माण द्वितीय विश्व युद्ध के समय हुआ है। यह पोलैंड के गणितज्ञों, ह्यूगो स्टीनहॉस, ब्रॉनिस्लाव नस्टर और स्टीफन बनाच के एक समूह द्वारा तैयार किया गया था। जो लावोव (तब पोलैंड में) में स्कॉटिश कैफे में प्राप्त होते थे। 1944 में 'अंतिम-मंदक' कहे जाने वाले खिलाड़ियों की किसी भी संख्या के लिए एक आनुपातिक (निष्पक्ष विभाजन) विभाजन तैयार किया गया था। इसका श्रेय स्टीनहॉस द्वारा बनच और नास्टर को दिया गया था। जब उन्होंने अर्थमितीय समाज की बैठक में 17 सितंबर 1947 को वाशिंगटन डी.सी में पहली बार समस्या को सार्वजनिक किया था। उस बैठक में उन्होंने इस प्रकार के विभाजनों के लिए आवश्यक कमी की सबसे छोटी संख्या खोजने की समस्या का भी प्रस्ताव रखा।
इन्वे-फ्री केक काटने के इतिहास के लिए इन्वे-फ्री केक-कटिंग देखें।
लोकप्रिय संस्कृति में
- 17-जानवरों की विरासत पहेली में 17 ऊंटों या हाथी या घोड़ों के निष्पक्ष विभाजन को 1/2, 1/3 और 1/9 के अनुपात में सम्मिलित किया गया है। यह एक प्रचलित गणितीय पहेली है। जिसका अधिकांशतः एक प्राचीन मूल होने का दावा प्रस्तुत किया जाता है। किन्तु इसका पहला प्रलेखित प्रकाशन 18वीं शताब्दी के ईरान में हुआ था।[6]
- Numb3rs सीज़न 3 के एपिसोड "वन आवर" में चार्ली केक काटने की समस्या के विषय में वार्तालाप करता है। जो उस राशि पर संचालित होती है। जो एक अपहरणकर्ता मांग रहा था।
- ह्यूगो स्टीनहॉस ने अपनी पुस्तक मैथमैटिकल स्नैपशॉट्स में निष्पक्ष विभाजन के कई प्रकारों के विषय में उल्लेख किया है। उन्होंने अपनी पुस्तक में कहा है कि फेयर डिवीजन का एक विशेष तीन-व्यक्ति संस्करण 1944 में बेर्देचो में जी. क्रोचमैनी द्वारा तैयार किया गया था और इसका दूसरा संस्करण श्रीमती एल कोट्ट द्वारा तैयार किया गया था।[7]
- मार्टिन गार्डनर और इयान स्टीवर्ट (गणितज्ञ) दोनों ने इस समस्या के विषय में कई भागों वाली पुस्तकें प्रकाशित की हैं।[8][9] मार्टिन गार्डनर ने समस्या का कोर डिवीजन फॉर्म प्रस्तुत किया। इयान स्टीवर्ट ने अमेरिकी वैज्ञानिक और नए वैज्ञानिक में अपने लेखों के साथ निष्पक्ष विभाजन की समस्या को प्रचलित बनाया है।
- डायनासोर कॉमिक्स की पट्टी केक काटने की समस्या पर आधारित है।[10]
- इजरायली फिल्म सेंट क्लारा (फिल्म) में एक रूसी अप्रवासी इजरायली गणित शिक्षक से पूछता है कि एक गोलाकार केक को 7 लोगों के बीच निष्पक्ष रूप से कैसे बांटा जा सकता है? उसका उत्तर इसके मध्य से 3 सीधे कट के चिन्ह बनाना है। जिससे 8 बराबर टुकड़ों में विभाजित किया जा सके। चूंकि केवल 7 व्यक्ति उपस्थित हैं। इसमें साम्यवाद की भावना में एक टुकड़ा त्याग दिया जाना चाहिए।
यह भी देखें
- ऑनलाइन निष्पक्ष विभाजन निष्पक्ष विभाजन का एक प्रकार है। जिसमें विभाजन के समय सभी आइटम या एजेंट उपलब्ध नहीं होते हैं।
- इक्विटी (अर्थशास्त्र)
- अंतर्राष्ट्रीय व्यापार
- न्याय (अर्थशास्त्र)
- बैग समस्या
- निष्पक्ष विभाजन में अनसुलझी समस्याओं की सूची
- नैश मध्यस्थता का खेल
- पिज्जा प्रमेय
- निष्पक्षता की मूल्य
- स्पाईट (गेम थ्योरी)
- सामरिक निष्पक्ष विभाजन
- एंटीकॉमन्स की त्रासदी
- सामान्य व्यक्तियों की त्रासदी
संदर्भ
- ↑ Aumann, Robert J.; Maschler, Michael (1985). "तल्मूड से दिवालियेपन की समस्या का खेल सैद्धांतिक विश्लेषण" (PDF). Journal of Economic Theory. 36 (2): 195–213. doi:10.1016/0022-0531(85)90102-4. Archived from the original (PDF) on 2006-02-20.
- ↑ Yaari, M. E.; Bar-Hillel, M. (1984). "न्यायोचित विभाजन करने पर". Social Choice and Welfare. 1: 1. doi:10.1007/BF00297056. S2CID 153443060.
- ↑ Stromquist, Walter (2008). "एन्वी-फ्री केक डिवीजनों को परिमित प्रोटोकॉल द्वारा नहीं पाया जा सकता है". The Electronic Journal of Combinatorics. 15. doi:10.37236/735. Retrieved October 26, 2022.
- ↑ Aumann, Yonatan; Dombb, Yair (2010). "कनेक्टेड पीसेज के साथ फेयर डिवीजन की दक्षता". Internet and Network Economics. International Workshop on Internet and Network Economics. Springer. pp. 26–37. doi:10.1007/978-3-642-17572-5_3.
- ↑ Sol Garfunkel. More Equal than Others: Weighted Voting. For All Practical Purposes. COMAP. 1988
- ↑ Ageron, Pierre (2013). "Le partage des dix-sept chameaux et autres arithmétiques attributes à l'immam 'Alî: Mouvance et circulation de récits de la tradition musulmane chiite" (PDF). Revue d'histoire des mathématiques (in français). 19 (1): 1–41.; see in particular pp. 13–14.
- ↑ Mathematical Snapshots. H.Steinhaus. 1950, 1969 ISBN 0-19-503267-5
- ↑ aha! Insight. Martin. Gardner, 1978. ISBN 978-0-7167-1017-2
- ↑ How to cut a cake and other mathematical conundrums. Ian Stewart. 2006. ISBN 978-0-19-920590-5
- ↑ "Dinosaur Comics!".
पाठ्य पुस्तकें
- Young, Peyton H. (1995). Equity: in theory and practice. Princeton University Press.
- Brams, Steven J.; Taylor, Alan D. (1996). Fair division: from cake-cutting to dispute resolution. Cambridge University Press. ISBN 0-521-55644-9.
- Robertson, Jack; Webb, William (1998). Cake-Cutting Algorithms: Be Fair If You Can. Natick, Massachusetts: A. K. Peters. ISBN 978-1-56881-076-8. LCCN 97041258. OL 2730675W.
- Herve Moulin (2004). Fair Division and Collective Welfare. Cambridge, Massachusetts: MIT Press. ISBN 9780262134231.
- Barbanel, Julius B.; with an introduction by Alan D. Taylor (2005). The geometry of efficient fair division. Cambridge: Cambridge University Press. doi:10.1017/CBO9780511546679. ISBN 0-521-84248-4. MR 2132232.
{{cite book}}
: CS1 maint: multiple names: authors list (link) Short summary is available at: Barbanel, J. (2010). "A Geometric Approach to Fair Division". The College Mathematics Journal. 41 (4): 268. doi:10.4169/074683410x510263. - Steven J. Brams (2008). Mathematics and Democracy: Designing Better Voting and Fair-Division Procedures. Princeton, NJ: Princeton University Press. ISBN 9780691133218.
सर्वेक्षण लेख
- विन्सेंट पी. क्रॉफोर्ड (1987). फेयर डिवीजन, द न्यू पालग्रेव: ए डिक्शनरी ऑफ इकोनॉमिक्स, वी. 2, पीपी. 274-75।
- हैल आर. वेरियन (1987). फेयरनेस, द न्यू पालग्रेव: ए डिक्शनरी ऑफ इकोनॉमिक्स, वी. 2, पीपी. 275-76।
- ब्रायन स्किर्म्स (1996)। सामाजिक अनुबंध का विकास कैम्ब्रिज यूनिवर्सिटी प्रेस। ISBN 978-0-521-55583-8
- Hill, T.P. (2000). "उचित हिस्सा पाने के लिए गणितीय उपकरण". American Scientist. 88 (4): 325–331. Bibcode:2000AmSci..88..325H. doi:10.1511/2000.4.325. S2CID 221539202.
- Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016). Handbook of Computational Social Choice (in English). Cambridge University Press. ISBN 9781107060432. (free online version), अध्याय 11–13।
- फेयर डिवीजन क्रिश्चियन क्लैमलर द्वारा - ग्रुप डिसिजन एंड नेगोशिएशन पीपी 183-202 की हैंडबुक में।
- केक-कटिंग: फेयर डिवीजन ऑफ डिविजिबल गुड्स क्लाउडिया लिंडनर और जॉर्ग रोथ द्वारा - अर्थशास्त्र और संगणना में पीपी 395-491 .
- अविभाज्य वस्तुओं का निष्पक्ष विभाजन जेरोम लैंग और जोर्ग रोथ द्वारा - अर्थशास्त्र और संगणना पीपी 493-550 में।
बाहरी संबंध
- Fair Division from the Discrete Mathematics Project at the University of Colorado at Boulder.
- Fair Division: Method of Markers
- Fair Division: Method of Sealed Bids