Лекции.Орг


Поиск:




Категории:

Астрономия
Биология
География
Другие языки
Интернет
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Механика
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Транспорт
Физика
Философия
Финансы
Химия
Экология
Экономика
Электроника

 

 

 

 


Геометрическое решение игр.




Игры с двумя стратегиями можно решить геометрически. Для этого начинаем решать игру со стороны игрока, у которого две стратегии.

Пусть этот игрок А.

 


 

Решается по принципу минимакса для игрока А.

Решение необязательно находится на пересечении линий.

 

Рассмотрим задачу со стороны игрока В.

 

 

Если у одного игрока 2 стороны, а у другого много, то игру также можно решить геометрически.

 

В результате упрощения, игра имеет вид:

 

  B1 B2 B3 B4
A1 -1   -3  
A2   -1   -5

 

Решим игру относительно игрока А:

 
 

 


Для решения необходимо решить совместное уравнение В4, В1.

Тангенс угла наклона

 
 

 

 


A1:

A2:

Решение игр m ´ n.

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

По определению решения игры, отклонение игрока от своей оптимальной стратегии невыгод­но для него. Если бы все стратегии были активными, то можно было бы поставить “ = ” в выра­жение .

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

Разделим левую и правую часть неравенств на величину , и обозначим величины . То­гда получим систему ограничений в следующем виде:

Так как то:

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

Аналогично делим на и обозначим . Получим задачу:

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

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

Доказательство: из теории линейного программирования известно, что задача линейного про­граммирования не имеет решения в двух случаях:

1) Нет допустимого решения, т. е. система ограничений несовместна.

2) Целевая функция не ограничена.

Покажем, что любая пара задач линейного программирования имеет решение: возьмём и . Рассмотрим самый маленький выигрыш матрицы : . Тогда в качестве решения можно взять следующее: . Подставим это решение во все строки линейных нера­венств . Так как , то, например, всегда, а остальные равны нулю, то у нас есть реше­ние всегда. Так как вероятности и цена игры больше нуля, поэтому . Так как , то мини­мальная величина ограничена по крайней мере нулём, таким образом мы доказали, что решение и всегда существуют. А если существует , то существует , и значит существует во второй задаче. Мы доказали основную теорему теории игр: любая матричная игра имеет решение в области смешанных стратегий.





Поделиться с друзьями:


Дата добавления: 2016-12-05; Мы поможем в написании ваших работ!; просмотров: 604 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Чтобы получился студенческий борщ, его нужно варить также как и домашний, только без мяса и развести водой 1:10 © Неизвестно
==> читать все изречения...

2431 - | 2318 -


© 2015-2024 lektsii.org - Контакты - Последнее добавление

Ген: 0.007 с.