Теория игр

Размещено на http://www.allbest.ru/

Федеральное государственное бюджетное учреждение

Высшего профессионального образования

"Финансовый Университет при Правительстве Российской Федерации"

(Финуниверситет)

Тульский филиал Финуниверситета

КОНТРОЛЬНАЯ РАБОТА

По дисциплине: "Теория игр"

Выполнил студент 2 курса

Гурова Ю.Г.

Проверил: Манохин Е.В.

Тула 2013 г.

Задача 1. Вычислите нижние и верхние цены и найдите седловые точки (если они есть) для игр со следующими матрицами:

Матрица 1

1. Проверяем, имеет ли платежная матрица седловую точку. Если да, то выписываем решение игры в чистых стратегиях.

Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I.

Находим гарантированный выигрыш, определяемый нижней ценой игры a =max (a_i) = 15, которая указывает на максимальную чистую стратегиюA₁. Верхняя цена игры b = min (b_j) = 15.

Седловая точка (1, 1) указывает решение на пару альтернатив (A1,B1). Цена игры равна 15.

Матрица 2

1. Проверяем, имеет ли платежная матрица седловую точку. Если да, то выписываем решение игры в чистых стратегиях.

Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I.

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max (a_i) = 7, которая указывает на максимальную чистую стратегию A₄.

Верхняя цена игры b = min (b_j) = 11.

Что свидетельствует об отсутствии седловой точки, так как a ? b, тогда цена игры находится в пределах 7 <= y <= 11. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии).

2. Проверяем платежную матрицу на доминирующие строки и доминирующие столбцы.

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

Говорят, что i-я стратегия 1-го игрока доминирует его k-ю стратегию, если a_ij >= a_kj для всех j Э N и хотя бы для одного j a_ij > a_kj. В этом случае говорят также, что i-я стратегия (или строка) - доминирующая, k-я - доминируемая.

Говорят, что j-я стратегия 2-го игрока доминирует его l-ю стратегию, если для всех j Э M a_ij <= a_il и хотя бы для одного i a_ij < a_il. В этом случае j-ю стратегию (столбец) называют доминирующей, l-ю - доминируемой.

В платежной матрице отсутствуют доминирующие строки.

В платежной матрице отсутствуют доминирующие столбцы.

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

Аналогично, игрок II должен выбрать свои смешанные стратегии так, чтобы минимизировать математическое ожидание игрока I.

3. Находим решение игры в смешанных стратегиях.

Запишем систему уравнений.

Для игрока I 7p₁+2p₂+7p₃+13p₄ = y 11p₁+7p₂+11p₃+7p₄ = y 2p₁+19p₂+13p₃+7p₄ = y 13p₁+13p₂+2p₃+7p₄ = y p₁+p₂+p₃+p₄ = 1 Для игрока II 7q₁+11q₂+2q₃+13q₄ = y 2q₁+7q₂+19q₃+13q₄ = y 7q₁+11q₂+13q₃+2q₄ = y 13q₁+7q₂+7q₃+7q₄ = y q₁+q₂+q₃+q₄ = 1 Решая эти системы методом Гаусса, находим:

y = 8¹⁷⁵/₂₅₇ p₁ = ⁷²⁰/₂₈₂₇ (вероятность применения 1-ой стратегии).

p₂ = ⁴²/₂₅₇ (вероятность применения 2-ой стратегии).

p₃ = ⁴⁶⁸/₂₈₂₇ (вероятность применения 3-ой стратегии).

p₄ = ¹⁰⁷/₂₅₇ (вероятность применения 4-ой стратегии).

Оптимальная смешанная стратегия игрока I: P = (⁷²⁰/₂₈₂₇; ⁴²/₂₅₇; ⁴⁶⁸/₂₈₂₇; ¹⁰⁷/₂₅₇) q₁ = ⁷²/₂₅₇ (вероятность применения 1-ой стратегии).

q₂ = ⁹⁷/₂₅₇ (вероятность применения 2-ой стратегии).

q₃ = ⁴⁴/₂₅₇ (вероятность применения 3-ой стратегии).

q₄ = ⁴⁴/₂₅₇ (вероятность применения 4-ой стратегии).

Оптимальная смешанная стратегия игрока II: Q = (⁷²/₂₅₇; ⁹⁷/₂₅₇; ⁴⁴/₂₅₇; ⁴⁴/₂₅₇) Цена игры:

y = 8¹⁷⁵/₂₅₇

Матрица 3

1. Проверяем, имеет ли платежная матрица седловую точку. Если да, то выписываем решение игры в чистых стратегиях.

Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I.

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max (a_i) = 4, которая указывает на максимальную чистую стратегию A₁.

Верхняя цена игры b = min (b_j) = 4.

Седловая точка (1, 1) указывает решение на пару альтернатив (A1,B1). Цена игры равна 4.

Значения параметров, входящих в матрицы

Задача 2. Найдите оптимальные смешанные стратегии игры (2 Ч2):

Элементы матрицы заданы в таблице.

1. Проверяем, имеет ли платежная матрица седловую точку. Если да, то выписываем решение игры в чистых стратегиях.

Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I.

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max (a_i) = 2, которая указывает на максимальную чистую стратегию A₁.

Верхняя цена игры b = min (b_j) = 4.

Что свидетельствует об отсутствии седловой точки, так как a ? b, тогда цена игры находится в пределах 2 <= y <= 4. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии).

2. Проверяем платежную матрицу на доминирующие строки и доминирующие столбцы.

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

Говорят, что i-я стратегия 1-го игрока доминирует его k-ю стратегию, если a_ij >= a_kj для всех j Э N и хотя бы для одного j a_ij > a_kj. В этом случае говорят также, что i-я стратегия (или строка) - доминирующая, k-я - доминируемая.

Говорят, что j-я стратегия 2-го игрока доминирует его l-ю стратегию, если для всех j Э M a_ij <= a_il и хотя бы для одного i a_ij < a_il.

В этом случае j-ю стратегию (столбец) называют доминирующей, l-ю - доминируемой.

В платежной матрице отсутствуют доминирующие строки.

В платежной матрице отсутствуют доминирующие столбцы.

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

3. Находим решение игры в смешанных стратегиях.

Математические модели пары двойственных задач линейного программирования можно записать так. Найти минимум функции F (x) при ограничениях:

4x₁+x₂ >= 1 2x₁+5x₂ >= 1 F (x) = x₁+x₂ > min

Найти максимум функции Ф (y) при ограничениях:

4y₁+2y₂ <= 1 y₁+5y₂ <= 1 Ф (y) = y₁+y₂ > max

Цена игры будет равна g = 1/F (x), а вероятности применения стратегий игроков:

q_i = g*y_i; p_i = g*x_i.

Цена игры: g = 1: ¹/₃ = 3 p₁ = 3 ²/₉ = ²/₃ p₂ = 3 ¹/₉ = ¹/₃ Оптимальная смешанная стратегия игрока I:

P = (²/₃; ¹/₃) q₁ = 3 ¹/₆ = ¹/₂ q₂ = 3 ¹/₆ = ¹/₂ Оптимальная смешанная стратегия игрока II:

Q = (¹/₂; ¹/₂) Цена игры: v=3 4. Проверим правильность решения игры с помощью критерия оптимальности стратегии.

?a_ijq_j <= v ?a_ijp_i >= v M (P₁; Q) = (4¹/₂) + (2¹/₂) = 3 = v M (P₂; Q) = (1¹/₂) + (5¹/₂) = 3 = v M (P; Q₁) = (4²/₃) + (1¹/₃) = 3 = v M (P; Q₂) = (2²/₃) + (5¹/₃) = 3 = v

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

Задача 3. Найти решения матричных игр графоаналитическим методом:

а) игра (2 Ч5):

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max (ai) = 3, которая указывает на максимальную чистую стратегию A1.

Верхняя цена игры b = min (bj) = 5.

Что свидетельствует об отсутствии седловой точки, так как a ? b, тогда цена игры находится в пределах 3 <= y <= 5. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии)

Решим задачу геометрическим методом, который включает в себя следующие этапы:

1. В декартовой системе координат по оси абсцисс откладывается отрезок, длина которого равна 1. Левый конец отрезка (точка х = 0) соответствует стратегии A₁, правый - стратегии A₂ (x = 1). Промежуточные точки х соответствуют вероятностям некоторых смешанных стратегий S₁ = (p₁,p₂).

2. На левой оси ординат откладываются выигрыши стратегии A₁. На линии, параллельной оси ординат, из точки 1 откладываются выигрыши стратегии A₂.

Решение игры (2 x n) проводим с позиции игрока A, придерживающегося максиминной стратегии. Доминирующихся и дублирующих стратегий ни у одного из игроков нет. Максиминной оптимальной стратегии игрока A соответствует точка N, лежащая на пересечении прямых B₄B₄ и B₅B₅, для которых можно записать следующую систему уравнений:

y = 5 + (2 - 5) p₂ y = 3 + (5 - 3) p₂

Откуда p₁ = ³/₅ p₂ = ²/₅ Цена игры, y = 3⁴/₅ Теперь можно найти минимаксную стратегию игрока B, записав соответствующую систему уравнений, исключив стратегию B₁,B₂,B₃, которая дает явно больший проигрыш игроку B, и, следовательно, q₁ = 0,q₂ = 0,q₃ = 0.

5q₄+3q₅ = y 2q₄+5q₅ = y q₄+q₅ = 1 или 5q₄+3q₅ = 3⁴/₅ 2q₄+5q₅ = 3⁴/₅ q₄+q₅ = 1

Решая эту систему методом обратной матрицы, находим:

q₄ = ²/₅ q₅ = ³/₅

б) игра (4 Ч2):

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max (ai) = 4, которая указывает на максимальную чистую стратегию A4.

Верхняя цена игры b = min (bj) = 6.

Что свидетельствует об отсутствии седловой точки, так как a ? b, тогда цена игры находится в пределах 4 <= y <= 6. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии)

Решим задачу геометрическим методом, который включает в себя следующие этапы:

1. В декартовой системе координат по оси абсцисс откладывается отрезок, длина которого равна 1. Левый конец отрезка (точка х = 0) соответствует стратегии B₁, правый - стратегии B₂ (x = 1). Промежуточные точки х соответствуют вероятностям некоторых смешанных стратегий S₁ = (p₁,p₂).

2. На левой оси ординат откладываются выигрыши стратегии B₁. На линии, параллельной оси ординат, из точки 1 откладываются выигрыши стратегии B₂.

Решение игры (m x 2) проводим с позиции игрока B, придерживающегося максиминной стратегии. Доминирующихся и дублирующих стратегий ни у одного из игроков нет.

Максиминной оптимальной стратегии игрока B соответствует точка N, лежащая на пересечении прямых A₃A₃ и A₄A₄, для которых можно записать следующую систему уравнений:

y = 2 + (6 - 2) q₂ y = 8 + (4 - 8) q₂

Откуда q₁ = ¹/₄ q₂ = ³/₄ Цена игры, y = 5 Теперь можно найти минимаксную стратегию игрока A, записав соответствующую систему уравнений, исключив стратегию A₁,A₂, которая дает явно больший проигрыш игроку A, и, следовательно, p₁ = 0,p₂ = 0.

2p₃+8p₄ = y 6p₃+4p₄ = y p₃+p₄ = 1 или 2p₃+8p₄ = 5 6p₃+4p₄ = 5 p₃+p₄ = 1

Решая эту систему методом обратной матрицы, находим:

p₃ = ¹/₂ p₄ = ¹/₂

теория игра стратегия игрок

Размещено на Allbest.ru