Тема 7. Задачи группового выбора (Лекции и семинары (материалы к занятиям))

Тема 7. Задачи группового выбора.На практике часто встречаются ситуации, когда имеются несколько ЛПР,каждое из которых имеет свои предпочтения на одном и том же множестве Aсравниваемых вариантов, и на основе этих индивидуальных предпочтенийнеобходимо выработать групповое (коллективное) предпочтение.Например, жюри необходимо распределить места между участникамисоревнования, гражданам страны нужно избрать президента и т.п.Такие задачи принятия решений называются задачами группового выбора,участвующие в них ЛПР называются выборщиками, а сравниваемые варианты –кандидатами.

В каждой такой задаче будем произвольным образом нумероватьвыборщиков числами от 1 до m, а кандидатов обозначать буквами a,b,… и т.д.Процесс построения группового предпочтения называется процедуройголосования, а правила, с помощью которых он производится, называютсяправилами голосования или принципом согласования.Как мы знаем, предпочтения могут задаваться различными способами,например, в виде бинарных отношений предпочтения или с помощью функцийвыбора.Взависимостиоттого,какимобразомзаданыиндивидуальныепредпочтения и в какой форме требуется построить групповое предпочтение,выделяют различные типы задач группового выбора и соответствующие им типыпроцедур голосования.

Рассмотрим из них следующие три типа:1)заданнабор<R1,…,Rm>отношенийиндивидуальногопредпочтения (т.н. профиль индивидуальных предпочтений),групповое предпочтение также требуется построить в видебинарного отношения R (или соответствующего ему строгогоотношения предпочтения P) на множестве кандидатов, такимобразом, R = F(R1,…,Rm) – процедура голосования типа У-У(«упорядочение – упорядочение»);2)задан профиль индивидуальных предпочтений <R1,…,Rm>, агрупповое предпочтение требуется построить в виде выбораC(A) = F(R1,…,Rm)–процедура(«упорядочение – выбор»);голосованиятипаУ-В3)для каждого i-го выборщика задан Ci(A) – его выбор из множествакандидатовA,необходимоC(A) = F(С1(A),…,Cm(A))–построитьпроцедурагрупповойголосованиявыбортипаВ-В(«выбор – выбор»).Рассмотрим процедуры голосования типа У-У. Будем считать, что Riявляются отношениями строгого порядка.Могут применяться следующие принципы согласования:– навязанный принцип согласования (независимо от того, каким бы ни былзадан профиль индивидуальных предпочтений, формируется одно и то жеотношение группового предпочтения);– диктаторский принцип согласования (R = Rj, т.е.

групповое предпочтениеформируетсяизпредпочтенияодногоj-говыборщика,независимоотпредпочтений Ri, i≠j остальных выборщиков);– правило простого большинства: пусть m(a,b) – число выборщиков, длякоторых a предпочтительнее, чем b; m(b,a) – количество выборщиков, длякоторых b предпочтительнее, чем a; отношение группового предпочтениязадается так: a R b ⇔ m(a,b) ≥ m(b,a);– правило тотально мажоритарного большинства: a P b ⇔ m(a,b) ≥ t, гдеt > m/2.Пример 1.Навязанный принцип согласования: нечестные выборы президента, когдазаранее известен результат выборов, независимо от фактического распределенияголосов избирателей.Диктаторский принцип согласования: «мы посовещались и я решил» –принцип принятия решений И.В. Сталина.Правило простого большинства: обычно применяется при принятии законовГосударственной Думой.Правило тотально мажоритарного большинства: ст.105 п.5 Конституции РФ:"...федеральный закон считается принятым, если при повторном голосовании занегопроголосовалонеменеедвухтретейотобщегоГосударственной Думы" (t=2/3).Пример 2.Множество кандидатов A = {a,b}, выборщиков двое.числадепутатовВозможны три предпочтения, задающие частичный порядок на A:R(1) = {<a,a>,<b,b>,<a,b>}R(2) = {<a,a>,<b,b>,<b,a>}R(3) = {<a,a>,<b,b>,<a,b>,<b,a>}Рассмотримвозможныепрофилииндивидуальногопредпочтенияигрупповые предпочтения, полученные по различным правилам:R1R2НПСДПС по R2ППБR(1)R(1)R(1)R(1)R(1)R(1)R(2)R(1)R(2)R(3)R(1)R(3)R(1)R(3)R(3)R(2)R(1)R(1)R(1)R(3)R(2)R(2)R(1)R(2)R(2)R(2)R(3)R(1)R(3)R(3)R(3)R(1)R(1)R(1)R(3)R(3)R(2)R(1)R(2)R(3)R(3)R(3)R(1)R(3)R(3)Замечание 1.

Отношения, полученные по правилам большинства, могут небыть транзитивными.Замечание 2. Правило тотально-мажоритарного большинства может бытьпостроено аксиоматически; это единственный тип правила, которое удовлетворяетследующим требованиям (аксиомам Мея):– однозначность (при любом профиле <R1,…,Rm> правило F определенооднозначно);– анонимность(групповоерешениенезависитотнумерованиявыборщиков);– нейтральность(групповоерешениенезависитотименованиякандидатов);– положительная реакция (если для некоторого профиля <R1,…,Rm>принцип согласования указывает, что a R b и если затем j-й выборщик меняетсвое предпочтение в пользу кандидата a, тогда как все остальные выборщикисохраняют свои предпочтения, то при новом профиле в групповом решении будетa P b, т.е. предпочтение станет строгим).Процедуры голосования типов В-В и У-ВПравило относительного большинства: каждый выборщик отдает свой голоснаиболее предпочтительному для себя кандидату, избирается кандидат a,получивший наибольшее число голосов f(a).Замечание: по правилу относительного большинства может победитькандидат, который является наименее предпочтительным для большинствавыборщиков.ПравилоБордá:каждыйвыборщиквсоответствиисосвоимипредпочтениями формирует отношение линейного порядка на множестве всех pкандидатов, на основе которого производится ранжирование следующим образом:наименеепредпочтительныйкандидатполучает0очков,следующийпопредпочтительности кандидат получает 1 очко и т.д., наиболее предпочтительныйкандидат получает p – 1 очков; побеждает кандидат с наибольшей суммой очковпо всем выборщикам (победитель по Бордá).Правило голосования с подсчетом очков (обобщение правила Бордá):аналогично правилу Бордá каждый выборщик производит ранжирование, рангикандидатам выставляются из фиксированной неубывающей последовательностичисел: s0 ≤ s1 ≤ … ≤ sp – 1, наименее предпочтительный кандидат получает s0 очков,следующий по предпочтительности кандидат получает s1 очков и т.д., наиболеепредпочтительныйкандидатполучаетsp – 1очков,побеждаеткандидатснаибольшей суммой очков по всем выборщикам.Замечание: правило относительного большинства тоже является частнымслучаем правила с подсчетом очков (при s0 = s1 = … = sp – 2 < sp – 1).Правило Кондорсе: если во множестве кандидатов, на котором построеногрупповоеотношениепредпочтенияпопринципупростогобольшинства,существует наибольший элемент, то он является победителем по Кондорсе.Состоятельным по Кондорсе правилом называется такое правило, котороевыбирает победителя по Кондорсе, если он существует.Теорема:существуютпрофилииндивидуальныхпредпочтений,прикоторых победитель по Кондорсе не может быть избран ни при каком способеподсчета очков (т.е.

правило с подсчетом очков не является состоятельным поКондорсе).Состоятельными по Кондорсе являются следующие два правила.ПравилоКопленда:намножествекандидатовстроитсягрупповоепредпочтение R по принципу простого большинства, затем каждому кандидату aвыставляется оценка следующим образом: f(a) = (число пар <a,x>∈R минус числопар <x,a>∈R, x≠a), побеждает кандидат с наибольшей оценкой (победитель поКопленду).ПравилоСимпсона:каждомукандидатуaвыставляетсяоценкаf(a) = min m(a,x) по всем x, где m(a,x) – число выборщиков, для которых aпредпочтительнее, чем x; побеждает кандидат с наибольшей оценкой (победительпо Симпсону).Пример 3:В выборах участвуют 5 выборщиков и 4 кандидата: A={a, b, c, d}.Пусть каждый выборщик в соответствии со своими предпочтениями задалотношениелинейногопорядканамножествекандидатов.Профильпопростогоиндивидуальных предпочтений выглядит так:R1R2R3R4R5abcdacbdbcdadbcacdbaгрупповоеотношениеПостроимпредпочтенияправилубольшинства.m(a,b)=2, m(b,a)=3, m(b,a)>m(a,b) ⇒ <b,a>∈Rm(a,c)=2, m(c,a)=3, m(c,a)>m(a,c) ⇒ <c,a>∈Rm(a,d)=2, m(d,a)=3, m(d,a)>m(a,d) ⇒ <d,a>∈Rm(b,c)=3, m(c,b)=2, m(b,c)>m(c,b) ⇒ <b,c>∈Rm(b,d)=3, m(d,b)=2, m(b,d)>m(d,b) ⇒ <b,d>∈Rm(c,d)=4, m(d,c)=1, m(c,d)>m(d,c) ⇒ <c,d>∈RТаким образом, R также является отношением линейного порядка:RbcdaРезультаты голосования в зависимости от применяемого правила:ПравилоОтносит.БордаКондорсеКоплендаСимпсонаf(a)=2f(a)=3+3+0+0+0=6∀x∈A <b,x>∈R,f(a)=0–3=–3f(a)=min{2,2,2}=2f(b)=1f(b)=2+1+3+2+1=9следовательно,f(b)=3–0=3f(b)=min{3,3,3}=3f(c)=1f(c)=1+2+2+1+3=9b – наибольшийf(c)=2–1=1f(c)=min{3,4,2}=2f(d)=1f(d)=0+0+1+3+2=6элемент в Af(d)=1–2=–1f(d)=min{3,2,1}=1abиcbbbбольш.ПодсчетПобедители∀x∈A <x,a>∈Ri, при i=3,4,5.

Следовательно, a – наименьший элемент в A(наихудший) для 3-го, 4-го и 5-го выборщиков, т.е. для большинства выборщиков.Нормативные свойства правил голосованияОптимальность по Парето: если кандидат a для всех выборщиковпредпочтительнее, чем кандидат b, то b не может быть избран.Анонимность: имена выборщиков не имеют значения, т.е. если двавыборщика поменяются своими предпочтениями, результат выборов не изменится.Нейтральность: имена кандидатов не имеют значения, в том смысле, чтопри переименовании a на b и b на a, если победителем был a, то победит b, еслипобедителем был какой-то другой x, то он и останется победителем.Монотонность: если a – победитель при данном профиле и профильизменить таким образом, что положение a улучшится, а попарное сравнениелюбых других кандидатов для любого выборщика не изменится, то a по-прежнемубудет выбран при новом профиле.Замечание: правила с подсчетом очков, правила Кондорсе, Копленда иСимпсона обладают вышеперечисленными свойствами.Аксиома пополнения: если две непересекающиеся группы N1 и N2выборщиков выбирают одного и того же кандидата a из одного и того жемножества A кандидатов, тогда объединенная группа выборщиков N1∪N2 такжевыберет кандидата a.Теорема:всеправиласподсчетомочковудовлетворяютаксиомепополнения; не существует состоятельного по Кондорсе правила, котороеудовлетворяло бы аксиоме пополнения.Аксиома участия: если кандидат a выбирается из множества A кандидатоввыборщиками из множества N, то объединение N∪i (выборщик i∉N) выберет a,либо кандидата, который для i более предпочтителен, чем a.Теорема:всеправиласподсчетомочковудовлетворяютаксиомепополнения; если A состоит хотя бы из 4-х кандидатов, то ни одно состоятельноепо Кондорсе правило не удовлетворяет аксиоме пополнения.Манипулируемость принципов согласованияПример 4:Пусть в примере 3 голосование проводится по правилу относительногобольшинства, в таком случае побеждает кандидат a, который наименеепредпочтителен для 4-го и 5-го выборщиков.Однако, если 4-й и 5-й выборщики знают предпочтения остальныхвыборщиков, то они могут исказить информацию о своих предпочтениях так,чтобы повлиять на исход выборов в лучшую для себя сторону.

А именно, если ониотдадут свои голоса не за кандидатов d и c, которые для них наиболеепредпочтительны, а за кандидата b, который по крайней мере предпочтительнеедля них, чем кандидат a, то будет избран b.Принципы согласования, допускающие манипулирование такого рода,называются манипулируемыми..