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

Теория игр изучает решения нескольких участников, когда результат каждого зависит не только от его действия, но и от действий остальных.

Определения

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

Равновесие не обязано быть общественно лучшим, единственным или справедливым.

Игры двух лиц с нулевой суммой

Выигрыш одного равен проигрышу другого. Для матрицы $A$ игрок строк максимизирует, игрок столбцов минимизирует.

Если:

${\max }_i{\min }_j{A}_{ij}={\min }_j{\max }_i{A}_{ij},$

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

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

Равновесие Нэша

Теорема Нэша: всякая конечная игра имеет хотя бы одно равновесие в смешанных стратегиях.

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

Как решать небольшую задачу

1. Назвать игроков, действия и информацию каждого.
2. Построить таблицу выигрышей.
3. Удалить строго доминируемые стратегии.
4. Найти лучшие реакции.
5. Проверить пересечения лучших реакций.
6. Если чистого равновесия нет, искать смешанное.

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

Инженерная интерпретация

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

Самопроверка

• Почему равновесие Нэша не обязательно оптимально для группы?
• Чем стратегия отличается от отдельного хода?
• Когда нужна смешанная стратегия?