«Вітчизнянанаука: сучаснийстан,актуальніпроблемитаперспективирозвитку»
жүктеу/скачать 8,82 Mb. Pdf көрінісі
|
Лемма 1. Пусть
2 , 1 2 , max , 1, 2,..., n n i n n i n M a C L n B n L . Тогда при 1 n n x B M 4 | | x MnL n P T x e .
Доказательство леммы 1. Аналогично доказательству соотношения (1.7) леммы 1 (см[1], с.358), причем используется лемма 2, которая доказана в работе [2].
Пусть
1, 2, , ... n n n n Y Y Y –
порядковые статистики,
, , , , , 1 1
n n j n j n j n j n j n j j U b Y MY b Z , где , { } j n b
– положительные константы, и пусть ( )
–
выпуклая функция, имеющая непрерывную производную. Тогда известно, что о ( ) n M U
–
неубывающая функция по каждому из коэффициентов 1, 2, , ; ;...;
n n n n b b b [2].
Справедливы следующие утверждения:
Пусть
, 1 max , 1, 2,.... i n i n C L n
2 1 1 | | ln |
| R M X X
. Тогда
1 | | n n P T n
«Проблеми та перспективи розвитку науки на початку третього тисячоліття у країнах Європи та Азії»
155
при любом фиксированном 0 .
Теорема 2. Пусть , 1 max , 1, 2,... i n i n C L n
и для 2
1 1 | | ln | |
t M X X
. Тогда
2 1 | ln | t n P T n
при любом фиксированном 0 .
Доказательство теоремы 1. Введем в рассмотрение следующие события: { :|
( ) | };
i n A w X w a 1 { : 1, ,
( ) ( )}
n i i i i A A i i n X w X w ; 1 { :| ( ) | }{ :
( ) ( )}
n i n i i i i A w X w a X w X w . Здесь
{ } n a
определены, как и выше.
Тогда { :|
| } { : (|
( ) | ) } n n w T x w T w x
{ : (| ( ) | ) } { (| ( ) | ) } n n w T w x A w T w x A
{ : (| ( ) | ) } { (| ( ) | ) } n n w T w x A w T w x A
.
Согласно последнему (| | ) ((|
| ) ) ((| | ) ) n n n P T x P T x A P T x A
1 (| | ) ( ) (| | ) | ( ) | n n n i n i P T x P A P T x P X w a
1 | | | |
n i n i P T x P X a .
(1) Из (1), положив x n , получим
1 | | | | | | n n n i n i P T n P T n P X a . Из последнего, имея в виду то, что случайные величины 1 2 , ,...., n x x x
одинаково распределены, находим, что
1 1 2 1 1 1 | | | | | |
n n n n n P T n P T n nP X a (2)
Далее, так как по определению ,
| | , |
| 2 i n i n M X a Y a , то, согласно лемме 1, при 1
получим
| | exp 8
n n P T n a L .
В силу последнего 8 1 1 1 | | n Lan n n n P T n e .
Теперь выбираем
156 «Проблеми та перспективи розвитку науки на початку третього тисячоліття у країнах Європи та Азії»
8 ln n n a PL n .
Тогда
2ln 1 1
n e
(3) при любом фиксированном 0
.
Теперь переходим к оценке 2 . По выбору последовательности { }
имеем 2 1 1 1 1 | | | | 8 ln
n n n nP X a C nP X PL
1 1 1 1 1 1 1 | | | |
j j j j n j n j n C n P b X b C P b X b n
2 2 2 1 1 1 1 1 1 | | | |
j j j j j j j j C P b X b j C b P b X b b
2 2 2 2 1 1 1 1 1 ln | | | | ln | | j j j j j C b b P b X b CM X X
(4) если
2 2 1 1 | | ln |
| M X X
. Здесь
8 ln
j b PL j и С
–
положительная постоянная, зависящая только от
и
, причем не всегда одна и та же. Соотношения (3), (4) вместе с (2) завершают доказательство теоремы 1.
Литература : 1.
Петров В.В. Суммы независимых случайных величин. М.: Наука, 1972.
2. Егоров В.А., Невзоров В.Б. О скорости сходимости к нормальному закону линейных комбинаций порядковых статистик. –
Теория вероятностей и ее применение. 1975, том ХХ, № 1.
(Киев, Украина)
Нобелевский лауреат Джон Нэш ( John Forbes Nash) нашел единый принцип (равновесие Нэша), который может применяться для многих социальных проблем. Как то за чашкой кофе Нэш заметил, что так же, как поверхность кофе имеет вихрь, по той же математической логике, любая социальная проблема имеет точку, в которой все игроки делают свои лучшие по отношению к другим ходы. Когда все стороны используют идеальную стратегию, это и приводит к созданию устойчивого равновесия. Игрокам выгодно сохранять это равновесие, так как любое изменение только ухудшит их положение.
Дадим определение равновесия Нэша в случае с двумя игроками. Пусть , , G I S u игра в нормальной форме.
1,2
I множество игроков, 1 2 , S S множества стратегий игроков, 1 2 , S S S
любой элемент i i s S
стратегия игрока i, i i s S стратегии всех игроков, кроме i. Функция выигрыша игрока i будет
присваивать каждому профилю стратегий s S
какой - то выигрыш: : .
u S Тогда s S равновесие Нэша, если для всех
, для всех ,
мы имеем , , . i i i i i i u s s u s s
Пожалуй, самой известной игрой в теории игр является «Дилемма заключенного». Эта игра была описана в 1950 году американскими математиками Дрешером и Фладом. Однако сейчас все ее знают в изложении, которое годом позже сформулировал Такер, для того чтобы рассказать эту
«Проблеми та перспективи розвитку науки на початку третього тисячоліття у країнах Європи та Азії»
157
игру на научно - популярной лекции. История такая: полиция поймала двух подозреваемых в совершении серьезного преступления –
ограбления банка. Однако у полиции недостаточно улик для того, чтобы доказать ограбление. Видно, что стекло разбито, однако где деньги, которые хранились в банке, непонятно. Что делать? Полиция разводит заключенных по разным частям следственного изолятора и предлагает каждому из них пойти на сделку со следствием, а именно: выдать улики на своего напарника в обмен на сокращение собственного срока пребывания в тюрьме. При этом, естественно, полиция запрещает обмен информацией между заключенными. И мы увидим, что с помощью этого ей удается добиться. Значит, у каждого из двух игроков, а именно заключенные в нашей игре являются игроками, есть на допросе две стратегии: это либо промолчать, либо пойти на сделку со следствием и сдать своего напарника, выдать на него улики, тем самым надеясь уменьшить свой собственный срок. Как устроены платежи
игроков в этой игре? Если оба игрока будут молчать, и не будут выдавать улики друг на друга, то тогда полиция отправит каждого из них в тюрьму всего лишь на 1 год: за мелкое хулиганство, за разбитое окно в банке. Если один из заключенных выдаст второго, а
второй промолчит, то тогда вся тяжесть совершения данного преступления ляжет на того игрока (подозреваемого), который промолчал. На него улики выданы, соответственно, он сядет в тюрьму за ограбление банка на 10 лет, а вот второй заключенный, на которого и
так не выданы улики, еще и получит возможность уменьшить свой срок. Его бы посадили за мелкое хулиганство на 1 год, но поскольку он пошел на сделку со следствием, то будем считать, что полиция его прощает и отпускает домой. В этом случае его платеж будет равен нулю. И, наконец, если оба заключенных пойдут на сделку со следствием, то тогда улики у полиции будут на каждого из них, каждый из них будет обвинен в ограблении банка. И это светило бы им наказанием в размере 10 лет заключения в тюрьме.
Однако вспоминаем, что каждый из них пошел на сделку со следствием. Значит, полиция тоже выполняет условия этого контракта, уменьшает каждому из них срок, и каждый отправляется в тюрьму на 5 лет. Матрица этой игры представлена следующим образом.
Игрок 2
Игрок 1
Промолчать
Сознаться Промолчать
-1;
– 1
-10; 0 Сознаться
0;
– 10
-5; – 5 Игра два на два. Давайте представим, как рассуждает первый заключенный. Он думает: «Какую стратегию мне (Игроку 1) выбрать? Если мой напарник (Игрок 2) будет молчать, и я тоже буду молчать, то я получу платеж равный минус 1, отправлюсь в тюрьму на 1 год. А если предам его, то получу платеж равный нулю, выйду на свободу. Мне лучше сознаться». Если я подозреваю, если первый заключенный подозревает, что напарник сознается в преступлении,
то тогда в случае, если первый заключенный будет молчать, то он отправится в тюрьму на 10 лет. А если предаст, то тогда на 5 лет. Значит, лучший ответ на стратегию «Сознаться» –
снова стратегия «Сознаться». Таким образом, у первого заключенного есть строго доминирующая стратегия –
«Сознаться». То же самое, естественно, можно сказать и про второго заключенного. Они симметричные. Значит, у второго заключенного тоже есть доминирующая стратегия. И она –
предавать первого. Таким образом, по определению профиль (Сознаться, Сознаться) является равновесием в строго доминирующих стратегиях. Этот же профиль будет и равновесием в слабо доминирующих стратегиях. Будем говорить, что профиль стратегий s Парето
- доминирует профиль стратегий s , если платежи, которые получают игроки в профиле s не меньше платежей, которые получают игроки в профиле s . И, по крайней мере, для одного игрока платеж, который он получает в профиле s , больше платежа, который он получает в профиле s . Мы будем говорить, что профиль стратегий s * называется Парето - оптимальным, если не существует никакого другого профиля стратегий s , который бы Парето - доминировал профиль стратегий s *. Давайте снова посмотрим
на «Дилемму заключенного». Какие из профилей являются Парето - оптимальными? Профиль (Сознаться, Сознаться), который, как мы знаем, является равновесием в строго доминирующих стратегиях. Является ли он Парето
- оптимальным? Ответ –
нет, потому что существует профиль (Промолчать, Промолчать), в котором оба игрока получают платеж, больший, чем в профиле (Сознаться, Сознаться). Значит, профиль (Промолчать, Промолчать) Парето
- доминирует профиль (Сознаться, Сознаться) и, соответственно, равновесие в строго доминирующих стратегиях не является Парето - оптимальным. Это, казалось бы, странно, потому что мы считали, что каждый игрок использует свою оптимальную стратегию, которая является наилучшим ответом игрока в ответ на любую из стратегий других игроков. В данном случае на любую из стратегий второго игрока. Второй игрок действует точно так же. Играет стратегию, которая является наилучшим ответом на любую из стратегий первого игрока. Однако, тем не менее, платежи, которые они получают в результате этого, оказываются меньше платежей, которые бы они получали, если бы договорились и молчали, в то время как полиция предложила бы им пойти на сделку со следствием. То есть профиль (Промолчать, Промолчать) является Парето - оптимальным. Почему? Потому что ни один из трех других профилей не Парето - доминирует профиль (Промолчать, Промолчать). Профиль (Промолчать, Сознаться) является Парето - оптимальным, потому что второй игрок никогда не может получить платеж, больший нуля. И это означает, что невозможно увеличить платеж первого игрока, не уменьшив платеж, который получает второй игрок. Профиль (Сознаться, Промолчать) тоже является Парето - оптимальным. Получается совершенно фантастическая история. В игре есть равновесие (Сознаться, Сознаться), однако Парето - оптимальными являются все профили, кроме равновесия.
В этом и есть некоторое нехорошее свойство равновесия. На самом деле, с точки зрения общественного благосостояния, равновесие ничего не означает. Те платежи, которые могут получать игроки в этом равновесии, могут быть меньше, чем платежи, которые бы они могли получить в каких - то других профилях. Мы видим, что в равновесии Нэша игроки получают необязательно наилучший для себя платёж. Существуют и реальные жизненные примеры, которые иллюстрируют это свойство равновесия Нэша. Давайте рассмотрим пример с раскладкой на клавиатуре. Традиционно сейчас используется раскладка, которая называется QWERTY по первым буквам на верхней строчке клавиатуры. Эта традиция была заложена ещё в конце XIX века. Тогда использовали печатные машинки, и нужно было сделать так, чтобы, нажимая на клавиши, сцепления рычагов не пересекались друг с другом в процессе печати. И поэтому буквы были расположены в таком порядке, чтобы часто встречающиеся подряд в словах алфавита буквы не были расположены рядом друг с другом
на печатной машинке. Это позволяло уменьшить число сцеплений рычагов в процессе печати. Однако сейчас, в XXI веке, печатными машинками почти никто не пользуется –
все используют клавиатуры. Были придуманы другие раскладки. К их числу относится, например, 158 «Проблеми та перспективи розвитку науки на початку третього тисячоліття у країнах Європи та Азії»
раскладка Dvorak. Но, тем не менее, по - прежнему подавляющее большинство пользователей печатают на клавиатурах, в которых используется раскладка QWERTY. Почему это так? Это как раз тот самый пример неоптимального равновесия Нэша. Если бы все использовали раскладку Dvorak, которая позволяет печатать быстрее, чем раскладка QWERTY, то каждый из пользователей получал бы больший платёж, и печатание занимало бы меньше времени: в этой раскладке буквы расположены в чуть более оптимальной последовательности. Но, тем не менее, ни одной из фирм, производящей клавиатуры, не выгодно начинать выпускать клавиатуры или ноутбуки с раскладкой Dvorak, потому что такие компьютеры покупать никто не будет –
все привыкли к использованию раскладки QWERTY, и переучиваться пользователю будет очень непросто. Значит, спрос на такие клавиатуры, на такие ноутбуки будет не очень большим, и невозможно при фиксированных стратегиях всех остальных использовать раскладку QWERTY отклониться и начать выпускать компьютеры с раскладкой Dvorak. Матрица этой игры представлена следующим образом.
2
QWERTY
DVORAK
QWERTY 1; 1
0; 0 DVORAK
0; 0 2; 2
Если Игрок 1 предположит, что Игрок 2 выберет QWERTY
, то Игроку 1 выгодней выбрать тоже QWERTY
. Если DVORAK
–
то DVORAK . И наоборот. Если Игрок 2 предположит, что Игрок 1 выберет QWERTY , то ему тоже выгодней выбрать QWERTY
, а если DVORAK
–
то DVORAK . Как видим, здесь два равновесия Нэша. Это стратегии (1;1) и (2;2). Но одна из них лучше другой. Это − пример неоптимального равновесия Нэша.
жүктеу/скачать 8,82 Mb. Достарыңызбен бөлісу:
|