Решения антагонистической игры в смешанных стратегиях. Антагонистические матричные игры

Рассмотрим конечную парную игру с нулевой суммой. Обозначим через a выигрыш игрока A , а через b – выигрыш игрока B . Так как a = –b , то при анализе такой игры нет необходимости рассматривать оба этих числа – достаточно рассматривать выигрыш одного из игроков. Пусть это будет, например, A . В дальнейшем для удобства изложения сторону A будем условно именовать "мы ", а сторону B – "противник ".

Пусть у нас имеется m возможных стратегийA 1 , A 2 , …, A m , а у противника n возможных стратегий B 1 , B 2 , …, B n (такая игра называется игрой m×n ). Предположим, что каждая сторона выбрала определенную стратегию: мы выбрали A i , противник B j . Если игра состоит только из личных ходов, то выбор стратегий A i и B j однозначно определяет исход игры – наш выигрыш (положительный или отрицательный). Обозначим этот выигрыш через a ij (выигрыш при выборе нами стратегии A i , а противником – стратегии B j ).

Если игра содержит кроме личных случайные ходы, то выигрыш при паре стратегий A i , B j есть величина случайная, зависящая от исходов всех случайных ходов. В этом случае естественной оценкой ожидаемого выигрыша является математическое ожидание случайного выигрыша . Для удобства будем обозначать через a ij как сам выигрыш (в игре без случайных ходов), так и его математическое ожидание (в игре со случайными ходами).

Предположим, что нам известны значения a ij при каждой паре стратегий. Эти значения можно записать в виде матрицы, строки которой соответствуют нашим стратегиями (A i ), а столбцы – стратегиям противника (B j ):

Такая матрица называется платежной матрицей игры или просто матрицей игры .

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

Рассмотрим пример 1 антагонистической игры 4×5. В нашем распоряжении есть четыре стратегии, у противника – пять стратегий. Матрица игры следующая:

Какой стратегией нам (т.е. игроку A ) воспользоваться? Какую бы мы ни выбрали стратегию, разумный противник ответит на нее той стратегией, для которой наш выигрыш будет минимальным. Например, если мы выберем стратегию A 3 (соблазнившись выигрышем 10), противник в ответ выберет стратегию B 1 , и наш выигрыш будет всего лишь 1. Очевидно, исходя из принципа осторожности (а он – основной принцип теории игр), надо выбирать ту стратегию, при которой наш минимальный выигрыш максимален .

Обозначим через α i минимальное значение выигрыша для стратегии A i :

и добавим к матрице игры столбец, содержащий эти значения:

Выбирая стратегию, мы должны предпочесть ту, для которой значение α i максимально. Обозначим это максимальное значение через α :

Величина α называется нижней ценой игры или максимином (максимум минимального выигрыша). Стратегия игрока A , соответствующая максимину α , называется максиминной стратегией .

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

Теперь проведем аналогичные рассуждения за противника B B A B 2 – мы ему ответим A .

Обозначим через β j A B ) для стратегии A i :

β j β :

7.ЧТО НАЗЫВАЕТСЯ ВЕРХНЕЙ ЦЕННОЙ ИГРЫТеперь проведем аналогичные рассуждения за противника B . Он заинтересован в том, чтобы обратить наш выигрыш в минимум, то есть отдать нам поменьше, но должен рассчитывать на наше, наихудшее для него, поведение. Например, если он выберет стратегию B 1 , то мы ответим ему стратегией A 3 , и он отдаст нам 10. Если выберет B 2 – мы ему ответим A 2 , и он отдаст 8 и т. д. Очевидно, осторожный противник должен выбрать ту стратегию, при которой наш максимальный выигрыш будет минимален .

Обозначим через β j максимальные значения в столбцах платежной матрицы (максимальный выигрыш игрока A , или, что то же самое, максимальный проигрыш игрока B ) для стратегии A i :

и добавим к матрице игры строку, содержащую эти значения:

Выбирая стратегию, противник предпочтет ту, для которой значение β j минимально. Обозначим его через β :

Величина β называется верхней ценой игры или минимаксом (минимум максимального выигрыша). Соответствующая минимаксу стратегия противника (игрока B ), называется минимаксной стратегией .

Минимакс – это значение выигрыша, больше которого заведомо не отдаст нам разумный противник (иначе говоря, разумный противник проиграет не больше, чем β ). В данном примере минимакс β равен 5 (соответствующая клетка в таблице выделена серым цветом) и достигается он при стратегии противника B 3 .

Итак, исходя из принципа осторожности («всегда рассчитывай на худшее!»), мы должны выбрать стратегию A 4 , а противник – стратегию B 3 . Принцип осторожности является в теории игр основным и называется принципом минимакса .

Рассмотрим пример 2 . Пусть игроки A и В одновременно и независимо друг от друга записывают одно из трех чисел: либо «1», либо «2», либо «3». Если сумма записанных чисел оказывается четной, то игрок B платит игроку A эту сумму. Если сумма нечетная, то эту сумму выплачивает игрок A игроку В .

Запишем платежную матрицу игры, и найдем нижнюю и верхнюю цены игры (номер стратегии соответствует записанному числу):

Игрок A должен придерживаться максиминной стратегии A 1 , чтобы выиграть не меньше –3 (то есть чтобы проиграть не больше 3). Минимаксная стратегия игрока B – любая из стратегий B 1 и B 2 , гарантирующая, что он отдаст не более 4.

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

Исходя из этой матрицы следует, что игрок B должен придерживаться любой из стратегий B 1 и B 2 (и тогда он проиграет не более 4), а игрок A – стратегии A 1 (и тогда он проиграет не более 3). Как видно, результат в точности совпадает с полученным выше, поэтому при анализе не важно, с точки зрения какого игрока мы его проводим.

8 ЧТО НАЗЫВАЕТСЯ ЦЕННОВОЙ ИГРОЙ.

9.В ЧЕМ СОСТОЙТ ПРИНЦЕП МИНИМАКСА.2. Нижняя и верхняя цена игры. Принцип минимакса

Рассмотрим матричную игру типа с платежной матрицей

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

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

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

Таким образом, Игрок 1 выбирает i

Игрок 2 точно также стремится обеспечить себе наивысшую величину выигрыша (или, что эквивалентно, наименьшую величину проигрыша) вне зависимости от выбранной стратегии противника. Его оптимальной стратегией будет столбец Н 0 с наименьшим максимальным платежом. Таким образом, Игрок 2 выберет j -ю стратегию, которая является решением задачи

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

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

В случае, когда верхняя цена игры равна нижней, т.е. = , оба игрока получают свои гарантированные платежи, а значение h ij * называется ценой игры .

Элемент матрицы h ij матрицы выигрышей, соответствующей стратегиям, называется седловой точкой матрицы Н .

В случае, если цена антагонистической игры равна 0, игра называется справедливой .

Рассмотрим игру, в которой Игрок 1 располагает двумя стратегиями, а Игрок 2 – тремя. Матрица выигрышей Игрока 1 имеет вид:

Замечание . Поскольку мы рассматриваем пример антагонистической игры, то матрица выигрышей Игрока 2 будет Н 2 =-Н 1 .

Игрок 1 рассчитывает, что если он выберет первую стратегию (т.е. первую строку матрицы Н 1 ), то противник выберет свою вторую стратегию (т.е. второй столбец) так, что выигрыш будет равен 1 . Если же он выбирает вторую стратегию, то противник может выбрать первую стратегию, так что выигрыш будет равен -1.

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

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

Взяв минимальные значения этих максимумов, Игрок 2 останавливается на своей второй стратегии, при которой его проигрыш минимален и равен :

Следовательно, в этой игре существуют совместные выборы стратегий, те. Е

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

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

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

Рассмотрим пример такой игры:

Для этой игры .

В итоге если игроки будут следовать предложенным выше правилам, то Игрок 1 выберет стратегию 1 и будет ожидать, что Игрок 2 выберет стратегию 2, при которой проигрыш равен -2, в то время как Игрок 2 изберет стратегию 3 и будет ожидать что Игрок 1 выберет стратегию 2 с выигрышем равным 4.

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

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

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

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

или матричных обозначениях

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

.

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

.

Фундаментальным результатом теории игр является так называемая Теорема о минимаксе, которая утверждает, что сформулированные задачи Игрока 1 и Игрока 2 всегда имеют решение для любой матрицы выигрышей , и кроме того, .

Как и для вполне определенных игр, стратегия Игрока 1 называется Максиминной стратегией , стратегия Игрока 2 - минимаксной стратегией, значение - ценой игры; в случае, когда игра называется справедливой.

Очевидным следствием из Теоремы о минимаксе является соотношение:

.

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

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

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

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

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

Аналогично -й столбец доминирует -й столбец, если для всех , хотя бы для одного .

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

Пример. Рассмотрим игру со следующей матрицей:

Исключение второй строки приводит к матрице: третий столбец в этой урезанной матрице доминирует второй, и исключение второго столбца дает: .

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

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

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

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

Например, матрица выигрышей имеет вид: .

Пусть Игрок 1 выбирает свою первую стратегию с вероятностью , а вторую с вероятностью . Если Игрок 2 выбирает свою первую стратегию, то (из первого столбца матрицы) математическое ожидание для Игрока 1 будет равно . Если Игрок 2 выбирает свою вторую стратегию, то в соответствии со вторым столбцом матрицы: .

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

Самым простым случаем, подробно разработанным в теории игр, является конечная парная игра с нулевой суммой (антагонистическая игра двух лиц или двух коалиций). Рассмотрим такую игру G , в которой участвуют два игрока А и В, имеющие противоположные интересы: выигрыш одного равен проигрышу другого. Так как выигрыш игрока А равен выигрышу игрока В с обратным знаком, мы можем интересоваться только выигрышем а игрока А. Естественно, А хочет максимизировать, а В - минимизировать а. Для простоты отождествим себя мысленно с одним из игроков (пусть это будет А) и будем его называть «мы», а игрока В - «противник» (разумеется, никаких реальных преимуществ для А из этого не вытекает). Пусть у нас имеется т возможных стратегий А 1 , A 2 , ..., А m , а у противника - n возможных стратегий В 1 , В 2 , ..; В n (такая игра называется игрой т × n ). Обозначим а ij наш выигрыш в случае, если мы пользуемся стратегией A i , а противник-стратегией B j .

Таблица 26.1

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

Если такая таблица составлена, то говорят, что игра G приведена к матричной форме (само по себе приведение игры к такой форме уже может составить трудную задачу, а иногда и практически невыполнимую, из-за необозримого множества стратегий). Заметим, что если игра приведена к матричной форме, то многоходовая игра фактически сведена к одноходовой - от игрока требуется сделать только один ход: выбрать стратегию. Будем кратко обозначать матрицу игры (a ij ).

Рассмотрим пример игры G (4×5) в матричной форме. В нашем распоряжении (на выбор) четыре стратегии, у противника - пять стратегий. Матрица игры дана в таблице 26.2

Давайте, поразмышляем о том, какой стратегией нам (игроку А) воспользоваться? В матрице 26.2 есть соблазнительный выигрыш «10»; нас так и тянет выбрать стратегию А 3 , при которой этот «лакомый кусок» нам достанется. Но постойте: противник тоже не дурак! Если мы выберем стратегию А 3 , он, назло нам, выберет стратегию В 3 , и мы получим какой-то жалкий выигрыш «1». Нет, выбирать стратегию А 3 нельзя! Как же быть? Очевидно, исходя из принципа осторожности (а он - основной принцип теории игр), надо выбрать

Таблица 26.2

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

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

Таблица 26.3

Из всех значений α i (правый столбец) выделено наибольшее (3). Ему соответствует стратегия A 4 . Выбрав эту стратегию, мы, во всяком случае, можем быть уверены, что (при любом поведении противника) выиграем не меньше, чем 3. Эта величина - наш гарантированный выигрыш; ведя себя осторожно, меньше этого мы получить не можем (я, может быть, получим и больше). Этот выигрыш называется нижней ценой игры (или «максимином» - максимальный из минимальных выигрышей). Будем обозначать его а. В нашем случае α = 3.

Теперь станем на точку зрения противника и порассуждаем за него. Он ведь не пешка какая-нибудь, а тоже разумен! Выбирая стратегию, он хотел бы отдать поменьше, но должен рассчитывать на наше, наихудшее для него, поведение. Если он выберет стратегию В 1 , мы ему ответим А 3 , и он отдаст 10; если выберет B 2 - мы ему ответим А 2 , и он отдаст 8 и т. д. Припишем к таблице 26.3 добавочную нижнюю строку и в ней запишем максимумы столбцов β j . Очевидно, осторожный противник должен выбрать ту стратегию, при которой эта величина минимальна (соответствующее значение 5 выделено в таблице 26.3). Эта величина β - то значение выигрыша, больше которого заведомо не отдаст нам разумный противник. Она называется верхней ценой игры (или «минимаксом» - минимальный из максимальных выигрышей). В нашем примере β = 5 и достигается при стратегии противника B 3 .

Итак, исходя из принципа осторожности (перестраховочного правила «всегда рассчитывай на худшее!»), мы должны выбрать стратегию А 4 , а противник - стратегию В 3 . Такие стратегии называются «минимаксными» (вытекающими из принципа минимакса). До тех пор, пока обе стороны в нашем примере будут придерживаться своих минимаксных стратегий, выигрыш будет равен а 43 = 3.

Теперь представим себе на минуту, что мы узнали о том, что противник придерживается стратегии В 3 . А ну-ка, накажем его за это и выберем стратегию А 1 - мы получим 5, а это не так уж плохо. Но ведь противник - тоже не промах; пусть он узнал, что наша стратегия А 1 ; он тоже поторопится выбрать В 4 , сведя наш выигрыш к 2, и т. д. (партнеры «заметались по стратегиям»). Одним словом, минимаксные стратегии в нашем примере неустойчивы по отношению к информации о поведении другой стороны; эти стратегиине обладают свойством равновесия.

Всегда ли это так? Нет, не всегда. Рассмотрим пример с матрицей, данной в таблице 26.4.

В этом примере нижняя Цена игры равна верхней: α = β = 6. Что из этого вытекает? Минимаксные стратегии игроков А и В будут устойчивыми. Пока оба игрока их придерживаются, выигрыш равен 6. Посмотрим, что будет, если мы (А) узнаем, что противник (В)

Таблица 26.4

держится стратегии B 2 ? А ровно ничего не изменится. Потому что любое отступление от стратегии А 2 может только ухудшить наше положение. Равным образом, информация, полученная противником, не заставит его отступить от своей стратегии В 2 . Пара стратегий А 2 , B 2 обладает свойством равновесия (уравновешенная пара стратегий), а выигрыш (в нашем случае 6), достигаемый при этой паре стратегий, называется «седловой точкой матрицы» 1). Признак наличия седловой точки и уравновешенной пары стратегий - это равенство нижней и верхней цены игры; общее значение α и β называется ценой игры. Мы будем обозначать его v :

α = β = v

Стратегии A i , B j (в данном случае А 2 , В 2 ), при которых этот выигрыш достигается, называются оптимальными чистыми стратегиями, а их совокупность - решением игры. Про саму игру в этом случае говорят, что она решается в чистых стратегиях. Обеим сторонам А и В можно указать их оптимальные стратегии, при которых их положение - наилучшее из возможных. А что игрок А при этом выигрывает 6, а игрок В - проигрывает 6,- что же, Таковы условия игры: они выгодны для А и невыгодны для В

1) Термин «седловая точка» взят из геометрии - так называется точка на поверхности, где одновременно достигается минимум по одной координате и максимум по другой.

У читателя может возникнуть вопрос: а почему оптимальные стратегии называются «чистыми»? Несколько забегая вперед, ответим на этот вопрос: бывают стратегии «смешанные», состоящие в том, что игрок применяет не одну какую-то стратегию, а несколько, перемежая их случайным образом. Так вот, если допустить кроме чистых еще и смешанные стратегии, всякая конечная игра имеет решение - точку равновесия. Но об атом речь еще впереди.

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

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

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

А теперь спросим себя, как быть, если игра не имеет седловой точки: α ≠ β ? Ну что же, если каждый игрок вынужден выбрать одну - единственную чистую стратегию, то делать нечего: надо руководствоваться принципом минимакса. Другое дело, если можно скоп стратегии «смешивать», чередовать случайным образом с какими-то вероятностями. Применение смешанных стратегий мыслится таким образом: игра повторяется много раз; перед каждой партией игры, когда игроку предоставляется личный ход, он «передоверяет» свой выбор случайности, «бросает жребий», и берет ту стратегию, которая выпала (как организовать жребий, мы уже знаем из предыдущей главы).

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

Итак, поговорим о смешанных стратегиях. Будем обозначать смешанные стратегии игроков А и В соответственно S A = (p 1 , р 2 , ..., p m ), S B = (q 1 , q 2 , …, q n ), где p 1 , p 2 , …, p m (образующие в сумме единицу) - вероятности применения игроком А стратегий А 1 , A 2 ,… , A m ; q 1 , q 2 , …, q n -вероятности применения игроком В стратегий В 1 , В 2 , ..., В n . В частном случае, когда все вероятности, кроме одной, равны нулю, а эта одна - единице, смешанная стратегия превращается в чистую.

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

Пара оптимальных стратегий
образующих решение игры, обладает следующим свойством:если один из игроков придерживается своей оптимальной стратегии, то другому не может быть выгодно, отступать от своей. Эта пара стратегий образует в игре некое положение равновесия: один игрок хочет обратить выигрыш в максимум, другой - в минимум, каждый тянет в свою сторону и, при разумном поведении обоих, устанавливается равновесие и устойчивый выигрыш v. Если v > 0, то игра выгодна для нас, если v < 0 - для противника; при v = 0 игра «справедливая», одинаково выгодная для обоих участников.

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

Составим матрицу игры. В одной партии у каждого игрока три стратегии: показать один, два или три пальца. Матрица 3×3 дана в таблице 26.5; в дополнительном правом столбце приведены минимумы строк, а в дополнительной нижней строке - максимумы столбцов.

Нижняя цена игры α = - 3 и соответствует стратегии A 1 . Это значит, что при разумном, осторожном поведении мы гарантируем, что не проиграем больше, чем 3. Слабое утешение, но все же лучше, чем, скажем, выигрыш - 5, встречающийся в некоторых клетках матрицы. Плохо нам, игроку А... Но утешимся:

положение противника, кажется, еще хуже: нижняя цена игры β = 4, т. е. при разумном поведении он отдаст нам минимум 4. В общем, положение не слишком хорошее - ни для той, ни для другой стороны. Но посмотрим: нельзя ли его улучшить? Оказывается, можно. Если каждая сторона будет применять не одну какую-то чистую стратегию, а смешанную, в которую

Таблица 26.5

первая и третья входят с вероятностями 1/4, а вторая - с вероятностью 1/2, т. е.

то средний выигрыш будет устойчиво равен нулю (значит, игра «справедлива» и одинаково выгодна той и другой стороне). Стратегии
образуют решение игры, а ее ценаv = 0. Как мы это решение нашли? Это вопрос другой. В следующем параграфе мы покажем, как вообще решаются конечные игры.

Тесты для итогового контроля

1. Антагонистическая игра может быть задана:

а) множеством стратегий обоих игроков и седловой точкой.

б) множеством стратегий обоих игроков и функцией выигрыша первого игрока.

2. Цена игры существует для матричных игр в смешанных стратегиях всегда.

а) да.

3.Если в матрице выигрышей все столбцы одинаковы и имеют вид (4 5 0 1), то какая стратегия оптимальна для 1-го игрока?

а) первая.

б)вторая.

в)любая из четырех.

4.Пусть в матричной игре одна из смешанных стратегий 1-го игрока имеет вид (0.3, 0.7), а одна из смешанных стратегий 2-го игрока имеет вид (0.4, 0, 0.6). Какова размерность этой матрицы?

а) 2*3.

в) другая размерность.

5. Принцип доминирования позволяет удалять из матрицы за один шаг:

а) целиком строки.

б) отдельные числа.

6.В графическом методе решения игр 2*m непосредственно из графика находят:

а) оптимальные стратегии обоих игроков.

б) цену игры и оптимальные стратегии 2-го игрока.

в) цену игры и оптимальные стратегии 1-го игрока.

7.График нижней огибающей для графического метода решения игр 2*m представляет собой в общем случае:

а) ломаную.

б) прямую.

в) параболу.

8. В матричной игре 2*2 две компоненты смешанной стратегии игрока:

а) определяют значения друг друга.

б) независимы.

9. В матричной игре элемент aij представляет собой:

а) выигрыш 1-го игрока при использовании им i-й стратегии, а 2-м – j-й стратегии.

б) оптимальную стратегию 1-го игрока при использовании противником i-й или j-й стратегии.

в) проигрыш 1-го игрока при использовании им j-й стратегии, а 2-м – i-й стратегии.

10.Элемент матрицы aij соответствует седловой точке. Возможны следующие ситуации:

а) этот элемент строго меньше всех в строке.

б) этот элемент второй по порядку в строке.

11. В методе Брауна-Робинсон каждый игрок при выборе стратегии на следующем шаге руководствуется:

а) стратегиями противника на предыдущих шагах.

б) своими стратегиями на предыдущих шагах.

в) чем-то еще.

12. По критерию математического ожидания каждый игрок исходит из того, что:

а) случится наихудшая для него ситуация.

в) все или некоторые ситуации возможны с некоторыми заданными вероятностями.

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

б) нет.

в) нет однозначного ответа.

14. Цена игры - это:

а) число.

б) вектор.

в) матрица.

15.Какое максимальное число седловых точек может быть в игре размерности 5*5 (матрица может содержать любые числа) :

16. Пусть в матричной игре размерности 2*3 одна из смешанных стратегий 1-го игрока имеет вид (0.3, 0.7), а одна из смешанных стратегий 2-го игрока имеет вид (0.3, x, 0.5). Чему равно число x?

в) другому числу.

17. Для какой размерности игровой матрицы критерий Вальда обращается в критерий Лапласа?

в)только в других случаях.

18. Верхняя цена игры всегда меньше нижней цены игры.

б) нет.

б) вопрос некорректен.

19. Какие стратегии бывают в матричной игре:

а) чистые.

б) смешанные.

в) и те, и те.

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

а) всегда.

б) иногда.

в) никогда.

21.Пусть в матричной игре одна из смешанных стратегий 1-го игрока имеет вид (0.3, 0.7), а одна из смешанных стратегий 2-го игрока имеет вид (0.4, 0.1,0.1,0.4). Какова размерность этой матрицы?

в) иная размерность.

22. Принцип доминирования позволяет удалять из матрицы за один шаг:

а) целиком столбцы,

б) отдельные числа.

в) подматрицы меньших размеров.

23. В матричной игре 3*3 две компоненты смешанной стратегии игрока:

а) определяют третью.

б) не определяют.

24. В матричной игре элемент aij представляет собой:

а) проигрыш 2-го игрока при использовании им j-й стратегии, а 2-м – i-й стратегии .

б) оптимальную стратегию 2-го игрока при использовании противником i-й или j-й стратегии,

в) выигрыш 1-го игрока при использовании им j-й стратегии, а 2-м – i-й стратегии,

25. Элемент матрицы aij соответствует седловой точке. Возможны следующие ситуации:

а) этот элемент больше всех в столбце.

б) этот элемент строго больше всех по порядку в строке.

в) в строке есть элементы и больше, и меньше, чем этот элемент.

26. По критерию Вальда каждый игрок исходит из того, что:

а) случится наиболее плохая для него ситуация.

б) все ситуации равновозможны.

в) все ситуации возможны с некоторыми заданными вероятностями.

27. Нижняя цена меньше верхней цены игры:

б) не всегда.

в) никогда.

28. Сумма компонент смешанной стратегия для матричной игры всегда:

а) равна 1.

б) неотрицательна.

в) положительна.

г) не всегда.

29. Пусть в матричной игре размерности 2*3 одна из смешанных стратегий 1-го игрока имеет вид (0.3, 0.7), а одна из смешанных стратегий 2-го игрока имеет вид (0.2, x, x). Чему равно число x?

Введение

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

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

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

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

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

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

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

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

Задача теории состоит в том, что является:

1) оптимальным поведением в игре.

2) исследование свойств оптимального поведения

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

4) построение численных методов нахождения оптимального поведения.

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

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

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

Математическая ТЕОРИЯ ИГР началась с анализа спортивных, карточных и других игр. Рассказывают, что первооткрыватель теории игр, выдающийся американский математик XXв. Джон фон Нейман пришел к идеям своей теории, наблюдая за игрой в покер. Отсюда и произошло название «теория игр».

Начнем исследование данной темы с ретроспективного анализа развития теории игр. Рассмотрим историю и развитие вопроса теории игр. Обычно «генеалогическое дерево» представляется в виде дерева в смысле теории графов, в которых разветвление происходит от некоторого единого «корня». Родословная теории игр - книга Дж. фон Неймана и О. Моргенштерна. Поэтому исторический ход развития теории игр как математической дисциплины, естественным образом расчленяется на три этапа:

Первый этап - до выхода в свет монографии Дж. фон Неймана и О. Моргенштерна. Его можно назвать «до монографическим». На этом этапе игра выступает пока еще как конкретное состязание, описываемое своими правилами в содержательных терминах. Лишь в конце его Дж. фон Нейман вырабатывает представление об игре как об общей модели абстрактного конфликта. Итогом этого этапа явилось накопление ряда конкретных математических результатов и даже отдельных принципов будущей теории игр.

Второй этап составляет сама монография Дж. фон Неймана и

О. Моргенштерна «Теория игр и экономическое поведение» (1944), объединившая в себе большинство ранее полученных (впрочем, по современным математическим масштабам довольно немногочисленных) результатов. Она впервые представила математический подход к играм (как в конкретном, так и в абстрактном понимании этого слова) в виде систематической теории.

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

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

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

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

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

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