Тема 7. Задачи группового выбора (1015592)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Тема 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.Принципы согласования, допускающие манипулирование такого рода,называются манипулируемыми..

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций