Задачи и упражнения

Задачи и упражнения

Решить матричную игру (то есть найти цену игры и оптимальные стратегии игроков):

1) 2) 3) 4) 5)

6) 7) 8) 9)

10) 11) 12)

13) Решить игру «чет-нечет»

Ответы:

1) 7/5; X=(0,8; 0,2); Y=(0,6; 0,4) 2) 3, (2,1) 3) 7/2; X=(0,25;075); Y=(0,5; 0,5); 4) 2, (1,2),(2,2) 5) 5, (1,1),(1,2) 6) 7/5; X=(0,8;0,2;0); Y=(0,6;0;0,4); 7) 3; (2,1); 8) 2; (1,2); (1,3); 9) 0,2; X=(0,4; 0,6; 0);

10) 1; X=(0,5; 0,5) 11) 1/7; X=(5/7; 2/7) 12) 6/7; X=(3/14; 11/14)

13) 0; (1/2, ½)

Примеры бесконечных антагонистических игр

Пример 1. (Одновременная игра преследования на плоскости.) Пусть и S2 — множества на плоскости. Игра Г заключается в следующем. Пусть 1 выбирает некоторую точку , а игрок 2 — точку . При совершении выбора игроки 1 и 2 не имеют информации о действиях противника, поэтому подобный выбор удобно интерпретировать как одновременный. Точки , являются в этом случае стратегиями игроков 1 и 2 соответственно. Таким образом, множества стратегий игроков совпадают с множествами и S2 на плоскости.

Целью игрока 2 является минимизация расстояния между ним и вторым игроком (игрок 1 преследует противоположную цель). Поэтому под выигрышем v(х, у) игрока 1 в этой игре будем понимать евклидово расстояние р(х, у) между точками и , т. е. v(х, у) = р(х, у), и . Выигрыш игрока 2 полагаем равным выигрышу игрока 1, взятому с обратным знаком (игра антагонистическая).

Задача 1. Пусть множества и S2 заданы следующими соотношениями:

Решить игру.

Задача 2. Пусть множества и S2 заданы следующими соотношениями:

Решить игру.

Пример 2. (Поиск на отрезке.) Простейшей игрой поиска с бесконечным числом стратегий является следующая игра.

Игрок 2 (прячущийся) выбирает точку , а игрок 1 (ищущий) выбирает одновременно и независимо точку . Точка у считается «обнаруженной», если , где . В этом случае игрок 1 выигрывает величину + 1, во всех остальных случаях его выигрыш полагается равным 0. Игра антагонистическая.

Таким образом, функция выигрыша имеет вид

Выигрыш игрока 2 полагается равным [-].

Задача 3. Решить описанную выше игру для .

Пример 3. Пусть - дважды дифференцируемая на области своего определения функция. Если соответствующая ей игра имеет седловую точку в чистых стратигиях, то последняя может быть найдена из системы дифференциальных уравнений:

Задача 4. Игра на единичном квадрате имеет функцию выигрыша

Найти ситуацию равновесия в этой игре.

Пример 4. (Шумная дуэль.) Каждому из двух дуэлянтов разрешается выстрелить только один раз. Предполагается, что оба они имеют «шумные» пистолеты, так что каждый знает, когда выстрелил его противник. Предполагается также, что функция меткости (вероятность попадания при стрельбе в момент времени t) игрока i определена на [0, 1], непрерывна, монотонно возрастает по t и . Если игрок 1 поражает игрока 2, то первый получает выигрыш +1; если игрок 2 поражает игрока 1, то игрок 1 получает (-1), если оба игрока стреляют одновременно и с одинаковым результатом (успешным или нет), то выигрыш игрока 1 равен 0.

Структура информации в этой игре (тот факт, что оружие шумное) принимается во внимание при составлении функции выигрыша . Если х<у, то вероятность того, что игрок 1 поразит противника, равна и выигрыш игрока 1 равен ; вероятность того, что игрок 1 промахнется, равна . Если игрок 2 еще не стрелял и знает, что игрок 1 больше не может выстрелить, то игрок 2 будет увеличивать свои шансы на успех, ожидая пока не станет равным 1. Таким образом, если игрок 1 промахнется в момент х, и , то он наверняка будет поражен игроком 2. Следовательно:

Продолжая аналогичным образом, окончательно имеем:

Решить игру.

Игры с непротивоположными интересами

Найти ситуации равновесия по Нэшу и Парето-оптимальные ситуации:

1) 2) 3) 4)

5) 6) 7) 8)

9) Существуют ли сильно равновесные ситуации в играх 1-4?

10) Рассматривая игры 1-8 как бескоалиционные, найти ситуации равновесия по Нэшу в смешанных стратегиях.

11) Рассматривая игры 5-8 как коалиционные, найти в них переговорные множества

Ответы:

10.1) X=(4/7; 2/7), Y=(2/3; 1/3) 10.4) X=(0,25; 0,75), Y=(0,5; 0,5)

10.5) X=(0,4; 0,6), Y=(0,6; 0,4) 10.6) X=(5/9; 4/9), Y=(5/9; 4/9)

10.7) X=(5/6; 1/6), Y=(1/2; 1/2) 10.8) X=(1/2; 1/2); Y=(1/2; 1/2)

Игры с бесконечным числом стратегий

Действительная функция f вогнута, если для всех , и любых выполнено

Теорема (Нэш [1951]). Предположим, что для любого множество стратегий есть выпуклое и компактное подмножество топологического векторного пространства (вообще говоря, своего для каждого i). Пусть для всех - непрерывная действительная функция на XN, определенная так что для всех функция вогнута по на . Тогда множество NE(G) равновесий по Нэшу игры непусто и компактно.

Следствие из теоремы Нэша (фон Нейман). Пусть — выпуклые компактные подмножества некоторых топологических векторных пространств, и пусть — непрерывная действительная функция, определенная на, причем

1) для всех вогнута по

2) для всех выпукла по.

Тогда игра двух лиц с нулевой суммой имеет по крайней мере одну седловую пару и, следовательно, цену.

Теорема Нэша позволяет утверждать, что множество NE(G) не пусто. Для того чтобы его вычислить, требуется решить следующую систему уравнений:

Если вогнута по , то приведенная выше задача глобальной оптимизации эквивалентна локальной задаче. Например, если — внутренняя точка множества и функция дифференцируема по , то условия эквивалентны условиям

Поскольку число независимых уравнений равно n, можно надеяться, что система будет иметь конечное число изолированных решений.

Пример. Олигополия с назначением выпуска

Пусть имеется п производителей с нулевыми затратами, которые регулируют предложение некоторого насыщаемого по потреблению товара. Производители поставляют свой товар на рынок. Общее предложение равно , а цена есть , где р — убывающая вогнутая функция на положительной полуоси:

Эту ситуацию можно представить как следующую игру:

Из наших условий на р получается, что функция вогнута по . Поскольку Xi не компактные множества, положим, , где S есть предложение, порождающее нулевую цену: p(s) = 0. Для усеченной игры применима теорема Нэша, которая позволяет утверждать существование NE-исхода х в усеченной игре. На самом деле исход х есть равновесие по Нэшу в исходной игре. Действительно, гарантированный выигрыш каждого игрока в усеченной игре есть 0, поэтому

В силу вогнутости и дифференцируемости ui па множестве X

NE-исход х удовлетворяет системе.

Задачи:

1.  Найдите NE-исход в вышеприведенной игре.

2.  Докажите, что общий выпуск товара при NE-исходе больше выпуска , максимизирующего общий доход производителей.

3.  Докажите, что любая стратегия для которой доминируется стратегией х*. Является ли данная игра разрешимой по доминированию?

4.  Дуополия с назначением выпуска

Предположим, что цена меняется по закону

Рассмотрим дуополию, которая формализуется как игра двух лиц, в которой множество стратегий каждого игрока есть отрезок [0, 1/2]. Докажите, что функция вогнута по . Вычислите функцию наилучших ответов обоих игроков и найдите NE-исход. Является ли он Парето-оптимальным?

Кооперативные игры

А) Оценить влиятельность игроков при помощи индекса Шепли-Шубика во взвешенных мажоритарных играх с квотой большинства 50% и весами игроков:

1) (1, 2,, 2,, 2,, 1, 1, 1)

Б) Оценить влиятельность игроков при помощи индекса Шепли-Шубика во взвешенных мажоритарных играх 1-4 с квотой большинства 2/3.

В) Выполнить задания пунктов А) и Б) для индексов Банцхафа.