Теория.игр.2013

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ЭКОНОМИЧЕСКИЙ УНИВЕРСИТЕТ»

КАФЕДРА ВЫСШЕЙ МАТЕМАТИКИ

МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ТЕОРИИ ИГР для студентов СПбГЭУ

по дисциплинам «Методы оптимальных решений», «Математические методы и модели

в принятии решений»

2

ИЗДАТЕЛЬСТВО САНКТ-ПЕТЕРБУРГСКОГО ГОСУДАРСТВЕННОГО

ЭКОНОМИЧЕСКОГО УНИВЕРСИТЕТА

2013

Рекомендовано научно-методическим советом университета

Методические указания по теории игр для студентов СПбГЭУ по дисциплинам «Методы оптимальных решений», «Математические методы

имодели в принятии решений». – СПб. : Изд-во СПбГЭУ, 2013. – 27 с.

Вметодических указаниях излагаются основные понятия и методы теории игр. Оно может быть использовано студентами всех специальностей СПбГЭУ для подготовки к практическим занятиям и экзамену. Методические указания содержат большое количество примеров, демонстрирующих применение теории игр к вопросам принятия оптимальных решений в различных сферах деятельности.

Составители: канд. экон. наук, доцент Н.Е. Авдушева канд. техн. наук, доцент М.Ю. Калинушкина

старший преп. О.Н. Коростелева

д-р техн. наук, профессор В.А. Рыжов д-р техн. наук, профессор Г.В. Савинов

канд. физ.-мат. наук, доцент Т.А. Федорова

Рецензент д-р техн. наук, профессор Г.М. Фридман

3

© СПбГЭУ, 2013

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

1.1. Основные понятия теории игр

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

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

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

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

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

4

В данных методических указаниях анализируются только равновесные ситуации, то есть такие ситуации, при которых ожидания экономических субъектов оказываются оправдавшимися – ожидаемые ими действия других субъектов совпадают с фактически выбранными. Такой подход позволяет существенным образом сузить область возможных решений. Перечислим основные определения, которые будут использоваться нами в дальнейшем. Предметом теории игр являются ситуации, которые мы называем конфликтами и совместными действиями. Будем предполагать, что для разрешения конфликта или ведения совместных действий каждый из участников придерживается определенных правил, сформулированных до игры, которые определяют выбор варианта в любой из возможных ситуаций. Такой набор правил носит название стратегии. А игры с определенными наборами правил называются стратегическими играми. Очевидно, что в стратегических играх отсутствуют случайные элементы, встречающиеся в таких играх, как бросание кости, рулетка или некоторые игры в карты. Таким образом, в стратегических играх каждый из участников последовательно совершает по определенным правилам оптимальный на его взгляд выбор из совокупности возможных вариантов.

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

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

Ход - это момент игры, когда игроки должны произвести выбор одного из вариантов продолжения игры.

Партией игры называется некоторая определенная совокупность ходов. Определенное состояние в момент игры называется позицией.

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

5

Различные виды игр можно классифицировать по следующим признакам:

-по числу игроков;

-по числу стратегий или ходов;

-по свойствам платежной функции.

В зависимости от числа игроков различают игры с двумя, тремя и более игроками.

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

Третий способ классификации игр - по свойствам функции цели - платежной функции. Одним из типов платежной функции является платежная функция в игре с нулевой суммой. Поясним это понятие. Предположим, что в рассматриваемой партии принимают участие n

i 1

то партию (игру) называют партией (игрой) с нулевой суммой.

Так, в игре двух участников с нулевой суммой выигрыш одного из игроков равен проигрышу другого.

1.3 Описание игры

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

(прямоугольной) форме.

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

6

каждой из которых соответствует строка матрицы. Игрок 2 выбирает одну из своих n стратегий S12 , S22 , , Sn2 , каждой из которых соответствует столбец матрицы. Пара чисел на пересечении выбранных строки и столбца показывает величину выигрыша каждого из игроков.

Платежная матрица имеет размерность m n , где m – число возможных стратегий игрока 1, n - число возможных стратегий игрока 2.

Если игра двух участников, представленная в нормальной форме, является игрой с нулевой суммой, вид платежной матрицы упрощается, так как в этом случае достаточно задать платежную матрицу только одного игрока, например, первого. Действительно, нулевая сумма игры означает, что Пi1j Пi2j 0 .

Значит, платежная матрица игрока 2 равна платежной матрице игрока 1, взятой со знаком «минус»:

Если игрок 1 выбирает стратегию Si1 ( i -строку), а игрок 2 выбирает стратегию S 2j ( j -столбец), то игрок 1 получит выигрыш Пij , а игрок 2 получит выигрыш Пij . Игры подобного типа называют матричными играми.

7

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

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

Пij1 Пij2 const a .

Любую игру с постоянной суммой можно свести к игре с нулевой суммой.

2. Матричные игры двух лиц с нулевой суммой

Рассмотрим матричную игру двух игроков с матрицей порядка m n

Как было указано ранее, строки матрицы соответствуют стратегиям игрока 1, а столбцы матрицы - стратегиям игрока 2. Тогда, если игрок 1 в

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

То есть для игрока 1 имеется выбор, который гарантирует ему, что он

8

Очевидно, что минимальный выигрыш по строкам: первая cтрока - +1,

вторая cтрока - +2, третья cтрока - -3.

Среди этих выигрышей максимальным является значение, равное +2 (вторая строка).

Аналогично, платежи игроку 2 представляют собой элементы матрицы A, взятой со знаком «минус». Таким образом, у игрока 2 имеется выбор, который гарантирует ему, что он получит, по меньшей мере

max min aij .

j i

Поскольку имеют место следующие равенства

max f min f ,min f max f ,

верхней ценой игры.

Снова рассмотрим наш пример. Очевидно, что максимальные

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

9

то игрок 1 должен понять, что он может получить V , а игрок 2 может помешать получить больше, чем V .

Описанная ситуация называется ситуацией с седловой точкой

(i* ; j* ) , которая находится на пересечении i* -й строки и j* -го столбца. То есть элемент V является одновременно минимальным в своей строке и максимальным в своем столбце. В рассмотренном выше примере - это элемент a22 2 . Если игрок 1 использует стратегию, соответствующую седловой точке, то игроку 2 выгоднее всего избрать свою стратегию также соответствующей седловой точке.

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

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

Например, мы играем в игру с платежной матрицей A:

1 при такой стратегии выигрывает не менее двух единиц - это гарантированный выигрыш первого игрока при любой стратегии второго.

Игрок 2 в рассматриваемой игре воспользуется второй стратегией S22 , так

как min max aij 3 , то есть игрок 2 при такой стратегии проиграет не

j i

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

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

Разберем еще один пример такой игры:

10

Для этой игры выполнено строгое неравенство 2 4 , то есть

свою очередь, игрок 2 изберет стратегию S32 и будет ожидать, что игрок 1 выберет стратегию S21 . Однако результат a13 3 оказывается одинаково неожиданным для обоих игроков. На самом деле, если игрок 2 выберет третью стратегию S32 , то игрок 1 поступит правильнее, выбирая вторую стратегию, а не первую. Аналогично, если игрок 1 выберет первую стратегию S11 , то игроку 2 выгоднее выбрать вторую стратегию, а не третью. Таким образом, в играх без седловой точки изложенный выше принцип решения оказывается непригодным. Однако этот принцип может снова стать верным, если расширить понятие стратегий за счет

смешанных (или случайных) стратегий.

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

игрока 1 назовем вектор:

где pi — вероятность выбора i -й чистой стратегии.

Поскольку компоненты вектора являются вероятностными, то они должны быть неотрицательными, а их сумма должна равняться единице.

Таким образом, смешанная стратегия представляет собой вектор, удовлетворяющий условиям

Точно так же для игрока 2 смешанной стратегией назовем вектор:

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