Рефетека.ру / Математика

Реферат: Методы решения биматричных игр


МЕТОДЫ РЕШЕНИЯ БИМАТРИЧНЫХ ИГР


Основные определения теории биматричных игр


Рассмотрим конфликтную ситуацию, в которой каждый из двух участников имеет следующие возможности для выбора своей линии поведения:

игрок А – может выбрать любую из стратегий А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) определяла равновесную ситуацию, необходимо и достаточно одновременное выполнение следующих неравенств


Методы решения биматричных игр, Методы решения биматричных игр,


Методы решения биматричных игр, Методы решения биматричных игр,

где

Методы решения биматричных игр Методы решения биматричных игр


Методы решения биматричных игр Методы решения биматричных игр.


Рефетека ру refoteka@gmail.com