ПРАКТИЧЕСКАЯ РАБОТА №3
Модели теории игр
Понятие об игровых моделях
Теория игр занимается разработкой различного рода рекомендаций по принятию решений в условиях конфликтной ситуации. Формируя конфликтные ситуации математически, их можно представить как игру двух, трёх и более игроков, каждый из которых преследует цель максимизации своего выигрыша за счет другого игрока. Математическая модель конфликтной ситуации называется игрой, стороны, участвующие в конфликте, – игроками, а исход конфликта – выигрышем. Для каждой формализованной игры вводятся правила, т.е. система условий, определяющая:
1. варианты действий игроков;
2. объем информации каждого игрока о поведении партнеров;
3. выигрыш, к которому приводит каждая совокупность действий.
Как правило, выигрыш может быть задан количественно (например, проигрыш – 0, выигрыш – 1, ничья – ½). Игра называется парной, если в ней участвуют два игрока, и множественной, если число игроков больше двух. Игра называется игрой с нулевой суммой, если выигрыш одного из игроков равен проигрышу другого. Выбор и осуществление одного из предусмотренных правилами действий называется ходом игрока. Ходы могут быть личными и случайными. Личный ход – сознательный выбор игроком одного из возможных действий (ход в шахматной игре), случайный ход – случайно выбранное действие (выбор карты из перетасованной колоды).
Стратегией игрока называется совокупность правил, определяющих выбор его действия при при каждом личном ходе в зависимости от сложившейся ситуации. Игра называется конечной, если у игрока имеется конечное число стратегий, и бесконечной – в противном случае.
Для того, чтобы решить игру, или найти решение игры, следует для каждого игрока выбрать стратегию, которая удовлетворяет условию оптимальности, т.е. один из игроков должен получить максимальный выигрыш, когда второй придерживается своей стратегии. В то же время второй игрок должен иметь минимальный проигрыш, если первый придерживается своей стратегии. Такие стратегии называются оптимальными. Целью теории игр является определение оптимальной стратегии для каждого игрока. При выборе оптимальной стратегии естественно предполагать, что оба игрока ведут себя разумно с точки зрения своих интересов.
Платежная матрица. Нижняя и верхняя цена игры
Рассмотрим парную конечную игру. Пусть игрок А располагает m личными стратегиями, которые обозначим А1, А2,…,Аm. Пусть у игрока B имеется n личных стратегий, обозначим их B1, B2,…,Bn. Говорят, что игра имеет размерность m ´ n. В результате выбора игроками любой пары стратегий Аi и Bj однозначно определяется исход игры, т.е. выигрыш aij игрока А (положительный или отрицательный) и проигрыш (-aij) игрока В. Матрица Р=(aij), элементами которой являются выигрыши, соответствующие стратегиям Аi и Bj, называется платежной матрицей или матрицей игры.
Пример – игра «Поиск»
Игрок А может спрятаться в убежище 1 – обозначим эту стратегию за А1 или в убежище 2 – стратегия А2. Игрок В может искать первого игрока в убежище 1 –стратегия В1, либо в убежище 2 – стратегия В2. Если игрок А находится в убежище 1 и его там обнаруживает игрок В, т.е. осуществляется пара стратегий (А1,В1), то игрок А платит штраф, т.е. a11=–1. Аналогично получаем a22=–1. Очевидно, что стратегии (А1,В2) и (А2,В1) дают игроку А выигрыш 1, поэтому a12=a21=1. Таким образом, получаем платежную матрицу
Рассмотрим игру m ´ n с матрицей Р=(aij) и определим наилучшую среди стратегий игрока А. Выбирая стратегию Аi, игрок А должен рассчитывать, что игрок В ответит на нее той из стратегий Вj, для которой выигрыш для игрока А минимален (игрок В стремится «навредить» игроку А).
Читать еще: Лесной человек яг-морт. Йиркап и лось
Обозначим через ai наименьший выигрыш игрока А при выборе им стратегии Аi для всех возможных стратегий игрока В (наименьшее число в i-й строке платежной матрицы), т.е. .
Среди всех чисел ai выберем наибольшее: . Назовем a нижней ценой игры, или максимальным выигрышем (максимином). Это гарантированный выигрыш игрока А при любой стратегии игрока В. Следовательно, .
Стратегия, соответствующая максимину, называется максиминной стратегией. Игрок В заинтересован в том, чтобы уменьшить выигрыш игрока А; выбирая стратегию Bj, он учитывает максимально возможный при этом выигрыш для A. Обозначим .
Среди всех чисел выберем наименьшее иназовем b верхней ценой игры, или минимаксным выигрышем (минимаксом). Это гарантированный проигрыш игрока В при любой стратегии игрока А. Следовательно, .
Стратегия, соответствующая минимаксу, называется минимаксной стратегией. Принцип, диктующий игрокам выбор наиболее осторожных минимаксной и максиминной стратегий, называется принципом минимакса.
Статистические игры
Во многих задачах, приводящихся к игровым, неопределенность вызвана отсутствием информации об условиях, в которых осуществляется действие. Эти условия зависят не от сознательных действий другого игрока, а от объективной действительности, которую принято называть «природой». Такие игры называют играми с природой (статистическими играми).
Задача
После нескольких лет эксплуатации промышленное оборудование оказывается в одном из следующих состояний: В1 – оборудование может использоваться в очередном году после профилактического ремонта; В2 – для безаварийной работы оборудования в дальнейшем следует заменить отдельные его детали и узлы; В3 – оборудование требует капитального ремонта или замены.
В зависимости от сложившейся ситуации В1,В2,В3 руководство предприятия может принять такие решения: А1– отремонтировать оборудование силами заводских специалистов, что требует соответствующих затрат а1=6, а2=10, а3=15 ден.ед; А2 – вызвать специальную бригаду ремонтников, расходы в этом случае составят b1=15, b2=9, b3=18 ден.ед; А3 – заменить оборудование новым, реализовав устаревшее оборудование по его остаточной стоимости. Совокупные затраты в результаты этого мероприятия будут равны соответственно с1=13, с2=24, с3=12 ден.ед.
Задание
1. Придав описанной ситуации игровую схему, выявить ее участников, указать возможные чистые стратегии сторон.
2. Составить платежную матрицу, пояснив смысл элементов aij матрицы (почему они отрицательные?).
3. Выяснить, какое решение о работе оборудования в предстоящем году целесообразно рекомендовать руководству предприятия, чтобы минимизировать потери при следующих предположениях: а) накопленный на предприятии опыт эксплуатации аналогичного оборудования показывает, что вероятности указанных состояний оборудования равны соответственно q1=0,15; q2=0,55; q3=0,3 (примените критерий Байеса); б) имеющийся опыт свидетельствует о том, что все три возможных состояния оборудования равновероятны (примените критерий Лапласа); в) о вероятности оборудования ничего определенного сказать нельзя (примените критерии Вальда, Сэвиджа, Гурвица). Значение параметра g=0,8 в критерии Гурвица задано.
Решение
1) Описанная ситуация представляет собой статистическую игру.
В качестве статистика выступает руководство предприятия, которое может принять одно из следующих решений: отремонтировать оборудование своими силами (стратегия А1), вызвать ремонтников (стратегия А2); заменить оборудование новым (стратегия А3).
Второй играющей стороной – природой будем считать совокупность факторов, влияющих на состояние оборудования: оборудование может использоваться после профилактического ремонта (состояние В1); нужно заменить отдельные узлы и детали оборудования (состояние В2): потребуется капитальный ремонт или замена оборудования (состояние В3).
2) Составим платежную матрицу игры:
Элемент платежной матрицы аij показывает затраты руководства предприятия, если при выбранной стратегии Аi оборудование окажется в состоянии Вj. Элементы платежной матрицы отрицательны, так как при любой выбранной стратегии руководству предприятия придется нести расходы.
Читать еще: Бэйн биография. Бэйн: Краткая история персонажа
3) Выясним, какое решение целесообразно рекомендовать руководству предприятия, чтобы минимизировать потери при следующих предположениях:
а) накопленный на предприятии опыт эксплуатации аналогично оборудования показывает, что вероятности состояний оборудования равны q1=0,15; q2=0,55; q3=0,3.
Платежная матрица игры
Платежная матрица – это метод статистической теории принятия решений, способствующий выбору руководителем правильного варианта.
Сущность игровых моделей
Математическая модель какой-либо конфликтной ситуации – это игра, стороны, принимающие участие в конфликте, — это игроки, а исход конфликта – это выигрыш.
Каждая формализованная игра имеет свои правила, т.е. систему условий, определяющих:
- Варианты решений игроков;
- Количество информации у каждого игрока о партнерах;
- Выигрыш, который является следствием совокупности действий.
Обычно выигрыш (проигрыш) задается количественно, к примеру, проигрыш оценивается нулем, а выигрыш – единицей, ничья – это 1/2. Количественная оценка исхода игры – это платеж.
Игра будет парной, когда в ней принимают участие два игрока, а множественной, когда число игроков превышает два.
Игра будет называться игрой с нулевой суммой в случае, если выигрыш одного игрока равняется проигрышу второго, т.е. сумма выигрышей двух сторон равна 0. Чтобы полностью задать игру, достаточно определить величину одного. Если обозначить за $a$ выигрыш одного игрока, за $b$ выигрыш другого, то игра с нулевой суммой будет равняться $b = – a$. В данном случае достаточно рассмотреть $а$.
Попробуй обратиться за помощью к преподавателям
Определение и осуществление какого-либо действия, предусмотренного правилами игры, называется ходом игроков. Ход может быть личным или случайным. При личном ходе игрок сознательно выбирает одно из возможных действий. Состав возможных вариантов регламентируется правилами игры, а зависит от совокупности предыдущих ходов обеих сторон.
Случайным ходом является случайно совершенное действие, к примеру, выбор карты из колоды.
Некоторые игры состоят только лишь из случайных ходов, например, азартные, а некоторые – только из личных, примером которых являются шашки, шахматы. Многие карточные игры относятся к играм смешанного типа, содержащим и случайные, и личные ходы.
Игры могут классифицироваться не только по видам ходов, но и по объему информации, которая доступна каждому игроку. В особый класс игр выделяются игры с полной информацией, в которых каждый игрок при личном ходе имеет информацию о результатах предыдущих ходов. Примером игры с полной информацией являются шашки, шахматы, «крестики и нолики». Многие игры, обладающие практическим значением, не относятся к категории игр с полной информацией, поскольку неизвестность в отношении действий противника – это существенный элемент конфликтных ситуаций.
Задай вопрос специалистам и получи
ответ уже через 15 минут!
Основное понятие теории игр – это понятие стратегии. Под стратегией игрока следует понимать совокупность правил, которые определяют выбор его действий при личном ходе в зависимости от ситуации. Игра будет конечной, если каждый игрок имеет определенное число стратегий, при обратной ситуации – бесконечной.
Чтобы отыскать решение игры, необходимо для каждого игрока определить стратегию, удовлетворяющую условиям оптимальности, другими словами, один игрок должен получить максимальный выигрыш, тогда как второй придерживается заданной стратегии. Проигрыш второго игрока должен быть минимальным, если первый следует своей стратегии. Данные стратегии являются оптимальными и должны удовлетворять условиям устойчивости, т.е. для любого игрока будет невыгодно отказываться от своей стратегии в данной игре.
Платежная матрица игры
Парная игра с нулевой суммой удобнее исследуется, если она представлена в матричном виде. Допустим, что игрок $A$ располагает m стратегиями $A_1, A_2, …, A_m$, а игрок $B$, т.е. противник, — $n$ стратегиями $B_1, B_2, …, B_n$. Данная игра будет называться игрой с размерностью $m * n$.
Читать еще: Певица Света: биография и личная жизнь.
Предположим, что игрок $A$ выбрал одну стратегию $A_j$. Игрок $B$, не обладая информацией о результатах выбора игрока $A$, выбрал себе стратегию $B_j$. Каждой паре стратегий ($A_j, B_j$) присущ платеж $a(ij)$ первому игроку от второго, т.е. выигрыш игрока $A$. Выигрыш игрока $B$ будет равен $–a(ij)$. Подобная игра называется матрицей, а матрица, которая составлена из значений $a(ij)$, называется платежной. Строки такой матрицы соответствуют выбранной стратегии игрока $A$, а столбцы – стратегии игрока $B$. В общем виде платежная матрица игры имеет вид (рисунок 1):
Рисунок 1. Платежная матрица. Автор24 — интернет-биржа студенческих работ
Так и не нашли ответ
на свой вопрос?
Просто напиши с чем тебе
нужна помощь
Матричные игры с нулевой суммой. Платежная матрица игры
ЭЛЕМЕНТЫ ТЕОРИИ ИГР
Во многих практических задачах возникают ситуации, когда требуется принять решение, не имея достаточной информации. Неизвестными могут быть как условия осуществления какой-либо операции, так и сознательные действия лиц, от которых зависит успех этой операции.
· Ситуации, в которых сталкиваются интересы двух сторон и результат любой операции, осуществляемой одной стороной, зависит от действий другой стороны, называются конфликтными.
· Математическая модель конфликтной ситуации называется игрой, а математическая теория, помогающая принимать рациональные решения в конфликтной ситуации, — теорией игр.
· Конфликтующие стороны называются игроками, а действия, которые могут выполнять игроки, — стратегиями.
От реальной ситуации игра отличается тем, что в игре противники действуют по строго определенным правилам.
· Матричной игрой называется игра, осуществляемая по следующим правилам:
1. В игре участвуют два игрока;
2. Каждый из игроков обладает конечным набором стратегий;
3. Игра заключается в том, что каждый из игроков, не имея информации о действиях противника, делает один ход (выбирает одну из своих стратегий). Результатом выбора игроками стратегий является выигрыш и проигрыш в игре.
4. И выигрыш, и проигрыш выражаются числами.
· Матричная игра называется игрой с нулевой суммой, если в этой игре выигрыш одного игрока равняется проигрышу другого игрока.
Каждая матричная игра с нулевой суммой имеет платежную матрицу. Для того чтобы построить эту матрицу, обозначим одного из игроков символом А, а другого – символом В, и предположим, что А1, А2,…, Аm – стратегии, которые может применять игрок А, а В1, В2,…, Вn – стратегии, которые может применять игрок В.
· Матричная игра, в которой у игрока А имеется m стратегий, а у игрока В – n стратегий, называется игрой типа .
,
у которой элементы равны выигрышам игрока А (и проигрышам игрока В) при применении игроками стратеги Ai и Bj соответственно.
· Матрица С называется платежной матрицей игры.
Пример 1.1.Игра, называемая «Открывание пальцев», заключается в следующем. Два игрока одновременно из сжатого кулака правой руки открывают по несколько пальцев. Общее количество открытых пальцев является суммой выигрыша, причем, если общее количество открытых пальцев четно, то выигрывает первый игрок, если же общее количество пальцев нечетно, то выигрывает второй игрок.
Составить платежную матрицу игры.
Решение.Поскольку каждый из игроков может открыть 1, 2, 3, 4 или 5 пальцев, то у каждого из них имеется по 5 соответствующих стратегий: стратегии А1, А2, А3, А4, А5 у первого игрока, и В1, В2, В3, В4, В5 – у второго. Таким образом, рассматриваемая игра является матричной игрой типа , и можно составить таблицу выигрышей, в зависимости от стратегий, применяемых игроками (Таблица 2.1.1):
Из таблицы 1.1 следует, что платежная матрица игры имеет вид
.
Источники:
http://lektsii.org/6-75250.html
http://spravochnick.ru/ekonomicheskaya_statistika/platezhnaya_matrica_igry/
http://mydocx.ru/6-141983.html
