वोटिंग एल्गोरिदम "सभी को खुश करें" क्या है?

Question

मैं एक मतदान एल्गोरिदम की तलाश में हूं जो बहुमत के वोटों और वोटों की संख्या के आधार पर विजेताओं को चुनता है।

वास्तविक जीवन उदाहरण:

हमारी कंपनी एक अनाज बार भी है। हमारे पास 3 अलग-अलग अनाज के लिए कमरा है। हम हमारे कर्मचारियों को यह आदेश देना चाहते हैं कि वे कौन से अनाज चाहते हैं।

हम कड़ाई से लोकप्रियता के आधार पर शीर्ष 3 विजेताओं लेने के लिए, क्योंकि वहाँ के कर्मचारियों के एक अल्पसंख्यक जो केवल (जो भी कारण के लिए) 1 विशेष अनाज खा सकते हैं हो सकता है और हम उन्हें देना चाहते हैं नहीं करना चाहती जितना संभव हो सके विशेष भत्ता।

निम्नलिखित वोट परिणाम देखते हुए, यहां परिणाम हैं जिन्हें हम एल्गोरिदम हमें देना चाहते हैं।

मैं एक एल्गोरिथ्म कि रैंकिंग के इस प्रकार करता है के लिए देख रहा हूँ। यदि आप कम से कम जो कुछ मैं ढूंढ रहा हूं उसका नाम प्रदान कर सकता हूं तो यह एक बड़ी मदद होगी क्योंकि मैं इसे बेहतर खोज सकता हूं। :)

धन्यवाद!

Answer 1

आप Hall's marriage theorem और/या assignment problem के सामान्यीकरण पर विचार करना चाह सकते हैं।

विचार इस मानदंड के लिए व्यक्ति p और अनाज c के बीच एक बढ़त के साथ एक द्विपक्षीय ग्राफ बनाने के लिए जहां नोड लोगों और अनाज कर रहे हैं, अगर pc के लिए वोट दिया है।लक्ष्य 3 अनाज चयन करने के लिए ऐसी है कि ग्राफ सभी अन्य अनाज को हटाने से उत्पन्न है

1. जुड़ा हुआ है, और

2. न्यूनतम/औसत अधिकतम (हर किसी चयनित अनाज के कम से कम एक खा जाएगा) प्रत्येक व्यक्ति की डिग्री

आप इसके बजाय किसी Maximum Coverage Problem के रूप में इस के बारे में सोच सकता है (मिनट/औसत खुशी अधिकतम)। इस मामले में, आपने C1,C2,...,Cm सेट किया है जहां Ci उन लोगों का समूह है जो अनाज i पसंद करते हैं। आप उदाहरण के लिए, तालिका में सूचीबद्ध क्रम में अनाज और लोगों लेने, आप

C1 = {1,5} 
C2 = {2} 
C3 = {1,4,5} 
C4 = {3,5} 

n, लोगों की संख्या हो ताकि Ci{1,2,...,n} के एक सबसेट है चलो की है। लक्ष्य k सेट्स को ढूंढना है ताकि संघ की कार्डिनालिटी अधिकतम हो। यदि एकाधिक समाधान मौजूद हैं, तो उस व्यक्ति को चुनें जो चौराहे की कार्डिनालिटी को कम करता है (उस राशि को कम करता है जिसके द्वारा एक व्यक्ति पर हावी होता है) या कम से कम लगातार तत्व दोहराया जाता है (कम से कम खुश व्यक्ति की खुशी को अधिकतम करता है) को अधिकतम करता है।

इस उदाहरण के लिए, सबसे छोटा k जिसके लिए सभी तत्व शामिल हैं k=3 और यह अद्वितीय समाधान C2,C3,C4 देता है।

हालांकि आप इसे देखते हैं, आपके पास एनपी-समस्या है, लेकिन उन्हें हल करने के लिए ज्ञात एल्गोरिदम हैं (संदर्भों के लिए विकिपीडिया लेख देखें)।

Answer 2

कोई भी सही मतदान प्रणाली नहीं है - http://en.wikipedia.org/wiki/Arrow%27s_impossibility_theorem देखें। http://en.wikipedia.org/wiki/Range_voting सहित नियमों को झुकाकर इसे पाने के कई प्रयास किए गए हैं।

रेंज वोटिंग के करीब एक विचार सभी को 12 वोट देना है और उन्हें उनकी इच्छानुसार वितरित करने की अनुमति देना है। अपने उदाहरण को देखते हुए, यदि आप मानते हैं कि जिन लोगों के पास एकाधिक विकल्प हैं, वे 12 वोटों को समान रूप से वितरित करते हैं - 12x1 या 6x2 या 4x3 या 3x4 - तो मुझे लगता है कि आपको वांछित परिणाम मिलते हैं, लकी आकर्षण के साथ कुल 10 वोट और बाकी सब कुछ इससे अधिक हो रही है।

Answer 3

अनाज की संख्या कम है, तो आप अपनी समस्या एक सबसेट कवर समस्या और जानवर बल के रूप में अपनी राह तलाशने क्या विन्यास सबसे "happyness"

var max_happyness = -INF 
for every subset {c1, c2, c3} of C: 
    max_hapyness = max(max_happyness, happyness(i1,i2,i3)) 

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

पेशेवर: यदि आप एक खुशहाली समारोह को परिभाषित कर सकते हैं, तो यह गारंटीकृत सर्वोत्तम परिणाम देता है।

विपक्ष: आपको एक खुशी समारोह को परिभाषित करने में सक्षम होना चाहिए।