Матрица антагонистической игры имеет вид. Антагонистические игры. а) этот элемент больше всех в столбце

Назначение сервиса . С помощью сервиса в онлайн режиме можно:

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

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

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

Описание алгоритма:

1. На основании анализа платёжной матрицы следует определить, существуют ли в ней доминируемые стратегии, и исключить их.
2. Найти верхнюю и нижнюю цены игры и определить, имеет ли данная игра седловую точку (нижняя цена игры должна быть равна верхней цене игры).
3. Если седловая точка существует, то оптимальными стратегиями игроков, являющимися решением игры, будут их чистые стратегии, соответствующие седловой точке. Цена игры равна верхней и нижней цены игры, которые равны между собой.
4. Если игра не имеет седловой точки, то решение игры следует искать в смешанных стратегиях. Для определения оптимальных смешанных стратегий в играх m × n следует использовать симплекс-метод, предварительно переформулировав игровую задачу в задачу линейного программирования.

Представим алгоритм решения матричной игры графически.

Рисунок - Схема решения матричной игры.

Методы решения матричной игры в смешанных стратегиях

Итак, если седловая точка отсутствует, решение игры проводят в смешанных стратегиях и решают следующими методами:

1. Решение игры через систему уравнений.
   Если задана квадратная матрица nxn (n=m), то вектор вероятностей можно найти, решив систему уравнений. Этот метод используется не всегда и применим только в отдельных случаях (если матрица 2x2 , то решение игры получается практически всегда). Если в решении получаются отрицательные вероятности, то данную систему решают симплекс-методом.
2. Решение игры графическим методом.
   В случаях, когда n=2 или m=2 , матричную игру можно решить графически .
3. Решение матричной игры симплекс-методом.
   В этом случае матричная игра сводится к

Московский Энергетический Институт

(Технический Университет)

Отчёт по лабораторной работе

по теории игр

«Программа поиска оптимальных стратегий для парной антагонистической игры, заданной в матричной форме»

Выполнили студенты

группы А5-01

Ашрапов Далер

Ашрапова Ольга

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

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

Если цели сторон прямо противоположны, то говорят об антагонистическом конфликте .

Игрой называется упрощённая формализованная модель конфликтной ситуации.

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

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

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

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

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

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

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

Классификация теоретико-игровых моделей

Игру n лиц принято обозначать как, где
- множество стратегийi-го игрока,
- платёж игры.

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

Дискретные (множества стратегийдискретны)

Конечные

Бесконечные

Непрерывные (множества стратегий непрерывны)

Бесконечные

n лиц (
)

Коалиционные (кооперативные)

Некоалиционные (некооперативные)

2-х лиц (парные)

Антагонистические (игры с нулевой суммой)

(интересы сторон противоположны, т.е. проигрыш одного игрока равен выигрышу другого)

Неантагонистические

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

С неполной информацией

С нулевой суммой (суммарный платёж равен нулю)

С ненулевой суммой

Одноходовые (лотереи)

Многоходовые

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

В данном пособии будем рассматривать антагонистические игры двух лиц , заданные в матричной форме. Это означает, что нам известно множество стратегий первого игрока (игрокA ){ A i }, i = 1,…, m и множество стратегий второго игрока (игрокB ){ B j }, j = 1,..., n , а также задана матрицаA = || a ij || выигрышей первого игрока. Поскольку речь идёт об антагонистической игре, то предполагается, что выигрыш первого игрока равен проигрышу второго. Считаем, что элемент матрицыa ij – выигрыш первого игрока при выборе им стратегииA i и ответе ему второго игрока стратегиейB j . Такую игру будем обозначать как
, гдеm - количество стратегий игрокаА, n - количество стратегий игрокаВ. В общем виде она может быть представлена следующей таблицей:

	B 1		B j		B n
A 1
A i
A m

Пример 1

В качестве простейшего примера рассмотрим игру, партия которой состоит из двух ходов.

1-й ход : ИгрокА выбирает одно из чисел (1 или 2), не сообщая о своём выборе сопернику.

2-й ход : ИгрокВ выбирает одно из чисел (3 или 4).

Итог : Выборы игроковА иВ складываются. Если сумма чётная, тоВ выплачивает её значение игрокуА , если же нечётная - наоборот,А выплачивает сумму игрокуВ .

Данная игра может быть представлена в виде
следующим образом:

	(выбор 3)	(выбор 4)
(выбор 1)
(выбор 2)

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

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

При решении игры в матричной форме следует проверить игру на наличие седловой точки . Для этого вводятся две величины:

– нижняя оценка цены игры и

– верхняя оценка цены игры.

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

Можно доказать, что α ≤ V ≤ β , гдеV –цена игры , т.е., вероятный выигрыш первого игрока.

Если выполняется соотношение α = β = V , то говорят, чтоигра имеет седловую точку
, ирешается в чистых стратегиях . Иными словами, имеется пара стратегий
, дающих игрокуА V .

Пример 2

Вернёмся к игре, рассмотренной нами в примере 1 и проверим её на наличие седловой точки.

	(выбор 3)	(выбор 4)
(выбор 1)
(выбор 2)

Для данной игры
= -5,
= 4,
, следовательно, она не имеет седловой точки.

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

Пример 3

Внесём в правила игры из примера 1 некоторые изменения. Предоставим игроку В информацию о выборе игрокаА. Тогда уВ появятся две дополнительные стратегии:

- стратегия, выгодная дляА. Если выборА - 1, то В выбирает 3, если выборА - 2, то В выбирает 4;

- стратегия, не выгодная дляА. Если выборА - 1, то В выбирает 4, если выборА - 2, то В выбирает 3.

	(выбор 3)	(выбор 4)
(выбор 1)
(выбор 2)

Эта игра - с полной информацией.

В данном случае
= -5,
= -5,
, следовательно, игра имеет седловую точку
. Данной седловой точке соответствуют две пары оптимальных стратегий:
и
. Цена игрыV = -5. Очевидно, что дляА такая игра невыгодна.

Примеры 2 и 3 являются неплохой иллюстрацией к следующей теореме, доказанной в теории игр:

Теорема 1

Всякая парная антагонистическая игра с полной информацией решается в чистых стратегиях.

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

Вслучае же отсутствия седловой точки, в качестве решения используются т.н.смешанные стратегии :, гдеp i и q j – вероятности выбора стратегийA i и B j первым и вторым игроками соответственно. Решением игры в данном случае является пара смешанных стратегий
, максимизирующих математическое ожидание цены игры.

Обобщением теоремы 1 на случай игры с неполной информацией служит следующая теорема:

Теорема 2

Любая парная антагонистическая игра имеет хотя бы одно оптимальное решение, т.е., пару в общем случае смешанных стратегий
, дающих игрокуА устойчивый выигрыш, равный цене игрыV , причёмα ≤ V ≤ β .

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

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

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?

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

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

Таблица 26.1

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

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

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

Давайте, поразмышляем о том, какой стратегией нам (игроку А) воспользоваться? В матрице 26.2 есть соблазнительный выигрыш «10»; нас так и тянет выбрать стратегию при которой этот «лакомый кусок» нам достанется.

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

Таблица 26.2

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

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

Таблица 26.3

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

Этот выигрыш называется нижней ценой игры (или «максимином» - максимальный из минимальных выигрышей). Будем обозначать его а. В нашем случае

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

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

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

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

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

Таблица 26.4

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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