निष्पक्ष विभाजन: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{short description|Problem of sharing resources}} | {{short description|Problem of sharing resources}} | ||
फेयर डिवीजन [[ खेल सिद्धांत | गेम थ्योरी]] में [[संसाधन|संसाधनों]] के एक समुच्चय को कई लोगों के बीच विभाजित करने की समस्या है। जिनके पास उनका अधिकार है, जिससे प्रत्येक व्यक्ति को उनका उचित प्राप्त हो सके। यह समस्या रियल वर्ल्ड सेटिंग | फेयर डिवीजन [[ खेल सिद्धांत | गेम थ्योरी]] में [[संसाधन|संसाधनों]] के एक समुच्चय को कई लोगों के बीच विभाजित करने की समस्या है। जिनके पास उनका अधिकार है, जिससे प्रत्येक व्यक्ति को उनका उचित प्राप्त हो सके। यह समस्या रियल वर्ल्ड सेटिंग में उत्पन्न होती है। जैसे कि इनहेरिटेन्स, साझेदारी विघटन, विवाह-विच्छेद सल्यूशन, इलेक्ट्रॉनिक [[आवृत्ति आवंटन]], हवाई यातायात प्रबंधन और [[पृथ्वी अवलोकन उपग्रह]] का शोषण। यह गणित, [[अर्थशास्त्र]] (विशेष रूप से [[सामाजिक पसंद सिद्धांत|सोशल च्वाइस थ्योरी]] ), [[विवाद समाधान]] आदि में एक सक्रिय अनुसंधान क्षेत्र है। निष्पक्ष विभाजन का केंद्रीय सिद्धांत यह है कि इस प्रकार के विभाजन को खिलाड़ियों द्वारा स्वयं किया जाना चाहिए। संभवतः [[मध्यस्थता]] का उपयोग करते हुए, किन्तु निश्चित रूप से मध्यस्थता नहीं होनी चाहिए। जैसा कि केवल खिलाड़ी ही यथार्थ रूप से जानते हैं कि वे सामानों को कैसे महत्व देते हैं। | ||
आर्किटेपल फेयर डिवीजन [[कलन विधि|एल्गोरिदम]] [[विभाजित करें और चुनें]]। यह प्रदर्शित करता है कि विभिन्न प्रकार के स्वाद वाले दो एजेंट एक केक को इस प्रकार से विभाजित कर सकते हैं कि उनमें से प्रत्येक का मानना है कि उसे सबसे अच्छा टुकड़ा प्राप्त हुआ। फेयर डिवीजन में अनुसंधान को इस प्रक्रिया के विस्तार के रूप में देखा जा सकता है। जो कि कॉम्प्ले्क्स सेटिंग के लिए अधिक कठिन होती है। | आर्किटेपल फेयर डिवीजन [[कलन विधि|एल्गोरिदम]] [[विभाजित करें और चुनें]]। यह प्रदर्शित करता है कि विभिन्न प्रकार के स्वाद वाले दो एजेंट एक केक को इस प्रकार से विभाजित कर सकते हैं कि उनमें से प्रत्येक का मानना है कि उसे सबसे अच्छा टुकड़ा प्राप्त हुआ। फेयर डिवीजन में अनुसंधान को इस प्रक्रिया के विस्तार के रूप में देखा जा सकता है। जो कि कॉम्प्ले्क्स सेटिंग के लिए अधिक कठिन होती है। | ||
| Line 44: | Line 44: | ||
इन व्यक्तिपरक मूल्य कार्यों के आधार पर निष्पक्ष विभाजन के लिए व्यापक रूप से उपयोग किए जाने वाले कई मानदंड हैं। इनमें से कुछ एक दूसरे के साथ संघर्ष करते हैं। किन्तु अधिकाशतः उन्हें जोड़ा जा सकता है। यहां वर्णित मानदंड केवल तभी हैं, जब प्रत्येक खिलाड़ी समान राशि का अधिकारी सिद्ध होता हो: | इन व्यक्तिपरक मूल्य कार्यों के आधार पर निष्पक्ष विभाजन के लिए व्यापक रूप से उपयोग किए जाने वाले कई मानदंड हैं। इनमें से कुछ एक दूसरे के साथ संघर्ष करते हैं। किन्तु अधिकाशतः उन्हें जोड़ा जा सकता है। यहां वर्णित मानदंड केवल तभी हैं, जब प्रत्येक खिलाड़ी समान राशि का अधिकारी सिद्ध होता हो: | ||
* एक [[आनुपातिक विभाजन]] का अर्थ है कि प्रत्येक व्यक्ति को अपने स्वयं के मूल्य | * एक [[आनुपातिक विभाजन]] का अर्थ है कि प्रत्येक व्यक्ति को अपने स्वयं के मूल्य फलन के अनुसार कम से कम उसका उचित भाग प्राप्त होता है। उदाहरण के लिए यदि तीन व्यक्ति एक केक बांटते हैं। जिससे प्रत्येक को कम से कम एक तिहाई अपने स्वयं के मूल्यांकन से मिलता है। अर्थात् प्रत्येक 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 से अधिक | * एक [[सुपर-आनुपातिक विभाजन]] वह होता है, जहां प्रत्येक खिलाड़ी को 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|[[पॉट्सडैम सम्मेलन]] द्वारा विभाजित बर्लिन]]वास्तविक दुनिया में कभी-कभी लोगों को बहुत सटीक अंदाजा होता है कि दूसरे खिलाड़ी सामान को कितना महत्व देते हैं और वे इसकी बहुत परवाह करते हैं। मामला जहां उन्हें एक-दूसरे के मूल्यांकन का पूरा ज्ञान है, गेम थ्योरी द्वारा तैयार किया जा सकता है। आंशिक ज्ञान को मॉडल करना बहुत कठिन है। निष्पक्ष विभाजन के व्यावहारिक पक्ष का एक बड़ा हिस्सा ऐसी प्रक्रियाओं का विकास और अध्ययन है जो इस तरह के आंशिक ज्ञान या छोटी गलतियों के बावजूद अच्छी तरह से काम करती हैं। | ||
एक अतिरिक्त आवश्यकता यह है कि निष्पक्ष विभाजन प्रक्रिया एक सत्य तंत्र हो, | एक अतिरिक्त आवश्यकता यह है कि निष्पक्ष विभाजन प्रक्रिया एक सत्य तंत्र हो, अर्थात् प्रतिभागियों के लिए उनके वास्तविक मूल्यांकन की रिपोर्ट करने के लिए यह एक प्रमुख रणनीति होनी चाहिए। निष्पक्षता और पारेटो-दक्षता के संयोजन में इस आवश्यकता को पूरा करना आमतौर पर बहुत कठिन होता है। | ||
== प्रक्रियाएं == | == प्रक्रियाएं == | ||
एक उचित विभाजन एल्गोरिथम दृश्य डेटा और उनके मूल्यांकन के संदर्भ में खिलाड़ियों द्वारा की जाने वाली कार्रवाइयों को सूचीबद्ध करता है। एक वैध प्रक्रिया वह है जो प्रत्येक खिलाड़ी के लिए उचित विभाजन की | एक उचित विभाजन एल्गोरिथम दृश्य डेटा और उनके मूल्यांकन के संदर्भ में खिलाड़ियों द्वारा की जाने वाली कार्रवाइयों को सूचीबद्ध करता है। एक वैध प्रक्रिया वह है जो प्रत्येक खिलाड़ी के लिए उचित विभाजन की आश्वासन देती है जो अपने मूल्यांकन के अनुसार तर्कसंगत रूप से कार्य करता है। जहां एक कार्रवाई एक खिलाड़ी के मूल्यांकन पर निर्भर करती है, प्रक्रिया उस [[रणनीति]] का वर्णन कर रही है जिसका एक तर्कसंगत खिलाड़ी पालन करेगा। एक खिलाड़ी इस तरह कार्य कर सकता है जैसे कि एक टुकड़े का एक अलग मूल्य था किन्तु वह सुसंगत होना चाहिए। उदाहरण के लिए यदि एक प्रक्रिया कहती है कि पहला खिलाड़ी केक को दो बराबर भागों में काटता है जिससे दूसरा खिलाड़ी एक टुकड़ा चुनता है, जिससे पहला खिलाड़ी यह दावा नहीं कर सकता कि दूसरे खिलाड़ी को अधिक मिला। | ||
खिलाड़ी क्या करते हैं: | खिलाड़ी क्या करते हैं: | ||
| Line 79: | Line 79: | ||
उचित विभाजन प्रक्रियाओं की सूची के लिए, देखें :श्रेणी:उचित विभाजन प्रोटोकॉल। | उचित विभाजन प्रक्रियाओं की सूची के लिए, देखें :श्रेणी:उचित विभाजन प्रोटोकॉल। | ||
कोई परिमित प्रोटोकॉल (भले ही असीमित हो) तीन या अधिक खिलाड़ियों के बीच एक केक के ईर्ष्या-मुक्त विभाजन की | कोई परिमित प्रोटोकॉल (भले ही असीमित हो) तीन या अधिक खिलाड़ियों के बीच एक केक के ईर्ष्या-मुक्त विभाजन की आश्वासन दे सकता है, यदि प्रत्येक खिलाड़ी को एक जुड़ा हुआ टुकड़ा प्राप्त करना है।<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> | ||
Revision as of 11:53, 5 May 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
