Вклад нобелевского лауреата Нэша в развитие теории игр

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

Пусть Г — антагонистическая игра. Говорят, что стратегия является максиминной для игрока 1, если

;

стратегия является максиминной для игрока 2, если

.

Т.е. максиминная стратегия для игрока i является стратегией, обеспечивающей ему максимальный гарантированный выигрыш. Следовательно, максиминная стратегия игрока 1 решает задачу:

.

Аналогично, максиминная стратегия 2-го игрока решает задачу:

.

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

Равновесие по Нэшу на практике находится с помощью средств линейного программирования (например, симплекс-метод), как будет показано в практическом примере. В случае платежной матрицы порядка 2хN или Nх2 имеет смысл решать задачу геометрическим способом.

В случае больших размеров платежных матриц применяют итерационные методы, позволяющие найти приближенное вероятностное распределение стратегий.

Пример решения матричной игры Допустим, игра 2х лиц описывается платежной матрицей A:

Требуется найти вероятностное распределение наилучших стратегий игроков.

При решении данной задачи был использован материал учебных пособий [1], [3], [4].

Cначала дополним матрицу столбцом Mini, в который запишем минимальные значения в строке и строкой Maxj, в которую запишем максимальные значения в столбце:

Таблица 4

B1 B2 B3 B4 Mini, A1 -1 3 2 0 -1 A2 3 2 1 2 1 A3 -1 2 1 -3 -3 Maxj 3 3 2 2 Минимальная цена игры — максимум из значений дополнительного столбца — равна 1.

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

Седловой точки нет, решения в чистых стратегиях не существует, следовательно, игра имеет решение в смешенных стратегиях.

Стратегия первого игрока — вектор ;

Стратегия второго игрока — вектор .

Чтобы все элементы матрицы были неотрицательны, прибавим к каждому элементу исходной матрицы число C=3.

; .

Так как все элементы третьей строки не больше соответствующих элементов второй строки, то третья строка является доминируемой и ее можно удалить. Кроме того, можно удалить второй столбец, доминирующий над третьим и четвертым.

Т.е. и .

После удаления останется:

;; .

Составим пару симметричных двойственных задач, так чтобы исходная задача была стандартной задачей максимизации, матрица коэффициентов этой задачи совпадала с платежной матрицей, а коэффициенты при неизвестных в целевой функции и свободные члены неравенств были бы равны 1.

Задача 1 Задача 2

Решим задачу 1 симплекс-методом. Она задана в форме общей задачи. Сведем ее к основной при помощи дополнительных неизвестных и. В результате получим следующую задачу.

Составим первую симплекс-таблицу, выбрав в качестве базисных переменных и .

Решение задачи симплекс-методом представлено в табл. 5−8.

Таблица 5

K 1 1 1 1 0 К Баз x0 x1 x2 x3 x4 x5 0×4 1 2 5 3 1 0 0×5 1 6 4 5 0 1 ИС — 0 -1 -1 -1 -1 0 Таблица 6

K 1 1 1 1 0 К Баз x0 x1 x2 x3 x4 x5 1×4 2/3 0 11/3 4/3 1 -1/3 0×1 1/6 1 2/3 5/6 0 1/6 ИС — 1/6 0 -1/3 -1/6 0 1/6 Таблица 7

K 1 1 1 1 0 К Баз x0 x1 x2 x3 x4 x5 1×2 2/11 0 1 4/11 3/11 -1/11 1×1 1/22 1 0 13/22 -2/11 5/22 ИС — 5/22 0 0 -1/22 1/11 3/22 Таблица 8

K 1 1 1 1 0 К Баз x0 x1 x2 x3 x4 x5 1×2 2/13 -8/13 1 0 5/13 -3/13 1×3 1/13 22/13 0 1 -4/13 5/13 ИС — 3/13 1/13 0 0 1/13 2/13 Все значения индексной строки положительны, поэтому согласно критерию оптимальности, найденное решение является оптимальным, т. е. равновесным по Нэшу.

Получили оптимальный план прямой задачи: ,

оптимальный план двойственной задачи: .

Значение целевой функции: .

.

Вероятности выбора стратегий игроками или решение исходной задачи:

;

.

Цена исходной игры: .

Критерий оптимальности стратегий. Для того, чтобы стратегии и были оптимальными стратегиями соответствующих игроков, а число v было ценой игры, необходимо и достаточно, чтобы выполнялись неравенства

где (i= 1, 2, … m) — всевозможные чистые стратегии первого игрока, (j = 1, 2, …, n) — всевозможные чистые стратегии второго игрока.

Проверим правильность решения игры с помощью критерия оптимальности стратегий. Для этого в неравенства критерия оптимальности подставим компоненты найденных оптимальных стратегий и, компоненты чистых стратегий (i= 1, 2, 3) и (j = 1, 2, 3, 4) и сравним их с ценой игры .

.

.

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

Ответ:

Игрок 1 выберет стратегию 1 с вероятностью 1/3;

стратегию 2 с вероятностью 2/3;

стратегию 3 с вероятностью 0;

Игрок 2 выберет стратегию 1 с вероятностью 0;

стратегию 2 с вероятностью 0;

стратегию 3 с вероятностью 2/3;

стратегию 4 с вероятностью 1/3.

Цена игры равна 4/3.

Заключение

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

Теория антагонистических игр находит применение в военных приложениях (вопросах стратегии и тактики), во многих социально-экономических исследованиях. Игровая методология является основой перспективного направления математической статистики, трактующего статистические задачи как игры исследователя с природой.

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

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

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

Список литературы

1. Мастяева И. Н., Горбовцов Г. Я., Семенихина О. Н. Исследование операций в экономике: Учебное пособие / Московский международный институт экономиетрики, информатики, финансов и права. М., 2003.-113 с.

Нейман Дж., Моргенштерн О. Теория игр и экономическое поведение: Пер. с англ. — М.: Наука, 1970.

3. Печерский С. Л., Беляева А. А. Теория игр для экономистов. Вводный курс. Учебное пособие. — СПб.: Изд-во Европ. Ун-та в С.-Петербурге, 2001. — 342 с.

4. Розен В. В. Математические модели принятия решений в экономике. Учебное пособие. — М.: Книжный дом «Университет», Высшая школа, 2002. — 2008 с.

5. Автобиография

http://nobelprize.org/nobel_prizes/economics/laureates/1994/nash-autobio.html

6. «Мир словарей»

http://mirslovarei.com/content_soc/TEORIJA-IGR-5487.html

7. Научно-математический блог

http://www.binarys.ru/

8. Нобелевские лауреаты

http://www.nobel-winners.com/Economics/john_nash.html

9. Онлайн энциклопедия кругосвет, статья «игр теория»

http://krugosvet.ru/enc/nauka_i_tehnika/matematika/IGR_TEORIYA.html

10. Game theory

http://homepage.newschool.edu/het//schools/game.htm