الاختيار الاجتماعي الحسابي

📅 آخر تحديث: ٣١ يوليو ٢٠٢٦
✍️ نُشر في: ٣١ يوليو ٢٠٢٦
الموسوعة الحرة

يُعدّ الاختيار الاجتماعي الحسابي ( COMSOC ) مجالًا يقع عند تقاطع نظرية الاختيار الاجتماعي ، وعلوم الحاسوب النظرية ، وتحليل أنظمة الوكلاء المتعددين . [ 1 ] ويتضمن تحليل المشكلات الناجمة عن تجميع تفضيلات مجموعة من الوكلاء من منظور حسابي. وعلى وجه الخصوص، يهتم الاختيار الاجتماعي الحسابي بالحساب الفعال لنتائج قواعد التصويت ، وبالتعقيد الحسابي لأشكال التلاعب المختلفة ، وبالقضايا الناشئة عن مشكلة تمثيل واستنباط التفضيلات في سياقات توافقية.

تحديد الفائز

قد تتضاءل فائدة نظام تصويت معين بشكل كبير إذا استغرق حساب الفائز في الانتخابات وقتًا طويلاً. لذا، من المهم تصميم خوارزميات سريعة قادرة على تقييم قاعدة التصويت عند إدخال أوراق الاقتراع . وكما هو شائع في نظرية التعقيد الحسابي ، تُعتبر الخوارزمية فعّالة إذا استغرقت وقتًا متعدد الحدود . يمكن تقييم العديد من قواعد التصويت الشائعة في وقت متعدد الحدود بطريقة مباشرة (أي، العد)، مثل عد بوردا ، والتصويت بالموافقة ، وقاعدة الأغلبية . أما بالنسبة لقواعد مثل طريقة شولز أو الأزواج المرتبة ، فيمكن استخدام خوارزميات أكثر تعقيدًا لإظهار وقت تشغيل متعدد الحدود. [ 2 ] [ 3 ] مع ذلك، تُعدّ بعض أنظمة التصويت صعبة حسابيًا. [ 4 ] على وجه الخصوص، يُعدّ تحديد الفائز في طريقة كيميني-يونغ ، وطريقة دودجسون ، وطريقة يونغ جميعها مسائل صعبة من نوع NP. [ 4 ] [ 5 ] [ 6 ] [ 7 ] وقد أدى ذلك إلى تطوير خوارزميات تقريبية وخوارزميات قابلة للمعالجة ذات معلمات ثابتة لتحسين الحساب النظري لمثل هذه المسائل. [ 8 ] [ 9 ] [ 10 ]

تمثيل التفضيلات

يُعدّ شكل أوراق الاقتراع التي يستخدمها الناخبون للتعبير عن تفضيلاتهم أحد أهم الفروقات بين قواعد التصويت. وأكثر شكلين شيوعاً هما أوراق الاقتراع بالموافقة وأوراق الاقتراع الترتيبية.

في نظام التصويت بالموافقة، يختار كل ناخب بعض المرشحين الذين يفضلهم. ولا يوجد أي تمييز أو ترتيب هرمي بين المرشحين الذين تمت الموافقة عليهم. وينطبق الأمر نفسه على المرشحين الذين لم تتم الموافقة عليهم. ولذلك، يُطلق على هذا النوع من التصويت اسم التصويت الثنائي . ويُستخدم نظام التصويت بالموافقة، على سبيل المثال، في التصويت القائم على الرضا والتصويت النسبي .

في المقابل، تتطلب الترتيبات الترتيبية من الناخب ترتيب جميع المرشحين من الأفضل إلى الأسوأ. يُستخدم هذا النوع من الاقتراع، على سبيل المثال، في قاعدة بوردا أو في تصويت باكلين .

هناك العديد من أنواع تنسيقات الاقتراع الأخرى الموصوفة في الأدبيات، مثل الرتب المبتورة، أو الاقتراع الثلاثي، أو اقتراع المنفعة الأساسية.

تركز بعض الأبحاث في مجال الاختيار الاجتماعي الحاسوبي على مدى تمثيلية نماذج الاقتراع، وعلى تطوير نماذج اقتراع معبرة وموجزة في الوقت نفسه. ويكتسب هذا الأمر أهمية خاصة في السياقات التوافقية، مثل التصويت متعدد الفائزين .

مواضيع أخرى

حلول البطولات

حل البطولة هو قاعدة تُحدد لكل بطولة مجموعة من الفائزين. وبما أن ملف تعريف التفضيلات يُنشئ بطولة من خلال علاقة الأغلبية ، يُمكن اعتبار كل حل بطولة بمثابة قاعدة تصويت تستخدم فقط معلومات حول نتائج مسابقات الأغلبية الثنائية. [ 11 ] وقد طُرحت العديد من حلول البطولات، [ 12 ] ودرس علماء نظرية الاختيار الاجتماعي الحاسوبي تعقيد مشاكل تحديد الفائز المرتبطة بها. [ 13 ] [ 1 ]

قيود التفضيل

تُعدّ مجالات التفضيل المقيدة، مثل التفضيلات أحادية الذروة أو أحادية التقاطع ، مجالًا هامًا للدراسة في نظرية الاختيار الاجتماعي ، إذ تتجنب التفضيلات في هذه المجالات مفارقة كوندورسيه ، وبالتالي يمكنها تجاوز نتائج الاستحالة مثل نظرية آرو ونظرية جيبارد-ساترثويت . [ 14 ] [ 15 ] [ 16 ] [ 17 ] من منظور حسابي، تُفيد هذه القيود في تسريع مسائل تحديد الفائز، حيث يمكن حساب قواعد الفائز الواحد وقواعد الفائزين المتعددين، التي تُعدّ صعبة حسابيًا، في وقت متعدد الحدود عند هيكلة التفضيلات بشكل مناسب. [ 18 ] [ 19 ] [ 20 ] [ 21 ] من ناحية أخرى، تميل مسائل التلاعب إلى أن تكون سهلة في هذه المجالات، لذا فإنّ آليات الحماية من التلاعب أقل فعالية. [ 19 ] [ 22 ] من المشكلات الحسابية الأخرى المرتبطة بقيود التفضيلات، تحديد متى ينتمي ملف تعريف تفضيلي معين إلى نطاق محدد. يمكن حل هذه المهمة في وقت متعدد الحدود في كثير من الحالات، بما في ذلك التفضيلات أحادية الذروة وأحادية التقاطع، ولكنها قد تكون صعبة بالنسبة للفئات الأكثر عمومية. [ 23 ] [ 24 ] [ 25 ]

انتخابات متعددة الفائزين

بينما تركز معظم قواعد التصويت التقليدية على اختيار فائز واحد، تتطلب العديد من الحالات اختيار عدة فائزين. هذا هو الحال عند انتخاب برلمان ذي عدد محدد من الأعضاء أو لجنة ، مع العلم أنه يمكن أيضًا استخدام قواعد التصويت متعددة الفائزين لاختيار مجموعة من التوصيات أو المرافق أو حزمة مشتركة من العناصر. وقد ركزت الأبحاث في مجال الاختيار الاجتماعي الحاسوبي على تعريف قواعد التصويت هذه، وفهم خصائصها، ودراسة تعقيد مشاكل تحديد الفائز المرتبطة بها. انظر: التصويت متعدد الفائزين .

انظر أيضاً

مراجع

  1. 1 2 براندت، فيليكس؛ كونيتزر، فنسنت؛ إندريس، أولي؛ لانغ، جيروم؛ بروكاسيا، أرييل د. (25-04-2016). دليل الاختيار الاجتماعي الحاسوبي . مطبعة جامعة كامبريدج. ISBN 9781107060432.
  2. ↑ شولز، ماركوس (11 يوليو 2010). "طريقة انتخابية جديدة أحادية الفائز، رتيبة، مستقلة عن الاستنساخ، متناظرة عكسيًا، ومتوافقة مع كوندورسيه". الاختيار الاجتماعي والرفاهية . 36 (2): 267-303 . doi : 10.1007/s00355-010-0475-4 . S2CID 1927244 . 
  3. ↑ بريل، ماركوس؛ فيشر، فيليكس (1 يناير 2012). "ثمن الحياد في طريقة الأزواج المرتبة" . وقائع المؤتمر السادس والعشرين للجمعية الأمريكية للذكاء الاصطناعي . AAAI'12: 1299-1305 .
  4. 1 2 بارتولدي الثالث، ج.؛ توفي، سي. أ.؛ تريك، م. أ. (1989-04-01). "أنظمة التصويت التي يصعب فيها تحديد الفائز في الانتخابات". الاختيار الاجتماعي والرفاهية . 6 (2): 157-165 . doi : 10.1007/BF00303169 . S2CID 154114517 . 
  5. ^ هيماسباندرا، إديث ؛ سباكوفسكي، هولجر؛ فوجل ، يورج (2005-12-16). "تعقيد انتخابات كيميني" . علوم الكمبيوتر النظرية . 349 (3): 382-391 . دوى : 10.1016/j.tcs.2005.08.031 .
  6. ↑ هيماسباندرا، إديث ؛ هيماسباندرا، لين أ.؛ روث، يورغ (1997). "تحليل دقيق لانتخابات دودجسون: نظام التصويت للويس كارول لعام 1876 كامل للوصول المتوازي إلى NP". مجلة ACM . 44 (6): 806-825 . arXiv : cs/9907036 . doi : 10.1145/268999.269002 . S2CID 367623 . 
  7. ↑ روث، يورغ؛ سباكوفسكي، هولغر؛ فوغل، يورغ (2003-06-06). "التعقيد الدقيق لمسألة الفائز في الانتخابات الشابة". نظرية أنظمة الحوسبة . 36 (4): 375-386 . arXiv : cs/0112021 . doi : 10.1007/s00224-002-1093-z . S2CID 3205730 . 
  8. ↑ كاراغيانيس، يوانيس؛ كوفي، جيسون أ.؛ فيلدمان، ميخال ؛ هومان، كريستوفر م.؛ كاكلامانيس، كريستوس؛ كارانيكولاس، نيكوس؛ بروكاسيا، أرييل د.؛ روزنشاين، جيفري س. (2012-08-01). "حول إمكانية تقريب انتخابات دودجسون ويونغ" . الذكاء الاصطناعي . 187 : 31-51 . doi : 10.1016/j.artint.2012.04.004 .
  9. ↑ أيلون، نير؛ شاريكار، موسى؛ نيومان، ألانثا (1 نوفمبر 2008). "تجميع المعلومات غير المتسقة: الترتيب والتجميع". مجلة ACM . 55 (5): 23:1–23:27. doi : 10.1145/1411509.1411513 . S2CID 5674305 . 
  10. ↑ بيتزلر، ناديا؛ فيلوز، مايكل ر.؛ غو، جيونغ؛ نيدرماير، رولف ؛ روزاموند، فرانسيس أ. (23-06-2008). "خوارزميات ذات معلمات ثابتة لدرجات كيميني". في فليشر، رودولف؛ شو، جينهوي (محرران). الجوانب الخوارزمية في المعلومات والإدارة . سلسلة محاضرات في علوم الحاسوب. المجلد 5034. سبرينغر برلين هايدلبرغ. الصفحات 60-71 . CiteSeerX 10.1.1.145.9310 . doi : 10.1007/978-3-540-68880-8_8 . ISBN    9783540688655.
  11. ↑ فيشبورن، ب. (1977-11-01). "دوال الاختيار الاجتماعي لكوندورسيه". مجلة SIAM للرياضيات التطبيقية . 33 (3): 469-489 . doi : 10.1137/0133030 .
  12. ↑ لاسلييه، جان فرانسوا (1997). حلول البطولات والتصويت بالأغلبية . سبرينغر فيرلاغ.
  13. ↑ مون، جون دبليو. (1968-01-01). مواضيع حول البطولات . هولت، راينهارت ووينستون.
  14. ↑ بلاك، دنكان (1948-01-01). " حول منطق اتخاذ القرارات الجماعية". مجلة الاقتصاد السياسي . 56 (1): 23-34 . doi : 10.1086/256633 . JSTOR 1825026. S2CID 153953456 .  
  15. ↑ روثستين، ب. (1990-12-01). "تفضيلات الترتيب المقيدة وقاعدة الأغلبية". الاختيار الاجتماعي والرفاهية . 7 (4): 331-342 . doi : 10.1007/BF01376281 . S2CID 153683957 . 
  16. ↑ آرو، كينيث ج. (26-06-2012). الاختيار الاجتماعي والقيم الفردية . مطبعة جامعة ييل. ISBN 978-0300186987.
  17. ↑ سين، أمارتيا؛ باتانايك، براسانتا ك (1969-08-01). "الشروط الضرورية والكافية للاختيار الرشيد في ظل قرار الأغلبية". مجلة النظرية الاقتصادية . 1 (2): 178-202 . doi : 10.1016/0022-0531(69)90020-9 .
  18. ↑ إلكيند، إديث ؛ لاكنر، مارتن؛ بيترز، دومينيك (2016-07-01). "قيود التفضيل في الاختيار الاجتماعي الحاسوبي: التقدم الأخير" (ملف PDF) . وقائع المؤتمر الدولي الخامس والعشرين حول الذكاء الاصطناعي . IJCAI'16: 4062–4065 .
  19. براندت ، فيليكس؛ بريل، ماركوس؛ هيماسپاندرا، إديث ؛ هيماسپاندرا، لين (1 يناير 2015). " تجاوز الحماية التوافقية: خوارزميات زمنية متعددة الحدود للناخبين ذوي الذروة الواحدة" . مجلة أبحاث الذكاء الاصطناعي . 53 : 439-496 . doi : 10.1613/jair.4647 . hdl : 1802/10425 .
  20. ↑ ن.، بيتزلر؛ أ.، سلينكو؛ ج.، أولمان (2013). "حول حساب التمثيل النسبي الكامل" . مجلة أبحاث الذكاء الاصطناعي . 47 (2013): 475-519 . arXiv : 1402.0580 . Bibcode : 2014arXiv1402.0580B . doi : 10.1613/jair.3896 . S2CID 2839179 . 
  21. ↑ سكاورون، بيوتر؛ يو، لان؛ فاليشيفسكي، بيوتر؛ إلكيند، إديث (2015-03-02). "تعقيد التمثيل النسبي الكامل للدوائر الانتخابية ذات التقاطع الواحد". علوم الحاسوب النظرية . 569 : 43-57 . arXiv : 1307.1252 . doi : 10.1016/j.tcs.2014.12.012 . S2CID 5348844 . 
  22. ↑ فاليشيفسكي، بيوتر؛ هيماسباندرا، إديث ؛ هيماسباندرا، لين أ.؛ روث، يورغ (2011-02-01). "الدرع الذي لم يكن موجودًا قط: المجتمعات ذات التفضيلات أحادية الذروة أكثر عرضة للتلاعب والتحكم". المعلومات والحوسبة . 209 (2): 89-107 . arXiv : 0909.3257 . doi : 10.1016/j.ic.2010.09.001 .
  23. ↑ بيترز، دومينيك (2016-02-25). "التعرف على التفضيلات الإقليدية متعددة الأبعاد". arXiv : 1602.08109 [ cs.GT ].
  24. ↑ دويغنون، جيه بي؛ فالماني، جيه سي (1994-03-01). "خوارزمية زمنية متعددة الحدود لتمثيلات الفتح أحادية البعد" (ملف PDF) . مجلة الخوارزميات . 16 (2): 218-233 . doi : 10.1006/jagm.1994.1010 . hdl : 2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/310087 .
  25. ↑ إسكوفيه، برونو؛ لانغ، جيروم؛ أوزتورك، ميلتيم (1 يناير 2008). "الاتساق أحادي الذروة وتعقيده" . وقائع مؤتمر ECAI 2008: المؤتمر الأوروبي الثامن عشر للذكاء الاصطناعي : 366-370 . ISBN 9781586038915.
  • يقدم موقع COMSOC الإلكتروني مجموعة من المواد المتعلقة بالاختيار الاجتماعي الحاسوبي، مثل ورش العمل الأكاديمية، وأطروحات الدكتوراه، وقائمة بريدية.