1 - Коллективные решения

1.

КОЛЛЕКТИВНЫЕ РЕШЕНИЯ
Быть добрым очень легко, быть справедливым — вот что трудно.
В. Гюго
Перед любым человеческим сообществом стоят две основные задачи:
созидание и распределение. Система распределения затрат и благ должна
разрешить так или иначе основную конфликтную ситуацию, связанную со
стремлением сделать вклад поменьше, а получить побольше.
Система распределения благ и затрат опирается на представления о
справедливости. Если большинство членов общества не признают
справедливости существующих принципов распределения, то либо оно
развалится, либо будет тратить все большие ресурсы на систему подавления и
наказания. Всякое общество пытается обосновать справедливость своей
системы распределения, заявляет о своем стремлении к совершенствованию
этой системы. Большинство общественных решений (таких как налоги и
общественные расходы) принимаются на основе голосования.
1

2.

Наиболее ярким примером коллективного принятия решений являются
демократические выборы. Можно считать, что групповые решения
вырабатывается на демократических основах, и все индивидуумы
равноправны. Примерами таких групп являются законодательный орган,
эксперты или арбитры, производящие отбор среди набора альтернатив.
Каждый член группы имеет свои предпочтения или мнения. Тогда можно
попытаться выработать некоторые процедуры, с помощью которых из
индивидуальных мнений можно построить согласованное обобщенное
мнение.
2

3.

ПРИМЕР (нетранзитивность):
В условиях демократии и свободы волеизъявления трое
министров должны определить, что важнее для страны – оборона,
образование или социальное обеспечение (в какую отрасль
вложить дополнительные инвестиции).
Министр А
Министр В
Министр С
Образование
Оборона
Соц. обеспечение
Соц. обеспечение Образование
Оборона
Оборона
Соц. обеспечение Образование
3

4.

Не существует универсального способа выявления
коллективного предпочтения, существует лишь бесконечное
множество достаточно разумных способов его выявления. Как
правило, они приводят к совершенно различным, а иногда и к
прямо противоположным результатам. При этом речь не о
нарушении
закона
или
технологии
PR.
Методика
манипулирования демократией предусматривает (в том числе)
всего лишь такой регламент проведения голосования, чтобы
получить необходимый конечный результат. То есть, вначале
нужно принять нужное правило голосования, а дальше – дело
математики.
4

5.

ПРИМЕР: 300 человек
избирателей должны выбрать 30
человек в совет трудового
коллектива. На эти 30 мест
претендуют 180 кандидатов. Администрация предприятия
определила правило: избранным в Совет будет тот, кто набрал
более половины от общего числа голосов. Избиратели в
бюллетене отмечают лучших (не обязательно одного).
После проведения первого тура только 2 человека набрало
более половины голосов избирателей. После проведения второго
тура было избрано еще 3 кандидата.
Администрация пришла к выводу, что таким образом дальше
голосовать нельзя, так как этот процесс затянется надолго.
Решили провести третий тур по правилу: в бюллетене
вычеркивать тех, кто по мнению избирателя не достоин быть
в Совете, а голоса ЗА считать по количеству бюллетеней, где
кандидат не вычеркнут. Оказалось, что необходимое
количество (25 кандидатов) набрано! Как так получилось? У кого
было преимущество в 3 туре?
5

6.

Базовые правила принятия
коллективных решений

7.

Правило относительного большинства
ПРИМЕР:
По правилу относительного большинства a набирает 8 голосов, b
набирает 7 голосов, c набирает 6 голосов, d набирает 0 голосов.
Следовательно, победителем является кандидат a.
7

8.

Правило относительного большинства с выбыванием
8

9.

a 8
b7
c 6
d0
Максимальное количество голосов у кандидата a, но это количество
не является строгим большинством (8 < 11). Следовательно,
проводится второй тур.
Во втором туре сравниваются кандидаты a и b: 13 избирателей
против 8 считают, что b лучше a, следовательно, победителем является
кандидат b. Все ли здесь хорошо?
9

10.

Казалось бы, все правильно и полностью соответствует процедуре
голосования. Однако как обстоит дело с кандидатами c и d, которые
выбыли в первом туре? Получаем:
14 против 7 считают, что c ≻ b,
13 против 8 считают, что d ≻ a.
Получается, что оба кандидата, выбывших в первом туре, были в два
раза лучше победителя!
10

11.

Первая попытка критического анализа процедур голосования была
предпринята лишь в конце XVIII века во Франции. В эти годы вопрос о
том, как надо принимать коллективные решения приобрел остроту
ножа гильотины.
Сомнения относительно принципа «решает большинство
голосов» возникли не только у законодателей после того, как
вопрос о казни Людовика XVI был принят Конвентом 1 1 декабря
1792 года большинством в один голос.
В то время в составе Конвента было 387 депутатов, соответственно
мнения «за» и «против» казни распределились почти поровну. В
Парижской Академии Наук началась активная дискуссия по вопросам
организации демократических выборов. Именно два академика
Парижской АН того времени по праву считаются основоположниками
теории голосования.
11

12.

Николя́ де Кондорсе́, маркиз де Кондорсе́ (17 сентября 1743 — 28
марта 1794) — французский философ, учёный-математик, академик
и политический деятель Аристократ по происхождению, Кондорсе
отказался от военной и церковной карьеры и стал ученым. Его
диссертация об интегральном исчислении, представленная в 16 лет
(Опыт интегрального исчисления, Du calcul intgral, 1765), была
высоко оценена Д'Аламбером. После издания Опытов анализа
(Essays d'Analyse, 1768) был принят в члены Академии наук, а в 1777
избран ее непременным секретарем, в 1782 Кондорсе был избран
членом
Французской
академии,
участвовал
в
знаменитой
Энциклопедии. Кондорсе мечтал о светлом будущем для
человечества,
о
необходимости
уравнения
гражданских
и
политических прав всех людей и о бесконечном совершенствовании
рода человеческого... Но революция, в которой он принимал
деятельное участие, погубила его. В тюрьме Кондорсе покончил с
собой, приняв яд.
Жан Шарль де Борда (04.05.1733 – 19.02.1799) – физик, геодезист и
математик, член Парижской АН. Родился в Даксе (департамент
Ланда). Служил офицером сначала в армии, а затем во флоте.
Математические работы Борда относятся к дифференциальным
уравнениям и сопротивлении жидкостей. Первая работа по
математике появилась в 20 лет. Его работы про сопротивление
жидкостей положили основание теории воздухоплавания. Борда
входил в Комиссию Лапласа по установлению единообразной
системы мер и весов. Во Франции существует общество имени Борда и
в память о нем на его родине установлен памятник.
12

13.

Принцип Кондорсе
Маркиз де Кондорсе сформулировал принцип или критерий,
позволяющий определить победителя в демократических
выборах. Принцип де Кондорсе состоит в следующем: кандидат,
который побеждает при сравнении один на один с любым из
других кандидатов, является победителем на выборах.
Согласно Кондорсе, справедливое определение победителя
возможно путем попарного сравнения кандидатов по числу
голосов, поданных за них. При этом каждый голосующий
упорядочивал кандидатов по степени своего желания видеть
данного кандидата победителем.
Принцип де Кондорсе предлагался как рациональный и
демократический. Однако вскоре маркиз де Кондорсе столкнулся
с парадоксом, получившим впоследствии его имя.
13

14.

ПРИМЕР:
Пусть на голосование поставлены три кандидата (А, В и С), и
голоса распределились следующим образом:
Число голосов Предпочтения
23
А≻В≻С
17
В≻С≻А
2
В≻А≻С
10
С≻А≻В
8
С≻В≻А
Сравним предпочтения в парах кандидатов.
А В С
А - 33 25
В 27 - 42
С 35 18 -
Получаем нетранзитивное соотношение: А ≻ В ≻ С ≻ А.
14

15.

Столкнувшись с этим парадоксом, Кондорсе выбрал в качестве
решения наименьшее зло: считать правильным мнение,
которое поддерживается большинством голосов (в данном
случае –А).
Вероятность парадокса Кондорсе
15

16.

Правило Борда
Согласно этому правилу результаты голосования выражаются в
виде числа баллов, набранных каждым из кандидатов. Пусть число
кандидатов равно n. Тогда за первое место присуждается (n–1) баллов,
за
второе
—
(n–2),
за
последнее
—
0
баллов.
Результат применения данного правила может вступать в противоречие с
правилом большинства: кандидат, поставленный большинством на
первое место, не всегда побеждает при использовании правила Борда.
Обобщение процедур Кондорсе и Борда
16

17.

Правило Копленда
Сравним кандидата А с любым другим кандидатом Х.
K A
1, если для большинства A X ;
X 1, если для большинства X A;
0, если для большинства A X .
Тогда оценка Копленда для кандидата А:
K (A) K (A
X)
X
Правило Симпсона
Сравним кандидата А с любым другим кандидатом Х.
S A
X Число избирателей для которых A
X.
Тогда оценка Симпсона для кандидата А будет вычисляться как:
S( A) min{S( A
X )}.
X
17

18.

Аксиомы Эрроу
Систематическое
исследование
всех
возможных
систем
голосования провел в 1951 г. Кеннет Эрроу из Стенфордского
университета.
Кеннет Джозеф Эрроу (англ. Kenneth Joseph Arrow; род. 23 августа
1921, Нью-Йорк) — американский экономист, лауреат Нобелевской
премии по экономике за 1972 год «за новаторский вклад в общую
теорию
равновесия
и
теорию
благосостояния». Американский
экономист Кеннет Джозеф Эрроу родился в Нью-Йорке. Закончив
колледж со степенью бакалавра по социальным наукам, он поступил в
Колумбийский университет, где в 1941 г. получил магистерскую степень
по математике. Однако учебу в аспирантуре он продолжил на отделении
экономики. Во время второй мировой войны, прервавшей его учебу,
Эрроу являлся офицером метеослужбы в американских ВВС и
дослужился до звания капитана. Первая работа будущего экономиста
носила название "Об оптимальном использовании ветров для
планирования полетов" и была навеяна опытом военной службы. В
1946 Эрроу вернулся к учебе в аспирантуре Колумбийского
университета. С 1949 г. Эрроу преподавал в Стэнфордском, а затем и
в Гарвардском университетах. В 1972 г. Эрроу получил совместно с Дж.
Хиксом Нобелевскую премию по экономике "за новаторский вклад
в общую теорию равновесия и теорию благосостояния".
Одним
из основных направлений исследований Эрроу была экономика
неопределенности. Именно благодаря его работам она стала одним
из основных разделов современной экономической теории и
прикладной экономики. Его "Очерки по теории принятия рискованных
решений" (1971), до сих пор остаются одним из лучших введений в
экономику неопределенности.
18

19.

Эрроу поставил вопрос в наиболее общем виде: можно ли создать
такую систему голосования, чтобы она была одновременно:
рациональной (без противоречий),
демократической (один человек — один голос),
решающей (позволяла осуществить выбор).
Вместо попыток изобретения такой системы Эрроу предложил
набор требований, аксиом, которым эта система должна удовлетворять.
Эти аксиомы были интуитивно понятны, приемлемы с точки зрения
здравого смысла и допускали математическое выражение в виде
некоторых условий.
Первая аксиома (аксиома универсальности) требует, чтобы
система голосования была достаточно общей для того, чтобы
учитывать все возможные распределения голосов избирателей.
Интуитивно это требование вполне очевидно. Заранее нельзя
предсказать распределение голосов.
19

20.

Вторая аксиома (аксиома единогласия). В соответствии с ней
необходимо, чтобы коллективный выбор повторял в точности
единогласное мнение всех голосующих. Если, например, каждый из
голосующих считает, что кандидат А лучше кандидата В, то и система
голосования должна приводить к этому результату.
Третья аксиома (независимости от несвязанных альтернатив):
если профиль голосования изменится так, что альтернативы А и В во
всех N списках останутся в том же порядке, то не изменится их порядок
и в окончательном результате. Пусть избиратель считает, что из пары
кандидатов А и В лучшим является А. Это предпочтение не должно
зависеть от отношения избирателя к прочим кандидатам.
Третья аксиома достаточно привлекательна, но не столь очевидна с
точки зрения каждодневного человеческого поведения. Часто она
нарушается судьями в фигурном катании. Давая сравнительные оценки
двум сильным фигуристам в одиночном катании, они стараются учесть
возможность хорошего выступления третьего сильного кандидата,
оставляя ему шансы стать победителем.
20

21.

Четвертая аксиома (аксиома полноты): система голосования
должна позволять выполнять результативное сравнение любой пары
кандидатов, определив, кто из них лучше (или их эквивалентность).
Пятая аксиома (аксиома транзитивности): если в соответствии с
мнением избирателей кандидат В не лучше кандидата А (хуже или
эквивалентен), кандидат С не лучше кандидата В, то кандидат С не
лучше кандидата А. Считается, что система голосования, не
допускающая нетранзитивности, ведет себя рациональным образом.
Эрроу доказал, что системы, удовлетворяющие всем аксиомам,
обладают недопустимым с точки зрения демократии недостатком:
каждая из них является правилом диктатора — личности,
навязывающей всем остальным избирателям свои предпочтения.
Требование исключения диктатора приводит к невозможности
создания системы голосования, удовлетворяющей всем аксиомам.
Поэтому результат Эрроу называют теоремой о невозможности. В
качестве ответа на теорему Эрроу часто приводят известные слова
У. Черчилля о том, что демократия является плохой формой правления,
но человечество пока не придумало ничего лучшего.
21

22.

Результаты К. Эрроу показывают, что в принципе невозможно
найти систему голосования, которая была бы одновременно
решающей, рациональной и демократической.
Нельзя отказаться от требования рациональности: система
голосования не должна приводить к нетранзитивности.
Нельзя не потребовать, чтобы система голосования была
решающей: коллективное безразличие, неумение сделать выбор
ведет в тупик.
Нельзя отказаться от требования демократичности выборов: в
современном мире право каждого человека выражать свое
мнение является фундаментальным.
С точки зрения реальной жизни важно знать, насколько часто
нарушаются все эти три условия одновременно. Исследования
французских ученых показали, что при моделировании всех возможных
распределений голосов избирателей и сохранении условий
демократичной и решающей системы голосования рациональность
нарушается примерно в 6-9% случаев.
22

23.

Ранжирование альтернатив

24.

Ранжирование альтернатив
Математические обозначения:
I = { i }, i = 1, … , n –эксперты (голосующие).
A = { aj }, j = 1, … , m –альтернативы (кандидаты).
Pi –ранжировка альтернатив, выполненная i-м экспертом.
x Pi y – i-й эксперт считает альтернативу x лучше альтернативы y.
x Ti y – i-й эксперт считает альтернативу x эквивалентной
альтернативе y.
Запись ранжировки множества альтернатив A = { x, y, u, v }:
Профиль (набор ранжировок) группы из трех экспертов:
24

25.

Свойства ранжировок:
Транзитивность (X лучше Y, Y лучше Z, следовательно, Xлучше Z).
Асимметричность (Если Xлучше Y, то не может быть, что Y лучше X).
ЗАДАЧА:
Как по заданному профилю группы экспертов найти
"выигравшую" альтернативу или, в менее общей постановке, как
найти ранжировку Р на А, которая выражает согласованное
мнение группы.
Если каждая ранжировка Pi получается в результате
упорядочения по предпочтению, то P представляет групповое
предпочтение. Правило построения групповой ранжировки по
групповому профилю будет называться функцией группового
выбора.
25

26.

Расстояние между ранжировками
Пусть Р и Q — ранжировки на множестве А, и a, b — элементы А.
Положим δPQ(a, b) равным:
0, если aPb и aQb;
2, если aPb и bQa или наоборот;
1, если в одной ранжировке aPb (либо bPa), а в ранжировке Q a и
b эквивалентны.
Тогда функция расстояния между ранжировками d(P, Q) равна сумме
значений δPQ(a, b) по всем (неупорядоченным) парам {a, b} из А.
ПРИМЕР:
26

27.

Медиана Кемени
Каково найти итоговое (среднее, общее) мнение группы? Согласно
идее Джона Кемени следует найти среднее мнение как решение
оптимизационной задачи. А именно, надо минимизировать суммарное
расстояние от кандидата в средние до мнений экспертов. Найденное
таким способом среднее мнение называют "медианой Кемени".
Медиана Кемени определяет ранжировку, которая находится
на наименьшем расстоянии от коллективного мнения группы
экспертов. Для получения коллективного мнения экспертов
используют
методы
средних
баллов
–
метод
средних
арифметических рангов и метод медиан рангов.
В конкретных пространствах нечисловых мнений экспертов
вычисление медианы Кемени может быть достаточно сложным делом.
Так, в пространстве ранжировок при использовании метрики,
связанной с коэффициентом ранговой корреляции Кендалла,
необходимо проводить достаточно сложные расчеты, в то время как
применение показателя различия на основе коэффициента ранговой
корреляции Спирмена приводит к упорядочению по средним рангам.
Поэтому упрощенный подход предлагает выбирать в качестве
приближенной медианы того эксперта, ранжировка которого
наименее удалена от ранжировок прочих экспертов.
27

28.

Совмещенные шкалы
Предположим, что напитки в баре (х, у, u и v) оцениваются по шкале
от 0 до 100, где балл –процент алкоголя.
Пусть при рассмотрении возможных напитков (альтернатив)
эксперт определяет на этой шкале свою идеальную оценку (эта оценка
характеризует его предпочтение в приведенной выше шкале 0-100).
Тогда получаем соответствующую ранжировку:
28

29.

Т.е. считаем, что для эксперта напиток x предпочтительнее
напитка y в том и только том случае, если расстояние от x до идеала
меньше расстояния от y до идеала.
Предположим теперь, что каждый эксперт может оценивать
напитки в единой шкале, и на той же шкале оценок помещаются сами
эксперты (идеальные оценки каждого индивидуума). Тогда получается
совмещенная количественная шкала:
Затем определяется эксперт, идеальная оценка которого является
медианой идеальных оценок всех экспертов. В качестве групповой
ранжировки берется ранжировка этого эксперта. Для трех экспертов с
множеством идеальных оценок {20, 50, 79} медиану определяет второй
эксперт с идеальной оценкой 50. Интересно отметить, что к тому же
результату приводит и правило простого большинства.
Ограничение метода: нечетное число экспертов.
29

30.

Материалы для дополнительного углубленного
изучения темы
Об алгоритмах расчета медианы Кемени
[https://www.zldm.ru/jour/article/viewFile/510/511.pdf]
[https://cyberleninka.ru/article/n/metody-poiska-mediany-kemeni-dlyanestrogih-i-chastichnyh-uporyadocheniy-alternativ/viewer]
[https://cyberleninka.ru/article/n/primenenie-mediany-kemeni-dlyaopredeleniya-optimalnoy-vyborki-algoritm-i-blok-shema/viewer]
[https://uniserv.iis.nsk.su/rdms/index.php?r=ontology%2Fshowindividual&individual_id=http%3A%2F%2Fwww.semanticweb.org%2Fgal%2F
ontologies%2F2018%2F0%2F9%2FDMSontology%23%D0%9C%D0%B5%D0%B4%D0%B8%D0%B0%D0%BD%D0%B
0_%D0%9A%D0%B5%D0%BC%D0%B5%D0%BD%D0%B8]
Экспертные оценки, бинарные отношения и дискретная оптимизация
[http://www.aup.ru/books/m156/7.htm]