Задачи группового выбора

Ситуация группового выбора возникает, когда в роли ЛПР выступает несколько равноправных лиц. На основе индивидуальных предпочтений этих лиц должно быть выработано согласованное групповое (иначе говоря, коллективное) решение.

Примерами таких ситуаций являются выборы в парламент страны, конкурс студенческой самодеятельности и т.п. Подобные задачи принятия решений называются задачами группового выбора, участвующие в них ЛПР называются выборщиками, а сравниваемые варианты – кандидатами.

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

Существуют различные модели группового выбора. Индивидуальные предпочтения могут задаваться, например, бинарными отношениями предпочтения или определяться функцией выбора.

В зависимости от того, каким образом заданы индивидуальные предпочтения и в какой форме требуется построить групповое предпочтение, выделяют различные типы задач группового выбора и соответствующие им типы процедур голосования. Рассмотрим основные из них.

1. Задан набор <R1,…,Rm> отношений индивидуального предпочтения (так называемый профиль индивидуальных предпочтений), групповое предпочтение требуется построить также в виде бинарного отношения R (или соответствующего ему строгого отношения предпочтения P) на множестве кандидатов. Таким образом, R = F(R1,…,Rm). Это процедура голосования типа У-У («упорядочение – упорядочение»).

2. Задан профиль индивидуальных предпочтений <R1,…,Rm>, групповое предпочтение требуется построить в виде выбора C(A) = F(R1,…,Rm) из множества кандидатов А. Это процедура голосования типа У-В («упорядочение – выбор»).

3. Для каждого i-го выборщика задан Ci(A) – его выбор из множества кандидатов A. Требуется построить групповой выбор Это процедура голосования типа В-В («выбор – выбор»).

Процедуры голосования типа «упорядочение – упорядочение»

Рассмотрим процедуры голосования типа У-У. Будем считать, что R_i являются отношениями полного квазипорядка.

Приведем примеры принципов согласования:

– навязанный принцип согласования (каким бы ни был задан профиль индивидуальных предпочтений, формируется одно и то же отношение группового предпочтения);

– диктаторский принцип согласования (R=R_j, то есть групповое предпочтение формируется из предпочтения одного j-го выборщика, независимо от предпочтений R_i, 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.

Пример 7.1. Множество кандидатов 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>}.

Имеется 9 возможных профилей индивидуальных предпочтений. В таблице 7.1 указаны групповые предпочтения, полученные по навязанному принципу согласования (НПС), когда независимо от мнения выборщиков групповое предпочтение определяется отношением R(1), и диктаторскому принципу (ДПС), когда групповой выбор определяется мнением выборщика R2:

Таблица 7.1

Правило простого большинства чрезвычайно распространено при принятии коллективных решений. Его часто усиливают правилом квалифицированного большинства. Например, в ст.105 п.5 Конституции РФ говорится: "...федеральный закон считается принятым, если при повторном голосовании за него проголосовало не менее двух третей от общего числа депутатов Государственной Думы" (t=2/3).

Существенным недостатком этих правил является то, что групповые решения, полученные по правилам большинства, могут не быть транзитивными. Нетранзитивность проявляется уже в случае трех выборщиков и трех объектов a, b, c. Если, например, первый выборщик ранжирует объекты в порядке убывания предпочтительности как (a, b, c) второй – (b, c, a), а третий – (c, a, b), то справедливо, что a предпочтительнее b, b предпочтительнее c. Но по правилу большинства c предпочтительнее a, в то время как по транзитивности должно быть a предпочтительнее c.

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

– определенность: при любом профиле <R1,…,Rm> правило F указывает единственное групповое решение;

– анонимность: групповое решение не зависит от обозначений выборщиков, то есть если два выборщика поменяются своими предпочтениями, результат выборов не изменится;

– нейтральность: групповое решение не зависит от именования кандидатов в том смысле, что при переименовании a на b и b на a, если победителем был a, то победит b, если победителем был какой-то другой x, то он и останется победителем.

– положительная реакция: если для некоторого профиля <R1,…,Rm> принцип согласования указывает, что a R b и если затем j-й выборщик меняет свое предпочтение в пользу кандидата a, тогда как все остальные выборщики сохраняют свои предпочтения, то для нового профиля в групповом решении будет a P b.

Процедуры голосования типа «упорядочение-выбор»

Приведем несколько примеров известных правил группового выбора типа «упорядочение – выбор».

Правило Бордá. Каждый выборщик в соответствии со своими предпочтениями формирует отношение линейного порядка на множестве p кандидатов, на основе которого производится ранжирование следующим образом: наименее предпочтительный кандидат получает 0 очков, следующий по предпочтительности кандидат получает 1 очко и т.д., наиболее предпочтительный кандидат получает p – 1 очко. Побеждает кандидат с наибольшей суммой очков по всем выборщикам (победитель по Бордá).

Правило голосования с подсчетом очков (обобщение правила Бордá). Аналогично правилу Бордá каждый выборщик производит ранжирование, ранги кандидатам выставляются из фиксированной неубывающей последовательности чисел: s0  s1  …  sp – 1. Наименее предпочтительный кандидат получает s0 очков, следующий по предпочтительности кандидат получает s1 очков и т.д., наиболее предпочтительный кандидат получает 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. Побеждает кандидат с наибольшей оценкой (победитель по Симпсону).

Пример 7.2. В выборах участвуют 5 выборщиков и 4 кандидата A= {a, b, c, d}.

Пусть каждый выборщик в соответствии со своими предпочтениями задал отношение линейного порядка на множестве кандидатов. Профиль индивидуальных предпочтений выглядит так:

Построим групповое отношение предпочтения по правилу простого большинства.

m(a,b)=2, m(b,a)=3, m(b,a)>m(a,b)  <b,a>R

m(a,c)=2, m(c,a)=3, m(c,a)>m(a,c)  <c,a>R

m(a,d)=2, m(d,a)=3, m(d,a)>m(a,d)  <d,a>R

m(b,c)=3, m(c,b)=2, m(b,c)>m(c,b)  <b,c>R

m(b,d)=3, m(d,b)=2, m(b,d)>m(d,b)  <b,d>R

m(c,d)=4, m(d,c)=1, m(c,d)>m(d,c)  <c,d>R

Таким образом, R также является отношением линейного порядка:

Результаты голосования в зависимости от применяемого правила представлены в таблице 7.1:

Таблица 7.1

Парадокс Эрроу

Все приведенные выше правила имеют те или иные недостатки. Поэтому имеет смысл сформулировать в виде аксиом некоторые разумные требования, которым должно удовлетворять «приемлемое» правило согласования, а затем исследовать логические следствия из них. Такой анализ впервые был проведен американским экономистом Кеннетом Эрроу.

Предположим, что групповое отношение R=F(R1,…,Rm) должно быть связным квазипорядком (то есть рефлексивным, транзитивным и полным бинарным отношением) при любых индивидуальных предпочтениях R1,…,Rm, описывающих строгие ранжирования. Будем рассматривать случай, когда число выборщиков m ≥ 2, а число объектов в A ≥ 3.

Система аксиом Эрроу состоит из следующих пяти аксиом.

1. Универсальность. Групповое отношение должно быть определено для любых профилей индивидуальных предпочтений.

2. Положительная связь. Если для данного профиля предпочтений верно a R b, то такое предпочтение должно остаться верным и тогда, когда индивидуальные предпочтения в попарных сравнениях, включающих b, либо не меняются, либо меняются в пользу a, в то время как остальные сравнения остаются неизменными.

3. Независимость от несущественных альтернатив. Пусть B произвольное подмножество множества A. Если в двух профилях предпочтений все попарные сравнения объектов из B совпадают, то они должны совпадать и в групповых решениях.

4. Суверенность граждан. Для каждой пары объектов a и b существует такой профиль индивидуальных предпочтений, что a R b.

5. Отсутствие диктатора. Групповое предпочтение не должно являться предпочтением одного из выборщиков, независимо от предпочтений остальных выборщиков.

Однако оказывается, что эти требования несовместимы.

Теорема (Эрроу о невозможности). Не существует принципов согласования, удовлетворяющих аксиомам 1-5.

Отметим, что теорема Эрроу распространяется лишь на те правила согласования F, для которых R – связный квазипорядок, предпочтения измеряются в порядковых, а не в количественных шкалах. Если эти условия снять, то теорема неверна. Например, аксиомам 1-5 удовлетворяют правила большинства. Однако они могут дать, как мы знаем, нетранзитивное групповое отношение.

Манипулируемость принципов согласования

Принцип согласования называется манипулируемым, если выборщик с номером i0, знающий этот принцип и знающий, каковы предпочтения остальных выборщиков, обладает возможностью изменить свои собственные предпочтения Ri0 так, что групповое предпочтение R окажется более выгодно для него.

Пример 7.3. Приведем пример манипулируемого принципа согласования. Пусть 3 выборщика выбирают из трех кандидатов – A={a, b, c}. Принцип согласования следующий. Голосование проводится в два тура. В первом туре производится выбор из кандидатов a и b по правилу простого большинства. Во втором туре кандидат c сравнивается с победителем первого тура и по правилу большинства определяется победитель второго тура.

Пусть личные предпочтения выборщиков выглядят следующим образом (в порядке убывания предпочтительности): первый выборщик ранжирует объекты как (a, b, c), второй – (b, c, a), а третий – (c, a, b).

При таких индивидуальных предпочтениях в первом туре победит кандидат a, а во втором – кандидат c. Таким образом, победителем такого голосования станет кандидат, который для первого выборщика является наименее предпочтительным. Однако если первый выборщик знает предпочтения остальных выборщиков и принцип выбора победителя, он может с выгодой для себя исказить собственное мнение. Например, если он сформулирует свои предпочтения как (b, a, c), то победителем окажется кандидат b, более приемлемый для первого выборщика, чем c.

Этот пример показывает, что правило простого большинства манипулируемо. Вопросам, связанным с манипулируемостью принципов согласования, посвящена работа Джиббарда и Сэттартуэта. В частности, показано, что любой принцип согласования, удовлетворяющий аксиомам Эрроу 1-5 и позволяющий выбрать единственного лучшего кандидата, является манипулируемым.