Принятие решений в условиях неопределенности

Вид материала

Документы

Содержание ТЕОРИЯ ИГР 1.1.Предмет и задачи теории игр Теория игр 1.1.1. Основные понятия и определения Оптимальной стратегией 1.1.2.Антагонистические игры Рассмотрим пример Принцип максимина Игра с седловой точкой 1.1.3.Решение игр в смешанных стратегиях Необходимость случайного изменения стратегии в игре без седловой точки Смешанной стратегией S Решением игры 1.1.4.Приведение матричной игры к задаче линейного программирования Принятие решений в условиях неопределенности. Элементы теории статистических решений 1.2.Игры с природой в условиях неопределенности. Оптимистическая позиция Позиция нейтралитета Особые случаи 1.3.Классические критерии принятия решений 1.4.Критерий пессимизма-оптимизма Гурвица. ... Полное содержание

Подобный материал:

• 5 семестр. Контрольные вопросы для подготовки к экзамену: Игры с природой. Принятие, 40.09kb.
• Интеллектуальные технологии в управлении предприятием, 117.18kb.
• Конспект лекций Математические методы и модели в экономике, 46.08kb.
• 1. Анализ предпринимательских рисков инструментами финансового анализа и финансового, 129.75kb.
• Принятие решений в процессе управления строительным предприятием в условиях неопределенности, 386.26kb.
• Особенности преподавания элементов теории риска на экономических специальностях вузов, 48.21kb.
• Методические указания Объектом исследования теории игр (ТИ) является принятие решений, 145.42kb.
• Тема: Процессы принятия решений в организации, 22.07kb.
• Лекция 03. 04. 07 Принятие решений как функция менеджмента, 65.61kb.
• Многокритериальные методы обоснования управленческих решений в условиях нестохастической, 189.79kb.

Тема. ПРИНЯТИЕ РЕШЕНИЙ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ

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

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

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

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

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

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

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

ТЕОРИЯ ИГР

1.1.Предмет и задачи теории игр

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

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

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

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

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


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

Первые работы по теории игр (Цермело, Борель, фон Нейман) относятся к началу ХХ века. Но только появление и широкое распространение ЭВМ привлекло к теории игр внимание широкого круга специалистов.

Теория стратегических игр, в своей математической форме, возникла в 30-х годах XX века. Ее создателем считается Джон фон Нейман. Первой фундаментальной книгой по теории игр была изданная в 1944 году работа "Теория игр и экономическое поведение" (Нейман Д., Моргенштерн О. М.:Наука,1970).

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

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

В зависимости от того, какими данными располагает исследователь, и какую задачу перед собой ставит, могут быть сформулированы различные теоретико-игровые модели. Различают три основных типа задач:

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

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

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

Формализованные модели конфликтов известны с давних пор: это игры в буквальном смысле слова - шахматы, карты, кости и т.п. Эти игры носят характер соревнования, протекающего по известным правилам. Терминология, заимствованная из практики таких игр, применима и для других конфликтных ситуаций, которые рассматривает теория игр.

1.1.1. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

Задолго до появления теории игр широко использовали подобные упрощённые модели конфликтов – игры в буквальном смысле слова: шашки, шахматы, домино и т.д. Отсюда и название самой теории игр, и различные термины.

ИГРОЙ называется всякая конфликтная ситуация, изучаемая в теории игр и представляющая собой упрощенную, схематизированную модель ситуации. От реальной конфликтной ситуации игра отличается тем, что не включает второстепенные, несущественные для ситуации факторы и ведется по определенным правилам, которые в реальной ситуации могут нарушаться.

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

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

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

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

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

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

1.1.2.АНТАГОНИСТИЧЕСКИЕ ИГРЫ

Опр. Антагонистической игрой называется система G=, где A,B - непустые множества стратегий соответственно первого и второго игроков; H(a,b) – функция выигрыша игрока A (то есть функция потерь игрока B), aA, bB.

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

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

Рассмотрим антагонистические игры более подробно. В этой игре, как было сказано выше, участвуют два игрока А и В, имеющих противоположные интересы: выигрыш одного равен проигрышу другого. Так как выигрыш игрока А равен выигрышу игрока В с обратным знаком, мы можем интересоваться только выигрышем игрока А. Естественно, А хочет максимизировать свой выигрыш, а В – минимизировать свой проигрыш. Пусть у игрока А имеется n возможных стратегий А₁, А₂, . . . ,А_n, а у противника – m – возможных стратегий В₁, В₂, . . ., В_m (такая игра называется игрой nm). Обозначим а_ij выигрыш игрока А в случае, если мы пользуемся стратегией Аi, а противник – стратегией Вj. Предположим, что для каждой пары стратегий (Аi, Вj) выигрыш (или средний выигрыш) аij нам известен. Тогда в принципе можно составить прямоугольную таблицу (матрицу), в которой перечислены стратегии игроков и соответствующие выигрыши (см. таблицу 1).

Таблица 1. Платёжная матрица

B A	В1	В2	. . .	Вm
А1	а11	а12		а1m
А2	а21			а2m
. . .
Аn	an1			аnm

Если такая таблица составлена, то говорят, что игра G приведена к матричной форме. Такая таблица называется платежной матрицей или просто матрицей игры. Отметим, что само по себе приведение игры к такой форме уже может составить трудную задачу, а иногда и практически не выполнимую, из-за необозримого множества стратегий. Заметим, что если игра приведена к матричной форме, то многоходовая игра фактически сведена к одноходовой – от игрока требуется сделать только один ход: выбрать стратегию. Будем кратко обозначать матрицу игры П=(а_ij). Если конечная игра записана в виде такой матрицы, то говорят, что она приведена к нормальной форме. Но попробуйте, например, записать и нормальной форме обыкновенные шахматы! Вы сразу столкнетесь с тем, что количество возможных стратегий необозримо велико — настолько велико, что их перечисление выходит за пределы возможностей не только человека, но и современной вычислительной машины. А жаль! Потому что, если бы построение матрицы шахматной игры было возможно, это имело бы очень любопытные последствия... Но не будем забегать вперед.

Рассмотрим пример. Игроки А и В одновременно и независимо друг от друга записывает каждый одно из трёх чисел: 1, 2 или 3. Если сумма записанных чисел оказывается четной, то игрок В платит игроку А эту сумму; если же сумма чисел оказывается нечетной, то эту сумму выплачивает игрок А игроку В.

У игрока А три стратегии:

А1 – записать 1; А2 – записать 2; А3 – записать 3.

Стратегии игрока В аналогичны. Рассматриваемая игра есть игра 33. Платёжная матрица имеет три строки и три столбца. Эта матрица представлена таблицей 2.

Таблица 2. Исходная платёжная матрица

B A	В1	В2	В3
А1	2	-3	4
А2	-3	4	-5
А3	4	-5	6

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

Таблица 3 Преобразованная платёжная матрица

B A	В1	В2	В3
А1	8	3	10
А2	3	10	1
А3	10	1	12

Принцип максимина

Естественный принцип оптимальности для антагонистической игры — принцип максимина (минимакса). Будем анализировать эту игру, используя платёжную матрицу, показанную на табл. 3. Предположим, что игрок А выбирает стратегию А₁. Тогда в зависимости от того, какую стратегию изберёт противник, наш выигрыш будет равен либо 8, либо 3, либо 10. Итак, выбирая стратегию А₁, мы в худшем случае получаем выигрыш 3. Если же выберем стратегию А₂ или А₃, то будем иметь в худшем случае выигрыш 1. Запишем минимальные возможные выигрыши для разных стратегий Аi в виде дополнительного столбца платёжной матрицы (табл. 4). Ясно, что следует выбирать ту стратегию, где минимальный возможный выигрыш оказывается наибольшим (по сравнению с остальными стратегиями). В данном случае это стратегия А₁. Выигрыш 3 является максимальным в тройке минимальных выигрышей (в тройке 3, 1, 1). Его называют максиминным выигрышем или, проще, максимином. У него ещё одно название – нижняя цена игры.

Табл. 4. Нижняя и верхняя цена игры

B A	В1	В2	В3	αi
А1	8	3	10	3
А2	3	10	1	1
А3	10	1	12	1
βi	10	10	12

Аналогичным образом рассуждает противник. Если он выберет стратегию В₁, то в худшем для себя случае позволит нам получить выигрыш 10. То же можно сказать и о стратегии В₂. При выборе стратегии В₃ худший (для противника) случай соответствует нашему выигрышу, равному 12. Числа 10, 10, 12 – максимальные значения наших выигрышей, отвечающие стратегиям противника В₁, В₂, В₃ соответственно. Выпишем эти значения в виде дополнительной строки платёжной матрицы (см. табл. 4). Ясно, что противник должен выбрать ту стратегию, где наш выигрыш оказывается наименьшим. Это есть либо стратегия В₁, либо В₂. Обе стратегии являются минимаксными, обе они дают противнику гарантию, что наш выигрыш не превысит минимакса, или, иначе, верхней цены игры, равной в данном случае 10.

Верхняя и нижняя цены игры.

Величина  называется нижней ценой игры.




Величина  называется верхней ценой игры.


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

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

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

Игра с седловой точкой

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

Рассмотрим некоторую игру 33, платёжная матрица которой дана табл. 5. Здесь как максиминный, так и минимаксный выигрыши равны 4. Иными словами, в данной игре нижняя и верхняя цена игры совпадают, обе равны 4. Выигрыш 4 является одновременно и максимальным из минимальных выигрышей для стратегий А₁, А₂, А₃ и минимальным из максимальных выигрышей для стратегий В₁, В₂, В₃. В геометрии точку на поверхности, являющуюся одновременно минимумом по одной оси координат и максимумом по другой, называют седловой точкой (см. рис. 1). По аналогии с геометрией элемент а₂₂=4 рассматриваемой здесь платёжной матрицы называют седловой точкой матрицы, а об игре говорят, что она имеет седловую точку.



Рис. 1. Пример поверхности с седловой точки

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

Если же игра не имеет седловой точки (см. табл. 4), то ни одна из стратегий Аi или Вi не является оптимальной.


Табл. 5. Платёжная матрица с седловой точкой

B A	В1	В2	В3	Минимумы строк, i
А1	2	3	7	2
А2	5	4	6	4
А3	6	2	1	1
Максимумы столбцов, j	6	4	7

Как быть, если игра не имеет седловой точки? Если каждый игрок вынужден выбирать одну-единственную чистую стратегию, то делать нечего: надо руководствоваться принципом минимакса. Другое дело, если можно свои стратегии "смешивать", чередовать случайным образом с какими-то вероятностями. Применение смешанных стратегий мыслится таким образом: игра повторяется много раз; перед каждой партией игры, когда игроку предоставляется личный ход, он "передоверяет" свой выбор случайности, "бросает жребий", и берёт ту стратегию, которая выпала.

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

1.1.3.Решение игр в смешанных стратегиях

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

Необходимость случайного изменения стратегии в игре
без седловой точки

Допустим, что мы и наш противник многократно играем в игру, матрица которой дана на рис. 4. Если мы выберем определённую стратегию, например максиминную стратегию A₁, и будем придерживаться её от игры к игре, то противник, поняв это, будет выбирать каждый раз стратегию B₂, в результате чего наш выигрыш не превысит нижней цены игры, т.е. будет равен 3. Если, однако, мы внезапно (для противника) сменим стратегию A₁ на стратегию A₂, то получим выигрыш 10. Разгадав нашу новую стратегию, противник тут же сменит стратегию B₂ на стратегию B₃, уменьшив наш выигрыш до 1. И так далее. Здесь проявляется общее правило для игр без седловой точки: игрок, играющий по определённой (детерминированной) стратегии, оказывается в более худшем положении по сравнению с игроком, который меняет стратегию случайным образом.

Впрочем, случайные изменения стратегии надо делать не как попало, а с умом. Пусть A₁, A₂, …, An — возможные стратегии игрока A. Для получения наибольшего эффекта он должен использовать все или некоторые из этих стратегий случайным образом, но не с одинаковыми, а с разными (специально вычисленными) вероятностями. Пусть стратегия A₁,используется с вероятностью p₁, стратегия A₂,с вероятностью p₂ и т. д.

Смешанной стратегией S_A игрока А называется применение чистых стратегий A₁, A₂, ..., A_n с вероятностями p₁, p₂, ..., p_i, ..., p_n причем сумма вероятностей равна 1: _ Смешанные стратегии игрока А записываются в виде матрицы

_,

или в виде строки S_A=(p₁, p₂, …, p_n). В отличие от смешанных стратегий S_A стратегии Aj называют чистыми. При надлежащем подборе вероятностей p_j смешанная стратегия может оказаться оптимальной. При этом выигрыш игрока A будет не меньше некоторого значения v, называемого ценой игры. Это значение больше нижней цены игры, но меньше верхней.

Аналогичны образом должен вести себя игрок B. Его оптимальная стратегия также есть некоторая смешанная стратегия



или в виде строки S_B=(q₁, q₂, …,q_m), где q_j — специально подобранные вероятности, с которыми игрок B использует стратегии B_j. Сумма вероятностей равна 1:_ При выборе игроком B оптимальной смешанной стратегии выигрыш игрока A будет не больше цены игры v.

Чистые стратегии можно считать частным случаем смешанных. На основании принципа минимакса определяется оптимальное решение (или решение) игры: это пара оптимальных стратегий S*_A , S*_B в общем случае смешанных, обладающих следующим свойством: если один из игроков придерживается своей оптимальной стратегии, то другому не может быть выгодно отступать от своей. Выигрыш, соответствующий оптимальному решению, называется ценой игры v. Цена игры удовлетворяет неравенству α≤v≤β, где α и β — нижняя и верхняя цены игры. Справедлива следующая основная теорема теории игр — теорема Неймана. Каждая конечная игра имеет по крайней мере одно оптимальное решение, возможно, среди смешанных стратегий. Пусть S*_A = (p*₁, p*₂, ..., p*_i, ..., p*_m) и S*_B = (q*₁, q*₂, ..., q*_i, ..., q*_n) — пара оптимальных стратегий. Если чистая стратегия входит в оптимальную смешанную стратегию с отличной от нуля вероятностью, то она называется активной.

Справедлива теорема об активных стратегиях: если один из игроков придерживается своей оптимальной смешанной стратегии, то выигрыш остается неизменным и равным цене игры v, если второй игрок не выходит за пределы своих активных стратегий.

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

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

1.1.4.Приведение матричной игры к задаче линейного программирования

Обозначим через S_A=(p₁, p₂, …, p_n) оптимальную смешанную стратегию игрока A. Требуется найти вероятности и определить цену игры при условии, что известна платёжная матрица игры. Допустим, что игрок B выбирает чистую стратегию B₁. Тогда средний выигрыш для игрока A будет равен a₁₁p₁+a₂₁p₂+…+a_n1p_n. Этот выигрыш должен быть не меньше цены игры v, следовательно, a₁₁p₁+a₂₁p₂+…+a_n1p_n≥v.

Если игрок B выберет стратегию B₂, то и в этом случае средний выигрыш игрока A должен быть не меньше цены игры v, следовательно, a₁₂p₁+a₂₂p₂+…+a_n2p_n≥v.

Какую бы стратегию ни выбирал игрок B, выигрыш игрока A всегда должен быть не меньше цены игры v. Поэтому мы можем записать следующую систему из m неравенств (напоминаем, что m — число чистых стратегий игрока B):

a₁₁p₁+a₂₁p₂+…+a_n1p_n≥v;

a₁₂p₁+a₂₂p₂+…+a_n2p_n≥v;

………………………… (1)

a_1mp₁+a_2mp₂+…+a_nmp_n≥v.

При этом p₁+p₂+…+p_n=1. (2)

Введя обозначения x₁=p₁/v, x₂=p₂/v, … x_n=p_n/v, перепишем (1) и (2) в виде

a₁₁x₁+a₂₁x₂+…+a_n1x_n≥1;

a₁₂x₁+a₂₂x₂+…+a_n2x_n≥1;

………………………… (3)

a_1mx₁+a_2mx₂+…+a_nmx_n≥1;

x₁+x₂+…+x_n=1/v. (4)

Нам желательно, чтобы цена игры была максимальной, следовательно, 1/v должна быть минимальной. Таким образом, поиск оптимальной смешанной стратегии свёлся к решению следующей задачи линейного программирования: надо найти неотрицательные величины x_i такие, чтобы они удовлетворяли неравенствам (3) и обращали в минимум сумму x₁+x₂+…+x_n, т.е.

L= x₁+x₂+…+x_n→min,

при ограничениях

a₁₁x₁+a₂₁x₂+…+a_n1x_n≥1;

a₁₂x₁+a₂₂x₂+…+a_n2x_n≥1;

…………………………

a_1mx₁+a_2mx₂+…+a_nmx_n≥1;

x_i≥0, i=1, 2, …, n/

Задача. Самолёты против зениток. Найдём оптимальную смешанную стратегию некоторой конкретной игры. Предположим, что сторона A нападает на сторону B. У стороны A имеются два самолёта, несущие мощное поражающее средство. У стороны B имеются четыре зенитки, при помощи которых осуществляется оборона важного объекта. Чтобы объект оказался разрушенным, достаточно, чтобы к нему прорвался хотя бы один самолёт. Для подхода к объекту самолёты могут выбрать любой из четырёх воздушных коридоров (см. рис. 2).



Рис. 2. Воздушные коридоры и объект

У стороны A есть две чистые стратегии: стратегия A₁ — самолёты посылаются в разных воздушных коридорах (безразлично, каких именно), стратегия A₂ — оба самолёта посылаются в каком-то одном из коридоров. Возможные стратегии стороны B таковы: B₁ — поставить по зенитке на каждый коридор, B₂ — поставить по две зенитки на какие-то два коридора (остальные два коридора остаются неохраняемыми, B₃ — поставить две зенитки на один из коридоров и по одной зенитке ещё на два коридора, B₄ — поставить три зенитки на один из коридоров и одну зенитку ещё на один коридор, B₅ — поставить все четыре зенитки на один из коридоров. Стратегии B₄ и B₅ заведомо невыгодны хотя бы потому, что три, а тем более четыре зенитки в пределах одного коридора не нужны, ведь у стороны A всего два самолета. Поэтому ограничимся стратегиями B₁, B₂, B₃.

Предположим, что сторона A выбрала стратегию A₁, сторона B — стратегию B₁. Ясно, что тогда ни один самолёт не прорвётся к объекту — выигрыш стороны есть нуль (a₁₁=0). Пусть выбраны стратегии A₁ и B₂. В этой ситуации, какие бы два коридора ни выбирала сторона B для размещения пар зениток, у самолётов всегда будут шесть равновероятных вариантов и только один проигрышный. Таким образом, при выборе стратегий A₁ и B₂ вероятный выигрыш стороны A составляет 5/6 (a₁₂=5/6). Рассуждая подобным образом, найдём остальные элементы платёжной матрицы данной игры (см. табл. 6). Нижняя цена игры равна ½, верхняя ¾. Седловой точки нет, оптимальное решение лежит в области смешанных стратегий.

Табл. 6. Платёжная матрица игры

B A	В1	В2	В3	min
А1	0	5/6	1/2	0
А2	1	1/2	3/4	1/2
max	1	5/6	3/4

Чтобы найти оптимальную смешанную стратегию, воспользуемся платёжной матрицей (см. табл. 6) и соотношениями (3) и (4). В результате получим следующую задачу линейного программирования:

x₁+x₂→min



_, x₁≥0, x₂≥1

Решение удобно представить графически. Для этого построим область допустимых решений D (см. рис. 3). Уравнение x₁+x₂=const описывает семейство параллельных прямых, которые на рисунке показаны штриховыми линиями. Из всех прямых, имеющих хотя бы одну точку в пределах допустимой области, наименьшей сумме x₁+x₂ соответствует прямая FF. Точка G соответствует оптимальной смешанной стратегии. Координаты этой точки: x₁=3/5; x₂=1. Отсюда v=5/8, p₁=3/8, p₂=5/8. Итак, оптимальная смешанная стратегия стороны A предполагает использование стратегии A₁ с вероятностью 3/8 и стратегии A₂ с вероятностью 5/8.

Как воспользоваться этой рекомендацией на практике? Если игра происходит один раз, то стороне A следует, по-видимому, избрать стратегию A₂, ведь p₂>p₁. Предположим, что игра совершается многократно (например, по отношению к многим объектам, подлежащим бомбардировке). Если игра повторяется раз N (N»1), то в 3N/8 случаях сторона A должна избрать стратегию A₁, а в 5N/8 случаях стратегию A₂.

Рассмотрим поведение стороны B. При выборе стороной A оптимальной смешанной стратегии её средний выигрыш оказывается в пределах между верхней ценой игры, раной ¾, и ценой игры v=5/8. При неразумном поведении стороны B выигрыш стороны A может оказаться равным верхней цене игры (и даже может стать больше). Если сторона B, в свою очередь, будет придерживаться



Рис. 3. Допустимая область D (область красного цвета) и решение G.

оптимальной смешанной стратегии, то выигрыш игрока A окажется равным цене игры v. Оптимальная смешанная стратегия стороны B сводится к тому, что эта сторона вообще не применяет стратегию B₃, стратегию B₁ использует с вероятностью ¼, а стратегию B₂ с вероятностью ¾. Нецелесообразность применения стратегии B₃ усматривается из рисунка: соответствующая этой стратегии прямая EE не имеет общих точек с красной областью. Для определения вероятностей, с какими должны использоваться стратегии B₁ и B₂, воспользуемся уже найденным значением цены игры (v=5/8): q₁0+q₂5/6=5/8. Отсюда видно, что q₁=1/4, q₂=3/4. [Тарасов Л. В. Мир, построенный на вероятности. – М.: Просвещение, 1984. – 191 с.].

При решении произвольной конечной игры размера n × m рекомендуется придерживаться следующей схемы:

1. Исключить из платежной матрицы заведомо невыгодные стратегии по сравнению с другими стратегиями. Такими стратегиями для игрока А (игрока В) являются те, которым соответствуют строки (столбцы) с элементами, заведомо меньшими (большими) по сравнению с элементами других строк (столбцов).
   
2. Определить верхнюю и нижнюю цены игры и проверить, имеет ли игра седловую точку. Если седловая точка есть, то соответствующие ей стратегии игроков будут оптимальными, а цена совпадает с верхней (нижней) ценой.
   
3. Если седловая точка отсутствует, то решение следует искать в смешанных стратегиях. Для игр размера m × n рекомендуется симплексный метод, для игр размера 2×2, 2×m, m×2 возможно геометрическое решение.
   

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

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

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