WWW.DISSERS.RU

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

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


Pages:     | 1 |   ...   | 4 | 5 || 7 | 8 |   ...   | 15 |

вать. При пасе второго игрока все деньги забирает первый игрок.

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

карта.

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

.

ь т я н и р П П а с П а с не равна нулю, то есть это – игра с непротивоположными интере- - продавец знает лишь, что цена покупателя лежит в диапазоне от b до B, а покупатель знает, что цена продавца лежит в диапасами, в отличие от антагонистической игры примера 5. • зоне от s до S Пример 6 [46, 47]. «Фермеры на общем поле».

Два фермера пасут коров на общем поле. Количество молока - продавец знает вероятность P1(b'), b' [b; B] того, что цена x, которое приносит корова, зависит от общего числа коров на покупателя равна b', а покупатель знает вероятность P2(s'), поле, x = 120 – n (литров), где n = n1 + n2 – общее количество коров s' [s; S], того, что цена продавца равна s' • на поле. Доход фермера определяется количеством молока, приПример 8 [65]. «Дележ в оркестре».

носимым его коровами: П1 = n1 (120 – n1 – n2), П2 = n2 (120 – n1 – Директор клуба обещает 100 руб. певцу S, пианисту P и n2). Сколько коров выпустят на поле фермеры В этой игре ударнику D за совместное выступление. Дуэт певца и пианиста он действия игроков – n1 и n2, а выигрыши – П1 и П2. Это также дисоценивает в 80 руб., ударника и пианиста – в 65 руб., а одного кретная однократная некооперативная игра двух лиц с полной пианиста – в 30 руб. Другие дуэты и солисты им не рассматриинформированностью.

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

множество действий каждого фермера будет представлять собой Как должны быть поделены деньги от выступления оркестра, отрезок действительной оси. • чтобы никто не был обижен • Пример 7 [74, 79, 82]. «Аукцион».

Игры в примерах 4-8 сформулированы по-разному. Так, поНа аукционе на продажу выставлен предмет. Есть один простановка игры в виде дерева принятия решений, как в примере давец и один покупатель. Цена предмета для продавца (мини«Минипокер», называется игрой в развернутой форме. Игрой в мальная цена, по которой продавец готов продать предмет) rs, цена нормальной форме называется представление игры в виде таблидля покупателя (максимальная цена, по которой покупатель готов цы (как в примере 5 «Два начальника»), или в виде задания возкупить предмет) – rb. Оба игрока знают свою цену, но не знают можных действий игроков и их выигрышей в зависимости от их цену противника. Они делают заявки ps и pb. Если заявка действий (как в примере 6 «Фермеры на общем поле») – см. глапокупателя выше заявки продавца, то предмет продается по средву 3.

ней стоимости p = (ps + pb) / 2. Если заявка продавца выше заявки Игры, в которых игроки неточно знают интересы противника, покупателя, то сделка не состоится.

как в примере 7 «Аукцион», называются играми с неполной инЭто также непрерывная игра двух лиц с непротивоположными формированностью – см. главу 4.

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

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

и способы их исследования.

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

Одни формы больше подходят для описания одних классов игр 49 (реальных ситуаций), другие – для других. Тем не менее, такое Для каждой нетерминальной вершины необходимо указать, многообразие постановок задач порождает свои сложности. Может какой игрок контролирует данную вершину, то есть осуществляет ли одна и та же игра быть представлена в различных формах выбор. Вершина может и не контролироваться ни одним из Стоит ли рассматривать все эти игры или можно ограничиться игроков, тогда эту вершину контролирует природа (как, например, рассмотрением игр только в одной форме Как тогда будут соот- стартовую вершину в примере 4). Вершина, контролируемая носиться решения игры, представленной в одной форме с реше- игроком с номером i, называется еще «точкой выбора i-го игрониями этой же игры, представленной в другой форме Ниже будут ка».

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

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



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

игровой ситуации. Из рисунка 5 видно, что, поскольку первый игрок знает, выпала ему красная или черная карта, он может различить две ситуации принятия решения, в отличие от второго ГЛАВА 3. ИГРЫ С ПОЛНОЙ ИНФОРМИРОВАННОСТЬЮ игрока, который не знает цвета масти выпавшей карты, но должен принять решение: принять ставку или спасовать. Значит, для 3.1. Определение игры в развернутой форме полноты описания необходимо, помимо игрока, контролирующего Развернутая форма – естественный способ представления саданную вершину, указать информационное состояние, в котором лонных игр, вроде шахмат или преферанса. Однако и другие игры он находится. На рисунке 5 контролируемые вершины второго (по крайней мере, дискретные), обычно сначала рассматриваются игрока объединены пунктиром, чтобы показать, что им соотв развернутой форме.

ветствует одно информационное состояние, названное – «Наугад».

Для того чтобы продемонстрировать основные элементы Заметим, что возможные альтернативы вершин, объединенных описания игры в развернутой форме, вспомним пример 4 «Миодним информационным состоянием, должны совпадать, иначе нипокер» (см. рисунок 5).

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

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

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

от выбора одного из игроков или от реализации внешнего 2) Каждой терминальной вершине Fi ставится в соотсобытия. Самая левая вершина («корень» дерева) означает сиветствие метка-«вектор выигрышей», то есть числовой вектор туацию в начале игры, конечные (терминальные) вершины ознаf(Fi)=(f1, f2, …, fn) (размерности n) выигрышей (полезностей) чают возможные исходы игры. Каждой конечной вершине поигроков.

ставлен в соответствие вектор выигрышей игроков. В случае двух 3) Каждой нетерминальной вершине ставится в соответигроков этот вектор состоит из пары чисел – значений полезности ствие метка контроля – номер игрока i N = {1, 2, …, n}, игроков при заданном исходе игры.

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

ствие метка информационного состояния игрока (обычно она В соответствии с введенной выше классификацией, среди игр отделяется от номера игрока точкой).

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

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

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

Определение 1: Игрой в развернутой форме называется систе- Этот случай является предметом исследования теории некооперама 1-6. тивных игр. Кроме того, результаты теории некооперативных игр Описание игры в развернутой форме довольно сложно, хотя и будут использованы в дальнейшем при исследовании кооперасодержательно богато. Следует ожидать, что и формулировка тивных игр.

понятия решения для таких игр будет громоздка. Поэтому вместо Определение 2: Игрой в нормальной форме n лиц с произтого, чтобы подробно исследовать игры в развернутой форме, вольной суммой называется система30 Г = (Xi, Ki, i N), где Xi – введем новую, более простую форму игры (нормальную, или непустые множества действий, Ki – функции выигрыша игроков, стратегическую форму), определим формальную процедуру пеKi: X1 … Xn 1.

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

ограниченными и замкнутыми множествами. Определения замкнутости и ограниченности подразумевают, что на множестве 3.2. Определение игры в нормальной форме действий определено понятие сходимости, то есть задана, как В отличие от довольно сложной постановки игры, рассмотминимум, топология. Часто в доказательствах необходимо наличие ренной выше, постановка игры в нормальной форме сравнительно метрики на множестве действий. На практике множества действий проста. Предполагается, что игроки имеют возможность лишь игроков обычно представляют собой подмножества векторного один раз выбрать альтернативу (действие), каждый из своего пространства, для которых можно использовать евклидову метримножества возможных действий. Также предполагается, что ку.





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

ния ОС) будет использоваться принятая в теории игр система обозначений.

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

виде матрицы, в которой он выбирает действие – номер строки, Множество стратегий каждого игрока будем обозначать Xi.

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

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

каждого вектора стратегий x X определим вероятность P(Q|x) Игры из примеров 5 и 6 – это игры в нормальной форме, реализации данного состояния Q при использовании игроками причем в примере 5 рассматривается биматричная игра. Приведем стратегий x с помощью рекуррентной процедуры, а именно:

еще один пример биматричной игры.

- если Q – корневая вершина, то, для произвольных x, Пример 9 [65]. «Семейный спор». P(Q|x) = 1;

Муж и жена решают, куда им пойти – на футбольный матч - если вершина R предшествует вершине Q в графе игры, пеили в театр. Если они не договариваются, то остаются дома. Перреход из R в Q определяется природой и происходит с вевое действие каждого из игроков соответствует поездке на футроятностью p, то P(Q|x) = P(R|x) p;

больный матч, второе – в театр. Биматрица игры записывается так - если вершина R предшествует Q в графе игры и переход из (первое число пары соответствует выигрышу мужа, второе – R в Q определяется одним из игроков, то P(Q|x) = P(R|x) в (4,1) (0, 0) случае, если данный переход содержится в векторе страте выигрышу жены): A = (0, 0) (1, 4). • гий игроков, в противном случае P(Q|x) = 0.

Таким способом для каждой терминальной вершины Fi можно определить соответствующие вероятности P(Fi|x) попадания в них 3.3. Переход от игры в развернутой форме при условии использования игроками вектора стратегий x.

к игре в нормальной форме Теперь можно определить ожидаемые значения выигрышей Постановка игры в нормальной форме гораздо проще для игроков при использовании ими вектора x по формуле изучения и формализации, чем игра в развернутой форме, поэтому (5) Ki (x1,x2,...,xn ) = fi (Fj )P(F |x), j ниже будут рассматриваться только решения игр в нормальной j форме. Для игр же в развернутой форме построим формальную где Fj – терминальные вершины графа игры.

процедуру перехода от них к играм в нормальной форме.

Теперь можно определить игру в нормальной форме, которая Сначала введем для игры в развернутой форме понятие соответствует исходной игре в развернутой форме. Множество игстратегии игрока.

роков новой игры совпадает с множеством игроков исходной игОпределение 3: Стратегией игрока для игры в развернутой ры, множествами действий будут определенные выше множества форме называется функция, отображающая множество информастратегий Xi, а функция выигрыша определяется формулой (5).

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

игры целесообразными является набор действий x X, тем са 55 мым полностью определяется и поведение игроков в исходной иг- каждый игрок составляет до начала игры. Этот план описывает все ре. действия, которые игрок будет предпринимать во всех возможных Отметим, что, поскольку выше было дано описание лишь игровых состояниях. Стратегия игроков даже в игре в нормальной дискретных игр в развернутой форме, то и получающиеся с по- форме может быть более сложной, чем просто выбор одного из мощью рассмотренной процедуры игры в нормальной форме так- элементов множества действий Xi (стратегия, состоящая в выборе же будут дискретными. действия из множества Xi, называется чистой стратегией).

Вспомним, что в играх в развернутой форме для тех ходов, Пример 10. Построение игры в нормальной форме которые делала природа, указывалась вероятность того или иного для примера 4 «Минипокер».

ее «хода». Аналогично и игроки могут не выбирать в каждой сиИгрок 1 имеет два информационных состояния: он знает, катуации некоторое единственное действие, а выбирать одно из ков цвет выбранной карты. Следовательно, его стратегиями будут:

Pages:     | 1 |   ...   | 4 | 5 || 7 | 8 |   ...   | 15 |










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

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