birmaga.ru
добавить свой файл

1


23.10.07

N-ядро

Лексимин


Определение. Будем говорить, что вектор не хуже вектора в смысле лексикографического порядка и писать , если либо x=y, либо существует i=1,…,n, для которого xi>yi и xi=yj для всех j<i.

  • Картинка {y: } и {y: yx }

Лемма. Отношение является отношением линейного порядка, то есть выполняются условия

  1. для любых векторов x и y либо xy, либо yx;

  2. для любого вектора x имеет место отношение xx;

  3. если xy и yx, то x=y;
  4. если xy и yz, то xz.


Доказательство. Докажем условие 1. Если x=y, то доказывать нечего. В противном случае множество индексов i, для которых xiyi не пусто. Пусть k – наименьший из таких индексов. Тогда xi=yi для всех i<k и имеет место одно из двух неравенств xk>yk или xk<yk. В первом случае xy, а во втором – yx.

Свойство 2 очевидно.

Докажем свойство 3. Допустим противное. Тогда множество индексов i, для которых xiyi не пусто. Пусть k – наименьший из таких индексов. Если xk>yk, то приходим к противоречию с условием yx, а если xk<yk, то получается противоречие с условием xy.

Остается доказать свойство 4. Если x=y или y=z утверждение очевидно. В противном случае пусть i – наименьший индекс, для которого xi>yi, а k – наименьший индекс, для которого yk>zk. Если ik, то для j<i выполняются равенства xj=yj=zj, и xi>yizi, значит, xz. Если же k<i, то для j<k выполняются равенства xj=yj=zj, и xiyi>zi и опять xz.


Лемма. Если множество X компактно, а отображение непрерывно, то множество таких xX, что для любого yX, не пусто и компактно.

Доказательство по существу проведено в предыдущем семестре.

Пусть x=(x1,…,xn) – вектор. Обозначим x=(x(1),…,x(n)) вектор, компоненты которого x(1)…x(n) есть компоненты вектора x, упорядоченные по возрастанию.

Лемма. Отображение, ставящее в соответствие вектору x вектор непрерывно.

Доказательство. Пусть k – семейство всех подмножеств множества N, содержащих k элементов. Тогда . Из утверждений, доказанных ранее, следует, что функция x(k) непрерывна. Так как все компоненты интересующего нас отображения непрерывны, непрерывно и оно само.

Определение. Будем говорить, что вектор не хуже вектора в смысле лексиминного порядка и писать , если .

  • Картинка {y: } и {y: yx }


Лемма. Отношение является отношением предпорядка, то есть выполняются условия

  1. для любых векторов x и y либо xy, либо yx;

  2. для любого вектора x имеет место отношение xx;

  3. если xy и yz, то xz.

Кроме того, выполняется условие

4. если xy и yx, то .

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

Обозначим множество всех таких xX, что для любого yX.

Лемма. Если множество X компактно, а отображение непрерывно, то множество не пусто и компактно.

Доказательство. Отображение x(f(1) (x),…f(n)(x)) непрерывно как суперпозиция непрерывных отображений. Тогда существует x, для которого отношение

(f(1) (x),…f(n)(x))(f(1) (y),…f(n)(y)) выполняется для всех y. Очевидно, . Множество замкнуто как прообраз точки при непрерывном отображении x(f(1) (x),…f(n)(x)), а, следовательно, компактно.

Лемма. Если x и y принадлежат множеству , то .

Лемма. Если x, то x – эффективная стратегия.

Доказательство. Достаточно заметить, что если x доминирует по Парето y, то
f(x) f(y).

Лемма. Если множество выпукло, то множество содержит не более одного элемента.

Доказательство. Допустим, что множество содержит два различных вектора x и y. Чтобы получить противоречие, достаточно доказать, что отношение xz не выполняется для


По определению xix(1) и yiy(1) для всех i. Сложив эти неравенства и разделив пополам, получим zix(1), так как x(1)=y(1). Следовательно, z(1)x(1). Если последнее неравенство – строгое, доказательство завершено.

Остается рассмотреть случай z(1)=x(1).Пусть номер i удовлетворяет условию zi=z(1). Тогда xi=x(1) и yi=y(1). Тогда для всех ji выполняются неравенства xjx(2) и yjy(2). Отсюда аналогичными рассуждениями получается, что xj=x(2) и yj=y(2) для некоторого j.

Повторяя эти рассуждения далее, придем к выводу, что x=y, что противоречит условию.

Мотивировка и определение


  • Д. Шмайдлер (Schmeidler D.), 1969

  • Философия эгалитаризма

  • Кэрин Грин

Рассмотрим игру в форме характеристической функции <N,v>.

Определение. Эксцессом вектора относительно коалиции K называется число .

Пусть B – множество векторов , удовлетворяющих равенству . Для каждого вектора определено 2n–2 чисел e(x,K), где K пробегает множество собственных коалиций. Упорядочив множество собственных коалиций каким-то образом, мы можем рассматривать набор e(x) чисел e(x,K), как элемент

2n–2-мерного векторного пространства.

Определение. Всякий элемент множества называется N-ядром игры <N,v>.

Лемма. Во всякой игре существует единственное N-ядро.

Доказательство. Пусть x0 – произвольный вектор из множества B, а . Рассмотрим множество A={xB: e(x,K)≥E, KN}. Это множество компактно, выпукло и не пусто, так как ему принадлежит, например, вектор x0. Следовательно, множество состоит ровно из одного вектора x.

Очевидно, что этот вектор не хуже любого вектора yB\A в смысле лексиминного порядка, что завершает доказательство.

Лемма. Во всякой игре N-ядро является дележом.

Доказательство. Пусть xN-ядро рассматриваемой игры. Коллективная рациональность вектора x немедленно следует из определения. Докажем индивидуальную рациональность.

Допустим, что xi<v(i). Обозначим . Тогда iK для любой коалиции K. В самом деле, иначе



(нестрогое неравенство следует из супераддитивности), сто противоречит выбору коалиции K.

Определим вектор y условием


где положительное число, которое меньше, чем . Для K выполняются неравенства


,

а для K справедливы неравенства



для некоторой коалиции I. Значит отношение (e(x,K))KN(e(y,K))KN не верно, что противоречит выбору вектора x. Лемма доказана.

Теорема о селекторе


Теорема. Если в игре <N,v> C-ядро не пусто, то N-ядро содержится в нем.

Доказательство. По теореме о характеризации ядра C-ядро состоит из всех дележей, для которых e(x,K)≥0 для всех коалиций K. Если это множество не пусто, то ему обязательно принадлежит N-ядро.

  • Эгалитаризм и устойчивость!

  • Решение неразрешимых систем

Поиск N-ядра


Приведем алгоритм поиска N-ядра.

Обозначим 1 множество всех собственных коалиций. Прежде всего, найдем максимум функции на множестве векторов, удовлетворяющих равенству . N-ядро непременно принадлежит множеству решений данной задачи. Введением вспомогательной переменной w эта задача сводится к следующей задаче линейного программирования.

Задача 1. wmax,

we(x,K), K1,

.

Решению (x1,w1) этой задачи соответствует седловая точка (x1,w1,1,1) функции Лагранжа



где двойственные переменные K неотрицательны, а переменная произвольна.

Отсюда следует, что , а значит множество не пусто. Тогда для любой коалиции K1 выполняется равенство . Положим 2=1\1.

Решив задачу 1, перейдем к решению задачи 2

Задача t. wmax,

we(x,K), Kt,

,

w1e(x,K), K1,



wt1e(x,K), Kt–1.

Очевидно, эта задача эквивалентна поиску максимума функции на множестве векторов, удовлетворяющих условиям

,

w1e(x,K), K1,



wt–1=e(x,K), Kt–1.

Если N-ядро принадлежит множеству допустимых решений этой задачи, то он принадлежит и множеству ее максимумов.


Решению (x1,w1) этой задачи соответствует седловая точка (xt,wt,t,t) функции Лагранжа



где двойственные переменные K неотрицательны, а переменная произвольна.

В силу выбора величин wk, для Kk выполняются равенства wk=e(xk,K). Как и выше устанавливается, что множество не пусто, и для всякой коалиции Kt выполняется равенство wt=e(xt,K).

Решив задачу t, переходим к задаче t+1, если ранг системы уравнений

w1=e(x,K), K1,



wt=e(x,K), Kt

меньше n. В противном случае останавливаем работу алгоритма.

Так как число уравнений в этой системе с каждым шагом растет, работа алгоритма непременно остановится.

Единственное решение этой системы уравнений и будет N-ядром.

Процесс поиска N-ядра может быть унифицирован переходом к решению двойственных задач. Задача 1 эквивалентна решению следующей задачи.

Задача 1*.

,

,

K≥0, K1.


Положив , придем к эквивалентной задаче



,

K≥0, K1.

Так как задачи эквивалентны, максимум в последней задаче достигается в одной из крайних точек множества ее допустимых значений. Зная крайние точки множества сбалансированных покрытий, этот максимум легко найти.

Аналогичным образом модифицируется и решение задачи t.

При малом числе игроков множество сбалансированных покрытий может быть описано явно, что позволяет эффективно находить N-ядро.

Примеры


  • N-ядро в играх трех лиц: картинки

  • N-ядро в играх трех лиц: алгоритм (Углы ((1),(2),(3),(23),(13),(12))=(1,1,1,0,,0,0),(1,0,0,1,0,0), (0,1,0,0,1,0), (0,0,1,0,0,1), (0,0,0,1/2,1/2,1/2)). Пример: v(1,2,3)=12, v(12)=2,, v(13)=3, v(23)=9,остальные нули. Ответ (0,11/2,13/2).

  • Производство кукурузы

  • Сбалансированный однопродуктовый рынок

  • Затраты на взлетную полосу

Доказательство теоремы Гермейера–Вателя


Полученные выше результаты позволяют доказать теорему Гермейера–Вателя, не опираясь на теорему Брауэра о неподвижной точке. Напомним соответствующую модель.

Пусть N={1,…,n} – множество игроков, – множество управлений i-го игрока, функции fi:Ui, i=1,…,n непрерывны и строго возрастают по каждому аргументу, а функция непрерывна и строго возрастает по каждому аргументу. Пусть, кроме того, F(0)0, а fi(0)=0 для всех i=1,…,n. Определим функцию выигрыша i-го игрока условием


gi(u1,…,un)=min{F(u1,…,un),fi(ai–ui)} (i=1,…,n)

(здесь принято обозначение ).

Игру =N,U1,…,Un,g1,…,gn будем называть игрой Гермейера–Вателя.

Лемма. Для того, чтобы необходимо, чтобы существовало разбиение множества игроков N=RS (RS=) для которого выполняются условия

() fi(aiui)=F(u) для всех iR;

() ui=0, fi(ai)<F(u) для всех iS.

Доказательство. Пусть .

Докажем сначала, что fi(aiui)F(u) для всех iN. Действительно, в противном случае fi(aiui)>F(u) для некоторого i. В силу предполагаемых свойств функций F и fi тогда для какого-то j. Обозначим 2= fi(aiui)–F(u) и


Фиксируем >0 так, чтобы выполнялись условия fi(aiv()i)>fi(aiui)–, 0<F(uvi())<F(u)+ и vi()ai ( такое существует, так как функции F и fi непрерывны). Тогда
fi(aiv()i)>F(uvi()) и, следовательно, gi(uvi())=F(uvi())>F(u)=gi(u). Для остальных игроков gk(uvi())≥gk(u), так как их личные критерии fk остаются неизменными, а общественный критерий возрастает при переходе от ситуации u к ситуации (uvi()). Значит, стратегия u не является эффективной, и тем более не верно, что . Получено противоречие.

Пусть теперь fi(ui)<F(u). Докажем, что ui=0. Вновь предположим противное. тогда для некоторого j. Обозначим 2=F(u)–fi(aiui) и


Фиксируем >0 так, чтобы выполнялись условия fi(aiv()i)<fi(aiui)+, F(uvi())>F(u)– и vi()≥0 ( такое существует, так как функции F и fi непрерывны). Тогда

fi(aiv()i)<F(uvi()) и, следовательно, gi(uvi())=fi(aiv()i)> fi(aiui)=gi(u). Для тех игроков k, для которых gk(u)gi(u) будем иметь fk(akuk)=gk(u) gi(u)= fi(aiui)< F(uvi()), поэтому gk(uvi())=gk(u), а это вновь противоречит выбору ситуации u.

Для доказательства леммы достаточно теперь взять R={iN: fi(aiui)=F(u)} и S=N\R.

Теорема. В игре Гермейера–Вателя существует ситуация равновесия по Нэшу.

Доказательство. В силу доказанной в первом разделе леммы, существует . В силу предыдущей леммы, тогда выполняются условия () и (). Но в предыдущем семестре установлено, что эти условия достаточны для того, чтобы ситуация u была ситуацией равновесия по Нэшу.

Задачи

    1. Пусть – автоморфизм игры, а x – ее N-ядро. Докажите, что x(i)=xi для любого i.


    2. Определим отображения следующим образом. Если y=ij(x), то yk=xk при ki,j, yi=xi, yj=xj, если xi<xj и yi=xj, yj=xi в противном случае. Докажите что эти отображения непрерывны. Докажите, что отображение, ставящее в соответствие вектору x вектор представима как суперпозиция отображений ij, и, следовательно, непрерывно.

    3. Рассмотрим точку в трехмерном пространстве. Как можно охарактеризовать лексиминный оптимум расстояний от этой точки до ребер заданного тетраэдра.

    4. Являются ли условия

() fi(aiui)=F(u) для всех iR;

() ui=0, fi(ai)<F(u) для всех iS.

достаточными для выполнения включения ?


Литература


  1. Мулен Э. Кооперативное принятие решений: Аксиомы и модели. М.: Мир.1991.

  2. Кукушкин Н.С., Морозов В.В. Теория неантагонистических игр. М.: МГУ. 1984.

  3. Вилкас Э.Й. Оптимальность в играх и решениях. М,: Наука, 1990

149119.doc 19.09.14