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

Выбором являются альтернативы, недоминируемые по V.Таким образом, данное правило является усилением обратногоправилаотносительногобольшинства,тоестьоноуменьшаетвероятность множественного выбора. Очевидно, что так как в примереиз таблицы 3.1. на первом этапе альтернатива "c" – это единственнаяальтернатива с наименьшим числом голосов против, то именно онабудет итоговым выбором: C ( P)  c .535. Правило БордаКаждой альтернативе x  A ставится в соответствие число ri ( x, P)равноемощностимножестваальтернатив,худших,чемxвпредпочтении Pi  P , то есть ri ( x, P) = Li ( x) = b  A : xPib , где Li (x) – этонижний срез альтернативы.

Сумма данных значений для i  Nназывается рангом Борда для альтернативы x,nr (a, P) = ri (a, Pi ).i =1В выбор входят альтернативы с максимальным рангомa  C( P)  [b  A, r (a, P)  r (b, P)].Для примера из таблицы 3.1. r(a)=r(b)=9, r(c)=8, r(d)=10, поэтомуC ( P)  d 5. Процедура БлэкаКоллективнымвыборомявляетсяпобедительКондорсе(альтернатива, которая не проигрывает любой другой альтернативе припопарном сравнении с точки зрения большинства), если он существует.В противном случае используется правило Борда.Для указанного выше примера имеется два победителя Кондорсе- альтернативы "a" и "d", поэтому выбором будет C ( P)  a, d 6. Процедура ХараВначалепервогоэтапаиспользуетсяправилопростогобольшинства.

Если существует альтернатива, которая побеждаетбольшинством голосов, то она выбирается. Иначе альтернатива x , закоторую подано наименьшее число голосов, отбрасывается и процедураприменяется снова на уменьшенном множестве альтернатив X  A \ x ипрофиле P / X .Для указанного в таблице 3.1 профиля на первом этапе будетотброшена альтернатива "c". Этого будет недостаточно, поэтому затембудет исключена альтернатива "b", за которую подан всего лишь один54голос.

В результате за альтернативы "a" и "d" подано одинаковоеколичество голосов, и мы не можем исключить одну альтернативу снаименьшим числом голосов. Таким образом, выбором будет C ( P)  a, d 7. Процедура КумбсаПроцедура изначально похожа на процедуру Хара. В началепервого этапа используется правило простого большинства. Еслисуществует альтернатива, которая побеждает большинством голосов, тоона выбирается. Иначе альтернатива x , против которой поданонаибольшее число голосов (у наибольшего числа агентов даннаяальтернатива стоит на последнем месте), отбрасывается, и процедураприменяется снова на уменьшенном множестве альтернатив X  A \ x ипрофиле P / X .Для таблицы 3.1. согласно алгоритму на первом этапеисключается альтернатива "a", при этом на уменьшенном профиле ниодна из оставшихся альтернатив не имеет простого большинства.Однако на следующем шаге мы не можем исключить никакойальтернативы, так как все альтернативы имеют одинаковое числохудших мест.

Таким образом процедура останавливается, и выборомстановится набор: C ( P)  b, c, d 8. Процедура исключения Борда [23]Сначала рассчитывается ранг Борда для каждой альтернативы,затем отбрасывается альтернатива с наименьшим рангом, и процедураприменяется снова на уменьшенном множестве альтернатив X  A \ x ипрофилеP/ X.Процедураостанавливается,когданевозможновыбросить альтернативу, так как после выбрасывания выбор станетпустым.Для примера из таблицы 3.1. на первом этапе исключаетсяальтернатива "c", и затем ранги Борда пересчитываются для новогопрофиля. Новые ранги r(a)=6, r(b)=5, r(d)=7.

Выкидывается альтернатива55"b" и получается, что в новом профиле одинаковые ранги Борда уальтернатив "a" и "d", поэтому выбором будет C ( P)  a, d .Отметим, что данное правило также называется правиломБолдуина [23].9. Процедура НэнсонаСначала рассчитывается ранг Борда для каждой альтернативы, затем рассчитывается средний ранг альтернатив r =  r (a, P) / A , иальтернативыx Aвыбрасываются,если aAr ( x, P) < r.Затемрассматривается множество X = {a  A : r (a, P)  r} , и процедура сноваприменяется на профиле P/X .Следует заметить, что это модифицированная процедура.

Воригинальной статье [79] предлагается исключать все альтернативы, укоторых ранг Борда меньше и равен среднему, а не только меньше, как врассматриваемом правиле.Для примера из таблицы 3.1. порядок исключения альтернативсовпадает с процедурой исключения Борда, поэтому выбором будетC ( P)  a, d .3.2.2 Правила, использующие мажоритарное отношениеОпределим мажоритарное отношение  для профиля P :xy  card{i  N | xPi y}  card{i  N | yPi x} .Иначе говоря, xy , тогда и только тогда, когда альтернатива xпобеждает альтернативу y простым большинством при попарномсравнении.10. Минимальное доминирующее множествоНабор X называется доминирующим множеством, если любаяальтернатива в X доминирует каждую альтернативу вне X согласномажоритарному отношению.

Иначе говоря x  A :56x  X  y  A \ X , xyДоминирующее множество называется минимальным, если ниодно из его собственных подмножеств не является доминирующим.Коллективный выбор согласно данному правилу является минимальнымдоминирующим множеством: C ( P)  X . Если таких множеств несколько,то выбор является их объединением.Для примера из таблицы 3.1. мажоритарный граф будетсодержать только две связи (в силу особенностей примера и четногочисла агентов): bc и db . Таким образом, минимальное доминирующеемножество будет: C ( P)  a, b, d 11.

Минимальное недоминируемое множествоНабор X называется недоминируемым множеством, если несуществует никаких альтернатив вне X , которые доминируют хотя быодну альтернативу в X согласно мажоритарному отношению. Иначеговоря x  A :x  X  y  A \ X , yxНедоминируемое множество называется минимальным, если ниодно из его собственных подмножеств не является недоминируемым.Коллективный выбор согласно данному правилу является минимальнымнедоминируемыммножеством: C ( P)  X .Еслитакихмножествнесколько, то выбор является их объединением.Так как мажоритарный граф не меняется при смене метода, тодля примера из таблицы 3.1. он также будет содержать только две связи:bc и db .Здесь существует два минимально недоминируемыхмножества a и d  , поэтому выбором будет их объединение:C ( P)  a, d .12.

Минимальное слабоустойчивое множествоНабор X называется слабоустойчивым множеством, если x  Ax  X  y  A \ X , yx  z  X , zy57Иначе говоря, x  X тогда и только тогда, когда если существуетальтернатива y извне, которая доминирует x , то существует какая-тоальтернатива z из X , которая доминирует y по мажоритарномуотношению. Слабоустойчивое множество называется минимальным,еслиниодноизегособственныхподмножествнеявляетсяслабоустойчивым. Коллективный выбор согласно данному правилуявляется минимальным слабоустойчивым множеством: C ( P)  X . Еслитаких множеств несколько, то выбор является их объединением.Для примера из таблицы 3.1.

минимальными слабоустойчивымимножествами будут множества a и d  , поэтому выбором будет ихобъединение: C ( P)  a, d .13. Правило ФишбурнаПостроим верхний срез альтернативы x для мажоритарногоотношения  : D( x)  y  A : yx . То есть это множество альтернатив,которые предпочтительнее x в мажоритарном отношении. На основеверхних срезов построим следующее отношение:x y  D( x)  D( y) .Выбором является множество альтернатив, не доминируемых по , т.е.x  C ( P)  y  A | y x .Дляпримераизтаблицы3.1верхниеконтурыбудутследующими: D(a)   , D(b)  d  , D(c)  b , D(d )   .

Таким образом,бинарное отношение  будет включать в себя следующие связи: a  b ,a  c , d  b , d  c . По определению, выбором будет C ( P)  a, d .14. Непокрытое множество 1Построим нижний срез альтернативы x для мажоритарногоотношения  :L( x)  y  A : xy . То есть это множество альтернатив,58которые хуже x в мажоритарном отношении. На основе нижних срезовпостроим следующее отношение:x  y  L( x)  L( y) .Выбором является множество альтернатив, не доминируемых по , т.е.x  C ( P)  y  A | y x .Дляпримераизтаблицы3.1.нижниеконтурыбудутследующими: L(a)   , L(b)  c , L(c)   , L(d )  b . Таким образом,бинарное отношение  будет включать в себя следующие связи: b  a ,b  c , d  a , d  c .

По определению выбором будет C ( P)  b, d  .15. Непокрытое множество 2На основе верхних срезов построим следующее отношение:x y  D( x)  D( y) .Выбором является множество альтернатив, не доминируемых по , т.е.x  C ( P)  y  A | yx .Как уже было сказано выше, для примера из таблицы 3.1. верхниеконтуры будут следующими: D(a)   , D(b)  d  , D(c)  b , D(d )   .Таким образом, бинарное отношение  будет включать в себяследующие связи: a  b , a  c , d  b , d  c . Новых связей (по сравнению спохожим правилом Фишбурна) здесь не добавится, поэтому выбор неизменится и будет C ( P)  a, d .16. Правило РичлсонаНа основе нижних и верхних срезов построим следующееотношение:x  y  L( x)  L( y)  D( x)  D( y)  L( x)  L( y)  D( x)  D( y)То есть одновременно должно наблюдаться нестрогое вложениенижних и верхних срезов, но в тоже время хотя бы одно из вложений59должно быть строгим.

Выбором является множество альтернатив, недоминируемых по  , т.е.x  C ( P)  y  A | yx .Для профиля из таблицы 3.1 бинарное отношение  будетсодержать только d  c , поэтому выбором будет C ( P)  a, b, d 17. Правило Коупленда 1Построим функцию u(x) , принимающую значения равныеразности мощностей нижнего и верхнего срезов альтернативы x длямажоритарного отношения  : u( x)  card ( L( x))  card ( D( x)) . Тогда вколлективныйвыборвходятальтернативы,обеспечивающиемаксимальное значение функции u(x) :x  C ( P)  y  A | u( x)  u( y)Для примера из таблицы 3.1 u(a)  0 , u(b)  0 , u(c)  1 , u(d )  1 ,поэтому выбор будет C ( P)  d .18.

Правило Коупленда 2Построим функцию u(x) , принимающую значения равныемощностинижнегосрезаальтернативыxдлямажоритарногоотношения  : u( x)  card ( L( x)) . Тогда в коллективный выбор входятальтернативы, обеспечивающие максимальное значение функции u(x) :x  C ( P)  y  A | u( x)  u( y)Для примера из таблицы 3.1 u(a)  0 , u(b)  1 , u(c)  0 , u(d )  1 ,поэтому выбор будет C ( P)  b, d  .19. Правило Коупленда 3Построим функцию u(x) , принимающую значения равныемощностиверхнегосрезаальтернативыxдлямажоритарногоотношения  : u( x)  card ( D( x)) .

Тогда в коллективный выбор входятальтернативы, обеспечивающие минимальное значение функции u(x) :x  C ( P)  y  A | u( x)  u( y)60Для примера из таблицы 3.1. u(a)  0 , u(b)  1 , u(c)  1 , u(d )  0 ,поэтому выбор будет C ( P)  a, d .3.2.3 q-Паретовские правилаДанная группа правил была представлена Алескеровым в работе[14] и исследована в [15] .20. Сильное q-Паретовское правило простого большинстваПусть f ( P; {i}, q) = {x  A : Di ( x)  q} , где Di (x) - это верхний срезальтернативыxдляагента i ,т.е.Di ( x)  y  A : yPi x .ПустьnI = {I  N : I =  } есть семейство минимальных коалиций, обладающих2простым большинством.