Методы решения биматричных игр
МЕТОДЫ РЕШЕНИЯ БИМАТРИЧНЫХ ИГР
1.
Основные определения теории биматричных игр
Рассмотрим конфликтную ситуацию, в которой каждый из двух
участников имеет следующие возможности для выбора своей линии поведения:
игрок А – может выбрать любую из стратегий А1,
... , Ат,
игрок В – любую из стратегий В1, …, Вn
При этом всякий раз их совместный выбор оценивается вполне определенно:
если игрок А выбрал i-ю
стратегию , а
игрок В – k-ю стратегию
, то в итоге
выигрыш игрока А будет равен некоторому числу , а выигрыш игрока В некоторому, вообще
говоря, другому числу .
Иными словами, всякий раз каждый из игроков получает свой приз.
Последовательно перебирая все стратегии игрока А и все
стратегии игрока В, мы сможем заполнить их выигрышами две таблицы
(первая из них описывает выигрыши игрока А, а вторая – выигрыши игрока В).
Обычно эти таблицы записывают в виде матриц
Здесь А – платежная матрица игрока А, а В – платежная
матрица игрока В.
При выборе игроком А i-й
стратегии, а игроком В – k-й
стратегии их выигрыши находятся в матрицах выплат на пересечении i-х строк и k-x столбцов: в матрице А это элемент , а в матрице В – элемент .
Таким образом, в случае, когда интересы игроков различны (но не
обязательно противоположны), получаются две платежные матрицы: одна – матрица
выплат игроку А, другая – матрица выплат игроку В.
Поэтому совершенно естественно звучит название, которое обычно
присваивается подобной игре – биматричная.
Замечание. Рассматриваемые матричные игры, можно
рассматривать и как биматричные, где матрица выплат игроку В противоположна
матрице выплат А:
В общем случае биматричная игра – это игра с ненулевой суммой.
Класс биматр. игр значительно шире класса матричных (разнообразие
новых моделируемых конфликтных ситуаций весьма заметно), а, значит, неизбежно
увеличиваются и трудности, встающие на пути их успешного разрешения.
Пример. «Студент — Преподаватель».
Рассмотрим следующую ситуацию. Студент (игрок А )
готовится к зачету, который принимает Преподаватель (игрок В).
Можно считать, что у Студента две стратегии – подготовиться к сдаче зачета
(+) и не подготовиться (-). У Преподавателя также две стратегии – поставить
зачет [+] и не поставить зачета [-].
В основу значений функций выигрыша игроков положим следующие соображения:
Количественно это можно выразить, например, так
2.
Смешанные стратегии в биматричных играх
В приведенных примерах описаны ситуации, в которых интересы
игроков не совпадают. Встает вопрос о том, какие рекомендации необходимо дать игрокам
для того, чтобы моделируемая конфликтная ситуация разрешилась. Иными словами,
что мы будем понимать под решением биматричной игры?
Попробуем ответить на это вопрос так:
вследствие того, что интересы игроков не совпадают, нам нужно
построить такое (компромиссное) решение, которое бы в том или ином, но в
одинаковом смысле удовлетворяло обоих игроков.
Не пытаясь сразу выражать эту мысль совсем точно, скажем –
попробуем найти некую равновесную ситуацию, явное отклонение от которой
одного из игроков уменьшало бы его выигрыш.
Подобный вопрос мы ставили и при рассмотрении матричных игр.
Напомним, что возникающее при разработке минимаксного подхода понятие
равновесной ситуации приводило нас к поиску седловой точки, которая, существует
не всегда – конечно, если ограничиваться только чистыми стратегиями игроков А
и В, т.е. стратегиями .
Однако при расширении матричной игры путем перехода к смешанным
стратегиям, т. е. к такому поведению игроков, при котором они чередуют (чистые)
стратегии с определенными частотами:
игрок А – стратегии A1,..., Ат с частотами р1,..., рт,
где
а игрок В – стратегии В1,....,
Вn, с
частотами q1,...,
qn, где
выяснилось, что в смешанных стратегиях равновесная ситуация всегда
существует. Иными словами, любая матричная игра в смешанных стратегиях разрешима.
Поэтому, рассматривая здесь биматричные игры, разумно попробовать
сразу же перейти к смешанным стратегиям игроков (этим мы предполагаем, что
каждая игра может быть многократно повторена в неизменных обстоятельствах).
В матричном случае смешивание стратегий приводило к расширению возможности
выплат в том смысле, что расчет строился из вычисления средних выигрышей
игроков А и В, которые определялись по элементам
платежной матрицы А и вероятностям и :
,
При смешанных стратегиях в биматричных играх также возникают
средние выигрыши игроков А и В, определяемые по
правилам, в которых уже нет никакой дискриминации игрока В:
,
3.
2x2 биматричные игры. Ситуация равновесия
Мы предполагаем уделить основное внимание случаю, когда у каждого
из игроков имеется ровно две стратегии, т. е. случаю т = п = 2. Поэтому
нам кажется уместным выписать приведенные выше формулы именно для такого
случая.
В 2 ´ 2
биматричной игре платежные матрицы игроков имеют следующий вид
, ,
вероятности
биматричная игра
решение
а средние выигрыши вычисляются по формулам
где
,
Сформулируем основное определение.
Определение. Будем считать, что пара
чисел
, ,
определяет равновесную ситуацию, если для любых р и q, подчиненных условиям одновременно выполнены следующие неравенства
(1)
Пояснение. Выписанные неравенства (1) означают
следующее: ситуация, определяемая смешанной стратегией (р*, q*), является равновесной, если отклонение от нее одного
из игроков при условии, что другой сохраняет свой выбор, приводит к тому, что
выигрыш отклонившегося игрока может только уменьшиться. Тем самым, получается,
что если равновесная ситуация существует, то отклонение от нее невыгодно самому
игроку.
Теорема 1 (Дж. Нэш). Всякая биматричная игра
имеет хотя бы одну равновесную ситуацию (точку равновесия) в смешанных
стратегиях.
Итак, равновесная ситуация существует. Но как ее найти?
Если некоторая пара чисел (р*, q*) претендует
на то, чтобы определять ситуацию равновесия, то для того, чтобы убедиться в
обоснованности этих претензий, или, наоборот, доказать их необоснованность,
необходимо проверить справедливость неравенств (1) для любого р в
пределах от 0 до 1 и для любого q в пределах от 0 до 1. В общем случае число таких проверок
бесконечно. И, следовательно, действенный способ определения равновесной
ситуации нужно искать где-то в ином месте.
Теорема 2. Выполнение неравенств
(1)
равносильно выполнению неравенств
Иными словами, для того, чтобы убедиться в обоснованности
претензий пары (р*, q*) на
то, чтобы определять равновесную ситуацию, нужно проверить справедливость
неравенства
только для двух чистых стратегий игрока А (р = 0 и
р = 1) и неравенства
только для двух чистых стратегий игрока В (q = 0 и q=
1).
Четыре неравенства (2) позволяют провести поиск точки равновесия
вполне конструктивно.
Запишем средние выигрыши игроков А и В
в более удобной форме.
Имеем
Обратимся к первой из полученных формул.
Полагая в ней сначала р = 1, а потом р = 0,
получаем,
Рассмотрим разности
Полагая
получим для них следующие выражения
В случае, если пара (р, q) определяет
точку равновесия, эти разности неотрицательны
Поэтому окончательно получаем
Из формул для функции нв
( р, q) при q = 1 и q = 0
соответственно имеем
Разности
и
с учетом обозначений
.
приводятся к виду
совершенно так же, как соответствующие разности для функции НА.
Если пара (р, q) определяет
точку равновесия, то эти разности неотрицательны
Поэтому
Вывод
Для того, чтобы в биматричной игре
, ,
пара (р, q) определяла
равновесную ситуацию, необходимо и достаточно одновременное выполнение
следующих неравенств
, ,
, ,
где
.