Колесник Г.В. Теория игр. Учебное пособие. Тверь: ТвГУ, 2009. 133 c.

ISBN 978-5-7609-0513-0

1. Некооперативные игры

1.1. Нормальная форма игры

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

построение моделей принятия решений в условиях конфликта.

В обыденном смысле под словом конфликт понимается противостояние

нескольких сторон (или их коалиций), при котором каждый из участников

желает нанести наибольший урон сторонам, не входящим в коалицию с ним.

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

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

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

Колесник Г.В. Теория игр. Учебное пособие. Тверь: ТвГУ, 2009. 133 c.

ISBN 978-5-7609-0513- Для того чтобы понять, каким образом может быть формально описан конфликт, необходимо выделить его основные компоненты. В конфликте всегда имеется несколько сторон или игроков, пытающихся достичь свои цели. В процессе взаимодействия игроки применяют некоторые действия для достижения своих целей и приходят к некоторому исходу, в той или иной степени удовлетворяющему их.

Сопоставим этим элементам конфликта их формальные аналоги.

Обозначим через N множество взаимодействующих сторон и определим для каждой стороны i N множество стратегий Xi, описывающее всевозможные действия, которые может предпринять данная сторона. Будем считать, что взаимодействие сторон заключается в одновременном выборе своих стратегий xi из множеств Xi. Результат этих выборов образует исход конфликта или ситуацию в игре (x1, x2, …, xN) X X i. Степень, в которой iN исход игры удовлетворяет интересам сторон, в общем случае удобно задавать отношением предпочтения каждой из сторон Ri на множестве возможных ситуаций X. В частном случае, когда отношение Ri допускает представление в виде функции полезности, цели сторон могут быть заданы в форме функциональных критериев ui : X R1.

Таким образом, формализованное представление конфликта может быть задано в виде набора Г = < N, {Xi}iN, X, {Ri}iN >.

Этот набор называется игрой в нормальной форме.

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

iN Рассмотрим несколько классических игр двух лиц.

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

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

Колесник Г.В. Теория игр. Учебное пособие. Тверь: ТвГУ, 2009. 133 c.

ISBN 978-5-7609-0513- Множество стратегий каждой из сторон в этой игре состоит из двух элементов: X1 = X2 = {«орел», «решка»}. Тогда выигрыш первого игрока (и соответственно проигрыш второго) есть функция u : X1 X2 R1, заданная на множестве из четырех элементов. Такую функцию удобно представлять в виде матрицы, поэтому игры с конечными дискретными множествами стратегий называют матричными:

Игрок орел решка орел –1 Игрок решка 1 – Из-за того что игра антагонистическая, чтобы полностью её описать, достаточно задать лишь один критерий (в данном случае – выигрыш первого игрока). Критерий второго игрока будет равен первому с противоположным знаком.

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

Снова у обоих игроков имеется по две стратегии: X1 = X2 = {«Сознаться», «Не сознаваться»}. Однако теперь их интересы не полностью противоположны, в связи с чем для полного описания игры должны быть заданы выигрыши каждого. Такие игры называются биматричными.

Матрицы «выигрышей» игроков в данной игре сведены в таблицу:

Колесник Г.В. Теория игр. Учебное пособие. Тверь: ТвГУ, 2009. 133 c.

ISBN 978-5-7609-0513- Верхнее число в каждой ячейке таблицы представляет собой выигрыш первого игрока, нижнее – выигрыш второго. В качестве выигрышей здесь взяты величины, противоположные срокам, которые получат игроки в каждой из ситуаций. Знак «минус» обусловлен тем, что чем строже наказание, тем ниже полезность игрока.

3. С е м е й н ы й с п о р. Как следует из названия, игроки – муж и жена.

Муж хочет сходить вечером на футбол, жена – в театр. Если они договорятся и пойдут куда-нибудь вместе, они получат большое удовольствие, если поругаются и пойдут не вместе, то вечер будет испорчен.

Множества стратегий игроков X1 = X2 = {«футбол», «театр»}. Матрица выигрышей:

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

Шофер управляет автомобилем, движущимся из точки с координатами (x10, y10) с постоянной скоростью v1, выбирая в каждый момент времени радиус кривизны траектории, который ограничен заданной величиной R (максимальным углом поворота руля).

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

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

Это пример дифференциальной игры, которая описывает, как разворачиваются действия игроков с течением времени. Стратегии игроков в Колесник Г.В. Теория игр. Учебное пособие. Тверь: ТвГУ, 2009. 133 c.

ISBN 978-5-7609-0513- Рис. 1. Графическая иллюстрация игры «шофер-убийца»

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

Так, в нашем примере стратегиями шофера и пешехода являются соответственно выбор радиуса кривизны траектории (t) и направления движения (t) в каждый момент времени. Этот выбор изменяет их координаты согласно известным физическим законам движения (рис. 1):

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

«Столкновение» происходит в момент времени, такой, что расстояние между шофером и пешеходом Тогда выигрыш шофера представляет собой функционал, определенный на парах стратегий ((t), (t)):

Колесник Г.В. Теория игр. Учебное пособие. Тверь: ТвГУ, 2009. 133 c.

ISBN 978-5-7609-0513- Обратим внимание, что нам снова понадобилось задать лишь одну функцию выигрыша, так как данная игра, так же как и рассмотренная выше игра «орлянка», является антагонистической.

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

1. Каждый игрок стремится максимизировать свой выигрыш.

2. Каждый из игроков имеет полную информацию об игре.

3. Свои стратегии игроки выбирают одновременно и независимо.

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

Проанализируем эти предположения более подробно.

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

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

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