Динамические игры с полной информацией реферат
Обновлено: 02.07.2024
Динамической называется игра, в которой каждый игрок может сделать несколько ходов, и по крайней мере один из игроков, делая ход, знает, какой ход сделал другой игрок (возможно, он сам).
В динамических играх различают полную и совершенную информацию. Если все игроки имеют общую информацию о правилах игры и функциях выигрыша, то информацию считают полной. Это понятие в равной степени относится как к статическим, так и к динамическим играм. Понятие совершенной информации относится только к динамическим играм, в которых игроки делают ходы последовательно в разные моменты времени. Говорят, что динамическая игра обладает совершенной информацией, если все сделанные ходы сразу же становятся известны всем игрокам.
Иногда динамическую игру удобно представить в виде дерева. Такое представление называется развернутой формой игры. Она должна содержать:
- множество вершин дерева игры, в том числе одну начальную вершину;
- для каждой вершины, кроме начальной – единственную вершину, которая непосредственно ей предшествует; при этом цепь предшествующих вершин, построенная из любой вершины, должна заканчиваться в начальной вершине (это предполагает отсутствие циклов);
- для каждой вершины, кроме конечных – единственного игрока, которому принадлежит ход в данной вершине;
- для каждой конечной вершины – вектор выигрышей всех игроков;
куда лететь. Если он летит в Гавану, игра заканчивается, а если в Нью-Йорк, то ход делает террорист, который решает, взрывать самолет или нет. На конечных вершинах дерева проставлены выигрыши игроков
(первый игрок – пилот):
Метод обратной индукции.
– не взрывать, поскольку при заданных выигрышах ему выгоднее именно не взрывать.
После этого игру можно частично свернуть (редуцировать), и дерево игры упрощается:
Поскольку действия террориста в Нью-Йорке несложно предугадать, пилот выбирает лететь в Нью-Йорк, где его выигрыш больше.
Таким образом, обратная индукция показывает, что пилот полетит в Нью-Йорк, а террорист не будет взрывать бомбу.
Обратную индукцию можно реализовать и на основе функций отклика игроков.
На первом шаге условие первого порядка для фирмы дает следующую функцию отклика фирмы на отбираемую долю выручки:
Зная эту функцию, рэкетиры максимизируют свою функцию выигрыша. Для этого надо подставить функцию отклика фирмы в функцию выигрыша рэкетиров и применить к полученному выражению условие первого порядка. Это дает значение α=1/2.
Определение. Стратегия (чистая) в динамической игре – это полный план действий игрока, который показывает, что он будет делать в каждой из вершин, в которой ход принадлежит ему.
Следует отметить, что в этом плане игрок указывает свои действия даже в тех вершинах, в которых он в процессе игры реально вряд ли окажется.
1-й игрок имеет две стратегии, совпадающие с альтернативами в вершине 1. Игрок 2 имеет 4 стратегии, каждая из которых определяет его действия в двух вершинах – 2 и 3. Его стратегии следующие: (2IBM,3IBM), (2IBM,3Mac), (2Mac,3IBM), (2Mac,3Mac).
9.9.1. Динамические игры с неполной информацией (динамические байесовские игры) обобщают статические игры с неполной информацией (статические байесовские игры). Здесь ситуация аналогична той, что имеет место во взаимодействии динамических и статических игр с полной информацией, которым были посвящены параграфы 9.1—9.7.
Важная особенность динамических игр с неполной информацией — наличие неизвестных вероятностей, с которыми игрок находится в той или иной вершине своего информационного множества, состоящего, естественно, более чем из одной вершины. Поэтому игрок должен делать предположения относительно того, с какой вероятностью он окажется в той или иной вершине своего информационного множества. Если у игрока есть такие предположения, то на их основе он выбирает стратегию, которая может обеспечить ему наибольший ожидаемый выигрыш
Эта идея является основной в понятии совершенного байесовского равновесия (СВР), для описания которого следует иметь: 1) набор стратегий (ур . всех игроков Р . Р ; 2) набор ожидаемых каждым игроком Рк стратегий = (уД . б Л) всех остальных игроков Р . Рк_ Рк+, . Рт, к = 1, . т\ 3) для каждого игрока Рк в каждом информационном множестве, в котором ему принадлежит ход, ожидаемое игроком Рк распределение вероятностей, заданное на вершинах этого информационного множества, к - 1. /и.
Для того чтобы описанный набор стратегий и ожиданий составлял СВР, требуется выполнение следующих условий: а) ожидаемое распределение вероятностей на вершинах информационных множеств для каждого игрока Рк соответствует (согласованы с) выбранной им стратегии Бк и тем стратегиям Б_к9 которые, как он (игрок Рк) ожидает, выберут остальные игроки Р. Рк_ Рк+. Р ; б) выбранная стратегия последовательно оптимальна при данных ожиданиях, т.е.
выбор игрока Рк в каждом его информационном множестве должен быть таким, чтобы максимизировать ожидаемый выигрыш в предположении, что после каждого информационного множества игра будет продолжена в соответствии с набором стратегий к= 1. т\ в) ожидаемые стратегии Б_к совпадают с фактически выбранными стратегиями Б_к9 т.е. = к = 1, . /и.
Особенность СВР в том, что в общем случае для его поиска невозможно использовать обратную индукцию, за исключением игр с почти совершенной информацией. Если игра не имеет по- дыгр, то СВР следует находить как решение системы уравнений: ожидаемые распределения вероятностей на вершинах информационных множеств находятся в соответствии с набором стратегий равновесия, а стратегия равновесия выбирается каждым игроком на основе предположений об ожидаемых распределениях вероятностей на вершинах информационных множеств.
9.9.2. Проиллюстрируем построение СБР на конкретном примере.
Пример 9.9.1. (В.П. Бусыгин и др. (2000), О. Shy (1995)). В самолет, который должен лететь из пункта М в пункт G, попал террорист, который требует, чтобы самолет летел в пункт Н. В противном случае террорист угрожает взорвать самолет. Террорист не может определить, куда летит самолет, но может определить, куда он прилетел. Дерево игры показано на рис. 9.14.
СБР приведенной динамической игры с неполной информацией должно состоять из следующих величин: 1) вероятности |Хр с которой сумасшедший террорист проводит свою операцию, т.е. выдвигает свои требования и угрожает, е [0; 1]; 2) вероят
1°. Ожидаемые выигрыши пилота от двух его возможных ходов равны —1а + (—1)(1 — а) = —1 в случае, если пилот посадит самолет в пункте Я, и а(-100) + (1 — а) = 1 в случае, если пилот посадит самолет в пункте (7.
| (0; 0) |
 4°. Набор вероятностей (цД |Х2°, |Х3°, а 0 ) задает СВР, если выполнены условия В связи с тем что рЛа) = 1, если а 0 = 0 дополняется СБР вида = 0, |12° = 0, |13° = 1, 0 2 /101. Отметим, что неравенство а 2 /ю1 означает, что вероятность а 0 , с которой пилот ожидает появления сумасшедшего террориста, является малой (для сравнения сопоставьте это неравенство с неравенством V > 2 /т п. 6° этого примера). 6°. Случай, когда р2 = 1 и \1 = 1, содержательно означает, что террорист (независимо от его типа) обязательно станет выдвигать свое требование и угрожать. Тогда для пилота вероятность а иметь на борту самолета сумасшедшего террориста, очевидно, будет совпадать с вероятностью V, с какой сумасшедшие террористы появляются вообще, т.е. а = V. На основании п. 3° этого примера щОХз) = 1, если |13 2 /101, то = °> и если у ( =а ) = 2 /юр то 0 - 2 /101, то СБР имеет вид = 1, р2° = 1, а 0 = V = 2 /101, 0 2 /101 содержательно означает, что сумасшедшие террористы на свете встречаются, к сожалению, не очень редко. Для реальной действительности это, скорее всего, так и есть. 7°. Случай, когда р2 е (0; 1) — необходимое условие равенства ц3 = У2 (см. п. 3° этого примера), которое, в свою очередь, есть необходимое условие равенства а = 2 /101 (см. п. 1° этого примера). Равенство |13 = У2 влечет равенство ^(Рз) = 1 (см. п. 3° этого примера). Используя вышеприведенную формулу Байеса (р1 = 1) (см. п. 2° этого примера), получим, что откуда, принимая во внимание неравенство ц2 2 /iop отк УД а следует, что природа порождает не так уж много сумасшедших террористов, что, к сожалению, не совсем так, как было отмечено в п. 6° этого примера. Следовательно, при v 2 /l0l получаем еще одно СБР о , о 99V о 1 о 2 = ^ = 2' « -101- Таким образом, в п. 5°—7° этого примера выписаны все СБР рассмотренной динамической игры с неполной информацией. Замечание 9.9.2. Дальнейшее развитие концепции равновесия в теории некооперативных игр (равновесие Нэша, совершенное в подыграх равновесие, равновесие Нэша — Байеса, совершенное байесовское равновесие) представлено в монографии D. Fudenberg and I. Tirole (2000), в которой подробно проанализированы последовательное равновесие, совершенное равновесие относительно дрожащей руки, правильное (рорег) равновесие и т.п. Широкий спектр понятий равновесия в теории игр свидетельствует о том, что в настоящее время вопрос о рациональном определении понятия оптимального решения игры, по-видимому, еще не имеет приемлемого ответа.
Первый слайд презентации: Лекция 5 Динамические игры с полной информацией1 Лекция 5 Динамические игры с полной информацией Полная и совершенная информация ( ПиСИ ). Двухходовая игра. Подходы Штакельберга и Гермейера. Общая модель динамической игры с ПиСИ. Обратная индукция и рациональность игроков. Модели, основанные на динамических играх с ПиСИ.
Слайд 2: Полная и совершенная информация ( ПиСИ )2 Полная и совершенная информация ( ПиСИ ). В динамических играх различают полную и совершенную информацию. Информацию считают полной, если все игроки имеют общую информацию о правилах игры и функциях выигрыша. Это понятие относится как к статическим так и динамическим играм. Понятие совершенной информации относится только к динамическим играм, в которых игроки делают ходы последовательно в разные моменты времени
Слайд 3: Полная и совершенная информация ( ПиСИ )3 Полная и совершенная информация ( ПиСИ ). Если все сделанные ходы сразу становятся известны всем игрокам, динамическая игра обладает совершенной информацией.
Слайд 4: Динамические игры с полной информациейДинамической будем называть такую игру, в которой каждый игрок может сделать несколько ходов и по крайней мере один из игроков, делая ход, знает, какой ход сделал другой игрок (возможно, он сам). В этой ситуации он стоит перед свершившимися фактами (уже сделанными ранее и известными ему ходами) и должен учитывать их при выборе своих действий. 4
Слайд 5: Динамические игры с полной информациейОписание динамической игры (с совершенной информацией) в развернутой форме должно включать : множество вершин дерева игры, в том числе одну начальную вершину; для каждой вершины, кроме начальной,— единственную вершину, которая непосредственно ей предшествует; при этом цепь предшествующих вершин, построенная из любой вершины, должна заканчиваться в начальной вершине (что предполагает, в том числе, отсутствие циклов); множество игроков ; для каждой вершины, кроме конечных,— единственного игрока, которому принадлежит ход в данной вершине; для каждой конечной вершины, т. е. такой, которая не предшествует ни одной другой вершине,— вектор выигрышей всех игроков. 5
Слайд 6: Двухходовая игра6 Двухходовая игра Пусть есть всего два игрока N= , и игра разворачивается во времени следующим образом: Ход 1. Игрок 1 выбирает некоторые действия a 1 A 1 Ход 2. Игрок 2, зная совершенный игроком 1 выбор a 1, выбирает некоторое действие a 2 A 2
Слайд 7: Двухходовая играСлайд 8: Двухходовая игра
Слайд 9: Подход Штакельберга9 Подход Штакельберга Подход Штакельберга – доброжелательность партнера : max max [ u 1 (a 1,a 2 ) ] = max [ u 1 (a 1 *, a 2 ) ] a 1 € A 1 a 2 € R 2 (a 1 ) a 2 € R 2 (a 1 * ) В экономических приложениях чаще используется подход Штакельберга, т.к. в случае безразличия лучше пойти навстречу партнеру. ( бесплатная услуга, может потом мне это как-то зачтется )
Слайд 10: Подход Гермейера10 Подход Гермейера. Подход Гермейера - гарантированный результат или осторожность: max min [ u 1 (a 1,a 2 ) ] = min [ u 1 (a 1 *, a 2 ) ] a 1 € A 1 a 2 € R 2 (a 1 ) a 2 € R 2 (a 1 * ) Гермейер исходил из общего принципа гарантированного результата. Если у нас есть информация о доброжелательности партнера в случае равного для него выигрыша, то можем пользоваться подходом Штакельберга. Но если такой информации нет, то только совет к максимальному гарантированному результату
Слайд 11: Двухходовая игра11 Двухходовая игра Стратегия в теории игр – это план действий на всю игру с учетом всей поступающей информации. Игрок 1 выбирает действие, не имея никакой дополнительной информации. Поэтому его множество стратегий S 1 =A 1 совпадает с множеством действий. Слайд 12: Двухходовая игра12 Двухходовая игра Игрок 2 перед выбором своего действия получает информацию о уже совершенном действии игрока 1. Но стратегию он должен выбрать до игры, поэтому его стратегия это отображение S 2 : A 1 →A 2, которая каждому действию a 1 игрока 1 ставит в соответствие некоторое действие s 2 (a 1 ) A 2 Положим u 1 (s 1, s 2 )= u (s, s 2 (s 1 )). Если у каждого игрока было по два возможных действия, то в двухходовой игре у игрока 1 будет две стратегии, а у игрока 2 станет четыре стратегии.
Слайд 13: Двухходовая игра13 Двухходовая игра Игру удобно представить в виде диаграммы, изображающей дерево игры. Решение игры можно найти в предположении, что игроки рациональны и что рациональность и структура игры являются общеизвестными фактами. При этом естественно воспользоваться методом обратной индукции. В соответствии с этим методом игру разматывают с конца.
Не вполне строго, но практически можно считать, что игра является игрой с полной информацией, если:
Если, к тому же, ни в каких аспектах игры (правилах, возможности или очерёдности ходов, определении момента завершения игры или результата) не участвует элемент случайности, такая игра будет ещё и детерминированной. Для любой детерминированной игры с полной информацией, теоретически, можно просчитать всё дерево возможных ходов игроков и определить последовательность ходов, которая гарантированно приведёт по крайней мере одного из них к выигрышу или ничьей, то есть всегда может быть построен алгоритм выигрыша или сведения игры вничью по крайней мере для одной из сторон. СодержаниеПримеры игр с полной информациейК играм с полной информацией относится большинство детерминированных настольных игр (например, шахматы, шашки, го, рэндзю, синци, сёги, крестики-нолики, реверси). Для большинства из них, однако, алгоритм выигрыша или гарантированной ничьей неизвестен: хотя теоретически он существует и может быть найден, на практике дерево вариантов слишком велико, чтобы его можно было построить и проанализировать за приемлемое время. ПримечанияЛитератураСм. такжеСсылкиWikimedia Foundation . 2010 . ПолезноеСмотреть что такое "Игра с полной информацией" в других словарях:Игра Ним — Ним математическая игра, в которой два игрока по очереди берут предметы, разложенные на несколько кучек. За один ход может быть взято любое количество предметов (большее нуля) из одной кучки. Выигрывает игрок, взявший последний предмет. В… … Википедия ИГРА НА ГРАФЕ — обобщение позиционной игры на случай, когда граф позиций не древовидный, а произвольный. Частным случаем И. на г. является игра Ним антагонистическая игра с полной информацией, в к рой для каждой окончательной позиции указано, выигрывает или… … Математическая энциклопедия Игра преследования — антагонистическая дифференциальная игра преследователя (догоняющего) и преследуемого (убегающего) , движения которых описываются системами дифференциальных уравнений: где фазовые векторы, определяющие состояния игроков и … Википедия Игра (задача) — Для улучшения этой статьи желательно?: Викифицировать статью. Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное. У этого термина существуют и другие значения, см. Игра (значения). Игра тип олимпиад … Википедия ИГРА С ИЕРАРХИЧЕСКОЙ СТРУКТУРОЙ — модель конфликтной ситуации при фиксированной последовательности ходов и обмена информацией участников. Основным объектом исследования в теории И. с и. с. является задача об отыскании наибольшего гарантированного результата и оптимальной… … Математическая энциклопедия Ним (игра) — У этого термина существуют и другие значения, см. Ним (значения). Ним математическая игра, в которой два игрока по очереди берут предметы, разложенные на несколько кучек. За один ход может быть взято любое количество предметов (большее… … Википедия ПОЗИЦИОННАЯ ИГРА — игра, имеющая характер развертывающегося в дискретном времени процесса на древовидно упорядоченном множестве (наз. также деревом). Конечной П. и. наз. система где 1) I множество игроков (|I| = n); 2) X конечное дерево, вершины к рого наз.… … Математическая энциклопедия Настольная игра — Настольная игра игра, основанная на манипуляции относительно небольшим набором предметов, которые могут целиком разместиться на столе или в руках играющих. В число настольных игр входят игры со специальным полем, карточные игры, кости,… … Википедия ПРЕСЛЕДОВАНИЯ ИГРА — антагонистическая дифференциальная игра преследователя (догоняющего) Ри преследуемого (убегающего) Е, движения к рых описываются системами дифференциальных уравнений: где х, у фазовые векторы, определяющие состояния игроков Ри Е соответственно; и … Математическая энциклопедия Портал (игра) — Portal Обложка отдельного ПК издания игры Разработчик Valve Corporation Издатель … Википедия Читайте также:
|
