Учебное пособие по курсу «Математика»
3.6.1. Основные понятия теории игр
В экономике довольно часто приходится сталкиваться с ситуацией, когда при наличии нескольких участников эффективность решения, принятого одним из них, существенно зависит от того, какие решения приняли другие участники. Например, при выборе ассортимента товаров, предполагаемого к выпуску на предприятии, необходимо учитывать, какой ассортимент товаров выпускают другие предприятия.
Если в такой ситуации интересы всех участников совпадают, то они могут договориться о совместных действиях. Однако гораздо чаще встречаются случаи, когда интересы участников не совпадают, а иногда – прямо противоположны. Ситуации такого типа называются конфликтными ситуациями. Построением математических моделей конфликтных ситуаций и разработкой методов решения возникающих в этих ситуациях задач занимается теория игр.
В каждой игре могут сталкиваться интересы двух и более противников. При этом в первом случае игра называется парной, а во втором – множественной. Поскольку участники множественной игры могут образовывать коалиции, то игра между такими коалициями превращается в парную игру. В рамках этой темы мы будем рассматривать только парные игры.
В теории игр выбор одного из предусмотренных правилами игры действий и его осуществление называется ходом. При этом созна тельный выбор игроками одного из возможных вариантов действий и его осуществление называется личным ходом. Теория игр занимается анализом только тех игр, которые содержат личные ходы. Ее основная задача – дать указания игрокам при выборе их личных ходов, т.е. рекомендовать им ту или иную оптимальную стратегию.
Стратегией игрока называется система правил, однозначно определяющая поведение игрока на каждом ходе в зависимости от ситуации, сложившейся в процессе игры. При этом оптимальной называется стратегия, которая при многократном повторении игры обеспечивает данному игроку максимально возможный средний выигрыш. Количество стратегий у каждого игрока может быть конечным или бесконечным, в зависимости от этого игры подразделяются на конечные и бесконечные.
Рассмотрим простейшую математическую модель конечной конфликтной ситуации, когда имеются два участника и выигрыш одного из них равен проигрышу другого. Такая модель называется парной игрой с нулевой суммой. При этом задачей первого игрока является максимизация своего выигрыша, а задачей второго – мини ми зация своего проигрыша, или минимизация выигрыша первого игрока.
Такую игру можно представить в виде матрицы, в которой строки – стратегии первого игрока, столбцы – стратегии второго игрока, а элементами матрицы являются выигрыши первого игрока, соответствующие данной паре стратегий. Такая матрица называется платежной. В общем случае, когда у первого игрока имеется m стратегий, а у второго – n стратегий, платежная матрица будет иметь вид:
Основной задачей каждого из игроков является нахождение наилучшей стратегии игры, при этом предполагается, что противники одинаково разумны, и каждый из них делает все, чтобы получить наибольшую выгоду для себя.
Для отыскания наилучшей стратегии первого игрока обозначим минимальный выигрыш (элемент) в каждой строке платежной матри цы через , т.е.
.
Зная , т.е. минимальные выигрыши при различных стратегиях , первый игрок выберет ту стратегию, которой соответствует максимальное значение . Обозначим это максимальное значение через , тогда:
.
Величина является гарантированным выигрышем, который может обеспечить себе первый игрок, и называется нижней ценой игры или максимином.
Для определения наилучшей стратегии второго игрока найдем максимальные значения выигрыша по столбцам платежной матрицы и, выбрав из них минимальное значение, получим:
,
где величина называется верхней ценой игры или минимаксом.
Если второй игрок будет придерживаться своей минимаксной стратегии, то он гарантированно обеспечит проигрыш, не превышаю щий .
Для любой матричной игры справедливо неравенство . Если , то такая игра называется игрой с седловой точкой, а пара оптимальных стратегий – седловой точкой платежной матрицы. В этом случае элемент называется ценой игры и является одновременно минимальным в –ой строке и максимальным в –ом столбце. Если игра имеет седловую точку, то говорят, что она решается в чистых стратегиях.
Если платежная матрица игры не имеет седловой точки, т.е. , то поиск решения игры приводит к применению сложной стратегии, состоящей в случайном применении двух и более стра тегий с определенными вероятностями. Такая стратегия называется смешанной стратегией.
Пусть платежная матрица игры имеет размерность , тогда смешанные стратегии первого игрока можно задать набором вероятностей, с которыми этот игрок применяет свои чистые стратегии, т.е. . Этот набор можно рассматривать как –мерный вектор, для координат которого справедливы соотно шения:
.
Аналогично для второго игрока набор вероятностей определяет –мерный вектор , для координат которого:
.
Выигрыш первого игрока при использовании смешанной стратегии определяется как математическое ожидание выигрыша:
.
Основная теорема теории игр. Каждая конечная игра имеет, по крайней мере, одно решение, возможно, в области смешанных стратегий.
Если решением игры является пара оптимальных смешанных стратегий, то, как правило, не все стратегии, доступные игрокам, входят в эти смешанные стратегии, т.к. для них соответствующие вероятности равны нулю.
Активными стратегиями игрока называются те, которые входят в его оптимальную смешанную стратегию с вероятностью, отличной от нуля.
Теорема об активных стратегиях. Если один из игроков придерживается своей оптимальной смешанной стратегии, то выигрыш остается неизменным и равным цене игры, независимо от действий другого игрока, если только он не выходит за пределы своих активных стратегий.
Если платежная матрица не содержит седловой точки, то задача отыскания оптимальной смешанной стратегии тем сложнее, чем больше размерность платежной матрицы. Поэтому матрицы большой размерности целесообразно упростить (уменьшить их размерность) путем вычеркивания дублирующих (одинаковых) и заведомо невыгодных стратегий.
ПРИМЕР: Упростить платежную матрицу игры
.
Для этой матрицы находим: , а также: и , т.е. седловой точки нет.
Анализ матрицы показывает, что все элементы не превы шают соответствующих элементов , т.е. вторая стратегия первого игрока заведомо невыгодна для него, поэтому можно исключить, т.е. вычеркнуть вторую строку матрицы. Все элементы меньше элементов , исключаем .
Для второго игрока: сравнивая и , исключаем ; сравнивая и , исключаем ; сравнивая и , исключаем . В результате проведенных упрощений получена квадратная матрица второго порядка:
.
3.6.2. Графическое решение игр вида (2 х n) и (m x 2)
Графический метод решения применим только к матричным играм, в которых хотя бы один игрок имеет только две стратегии.
Рассмотрим графическое решение игр вида 2 x n. Пусть такая игра задана платежной матрицей:
.
Предположим, что в этой матрице седловой точки нет. Введем обозначе ния: – вероятность применения игроком A первой стратегии; – вероятность применения игроком A второй стратегии; причем: ; – вероятность применения игроком B –ой стратегии, где .
В этих обозначениях ожидаемый выигрыш первого игрока при примене нии вторым первой стратегии составит:
.
Аналогично найдем ожидаемые выигрыши первого игрока при применении игроком B всех остальных его стратегий. В результате получим таблицу:
-
Чистые стратегии
игрока B
Ожидаемые выигрыши
игрока A
1
2
…
…………………..
n
Из таблицы следует, что ожидаемый выигрыш игрока A при любых чистых стратегиях игрока B линейно зависит от . Другими словами, зависи мость между ожидаемым выигрышем игрока A и вероятностью применения им первой стратегии (при данной чистой стратегии игрока B) может быть представлена в виде прямой линии. Количество таких прямых линий будет равно количеству стратегий игрока B. Первый игрок (игрок A) должен выбирать такие стратегии, чтобы макси мизировать свой минимальный ожидаемый выигрыш. Поэтому оптимальная стратегия первого игрока определяется как точка пересечения прямых линий, в которой его минимальный ожидаемый выигрыш максимален.
Аналогично, оптимальная стратегия второго игрока (игрока B) определя ется как точка пересечения прямых линий, в которой его максимальный ожи даемый проигрыш минимален.
ПРИМЕР 1. Найдите оптимальное решение игры, заданной платежной матрицей вида
.
Для поиска седловой точки в платежной матрице вычислим:
Следовательно, цена игры заключена в пределах: , и седловой точки матрица игры не имеет. Поскольку количество чистых стратегий у первого игрока равно двум, найдем оптимальное решение игры графическим методом. Для этого составим таблицу ожидаемых выигрышей первого игрока в зависимости от чистых стратегий второго игрока. По результатам таблицы проведем необходимые построения, показанные на рис. 3.6, и убедимся в том, что искомое значение является абсциссой точки пересечения прямых, соответствующих второй и третьей чистым стратегиям второго игрока, и, следовательно, может быть найдено из равенства: .
-
Чистые стратегии второго игрока
Ожидаемые выигрыши первого игрока
1
2
3
4
Решив уравнение, найдем: и . Тогда цена игры составит: .
Итак, оптимальное решение игры для первого игрока можно записать в следующем виде:
.
Прежде чем приступить к поиску оптимального решения игры для второго игрока отметим, что оптимальная стратегия первого игрока найдена из равенства выражений, соответствующих второй и третьей чистым стратегиям второго игрока, т.е. именно эти стратегии второго игрока являются активными, поэтому можно записать:
.
С учетом этого построим таблицу ожидаемых проигрышей второго игрока в зависимости от чистых стратегий первого игрока.
-
Чистые стратегии первого игрока
Ожидаемые проигрыши второго игрока
1
2
Не проводя ненужных в данном случае построений, запишем равенство (уравнение) в виде:
,
и из него немедленно найдем: и . При этом цена игры составит: .
Таким образом, оптимальное решение для второго игрока можно записать в следующем виде:
.
ПРИМЕР 2. Найдите оптимальное решение игры, заданной пла теж ной матрицей вида
.
Найдем нижнюю и верхнюю цены игры:
.
Таким образом, и, следовательно, седловая точка в матрице игры отсутствует, и, поскольку у второго игрока имеется только две чистых стратегии, найдем решение игры графическим методом. Составим таблицу ожидаемых проигрышей второго игрока в зависимости от чистых стратегий первого игрока, а затем проведем необходимые построения, показанные на рис. 3.7.
-
Чистые стратегии первого игрока
Ожидаемые проигрыши второго игрока
1
2
3
4
Из рассмотрения верхней части рис. 3.7 следует, что искомое значение может быть найдено из равенства: и составляет , но тогда, очевидно: и .
Итак, оптимальное решение для второго игрока можно записать в следующем виде:
.
Заметим, что прямые, пересекающиеся в минимаксной точке, соответствуют первой и третьей чистым (активным) стратегиям первого игрока. Это означает, что выполняются следующие равенства:
.
С учетом полученных равенств, отыщем оптимальную стратегию первого игрока. Для этого составим таблицу ожидаемых выигрышей первого игрока в зависимости от чистых стратегий второго игрока
| Чистые стратегии второго игрока | Ожидаемые выигрыши первого игрока |
| 1 | |
| 2 | |
Из таблицы следует, что: , или , но тогда можно найти: и .
Таким образом, оптимальное решение игры для первого игрока можно записать в следующем виде:
.
3.6.3. Решение матричных игр методами линейного программирования
Теория игр находится в тесной связи с линейным программи рованием, т.к. каждая конечная игра двух лиц с нулевой суммой может быть представлена как задача линейного программирования.
Действительно, для первого игрока математическую модель задачи можно за писать в виде:
Эту модель можно существенно упростить, разделив все ограничений на величину . Это возмож но, если . Если , то рекомендуется прибавить любое положительное число ко всем элементам платежной матрицы, что гарантирует положи тельность значений цены модифицированной игры. При этом действи тельное значение цены игры получается вычитанием этого числа C. Если же , то следует сменить знаки неравенств ограничений на противопо ложные.
Пусть для определенности . Если ввести обозначение: а также учесть, что при величина , получим задачу линейного программиро вания с ма тематической моделью вида:
Совершенно аналогично, с учетом обозначений: и , можно получить математическую модель линейной задачи для второго игрока:
Очевидно, что задача линейного программирования второго игрока является двойственной по отношению к задаче линейного программирования первого игрока. Поэтому можно симплекс-методом найти оптимальное решение для одного (любого) игрока, а затем и для второго, пользуясь теоремами двойственности.
ПРИМЕР: Найти методами линейного программирования оптимальное решение матричной игры примера 2 подраздела 3.6.2.
Поскольку платежная матрица игры имеет вид:
с учетом обозначений ; ; математическую модель задачи линейного программирования для первого игрока можно записать в следующем виде:
С учетом обозначений: и математическую модель задачи линейного программирования для второго игрока можно составить, пользуясь правилами составления моделей двойственных задач (подраздел 3.1.3), тогда получим:
Предположим, что симплекс-методом, или графическим методом найдено оптимальное решение задачи линейного программирования для второго игрока в виде: . Этому решению соответствует оптимальное решение матричной игры для второго игрока в виде: .
Для отыскания оптимального решения задачи линейного программирования первого игрока воспользуемся теоремами двойственности (подраздел 3.1.3). Согласно первой теореме двойственности, запишем: . Поскольку , по второй теореме двойственности заключаем, что неравенства ограничений задачи линейного программирования первого игрока могут быть записаны в виде системы уравнений:
Подставим найденные оптимальные решения и в систему ограничений задачи линейного программирования второго игрока и, используя вторую теорему двойственности, получим:
С учетом полученных результатов записанную систему уравнений можно переписать в виде:
Решения этой системы будут оптимальными (отличными от нуля) решениями задачи линейного программирования первого игрока: и . Следовательно, оптимальное решение этой задачи можно записать в виде: , а оптимальное решение матричной игры для первого игрока в следующем виде: .
3.6.4. Игры с «природой»
В рассмотренных в предыдущих подразделах матричных играх предполагалось, что в них принимают участие два игрока, интересы которых прямо противоположны. Так, если действия одного из игроков направлены на увеличение выигрыша, то другой игрок предпринимает все возможные действия, чтобы уменьшить свой проигрыш. Однако в некоторых задачах, сводящимся к игровым, имеется неопределен ность, вызванная отсутствием информации об условиях, в которых осуществляется действие (погода, покупательский спрос, объем перевозок транспор том и т.д.). Эти условия зависят не от сознательных действий другого игрока, а от объективной действитель ности. Такие игры называются играми с природой. При этом «природа» рассматривается как некоторая незаинтересованная инстанция, поведение которой неизвестно, но всегда не содержит элементов активного и сознательного противодействия. В играх с природой человек (первый игрок) старается действовать осмотритель но, второй же игрок – природа действует случайно.
Условия такой игры, как правило, задаются платежной матрицей, в которой стратегии природы (второго игрока) представляют собой все возможные состояния природы.
Имеется ряд критериев, которые используются при выборе оптимальной стратегии первым игроком. Перечислим некоторые из них.
1. Критерий Уальда. Критерий рекомендует применять макси минную стратегию. Она определяется условием: и совпадает с нижней ценой игры. Поэтому этот критерий часто называют критерием крайнего пессимизма, т.е. предполагается, что природа будет действовать наихудшим для человека (первого игрока) образом.
2. Критерий крайнего оптимизма. Этот критерий определя ется условием . При этом считается, что природа будет наиболее благоприятна для человека (первого игрока).
3. Критерий Гурвица. Этот критерий рекомендует выбирать стратегию, определяемую формулой:
,
где – степень оптимизма может изменяться в диапазоне [0, 1]. Критерий придерживается промежуточной позиции, учитывающей возможность как наихудшего, так и наилучшего поведения природы. При критерий Гурвица превращается в критерий Уальда, а при – в критерий крайнего оптимизма. Причем выбор того или иного значения связан со степенью ответственности лица, принимающего решение по выбору стратегии. Чем хуже последствия ошибочных решений, больше желание застраховаться, тем выбирается ближе к единице.
4. Критерий Сэвиджа. Суть критерия состоит в выборе такой стратегии, которая не допускала бы чрезмерно высоких потерь, к которым она может привести. При этом анализируется не платежная матрица, а матрица рисков, элементы которой определяются по формуле:
.
и показывают, какой убыток понесет человек (первый игрок), если для каждого состояния природы он не выберет наилучшей стратегии. Оптимальная стратегия определяется формулой:
.
Применение этих критериев к анализу матрицы игры с природой, несмотря на субъективность их выбора, часто дает лучшее представление о ситуации, достоинствах и недостатках каждого решения, чем непосредственное рассмотрение матрицы, особенно достаточно большого размера.
Рекомендуемая литература по теме 3.6: [3, 5, 7, 10].
ВОПРОСЫ:
Что называется стратегией игрока?
Что называется оптимальной стратегией игрока?
Какое утверждение служит основой для методов решения матричных игр?
Что представляют собой элементы платежной матрицы?
При каких условиях возможно применение графического метода решения матричных игр?
В чем состоит основная идея графического метода решения матричных игр?
Какой универсальный метод может быть использован при решении матричных игр любой размерности и почему?
В чем состоит основное различие между обычными матричными играми и играми с природой?
ЛИТЕРАТУРА
Программа курса «Математика». – М.: Издание ИМЭС, 2008.
Налимов В.Н. Теория вероятностей и математическая статистика для экономистов: Учебное пособие по курсу «Математика». – М.: «Весть», 2007.
Налимов В.Н. Экономико-математические методы и модели: Учебное пособие по курсу «Математика». – М.: «Весть», 2008.
Гмурман В.Е. Теория вероятностей и математическая статистика: Учебное пособие для вузов – М.: Высшая школа, 2000.
Красс М.С., Чупрынов Б.П. Основы математики и ее приложения в экономическом образовании: Учебник. – М.: Дело, 2000.
Солодовников А.С., Бабайцев В.А., Браилов А.В., Шандра И.Г. Математика в экономике: Учебник. Ч. 1. – М.: Финансы и статис ти ка, 2005.
Фомин Г.П. Математические методы и модели в коммерческой деятельности: Учебник. – М.: Финансы и статистика, 2005.
Общий курс высшей математики для экономистов: Учебник / Под редакцией В.И. Ермакова. – М.: ИНФРА-М, 1999.
Вентцель Е.С. Теория вероятностей: Учебник. – М.: Физматгиз, 1962.
10. Вентцель Е.С. Исследование операций. – М.: Наука, 2000.
11. Елисеева И.И., Юзбашев М.М. Общая теория статистики:
Учебник. – М.: Финансы и статистика, 2000.
12. Налимов В.Н. Основы высшей математики для экономистов:
Учебное пособие по курсу «Математика» - М.: «Весть», 2006.
ОГЛАВЛЕНИЕ
Предисловие …………………………………………………………………..3
Раздел 1. Теория вероятностей …………………………………………..6
страница 1 ... страница 9страница 10страница 11страница 12страница 13
скачать
Другие похожие работы: