Ирина Эланс
Теория игр. 7
Теория игр
Содержание
Введение
Понятие «Теории игр»
1. Кооперативная теория игр
2. Антагонистические и позиционные игры
3. Задача
Заключение
Список использованной литературы
Введение
Теория игр, раздел математики, изучающий формальные модели принятия оптимальных решений в условиях конфликта. При этом под конфликтом понимается явление, в котором участвуют различные стороны, наделённые различными интересами и возможностями выбирать доступные для них действия в соответствии с этими интересами. Отдельные математические вопросы, касающиеся конфликтов, рассматривались (начиная с 17 в.) многими учёными. Систематическая же математическая теория игр была детально разработана американскими учёными Дж. Нейманом и О. Моргенштерном (1944) как средство математического подхода к явлениям конкурентной экономики. В ходе своего развития Теория игр переросла эти рамки и превратилась в общую математическую теорию конфликтов. В рамках Теории игр в принципе поддаются математическому описанию военные и правовые конфликты, спортивные состязания, «салонные» игры, а также явления, связанные с биологической борьбой за существование.
Понятие «Теории игр»
Теория игр, раздел математики, изучающий формальные модели принятия оптимальных решений в условиях конфликта. В условиях конфликта стремление противника скрыть свои предстоящие действия порождает неопределённость. Наоборот, неопределённость при принятии решений (например, на основе недостаточных данных) можно интерпретировать как конфликт принимающего решения субъекта с природой. Поэтому Теория игр рассматривается также как теория принятия оптимальных решений в условиях неопределённости. Она позволяет математизировать некоторые важные аспекты принятия решений в технике, сельском хозяйстве, медицине и социологии. Перспективен подход с позиций Теории игр к проблемам управления, планирования и прогнозирования.
Основным в Теории игр является понятие игры, являющееся формализованным представлением о конфликте. Точное описание конфликта в виде игры состоит поэтому в указании того, кто и как участвует в конфликте, каковы возможные исходы конфликта, а также кто и в какой форме заинтересован в этих исходах. Участвующие в конфликте стороны называются коалициями действия; доступные для них действия -- их стратегиями; возможные исходы конфликта -- ситуациями (обычно каждая ситуация понимается как результат выбора каждой из коалиций действия некоторой своей стратегии); стороны, заинтересованные в исходах конфликта, -- коалициями интересов; их интересы описываются предпочтениями тех или иных ситуаций (эти предпочтения часто выражаются численными выигрышами). Конкретизация перечисленных объектов и связей между ними порождает разнообразные частные классы игр.
2.
Кооперативная теория игр
Если в игре имеется единственная коалиция действия, то стратегии этой коалиции можно отождествить с ситуациями и далее больше уже о стратегиях не упоминать. Такие игры называются нестратегическими. Класс нестратегических игр весьма обширен. К их числу относятся, в частности, кооперативные игры.
Примером нестратегической (кооперативной) игры может служить простая игра, состоящая в следующем. Множеством ситуаций являются в ней всевозможные распределения (дележи) между игроками некоторого количества однородной полезности (например, денег). Каждый делёж описывается теми суммами, которые при этом получают отдельные игроки. Коалиция интересов называется выигрывающей, если она может даже в условиях противодействия со стороны всех остальных игроков присвоить и разделить между своими членами всю имеющуюся полезность. Все коалиции, не являющиеся выигрывающими, совсем не могут присвоить какой-либо доли полезности. Такие коалиции называются проигрывающими. Естественно считать, что выигрывающая коалиция предпочитает один делёж другому, если доля каждого из её членов в условиях первого дележа больше, чем в условиях второго. Проигрывающие же коалиции не могут сравнивать дележи по предпочтительности (это условие также вполне естественно: коалиция интересов, которая сама не в состоянии добиться ничего, вынуждена соглашаться на любой делёж и лишена возможности выбора между дележами).
Если в игре имеется более одной коалиции действия, то игра называется стратегической. Важный класс стратегических игр составляют бескоалиционные игры, в которых коалиции действия совпадают с коалициями интересов (они называются игроками), а предпочтения для игроков описываются их функциями выигрыша: игрок предпочитает одну ситуацию другой, если в первой ситуации он получает больший выигрыш, чем во второй.
Одним из простейших примеров бескоалиционной игры может служить «морра» в следующем своём варианте. Три игрока показывают одновременно 1 или 2 пальца каждый. Если все три игрока показывают одно и то же число, то выигрыш каждого равен нулю. В противном случае один из игроков показывает a (= 1 или 2) и получает b из некоторого источника (например, из банка, образованного предварительными взносами), а два других игрока, показывающие одно и то же b (? a), не получают ничего.
3. Антагонистические и позиционные игры
Если в бескоалиционной игре участвуют два игрока, а значения их функций выигрыша в любой ситуации отличаются только знаками, то игра называется антагонистической игрой; в ней выигрыш одного из игроков в точности равен проигрышу другого. Если в антагонистической игре множества стратегий обоих игроков конечны, то игра называется матричной игрой ввиду некоторой специфической возможности её описания.
Антагонистические игры (матем.), понятие теории игр. Антагонистические игры -- игры, в которых участвуют два игрока (обычно обозначаемые I и II) с противоположными интересами. Для А. и. характерно, что выигрыш одного игрока равен проигрышу другого и наоборот, поэтому совместные действия игроков, их переговоры и соглашения лишены смысла. Большинство азартных и спортивных игр с двумя участниками (командами) можно рассматривать как А. и. Принятие решений в условиях неопределённости, в том числе принятие статистических решений, также можно интерпретировать как А. и. Определяются А. и. заданием множеств стратегий игроков и выигрышей игрока I в каждой ситуации, состоящей в выборе игроками своих стратегий. Таким образом, формально А. и. есть тройка ‹А, В, Н›, в которой А и В -- множества стратегий игроков, а Н (а, b) -- вещественная функция (функция выигрыша) от пар (а, b), где а ? A, b ? В. Игрок I, выбирая а, стремится максимизировать Н(а, b), а игрок II, выбирая b, -- минимизировать Н (а, b). А. и. с конечными множествами стратегий игроков называются матричными играми.
Матричные игры - игры, в которых участвуют два игрока (I и II) с противоположными интересами, причём каждый игрок имеет конечное число чистых стратегий. Если игрок I имеет m стратегий, а игрок II -- n стратегий, то игра может быть задана (m ? n)-maтрицей А = ||aij||, где aij есть выигрыш игрока I, если он выберет стратегию i (i = -1,..., m), а игрок II -- стратегию j (j = 1,..., n).
В качестве другого примера бескоалиционной игры можно привести шахматы. В этой игре участвуют два игрока (белые и чёрные). Стратегия каждого из игроков есть мыслимое (хотя практически и не поддающееся детальному описанию) правило выбора в каждой возможной позиции некоторого хода, допускаемого движениями фигур. Пара таких правил (за белых и за чёрных) составляет ситуацию, которая полностью определяет протекание шахматной партии и в том числе её исход. Функция выигрыша белых имеет значение 1 на выигрываемых партиях, 0 на ничейных и -- 1 на проигрываемых (такой способ начисления очков практически ничем не отличается от принятого в турнирной и матчевой практике). Функция выигрыша чёрных отличается от функции выигрыша белых лишь знаком. Из сказанного видно, что шахматы относятся к числу антагонистических и притом матричных игр. В шахматах стратегии не выбираются игроками до начала игры, а реализуются постепенно, ход за ходом. Это значит, что шахматы принадлежат к позиционным играм.
Позиционные игры, класс бескоалиционных игр, в которых принятие игроками решений (т. е. выбор ими стратегий) рассматривается как многошаговый или даже непрерывный процесс. Другими словами, в П. и. в ходе процесса принятия решений субъект проходит последовательность состояний, в каждом из которых ему приходится принимать некоторое частичное решение. Поэтому в П. и. стратегии игроков можно понимать как функции, ставящие в соответствие каждому информационному состоянию игрока (т. е. состоянию, характеризуемому информацией игрока о положении дел в игре в данный момент) выбор некоторой возможной в этом состоянии альтернативы.
И. т. является нормативной теорией, тоесть предметом её изучения являются не столько сами модели конфликтов (игры), как таковые, сколько содержание принимаемых в играх принципов оптимальности, существования ситуаций, на которых эти принципы оптимальности реализуются (такие ситуации или множества ситуаций называются решениями в смысле соответствующего принципа оптимальности), и, наконец, способы нахождения таких ситуаций. Рассматриваемые в И. т. объекты -- игры -- весьма разнообразны, и пока не удалось установить принципов оптимальности, общих для всех классов игр. Практически это означает, что единого для всех игр истолкования понятия оптимальности ещё не выработано. Поэтому прежде чем говорить, например, о наивыгоднейшем поведении игрока в игре, необходимо установить, в каком смысле эта выгодность понимается. Все применяемые в И. т. принципы оптимальности при всём их внешнем разнообразии отражают прямо или косвенно идею устойчивости ситуаций или множеств ситуаций, составляющих решения. В бескоалиционных играх основным принципом оптимальности считается принцип осуществимости цели, приводящий к ситуациям равновесия. Эти ситуации характеризуются тем свойством, что любой игрок, который отклонится от ситуации равновесия (при условии, что остальные игроки не изменят своих стратегий), не увеличит этим своего выигрыша.
В частном случае антагонистических игр принцип осуществимости цели превращается в так называемый принцип максимина (отражающий стремление максимизировать минимальный выигрыш).
Принципы оптимальности (первоначально выбиравшиеся интуитивно) выводятся на основании некоторых заранее задаваемых их свойств, имеющих характер аксиом. Существенно, что различные применяемые в И. т. принципы оптимальности могут противоречить друг другу.
Теоремы существования в И. т. доказываются преимущественно теми же неконструктивными средствами, что и в других разделах математики: при помощи теорем о неподвижной точке, о выделении из бесконечной последовательности сходящейся подпоследовательности и т. п., или же, в весьма узких случаях, путём интуитивного указания вида решения и последующего нахождения решения в этом виде.
Фактическое решение некоторых классов антагонистических игр сводится к решению дифференциальных и интегральных уравнений, а матричных игр -- к решению стандартной задачи линейного программирования. Разрабатываются приближённые и численные методы решения игр. Для многих игр оптимальными оказываются так называемые смешанные стратегии, то есть стратегии, выбираемые случайно (например, по жребию).
4. Задача
Предприятие может выпускать два вида продукции, используя один набор компонентов, причем количество выпускаемой продукции определяется целыми числами. Прибыль, получаемая предприятием от продажи единицы продукции каждого вида, расход каждого из компонентов на производство единицы продукции каждого вида и лимиты по каждому из компонентов представлены в Таблице 1.
Необходимо определить количество продукции каждого вида, которое необходимо выпустить для получения максимальной прибыли при условии не перерасходования лимитов по компонентам. Данная задача решается
Таблица 1
Математическая формулировка задачи:
F= 5x+4x>max
3x +3x ?29
5x +8x ?22
3x +9x ?31
9x +8x ?23
х, х - выпускаемое количество продукции.
Решение с использованием функции Microsoft Excel «Поиск решения».
1. Вводим исходные данные (Таблица 1).
2. Вводим формулы в ячейки, значения которых нам неизвестны.
B8=B6*B7+C6*C7
3. Выполнить команду Сервис > Поиск решения. Откроется диалоговое окно Поиск решения.(Рисунок 2).
· Установить курсор в поле Установить целевую ячейку диалогового окна и щелкнуть мышкой на целевой ячейке В8.
· Устанавить максимальное значание.
· Установить курсор в поле Изменяя ячейки и выделить диапазон изменяемых ячеек В6:С6.
· Установить курсор в поле Ограничения, щелкнуть кнопку Добавить и вводить в появившееся диалоговое окно (Рисунок 1) поочередно все необходимые ограничения.
Рисунок 2.1
· Щелкнуть на кнопке Выполнить диалогового окна Поиск решения.
Результаты поиска решения представлены в Таблице 2, Рисунок 3.
Решив задачу, я определила, что количество выпускаемой продукции первого типа равно 2 ед., второго - 0 ед., т.е. производство продукции второго типа будет нерентабельным и поэтому будет лучше отказаться от выпуска этой продукции. Общая прибыль равна 10. При этом соблюдены все введенные мною ограничения.
Таблица 2
Рисунок 2.3
Заключение
И. т., созданная для математического решения задач экономического и социального происхождения, не может в целом сводиться к классическим математическим теориям, созданным для решения физических и технических задач. Однако в различных конкретных вопросах И. т. широко используются весьма разнообразные классические математические методы. Кроме этого, И. т. связана с рядом математических дисциплин внутренним образом. В И. т. систематически и по существу употребляются понятия теории вероятностей. На языке И. т. можно сформулировать большинство задач математической статистики.
И. т. применяется в экономике, технике, военном деле и даже в антропологии. Основные трудности практического применения И. т. связаны с экономической и социальной природой моделируемых ею явлений и недостаточным умением составлять такие модели на количественном уровне.
Список использованной литературы
1. Шикин Е.В., Чхартишвили
А.Г. Математические методы и
2. Трояновский В.М. Математическое моделирование в менеджменте. Учебное пособие. 2-е изд., испр. и доп. - М.: Издательство РДЛ. 2003.
Понятие об игровых моделях. Платежная матрица. Нижняя и верхняя цена игры. Решение игр в чистых стратегиях. Решение игр в смешанных стратегиях. Геометрическая интерпретация игры 2×2. Приведение матричной игры к задаче линейного программирования.
5.1. Понятие об игровых моделях
На практике часто приходится сталкиваться с задачами, в которых необходимо принимать решения в условиях неопределенности, т. е. возникают ситуации, в которых две (или более) стороны преследуют различные цели, а результаты любого действия каждой из сторон зависят от мероприятий партнера. Такие ситуации относятся к конфликтным: результат каждого хода игрока зависит от ответного хода противника, цель игры – выигрыш одного из партнеров. В экономике конфликтные ситуации встречаются очень часто и имеют многообразный характер. К ним относятся, например, взаимоотношения между поставщиком и потребителем, покупателем и продавцом, банком и клиентом.
Теория игр – раздел математики, изучающий конфликтные ситуации на основе их математических моделей.
Игра – математическая модель конфликтной ситуации.
Игроки – стороны, участвующие в конфликте.
Выигрыш – исход конфликта. Для того чтобы решить игру, или найти решение игры, следует для каждого игрока выбрать стратегию, которая удовлетворяет условию оптимальности, т. е. один из игроков должен получать максимальный выигрыш, когда второй придерживается своей стратегии. В то же время второй игрок должен иметь минимальный проигрыш, если первый придерживается своей стратегии. Такие стратегии называются оптимальными. Оптимальные стратегии должны также удовлетворять условию устойчивости, т. е. любому из игроков должно быть невыгодно отказаться от своей стратегии в этой игре.
5.2. Платёжная матрица. Нижняя и верхняя цена игры
Рассмотрим парную конечную игру. Пусть игрок А располагает m личными стратегиями, которые обозначим A1, A2, …, Аm. Пусть у игрока В имеется n личных стратегий, обозначим их B1, B2, …, Bm. Таким образом, игра имеет размерность m × n. В результате выбора игроками любой пары стратегий однозначно определяется исход игры, т. е. выигрыш аij игрока А (положительный или отрицательный) и проигрыш (–аij) игрока В. Предположим, что значения аij известны для любой пары стратегий (Ai, Bj). Матрица , элементами которой являются выигрыши, соответствующие стратегиям Ai и Bj, называется платежной матрицей, или матрицей игры. Общий вид такой матрицы представлен в табл. 5.1.
Таблица 5.1
Платёжная матрица
Вj Аi |
В1 |
В2 |
… |
Вn |
А1 |
а11 |
а12 |
… |
а1n |
А2 |
а21 |
а22 |
… |
а2n |
… |
… |
… |
… |
… |
Аm |
аm1 |
аm2 |
… |
аmn |
Рассмотрим игру m × n с матрицей и определим наилучшую среди стратегий A1, A2, …, Аm. Выбирая стратегию Аi игрок А должен рассчитывать, что игрок В ответит на нее той из стратегий Bj, для которой выигрыш для игрока А минимален (игрок В стремится «навредить» игроку А).
Обозначим через α наименьший выигрыш игрока А при выборе им стратегии А; для всех возможных стратегий игрока В (наименьшее число в i-й строке платежной матрицы).
Назовем α нижней ценой игры, или максимальным выигрышем (максимином). Это гарантированный выигрыш игрока А при любой стратегии игрока В. Следовательно,
.
Стратегия, соответствующая максимину, называется максиминной стратегией. Игрок В заинтересован в том, чтобы уменьшить выигрыш игрока А; выбирая стратегию Bj, он учитывает максимально возможный при этом выигрыш для А. Назовем В верхней ценой игры, или минимаксным выигрышем (минимаксом). Это гарантированный проигрыш игрока В. Следовательно,
.
Стратегия, соответствующая минимаксу, называется минимаксной стратегией.
Принцип, диктующий игрокам выбор наиболее «осторожных» минимаксной и максиминной стратегий, называется принципом минимакса. Этот принцип следует из разумного предположения, что каждый игрок стремится достичь цели, противоположной цели противника.
Если верхняя и нижняя цены игры совпадают, то общее значение верхней и нижней цены игры α = β = ν называется чистой ценой игры, или ценой игры.
Минимаксные стратегии, соответствующие цене игры, являются оптимальными стратегиями, а их совокупность – оптимальным решением, или решением игры. В этом случае игрок А получает максимальный гарантированный (не зависящий от поведения игрока В) выигрыш ν, а игрок В добивается минимального гарантированного (вне зависимости от поведения игрока А) проигрыша ν. Говорят, что решение игры обладает устойчивостью, т. е. если один из игроков придерживается своей оптимальной стратегии, то для другого не может быть выгодным отклоняться от своей оптимальной стратегии.
Пара чистых стратегий Ai и Bj дает оптимальное решение игры тогда и только тогда, когда соответствующий ей элемент аij является одновременно наибольшим в своем столбце и наименьшим в своей строке. Такая ситуация, если она существует, называется седловой точкой (по аналогии с поверхностью седла, которая искривляется вверх в одном направлении и вниз – в другом).
Обозначим А* и В* – пару чистых стратегий, на которых достигается решение игры в задаче с седловой точкой. Введем функцию выигрыша первого игрока на каждой паре стратегий: P(Ai Bj) = аij. Тогда из условия оптимальности в седловой точке выполняется двойное неравенство: P(Ai, B*) ≤ Р(А*, В*) ≤ P(A*, Bj), которое справедливо для всех . Действительно, выбор стратегии А* первым игроком при оптимальной стратегии В* второго игрока максимизирует минимальный возможный выигрыш: Р(А*, В*) ≥ P(Ai, B*), а выбор стратегии В* вторым игроком при оптимальной стратегии первого минимизирует максимальный проигрыш: Р(А*, В*) ≤ P(A*, Bj).
5.3. Решение игр в смешанных стратегиях. Приведение матричной игры к задаче линейного программирования
Если игра не имеет седловой точки, то применение чистых стратегий не дает оптимального решения игры. В таком случае можно получить оптимальное решение, случайным образом чередуя чистые стратегии.
Смешанной стратегией игрока А называется применение чистых стратегий A1, A2, …, Аm с вероятностями р1, р2, …, рm, причем сумма вероятностей равна: . Смешанные стратегии игрока А записываются в виде . Аналогично смешанные стратегии игрока В обозначаются как , где сумма вероятностей появления стратегий .
Чистые стратегии можно считать частным случаем смешанных и задавать строкой, в которой 1 соответствует чистой стратегии. На основании принципа минимакса определяется оптимальное решение (или решение) игры: это пара оптимальных стратегий S*A, S*В, в общем случае смешанных, обладающих следующим свойством: если один из игроков придерживается своей оптимальной стратегии, то другому не может быть выгодно отступать от своей. Выигрыш, соответствующий оптимальному решению, называется ценой игры ν. Цена игры удовлетворяет неравенству α ≤ v ≤ β, где α и β – нижняя и верхняя цены игры.
Пусть и – пара оптимальных стратегий.
Решение задачи линейного программирования (ЛП) определяет оптимальную стратегию . При этом цена игры
. (
Очевидно, при определении оптимальных стратегий в конкретных задачах следует выбрать ту из взаимно-двойственных задач, решение которой менее трудоемко, а решение другой задачи найти с помощью теорем двойственности.
5.4. Примеры решения задач систем массового обслуживания
Пример 1. Предприятие может выпускать три вида продукции (А1, A2 и А3), получая при этом прибыль, зависящую от спроса, который может быть в одном из трёх состояний (В1, В2 и В3). Дана матрица (табл. 5.2), ее элементы аij характеризуют прибыль, которую получит предприятие при выпуске i-й продукции с j-м состоянием спроса.
Таблица 5.2
Платежная матрица игры
Вj Аi |
В1 |
В2 |
В3 |
pi |
α |
А1 |
3 |
6 |
8 |
p1 |
3 |
А2 |
9 |
4 |
2 |
p2 |
2 |
А3 |
7 |
5 |
4 |
p3 |
4* |
qj |
q1 |
q2 |
q3 |
||
β |
9 |
6* |
8 |
α = 4, β = 6 |
Определить оптимальные пропорции в выпускаемой продукции, гарантирующие среднюю величину прибыли при любом состоянии спроса, считая его неопределенным.
Решение. Задача сводится к игровой модели, в которой игра предприятия А против спроса В задана платежной матрицей (табл. 5.3).
Определим нижнюю и верхнюю цены игры в табл. 5.2.
Так как α ≠ β, то седловая точка отсутствует, и оптимальное решение следует искать в смешанных стратегиях игроков:
и .
Обозначив xi = pi/v, yj = qj/v, составим две взаимно-двойственные задачи линейного программирования.
Задача 1. Игрок А. |
Задача 2. Игрок В. |
Рекомендуется решать задачу на максимум, как, например, задача 2, поскольку первое базисное решение для нее будет допустимым. Введем добавочные переменные и перейдем к уравнениям, т. е. приведём задачу линейного программирования к каноническому виду[1]. Учитывая соответствие между переменными задач (вторая теорема двойственности), получим:
Свободные (первоначальные) |
Базисные (дополнительные) |
x1 x2 x3 |
x4 x5 x6 |
↕ ↕ ↕ |
↕ ↕ ↕ |
y4 y5 y6 |
y1 y2 y3 |
Базисные (дополнительные) |
Свободные (первоначальные) |
т. е.: x* = (0,074; 0; 0,111), у* = (0,037; 0,148; 0). При решении задачи линейного программирования с помощью надстройки MS Excel «Поиск решения» решение двойственной задачи содержится в отчёте Устойчивость: основные переменные – в столбце «Результ. значение», а дополнительные – в столбце «Теневая цена».
Используя первую теорему двойственности, получим: Zmin = Z´max = 0,185. По формуле (5.3): ν = 1/0,185 = 5,4. Учитывая, что xi = pi/v, yj = qj/v, получим:
pi = xi ∙ v, p1 = 0,074 ∙ 5,4 = 0,4, p2 = 0 ∙ 5,4 = 0, p3 = 0,111 ∙ 5,4 = 0,6.
qj = yj ∙ v, q1 = 0,037 ∙ 5,4 = 0,2, q2 = 0,148 ∙ 5,4 = 0,8, q3 = 0.
Оптимальная стратегия игрока А – SA = (0,4; 0; 0,6), игрока В – SВ = = (0,2; 0,8; 0).
Решение двойственной задачи линейного программирования представлено на рис. 5.1–5.3.
Рис. 5.1. Решение задачи теории игр с помощью надстройки MS Excel «Поиск решения»
Рис. 5.2. Данные для решения задачи в надстройке MS Excel «Поиск решения»
Рис. 5.3 Использование отчёта «Устойчивость» для поиска дополнительных переменных
Ответ: Предприятие должно выпустить 40 % продукции А1 и 60 % продукции А3, а продукцию А2 не выпускать.
Оптимальный спрос в 20 % времени находится в состоянии В1, и в 80 % – в состоянии В2, при этом математическое ожидание прибыли составит 5,4 ден. ед.
При решении произвольной конечной игры размера m × n рекомендуется придерживаться следующей схемы.
1. Исключить из платежной матрицы заведомо невыгодные стратегии по сравнению с другими стратегиями. Такими стратегиями для игрока А (игрока В) являются те, которым соответствуют строки (столбцы) с элементами, заведомо меньшими (большими) по сравнению с элементами других строк (столбцов).
2. Определить верхнюю и нижнюю цены игры и проверить, имеет ли игра седловую точку. Если седловая точка есть, то соответствующие ей стратегии игроков будут оптимальными, а цена совпадает с верхней (нижней) ценой.
3. Если седловая точка отсутствует, то решение следует искать в смешанных стратегиях.
5.5. Исходные данные
