Диссертация (Манипулирование в задаче коллективного принятия решений), страница 10

Тогда мы можем определить выбор какC ( P) =  f ( P;{i}, q) .I I iIДругими словами, выбирается альтернатива, которая является лучшейдля каждого участника хотя бы в одной простой коалиции участников.Если такой альтернативы не существует, то мы рассматриваем случайq=1 (смотрим на первые две лучшие альтернативы для каждого), q=2 итак далее пока не будет выбрана хотя бы одна альтернатива.Дляпримераизтаблицы3.1.минимальныекоалиции,обладающие простым большинством, содержат 4 участника. Такихкоалиций всего 15.

Если рассмотреть q=0, то для каждой колацилиизначение f ( P;{i},0)   .Смотрим на q=1, для всех коалиций, кромеiIкоалиции из 1, 4, 5, 6 участников f ( P;{i},1)   , для коалиции 1, 4, 5, 6iI f ( P;{i},1)  b . Таким образом, выбором будет C( P)  b .iI21.Сильноеq-ПаретовскоеправилоотносительногобольшинстваДанное правило повторяет предыдущее с учетом следующегоусиления. Если выбрано несколько альтернатив, то для каждой61альтернативы считается количество коалиций, которые её выбирают.Альтернатива(ы) с максимальным числом таких коалиций и являетсяокончательным выбором.Так как для предыдущего правила выбором была лишь однаальтернатива, то выбор не изменится: C ( P)  b22.Сильнейшееq-Паретовскоеправилопростогобольшинстваn2Пусть теперь f ( P; I , q) = {x  A :  Di ( x)  q} , где I = {I  N : I =  }iIесть семейство коалиций, обладающих простым большинством.

Тогдамы можем определить выбор какC ( P) =  f ( P; I , q) .I IКак и в других правилах, начинаем проверку со случая q=0. Если выборпуст, то мы рассматриваем случай q=1 (смотрим на пересечениеконтуров мощности один и меньше), q=2 и так далее, пока не будетвыбрана хотя бы одна альтернатива.Продемонстрируем это правило на том же примере. Изобразим втаблице 3.2. значения функции f ( P; I , q) для рассматриваемого примера.В ячейках таблицы отражено значение D ( x) ,iдля соответствующейiIкоалиции и альтернативы – само значение f ( P; I , q) находится впоследнем столбце.62Таблица 3.2. – Значение D ( x) для коалиций простого большинства.iiIКоалицияabcdf ( P; I , q  0){1234}ПустоПустоПустоПустоabcd{1235}ПустоПустоПустоПустоabcd{1236}ПустоПустоПустоПустоabcd{1245}ПустоПустоПустоПустоabcd{1246}ПустоПустоПустоПустоabcd{1256}ПустоПустоПустоПустоabcd{1345}ПустоПустоПустоПустоabcd{1346}ПустоПустоПустоПустоabcd{1356}ПустоПустоПустоПустоabcd{1456}ПустоПустоbПустоabd{2345}ПустоdПустоПустоacd{2346}ПустоПустоПустоПустоabcd{2356}ПустоПустоПустоПустоabcd{2456}ПустоПустоПустоПустоabcd{3456}ПустоПустоПустоПустоabcdОчевидно, что в этом случае C ( P) =  f ( P; I , q  0)  a, d  .I IВследующемразделеописаныиндексыоценкиманипулируемости.3.3.

Индексы манипулируемости и методика расчетаДля анализа степени манипулируемости используются дваиндекса. Первый из них – индекс Нитцана-Келли – был впервыепредложен Нитцаном [80], а затем использован в работе Келли [65],NK 63d0(m!) n,где d 0 – количество всех профилей, в которых хотя бы один участникуспешно манипулирует. Так как m – это число альтернатив, то m! –число всех возможных линейных порядков; так как n – это числоучастников голосования, (m!) n – число всех возможных профилейпредпочтений.

Таким образом, индекс NK – это просто доля всехманипулируемых профилей.Мы также используем при расчете расширенную версию индексаКелли, предложенную в [21]. Пусть  k – количество профилей, вкотором ровно k участников голосования могут манипулировать. В этомслучае можно построить индекс J k k(m!) n, который будет показыватьдолю профилей, манипулируемых ровно k участниками. Очевидно, чтоK  J 1  J 2    J n . Таким образом, мы используем векторный индексJ  J 1 , J 2 ,, J n  .В [21] был предложен индекс свободы манипулирования I 1 . Вдиссертациипомимоиспользоватьтакжесвободыиндексманипулированиянечувствительностипредлагаетсякискажениямпредпочтений и индекс возможности ухудшения результата.

Рассмотримслучай сильного манипулирования. Очевидно, что всего для участника iв профилеjсуществует m!1 различных вариантов искаженияпредпочтений. Пусть в  ij случаях манипулирующий участник добьетсяулучшения коллективного выбора по сравнению со случаем искреннихпредпочтений, в  ij0 случаях результат не изменится, а в  ij случаях,соответственно, итоговый выбор будет для участника i хуже. Получаем,что  ij   ij0   ij  m!1 .

Разделив каждое  ij на m!1 , получимсоответствующую долю. Суммируя соответствующие доли по всемучастникам в рамках одного профиля и деля на n , получаем среднююдолю соответствующего результата по профилю. Затем аналогично64суммируются доли по всем профилям, и сумма делится на (m!) n . Такимобразом, получаются три индекса(jm1!) in1  ijnI1 (m!) n  n  (m!1),где  ij равно  ij ,  ij0 или  ij для получения соответствующего индекса.Очевидно, что I 1  I 10  I 1  1.Случай слабого манипулирования отличается тем, что  ij ,  ij0 и  ijне покрывают все возможные последствия искажения предпочтений.Так как в этом случае расширенные предпочтения являются частичнымпорядком, возможна ситуация неопределенного перехода, когда послеискажения предпочтений новый выбор несравним со старым.

Такимобразом, добавляются новые случаи  ij? и соответствующий индекс I 1? ,причем I 1  I 10  I 1?  I 1  1 . Очевидно, что для случая сильногоманипулирования I 1?  0 .В то время как указанные выше индексы показывают степеньманипулируемости, следующие два индекса оценивают эффективностьманипулирования. Пусть искренним коллективным выбором являетсянабор C (P) , который стоит на k -том месте в расширенныхпредпочтенияхi-гоучастника.Предположим,чтопослеманипулирования i-го участника коллективный выбор стал C ( P ) ,стоящий на s -ом месте в расширенных предпочтениях i -го участника.Очевидно, что по определению манипулирования s < k .

Введемвеличину   k  s , которая будет показывать на сколько «мест» врасширенных предпочтениях улучшился выбор i -го участника.Просуммируем  для всех неискренних предпочтений, в которыхманипулирование выгодно, и поделим полученное значение на  ij .Полученный индекс будет обозначаться через Z ij и показывать среднийвыигрыш в терминах «мест» в результате манипулирования участника i65в данном профиле.

Усредняя данные индексы по всем участникамголосования в рамках одного профиля и по всем профилям, получаеминдексI2( m!) nnj =1i =1 ij =Z.(m!) n  nСледующий индекс I 3 является модификацией I 2 . Вместо оценкисреднего выигрыша манипулирования i -го участника ( Z ij ) оцениваетсявеличинаZ ijmax = max ( Z1 ,..., Z  ).ijДругими словами Z ijmax показывает максимальный выигрыш втерминах мест, который может быть получен участником i в результатеманипулирования. Аналогично, усредняя по всем участникам и всемпрофилям, получаем индекс( m!) nI3 =j =1nmaxi =1 ijZ(m!) n  n.Индексы I 2 и I 3 введены в [21].

Заметим, что эти индексыопределены лишь для случая сильного манипулирования, так какпонятие выигрыша для частичного порядка неопределено. ИндексыNK , I 1 , I 2 , I 3 , J рассчитаны для всех правил из предыдущего раздела.Описанные выше индексы рассчитывались для всех возможныхпрофилей предпочтений при 3, 4, 5 альтернативах и 3, 4, 5 агентах.Стоит отметить,что это сложная вычислительная задача, так как в случае(5,5) количество профилей составляет (5!) 5  24,9 млрд, что требуетдлительноговременивычисления.Дляупрощенияподсчетовиспользуется свойство анонимности, которому удовлетворяют всерассматриваемые правила.

Известно, что если правило удовлетворяетсвойству анонимности, то коллективное решение зависит лишь от того,как проголосовали участники процесса, а не от того, кто именно66голосовал. Иначе говоря, при перестановке предпочтений междуагентами выбор не должен меняться. Очевидно, что если один профиль,являетсяманипулируемымдляданногоправила,топрофили,полученные из него путем перестановок, также будут манипулируемы.Данное наблюдение позволяет упростить вычисления и рассматриватьвсего лишьмлнСnm! n 1профилей.профилей, что для случая (5,5) составляетПрирасчетеиндексовучитываетсяС5124 225количествопрофилей, которое можно получить из данного путем перестановок.Дляслучаябольшегочислаучастниковиспользовалсястатистический подход.