Кіріспе

Бір жеңімпаздың сайлау жүйесі Кемены-Янг әдісі - сайлауда ең танымал таңдауларды анықтау үшін реттік бюллетеньдерді және жұптық салыстыруды пайдаланатын сайлау жүйесі. Бұл Кондорце әдісі, өйткені егер Кондорце жеңімпазы болса, ол әрқашан ең танымал таңдау ретінде саналады. Бұл әдіс әр ықтимал реттілік үшін балл береді, онда әр реттілік қай таңдау ең танымал болуы мүмкін екенін, қай таңдау екінші ең танымал болуы мүмкін екенін, қай таңдау үшінші ең танымал болуы мүмкін екенін және тағы басқасын қарастырады. Ең жоғары ұпай алған реті - жеңімпаз, ал жеңімпаз ретідегі бірінші таңдау - ең танымал таңдау. (Қалған жағдайда, байланыстың кез келген деңгейде болуы мүмкін.) Кемены-Янг әдісі Кемены ережесі, VoteFair танымалдылық рейтингісі, ең жоғары ықтималдық әдісі және медиандық қатынас деп те аталады.

Есептеу әдістері мен есептеу күрделілігі

Үміткерлер саны бойынша Кемени Янгтың уақыт полиномиалы бойынша рейтингін есептеу алгоритмі белгісіз және проблема NP қиын немесе 7 сайлаушы (жеке). Есептеу әдістері барша сандарды бағдарламалауға негізделген, кейде секунд ішінде 40 кандидатқа дауыс берудің толық рейтингін есептеуге мүмкіндік беретіндігі туралы хабарланған. Алайда, кейбір 40 кандидат 5 сайлаушы Кеменің кездейсоқ құрылған сайлауы 3 ГГц Pentium компьютерінде 2006 жылы пайдалы уақыт шектеуімен шешілмеді. Кемен Юнг рейтингін есептеу үшін полиномиалдық уақытқа жуықтау схемасы бар, сондай-ақ мұндай рейтингті есептеу үшін O*(2O () уақытпен параметрленген субекспоненциалдық уақыт алгоритмі бар.