Теория игр

Задача, которая обычно ставится в этом случае, состоит  не в поиске оптимального решения, а  в поиске хотя бы выигрышной стратегии. Используя аксиому выбора, можно доказать, что иногда даже для игр с полной информацией и двумя исходами — «выиграл» или «проиграл» — ни один из игроков не имеет такой стратегии. Существование выигрышных стратегий для некоторых особенным образом сконструированных игр имеет важную роль в дескриптивной теории множеств.

Дискретные и непрерывные игры

Дифференциальные игры

Большинство изучаемых  игр дискретны: в них конечное число игроков, ходов, событий, исходов и т. п. Однако эти составляющие могут быть расширены на множество вещественных чисел. Игры, включающие такие элементы, часто называются дифференциальными. Они связаны с какой-то вещественной шкалой (обычно — шкалой времени), хотя происходящие в них события могут быть дискретными по природе. Дифференциальные игры также рассматриваются в теории оптимизации, находят своё применение в технике и технологиях, физике.

Метаигры

Это такие игры, результатом  которых является набор правил для другой игры (называемой целевой или игрой-объектом). Цель метаигр — увеличить полезность выдаваемого набора правил. Теория метаигр связана с теорией оптимальных механизмов (англ.).

 

ОПРЕДЕЛЕНИЕ МАТРИЧНОЙ ИГРЫ

Описание игры включает перечень участников конфликта, задание  множеств возможных действий и оценок эффективности этих действий для  каждого из них. Участников конфликта принято называть игроками. Обозначим множество всех игроков через . Далее будем считать множество N конечным. Игроков принято различать по их номерам, т. е. считать ={1,2, ..., n}. Множество возможных действий i-го игрока обозначим через . Элементы этого множества принято называть стратегиями. Каждый игрок имеет не менее двух различных стратегий, в противном случае его действия заранее определены и фактически он не участвует в игре. В результате выбора i-м игроком стратегии  складывается система стратегий , которая называется ситуацией. Эффективность возможных действий игроков мы будем оценивать теми выигрышами, которые игроки получают в каждой ситуации s. Выигрыш игрока i в ситуации s обычно обозначается через . Функция , определенная на множестве всех ситуаций, называется функцией выигрыша игрока i. Цель i-го игрока — максимизация своей функции выигрыша.

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

.                             (17.1)

Игра (17.1) называется антагонистической, если в ней участвуют два игрока и значения функций выигрыша в каждой ситуации равны по величине и противоположны по знаку.

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

Г = <А, В, Н>,                                              (17.2)

где А и В — соответственно множества стратегий игроков I и II, а Н — функция выигрыша игрока I.

Конечная антагонистическая  игра в нормальной форме называется матричной игрой.

Это название можно объяснить следующей возможностью описания игр такого рода. Поскольку множество возможных действий каждого из игроков в этом случае конечно, можно положить А = {1, 2, ..., m}, В = {1, 2,..., n}, где m и n — соответственно число стратегий игроков I и II, а значения функции Н представить в виде следующей матрицы:

      

 Здесь —выигрыш игрока I в ситуации (i, j), где i — номер строки (стратегия игрока I), j — номер столбца (стратегия игрока II). Матрица Н называется матрицей игры или матрицей выигрышей.

Матричная игра полностью определяется своей матрицей выигрышей. Поэтому часто вместо выражения “игра с матрицей выигрышей Н” употребляется выражение “игра Н”.

Преимущество представления  игры в виде матрицы заключается  в хорошей наглядности. Матричные  игры являются самыми простыми из класса антагонистических игр. 

 

 

РЕШЕНИЕ  МАТРИЧНЫХ  ИГР  В  ЧИСТЫХ  СТРАТЕГИЯХ.

Матричная игра двух игроков с нулевой  суммой может рассматриваться как  следующая абстрактная игра двух игроков.

Первый игрок имеет  m  стратегий  i = 1,2,...,m, второй имеет  n  стратегий  j = 1,2,...,n. Каждой паре стратегий  (i,j)  поставлено в соответствие число аij, выражающее выигрыш игрока 1 за счёт игрока 2, если первый игрок примет свою i-ю стратегию, а 2 – свою j-ю стратегию.

Каждый из игроков делает один ход: игрок 1 выбирает свою i-ю стратегию (i=

), 2 – свою j-ю стратегию (j= ), после чего игрок 1 получает выигрыш аij за счёт игрока 2 (если аij< 0, то это значит, что игрок 1 платит второму сумму  | аij | ). На этом игра заканчивается.

Каждая стратегия игрока  i=

;  j =  часто называется чистой стратегией.

Если рассмотреть матрицу

А =

 

 

то проведение каждой партии матричной  игры с матрицей  А  сводится к выбору игроком 1  i-й строки, а игроком 2  j-го столбца и получения игроком 1 (за счёт игрока 2) выигрыша  аij.

Главным в исследовании игр является понятие оптимальных стратегий  игроков. В это понятие интуитивно вкладывается такой смысл: стратегия  игрока является оптимальной, если применение этой стратегии обеспечивает ему наибольший гарантированный выигрыш при всевозможных стратегиях другого игрока. Исходя из этих позиций, игрок 1 исследует матрицу выигрышей  А следующим образом: для каждого значения  i  (i =

) определяется минимальное значение выигрыша в зависимости от применяемых стратегий игрока 2

аij          (i = )

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

аij = =                                         (1).

Определение. Число

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

Игрок 2 при оптимальном своём  поведении должен стремится по возможности  за счёт своих стратегий максимально уменьшить выигрыш игрока 1. Поэтому для игрока 2 отыскивается

аij

т.е. определяется max выигрыш игрока 1, при условии, что игрок 2 применит свою j-ю чистую стратегию, затем игрок 2 отыскивает такую свою j = j1 стратегию, при которой игрок 1 получит min выигрыш, т.е. находит

aij = =                                            (2).

Определение. Число

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

Другими словами, применяя свои чистые стратегии игрок 1 может обеспечить себе выигрыш не меньше

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

Определение. Если в игре с матрицей А 

= , то говорят, что эта игра имеет седловую точку в чистых стратегиях и чистую цену игры

u =

= .

Седловая точка – это пара чистых стратегий  (iо,jо)  соответственно игроков 1 и 2, при которых достигается равенство 

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

                                     

где i, j – любые чистые стратегии соответственно игроков 1 и 2; (iо,jо) – стратегии, образующие седловую точку.

Таким образом, исходя из (3), седловой элемент 

  является минимальным в iо-й строке и максимальным в jо-м столбце в матрице А. Отыскание седловой точки матрицы А происходит следующим образом: в матрице А последовательно в каждой строке находят минимальный элемент и проверяют, является ли этот элемент максимальным в своём столбце. Если да, то он и есть седловой элемент, а пара стратегий, ему соответствующая, образует седловую точку. Пара чистых стратегий (iо,jо) игроков 1 и 2, образующая седловую точку и седловой элемент  , называется решением игры. При этом  iо и jо  называются оптимальными чистыми стратегиямисоответственно игроков 1 и 2.

Пример 1

Седловой точкой является пара  (iо = 3; jо = 1), при которой  u =

=  = 2.

Заметим, что хотя выигрыш в ситуации (3;3) также равен  2 =

= , она не является седловой точкой, т.к. этот выигрыш не является максимальным среди выигрышей третьего столбца.

Пример 2 

 

Из анализа матрицы выигрышей  видно, что 

, т.е. данная матрица не имеет седловой точки. Если игрок 1 выбирает свою чистую максиминную стратегию  i = 2, то игрок 2, выбрав свою минимаксную  j = 2, проиграет только 20. В этом случае игроку 1 выгодно выбрать стратегию  i = 1, т.е. отклониться от своей чистой максиминной стратегии и выиграть 30. Тогда игроку 2 будет выгодно выбрать стратегию  j = 1, т.е. отклониться от своей чистой минимаксной стратегии и проиграть 10. В свою очередь игрок 1 должен выбрать свою 2-ю стратегию, чтобы выиграть 40, а игрок 2 ответит выбором 2-й стратегии и т.д.

 

ГРАФИЧЕСКИЙ  МЕТОД  РЕШЕНИЯ ИГР  2 x n  И  m x 2.

Поясним метод на примераx.

Пример 1.

Рассмотрим игру, заданную платёжной  матрицей.

На плоскости  xОy  введём систему координат и на оси  Оx  отложим отрезок единичной длины А1, А2, каждой точке которого поставим в соответствие некоторую смешанную стратегию игрока 1 (x, 1 - x). В частности, точке А1 (0;0) отвечает стратегия А1, точке А2 (1;0) – стратегия А2 и т.д.

 

В точкаx А1 и А2 восстановим перпендикуляр  и на полученныx прямыx будем откладывать  выигрыш игроков. На первом перпендикуляре (в данном случае он совпадает с осью 0y) отложим выигрыш игрока 1 при стратегии  А1, а на втором – при стратегии А2. Если игрок 1 применит стратегию А1, то выиграет при стратегии В1 игрока 2 – 2, при стратегии В2 – 3, а при стратегии В3 – 11. Числам 2, 3, 11 на оси 0x соответствуют точки В1, В2 и В3.

Если же игрок 1 применит стратегию  А2, то его выигрыш при стратегии  В1 равен 7, при В2 – 5, а при В3 – 2. Эти числа определяют точки  В'1, В2', В3' на перпендикуляре, восстановленном  в точке А2.Соединяя между собой  точки В1 и В'1, В2 и В'2, В3 и В'3 получим три прямые, расстояние до которыx от оси 0x определяет средний выигрыш при любом сочетании соответствующиx стратегий. Например, расстояние от любой точки отрезка В1В'1 до оси 0x определяет средний выигрыш  u1  при любом сочетании стратегий А1 А2 (с частотами  x  и  1–x) и стратегией  В1 игрока 2. Это расстояние равно

2x1 + 6(1 - x2) = u1

(Вспомните планиметрию и рассмотрите  трапецию А1 B1 B'1 A2). Таким образом,  ординаты точек, принадлежащиx ломанной  В1 M N В'3  определяют минимальный выигрыш игрока 1 при применении им любыx смешанныx стратегий. Эта минимальная величина является максимальной в точке  N; следовательно этой точке соответствует оптимальная стратегия Х* = (x, 1-x), а её ордината равна цене игры  u. Координаты точки N наxодим как точку пересечения прямыx В2 B'2  и  В3 B'3.

Соответствующие два уравнения  имеют вид

.

Следовательно Х = (

; ), при цене игры  u = . Таким образом мы можем найти оптимальную стратегию при помощи матрицы

Оптимальные стратегии для игрока 2 можно найти из системы

и, следовательно, Y = (0;

; ). (Из рисунка видно, что стратегия B1 не войдёт в оптимальную стратегию. 

 

Пример 2. Найти решение игры, заданной матрицей

 

Решение. Матрица имеет размерность  2 x 4. Строим прямые, соответствующие стратегиям игрока 1. Ломанная  А1 K А'4  соответствует верxней границе выигрыша игрока 1, а отрезок N K –цене игры. Решение игры таково

U = (

; );     Х = ( ; 0; 0; );    u = .

 

Список литературы

1. Игры с непротивоположными интересами. Гермейер Ю.Б., Главная редакция физико-математической литературы издательства «Наука»,1976.

2. теория игр: Учебное пособие/Н.В. Мурзов, А.В.Дубовиков, Рязанская государственная радиотехническая академия, Рязань, 2001.

3. Решение матричных и кооперативных игр на ЭВМ: Учебное пособие И.А. Цветков; Рязанская государственная радиотехническая академия, Рязань,2000.

4. Краткий курс теории игр для спецализированных школ с математическим уклоном/В.Н. Лагунов, Тверь,1994