Помоги проекту - поделись книгой:
Если вы уплатите взнос заранее, математическое ожидание равно -150 (вне зависимости от того, поедете вы или нет, так как взнос не возвращается).
Если вы платите непосредственно по прибытии, то математическое ожидание равно -200 • р + (1 — р) • 0 = -200 •
Математические ожидания равны при р = 150/200 = 0,75.
Следовательно, если р > 0,75, то лучше заплатить заранее, если же р < 0,75, то лучше заплатить по прибытии на конференцию. При р = 0,75 результат будет одинаков.
Можно ли обыграть банк? Вероятность повторяющихся событий
Как мы увидели из предыдущего раздела, математическое ожидание помогает понять, является азартная игра равновесной или нет. Если игра равновесная, то после большого числа ходов ожидается, что мы не получим ни выигрыша, ни проигрыша. В противном случае мы можем рассчитать средний ожидаемый выигрыш или проигрыш. Несмотря на это, существовали и до сих пор существуют игроки, которым после множества ставок в игре с нулевым или отрицательным математическим ожиданием удается выигрывать. Рассмотрим математические инструменты, которые позволяют проанализировать повторяющиеся ходы (ставки) в азартной игре. Целью нашего анализа будет определить вероятность того, что мы сможем «превзойти ожидания».
Начнем с анализа игры в рулетку с 37 секторами (числа от 1 до 36 и 0). Какова вероятность того, что в 10 играх три раза выпадет зеро?
Вероятность выпадения трех зеро подряд в определенный момент игры равна (1/37)3 • (36/37)7 = 0,00016. Общая вероятность равна этому результату, умноженному на число позиций, которое может занимать последовательность из трех нулей: Сю з = 120. Иными словами,
что приблизительно соответствует 1 шансу из 50. Этот пример можно обобщить, получив важный для анализа азартных игр результат. Если в азартной игре или в произвольном эксперименте совершено n ставок или n независимых друг от друга испытаний и нам известна вероятность одиночного события (успешного исхода испытания), то
Распределение количества «успешных» исходов от 1 до n называется биномиальным распределением. Для применения этой формулы необходимо, чтобы испытания были независимыми и чтобы вероятность успешного исхода отдельного события не менялась.
Используем биномиальное распределение, чтобы найти вероятность того, что при n бросках монеты r раз выпадет решка, r = 1, 2, ...,n при n = 8. В этом случае
Симметричное распределение, которое можно увидеть из таблицы, — следствие того, что вероятность выпадания решки при одиночном броске равна 1/2. Читатель наверняка уже заметил, что последовательность чисел (1, 8, 28, 56, 50, 56, 28, 8, 1) из таблицы выше, сумма которых равна 256 (28), совпадает с одним из рядов треугольника Паскаля. Следовательно, биномиальное распределение связано с биномиальными коэффициентами, которые в данном конкретном случае равны коэффициентам в биноме (а + b)8.
Глава 4. Математическая теория игр
Девяносто процентов всей математики, за исключением тех разделов, которые появились ввиду практической необходимости, состоит в разгадывании загадок.
Теория игр — раздел математики, который изучает главным образом принятие решений. Теория игр применима во всех ситуациях, в которых присутствует конфликт, когда стороны должны принимать оптимальное решение, исходя из своих интересов, ничего не зная о решениях оппонентов. Эта теория формулируется на основе абстрактных игр (отсюда и название), но на самом деле объектом изучения являются не сами игры, а их применение в ситуациях, которые в силу своей специфики можно смоделировать в виде абстрактных игр.
В этой главе речь пойдет об играх с нулевой суммой для двух игроков. Слова «нулевая сумма» означают, что в любой момент времени выигрыш одного игрока равен проигрышу другого. Иными словами, победитель всегда один, и он «получает все». Предполагается, что каждый игрок стремится совершить оптимальный ход, то есть тот, который сулит наибольший выигрыш. Другими словами, ни один из игроков не согласится на меньшее, чем весь выигрыш полностью.
Начала теории игр
В качестве введения в теорию игр мы расскажем о трех играх разного уровня сложности и на их примере объясним отдельные ключевые понятия, которые будут использоваться в этой и следующей главах. В этой теории применяется игровая терминология и речь идет об играх, игроках, партиях, стратегии, равновесной игре и так далее. Несмотря на это, читателю нужно понимать, что представленные задачи не обязательно соответствуют какой-либо реальной игре в том смысле, как в предыдущих главах. Нагляднее будет представлять ситуацию (противостояние) между двумя людьми или группами с установленными правилами, определяющими возможные действия. Оба игрока принимают решения одновременно (а не по очереди, как в играх, описанных в главе 2), никто из них не знает о решениях соперника. В результате принятых решений выигрывает тот или другой игрок. Далее мы будем называть подобные ситуации играми, участников будем именовать игроками. Под стратегией будем понимать решение, принятое игроком, а под выигрышем или проигрышем — последствия принятых игроками решений.
Уже в XVII веке такие ученые, как Христиан Гюйгенс (1629-1695) и Готфрид Вильгельм Лейбниц (1646-1716), предложили создать дисциплину, в которой бы использовались научные методы для изучения человеческих конфликтов и взаимодействий. Однако получить какие-либо значимые результаты по этой теме им не удалось. На протяжении всего XVIII века не было написано практически ни одной работы по анализу игр, которая бы имела подобную цель. Заслуживает упоминания письмо Джеймса Уолдгрейва от 1713 года, в котором приводится решение карточной игры для двух игроков под названием Le Her. Автор использовал способ, похожий на смешанную стратегию, и привел минимаксное решение. Несмотря на это, не было разработано ни теоретической базы, ни обобщений, чтобы подобный метод можно было применить в других случаях. В XIX веке многие экономисты создавали простые математические модели для анализа простейших конкурентных ситуаций. Среди них выделяется работа Антуана Огюста Курно «Исследование математических принципов теории богатства» (1838), в которой рассматривается случай дуополии и приводится решение, которое можно считать частным случаем равновесия Нэша. Тем не менее, теория игр как фундаментальная математическая теория появилась лишь в первой половине XX века.
Начнем рассказ об основах теории игр со следующего случая. Он очень прост и не представляет никакого интереса в качестве игры. Два игрока А и Б одновременно записывают число (1 или 2). Игрок Б должен заплатить игроку А сумму в евро, равную результату сложения двух записанных чисел. Очевидно, игра неравновесная (А всегда выигрывает), но тем не менее мы можем задаться вопросом: как должен действовать каждый игрок в соответствии со своими интересами? Для этого рассмотрим матрицу игры, так называемую платежную матрицу, в которой приведены возможные результаты:
Элементы матрицы обозначают сумму в евро, которую должен заплатить игрок Б игроку А при выборе соответствующей стратегии. Каждый игрок имеет два варианта действий, поэтому всего в матрице четыре элемента. Игра очень простая, и очевидно, что, действуя согласно своим интересам, А напишет 2, Б напишет 1, выигрыш игрока А составит 3 евро.
Проанализируем ходы игроков более подробно, чтобы увидеть, каковы варианты действий для каждого игрока. А не знает, какое число записал Б, но предполагает, что Б хочет платить как можно меньше. Поэтому если А напишет 1, то выиграет минимум 2 евро, если напишет 2 — выиграет минимум 3 евро. Говорят, что 3 (число в нижней левой ячейке матрицы) — это
Число, соответствующее седловой точке (в нашем случае 3 евро), называется ценой игры. Оно достигается всякий раз, когда каждый игрок действует в соответствии со своей оптимальной стратегией. Если один из игроков сделает иной ход (использует иную стратегию), то противник сможет повысить цену игры, выиграв больше или потеряв меньше в зависимости от того, о каком из игроков идет речь. Также говорят, что для этой игры существует чистая стратегия.
Теперь представим себе другую игру с теми же правилами, но с другой платежной матрицей: если оба игрока записывают одинаковое число, А выигрывает 1 евро, если же числа отличаются, Б выигрывает 1 евро.
Теперь максиминным значением является -1 (оба минимальных значения равны -1), минимаксным значением для Б является 1 (оба максимума равны 1). Эта игра не имеет седловой точки, следовательно, не существует одной чистой стратегии. Если А будет использовать некую стратегию (например, всегда будет записывать 1), о которой будет известно Б, он всегда будет записывать 2 и всегда будет выигрывать 1 евро. Так как эта игра очень простая и симметричная, оптимальной стратегией будет любая, при которой игрок будет чередовать двойки и единицы так, чтобы соперник не смог определить его стратегию. Для этого оптимальной стратегией будет записывать числа наудачу. Например, можно бросать монету и записывать 1, если выпадает решка, и 2, если выпадает орел. В этом случае нельзя говорить о чистых стратегиях, так как стратегию нельзя определить заранее из-за вмешательства случайных событий. Когда оптимальная стратегия содержит элемент неопределенности и должна держаться в секрете, такую стратегию называют
Два приведенных нами примера соответствуют двум простым случаям, которые можно назвать крайними: в первом случае для игры определена чистая стратегия, так как оптимальные стратегии для каждого из игроков приводят к одному и тому же результату. Этот результат называется
Рассмотрим третью игру. Она похожа на две предыдущие, но определить оптимальные стратегии для каждого игрока будет сложнее. Как и в прошлых примерах, каждый игрок может записать одно из двух чисел: А может записать 1 или 8, Б может записать 2 или 7. Если четность обоих чисел совпадает (они оба четные или оба нечетные), А выигрывает сумму, равную записанному им числу. Если же одно из чисел четное, а другое — нет, победа остается за игроком Б, который выигрывает сумму, равную записанному им числу. Платежная матрица этой игры выглядит так:
Заметим, что элементы матрицы обозначают выигрыши игрока А. Поэтому в случае победы игрока Б элемент матрицы является отрицательным и отражает проигрыш игрока А. Может показаться, что игра равновесная (А может выиграть 1 или 8 евро, Б — 2 или 7 евро), но седловой точки не существует: максиминное значение равно -2 (-2 > -7), минимаксное равно 1 (1 < 8). На самом деле если в платежной матрице 2x2 числа вдоль одной диагонали больше, чем вдоль другой, седловой точки не существует, поэтому для такой игры нет оптимального решения. Однако имеется важное отличие этой игры от предыдущей. В предыдущей игре наилучшим вариантом было использование случайных стратегий обоими игроками, в этом случае выигрыши уравнивались. Здесь же игрок Б имеет шансы на победу. Оптимальная стратегия для каждого игрока по-прежнему предусматривает случайные действия, но не является полностью случайной, так как каждый должен принимать решения, соблюдая определенные соотношения. Решением игры в этом случае является использование смешанных стратегий обоими игроками. О том, как определить результаты этой игры, то есть об оптимальной стратегии для каждого игрока и о средней цене игры, мы поговорим несколько позже.
Читатель уже заметил, что мы представили различные игры в виде матриц, в которых содержатся различные стратегии для первого игрока (строки матрицы) и второго игрока (столбцы). Подобным представлением, которое известно как
В начале XX века начала складываться теоретическая основа современной теории игр, окончательно оформившейся в середине столетия. Авторство первой теоремы принадлежит логику Эрнсту Цермело (1871-1956). Он сформулировал и доказал ее в 1912 году. Эта теорема подтверждает, что любая конечная игра с полной информацией (например, шашки или шахматы) имеет оптимальное решение в чистых стратегиях, то есть в отсутствие элемента неопределенности. Эта теорема не описывает, как можно найти подобные стратегии.
Примерно в 1920 году великий математик Эмиль Борель заинтересовался бурно развивающейся теорией и представил идею о смешанной стратегии (в которой фигурирует элемент случайности). Вскоре над этой темой начал работать Джон фон Нейман, и в 1928 году он сформулировал и доказал теорему о минимаксе. Очень скоро эта теорема стала ключевым элементом в дальнейшем развитии теории игр. Теорема фон Неймана гласит, что в конечной игре для двух игроков А и Б существует среднее значение, обозначающее возможный выигрыш игрока А и Б, если оба игрока действуют разумно, то есть пытаются увеличить выигрыш (или уменьшить проигрыш).
Французский математик Эмиль Борель, автор множества исследований по теории вероятностей.
Когда достигается равновесие?
Игры, которые мы проанализировали в прошлом разделе, являются простыми по нескольким причинам: в них участвуют два игрока, у каждого из них только два возможных хода (платежная матрица всегда имеет размеры 2X2). Кроме того, это игры с нулевой суммой, так как сумма выигрышей обоих игроков всегда равна нулю (проигрыш понимается как отрицательный выигрыш). В каждой партии нужно выбрать всего лишь один из двух возможных ходов. Каждый игрок может придерживаться оптимальной для себя стратегии в соответствии с правилами игры. В этом случае игра будет определена и результат будет равен цене игры (как в первом примере предыдущего раздела). Мы увидели, что этот результат является решением игры, если речь идет об игре с седловой точкой, то есть если один из элементов матрицы является одновременно максиминным (максимальным значением среди минимальных в каждой строке) и минимаксным (минимальным значением среди максимумов в каждом столбце). Если седловая точка отсутствует, мы не можем вести речь о чистых стратегиях, и следует применять смешанные стратегии, в которых используются случайные события и которые нужно сохранять в тайне от соперника. В случаях, когда платежная матрица симметрична, стратегией является полностью случайный выбор (как было показано в примере 2). В ином случае даже при использовании случайной стратегии выбор хода должен производиться в соответствии с определенным соотношением (что показано в примере 3).
Джон фон Нейман, известный по работам во множестве областей, является одним из наиболее выдающихся математиков XX века. Он начал научную деятельность в родном Будапеште, где изучал математику. Затем он переехал в Берлин, чтобы заниматься физикой, а позже в Цюрих, где изучал химию. С 1930 года он жил и работал в США. В Гёттингене под руководством Гильберта фон Нейман занимался теоретическими вопросами чистой математики, а также совместно с Гейзенбергом работал над началами квантовой теории. Он внес существенный вклад во многие сферы науки, в частности в теорию множеств, функциональный анализ, логику, теорию вероятностей, прикладную математику в экономике, квантовую физику и метеорологию.
Его интересы выходили за рамки чистой и прикладной математики и охватывали также столь различные области, как атомная физика, проектирование компьютеров, когнитивная психология и экономика. Одно из важнейших его достижений, относящееся к прикладной математике в экономике, — создание теории игр, которую он сформулировал в книге «Теория игр и экономическое поведение»», опубликованной совместно с экономистом Оскаром Моргенштерном в Принстоне в 1944 году. Этот труд считается фундаментальным в теории игр. Он ознаменовал создание теории игр, которая уже через несколько лет, начиная с 1950-х годов, стала находить применение в анализе множества реальных ситуаций.
Абстрактная игра с чистыми стратегиями
Проанализируем более подробно игры первого типа и посмотрим, что происходит при расширении платежной матрицы, то есть в случаях, когда для каждого игрока имеется больше двух возможных ходов.
Представим следующую игру для двух игроков: игрок А выбирает строку (F1, F2, F3), его соперник — столбец (Cl, С2, СЗ) из следующей платежной матрицы, при этом ни один из игроков не знает о выборе оппонента. Выбор игроков определит элемент матрицы (он находится на пересечении выбранных строки и столбца), который укажет, сколько евро должен заплатить второй игрок первому. Как должен действовать каждый игрок, чтобы увеличить свой выигрыш или уменьшить проигрыш?
Игрок А анализирует минимальные выигрыши в зависимости от совершенных ходов. Если он выберет F1, минимальный выигрыш равен -2, 2 для строки F2 и - 1 для строки F3. Наибольший из минимальных выигрышей (максиминное значение) равен 2. Если игра является определенной, нужно выбирать строку F2. Аналогично игрок Б анализирует наибольшие проигрыши в зависимости от совершенных ходов. Если он выберет С1, максимальный проигрыш равен 6, 7 — для столбца С2 и 2 — для столбца СЗ. Наименьший из максимальных проигрышей (минимаксное значение) равен 2. Если игра является определенной, нужно выбирать столбец СЗ.
Так как в этой игре максиминное и минимаксное значения совпадают и равны 2 евро, говорят, что игра является определенной, имеет цену 2 и имеет решение в чистых стратегиях: игрок А выберет F2, игрок Б — СЗ. Также говорят, что 2 является седловой точкой, или точкой равновесия (максимальное из минимальных значений совпадает с минимальным из максимальных).
Этот пример можно обобщить для этого же числа игроков, но дав им возможность выбора не из трех, а из n ходов. Таким образом, платежная матрица будет иметь размеры n × n. Если для игры существует седловая точка, то говорят, что игра имеет точку равновесия, которой соответствует пара чистых стратегий (оптимальных для каждого игрока). Игра имеет стабильный результат, так как одностороннее изменение стратегии одним из игроков приведет к тому, что его результат станет хуже, соответственно, возрастет выигрыш оппонента.
Мы предлагаем читателю проанализировать матрицы следующих игр с нулевой суммой и определить, имеют ли они седловую точку.
Выборы и рестораны: применение игр с чистыми стратегиями
Метод решения абстрактных игр, приведенный в прошлом разделе, можно применить в ситуациях различного рода. Рассмотрим два конкретных примера.
Представим следующую ситуацию: в некой стране во время предвыборных дебатов внимание общественности привлекла постройка объездной магистрали вокруг столицы. Имеются два варианта: трасса может пройти севернее (С) или южнее (Ю) города. Две основные партии страны, А и Б, должны определить предвыборную программу и решить, за какой из вариантов они выступают. Также они могут избежать обсуждения и никак не касаться этого вопроса в предвыборной программе. Руководство обеих партий знает, что их сторонники поддержат любое решение, но остальное население будет склоняться к тому или иному варианту, и если обе партии сделают одинаковый выбор, избиратели воздержатся от голосования. По итогам предвыборных опросов, которые известны обеим партиям, были получены следующие результаты:
Так, если партия А предложит проложить магистраль севернее, а партия Б — южнее, партия А получит 45% голосов. Если же обе партии не будут затрагивать эту тему, партия А получит 35% голосов. Какие решения примут обе партии при заданных условиях?
Если руководствоваться приведенной матрицей, то выбор прост: партия А показывает наилучшие результаты, если будет поддерживать постройку трассы на юге. Именно этого варианта она и будет придерживаться. Аналогично партия Б заметит, что результаты партии А будут наихудшими (что устраивает партию Б), если Б будет избегать этой темы. Такой будет стратегия партии Б. Следовательно, игра имеет седловую точку (партия А голосует за постройку трассы на юге, Б избегает темы), цена игры — 45% голосов в пользу партии А.
Теперь предположим, что матрица имеет следующий вид:
Стратегия партии А по-прежнему ясна: оптимальным вариантом в любом случае является постройка магистрали на севере. Но теперь партия Б не сможет принять оптимальное решение, не зная о выборе партии А. Выбор в пользу постройки на юге (Ю) очень привлекателен, так как в этом случае партия А может остаться лишь с 20% голосов. Однако такой выбор не имеет смысла: если партия А сделает правильный выбор, то в этом случае она получит 55% голосов, а не 20%. Поэтому для партии Б предпочтительнее не касаться этой темы, в результате партия А получит 45% голосов.
Наконец, предположим, что матрица имеет следующий вид:
Теперь ни одна из партий не может сразу сделать выбор, так как оптимальное решение будет зависеть от того, что предпочтет оппонент. Поэтому сторонам нужно определить, какой вариант будет оптимален вне зависимости от выбора соперника. Иными словами, какой вариант — наилучший из худших. Так, если партия А выберет вариант С, то получит минимум 10%, минимум 45% — если выберет Ю, и минимум 10%, если не будет касаться этой темы. Следовательно, оптимальным вариантом является постройка трассы на юге. Аналогично если партия Б выберет вариант С, то партия А получит максимум 45%. Если партия Б выступит за постройку трассы на юге, то партии А может достаться до 55% голосов, а если партия Б уклонится от обсуждения, то партия А получит до 65%. Следовательно, партия Б должна выбрать вариант С.
В этом случае оптимальный выбор для каждой партии приводит к одинаковому результату в 45% голосов в пользу А. Эта точка является седловой, или точкой равновесия.
Двое друзей, Мария и Георгий, хотят открыть ресторан у перекрестка больших дорог за городом, который окружают горы. У них не возникло никаких разногласий, кроме одного: Мария хочет открыть ресторан в низине, а Георгий — высоко в горах, и в этом вопросе их мнения полностью противоположны. Чтобы принять решение, они придумали провести игру: друзья выбрали три параллельных автомагистрали Al, А2 и АЗ, которые идут с запада на восток, и три параллельных дороги С1, С2 и СЗ, которые идут с севера на юг. Эти дороги образуют девять перекрестков. Высота каждого перекрестка приведена в следующей матрице:
Чтобы определить место будущего ресторана, компаньоны решили действовать так: Мария выбирает одну автомагистраль (Al, А2 или АЗ), Георгий — другую (Cl, С2 или СЗ). На пересечении выбранных дорог и будет построен ресторан. Как должен действовать каждый игрок, чтобы ресторан в итоге был построен в соответствии с его интересами?
Георгий — пессимист и из трех минимальных значений (470, 540, 280) выбирает максимум. Он решает выбрать дорогу С2, что гарантирует высоту в 540 метров. Аналогично Мария оценивает максимальную высоту каждой дороги (540, 1050, 930) и выбирает трассу А1, что обеспечивает наименьшую высоту, 540 метров. Итак, оба игрока сделали свой выбор и результат в 540 метров является оптимальным для каждого из них. Иными словами, если один из компаньонов изменит свой выбор, то результат будет меньше соответствовать его интересам.
С одной стороны, эти примеры показывают разнообразие ситуаций, в которых можно найти решение, устраивающее обе стороны с противоположными интересами. С другой стороны, если матрица имеет седловую точку, то результат полностью определяется оптимальным выбором, совершенным обоими соперниками.
Когда равновесия не существует: смешанные стратегии
Многие игры и задачи, в которых используется подобная модель, нельзя решить в чистых стратегиях, так как в них отсутствует точка равновесия. Обычно для каждого игрока не существует доминантной чистой стратегии, то есть стратегии, которая каждый раз будет оптимальной. Напротив, игроки не могут раскрывать свою стратегию и всячески пытаются утаить ее от соперника, в том числе путем обмана. Например, именно так действуют игроки в покер, которые всячески стараются обмануть соперников и раскрывают свои карты только тогда, когда этого прямо требуют правила игры.
Определение оптимальной смешанной стратегии
Вспомним третью (последнюю) игру, о которой говорилось в первом разделе этой главы. Каждый из двух игроков может записать одно из двух чисел: игрок А может записать 1 или 8, игрок Б — 2 или 7. Если четность обоих чисел совпадает (они оба четные или оба нечетные), А выигрывает сумму, равную записанному им числу. Если же одно из чисел четное, а другое — нет, победа остается за игроком Б, который выигрывает сумму, равную записанному им числу. Матрица игры выглядит так:
Игра выглядит справедливой (игрок А может выиграть 1 или 8 евро, игрок Б — 2 или 7), седловой точки не существует: максиминное значение равно -2, минимаксное — 1. Поэтому ни для одного из игроков не существует чистой стратегии. Посмотрим, как в этом случае можно сформировать смешанную стратегию, которая будет оптимальной и позволит определить цену игры.
Смешанная стратегия — это некий «случайный» выбор одной чистой стратегии из набора. Чтобы сформировать смешанную стратегию, каждой чистой стратегии присваивается вероятность, означающая, с какой частотой игрок будет использовать эту чистую стратегию. Например, в нашем случае для игрока А есть две чистые стратегии (записать 1 или записать 8), для Б — две другие. Попробуем найти вероятности
Сначала нужно определить вероятности для чистых стратегий игрока А. Обозначим за р вероятность того, что этот игрок запишет 8. Тогда вероятность написания 1 будет равна 1 — р. Следовательно, если игрок Б запишет 7, ожидаемый выигрыш игрока А составит
V = 1 (1 - р) + (-7) р. Получим линейное уравнение V = 1 - 8р.
Если же, напротив, Б запишет 2, то ожидаемый выигрыш для игрока А составит
V = (-2)(1 - р) + 8р, что равносильно V = 10р — 2.
Игрок А хочет найти, для какого р ожидаемый выигрыш будет наибольшим вне зависимости от того, какую из двух стратегий выберет игрок Б. Решив систему из двух линейных уравнений, получим значения р и V для игрока А. В данной задаче р = 1/6, V = -1/3.
Аналогично можно найти смешанную стратегию для игрока Б. Обозначим за р вероятность того, что он запишет 2. Тогда вероятность того, что он напишет 7, будет равна (1 — р). Если А запишет 1, то ожидаемый выигрыш Б составит
V = 2р + ( -1) (1 - р), что равносильно V = Зр — 1.
Аналогично если А выберет другую стратегию и запишет 8, то ожидаемый выигрыш игрока Б составит
V = ( -8)р + 7 (1 - р), то есть V = 7 - 15р.
Игрок Б хочет найти, для какого р ожидаемый выигрыш будет наибольшим вне зависимости от того, какую из двух стратегий выберет игрок А. Решив систему из двух линейных уравнений, получим значения р и V для игрока Б. Результаты будут следующими: р = 4/9, V* = 1/3.
Метод, который мы только что применили, можно обобщить для матриц 2 × 2 и использовать для решения игр, которые не имеют седловой точки, в смешанных стратегиях. Проанализируем полученные результаты более подробно. Во-первых, заметим, что ожидаемые выигрыши совпадают (V = 1/3) и отличаются только знаком. Для А найденный выигрыш отрицательный, для Б — положительный. Это означает, что Б ожидает выиграть столько, сколько проиграет А. Цена игры (средний выигрыш игрока А) определяется с помощью уравнения (ad - bc)/(а + d - b - с), где a,b,c,d — элементы платежной матрицы (слева направо и сверху вниз). Так, в нашем случае цена игры равна (8 - 14)/18 = -6/18 = -1/3, что означает, что игрок А в среднем будет проигрывать 1 евро за каждые три партии, если оба игрока будут придерживаться оптимальных стратегий.
Теперь мы можем напрямую найти смешанные стратегии как для игрока А, так и для игрока Б. Соотношение, с которым игрок А должен применять смешанные стратегии, можно определить, если найти выигрыш и проигрыш для каждой строки матрицы. Так, его выигрыши равны 1 - (-2) = 3 (для первого ряда) и - 7 - 8 = -15 (для второго ряда). Следовательно, в рамках оптимальной стратегии игрок А должен действовать случайным образом, но соблюдать соотношение 15 к 3, или 5 к 1. Он должен записывать 1 в пять раз чаще (например, перед каждым ходом бросать обычный кубик, на пять граней которого нанесена цифра 1, а на одну грань — цифра 8). Заметим, что этот результат совпадает с тем, который мы получили, решив систему уравнений. Вероятность того, что игрок А запишет 8, должна равняться 1/6, следовательно, вероятность того, что он запишет 1, должна равняться 5/6.
Проведем аналогичные вычисления для игрока Б (по столбцам). Для первого столбца 1 — (—7) = 8, для второго столбца -2 -8 = -10. Следовательно, игрок Б должен придерживаться соотношения 10 к 8, либо, что аналогично, 5 к 4, в пользу числа 7. Это совпадает с решением системы уравнений, приведенной выше: мы вычислили, что вероятность написания 2 должна составлять 4/9, следовательно, вероятность написания 7 должна составлять 5/9.
Теперь мы можем сформулировать оптимальную смешанную стратегию для каждого игрока. А делает ходы произвольным образом, но должен записывать 1 с вероятностью 5/6 и записывать 8 с вероятностью 1/6. Аналогично игрок Б должен произвольным образом выбирать между 7 (с вероятностью 5/9) и 2 (с вероятностью 4/9).
Для всех конечных игр двух игроков с нулевой суммой существует значение V, равное среднему ожидаемому выигрышу игрока А у игрока Б, если оба будут действовать разумно, то есть совершать ходы с целью увеличения выигрыша.
Эта теорема считается основной в теории игр и используется множеством способов даже в этой главе. Фон Нейман, который ее сформулировал и доказал, полагал, что в ее основе лежат три основные предпосылки.
1. Существование стратегии для первого игрока, которая наилучшим образом соответствует его интересам и позволяет ему получить определенный выигрыш (среднюю цену игры). Второй игрок ничего не может сделать против этой стратегии.
2. Существование стратегии для второго игрока, которая наилучшим образом соответствует его интересам и позволяет ему не проиграть более определенного значения (больше средней цены игры). Первый игрок ничего не может сделать против этой стратегии.
3. Тот факт, что игра имеет нулевую сумму, то есть выигрыш одного игрока равен проигрышу другого, означает, что существует некая средняя цена игры. И первый, и второй игрок согласны с этой средней ценой (она будет выигрышем для одного игрока и проигрышем для другого), поскольку любая другая стратегия будет в меньшей степени соответствовать их интересам.
Наконец, несмотря на то что седловой точки не существует, можно показать, что если каждый игрок будет придерживаться оптимальной смешанной стратегии, то игрок Б в среднем будет выигрывать 1/3 евро за партию. Если Б выберет любую другую стратегию, а игрок А будет придерживаться прежней, то выигрыш Б уменьшится. Напротив, если игрок Б будет придерживаться оптимальной стратегии, а игрок А выберет другую, проигрыш А возрастет.
Применение смешанных стратегий
В прошлом разделе мы подробно рассмотрели пример игры, чтобы увидеть, как можно решить игру в смешанных стратегиях для обоих игроков в случае, если игра не имеет седловой точки, то есть максиминное и минимаксное значения не совпадают. Мы рассмотрели абстрактную игру, чтобы читатель не отвлекался и сосредоточил внимание на элементах платежной матрицы, а не задумывался о том, что они означают.
Рассмотрим другие примеры, чтобы увидеть возможные применения метода смешанных стратегий.
Поделиться книгой: