Игры априорного и статистического оценивания тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

п п %

МОСКОВСКИ!! ОРДЕНА ЛЕНИНА, ОРДЕНА ОКТЯБРЬСКОЙ РЕВОЛЮЦИИ И ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. Л1. В. ЛОМОНОСОВА

Факультет вычислительной математики и кибернетики

На правах рукописи

ЛУЦЕНКО

Михаил Михайлович

ИГРЫ АПРИОРНОГО И СТАТИСТИЧЕСКОГО ОЦЕНИВАНИЯ

01.01.09.— Математическая кибернетика

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

МОСКВА 109)

Работа выполнена в Ленинградском институте инженеров железнодорожного транспорта.

Официальные оппоненты: доктор физ.-мат. наук, профессор Н. Н. ВОРОБЬЕВ;

доктор физ.-мат. наук, профессор Л. А. ПЕТРОСЯН;

доктор физ.-мат. наук, профессор А.,. Г. СУХАРЕВ.

Ведущее предприятие — Институт проблем кибернетики АН СССР.

Защита диссертации состоится « . »«^р^^/г'у^ 199 «ч г.

и о__^ '

. . часов на заседании специализированного совета МГУ Д.053.05.38 по математике по адресу: 119899, ГСП, Москва В-234, Ленинские горы, МГУ, факультет вычислительной математики и кибернетики, аудитория 685.

С диссертацией можно ознакомиться в библиотеке факультета вычислительной математики и кибернетики МГУ.

Ученый секретарь специализированного совета, профессор

Н. П. ТРИФОНОВ

- ъ-

Лгстуальность темы исследования. Для целого ряда приложений представляет интерес задача оценки переменной величины с той или ино!( степенью точности.

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

г*

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

Исследованием бесконечных антагонистических игр, к когорг.т сводятся задачи априорного оценивания, занимались Н.Дресср, Н.Н.Воробьев, С.Карлин, Г.Дюбин и др. Основа теории статистических игр были заложены А.Вальдом в 50-х годах и развиты в работах , Елекуоллз и Гиргика, Закса и др. Однако, до сих пор бесконечнее антагонистические игры, поддающиеся резенига, составляют черезвы-чайно узкие и разрозненные классы игр. На важность дальпсГ.пего расширения и укнокения числа таких классов указывалось в работах Г.У.Куна, А.У.Танкера, С.Карлина, Н.Н.Воробьева. За использование общего теоретико игрового подхода к статистическим задачам выступали А.Вальд, А.А.Боровков, З..Леман.

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

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

тическои виде.

Научная новизна.

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

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

3. Показано, что более часто встречающиеся игры с разрывными функциями выигрыша решаются проще, чем классические игры.

4. Развиты классические теоретико-игровые методы и перенесены методы классической математики ( преобразование Лапласа, уравнение восстановления ) на игры с кусочно непрерывными фикциями выигрыша.

5. Создан новый аппарат для исследования широкого класса игр близкий к уравнениям Беллмана.

6. Прстроено решение большого числа игр на единичном квадрате в аналитическом виде С создано некоторое исчисление игр ).

7. Построена минимаксная интервальная оценка параметра биномиального закона.

8. Указана связь между играми с выбором момента времени и случайными блужданиями на единичном отрезке.

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

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

Построены минимаксные интервальные оценки параметра семейства дискретных случайных величину при малом объеме выборки.

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

Апробация работы. Результаты работы докладывались на Ш Всесоюзной конференции по теории игр (1974г.), Ш Всесоюзной конференции по исследованию операций (1978г.), на Ленинградских симпозиумах по теории игр, на конференциях в г.Илменау (1988г.), Ыйзенах (1989г.) ГДР, на Всесоюзном совещании "Пути повышения качества прогнозов" (1990г.), а также на различных семинарах городов Москвы и Ленинграда.

Объем и структура работы. Работа состоит из введения, 7 глав, занимающих 230 стр. м/т. Библиография содержит 85 наименований работ отечественных и зарубежных авторов.

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

игрой оценивания ) с функцией выигрыша

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

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

Формально такая ситуация описывается бесконечной антагонистической игрой априорного оценивания Г~<Х,к> , в которой X - множество чистых стратегий игроков ( Х^- ). а -

функция выигрыша.

Несмотря на успехи достигнутые при решении антагонистических игр ебщих методов решения их не существует. В последние годы практически прекратились работы, в которых бы приводились решения новых классов антагонистических игр. А в своей работе Е.Б. Яновская пишет о том, что общую теорию решения бесконечных антагонистических игр в явном виде ( в отличие от приближенных методов ) современными математическими методами вообще построить

невозмонно.

ГЛЛ. ИГШ ОЦЕНИВАНИЯ. ПРЖЕШ И МСШИЯ

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

Еольиое внимание уделяется анализу методов решения антагонистических игр. В частности, перечисляются те классы игр, решения которых были получены в ЬО-х - 60-;< годах сотрудниками корпорации Е.АЫЪи др. Описываются классы игр, резание которых получено новыми, недавно разработанными методами. Будет геречлелен целый ряд содержательных примеров конфликтных ситуаций, приводящих к играм априорного оценивания, а такке некторые математические задачи, связанные с играми оценивания. Здесь такие анализируются трудности, которые возникают при решении статистических игр оценивания в зависимости от вида (функции потерь.

§ 1„ Основные определения

В отом параграфе даны определения: антагонистической игры, седловой точки, смешанного расширения, выравнивающей стратегии, игр априорного и статистического оценивания,

5 2- Классические неводы решения антагонистических игр

Начиная с 50-х годов в работах сотрудников корпорации начала разрабатываться обциП подход к решению бесконечных антагонистических игр. Порядок проводимых ими исследований повторял историк) развития математического анализа или дифференциальных уравнений: от исследования игр с полиномиальными н рацноналыщып ядрами к играм с аналитическими функция;,;» выигрша, а далее: ослабление ограничений на непрерывность и попытки построения аппроксимирующих моделей для игр но единичном квадрате. В разках этого, теперь уке классического подхода, обнаружилось, что наличие разрыва у фикции выигрыша или ее производной монет значительно помочь при построении решения игры на единичном квадрате.

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

вескому порядку их решения.

§ 3. Обобщенные методы решения антагонистических игр

В 50-х - 50-х годах в работах М.Дрешера, Н.Н.Воробьева появился другой подход к построению решения игр на единичном квадрате. Этот подход был нацелен непосредственно на игры с разрывными функциями выигрыша. В частности, удалось построить достаточно полную теорию игр, функция выигрыша которых принимает два значения. Однако, перспективность этого подхода оценена лишь недавно, когда его удалось объединить с такими разработанными аппаратами: теория обобщенных функций с ее техникой дифференцирования и интегрирования, сверточной алгеброй, преобразованием Лапласа и др.

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

§ 4. Статистические игры оценивания

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

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

В настоящем параграфе описывается связь меяду некоторыми статистическими задачами и играми оценивания.

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

Ситуации, в которых один из участников стремится "наиболее точно" угадать состояние или действие противника хорошо описываются играми априорного оценивания. Конкретный вид игры зависит :;ак от множества допустимых состояний так и от того, что пониыа-

етоя под "наиболее тошойи оценкой» Наиболее простыми оказываются игры, в которых потери пергогс участника растут пропорционально расстоянию между его оценкой и истинным состоянием второго ¡■грока ( игры угадывания с выпукльыи функциями выигрыша см. H.H. Воробьев ). Однако, в конкретных конфликтных ситуациях "точность оценки" понимается значительно более слонннм образом.

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

5 6. Математические задачи евязаннве с играми оценивания

Цель настоящего параграфа продемонстрировать тот недостаточно осознанный факт, что теорию игр можнс использовать как средство исследования в дртугкх разделах математики к возникших совсем по другому поводу. В своей книге Т.Партхасаратхи и Т.Рагхаван показывают как хорошо известные теоретико-игроЕые результаты дают возможность получать почти тривиально доказательства некоторых классических теорем. В настоящем параграфе мы покажем как методы решения игр оценивания позволяют решать другие математические задачи: определение времени жизни точки случайно блуждающей на отрезке, вычисление абсолютной i-знтро-пии, некоторые задачи динамического программирования.

ГЛ.2. ИГРУ АПРИОРНОГО ОЦЕНИВАНИЯ С КУСОЧНОНЕПРЕШВШИ ФУНКЦИЯМИ ВЫИРРША

Настоящая глава посвящена исследованию игр априорного оценива» яия вида Г (,1с) = < Г0»1!, ^ > . Будет описана алгебра обоб-

щенных функций Ct( О ), порожденная ступенькой Хевисайда 6 и обобщенной (&нкциеГ Дирака . На языке этой алгебры мы будем строить функции выигрнпа, обращая особое внимание на «функции

г. . где - обобщенная функция с носи-

телем, содержащемся в множестве [-£.,£"} . Работая с алгеброй ÖL , нам придется использовать алгебраические свойства этой

алгебры. Кроме того мы исследуем алгебру функцийизоморфную алгебре 01 и полученную из алгебры 01 с помощью преобразования Лапласа.

На язьгке обобщенны?: функций мы запишем условие оптимальности в игре Г ( Ь. ) в виде

Л -г

причем оптимальные стратегии в игре 1 будут И где к" (.-И - кСг^.

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

Наиболее подробно будут исследованы а) игра "трапеция" с функцией выигрыша

ь 10.1- о* и* - о

и«10-г 2 Ц

1=1 1

= £(21-/1-0

/ ч

/ :

-ь-ь

г~ •-к

1—' .

Игры априорного оценивания с кусочнонепрернвными функциям выигрыша неоднократно исследовались ( см. М.Дрешер, Н.Н.Воробьев, Г.Н.Двбин, М.И.Маслова ). Алгебра ОI для игр на единичном квадрате впервые была определена автором в работах ^14,15]-Там же можно найти основные результаты настоящей главы. В частности, решение игры "трапеция" и "пирамида".

§ I. Сверточная алгебра обобщенных функций Обозначим ступеньку Хевксайда через а

> -Ь > о <

[-с. ч то£[0,11 _5

а через Ьа обобщенную функцию Дирака с носителем в точке ае Я, Обозначим через &( 6 , Ъ ) наименьшую алгебру обобщенных функций замкнутую относительно операций сложения, умножения на число, свертки. Эта алгебра очень обширна и содержит кусочно

-1Q-

поликомкальные функции. Обозначим через

л.

пл

-5»

и

ЬА J_^t

вероятностную меру с носителем в точках Q; = (2i-t-

При исследовании свойств алгебры О! широко используется преобразование Лапласа.

§ 2. Абстрактно алгебраические методы решения игр априорного оценивания

Рассмотрим игру априорного оценивания Г (W ), где функция К определена на отрезке [-1,1]. Решение игры Г (М будем искать в смешанных стратегиях. При решении игр мы будем широко использовать язык теории обобщенных функций.

Теорема I. Пусть в игре априорного оценивания file ) оптимальные стратегии игроков /•*",-?* удовлетворяют условиям

Lrtf Sup

(2)

где £'0, а - плотность произвольной вероятностной меры, ъирр е. , тогда /**", У будут оптимальными страте-

гиями игроков в игре Г ( к * .

Теорема имеет довольно общий характер, а именно: по решению каждой игры Г ( и ) удовлетворяющему условию, строится решение целого класса игр. Однако, игр V (к ), решение которых удовлетворяет условию ( 2 ) известно немного.

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

Определении: Будем называть квадратную патрицуА теплицевой, если ее элемена-ы имепт вид , т.е.

А-«Ч> -

а0 a.j ... > а, аь ом...а.и+г йг ал а„ •••а.и+?

Таким образом, теплицгвая матрица А задается набором из

-11 -

2n-I числа a.att,a.nt.3,...,Oc>a,......

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

Om , -t е. ] атл > 2(mi-V>Ä [

,, I т = -ni-i,-n+2y ■> л-1

Для любого вектора X=(

X, , •.., ) определим

yf = i *i ■

Если X -смешанная стратегия, то - вероятностная мера. Теорема. Пусть А- теплицевая матрица порядка п. , а Д£ -произвольная вероятностная мера с носителем ьмррА^е. [-s.e^ Значение игры Г С k ), к = * \ ' г,ае величи~

на сдвига определяется из условий

Г€ ]г, > с е [о, (3)

равно значению матричной игры Г (А ). Оптимальные стратегии У в игре Г С к ) находятся по оптимальным стратегиям "X ,Т игроков I и 2 в матричной игре Г (А ) по формулам

Замечания: I) Условия ( 3 ) совместны при А^ J ' 2(n-0J

§ 3. Игра<трапеция"

В этом параграфе приводится решение игры с функцией выигрыша типаtтрапеция!

Теорема. Значение игры Г ( к ) с функцией выигрыша типа "трапеция" k = * ip& , 0 <■ £ £ & монет быть найдено

Х) У2па при .gfcj,

а оптимальные выравнивающие стратегии!* игроков I и 2 соотрзт-ственно имеют вид •>*= * Sya

оптимальная стратегия игрока I будет

Я (11 + 1}

оптимальная стратегия игрока 2 оудет

1/ \

6 .,. ~р~ /;.„ % пои /¿п. /

, П-1 4-1 _ \

5 Решение игры с функцией выигрша ткпй.шрмщш'.

В &тоы параграфе будем строить решения игр l' (к ) с функцией льшгрыша Sc ПРИ различных ограничениях на вид обобщен-

ной функции . Нам будет полезна следующая теорема.

Теорема I: Пусть обобщенная функция, ФCö") » •¿«pf -i , 1,тогда значение игры Г С k >,

при й fe ] ^ [ имеет вид

а оптимальные стратегии обоих игроков могут быть найдены по фор* бГп.а * "Уг • 5 )

Доказательство ачеой теореш несложно и является незначительным видоизменение»; доказательства леммы 1 работы [34]. При доказательстве существенно используется то, что вероятностная мера ^».й * ^Vä ¿шляется выравнивающей стратегией в игре Г ( ). Заметки» етс при V./.. О настоящая георема является непосредственным следсусиеы теоремы 2-работы [ 14 ].

Таким образом, в плоссости мнокество точекЪ , для которых решение игра Г (к ), к = ц>4 «■ находится по формулам ■ ч , 5" ) имеет вид слояюй зубчато!! области.

Значительно более сложно получить решение игры Г С -X« ) и «ех случаях, когда значения параметров i t й не входят в область Ъ . В этих случаях вид решения существенно зависит не толь-го от величины носителя, но и от вида обобщенной функции А^. В ■таботе \Д4*] исследовалась игра Г ( ) „ ;.ö„ Дс=

Было получено лолеиио зтоУ игщ пои ьгву. •«•. , л .» О

Ра смотрим теперь игру Г ( ) « кусочно-постоянной фу iiKri.ii-'

ВНИРрЬШа V. = ЧЧЛ с'т,и , СЛучпМ >,г - О'.,,,.....

I дает решение это« игры пр>:

{у/- 1)7 ^ . 0<"'Н ' ' •> .'

Игру Г С к ) с ¡¿ункциеЙ швгрдап - « %г и<->. < уь

дем называть игрой с функцией даигшгяа типа ''"яишиндаЧ уяк ..м. при А > (»« график функции к напоминает пирамид1/- (Ьмс.чг

что при Л- к у (к функция Ьй^б,,,--'^.. '-о.

т.е. имеет вид "пирамиды", но с меньшим числом ступенек,, Г> м-.--НОСТИ, при Л = ^ функция к = # <5^ - V - IIOH.IT.

пороговая.

Теорема 2: Значения игра Г { к ), * = Чл* ^»»с "!/Ч!Г'"

вид

I V •• • / I» 1.Ш-1 . •).-'-,■''

пр"

ИЛ - (£-»)» > % . -

ад - ¿2 < % _ о»-о^;

а оптимальные стратегии игроков 1 и 2 могут бить найденч «о фп-цулам

ч;. у -

_/-»"*' ) " fn.fi

где Х4]м, , М*

-) - (2и-1)л -»• )

План доказательез'вгг этой, п такло еждуы.ли -.оол.-ч '.'л^ь. Проверяется, что носители вероятностных мер птададяекг

единичному отрезку„ Доказывается равенство.

ьД <?<>/'*>-г (Ь ^ , -»>'

-

г

Следовательно, пара ( ^ ) - оптимальные стратегии игрокои. а V ( к ) - значение игры Г ( к ).

5 Ь. Решение игры с функцией выигрыша к = Ч'а*^,,

Дальнейшее решение игры Г ( и ) с функцией выигрыша к ---■ ^ *■ наталкивается на определенные технические

трудности, связанные с громоздкостью получаемых результатов. Некоторые из них будут видны на примере решения игры Г ( К ) с функцией выигрыша к - типа "труба". В настоя-

щем параграфе расширяется то множество значений параметров ( £ » Л }и1Я КОТОРЫХ получено решение в предыдущих теоремах.

Теорема : Реиение игры Г С ^ ) с функцией выигрыша типа "труба" к = может быть найдено по формулам

¿Г

1) при Е=1 , + «Л •> , (и-ГМ ¿ ^ **= ,

2) при = г^-г)^,

/** и, Уг . , где и, , находятся по

формулам

3) при 24 Г, п =У

¿л* ^чл'-. * , где г<г) находятся по

формулам

4) при ^ ^ и-? ^

(Л-О <7* 1'ъ (л-у) > >г 2(ь-1)>; г у.

С ^ С ^ «"

+- (£н- ь ^ _ л (и--о« ск-1) (а-у) 1.

ХОДЯТСЯ ПО формула.';. !•/) при и-5 £ г 2

(;.--/)// г Л. (А-'Л '' _ ( >!-' ' - f) >£ Пй > ^

С»- 7ч)и *-(£>>-к у2 г Су*-*--[-^(»-Я+О--[-')■[ к.,

Заштриховано множество точек, для которых найдено решение игри "труба" Г^д.* Ч>йУ

находятся по форадлаи

где и,, , V,

гл.з. негоду теорли вероятностей при решши игр на

ЕДИНИЧНОМ КВАДРАТЕ

В настояце главе мы покакеы, как катоды теории вероятностей ( теория восстановления, преобразование Лапласа ) позволяют получать решение игр на единичном квадрате в явном виде. Будет указана связь между "временем жизни" точки, случайно блуядащей на отрезке [0,1] и игрой с выбрроы момента времена.

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

Основные результаты настоящей главы можно найти в работе {"?].

§ I. Игры априорного оценивания с показательной функцией выигриаа

Теорема. Значение игры априорного оценивания

Оз-О, Г 2й>0 находится по формуле

г (к'),

где

ГС (£ \ 1=С

-2Ца -аг

е + а е

О |=С>

£ О-г-дгЛе2'4 )

, а плотности

где т= 1/М+1, -п« оптимальных стратегий игроков находятся по формулам V = ^ , где

£ + оТё 2иЧ

л-1

е' ¿«0

Гу'е-^Я +ае-аг£еЛлЧ )

§ 2. Случайные блупдания на отрезке и игры с выбором ыомента времени

В дальнейшем мы будем рассматривать игры априорного оценивания Г- (Д.З. ^ , в которых функция V. ( "Ь ) — непрерывна справа на отрезке [-I.il. а вне этого отрезка равна нулю.

Учитывая определение, данное Карлинш игра априорного оценивания Г будет игрой с выбором момента времени если на промежутках [-1,0Г Л 0,1] функция \<.( ) - убывает и

Но+О4) ^ к.Со-0^ , или ( 4г ) - возрастает и

к ((Л-о) \c C0-oV

Пусть взаимонезависимые случайные величины с

одним и геи же распределением И . Обозначим 5>о =0

2,+....+ 2^; последовательность \ образует случайное' блуждание порожденное Н .

Теорема. Пусть ТС * ) - время нахождения частицы на отрезке 10,*3 при условии, что она не выходила за отрезок [0,1") , тогда число 1г = 1/Т (I) - значение, функция (г ( * ) = ) - функция распределения выравнивающей стратегии игрока 2 в игре априорного оценивания Г (Д0^1"! > к") с функцией выигрыша

V- 1,-Н.

Здесь 4[а (.0 - характеристическая функция промежутка

§ 3. Игры априорного оценивания и уравнения восстановления

Рассмотрим игру априорного оценивания Г ( ^ ), где к ( ^ ) -непрерывная справа, («возрастающая при 4: г функция и рчвна нулю при -Ь^г , к( г с. Если г> 0, то Г имеет седловую точку (1,1). В дальнейшем мы будем считать г< 0. Значение функции к( ^ ) будем считать положительным, так как п противном

-13-

случае игра Г имеет седловую точку (0,0).

Теорема. Если в игре априорного оценвшния ' ( ) фдккр,ия к ( t ) - не возрастает и положительна при "Ы [г«11 , и равна нулю при 4: < г , то функции распределения оптимальных стратегий игроков I и 2 могут быть найдены из решения соответст-вуощих уравнений восстановления.

В качестве примера приведем систему уравнений для нахождения функции распределения Сг оптимальной стратегией игрока 2.

где ^ - значение игри Г. ( Формула дм значения игры приводится в диссертации ).

§ 4. Решение игр априорного оценивания с помощью преобразования Лапласа В етоы параграфе приводится примеры игр с кусочнонепрерывнши ядрами. Например, приводятся ренения игр с ядрами:

... < ¿а

Р1> о

2) и^Са-кМ^ О ^ А > О

3) каь

л л ь \

ГЛ.4, игга Л-ВСТРЕЧИ

В отой главе рассматриваются игры априорного оценивания с ло-.роговыми функциями выигрыша Г (X > А ) ( иг{н А-встречи ). В »тих играхХ компактное подмножество функция выигрыша имеет вид:

-V3-- } 1 • есгй

^ 1 0 • ecj:£i

Такие игр; ппервио рассматривалась в работах Н.Дреасра, Д.ГеЯ-ла. Полное репение игры Г ([0,1],й) получено Н.Н.Ворэбьовки. Асимптотическим поведением игр! Г (X . Л ) занимались ЗлеЯшан и Крапивин, однако полученные иии результаты незерш.

§ I. Игра А -встречи на кокпаото

В J I гл.4 ксследуе-тсл пскнптоткчгспоа поведение игры д -встречи Г(Х »А ) при л-*. 0. ПустьX - компактнее подмножество Rn. Игра Р(Х , А ) инее? значение, которое ш обозначаем через V (X • & ) или чорез *у { Д ), если будет ясно о каком именно компакте идет речь. Обозначим через нокоторуо оптикальнуя стратегия игрока I, а через ^ г- £ - оггакмалънуо стратегия¿трока 2 . Астаптотическое поэедегаю v (X У при малых А опнсиваеуся сдедус-зей теореыоП.

Tcops-ia Г. Если X - кокпактноо измеримое по Иордану подото-яесуео R.ft, {-чС^ )»0, то

Г42 * /voo '

где о бьем единичного «.-мерного шара.

Пусть А - вероятностная мера, равномерно распределешшя на компакте X. Теорема 2 утверждает, что в условиях теорекн I меры слабо сходятся к «ере X при и-ъ 0 и

Полученная оценка асимптотического поведения & ) даст

возможность доказать, что для любого измеримого по Еордаку кошактного подмножества йЛи )> 0 разность На(Х)"^л>А)

- ограничена. Здесь £ ) - ноямогоровская & -энтропия, а ЗйС ^ ) - аболотиая д-эрктропия«, Эта гадала была поставлена Е.Познером, Е.Родэшчеи в работе в связи с поиском изкбодеа экономного способа передачи инфортани о ниокестпо А е povhoctf г<

ДО & .

5 2. Игра Д -встречи на п -ыариоы заро

В ? 2 рассматривается игра д. -зотречм на одиодгенсм п •гщяох шаре-Л,ь С »л-2). Используя сообраления симметрии, агрз сводится к некоторой игре на квадрате { & ) с довольно сяожноП

.,-ао-

функцией выигрыша. Оказывается, что при £ Л <• 1 функция выигрыша в игре Р„ ( Л ) имеет единственную седловуо точку

| а значение игры ь ), и следовательно игры Г (-Пп, Д равно

' оясЯи.4 ,

ь о

где т

*

^ ( * ) - гамма функция.

Используя сведение игры Г & ) к 6 ), иы получим,

что в первоначальной игра Г(ЛП , & ) у игроков I и 2 существуют оптимальные стратегии равномерно распределенные на С и. -15-мерных сферах соответственно радиусов -/7-1? и I.

В работе также приводится решеине игры Гп(1/2) при п 2.

§ 3. Игра &-встречи на трехмерно» шаре

В § 3 гл.4 более подробно исследована игра & ), к которой как уже отметалось, сводится игра Г , д ) . функция выигрыша в игре Г, ( д ) имеет вид

4. , при х*^ £ А

. . при

, при

При L ¿ А/Гг функция х ухе не имеет седловую точку,

повтому решение игры Г3( А > ищется в смешанных стратегиях. Обозначим через р>- меру с плотностью хехл , заданную на отрезке [О, J I- л8-' "] , а через i - меру с плотность» , задан-

ную на отрезке £о, Jl- i?b] . Через , - обозначим единственные корни двух уравнений, указанные в тексте диссертации.

Теорема 5. Пусть ьt £«V,Y<a 1 . где ^=0,5537...

А тг г ,---лтчг1

Оптимальныыи стратегиями игрок;,в I и 2 соответственно будут:

=ал>ЦБд+¿¡г У* + ^ ^^ ^ *

Здесь вероятностная пера с носителей в точке С1 . Теорема 6. Дусть , где «¿,«0,5537...

=0,475... Значение игры Г5() будет равно:

Оптимальные стратегии игроков I и 2 соответственно равны:

I П—/ Я^Ч ор *Г~ехр (. -д— ).

Таким образок, эти теорема дают возможность указать вид оптимально стратегий игроков з игре Г (-^з , & ).

Все основные результаты главы 4 опубликованы в работах автора [1,3].

ГЛ.5, игга ИНТЕРВАЛЬНОГО ОЦЕНИВАНИЯ

Эта гдась посзяцена резегага известной статистической задачи: построение минимаксной интервальной оценки параметра семейства дискретных случайных величин по результатам наблюдения, т.е. решается статистическая игра Г=4 ^о,^11"1, гХ> с функцией внигриса

где ^е^ои! - оцениваемый параметр, (*«>... - век-

тор оценок, - - вероятность того,

что случайная величина ) принимает значение I , й(^) -

промежуток содержащий точку м » >0 ~ некоторая функция,

Ьф* Ьф-Пф . *

5 I. Об использовании метода динамического программирования при решении игр оценивания

В атом параграфе исследуются уравнения вида

¡Г0>= »ах

Теорема. Р&сстоггрш игру ецзшваная Г= < йуПДо/^, .&-> с функцией ветгр^ ¿¿{х^У- '¡^ ^З-а.рЗ » где

(£ ) - полоеггсдыйл поа^иедрарышая снизу на отрезке [0,1] функция, тогда значение игри шаодктся по формуле

V» («<« £ , (?)

где какехцуи берегся по ссеу Бозрастсюциа пссдедог ат ельносгяа * "Ь«, , для которых 4. - "I; >✓ А Плогность распредодешш ошчшалышй стратегии игрока 2 находится по формуле

где последовательность \ ^ > \ та., на которой достигается максимум в формуле С ? )• Сункцк» распределения Г * оптимальной стратегии игрока I наЯдси из уравнений

= у.-лх СГ(А-ь) + VI «Л

В конце приводятся формула решения игри Т~ ^ Г0- Ю"], ^З^За'ДЗ ** сР * * с тон елутас, когда | ( £ )

полоЕитольна и имеет едкнстьенний каксж^м.

Значение поодчиеизЙся статистической игра Г указывает среднее число бззосибочнцх оценок параметра 3 = 1с, 1"} . Решение игр! Г шгст быть получено только в созванных стратегиях, помочу оптимальные стратегия Природы и Статистика могут быть интерпретированы соответственно как наихудшее априорюе распределение оцениваемого параметра и наилучшая рандомизированная оценка Статистика или минимаксное решэдее правило.

Наибольший интерес представляет тот слутай, когда Ь(-семейство биномиальных случайных величин, а )-1. У»е наи-

более простой случай и.=0 оказался нетривиальным ( полно стьс разобран Н.Н.Воробьевым ). Оценка параметра по результатам одного наблюдения С п =1) подробно исследовалась в работах Н.А.Никитиной и М.М.Луценко [II], где указано значение игры и даны аналитические выражения для оптимальных стратегий обоих игреков при всех

возможностей:

1) Если |М >2<Л и для всех , достаточно близки;; д А» 1тг{к)~ ц0~ «(-У

2) Если = , то (АД -

и длях близких к >.о (Х>и, «(Аэ>- »СЛ). «а)- ' -

Аналогичную теорему мокно доказать и дчя случая, когда да С ^ ) или и С А ) убывает, если А аозарстак, проходит через критическое значение.

Испольщзя эти теоремы, можно находить критические значения параметра А .

§ 4. Асимптотическое поведение оптимальных стратегий в игре Г ( X ) .

В 5 4 главы б исследуется асимптотическое поведение стратегий /Ч > при X . Функции ул ( и ), определенная по формуле

(I), при А -»о« сходятся к функции

при V ^ 4 к/г при |ч\ * ^

° при \ц\ >

Решение игра I* с функцией выигрыша £ (■■*• - похоже на решение игру с пороговой функцией выигрыша. 'Так как функции ч ) сходятся к \ ( и ) при А —> естественно опидагь, что и оптимальные стратегии в играх Г ( А) сходятся к некоторым оптимальным стратегиям в игре Г . Однако это будет иметь место не всегда и зависит от того, целое или нет число 1/2 .

Обозначим через - соответственно следующие вероятностные

меры: 4 £

К/2 с

если М- четно

I ¡Ым^-а*^4 Тк 1 Ко^^-ик-Д,

если Н- нечетно.

Теорема 6. Пусть К4 [^й] » -у2д - число

нецелое. Тогда

П Существует такое число , что при "> А„ число точек в спект-

- 88-

pax соответственно равно tf, )Г +S

2) ¿fки м® - uj^. .

Х-^ОО I л

3) ^ = <% .

не трудно проверить, что ыера и буду? оптимальнь-уи стратегиями игроков I и 2 соответственно в играТ 3

Теорема V. Пусть jj i = W - целой число, тогда

I) Существует такое число Ав, что при

о ЧИСЛО V04GК 13

спектрах ^ , í* соответственно равном-I, !Г

2> l'n> S»T= » пРичем

'прйчем * й;

где A(zi-t) «Vx + °0М J ,0¡ - находятся из решения

некоторой системы уравнений.

Таким образом, результаты, полученные для в случае Д/2

- целое число, несколько более точные, чоы в случае 1/24« нецелое число. Заметим, что в отличие от случая 1/2¿нецелое число, мера w„., - не будет оптимальной стратегией игрока I в игре г В конце параграфа даны примеры нахождения при неболь-

ших V".

ГЛ.7, ИГШ С КУСОЧК)ВОГНУТШ!И ФУНКЦИЯМИ ВЫИГШИА.

В главе 7 рассматриваются игры с непрерывными кусочновогнугыка функциями выигрыша:

ÍL при х+й^

ПРИ (3)

МСх,^ при

где Д4> [о, 13 , * А . a ¿ , V - строговогнутае

и триады непрерывно дифференцкруеггые функции, причем Ц,х- о, (fg " ¿g ¿ О при Х +

vx - м„<.0, -Mj ю при

С Допустимы спучаи Ь или К тозгдественно равны нулю )»

Игры о кусочноБОГнутымя функциями выигрыша (9) является обобщением игр априорного оценивания с нусочновогнутыми функциями выигрыаа. Примеры игр априорного оценивания с кусочновогнугыми функциями выиграаа приведены в гл.1 диссертации.

В гл.1 указаны некоторые возможные приложения игр с кусочно» вогнуытми функциями выигрыша среди которых наиболее важным явля-

огсл огскме к теории связи.

Класс игр (3 ) довольно обширен и является обобщением игр с погнутыми (¡дункциями выигрыша и бабочкообразных игр (гл.1).

В первые игры игра С 9 ) переходит .когда Д,,Аг =0 по вторых игра ( 3 ) переходит, когда Д,=0, =1.

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

Все основные результаты главы 7 содержатся в работе автора

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

§ I. Общая теория

Теорема 4.1. При любых Л^Д^о/О всякая оптимальная стратегия игрока 2 зз игре с кусочновогнутой функцией выигрыша С 9 ) -непрерывна внутри единичного интервала за исключением, быть может, точек Кл и I-

Обозначим через ^аЛ , ) смешанную стратегра,

которая чистям стратеги®.! О и I приписывает соответственно вероятности oi и р , а на отрезке [Q ,61 задается непрерывной плотностью и не имеет других точек спектра.

В теоремах 2 и 3 доказывается, что оптимальные стратегии прро-ков в игре (9) имеют один из следующих трех видов

I) P-lV

п) ч^.^Лц^Ч^

где и .. '^41'^с.й 1' w'1 ^ '^находятся из некоторой системы интегральных уравнений.

Оптимальные стратегии в случае I такие же как и вогнутых играх, о случае П вштимальные стратегии похожи на оптимальные :тратег!ш бабочкообразных игр, вид III характерен именно для данного класса игр.

-СО-

{] 2. Пркнврл реи-««««

Б 5 2 ГШ) 4 врмядахея г:£иеййя двух игр априорного

оценишиия с Сзйквйя»» ышррыва.

!ЯШЙ1 АВТОРА Ш ТИЕ ДИССЖИЙЦИИ

I» Дуцст» И.Ы. &ушга о й -всхречи п еауч&е круга и варе. Тезисы докладов Ш ВсессиушоП конфозсицш по теории игр. Одесеа, 1974.

2. Луценко Ы.М. Злдачз о л -истрече на компакте. Теорстико игровые «.опросы принятия рссешш. Л», Наука, 1078. стр. И6-124 (Рукопись ДСП. в БИВДХИ 25.1!.»76, К» 4107-76 ДЕЛ, РЕ Мат., 1977, ЗВ597 ).

3, Луцзнао Н.Н. 5а?с«и> о ь -ь&^ргче на трехмерной каре,- Теория ворэяиюетей и со ядаздюш, 2978, т.лХШ, вып.1, стр. 198-203. Л^цешю О псег&ом^а.олсобраэтк игра::. Тезисы докладов

□ Веесоаэкей ксифвщщт »ж вссждавош» операций, Горький,

2973,

5а Луценхс Нгрз с иеса^колюкяообраашаи функциями выигрыша, 45 С Скопись ь ШШГИ 6.02.79 ],« 476-79, ДЕЛ., И

йи. ИШ,- В982

б. Луценко Ei.il. йгрз с азсйиювагнугют функциями выигрыша. Суще-егьовш« рагеаий, усгойчавость и ян^ормзроканноегь в теории игр» КааинккеаяА тес. ^ни'серсите?, 1973, е*р. 90-98. Луценхо Li.ll. Игра априорного оцгнигсшя. с показательной функцией ваягрьш» Математические иегод) в социальных науках, йнеттут охокомихй АН ЛитСССР, Вильнюс, 1986, вып.19, с.42-47. 8. Луценко Ы.Ц. Сб использовании иетода динамического программирования при ревзнии игр оценивания. Кагегамгические методы в социальных науках, Инс?:1?у? вконоийкй АК ЛитСССР, Вильнюс, 1987, шп.20, е.28-27.

О о«к играх лродгояогавдея» «?го ь?, 1/2

-319. Луцешсо МД1. Игры априорного оценивания и их репение. Натемати-ческие метода в социалышх науках, Институт экономики АН Лит ССР, Вильнюс, 1988, вып.21, с.38-43.

Ю.Луценко М.1.1. Оценка определенного интеграла методом динамического программирования, сб. Днффереицкалыше уравнения с частными производными, Ленинградский педагогический институт, Ленинград, 1983, с.102-104.

П.Луценко M.LI. Теоретико-у.гровой метод оценки параметра биномиального закона по результатам одного наблюдения, т. Теория вероятностей и ее применения, LI., 1969, Т.ХХХ1У, е::п.З, с.£69-593.

ТЭ.Луценко L1.IÍ. Теоретико-игровой метод оценки параметра бшотааль-ного закона, т. Теория вероятностей и ез применения, Ii., 1590, т. ХХХУ, вш.З, с.471-482.

13. ¿utsevik.cs М. ^i'.cimicaí. progro-wnnng rn^tlioc! s i vi gane

tVieor^ awJ stcCtístics. Malbe^aiUcUe aptomeruv^ - -orie íLvici anwewduvKjeyi . ^rtragcxúsaüge , Eise.nac.li, , "TexiUmseile. Hoc.Wsc.lauPe. iLmenau 1^2-1-35.

1<!,Луценко U.M. Об одном подходе кр реаенио игр на единичном квадрате с функцией вкигрыса к (* ), часть I. Optimijatiou 21 (1990), I, с.71-86, ■ 15,Луцеш;о U.M* Об одном подоходз к репенио игр на единичном квадрате с (функцией выигрыша к { X -Ч ), часть П. OpUmiwUon 21(1990).

15.Луценно U.U. Игры оценивания. Тезисы докладов всесоюзного совещания пути повышения качества прогнозов, 1'оскза-Ленинград, 1990, с.72-74,

Подписано к печати 15.II.91 г. Усл.печ.л. 1,8. Оормзг 60x84 /16. Печать офсетная. Бумага для мпоз. апп. Тираж ICO экз. Заказ И IS36. Бесплатпо.

Тип. ЛШК'Га I9003I С-Петербург. Московский пр.,9 ■