Автореферат (Концепции решений в задаче коллективного выбора), страница 3

Альтернатива x называется обобщенно-устойчивой, если любаядругая альтернатива в A достижима из x, в противном случае x называетсянеустойчивой. По аналогии с альтернативами множество альтернатив Xназывается обобщенно-устойчивым множеством, если любая альтернатива, непринадлежащая X, достижима из какой-либо альтернативы, принадлежащей X,в противном случае множество X считается неустойчивым.Определеннаяинтерпретированаданнымдинамически.образомустойчивостьЕстественноможетрассматриватьбытьнекоторуюпозицию (состояние системы), как более устойчивую, если ее "труднее"изменить.

В играх, связанных с голосованием, под "системой" подразумеваетсяобъект коллективного управления. Альтернативами являются различныезначения параметров или условий функционирования объекта, зависящие отрешений управляющей группы. При этом под "состоянием системы" можетпониматься как сама альтернатива, являющаяся status quo, то есть текущеезначение параметров управления, так и некоторое множество альтернатив, ккоторому status quo принадлежит.

Данное состояние системы тем "труднее"изменить, чем меньше усилий (шагов игры, раундов голосования) необходимодля того, чтобы вернуть систему назад в это состояние после того, каксостояние системы было изменено в очередном раунде голосования.Вводится понятие расстояния до альтернативы от альтернативы и отмножества альтернатив. Устойчивые альтернативы и устойчивые множестваразличаются по степени своей устойчивости, которая измеряется расстояниемдо самой далекой альтернативы от данной альтернативы или множества.Устойчивые альтернативы и минимальные устойчивые множества одногопорядка устойчивости k образуют, соответственно, класс k-устойчивыхальтернатив SP(k) и класс k-устойчивых множеств SS(k).

Множества этих классовявляются фильтрациями минимального доминирующего множества, то есть14образуют микроструктуру турнира. Их можно рассматривать как обобщениянепокрытого множества и слабоустойчивого множества, поскольку класс 2устойчивых альтернатив есть непокрытое множество, SP(k)=UC, а класс 1устойчивых множеств есть объединение минимальных слабоустойчивыхмножеств SS(k)=MWS.Доказывается теорема о непустоте классов k-устойчивых альтернатив.Теорема 3.1 Если победитель Кондорсе отсутствует, то каждый классустойчивых альтернатив порядка k меньшего либо равного максимальному ибольшего единицы непуст, SP(k)≠, 2≤k≤m=maxxMDk(x), где k(x) - порядокустойчивости альтернативы х.Вводится множество P(k) - множество тех альтернатив, от которых можнодостичь любой альтернативы в A не более чем за k шагов.

По определению P(k)есть прямая сумма всех классов устойчивых альтернатив порядка k и меньше,P(k)=SP(1)+SP(2)+…+SP(k).Согласноопределениюотношениязахватаальтернатива x является незахваченной, если любая альтернатива в Aдостижима из x за не более чем три шага. Таким образом, P(3) - этонезахваченное множество UCp, P(3)=SP(1)+SP(2)+SP(3)=UCp.Следовательно, в минимальном доминирующем множестве MD возникаетследующая система подмножеств:1) P(1)={CW}=MD; если P(1)=, то2) P(2)=UC≠, непокрытое множество;3) P(3)=UCp, незахваченное множество;4) P(1)P(2)P(3)…P(m-1)P(m)=MD,m=maxxMDk(x),причемвсевложения строгие согласно Теореме 3.1.Вводится множество S(k) - объединение всех минимальных обобщенноустойчивых множеств, из которых можно достичь любой альтернативы, непринадлежащей данному множеству, за не более чем k шагов. Очевидно,множество S(k) есть прямая сумма классов устойчивых множеств порядка k именьше, S(k)=SS(1)+SS(2)+…+SS(k)15Между множествами, введенными с помощью понятия устойчивости,устанавливается связь, аналогичная связи, установленной для UC и MWSТеоремой 2.1.

Эта связь определяется Теоремой 3.2.Теорема 3.2 1) P(2)S(1)P(3) (то есть UCMWSUCp);2) k: k>1 P(k)S(k)P(k+2).Следствие xSP(2)  xSS(1); xSP(k), k>2  (xSS(k-2), или xSS(k-1), илиxSS(k)) & xSS(i), (i>k) или (i<k-2).В качестве примеров рассмотрим следующие три турнира.A={a, b, v, w, x, y, z};µ1={(a, b), (a, w), (a, x), (a, y), (a, z), (b, v), (b, x), (b, y),(b, z), (v, a), (v, w), (v, x), (v, z), (w, b), (w, x), (w, y), (x,y), (x, z), (y, v),(y, z), (z, w)} (рис.

5);Рис. 1µ2={(a, b), (a, w), (a, x), (a, y), (a, z), (b, v), (b, x), (b, y),(b, z), (v, a), (v, w), (v, x), (v, z), (w, b), (w, x), (w, y), (x,y), (x, z), (y, v),(z, w), (z, y)} (рис. 6);Рис. 2µ3={(a, b), (a, w), (a, x), (a, y), (a, z), (b, v), (b, x), (b, y),(b, z), (v, a), (v, x), (v, z), (w, b), (w, v), (w, x), (w, y), (x,y), (x, z), (y, v),(z, w), (z, y)} (рис. 7).Рис. 3Для каждого орграфа распределение альтернатив по классам альтернатив{SP(k)} и классам множеств {SS(k)} показано в Таблице 3.16Таблица 3. Распределение альтернатив по классам альтернатив {SP(k)} иклассам множеств {SS(k)} для орграфов, изображенных на рис.

1, 2, 3.Рисунок 1Рисунок 2SP(2)SP(3)a, b, vy, wSS(1)SS(2)zSS(2)SS(3)xSS(3)SS(1)SP(2)SP(3)a, b, vy, wРисунок 3SP(4)SS(1)zxSP(2)SP(3)a, b, v, wy, zSS(2)SS(3)xЭти примеры демонстрируют, что реализуются все три теоретическивозможныхвариантапринадлежностиk-устойчивойальтернативыкопределенному классу устойчивых множеств: x(SS(k-2), SP(k)), x(SS(k-1), SP(k)),x(SS(k), SP(k)).

Следовательно, ситуацию P(2)S(1) нельзя обобщить на всемножества {S(k)}, {P(k)} и сделать утверждение Теоремы 3.2 более сильным.Очевидно, вложение P(2)S(1) (UCMWS) - это всего лишь "граничный эффект".Важно отметить, что P(k)S(k)P(k+2) не означает, что имеет место либоP(k)S(k)P(k+1), либо P(k+1)S(k)P(k+2). Турнир (A, µ2) показывает, что возможныслучаи, когда существуют пары альтернатив (x, y), одна из которых (x)принадлежит классу множеств более устойчивых и классу альтернатив менееустойчивых по сравнению с другой (y), x(SS(k-2), SP(k)), y(SS(k-1), SP(k-1)).Следовательно, несмотря на то, что можно сравнивать альтернативы поустойчивости, используя классы устойчивых альтернатив {SP(k)} или классыустойчивых множеств {SS(k)}, эти системы классов не порождают совместногопорядка.

Можно считать альтернативу x более устойчивой, чем альтернатива y,когда x(SS(k), SP(l)), y(SS(m), SP(n)), k≤m, l≤n & (k<m или l<n), но нельзясравнить альтернативы x(SS(k-2), SP(k)) и y(SS(k-1), SP(k-1)).В итоге демонстрируется, что в турнирах иерархии классов k-устойчивыхальтернативиk-устойчивыхмножестввсовокупностисиерархиейдоминирующих множеств порождают соответственно микро- и макроструктуру множества альтернатив, в основе которых лежит различие вустойчивости.17В четвертой главе «Матрично-векторное представление решений и егокомпьютерная реализация» представление произвольного отношения напроизвольноммножествеспомощьюматрицыинцидентностисоответствующего орграфа и представление произвольного подмножестваданного множества с помощью характеристического вектора используются длятого, чтобы почти все рассмотренные концепции решений и их обобщения(классы k-устойчивых альтернатив и множеств) единообразно представить влогико-алгебраической форме - в виде булевых векторов, значения которыхопределяются как результат последовательности арифметических операций надбулевыми матрицами, представляющими отношения.

Это представлениерешений обеспечивает удобный алгоритм их вычисления.В данной главе также вводятся пять новых версий непокрытогомножества и одна (третья) новая версия слабоустойчивого множества.В разделе 4.1 даются основные определения понятий, связанных сматрично-векторным представление множеств и отношений. Матрица R=[rij]представляет отношение  на A, если  i, jA rij=1  (i, j) и rij=0  (i, j).Произвольное множество альтернатив B, BA, может быть представлено спомощью характеристическогоn-компонентного(n=|A|)вектораb=[bi],определяемого следующим образом:  iA bi=1  iB и bi=0  iB.

В данномразделе устанавливается основное соотношение, используемое в дальнейшемдля получения матрично-векторных представлений решений, - формула векторамножества максимальных элементов MAX() данного отношения .Лемма 4.2. 1) Если матрица R является представлением отношения , товектор max() множества максимальных элементов этого отношения MAX()выражается формулой max()= (R  R tr )  a ; 2) если  полно, то max()= (R  E)  a ;3) если  асимметрично, то max()= R tr  a . Здесь Е - это единичная матрица.Раздел 4.2 посвящен рассмотрению свойств матричных представленийM, T и U отношений µ,  и =, где  - это отношение идентичности,репрезентируемое матрицей E.18В разделе 4.2 дается матрично-векторное представление таких решений,как победитель Кондорсе и ядро.

По определению Cr=MAX(µ). Так как µ - этоасимметричная часть отношения , то согласно Лемме 4.2 и Следствию из нееCr=MAX(µ)=MAX() и cr=max(µ)=max()= M tr  a = U  a = (M  T  E)  a .Если булева матрица R есть сумма каких-то матриц X и Y, то есть, еслиR=X+Y, то rij=1  xij=1  yij=1. Пусть R=M+E.

Если rij=1 для любого j, тогдаальтернатива i есть победитель Кондорсе. Следовательно, cw= (M  E)  a будетхарактеристическим вектором множества победителей Кондорсе.В разделе 4.3 дается представление всех версий непокрытого множестваnUC.

Если взять произведение матриц R=MM, то элемент rij=  mik  mkj не будетk 1равен нулю тогда и только тогда, когда существует, по крайней мере, однаальтернатива k, такая, что альтернатива i доминирует над альтернативой k, аальтернатива k доминирует над альтернативой j. С помощью этого наблюденияможно построить матрицы, представляющие пять версий отношения покрытияN (N=IV). Поскольку во всех версиях отношение покрытия асимметрично, тотолько непокрытые альтернативы являются максимальными элементамиотношения покрытия , то есть, UCN=MAX(N) (N=IV).

Таким образом, длявычисления ucN (N=IV) непокрытых множеств UCN (N=IV) можноиспользовать Лемму 4.2. Например, ucIII=max(III)= (T  M  M  M  M  T  E)  a .В разделе 4.4 дается матрично-векторное представление незахваченногомножества UCp. Схема рассуждений аналогична тем, что используются впредыдущем разделе. В итоге ucp=max()= (M  U  M  U  M  M  U  U)  a .В разделе 4.5 дается матрично-векторное представление минимальногодоминирующего множества MD, минимального недоминируемого множестваkMU и незапертого множества UT.

Рассмотрим матрицы M(k)=  M i +E иi 1kU(k)=  U i ; m(k)ij=1 тогда и только тогда, когда есть µ-путь от альтернативы i доi 119альтернативы j, ji, длины l: 0<lk, также m(k)ii=1 для всех i, 1in.Следовательно, M(k) есть матрица, представляющая k-транзитивное замыканиеотношения µ, k(µ). Соответственно, U(k) - это матрица, представляющая k().Т.к. A конечно, то существует минимальный µ-путь длины большей либоравной длине любого другого минимального µ-пути в A.