Теория игр и принятие решений
Теория игр и принятие решений: стратегическое взаимодействие, равновесия, смешанные стратегии и решения при неполной информации.
1. Карта курса
- Игры в нормальной и расширенной форме.
- Равновесие Нэша и доминирование стратегий.
- Смешанные стратегии и минимакс.
- Решения в условиях неопределенности и риска.
Рекомендуемый режим освоения: теория \(\rightarrow\) 2-3 задачи вручную
\(\rightarrow\) вычислительная проверка \(\rightarrow\) короткий конспект ошибок.
1.1. Лекционный маршрут и выходные компетенции
- Недели 1-3: геометрия задачи, выпуклость и структура ограничений.
- Недели 4-6: условия оптимальности и двойственные постановки.
- Недели 7-10: численные методы, шаговые стратегии и критерии остановки.
- Недели 11-14: чувствительность решения и прикладная интерпретация параметров.
2. Теоретический каркас
Оптимизационный блок связывает модель цели и ограничения с алгоритмом поиска решения. Важнейшая часть — проверка условий оптимальности и устойчивость найденного решения к изменению данных.
Стандарт постановки: определить переменные, функционал цели,
ограничения, класс допустимых решений и критерий качества.
Методологический минимум: KKT/двойственность/динамическое
программирование выбираются по структуре задачи, а не «по шаблону».
2.1. Строгий минимум раздела
- Перед решением проверять геометрию задачи: выпуклость, гладкость, тип ограничений.
- Разделять необходимые и достаточные условия оптимальности.
- Для constrained-задач обосновывать регулярность перед применением KKT.
- Проводить анализ чувствительности оптимума к изменению параметров и ограничений.
Требование уровня "отлично": уметь не только выполнить вычисление,
но и письменно обосновать корректность каждого шага с явным указанием условий применимости.
3. Ключевые формулы и зависимости
| Концепт | Формула / интерпретация |
|---|---|
| Общая задача | \(\min\limits_x f(x)\) при \(g_i(x)\le0\), \(h_j(x)=0\) |
| KKT-условия | \(\nabla_x L(x,\lambda,\nu)=0\), \(\lambda_i\ge0\), \(\lambda_i g_i(x)=0\) |
| Двойственность | \(d^*\le p^*\) |
| Градиентный шаг | \(x_{k+1}=x_k-\alpha_k\nabla f(x_k)\) |
| Нэш | \(u_i(s_i^*,s_{-i}^*)\ge u_i(s_i,s_{-i}^*)\) |
| Смешанная стратегия | \(p\in\Delta(S)\) |
| Ожидаемая полезность | \(\mathbb E[U]=\sum p_i u_i\) |
4. Методика решения типовых задач
- Проверять выпуклость до выбора численного алгоритма.
- Разделять необходимые и достаточные условия оптимальности.
- Использовать двойственную задачу для интерпретации чувствительности.
- Проводить анализ ограничений на активность/неактивность.
- Сравнивать локальные и глобальные методы поиска.
- Документировать устойчивость решения к вариациям параметров.
4.1. Формат эталонного решения
- Формально выписать цель, ограничения и множество допустимых решений.
- Проверить условия применимости KKT/двойственности.
- Найти кандидаты и подтвердить характер точки вторыми условиями.
- Сделать sensitivity analysis по ключевым коэффициентам модели.
- Объяснить практический смысл итогового решения и активных ограничений.
Оформление полного решения: постановка \rightarrow выбор метода \rightarrow
вычисления \rightarrow контроль ошибки \rightarrow интерпретация результата.
5. Разбор прикладного кейса
Кейс: ценовая конкуренция двух игроков
Формируется матрица выигрышей, удаляются доминируемые стратегии, затем находится смешанное равновесие. Проводится анализ чувствительности к изменению структуры издержек.
Проверка результата: после вычислений обязательно фиксировать
1) численную стабильность, 2) чувствительность к параметрам,
3) интерпретацию в терминах исходной предметной задачи.
5.1. Углубление кейса
Продвинутый кейс обязан включать экономическую/физическую интерпретацию множителей Лагранжа и анализ активных ограничений. Именно это показывает, что найденный минимум полезен как инструмент принятия решений, а не только как число.
- Проверить вторые условия и отделить седловые точки от минимума.
- Сравнить локальные и глобальные методы при неоднозначном рельефе функции.
- Показать, какие параметры сильнее всего влияют на положение оптимума.
6. Типичные ошибки
- Применение KKT без проверки условий регулярности.
- Смешение локального и глобального минимума.
- Неверная интерпретация множителей Лагранжа.
- Игнорирование масштабирования переменных.
- Отсутствие sensitivity analysis.
6.1. Диагностика ошибок
- Не смешивать локальный минимум с глобальным без дополнительного анализа.
- Не применять KKT при нарушенной регулярности ограничений.
- Проверять масштабирование переменных, чтобы избежать численной деградации.
- Контролировать интерпретацию множителей Лагранжа в прикладном контексте.
7. Практикум (3 уровня)
Уровень A: базовая техника
- Решить 12-15 стандартных задач с полной записью решения.
- Для каждой задачи указать примененный метод и почему он корректен.
- Проверить 3 задачи альтернативным методом.
Уровень B: продвинутая отработка
- Решить 8 задач с параметрами и анализом вырожденных случаев.
- Оценить погрешность/устойчивость результата на вариациях входа.
- Подготовить короткий отчёт с выводами (1-2 страницы).
Уровень C: мини-проект
- Реализовать вычислительный прототип по теме курса.
- Сравнить минимум 2 метода и обосновать выбор лучшего.
- Подготовить репродуцируемый notebook с графиками и выводами.
8. Экзаменационный минимум и литература
Минимум к экзамену
- Все базовые определения курса в строгой формулировке.
- Ключевые теоремы/критерии и условия их применимости.
- Алгоритм решения типовой задачи каждого раздела.
- Умение объяснить источник ошибки и устойчивость метода.
- Интерпретация результата в прикладном контексте.
Рекомендуемая литература
- Osborne, Rubinstein. Game Theory; Myerson R. Game Theory
- Материалы семинаров и практикумов кафедры.
- Набор задач повышенной сложности (подготовка к экзамену).
Тренажер билетов
- Запишите полную постановку задачи и объясните выбор метода решения.
- Выведите KKT-условия и прокомментируйте экономический смысл множителей.
- Разберите пример с несколькими локальными экстремумами и стратегией поиска глобального.
- Покажите sensitivity analysis: как изменится оптимум при варьировании ограничений.
План повторения перед экзаменом
Эффективная подготовка строится циклом "теория \rightarrow задачи \rightarrow разбор ошибок". Для каждого раздела фиксируйте: формулировку ключевых определений, один эталонный алгоритм решения и типовую ловушку, которая чаще всего приводит к неверному ответу.
- Сделать короткий one-page summary по каждому разделу с формулами и условиями применимости.
- Решить минимум 2 задачи базового и 1 задачу повышенного уровня по каждому крупному блоку.
- Провести устный прогон билета: формулировка теоремы, схема доказательства, прикладная интерпретация.