Основы теории игр

ЛЕКЦИЯ 5. ОСНОВЫ ТЕОРИИ ИГР ИСТОРИЯ ВОПРОСА 1944 г. Джон фон Нейман, Оскар Моргенштерн «Теория игр и экономическое поведение». 50-е годы- Джон Нэш - методы анализа, в которых все участники или выигрывают, или терпят поражение. Эти ситуации получили названия o Стороны должны использовать оптимальную стратегию, что приводит к созданию устойчивого равновесия по Нэшу. o Классический подход к конкуренции А.Смита, когда каждый сам за себя, неоптимален. o Оптимальны стратегии, когда каждый старается сделать лучше для себя, делая лучше для других. Томас Шеллинг. «Стратегия конфликта» (нобелевская премия по экономике 2005 г). Пример: ситуация купли-продажи дома. У продавца и покупателя есть общий интерес: один хочет продать дом, другой – его купить. Конфликт - вопрос цены сделки: продавец хочет продать подороже, покупатель – купить подешевле. Поведенческие стратегии договорится между собой (на каких условиях, и как каждому добиться для себя лучших условий) - исследования Шеллинга. 2 ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ИГР Игра – модель конфликтной ситуации, имеет правила действий игроков, для достижения выигрыша в результате принятия некоторой стратегии. Теория игр (ТИГР) –прикладная междисциплинарная наука, изучающая математические модели принятия решений в конфликтных ситуациях. Антагонистические игры - интересы участников противоположны. Игра коалиционная - участвуют n лиц, могут вступать между собой в постоянные или временные коалиции. Биматричные, дифференциальные, матричные, статистические игры с природой и др. Цель теория игр - выработка оптимальных стратегий для каждого игрока. Локальные задачи теории игр 1) выяснение условий равновесия (компромисса, седловой точки), в наибольшей степени устраивающего игроков; 2) поиск устойчивых решений, когда отход от оптимальной стратегии невыгоден обоим игрокам; 3) доказательство, что при многократном повторении игры и разных стратегиях, седловая точка и устойчивые решения существуют. История. 1944 кн. Дж. фон Нейман, О. Моргенштерн. Теория игр и экономическое поведение (решение бизнес-задач с неполной информацией). 1960-е годы. Нэш, Гурвиц. 1994, 1996, 2007 -Нобелевские премии по ТИ. 2007: Гурвиц, Майерсон и Маскин «за первопроходческий вклад в теорию игр и принятие решений». Они дали ответ на вопрос: как осуществить сделку с максимальной пользой для себя? Механизм оптимален, если для каждого игрока выгоднее сказать правду, чем солгать. Тогда каждый останется в выигрыше 3 ИНТЕРПРЕТАЦИЯ СТРАТЕГИЙ Преступник Б Стратегия «молчать» Преступник Б Стратегия «предать» Преступник А Стратегия «молчать» Пол года каждому 10 Лет преступнику А Отпустить преступника Б Преступник А Стратегия «предать» 10 Лет преступнику Б Отпустить преступника А 2 года каждому БИМАТРИЧНЫЕИГРЫ. ИГРЫ С НЕНУЛЕВОЙ СУММОЙ Игра с ненулевой суммой двух лиц: биматричная игра. Матрица выигрыша 1-го игрока: строки, столбцы – стратегии 1-го, 2-го игроков, соответственно; в клетках таблицы – значения выигрыша 1-го игрока. Матрица выигрыша 2-го игрока: строки, столбцы – стратегии 1-го, 2-го игроков, соответственно; в клетках таблицы – значения выигрыша 2-го игрока. Игра с нулевой суммой двух лиц: антагонистическая игра: единственная матрица выигрышей одного из игроков; выигрыш одного игрока означает проигрыш другого, (сумма равна нулю). ! Интересы игроков не всегда полностью противоположны: имеется возможность сообщать друг другу о своих намерениях, координировать свои действия, применять блеф, угрозы, другие способы обмена информацией. ! Выигрыш одного игрока – не обязательно означает проигрыш другого. ! Сумма выигрышей – не обязательно равна нулю (игры с ненулевой суммой). Общая особенность у шахмат, карточных игр, войн, переговоров, рыночной конкуренции, аукционов: общее описание стратегий при помощи теории игр; если имеет место противоборство субъектов, возникает игра. 5 БИМАТРИЧНЫЕ ИГРЫ С НЕНУЛЕВОЙ СУММОЙ. ПРИМЕР 1 В зависимости от выбора стратегий в игре складываются четыре ситуации, которые могут приносить игрокам разное моральное удовлетворение. Оценки морального удовлетворения выставим в шкале с положительными и отрицательными баллами и примем их за выигрыши игроков. Пусть цель каждого игрока МАКСИМИЗАЦИЯ индивидуального выигрыша. Две матрицы однозначно задают правила игры Самый большой по модулю выигрыш (−3) соответствует случаю, когда у преподавателя остались сомнения в добросовестности студента, но зачет6 уже поставлен БИМАТРИЧНЫЕ ИГРЫ С НЕНУЛЕВОЙ СУММОЙ. ПРИМЕР 1. Зачет Определение равновесных стратегий Сравнение равновесных выигрышей игроков (1, 1) , (2, 2) ⇒ значения клеток (2 0) 〉 (0 -1) Стратегия (1 , 1) наиболее предпочтительная для игроков Содержательно в равновесных ситуациях воплощается «закон справедливости»: за хорошую подготовку к зачету студент получает зачет, а за плохую подготовку по справедливости не получает. Моральное удовлетворение студента и преподавателя в первой ситуации выше, чем во второй7 * БИМАТРИЧНЫЕ ИГРЫ С НЕНУЛЕВОЙ СУММОЙ. ПРИМЕР 2. Дилемма заключенного Платежные матрицы 8 * БИМАТРИЧНЫЕИГРЫ С НЕНУЛЕВОЙ СУММОЙ. ПРИМЕР 2. Дилемма заключенного Сравним ситуации (1, 1) и (2, 2). Выигрыш в ситуации (1, 1) выше, т.е. более выгодной стратегией является молчание. Однако, не имея контактов между собой и к тому же не очень доверяя друг другу, каждый из заключенных может прийти к выводу, что нужно сознаваться и получить 3 года, чем молчать, рискуя получить 10 лет. Дилемма заключенного в экономике: решение ЛПР о максимизации выигрыша может обернуться вредом для него самого или для другого ЛПР. Дилемма объясняет, почему продавцы зачастую стремятся к сговору на рынке вместо конкуренции, которая была бы выгоднее для общества 9 * БИМАТРИЧНЫЕ ИГРЫ С НЕНУЛЕВОЙ СУММОЙ. ПРИМЕР 3. Дележ ресурсов Две пиратских процедуры дележа добычи (золото), которые выглядят вполне демократичными и открытыми, но происходят в атмосфере взаимного недоверия. СЛУЧАЙ 1. 10 * БИМАТРИЧНЫЕ ИГРЫ С НЕНУЛЕВОЙ СУММОЙ. ПРИМЕР 3. Дележ ресурсов. СЛУЧАЙ 2. Влияние недоверия 11 АНТАГОНИСТИЧЕСКИЕ ИГРЫ. ИГРЫ С НУЛЕВОЙ СУММОЙ Для поиска оптимальной стратегии используется «пессимистический» критерий максимина/минимакса и основанный на выборе наилучшей из наихудших возможностей. Основные предположения: 1) оба игрока одинаково сильны и не прощают ошибок; 2) оптимальное решение достигнуто, если ни одному из игроков невыгодно изменять свою стратегию (точка равновесия или седловая точка), т.е. достижение компромисса в реальном конфликте сторон, имеющих противоположные интересы, является выгодным для каждого 12 из противников АНТАГОНИСТИЧЕСКИЕ ИГРЫ С НУЛЕВОЙ СУММОЙ. Пример 4 Игры, имеющие седловые точки, называют вполне определенными, или играми с полной информацией (каждый игрок знает все предшествующие ходы, как свои, так и противника). Платежная матрица Находим минимальный элемент в каждой строке матрицы и выбираем среди них максимальный (МАКСИМИН РАВЕН 3) Седловая точка: одновременно является минимальным элементом строки и максимальным элементом в столбце платежной матрицы. Находим максимальный элемент в каждом столбце матрицы и выбираем среди них минимальный (МИНИМАКС РАВЕН 3). Для данной матрицы α = β = ν =3, т.е. игра имеет седловую точку (точка равновесия, или точка Нэша). Здесь ν – чистая цена игры. 13 АНТАГОНИСТИЧЕСКИЕ ИГРЫ С НУЛЕВОЙ СУММОЙ. Примеры 5 Игры с полной информацией (имеют седловую точку): шашки, шахматы, крестики/нолики, «выкладывание монет».... Выкладываются монеты на пустое место. Проигрывает тот, кому места не достанется. Оптимальная стратегия: если 1-й игрок кладет монету в центр, а затем симметрично повтряет ход 2-го игрока, то шансов выиграть 2-му игроку не остается. Большинство антагонистических игр двух лиц с нулевой суммой не имеют седловой точки (нет решения в чистых стратегиях) Интервал [− 2, 2] является Игра Морра с платежной матрицей А= «ничейным», каждый из игроков может попытаться улучшить результат на этом интервале ? Если α < β, то существует ли в игре цена, и какие стратегии рекомендовать игрокам в качестве оптимальных стратегий? ИГРА «ОРЛЯНКА». Условия игры: 1-й игрок выкладывает монету на стол, 2-й игрок (не видя монеты) угадывает, какой стороной вверх она положена («орел» – О, «решка» − Р). В случае угадывания получает от 1-го игрока 1 рубль, а в противном случае уплачивает 14 ему 1 рубль. АНТАГОНИСТИЧЕСКИЕ ИГРЫ С НУЛЕВОЙ СУММОЙ. Пример 6. ОРЛЯНКА Условия игры: 1-й игрок выкладывает монету на стол, 2-й игрок (не видя монеты) угадывает, какой стороной вверх она положена («орел» – О, «решка» − Р). В случае угадывания получает от 1-го игрока 1 рубль, а в противном случае уплачивает ему 1 рубль. Седловой точки нет. Если игра проводится только один раз, то каждый из игроков может принять любое решение. Оптимальных стратегий нет. При многократном повторении игры положение меняется. Придерживаться одной стратегии невыгодно, их надо случайно смешивать (причем в данной игре – с одинаковой частотой). СМЕШАННОЙ СТРАТЕГИЕЙ ИГРОКА НАЗЫВАЕТСЯ ПОЛНЫЙ НАБОР ВЕРОЯТНОСТЕЙ ПРИМЕНЕНИЯ ЕГО ЧИСТЫХ СТРАТЕГИЙ. Если 1-й игрок имеет m чистых стратегий, то его смешанная стратегия p = (p1, p2,…, pm), pi – вероятность применения чистой стратегии xi при многократном повторении игры, p1+ p2+…+pm = 1. Аналогично, если 2-й игрок имеет n чистых стратегий, то его смешанная стратегия q = (q1, q2,…,qn), qj − вероятность применения чистой стратегии yj, q1+ q2+…+qn=1. Чистая стратегия – частный случай смешанной стратегии: если в смешанной стратегии i-я чистая стратегия применяется с вероятностью 1, то все остальные чистые стратегии не применяются. Для соблюдения секретности каждый игрок применяет свои стратегии независимо от выбора другого игрока (лотерея). Основная теорема теории игр (1927 сформулировал Борель, 1928 доказал Нейман). Всякая конечная антагонистическая игра двух лиц с нулевой суммой имеет цену ν* и у каждого игрока имеется, по меньшей мере, одна оптимальная стратегия (p*, q*). АНТАГОНИСТИЧЕСКИЕ ИГРЫ. АЛГОРИТМ ПРОВЕРКИ ОПТИМАЛЬНОСТИ СТРАТЕГИИ. Свойство оптимальности некоторой стратегии (p, q): M (pi, q*) ≤ M (p*, q*) ≤ M (p*, qj) (*) справедливое для всех i = 1, 2,…, m; j = 1,2,…, n; pi=P{xi}, qj=P{yj}, 1. Определить величину среднего выигрыша М(p*, q*) для заданной смешанной стратегии. 2. Проверить, выполняются ли в (*) неравенства слева для всех i = 1, 2,…, m. Если для некоторого i неравенство не выполняется, то стратегия p* не является оптимальной и останов. 3. Проверить, выполняются ли в (*) неравенства справа для всех j = 1, 2,…, n. Если для некоторого j неравенство не выполняется, то стратегия q* не является оптимальной и останов. 4. Если неравенства (*) справедливы для всех индексов i, j, то стратегии p* и q* являются оптимальными, а цена игры равна М(p*, q*). «Пессимистический» критерий - максимина/минимакса Для построения матрицы игры необходимо определить стратегии игроков: X = { х1, x2, x3, x4 } = {(1, 1), (1, 2), (2, 1), (2, 2)}; Y = { y1, y2, y3, y4 } = {(1, 1), (1, 2), (2, 1), (2, 2)}, первое число: сколько пальцев показывает игрок 1, второе – сколько пальцев, по его мнению, покажет противник. Игра состоит из 4×4 = 16 партий, матрица выигрышей А 1-го игрока имеет вид: В антагонистических играх двух лиц с нулевой суммой единственным критерием выбора оптимальной стратегии является следующий: Оптимальной стратегией игрока является такая стратегия, использование которой при многократном повторении игры обеспечивает игроку максимально возможный средний выигрыш (или минимально возможный средний проигрыш). АНТАГОНИСТИЧЕСКИЕ ИГРЫ. ПРОВЕРКА ОПТИМАЛЬНОСТИ СТРАТЕГИИ. Пример 7 Игра Морра с платежной матрицей А Задача. Будут ли оптимальными в этой игре следующие стратегии 1-го и 2-го игрока: p = (0, 3/5, 2/5, 0) и q = (0, 4/7, 3/7, 0). Решение. Следует проверить справедливость неравенства для всех i, j = 1, 2, 3, 4. M (pi, q*) ≤ M (p*, q*) ≤ M (p*, qj) (*) 1) Оценим величину среднего выигрыша для заданных стратегий: М(p, q) = ∑i∑jaijpiqj = 0×(0×0+2×4/7 − 3×3/7+0×0) + 3/5×( − 2×0 +0×4/7+0×3/7+ 3×0) + 2/5×(3×0+0×4/7+0×3/7 − 4×0) + 0×(0×0 − 3×4/7+4×3/7+0×0) = 0. 2) Проверим, выполняются ли неравенства слева M (pi, q) ≤ M (p, q) для i = 1, 2, 3, 4 M (p1, q) = 0×0+2×4/7 − 3×3/7+0×0 = − 1/7 < 0, M (p2, q) = − 2×0+0×4/7+0×3/7+3×0 = 0, А= M (p3, q) = 3×0+0×4/7+0×3/7 − 4×0 = 0, M (p4, q) = 0×0 − 3×4/7+4×3/7+0×0 = 0. 3) Проверим, выполняются ли неравенства справа M(p, q) ≤ M(p, yj) для j = 1, 2, 3, 4 M(p, q1) = 0×0 − 2×3/5+3×2/5+0×0 = 0, M(p, q2) = 2×0 +0×3/5+0×2/5 − 3×0 = 0, M(p, q3) = − 3×0 +0×3/5+0×2/5+4×0 = 0, M(p, q4) = 0×0+3×3/5 − 4×2/5+0×0 = 1/5 > 0. 4) Неравенства справедливы для всех индексов i, j, следовательно, стратегии p, q являются оптимальными: p:=p*, q:=q*, а цена игры равна 0. АНТАГОНИСТИЧЕСКИЕ ИГРЫ. ИНВАРИАНТНОСТЬ РЕЗУЛЬТАТА ОТНОСИТЕЛЬНО ЛИНЕЙНЫХ МАТРИЧНЫХ ПРЕОБРАЗОВАНИЙ Удаление доминируемых и дублирующих строк (столбцов) не влияет на решение игры. Стратегии называются дублирующими, если в матричной игре имеются строки (столбцы) с одними и теми же элементами. Рассматривая стратегии 1-го игрока, сравним поэлементно строки s и t. Целью 1-го игрока является максимизация выигрыша. Если все asj ≥ atj (j = 1, 2,…, n), то выигрыш 1-го игрока при стратегии xs будет больше, чем при стратегии xt. В этом случае стратегия xt будет доминируемой, и ее можно исключить, упростив тем самым игру. Поскольку 2-й игрок стремится минимизировать свой проигрыш, то, рассматривая его стратегии, сравним поэлементно столбцы r и h. Если все элементы air ≥ aih (i=1, 2,…, m), то проигрыш 2-го игрока при стратегии yr будет больше, чем при стратегии yh. В этом случае стратегия yr будет доминируемой, и ее можно исключить из матрицы, упростив игру.