Кіріспе

Реттелген таңдау дауыс беру жүйелерінде мүмкін емес нәтиже

Гиббард-Саттертвейт теоремасы – дауыс беру теориясындағы теорема. Оны алғаш рет философ Майкл Даммет және математик Робин Фаркхарсон 1961 жылы болжады, ал кейін философ Аллан Гиббард 1973 жылы және экономист Марк Саттертвейт 1975 жылы тәуелсіз түрде дәлелдеді. Ол бір жеңімпазды таңдайтын детерминистік реттік сайлау жүйелерін қарастырады және кез келген дауыс беру ережесі үшін келесі үш нәрсенің кем дегенде біреуі орындалуы керек деп мәлімдейді:

Ереже диктаторлық, яғни жеңімпазды таңдай алатын ерекше сайлаушы бар; немесе
Ереже мүмкін нәтижелерді тек екі нұсқаға дейін шектейді; немесе
Ереже тактикалық дауыс беруға жағдай жасайды: кейбір жағдайларда сайлаушының шын ниетімен берген дауысы оның пікірін тиімді қорғай алмайды. Бұл теореманың қолданылу аясы реттік дауыс берумен шектеледі. Ол баллмен дауыс беру немесе STAR дауыс беру сияқты кардиналдық дауыс беру жүйелеріне, сондай-ақ бірнеше жеңімпазды дауыс беруға, детерминистік емес әдістерге немесе дауыс берусіз шешім қабылдау механизмдеріне қолданылмайды. Гиббард теоремасы одан да жалпы және ординалдық емес дауыс беру сияқты, коллективтік шешім қабылдау процестерін қамтиды. Гиббард теоремасы кардиналдық әдістердің міндетті түрде екі үміткердің салыстырмалы бағасын өзгертуге ынталандыратынын білдірмейді. Гиббардтың 1978 жылғы теоремасы және Хайланд теоремасы одан да жалпы және осы нәтижелерді детерминистік емес процестерге дейін кеңейтеді, онда нәтиже ішінара жаққа байланысты болуы мүмкін; ал Дугган-Шварц теоремасы осы нәтижелерді көп жеңімпаз сайлау жүйелеріне дейін кеңейтеді.

Ресми мәлімдеме

Альтернативалар жиынтығы (шекті деп есептеледі) болсын, олар үміткерлер деп аталады, бірақ міндетті түрде адамдар емес: олар белгілі бір мәселе бойынша бірнеше мүмкін шешімдер де болуы мүмкін. Сайлаушылар жиынтығын арнайы белгілейміз. Альтернативалар бойынша қатаң әлсіз реттелулер жиынтығы болсын: осы жиынтықтың әрбір мүшесі сайлаушының қалауын көрсете алады, онда сайлаушы кейбір альтернативалардың ретіне қатысты бейжай болуы мүмкін. Дауыс беру қағидасы – функция, оның кірісі қалаулардың профилі, ал нәтижесі жеңімпаз үміткерді анықтау. Егер бір сайлаушы өз дауыс бюллетенін басқа бюллетеньмен ауыстыру арқылы өзі қалайтын нәтижеге қол жеткізе алатын профиль болса, онда осы қағида манипуляцияға бейім деп айтамыз. -тің бейнесі деп, сайлаудың мүмкін нәтижелер жиынтығын атаймыз. Мысалы, -тің кемінде үш мүмкін нәтижесі бар деу үшін, -тің кардиналдығы 3 немесе одан көп болуы керек. Егер диктатор болып табылатын сайлаушы болса және жеңімпаз альтернатива басқа сайлаушылардың қалауларына қарамастан, оның ең жақсы көретін альтернативасы болса, онда осы қағида диктаторлық деп аталады. Егер диктатордың бірнеше бірдей ең жақсы көретін альтернативалары болса, онда жеңімпаз альтернатива олардың бірі болады.

Қарсы мысалдар мен заңдағы ойық жерлер

Гиббард-Саттертуэйт теоремасының шарттары орындалмаған жағдайларда, түрлі "қарсы мысалдар" кездеседі.

Кардиналдар дауысы

Үш үміткерден сайлауды ұпаймен дауыс беру арқылы қарастырайық. Дауыс беруші үшін ең жақсы үміткерге ең жоғары ұпай, ал ең нашар үміткерге ең төмен ұпай беру әрқашан тиімді. Содан кейін, дауыс беруші ортаңғы үміткерге қандай ұпай бергеніне қарамастан, ол әрқашан бірінші және соңғы ұпайлардың арасында (қатаң емес) болады; бұл дауыс берушінің ұпай бюллетені оның шын рейтингісімен әлсіз үйлесімді екенін білдіреді. Дегенмен, нақты тиімді ұпай, Гиббард теоремасы көрсеткендей, басқа дауыс беру бюллетеньдеріне байланысты болуы мүмкін.

Бірнеше рет жүргізілген диктатура

Серіктік диктатура былай анықталады. Егер 1 сайлаушыда бірегей ең жақсы көретін үміткер болса, онда сол үміткер сайланады. Әйтпесе, мүмкін нәтижелер ең көп ұнаған үміткерлермен шектеледі, ал қалған үміткерлер тізімнен шығарылады. Содан кейін 2-ші сайлаушының дауысы қарастырылады: егер тізімнен шығарылмағандардың арасында бірегей ең жақсы көретін үміткер болса, онда сол үміткер сайланады. Әйтпесе, мүмкін нәтижелер тізімі тағы да қысқартылады, осылай жалғаса береді. Барлық дауыстар қарастырылғаннан кейін бірнеше үміткер тізімнен шығарылмаған болып қалса, онда кез келген теңдікті шешу ережесі қолданылады. Бұл дауыс беру ережесін манипуляциялауға болмайды: сайлаушы өзінің шын ниеттерін білдіруі әрқашан тиімді. Ол сондай-ақ диктаторлық болып табылады, ал оның диктаторы – 1-ші сайлаушы: жеңімпаз әрқашан осы сайлаушының ең жақсы көретін үміткері болады немесе, егер бірнеше ең жақсы көретін үміткерлер болса, олардың арасынан таңдалады.

Қарапайым көпшілік дауыс беру

Егер екі ғана мүмкін нәтиже болса, дауыс беру ережесі диктаторлық болмай-ақ, манипуляцияға төтеп бере алады. Мысалы, қарапайым көпшілік дауыс беруде: әрбір сайлаушы өзінің ең қолайлы нұсқасына 1 ұпай, ал қалғандарына 0 ұпай береді, және ең көп ұпай жинаған нұсқа жеңімпаз деп жарияланады. (Егер екі нұсқа да бірдей ұпай санына жетсе, теңдік кездейсоқ емес, бірақ белгілі бір тәртіппен шешіледі, мысалы, нәтиже жеңіске ие болады.) Бұл дауыс беру ережесімен манипуляция жасау мүмкін емес, себебі сайлаушы өзінің шын ниетін білдіргенде әрқашан артық пайда көреді; және ол әсте диктаторлық емес. Көптеген басқа ережелер де манипуляцияға төтеп береді және диктаторлық емес: мысалы, егер бір нұсқа дауыс берушілердің үштен екісінің қолдауын алса, ал қалған жағдайда екінші нұсқа жеңіске ие болады делік.

Қорытынды

Енді екі үміткердің арасында сайлаушының бей-жай бола алмайтынын болжайтын жағдайды қарастырамыз. Біз кандидатар жиыны бойынша қатаң тәртіптемелер жиынтығын белгілейміз және қатаң дауыс беру ережесін функция ретінде анықтаймыз. Мүмкін нәтижелердің, манипуляцияға болатын және диктаторлық сипаттамалары осы аяқта табиғи түрде бейімделеді. Қатаң дауыс беру ережесі үшін Гиббард-Саттертвейт теоремасының керісі дұрыс. Шындығында, қатаң дауыс беру ережесі диктаторлық болып табылады, егер және тек қана ол әрқашан мүмкін нәтижелердің ішінде диктатор ең жақсы көретін кандидатын таңдаса; әсіресе, ол басқа сайлаушылардың бюллетеньдеріне тәуелді емес. Осының салдарынан, оны манипуляциялау мүмкін емес: диктатор өзінің адал дауысымен толық қорғалған, ал басқа сайлаушылардың нәтижеге әсері жоқ, сондықтан олардың адал дауыс беруден ауытқуға қызығушылығы жоқ. Осылайша, біз келесі тепе-теңдікке жетеміз. Теоремада да, оның қорытындысында да, кез келген баламаның сайлануы мүмкін деген болжам қажет емес. Тек олардың кем дегенде үшеуі жеңіске жетуі мүмкін деп есептеледі, яғни дауыс беру ережесінің мүмкін нәтижелері болып табылады. Кейбір басқа баламалар ешқандай жағдайда сайлануы мүмкін емес: теорема мен қорытынды бәрібір қолданылады. Дегенмен, бұл тұжырым кейде аздап өзгеше түрінде ұсынылады: ережеде кем дегенде үш мүмкін нәтиже бар деген болжамның орнына, кейде жиынтықта кем дегенде үш элемент бар екені және дауыс беру ережесі толық екені, яғни әр балама мүмкін нәтиже болып табылады деп есептеледі. Кейде толықтық болжамының орнына, ереже бірауыздан деп есептеледі, яғни егер барлық сайлаушылар бір кандидатты жақсы көрсе, онда ол міндетті түрде сайлануы керек.

Дәлелдің сызбасы

Гиббард-Саттертвейт теоремасы әлеуметтік рейтингтік функцияларға қатысты Ароудың мүмкін еместік теоремасын қолдану арқылы дәлелденуге болады. Біз кейбір дауыс беру ережесі Парето тиімді деп есептелетін қарапайым жағдайда дәлелдеудің жоспасын ұсынамыз. Әлеуметтік рейтингтік функцияны былай құруға болады: функция, егер дауыс берушілердің басымдықтарындағы және жаңа басымдықтарды құрады, онда осы екеуін барлық дауыс берушілердің басымдықтарының жоғары жағына жылжытады. Содан кейін, функция таңдайды ма, әлде екіншісін таңдай ма, соны анықтайды. Егер функция манипуляцияға төтеп беретін және диктаторлық емес болса, онда ол маңызды емес баламалардың тәуелсіздігін қанағаттандырады. Ароудың мүмкін еместік теоремасы үш немесе одан көп балама болған жағдайда, мұндай функция диктатура болуы керек дейді. Демек, мұндай дауыс беру ережесі де диктатура болуы керек. Кейінірек зерттеушілер дәлелдеудің басқа түрлерін әзірледі.

Тарих

Дауыс берудің стратегиялық аспектісін 1876 жылы әлеуметтік таңдау теориясының негізін қалаушы Чарльз Доджсон, сондай-ақ Льюис Кэрролл атап көрсеткен. Оның (нақты бір дауыс беру жүйесі туралы) сөзін Данкан Блэк танымал етті: «Бұл дауыс беру принципі сайлауды сайлаушылардың ынтасын шын бағалаудан гөрі, дағдыға негізделген ойынға айналдырады». 1950 жылдары Робин Фаркхарсон дауыс беру теориясы бойынша маңызды мақалалар жариялады. Майкл Даметпен бірлескен мақаласында ол кем дегенде үш нәтижесі бар детерминистік дауыс беру ережелерінде тікелей тактикалық дауыс берудің мүмкін еместігін болжады. Бұл болжамды кейіннен Алан Гиббард пен Марк Саттертвейт тәуелсіз түрде дәлелдеді. 1973 жылғы мақаласында Гиббард 1951 жылғы Ароудың мүмкін емес теоремасын қолданып, қазір бізге Гиббард теоремасы ретінде белгілі нәтижені дәлелдеді.

Маңыздылық

Гиббард-Саттертвейт теоремасы көбінесе дауыс беру жүйелері туралы нәтиже ретінде ұсынылады, бірақ оны шешім қабылдау ережелерінің кеңірек класын қамтитын механизмді жобалаудың маңызды нәтижесі деп қарастыруға болады. Ноам Нисан бұл қатынасты былай түсіндіреді: GS теоремасы ынталандыруға сәйкес әлеуметтік таңдау функцияларын құруға деген кез келген үмітті жоққа шығарады. Механизмді жобалау саласының барлығы осы мүмкін емес нәтижеден қашуға, модельде әртүрлі өзгерістер енгізу арқылы тырысады. Осы "қашу жолдарының" негізгі идеясы – олар рейтингтік дауыс беруден әлдеқайда кең механизмдер класына мүмкіндік береді, бұл Ароудың мүмкін емес теоремасынан қашу жолдарына ұқсас.