2.4. МАЖОРИРОВАНИЕ (ДОМИНИРОВАНИЕ) СТРАТЕГИЙ
Мажорирование представляет отношение между стратегиями, наличие которого во многих практических случаях дает возможность сократить размеры исходной платежной матрицы игры. Рассмотрим это понятие на примере матрицы
Рассуждая с позиции игрока 2, можно обнаружить преимущество его третьей стратегии перед второй, поскольку при первой стратегии игрока 1 выигрыш игрока 2 равен —3 (вторая стратегия) и 1 (третья стратегия), а при второй стратегии игрока 1 выигрыш игрока 2 равен —2 (вторая стратегия) и - 0,5 (третья стратегия). Таким образом, при любой стратегии игрока 1 игроку 2 выгоднее применять свою третью стратегию по сравнению со второй; при наличии третьей стратегии игрок 2, если он стремится играть оптимально, никогда не будет использовать свою вторую стратегию, поэтому ее можно исключить из игры, т.е. в исходной платежной матрице можно вычеркнуть 2-й столбец:
С позиции игрока 1 его первая стратегия оказывается хуже второй, так как по первой стратегии он только проигрывает. Поэтому первую стратегию можно исключить, а матрицу игры преобразовать к виду:
(0 0,5).
Учитывая интересы игрока 2, следует оставить только его первую стратегию, поскольку, выбирая вторую стратегию, игрок 2 оказывается в проигрыше (0,5 - выигрыш игрока 1), и матрица игры принимает простейший вид: (0), т.е. имеется седловая точка.
Мажорирование можно распространить и на смешанные стратегии. Если элементы одной строки не все меньше (или равны) соответствующих элементов других строк, но все меньше (или равны) некоторых выпуклых линейных комбинаций соответствующих элементов других строк, то эту стратегию можно исключить, заменив ее смешанной стратегией с соответствующими частотами использования чистых стратегий.
В качестве иллюстрации к сказанному рассмотрим матрицу игры:
Для первых двух чистых стратегий игрока 1 возьмем частоты их применения (вероятности) равными 0,25 и 0,75.
Третья стратегия игрока 1 мажорируется линейной выпуклой комбинацией первой и второй чистых стратегий, взятых с частотами 0,25 и 0,75 соответственно, т.е. смешанной стратегией:
24*0,25 + 0*0,75 = 6 > 4;
0*0,25 + 8*0,75 = 6 > 5.
Поэтому третью стратегию игрока 1 можно исключить, используя вместо нее указанную выше смешанную стратегию.
Аналогично если каждый элемент некоторого столбца больше или равен некоторой выпуклой линейной комбинации соответствующих элементов некоторых других столбцов, то этот столбец можно исключить из рассмотрения (вычеркнуть из матрицы). Например, для матрицы
третья стратегия игрока 2 мажорируется смешанной стратегией из первой и второй его чистых стратегий, взятых с частотами 0,5 и 0,5:
10*0,5 + 0*0,5 = 5 < 6;
0*0,5 + 10*0,5 = 5 < 7.
Таким образом, исходная матрица игры эквивалентна матрице следующего вида:
Как видно, возможности мажорирования смешанными стратегиями в отличие от чистых значительно менее прозрачны (нужно должным образом подобрать частоты применения чистых стратегий), но такие возможности есть, и ими полезно уметь пользоваться.
Задачи для самостоятельного решения
Задача 2.2. Найдите седловые точки следующих платежных матриц:
Задача 2.3. Найдите  для платежной матрицы:
Задача 2.4. Решите аналитически и графически, используя понятие доминирования, игры, определяемые следующими платежными матрицами:
Задача 2.5. Постройте платежную матрицу двухпальцевой игры Морра, которая заключается в следующем. В игру играют два человека: каждый из них показывает один или два пальца и одновременно называет число пальцев, которое, по его мнению, покажет его противник (естественно, противник этого не видит). Если один из игроков угадывает правильно, он выигрывает сумму, равную сумме пальцев, показанных им и его противником. В противном случае - ничья (выигрыш равен нулю).
Найдите нижнюю и верхнюю цены игры.
Задача 2.6. Используя понятие доминирования, уменьшите размеры следующей платежной матрицы:
Для задач 2.7-2.12 постройте платежную матрицу игры и сформулируйте соответствующую модель линейного программирования.
Задача 2.7. Пусть сторона А засылает подводную лодку в один из п районов. Сторона В, располагая т противолодочными кораблями, желает обнаружить лодку противника. Вероятность обнаружения лодки в j-м районе (j = 1,...,п) равна pj. Предполагается, что обнаружение подлодки каждым кораблем является независимым событием. Сторона В может посылать в различные регионы разное количество кораблей (распределение т кораблей по регионам и есть стратегии стороны В). Сторона В стремится максимизировать вероятность обнаружения подлодки. Сторона А желает противоположного.
Вероятность обнаружения лодки в районе j, в котором находится rij кораблей (i - номер стратегии), равна:
причем  . Найдите оптимальное распределение противолодочных кораблей по регионам.
Рассмотреть частный случай: m = 2, п = 2, р1 = 0,6, р2 = 0,4.
Задача 2.8. Каждому из игроков выдается по бубновому и трефовому тузу. Игрок 1 получает также бубновую двойку, а игрок 2 - трефовую. При первом ходе игрок 1 выбирает и откладывает одну из своих карт, а игрок 2, не зная карты, выбранной игроком 1, также откладывает одну из своих карт. Если были отложены карты одной масти, то выигрывает игрок 1, в противном случае выигравшим считается игрок 2. Если отложены две двойки, выигрыш равен нулю. Размер выигрыша определяется картой, отложенной победителем (тузу приписывается одно очко, двойке - два).
Задача 2.9. Фирма изготавливает железобетонные панели, используя в качестве основного сырья цемент. В связи с неопределенным спросом на изделия потребность в сырье в течение месяца также не определена. Цемент поставляется в мешках, причем известно, что потребность может составлять D1,D2,...,Dn мешков. Резервы сырья на складе могут составлять R1,R2,...,Rn мешков в месяц. Учитывая, что удельные затраты на хранение сырья равны с1 а удельные издержки дефицитности сырья (потери, связанные с отсутствием необходимого количества цемента на складе) равны с2, определить оптимальную стратегию управления запасами цемента на складе.
Рассмотреть частный случаи: п = 5, c1 = 5, c2 = 3;
D = (1 500, 2 000, 2 500, 3 500, 4 000), R =(1 500, 2 000, 2 500, 3 500, 4 000).
Задача 2.10. Игрок 2 прячет некоторый ценный предмет в одном из п мест, а игрок 1 этот предмет ищет. Если он его находит, то получает сумму аi где i = 1,2, ..., п, в противном случае - не получает ничего.
Задача 2.11. Два игрока независимо друг от друга называют по одному числу из диапазона 1 - 5. Если сумма чисел нечетная, то игрок 2 платит игроку 1 сумму, равную максимальному из чисел; если четная, то платит игрок 1.
Задача 2.12. Два игрока имеют по п рублей и предмет ценой с > 0. Каждый игрок делает заявку в запечатанном конверте, предлагая i руб. (где i - одно из целых чисел от 0 до п) за предмет. Записавший большее число получает предмет и платит другому предложенную им сумму. Если оба игрока заявляют одинаковую сумму, то предмет назначается без компенсирующего одностороннего платежа одному из игроков путем бросания монеты, так что ожидаемая доля каждого в предмете составляет в этом случае половину с. Постройте платежную матрицу игры и определите, имеет ли игра седловую точку.
|
