Биматричные игры и их решение

Размещено на http://www.allbest.ru/

Введение

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

Для решения такого рода задач используется математическое моделирование. Введём несколько основных понятий. Математическая модель конфликтной игрой называется игрой. Стороны конфликта - игроки, действие игрока - ход, совокупность ходов - стратегия, результат игры - выигрыш.

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

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



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

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

игрок А - может выбрать любую из стратегий А1, ... , Ат,

игрок В - любую из стратегий В1, …, Вn

При этом всякий раз их совместный выбор оценивается вполне определенно:

если игрок А выбрал i-ю стратегию , а игрок В - k-ю стратегию , то в итоге выигрыш игрока А будет равен некоторому числу , а выигрыш игрока В некоторому, вообще говоря, другому числу .

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

Последовательно перебирая все стратегии игрока А и все стратегии игрока В, мы сможем заполнить их выигрышами две таблицы (первая из них описывает выигрыши игрока А, а вторая - выигрыши игрока В).

Обычно эти таблицы записывают в виде матриц

Здесь А - платежная матрица игрока А, а В - платежная матрица игрока В.

При выборе игроком А i-й стратегии, а игроком В - k-й стратегии их выигрыши находятся в матрицах выплат на пересечении i-х строк и k-x столбцов: в матрице А это элемент , а в матрице В - элемент .

Таким образом, в случае, когда интересы игроков различны (но не обязательно противоположны), получаются две платежные матрицы: одна - матрица выплат игроку А, другая - матрица выплат игроку В. Поэтому совершенно естественно звучит название, которое обычно присваивается подобной игре - биматричная.

Замечание. Рассматриваемые матричные игры, можно рассматривать и как биматричные, где матрица выплат игроку В противоположна матрице выплат А:

В общем случае биматричная игра - это игра с ненулевой суммой.

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

Общий принцип решения биматричных игр

В первое неравенство системы последовательно подставляются все чистые стратегии игрока А, при предположении, что В придерживается своей оптимальной стратегии. Во второе неравенство подставляются все чистые стратегии игрока В, при предположении, что А придерживается своей оптимальной стратегии.

Полученная система m+n неравенств, решение которой дает значение элементов оптимальных смешанных стратегий (P*,Q*) и платежи, получаемые игроками в точке равновесия.

Пример: борьба за рынок.

А=

В=

Решение задачи

vA=-10?1q1+2?1*(1-q1)+(1-p1)q1-(1-p1)(1-q1)=-14?1q1+3?1+2q1-1

vB=5?1q1-2?1*(1-q1)-(1-p1)q1 +(1-p1)(1-q1)=9?1q1-3?1-2q1+1

Пусть

p1=1 тогда vA=2-12q1 -14?1q1+3?1+2q1-1

p1=0 тогда vA=-1+2q1 -14?1q1+3?1+2q1-1

q1=1тогда vB=-1+6?1 9?1q1-3?1-2q1+1

q1=0 тогда vB=1-3?1 9?1q1-3?1-2q1+1

Cоставляем 4 системы, преобразовываем, получаем:

(p1-1)(-14q1+3) 0

p1 (-14q1+3) 0

(q1-1)(9?1-2) 0

q1 (9?1-2) 0

p1=0 следовательно -(-14q1+3) 0 q1 3/14

p1=1 следовательно (-14q1+3)>=0 q1 3/14

0<p1<1 следовательно -(-14q1+3) 0 и (-14q1+3) 0->q1=3/14

q1=0 следовательно p1 2/9

q1=1 следовательно p1 2/9

0<q1< 0-p1=2/9

Строим график по всем p и всем q, получается на пересечении точка

p1=2/9, q1=3/14

- решение системы неравенств.

P(2/9;7/9), Q(3/14;11/14)

vA=4/7, vB=1/3

Вывод: 2/9 товара предлагать на первом рынке и 7/9 на втором рынке и тогда минимальный проигрыш -- 4/7. 3/14 -защищать 1-й рынок, 11/14-защищать второй рынок.

Примеры решения биматричных игр

Пример 1. «Студент -- Преподаватель».

Рассмотрим следующую ситуацию. Студент (игрок А ) готовится к зачету, который принимает Преподаватель (игрок В). Можно считать, что у Студента две стратегии - подготовиться к сдаче зачета (+) и не подготовиться (-). У Преподавателя также две стратегии - поставить зачет [+] и не поставить зачета [-].

В основу значений функций выигрыша игроков положим следующие соображения:



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

Пример 2. Рассмотрим парную игру, в которой каждый из участников имеет следующие возможности для выбора своей линии поведения:

игрок А - может выбрать любую из стратегий А1, …, Аm;

игрок В - любую из стратегий В1, …, Вn;

Если игрок А выбрал стратегию Аi, игрок В - Вj, то в итоге выигрыш игрока А составит аij, игрока В - bij. Выигрыши игроков А и В можно записать в виде двух таблиц.

А=

В=

Таким образом, если интересы игроков различны, но не обязательно противоположны, для описания игры используются две платёжные матрицы. Данный факт и дал название подобным играм - биматричным.

Смешанные стратегии в биматричных играх

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

Можно ответить на это вопрос так:

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

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

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

.

Однако при расширении матричной игры путем перехода к смешанным стратегиям, т. е. к такому поведению игроков, при котором они чередуют (чистые) стратегии с определенными частотами:

игрок А - стратегии A1,..., Ат с частотами р1,..., рт, где



а игрок В - стратегии В1,...., Вn, с частотами q1,..., qn, где

выяснилось, что в смешанных стратегиях равновесная ситуация всегда существует. Иными словами, любая матричная игра в смешанных стратегиях разрешима.

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

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

,

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

,



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

, ,

, ,

где

.

Размещено на Allbest.ru