Реферат: Г. К. Честертон Графы (терминология)

10.10.09
Динамические игры
– Я подвожу маркиза к дуэли – радостно пояснил Сайм – после тридцать девятого ответа, гласящего…

– А вы не подумали,– весомо и просто спросил профессор,– что маркиз может все сорок три раза ответить иначе. Тогда, мне кажется, ваши реплики будут несколько натянутыми.

Сайм ударил кулаком по столу, лицо его сияло.

– И верно!– согласился он.– Ах, в голову не пришло! Вы удивительно умны, профессор. Непременно прославитесь!

Г.К. Честертон
Графы (терминология)
Определение. Графом называется пара (V,E), где V – конечное множество, а ES2(V) (здесь S2(V) обозначает множество неупорядоченных пар элементов множества V). Элементы множества V называют вершинами графа, а элементы множества E – его ребрами. Если v – вершина, а e – ребро, и ve, то говорят, что вершина v и ребро e инцидентны. Если v и w – вершины и {v,w}E, то говорят, что вершины v и w – смежные.

Матрицы смежности и инцидентности

Определение. Упорядоченный набор (v1,v2,…,vn) вершин графа называется путем в графе, если вершины vi и vi+1 смежны для любого i=1,…,n–1. Говорят, что путь (v1,v2,…,vn) соединяет вершины v1 и vn. Число n–1 называют длиной пути.

Определение. Говорят, что граф связен, если для любых двух вершин найдется соединяющий их путь.

Определение. Путь (v1,v2,…,vn) называется простым, если вершины v1,v2,…,vn попарно различны.

Определение. Путь (v1,v2,…,vn) называется циклом, если v1=vn.

Определение. Цикл (v1,v2,…,vn) называется простым, если вершины v1,v2,…,vn–1 попарно различны.

Определение. Связный граф, не содержащий простых циклов положительной длины, называется деревом.

^ Лемма. Если в дереве заданы две вершины, то существует единственных простой путь соединяющий их.

Доказательство. Пусть v и w – две вершины дерева. Так как дерево – связный граф, существует соединяющий их путь. Пусть (v=v1,v2,…,vn=w) кратчайший из таких путей. Тогда этот путь – простой. Действительно, если vi=vj для некоторого i и некоторого j>i, то путь (v1,v2,…,vi,vj+1,vj+2,…,vn) по-прежнему соединяет v и w и имеет меньшую длину, что противоречит выбору исходного пути. Существование доказано.

Докажем единственность. Пусть существуют два различных простых пути (v=v1,v2,…,vn=w) и (v=w1,w2,…,wk=w). Так как они различны, найдется вершина wi, не принадлежащая пути (v=v1,v2,…,vn=w). Пусть j – наименьший номер, такой, что все вершины wj,wj+1,…,wi не принадлежат (v=v1,v2,…,vn=w), а l – наибольший номер, такой, что все вершины wi,wi+1,…,wl не принадлежат (v=v1,v2,…,vn=w). Тогда вершины wi–1 и wl+1 принадлежат пути (v=v1,v2,…,vn=w), то есть wj–1=vp и wl+1=vq для некоторых p и q. Если p<q, то путь (vp,wj,…,wl ,vq,vq–1,…,vp) будет простым циклом, а если p>q, то простым циклом будет путь (vp,wj,…,wl ,vq,vq+1,…,vp). В обоих случаях получается противоречие с определением дерева. Лемма доказана.

Определение. Семейство множеств V0,V1,…,Vn называется разбиением множества V, если множества V0,V1,…,Vn попарно не пересекаются, а их объединение равно V.

Определение. Пусть заданы два разбиения V0,V1,…,Vn и W0,W1,…,Wk множества V. Говорят, что разбиение V0,V1,…,Vn является утончением разбиения W0,W1,…,Wk, если каждое из множеств V0,V1,…,Vn содержится ровно в одном из множеств W0,W1,…,Wk.

Определение. Пусть в дереве отмечена некоторая вершина o. Ребра, инцидентные вершине v и не принадлежащие простому пути, соединяющему v с o, называются альтернативами в вершине v. Все вершины дерева с отмеченной вершиной естественным образом разбиваются на классы в соответствии с количеством альтернатив в них. Это разбиение называется альтернативным. Вершины, в которых нет альтернатив, называются финальными.

Определение. Пара (,), где  – отображение, ставящее в соответствие различным вершинам графа различные точки плоскости, а  – отображение, ставящее в соответствие ребру (v1,v2) графа отрезок с концами (v1) и (v2), называется вложением графа в плоскость, если отрезки, соответствующие различным ребрам не имеют общих внутренних точек.

^ Лемма. Любое дерево может быть вложено в плоскость.

Доказательство. Расстоянием между вершинами дерева будем называть длину единственного простого пути, соединяющего их.

Произвольным образом выберем вершину v0 дерева и отнесем ее классу V0. Для отнесем к классу Vt те и только те вершины, которые находятся на расстоянии t. Все множество вершин разобьется на конечное число классов.

Введем на плоскости декартовы координаты и положим (v0)=(0,0).

Произвольным образом перенумеруем вершины v1,…,vl множества V1 и положим (vi)=(i,1).

Каждая вершина множества Vt+1 смежна ровно с одной вершиной множества Vt. Считая, что вершины множества Vt уже перенумерованы, перенумеруем вершины множества Vt+1 так, чтобы выполнялось неравенство i<j всякий раз, когда viVt+1, vjVt+1, {vi,vp}E, {vj,vq}E, vpVt, vqVt и p<q. Положим (vj)=(j,t), если vjVt.

Построенное отображение удовлетворяет условиям леммы. Если viVt+1, vpVt, vjVr+1, vqVr и t<r, то отрезки [(vi),(vp)] и [(vj),(vq)] не пересекаются, так как лежат по разные стороны от прямой y=r, а если t=r, то эти отрезки не пересекаются в силу выбора способа нумерации.
^ Игры в позиционной форме
Определение. Говорят, что задана игра n лиц в позиционной форме, если заданы:

Вложенное в плоскость дерево, называемое деревом игры, с отмеченной вершиной v0 и выделенным ребром, инцидентным этой вершине.

Разбиение множества вершин этого дерева на подмножества V0,V1,…,Vn. Это разбиение называется разбиением по игрокам. Элементы множества V0 называются позициями случая, а элементы множества Vi– личными позициями i-го игрока (i=1,…,n).

Разбиение множества вершин дерева игры, являющееся утончением, как альтернативного разбиения, так и разбиения по игрокам. Элементы этого разбиения называются информационными множествами.

Вероятностное распределение (p1(I),p2(I),…,pm(I)) на множестве {1,…m} для каждого информационного множества I, содержащегося в V0, в вершинах которого имеется m альтернатив.

Упорядоченный набор из n чисел, называющихся выигрышами игроков для каждой финальной вершины.

Определение. Отмеченная вершина дерева игры называется начальной позицией игры. Вершины дерева, не являющиеся ни финальной, ни начальной, называются промежуточными позициями игры. Всякий простой путь, соединяющий начальную позицию игры с какой-нибудь финальной вершиной, называется партией в игре.

Считается, что в начальный момент времени игра находится в начальной позиции. При разыгрывании игры последовательно, шаг за шагом, реализуются шаги одного из двух типов.

Если игра находится в позиции v, принадлежащей множеству V0, то находится реализация j случайной величины, заданной для информационного множества, содержащего вершину v. Находится j-я альтернатива в вершине v, считая против часовой стрелки от единственного ребра, инцидентного вершине v и не являющегося альтернативой (если вершина v – начальная, то отсчет начинается с отмеченного ребра). Далее берется вторая вершина w, инцидентная выбранной альтернативе, и считается, что игра перешла в позицию w.

Если игра находится в позиции v, принадлежащей Vi, то выбор альтернативы делает i-ый игрок. При этом он не знает, в какой именно позиции находится игра, но знает информационное множество, которому эта позиция принадлежит. Следовательно, он знает число альтернатив m в позиции v. Он выбирает натуральное число jm. После этого находится j-я альтернатива в вершине v, считая против часовой стрелки от единственного ребра, инцидентного вершине v и не являющегося альтернативой (если вершина v – начальная, то отсчет начинается с отмеченного ребра). Далее берется вторая вершина w, инцидентная выбранной альтернативе, и считается, что игра перешла в позицию w.

За конечное число таких шагов игра попадет в одну из финальных вершин v, в которой заданы числа (h1(v),h2(v),…,hn(v)). Выигрыш игрока i составит hi(v).
^ Нормальная форма позиционной игры
Пусть задана позиционная игра n лиц. Построим игру в нормальной форме Г следующим образом.

Множество игроков ^ N в этой игре равно {1,2,…,,n}.

Пусть iN и W={I1,I2,…,Ik} – семейство всех информационных множеств позиционной игры, содержащихся в множестве Vi. Будем считать, что Ui есть множество всех функций ui, отображающих W в и удовлетворяющих следующему условию: число ui(I) не превосходит количества альтернатив в любой вершине из множества I.

Стратегия ui задает вероятностное распределение (p1(v),p2(v),…,pm(v)) на множестве всех альтернатив в вершине v по следующему правилу: В позициях случая также задается вероятностное распределение (p1(v),p2(v),…,pm(v)) на множестве альтернатив условием pj(v)=pj(I), если jI.

Для каждой финальной вершины w определен единственный путь (v0,v1,…,vk=w), соединяющий ее с начальной вершиной v0 и числа qt (t=0,…,k–1), равные pj(vt), где j номер альтернативы {vt,vt+1} в вершине vt. Положим . Непосредственно проверяется, что величины P(w) задают вероятностное распределение на множестве финальных вершин. Таким образом, величины hi(w) можно считать случайными, причем распределения этих величин зависят от стратегий всех игроков. Обозначим gi(u1,u2,…,un) математическое ожидание величины hi при условии, что игроки выбрали стратегии u1,u2,…,un соответственно.

Определение. Построенная таким образом игра Г=<N,U1,…,Un,g1,…,gn> называется нормальной формой данной позиционной игры.

Пример: Фан-тан

С помощью этой конструкции на класс позиционных игр переносятся понятия седловой точки, смешанной стратегии, равновесия по Нэшу и т. д.

С помощью позиционных игр удобно моделировать салонные игры (шахматы, шашки, нарды, покер, преферанс и т.д.), а также многие другие процессы, в которых принятие решений разворачивается во времени.

Определение. Позиционная игра n лиц называется игрой с полной информацией, если все ее информационные множества содержат ровно по одному элементу.

В играх с полной информацией информационные множества естественным образом отождествляются с позициями игры. В дальнейшем мы будем этим пользоваться для упрощения обозначений.

Шахматы, шашки и нарды являются играми с полной информацией, а покер и преферанс – нет.

Рассмотрим класс  позиционных игр, различающихся только информационным разбиением. Непосредственно устанавливаются следующие факты.

Лемма. В классе  существует ровно одна игра, в которой каждое информационное множество равно пересечению одного множества альтернативного разбиения и одного множества с разбиения по игрокам исходной игры. Любая игра класса  является квазиинформационным расширением этой игры.

^ Лемма. В классе  существует единственная игра с полной информацией. Она является квазиинформационным расширением любой игры класса .

Лемма. Пусть заданы две игры класса , причем информационное разбиение в первой из них является утончением информационного разбиения во второй. Тогда первая игра является квазиинформационным расширением второй.

Потеря структуры при переходе к нормальной форме
^ Совершенное равновесие в динамических играх
Теорема. Во всякой игре с полной информацией существует ситуация равновесия по Нэшу.

Доказательство. Для каждой вершины v дерева игры определим набор чисел (h1(v),h2(v),…,hn(v)) и для каждой нефинальной личной позиции v i-го игрока определим натуральное число ui(v) следующим образом.

Для всех финальных вершин дерева числа (h1(v),h2(v),…,hn(v)) уже определены. Далее действуем индуктивно.

Из множества вершин, в которых эти числа еще не определены, выбираем любую вершину v, расстояние от которой до начальной вершины максимально. Тогда для всех альтернатив {v,w1},{v,w2},…,{v,wm} числа (h1(wj),h2(wj),…,hn(wj)) уже определены. Если v – это позиция случая, в которой заданы вероятности (p1(v),p2(v),…,pm(v)) выбора альтернатив {v,w1},{v,w2},…,{v,wm}, то положим . Если же v – личная позиция i-го игрока, то найдем j, для которого , положим ui(v)=j и hk(v)=hk(wj) для всех k=1,…,n.

За конечное число таких шагов числа (h1(v),h2(v),…,hn(v)) будут определены для всех вершин графа игры, а функция ui будет определена для всех личных позиций i-го игрока.

Индукцией «с конца» доказывается, что gi(u)=gi(u1,…,un)=hi(v0). Пусть теперь – произвольная стратегия i-го игрока и (v0,v1,…,vk) – порождаемая ситуацией партия игры. Вновь индукцией «с конца» доказывается, что hi(vk)hi(vl). Из неравенств hi(vk)hi(v0) следует, что построенная ситуация u – ситуация равновесия. Теорема доказана.

Для всякой позиционной игры и любой вершины v ее дерева игры можно определить понятие подыгры с начальной вершиной v следующим образом.

Пусть v – произвольная вершина дерева игры и V(v) – это множество всех вершин w, для которых существует такой набор (v=v1,v2,…,vk=w), что для всех j=1,…,k–1 {vk,vk+1} есть альтернатива в вершине vk. Очевидно, V(v0)=V.

Дерево подыгры с вершиной v имеет множество вершин V(v). Его ребрами являются все ребра исходной игры, обе вершины которой принадлежат V(v). Разбиение по игрокам в подыгре есть , а всякое информационное множество в подыгре имеет вид , где ^ I – некоторое информационное множество в исходной игре. Выигрыши игроков (h1(w),h2(w),…,hn(w)) в любой финальной вершине w подыгры и вероятности (p1(w),…,pm(w)) в любой позиции w случая в подыгре те же, что в исходной игре. Начальной позицией подыгры является вершина v, а отмеченным ребром – первая альтернатива в этой вершине, считая против часовой стрелки от ребра, не являющегося альтернативой.

Непосредственно проверяется, что так определенная подыгра сама является позиционной игрой n лиц.

Понятие подыгры особенно естественно для игр с полной информацией.

Если ui – любая стратегия в исходной игре, то ограничение функции ui на множество будет стратегией того же игрока в подыгре.

Определение. Ситуация u в позиционной игре называется ситуацией совершенного равновесия, если для любой вершины v дерева игры ограничения стратегий ui образуют ситуацию равновесия по Нэшу в подыгре с начальной вершиной v.

Из доказательства предыдущей теоремы легко усмотреть, что построенная там ситуация равновесия по Нэшу является ситуацией совершенного равновесия.
^ Равновесие по Нэшу в позиционных играх
Я до того упряма, что и себя, бедняжечку, не пожалею.

Е. Шварц

Пример: существуют несовершенные равновесия по Нэшу.

Полное множество ситуаций равновесия по Нэшу в позиционной игре с полной информацией описывается конструкциями, приведенными ниже. Для простоты рассмотрим игры без случайных ходов (то есть игры, в которых V0=). В этом случае удобна следующая терминология.

Определение. Будем говорить, что в ситуации (u1,u2,…,un) реализуется партия (v0,v1,…,vk), если для любого l=1,…,k–1 пара {vl,vl+1} есть ui(vl)-я альтернатива в позиции vl, считая против часовой стрелки от ребра, инцидентного вершине vl и не являющегося альтернативой в этой вершине1 (здесь i – игрок, личной позицией которого является вершина vj).

Рекуррентным образом определим максимальный гарантированный результат i–го игрока Li(v) в вершине v, его осторожную стратегию и стратегии наказания i-го игрока (для ji). Если v – финальная вершина, положим Li(v)=hi(v). Если v – личная позиция i-го игрока, и для всех альтернатив {v,w1},{v,w2},…,{v,wm} в вершине v значения Li(wl) уже определены, то найдем индекс l, для которого значение Li(wl) максимально и положим Li(v)= Li(wl) и . Если же v – личная позиция j-го (ji) игрока, и для всех альтернатив {v,w1},{v,w2},…,{v,wm} в вершине v значения Li(wl) уже определены, то найдем индекс l, для которого значение Li(wl) минимально и положим Li(v)= Li(wl) и .

Теорема. Партия (v0,v1,…,vk) реализуется в некоторой ситуации равновесия по Нэшу в позиционной игре с полной информацией тогда и только тогда, когда для всех l=1,…,k–1 выполняются неравенства hi(vk)≥Li(vl), где i – это тот игрок, личной позицией которого является вершина vl.

Доказательство. Докажем сначала необходимость. Допустим противное. Пусть u=(u1,u2,…,un) – ситуация равновесия, в которой реализуется партия (v0,v1,…,vk), и найдется личная позиция i-го игрока vl, в которой выполняется неравенство hi(vk)<Li(vl). Рассмотрим стратегию i-го игрока, определенную равенством для всех его личных позиций v. В ситуации реализуется партия (v0,v1,…,vl,wl+1,…,wm). В силу определения стратегии i-ый игрок получит в ней выигрыш hi(wm)≥Li(vl), что больше, чем выигрыш hi(vk) в ситуации u. Получено противоречие с тем, что u – ситуация равновесия, и тем самым необходимость доказана.

Докажем достаточность. Обозначим (vl) – номер альтернативы {vl,vl+1} в вершине vl. Для любой вершины v дерева игры определен единственный путь (w0=v0,w1,…,wm=v) , соединяющий ее с начальной вершиной. Пусть l – наибольший номер, при котором vl{w0,…,wm} и j – тот игрок, для которого вершина vl является личной позицией. Положим q(v)=j (величины q(v) определены для всех позиций игры, не принадлежащих партии (v0,v1,…,vk)). Рассмотрим стратегию ui, определенную равенствами для всех личных позиций v i-го игрока. Так определенная ситуация u=(u1,u2,…,un) будет ситуацией равновесия, в которой реализуется партия (v0,v1,…,vk).

То, что партия (v0,v1,…,vk) действительно реализуется в построенной ситуации, устанавливается по индукции, исходя из определения стратегий u1,u2,…,un.

Покажем, что ситуация u является ситуацией равновесия. Пусть – произвольная стратегия i-го игрока и в ситуации реализуется партия (v0,v1,…,vl,wl+1,…,wm), в которой wl+1vl+1. Тогда для всех vV(vl+1)Vj выполняются равенства и в силу определения стратегий выигрыш hi(wm) i-го игрока в ситуации не может превышать величины Li(vl), которая по условию не превосходит выигрыша hi(vk) того же игрока в ситуации u. Теорема доказана.
^ Многошаговые игры
Лемма. Пусть U1,…,UT,V1,…,VT – компактные множества, а – непрерывная функция. Обозначим множество всех функций . Тогда



Доказательство. Очевидно



В силу результатов предыдущей лекции



Повторяя те же рассуждения, получим нужный результат.

Лемма. Пусть U1,…,UT,V1,…,VT – компактные множества, а – непрерывная функция. Обозначим множество всех функций , – множество всех функций . Тогда



Доказательство аналогично предыдущему

Лемма. Пусть U1,…,UT,V1,…,VT – компактные множества, а – непрерывная функция. Обозначим множество всех функций , и пусть 1,2,…,T – вероятностные меры на V1,V2,…,VT соответственно. Тогда



Доказательство аналогично предыдущему.

Определение. Управляемой динамической системой называется набор , где Xt – множества, называемые фазовыми пространствами, xX0 – начальная фазовая точка, – множества управлений, – функции перехода, – терминальные критерии.

С каждой управляемой динамической системой можно связать несколько игр.

Определение. Игрой на классе программных стратегий, соответствующей управляемой динамической системе называется набор Г=<N,U1,…,Un,g1,…,gn>, в котором N={1,…,n}, , а значения функций вычисляются с помощью рекуррентных соотношений

x0=x,

, t=0,…,T,

gi(u1,…,un)=hi(xT+1), i=1,…,n

(здесь ).

Определение. Игрой на классе позиционных стратегий, соответствующей управляемой динамической системе называется набор *Г=<N,*U1,…,*Un,*g1,…,*gn>, в котором N={1,…,n}, , а значения функций вычисляются с помощью рекуррентных соотношений

x0=x,

, t=0,…,T,

, t=0,…,T,

gi(u1,…,un)=hi(xT+1), i=1,…,n

(здесь ).

Справедлива

Лемма. Игра на классе позиционных стратегий является квазиинформационным расширением игры на классе программных стратегий, соответствующей той же управляемой динамической системе.

Доказательство. Значения проекции определяются рекуррентными соотношениями

x0=x,

, t=0,…,T,

, t=0,…,T.

Вложения ci определяются стандартным образом, после чего аксиомы квазиинформационного расширения проверяются по индукции.

Использовать специфику игр на классе программных стратегий в общем случае не удается. Для игр на классе позиционных стратегий решение многих задач упрощается. Например, рассмотрим антагонистическую игру *Г={1,2},*U1,*U2,*g1, *g2=–*g1> на классе позиционных стратегий, соответствующую динамической управляемой системе . Справедлива

Теорема. Пусть множества Xt и компактны, а функции ft и hi непрерывны. Тогда максимальный гарантированный результат первого игрока может быть вычислен с помощью рекуррентных формул



, t=T,T–1,…,0,

L=L0(x).

Доказательство проводится индукцией «с конца».

Если множества конечны, то соответствующие игры на классах программных и позиционных стратегий легко могут быть представлены как позиционные игры. Наличие этой связи позволяет, например, легко перенести на случай игр двух лиц на классе позиционных стратегий последнюю теорему из предыдущего раздела.

Проклятие размерности
^ Принцип максимума
Пусть в динамической системе



множества есть подмножества каких-то линейных пространств, а функции линейны, то есть , h1(xT+1)=exT+1, где At,Bt,Ct – некоторые матрицы, а e – вектор подходящей размерности.

Определим векторы

pT+1=e,

pt=pt+1At, t=T,T–1,…,0.

Теорема. В игре на классе программных стратегий, соответствующей линейной динамической управляемой системе, существует седловая точка, которая определяется условиями , для всех t=0,…,T.

Доказательство. Непосредственные вычисления показывают, что

,

откуда немедленно следует нужный результат.
^ Модель управления портфелем ГКО
В качестве примера использования идей динамического программирования рассмотрим модель управления портфелем государственных краткосрочных облигаций (ГКО). Эта модель строилась в 1993 г. в интересах коммерческого банка, выступающего рынке государственных облигаций в роли инвестора.

ГКО являются дисконтными облигациями. Это означает, что эмитент, выпуская их в обращение, обязуется в определенный день выкупить их у владельца по заранее оговоренной цене (номиналу). Прибыль инвестора получается за счет разницы цены покупки или продажи. Каждый инвестор может в любой рабочий день между днем первичного размещения облигаций и днем погашения купить или продать облигации по сложившейся на рынке цене. При этом ему придется заплатить комиссионные в размере kx, где k – ставка комиссионных, а x – сумма сделки.

Одновременно на рынке обращаются облигации разных выпусков, отличающиеся сроками погашения. Соответственно встает задача о распределении инвестируемых средств между этими выпусками с тем, чтобы максимизировать прибыль.

Введем обозначения. Пусть инвестируется сумма денег на фиксированный срок от t=0 до t=T. Выпуски ГКО обозначим числами i, изменяющимися от 1 до n. Для упрощения формул как один из вы пусков ГКО будем рассматривать деньги, присвоив им номер 0. Количество облигаций i-го выпуска, находящихся в портфеле инвестора в в конце торговой сессии в день t обозначим .

Сделаем следующие предположения.

Гипотеза 1. За рассматриваемый период список облигаций, находящихся в обращении не изменяется.

Гипотеза 2. На весь период инвестирования задан прогноз изменения цен, так что цена облигаций i-го выпуска в день t считается равной (разумеется, цена денег в любой момент равна 1).

Гипотеза 3. Действия рассматриваемого инвестора не влияют на динамику цен.

Гипотеза 4. Все сделки в данный день производятся по одной и той же цене.

Гипотеза 5. Портфель инвестора достаточно велик, поэтому можно пренебречь эффектами, связанными с целочисленностью количеств облигаций.

Гипотеза 6. Целью управления портфелем является максимизация стоимости портфеля в конечный момент времени .

Гипотеза 7. Единственным ограничением при переформировании портфеля во время торговой сессии является баланс находящихся в распоряжении инвестора средств: .

Правомерность использования этих гипотез удобно будет обсудить несколько позже. А пока приступим к поиску оптимальной стратегии оперирующей стороны.

Начнем с рассмотрения случая, когда величиной комиссионных можно пренебречь (то есть положить k=0). Тогда стандартной индукцией с конца легко устанавливается, что в день t все имеющиеся в распоряжении средства инвестор должен вкладывать в бумаги
i-го выпуска, где число i определяется условием (если таких выпусков несколько, то оптимальным является любое распределение средств между этими выпусками).

Отсюда получаются следующие качественные выводы.

Если прогноз фиксирован, то оптимальная стратегия не зависит от предыстории. (Разумеется, динамика цен в прошлом может использоваться при построении прогноза, но в силу гипотезы 3 на него не влияют действия рассматриваемого инвестора).

Оптимальная стратегия не зависит от срока инвестирования средств.

Для принятия решения в момент времени t нужен прогноз только на следующий день (и не нужен прогноз на более длительный срок).

Для принятия решений можно пользоваться реальными ценами сегодняшней сессии, и использовать прогноз только на завтра.

Все средства можно вкладывать в облигации только одного выпуска, цена которого растет наиболее динамично.

Вернемся к рассмотрению общего случая.

Рекуррентным образом определим величины , t=0,1,…,T, j=0,1,…,n. Положим , для j>0 и .

Стандартной индукцией «с конца» проверяется, что оптимальные действия в момент времени t состоят в следующем. Если, то с облигациями j-го выпуска никаких операций производить не следует. В противном случае все их нужно продать, а вырученные средства вложить в тот выпуск i, для которого .

Несложный анализ найденного решения показывает, что выводы 1 и 4 остаются неизменными.

Вывод 5 несколько изменяется. Если в начальный момент времени портфель был диверсифицирован, то при не очень разбалансированном рынке диверсификация оптимального портфеля будет сохраняться, но все-таки будет тенденция к тому, что все средства, в конце концов, сосредоточатся в облигациях одного выпуска.

Выводы 2 и 3 изменятся следующим образом. Пусть номер i удовлетворяет условию и пусть найдется такой момент времени  (t<<T), что . Тогда действия в момент времени t зависят только от прогноза до момента времени  и не зависят от срока инвестирования T, если только T>.

Эти выводы особенно важны, поскольку, с одной стороны, наличие очень «длинного» прогноза является слишком сильным предположением. А с другой стороны, во многих интересных случаях срок инвестиций заранее не известен, хотя и не очень короток. По реальным наблюдениям срок –t обычно составлял порядка двух недель. Это почти полностью оправдывает принятие гипотезы 6, и позволяет значительно ослабить гипотезу 2.

Обсудим остальные предположения.

От гипотезы 1 можно избавиться чисто формальным трюком. Будем считать, что все облигации, которые находились в обращении в течение рассматриваемого периода, находились в обращении на протяжении всего этого периода. Но цена облигаций после погашения не меняется и равна цене в день погашения. А цена облигаций до момента их фактического выпуска в обращения постоянна и равна цене в день их выпуска. Тогда вложения в такие «фиктивные» бумаги столь же хороши, как вложения в «наличные», что позволяет в случае нужды скорректировать найденное оптимальное решение, не ухудшив его.

Рассматриваемый инвестор контролировал менее одного процента объема рынка, поэтому гипотеза 3 весьма правдоподобна. Тем более, что вывод 4 позволяет рассматривать только влияние сегодняшних действий инвестора на цены завтра и в последующие дни. Заметить такое влияние в реальности ни разу не удалось.

К гипотезе 4 можно сформулировать два возражения. Во-первых, цена покупки может отличаться от цены продажи. На практике в момент написания модели характерные спрэды были невелики. Кроме того, имея прогноз величины спрэда2 его можно учесть, не меняя структуры модели, а просто увеличив на соответствующую величину размер комиссионных k. Во-вторых, цены могут меняться в течение торговой сессии. Это возражение отчасти снимается выводом 4, а отчасти тем, что в нормальной ситуации колебания цен в течение одного дня бывали невелики по сравнению с доступной точностью построения прогноза.

Количество облигаций в портфеле рассматриваемого инвестора измерялось тысячами (подчас многими), поэтому гипотеза 5 вполне приемлема.

Гипотеза 7 оправдывается существующими правилами обращения облигаций.

Таким образом, наиболее существенным является ослабленный вариант гипотезы 2. Это предположение действительно важно. В частности, от него зависит важный вывод 5.

Построенная модель, с одной стороны, показывает целесообразность декомпозиции задачи управления портфелем на две части: задачу построения прогноза и задачу принятия оперативных решений. А с другой стороны демонстрирует тот факт, что эти задачи не являются независимыми, и требования к построенному прогнозу определяются процедурой принятия решений.

Чтобы понять это, рассмотрим модельный пример. Пусть имеются облигации всего двух выпусков, текущие цены которых равны 70 и 80. Срок инвестирования составляет один день, и имеется два прогноза цен на завтра. Согласно первому цены будут раны 80 и 90 соответственно, а согласно второму – 50 и 70. Пусть фактические завтрашние цены оказались равны 77 и 90. Какой из прогнозов лучше? Как ни странно, второй. Согласно ему средства следует инвестировать в облигации второго выпуска, что обеспечивает доходность 13,7%. А если пользоваться первым прогнозом, то следует инвестировать средства в облигации первого выпуска, что в реальности принесет всего 10% прибыли.

В выяснении подобных качественных особенностей рассматриваемой проблемы и заключалась основная цель построения данной, сугубо предварительной модели.

Модель дележа у Льюса–Райфы стр. 465

Задача о фальшивых монетах как позиционная игра
Задачи
Приведите пример игры с полной информацией, в которой выигрыши в ситуации совершенного равновесия доминируются выигрышами в какой-то другой ситуации равновесия по Нэшу.

Чем отличаются позиционные формы матричных игр и ?

***

(Баше де Мезириак, 1612 г.) Двое называют поочередно целые числа от 1 до 10 и выигрывает тот, кто первый доведет до 100 сумму чисел, названных обоими игроками. Кто выигрывает при правильной игре? Найдите оптимальную стратегию.

Имеется 19 спичек. Двое играющих по очереди берут из них 1, 2 или три спички. Проигравшим считается тот, кто возьмет последнюю спичку. Доказать, что берущий спичку первым всегда может выиграть.

Каждой вершине куба поставлено в соответствие некоторое неотрицательное действительное число, причем сумма всех этих чисел равна 1. Первый выбирает любую грань куба, второй выбирает другую грань и, наконец, первый выбирает третью грань куба. При этом выбирать грани, параллельные уже выбранным нельзя. Докажите, что первый игрок может играть так, чтобы число, соответствующее общей вершине трех выбранных граней, не превосходило 1/6.

Коля и Петя делят 2n+1 орехов (n>2), причем каждый хочет получить возможно больше. Предлагается три способа дележа (каждый проходит в три этапа).

1-й этап: Петя делит все орехи на две части, в каждой не меньше двух орехов.

2-й этап: Коля делит каждую часть снова на две, в каждой не меньше одного ореха.

(1-й и 2-й этапы общие для всех трех способов)

3-й этап: при первом способе Коля берет себе большую и меньшую части; при втором способе Коля берет обе средние части; при третьем способе Коля берет либо большую и меньшую части, либо обе средние части, но за право выбора отдает Пете один орех.

Определите, какой способ самый выгодный для Коли, и какой наименее выгоден для него.

Имеется набор G из n шаров. Два игрока A и B играют в следующую игру: в первом раунде A делит G на два непустых набора, а B выбирает один из них. Во втором раунде A делит выбранный набор еще на два, а B выбирает один из них и т. д. Игра заканчивается, когда в выбранном игроком B наборе только один шар, при этом игрок A выигрывает, если число раундов нечетно, и проигрывает, если это число четно. Определите, кто выигрывает при правильной игре и укажите выигрышную стратегию, если

А) n=1994; Б) n – произвольное натуральное число.

Двое играют в такую игру. Один называет цифру, а другой выставляет ее по своему усмотрению вместо одной из звездочек в следующей разности: ****–****. Затем первый называет еще одну цифру и так далее 8 раз, пока все звездочки не заменятся на цифры. Тот, кто называет цифры, стремится к тому, чтобы разность получилась как можно больше, а второй – чтобы она стала как можно меньше. Докажите, что

а) второй может расставлять цифры так, чтобы получившаяся при этом разность стала бы не больше 4000 независимо от того, какие цифры назвал первый;

б) первый может называть цифры так, чтобы разность стала не меньше 4000независимо от того, куда расставляет эти цифры второй.

Даны две кучки спичек. Вначале в одной кучке m спичек, в другой – n спичек, m>n. Двое по очереди берут из кучки спички. За один ход игрок берет из одной кучки любое (отличное от нуля) число спичек, кратное числу спичек в другой кучке. Выигрывает игрок, взявший последнюю спичку в одной из кучек.

а) Докажите, что если m>2n, то игрок делающий первый ход может обеспечить себе выигрыш.

б) при каких  верно следующее утверждение: если m>n, то игрок, делающий первый ход, может обеспечить себе выигрыш?

Дана система уравнений Два игрока по очереди ставят вместо многоточий числа. Начинающий выигрывает, если получившаяся система не имеет решений, и проигрывает в противном случае. Кто выигрывает при правильной игре обеих сторон?

*** Фикция ***

На окружности дано 25 точек. Двое по очереди проводят хорды с концами в этих точках так, чтобы хорды не пересекались. Проигрывает тот, кто не может провести хорду. Кто выигрывает при правильной игре – начинающий или его партнер?

На окружности дано 20 точек. Двое по очереди проводят хорды с концами в этих точках так, чтобы хорды не пересекались. Проигрывает тот, кто не может провести хорду. Кто выигрывает при правильной игре – начинающий или его партнер?

*** Симметрия ***

Двое по очереди закрашивают клетки таблицы 88. Одним ходом разрешается закрасить одну или несколько клеток, расположенных либо в одной строке, либо в одном столбце. Клетки, закрашенные ранее, закрашивать вторично запрещается. Проигравшим считается тот, кто не может сделать очередной ход. Кто выигрывает при правильной игре: начинающий или его партнер.

На доске написано . Двое играющих по очереди записывают вместо многоточий произвольные числа. Начинающий выигрывает, если получившееся уравнение не имеет корней, и проигрывает в противном случае. Кто, начинающий или его партнер, имеет в этой игре выигрышную стратегию.

На столе лежат карточки, на которых написаны по разу все делители числа 2000, причем на каждой карточке написан ровно один делитель. Два игрока по очереди берут себе по одной карточке. Игра производится до тех пор, пока у одного из игроков число на одной из его выбранных карточек не будет делиться на число на другой из его карточек – этот игрок считается проигравшим. Кто из игроков – начинающий или его партнер – выигрывает при правильной игре обеих сторон.

Полем игры служит прямоугольный лист бумаги, разграфленный на квадратные клетки так, что имеется 10 клеток в каждой строке и 11 клеток в каждом столбце. Двое играющих делают ходы по очереди. Ход заключается в зачеркивании прямоугольника, состоящего из двух клеток. Игра идет до тех пор, пока можно делать ход. Выигравшим считается тот, кто сделает последний ход. Доказать, что сделавший первый ход всегда может выиграть.

*** Домино ***

Двое играют на шахматной доске в следующую игру: первый ставит на доску короля и делает ход по обычным шахматным правилам, то есть передвигает короля на соседнюю клетку по вертикали, или по горизонтали, или по диагонали. После этого игроки поочередно делают ходы королем, причем не разрешается ставить короля на клетки, где он уже побывал. Проигрывает тот, кто не может сделать очередной ход. Кто выигрывает в этой игре?

Двое играющих по очереди красят клетки квадрата 88. За один ход игрок красит своим цветом одну клетку. Перекрашивать клетки нельзя. Первый стремится закрасить своим цветом квадрат 22. Может ли второй игрок помешать первому независимо от его игры?

*** Запас ***

Дана полоска клетчатой бумаги длиной в 100 клеток. Двое играющих по очереди красят клетки в черный цвет, причем первый всегда красит 4 подряд идущие клетки, а второй – т