Теория игр
.docxУ нас всего 4 раза. Дегтярев Андрей Харитонович.
Введение в дисциплину. 1. Задачи и структура курса. 2. История развития. 3. Ограничения.
Из множества альтернатив выбрать наилучшую - оптимизация. В отличие от других подходов, учитывается поведение других лиц. Очень развито на Западе и слабо развито в СССР. Нужно знать терминологию и моделировать реальные ситуации из мо. Научиться делать количественный анализ событий путем использования аппарата теории игр. Научиться прогнозировать развитие ситуации и выбирать стратегию. Правильно оформлять результаты. Естественно, мы за 16 часов не научимся - но это будет неплохая база, если в дальнейшем захотим изучать. Вообще, этим занимаются математики на мехмате. Но это техническая версия, у нас же - гуманитарная версия. Для тупых, ога. ;-) Будет 3 раздела. 1 - основные понятия. 2 - теоретико-игровой анализ МО. 3 - теория игр и политология. Теория игр это математическая теория анализа стратегического поведения при взаимодействии сторон. Сестры - теория принятия решений и теория вероятности, линейная алгебра, теория множеств и исследования операций. История развития теории игр. Играли люди с древности. Были и игровые модели. Такие игры называются салонными играми, их не используют для мо. Не все игры подходят к МО. В основе современной теории игр - 1928 год, статья "Теория стратегических игр" Джона фон Неймана в математическом журнале. Синтез алгебры и всего такого. В 44 тот же Нейман развил эту теорию до монографии "Теория игр и экономическое поведение", вместе с Оскаром Моргнштерном. В ней содержался новый инструментарий для матана экономических процессов. Игры с нулевой суммой и коалиционные игры - оттуда. С этой книжки Неймана стали негласно звать великим математиком. Нейман - разработчик компьютерных программ - один из первых. Входил в атомный комитет США. Давал консультации, куда лучше бросать первые бомбы на Японию. Его дело развил - Джон Нэш. В 50м защитил диссертацию, где изложил все, что развить. От него - "Равновесие по Нэшу", бескоалиционные игры. В отличие от теории Неймана, Нэш рассматривал ситуации, когда существует несколько оптимальных наборов стратегий. Которые были устойчивы - отсюда и устойчивость, равновесие по Нэшу. Несколько устойчивых состояний возможны - и в экономике, и политике и много где. Теория игр актуальна и для настоящего времени. 50е-70е - время развития этой науки, позднее - период разочарования. Наука развивалась при мощной государственной поддержке - РЭНД-Корпорэйшн, почти военное формирование. В 70е - охлаждение мирового интереса, из-за разочарования в практических результатах. В настоящее время основное направление развития - бескоалиционные игры, це Нэш развивал. В Советской России. Конечно, теория игр развивалась. Но это была калька с рэнд-корпорэйшн. Идеологические соображения. Применение вступало в противоречие с Марксизмом, тк отрыв формы от содержания и решения принимают игроки, а не классы. Рандомизация. Применяется в военной области, международных соглашениях. Ограничения. Вопреки распространенному мнению, ТИ - всего лишь инструмент анализа двух или более сторон. Скорее средство для поддержки принятия решений, чем инструмент для принятия решения. Причины ограничения ТИ на практике. - В рамках ТИ 1 критерий - выигрыш, в реальности факторов и критериев много. - Неполнота информации. 1 человек может в нескольких играх участвовать - Неизвестен выигрыш противника. Сложность количественной оценки при построении игры. - Вся теория игр на рациональности поведения всех людей. Неучет человеческого фактора. - Техническая сложность решения игр при большом количестве стратегий. - Игры с большим числом игроков имеют математическое решение лишь в частных случаях.
Литература. Ее не много, а очень много. Большинство этих книг - сложные, и их смотреть нинада, пнятненько? Вильямс Дж. Д. - Совершенный стратег или букварь по теории стратегических игр. Изложено довольно-таки просто, и осмотрены в основном конкретные игры. Diplomacy Games. Formal Models and International Negotiations - Springer.
Типы игр и их взаимосвязь. 1 - число игроков. 2 игрока - парные игры. Теория парных игр наиболее разработана. Число игроков - n. n=2. При n>2 появляется возможность возникновения коалиций - это жутко усложняет дело. Настолько, что коалиционные игры не рассматриваются почти. Тем не менее, при н больше 2 возможны и бескоалиционные игры, которые и рассматривал Нэш. 2 - выигрыш. Сумма выигрышей и проигрышей. В простейшем случае выигрыш одной - проигрыш другой. Такие игры называют с нулевой суммой - Zero Sum, называемые еще Антагонистические игры. Безобидные(честные игры) - в большинстве выигрыш одного равен 0. Игры с ненулевой суммой - выигрыш одного и проигрыш другого складываем, но не получаем. Соответствуют возможности достижения взаимовыгодного положения. Игры с нулевой суммой реже соответствуют действительности. 3 - по числу стратегий. Игра н*м - у первого игрока н стратегий, у второго - м. 4 - многоходовые и одномоментные. Многоходовую игру сводят к одномоментной. Под стратегией игрока понимается вся последовательность ходов - одна стратегия. Игры, в которых у игроков конечное число стратегий - конечные. Бесконечное число стратегий - бесконечная игра. Выбор стратегии или выбор хода может делаться осознанно - и тогда это называется личный ход. Неосознанно - называется "случайный выбор". Игры, которые содержат только случайный выбор - азартные. До 20 века - основной элемент теории игр. Стратегическая неопределенность связана с неопределенностью выбора хода противника. Игры качества - двузначный ответ, важно только кто победил. Нам нужна одна победа, мы за ценой не постоим. Игры степени - желательность исхода игры определяется значением численного параметра. При играх степени каждый игрок стремится максимизировать свой выигрыш. Нормальная форма представления. Пусть у первого игрока 2 возможные стратегии, у второго - 3.(таблица) 1 стратегия 1го игрока и 1я 2гоигрока - выигрыш 5, 2я 1го - 7. 2 1го и 2 2го - 4. 1 1го и 3 2го - 8. Такая таблица - матрица выигрышей, или платежная матрица. Но она идет для первого игрока. Если игра с нулевой суммой, то матрица та же, только со знаком минус. Так как она повторяет предыдущую, ее не пишут. Это (матрица) нормальная форма игры. Если сумма не нулевая, то матрицу выигрыша для 2 игрока писать надо. Если матрицы 2, то такая игра - БИМАТРИЧНАЯ. Пример игры с нулевой суммой. 2 человека. Показывают 1,2 или 3 пальца. Если сумма четная, то выиграл первый игрок, нечетная - второй. Пример 2ой - бросают кубик. Игра в виде граф. Помимо матричной формы игру можно представить в виде графа. Граф - дерево игры, потому что похож на дерево с ветками. Граф - многоходовой игре. В каждой точке разветвления делается выбор хода. Граф аналогичен дереву решений. Рассмотрим игру "базар" с 3 игроками. Вор, продавец, полицейский. (В скобках выигрыш) Вор - не воровать(0, 0,0)/ украсть, продавец молчит (1,-2,0) либо кричит, полиция вступает в игру - ловить(-2,1,2) или не ловить(1,-3,0)/вооруженное ограбление, кричать или не кричать продавцу. Продавец кричит и полиция ловит(1,-2,0) или не ловит(-5,1,3). Не кричит - (1,-1,0). Анализ такого графа позволяет понять предпочтение игроков и сделать прогноз в развитии ситуации. Любой игре в виде графа можно поставить игру в нормальной форме в виде матрицы. Карточная игра, 2 человека и 2 карты. У одного 2ойка и туз. Верит/ не верит Туз, правда 1 -2 Туз, лжет -1 -2 2, правда -1 2, лжет 1 -1 Непонятно, как так. Ну и ладно.
Лекция 3. Решение бескоалиционных игр в чистых стратегиях. Выбор оптимального ответного хода. Принцип минимакса.
(вот эту лекцию найдите лучше где-нибудь еще, или повикипедьте) Решение игры в чистых стратегиях - конкретная стратегия однозначно лучше. Когда же ни от одной стратегии не отказываются, стратегии смешанные. Есть игры смешанных стратегий. Задача оптимального выбора с учетом выбора соперника. Простейшая процедура - последовательное исключение заведомо слабых стратегий. Если окажется, что при любом выборе второго игрока некоторая стратегия первого игрока заведомо хуже, чем другая, то ее надо сразу вычеркнуть сразу же. Аналогично рассуждает и второй. Невыгодная строка матрицы - доминируемая. Если 2 страны одинаковы, то это дублирующая стратегия. Выбор оптимального ответного хода. Предполагается, что противник уже сделал ход. И какой ход - известно. Если известна матрица игры и известен выбор соперника, то решение игры тривиально. Иногда выбор оптимального хода надо делать, когда задана не матрица, а функция. Принцип минимакса. Противник будет находить в строке минимальное число. А мы это знаем. Поэтому первый игрок заинтересован выбрать ту стратегию, где этот минимальный элемент больше, чем в других строках. Таким образом первый игрок обеспечивает наилучший гарантированный выигрыш. Выбор гарантированного выигрыша, который не может ухудшить соперник - рациональный выбор. Рациональный выбор подразумевает, что при одной стратегии выигрыш равен 50, а при другой - от 40 до 70 - то выбирается 50. Минимакс и Максимин. В таких случаях говорят, что минимаксная стратегия неустойчива. 2 3 4 - 2 рационально 6 0 5 -1 2 3 3 по вертикали рациональна
Когда нижняя и верхняя цена совпадает, это число называется ценой игры и игра решается в чистых стратегиях. Элемент матрицы, стоящий на пересечении стратегий - седловая точка. Седловых точек может быть несколько. Теория Нэша. Игры с ненулевой суммой, когда у каждого игрока своя матрица, биматричная.
1-я 2я 1 стр. 2,2 2,2 2 стр. 4,2 1,3 3 стр. 5,4 1,3 Для биматричных игр минимакса нет. Однако есть понятие, аналогичное седловой точке. Оно называется "устойчивость по Нэшу". Если она есть, то оба игрока будут придерживаться определенной стратегии, так как иначе их выигрыш уменьшается при неизменной стратегии партнера. Ни одному игроку не выгодно менять стратегию, если другие ее не меняют. В вышестоящей игре точка 3стр - 1-ой устойчива. В отличие от седловых точек, равновесий по Нэшу может быть несколько. Понятие множественного равновесия может соответствовать смене государственного строя и другим м-н ситуациям.
Седловые точки и равновесие по Нэшу. Игры в смешанных стратегиях. Иногда ситуация такая, шо решение - пропорция, которую следует применять при стратегии игроков. Стратегия, которой соответствует 0, называется неактивной. А те, которые используются - активные. Решения в смешанных стратегиях, когда активна только 1 стратегия. Выигрыш при смешанной стратегии всегда больше, чем при любой из чистых стратегий. Для любой парной игры с нулевой суммой всегда есть решение. Частота применения стратегий. Смысл в том, что зная частоту применения, можно посчитать вероятность. Если смешанная стратегия выражена в виде пропорции, то стоящие в ней числа - относительные частоты применения стратегий. Пример частоты применения стратегии - русская рулетка. Использование датчиков случайных чисел. Любые вычислительные методы, связанные с использованием этого датчика - методы Монте-Карло. Игра - Наступление и оборона. Оборона защищает 2 объекта, 1 из них в три раза важнее другого. Защитить можно лишь 1 объект и напасть можно на 1. Составим матрицу игры, где элементы равны стоимости уцелевших объектов. Условия игры таковы, что если напали на охраняемый объект - победила оборона. Важный не важный Важный 4 3 Не важный 1 4 Цена игры пока неизвестна - надо мешать стратегии. Надо вычесть второй столбец матрицы из первого. 4 - 3 получаем 1 1 - 4 получаем -3 Оптимальная смесь - отношение нижнего элемента к верхнему - 3 к одному. Это для защиты. Для нападения же надо вычесть - первый столбец из второго. Нападать надо чаще на мене важный объект. Защищать чаще - более важный. 7 - 3 = 4 2 - 11 = 9 Получается 9 к 4. Рано поздно Рано 0 - -1 1 Поздно -3 - 0 -3 У м.ч. лучше приходить 3жды рано и 1 опаздывать, девушке без лучше опаздывать три раза.
Если у одного 2 стратегии, а у 2 больше, чем 2, то игра решается графическим методом. 1я 2я 3я 1-я х a11 a12 a13 2-я (1-х) a21 a22 a23 Обводим 1 столбик. Если у 2го игрока 3 стратегии, получится картинка с 3 прямыми линиями. Графический метод решения игр. На пересечении стратегий выбираем минимульную крышу по минимальным пересечениям. Затем - максимальную точку на ней. Оптимальная смесь стратегий 2го игрока определяется потом путем дополнительных расчетов, хотя сразу можно сказать, что противнику следует использовать только те стратегии, линии которых проходят через выделенную точку. Любую парную игру с нулевой суммой можно решать приближенно. Например, с использованием программой Excel. Там есть функция "поиск решений".
25.10. Теоретико-игровой анализ международных отношений. Простые игровые модели мн конфликтов. Анализ карибского кризиса. Применение вероятностной угрозы. Типовые игры, применяемые в анализе м/о. Карибский кризис как парная игра с ненулевой суммой 2 на 2. 1 игрок - сша. 2 - ссср. США - не угрожать(игра закончена, -2 балла и 2 для советов - то есть -2,2) или угрожать - перед вопросом ссср, убрать ракеты(1,-4) или защищать(-10,-8). P - вероятность жесткой позиции и вероятность мягкой позиции - 1-p. Жесткая и мягкая позиция отличается выигрышами для ссср в случае различных сценариев. При жесткой выигрыши в случае защиты бомб больше. Игра начинается с учетом точки природы. Средний выигрыш при угрозе для США: -10(это при жесткой позиции ссср) умноженное на П плюс 1 (выигрыш сша при мягкой позиции ссср) умноженное на 1-П. Средний выигрыш равен 1-11П. Пменьше 3/11. То есть, при П меньше 0.27 сша не должно угрожать ссср. 2- применение вероятностной угрозы. Существует концепция вероятностной угрозы. - brinkmanship. Противнику объявляют, что если через 24 часа не убираете ракеты, то мы бросаем монетку и выпадет орел - мы начинаем войну. Угроза дозируется. Вероятность войны - вероятность ку. -10Ку - 2(1 - Ку)=-2 - 8Ку. То есть надо и думать за противника. Вывод - если П меньше, чем 0.27, надо применять простую угрозу, если от 0.27 до 0.38 - дозированную угрозу, больше - не связываться. На самом деле, ситуация с brinkmanship требует очень точного знания параметров всех - что невозможно. Коллективное пастбище. Если заводить еще одну овцу - выигрыш в 1. Издержки - -10/Н(то есть вред деленный на количество коллег-пастухов). Но. Тогда поголовье овец будет расти и расти и места не останется. Существует несколько типовых парных симметричных игр 2на2 с ненулевой суммой. Первая - Диллема заключенного. Задержаны 2 преступника и допрашивают отдельно их. 1 валит все на другого - то получает максимальный выигрыш, второй получает максимальный срок. Оба признаются - защитывается явка с повинной и каждому по году. Если оба отрицать будут - их обоих отпустят. Стратегии молчать и признаться. Если оба молчат - 1,1. Молчать признаться Молчать 1,1 -3,3 Признаться 3,-3 -1,-1. Польза для общества - польза для обоих - если оба молчат. В игре 2 точки равновесия по Нэшу. Аналог в м/о - выполнение соглашений о разоружении, контроле за вооружениями. Аксельрод. Чикен - свернуть или не свернуть от навстречу едущей машины. Свернуть не сворачивать Свернуть 1,1 -1,3 Не сворачивать 3,-1 -3,-3. Равновесие неустойчиво потому что каждому хотелось бы перейти в другую точку. Аналоги в м/о - гонка вооружений, переговоры с угрозой применения санкций, нагнетание напряженности в отношениях. Охота на оленя. 2 охотника - 2 стратегии - подстрелить оленя или зайца. Оленя надо помочь донести, но это более ценная добыча. Если только 1 пойдет на оленя - олень пропадет. Олень заяц Олень 1,1 -3,0 Заяц 0,-3 -1,-1 Аналоги в м/о - взаимная выдача преступников, применение экономического эмбарго или санкций. Тупик. Уступить не уступить Уступить -1,-1 -3,3 Не уступить 3,-3 1,1 Правый нижний угол - равновесие по Нэшу. Аналоги - война. Страховка. Или эстафета. Идет эстафета. Выкладывается не выкладывается Выкладывается 1,1 -3,-2 Не выкладывается -2,-3 0,0 Аналоги - выполнение договоров в м/о. Киотский протокол, конвенция по правам детей, договор о нераспространении ядерного оружия. Битва полов. Пара решает, куда пойти вечером. Со стороны мужчины мы. Футбол опера Футбол 8,4 3,3 Опера 2,2 4,8 Дамба. Два хозяина на 1 берегу реки - иногда их затапливает. Построить дамбу или нет? Затраты на строительство - 4, ущерб от наводнения - 6. Строить не строить Строить -4,-4 -10,-6 Не строить -6,-10 -6,-6 Есть еще одна игра "дамба ", но они тут на разных берегах. Если только 1 строит - то урон соседу. Строить не строить Строить -4,-4 -4,-10 Не строить -10,-4 -6,-6 Игр больше и нет смысла все смотреть.
Лекция 6. Применение теории игр в политологии. Выбор стратегии на выборах. Игры на оптимальное размещение. Оптимизация предвыборной платформы с учетом выбора избирателей. Пляж.2 продавца продают прохладительные напитки. (Секторы, х - палатка) 1 2х 3 4 5 6х 7 8 9 Из 1 и 3 сектора идут ко 2ому в палатку, из 5 и 7 - в 6. Стратегий 9, игра 2 на 2. Построим матрицу выигрышей для 1 продавца. Число секторов пляжа - выигрыш. 1 2 3 4 5 6 7 8 9 1 4.5 1 1.5 2 2.5 3 3.5 4 4.5 2 4.5 2 2.5 3 3.5 4 4.5 5 5.5 3 1.5 7 4.5 3 3.5 4 4.5 5 5.5 4 7 6.5 6 4.5 4 4.5 5 5.5 6 5 6.5 6 5.5 5 4.5 5 5.5 6 6 6 7 8 9 (до конца мы не осилили) Оптимальный вариант - 5 столбец и 5 строчка. Рассмотрим 2 кандидата на выборы. 9 секторов пляжа - 9 секторов избирателей - крайне левые, левые, правые итд. Каждый интервал - 10 тысяч избирателей. Какую предвыборную платформу выгоднее выдвинуть - куда поставить палатку? Гарантированный вчигрыш - когда позиции умеренные. Если проводят выборы без праймериз, то оба кандидата будут умеренными. Этот подход легко обобщается на случай, когда неравномерный спектр избирателей. При этом достаточно задать разное количество отдыхающих в секторах пляжа. Например - во всех секторах по 10 тысяч, в 6 и 7по 15. В связи с этим изменится матрица выигрыша, ее придется пересчитать. В данном случае получается, что для обоих игроков минимаксными стратегиями является 5 и 6. Недостатки таких моделей - не учитывается отказ избирателей от голосования, не учитываются затраты на агитацию итд