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

Вид материала

Документы

Содержание Многошаговые игры

Подобный материал:

• Терминология в пауэрлифтинге, 280.99kb.
• Рабочая программа дисциплины Графы и алгоритмы Направление подготовки, 133.78kb.
• Планирование, управление, контроль 76 Терминология по охране объектов нефтепроводного, 1117.18kb.
• «Современная терминология заготовки и переливания крови», 28.84kb.
• Л. А. Чернышова отраслевая терминология в свете антропоцентрической парадигмы, 2698.99kb.
• Артур Конан Дойл. Как Копли Бэнкс прикончил капитана Шарки. Киплинг Р. Д. Дьявол, 33.4kb.
• Г. К. Честертон По-настояшему боишься только того, чего не по­нимаешь, 5959.79kb.
• Г. К. Честертон, 1996.42kb.
• Г. К. Честертон святой франциск ассизский, 1309.11kb.
• Вопросы к теоретическому зачету группы с (sis ­­– 2003), 29.23kb.

^

Многошаговые игры

Лемма. Пусть U₁,…,U_T,V₁,…,V_T – компактные множества, а – непрерывная функция. Обозначим множество всех функций . Тогда



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



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



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

Лемма. Пусть U₁,…,U_T,V₁,…,V_T – компактные множества, а – непрерывная функция. Обозначим множество всех функций , – множество всех функций . Тогда



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

Лемма. Пусть U₁,…,U_T,V₁,…,V_T – компактные множества, а – непрерывная функция. Обозначим множество всех функций , и пусть ₁,₂,…,_T – вероятностные меры на V₁,V₂,…,V_T соответственно. Тогда



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

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

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

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

x₀=x,

, t=0,…,T,

gⁱ(u¹,…,uⁿ)=hⁱ(x_T+1), i=1,…,n

(здесь ).

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

x₀=x,

, t=0,…,T,

, t=0,…,T,

gⁱ(u¹,…,uⁿ)=hⁱ(x_T+1), i=1,…,n

(здесь ).

Справедлива

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

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

x₀=x,

, t=0,…,T,

, t=0,…,T.

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

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

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



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

L=L₀(x).

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

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

• Проклятие размерности