Задачи по теории игр с решениями: Примеры решений по теории игр

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

• Платёжная матрица, чистые стратегии, цена игры
• Седловая точка в матричных играх
• Матричные игры с оптимальной смешанной стратегией
• Сведение матричной игры к задаче линейного программирования
• Игры с матрицей 2 Х 2
• Составление матричной игры

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

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

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

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

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

Рассмотрим игру, в которой имеются два участника: первый игрок и второй игрок. Пусть в распоряжении первого игрока имеется m чистых стратегий, а в распоряжении второго игрока – n чистых стратегий. Поскольку рассматривается игра, естественно, что в этой игре есть выигрыши и есть проигрыши.

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

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

.

Если первый игрок выбирает i-ю чистую стратегию, а второй игрок – j-ю чистую стратегию, то выигрыш первого игрока составит aij единиц, а проигрыш второго игрока – также aij единиц.

Так как

aij + (- aij) = 0, то описанная игра является матричной игрой с нулевой суммой.

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

.

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

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

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

.

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

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

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

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

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

Таким образом, проигрыш второго игрока будет минимальным из максимальных. Отсюда и название – минимаксный выигрыш. Номер столбца этого элемента и будет номером чистой стратегии, которую выбирает второй игрок. Если второй игрок использует “минимакс”, то независимо от выбора стратегии первым игроком, он проиграет не более v2 единиц.

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

.

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

Решение. Справа от платёжной матрицы выпишем наименьшие элементы в её строках и отметим максимальный из них, а снизу от матрицы – наибольшие элементы в столбцах и выберем минимальный из них:

Наибольший из наименьших элементов строк – 2, это нижняя цена игры, ей соответствует первая строка, следовательно, максиминная стратегия первого игрока первая. Наименьший из наибольших элементов столбцов – 5, это верхняя цена игры, ей соответствует второй столбец, следовательно, минимаксная стратегия второго игрока – вторая.

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

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

.

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

.

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

.

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

.

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

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

.

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

Решение. Справа от платёжной матрицы выпишем наименьшие элементы в её строках и отметим максимальный из них, а снизу от матрицы – наибольшие элементы в столбцах и выберем минимальный из них:

Наибольший из наименьших элементов строк – 3, это нижняя цена игры, ей соответствует вторая строка, следовательно, максиминная стратегия первого игрока вторая. Наименьший из наибольших элементов столбцов – 5, это верхняя цена игры, ей соответствует первый столбец, следовательно, минимаксная стратегия второго игрока – первая.

Если верхняя и нижняя цена игры одинаковая, то считается, что матричная игра имеет седловую точку.

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

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

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

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

.

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

Решение. Справа от платёжной матрицы выпишем наименьшие элементы в её строках и отметим максимальный из них, а снизу от матрицы – наибольшие элементы в столбцах и выберем минимальный из них:

Нижняя цена игры совпадает с верхней ценой игры. Таким образом, цена игры равна 5. То есть . Цена игры равна значению седловой точки . Максиминная стратегия первого игрока – вторая чистая стратегия, а минимаксная стратегия второго игрока – третья чистая стратегия. Данная матричная игра имеет решение в чистых стратегиях.

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

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

.

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

Правильное решение и ответ.

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

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

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

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

.

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

.

Нет времени вникать в решение? Можно заказать работу!

Если первый игрок использует смешанную стратегию p, а второй игрок – смешанную стратегию q, то имеет смысл математическое ожидание выигрыша первого игрока (проигрыша второго игрока). Чтобы его найти, нужно перемножить вектор смешанной стратении первого игрока (который будет матрицей из одной строки), платёжную матрицу и вектор смешанной стратегии второго игрока (который будет матрицей из одного столбца):

.

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

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

.

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

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

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

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

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

,

.

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

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

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

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

.

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

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

.

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

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

,

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

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

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

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

,

.

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

,

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

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

,

,

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

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

.

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

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

Приводим задачу к канонической форме и решаем задачу и двойственную ей задачу симплекс-методом.

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

.

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

.

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

.

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

.

Находим цену игры:

.

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

.

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

.

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

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

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

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

.

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

.

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

.

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

.

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

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

.

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

.

Цена игры:

.

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

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

Предприятие может выпускать три вида продукции (A1, A2, A3), получая при этом прибыль, зависящую от спроса, который может быть в одном из четырёх состояний (B1, B2, B3, B4). Дана матрица, элементы которой aij характеризуют прибыль, которую получит предприятие при выпуске i-й продукции с j-м состоянием спроса.

	B1	B2	B3	B1
A1	3	3	6	8
A2	9	10	4	2
A3	7	7	5	4

Решение. Задача сводится к матричной игре предприятия A против спроса B.

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

.

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

Нет времени вникать в решение? Можно заказать работу!

К началу страницы

Поделиться с друзьями

Теория игр: основы. Примеры записи и решения игр из жизни

Материалы по векторам и матрицам

Векторы: определения и действия над векторами

Произведение двух матриц

Линейное программирование

Задача и теоремы линейного программирования, примеры формулировки задач

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

Кафедры

Кафедры

1. Водоснабжение, водоотведение и гидротехника

2. Геотехника и дорожное строительство

3. Городское строительство и архитектура

4. Градостроительство

5. Дизайн и художественное проектирование интерьера

6. Землеустройство и геодезия

7. Инженерная экология

8. Иностранные языки

9. Информационно-вычислительные системы

10. История и философия

11. Кадастр недвижимости и право

12. Маркетинг и экономическая теория

13. Математика и математическое моделирование

14. Менеджмент

15. Механизация и автоматизация производства

16. Механика

17. Начертательная геометрия и графика

18. Организация и безопасность движения

19. Основы архитектурного проектирования

20. Рисунок, живопись и скульптура

21. Строительные конструкции

22. Теплогазоснабжение и вентиляция

23. Технология строительных материалов и деревообработки

24. Управление качеством и технологии строительного производства

25. Физика и химия

26. Физическое воспитание

27. Экономика, организация и управление производством

28. Экспертиза и управление недвижимостью

29. Эксплуатация автомобильного транспорта

Новости

• Главные новости
• Научные мероприятия
• Жизнь университета

Дата: 02-07-2023 Просмотры: 43

Дата: 02-06-2023 Просмотры: 45

Дата: 02-03-2023 Просмотры: 116

Дата: 01-13-2023 Просмотры: 115

Дата: 12-19-2022 Просмотры: 158

Дата: 12-19-2022 Просмотры: 205

Дата: 02-03-2023 Просмотры: 38

Дата: 01-27-2023 Просмотры: 98

Дата: 01-24-2023 Просмотры: 156

Бакалавриат/Специалитет

Магистратура

Аспирантура

Наука

• Научные направления
• Научные издания
• Диссертационные советы

Ресурсы

Теория игр: концепции решений и стратегическое превосходство (часть 4) | Ковшик Чиламкурти | Nerd For Tech

Вера и лучший ответ, общая рациональность

Создано автором

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

«строго доминантная стратегия — это стратегия, которая всегда является лучшим, что вы можете сделать, независимо от того, что выберут ваши оппоненты»

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

Дилемма заключенных

Если игрок предпочитает хранить молчание, возможные результаты -1 и -3 зависят от того, решит ли противник игрока хранить молчание или предать соответственно. если игрок решит предать, то возможные результаты равны 0 и -2, в зависимости от того, решит ли противник игрока хранить молчание и предать соответственно.

Здесь мы легко можем сделать вывод, что молчание { RS (молчать)} хуже, чем предательство { BE (предательство другого заключенного)} для каждого игрока, независимо от того, что делает его противник. Мы говорим, что такая стратегия предательства {BE} доминирует.

Определение: Пусть sᵢ∈ Sᵢ и s”ᵢ∈ Sᵢ возможные стратегии игрока i. Мы говорим, что в s”ᵢ строго доминирует sᵢ, если для любой возможной комбинации стратегий других игроков, s₋ᵢ∈ S₋ᵢ, выигрыш игрока i от s”ᵢ строго меньше, чем от sᵢ. То есть
vᵢ(sᵢ, s₋ᵢ) > vi(s”ᵢ, s₋ᵢ) для всех s₋ᵢ∈ S₋ᵢ .
Мы будем писать sᵢ >ᵢ s”ᵢ, чтобы обозначить, что s”ᵢ находится под строгим доминированием s₋ᵢ

Мы можем предложить новую концепцию решения, используя приведенное выше определение Концепция строгого доминирования: «строго доминирующая стратегия – это стратегия, которая всегда лучшее, что вы можете сделать, независимо от того, что выберут ваши оппоненты»

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

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

Легко заметить, что не существует строго доминирующей стратегии. для обоих игроков.
Обратите внимание, что если игрок 2 играет « M» , то игрок 1 также должен играть « M» , а если игрок 2 играет « H », то игрок 1 должен играть « H ». Совершенно очевидно, что здесь нет строгого доминирования.
При отсутствии стратегии строгого доминирования мы должны заключить, что концепция решения строгого доминирования может применяться не ко всем видам игр.

Это важное допущение, утверждающее, что структура игры и рациональность игроков общеизвестны среди игроков.

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

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

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

Если игрок 1 выбирает U, стратегия с наибольшим выигрышем для игрока 2 — L. Если игрок 1 выбирает M, стратегия с наибольшим выигрышем для игрока 2 — R. Анализируя таким образом, можно сделать вывод, что у обоих игроков нет строго доминирующей стратегии. Если внимательно присмотреться, для игрока 2 существует одна строго доминируемая стратегия.0005

В стратегии C строго доминирует R.

В этом новом матричном представлении и M, и D строго доминируются U для игрока 1.

Это привело к следующему уровню исключения, где действия M,D исключены.

Отсюда довольно просто: Игрок 1 выбирает U, а Игрок 2 выбирает
L, так как v(L) = 3 > v(R)=2.

Если для игрока i существует строгая доминирующая стратегия, то независимо от его системы убеждений игрок i всегда выбирает строгую доминирующую стратегию.

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

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

Определение : Стратегия sᵢ ∈ Sᵢ является лучшим ответом игрока i на стратегии его противников s₋ᵢ ∈ S₋ᵢ, если
vᵢ(sᵢ, s₋ᵢ) ≥ vᵢ(s”ᵢ, s₋ᵢ). ∀s”ᵢ∈ Sᵢ

Предположим, что sᵢ – лучший ответ игрока i на его оппонентов, играющих s’₋ᵢ. Игрок i будет играть sᵢ только тогда, когда он считает, что его противники будут играть s’₋ᵢ. Концепция веры занимает центральное место в анализе стратегического поведения. Строго доминирующая стратегия игрока — это его лучший ответ, независимый от игры его противников.

Пример

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

Спасибо за ваше время.

Теория игр | Определение, факты и примеры

платежная матрица с седловой точкой

Смотреть все СМИ

Ключевые люди:

Джон фон Нейман Уильям Райкер Томас С. Шеллинг Джон Нэш Ллойд Шепли

Похожие темы:

поощрительная совместимость игра с положительной суммой Дилемма заключенного кооперативная игра теория полезности

Просмотреть весь связанный контент →

Резюме

Прочтите краткий обзор этой темы

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

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

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

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

Классификация игр

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

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

Оформите подписку Britannica Premium и получите доступ к эксклюзивному контенту. Подписаться сейчас

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

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

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

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

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

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

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