Разработанный МФТИ курс отличается тем, что все основные конструкции и принципы теории вводятся непосредственно на основе разбираемых "с нуля" конкретных этюдов. Каждый этюд начинается с понятной непрофессионалу проблемы. В одних случаях это просто "детская игра", в других - формализованное жизненное наблюдение, в третьих - обобщённая социальная закономерность. Сюжет затем разворачивается, исходя из логики содержащегося в нём конфликта, и сам порождает тот или иной принцип разрешения конфликта, который окончательно строго формализуется в виде решения игры. Этюдов всего рассмотрено чуть более десяти, и они в совокупности покрывают основные формальные конструкции базовой теории игр. В нескольких отступлениях приведены формулировки теорем существования игровых решений с набросками доказательств.
Динамическая игра с совершенной информацией: общее описание
Loading...
来自 Moscow Institute of Physics and Technology 的课程
Теория игр
32 个评分
从本节课中
Динамическая теория игр
Мы переходим к изучению динамической теории игр, то есть игр, в которых игра длится несколько раундов.
与讲师见面
Дмитрий Ильинскийпреподаватель
кафедра дискретной математики МФТИ
Итак, давайте дадим определение динамической игры с совершенной
информацией.
[БЕЗ_ЗВУКА]
[БЕЗ_ЗВУКА] Вообще,
динамическая игра, если мы хотим охватить одним и тем же
определением очень-очень много разных игр из различных этюдов и сюжетов,
то оказывается, что концепция динамической игры — это не очень простой объект.
То есть надо сразу же смириться с тем,
что определение содержит нагромождение каких-то, так сказать, понятий новых.
И я поэтому решил разделить его на две части.
Вначале мы будем говорить только об играх с совершенной информацией.
Сейчас я чуть дальше скажу, что это означает.
Фактически это означает, что есть строгая последовательность ходов,
и игроки никогда не ходят одновременно.
И потом уже самую общую игру динамическую мы
определим некоторым универсальным способом как игру с некоторой
дополнительной нагрузкой на нее, которая называется информационное множество.
И вот это вот последнее определение, которое мы дадим в дальнейшем,
оно будет охватывать буквально все примеры, которые у нас будут.
А пока давайте я расскажу,
что такое игра, в которой ходы делаются строго последовательно,
и вся информация на каждом этапе вскрывается о том, что сделано до этого.
Итак, это прежде всего дерево Г — дерево игры.
Ну а также список игроков.
Список игроков входит в определение игры вообще во всех ветвях теории игр,
в том числе даже в кооперативной, в которой схожесть со всем предыдущим
только в том, что есть тоже список игроков, все остальное совершенно иное.
Значит, есть дерево игры, дерево с отмеченной стартовой вершиной.
[БЕЗ_ЗВУКА] Давайте
ее вот так звездочкой обозначим.
Звездочка — это стартовая вершина дерева.
Если я в дереве некоторую вершину называю стартовой,
то тогда уже этим самым я говорю о том,
что у меня есть направление движения по дереву, потому что про
каждое ребро можно сказать, какая из его вершин ближе к вот этой стартовой.
Так как циклов нет, то это всегда однозначно определено.
Поэтому дерево со стартовой вершиной можно изобразить, так сказать,
снизу вверх: из стартовой вершины выходит некоторое количество ребер,
значит, дальше из следующих вершин тоже выходят какие-то ребра.
Это совершенно произвольная конструкция,
то есть произвольное дерево с отмеченной вершиной можно таким образом записать.
Дерево конечное.
Бесконечные игры у нас будут, но дальше.
Пока строго конечные.
Значит, дерево конечное, но и соответственно у нас наступит момент
всегда, если мы будем идти от звездочки в разные стороны,
то куда бы мы ни шли, в конце концов наступит момент, когда дальше идти нельзя.
Все вершины,
из которых идти нельзя, то есть такие,
что они не находятся ни на каком пути между звездочной вершиной и
какой-либо другой, они называются терминальными.
Давайте введем некоторое обозначение.
Значит, X — множество вершин, [БЕЗ_ЗВУКА]
множество ребер
будет обозначаться за A, и кроме того,
для любой маленькой вершинки x A(x) — это множество ребер,
идущих дальше от вершины «звездочка».
То есть из каждой вершины x одно и ровно одно
ребро ведет в сторону обратно к звездочке, ну то есть между
любыми двумя вершинами дерева существует ровно один путь кратчайший.
И если этот путь из вершины x, — вот этот путь начинается с вот этого
ребра «наверх», а все остальные ребра идут «вниз».
Вот это множество ребер, идущих «вниз», мы обозначим за A(x).
A(x) — ребра, идущие «вниз».
И в терминах теории игр понятно, что это означает,
что если какой-то игрок ходит в этой точке,
то вот эти ребра — это множество его возможных ходов.
В частности, в звездочке тоже кто-то ходит.
И вообще имеется, должно быть задано
отображение из множества всех вершин,
кроме терминальных, в множество игроков.
То есть нужно сказать в каждой вершине, кто ходит.
В терминальных вершинах ходов нет.
Там игра заканчивается и говорится, какой исход игры.
Или, например, просто список выигрышей, можно просто задать здесь список
выигрышей, то есть какой-то вектор из R в степени n.
Ну давайте все это формализуем.
Итак, что такое терминальные вершины?
T — это множество таких x,
что A(x) — пустое множество,
то есть из которых путь есть только «наверх».
Значит, чтобы задать игру,
нужно для каждой терминальной вершины задать выигрыши игроков.
Соответственно, мы задаем некоторое отображение u из T в R в степени N,
которое каждой вершине t терминальной задает список выигрышей в ней.
Значит, это числа u1 в степени t и так далее,
un в степени t, где N — это множество игроков,
которых можно просто переименовать: {1, 2, ..., n}.
То есть задано, кто сколько выигрывает для каждой терминальной вершины.
Но при этом каждая нетерминальная вершина должна быть помечена одним из игроков.
Это означает, что существует некоторое отображение,
давайте его назовем вот такой вот ι,
[БЕЗ_ЗВУКА] из
множества нетерминальных вершин, в частности «звездочка» здесь включается,
в N.
И в этом случае,
в этом случае Xi,
давайте назовем за Xi — это прообраз игрока i,
то есть множество вершин, которое им контролируются, этим игроком.
То есть Xi — это множество, это ι в –1 степени от i,
то есть множество вершин x,
где ходит, в x ходит
игрок i.
Ну, собственно говоря, на этом описание игры заканчивается.
