Элементы теории игр

Предмет и метод теории игр

Классификация игр

Матричные игры

·      Решение матричных игр в чистых стратегиях

·      Смешанное расширение матричной игры

 

 

Предмет и метод теории игр

Игра — это математическая модель конфликтной ситуации, которая предполагает наличие следующих компонентов:

а) заинтересованных сторон;

б) возможных действий каждой из сторон;

в) интересов сторон.

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

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

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

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

Для игр характерна неопределенность результата (исхода).

Причины неопределенности относятся к трем группам:

1)комбинаторные источники (шахматы);

2)влияние случайных факторов (игра в орлянку, кости, карточные игры, где случаен расклад);

3) стратегическое происхождение: игрок не знает, какого образа действий придерживается его противник. Здесь неопределенность исходит от другого лица.

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

Таким образом, в стратегической игре действия предпринимают две стороны или более, в отличие от нестратегической игры, в которой действия предпринимает одна сторона, а остальные являются заинтересованными сторонами.

Классификация игр

Классификацию игр можно проводить:

по количеству игроков,

количеству стратегий,

характеру взаимодействия игроков,

характеру выигрыша,

количеству ходов,

состоянию информации

и т.д.

 

В зависимости от количества игроков различают игры двух и n игроков. Первые из них наиболее изучены. Игры трёх и более игроков менее исследованы из-за возникающих принципиальных трудностей и технических возможностей получения решения. Чем больше игроков - тем больше проблем.

По количеству стратегий игры делятся на конечные и бесконечные. Если в игре все игроки имеют конечное число возможных стратегий, то она называется конечной. Если же хотя бы один из игроков имеет бесконечное количество возможных стратегий игра называется бесконечной.

По характеру взаимодействия игры делятся на:

1)бескоалиционные: игроки не имеют права вступать в соглашения, образовывать коалиции;

2)коалиционные (кооперативные) – могут вступать в коалиции.

В кооперативных играх коалиции наперёд определены.

По характеру выигрышей игры делятся на: игры с нулевой суммой (общий капитал всех игроков не меняется, а перераспределяется между игроками; сумма выигрышей всех игроков равна нулю) и игры с ненулевой суммой.

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

Матричная игра - это конечная игра двух игроков с нулевой суммой, в которой задаётся выигрыш  игрока 1 в виде матрицы (строка матрицы соответствует номеру применяемой стратегии игрока 1, столбец - номеру применяемой стратегии игрока 2; на пересечении строки и столбца матрицы находится выигрыш игрока 1, соответствующий применяемым стратегиям).

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

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

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

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

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

Матричные игры 

Решение матричных игр в чистых стратегиях

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

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

Каждый из игроков делает один ход: игрок 1 выбирает свою i-ю стратегию , 2 - свою j-ю стратегию , после чего игрок 1 получает выигрыш а_ij за счёт игрока 2 (если а_ij< 0, то это значит, что игрок 1 платит второму сумму |а_ij |). На этом игра заканчивается.

Каждая стратегия игрока ; часто называется чистой стратегией.

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

 

 

 

 

 

 

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

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

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

 

                                                       (1)

 

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

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

 

Поэтому для игрока 2 отыскивается

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

 

                                             (2)

 

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

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

 

! Определение.  Если в игре с матрицей А V₁=V₂ , то говорят, что эта игра имеет седловую точку в чистых стратегиях и чистую цену игры

V = V₁=V₂.

Седловая точка - это пара чистых стратегий (i_о,j_о) соответственно игроков 1 и 2, при которых достигается равенство V₁=V₂ . В это понятие вложен следующий смысл: если один из игроков придерживается стратегии, соответствующей седловой точке, то другой игрок не сможет поступить лучше, чем придерживаться стратегии, соответствующей седловой точке.

Математически это можно записать и иначе:

 

                                                     (3)

 

Таким образом, исходя из (3), седловой элемент  является минимальным в i_о-й строке и максимальным в j_о-м столбце в матрице А. Отыскание седловой точки матрицы А происходит следующим образом: в матрице А последовательно в каждой строке находят минимальный элемент и проверяют, является ли этот элемент максимальным в своём столбце. Если да, то он и есть седловой элемент, а пара стратегий, ему соответствующая, образует седловую точку.

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

Пример

Дана матрица выигрышей

 

Наибольший выигрыш для игрока 1 (8) дает вторая стратегия i=2. Однако, если игрок 1 сделает такой ход, в ответ игрок 2 выберет стратегию j=2, и  выигрыш составит всего 6.

Очевидно, что исходя из ПРИНЦИПА ОСТОРОЖНОСТИ (основной принцип теории игр), надо выбрать ту стратегию, при которой НАШ МИНИМАЛЬНЫЙ ВЫИГРЫШ  БУДЕТ МАКСИМАЛЬНЫМ. Это так называемый "ПРИНЦИП МИНИМАКСА":

ПОСТУПАЙ ТАК, ЧТОБЫ ПРИ НАИХУДШЕМ ДЛЯ ТЕБЯ ПОВЕДЕНИИ  ПРОТИВНИКА ПОЛУЧИТЬ МАКСИМАЛЬНЫЙ ВЫИГРЫШ.

Добавим в таблицу столбец, в котором запишем минимальное значение в каждой строке, и выберем из этих минимальных значений максимальное. Это определит стратегию  игрока1 – i₀=2

 

 

Следовательно, нижняя чистая цена игры V1=6

Добавим в таблицу строку, в которой запишем максимальное значение в каждом столбце, и выберем из этих максимальных значений минимальное. Это определит стратегию  игрока2 – j₀=2. Верхняя чистая цена игры V2=6. V1=V2=V=6.

Игра имеет седловую точку a₂₂ =V=6. Следовательно, игра имеет решение в чистых оптимальных решениях. На этом решение игры закончено.

 

Смешанное расширение матричной игры

 

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

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

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

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

Рассмотрим модель смешанных стратегий.

! Определение. Смешанной стратегией игрока называется полный набор вероятностей применения его чистых стратегий.

Будем обозначать смешанные стратегии (набор чисел) игроков A и B соответственно:  

 P = (p₁, p₂, …, p_m) ; Q = (q₁, q₂, …, q_n)

 где p_i вероятность применения игроком A i-й стратегии  A_i,  q_{j –} вероятность применения игроком B своей j-й стратегии B_j

p_i ³ 0     (i = 1,m),

Аналогично для игрока 2, который имеет n чистых стратегий

q_j ³ 0,   (j = 1,n),

Если при решении задачи оптимизации получается, что пара каких либо вероятностей равна единице - p_m = 1 и q_n = 1 (остальные равны нулю), то игра имеет решение в чистых стратегиях: (A_m ; B_n ). Такая тактика (правда, обычно безо всяких математических обоснований) часто применяется в карточных играх.

В теории игр на этот счет существует одна  из  основных теорем:

ЛЮБАЯ КОНЕЧНАЯ ИГРА ДВУХ СТОРОН С НУЛЕВОЙ СУММОЙ ИМЕЕТ ПО КРАЙНЕЙ МЕРЕ ОДНО РЕШЕНИЕ – ПАРУ ОПТИМАЛЬНЫХ СТРАТЕГИЙ, В ОБЩЕМ СЛУЧАЕ СМЕШАННЫХ –(i_o; j_o) И СООТВЕТСТВУЮЩУЮ ЦЕНУ (V)

Оптимальные стратегии обладают следующим свойством: 

ЕСЛИ ОДНА ИЗ СТОРОН ПРИДЕРЖИВАЕТСЯ СВОЕЙ ОПТИМАЛЬНОЙ СТРАТЕГИИ, ТО ДРУГОЙ СТОРОНЕ НЕ МОЖЕТ БЫТЬ ВЫГОДНО ОТСТУПАТЬ ОТ СВОЕЙ.

Пример

 Пусть предприятие ожидает поступления одного из двух взаимоисключающих крупных заказов Z1 и Z2, требующих выполнения токарных и слесарных работ. По данным расчётов при поступлении заказа Z1 максимальный объём затрат труда по токарным работам составит 600 чел.-дней, а максимальный объём затрат труда слесарей составит 1900 чел.-дней. Аналогичные показатели при поступлении заказа Z2 равны 1000 и 625 чел.-дней соответственно.

Согласно договорам заказчики возмещают затраты предприятия из расчёта 48 ден.ед. за 1 чел.-день токарных работ и 16 ден.ед. за 1 чел.-день слесарных работ. Затраты предприятия, включая оплату труда рабочих, занятых на выполнении заказов, составляют 27 ден.ед. за 1 чел.-день для токарей и 8 ден. ед. для слесарей.

Задача заключается в максимизации средней величины прибыли предприятия с учётом неопределённости, так как неизвестно, какой из двух заказов поступит.

Решение

Предприятие в данных условиях должно определить оптимальную стратегию в выделении трудовых ресурсов , обеспечивающих при любой ситуации с заказами определённый средний доход. Таким образом задача относится к теории игр, причём игра в данном случае будет относится к типу игр с природой. Предприятие как игрок располагает в этих условиях двумя чистыми стратегиями: стратегия P1 с расчётом на поступление заказа Z1 стратегия P2 с расчётом на поступление заказа Z2

Природу будем рассматривать как второго игрока также с двумя стратегиями: заказ Z1(стратегия Q1) и заказ Z2(стратегия Q2).

Необходимо составить платёжную матрицу А:

Если предприятие выберет стратегию P1, то в случае поступления заказа Z1 доход будет равен 600(48-27)+1900(16-8)=27800 ден.ед. (элемент а₁₁).

А в случае поступления заказа Z2 доход составит

600(48-27)+625(16-8)-(1900-625)8=7400 ден. ед. (элемент а₁₂).

Если предприятие выберет стратегию P2, то при поступлении заказа Z1 будет получен доход в размере

600(48-27)+625(16-8)-(1000-600)27=6800 ден.ед. (элемент а₂₁).

А при поступлении заказа Z2 доход будет равен

1000(48-27)+625(16-8)=26000 ден.ед. (элемент а₂₂)

Таким образом, платёжная матрица данной игры имеет вид:

Первая и вторая строки этой матрицы соответствуют стратегиям P1 и P2 предприятия, а первый и второй столбцы – стратегиям Q1 и Q2 природы.

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

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

Пусть х означает частоту применения первым игроком (предприятием) стратегии P1, тогда частота применения им стратегии P2 будет равна (1-x).В случае оптимальной смешанной стратегии первый игрок получит и при стратегии Q1(заказ Z1), и при стратегии Q2(заказ Z2) второго игрока одинаковый средний доход, что соответствует следующему уравнению:

а₁₁x+ а₂₁(1-x) = а₁₂x+ а₂₂(1-x), что соответствует:

27800х+6800(1-х) = 7400х+26000(1-х)

В результате решения уравнения получаем: х=16/33; (1-х)=17/33. Следовательно, первый игрок, применяя чистые стратегии P1 и P2 в соотношении 16:17, будет иметь оптимальную смешанную стратегию, обеспечивающую ему в любом случае гарантированный средний доход в размере 27800(16/33)+6800(17/33) = 16981,82 ден. ед., который и будет в данном случае ценой игры.

Легко рассчитать количество ресурсов труда токарей и слесарей, которое  должно обеспечить предприятие при оптимальной стратегии:

(600 чел.-дн. токарей+1900 чел.-дн. слес.)(16/33) + (1000 чел.-дн. Ток.+625чел.-дн. Слес.)(17/33)=

=806 чел.-дн. токарей+1243,2 чел.-дн. слесарей.

Таким образом, оптимальная стратегия предприятия в управлении трудовыми ресурсами в данных условиях заключается в обеспечении ресурса труда токарей в размере 806 чел.-дн. и ресурса труда слесарей в размере 1243,2 чел.-дн. Эта стратегия гарантирует предприятию при любом стечении обстоятельств средний доход в сумме 16981,82 ден.ед.