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

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



НазваниеМ. А. Булгаков Бессмыслица искать решение, если оно и так есть. Речь идет о том, как поступать с задачей, которая решения не имеет. Это глубоко принципиальный вопрос, который, как я вижу, тебе, прикладнику, не дос
Дата17.10.2016
Размер
ТипУроки, сочинения


15.09.09

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

М.А. Булгаков


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

А. Стругацкий, Б. Стругацкий

Смешанные расширения

Определения


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

Начнем с мотивировки вводимых ниже конструкций. Приведем цитату из рассказа Э.А. По1 (1809–1849).

«Мне знаком восьмилетний мальчуган, чья способность угадывать в игре «чет и нечет» снискала ему всеобщее восхищение. Это очень простая игра: один из играющих сжимает в кулаке несколько камешков и спрашивает у другого, четное ли их количество он держит, или нечетное. Если второй играющий угадывает правильно, то он выигрывает камешек, если же неправильно, то проигрывает камешек. Мальчик, о котором я упомянул, обыграл всех своих школьных товарищей. Разумеется, он строил свои догадки на каких-то принципах, и эти последние заключались лишь в том, что он внимательно следил за своим противником и правильно оценивал степень его хитрости. Например, его заведомо глупый противник поднимает кулак и спрашивает: «Чет или нечет?». Наш школьник отвечает «нечет» и проигрывает. Однако в следующей попытке он выигрывает, потому что говорит себе: «Этот дурак взял в прошлый раз четное количество камешков и, конечно, думает, что отлично схитрит, если теперь возьмет нечетное количество. Поэтому я опять скажу – нечет!» Он говорит «нечет и выигрывает. С противником чуть поумнее он рассуждал бы так: «Этот мальчик заметил, что я сейчас сказал «нечет», и теперь сначала захочет изменить число камешков на нечетное, но тут же спохватится, что это слишком просто, и оставит их количество прежним. Поэтому я скажу «чет!» Он говорит «чет!» и выигрывает. Вот ход рассуждений маленького мальчика, которого его товарищи окрестили счастливчиком».

– Всего только – ответил я,– умение полностью отождествить свой интеллект с интеллектом противника.

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

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

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

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

Определение. Смешанной стратегией первого (второго) игрока в игре <U,V,g> называется вероятностная мера на множестве U (V).

Определение. Смешанным расширением игры <U,V,g> называется игра , где и – множества всех смешанных стратегий первого и второго игроков соответственно, а критерий определяется как математическое ожидание выигрыша в исходной игре, при условии, что соответствующие случайные величины независимы.

Когда нужно избежать путаницы, стратегии в исходной игре <^ U,V,g> называют чистыми.

Каждую чистую стратегию u можно отождествить с «сингулярной» смешанной стратегией определив отображение следующим условием: Аналогичным образом определяется отображение . При этом «выигрыши сохраняются», то есть для всех u и v. Это дает моральное право использовать слово «расширение».

Интересно отметить, что понятие смешанного расширения появилось в работе Э.Бореля, датированной 1921 г., то есть намного позднее того, как был написан рассказ Эдгара По.
^

Матричные игры


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

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

Если множества U={1,…,k} и V={1,…,m} конечны, то функцию выигрыша удобно задавать с помощью матрицы . Поэтому игры с конечными множествами стратегий часто называют матричными. В таком случае можно считать, что , , и тогда .

Теорема (фон Нейман, 1926). Всякая матричная игра имеет седловую точку в смешанных стратегиях.

Доказательство. Множества и представляют собой выпуклые подмножества (симплексы) конечномерных евклидовых пространств. Функция линейна по каждой из переменных, значит, она непрерывна и одновременно и выпукла и вогнута, как по u, так и по v. Таким образом, игра удовлетворяет всем условиями теоремы Какутани о существовании седловой точки в выпуклой игре.

Понять важность концепции смешанного расширения в принятии решений помогает следующий эксперимент3. На заре развития вычислительной техники был сконструирован специализированный компьютер для игры в «орла» и «решку» (его полная электрическая схема умещается на книжной странице стандартного формата). В эксперименте этот компьютер сыграл против посетителей и сотрудников Bell Telephone Laboratories 9795 партий, из которых выиграл 5218 (т.е. несколько больше 53%). Компьютер пользовался при этом датчиком случайных числе, поэтому такой перевес мог бы быть и случайным, но вероятность этого составляет около 10-10. То есть человек оказывается беспомощным даже перед примитивным компьютером, если пользуется своей логикой. Отсюда – необходимость рандомизации.

Кстати, разумеется, стратегия данного компьютера не является оптимальной. При правильной игре против него вероятность выигрыша составляет 60%.
^

Свойства смешанных расширений


Обозначим gi i-ую строку матрицы G, а gj – ее j-ый столбец.

Лемма. Цена игры равна каждому из чисел или .

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

Лемма. Если p – цена игры , то .

Доказательство. Согласно предыдущей лемме . Но множество {c(u): uU} есть подмножество множества , поэтому . Воспользовавшись равенством , получим левое неравенство. Правое доказывается аналогично.

Лемма. Если (u0,v0) – седловая точка в игре <U,V,g>, то (c(u0),d(u0)) будет седловой точкой в игре .

Доказательство. Пусть – произвольная смешанная стратегия первого игрока. Так как (u0,v0) – седловая точка, выполняются неравенства g(u,v0)g(u0,v0). Домножая эти неравенства на соответствующие вероятности, и суммируя, получим или . Аналогично доказывается неравенство .
^

Сведение к задаче линейного программирования


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

tmax,

,

.

,

Эту задачу можно еще немного упростить. Введем новые переменные . Тогда задача перепишется в виде

tmax,

x1g11,…,xkgk1,

x10,…,xk0.

,

Используя последнее равенство, переменную t можно вовсе исключить, переписав задачу в виде

,

x1g11,…,xkgk1,

x10,…,xk0.

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

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

^ Лемма. Множество оптимальных смешанных стратегий в матричной игре представляет собой выпуклый компактный многогранник.

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

Доминирование


Определение. Бинарным отношением на множестве A называется всякое подмножество ^ R декартова произведения AA.

Часто вместо (a,b)R пишут aRb.

Определение. Отношение R называется рефлексивным, если aRa для любого a.

Определение. Отношение R называется транзитивным, если из aRb и bRc следует aRc.

Определение. Отношение R называется антисимметричным, если из aRb и bRa следует, что a=b.

Определение. Рефлексивное, антисимметричное и транзитивное отношение называют отношением частичного порядка.

Определение. Стратегия u1 первого игрока слабо доминирует его же стратегию u2, если g(u1,v)≥g(u2,v) для любого v. Стратегия v1 первого игрока слабо доминирует его стратегию v2, если g(u1,v)≤g(u2,v) для любого u.

Определение. Стратегия u1 первого игрока сильно доминирует его же стратегию u2, если g(u1,v)>g(u2,v) для любого v. Стратегия v1 первого игрока сильно доминирует его стратегию v2, если g(u1,v)<g(u2,v) для любого u.

Лемма. Если стратегия i в матричной игре слабо доминируется стратегией какой-то другой стратегией, то найдется такая оптимальная смешанная стратегия , что =0.

Доказательство. Пусть чистая стратегия l слабо доминирует стратегию i, и пусть – седловая точка в смешанном расширении данной игры. Тогда для любых стратегий и . Определим стратегию , положив для всех остальных j. Из условия слабого доминирования следует, что для всех . Отсюда , то есть на самом деле , то есть – тоже оптимальная стратегия первого игрока, что и требовалось доказать.

Аналогично доказывается

Лемма. Если стратегия i в матричной игре сильно доминируется стратегией какой-то другой стратегией, то для любой оптимальной смешанной стратегии имеет место равенство =0.

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

Лемма. Пусть – оптимальная стратегия первого игрока, причем . Тогда для любой оптимальной стратегии второго игрока.

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

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

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

В этой связи интересно проанализировать ситуацию, сложившуюся в полуфинальной игре женских сборных России и Бразилии на олимпиаде в Афинах. Сборная Бразилии по ходу матча выигрывала 2:1 по партиям и 24:19 в четвертой партии, но в результате проиграла. Общественное мнение Бразилии обвинило в проигрыше доигровщицу команды, не забившую несколько решающих мячей в четвертой партии. А по статистике она за весь матч набрала 35 очков, то есть нападала гораздо чаще и успешнее своих подруг. Предыдущая лемма показывает, что связующая сборной Бразилии выбрала явно не оптимальную стратегию, чем и воспользовались блокирующие сборной России.

Примеры


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

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

Любая смешанная стратегия первого игрока может быть записана в виде (q,1–q), где q – некоторое число, принадлежащее отрезку [0,1]. Поэтому нужно вычислить . Максимум, очевидно, может достигаться либо на концах отрезка, либо в точке пересечения графиков функций . На концах отрезка , а в точке это выражение принимает значение 3. Значит, цена игры равна 3, а оптимальная смешанная стратегия первого игрока есть .

Аналогично находится оптимальная стратегия 5 второго игрока в редуцированной игре.

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

Пример. Рассмотрим известную игру «камень–ножницы–бумага». Она описывается матрицей .

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

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

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

^ Пример (фон Нейман, 1953). Полицейский ищет гангстера, который может прятаться в одном из n баров. Вероятность задержания гангстера, если он находится в баре с номером i, равна ai. Естественно, полицейский стремится максимизировать эту вероятность.

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

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

из n+1 уравнения с n+1 неизвестным. Откуда , .

Аналогично находится оптимальная стратегия преступника .

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

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

Замечание. Данная игра использовалась фон Нейманом для решения следующей задачи оптимального назначения: имеется n рабочих, n видов работ и набор вещественных чисел aij, характеризующих производительность i-го рабочего на работе вида j. На какую работу следует определить каждого рабочего6, чтобы добиться максимума общей производительности?

Пример. Пусть оперирующая сторона умеет производить два типа танков A и B, а ее вероятный противник – тоже два типа C и D. При этом известно, что 70% встреч AC выигрывает A, 60% встреч CBвыигрывает C, 85% встреч BDвыигрывает B, а 65% встреч DA выигрывает D. Рассматривается вопрос о том, какой тип танков ставить на вооружение?

Очевидно, ситуация описывается матричной игрой с матрицей . Непосредственная проверка показывает, что седловой точки в этой игре нет. Оптимальная смешанная стратегия оперирующей стороны (0.375, 0.625), то есть 37.5% стоящих на вооружении танков должны иметь тип A, а остальные – тип B.

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

  • «Орел-решка» – иррациональность + динамика – сдвиги на торе – эргодичность – дискретный вариант – существование седловой точки?

  • Две игры Бореля у фон Неймана стр.643.

  • У мак-Кинси глава III параграф 3.

  • У мак-Кинси стр. 107 – сетевые игры

Задачи


  1. Рассмотрите семейство антагонистических игр 22: . Докажите, что оно разбивается на два подмножества:

А) Если пересечение [a,d] и [b,c] не пусто, то игра имеет седловую точку в чистых стратегиях.

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

***

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

  2. Приведите примеры таких матриц A и B, что

А) p(A+B)<p(A)+p(B);

Б) p(A+B)>p(A)+p(B);

В) p(A+B)=p(A)+p(B),

где p(A) – цена игра с матрицей A?

  1. Все элементы матрицы неотрицательны, причем каждый столбец содержит, по крайней мере, один положительный элемент. Докажите, что цена игры с этой матрицей положительна.

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

  3. Докажите, что цена игры, матрица которой состоит из рациональных чисел, рационально.

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

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

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

  7. Докажите, что p(–A)=–p(AT), где AT – матрица, транспонированная к A.

  8. Пусть A – квадратная кососимметрическая матрица, то есть A=–AT, где AT – матрица, транспонированная к A. Докажите, что в смешанном расширении соответствующей матричной игры существует по крайней мере одна седловая точка такая, что .

***

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

А) в некоторую оптимальную стратегию первого игрока?

Б) в любую оптимальную стратегию первого игрока?

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

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

  3. Следует ли из того, что i-я компонента любой оптимальной стратегии первого игрока равна нулю, доминирование i-ой строки матрицы некоторой выпуклой комбинацией других строк?

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

А)

Б)

В)

Г)

Д)

Е)

Ж)

З) ,

И) .

***

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

А) ,

Б) ,

В) .

  1. Найдите цены и оптимальные смешанные стратегии в играх с матрицами

А) ,

Б) ,

В) .

Г) ,

Д) ,

Е) .

Ж) .

***

  1. Покажите, что игра с матрицей , где a>b>c>0 имеет единственную седловую точку. Найдите ее и цену игры. Каково будет решение, если a>b>c и c<0?

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

  3. Докажите, что игра с матрицей имеет единственную седловую точку.

  4. Дана матричная игра с матрицей (aij) для которой Найдите значение игры в смешанных стратегиях и оптимальные стратегии.

  5. Найдите седловую точку в игре с матрицей (aij), если причем bi>0 при всех i.

  6. Найдите цену и оптимальные смешанные стратегии игры с матрицей .

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

  8. Игрок 1 выбирает одну из n ячеек и прячется в ней. Игрок 2 ищет игрока 1 путем проверки одной из ячеек. Если игрок прячется в i-ой ячейке, а игрок 2 проверяет j-ю ячейку, то выигрыш игрока 1 равен . Игра антагонистическая.

А) при n=3 найти седловую точку и цену игры.

Б) Найти седловую точку и цену игры в общем случае.

  1. Условия аналогичны предыдущей задаче, но в случае, если i не равно j игрок 2 платит игроку 1 штраф в размере cj>0, а в случае обнаружения игрока 1 в ячейке i игрок 2 получает сумму ri. Вероятность обнаружить игрока 1 в ячейке j, при условии, что i=j, равна j(0,1).

А) Построить матрицу игры.

Б) При n=3, ri=i, i=1/2i, ci=i найти седловые точки и цену игры.

В) Пусть c1min{c2,…,cn}, nrncn–c1. Докажите, что c1 – цена игры, а (n,1) – седловая точка в чистых стратегиях.

Г) ???Пусть – цена игры, а векторы с компонентами и определяют седловую точку в смешанных стратегиях.

***

  1. Докажите, что если для всех значений i и j выполняется неравенство
    ai–1,j–2ai,j+ai+1,j0, то в игре с матрицей (aij) у первого игрока есть оптимальная стратегия, в которой все элементы, кроме, быть может, первого и последнего, нулевые.

  2. Докажите, что если для всех значений i и j выполняется неравенство
    ai,j1–2ai,j+ai,j+10, то в игре с матрицей (aij) для каждого игрока существует оптимальная стратегия, спектр которой содержит не более двух точек.

  3. Докажите, что если для всех значений i и j выполняется неравенство
    ai–1,j–2ai,j+ai+1,j0, то в игре с матрицей (aij) для каждого игрока существует оптимальная стратегия, спектр которой содержит не более двух точек.

***

  1. Отождествим матрицу игры размера kn с точкой kn–мерного евклидова пространства. Пусть отображение F ставит в соответствие каждой точке пространства множество седловых точек в игре с соответствующей матрицей. Докажите, то отображение F замкнуто. Является ли оно полунепрерывным снизу?

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

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

***

  1. Установите связь между оптимальными стратегиями игры с матрицей A и оптимальными стратегиями симметричной игры с матрицей .

Литература


  1. Воробьев Н.Н. Теория игр для экономистов–кибернетиков. М.: Наука, 1985.

  2. Мак Кинси Дж. Введение в теорию игр. М.: Физматлит, 1960.

  3. Фон Нейман Дж., Моргенштерн О. Теория игр и экономическое поведение. М.: Наука, 1970.

1 См. По Э.А. Похищенное письмо //Собрание сочинений в двух томах. Т. 2. Воронеж, «Полиграф». 1995. С.142–143.

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

3 См. Hagelbarger D.W. SEER, a sequence extrapolating robot, Trans. IRE, EC-5, №1 (1956),1–7 (Русский перевод Хагельсбаргер Д.У. СИИР – автомат, экстраполирующий последовательности //Кибернетический сборник. Вып.1. М.: ИЛ, 1960. С. 275–289.

4 А при достаточно малых  сильно доминируется строкой .

5 То, что она в данном случае совпала с оптимальной стратегией первого игрока – случайность. Полезно подумать, чем это обусловлено.

6 по одному на каждую работу

27.02.2014




Похожие:

М. А. Булгаков Бессмыслица искать решение, если оно и так есть. Речь идет о том, как поступать с задачей, которая решения не имеет. Это глубоко принципиальный вопрос, который, как я вижу, тебе, прикладнику, не дос iconГ. П. Щедровицкий «Философия у нас есть!»
Я понимаю основания для таких высказываний и вроде бы могу согласиться, что если речь идет об официальной философии, то там очень...
М. А. Булгаков Бессмыслица искать решение, если оно и так есть. Речь идет о том, как поступать с задачей, которая решения не имеет. Это глубоко принципиальный вопрос, который, как я вижу, тебе, прикладнику, не дос iconЛекция Архитектура программного обеспечения. Анализ области решений
Целью этой деятельности является понимание, можно ли вообще решить стоящие перед разрабатываемой системой задачи, при каких условиях...
М. А. Булгаков Бессмыслица искать решение, если оно и так есть. Речь идет о том, как поступать с задачей, которая решения не имеет. Это глубоко принципиальный вопрос, который, как я вижу, тебе, прикладнику, не дос iconГенри Джеймс. Европейцы
Евгения пока не дала на это согласия, так что сейчас вопрос открыт. От всех рассказов и событий голова у Гертруды идет кругом, и...
М. А. Булгаков Бессмыслица искать решение, если оно и так есть. Речь идет о том, как поступать с задачей, которая решения не имеет. Это глубоко принципиальный вопрос, который, как я вижу, тебе, прикладнику, не дос iconУрок физики и математики по теме: "Принцип суперпозиции электрических полей. Решение задач"
Хорошо, если учитель математики будет принимать активное участие в обсуждении решения физических задач (в том числе и при численных...
М. А. Булгаков Бессмыслица искать решение, если оно и так есть. Речь идет о том, как поступать с задачей, которая решения не имеет. Это глубоко принципиальный вопрос, который, как я вижу, тебе, прикладнику, не дос iconВариант №12 в задачах 1-9 найти общие решения уравнений и частные решения, если есть начальные условия. 1
Ородным. Сделаем замену Тогда. Получим уравнение, или. Разделяем переменные: Интегрируем уравнение: Получим: или. Вернёмся к переменной...
М. А. Булгаков Бессмыслица искать решение, если оно и так есть. Речь идет о том, как поступать с задачей, которая решения не имеет. Это глубоко принципиальный вопрос, который, как я вижу, тебе, прикладнику, не дос iconЭра автозвука неизбежно началась
Большинство из нас хоть как-то дорабатывает или просто меняет ту аудиосистему, которая рано или позно перестаёт радовать слух так,...
М. А. Булгаков Бессмыслица искать решение, если оно и так есть. Речь идет о том, как поступать с задачей, которая решения не имеет. Это глубоко принципиальный вопрос, который, как я вижу, тебе, прикладнику, не дос iconЗапросы о спросе
И если у западных компаний главный вопрос – как оперативно реагировать на изменения спроса, то у отечественных есть и еще одна проблема...
М. А. Булгаков Бессмыслица искать решение, если оно и так есть. Речь идет о том, как поступать с задачей, которая решения не имеет. Это глубоко принципиальный вопрос, который, как я вижу, тебе, прикладнику, не дос iconПрограммирование programming
В своем широком смысле оно пронизывает всю нашу жизнь, так как когда мы планируем какое-то действие, мы расписываем для себя как...
М. А. Булгаков Бессмыслица искать решение, если оно и так есть. Речь идет о том, как поступать с задачей, которая решения не имеет. Это глубоко принципиальный вопрос, который, как я вижу, тебе, прикладнику, не дос iconМастер-класс как нарисовать кенгуру
Животное имеет особые косточки таза, сумчатые кости, причем они есть как у самок, так и у самцов. А вот сумка для вынашивания детенышей...
М. А. Булгаков Бессмыслица искать решение, если оно и так есть. Речь идет о том, как поступать с задачей, которая решения не имеет. Это глубоко принципиальный вопрос, который, как я вижу, тебе, прикладнику, не дос icon«О маленьких детях»
И все с этой задачей превосходно справились. Это значит, что каждый из нас придумал, как ему научиться общаться и воспринимать информацию...
Разместите ссылку на наш сайт:
Уроки, сочинения


База данных защищена авторским правом ©izlov.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
связаться с нами