МЕТОДЫ РЕШЕНИЯ БИМАТРИЧНЫХ ИГР
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)
равносильно выполнению неравенств
/>/>
/>/> (2)
Иными словами, для того, чтобы убедиться в обоснованностипретензий пары (р*, q*) нато, чтобы определять равновесную ситуацию, нужно проверить справедливостьнеравенства
/>
только для двух чистых стратегий игрока А(р = 0 ир = 1) и неравенства
/>
только для двух чистых стратегий игрока В (q= 0 иq=1).
Четыре неравенства (2) позволяют провести поиск точки равновесиявполне конструктивно.
Запишем средние выигрыши игроков Аи Вв более удобной форме.
Имеем
/>
Обратимся к первой из полученных формул.
Полагая в ней сначала р = 1, а потом р = 0,получаем,
/>
Рассмотрим разности
/>
/>
Полагая
/> />
получим для них следующие выражения
/>
/>
В случае, если пара (р, q) определяетточку равновесия, эти разности неотрицательны
/> />
Поэтому окончательно получаем
/>
Из формул для функции нв( р, q) при q= 1 и q= 0соответственно имеем
/>
Разности
/> и
с учетом обозначений
/> />.
приводятся к виду
/>
/>
совершенно так же, как соответствующие разности для функции НА.
Если пара (р, q) определяетточку равновесия, то эти разности неотрицательны
/> />
Поэтому
/>
Вывод
Для того, чтобы в биматричной игре
/>, />,
пара (р, q) определяларавновесную ситуацию, необходимо и достаточно одновременное выполнениеследующих неравенств
/>, />,
/>, />,
где
/> />
/> />.