Камень, ножницы, теорема. Фон Нейман. Теория игр. - [20]
Исходя из этого фон Нейман определил седловую точку как точку матрицы, обладающую следующими характеристиками.
1. Она имеет минимальное значение на своей строке.
2. Она имеет максимальное значение в своем столбце.
Джон Форбс Нэш родился 13 июня 1928 года в Блюфильде, штат Вирджиния, США. Уже в очень раннем возрасте он проявил незаурядные способности к математике и оказался в числе десяти учеников его же возраста, получивших стипендию на учебу в Политехническом институте Карнеги.
Там он сначала изучал инженерное дело и химию, а позже понял, что его настоящее призвание — математика.
После института Нэш поступил в Принстонский университет. Там он заслужил восхищение сокурсников придуманной им настольной игрой, которая позже появилась в продаже под названием гекс. Увлечение играми было частью математических исследований Нэша. В 1950-е годы теория игр стала одной из самых интересных областей математики. Нэш внес ключевой вклад в первое экспериментальное изучение дилеммы заключенного (см. главу 5), а затем занялся играми с нулевой суммой, или некооперативными играми, в которых игроки преследуют прямо противоположные интересы. Одним из самых важных достижений ученого стало понятие так называемого равновесия Нэша. Впоследствии он основал на нем новую экономическую теорию, за которую получил Нобелевскую премию по экономике в 1944 году. Равновесие Нэша проявляется в ситуации, когда две стороны приходят на определенном этапе игры или в сделке к соглашению, нарушение или изменение которого причинит ущерб им обеим. Равновесие характеризует такую фазу игры, в которой ни один из ее участников не может увеличить выигрыш, изменив стратегию в одностороннем порядке.
Если во время игры участник А предположит, что В не поменяет стратегию и, следовательно, сохранит свою, и участник В, в свою очередь, тоже подумает, что Л сохранит стратегию, то говорится, что игра достигла равновесия Нэша, названного так в честь американского математика Джона Форбса Нэша (р. 1928). В конкретной игре равновесия Нэша может не быть, или оно может быть одно либо их окажется несколько.
Не во всех играх с двумя игроками и нулевой суммой есть седловая точка. Рассмотрим очень простой пример с подбрасыванием двух монеток. Каждый игрок ставит 1 евро. Первый одновременно подбрасывает в воздух две монеты. Если на обеих выпадает орел или решка, он оставляет их обе себе. Но если выпал один орел и одна решка, монеты забирает второй игрок. Платежная матрица такой игры будет следующей.
Решка | Орел | |
Решка | 1 | -1 |
Орел | -1 | 1 |
Легко убедиться, что разница между минимальным из максимальных значений и максимальным из минимальных составляет два евро. Изучая ситуации такого типа, фон Нейман еще больше отточил свою теорию игр и ввел различие между чистыми и смешанными стратегиями. К первым относятся игры, в которых игрок выбирает одну и ту же стратегию во всех раундах. Если оба игрока выбирают один и тот же путь, все партии будут одинаковыми. Напротив, в играх со смешанными стратегиями игрок меняет свое поведение от раунда к раунду произвольным образом.
Например, он может определить свою стратегию в зависимости от подброшенной монеты. В статье 1928 года Джон фон Нейман привел математическое доказательство того, что в каждой игре с двумя участниками и нулевой суммой, в которой можно играть с чистыми или смешанными стратегиями, стратегия минимакс каждого из игроков всегда привела бы к стабильной ситуации, седловой точке. На этом результате основана общая теория игр. Наконец, теорема о минимаксе утверждает, что в каждой конечной игре с двумя рациональными игроками, нулевой суммой и с чистой или смешанной стратегией всегда есть решение. Фон Нейман считал эту теорему краеугольным камнем теории игр.
Первая теорема о минимаксе, доказанная фон Нейманом в 1928 году, может применяться к большинству игр с двумя участниками и нулевой суммой, главное условие — чтобы в каждый момент оба игрока точно знали, на какой стадии находится игра. Эти игры фон Нейман назвал играми с полной информацией. Играя в шахматы, шашки или трис, каждый игрок может видеть расположение фигур после хода. Если же один игрок закроет часть доски, это условие перестанет выполняться, и применить теорему будет нельзя.
Фон Нейман доказал вторую теорему о минимаксе, которая могла использоваться для игр с двумя участниками, нулевой суммой, но неполной информацией. Согласно этой теореме, определить выигрышную стратегию невозможно для одной партии, но возможно, если сыграть их несколько.
Очень простая игра, иллюстрирующая эти условия, — классическая «камень, ножницы, бумага». Платежная матрица такой игры, в которой игроки ставят по 1 евро в каждой партии, имела бы такой вид.
В | ||||
Камень | Бумага | Ножницы | ||
А | Камень | 0 | -1 | 1 |
Бумага | 1 | 0 | -1 | |
Ножницы | -1 | 1 | 0 |
Если, например, А выбирает бумагу, а В — камень, то А выигрывает 1 евро, который, соответственно, проигрывает В. Ничья, когда никто не выигрывает и не проигрывает, соответствует значению 0.
Легко убедиться, что для этого примера теорема о минимаксе не работает, так как максимальный минимум для любой строки равен -1, в то время как минимальный максимум любого столбца — 1. Это происходит из-за того, что у игроков нет полной информации об игре. В одной-единственной партии отсутствует критерий, позволяющий выбрать одну из трех стратегий. Но если сыграть несколько раз, то можно обнаружить, что один из игроков следует определенной модели поведения. Согласно фон Нейману, лучшей стратегией будет положиться на волю случая, так как это помешает нашему противнику понять нашу схему игры. А если такой путь выберет и противник, то хотя ему не будет гарантирована победа, он получит разумный шанс сыграть вничью, а это один из способов минимизировать потери.
Рассказ о жизни и делах молодежи Русского Зарубежья в Европе в годы Второй мировой войны, а также накануне войны и после нее: личные воспоминания, подкрепленные множеством документальных ссылок. Книга интересна историкам молодежных движений, особенно русского скаутизма-разведчества и Народно-Трудового Союза, историкам Русского Зарубежья, историкам Второй мировой войны, а также широкому кругу читателей, желающих узнать, чем жила русская молодежь по другую сторону фронта войны 1941-1945 гг. Издано при участии Posev-Frankfurt/Main.
В книге рассказывается история главного героя, который сталкивается с различными проблемами и препятствиями на протяжении всего своего путешествия. По пути он встречает множество второстепенных персонажей, которые играют важные роли в истории. Благодаря опыту главного героя книга исследует такие темы, как любовь, потеря, надежда и стойкость. По мере того, как главный герой преодолевает свои трудности, он усваивает ценные уроки жизни и растет как личность.
Уникальное издание, основанное на достоверном материале, почерпнутом автором из писем, дневников, записных книжек Артура Конан Дойла, а также из подлинных газетных публикаций и архивных документов. Вы узнаете множество малоизвестных фактов о жизни и творчестве писателя, о блестящем расследовании им реальных уголовных дел, а также о его знаменитом персонаже Шерлоке Холмсе, которого Конан Дойл не раз порывался «убить».
Это издание подводит итог многолетних разысканий о Марке Шагале с целью собрать весь известный материал (печатный, архивный, иллюстративный), относящийся к российским годам жизни художника и его связям с Россией. Книга не только обобщает большой объем предшествующих исследований и публикаций, но и вводит в научный оборот значительный корпус новых документов, позволяющих прояснить важные факты и обстоятельства шагаловской биографии. Таковы, к примеру, сведения о родословии и семье художника, свод документов о его деятельности на посту комиссара по делам искусств в революционном Витебске, дипломатическая переписка по поводу его визита в Москву и Ленинград в 1973 году, и в особой мере его обширная переписка с русскоязычными корреспондентами.
Настоящие материалы подготовлены в связи с 200-летней годовщиной рождения великого русского поэта М. Ю. Лермонтова, которая празднуется в 2014 году. Условно книгу можно разделить на две части: первая часть содержит описание дуэлей Лермонтова, а вторая – краткие пояснения к впервые издаваемому на русском языке Дуэльному кодексу де Шатовильяра.
Книга рассказывает о жизненном пути И. И. Скворцова-Степанова — одного из видных деятелей партии, друга и соратника В. И. Ленина, члена ЦК партии, ответственного редактора газеты «Известия». И. И. Скворцов-Степанов был блестящим публицистом и видным ученым-марксистом, автором известных исторических, экономических и философских исследований, переводчиком многих произведений К. Маркса и Ф. Энгельса на русский язык (в том числе «Капитала»).