WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 | 4 | 5 |
Федеральное агентство по образованию Санкт-Петербургский государственный архитектурно-строительный университет К. В. ГРИГОРЬЕВА БЕСКОАЛИЦИОННЫЕ ИГРЫ В НОРМАЛЬНОЙ ФОРМЕ Часть 1 Учебное пособие Санкт-Петербург 2007 1 УДК 51 Рецензенты: канд. физ.-мат. наук Парилина Е. М. (каф. математической теории игр и статистических решений ф-та прикладной математики – процессов ЗАНЯТИЕ № 1 управления Санкт-Петербургского государственного университета); канд. физ.-мат.

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

оптимального управления в условиях конфликта (в условиях Бескоалиционные игры в нормальной форме. Часть 1: учебное пособие / столкновения сторон, каждая из которых стремится воздействовать на СПб. гос. архит.-строит. ун-т. – СПб., 2007. – 78 с.

развитие конфликта в своих интересах).

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

ричные (антагонистические) и биматричные. Много внимания уделено понятию «Теория игр – это теория рационального поведения людей ситуации равновесия как решению бескоалиционных игр. В качестве методов рес несовпадающими интересами» [8].

шений предлагаются, в частности, равновесие по Нэшу, оптимальность по Паре«Теория игр – наука о стратегическом мышлении» [9].

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

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

мере “выигрыша”, который он мог бы получить, выбрав в данной ситуации данную стратегию» [1].

Табл. 1. Ил. 1. Библиогр.: 2 назв.

Неопределенность в GT является следствием сознательной деятельности другого лица (лиц), отстаивающего свои интересы. В связи Рекомендовано Редакционно-издательским советом СПбГАСУ в качестве с этим под «теорией игр понимается теория математических моделей учебного пособия принятия оптимальных решений в условиях конфликтов» [2].

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

© Санкт-Петербургский государственный Моделями GT описываются экономические и правовые конфликархитектурно-строительный ты, взаимодействие человека с природой, биологическая борьба за сууниверситет, ществование, военное дело и т. д. [3, 4, 11, 12, 13, 15, 19]. Теоретикоигровой подход к изучению формирования коалиций является своего рода традицией в социальных и политических науках [14, 16, 17, 18, 20, 21].

В книге «Game Theory and the Law» (D. Baird, R. Gertner, С. Picker, 1994) 2 аппарат GT впервые применяется к анализу того, как законы влияют на бескоалиционные, в которых каждая коалиция или множеповедение людей, партий и т. д. ство игроков, действующих совместно, состоит лишь из одОсобая роль теории игр выделяется в экономическом моделирова- ного игрока; теория бескоалиционных игр – это способ модении: «Суть теории игр в том, чтобы помочь экономистам понимать и лирования и анализа ситуаций, в которых оптимальные репредсказывать то, что будет происходить в экономическом контексте» шения каждого игрока зависят от его представлений об игре [10]. «Аппарат теории равновесия и теории игр послужил основой для оппонентов; важнейший момент теории – игроки не должны создания современных теорий международной торговли, налогообложе- придерживаться произвольных представлений об игре своих ния, общественных благ, монетарной экономики, теории производствен- оппонентов: и каждый игрок должен пытаться предсказать ных организаций» [7]. игру своих оппонентов, используя свои знания правил игры и исходя из предположений, что его оппоненты сами рациональ1.2. Классификация игр ны, а потому пытаются предсказать игру своих оппонентов и максимизировать свои собственные выигрыши, однако так Все модели в GT принято называть играми. Математическое опи- называемая кооперативная теория бескоалиционных игр досание игры сводится к перечислению всех действующих в ней игроков, пускает временные объединения игроков в коалиции в проуказанию для каждого игрока всех его стратегий, а также численного цессе игры с последующим разделением полученного выигвыигрыша, который он получит после того, как игроки выберут свои рыша или принятие совместных решений;

стратегии. В результате игра становится формальным объектом, кото- • по степени информативности «игроков» в игре:

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



стохастические, когда известно множество возможных ва• по числу «игроков» (сторон) N 2;

риантов условий и их вероятностное распределение;

• по числу ходов в игре:

неопределенные, когда известно множество возможных вари многошаговые;

антов, но без какой-либо информации об их вероятностях;

бесконечные;

• по выигрышу игры:

• математической структуре модели игры:

антагонистические;

рекурсивные;

игры с ненулевой суммой;

дифференциальные;

• по характеру получения информации:

• по числу стратегий игры:

статические игры или игры в нормальной форме (игроки конечные;

получают всю предназначенную им информацию до начала бесконечные, если хотя бы у одного «игрока» число стратеигры и ходят один раз, одновременно и независимо);

гий бесконечно;

динамические игры или игры в позиционной форме (инфор• по взаимоотношениям игроков:

мация поступает игрокам в процессе развития игры);

кооперативные (коалиционные), в которых принимающие • по полноте имеющейся у игроков информации:

решение игроки объединены в фиксированные коалиции; чле статические игры с полной информацией предполагают, ны одной коалиции могут свободно обмениваться информачто у игроков имеется вся «необходимая» информация друг о цией и принимать полностью согласованные решения; игродруге, включая выигрыши игроков;

ки могут вступать в коалицию и договариваться о совмест если игрок знает свою функцию выигрыша, но не знает функных действиях;

ций выигрыша остальных игроков, то тогда участники долж4 ны иметь какие-то представления относительно предпочте- Такая игра называется биматричной, так как ее можно представить ний других участников, а также должны иметь представле- в виде двух матриц ния об их представлениях о предпочтениях других и т. д.; здесь 11 … 1n 11 … 1n мы приходим к понятию Байесовых игр (статические игры … … … с неполной информацией);

и … … ….

… mn … mn динамические игры с полной информацией и неполной ин m1 mформацией.

Отметим, что формально постановка игры в нормальной форме имеет следующую интерпретацию: игроки одновременно и независимо 1.3. Игра в нормальной форме друг от друга выбирают свои стратегии xi Xi ; после этого возникает Определение 1.1. Под игрой в нормальной (или стратегической) ситуация (x1,…, xn ); на этом игра прекращается, и i -й игрок получает форме понимается объект свой выигрыш Ki(x1,…, xn ), где i N.

G = {N, X1, …, X, K1, …, Kn}, n Возникает следующая проблема: каждый игрок стремится максигде – множество игроков; X – конечное множество чистых о N ={1, n} i мизировать свой выигрыш. Такая постановка математически некорректна, так как игрок знает только свою стратегию xi и не знает других парастратегий xi -го игрока, ; xi – чистая стратегия i -го игрока, а, i i N метров. В связи с этим существуют различные подходы к понятию оптиа i N, xi Xi ; Ki(x1,…, xn ) – вещественная функция выигрышей игрока мального поведения.

i, определенная на декартовом произведении X = X1 X2 … X.

В 1950 г. Джон Нэш (лауреат Нобелевской премии по экономике n 1994 г.) ввел понятие ситуации равновесия как метода решений бескоНабор стратегий x = (x1,…, xn), x X называется ситуацией алиционных игр.

игры.

Определение 1.2. Ситуация, образующаяся в результате выбора Рассмотрим простейшую статическую модель – игру в нормальной всеми игроками некоторых своих стратегий, называется равновесной, форме если ни одному из игроков невыгодно изменять свою стратегию при ус(11,11) … (1n,1n) ловии, что остальные игроки придерживаются равновесных стратегий.

Именно равновесие по Нэшу и его модификации признаются наи… … …, более подходящими концепциями решения таких игр.

(m1,m1) … (mn,mn) в которой имеем: 1.4. Равновесие по Нэшу участие двух игроков, N = {1,2} Введем обозначения. Пусть ситуация игры x = (x1,…, конечное множество стратегий каждого из игроков:

ует xi-1, xi, xi+1,…, xn ). Вместо стратегии xi игрок использует i X1 ={i i = 1, m} – стратегии первого игрока;

стратегию xi : (x || xi ) = (x1,…, xi-1, xi, xi+1,…, xn ).

– стратегии второго игрока;

X2 = {j j = 1,n} Определение 1.3. Будем говорить, что ситуация (это набор x ситуация игры – пара стратегий ;

(i, j) стратегий) является равновесной по Нэшу (NE – Nash Equilibrium), если имеет место K1(i, j) = ij – выигрыш первого игрока и K2(i, j) = ij – Ki(x) Ki(x || xi ) i N, xi Xi.

выигрыш второго игрока.

6 Если игроки договорились о выборе стратегии и возможна ситуация Ф Ф Следовательно, – NE. В ситуации (Ф,Ф) у мужа – x =(xМ, xЖ), входящая в равновесие по Нэшу, то получается устойчивый договор, x у жены –. Какие у игроков альтернативы K1(ФФ) = 4; K2(ФФ) =и в дальнейшем ни один из игроков в индивидуальном порядке не заинтересован в отклонении от равновесия по Нэшу, так как выигрыш У мужа – у жены –. Так как K1(ТФ) = 0; K2(ФТ) = 0 K1(ФФ) > K1(ТФ) может только уменьшиться. В то же время равновесие по Нэшу не и, то (Ф,Ф) – NE.

K2(ФФ) > K2(ФТ) является устойчивым против отклонения группы игроков. Если сразу Аналогично можно рассмотреть остальные комбинации, откуда отойдет некоторая коалиция игроков, то они могут выиграть.

получится, что здесь есть два равновесия по Нэшу в чистых стратегиях – Пример 1.1. Семейный спор..





N = {муж (М), жена (Ж)} (Ф,Ф) и (Т,Т).

Каждый имеет две альтернативы: пойти в театр (Т) или на футбол (Ф), Пример 1.2. Дилемма заключенного. Двое подозреваемых в совершении тяжкого преступления арестованы и помещены в одиночные т. е. X = X ={xТ, xФ}. Если они вместе пойдут на футбол, то Он М Ж камеры, причем они не имеют возможности передавать друг другу какиеполучит больше удовольствия, чем Она; если они вместе пойдут в театр, либо сообщения. Их допрашивают поодиночке. Если оба признаются в то – наоборот. Наконец, если они окажутся в разных местах, то они не совершении преступления, то с учетом их признания им грозит тюремное получат никакого удовольствия. Рассматриваемая ситуация моделируется заключение сроком по 8 лет каждому. Если оба будут молчать, то они следующей игрой:

будут наказаны за совершение какого-то незначительного преступления Ф Ф Ф Ф Т Ф Т Ф (скажем, незаконное хранение оружия или что-нибудь другое) и получат (K1(xМ, xЖ), K2(xМ, xЖ)) (K1(xМ, xЖ), K2(xМ, xЖ)) в этом случае по одному году тюремного заключения. Если же один из = них сознается (С), а другой – нет (Н), то первый за содействие следствию Ф Т Ф Т Т Т Т Т (K1(xМ, xЖ), K2(xМ, xЖ)) (K1(xМ, xЖ), K2(xМ, xЖ)) будет вовсе освобожден от наказания, тогда как второй будет приговорен к максимально возможному за данное преступление наказанию – Ж 10-летнему тюремному заключению.

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

Ф (4,1) (0,0).

= М II Т (0,0) (1,4) С Н Рассмотрим ситуацию (Ф,Ф). Запишем математически: – С (- 8,-8) (0,-10).

x I единственная альтернатива, аналогично, – единственная Н (-10,0) (-1,-1) x1 x альтернатива :

xРассмотрим каждую ситуацию в отдельности:

Ф Ф K1(СС) = -8; K2(СС) = -8;

x = (x1, x2 ), x1 = xМ, x2 = xЖ ;

(СС): NE;

K1(НС) = -10; K2(СН) = -10;

Т Ф (x || x1) = (xМ, xЖ );

- 8 > -10; - 8 > -10;

Ф Т (x || x2 ) = (xМ, xЖ );

K1(СН) = 0; K2(СН) = -10;

K1(x) = 4; K2(x) = 1;

(СН): не NE;

K1(НН) = -1; K2(СС) = -8;

K1(x || x1) = 0; 4 > 0; K2(x ||x2) = 0; 1 > 0.

0 > -1; -10 > -9;

/ 8 K1(НН) > K1(СС) K1(НС) = -10; K2(НС) = 0;

(СС) : так как не опт. по Парето;

(НН):

(НС): K1(СС) = -8; K2(НН)= -1; не NE;

K2(НН) > K2(СС) -10 > -8; 0 > -1;

/ (СН) : так как ¬ x : K1(x ) > K1(СН) = 0 опт. по Парето;

K1(НН) = -1; K2(НН) = -1;

(НС) : так как ¬ x : K2(x ) > K2(НС) = 0 опт. по Парето;

(НН): не NE.

K1(СН) = 0; K2(НС) = 0;

K1(x ) > K1(НН) -1 > 0; -1 > 0;

/ / ¬ x :

(НН) : так как опт. по Парето.

(x ) > K2(НН) KСледовательно, (СС) – NE.

Самостоятельная работа № 1.5. Оптимальность по Парето * * Исследовать все ситуации на равновесие по Нэшу и оптимальность Определение 1.4. Ситуация называется оптиx* = (x1,…, xn) по Парето.

мальной по Парето, если не существует никакой другой ситуации x = (x1,…, xn), такой что:

ЗАНЯТИЕ № 1) ;

Ki(x ) Ki(x*) i N 2) хотя бы для одного i0 N Ki (x ) > Ki (x*).

0 2.1. Антагонистические игры. Седловая точка Пример 1.3. Семейный спор Определение 2.1. Игра в нормальной форме называется игрой K1(ФФ) = 4; K1(ФТ) = 0; K1(ТФ) = 0; K1(ТТ) = 1; с нулевой суммой, если для любого набора стратегий x = (x1,…, xn) выполняется условие K2(ФФ) = 1; K2(ФТ) = 0; K2(ТФ) = 0; K2(ТТ) = 4;

n (ФФ) : так как ¬ x : K1(x ) > K1(ФФ) = 4 опт. по Парето;

(x1,…, xn) = 0.

Ki i=K1(ФФ) > K1(ФТ) Эта игра представляет собой замкнутую систему: все то, что кто(ФТ) : так как не опт. по Парето;

(ФФ):

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

K1(ФФ) > K1(ТФ) Будем далее считать, что.

N = {1,2} (ТФ) : так как (ФФ): не опт. по Парето;

K2(ФФ) > K2(ТФ) Определение 2.2. Игра двух лиц с нулевой суммой называется антагонистической.

(ТТ) : так как ¬ x : K2(x ) > K2(ТТ) = 4 опт. по Парето.

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

Пример 1.4. Дилемма заключенного K1(i, j)+ K2(i, j) = K1(СС) = -8; K1(СН) = 0; K1(НС) = -10; K1(НН) = -1;

или K2(СС) = -8; K2(СН) = -10; K2(НС) = 0; K2(НН) = -1;

.

K1(i, j) = -K2(i, j) i X1, j X10 Пример 2.1. Орел и решка. В этой игре каждый из двух игроков В седловой точке элемент матрицы i, j является одновременно выбирает независимо друг от друга монетку, повернутую вверх либо минимумом в своей строке и максимумом в своем столбце.

«орлом», либо «решкой». Если выбор игроков различен, то игрок 2 плаПример 2.2. В игре с матрицей тит игроку 1 один доллар. Если выбор совпадает, то – наоборот. Матрица выигрышей такой игры:

6 (3) о р 0 1 0 о (-1, 1) (1, -1).

(3)5 (3) р (1, -1) (-1, 1) 0 0 Определение 2.3. Конечная антагонистическая игра называется GA ситуация является равновесной.

(2, 2) матричной (МИ), поскольку выигрыши игроков полностью задаются Определение 2.5. Стратегия i или, входящая в ситуацию равнj матрицей A выигрышей первого игрока.

овесия, называется оптимальной стратегией 1-го или 2-го игрока.

Рассмотрим вопрос об оптимальном поведении игроков в антагоОпределение 2.6. Значение функции выигрыша в ситуации нистической игре. Напомним, что естественно в этой игре считать GA равновесия i, j = v называется значением игры.

Pages:     || 2 | 3 | 4 | 5 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

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