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

Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования

Финансовый Университет

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

Кафедра «Математическое моделирование

экономических процессов (ММЭП)»

Теоретико-практическая работа по учебной дисциплине «Теория игр»

на тему:

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

Выполнил

Проверил

Москва 2010

2

Содержание

Введение

Теоретическая часть

Геометрическое решение игры 2х2

Геометрическое решение игры 2хn.

Геометрическое решение игры mх2.

Практическая часть

Заключение

Список использованной литературы

2

Введение

Графический метод решения игр позволяет решать в смешанных стратегиях антагонистические игры размером 2х2, 2хn и mх2. Этот метод обязательно предполагает наличие у хотя бы одного из игроков только двух стратегий, потому что иначе ситуацию невозможно будет представить на плоскости.

Остановимся на понятии смешанных стратегий. Случай, имеет место равновесная ситуация, т.е. такая ситуация, когда применение неких определенных стратегий двух игроков  максимально выгодно для обоих, на практике встречается редко.  Обычно каждая сторона старается увеличить свой выигрыш (или уменьшить проигрыш) по сравнению с нижней (или верхней) ценой игры. Для этого требуется скрыть свое поведение от противника, сделать его непредсказуемым, так как прямое применение единственной стратегии может быть путем логических рассуждений предугадано противником. В то же время полный отказ от рационального начала и переход к бессистемному поиску вариантов решений означал бы прекращение игры как таковой и замену ее неуправляемым случайным процессом. Приемлемый компромисс достигается здесь применением нескольких стратегий, чередующихся по случайному закону с определенным соотношением частот. Такие стратегии и называются смешанными [1, 27-28].

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

Для этого будут последовательно разобраны теоретические решения игр размером 2х2, 2хn и mх2, представлены графики, иллюстрирующие теорию, и пример к теории, а также приведено решение задачи, моделирующей реальную рыночную ситуацию.

Теоретическая часть

Геометрическое решение игры 2х2

Рассмотрим игру 2х2 с матрицей

Игрок А располагает двумя стратегиями: и и применяет стратегию с вероятностью , а стратегию с вероятностью , т.е его смешанная стратегия выражается через смешанную стратегию P=(). Очевидно, что +=1. Обозначим через p; тогда из нормировочного равенства получим =1−=1−р и смешанная стратегия принимает вид Р=(1−р,р), где р [0,1]. Значит, каждому р [0,1] соответствует единственная смешанная стратегия Р=(1−р,р) игрока А, которая при р=0 превращается в чистую стратегию =(1,0), а при р=1 – в чистую стратегию =(0,1), и наоборот, каждой смешанной стратегии Р=(1−р,р) игрока А соответствует единственная вероятность р [0,1], при этом чистой стратегии =(1,0) соответствует p=0, а чистой стратегии =(0,1) соответствует р=1. Таким образом, устанавливается взаимно однозначное соответствие [0,1]р ↔ Р=(1−р,р) между точками отрезка [0,1] и множеством всех смешанных стратегий игрока А. Это обстоятельство позволяет нам каждую смешанную стратегию Р=(1−р,р) игрока А представить той же точкой (отрезка [0,1] оси р), которой изображается вероятность р (см. рис. 1). При этом длина отрезка [0, p] равна р, а длина отрезка [p,1], равна 1−р [2, 175-176].

                                                             Рис. 1

Предположим, что игрок А выбирает смешанную стратегию Р=(1−р,р), а игрок В – чистую стратегию . Тогда в ситуации (Р, ) игрок А получает выигрыш

(1)

Графиком этой функции будет отрезок прямой, заключенный между двумя перпендикулярами к отрезку [0,1] в его концах. Для построения этого отрезка достаточно найти его концы, т.е. точки его пересечения с указанными перпендикулярами. При р=0 имеем Р= и, следовательно, Н(,)=, а при р=1 имеем Р= и, значит, Н(,)=. Справедливость этих равенств легко усматривается из равенства (1) соответственно при р=0 и р=1. Таким образом, концами исходного отрезка являются точки (0, ) и (1, ). Построив эти точки и соединив их, получим требуемый отрезок, обозначаемый нами через , который является графиком функции (1). На рисунке 1 мы предполагаем для определенности, что >>0.

Таким образом, если игрок В придерживается своей стратегии , то при любой стратегии Р=(1−р,р) игрока А выигрыш последнего геометрически выражается ординатой Н(Р,) точки, лежащей на отрезке и имеющей абсциссу р [2, 176-177].

Если игрок А выбирает стратегию Р=(1−р,р), а игрок В – чистую стратегию , то аналогичным образом можно построить отрезок (см. рис. 2), представляющий собой график функции

(2)

Рис. 2

Отрезок определяется стратегией . Ордината Н(Р,) представляет собой выигрыш игрока А в ситуации (Р, ) выбора игроком А стратегии Р=(1−р,р), а игроком В – стратегии .

Построим оба отрезка и в одной системе координат, предполагая дополнительно, что <, >, < (см. рис. 3).                                                                                                                 Рис. 3

Показатель эффективности смешанной стратегии Р=(1−р,р), р[0,1],

(3)

Представляет собой функцию от р [0,1], являющуюся нижней огибающей функций Н(Р,) и Н(Р, ). На рисунке 3 график нижней огибающей α(Р) есть ломаная N, выделенная жирной линией. Так как максимум α(Р) достигается на оптимальной стратегии , то для ее нахождения надо найти наивысшую (максимальную) точку нижней огибающей N. На рисунке 3 этой точкой является точка N. Затем нужно определить абсциссу этой точки, проведя из нее перпендикуляр до пересечения с отрезком  [0,1]; точка пересечения как раз и будет представлять оптимальную стратегию игрока А. Поскольку цена игры , то V будет равняться ординате точки N, т.е. длине отрезка N [2, 179].

Так как <, то показатель неэффективности стратегии равняется α()= = и изображается нижней точкой на левом перпендикуляре. Так как <, то показатель неэффективности стратегии равняется α()= = и изображается нижней точкой на правом перпендикуляре. Следовательно, поскольку >, нижняя цена игры в чистых стратегиях α= и изображается верхней из двух точек и .

Аналогично, в силу неравенства >, показатель неэффективности стратегии равен : β()==, и изображается верхним концом отрезка , а показатель неэффективности стратегии в силу неравенства > равен : β()== и изображается верхним концом отрезка . А так как <, то верхняя цена игры в чистых стратегиях β= и изображается нижней из двух точек и . На рисунке 3 видим, что α<V<β.

Итак, оптимальной стратегией игрока А является смешенная стратегия , где – абсцисса точки N, при которой чистые стратегии и выбираются им случайным образом с вероятностями соответственно 1− и ; при этом минимальный гарантированный выигрыш игрока А при любой стратегии игрока В (в-частности, при наихудшей для игрока А) равен V – ординате точки N [2, 179-180].

Геометрическое решение игры 2хn.

Пусть в некоторой игре Г первый игрок имеет чистые стратегии и , а второй игрок – n  чистых стратегий , , …, . Тогда фундаментальный симплекс смешанных стратегий первого игрока есть отрезок [0,1]. Предположим, игрок А выбирает стратегию Р=(). Показатель эффективности этой стратегии есть

(4)

Учитывая, что =р, а = 1−р, выразим α(Р) формулой

(5)

Таким образом, α(Р) представляет собой нижнюю огибающую n линейных функций

(6).

Стратегия , удовлетворяющая равенству  (7), является (по основной теореме фон Неймана) оптимальной, т.е. абсцисса максимальной (наивысшей) точки нижней огибающей α(Р) определяет оптимальную стратегию [4], придерживаясь которой игрок А выбирает свои чистые стратегии случайным образом, причем стратегию – с вероятностью 1−р0, а стратегию  – с вероятностью р0. По той же теореме цена игры

(7)

Т.е. цена игры V равна ординате максимальной точки нижней огибающей.

Рассмотрим пример.

Задача 1. Найти оптимальную стратегию игрока А.

А =  (   )

Решение.

) = р(-2) + (1 – р)7 = -2р + 7 – 7р = -9р +7.

= р(-1) + (1 – р)3 = -4р + 3.

= р + (1 – р)2 = -р +2.

= р6 + (1 – р) = 5р + 1.

График этих функций выглядит так, как показано на рисунке 4.

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

-р + 2 = 5р + 1;

1= 6р;  р = 1/6.

V = 5*(1/6) + 1 = 11/6.

Рис. 4

Ответ: активными стратегиями игрока В будут стратегии 3 и 4, цена игры V = 11/6.

Геометрическое решение игры mх2.

Игра размером mх2 может быть решена двумя способами. Первый способ – транспонировать исходную матрицу. Тогда задача сведется к решению игры nх2.

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

Рис. 5

Практическая часть

Рассмотрим пример применения графического метода для решения задачи экономического характера.

Задача 2. Предприятие может выпускать два вида продукции (A1 и А2), получая при этом прибыль, зависящую от спроса, который может оказаться в одном из четырех состояний (В1, В2, В3 и В4). Задана матрица, ее элементы характеризуют прибыль, которую получит предприятие при выпуске i-го вида продукции и j-ом состоянии спроса (таблица 1).

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

Таблица 1 - Платежная матрица Задачи 2.