Онлайн-калькулятор по теории игр
Примеры решенийМетод Брауна Системы массового обслуживанияМатрица рисков Седловая точка Платежная матрица Цена игрыСмешанные стратегии Матричная игра онлайн Чистые стратегии
Раздел «Теория игр» представлен тремя онлайн-калькуляторами:
- Оптимальные стратегии игроков. В таких задачах задана платежная матрица. Требуется найти чистые или смешанные стратегии игроков и, цену игры. Для решения необходимо указать размерность матрицы и метод решения. В сервисе реализованы следующие методы решения игры двух игроков:
- Минимакс. Если необходимо найти чистую стратегию игроков или ответить на вопрос о седловой точке игры, выберите этот метод решения.
- Симплекс-метод. Используется для решения игры в смешанных стратегиях методами линейного программирования.
- Графический метод. Используется для решения игры в смешанных стратегиях. Если есть седловая точка, решение прекращается. Пример: По заданной платежной матрице найти оптимальные смешанные стратегии игроков и цену игры, используя графический метод решения игры.
- Итерационный метод Брауна-Робинсона. Итеративный метод применяется тогда, когда не применим графический метод и когда практически не приминимы алгебраический и матричный методы.
Этот метод дает приближенное значение цены игры, причем истинное значение можно получить с любой нужной степенью точности. Этот метод недостаточен для нахождения оптимальных стратегий, но он позволяет отслеживать динамику пошаговой игры и определить цену игры для каждого из игроков на каждом шаге.
Во всех методах применяется проверка на доминирующие строки и столбцы. - Биматричная игра. Обычно в такой игре задают две матрицы одинакового размера выигрышей первого и второго игроков. Строки этих матриц соответствуют стратегиям первого игрока, а столбцы матриц – стратегиям второго игрока. При этом в первой матрице представлены выигрыши первого игрока, а во второй матрице – выигрыши второго.
- Игры с природой. Используется, когда необходимо выбрать управленческое решение по критериям Максимакса, Байеса, Лапласа, Вальда, Сэвиджа, Гурвица.
Для критерия Байеса необходимо также будет ввести вероятности наступления событий. Если они не заданы, оставьте значения по умолчанию (будут равнозначные события).
Для критерия Гурвица укажите уровень оптимизма λ. Если в условиях данный параметр не задан можно использовать значения0, 0.5 и 1. - Аддитивный критерий оптимальности. Этот сервис используется, если требуется выбрать определенную стратегию среди множества других по заданным критериям с указанием их важности.
Варианты (стратегии) Производительность. шт./час Стоимость оборудования. ден. ед. Энергоемкость. у.е. Надежность. у.е. Завода I 5 7 5 6 Завода II 3 4 7 3 Завода III 4 6 2 4 Вес критерия, λj 0. 40.2 0.1 0.3
Этот метод дает приближенное значение цены игры, причем истинное значение можно получить с любой нужной степенью точности. Этот метод недостаточен для нахождения оптимальных стратегий, но он позволяет отслеживать динамику пошаговой игры и определить цену игры для каждого из игроков на каждом шаге.
4Во многих задачах требуется находить решение средствами ЭВМ. Одним из инструментов служат вышеприведенные сервисы и функции Excel.
Задать свои вопросы или оставить замечания можно внизу страницы в разделе Disqus.
Можно также оставить заявку на помощь в решении своих задач у наших проверенных партнеров (здесь или здесь).
Нижняя и верхняя цена игры
Найдем наилучшую стратегию игрока A, для чего проанализируем последовательно все его стратегии. Выбирая стратегию Ai, мы должны рассчитывать, что игрок B ответит на нее такой стратегией Bj, для которой выигрыш A будет минимальным. Поэтому среди чисел первой строки выбираем минимальное, обозначим его , запишем его в добавочный столбец. Аналогично для каждой стратегии Ai выбираем , т.е. αi – минимальный выигрыш при применении стратегии Ai.
В примере 1:
α1= min {0, –1, –2} = –2;
α 2= min {1, 0, –1} = –1;
α 3= min {0, –1, –2} = 0.
Эти числа запишем в добавочном столбце. Какую же стратегию должен выбрать игрок A? Конечно же, ту стратегию, для которой αi максимально. Обозначим . Это гарантированный выигрыш, который может обеспечить себе игрок A, т.е. ; этот выигрыш называется нижней ценой игры или максимином. Стратегия Ai, обеспечивающая получение нижней цены игры, называется максиминной (перестраховочной). Если игрок A будет придерживаться этой стратегии, то ему гарантирован выигрыш ≥α при любом поведении игрока B.
В примере 1 . Это означает, что если A будет писать «3», то он хотя бы не проиграет. Игрок B заинтересован уменьшить выигрыш A. Выбирая стратегию
Обозначим . Аналогично при выборе стратегии Bj максимально возможный выигрыш A– ; запишем эти числа в добавочной строке.
Чтобы уменьшить выигрыш A, надо из чисел β j выбрать наименьшее . Число называется верхней ценой игры или минимаксом. Это гарантированный проигрыш игрока B (т. е. он проиграет не больше, чем β).
Стратегия игрока B, обеспечивающая выигрыш ≥ — β, называется его минимаксной стратегией.
В примере 1:
β1=max{0,1,2}=2;
β2=max{-1,0,1}=1;
β3=max{-2,-1,0}=0;
β=min{2,1,0}=0;
Это означает, что оптимальная стратегия B – писать «3», тогда он хотя бы не проиграет.
| B↓A→ | B1 | B2 | B3 | αi |
| A1 | 0 | – 1 | –2 | –2 |
| A2 | 1 | 0 | –1 | –1 |
| A3 | 2 | 1 | 0 | 0 |
| βj | 2 | 1 | 0 | 0 |
Этот принцип следует из разумного предположения, что каждый игрок стремится достичь цели, противоположной цели противника.
В примере 1 α=β. Если α=β, т.е. минимакс совпадает с максимином, то такая игра называется игрой с седловой точкой. Седловая точка – это пара оптимальных стратегий ( Ai, Bj). В примере 1 игра имеет седловую точку (А3, B3). В этом случае число α = β называется (чистой) ценой игры (нижняя и верхняя цена игры совпадают). Это означает, что матрица содержит такой элемент, который является минимальным в своей строке и одновременно максимальным в своем столбце. В примере 1 это элемент 0. Цена игры равна 0.
Оптимальные стратегии в любой игре обладают важным свойством, а именно – устойчивостью. Это означает, что каждый из игроков не заинтересован в отходе от своей оптимальной стратегии, т.
к. это ему невыгодно. Отклонение от оптимальной стратегии игрока А приводит к уменьшению его выигрыша, а одностороннее отклонение игрока В – к увеличению проигрыша. Говорят, что седловая точка дает положение равновесия.
Перейти к онлайн решению
Пример 2. Первая сторона (игрок А) выбирает один из трех типов вооружения – А1,
А2, А3, а противник (игрок В) – один из трех видов самолетов: В1, В2, В3.
Цель В – прорыв фронта обороны, цель А – поражение самолета.
Вероятность поражения самолета В1 вооружением А1 равна 0,5, самолета В2 вооружением А1 равна 0,6, самолета В3 вооружением А1 равна 0,8 и т.д., т.е. элемент a
Платежная матрица имеет вид:
| В / А | Вид самолета | |||
| В1 | В2 | В3 | ||
| Тип вооружения | А1 | 0,5 | 0,6 | 0,8 |
| А2 | 0,9 | 0,7 | 0,8 | |
| А3 | 0,7 | 0,5 | 0,6 | |
Решение. В каждой строке находим минимальный элемент и записываем его в добавочном столбце. В каждом столбце находим максимальный элемент и записываем его в добавочной строке.
| В / А | В1 | В2 | В3 | α i |
| А1 | 0,5 | 0,6 | 0,8 | 0,5 |
| А2 | 0,9 | 0,7 | 0,8 | 0,7 |
| А3 | 0,7 | 0,5 | 0,6 | 0,5 |
| β j | 0,9 | 0,7 | 0,8 | 0,7 / 0,7 |
Ответ: α=β=0,7. Оптимальные стратегии – А2 и В2.
Пример 3. Игра в орлянку. Каждый игрок при своем ходе может выбирать одну из двух стратегий: орел или решка. При совпадении выбранных стратегий А получает выигрыш +1, при несовпадении B получает выигрыш 1 (т. е. А получает выигрыш –1). Платежная матрица:
| В / А | В1 (орел) | В2 (решка) |
| А1 (орел) | 1 | -1 |
| А2(решка) | -1 | 1 |
Решение.
| В1 | В2 | αi | |
| А1 | 1 | -1 | -1 |
| А2 | -1 | 1 | 1 |
| βj | 1 | 1 | -1 1 |
α = -1, β = 1, т.
е. А проиграет не больше 1, и B проиграет не больше 1. Так как α ≠ β, игра не имеет седловой точки. Положения равновесия в этой игре не существует, и оптимального решения в чистых стратегиях найти нельзя.
Пример. Найдите нижнюю цену игру, верхнюю цену игры, определите седловые точки, оптимальные чистые стратегии и цену игры (если они существуют).
Найти верхнюю и нижнюю цену игры.
| Игроки | B1 | B2 | B3 | B4 | a = min(Ai) |
| A1 | 7 | 6 | 4 | 5 | 4 |
| A2 | 2 | 1 | 9 | 7 | 1 |
| A3 | 4 | 5 | 3 | 5 | 3 |
| b = max(Bi) | 7 | 6 | 9 | 7 |
Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = 4, которая указывает на максимальную чистую стратегию A1.
Верхняя цена игры b = min(bj) = 6.
Что свидетельствует об отсутствии седловой точки, так как a ≠ b, тогда цена игры находится в пределах 4≤y≤6. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии)
Стратегия A1 доминирует над стратегией A3 (все элементы строки 1 больше или равны значениям 3-ой строки), следовательно исключаем 3-ую строку матрицы. Вероятность p3 = 0.
| 7 | 6 | 4 | 5 |
| 2 | 1 | 9 | 7 |
1. В декартовой системе координат по оси абсцисс откладывается отрезок, длина которого равна 1. Левый конец отрезка (точка х = 0) соответствует стратегии A1, правый — стратегии A2 (x = 1).
Промежуточные точки х соответствуют вероятностям некоторых смешанных стратегий S1 = (p1,p2).2. На левой оси ординат откладываются выигрыши стратегии A1. На линии, параллельной оси ординат, из точки 1 откладываются выигрыши стратегии A2.
Решение игры (2 x n) проводим с позиции игрока A, придерживающегося максиминной стратегии. Доминирующихся и дублирующих стратегий ни у одного из игроков нет.
Максиминной оптимальной стратегии игрока A соответствует точка N, лежащая на пересечении прямых B2B2 и B3B3, для которых можно записать следующую систему уравнений:
y = 6 + (1 — 6)p2
y = 4 + (9 — 4)p2
Откуда
p1 = 4/5
p2 = 1/5
Цена игры, y = 5
Теперь можно найти минимаксную стратегию игрока B, записав соответствующую систему уравнений, исключив стратегию B1,B4, которая дает явно больший проигрыш игроку B, и, следовательно, q1 = 0,q4 = 0.
6q2+4q3 = y
q2+9q3 = y
q2+q3 = 1
или
6q2+4q3 = 5
q2+9q3 = 5
q2+q3 = 1
Решая эту систему методом Гаусса, находим: q2 = 1/2, q3 = 1/2
Графический метод решения игры 2 на n
Содержание
- 1 Графический метод решения игры $2\times n$
- 2 Пошаговая процедура решения игры 2 на n
- 3 2 игры на n графическим методом Пример 1
- 4 Игра 2 на n графическим методом Пример 2
- 5 Сноска
Графический метод решения игры $2\times n$
Игра, в которой один игрок имеет только два варианта действий, а другой игрок имеет более два (скажем, $n$) действия называются игрой $2\times n$.
Графический метод можно использовать для решения игры $2\times n$ или $m\times 2$ или игры, сводящейся либо к $2\times n$, либо к $m\times 2$ после применения свойства доминирования.
В этом уроке мы обсудим графический метод решения игры $2\times n$ или игры, сводящейся к $2\times n$ после применения свойства доминирования.
Пошаговая процедура решения игры 2 на n
Рассмотрим игру $2\times n$. В этой игре у игрока $A$ $2$ стратегий, а у игрока $B$ $n$ стратегий. Предположим, что в игре нет седловой точки.
| Игрок A \ Player B | $ B_1 $ | $ B_2 $ | $ \ CDOT $ | $ B_N $ |
|---|---|---|---|---|
| $ A_1 $ | $a_{12}$ | $\cdots$ | $a_{1n}$ | |
| $A_2$ | $a_{21}$ | $a_{22}$ | $\$a_{2n}$ |
Ниже приведены шаги для решения игры $2\times n$ с использованием графического метода.
Шаг 1
Применить принцип максимина-минимакса, чтобы проверить, существует ли седловая точка. Если седловая точка существует, то остановите метод и рассчитайте стоимость игры, в противном случае перейдите к следующему шагу.
Шаг 2
Постройте две вертикальные оси, ось 1 и ось 2, используя соответствующие масштабы.
Ось 1 представляет значения выигрыша стратегии $A_2$ для игрока $A$, а ось 2 представляет значения выигрыша стратегии $A_1$ для игрока $A$.
(График является просто образцом.)2 by n игра 1
Шаг 3
Соедините точку, представляющую $a_{1j}$ на оси 2, с точкой, представляющей $a_{2j}$ на оси 1, для всех $j = 1, 2,\cdots,n$ . (График является просто образцом.) Игра 2 на n
Шаг 4
Отметьте нижнюю границу (называемую Нижний конверт ) линий жирным отрезком. самая высокая точка на нижнем конверте дает максимум точек $P$ и определяет два критических хода (стратегии) игрока $B$.2 в n игре
Предположим, что нижний конверт создан по стратегии $B_1$ и $B_n$. Самая высокая точка на нижней огибающей дает точку максимина. Это показывает, что двумя критическими ходами для игрока $B$ являются $B_1$ и $B_n$.
Using the above selection the reduced game becomes
| Player A \ Player B | $B_1$ | $B_n$ |
|---|---|---|
| $A_1$ | $a_{11}$ | $ a_{1n}$ |
| $A_2$ | $a_{21}$ | $a_{2n}$ |
Шаг 5
Решите сокращенную игру (т. е. $2\times 2$), используя критерий максимина. (если существует седловая точка, найдите ценность игры, в противном случае используйте технику смешанной стратегии, чтобы найти ценность игры.)
Игра 2 на n графическим методом Пример 1
Решите игру со следующим выигрышем для игрока А.
| Игрок A \ Игрок B | $B_1$ | $B_2$ | $B_3$ | $B_4$ |
|---|---|---|---|---|
| $A_1$ | 1 | 3 | -3 | 5 |
| $A_2$ | 2 | 5 | 4 | — 4 |
Решение
Дана игра $2\times 4$.
То есть у игрока $A$ две стратегии, а у игрока $B$ четыре стратегии. Проверим по максимин-минимаксному принципу, есть ли в игре седловая точка.
| B1 | B2 | B3 | B4 | |
|---|---|---|---|---|
| A1 | 1 | 3 | -3 | 5 |
| A2 | 2 | 5 | 4 | — 4 |
Шаг 1
Примените принцип максимина-минимакса, чтобы проверить, существует ли седловая точка.
| B1 | B2 | B3 | B4 | РядМин | |
|---|---|---|---|---|---|
| A1 | 1 | 3 | -3 | 5 | -3 |
| A2 | 2 | 5 | 4 | -4 | -4 |
| ColMax | 2 | 5 | 4 | 5 |
Таким образом, $Max(min) = Max(-3, -4)=-3$ и $Min(max)=Min(2, 5) , 4, 5)=2$.
Поскольку $Max(min)\neq Min(max)$ для игры, в игре нет седловой точки.
Шаг 2
Постройте две вертикальные оси, ось 1 и ось 2.
Ось 1 представляет значения выигрыша стратегии $A_2$ для игрока $A$, а ось 2 представляет значения выигрыша стратегии $A_1$ для игрока $A $.Ex01-2bynA
Пусть игрок $A$ использует стратегию $A_1$ с вероятностью $p$ и стратегию $A_2$ с вероятностью $1-p$.
Ожидаемый выигрыш игрока $A$ для любой чистой стратегии игрока $B$ будет равен
| Стратегия $B$ | Ожидаемый выигрыш для $A$ |
|---|---|
| $B_1$ | $E_1= p+2(1-p) = -p+2$ |
| $B_2$ | 5(1-p)=-2p+5$ |
| $B_3$ | $E_3= -3p+4(1-p)=-7p+4$ |
| $B_4$ | $E_4 = 5p-4(1-p)= 9p-4$ |
Шаг 3
Соедините точку, представляющую $a_{1j}$ на оси 2, с точкой, представляющей $a_{2j}$ на оси 1 для всех $j = 1, 2,3$.
Шаг 4
Отметьте самую нижнюю границу (называемую Нижний конверт ) линий жирным отрезком. самая высокая точка на нижнем конверте дает максимум точек $P$ и определяет два критических хода (стратегии) игрока $B$.Ex01-2bynC
Два критических хода для игрока $B$ $B_3$ и $B_4$.
Высшая точка $P$ на нижнем конверте дает точку максимина.
Шаг 5
The reduced game (i.e. $2\times 2$) is
| Player A \ Player B | $B_3$ | $B_4$ |
|---|---|---|
| $A_1$ | -3 | 5 |
| $A_2$ | 4 | -4 |
Применить критерий максимина.
| B3 | B4 | |
|---|---|---|
| A1 | -3 | 5 34 | -4 |
- Выбрать минимальный элемент каждой строки платежной матрицы,
$$ \begin{equation*} \text{j_} т.
е., a_{ij}, i=1,2,\cdots, m. \end{equation*} $$
| B3 | B4 | RowMin | |
|---|---|---|---|
| A1 | -3 | 5 | -3 |
| A2 | 4 | -4 | -4 |
- Для каждого столбца платежной матрицы выберите максимальный элемент и назовите его ColMax .
$$ \begin{equation*} \text{т.е. } \max_{i} a_{ij}, j=1,2,\cdots, n. \end{equation*} $$
| B3 | B4 | RowMin | |
|---|---|---|---|
| A1 | -3 | 5 | -3 |
| A2 | 4 | -4 | -4 |
| ColMax | 4 | 5 |
- Из каждого RowMin получить максимальное значение, $xRow, т.е.
$$ \begin{equation*} \text{т.
е. } \max_{i}\min_{j} a_{ij}=\underline{v}. \end{equation*} $$
Таким образом, $Max(min) = Max(-3, -4)=-3$
- Для каждого ColMax найдите минимальное значение, т.е. $Min(ColMax)$.
$$ \begin{equation*} \text{т. е. } \min_{j}\max_{i} a_{ij}=\overline{v}. \end{уравнение*} $$
Таким образом, $Min(max)=Min(4, 5)=4$.
Так как $Max(min)\neq Min(max)$ для игры, в игре нет седловой точки.
Следовательно, оптимальную стратегию для редуцированной игры можно получить алгебраическим методом.
$$ \begin{align} p_1 &= \frac{d-c}{(a+d)-(b+c)}\\ &=\frac{(-4)-4}{(-3- 4)-(5+4))}\\ &=\frac{-8}{-16}\\ &=\frac{1}{2}\\ p_2 &= 1-p_1\\ &=\frac {1}{2} \end{aligned} $$
и оптимальные стратегии для игрока B могут быть определены с помощью
$$ \begin{align} q_1 &= \frac{d-b}{(a+d)-(b+c)}\\ &=\frac{(-4)-5}{(-3-4 )-(5+4)}\\ &=\frac{-9}{-16}\\ &=\frac{9}{16}\\ q_2 &= 1-q_1\\ &=\frac{7 {16}. \end{aligned} $$
Оптимальные стратегии для игрока A можно записать как
$$ \begin{aligned} S_{A} &= \begin{bmatrix} A_1 & A_2 \\ p_1 & p_2 \ end{bmatrix}\\ &=\begin{bmatrix} A_1 & A_2\\ \frac{1}{2} &\frac{1}{2} \end{bmatrix} \end{aligned} $$
и оптимальные стратегии для игрока B могут быть записаны как
$$ \begin{aligned} S_{B} &= \begin{bmatrix} B_1 & B_2 & B_3 & B_4\\ 0 & 0 & q_1 & q_2 \ end{bmatrix}\\ &= \begin{bmatrix} B_1 & B_2 & B_3 & B_4\\ 0 & 0 & \frac{9}{16} & \frac{7}{16} \end{bmatrix} \end {выровнено} $$
И ценность игры для игрока А определяется как
$$ \begin{align} V &=\frac{ad-bc}{(a+d)-(b+ c)} \\ &=\frac{(-3)(-4)-(5)(4)}{(-3-4)-(5+4)} \\ &=\frac{-8} {-16}\\ &=\frac{1}{2}.
\end{выровнено} $$
Таким образом, мы заключаем, что игрок $A$ может выбрать стратегию $A_1$ с вероятностью $\dfrac{1}{2}$ и стратегию $A_2$ с вероятностью $\dfrac{1}{2}$. Игрок $B$ может выбрать стратегию $B_3$ с вероятностью $\dfrac{9}{16}$ и стратегию $B_4$ с вероятностью $\dfrac{7}{16}$. При этом стоимость игры для игрока A равна $\dfrac{1}{2}$, а для игрока B равна $-\dfrac{1}{2}$.
2 на n игру графическим методом Пример 2
Решить игру со следующим выигрышем для игрока А.
| Player A \ Player B | $B_1$ | $B_2$ | $B_3$ |
|---|---|---|---|
| $A_1$ | 1 | 3 | 10 |
| $A_2$ | 8 | 6 | 2 |
Решение
Дана игра $2\times 3$. То есть у игрока $A$ две стратегии, а у игрока $B$ три стратегии. Проверим по максимин-минимаксному принципу, есть ли в игре седловая точка.
| B1 | B2 | B3 | |
|---|---|---|---|
| A1 | 1 | 3 | 10 |
| A2 | 8 | 6 | 2 |
Step 1
Примените принцип максимина-минимакса, чтобы проверить, существует ли седловая точка.
| B1 | B2 | B3 | RowMin | |
|---|---|---|---|---|
| A1 | 1 | 3 | 10 | 1 |
| A2 | 8 | 6 | 2 | 2 |
| ColMax | 8 | 6 | 10 |
Таким образом, $Max(min) = Max(1, 2, )=2$ и $Min(max)=Min(8, 6, 10)=6$. Поскольку $Max(min)\neq Min(max)$ для игры, в игре нет седловой точки.
Шаг 2
Построение двух вертикальных осей, оси 1 и оси 2.
Ось 1 представляет значения выплат стратегий $A_2$ для игрока $A$, а ось 2 представляет значения выплат стратегий $A_1$ игрока $A$.
Ex02-2bynA
Шаг 3
Соедините точку, представляющую $a_ {1j}$ по оси 2 до точки, представляющей $a_{2j}$ по оси 1 для всех $j = 1, 2,\cdots,n$.Ex02-2bynB
Пусть игрок $A$ играет стратегия $A_1$ с вероятностью $p$ и стратегия $A_2$ с вероятностью $1-p$.
Ожидаемый выигрыш игрока $A$ для любой чистой стратегии игрока $B$ будет равен
| Стратегия $B$ | Ожидаемый выигрыш для $A$ | ||
|---|---|---|---|
| $B_1$ | $E_1= 6 900 38(1-p) = -9004 | $B_2$ | $E_2= 3p+6(1-p)=-3p+6$ |
| $B_3$ | $E_3= 10p+2(1-p)=8p+2$ |
Шаг 4
Отметьте нижнюю границу (называемую Нижний конверт ) линий жирным отрезком. самая высокая точка на нижний конверт дает максимин очков $P$ и определяет два критических хода (стратегии) игрока $B$.Ex02-2bynC
Два критических хода для игрока $B$ это $B_2$ и $B_3 $.
Высшая точка $P$ на нижнем конверте дает точку максимина.
Шаг 5
Сокращенная игра (т.е. $2\умножить на 2$) равна
| Игрок A \ Игрок B | $B_2$ | $B_3$ 9003 2 10045 $A_1$ | 3 | 10 |
|---|---|---|---|---|
| $A_2$ | 6 | 2 |
Применить максимальный критерий.
| B2 | B3 | |
|---|---|---|
| A1 | 3 | 10 |
| A2 | 6 | 2 |
- Select the minimum element of each row of the payoff матрица,
$$ \begin{equation*} \text{т.е. } \min_{j} a_{ij}, i=1,2,\cdots, m. \end{уравнение*} $$
| B2 | B3 | RowMin | |
|---|---|---|---|
| A1 | 3 | 10 | 3 |
| A2 | 6 | 2 | 2 |
- Для каждого столбца платежной матрицы выберите максимальный элемент и назовите его ColMax .
$$ \begin{equation*} \text{т.е. } \max_{i} a_{ij}, j=1,2,\cdots, n. \end{уравнение*} $$
| B2 | B3 | RowMin | |
|---|---|---|---|
| A1 | 3 | 10 | 3 |
| A2 | 6 | 2 | 2 |
| ColMax | 6 | 10 |
- Из каждого RowMin получите максимальное значение, т. е. $Max(RowMin)$.
$$ \begin{equation*} \text{т. е. } \max_{i}\min_{j} a_{ij}=\underline{v}. \end{уравнение*} $$
Таким образом, $Max(min) = Max(3, 2)=3$
- Для каждого ColMax получите минимальное значение, т.е. $Min(ColMax)$.
$$ \begin{equation*} \text{т. е. } \min_{j}\max_{i} a_{ij}=\overline{v}. \end{equation*} $$
Таким образом, $Min(max)=Min(6, 10)=6$.
Так как $Max(min)\neq Min(max)$ для игры, в игре нет седловой точки.
Следовательно, оптимальную стратегию для редуцированной игры можно получить алгебраическим методом.
$$ \begin{align} p_1 &= \frac{d-c}{(a+d)-(b+c)}\\ &=\frac{2-6}{(3+2)-(10+ 6)}\\ &=\frac{-4}{-11}\\ &=\frac{4}{11}\\ p_2 &= 1-p_1\\ &=\frac{7}{11} \ end{aligned} $$
и оптимальные стратегии для игрока B могут быть определены как
$$ \begin{aligned} q_1 &= \frac{d-b}{(a+d)-(b+c) }\\\\ &=\frac{2-10}{(3+2)-(10+6)}\\ &=\frac{-8}{-11}\\ &=\frac{8} {11}\\ q_2 &= 1-q_1\\ &=\frac{3}{11}. \end{выровнено} $$
Оптимальные стратегии для игрока А можно записать в виде
$$ \begin{aligned} S_{A} &= \begin{bmatrix} A_1 & A_2 \\ p_1 & p_2 \end{bmatrix}\\ &=\ begin{bmatrix} A_1 & A_2\\ \frac{4}{11} &\frac{7}{11} \end{bmatrix} \end{aligned} $$
и оптимальные стратегии для игрока B могут быть записывается как
$$ \begin{aligned} S_{B} &= \begin{bmatrix} B_1 & B_2 & B_3\\ 0 & q_1 & q_2 \end{bmatrix}\\ &= \begin{bmatrix} B_1 & B_2 & B_3\\ 0 & \frac{8}{11} & \frac{3}{11} \end{bmatrix} \end{aligned} $$
И ценность игры для игрока А определяется как
$$ \begin{aligned} V &= \frac{ad-bc}{(a+d)-(b+c)}\\ &=\frac{(3)(2)-(10)(6)}{(3+2)-(10+6)} \\ &=\frac{-54}{-11}\\ &= 4.
9091. \end{aligned} $$
Таким образом, мы заключаем, что игрок $A$ может выбрать стратегию $A_1$ с вероятностью $\dfrac{5}{12}$ и стратегию $A_5$ с вероятностью $\dfrac{7} {12}$. Игрок $B$ может выбрать стратегию $B_1$ с вероятностью $\dfrac{8}{11}$ и стратегию $B_2$ с вероятностью $\dfrac{3}{11}$. А стоимость игры для игрока А составляет 4,9 доллара.091$, а для игрока B -4,9091$.
Endnote
В этом уроке вы узнали о графическом методе решения игры $2\times n$ и о том, как использовать графический метод для решения игры $2\times n$ с иллюстрированными примерами.
Чтобы узнать больше о различных методах решения игры, обратитесь к следующим руководствам:
- Теория игр
Дайте мне знать в комментариях, если у вас есть вопросы по Графический метод решения игры $2\times n$ и ваше мнение об этой статье.
Теория игр (игра в нормальной форме) | Набор 6 (Графический метод [2 X N] Game)
Улучшить статью
Сохранить статью
Платежная матрица игры 2 * N состоит из 2 строк и N столбцов .
В этой статье пойдет речь о том, как решить игру 2*N графическим методом.
Рассмотрим приведенную ниже игру 2 * 5:
Решение: Сначала проверьте седловую точку игры. В этой игре нет седловой точки.
Шаг 1: Уменьшите размер платежной матрицы, применив свойство доминирования, если оно существует. Этот шаг не является обязательным. Размер уменьшен, чтобы просто упростить задачу. Игра может быть решена без уменьшения размера.
Сократив описанную выше игру с помощью свойства доминирования, мы получим следующую игру.
Шаг 2: Пусть x будет вероятностью выбора альтернативы 1 игроком А, а (1 – x) будет вероятностью выбора альтернативы 2 игроком А.
Выведите функцию ожидаемого выигрыша игрока А по отношению к каждой альтернативе игрока Б. Для этого просто умножьте значения столбца альтернативы Б на соответствующую вероятность выбора альтернатив игроком А. Например, первая альтернатива игрока Б — это столбец номер 1.
, так что умножьте -4 с x и 3 с (1 – x) и сложите их, тогда полученное выражение является функцией ожидаемого выигрыша A. Точно так же вторая альтернатива игрока B — это столбец номер 2, поэтому умножьте 2 на x и -9 на (1 — x) и сложите их. Точно так же третья альтернатива игрока B — это столбец номер 4, поэтому умножьте -6 на x и 4 на (1 — x) и сложите их. Пожалуйста, обратитесь к показанной таблице.
Шаг 3: Найдите значение усиления, когда x = 0 и x = 1 . См. таблицу ниже:
Шаг 4: Теперь постройте график функции усиления в подходящем масштабе. [Оставить x на оси X, а усиление на оси Y]
Если B выбирает первую альтернативу, т. е. первую стратегию, когда x = 0 ожидаемый выигрыш A равен 3 и когда x = 1 A ожидаемый выигрыш -4 .
Если B выбирает вторую альтернативу, т.
е. вторую стратегию, когда x = 0 ожидаемый выигрыш A равен -9 и когда x = 1 ожидаемый выигрыш A равен 2 .
Если B выбирает третью альтернативу, т. е. четвертую стратегию, при x = 0 ожидаемый выигрыш A равен 4 , а при x = 1 ожидаемый выигрыш A равен -6 .
Используя приведенную выше информацию, постройте график.
Шаг 5: Найти самую высокую точку пересечения на нижней границе графика –> Максимальная точка , так как A является игроком Максимина .
Нижняя граница ABC. А самой высокой точкой среди A, B и C является B. Эта точка пересечения B называется точкой Максимина .
Шаг 6: Если количество линий, проходящих через точку максимина, равно только двум, сформируйте платежную матрицу 2 * 2, а затем решите игру, как описано в этой статье.
Если нет, определите любые две линии с противоположными наклонами, проходящие через эту точку.