Теория игр-конспект
Теория игр и исследование операций (ИО) — это две тесно связанные дисциплины, которые часто используются вместе для анализа сложных систем и принятия оптимальных решений.
· Исследование операций (ИО) — это наука о том, как принимать наилучшие решения в условиях ограниченных ресурсов. Она фокусируется на оптимизации деятельности одного лица или организации, которая противостоит пассивной среде (например, природе, технологическим процессам, случайным событиям).
· Ключевой вопрос: "Что мне сделать, чтобы достичь своей цели максимально эффективно?"
· Инструменты: линейное программирование, симуляция, теория очередей, управление запасами.
· Теория игр (ТИ) — это наука о стратегическом взаимодействии рациональных игроков. Она фокусируется на ситуациях, где результат вашего решения зависит от решений других разумных игроков, у которых есть свои, возможно, противоположные цели.
· Ключевой вопрос: "Что я должен сделать, учитывая, что другие тоже думают и принимают решения, которые повлияют на меня?"
· Инструменты: равновесие Нэша, дилемма заключенного, аукционы, кооперативные и некооперативные игры.
Пример 1: Управление запасами (чистое ИО)
Задача: Сеть супермаркетов хочет оптимизировать уровень запасов молока.
· Анализ в рамках ИО: Компания анализирует свои данные: спрос покупателей (который является случайной величиной), затраты на хранение, стоимость заказа, штрафы за дефицит. Строится модель управления запасами (например, модель Уилсона), которая вычисляет оптимальный размер заказа и точку заказа. "Противник" здесь — стохастический спрос и издержки.
· Где появляется Теория игр? Представьте, что рядом открывается супермаркет конкурента. Теперь ваше решение о цене на молоко и уровне запасов зависит от цен и акций конкурента. Если вы снизите цену, он может ответить тем же. Это уже игра на олигопольном рынке (например, модель Бертрана или Курно), которая анализируется методами ТИ.
Пример 2: Планирование перевозок (ИО с элементами ТИ)
Задача: Логистическая компания хочет найти самый короткий/дешевый маршрут для доставки товаров из пункта А в пункт Б.
· Анализ в рамках ИО: Используются методы сетевого анализа (алгоритм Дейкстры). Задача сводится к нахождению кратчайшего пути в графе. "Пробки" рассматриваются как случайное событие или фиксированная задержка.
· Где появляется Теория игр? Рассмотрите навигатор (например, Waze или Яндекс.Навигатор). Он рекомендует маршруты миллионам водителей одновременно. Если все послушают навигатор и поедут по самому короткому пути, он превратится в пробку и станет самым долгим. Это классическая "задача о назначении цены" (price of anarchy) в теории игр. Навигатор должен не просто найти оптимальный путь для одного водителя, а учитывать, как решения всех водителей collectively влияют на транспортный поток, стремясь к равновесию по Нэшу для всей системы.
Пример 3: Дилемма заключенного (классическая ТИ, которую можно увидеть в бизнесе)
Задача: Два менеджера из конкурирующих отделов должны решить, сотрудничать им в рамках общего проекта или преследовать личные интересы.
· Сценарий:
· Если оба сотрудничают, оба получают хороший бонус (+5, +5).
· Если один сотрудничает, а другой "сачкует", сачкующий получает максимум выгоды за счет другого (+8, 0).
· Если оба сачкуют, проект проваливается, и оба получают выговор (0, 0).
· Анализ в рамках ТИ: Индивидуальная рациональность подталкивает каждого к тому, чтобы "сачковать" (это доминирующая стратегия), что приводит к худшему общему исходу (0, 0) — равновесие Нэша. Это не оптимально по Парето (исход (+5,+5) лучше для всех).
· Связь с ИО: Если бы это был один менеджер, принимающий решение против природы (например, "инвестировать или нет"), ИО нашло бы оптимальное решение. Но как только появляется второй разумный агент, чистая оптимизация не работает, и требуется анализ стратегического взаимодействия.
Пример 4: Аукционы и торги (синтез ИО и ТИ)
Задача: Компания участвует в тендере на государственный контракт.
· Элемент ИО: Компания рассчитывает свою стоимость выполнения проекта (себестоимость). Это внутренняя оптимизационная задача.
· Элемент ТИ: Чтобы определить ставку, компания должна предсказать, какие ставки сделают конкуренты. Слишком высокая ставка — проиграете тендер. Слишком низкая — выиграете, но получите убыток. Это чистейшая теория игр (аукционы с независимыми частными оценками). Оптимальная ставка является результатом стратегических размышлений, а не просто внутренней оптимизации.
Выводы:
1. Исследование операций — это фундамент для принятия решений в контролируемой или стохастической среде.
2. Теория игр вступает в игру, когда среда становится "разумной" и состоит из других лиц, принимающих решения.
3. На практике эти дисциплины часто используются вместе: сначала с помощью ИО вы определяете свои возможные стратегии и их "стоимость", а затем с помощью ТИ анализируете, какую из этих стратегий выбрать в условиях стратегического взаимодействия с другими игроками.
Таким образом, теория игр не заменяет исследование операций, а дополняет его, предоставляя мощный аппарат для анализа более сложных и реалистичных ситуаций, где присутствует конфликт, кооперация или их смесь.
Практический пример с решением:
Сценарий: «Планерная фабрика двух братьев»
Два брата, Алексей и Борис, унаследовали завод. Они решили разделить производство:
· Алексей производит самолеты.
· Борис производит крылья для этих самолетов.
Завод один, но цеха независимы. Для простоты будем считать, что один самолет требует один комплект крыльев.
Этап 1: Задача Исследования Операций
Проблема Алексея (Производитель самолетов):
· Переменная: x - количество производимых самолетов в месяц.
· Выручка с одного самолета: 80 000 руб.
· Его постоянные издержки (аренда, свет): 400 000 руб./мес.
· Его переменные издержки (труд, материалы, кроме крыльев): 20 000 руб./планер.
Сначала Алексей думает как "исследователь операций". Он должен найти x, который максимизирует его прибыль.
Формула прибыли Алексея:
P_A(x) = Выручка - (Постоянные издержки + Переменные издержки)
P_A(x) = 80000*x - (400000 + 20000*x)
P_A(x) = 60000*x - 400000
Решение:
Это линейная функция.Прибыль растет с ростом x. Значит, чем больше он производит, тем больше прибыль. Он смотрит на мощность цеха и видит, что может производить до 30 самолетов в месяц. Его оптимальная стратегия: x = 30.
· P_A(30) = 60000*30 - 400000 = 1 800 000 - 400 000 = 1 400 000 руб.
Вывод ИО: Алексей должен производить 30 самолетов.
Этап 2: Появление Взаимозависимости — Вход в Теорию Игр
Проблема Бориса (Производитель крыльев):
· Переменная: p - цена за один комплект крыльев, который он назначает Алексею.
· Себестоимость производства одного комплекта крыльев: 10 000 руб.
· Спрос на крылья жестко равен количеству самолетов x, которые решит произвести Алексей.
Алексей теперь не может просто считать переменные издержки постоянными. Его затраты на крылья зависят от цены p, которую назначит брат.
Обновленная формула прибыли Алексея:
P_A(x, p) = 80000*x - [400000 + (20000 + p)*x]
P_A(x, p) = 80000x - 400000 - 20000x - p*x
P_A(x, p) = (60000 - p)*x - 400000
Теперь прибыль Алексея зависит не только от его решения x, но и от решения Бориса p.
Прибыль Бориса:
P_B(p, x) = (p - 10000) * x
Прибыль Бориса зависит от его цены p и от решения Алексея о количестве x.
Мы получили игру. У каждого игрока есть своя стратегия:
· Алексей: Выбрать x (от 0 до 30).
· Борис: Выбрать p (≥ 10 000, иначе себе в убыток).
Этап 3: Анализ Равновесия по Нэшу
Мы ищем такую пару (x*, p*), где ни одному из братьев не выгодно в одиночку отклоняться от своей стратегии.
Шаг 1: Лучший ответ Алексея на цену Бориса.
Алексей, как рациональный игрок, видит цену p и выбирает x, чтобы максимизировать P_A(x, p) = (60000 - p)*x - 400000.
· Если (60000 - p) > 0, то функция растет с x. Значит, его лучший ответ BR_A(p) = 30 (максимальная мощность).
· Если (60000 - p) < 0, то производство убыточно. Его лучший ответ BR_A(p) = 0 (ничего не производить).
· Если (60000 - p) = 0, ему безразлично любой x.
Вывод: Лучший ответ Алексея:
BR_A(p) = { 30, если p < 60000; 0, если p > 60000 }
Шаг 2: Лучший ответ Бориса на объем производства Алексея.
Борис, зная, что Алексей купит ровно x комплектов, максимизирует P_B(p, x) = (p - 10000) * x.
· Это также линейная функция от p. Чем выше цена, тем выше прибыль с единицы.
· Но есть ограничение! Если Борис назначит слишком высокую цену, Алексей может отказаться от производства (x=0), и прибыль Бориса будет нулевой.
Из шага 1 мы знаем, что Алексей будет производить x=30 только если p < 60000. Если p превысит 60000, x станет равным 0.
Следовательно, лучшая стратегия Бориса — назначить максимально возможную цену, при которой Алексей еще согласен производить 30 самолетов. Эта цена p = 60000 (вернее, чуть-чуть меньше, например, 59999 руб., чтобы Алексею все же было выгодно).
Посчитаем прибыль Бориса при x=30:
· Если p = 60000, то P_B = (60000 - 10000)*30 = 1 500 000 руб.
· Если p = 50000, то P_B = (50000 - 10000)*30 = 1 200 000 руб. (меньше!)
· Если p = 61000, то Алексей уходит, x=0, P_B = 0.
Вывод: Лучший ответ Бориса BR_B(x) — назначать p = 60000, при условии, что Алексей производит 30 самолетов.
Шаг 3: Нахождение равновесия.
Сводим лучшие ответы вместе:
· Борис назначает p* = 60000.
· Алексей, видя p=60000, оказывается в точке безразличия (60000 - p) = 0. Его прибыль в любом случае P_A = -400000 (убыток в размере постоянных издержек!). Рациональнее всего ему все же производить x*=30, чтобы хоть как-то покрыть часть постоянных издержек (выручка 2.4 млн покрывает переменные издержки 1.2 млн и часть постоянных), либо вести переговоры. В рамках некооперативной игры, где братья не договариваются, равновесием Нэша будет:
· p* = 60000
· x* = 30
Итоговые прибыли в равновесии:
· P_A = (60000 - 60000)*30 - 400000 = **-400 000 руб.** (Алексей в убытке!)
· P_B = (60000 - 10000)*30 = **1 500 000 руб.** (Борис получает всю прибыль системы)