Контрольная работа по теории игр

Если у вас нету времени на контрошу по теории игр вы всегда можете попросить меня, вам нужно написать мне, и я вам помогу онлайн или в срок 1-3 дня всё зависит что там у вас за работа, вдруг она огромная!

Чуть ниже размещён теоретический и практический материал, который вам поможет сделать работу если у вас много свободного времени и желания!

 

 

Введение в теорию игр

Математические модели игр

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

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

 

По этой ссылке вы сможете узнать как я помогаю с контрольными работами:

Помощь с контрольными работами

 

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

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

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

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

 

По этой ссылке вы сможете научиться оформлять контрольную работу:

Теоретическая контрольная работа примеры оформления

 

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

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

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

Основные понятия

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

Такие ситуации называются конфликтными. Конфликтная ситуация характеризуется следующими чертами:

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

 

По этой ссылке вы сможете заказать контрольную работу:

Заказать контрольную работу

 

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

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

Так, если целью объединения являются совместные действия, то эти объединения называются коалициями действия. Если же объединение образовано по признаку идентичности предпочтений исходов игры, то они называются коалициями интересов. Указанные коалиции не всегда совпадают. В случае совпадения их называют просто коалициями. С точки зрения временного фактора коалиции могут быть временные или постоянные на протяжении игры. Если в игре участвуют два противника, то она называется парной. Если число противников более двух, то игра называется множественной. Множественная игра с двумя постоянными коалициями есть не что иное, как парная игра.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Контрольная работа по теории игр

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

Можно разделить игры на классы по мощности множеств стратегий игроков. Как уже отмечалось, если множество стратегий каждого игрока конечно, то игра называется конечной. В противном случае она называется бесконечной.

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

В силу равенства (3.1) Контрольная работа по теории игр(т. е. матрица В противоположна транспонированной матрице А).

 

Возможно вам пригодятся эти страницы:

Контрольная работа по гражданскому праву заказать
Контрольная работа по управлению проектами заказать
Контрольная работа по теории государства заказать
Контрольная работа по термодинамике заказать

 

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

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

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

Математические модели игр

Рассмотрим парную игру с игроками А и В. Пусть игрок А имеет т стратегий m Контрольная работа по теории игр, а (противник) игрок В n стратегий Контрольная работа по теории игр . Натуральные числа т и п в общем случае никак не связаны между собой.

Если каждый из игроков А и В сознательно определенным образом выбирает стратегии Ai и Bj соответственно, то сложившаяся ситуация (в чистых стратегиях) (AiBj) однозначно определяет выигрыш игрока А, выражающийся действительным числом aij, которое одновременно является и проигрышем игрока В. А число (- aij )выражает проигрыш игрока А и выигрыш игрока В . Если число aij отрицательно, то в принятой нами формализованной терминологии оно будет представлять отрицательный выигрыш игрока А, а по сути его проигрыш. Числа aij это значения функции выигрыша FA игрока Контрольная работа по теории игр. Ходы игроков с сознательным выбором одной из возможных своих чистых стратегий называют иногда личными ходами.

Выигрыши Контрольная работа по теории игр можно расположить в виде матрицы, номера строк которой соответствуют номерам стратегий игрока А, а номера столбцов номерам стратегий игрока В.

Контрольная работа по теории игр

Матрица А называется матрицей выигрышей игрока А. Обозначим через bji значения функции выигрыша Рв игрока В, т. е. ед, Контрольная работа по теории игр Контрольная работа по теории игр. Тогда матрица выигрышей игрока В будет иметь вид

Контрольная работа по теории игр

Если рассматриваемая игра – антагонистическая (т.е. с нулевой сумой выигрышей), то функции выигрышей FA и FB игроков A и B связаны между собой равенством (3.1) и, следовательно,

Контрольная работа по теории игр

Эти равенства означают, что матрица выигрышей B игрока B является противоположной транспонированной матрице A:

Контрольная работа по теории игр

Таким образом, матрица В вполне определяется матрицей А. Матрицу А также называю матрицей игры, или платежной матрицей. Матрица А имеет размер m Контрольная работа по теории игр n, где первая компонента размера m указывает на число строк (т.е. число стратегий игрока А), а вторая n на число столбцов (число стратегий игрока В). Поэтому часто такую игру называют mКонтрольная работа по теории игр n игрой.

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

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

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

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

Пример 4.1 (антагонистическая конкуренция) [7]. Фирма А производит некоторый сезонный товар, имеющий спрос в течение n единиц времени, и который она может поставить на рынок в один из моментов Контрольная работа по теории игр(см. рис. 4.1).

Контрольная работа по теории игр

Для конкурентной борьбы с фирмой А дочерняя фирма В концерна D не заботясь о собственных доходах, производит аналогичный товар, который поступает на рынок в один из моментовКонтрольная работа по теории игр Цель фирмы В разорение фирмы А, после чего, используя капитал концерна D она может легко наверстать упущенное. Единственным законным средством фирмы В в конкурентной борьбе является выбор момента поставки товара на рынок, так как понижение цены на поставляемый товар запрещено определенным соглашением. Для разорения фирмы А фирма В должна минимизировать ее дохода. Пусть технология выпуска товара такова, что чем дольше он находится в производстве, и, следовательно, позже поступает на рынок, тем выше его качество, а реализуется товар только более высокого качества (так как цена на товары разного качества одна и та же). Доход от продажи товара в единицу времени составляет с денежных единиц.

Требуется построить функцию выигрыша фирмы А, где под выигрышем понимается в данном случае доход этой фирмы, зависящий от складывающихся ситуаций. Используя функцию выигрыша, надо составить матрицу игры для случая n = 4 и выписать конкретный вид этой матрицы, который она приобретает в случае, когда доход c = 6 денежным единицам.

Пример 4.2. На каждой из двух торговых баз ассортиментный минимум составляет один и тот же набор из n видов товаров. Каждая база должна поставить в свой магазин только один из этих видов товара. Магазины, обозначим их А и В, конкурируют между собой. Один и тот же вид товара в обоих магазинах продается по одной и той же цене. Однако, товар, поставляемый в магазин В, более высокого качества. Если магазин А завезет с базы товар Контрольная работа по теории игр вида Контрольная работа по теории игр, nотличный от товара j -го вида Контрольная работа по теории игр, n завезенного в магазин В , то товар го вида будет пользоваться спросом и магазин А от его реализации получит прибыль ci денежных единиц. Если же в магазины А и В завезены товары одинакового вида Контрольная работа по теории игр то товар Контрольная работа по теории игр вида в магазине А спросом пользоваться не будет, поскольку такой же товар, по такой же цене, но более высокого качества, можно купить в магазине В, и потому магазин А понесет убытки по транспортировке, хранению и возможно порче товара Контрольная работа по теории игр вида в размере di денежных единиц.

Требуется формализовать данную конфликтную ситуацию и построить матрицу игры при n = 3.

Антагонистические игры

Максиминные и минимаксные стратегии. Нижняя и верхняя цены игры в чистых стратегия

Рассмотрим матричную mКонтрольная работа по теории игр n игру с игроками А и В, в которой игрок А обладает m чистыми стратегиями Контрольная работа по теории игр игрок В - n чистыми стратегиями Контрольная работа по теории игр Значения функции выигрыша игрока А обозначим через aij , т. е. Контрольная работа по теории игр .

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

Контрольная работа по теории игр

расположенных в Контрольная работа по теории игр строке матрицы (3.1), в зависимости от выбранной игроком В стратегии. Предполагая поведение игрока А крайне осмотрительным, необходимо считать, что игрок В сыграет наилучшим для себя образом и на выбор игроком А стратегии Ai выберет ту стратегию Bi , при которой выигрыш игрока А окажется минимальным. Обозначим минимальный среди выигрышей (5.1) через Контрольная работа по теории игр :

Контрольная работа по теории игр

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

Контрольная работа по теории игр

то по формуле (5.2)

Контрольная работа по теории игр

Описанный принцип (3.3) или (3.4) выбора эффективной стратегии игроком А называется макашштым принципом, а выигрыш Контрольная работа по теории игр максимином. СтратегияКонтрольная работа по теории игр , соответствующая максимину Контрольная работа по теории игр , называется максминной стратегией игрока А. Множество всех (чистых) максиминных стратегий игрока А обозначим через Контрольная работа по теории игр.

Аналогично вводится критерий оценки выигрышей для игрока В. Как игрок В предполагает, что игрок А играет наилучшим для себя образом, то выигрышем игрока А будет максимальное из чисел (5.7); обозначим его через Контрольная работа по теории игр :

Контрольная работа по теории игр

и назовем показателем неэффективности стратегии Bj . Таким образом, для любой стратегии Bj игрока В наибольший его проигрыш равен Контрольная работа по теории игр. В интересах игрока В выбрать стратегию с минимальным показателем неэффективности. Наименьшее из чисел (3.5) обозначим Контрольная работа по теории игр :

Контрольная работа по теории игр

Отсюда в силу формулы (3.5) получим для Контрольная работа по теории игр выражение:

Контрольная работа по теории игр

Выбор игроком В стратегии с наименьшим показателем Контрольная работа по теории игр оправдывает то, что он назван показателем неэффективности.

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

Контрольная работа по теории игр

называется минимаксной стратегией игрока В.

Множество всех (чистых) минимаксных стратегий игрока В обозначим через Контрольная работа по теории игр

Величину Контрольная работа по теории игр называют верхней ценой игры.

Для нахождения нижней и верхней цен игры удобно матрицу игры (4.1) увеличить в размерах, приписав Контрольная работа по теории игр столбец показателей эффективности Контрольная работа по теории игр стратегий Ai игрока А и Контрольная работа по теории игр строку показателей неэффективности Контрольная работа по теории игр, стратегий Bj игрока В, В результате получим следующую матрицу:

Контрольная работа по теории игр

Теорема 5.1. Для элементов матрицы (3.8) имеют место неравенства

Контрольная работа по теории игр

и, следовательно, нижняя цена игры не больше ее верхней цены в чистых стратегиях:

Контрольная работа по теории игр

Пример 5.1. Найти нижнюю и верхнюю цены игры, а также максиминные стратегии игрока А и минимаксные стратегии игрока В в условиях примера 4.2 при Контрольная работа по теории игр денежным единицам.

Решение. Определяя показатели эффективности стратегий Ai и неэффективности стратегий Bj , мы из матрицы (4.2) получим матрицу

Контрольная работа по теории игр

из которой видно, что нижняя цена игры Контрольная работа по теории игр, а верхняя цена игрыКонтрольная работа по теории игр

Так как Контрольная работа по теории игр , то стратегии A2 и A3 игрока А являются максиминными: Контрольная работа по теории игр.

Аналогично, из равенств Контрольная работа по теории игр вытекает, что каждая из стратегий B1,B2,B3 игрока В является минимаксной: Контрольная работа по теории игр

Решение антагонистической игры с седловой точкой

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

Контрольная работа по теории игр

Из этих таблиц видно, что после первых ходов игроков А и В сложилась ситуация (A2,B2), которая устраивает игрока В (он получает максимальный выигрыш - a22 = 2), но не устраивает игрока А (он получает минимальный "выигрыш" -a22 = -2). Поэтому игрок А своим вторым ходом, меняя стратегию A2 на A3, приводит игру к ситуации (A3,B2), которую уже не приемлет игрок В. Игрок В заменяет стратегию B2 на B3 и исходом игры становится ситуация (A3,B2) и т. д. Смена ситуаций выглядит следующим образом:

Контрольная работа по теории игр

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

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

Контрольная работа по теории игр

В данном случае максиминной стратегией игрока А является стратегия A2 , а минимаксной стратегией игрока В стратегия B3. Если игрок А придерживается своей максиминной стратегии A2, то игрок В должен выбрать свою минимаксную B3 с тем, чтобы выигрыш игрока А (или, что то же, проигрыш игрока В) был минимальным a23 = 0,4 (во 2-й строке матрицы (4.1)). На это игрок А должен ответить выбором опять же стратегии A2, чтобы получить максимальный (в 3-м столбце) выигрыш a23 = 0,4. Ответным ходом игрок В опять выбирает стратегию B3 и т. д.

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

Нижняя и верхняя цены игры совпадают:

Контрольная работа по теории игр

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

Пусть имеем mКонтрольная работа по теории игрn-игру, игроки А и В которой обладают соответственно следующими множествами чистых стратегий: Контрольная работа по теории игр. Пусть матрица этой игры имеет вид (5.12).

Ситуация Контрольная работа по теории игр (сложившаяся в результате выбора игроками А и В соответственно стратегий Контрольная работа по теории игр,) называется удовлетворительной (приемлемой, допустимой) для игрока А, если

Контрольная работа по теории игр

и удовлетворительной для игрока В, если

Контрольная работа по теории игр

Ситуация Контрольная работа по теории игрназывается равновесной, или ситуацией равновесия, или устойчивой, или седловой, точкой игры, если она удовлетворительна для каждого из игроков А и В, т.е. если выполняются неравенства (4.2) и (4.3):

Контрольная работа по теории игр

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

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

Соотношения между множествами оптимальных стратегий каждого игрока, с одной стороны, и множествами максиминных стратегий игрока А и минимаксных стратегий игрока В, с другой стороны, устанавливается следующей теоремой.

Теорема 6.6. Справедливы следующие утверждения.

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

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

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

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

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

Контрольная работа по теории игр

То же относится и к смешанным стратегиям игрока B:

Контрольная работа по теории игр

Обозначим через

Контрольная работа по теории игр

Каждую чистую стратегию Контрольная работа по теории игр, игрока А можно рассматривать как смешанную стратегию

Контрольная работа по теории игр

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

Контрольная работа по теории игр

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

Руководствуясь приведенными определениями, мы видим, что правая часть равенства (у.2) является выпуклой комбинацией орт Контрольная работа по теории игр (см. (5.1)) и потому множество SA всех смешанных стратегий геометрически представляет собой фундаментальный (m -1)-мерный симплекс с m вершинами в точках Контрольная работа по теории игр , представляющих чистые стратегии (выпуклая оболочка, натянутая на чистые стратегии).

Примеры симплексов

 

Контрольная работа по теории игр

Функции выигрыша в смешанных стратегиях

Если игроки А и В независимо друг от друга выбрали смешанные стратегии соответственно Контрольная работа по теории игр , то упорядоченная пара (Р, Q) называется ситуацией в смешанных стратегиях. В условиях ситуации (Р, Q) в смешанных стратегиях чистые стратегии Ai и Bj выбираются независимо друг от друга случайным образом с вероятностями соответственно pi и qj . Поэтому вероятность совместного выбора чистых стратегий (Ai ,Bj) равна произведению их вероятностей: piqj. Но в ситуации (Ai ,Bj) в чистых стратегиях игрок А получает выигрыш aij. Вероятность этого выигрыша совпадает с вероятностью ситуации (Ai ,Bj), т. е. равна piqj. Таким образом, выигрыш игрока А в ситуации (Р, Q) в смешанных стратегиях представляет собой дискретную случайную величину, принимающую значения aij с вероятностью piqj. Тогда средний выигрыш игрока А в ситуации (Р, Q) в смешанных стратегиях есть математическое ожидание указанной случайной величины

Контрольная работа по теории игр

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

Контрольная работа по теории игр

где Контрольная работа по теории игр

Форма (6.2) задания функции выигрыша в смешанных стратегиях называется координатной. Функцию Н можно задать и в матричной форме

Контрольная работа по теории игр

Теорема 6.1. Для каждой смешанной (в частности, чистой) стратегии игрока А существует (достигается)

Контрольная работа по теории игр

Для каждой смешанной (в частности, чистой) стратегии е8в игрока В существует (достигается)

Контрольная работа по теории игр

Число Контрольная работа по теории игр, определенное равенством (6.2) (существование которого доказано в теореме 6.1), назовем показателем эффективности смешанной стратегии Контрольная работа по теории игр игрока А относительно множества SB смешанных стратегий игрока В.

Если в этом определении множество смешанных стратегий SB игрока В заменить на множество Контрольная работа по теории игр его чистых стратегий, то получим определение показателя эффективности смешанной стратегии Контрольная работа по теории игр игрока А относительно множества Контрольная работа по теории игр чистых стратегий игрока В:

Контрольная работа по теории игр

Теорема 6.2. Показатели эффективности любой смешанной (в частности, чистой) стратегии Контрольная работа по теории игр игрока А относительно множеств Контрольная работа по теории игр и SB чистых и смешанных стратегий противника В равны, т.е.

Контрольная работа по теории игр

ЧислоКонтрольная работа по теории игр, определенное равенством (6.3), назовем показателем неэффективности смешанной стратегии Контрольная работа по теории игр игрока В относительно множества SA смешанных стратегий игрока А, а число

Контрольная работа по теории игр

показателем неэффективности смешанной стратегии Q игрока В относительно множества Контрольная работа по теории игр чистых стратегий игрока А.

Теорема 6.3. Показатели неэффективности любой смешанной (в частности, чистой) стратегии Контрольная работа по теории игр игрока В относительно множеств Контрольная работа по теории игри SA чистых и смешанных стратегий игрока А равны, т.е.

Контрольная работа по теории игр

Нижней ценой (или максимином) матричной игры в смешанных стратегиях называется величина

Контрольная работа по теории игр

Верхней ценой (или минимаксом) матричной игры в смешанных стратегиях называется величина

Контрольная работа по теории игр

Те о р е м а 6.4. Для любой конечной матричной игры существуют нижняя и верхняя цены игры в смешанных стратегиях. Соотношения между нижними и верхними ценами игры в чистых и смешанных стратегиях устанавливаются в следующей теореме.

Т е о р е м а 6.5. Нижняя цена игры а и верхняя цена игры (3 в чистых стратегиях, нижняя цена игры V и верхняя цена игры V в смешанных стратегиях удовлетворяют следующему неравенству

Контрольная работа по теории игр

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

Если нижняя и верхняя цены игры в смешанных стратегиях совпадают, то их общее значение

Контрольная работа по теории игр

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

Контрольная работа по теории игр

(и тогда это общее значение равно H(P0, Q0), называются оптимальными смешанными стратегиями соответственно игроков А и В.

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

Нетрудно показать, что

Контрольная работа по теории игр

т. е. цена игры в смешанных стратегиях V не меньше нижней цены игры в чистых стратегиях а и не больше верхней цены игры в чистых стратегиях Контрольная работа по теории игр . Полным решение игры в смешанных стратегиях называется совокупностьКонтрольная работа по теории игрмножеств оптимальных стратегий игроков и цены игры. Любая пара оптимальных стратегий Po,Q0 и цена игры V образуют частное решение в смешанных стратегиях.

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

Теорема 7.1 (основная теорема матричных игр фон Неймана). Любая матричная игра имеет решение в смешанных стратегиях, т. е. существуют цена игры в смешанных стратегиях V и оптимальные смешанные стратегии P0 и Q0 соответственно игроков А и В, т. е.

Контрольная работа по теории игр

Теорема 7.2 (свойство равнозначности седловых точек). Если Контрольная работа по теории игр седловые точки функции f (x, y)на декартовом произведении XКонтрольная работа по теории игрY, то значения данной функции в этих точках совпадают:

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

Контрольная работа по теории игр,

и выполнялось их равенство

Контрольная работа по теории игр

Пример 7.1. Пусть Контрольная работа по теории игр т.е. х и у скалярные переменные, и точки (x', y') и (x", y"), которые графически изображаются двумя вершинами прямоугольника (см. рис. 7.1), являются седловыми точками функции f (x, y) . Тогда по свойству взаимозаменяемости, сформулированному в теореме 9.3, остальные две вершины этого прямоугольника (x', y") и (x", y') также являются седловыми. В связи с этим иногда свойство взаимозаменяемости седловых точек называют свойством "прямоугольности".

Если, в частности, x' = x," то точки (x', y') , (x", y")лежат на одной вертикали x = x' = x" а если y' = y" то эти точки лежат на одной горизонтали y = y' = y" ; поэтому в этих случаях взаимозамена неравных координат этих точек приводит к паре тех же точек и прямоугольник вырождается в отрезок.

Контрольная работа по теории игр

Рис. 7.1

Пример 9.3. Применяя критерий (теорема 9.4), определить, существует ли у функции

Контрольная работа по теории игр

на декартовом квадрате [0,1]2 седловые точки.

Решение. Очевидно, что

Контрольная работа по теории игр

и, следовательно,

Контрольная работа по теории игр

Также очевидно, что

Контрольная работа по теории игр

и потому

Контрольная работа по теории игр

Итак, имеем

Контрольная работа по теории игр

т.е. выполняются необходимые условия и потому на квадрате [0,1]2 существуют седловые точки.

Критерии и свойства оптимальных стратегий

Т е о р е м а 8.1. Пусть Vцена игры, H(P,Q) функция выигрыша, За и множества смешанных стратегий соответственно игроков А и В.

1. Для того чтобы стратегия P0 игрока А была оптимальной, необходимо и достаточно, чтобы выполнялось неравенство

Контрольная работа по теории игр

т.е. выбор игроком А оптимальной стратегии P0 гарантирует ему выигрыш Контрольная работа по теории игр, не меньший цены игры V, при любой стратегии Q игрока В.

2. Для того чтобы стратегия Q0 игрока В была оптимальной, необходимо и достаточно, чтобы выполнялось неравенство

Контрольная работа по теории игр

т. е. выбор игроком В одной из своих оптимальных стратегий гарантирует ему проигрыш, не больший цены игры У, при любой стратегии Р игрока А.

Теорема 8.2. Пусть V цена игры, H(P,Q) функция выигрыша, Контрольная работа по теории игр мnножества чистых стратегий соответственно игроков А и В.

1. Для того чтобы стратегия P0 игрока А была оптимальной, необходимо и достаточно, чтобы

Контрольная работа по теории игр

2. Для того чтобы стратегия Q0 игрока В была оптимальной, необходимо и достаточно, чтобы

Контрольная работа по теории игр

Пример. Рассмотрим матричную игру2Контрольная работа по теории игр3 с платежной матрицей

Контрольная работа по теории игр

и смешанные стратегии Контрольная работа по теории игр соответственно игроков А и В. В упражнении 9.2 было отмечено, что из примера 8.3 по теореме фон Неймана следует оптимальность стратегии P0 и Q0. Установим этот факт на основании теоремы 8.2.

Имеем, что цена игры Контрольная работа по теории игр

Получаем следующие значения функции выигрыша:

Контрольная работа по теории игр

Таким образом, Контрольная работа по теории игр и потому по достаточной части утверждения 1 теоремы 8.2 (см. (10.10)) стратегия Контрольная работа по теории игр является оптимальной стратегией игрока А.

Также имеют место неравенства Контрольная работа по теории игр, (которые на самом деле являются равенствами) и, следовательно, по достаточной части утверждения 2 теоремы 8.2 стратегия Контрольная работа по теории игр является оптимальной стратегией игрока В.

Пусть Контрольная работа по теории игр оптимальная смешанная стратегия игрока А. В общем случае, некоторые из вероятностей Контрольная работа по теории игр могут быть равными нулю. Если Контрольная работа по теории игр, где i одно из чисел 1,...,m, то в оптимальной смешанной стратегии Контрольная работа по теории игр чистая стратегия Ai не участвует и потому называется пассивной. Чистые стратегии Ai , входящие в оптимальную стратегию Р° с положительной вероятностью Контрольная работа по теории игр, называются активными стратегиями игрока А. Таким же образом определяются активные стратегии игрока В. Понятно, что оптимальная чистая стратегия является активной. Следующая теорема об активных стратегиях играет существенную роль в решении игр.

Теорема 8.3(об активных стратегиях). Пусть Vцена игры, Контрольная работа по теории игр оптимальные стратегии соответственно игроков А и В. Тогда справедливы следующие утверждения.

1. Для любой активной стратегии Контрольная работа по теории игр игрока А выполняется равенство

Контрольная работа по теории игр

2. Для любой активной стратегии Контрольная работа по теории игр игрока В выполняется равенство

Контрольная работа по теории игр

Принцип доминирования

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

Контрольная работа по теории игр

Каждой смешанной (в частности, чистой) стратегии Контрольная работа по теории игр игрока А поставим в соответствие строку

Контрольная работа по теории игр

Строку (9.1) можно представить так:

Контрольная работа по теории игр

Обратно, каждой выпуклой комбинации (9.2) строк матрицы А с коэффициентами Контрольная работа по теории игр поставим в соответствие смешанную стратегию Контрольная работа по теории игр pигрока А.

Таким образом, между смешанными (в том числе и чистыми) стратегиями Контрольная работа по теории игр игрока А и выпуклыми комбинациями

Контрольная работа по теории игр

строк Контрольная работа по теории игр матрицы А устанавливается взаимно-однозначное соответствие

Контрольная работа по теории игр

Из (9.1) или (9.3) ясно, что каждой чистой стратегии Контрольная работа по теории игр игрока А ставится во взаимно-однозначное соответствие Контрольная работа по теории игр строка Контрольная работа по теории игр матрицы А.

Если для двух выпуклых комбинаций строк матрицы А

Контрольная работа по теории игр

выполняются неравенства

Контрольная работа по теории игр

то говорят, что строка (9.5) доминирует строку (9.4), а строка (9.4) доминируется строкой (9.5). Таким образом, строка (11.5) — доминирующая строку (9.4), а строка (9.4) — доминируемая строкой (9.5).

Если каждое из неравенств (9.6) является равенством, то строки (9.4) и (9.5) называют дублирующими друг друга. Каждая из двух дублирующих строк является одновременно и доминируемой, и доминирующей другую.

Если каждое из неравенств (9.6) является строгим, то говорят, что строка (9.5) строго доминирует строку (9.4), а строка (9.4) строго доминируется строкой (9.5), или строка (9.5) является строго доминирующей строку (9.4), а строка (9.4) является строго доминируемой строкой (9.5). Аналогичная терминология используется и для соответствующих стратегий игрока А. А именно, если строка (9.5) доминирует, соответственно дублирует, соответственно строго доминирует строку (9.4), то говорят, что стратегия Контрольная работа по теории игр доминирует, соответственно дублирует, соответственно строго доминирует стратегию Контрольная работа по теории игр

Так как элементами строк, соответствующих по (9.3) смешанным стратегиям, являются выигрыши игрока А (см. (9.1)), то из данных определений понятно, что для игрока А дублирующие стратегии равнопредпочтительны, а доминируемая не дублирующая стратегия заведомо для него невыгодна.

Аналогично, каждой смешанной (в частности, чистой) стратегии Контрольная работа по теории игр игрока В поставим в соответствие столбец

Контрольная работа по теории игр

Если для двух выпуклых комбинаций столбцов матрицы А

Контрольная работа по теории игр

справедливы неравенства

Контрольная работа по теории игр

то говорят, что столбец (9.8) (стратегия Контрольная работа по теории игр) доминирует столбец (9.9) (стратегию Контрольная работа по теории игр) а столбец (9.9) (стратегия Контрольная работа по теории игр ) доминируется столбцом (9.8) (стратегией Контрольная работа по теории игр ).

В случае, когда каждое неравенство (9.10) является равенством, столбцы (9.8) и (9.9) (стратегии Контрольная работа по теории игр ) называются дублирующими. Если каждое неравенство (9.10) является строгим, то столбец (9.8) (стратегия Контрольная работа по теории игр) называется строго доминирующим (строго доминирующей) столбец (9.9) (стратегию Контрольная работа по теории игр ), а столбец (11.11) (стратегия Q ) строго доминируемым (строго доминируемой) столбцом (11.10) (стратегией Контрольная работа по теории игр).

Теорема 9.1. Справедливы следующие предложения. 1 .Если k -я строка, Контрольная работа по теории игр, mматрицы А игры доминируется некоторой выпуклой комбинацией остальных ее строк, то существует оптимальная смешанная стратегия Контрольная работа по теории игригрока А, в которой k -я чистая стратегия Ak выбирается им с нулевой вероятностью, т.е Контрольная работа по теории игр

2. Если k -я строка, Контрольная работа по теории игр, mматрицы A игры строго доминируется некоторой выпуклой комбинацией остальных ее строк, то в любой оптимальной смешанной стратегии Контрольная работа по теории игригрока А чистая k -я стратегия Ak выбирается им с нулевой вероятностью, т.е. Контрольная работа по теории игр .

3. Если Контрольная работа по теории игр столбец, Контрольная работа по теории игр, nматрицы А игры доминируется некоторой выпуклой комбинацией остальных ее столбцов, то существует оптимальная смешанная стратегия Контрольная работа по теории игр игрока В, в которой Контрольная работа по теории игр

4. Если Контрольная работа по теории игр столбец, Контрольная работа по теории игр , nматрицы А игры строго доминируется некоторой выпуклой комбинацией остальных ее столбцов, то в любой оптимальной смешанной стратегии Контрольная работа по теории игр игрока В чистая Контрольная работа по теории игр стратегия Bl выбирается им с нулевой вероятностью, т е. Контрольная работа по теории игр.

Следствие 9.1.

1. Если k -я строка матрицы игры доминируется (строго доминируется) некоторой другой строкой, то существует (любая) оптимальная смешанная стратегия игрока А, в которую чистая стратегия Ak входит с нулевой вероятностью.

2. Если Контрольная работа по теории игр столбец матрицы игры доминируется (строго доминируется) некоторым другим столбцом, то существует (любая) оптимальная смешанная стратегия игрока В, в которую чистая стратегия l B входит с нулевой вероятностью.

Следствие 9.2 (о дублирующих чистых стратегиях). Одну из двух дублирующих чистых стратегий можно удалить.

Пример 11.1. Рассмотрим игру 3x5 с матрицей

Контрольная работа по теории игр

В данной матрице B2 и B5 дублирующие стратегии игрока В. Поэтому в соответствии со следствием 9.2 один из этих столбцов можно удалить. Удалим, например, 5-й столбец. В оставшейся матрице 3-й Столбец строго, а 4-й столбец нестрого доминируются 1-м столбцом. Поэтому можно удалить также 3-й и 4-й столбцы. В результате получим матрицу

Контрольная работа по теории игр

2-я строка матрицы (9.12) строго доминируется выпуклой комбинацией 1-й и 3-й строк с коэффициентами Контрольная работа по теории игр

Контрольная работа по теории игр

Поэтому нужно отбросить 2-ю строку. В результате получим матрицу

Контрольная работа по теории игр

Нижняя цена в чистых стратегиях игры с матрицей (11.25) Контрольная работа по теории игр, а верхняя цена Контрольная работа по теории игр. Так как Контрольная работа по теории игр, то решение надо искать в смешанных стратегиях. Предположим, что Контрольная работа по теории игр оптимальные стратегии игроков и V цена игры с матрицей (9.13). Тогда по необходимым условиям оптимальности стратегий, сформулированным в теореме 9.2, имеем

Контрольная работа по теории игр

Умножив 1-е неравенство системы (9.14) на 2 и прибавив ко 2-му, получим

Контрольная работа по теории игр

Умножив 3-е неравенство системы (9.4) на 2 и прибавив к 4-му, получим

Контрольная работа по теории игр

Из неравенств (9.15) и (9.16) следует равенство Контрольная работа по теории игр. Подставим найденное значение V в систему (9.15):

Контрольная работа по теории игр

Из первых двух уравнений системы (11.29): Контрольная работа по теории игр, а из вторых двух уравнений: Контрольная работа по теории игр

Учитывая удаленные столбцы и строку для исходной игры с матрицей (11.11), получим следующее (частное) решение:

Контрольная работа по теории игр

Поскольку 4-й столбец матрицы (11.23) нестрого доминировался 1-м столбцом, то могут существовать и другие оптимальные стратегии игрока В, в которых чистая стратегия B1 будет входить с положительной вероятностью.

Игры 2хп

Рассмотрим игру с матрицей

Контрольная работа по теории игр

В этой игре игрок А обладает двумя чистыми стратегиями A1 и A2, а игрок В имеет п чистых стратегий Контрольная работа по теории игр

Известно, что показатель эффективности стратегии Контрольная работа по теории игр

Контрольная работа по теории игр

Если Контрольная работа по теории игр , pпоскольку Контрольная работа по теории игр. Тогда Контрольная работа по теории игр будет выражаться формулой

Контрольная работа по теории игр

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

Стратегия Контрольная работа по теории игр, удовлетворяющая равенству

Контрольная работа по теории игр

где, напомним, SA множество всех смешанных (в том числе и чистых) стратегий игрока А, является (по основной теореме 8.1 матричных игр фон Неймана, см. [9])) оптимальной, т.е. абсцисса Контрольная работа по теории игр максимальной (наивысшей) точки нижней огибающей Контрольная работа по теории игр определяет оптимальную стратегию Контрольная работа по теории игр, придерживаясь которой игрок А выбирает свои чистые стратегии случайным образом, причем стратегию A1 с вероятностью Контрольная работа по теории игр , а стратегию A2 с вероятностью p0.

По теореме фон Неймана

Контрольная работа по теории игр

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

1. Берем горизонтальный отрезок [0,1].

2. Через концы отрезка [0,1] проводим к нему два перпендикуляра: левый и правый.

3. На левом перпендикуляре, лежащем на вертикальной числовой оси, от точки 0 его пересечения с отрезком [0,1] откладываем все элементы первой строки матрицы А.

4. На правом перпендикуляре от точки 1 его пересечения с отрезком [0,1] откладываем (как на вертикальной числовой оси) все элементы второй строки матрицы А.

З а м е ч а н и я к п у н к т а м 1, 3, 4. Масштабы на левом и правом перпендикулярах должны быть одинаковыми, не обязательно совпадающими с масштабом горизонтального отрезка [0,1]. 5. Каждую пару точек, изображающих элементы Контрольная работа по теории игр, стоящие в j -м столбце матрицы А, соединяем отрезком Контрольная работа по теории игр Таким образом, будут построены n отрезков, представляющих собой графики n линейных функций

Контрольная работа по теории игр

6. Если все отрезки Контрольная работа по теории игр неубывающие (имеют неотрицательный наклон Контрольная работа по теории игр то стратегия A2 доминирует стратегию A1. Если все отрезки Контрольная работа по теории игр nвозрастающие (имеют положительный наклон Контрольная работа по теории игр то стратегия A2 строго доминирует стратегию A1.

7. Если все отрезки Контрольная работа по теории игр, nневозрастающие (имеют неположительный наклон): Контрольная работа по теории игр, то стратегия A1 доминирует стратегию A2. Если все отрезки Контрольная работа по теории игр, nубывающие (имеют отрицательный наклон): Контрольная работа по теории игрnто стратегия A1 строго доминирует стратегию A2.

8. Если отрезок Контрольная работа по теории игрaa лежит не ниже отрезкаКонтрольная работа по теории игр, Контрольная работа по теории игр ,то стратегия Bj2 доминирует стратегию Bj1 . Если отрезок Контрольная работа по теории игрaa лежит выше отрезка Контрольная работа по теории игр, то стратегияBj2 строго доминирует стратегию Bj1 .

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

10. На нижней огибающей находим максимальную (наивысшую) точку (или точки).

11. Абсцисса p0 этой точки (удовлетворяющая равенству (10.1)) является вероятностью выбора игроком А чистой стратегии А2 в оптимальной смешанной стратегии Контрольная работа по теории игр

12. Ордината наивысшей точки нижней огибающей является ценой игры V (см. 10.2)).

13. Верхний из двух концов нижней огибающей (лежащих на перпендикулярах) есть нижняя цена игры в чистых стратегиях Контрольная работа по теории игр .

14. Нижний из верхних концов отрезков Контрольная работа по теории игр, nесть верхняя цена игры в чистых стратегиях Контрольная работа по теории игр .

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

В этом случае чистая стратегия игрока В, номер которой совпадает со вторым индексом седловой точки, является оптимальной.

Контрольная работа по теории игр

Рис. 10.1

На рис. 10.1 из n отрезков Контрольная работа по теории игр, nуказаны три, которые принимают участие в конструировании нижней огибающей, выделенной жирной линией; N максимальная точка этой огибающей; р° абсцисса точки N, следовательно Контрольная работа по теории игр оптимальная смешанная стратегия игрока А: цена игры V равна ординате точки N; нижняя цена игры в чистых стратегиях Контрольная работа по теории игр ; верхняя цена игры в чистых стратегиях Контрольная работа по теории игр ; на рисунке видно, что Контрольная работа по теории игр

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

Контрольная работа по теории игр

и, следовательно,

Контрольная работа по теории игр

а цепа игры

Контрольная работа по теории игр

Т е о р е м а 16.2. Пусть через максимальную точку N нижней огибающей отрезков Контрольная работа по теории игр , пnорождаемых чистыми стратегиямиКонтрольная работа по теории игр , иnгрока В, проходят два каких-либо отрезка Контрольная работа по теории игрКонтрольная работа по теории игр

Для того чтобы смешанная стратегия Контрольная работа по теории игр игрока В, где

Контрольная работа по теории игр

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

Игры mКонтрольная работа по теории игр2

В этом параграфе рассмотрим игру mКонтрольная работа по теории игр2, в которой игрок A обладает m чистыми стратегиями Контрольная работа по теории игр а игрок Bдвумя чистыми стратегиями B1 и B2.

Матрица игры имеет вид

Контрольная работа по теории игр

Известно, что показатель неэффективности Контрольная работа по теории игр стратегии Контрольная работа по теории игр Контрольная работа по теории игр игрока B имеет вид

Контрольная работа по теории игр

Если обозначить Контрольная работа по теории игр и

Контрольная работа по теории игр

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

Если стратегия Контрольная работа по теории игр удовлетворяет равенству

Контрольная работа по теории игр

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

По той же теореме фон Неймана цена игры

Контрольная работа по теории игр

т. е. цена игры V равна ординате минимальной точки верхней огибающей.

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

Контрольная работа по теории игр

Рис. 11.1

Алгоритм "В"

1. Берем горизонтальный отрезок [0,1].

2. Через концы отрезка [0,1] проводим к нему два перпендикуляра: левый и правый.

3. На левом перпендикуляре, лежащем на вертикальной числовой оси, от точки 0 его пересечения с отрезком [0,1] откладываем все элементы первого столбца матрицы А.

4. На правом перпендикуляре от точки 1 его пересечения с отрезком [0,1] откладываем (как на вертикальной числовой оси) все элементы второго столбца матрицы А.

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

Контрольная работа по теории игр

6. Если все отрезки Контрольная работа по теории игр, имеют неотрицательный наклон, т. е. положительный или нулевой (другими словами, все отрезки Контрольная работа по теории игрнеубывающие: Контрольная работа по теории игр то стратегия B1, доминирует стратегию B2. Если все отрезки Контрольная работа по теории игр, имеют положительный наклон, т. е. являются возрастающими: Контрольная работа по теории игр, то стратегия B1 строго доминирует стратегию B2.

7. Если все отрезки Контрольная работа по теории игр, имеют неположительный наклон, т. е. отрицательный или нулевой (другими словами, все отрезки Контрольная работа по теории игр, невозрастающие: Контрольная работа по теории игр, то стратегия B2 доминирует стратегию B1 . Если все отрезки Контрольная работа по теории игр, имеют отрицательный наклон, т. е. являются убывающими: Контрольная работа по теории игр, то стратегия B2 строго доминирует стратегию B1.

8. Отрезок Контрольная работа по теории игр 2лежит не ниже отрезка Контрольная работа по теории игр, то стратегия Контрольная работа по теории игрдоминирует стратегиюКонтрольная работа по теории игр . Если отрезокКонтрольная работа по теории игрaa лежит выше отрезка Контрольная работа по теории игр, то стратегия Контрольная работа по теории игр строго доминирует стратегиюКонтрольная работа по теории игр .

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

10. На верхней огибающей находим минимальную (наинизшую) точку (точки).

11. Абсцисса q0 минимальной точки (удовлетворяющая равенству (17.2)) является вероятностью случайного выбора игроком В чистой стратегии В2 в оптимальной смешанной стратегии Контрольная работа по теории игр.

12. Ордината минимальной точки верхней огибающей является ценой игры V (см. (17.3)).

13. Верхний из нижних концов отрезков Контрольная работа по теории игр, является нижней ценой игры в чистых стратегиях Контрольная работа по теории игр .

14. Нижний из концов верхней огибающей (лежащих на перпендикулярах) является верхней ценой игры в чистых стратегиях Контрольная работа по теории игр .

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

На рис. 17.1 из т отрезков Контрольная работа по теории игр, указаны четыре Контрольная работа по теории игр , первые три из которых принимают участие в конструировании верхней огибающей, выделенной" жирной линией. Точка М минимальная точка этой верхней огибающей, имеющая своей абсциссой q0 . Поэтому Контрольная работа по теории игр оптимальная смешанная стратегия игрока В.

Ордината точки М есть цена игры V. Нижняя цена игры в чистых стратегияхКонтрольная работа по теории игрa , верхняя цена игры в чистых стратегияхКонтрольная работа по теории игр . Так как среди отрезков Контрольная работа по теории игр имеются отрезки с положительным и отрицательным наклонами (например, отрезокКонтрольная работа по теории игримеет положительный наклон, а отрезок Контрольная работа по теории игр отрицательный), то стратегия В2 не доминирует и не доминируется стратегией B1. Так как отрезки Контрольная работа по теории игр лежат выше отрезка Контрольная работа по теории игр , то каждая из стратегий Контрольная работа по теории игр строго доминирует стратегию Контрольная работа по теории игр Оптимальную стратегию Контрольная работа по теории игр игрока В и цену игры V можно подсчитать и по формулам, которые даются в следующей теореме.

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

Контрольная работа по теории игр

и, следовательно,

Контрольная работа по теории игр

а цена игры

Контрольная работа по теории игр

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

Для того чтобы смешанная стратегия Контрольная работа по теории игр игрока А, где

Контрольная работа по теории игр

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

Игры m x n и их решение с помощью линейного программирования

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

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

Контрольная работа по теории игр

положительны:

Контрольная работа по теории игр

Условие (12.1) не умаляет общности, поскольку матрица с любыми элементами может быть приведена к матрице с положительными элементами аффинным преобразованием

Контрольная работа по теории игр

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

Теорема 20.1. Решение матричной игры тхп с матрицей А, элементы которой удовлетворяют условию (12.1), эквивалентно решению следующей пары двойственных друг другу стандартных задач линейного программирования: найти Контрольная работа по теории игр , при ограничениях

Контрольная работа по теории игр

найти Контрольная работа по теории игр при ограничениях

Контрольная работа по теории игр

Точнее говоря, если Контрольная работа по теории игр оптимальное решение задачи (12.2), Контрольная работа по теории игр оптимальное решение задачи (20.3), то

Контрольная работа по теории игр

- цена игры с матрицей А,

Контрольная работа по теории игр

- оптимальная стратегия игрока А,

Контрольная работа по теории игр

- оптимальная стратегия игрока В.

Пример. Необходимо найти решение матричной игры 3x3 с матрицей

Контрольная работа по теории игр

Чтобы сделать все aij неотрицательными, прибавим ко всем элементам матрицы L = 5. Получим матрицу:

Контрольная работа по теории игр

При этой цена игры увеличится на 5, а решение не изменится. Определим оптимальную стратегию Контрольная работа по теории игр . Условия (12.3) имеют вид:

Контрольная работа по теории игр

где Контрольная работа по теории игр

Чтобы избавиться от знаков неравенства, введем фиктивные переменные z1,z2,z3; условия (12.6) запишутся в виде:

Контрольная работа по теории игр

Линейная форма Ф имеет вид:

Контрольная работа по теории игр

и должна быть сделана как можно меньше.

Если все три стратегии В являются «полезными», то все три фиктивные переменные z1,z2,z3 обратятся в нуль (т. е. выигрыш, равный цене игры Контрольная работа по теории игр , будет достигаться при каждой стратегии Bj ). Но мы пока не имеем оснований утверждать, что все три стратегии являются «полезными». Чтобы проверить это. попытаемся выразить форму Ф через фиктивные переменные z1,z2,z3 и посмотрим, добьемся ли мы, полагая их рапными нулю, минимума формы. Для этого разрешим уравнения (5.7) относительно переменных Контрольная работа по теории игр (т. е. выразим Контрольная работа по теории игр через фиктивные переменные z1,z2,z3):

Контрольная работа по теории игр

Складывая Контрольная работа по теории игр получим

Контрольная работа по теории игр

В выражении (12.9) коэффициенты при всех z положительны; значит, любое увеличение z1,z2,z3 сверх нуля может привести только к увеличению формы Ф, а мы хотим, чтобы она была минимальна. Следовательно, значениями z1,z2,z3 обращающими форму (12.9) в минимум, являются Контрольная работа по теории игр

Подставляя их в формулу (12.9), находим минимальное значение формы

Контрольная работа по теории игр

откуда цена игры Контрольная работа по теории игр

Подставляя нулевые значения z1,z2,z3 в формулы (5.8), находим:

Контрольная работа по теории игр

или, умножая их наКонтрольная работа по теории игр

Контрольная работа по теории игр

Таким образом, оптимальная стратегия А найдена:

Контрольная работа по теории игр

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

Контрольная работа по теории игр

Для этого воспользуемся нашими любыми двумя «полезными» стратегиями (например, A2 и A3) и напишем уравнения:

Контрольная работа по теории игр

откуда Контрольная работа по теории игр .Оптимальная стратегия противника будет такой же, как наша:

Контрольная работа по теории игр

Теперь вернемся к первоначальной (не преобразованной) игре. Для этого нужно только от цены игры Контрольная работа по теории игр отнять величину L = 5, прибавленную к элементам матрицы. Получим цену исходной игры Контрольная работа по теории игр. Следовательно, оптимальные стратегии обеих сторон обеспечивают средний выигрыш, равный нулю; игра в одинаковой мере выгодна или невыгодна для обеих сторон.

Игры в условиях риска

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

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

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

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

Пусть игрок А имеет т возможных стратегий Контрольная работа по теории игр а природа П может находиться в одном из п состояний Контрольная работа по теории игр, которые можно рассматривать как ее "стратегии".

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

Контрольная работа по теории игр

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

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

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

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

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

Контрольная работа по теории игр

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

Для характеризации степени удачности применения игроком А стратегии Ai , при состоянии Пj природы П вводят понятие "риска". Риском rij игрока А при выборе им стратегии Ai в условиях состояния Пj природы П называется разность между показателем благоприятности Bi состояния природы Пj и выигрышем aij, т. е. разность между выигрышем, который игрок А получил бы, если бы знал заранее, что природа примет состояние Пj , и выигрышем, который он получит при этом же состоянии Пj , выбрав стратегию Ai т. е.

Контрольная работа по теории игр

Таким образом, риск Контрольная работа по теории игр игрока А при применении стратегии Ai в условиях состояния природы Пj есть упущенная им возможность максимального выигрыша Контрольная работа по теории игр при этом состоянии природы. Эта упущенная возможность определяется, как это следует из (13.2), невыигранной частью величины максимального выигрыша Контрольная работа по теории игр

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

Из формул (13.1) и (13.2) следует, что риск Контрольная работа по теории игр для любых Контрольная работа по теории игр и Контрольная работа по теории игр неотрицателен:

Контрольная работа по теории игр

Можно установить и верхнюю границу рисков для каждого состояния природы Пj . Для этого введем в рассмотрение величину

Контрольная работа по теории игр

представляющую собой наименьший выигрыш игрока А при состоянии природы Пj . Тогда из (13.2)

Контрольная работа по теории игр

Разность Контрольная работа по теории игр естественно назвать колебанием выигрышей при состоянии природы Контрольная работа по теории игр

Если Контрольная работа по теории игр, т. е. стратегия Ai при состоянии природы Пj является безрисковой.

Если Контрольная работа по теории игр, то риск rij , который по определению (13.2) равен Контрольная работа по теории игр является максимальным (см. (13.5)). Следовательно, по критерию риска стратегия Ai этом случае наихудшая.

Для матрицы А матрица рисков RA имеет ту же размерность и следующий вид:

RA =

Контрольная работа по теории игр

Отметим, что матрица выигрышей А однозначно порождает матрицу рисков RA, поскольку каждый риск rij однозначно определяется по формуле (13.2) соответствующими показателем благоприятности Контрольная работа по теории игрсостояния природы Пj и выигрышем aij . Обратное неверно: одна и та же матрица рисков может соответствовать разным матрицам выигрышей.

Пример 1. Рассмотрим игру с природой, для которой известна матрица игры

Контрольная работа по теории игр

Необходимо построить матрицу рисков.

Дополним матрицу игры строкой показателей благоприятности состояний природы

Контрольная работа по теории игр

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

Контрольная работа по теории игр

Матрица рисков проясняет некоторые нюансы рассматриваемой игры с природой. Так, если игрок А выбрал стратегию А6 (см. матрицу выигрышей (13.6)), то при состояниях природы П1 и П3 он получает одинаковые выигрыши Контрольная работа по теории игр. Однако эти выигрыши не являются равноценными в смысле рисков, поскольку удачность выбора стратегии А6 по отношению к состояниям природы П1 и П3 разная. Благоприятность состояния природы П1 для возможности увеличения выигрыша равна Контрольная работа по теории игр, а состояния П3 равнаКонтрольная работа по теории игр (см. последнюю строку матрицу (13.6)). Поэтому риски игрока А при выборе стратегии А6 и при состояниях природы П1 и П3 соответственно равны Контрольная работа по теории игр (см. матрицу рисков (13.7)). Другими словами, при состоянии природы П1 игрок А мог выиграть по максимуму Контрольная работа по теории игрединиц выигрыша, а выбрав стратегию А6 , выиграл всего Контрольная работа по теории игр единиц, потеряв Контрольная работа по теории игр возможных единиц. При состоянии природы П3 игрок А мог выиграть максимум Контрольная работа по теории игр единиц выигрыша, а выиграл, придерживаясь стратегии Контрольная работа по теории игр единицы, потеряв всего Контрольная работа по теории игр единицу. Таким образом, выбор стратегии А6 по отношению к состоянию природы П3 более удачлив, чем по отношению к состоянию природы П1. Именно эту ситуацию и отражает матрица рисков (13.7).

Матрица выигрышей (13.6) однозначно определяет матрицу рисков (13.7). Обратное, однако, неверно.

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

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

Рассмотрим игру с природой, в которой статистик-игрок А имеет т возможных стратегий Контрольная работа по теории игр, а природа П может пребывать в одном из п своих состояний Контрольная работа по теории игр. Предположим, что статистик может оценить последствия применения каждой своей чистой стратегии Ai в зависимости от каждого состояния П j природы П, т. е. статистику известен численный результат aij при выборе каждой стратегии Контрольная работа по теории игр, и при каждом состоянии природы Контрольная работа по теории игр. Тогда, как мы знаем из предыдущего § 13, игру с природой можно задать платежной матрицей

Контрольная работа по теории игр

Контрольная работа по теории игр

размера Контрольная работа по теории игр

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

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

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

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

Контрольная работа по теории игр

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

Оптимальной среди чистых стратегий по критерию Байеса относительно выигрышей считается стратегия Контрольная работа по теории игр с максимальным показателем эффективности (14.1), т. е. с максимальным средним выигрышем

Контрольная работа по теории игр

Теорема 14.1. СтратегияКонтрольная работа по теории игр , оптимальная среди чистых стратегий по критерию Байеса относительно выигрышей, является оптимальной по тому же критерию и среди всех смешанных стратегий множества SA.

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

Пример 1. Найдем оптимальную стратегию предприятия в выпуске новых видов продукции по критерию Байеса относительно выигрышей. Платежная матрица игры

Контрольная работа по теории игр

Для удобства перепишем матрицу (14.3), добавив строку вероятностей состояний природы и столбец показателей эффективности стратегий игрока А, т.е. средних выигрышей, вычисленных по формуле (14.2):

Так, например, по формуле (14.2) при Контрольная работа по теории игр

Контрольная работа по теории игр

Из последнего столбца матрицы (14.3) видно, что стратегия A4 имеет наибольший показатель эффективности Контрольная работа по теории игр и, следовательно, по критерию Байеса относительно выигрышей, она является оптимальной.

Критерий Байеса относительно рисков. Рассмотрим ту же игру с природой с матрицей (22.1), в которой известны вероятности состояний природы Контрольная работа по теории игр При принятии решений в условиях риска можно пользоваться не только средними выигрышами, но и средними рисками. Составим матрицу рисков для матрицы игры, используя формулу рисков (13.2):

Контрольная работа по теории игр

Показателем неэффективности стратегии Ai по критерию Байеса относительно рисков называется среднее значение (математическое ожидание) рисков Контрольная работа по теории игр строки матрицы (22.9), вероятности которых, очевидно, совпадают с вероятностями состояний природы. Обозначим средний риск при стратегии Ai через Контрольная работа по теории игр , тогда

Контрольная работа по теории игр

является взвешенным средним рисков i -й строки матрицы (14.4) с весами Контрольная работа по теории игр

Оптимальной среди чистых стратегий по критерию Байеса относительно рисков является стратегия Контрольная работа по теории игр , показатель неэффективности (14.5) которой минимален, т.е. минимален средний риск

Контрольная работа по теории игр

Теорема 14.1. Если Контрольная работа по теории игр стратегия, оптимальная среди чистых стратегий по критерию Байеса относительно рисков, то она является оптимальной по тому же критерию и среди всех смешанных стратегий множества SA.

Критерий Лапласа относительно выигрышей. В предыдущих двух критериях Байеса известные вероятности Контрольная работа по теории игр состояний природы могли быть получены из статистических данных, отражающих многократное решение подобных задач, или в результате наблюдений за поведением природы. Однако довольно часто складывается такая ситуация, когда мы лишены возможности определить вероятности состояний природы указанными способами. Желая все же принять решение в условиях риска, мы вынуждены оценить вероятности состояний природы субъективно. Существуют различные методы численной субъективной оценки степени правдоподобности состояний природы. Один из них состоит в том, что мы не можем отдать предпочтение ни одному из состояний природы и потому считаем их равновероятными, т.е. Контрольная работа по теории игр. Этот принцип называется "принципом недостаточного основания " Лапласа. На нем основан критерий Лапласа относительно выигрышей.

Показателем эффективности стратегии Ai по критерию Лапласа относительно выигрышей называется среднее арифметическое выигрышейКонтрольная работа по теории игрстроки:

Контрольная работа по теории игр

Оптимальной среди чистых стратегий по критерию Лапласа относительно выигрышей считается стратегияКонтрольная работа по теории игр ,показатель эффективности которой, вычисляемый по формуле (14.7), максимален, т е. Контрольная работа по теории игр .

Пример. Рассмотрим игру с природой, заданную матрицей игры

Контрольная работа по теории игр

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

Контрольная работа по теории игр

Контрольная работа по теории игр

Так, например, Контрольная работа по теории игр. Из последнего столбца матрицы (14.8) видно, что наибольшим показателем эффективности обладает стратегия А3, для которой а3= 26.

Значит, по критерию Лапласа относительно выигрышей оптимальной является стратегия A3.

Критерий Лапласа относительно рисков. Критерий Байеса относительно рисков при равновероятных состояниях природы, Контрольная работа по теории игр , превращается в критерий Лапласа относительно рисков.

Тогда величина Контрольная работа по теории игр или более простая величина представляет собой показатель неэффективности стратегии Ai по критерию Лапласа относительно рисков. Следовательно, оптимальной среди чистых стратегий по критерию Лапласа относительно рисков является стратегия Контрольная работа по теории игр , показатель неэффективности Контрольная работа по теории игр которой минимален. Подставляя в (14.5) значения Контрольная работа по теории игр, получим показатель неэффективности смешанной стратегии Р по критерию Лапласа относительно рисков, вместо которого можно рассматривать более простую величину Контрольная работа по теории игр .

Стратегия Р, для которой показатель Контрольная работа по теории игр принимает минимальное значение, является оптимальной среди всех стратегий множества SA.

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

Контрольная работа по теории игр

Из (14.9) следует, что если Контрольная работа по теории игр убывающая, соответственно возрастающая, последовательность, то убывающей, соответственно возрастающей, является и последовательность Контрольная работа по теории игр. В самом деле, если 1 ,q..., n q убывающая последовательность, т. е. Контрольная работа по теории игр, то Контрольная работа по теории игр . Тогда из (14.9) Контрольная работа по теории игр откуда , Контрольная работа по теории игр, что и означает убывание последовательности Контрольная работа по теории игр. Если Контрольная работа по теории игр возрастающая последовательность, то возрастание последовательности Контрольная работа по теории игр доказывается аналогично.

Из (14.9) и нормировочного равенства

Контрольная работа по теории игр

можно выразить вероятности Контрольная работа по теории игр через числа Контрольная работа по теории игр.

Действительно, из (14.9) Контрольная работа по теории игр,: откуда

Контрольная работа по теории игр

Из (14.9) Контрольная работа по теории игр , или после подстановки сюда равенства (14.11)

Контрольная работа по теории игр

и т.д.

Контрольная работа по теории игр

Следовательно, из (22.30)

Контрольная работа по теории игр

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

В частности, если Контрольная работа по теории игр арифметическая профессия с положительными членами и разностью d , то

Контрольная работа по теории игр

Если Контрольная работа по теории игр геометрическая прогрессия с положительными членами и (следовательно, с положительным) знаменателем Контрольная работа по теории игр

Контрольная работа по теории игр

Игры в условиях неопределенности. Критерий принятия решений

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

Обобщенный критерий пессимизма-оптимизма Гурвица относительно выигрышей с коэффициентами Контрольная работа по теории игр[14].

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

Контрольная работа по теории игр

Контрольная работа по теории игр

Каждая строка Bi матрицы В является перестановкой выигрышей при стратегии Контрольная работа по теории игр. Не исключена возможность, что для некоторых номеров i и j будет иметь место равенствоКонтрольная работа по теории игр. В силу неравенств (23.1) в первом столбце матрицы В стоят минимальные выигрыши при каждой стратегии

Контрольная работа по теории игр

а в последнем n -м столбце - максимальные выигрыши при каждой стратегии

Контрольная работа по теории игр

Пусть числа Контрольная работа по теории игр удовлетворяют условиям

Контрольная работа по теории игр

Показателем эффективности стратегии Ai по рассматриваемому критерию назовем число

Контрольная работа по теории игр

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

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

Контрольная работа по теории игр

Числа

Контрольная работа по теории игр

назовем показателями соответственно пессимизма и оптимизма. В обозначениях (15.6) индекс "p" первая буква английского pessimism, индекс "о" первая буква английского optimism, Контрольная работа по теории игр целая часть числа Контрольная работа по теории игр , т. е. наибольшее целое число, не превосходящее числа Контрольная работа по теории игр; очевидно, что

Контрольная работа по теории игр

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

Если показатель оптимизма Контрольная работа по теории игр и, следовательно, показатель пессимизма Контрольная работа по теории игр, то критерий более "оптимистический", чем "пессимистический"; если, наоборот, показатель оптимизма Контрольная работа по теории игр и, следовательно, показатель пессимизма Контрольная работа по теории игр, то критерий более "пессимистический", чем "оптимистический"; если же показатели оптимизма и пессимизма равны: Контрольная работа по теории игр, то критерий можно считать реалистическим.

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

Контрольная работа по теории игр

которые, очевидно, удовлетворяют условиям (14.4).

Подставляя значения коэффициентов (15.7) в формулу (15.5) и учитывая (15.2), получим показатель эффективности стратегии Ai по критерию Вальда:

Контрольная работа по теории игр

представляющий собой минимальный выигрыш игрока А при применении им стратегии Ai . Оптимальной среди чистых стратегий по критерию Вальда является, таким образом, стратегия Контрольная работа по теории игр , имеющая максимальный показатель эффективности (15.8):

Контрольная работа по теории игр

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

Контрольная работа по теории игр

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

Контрольная работа по теории игр

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

Контрольная работа по теории игр

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

Контрольная работа по теории игр

удовлетворяющими, очевидно, условиям (15.4).

Оптимальной же стратегией по этому критерию считается стратегия Контрольная работа по теории игрс максимальным показателем эффективности

Контрольная работа по теории игр

Позиционные игры. Понятие позиционной игры и ее нормальной формы

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

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

Пример. Игра состоит из трех ходов, которые делают два игрока. Первый ход делает первый игрок: он выбирает число x из множества двух чисел {1,2}.

Второй ход делает второй игрок: зная, какое число x выбрано первым игроком в первом ходе, он выбирает число у из множества двух чисел {1,2}.

Третий ход делает первый игрок: зная, какое число у выбрал второй игрок, и помня, какое число x он выбрал при первом ходе, выбирает число z из множества двух чисел {1,2}.

На этом игра заканчивается и происходит распределение выигрышей, второй игрок платит первому сумму, определенную функцией M(x, y,z), где М задана следующим образом:

Контрольная работа по теории игр

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

Контрольная работа по теории игр

Другими словами, у второго игрока столько стратегий, сколько имеется способов отображения множества {1,2} в себя.

Стратегия для первого игрока должна учитывать результаты сделанных ранее выборов. При каждом выборе на первом ходе может быть два выбора на втором ходе, т. е. уже имеется четыре варианта, а при каждом из этих вариантов может быть сделано два выбора, т. е. всего 8 возможных стратегий. Обозначим через Контрольная работа по теории игр стратегию первого игрока: где i означает выбор первым игроком на первом ходе; Контрольная работа по теории игр — выбор первым игроком на третьем ходе, если второй игрок на втором ходе выбрал число 1: Контрольная работа по теории игр — выбор первым игроком на третьем ходе, если второй на втором ходе выбрал число 2.

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

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

Таблица 1

Контрольная работа по теории игр

Графическое представление позиционной игры

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

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

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

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

Контрольная работа по теории игр

Определение позиционной игры

Позиционной игрой будем называть конечную игру п игроков состоящую из:

1. Дерева Т (понятие дерева игры было дано в 3.2 этой главы).

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

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

4. Сопоставления каждой точке разветвления Т дерева, соответствующей случайному ходу, элемента множества где к — число альтернатив (выборов) в точке т. q . число прямых, выходящих из точки полный набор вероятностей применения альтернатив.

5. Разбивки точек разветвления на непересекающиеся и полные множества (информационные множества), удовлетворяющие следующим условиям:

а) все точки разветвления, принадлежащие данному информационному множеству, относятся, согласно пункту 3, к одному игроку;

б) все точки разветвления, принадлежащие одному информационному множеству, имеют одинаковое число альтернатив, которые мы будем нумеровать справа налево;

в) если (см, пункт 3) точке разветвления q поставлено в соответствие число 0, то информационное множество, в котором находится состоит из одной точки;

г) если S — партия игры, т. е. ломаная линия, идущая от основания дерева к одной из его вершин, и если А — любое информационное множество, то существует не больше одной точки разветвления, принадлежащей обоим множествам S и A, Понятие стратегии также нуждается в уточнении в связи с уточнением понятия позиционной игры.

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

Позиционные игры с полной информацией

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

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

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

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

Аналогичное положение и у второго игрока. Усечением позиционной игры с полной информацией называется игра, которая получается из данной путем исключения первого хода. Теперь сформулируем теорему 16.1 о существовании точки равновесия. Теорема 16.1. Пусть A(1) ) и A(2) — множества стратегий, имеющихся у P1 и P2 в игре игроков с полной информацией, и пусть А — их декартово произведение. Тогда А имеет точку равновесия.

Позиционные игры с идеальной памятью

Игры с идеальной памятью являются интересным обобщением игр с полной информацией.

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

Позиционная игра — это игра с идеальной памятью, если для нее выполняются следующие условия: пусть P и Q — любые два хода, выполняемые одним игроком и такие, что в некоторой партии игры ход Р предшествует ходу Q ; U и V — информационные множества, содержащие соответственно P и Q ; каждая точка множества U дает k альтернатив;

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

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

О п р е д е л е н и е . Стратегией поведения данного игрока называется функция, определенная на классе информационных множеств, которая соотносит каждому информационному множеству U элемент — набор вероятностей Контрольная работа по теории игр выбора альтернатив, т.е. из множества S, где r — число альтернатив, которое дает U . По данной стратегии поведения одного игрока и по данной чистой или смешанной стратегии или стратегии поведения другого игрока можно вычислить ожидаемый выигрыш каждого игрока.