Мотивировка и определение. Теория игр. Игры и их решение
Выбери формат для чтения
Загружаем конспект в формате doc
Это займет всего пару минут! А пока ты можешь прочитать работу в формате Word 👇
16.10.07
Вектор Шепли.
Мотивировка и определение
Определение. Автоморфизмом игры называется всякая перестановка элементов множества N, удовлетворяющая условию: v(K)=v((K)) для любой коалиции K.
• Рюрик
• Плата за участие в игре
Определение. Вектором Шепли называется отображение, которое каждой игре в форме характеристической функции ставит в соответствие дележ в соответствующей игре, если оно удовлетворяет следующим условиям:
1. для любого носителя K (аксиома эффективности);
2. для любого автоморфизма игры (аксиома симметрии);
3. для любых двух игр и (аксиома агрегации).
Лемма. Вместо аксиомы эффективности можно использовать следующее свойство
4. для любого болвана i (аксиома болвана).
Доказательство. Пусть выполнены аксиомы 1,2,3. Рассмотрим произвольного болвана i. Множество N\{i} является носителем, поэтому . Так как игрок i является болваном v(N\{i})+v(i)=v(N). А так как вектор (v) является дележом в игре выполняется условие. Сравнивая три полученных равенства, получим , то есть выполняется аксиома 4.
Обратно, пусть выполняются аксиомы 2, 3 и 4. Рассмотрим произвольный носитель K. Так как все игроки, не входящие в K являются болванами, выполняется условие . По аксиоме болвана v(j)=j(j) для jN\K. А так как вектор (v) является дележом в игре выполняется условие. Из этих трех условий получаем равенство , означающее, что выполнено утверждение аксиомы 1.
Лемма. Возможно задание вектора Шепли двумя свойствами:
5. для любой перестановки множества N (аксиома анонимности);
6. если для всех коалиций K не содержащих игрока i, то i(v)= i(w) (аксиома маргинальности).
Вычисление вектора Шепли
Теорема. Единственная функция, удовлетворяющая аксиомам Шепли, задается формулами
, i=1,…,n. (*)
• Маргинальность. Можно в качестве аксиомы.
• Каждому по способностям.
Доказательство. Начнем с анализа аксиом.
Лемма. Если j – болван, то из аксиом Шепли следует, что j(v)=v(j).
Доказательство см. в предыдущем разделе.
• используется только первая аксиома.
Лемма. Для любого неотрицательного числа и простейшей игры вектор аксиомам Шепли удовлетворяет только вектор, определяющийся условиями
Доказательство. Если коалиция R состоит из одного игрока, утверждение следует из первой аксиомы.
Пусть i и k – любые два игрока из коалиции R. Рассмотрим перестановку , меняющую местами игроков i и k, и оставляющую всех остальных игроков на месте. Непосредственно проверяется, что эта перестановка является автоморфизмом. Тогда по второй аксиоме i(v) =k(v). Таким образом, все компоненты вектора , соответствующие игрокам из коалиции R равны. Но эта коалиция является носителем. Значит, по аксиоме 1, сумма этих компонент равна . Отсюда следует первая часть доказываемого утверждения.
Вторая часть следует из предыдущей леммы и того факта, что все игроки, не входящие в R являются болванами.
Лемма. Если разность характеристических функций v и w является характеристической функцией, то (v–w)=(v)–(w).
Доказательство. По аксиоме агрегации в таком случае (v)=(v–w)+(w), откуда и следует утверждение леммы.
Лемма.
Доказательство. Воспользовавшись равенством и формулой бинома Ньютона, получим
Осталось вычислить интеграл в правой части равенства. Очевидно,
.
Интегрируя по частям, получим
.
Отсюда по индукции получаем
что доказывает лемму.
Лемма. Существует не более одной функции, удовлетворяющей аксиомам Шепли.
Доказательство. Разложим функцию v по базису из простейших функций и воспользуемся доказанной выше «аддитивностью» вектора Шепли по отношению к взвешенным суммам простейших функций. Получим
Преобразуем это выражение.
Число коалиций R, содержащих коалицию K и имеющих r членов равно . Остается воспользоваться результатом предыдущей леммы.
Теперь проверим, что функция, определенная формулами (*), удовлетворяет всем аксиомам Шепли.
Лемма. Формула (*) определяет дележ.
Доказательство. Докажем индивидуальную рациональность. В силу супераддитивности
Внутренняя сумма содержит одинаковых слагаемых, поэтому
Докажем коллективную рациональность. Для этого вычислим сумму
.
Определим коэффициент при v(K) в этой сумме. Если KN, то v(K) входит в эту сумму #K раз с положительным знаком, и #N–#K раз с отрицательным. Следовательно, искомый коэффициент равен
Член v(N) входит в сумму только с положительным знаком, причем #N раз. Следовательно, коэффициент при нем равен
.
Итак, искомая сумма равна v(N), что и доказывает лемму.
Лемма. Формула определяет вектор Шепли.
Доказательство. Проверим выполнение аксиомы эффективности. Если игрок i – болван, то
.
Как установлено при доказательстве предыдущей леммы, сумма в правой части этого равенства равна v(i). Таким образом, для любого болвана i. Поэтому, если K – носитель игры, то и . А в силу предыдущей леммы . Из этих трех условий следует равенство .
Докажем справедливость утверждения аксиомы симметрии. Пусть – произвольный автоморфизм. Имеем
так как вместе с K коалиции (K) весь класс подмножеств множества N. Далее
(последнее равенство справедливо в силу определения автоморфизма). Но тогда
Аксиома 3 справедлива, так как функция по определению линейна.
Лемма, а с ней и теорема доказаны.
Конструктивное определение
Если коалиция K уже сформировалась, то ценность не входящего в нее игрока i с точки зрения этой коалиции равна . Поэтому разумной платой за присоединение игрока i к коалиции K является именно эта величина.
Теорема. Если игроки присоединяются к игре в случайном порядке, причем все порядки равновероятны, то математическое ожидание выигрыша i-го игрока определяется соответствующей компонентой вектора Шепли.
Доказательство. Всего имеется n! Равновероятных исходов. Число исходов, когда игроки, входящие в коалицию K, присоединятся к игре раньше игрока i, равно
#K!(#N–#K–1)!, поэтому вероятность того, что игрок i получит выигрыш , равна . Остается воспользоваться определением математического ожидания и сделать замену переменной суммирования.
• Условие локально!
Вариационное определение
Теорема. Значение вектора Шепли для игры является точкой минимума функции на множестве векторов x, удовлетворяющих условию .
Доказательство. Очевидно, что решение данной оптимизационной задачи существует и единственно. Будем решать ее стандартным методом поиска условного экстремума. Дифференцируя функцию Лагранжа
,
получим систему уравнений
, iN,
или
.
Игрок i входит в коалиций, содержащих игрока i и имеющих k членов, а игрок ji входит в коалиций, содержащих игрока i и имеющих k членов. Поэтому уравнение преобразуется к виду
После упрощений получим
,
или
.
С учетом условия задачи получим
. (#)
Просуммируем все эти уравнения
,
разделим на n и учтем условие задачи
.
Вычитая из уравнения (#), получим
Преобразуем правую часть
В сумму член с v(K) входит #K раз, а в сумму слагаемое v(K\{i}) входит #N-#K раз. Кроме того, каждой коалиции K, содержащей i соответствует коалиция K\{i}, не содержащая i. Поэтому
Отсюда и получается утверждение теоремы.
Примеры
• Производство кукурузы (сначала помещик с помощью интерпретации с подключением к игре, потом – остальные с помощью симметрии)
• Сбалансированы однопродуктовый рынок (противоположные перестановки)
• Затраты на взлетную полосу
Вектор Шепли и C-ядро
Лемма. В 0-1-редуцированной игре трех лиц вектор Шепли принадлежит ядру тогда и только тогда, когда выполняются неравенства
4v({1,2})+ v({1,3}+ v({2,3})) 4, 4v({1,3})+ v({1,2}+ v({2,3})) 4,
4v({2,3})+ v({1,2}+ v({1,3})) 4.
Доказательство. Согласно полученной формуле в данном случае вектор Шепли имеет компоненты
Согласно теореме о характеризации ядра этот вектор принадлежит C-ядру, тогда и только тогда, когда выполняются неравенства
Откуда и следует утверждение леммы.
Пример. Затраты на создание системы водоснабжения в трех районах описываются характеристической функцией v({1})=–120, v({2})=–140, v({3})=–120, v({1,2})=–170, v({1,3})=–160, v({2,3})=–190, v({1,2,3})=–255.
Вектор Шепли в этой игре не принадлежит C-ядру, так как например, . Однако C-ядро в этой игре не пусто. Ему принадлежит, например, точка .
• Вообще говоря, вектор Шепли лежит вне ядра. (Картинка)
Выпуклые игры
В этом разделе рассматриваем только выпуклые игры.
Лемма. Пусть – произвольная перестановка множества N. Тогда вектор x, определяемый условиями (i=2,…,n) является крайней точкой C-ядра, и других крайних точек нет.
Доказательство. Не ограничивая общности, можно считать, что перестановка тождественная. Принадлежность соответствующего дележа C-ядру доказана в лекции, посвященной C-ядру.
Рассматриваемый вектор лежит на границах гиперплоскостей, ограничивающих полупространства
x1≥v({1}), x1+x2≥v({1,2}),…,x1+…+xn≥v({1,…n}).
Нормальные векторы этих гиперплоскостей линейно независимы, поэтому любой вектор y может быть представлен как их линейная комбинация. Если вектор ненулевой, то, по крайней мере, один коэффициент в этом разложении будет ненулевым. Если он отрицателен, то сдвиг в направлении вектора y приведет к нарушению соответствующего неравенства. А если он положителен, то сдвиг в направлении вектора –y приведет к нарушению того же неравенства. В одном из этих случаев точка выйдет за пределы ядра. Следовательно, точка x – крайняя.
Пусть теперь x – крайняя точка C-ядра. Рассмотрим множество
.
Множество (x) замкнуто относительно операций объединения и пересечения. В самом деле, пусть K и I – коалиции из этого семейства. Тогда
(первое и второе неравенства следует из того, что x принадлежит C-ядру, а последнее – из того, что игра выпукла). Значит, на самом деле . Аналогично рассматривается и случай с пересечением.
Пусть =K1K2…Km=N – наибольшая по длине цепочка коалиций, принадлежащих (x). Допустим, что, по крайней мере, два элемента i и j принадлежат Kk+1\Kk.Так как x – крайняя точка C-ядра, она является единственным решением системы уравнений
, K(x).
Поэтому существует K(x) такая, что iK но jK (или наоборот)1. Тогда принадлежит (x) ввиду замкнутости относительно объединения и пересечения и KkSKk+1, что противоречит выбору цепочки.
Следовательно, длина цепочки равна n и вектор x имеет искомый вид.
Теорема. Для выпуклых игр вектор Шепли принадлежит C-ядру.
Доказательство. В силу формулы (*) вектор Шепли является линейной комбинацией точек x. Поскольку C-ядро выпукло, вектор Шепли принадлежит ему.
Определение. Игра называется строго выпуклой, если она выпукла и для любых двух коалиций I и K выполняется неравенство , если только K\I и I\K.
Лемма. Если игра строго выпукла, то все векторы x различны.
Доказательство. Если I и K принадлежат (x), то либо KI, либо IK. Действительно, в противном случае
,
что противоречит строгой выпуклости.
Поэтому соответствие между крайними точками x и множествами (x) взаимно однозначно, а эти множества образуют все цепочки длины n.
Следствие. Для строго выпуклых игр значение вектора Шепли есть центр тяжести крайних точек C-ядра.
Задачи
1. Пусть функции v и w удовлетворяют условиям v(K)=w(K) при KN и v(N)>w(N). Докажите, что i(v)> i(w) для любого iN.
2. Пусть игры и являются аффинно эквивалентными и для любой коалиции i выполняется равенство . Докажите, что i(w)=k i(v)+ai.
3. Пусть функция v определена условием Найдите вектор Шепли соответствующей игры.
4. Какой многогранник представляет собой C-ядро в строго выпуклой игре четырех лиц?
Литература
1. Воробьев Н.Н. Теория игр для экономистов–кибернетиков. М.: Наука, 1985.
2. Мулен Э. Кооперативное принятие решений: Аксиомы и модели. М.: Мир.1991.
3. Оуэн Г. Теория игр. М.: Мир. 1971.
4. Льюс Р.Д., Райфа Х. Игры и решения. М.: ИЛ, 1961.
