МЕТОДЫ УПРОЩЕНИЯ ПЛАТЁЖНЫХ МАТРИЦ. ДОМИНИРОВАНИЕ И ДУБЛИРОВАНИЕ СТРАТЕГИЙ

ОСНОВНЫЕ ПОНЯТИЯ

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

Опр. Конфликт – это противоречие, вызванное противоположными интересами.

Игра - математическая модель конфликтной ситуации. В отличие от реального конфликта игра ведётся по четким правилам.

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

Развитие игры происходит последовательно, по этапам или ходам. Ходом в теории игр называют выбор одного из предусмотренных правилами игры действия.

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

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

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

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

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

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

Игра называется игрой с нулевой суммой, если один игрок выигрывает ровно столько, сколько проигрывает другой, т.е. сумма выигрыша и проигрыша сторон равна нулю.

Парная игра с нулевой суммой называется антагонистической игрой.

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

ПЛАТЕЖНАЯ МАТРИЦА. ВЕРХНЯЯ И НИЖНЯЯ ЦЕНА ИГРЫ.

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

Предположим, что игрок А имеет m стратегий (А₁, А₂, ..., А_m), а игрок В — n стратегий (В₁, В₂, ..., В_n). Такая игра называется игрой размерностью m ´ n. Пусть каждая сторона определилась с выбором стратегии: игрок A выбрал одну из своих возможных стратегий A_i (i = 1, 2, ..., m), игрок В — B_j (j = 1, 2, ..., n), то выбор стратегии (A_i, B_j) однозначно определяет исход игры , т.е. выигрыш игрока I. Предположим, что значения a_ij известны для каждой пары стратегий (A_i, B_j). Эти числа удобно представить в виде матрицы, называемой платежной матрицей, строки которой соответствуют стратегиям игрока А, а столбцы — стратегиям игрока В. Каждый элемент (a_ij > 0) матрицы определяет величину выигрыша игрока I и проигрыш игрока II. Платежная матрица имеет следующий вид:

I \ II B₁ B₂ ... B_j ... B_n

A₁ a₁₁ a₁₂ ... a_1j ... a_1n

A₂ a₂₁ a₂₂ ... a_2j ... a_2n

... ... ... ... ... ... ...

A_i a_i1 a_i2 ... a_ij ... a_in

... ... ... ... ... ... ...

A_m a_m1 a_m2 ... a_mj ... a_mn

Такая игра называется матричной.

Цель игрока I — максимизировать свой выигрыш, а игрока II — минимизировать свой проигрыш.

Пример 1.

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

А =

Пример 2.

Игроки A и B играют в следующую игру. Игрок A записывает одно из чисел 6, 7, 9, а игрок B записывает одно из чисел 4, 5. Если сумма чисел четная, то это выигрыш игрока А. Если сумма чисел нечётная, то это выигрыш игрока В (проигрыш игрока А). Найти платёжную матрицу игры А.

Имеем три стратегии первого игрока. А₁ = 6, А₂ = 7, А₃ = 9, В₁ = 4, В₂ = 5. Матрица игры:

А =

Пример 3.

Каждый из игроков, A или B , может записать, независимо от другого, цифры 1, 2 и 3. Если разность между цифрами, записанными игроками, положительна, то A выигрывает количество очков, равное разности между цифрами. Если разность меньше 0, выигрывает B. Если разность равна 0 – ничья.
У игрока A три стратегии (варианта действия): A₁= 1 (записать 1), A₂= 2, A₃= 3, у игрока В тоже три стратегии: B₁, B₂, B₃.

B A	B₁= 1	B₂= 2	B₃= 3
A₁ = 1	0	-1	-2
A₂= 2	1	0	-1
A₃= 3	2	1	0

Задача игрока A – максимизировать свой выигрыш. Задача игрока B – минимизировать свой проигрыш, т. е. минимизировать выигрыш A. Это парная игра с нулевой суммой.

Проанализируем последовательно каждую стратегию игрока А.

I \ II B₁ B₂ ... B_j ... B_n

A₁ a₁₁ a₁₂ ... a_1j ... a_1n a₁

A₂ a₂₁ a₂₂ ... a_2j ... a_2n a₂

... ... ... ... ... ... ... ...

A_i a_i1 a_i2 ... a_ij ... a_in a_i

... ... ... ... ... ... ... ...

A_m a_m1 a_m2 ... a_mj ... a_mn a_m

Β_j b₁ b₂ ... b_j ... b_n

Если игрок А выбирает стратегию А₁, то игрок В может выбрать такую стратегию B_j, при которой выигрыш игрока А будет равен наименьшему из чисел a₁_j:

Выбирая стратегию A_i, игрок А должен рассчитывать на то, что в результате разумных действий игрока В он не выиграет больше, чем a_i. Поэтому игрок А должен выбрать ту стратегию, для которой a_i максимально:

Величина a — гарантированный выигрыш, который может обеспечить себе игрок А при любом поведении игрока В. Величина a называется нижней ценой игры или максимином, а стратегия А_i игрока А, обеспечивающая получение нижней цены игры, называется максиминной чистой стратегией. При этом игрок А при любом поведении игрока В обеспечивает себе выигрыш, не меньше a: a_i £ a (i = 1, 2, ..., m).

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

и среди этих значений выбрать наименьшее: .

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

b_j ³ b (j = 1, 2, ..., n).

Всегда справедливо неравенство a £ b.

Таким образом, придерживаясь максиминной стратегии A_i, игрок А желает получить выигрыш не менее a не зависимо от действий игрока В, а игрок В, придерживаясь минимаксной стратегии B_j, гарантирует себе проигрыш не больше b.

Принцип максимальной осторожности, диктующий игрокам выбор максиминной или минимаксной стратегий в теории игр, называется принципом минимакса. Этот принцип был впервые сформулирован Дж. фон Нейманом в 1944 году.

Пример 1.

Дана платежная матрица. Найти решение игры: определить нижнюю и верхнюю цены игры и минимаксные стратегии:

I \ II B₁ B₂ B₃ B₄ a →min

A₁ 5 3 8 2 2

A₂ 1 6 4 3 1

A₃ 9 5 4 7 4↓ max

_β 9 6 8 7

↓ max → min

Таким образом, нижней цене игры (a = 4) соответствует стратегия A₃ игрока I. Выбирая эту стратегию, игрок I достигнет выигрыша не меньше 4 в худшем случае, когда игрок II выбирает В₃. Верхней цене игры (b = 6) соответствует стратегия игрока II — В₂ Стратегия В₂ гарантирует II игроку проигрыш не более 6, в худшем случае, когда I игрок выбирает А₂ . Эти стратегии являются минимаксными. Если первый игрок знает, что второй выбирает В₃, то ему выгоднее отклониться от А₃ и выбрать более рискованную стратегию А₂. Рассуждения можно продолжить для второго игрока. Следовательно, партнеры «заметались по стратегиям», т.е. ситуация неустойчивая по отношению к информации о поведении второго игрока.

Существуют матричные игры, для которых нижняя цена игры равна верхней, т.е. a = b. Такие игры называются играми с седловой точкой.

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

В этом случае g = a = b=a_ij называется чистой ценой игры, а стратегии игроков и , позволяющие получить это значение — оптимальными.

Оптимальные стратегии и и чистая цена являются решением игры в чистых стратегиях.

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

Пример 2.

Пусть задана платежная матрица. Найти нижнюю и верхнюю цены игры.

I II B₁ B₂ B₃ a

A₁ 5 1 2 1

A₂ 2 6 2 2

A₃ 3 4 3 3

b 5 6 3

Следовательно a = b = g = 3.

Седловой точкой является пара альтернатив (А₃, В₃).

Пример3.

Первая сторона (игрок А) выбирает один из трех типов вооружения – А₁, А₂, А₃, а противник (игрок В) – один из трех видов самолетов: В₁, В₂, В₃. Цель В – прорыв фронта обороны, цель А – поражение самолета. Вероятность поражения самолета В₁ вооружением А₁ равна 0,5, самолета В₂ вооружением А₁ равна 0,6, самолета В₃ вооружением А₁равна 0,8 и т.д., т.е. элемент a_ij платежной матрицы – вероятность поражения самолета В_j вооружением А_i. Платежная матрица имеет вид:

В А		Вид самолета
В А		В₁	В₂	В₃
Тип вооружения	А₁	0,5	0,6	0,8
	А₂	0,9	0,7	0,8
	А₃	0,7	0,5	0,6

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

В А	В₁	В₂	В₃	α_i
А₁	0,5	0,6	0,8	0,5
А₂	0,9	0,7	0,8	0,7
А₃	0,7	0,5	0,6	0,5
β_j	0,9	0,7	0,8	0,7 0,7

В добавочном столбце находим максимальный элемент = 0,7, в добавочной строке находим минимальный элемент = 0,7.
Ответ: α = β = 0,7. Оптимальные стратегии – А₂ и В₂.

Пример 4.

Игра в орлянку. Каждый игрок при своем ходе может выбирать одну из двух стратегий: орел или решка. При совпадении выбранных стратегий А получает выигрыш +1, при несовпадении B получает выигрыш 1 (т. е. А получает выигрыш –1). Платежная матрица:

В А	В₁(орел)	В₂(решка)
А₁(орел)	1	-1
А₂(решка)	-1	1

Найти нижнюю и верхнюю цену игры. Имеет ли игра седловую точку?

Решение.

В А	В₁	В₂
А₁	1	-1	-1
А₂	-1	1	1
β_j	1	1	-1 1

α = -1, β = 1, т. е. А проиграет не больше 1, и B проиграет не больше 1. Так как α ≠ β, игра не имеет седловой точки. Положения равновесия в этой игре не существует, и оптимального решения в чистых стратегиях найти нельзя.

МЕТОДЫ УПРОЩЕНИЯ ПЛАТЁЖНЫХ МАТРИЦ. ДОМИНИРОВАНИЕ И ДУБЛИРОВАНИЕ СТРАТЕГИЙ

Рассмотрим несколько методов упрощения платёжных матриц.

Первый метод, используемый для уменьшения размерности матрицы, основан на одном из важнейших понятий в теории игр - понятии доминирования стратегий.

Если i-я строка поэлементно не меньше (≥) j-й строки, то говорят, что i-я строка доминирует над j-й строкой. Поэтому игрок A не использует j-ю стратегию, так как его выигрыш при i-й стратегии не меньше, чем при j-й стратегии, вне зависимости от того, как играет игрок B.

Аналогично, если i-й столбец поэлементно не меньше (≥) j-го столбца, то говорят, что j-й столбец доминирует над i-м столбцом. Поэтому игрок B не использует i-ю стратегию, так как его проигрыш (равный выигрышу игрока A) при j-й стратегии не больше (≤), чем при i-й стратегии, вне зависимости от того, как играет игрок A. Стратегии, над которыми доминируют другие стратегии, надо отбросить. На цене игры это никак не скажется. Зато размер матрицы игры понизится. С этого и нужно начинать решение игры.

Частный случай доминирования является дублирование стратегий.

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

Рассмотрим ряд примеров.

Пример 1. Платёжная матрица игры задана в виде:

Упростим игру (упростим платёжную матрицу).

1-я и 4-я строки равны. Поэтому отбросим 4-ю строку. Получим матрицу:

2-я строка доминирует над 3-й строкой (6 > 3, 5 > 4, 8 = 8, 7 > 6). Поэтому отбросим 3-ю строку. Получим матрицу:

2-й столбец доминирует над 3-м столбцом (9 = 9, 5 < 8). Поэтому отбросим 3-й столбец. Получим матрицу:

Строки между собой не сравнимы (8 > 6, 4 < 7), столбцы тоже (8 < 9, 6 > 5; 8 > 4, 6 < 7; 9 > 4, 5 < 7). Дальнейшее упрощение невозможно. Мы свели игру 4×4 к игре 2×3.

Пример 2. С учетом вариантов конъюнктуры В₁, В₂, В₃, В₄, В₅ сложившейся на рынке и поведения покупателей в микрорайоне города коммерческое предприятие разработало шесть технологий продажи товаров А_1,А_2, А₃, А₄, А₅, А₆. Найти оптимальное решение. Возможные варианты среднедневного товарооборота в млн.руб. приведены в таблице:

	В₁	В₂	В₃	В₄	В₅
А₁	0,4	0,9	0,5	0,5	0,6
А₂	0,6	0,5	0,7	0,8	0,9
А₃	0,6	0,3	0,8	0,6	0,7
А₄	0,3	0,8	0,5	0,4	0,3
А₅	0,1	0,3	0,5	0,4	0,3
А₆	0,4	0,8	0,5	0,4	0,5

Стратегия А₁ доминирует над стратегией А₆, а стратегия А₄доминирует над стратегией А₅, следовательно исключаем 5 и 6 строки матрицы

	В₁	В₂	В₃	В₄	В₅
А₁	0,4	0,9	0,5	0,5	0,6
А₂	0,6	0,5	0,7	0,8	0,9
А₃	0,6	0,3	0,8	0,6	0,7
А₄	0,3	0,8	0,5	0,4	0,3

С позиций проигрышей строки В стратегии В_3,В₄ и В₅ доминируют над стратегией В_1,поэтому эти столбцы исключаем из таблицы:

	В₁	В₂
А₁	0,4	0,9
А₂	0,6	0,5
А₃	0,6	0,3
А₄	0,3	0,8

С позиций игрока А стратегия А₁ доминирует над стратегией А₄, а стратегия А₂ доминирует над стратегией А₃, следовательно исключаем 3 и 4 строки матрицы:

	В₁	В₂
А₁	0,4	0,9
А₂	0,6	0,5

Пример 3. Матрица игры

Упростить игру.

1 - ый шаг: A₁доминирует A₂: вычёркиваем 2- ю строку, в результате получаем платёжную матрицу:

2-ой шаг: A₃доминирует A₁: вычёркиваем 1- ю строку, в результате получаем платёжную матрицу:

3-ий шаг: B₂ доминирует B₁ вычёркиваем 1- ый столбец, в результате получаем платёжную матрицу:

4-ый шаг: B₄ доминирует B₃ вычёркиваем 2 - ый столбец, в результате получаем платёжную матрицу:

5 -ый шаг: A₃доминирует A₄: вычёркиваем 4 - ю строку, в результате получаем платёжную матрицу:

6 - ой шаг: B₂ доминирует B₄ вычёркиваем 4 - ый столбец, в результате получаем платёжную матрицу:

В результате упрощения платёжной матрицы было установлено наличие седловой точки и получено оптимальное решение в чистых стратегиях: первый игрок A должен действовать, все время, выбирая стратегию A₃, а игрок B выбирает стратегию B₂.

Тот же результат получается, если использовать максиминную стратегию.

V_* = max min a_ij = max{4,3,6,3}= 6

V^* = min max a_ij= min{8,6,10,8}= 6

V_* = V* = 6, элемент матрицы а₃₂ является седловой точкой.

Замечание. Если игра m×n имеет седловую точку, то после упрощений платёжной матрицы мы всегда получим игру 1×1.

Продолжим рассмотрение методов упрощения платёжной матрицы.

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

Теорема об аффинных преобразованиях. Аффинное преобразование (преобразование подобия и сдвига) платежной матрицы, т.е. преобразование всех элементов матрицы A вида: , где k ≠ 0 и b -любая константа, не изменяет решение игры. Кроме того, цена преобразованной игры может быть получена из цены первоначальной игры V по тому же правилу:

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

Прибавление (вычитание) некоторой фиксированной суммы b к каждому из элементов a_ij платёжной матрицы A изменит на такую же сумму выигрыш (проигрыш) каждого из игроков, не меняя при этом решения игры. Это свойство может быть использовано для преобразования исходной матрицы игры к более удобному виду. Так, например, если элементы платежной матрицы представляют собой дроби с общим знаменателем, то каждый элемент матрицы a_ij можно умножить на некоторую константу, в результате чего элементы преобразованной матрицы будут представлять собой целые числа; если же большинство клеток матрицы заполнены одинаковыми элементами, то их можно вычесть из каждого элемента матрицы для получения нулей, которым будут равны соответствующие элементы матрицы. Кроме того, цену игры всегда можно сделать положительной.

Пример 3. Задана платёжная матрица игры:

A =

Необходимо упростить матрицу игры.

1 - ый шаг: умножим каждый из элементов матрицы A на k = 0.01, получим:

2 - ой шаг: к каждому элементу матрицы A' прибавим b = 4, получим матрицу:А=

Таким образом, мы получили платёжную матрицу с положительными элементами и небольшими по абсолютной величине. Работа с такой матрицей проще, чем с исходной матрицей. Элементы матрицы А получены преобразованием: a_ij^*= 0.01a_ij + 4.

Дата добавления: 2020-11-23; просмотров: 1173; Мы поможем в написании вашей работы!

Поделиться с друзьями:

12 3 4 Следующая ⇒

Мы поможем в написании ваших работ!