Модели задач теории игр в системах компьютерной математики

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «МОРДОВСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ ИНСТИТУТ ИМЕНИ М.Е. ЕВСЕВЬЕВА»

Факультет физико –математический

Кафедра информатики и вычислительной техники

Реферат на тему:

Модели задач теории игр в системах компьютерной математики

Выполнила: Байкова Т. С.

Проверила: Кормилицына Т. В.

Саранск 2017

Содержание:

1. Введение…………………………………………………………………...............3

2. Основная часть:

2.1. Математические модели теории игр……………………………………...4-8

2.2. Формализация игры. Матрица игры……………………………………..9-14

2.3. Нижняя и верхняя цена игры…………………………………...............15-19

2.4. Платежная матрица………………………………………………….......20-27

3. Заключение……………………………………………………………….............28

4. Список используемой литературы……………………………………………...29

Введение

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

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

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

В экономике конфликтные ситуации встречаются очень часто и имеют многообразный характер. Например, взаимоотношения между поставщиком и потребителем, покупателем и продавцом, банком и клиентом. Каждый из них имеет свои интересы и стремится принимать оптимальные решения, помогающие достигнуть поставленных целей в наибольшей степени. При этом каждому приходится считаться не только со своими целями, но и с целями партнера и учитывать решения, которые эти партнеры будут принимать (они заранее могут быть неизвестны). Чтобы в конфликтных ситуациях принимать оптимальные решения, создана математическая теория конфликтных ситуаций, которая называется теорией игр. Возникновение этой теории относится к 1944 г., когда была издана монография Дж. фон Неймана «Теория игр и экономическое поведение»

Математические модели теории игр

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

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

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

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

Личный ход – это сознательный выбор игроком одного из вариантов действий (например, в шахматах).

Случайный ход – это случайно выбранное действие (например, бросание игральной кости). Мы будем рассматривать только личные ходы.

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

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

Цель теории игр – разработать методы для определения оптимальной стратегии каждого игрока.

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

Раздел Теория игр представлен тремя онлайн-калькуляторами:

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

2. Биматричная игра. Обычно в такой игре задают две матрицы одинакового размера выигрышей первого и второго игроков. Строки этих матриц соответствуют стратегиям первого игрока, а столбцы матриц – стратегиям второго игрока. При этом в первой матрице представлены выигрыши первого игрока, а во второй матрице – выигрыши второго.

3. Игры с природой. Используется, когда необходимо выбрать управленческое решение по критериям Максимакса, Байеса, Лапласа, Вальда, Сэвиджа, Гурвица.

Пример 1. Каждый из игроков, A или B , может записать, независимо от другого, цифры 1, 2 и 3. Если разность между цифрами, записанными игроками, положительна, то A выигрывает количество очков, равное разности между цифрами. Если разность меньше 0, выигрывает B. Если разность равна 0 – ничья.

У игрока A три стратегии (варианта действия): A1= 1 (записать 1), A2= 2, A3= 3, у игрока тоже три стратегии: B1, B2, B3.

B A B1= 1 B2= 2 B3= 3

A1 = 1 0 -1 -2

A2= 2 1 0 -1

A3= 3 2 1 0

Задача игрока A – максимизировать свой выигрыш. Задача игрока B – минимизировать свой проигрыш, т.е. минимизировать выигрыш A. Это парная Основные понятия теории игр

В экономической практике часто имеют место конфликтные ситуации. Игровые модели - это, в основном, упрощенные математические модели конфликтов. В отличие от реального конфликта игра ведётся по четким правилам. Для моделирования конфликтных ситуаций разработан специальный аппарат - математическая теория игр. Стороны, участвующие в конфликте, называются игроками.

Каждая формализованная игра (модель) характеризуется:

1. количеством субъектов - игроков, участвующих в конфликте;

2. вариантом действий для каждого из игроков, называемых стратегиями;

3. функциями выигрыша или проигрыша (платежа) исхода конфликта;

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

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

Смоделировать (решить) антагонистическую игру - значит, для каждого игрока указать стратегии, удовлетворяющие условию оптимальности, т.е. игрок A должен получить максимальный гарантированный выигрыш, какой бы своей стратегии не придерживался игрок B, а игрок B должен получить минимальный проигрыш, какой бы своей стратегии не придерживался игрок A. Оптимальные стратегии характеризуются устойчивостью, то есть ни одному из игроков не выгодно отклоняться от своей оптимальной стратегии.

Примечание. Различают игры кооперативные и некооперативные, с полной информацией и не полной. В игре с полной информацией перед каждым ходом каждый игрок знает все возможные ходы (стратегии поведения) и выигрыши. В кооперативных играх допускается возможность предварительных переговоров между игроками. Мы будем рассматривать некооперативные игры с полной информацией.

Математическая теория игр является разделом математики, изучающей принятие решений в конфликтных ситуациях.

Определим основные понятия теории игр.

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

Каждый игрок может иметь свои стратегии. Стратегией i-го игрока x2 называется одно из возможных решений из множества допустимых решений этого игрока.

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

Каждый из n участников игры может выбирать свою стратегию. Совокупность стратегий x=x1,x2,…,xn, которые выбрали участники игры, называется игровой ситуацией.

Оценить ситуацию x с точки зрения преследуемых ЛПР целей можно, построив целевые функции (или критерии качества), ставящие в соответствие каждой ситуации x числовые оценки f1(x),f2(x),…,fn(x) (например, доходы фирм в ситуации x или их затраты и т. д.).

Тогда цель i– го ЛПР формализуется следующим образом: выбрать такое свое решение xi, чтобы в ситуации x=x1,x2,…,xn число fi(x) было как можно большим (или меньшим). Однако достижение этой цели от него зависит лишь частично, поскольку другие участники игры влияют на общую ситуацию x с целью достижения своих собственных целей (оптимизируют свои целевые функции). Значение целевой функции в той или иной игровой ситуации можно назвать выигрышем игрока в этой ситуации.

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

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

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

Матричными играми называются конечные игры двух игроков с нулевой суммой. В этом случае номер строки матрицы соответствует номеру стратегии Ai игрока 1, а номер столбца – номеру стратегии Bj игрока 2.

Элементами матрицы aij является выигрыш игрока 1 для ситуации (реализации стратегий) AiBj. В силу того, что рассматривается матричная игра с нулевой суммой, выигрыш игрока 1 равен проигрышу игрока 2.

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

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

Биматричная игра – это конечная игра двух игроков с ненулевой суммой. В этом случае для каждой игровой ситуации AiBj каждый из игроков имеет свой выигрыш aij для первого игрока и bij– для второго игрока. К биматричной игре сводится, например, поведение производителей на рынках несовершенной конкуренции. Анализу этой проблемы посвящена тема 6 настоящего учебного пособия.

По степени неполноты информации, которой обладают ЛПР, игры делятся на стратегические и статистические.

Стратегические игры – это игры в условиях полной неопределенности.

Статистические игры – это игры с частичной неопределенностью. В статистической игре всегда имеется один активный игрок, имеющий свои стратегии и цели. Другим игроком (пассивным, не преследующим своих целей) является природа. Этот игрок реализует свои стратегии (состояния природы) случайным образом, причем вероятность реализации того или иного состояния можно оценить с помощью статистического эксперимента.

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

Формализация игры. Матрица игры

Пусть у игрока A есть m возможных ходов (стратегий) A1, A2,... Am, а у игрока B n возможных ходов (стратегий) B1, B2, ... Bn. Если игрок A сделает ход Ai, а игрок B сделает ход Bj, то эти ходы Ai и Bj однозначно определяют исходы игры aij для игрока А и bij для игрока В. Полные наборы исходов игры записываются в виде платёжных матриц размером mⅹn, стратегии игрока А соответствуют строкам матриц, а стратегии игрока В соответствуют столбцам матриц.

В общем случае у каждого игрока своя платёжная матрица и игра называется биматричной. Две матрицы могут быть преобразованы в одну - биматрицу, каждый элемент которой состоит из двух чисел, выигрыша игрока А и проигрыша игрока В. Поскольку мы ограничились рассмотрением антагонистическими играми, при которых выигрыш одного из игроков точно равен проигрышу другого, то на матрицы А и В налагается условие А + В = 0 (или А = - В, aij = - bij ). В этом случае можно ограничиться только одной матрицей - матрицей А. Такие игры называются матричными.

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

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

А =

ПРИМЕР 2. Игроки A и B играют в следующую игру. Игрок A записывает одно из чисел 6, 7, 9, а игрок B записывает одно из чисел 4, 5. Если сумма чисел четная, то это выигрыш игрока А. Если сумма чисел нечётная, то это выигрыш игрока В (проигрыш игрока А). Найти платёжную матрицу игры А.

Имеем три стратегии первого игрока. А1 = 6, А2 = 7, А3 = 9, В1 = 4, В2 = 5. Матрица игры:

А =

Оптимальные стратегии

С платёжной матрицей A = (aij) связано несколько основных понятий теории игр (игровых моделей).

Определение 1. Нижней ценой игры V* называется величина, являющаяся максиминным значением платёжной матрицы:

V* = max min aij

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

Определение 2. Верхней ценой игры V* называется величина, являющаяся минимаксным значением платёжной матрицы:

V* = min max aij

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

В силу того, что игра антагонистическая, всегда V* ≤ V*. Если V* = V* = V, то просто говорят о цене игры, такая игра называется вполне определённой, игрой с седловой точкой, поскольку значение элемента платёжной матрицы, равное V = V* = V* является минимальным в своей строке и максимальным в своём столбце. Соответствующие этой цене игры стратегии называются оптимальными, поскольку второй игрок не может понизить нижнюю цену игры, а первый игрок не может повысить верхнюю цены игры.

ПРИМЕР 3. Платёжная матрица игры:

А = .

Определим, существует ли седловая точка. Для этого находим минимум в каждой строке матрицы. Минимальным числом в первой строке будет 3, во второй - 4 и в третьей - 2. Из полученных минимумов находим максимум:

V* = max(3,4,2) = 4

Находим максимум в каждом столбце. Это числа 6, 7, 4 соответственно. Из полученных максимумов находим минимум:

V* = min(6,7,4) = 4

Следовательно, исходя из данного выше определения цены игры, в данном случае цена игры V = V* = V* = 4, седловая точка существует, и это есть элемент платёжной матрицы a23 = 4. Ей соответствуют единственная оптимальная стратегии - A2 первого игрока и единственная оптимальная стратегия - B3 второго игрока.

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

ПРИМЕР 4. Задана платёжная матрица игры, необходимо найти оптимальное решение игры.

А =

Определим, существует ли седловая точка. Для этого находим минимумы в каждой строке матрицы. Минимальным числом в первой строке будет 1, во второй это 2 и в третьей тоже 2. Из полученных минимумов находим максимум:

V* = max(1,2,2) = 2

Находим максимум в каждом столбце. Это числа 4, 2, 2 соответственно. Из полученных максимумов находим минимум:

V*=min(4,2,2) = 2

Следовательно, исходя из данного выше определения цены игры, в данном случае цена игры V = V* = V* = 2. Ей соответствуют стратегии A2 , А4 первого игрока, и стратегии В2, B3второго игрока (так как a22= а23 = а32 = а33 = 2). Из приведённого анализа следует, что в рассматриваемой платёжной матрице A существуют четыре седловых точек a22 , а23 , а32 , а33, поскольку каждый из этих элементов является минимальным элементом в своей строке и максимальным элементом в своём столбце.

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

• 2-я стратегия первого игрока и 2-я стратегия второго игрока, которым соответствует элемент а22;

• 2-я стратегия первого игрока и 3-я стратегия второго игрока, которым соответствует элемент а23;

• 3-я стратегия первого игрока и 2-я стратегия второго игрока, которым соответствует элемент а32;

• 3-я стратегия первого игрока и 3-я стратегия второго игрока, которым соответствует элемент а33.

Данный пример иллюстрирует тот факт, что конечная антагонистическая игра может иметь множество оптимальных решений (множество пар оптимальных стратегий).

ПРИМЕР 5. Задана платёжная матрица игры A, необходимо найти решение игры.

A =

В данной игре

V* = max (min aij)= 3aij

V* = min (max aij) = 4

Поскольку V* - выполняется соотношение строгого неравенства, следовательно, седловая точка в игре отсутствует, ситуации равновесия не существует. Очевидно, что для данной игры рассмотренный выше подход к нахождению оптимального решения неприменим, а максиминная и минимаксная стратегия игроков не являются решением игры.

Приведённые выше примеры иллюстрируют тот факт, что антагонистические игры делятся на два класса:

1. вполне определённые игры, т.е. те, в которых существует седловая точка, ситуация равновесия и решение игры в чистых стратегиях;

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

Нижняя и верхняя цена игры

Найдем наилучшую стратегию игрока A, для чего проанализируем последовательно все его стратегии. Выбирая стратегию Ai, мы должны рассчитывать, что игрок B ответит на нее такой стратегией Bj, для которой выигрыш Aбудет минимальным. Поэтому среди чисел первой строки выбираем минимальное, обозначим его , запишем его в добавочный столбец. Аналогично для каждой стратегии Ai выбираем , т.е. αi – минимальный выигрыш при применении стратегии Ai.

В примере 1:

α1 = min {0, –1, –2} = –2;

α 2 = min {1, 0, –1} = –1;

α 3 = min {0, –1, –2} = 0.

Эти числа запишем в добавочном столбце. Какую же стратегию должен выбрать игрок A? Конечно же, ту стратегию, для которой αi максимально. Обозначим . Это гарантированный выигрыш, который может обеспечить себе игрок A, т.е. ; этот выигрыш называется нижней ценой игры или максимином. Стратегия Ai, обеспечивающая получение нижней цены игры, называется максиминной (перестраховочной). Если игрок A будет придерживаться этой стратегии, то ему гарантирован выигрыш ≥α при любом поведении игрока B.

В примере 1 . Это означает, что если A будет писать «3», то он хотя бы не проиграет. Игрок Bзаинтересован уменьшить выигрыш A. Выбирая стратегию B1, он из соображений осторожности учитывает максимально возможный при этом выигрыш A. Обозначим . Аналогично при выборе стратегии Bjмаксимально возможный выигрыш A– ; запишем эти числа в добавочной строке. Чтобы уменьшить выигрыш A, надо из чисел β j выбрать наименьшее . Число называется верхней ценой игры или минимаксом. Это гарантированный проигрыш игрока B (т. е. он проиграет не больше, чем β). Стратегия игрока B, обеспечивающая выигрыш ≥ - β, называется его минимаксной стратегией.

В примере 1:

Это означает, что оптимальная стратегия B – писать «3», тогда он хотя бы не проиграет.

B A	B1	B2	B3
A1	0	– 1	–2	–2
A2	1	0	–1	–1
A3	2	1	0	0
	2	1	0	0 0

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

Можно доказать, что , т. е. .

В примере 1 α = β. Если , т.е. минимакс совпадает с максимином, то такая игра называется игрой с седловой точкой. Седловая точка – это пара оптимальных стратегий ( Ai, Bj). В примере 1 игра имеет седловую точку (А3,B3). В этом случае число α = β называется (чистой) ценой игры (нижняя и верхняя цена игры совпадают). Это означает, что матрица содержит такой элемент, который является минимальным в своей строке и одновременно максимальным в своем столбце. В примере 1 это элемент 0. Цена игры равна 0.

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

Пример 2. Первая сторона (игрок А) выбирает один из трех типов вооружения – А1, А2, А3, а противник (игрок В) – один из трех видов самолетов: В1, В2, В3. Цель В – прорыв фронта обороны, цель А – поражение самолета. Вероятность поражения самолета В1 вооружением А1 равна 0,5, самолета В2 вооружением А1 равна 0,6, самолетаВ3 вооружением А1 равна 0,8 и т.д., т.е. элемент aij платежной матрицы – вероятность поражения самолета В jвооружением Аi. Платежная матрица имеет вид:

В А		Вид самолета
		В1	В2	В3
Тип вооружения	А1	0,5	0,6	0,8
	А2	0,9	0,7	0,8
	А3	0,7	0,5	0,6

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

Решение. В каждой строке находим минимальный элемент и записываем его в добавочном столбце. В каждом столбце находим максимальный элемент и записываем его в добавочной строке.

В А	В1	В2	В3	α i
А1	0,5	0,6	0,8	0,5
А2	0,9	0,7	0,8	0,7
А3	0,7	0,5	0,6	0,5
β j	0,9	0,7	0,8	0,7 0,7

В добавочном столбце находим максимальный элемент = 0,7, в добавочной строке находим минимальный элемент = 0,7.

Ответ: = 0,7. Оптимальные стратегии – А2 и В2.

Пример 3. Игра в орлянку. Каждый игрок при своем ходе может выбирать одну из двух стратегий: орел или решка. При совпадении выбранных стратегий А получает выигрыш +1, при несовпадении B получает выигрыш 1 (т. е. А получает выигрыш –1). Платежная матрица:

В А	В1 (орел)	В2 (решка)
А1 (орел)	1	-1
А2 (решка)	-1	1

Найти нижнюю и верхнюю цену игры. Имеет ли игра седловую точку?

Решение.

В А	В1	В2
А1	1	-1	-1
А2	-1	1	1
	1	1	-1 1

α = -1, β = 1, т. е. А проиграет не больше 1, и B проиграет не больше 1. Так как α ≠ β, игра не имеет седловой точки. Положения равновесия в этой игре не существует, и оптимального решения в чистых стратегиях найти нельзя.

Пример. Найдите нижнюю цену игру, верхнюю цену игры, определите седловые точки, оптимальные чистые стратегии и цену игры (если они существуют).

Седловая точка

Седловая точка – это пара оптимальных стратегий (Ai, Bj). В этом случае число a=b называется (чистой) ценой игры (нижняя и верхняя цена игры совпадают). Это означает, что матрица содержит такой элемент, который является минимальным в своей строке и одновременно максимальным в своем столбце.

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

Игроки	B1	B2	B3	B4	a = min(Ai)
A1	8	7	0	6	0
A2	6	8	5	10	5
b = max(Bi )	8	8	5	10	0

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

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

Седловая точка (2, 3) указывает решение на пару альтернатив (A2,B3). Цена игры равна 5.

Платежная матрица

Парную игру с нулевой суммой удобно исследовать, если она описана в виде матрицы.

Предположим, что игрок A имеет m стратегий (обозначим их А1, А2, …, Am), а игрок B (противник) – n стратегий (B1, B2, …, Bm). Такая игра называется игрой размерности m х n. Пусть игрок A выбрал одну из своих возможных стратегий Ai. Игрок B, не зная результата выбора игрока A, выбрал стратегию Bj. Для каждой пары стратегий (Ai, Bj) определен платеж aij второго игрока первому, т.е. выигрыш игрока A. Выигрышем игрока B будет соответственно (– aij). Никакой дискриминации по отношению ко второму игроку здесь нет, т. к. величины aijмогут быть и отрицательны, тогда –aij 0. Например, a13 = –2 – выигрыш A, –a13 = 2 – выигрыш B. Такая игра называется матричной; матрица, составленная из чисел aij , называется платежной. В примере 1 платежная матрица имеет вид

.

Строки этой матрицы соответствуют стратегиям игрока A, а столбцы – стратегиям игрока B. Общий вид такой матрицы

B A	B1	B2	…	Bj	…	Bn
A1	a11	a12	…	a1j	…	a1n
A2	a21	a22	…	a2j	…	a2n
			…		…
Ai	ai1	ai2	…	aij	…	ain
…	…	…	…	…	…	…
Am	am1	am2	…	amj	…	amn

ПРИМЕР. Игроки A и B играют в следующую игру. Игрок A записывает одно из чисел 3, 7, 8, а игрок Bзаписывает одно из чисел 4, 5. Если сумма чисел четная, то это выигрыш игрока A. Если сумма чисел нечётная, то это выигрыш игрока B (проигрыш игрока A). Найти платёжную матрицу и оптимальное решение.

Решение. Если сумма чисел чётная, игрок A получает выигрыш +1, иначе игрок B получает выигрыш +1 (т.е. Aполучает выигрыш –1). Платежная матрица:

	3	7	8
4	-1	-1	1
5	1	1	-1

Далее решение ищем с помощью калькулятора.

Методы упрощения платёжных матриц. Доминирование и дублирование стратегий

Рассмотрим несколько методов упрощения платёжных матриц.

Первый метод, используемый для уменьшения размерности матрицы, основан на одном из важнейших понятий в теории игр - понятии доминирования стратегий.

Если i-я строка поэлементно не меньше (≥) j-й строки, то говорят, что i-я строка доминирует над j-й строкой. Поэтому игрок A не использует j-ю стратегию, так как его выигрыш при i-й стратегии не меньше, чем при j-й стратегии, вне зависимости от того, как играет игрок B.

Аналогично, если i-й столбец поэлементно не меньше (≥) j-го столбца, то говорят, что j-й столбец доминирует над i-м столбцом. Поэтому игрок B не использует i-ю стратегию, так как его проигрыш (равный выигрышу игрока A) при j-й стратегии не больше (≤), чем при i-й стратегии, вне зависимости от того, как играет игрок A. Стратегии, над которыми доминируют другие стратегии, надо отбросить и приписать им нулевые вероятности. На цене игры это никак не скажется. Зато размер матрицы игры понизится. С этого и нужно начинать решение игры.

Частный случай доминирования является дублирование стратегий.

Если платёжная матрица игры содержит несколько одинаковых строк (столбцов), то из них оставляем только одну строку, а остальные строки (столбцы) отбрасываем. Отброшенным стратегиям припишем нулевые вероятности.

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

Теоремы о доминирующих стратегиях:

Пусть I - игра, в матрице которой i -я стратегия первого игрока доминирует над i +1, а G - игра, матрица которой получена из матрицы I исключением i + 1 стратегии (строки). Тогда:

1. цена игры I равна цене игры G;

2. оптимальная смешенная стратегия Q*= (q1*,q2*,…,qn*) второго игрока в игре G является также его оптимальной смешанной стратегией в игре I;

3. если P*= (p1*,p2*,…,pi*, p*i+2,…, pm*) оптимальная смешенная стратегия первого игрока в игре G, то его смешенная стратегия P*= (p1*,p2*,…,pi*, p*i+2,…, pm*) является оптимальной в игре I.

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

Рассмотрим ряд примеров с использованием калькулятора.

Смешанные стратегии

В общем случае V* ≠ V* - седловой точки не существует. Оптимальное решение в чистых стратегиях также не существует. Однако, если расширить понятие чистой стратегии введением понятия смешанной стратегии, то удаётся реализовать алгоритм нахождения оптимального решения не вполне определённой игровой задачи, аналогичный рассмотренному выше. В такой ситуации предлагается использование статистического (вероятностного) подхода к нахождению оптимального решения антагонистической игры. Для каждого игрока, наряду с данным набором возможных для него стратегий, вводится неизвестный вектор вероятностей (относительных частот), с которыми следует применять ту или иную стратегию.

Обозначим вектор вероятностей (относительных частот) выбора заданных стратегий игрока A следующим образом:

P = (p1, p2,…, pm),

где pi≥ 0, p1 + p2 +…+ pm= 1. Величина pi называется вероятностью (относительной частотой) применения стратегии Ai.

Аналогично для игрока B вводится неизвестный вектор вероятностей (относительных частот) имеет вид:

Q = (q1, q2,…, qn),

где qj≥ 0, q1 + q2 +…+ qn = 1. Величина qj называется вероятностью (относительной частотой) применения стратегии Bj. Совокупность (комбинация) чистых стратегий A1, A2, …Am и B1, B2, …Bn в сочетании с векторами вероятностей выбора каждой из них называются смешанными стратегиями.

Основной теоремой в теории конечных антагонистических игр является Теорема фон Неймана: каждая конечная матричная игра имеет, по крайней мере, одно оптимальное решение, возможно, среди смешанных стратегий.

Из этой теоремы следует, что не вполне определённая игра имеет хотя бы одно оптимальное решение в смешанных стратегиях. В таких играх решением будет пара оптимальных смешанных стратегий P* и Q*, таких, что если один из игроков придерживается своей оптимальной стратегии, то и другому игроку не выгодно отклоняться от своей оптимальной стратегии.

Средний выигрыш игрока A определяется математическим ожиданием:

Если вероятность (относительная частота) применения стратегии отлична от нуля, то такая стратегия называется активной.

Стратегии P*, Q* называются оптимальными смешанными стратегиями, если

MA(P, Q*) ≤ MA(P*, Q*) ≤ MA(P*, Q)

В этом случае MA(P*, Q*) называется ценой игры и обозначается через V (V* ≤ V ≤ V*). Первое из неравенств (1)означает, что отклонение игрока A от своей оптимальной смешанной стратегии при условии, что игрок B придерживается своей оптимальной смешанной стратегии, приводит к уменьшению среднего выигрыша игрока A. Второе из неравенств означает, что отклонение игрока B от своей оптимальной смешанной стратегии при условии, что игрок A придерживается своей оптимальной смешанной стратегии,приводит к увеличению среднего проигрыша игрока B.

Решение игры в смешанных стратегиях геометрическим методом

Пусть игра задана платежной матрицей

По оси абсцисс отложим единичный отрезок А1 А2, где точкаА1 (0, 0) изображает стратегию А1, А2 (1, 0) – стратегию А2, а каждая промежуточная точка SA этого отрезка изображает смешанную стратегию первого игрока PA = (p1, p2), где p1– расстояние от точки SA до A2, p2–расстояние от точки SA до A1. Выигрыш игрока A будем откладывать на вертикальных отрезках.

Случай 1. Если игрок B применит стратегию В1, то выигрыш игрока A при стратегии А1 равен а11, поэтому на оси ординат отложим отрезок А1В1 = а11. При применении игроком A стратегии А2 выигрыш равен а21, отложим этот отрезок на перпендикуляре из точки А2, обозначим полученную точку В1'. Ордината любой точки М1 отрезкаВ1В1′ равна среднему выигрышу игрока A при применении смешанной стратегии SA (действительно, этот выигрыш равен математическому ожиданию случайной величины, т.е. a11p1 + a21p2). Запишем уравнение прямой В1В1′:

, т. е. ,

тогда при x = p2 получим

y = a11 + p2a21 – p2a11 = a11(1-p2) + p2a21 = a11p1 + a21p2

Случай 2. Если игрок B применяет стратегию В2, то аналогично откладываем отрезки а12 и а22 и получаем отрезок В2В2′. Ордината любой точки М2 отрезка В2В2′ – выигрыш игрока A, если A применяет смешанную стратегию SA, а B – стратегию В2.

Построим нижнюю границу выигрыша игрока А – ломаную В1 NВ2′. Ординаты точек этой ломаной показывают минимальные выигрыши игрока А при использовании им любой смешанной стратегии. Оптимальное решение игры определяет точка N, в которой выигрыш игрока А принимает наибольшее значение. Ордината точки Nравна цене игры. Проекция этой точки на ось ОХ показывает оптимальную стратегию (р1, р2).

Аналогично находится оптимальная стратегия Q = (q1 , q2) игрока B, только в соответствии с принципом минимакса надо находить верхнюю границу выигрыша, т. е. строить ломаную А2NА1′ и брать точку N с наименьшей ординатой.

Абсцисса точки N определяет оптимальную стратегию игрока B, т. е. Q = (q1 , q2).

Пример. Решить игру, заданную платежной матрицей , графоаналитическим способом.

Решение. Нижняя цена игры a = 1,5, верхняя цена игры b = 2. Так как , седловой точки нет. Так как a1 = 1,5, a21 = 2 строим точки B1(0;1,5) и B2(1;2), соединяем их отрезком. Так как a21 = 3, a22 = 1 строим точки B2(0;3) и B2’(1;1), соединяем их отрезком.

Уравнение прямой В1В1′:

, т. е. y = 0,5x + 1,5;

уравнение В2В2′:

, т. е. y = 3-2x.

Найдем точку N пересечения прямых В1В1′ и В2В2′, для чего решим систему уравнений:

т. е. N(0,6; 1,8), откуда p2= 0,6; p1= 0,4; γ = 1,8 – цена игры. Аналогично строим точки А1(0; 1,5) и А1′(1;3), А2(0; 2) и А2′(1; 1) и находим точку M пересечения прямых А1А1′ иА2А2′.

Ответ: смешанная стратегия игрока А: PA= (0,4; 0,6), игрока В: QB = (0,8; 0,2); цена игры 1,8.

Заключение

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

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

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

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

1. www.spbgid.ruindex.phpnews=125958 актуальна на 15.11.2008.

2. Оуэн Г. Теория игр.- М.: Мир, 1971.- 230с.

3. Воробьев Н.Н. Теория игр для экономистов-кибернетиков. – М.: Наука, Главная редакция физико-математической литературы, 1985. – 272 с.

4. Вентцель Е.С. Элементы теории игр. – М.: Наука, 1961. – 67 с.

5. pasadvice.narod.ru/stat/teorigr.htm актуальна на 29.10.2008.

6. Балдин К.В., Воробьев С.Н., Уткин В.Б. Управленческие решения. — М.: Издательство – торговая корпорация «Дашков и Кͦ», 2006. — 496 с.

7. www.12manage.com/methods_game_theory_ru.html актуальна на 14.11.2008.

8. www.ecsocman.edu.ru/db/msg/54933.html актуальна на 3.11.2008.

9. Мулен Э. Теория игр с примерами из математической экономики: Пер с франц.- М.: Мир, 1985.-200 с.

10.Воробьев Н.Н. Теория игр. – М.: Наука, 1976. – 64 с.

11.Васин А.А., Морозов В.В. Введение в теорию игр с приложениями к экономике. – М.: 2003. – 278 с.

12.Интрилигатор М. Математические методы оптимизации и экономическая теория. — М.: Айрис – пресс, 2002. — 576 с.

13.http://ru.wikipedia.org/wiki/ актуальна на 11.11.2008.

14.Волков И.К., Загоруйко Е.А. Исследование операций. — М.: Издательство МГТУ им. Н.Э. Баумана, 2000. — 436 с.

15.Харина О.Ю. Методическое пособие для студентов экономических специальностей г Петропавловск, 2005. — 85с.

16.Воробьев Н.Н. Основы теории игр. Бескоалиционные игры. – М.: Наука, 1984. – 495 с.

17.Лапшин К.А. Игровые модели и принятие решений. — М.: Москва, 2001. 45 с.

18.Таха, Хемди А. Введение в исследование операций. — М.: Издательский дом «Вильямс», 2005. – 912 с.

19.Шевчук Е.В., Касимов И.Р. Методическое пособие по выполнению курсовых проектов и работ: учебно-методическое пособие. Петропавловск: СКГУ им. М. Козыбаева, 2007. – 30 с.

20.Шинтемирова А.У., Морозова О.В. Инструкции по выполнению письменных работ студентами бакалавриата. — Петропавловск: СКГУ им. М. Козыбаева, 2006. – 60 с.