Равноценность. Если в игре несколько седловых точек, то значения функции выигрыша в них одинаковы

1. Равноценность. Если в игре несколько седловых точек, то значения функции выигрыша в них одинаковы.

2. Взаимозаменяемость оптимальных стратегий. Игроки могут заменить свои оптимальные стратегии другими оптимальными стратегиями, при этом равновесие не нарушится, а выигрыш (проигрыш) останется неизменным.

Теорема. Аффинно-эквивалентные игры имеют одни и те же седловые точки ( то есть их решения совпадают).

Седловыке точки и минимаксы

Устойчивое решение игры может быть получено путем следующих рассуждений:

В самом неблагоприятном случае выигрыш первого игрока не может быть уменьшен по вине противника, если он удовлетворяет условию:

a _ij* = min а_ij

С другой стороны, руководствуясь принципом выгоднгодности первый игрок будет стремиться увеличить свой выигрыш, сохраняя свойство устойчивости, поэтому v_н = max min а_ij

Это нижняя цена игры. Рассуждая подобным образом за второго игрока получим верхнюю цену игры:

v_в = min max а_ij

Интуитивно ясно, что значение ( цена ) игры лежит между v_н и v_в.

Теорема. Для того, чтобы в матричной игре существовали минимаксы, необходимо и достаточно, чтобы равны были минимаксы:

max min а_ij = min max а_ij

Оптимальные смешанные стратегии и их свойства.

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

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

Смешанной стратегией игрока в матричной игре называется полный набор вероятностей x = ( x₁, x₂ ... x_m) и y = ( y₁, y₂ ... y_n) применения его чистых стратегий. (чистые стратегии - исходные).

 Свойства смешанных стратегий.

 1 свойство. Если x" = ( x₁, x₂, ... x_m ) и y" = ( y₁, y₂,...y_n ) - оптимальные смешанные стратегии игроков в матричной игре, то для произвольных стратегий x и y справедливо

 Н ( А, x", y) = å a_ij x_i" ³ v для всех j=1:n, так как это равносильно использованию вторым игроком чистой j-той стратегии: y = ( 0, 0,...y_j=1,... 0, 0 )

 Н ( А, x, y") = å a_ij y_j" £ v для всех i=1:m, так как это равносильно использованию первым игроком чистой i-той стратегии: x = ( 0, 0,...x_i=1,... 0, 0 )

 2 свойство. Если в матричной игре с матрицей А и ценой игры v стратегии x" и y" - оптимальные, то

 если å a_ij x_i" > v, то y_j" = 0

 если å a_ij y_j" < v, то x_i" = 0

 если неравенства обращаются в равенства, то соответственно:

 xi" ¹ 0, yj" ¹ 0.

 На приведенных свойствах основано решение матричных игр в смешанных стратегиях.

 2.6. Доминирование в матричных играх.

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

 Пусть задана матричная игра с платежной матрицей А, а смешанные стратегии игроков представлены в виде x = ( x₁, x₂,... x_m ) и y = ( y₁, y₂,... y_n). Вектор х' строго доминирует вектор х"( вектор x" строго доминируется вектором x' ), если справедливо: x_i' > x_i" , i=1:m. Если неравенство нестрогое, то и доминирование является нестрогим.

Теорема. Если строка с номером r в матрице А строго доминируется выпуклой линейной комбинацией всех остальных строк, то она входит с нулевой вероятностью в любую оптимальную смешанную стратегию первого игрока.

 Если x~, y~- пара оптимальных смешанных стратегий игры с матрицей A, то удалив из вектора x~ нулевую координату с номером r получим пару оптимальных смешанных стратегий x`~,y~ игры с матрицей A`, полученной из матрицы A вычеркиванием строки с номером r.

 Обратное утверждение тоже верно. Если x`~,y~- пара оптимальных смешанных стратегий игры с матрицей A`, то добавив в качестве r-той коодинаты вектора x`~ ноль и сдвинув на одно место вправо все координаты вектора x~ с номерами r, r+1... m-1, получим пару оптимальных смешанных стратегий x~,y~ игры с матрицей A.

Теорема. Если строка с номером r в матрице А нестрого доминируется выпуклой линейной комбинацией всех остальных строк, то существует оптимальная смешанная стратегия первого игрока x~, у которой r-тая координата равна нулю.

 Любая пара x`~,y~ оптимальных смешанных стратегий игры с матрицей А` преобразуется в пару оптимальных смешанных стратегий x~,y~ игры с матрицей А добавлением нулевой координаты с номером r в вектор x`~ и сдвигом координат этого вектора с номерами r, r+1,...m-1 на одно место вправо.

 Во всех этих случаях значение игры с матрицей А совпадает со значением игры с матрицей А~.

Теорема. Если столбец с номером s в матрице А строго доминирует выпуклую линейную комбинацию всех остальных столбцов, то он входит с нулевой вероятностью в любую оптимальную смешанную стратегию второго игрока.

 Если x~,y~ - пара оптимальных смешанных стратегий в игре с матрицей А, то удалив из вектора y~ нулевую координату с номером s, получим пару оптимальных смешанных стратегий x~,y`~ игры с матрицей A`, полученной из матрицы А вычеркиванием столбца с номером s.

 Обратное: если x~,y`~ - пара оптимальных смешанных стратегий игры с матрицей A`, то добавив в качестве координаты с номером s вектора y`~ ноль и сдвинув все координаты с номерами s, s+1,... n-1 на одно место вправо получим пару x~,y~ оптимальных смешанных стратегий в игре с матрицей А.

Теорема. Если столбец с номером s в матрице А нестрого доминирует выпуклую линейную комбинацию всех остальных столбцов, то существует такая оптимальная смешанная стратегия y~ второго игрока, в которой координата с номером s равна нулю и любая пара x~,y`~ оптимальных смешанных стратегий игры с матрицей А` преобразуется в пару оптимальных смешанных стратегий x~,y~ игры с матрицей А добавлением нулевой s-той координаты и сдвигом координат с номерами s, s+1,... n-1 вектора y`~ вправо на одно место.

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

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

 Метод приближенного определения цены игры.

Способ отыскания приближенного решения прямоугольных игр был сформулирован в работе Г.В.Брауна, а сходимость процесса была доказана Джулией Робинсон в 1951 году.

Этот метод, называемый еще итеративным, опирается на традиционный статистический принцип: основывать будущие решения на соответствующей предыстории.

Заключается он в последовательной процедуре "сближения" вержней и ниждей цены игры с заданной точностью.

Глава . Биматричные игры

[VU1] 

Функция выигрыша биматричной игры представляет собой две платежные матрицы : А - определяет выигрыш первого игрока, а В - выигрыш второго игрока. Первый игрок имеет m чистых стратегий ( m строк в матрицах А и В ) Второй игрок имеет n чистых стратегий ( n столбцов в матрицах А и В ).

В результате выбора первым игроком i-той стратегии, а вторым игроком j-той стратегии, первый игрок получает выигрыш a_ij, а второй - b_ij .

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

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

а_i*j ³ а_ij j=1:n

Для второго игрока ситуация ij* приемлема, если его выигрыш в этой ситуации не меньше, чем в любой другой:

b_i*j ³ b_ij i=1:m

Tаким образом, приемлемые ситуации для первого игрока - это максимальные элементы встолбцах матрицы А, а для второго игрока - максимальные (тоже!) элементы в строках матрицы В.

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

а_i*j* ³ а_ij*

b_i*j* ³ b_i*j

Множество ситуаций равновесия G образуется как пересечение множеств приемлемых ситуаций первого и второго игроков.

Пример.

G₁={(1,1),(1,3),(3,2),(3,3)}

G₂={(1,1),(2,1),(2,3),(3,2)} G = {(1,1),(3,2)}

I v(1,1)= 3 II v(1,1)= 3

v(3,2)= 3 v(3,2)= 2

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

Из примера хорошо видно, что хотя (1,1) и (3,2) - ситуации равновесия, ситуации (1,2) и (3,1) таковыми не являются, в отличие от матричных игр.

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

Так, в рассматриваемом примере второй игрок заинтересован в том, чтобы первый выбрал i=1, так как при этом v(II)= 3. Первому же игроку с точки зрения выгоды безразлично какую стратегию выбрать - первую или третью - в любом случае его выигрыш составляет 3. Если первый игрок доброжелательно настроен по отношению к противнику, то он выберет первую стратегию, чтобы и второй игрок получил максимальный выигрыш. В противном случае первый потребует за выбор более выгодной для второго стратегии дополнительную плату, и если эта плата будет меньше единицы, то очевидно, что второй игрок согласится на эту сделку.Такая игра называется игрой с побочными платежами.

Если в биматричной игре ситуаций равновесия нет, но игроки имеют возможность договориться между собой, то обычно применяют такой искусственный прием: находится i*j* такая,что:

max ( a_ij + b_ij ) = ( a_i*j* + b_i*j* )

и делится между игроками по заранее оговоренному правилу.

Пример.

Ситуаций равновесия нет. Находим максимальный элемент в матрице А+В

max = 5, ( i, j ) = (3,2). Эта сумма должна быть разделена между первым и вторым игроками.

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

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

Задание по биматричным играм

Придумать условие биматричной игры n*m, n = m > 3 и найти ее решения в чистых стратегиях ("игра с побочными платежами")

Глава . Нестратегические игры

Похожие работы

Теория принятия решений: математические методы для выбора специалиста на должность администратора сети

Скачать

16587

14

0

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

Математические методы в теории принятия решений

Скачать

22330

8

1

... максимизирующий выделенный критерий на множестве исходов, оценки которых по остальным критериям не ниже назначенных. Всякие задачи принятия решения является: Альтернативы (варианты, планы, допустимые альтернативы) Исходы (Результаты) Оптимальные решения (Наилучшие решения) Математическая модель ЗПР включает в себя формальное описание этих компонентов. X - множество допустимых альтернатив A ...

Теория принятия решений

Скачать

83422

1

0

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

Измерительные шкалы в математическом моделировании. Теория принятия решений

Скачать

13429

2

0

... , среднее распределение процентных отношений, дисперсия, стандартные отклонения, коэффициенты вариации Коэффициенты – j, c2, Чупрова, Спирмена, коэффициент корреляции Пирсона 2. Теория принятия решений Выбор любого управленческого решения всегда ограничен. Это объясняется необходимостью следовать определённым нормам поведения, которые и ориентируют руководителя. В зависимости от ...