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

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

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

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

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

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

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

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

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

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

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. Пусть матричная игра задана матрицей, в которой все элементы отрицательны. Цена игры положительна:

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

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. Сумма компонент смешанной стратегия для матричной игры всегда:

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

Источник

Теория игр. Матричные игры. Онлайн калькулятор

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

Предупреждение

Теория игр − теоретическая часть

Бывают ситуации, в которых сталкиваются интересы двух и более сторон. При этом эффективность принимаемого решения одной стороны зависит от действий другой стороны. Такие ситуации называются конфликтными. Конфликтная ситуация называется антагонистической, если увеличение выигрыша одной стороны на определенную величину приводит к уменьшению выигрыша другой стороны на такую же величину. Математическая модель таких ситуаций описывается матричной игрой. Участники игры (т.е. лица, принимающие решение) называются игроками. Принятие игроком того или иного решения в процессе игры и его реализация называется ходом. Ходы могут быть личными (т.е. сознательными) и случайными. Стратегия игрока − осознанный выбор одного из множества вариантов его действий. Стратегия называется чистой, если выбор игрока неизменен от партии к партии. У первого игрока есть m чистых стратегий, а у второго игрока n чистых стратегий. Если множество стратегий игроков конечный, то игра называется конечной, а если хотя бы у одного игрока множество стратегий бесконечно, то игра называется бесконечной. Стратегия игрока называется оптимальной, если она обеспечивает данному игроку (при многократном повторении) максимально возможный средний выигрыш или минимально возможный средний проигрыш.

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

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

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

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

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

Таким образом игра с нулевой суммой однозначно определяется матрицей

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

Игра проходит партиями. Партия начинается с первого игрока. Он выбирает некоторую строку i матрицы. В ответ на это второй игрок выбирает некоторый столбец j. На этом заканчивается партия и второй игрок платит первому сумму a_ij, если a_ij>0 или первый игрок платит сумму a_ij второму игроку, если a_ij Теорема 1. В матричной игре нижняя цена игры не превосходит верхней цены, т.е. α ≤ β.

Если для чистых стратегий A_k и B_l игроков A и B имеет место равенство α = β, то пару чистых стратегий (A_k,B_l) называют седловой точкой матричной игры а γ=α = β чистой ценой игры. Элемент a_kl называют седловым элементом платежной матрицы.

Заметим, что отклонение игрока A от максимальной стратегии A_k ведет к уменьшению его выигрыша, а отклонение игрока B от минимальной стратегии B_l ведет к увеличению его проигрыша. Поэтому A_k и B_l являются оптимальными чистыми стратегиями игроков A и B, соответственно.

Тройку (A_k, B_l, γ) называют решением матричной игры. Если игра имеет седловую точку, то говорят, что она решается в чистых стратегиях.

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

Если матричная игра не имеет седловой точки, то α ≠ β, и, Теорему 1, получим: α * и q * называются оптимальными, если они образуют седловую точку для платежной функции M(p,q), т.е.

Значение платежной функции при оптимальных смешанных стратегиях p * и q * называют ценой игры:

Теорема 2 (Основная теорема теории матричных игр). В любой матричной игре у игроков есть оптимальные смешанные стратегии.

Доказательство. Пусть игра имеет платежную матрицу

где все элементы положительны.

Математическое ожидание выигрыша игрока A равна:

При любом выборе игроками своих смешанных стратегий p и q, математическое ожидание будет положительным, так как все элементы a_ij платежной матрицы положительны, p_i неотрицательные числа и среди них есть хотя бы одно положительное число, q_j неотрицательные числа и среди них есть хотя бы одно положительное число.

так как a_ij >0, i=1,2. m, j=1,2. n. Поскольку α>0 и γ не может быть меньше нижней цены игры, то γ ≥ α, а так как α>0, то γ >0.

Пусть игрок A выбирает такую стратегию p, что математическое ожидание его выигрыша независимо от того, какую стратегию выбирает игрок B было не меньше некоторой величины γ:

где p_i >0, i=1,2. m, . Каждая строка в системе линейных неравенств (3) соотвесттвует определенной стратегии игрока B.

Преобразуем систему нерравенств (3), введя новые обозначения:

Разделим все неравенства системы (3) на положительное число γ. Тогда имеем:

Цель игрока A − максимизировать свой гарантированный выигрыш γ или минимизировать величину

Таким образом, приходим к следующей задаче линейного программирования:

Сделав аналогичные рассуждения с позиции игрока B, получим следующую задачу линейного программирования:

Покажем, что задачи линейного программирования (4) и (5) имеют допустимые решения. Так как a_ij >0, то можно подобрать достаточно большие положительные числа y_i, i=1,2. m так, чтобы выполнялись неравенства (4b). Значит задача линейного программирования (4) имеет допустимое решение.

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

Найдем оптимальные смешанные стратегии игроков:

,

.

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

Если в матрице есть отрицательные элементы или нули, то можно сделать матрицу положительным, добавив к каждому элементу матрицы достаточно большое положительное число r. Тогда получим следующую матрицу A’(a_ij+r).

Математическое ожидание выигрыша игрока A с платежной матрицей A(a_ij):

Математическое ожидание игрока A с платежной матрицей A’(a_ij+r):

Игра с платежной матрицей A’ имеет седловую точку в смешанных стратегиях:

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

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

Источник

Матричные игры: примеры решения задач

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

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

Теперь обо всём по порядку и подробно.

Платёжная матрица, чистые стратегии, цена игры

В матричной игре её правила определяет платёжная матрица.

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

Составим платёжную матрицу:

.

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

.

Как происходит выбор стратегии в матричной игре?

Вновь посмотрим на платёжную матрицу:

.

Пример 1. Дана матричная игра с платёжной матрицей

.

Определить максиминную стратегию первого игрока, минимаксную стратегию второго игрока, нижнюю и верхнюю цену игры.

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

Итак, гарантированный выигрыш первого игрока:

.

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

.

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

.

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

.

Ещё пример из этой же серии.

Пример 2. Дана матричная игра с платёжной матрицей

.

Определить максиминную стратегию первого игрока, минимаксную стратегию второго игрока, нижнюю и верхнюю цену игры.

Седловая точка в матричных играх

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

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

В этом случае матричная игра имеет решение в чистых стратегиях.

Пример 3. Дана матричная игра с платёжной матрицей

.

Найти нижнюю и верхнюю цену игры. Имеет ли данная матричная игра седловую точку?

Решить задачу на матричную игру самостоятельно, а затем посмотреть решение

Пример 4. Дана матричная игра с платёжной матрицей

.

Найти нижнюю и верхнюю цену игры. Имеет ли данная матричная игра седловую точку?

Матричные игры с оптимальной смешанной стратегией

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

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

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

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

.

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

.

.

Если уже подзабыто произведение матриц, то следует повторить материал.

Пример 5. Дана матричная игра с платёжной матрицей

.

Определить математическое ожидание выигрыша первого игрока (проигрыша второго игрока), если смешанная стратегия первого игрока , а смешанная стратегия второго игрока .

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

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

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

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

,

.

В таком случае для функции E существует седловая точка, что означает равенство .

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

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

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

Функция цели в прямой задаче линейного программирования:

.

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

Функция цели в двойственной задаче:

.

Система ограничений в двойственной задаче:

Оптимальный план прямой задачи линейного программирования обозначим

,

а оптимальный план двойственной задачи обозначим

Линейные формы для соответствующих оптимальных планов обозначим и ,

а находить их нужно как суммы соответствующих координат оптимальных планов.

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

,

.

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

,

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

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

,

,

Пример 6. Дана матричная игра с платёжной матрицей

.

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

Решение. Составляем соответствующую данной матричной игре задачу линейного программирования:

Получаем решение прямой задачи:

.

Находим линейную форму оптимальных планов как сумму найденных координат:

.

Получаем решение двойственной задачи:

.

Находим линейную форму оптимальных планов как сумму найденных координат:

.

.

Находим оптимальную смешанную стратегию первого игрока:

.

Находим оптимальную смешанную стратегию второго игрока:

.

Игры с матрицей 2 Х 2

Пусть дана игра с платёжной матрицей

Если эта матричная игра имеет седловую точку, то она имеет решение в чистых стратегиях, как показано в параграфах 1 и 2.

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

Формула для нахождения оптимальной смешанной стратегии первого игрока:

.

Формула для нахождения оптимальной смешанной стратегии второго игрока:

.

Формула для нахождения цены игры:

.

Пример 7. Дана матричная игра с платёжной матрицей

.

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

Решение. Оптимальные смешанные стратегии первого игрока получаем по соответствующей из приведённых формул:

.

Оптимальные смешанные стратегии второго игрока получаем также по соответствующей формуле:

.

.

Составление матричной игры

Матричная игра, седловая точка, чистые стратегии, смешанные стратегии. А для чего всё это? Рассмотрим на примере, как с помощью матричных игр решаются экономические задачи.

Пример 8. Составить матричную игру для следующей задачи.

.

Далее составляется и решается задача линейного программирования. Это мы уже умеем.

Источник