Итерационные методы решения матричных игр
Многократное фиктивное разыгрывание игры, когда одна итерация называется партией - сущность метода Брауна-Робинсона. Теорема, которая подтверждает сходимость алгоритма. Формулы, применяющиеся для определения значения итеративных последовательностей.
| Рубрика | Математика |
| Вид | статья |
| Язык | русский |
| Дата добавления | 25.01.2022 |
| Размер файла | 36,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru
Размещено на http://www.allbest.ru
Итерационные методы решения матричных игр
1. Метод Брауна-Робинсона (метод фиктивного разыгрывания)
Идея метода: многократное фиктивное разыгрывание игры, когда одна итерация называется партией.
Рассматривается матричная игра ГА с матрицей А={бij}, где .
В первой партии игроки произвольно выбирают свои чистые стратегии.
В k-й партии каждый игрок выбирает ту чистую стратегию, которая максимизирует его ожидаемый выигрыш против наблюдаемого эмпирического вероятностного распределения противника за (k-1) партию. Пусть за k - партий игрок 1 i-ю стратегию использовал -раз, а игрок 2 свою j-ю стратегию использовал -раз.
В (k+1)-й партии игрок 1 будет использовать ik+1-стратегию, а игрок 2 -jk+1 стратегию.
Запишем следующие соотношения:
;
.
Если рассмотреть как соответственно верхнее и нижнее приближённые значения за k- партий, то приближённые оптимальные смешанные стратегии соответственно 1 и 2 го игроков за k-партий можем записать как:
и .
Значение игры V находится в диапазоне:
.
Сходимость представленного алгоритма подтверждается следующей теоремой:
Теорема:
.
Недостатком данного метода является его медленная и немонотонная сходимость.
Пример. Найти приближённые оптимальные стратегии игроков и значение матричной игры с матрицей . Видим из написанного, что седловой точки нет и значение игры находится в интервале 1<V<2. Стратегии игрока 1 обозначены как б, в, г, стратегии игрока обозначены как a, b, c.
Вычислительный алгоритм удобнее представить в виде следующей таблицы, в которой на первом шаге взяты первые чистые стратегии игроков:
Табл. 1
|
№ партии |
Выбор игрока 1 |
Выбор игрока 2 |
Выигрыш игрока 1 |
Проигрыш игрока 2 |
|||||||
|
б |
в |
г |
a |
b |
c |
||||||
|
1 |
б |
a |
2 |
3 |
1 |
2 |
1 |
3 |
|||
|
2 |
в |
b |
3 |
3 |
3 |
5 |
1 |
4 |
|||
|
3 |
в |
b |
4 |
3 |
5 |
8 |
1 |
5 |
|||
|
4 |
г |
b |
5 |
3 |
7 |
9 |
3 |
6 |
|||
|
5 |
г |
b |
6 |
3 |
9 |
10 |
5 |
7 |
|||
|
6 |
г |
b |
7 |
3 |
11 |
11 |
7 |
8 |
|||
|
7 |
г |
b |
8 |
3 |
13 |
12 |
9 |
9 |
|||
|
8 |
г |
c |
11 |
4 |
14 |
13 |
11 |
10 |
|||
|
9 |
г |
c |
14 |
5 |
15 |
14 |
13 |
11 |
|||
|
10 |
г |
c |
17 |
6 |
16 |
15 |
15 |
12 |
|||
|
11 |
б |
c |
20 |
7 |
17 |
17 |
16 |
15 |
|||
|
12 |
б |
c |
23 |
8 |
18 |
19 |
17 |
18 |
и
2. Монотонный алгоритм решения матричных игр
Алгоритм позволяет находить (точно и приближённо) оптимальную стратегию 1-го игрока и значение матричной игры V.
Рассматривается матричная игра ГА с матрицей размерности mЧn. Обозначим через - приближённое значение оптимальной стратегии 1-го игрока на N-й итерации. Также введём на N-й итерации как важный элемент нашего алгоритма вспомогательный вектор . Пояснения по его получению будет дано по шагам алгоритма.
Шаг 0: игрок 1 выбирает произвольную свою чистую стратегию i0, т.е. , и вспомогательный вектор строка матрицы А. Приближённое значение игры на шаге 0 будем определять, как
(1)
и через
(2)
обозначим множество тех индексов, для которых выполняется равенство (1).
Замечание: на последующих шагах алгоритма соотношения (1) и (2) будем определять аналогично, лишь изменяя верхний индекс 0 на индекс соответствующего шага, т.е. для N шага эти значения будем обозначать соответственно: VN, JN.
Шаг N-1: допустим, что выполнена N-1 итерация и полученыx N-1, cN-1, VN-1.
Шаг N: тогда xN, cN вычисляются по следующим формулам:
(3)
(4),
где , а получение векторов , будем описывать ниже:
Пусть на Nшаге рассматривается игра ГNГАcматрицей АN=, где , т.е. это матрица А только с частью столбцов, определяемых на N-1 шаге по формулам (1) и (2).
Решаем подыгру ГN и находим для этой игры оптимальную стратегию 1-го игрока . Вектор определяем по формуле:
,
где ai строки матрицы А.
Далее решаем (2Чn)-игру с матрицей:
(5)
и находим для этой игры оптимальную стратегию 1-го игрока (1-бN, бN), значения которых подставляем в уравнения (3), (4) для нахождения xN, cN.
Вычислительный процесс продолжается до тех пор, пока не будет выполнено условие бN =0 или не будет достигнута требуемая точность вычисления.
Условие бN =0 говорит о том, что в матрице (5) первая строка доминирует вторую и, следовательно, в качествеоптимальной стратегии 1-го игрока в исходной задаче можно взять х*=xN=xN-1 и V=VN-1.
Сходимость алгоритма гарантируется следующей теоремой:
Теорема: если - итеративные последовательности, значения которых получаются согласно формулам соответственно (1), (3), тогда выполняются следующих 3 условия:
1. VN>VN-1, т.е. последовательность строго монотонно возрастет с ростом итераций;
2. , где V - цена исходной задачи;
3. , х*Х* - оптимальная стратегия первого игрока.
Рассмотрим пример. Дана игра ГА с платёжной матрицей .
Найти ситуацию равновесия в данной игре.
Решение: шаг 0.В качестве х0 выберем первую чистую стратегию 1-го игрока, т.е. х0=(1,0,0) и соответственно в качестве с0 выберем первую строку матрицы А: . Решаем по алгоритму выражение (1):
итеративный игра формула
=min(2,1,3)=1=.
Следовательно (2) J0={2}, т.е. второй столбец матрицы А.
Шаг 1. Для нахождения , и подстановки их значений в формулы (3), (4) рассмотрим подыгру Г1ГА c матрицей А1=, равной второму столбцу матрицы А. Оптимальной стратегией этой игры есть выбор третьей чистой стратегии 1-го игрока, как лучший выигрыш из 1, 0, 2, т.е. =(0,0,1)., т.е. третья строка матрицы А.
Решаем (2Ч3) игру с матрицей. Так как элементы третьего столбца а3 данной матрицы элементов первого столбца а1, то он доминируем первым столбцом, следовательно его можно убрать из решения, не нарушая спектр оптимальных стратегий. Имеем (2Ч2) игру с матрицей. Эта игра вполне смешанная, поэтому решая эту игру по известным формулам прямого счёта, получим оптимальную стратегию 1-го игрока (1-б1, б1)=.
Так как б10, то вычисления продолжаем. Вычислим формулы (3) и (4):
;
;
,
т.е. 1 и 2-й столбцы матрицы А.
Шаг 2. Для нахождения , рассмотрим подыгру Г2ГА c матрицей А2=, равной первому и второму столбцам матрицы А. Так как доминируема и её можно вычеркнуть из спектра оптимальных стратегий. Имеем (2Ч2) игру с матрицей. Эта игра вполне смешанная, поэтому решая эту игру по известным формулам прямого счёта, получим для игры с матрицей оптимальную стратегию 1-го игрока =. Добавлением 0 в качестве первой координаты в получим = оптимальную стратегию 1-го игрока для игры с матрицей А2.
. Решаем (2Ч3) игру с матрицейа2 доминируема а1 матрица 1-б2=1 и б2=0вычисления по алгоритму закончены.
Имеем
V=V1=, х*=x2=x1=х*Ах*Ау*=V
=, а так как
у*=(*,1-*,0),
где *[0,1].
Самостоятельно решить матричные игры с платёжными матрицами:
и итерационными методами Брауна-Робинсона и монотонным методом, когда по первому методу в матрице А на первом шаге выбрать вторые чистые стратегии игроков, а в матрице В - выбрать четвёртую чистую стратегию 1-го игрока и вторую чистую стратегию 2-го игрока и найти приближённые оптимальные стратегии игроков и интервал, в котором находится значение игры, сделав по 20 итераций. Для второго метода на 0-м шаге в качестве чистой стратегии для матрицы А выбрать третью чистую стратегию 1-го игрока, а для матрицы В четвёртую чистую стратегию 1-го игрока.
Размещено на Allbest.ru
...Подобные документы
Теория игр – раздел математики, предметом которого является изучение математических моделей принятия оптимальных решений в условиях конфликта. Итеративный метод Брауна-Робинсона. Монотонный итеративный алгоритм решения матричных игр.
дипломная работа [81,0 K], добавлен 08.08.2007Свойства гармонических функций. Бесконечная дифференцируемость, конформная инвариантность, принцип экстремума, теорема единственности. Свойство среднего значения. Интегральные формулы Пуассона и Шварца. Неравенство Харнака, равномерная сходимость.
методичка [523,2 K], добавлен 14.10.2013Анализ методов решения систем нелинейных уравнений. Простая итерация, преобразование Эйткена, метод Ньютона и его модификации, квазиньютоновские и другие итерационные методы решения. Реализация итерационных методов с помощью математического пакета Maple.
курсовая работа [820,5 K], добавлен 22.08.2010Основные определения теории биматричных игр. Пример биматричной игры "Студент-Преподаватель". Смешанные стратегии в биматричных играх. Поиск "равновесной ситуации". 2x2 биматричные игры и формулы для случая, когда у каждого игрока имеется две стратегии.
реферат [84,2 K], добавлен 13.02.2011Итерационные методы (методы последовательных приближений) для решения уравнений. Одношаговые итерационные формулы. Метод последовательных приближений Пикара. Возникновение хаоса в детерминированных системах. Методы решения систем алгебраических уравнений.
контрольная работа [166,2 K], добавлен 04.09.2010Общая характеристика сходимости последовательностей случайных величин и вероятностных распределений. Значение метода характеристических функций в теории вероятностей. Методика решения задач о типах сходимости. Анализ теоремы Ляпунова и Линдеберга.
курсовая работа [2,6 M], добавлен 22.07.2011Математические модели явлений или процессов. Сходимость метода простой итерации. Апостериорная оценка погрешности. Метод вращений линейных систем. Контроль точности и приближенного решения в рамках прямого метода. Метод релаксации и метод Гаусса.
курсовая работа [96,7 K], добавлен 13.04.2011Сходимость последовательностей случайных величин и вероятностных распределений. Метод характеристических функций. Проверка статистических гипотез и выполнение центральной предельной теоремы для заданных последовательностей независимых случайных величин.
курсовая работа [364,8 K], добавлен 13.11.2012Характеристика важнейших типов сходимости итерационных последовательностей. Специфические особенности применения метода Ньютона для определения кратных корней. Алгоритм нахождения корней трансцендентного уравнения с использованием метода секущих.
дипломная работа [964,9 K], добавлен 09.06.2019Основные понятия и определения кубических уравнений, способы их решения. Формула Кардано и тригонометрическая формула Виета, сущность метода перебора. Применение формулы сокращенного умножения разности кубов. Определение корня квадратного трехчлена.
курсовая работа [478,4 K], добавлен 21.10.2013Поиск нулей функции как важнейшая процедура при исследовании и построении различных функций зависимостей, его значение при изучении непрерывных процессов. Характерные признаки наличия корня у функции. Итерация Ньютона для задания системы уравнений.
реферат [48,6 K], добавлен 10.08.2009Задачи для обыкновенных дифференциальных уравнений. Квадратурные формулы. Теоретические основы метода сеток для решения задачи Коши. Погрешность аппроксимации, устойчивость, основная теорема метода сеток. Схема предиктор-корректор 2-го порядка.
реферат [47,4 K], добавлен 07.12.2013Суть модифицированного метода Эйлера. Определение интерполяционного многочлена. Выведение формулы трапеций из геометрических соображений. Применение для расчетов интерполированного полинома Ньютона. Составление блок-схемы алгоритма решения уравнений.
курсовая работа [252,7 K], добавлен 14.02.2016Сущность итерационного метода решения задачи, оценка его главных преимуществ и недостатков. Разновидности итерационных методов решения систем линейных алгебраических уравнений: Якоби, Хорецкого и верхней релаксации, их отличия и возможности применения.
курсовая работа [39,2 K], добавлен 01.12.2009Сходимость последовательностей случайных величин. Центральная предельная теорема для независимых одинаково распределенных случайных величин. Основные задачи математической статистики, их характеристика. Проверка гипотез по критерию однородности Смирнова.
курсовая работа [1,6 M], добавлен 13.11.2012Методика преобразования вращения и ее значение в решении алгебраических систем уравнений. Получение результирующей матрицы. Ортогональные преобразования отражением. Итерационные методы с минимизацией невязки. Решение методом сопряженных направлений.
реферат [116,3 K], добавлен 14.08.2009Решения задач дискретной математики: диаграммы Эйлера-Венна; высказывание в виде формулы логики высказываний и формулы логики предикатов; СДНФ и СКНФ булевой функции. При помощи алгоритма Вонга и метода резолюции выяснить является ли клауза теоремой.
контрольная работа [133,5 K], добавлен 08.06.2010История квадратных уравнений: уравнения в Древнем Вавилоне и Индии. Формулы четного коэффициента при х. Квадратные уравнения частного характера. Теорема Виета для многочленов высших степеней. Исследование биквадратных уравнений. Сущность формулы Кордано.
реферат [75,8 K], добавлен 09.05.2009Базовые основы системы mn параметров, варианты их значений. Теоремы циклов для треугольников и прямоугольного треугольника. Тайна теоремы Пифагора, предистория ее рождения. Итерационные формулы и их использование. Дисперсия точек ожидаемой функции.
статья [241,5 K], добавлен 24.11.2011Определение матричных игр в чистых стратегиях. Смешанные стратегии и их свойства. Решения игр матричным методом. Метод последовательного приближения цены игры. Отыскание седлового элемента. Антагонистические игры как первый класс математических моделей.
контрольная работа [855,7 K], добавлен 01.06.2014
