Обратимся к задаче общественного выбора. Пусть имеется N избирателей, которым необходимо ранжировать k альтернатив. Будем считать выполненными некоторые условия, благодаря которым станет возможным сам анализ, а также получение определенных результатов. Мы будем предполагать следующее:
1. Для дальнейших построений удобно считать каждую альтернативу сущностью в себе, имеющую скрытую ценность. Мы лишь условно наклеиваем ярлыки на каждую альтернативу, не меняя ее внутреннего содержания. Можно, например, пронумеровать все альтернативы целыми числами 1...k, чего мы и будем придерживаться. Идея вещи в себе в том, что мы легко можем переклеить наши номерки, но конкретная альтернатива совершенно не зависит от номера, который мы ей присвоили. В этом отличие от подхода теории множеств, в котором обозначение альтернативы (малыми буквами латинского алфавита и т.д.) полностью ее определяет, откуда следует, что сущность предмета сосредотачивается в его названии. Другим простым доводом в пользу идеи скрытых сущностей является чисто прагматическая мысль, что если мы умеем переклеивать ярлыки на альтернативах, то мы хотя бы как-то можем с ними работать. В теории множеств, напротив, мы бессильны перед абсолютными именами вещей.
2. Мы будем считать, что все избиратели полностью упорядочивают альтернативы, т.е. что каждый из них предъявляет линейный порядок всех альтернатив в качестве своего мнения. Это предположение является более сильным, чем обычно принято в теории выбора, где допустимы любые связные транзитивные отношения предпочтения (слабые порядки). Вводя его, невозможно избежать больших требований к избирателям, их большей ответственности. Однако, кажется вполне естественным, что после того, как избиратель предоставил свой частичный порядок, мы можем уточнять его мнение по каждому из классов эквивалентных вариантов. Хотя этот подход сильно напоминает независимость от посторонних альтернатив, тем не менее его смысл скорее в последовательном уточнении предпочтений избирателя, а не в утверждении НПА. Более того мы будем требовать, чтобы наша процедура выбора (система голосования) также давала на выходе линейный порядок альтернатив.
Аксиомы Эрроу
Аксиомы Эрроу включают универсальность, монотонность, независимость от посторонних альтернатив, ненавязывание, отсутствие диктатора. Первые два требования просты и эффективны, их адекватность не вызывает сомнения. Однако оставшиеся три не кажутся столь очевидными.
Действительно, независимость от посторонних альтернатив(НПА) говорит о том, что для любой пары альтернатив мы способны дать ответ, какая из них лучше, забывая про все остальные альтернативы. Это ясно и действительно имеет место. Однако, мы не можем строить упорядочение всех альтернатив исхъодя из парных сравнений и именно в этом слабость НПА. Эрроу же напротив, требует чтобы избирательная система удовлетворяла НПА и одновременно строила упорядочение всех альтернатив. Противоречие условия транзитивности и НПА приводит в итоге к теореме невозможности.
Ненавязанность также является не слишком удачным условием. Дело в том, что оно не затрагивает равенство альтернатив, а говорит лишь о существовании определенного профиля предпочтений, при котором данная альтернатива выигрывает. Иначе говоря система, в которой один выигрывает лишь при единогласном решении, а второй - при всех остальных очевидно является несправедливой, но она удволетворяет условию ненавязанности.
То же самое можно сказать об условии отсутствия диктатора. Система, в которой все решают два человека, если кооперируются, признается этой аксиомой приемлемой, хотя отличие от диктатуры невероятно мало. Кроме того, диктатура в чистом виде практически не встречается. Чаще правит очень узкая группа людей.
Формальная модель
Прежде всего мы заметим, что любой линейный порядок на множестве {1,....,k} соответствует ровно одному элементу симметрической группы S_k. Тогда списку линейных порядков всех N избирателей соответствует N-кратное прямое произведение групп перестановок из k элементов S_k^N. Особенно важным является то, что прямое произведение групп - снова группа. Примем следующее
Определение 1: Функцией общественного выбора называется функция, которая каждому элементу S_k^N ставит в соответствие ровно один элемент S_k
Ясно, что удовлетворяющих этому определению функций невероятно огромное количество. Однако без дополнительных требований структура этих функций полностью размыта. Поэтому будем последовательно вводить различные свойства, которым бы удовлетворяла желательная процедура выбора.
Единогласие
Представим себе, что общество существует в полном согласии. Это значит, что все избиратели ранжируют альтернативы одинаково. Тогда вполне разумно ожидать, что наша избирательная система будет солидарна с мнением общества, ведь она и предназначена, чтобы выражать точку зрения общества как целого. Поэтому имеет смысл
Определение 2
Система выбора называется единогласной, если для любого элемента диагональной подгруппы S_k^N (p,...,p) ставит в соответствие сам элемент p
Это желательное свойство является доволльно слабым в том отношении, что практически не ограничивает структуру функции выбора.
Универсальность
Желательно, чтобы система голосования всегда определяла коллективную ранжировку. Иначе говоря, мы хотим получить корректный ответ для любого списка предпочтений избирателей
Определение 3
Функция выбора универсальна, если она определена для любого элемента S_k^N
Это требование является важным, однако его настоящее значение проясняется при дополнительных требованиях к нашей системе выбора.
Анонимность
Одной из основных черт современного общества является равенство. Оно безусловно есть крайне желательное свойство гражданского общества. Несмотря на увлекательность и сложность вопроса о принципиальной возможности равенства, мы обойдем его стороной, веря, что ответ на него положителен. Ясно, что функция выбора не должна нарушать равенства граждан, иначе мы не можем считать ее вполне приемлемой. Постараемся формализовать это свойство:
Определение 4
Функция выбора называется анонимной, если любая перестановка ее аргументов не меняет ее значения
До какой степени ограничивает это требование множество функций выбора? Припишем линейный порядок элементам S_k. Легко понять, что мы можем построить все анонимные функции, определяя их на канонических наборах переменных, т.е. таких наборах, которые возрастают по выбранному порядку. Относительно введения самого порядка нет никаких сложностей, ибо всякая группа S_k конечна для конечных k и N. Рассмотрение случая бесконечного числа вариантов и бесконечного числа избирателей проводить не будем.
Нейтральность
Равенство должно выражаться не только в том, что мы одинаково ценим мнение каждого избирателя. Равенство также подразумевает, что альтернативы тоже оцениваются по их скрытым сущностям, а не по номеру который мы им присвоили. Вопрос познания скрытой сущности, которое необходимо для верного и сознательного выбора избирателей важен, но скорее относится к философии. В этом смысле мы избавимся от это сложнейшей проблемы просто оставив ее на плечах каждого индивида. Сформулируем теперь условие равенства альтернатив:
Определение 5
Функция выбора называется нейтральной, если выполнено F(a*p1,...a*pN)=a*F(p1,...,pN), где a, p1,...,pN элементы S_k
Чтобы яснее представить себе это условие достаточно привести следующую интерпретацию. Пусть верхняя строка в записи перестановки будет означать места, а нижняя - номера альтернатив. Тогда каждая перестановка - распределение альтернатив по местам. Мы можем, как мы сказали, произвольным образом переклеить номерки. Очевидно, что функция выбора не должна зависеть от того, как мы называем альтернативу, а ориентироваться только на скрытую ценность последней. А потому для получения решения, нам просто надо переклеить номерки старого решения так же, как мы сделали для предпочтений избирателей.
Заметим теперь следующий факт. Множество диагональных элементов D^N=(p,...,p) группы S_k^N образует подгруппу. Это означает, что условие нейтральности существенно упрощает структуру функции выбора. Нам достаточно определить значение функции выбора для одного представителя каждого смежного класса по подгруппе D^N.
Можно однако использовать нейтральность иначе. Определим все элементы общей группы S_k^N, которые система будет отображать в единичный элемент группы S_k (тождественную перестановку). Это множество G является полным описанием системы выбора. Значение на остальных наборах получаем с помощью применения свойства нейтральности. Мощность G не превышает числа смежных классов группы S_k^N по диагональной подгруппе D^N. Для универсальной системы она равна индексу диагональной подгруппы.
Один простой парадокс
Теперь мы попробуем оценить к чему приводят все перечисленные свойства в совокупности. Легко проверить, что верно
Утверждение 1:
Для анонимной нейтральной системы следующие условия эквивалентны:
1. Мощность генератора равна индексу диагональной подгруппы, кроме того N взаимно просто с порядком всех подгрупп S_k^N(в том числе с порядком полной группы)
2. Система выбора универсальна
Доказательство следует непосредственно из того факта, что элемент группы действует на группе в целом как перестановка(теорема Кэли). Условие на число N, сформулированное выше, удовлетворительно в случае группы перестановок, поскольку у группы перестановок из k элементов имеются подгруппы порядков 1,...,k и всевозможных произведений этих чисел. Но оно является крайне неудобным в общем случае произвольной группы, ведь для его проверки мы должны располагать информацией о всех подгруппах данной группы. А это, как известно нетривиальная задача. Поэтому на практике удобнее считать N простым числом, превышающим порядок группы. В случае перестановок достаточно, чтобы N было простым числом, превышающим k, либо являлось произведением степеней последних.
Этот результат является общеизвестным, но его получение исходя из нормальной формы игры менее наглядно. Смысл этого утверждения очень глубок. Вспомним, что мы потребовали от системы выбора не так уж много. Мы всего лишь хотели, чтобы любое мнение было возможно высказать (универсальность), чтобы все альтернативы имели шансы победить (нейтральность), наконец. чтобы все избиратели имели равное влияние (анонимность). То что мы потребовали линейных предпочтений избирателей и полного порядка на выходе системы выбора не играет роли, и легко обобщается на транзитивные, связные отношения. Что же мы получили? Наша системы дает нам ответ лишь при конкретном соотношении между числом альтернатив и избирателей. Но это значит, что для универсальной системы выбора нам придется либо нарушить нейтральность (ограничивая число альтернатив), либо нарушить анонимность (ограничивая число выборщиков). Это одна точка зрения на сложившуюся ситуацию. Другая сторона дела в том, что мы не можем полностью переложить проблему выбора на формальную процедуру, так, чтобы она в равной степени отражала взгляды каждого избирателя. Так же можно заметить, что мы можем использовать нашу формальную процедуру выбора, если выберем простое число выборщиков. Либо выберем одну альтернативу. Так мы приходим к парадоксу. Чтобы использовать систему выбора, нам приходиться делать выбор между большим числом альтернатив (в данном случае нам придется избрать простое число представителей-выборщиков), либо выбрать альтернативу, а значит решить исходную задачу самим. Эти рассуждения демонстрируют, что нам приходится выбирать между свободой и равенством для части общества с одной стороны, и ограниченной свободой для всех с другой.
Простое доказательство теоремы Эрроу
Рассмотрим известную теорему Эрроу. Мы немного изменим формулировку теоремы в соответствии с введенными определениями, а также покажем, что результат теоремы совершенно не зависит от свойства монотонности, а также от эквивалентного ему свойства оптимальности по Парето. мы можем исключить это свойство, которым пользуются в стандартных формулировках благодаря немного более сильным понятиям анонимности, нейтральности и универсальности.
Теорема Эрроу
Не существует функции выбора, которая бы была универсальной, анонимной. нейтральной и удовлетворяла бы независимости от посторонних альтернатив в случае, когда имеется три или более альтернатив
Док-во:
Допустим имеем три альтернативы для выбора. Предположим, что существует системы выбора, которая удовлетворяет всем требованиям теоремы. Прежде всего, используем следующие рассуждения. В силу независимости от посторонних альтернатив, для каждой пары альтернатив результат зависит от того, к какому смежному классу относится перестановка каждого избирателя относительно подгруппы, содержащей транспозицию этих альтернатив и единичный элемент. Определим класс перестановки как "+", если порядок совпадает с порядком альтернатив в тождественной перестановке, и "-" в ином случае. По указанному свойству, а также в силу нейтральности результат функции выбора для каждой пары альтернатив будет зависеть от последовательности "+" классов и "-" классов перестановок избирателей. Согласно же анонимности мы можем переставлять "+" и "-", не меняя значение функции выбора. Приведем список всех перестановок и классы к которым их отнесем в парных сравнениях альтернатив:
123 132 213 231 312 321
1>2 + + - - + -
2>3 + - + + - -
3>1 - - - + + +
Основное внимание уделим тому, что можно выбрать перестановки так, что для всех трех строк получится одинаковое число плюсов и минусов.
Теперь будем приводить примеры:
1. Если число избирателей кратно трем, то выберем профиль состоящий из степеней цикла (123)
2. Если в остатке деления числа избирателей на 3 получается 2, используем пункт 1, а оставшимся двум припишем 312 и 213
3. Если в остатке деления числа избирателей на 3 получается 1. то используем пункт 1, а для оставшихся 4 избирателей используем дважды пункт 2
Мы получаем строки, в каждой из которых число "+" и "-" одинаково. Это значит, что системы выбора должна либо утвердить все три класса как "+", либо опровергнуть все как "-". Как видно, однако, первые два ответа противоречат третьему из-за транзитивности, а потому одинаковый ответ на все три условия приводит к циклу.
Аналогично доказывается теорема Сена и теорема Гиббарда. На самом деле невозможность построить функции выбора, удовлетворяющей перечисленным в условиях теоремы свойствам полностью связана с независимостью от посторонних альтернатив. Мы можем получить любой порядок в зависимости от очереди, в которой будем проводить сравнение пары альтернатив.
Ограничение возможных предпочтений
Одним из возможных решений парадокса Эрроу считается отказ от свойства универсальности, а значит ограничение возможных предпочтений избирателей. Эти идеи отразились в работах Кумса, Блэка, Сена. В принципе, все предложили примерно одно и то же решение - предположение об однопиковых предпочтениях. Внешне это предположение не выглядит слишком уж ограничительным. Однако, теоремы Блэка об однопиковых предпочтениях, теорема Сена о когерентном профиле участников утверждают, что существуют функции выбора, удовлетворяющие остальным аксиомам Эрроу. Но они нарушают два условия Эрроу - не только универсальность, но и нейтральность. Дело в том, что когда мы строим однопиковые предпочтения (т.е. список разрешенных перестановок), мы приписываем всем альтернативам некоторый порядок, согласно которому они располагаются на числовой оси. Легко заметить, что альтернатива, которую мы считаем радикальной всегда проигрывает более умеренным альтернативам. Можно тогда задать вопрос: как избирателю выразить свое мнение, если он предпочитает две крайние альтернативы, а уж потом все оставшиеся? Теперь становится понятным, каким образом нарушается нейтральность системы. Из-за ограничения допустимых предпочтений нарушается также и равенство избирателей (не в смысле определения 4).
Легко также уяснить, каким образом мы можем так ограничить преджпочтения чтобы избавиться от цикличности и нарушения функционального свойства. Как мы видели выше, все такие неприятности случаются из-за наличия нетривиальных подгрупп у основной для нас группы перестановок. Поэтому, как только мы устраним свойство замкнутости подгрупп, беды наши кончатся. Несложно показать, что если устранить замкнутость малых подгрупп, замкнутость подгрупп, содержащих первые тоже исчезает. При этом важно, что мы не можем убрать замкнутость подгрупп второго порядка, поскольку тогда система голосования станет навязывающей. Поэтому достаточно перебрать все циклы длиной 3 и удалить в каждом по одному элементу. Именно такую процедуру предложил Сен, назвав полученные профили избирателей когерентными. Возникает сложность: что делать с теми избирателями, чьи профили некогерентны?
Следует отметить, что если бы предпочтения каждого действительно описывались идеальной альтернативой на некоторой числовой прямой, то не имело бы смысла вводить ограничение на возможные предпочтения, поскольку иные нам бы просто не встретились. В этом отношении невмешательство кажется мне более разумным, чем бессмысленное ограничение.
Монотонность
Свойство монотонности очень легко формулировать в терминах порядков. Для нашей формализации рассмотрение этого простого и ясного свойства весьма затруднительно. Дело в том, что на перестановках нет никакого порядка, а потому мы не можем говорить о какой-либо монотонности. Возможным разрешением является построение группы операторов, которые одним перестановкам ставят другие, причем так, чтобы их действие согласовывалось с интуитивным понятием укрепления позиций альтернативы.
Литература:
Kenneth J. Arrow. "Social choice and individual values" Chapman & Hall, 1951.
Steven J. Brams. "Approval voting" Springer, 2007.
Р. Л. Льюс, Х. Райфа. "Игры и решения: введение и критический обзор" Издательство иностранной литературы, 1961.
Р. Д. Кини, Х. Райфа. "Приянтие решений при многих критериях: предпочтения и замещения" Радио и связь, 1981.
Э. Мулен. "Кооперативное принятие решений: аксиомы и модели" Мир, 1991.
М. Холл. "Теория групп" Издательство иностранной литературы, 1962.
О. Богопольский. "Введение в теорию групп" Москва-Ижевск: институт компьютерных исследований, 2002.
Р. Клима, Дж. Ходж. "Математика выборов" МЦНМО, 2007.