Dodgsons usuli - Dodgsons method - Wikipedia

Qismi Siyosat turkumi
Saylov tizimlari
Rangli ovoz berish qutisi.svg Siyosat portali

Dodgson usuli bu saylov tizimi sifatida tanilgan muallif, matematik va mantiqchi Charlz Dodgson tomonidan taklif qilingan Lyuis Kerol. Usulini kengaytirishdir Kondorset usuli nomzodlarni Kondorset g'olibi topilguncha almashtirish orqali. G'olib minimal miqdordagi svoplarni talab qiladigan nomzod hisoblanadi. Dodgson ushbu ovoz berish sxemasini 1876 yilda yozgan "Ikki martadan ortiq masalalar bo'yicha ovoz olish usuli" nomli asarida taklif qilgan. Butun son berilgan k va saylov, bu shunday To'liq emas nomzod Kondorset g'olibiga aylanishi mumkinligini aniqlash k almashtirishlar.

Tavsif

Dodgson uslubida har bir saylovchi barcha nomzodlarning buyurtma qilingan ro'yxatini o'z xohishiga ko'ra (yaxshidan yomongacha) taqdim etadi. G'olib nomzod sifatida aniqlanadi, unga har bir saylov byulletenida (barcha nomzodlar ustiga qo'shilgan) minimal juftlik almashinuvini amalga oshirishimiz kerak. Kondorets g'olibi. Xususan, agar allaqachon mavjud bo'lsa Kondorets g'olibi, ular saylovda g'alaba qozonishadi.

Qisqasi, biz ovoz berish profilini minimal darajada topishimiz kerak Kendall Tau masofasi Kondorset g'olibiga ega bo'lgan yozuvdan; keyin, Condorcet g'olibi g'olib deb e'lon qilinadi. G'olibni yoki hatto nomzodning Dodgson hisobini hisoblash (ushbu nomzod g'olib bo'lishi uchun zarur bo'lgan svoplar soni) Qattiq-qattiq muammo [1] dan kamaytirish orqali To'liq qopqoq 3-to'plamlar (X3C) tomonidan.[2]

Adabiyotlar

  1. ^ Bartholdi, J .; Tovey, C. A .; Nayrang, M. A. (1989 yil aprel). "Saylovda kim g'olib chiqqanligini aniqlash qiyin bo'lgan ovoz berish sxemalari". Ijtimoiy tanlov va farovonlik. 6 (2): 157–165. doi:10.1007 / BF00303169. Maqola faqat to'g'ridan-to'g'ri NP-ning qattiqligini isbotlaydi, ammo qaror muammosi NP-da ekanligi aniq, chunki nomzod va k svoplar ro'yxati berilgan, bu nomzod polinom vaqtida Kondorset g'olibi ekanligini bilib olishingiz mumkin.
  2. ^ Garey, Maykl R.; Jonson, Devid S. (1979). Kompyuterlar va qulaylik. W.H. Freeman Co., San-Frantsisko.