Игровые ситуации в модифицированной задаче оптимального выбора
Для задачи оптимального выбора наилучшего или второго по качеству объекта рассмотрена игровая ситуация, в которой участвуют два игрока, осуществляющие свой выбор на двух различных множествах объектов. Данная игровая ситуация рассмотрена в двух модификациях в зависимости от информации, доступной игро...
Збережено в:
| Опубліковано в: : | Кибернетика и вычислительная техника |
|---|---|
| Дата: | 2012 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН України та МОН України
2012
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/45829 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Игровые ситуации в модифицированной задаче оптимального выбора / С.И. Доценко // Кибернетика и вычисл. техника. — 2012. — Вип. 168. — С. 3-13. — Бібліогр.: 5 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859826374947110912 |
|---|---|
| author | Доценко, С.И. |
| author_facet | Доценко, С.И. |
| citation_txt | Игровые ситуации в модифицированной задаче оптимального выбора / С.И. Доценко // Кибернетика и вычисл. техника. — 2012. — Вип. 168. — С. 3-13. — Бібліогр.: 5 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и вычислительная техника |
| description | Для задачи оптимального выбора наилучшего или второго по качеству объекта рассмотрена игровая ситуация, в которой участвуют два игрока, осуществляющие свой выбор на двух различных множествах объектов. Данная игровая ситуация рассмотрена в двух модификациях в зависимости от информации, доступной игрокам. В обеих ситуациях найдены оптимальные стратегии игроков, обеспечивающие равновесие по Нэшу. Также рассмотрена альтернативная игровая ситуация, в которой два игрока осуществляют просмотр на одном множестве объектов и целью каждого из них является выбор объекта, лучшего чем у противника.
Для задачі оптимального вибору найкращого або другого за якістю об’єкту розглянуто ігрову ситуацію, в якій беруть участь два гравці, які здійснюють свій вибір на двох різних множинах об’єктів. Гравці порівнюють вибрані об’єкти. Дану ігрову ситуацію розглянуто в двох модифікаціях, в залежності від інформації, яка є доступною гравцям на момент прийняття ними рішення. В обох ситуаціях знайдено оптимальні стратегії гравців, що забезпечують рівновагу за Нешем. Також розглянуто альтернативну ігрову ситуацію, в якій два гравці проглядають об’єкти та здійснюють свій вибір на одній множині елементів. Метою кожного гравця є вибір об’єкту кращого, ніж у суперника.
The optimal choice problem (also known as “secretary problem”) is one of the classic case in point in operations research field (namely stochastic optimization). The origin of this problem was just a puzzle, introduced by Martin Gardner. It turned out afterward that the “secretary problem” and its numerous modifications are good examples in both optimal stopping Markov chains and game theory. The basic principle of multisteps games is so called complex rational behavior concept: “I behave optimally. I know that my rival behaves optimally. I know that he knows that I behave optimally, etc.”.
|
| first_indexed | 2025-12-07T15:29:53Z |
| format | Article |
| fulltext |
3
Сложные системы управления
УДК 681.5
С.И. Доценко
ИГРОВЫЕ СИТУАЦИИ В
МОДИФИЦИРОВАННОЙ
ЗАДАЧЕ ОПТИМАЛЬНОГО ВЫБОРА
Для задачи оптимального выбора наилучшего или второго по качеству
объекта рассмотрена игровая ситуация, в которой участвуют два игрока, осуществляющие
свой выбор на двух различных множествах объектов. Данная игровая ситуация
рассмотрена в двух модификациях в зависимости от информации, доступной игрокам. В
обеих ситуациях найдены оптимальные стратегии игроков, обеспечивающие равновесие
по Нэшу. Также рассмотрена альтернативная игровая ситуация, в которой два игрока
осуществляют просмотр на одном множестве объектов и целью каждого из них является
выбор объекта, лучшего чем у противника.
Введение
Задача выбора наилучшего объекта на сегодняшний день является одной
из классических задач исследования операций, а именно стохастической
оптимизации. Изначально она была придумана Мартином Гарднером в
середине 20-го века как головоломка. В последствии оказалось, что данная
задача и ее множественные модификации могут служить иллюстративными
примерами в теории оптимальной остановки марковских процессов и теории
игр. В основе анализа многошаговых игр лежит так называемая концепция
сложного рационального поведения игроков, когда каждый игрок исходит из
таких предпосылок: «Я веду себя оптимальным образом на каждом шаге. Я
знаю, что противник ведет себя оптимальным образом. Я знаю, что
противник знает, что я веду себя оптимальным образом и т.д.».
В [1] была рассмотрена задача выбора наилучшего объекта,
сформулированная следующим образом. Пусть некто в случайном порядке
знакомится с n объектами и хочет выбрать среди них наилучший. При этом
после ознакомления с очередным объектом нужно либо остановить на нем
свой выбор, либо отвергнуть его, возвращаться к ранее просмотренным
объектам нельзя. Объекты являются упорядоченными определенным образом
по качеству, т.е. качества любых двух объектов сравнимы между собой.
«Ознакомление в случайном порядке» означает, что изначально все n!
перестановок, задающих порядок просмотра объектов, равновероятны.
Объект, наилучший среди всех n, в дальнейшем будем называть
наилучшим, а объект, лучший среди k просмотренных, – максимальным.
Очевидно, что в ходе просмотра следует анализировать целесообразность
остановки выбора на некотором объекте, только если он является
максимальным. При этом оказывается, что первый объект является
максимальным и индексы максимальных объектов образуют цепь Маркова с
переходными вероятностями .,
)1(
),( kj
jj
kjkp >
−
= Независимо от того, был
ли k-й элемент максимальным или нет, вероятность того, что среди элементов
С.И. Доценко, 2012
ISSN 0452-9910. Кибернетика и вычисл. техника. 2012. Вып. 168
4
с индексами nk ,...,1+ минимальный индекс максимального элемента будет j,
равна kj
jj
k
>
−
,
)1(
и с вероятностью
n
k в последовательности nk ,...,1+ не
встретится ни одного максимального элемента.
Доказано, что для того, чтобы выбрать наилучший объект из n, нужно
придерживаться такой стратегии: вначале пропустить все элементы с
индексами 1,...,1 * −k и затем остановить свой выбор на первом
максимальном элементе, индекс которого не меньше *k , где *k определяется
из двойного неравенства .
1
1...
1
11
1
1...1
** −
++
−
<≤
−
++
nknk
Оказывается, что
при ,∞→n ,1
en
k
→ а вероятность выбора наилучшего объекта при
соблюдении описанной стратегии стремится к 1 / e. Множество индексов
элементов, на которых необходимо остановиться, если они окажутся
максимальными, будем обозначать }*,...,{~* nkA = .
В [2] было рассмотрено обобщение задачи из [1]. Пусть в результате
просмотра требуется найти не обязательно наилучший объект, а такой, ранг
которого среди n не превышает r (т.е. объект является r-м по качеству среди
всех). Обозначим ранг k-го по счету объекта среди m просмотренных через
)|( maR k . Состояние просмотра будем описывать парой (k, i), где k — номер
просматриваемого объекта, i — его ранг среди k просмотренных, т.е.
.)|( ikaR k =
В [1] было показано, что если изначально все перестановки naa ,...,1
равновероятны, то независимо от взаимного расположения 11,..., −kaa ранг ka
в последовательности kaa ,...,1 с равными вероятностями k/1 принимает
одно из возможных значений k,...,1 (назовем это свойство (*)). С
использованием этого свойства в [2] было показано, что опорное множество
состояний A~ , на которых следует остановить просмотр, обладает такими
признаками: AikAik ~),1(~),( ∈+⇒∈ , AikAik ~)1,(~),( ∈−⇒∈ .
В случае если ценность выбранного объекта зависит от ранга и функция
ценности является невозрастающей (т.е. пусть за выбор i-го по качеству
объекта
−−−−
= ri ,1 выплачивается выигрыш iα , причем rα≥≥α≥α ...21 , то
указанные свойства опорного множества сохраняются. Поэтому cуществует
набор целых чисел nsss r ≤≤≤≤ ...21 , такой, что
{ } { } { },),(),...,,(...)2,(),...,2,()1,(),...,1,(~
21 nsrsnsnsA rr∪∪∪= а оптимальная
стратегия, максимизирующая ожидаемую величину выигрыша, имеет
следующий вид:
1) пропустить все объекты от 1 до 11 −s ;
2) остановиться на первом максимальном объекте, индекс которого не
превышает 12 −s , а если такового не найдется, то перейти к п.3;
3) остановиться на первом объекте, индекс которого не превышает 13 −s ,
а ранг не превышает 2, и т.д.;
5
r+1) начиная с элемента rs , остановиться на элементе, ранг которого не
превышает r.
Конкретные значения rss ,...,1 зависят от n и от rαα ,..,1 .
Рассмотрим частный случай ].1;0[,1,2 21 ∈α=α=α=r Найдем
предельные значения ns /1 и ns /2 при ∞→n в зависимости от параметра
α. Для этого предварительно найдем некоторые вероятности, вычисление
которых базируется на свойстве (*) и правилах суммы и произведения
вероятностей:
0) вероятность того, что в ряду ,...2,1 ++ kk ближайший максимальный
элемент будет иметь индекс j,
( ) ( ) ( )( )==>−>+>+= −++ 1|,11|,...,12|,1)1|(),( 121 jaRjaRkaRkaRPjkP jjkk
( ) ( )( ) ( )( ) ;
)1(
1|11|...1)1|( 11 −
==×>−××>+= −+ jj
kjaRPjaRPkaRP jjk
1) вероятность того, что элемент окажется лучшим из n при условии, что
он является лучшим из k,
( )==== 1)|(|1)|(),(1 kaRnaRPnkP kk
( ) ( ) ;1)|(...1)1|( 1 n
knaRPkaRP nk =>××>+= +
2) вероятность того, что элемент окажется вторым из n при условии, что
он является лучшим среди k,
( )==== 1)|(|2)|(),(2 kaRnaRPnkP kk
( ) ( ) ×>−=××>+= −+
+=
∑ 1)1|(...1)1|( 11
1
jaRPkaRP jk
n
kj
( ) ( ) ( ) ;
)1(
)(1)|(...1)1|(1)|( 1 −
−
=>××>+×=× + nn
knknaRPjaRPjaRP njj
3) вероятность того, что элемент окажется вторым из n при условии, что
он является вторым среди k,
( ) ==== 2)|(|2)|(),(3 kaRnaRPnkP kk
( ) ( )
)1(
)1(2)|(...2)1|( 1 −
−
=>=××>+= + nn
kknaRPkaRP nk ;
4) вероятность того, что при дальнейшем просмотре элементов
nk ,...,1+ среди элементов 1,...,1 −+ jk не будет встречаться максимальных
или вторых по качеству, а j-й элемент окажется лучшим среди
просмотренных, равна
6
>−>+>+= −++ )1|(,...,2)2|(,2)1|((),( 12141 jaRkaRkaRPjkP jkk
( )>+>+===> ++ 2|,2)1|((),(1)|(,2 2142 kaRkaRPjkPjaR kkj
( ) ×>+==>−> +− )22|()2)|(,2)1|(,...,2 21 kaRPjaRjaR kjj
==×>−×>+×× −+ )1)|(()2)1|(()2)1|((... 11 jaRPjaRPkaRP jjk
>−××>+×>+= −++ )1|((...)2)2|(()2)1|(( 121 jaRPkaRPkaRP jkk
( ) .
)2)(1(
)1(1
1
3...
21
1)2|()2
−−
−
=×
−
−
××
+
×
+
−
==×>
jjj
kk
jj
j
k
k
k
kjaRP j
Пусть )),(( ikf — средний выигрыш при остановке на элементе (k, i),
тогда
)1(
)(),(1),())1,(( 21 −
−
α+=α×+×=
nn
knk
n
knkPnkPkf ,
)1(
)1(),())2,(( 3 −
−
α=α=
nn
kknkPkf .
Поскольку по определению A~)2,1( 2 ∉−s , а
A~)2,(...),2,( 2 ∈ns , ,A~)1,(...),1,( 2 ∈ns то
( ) ( ) ).2,(,1)1,(,1)2,1(
2
242
2
2412 jfjsPjfjsPsf
n
sj
n
sj
∑∑
==
−+−≤−
Обозначим γ,=
∞→ n
s
n
2lim тогда, после подстановок, элементарных
преобразований и перехода к пределу в неравенстве имеем:
.1111111 1 1
2
1
2 ∫ ∫∫
γ γγ
−
γ
α+−
γ
=α+
−
α+≤α dt
t
dt
t
tdt
t
(1)
С другой стороны,
( ) ( ) )2,(,)1,(,),()2,(
12
242
12
241232 jfjsPjfjsPnsPsf
n
sj
n
sj
∑∑
+=+=
+≥α×= ,
отсюда, после аналогичных преобразований, получим неравенство (1) с
противоположным знаком, отсюда
.
12
1
+α
+α
=γ (2)
Исследуем асимптотическое поведение величины
n
s1=β при ∞→n .
Поскольку ,A~)1,1( 1 ∉−s а ,A~)1,),...(1,( 1 ∈ns ,A~)2,),...(2,( 2 ∈ns то
+×−≤− ∑
−
=
)1,(),1()1,1(
12
1
11 jfjsPsf
s
sj
( )( );)2,(,1)1,(),1(
1
1
2
242241
2
1 ∑
=
×−+×−
−
−
+
n
sj
jfjsPjfjsP
s
s
7
+×≥ ∑
−
+=
)1,(),()1,(
12
11
11 jfjsPsf
s
sj
( )( ).)2,(,1)1,(),1(
1 2
242241
2
1 ∑
=
×−+×−
−
+
n
sj
jfjsPjfjsP
s
s
Переход к пределу в данных неравенствах приводит к равенству
( ) αβ+
β
γ
α+=αβ−α+ ln11 , отсюда β — корень уравнения
( )
+α
+α
−=β−β
+α
α
12
1ln1ln
1
2 . (3)
При этом вероятности того, что выбранный элемент является
первым/вторым сходятся к таким величинам:
( ) ( ) ( )∑∑
=
−
=
×−×−−+−=π
n
sj
s
sj
njPjsPssPnjPjsP
2
1241211
12
1
111 ,,11,1),(),1( ,
( )
β−
+α
+α
+
+α
α
β=γ−β+
β
γ
β→π
∞→
)ln(
12
1ln
12
1ln1
n
,
( ) ( )×−−+−=π ∑
−
=
1,1,),1( 21
12
1
212 ssPnjPjsP
s
sj
( ) ( ) ( ) ( )( )
×−+×−× ∑
=
n
sj
njPjsPnjPjsP
2
32422241 ,,1,,1 ,
( ) ( ) ( )
+α
−β+β−
+α
+α
β=γ−β+β−γβ−
β
γ
β→π
∞→
12
1ln
12
1ln1ln2
n
,
а средняя величина выигрыша с учетом (3) равна
( )αβ−α+β=απ+π= 121v .
Обозначим предельные значения
,)ln(
12
1ln
12
),(1
β−
+α
+α
+
+α
α
β=βαg
( ) ( ) .
12
1ln
12
1ln,2
+α
−β+β−
+α
+α
β=βαg
(4)
Назовем стратегией 1–2 следующую последовательность действий.
Пусть задано 10 ≤α≤ — отношение важности второго по качеству элемента
к важности наилучшего. Найдем β и γ по формулам (3) и (2). В ходе
просмотра следует придерживаться такой стратегии:
1) пропустить все элементы от 1 до 1−βn ;
2) при просмотре элементов с номерами от nβ до 1−γn остановиться на
первом максимальном элементе, если таковой найдется, иначе перейти к п. 3;
3) при просмотре элементов с номерами от nγ до n остановиться на
первом элементе, текущий ранг которого не превышает 2.
8
Первая игровая ситуация —
борьба за выбор лучшего объекта при выборе из разных множеств
Пусть в выборе принимают участие два игрока, которые осуществляют
свой выбор на двух разных множествах элементов. Для каждого из игроков
возможны три исхода просмотра:
1) выбран наилучший (1-й) элемент;
2) выбран второй по качеству (2-й) элемент;
3) не выбран ни один из элементов из п. 1, 2.
Считается, что в данной нумерации чем меньше номер, тем лучше исход.
Игрок, исход выбора которого оказался хуже, платит единичную сумму
другому игроку. Если исходы игроков одинаковы, то фиксируется ничья и
платежей не производится.
Рассмотрим два варианта игры.
1. Несимметричная игра
Пусть исход просмотра 1-го игрока становится известным 2-му игроку,
до того как он начнет просмотр.
Пусть исход 1-го игрока — 1. Тогда 2-й игрок должен выбрать стратегию,
максимизирующую вероятность выбора 1-го по качеству элемента, т.е.
положить .1=α Тогда ,1,1
=γ=β
e
т.е. второй игрок должен придерживаться
стратегии классической задачи, что обеспечит выбор 1-го по качеству
элемента с вероятностью
e
1 , и, таким образом, средний выигрыш 2-го игрока
составит 6321,0)1(1101
−≈−×
−+×+
ee
.
Пусть исход 1-го игрока — 2. Тогда если 2-й игрок придерживается
стратегии, обеспечивающей ему выбор 1-го/2-го элемента с вероятностями
1p и 2p соответственно, то его средний выигрыш равен
1
2
1212)1()1(01 21212121 −
+=−+=−×−−+×+× pppppppp ,
т.е. коэффициенты важности выбора 1-го и 2-го элементов относятся как 2 к 1,
значит он должен придерживаться стратегии 1–2, положив 2/1=α , тогда
,34794,0≈β ,75,0=γ 46138,0
2
1max 21 ≈
+ pp и, таким образом, средний
выигрыш 2-го игрока равен 0772,0146138,02 −≈−× .
Пусть исход 1-го игрока — 3. Тогда ожидаемый выигрыш 2-го игрока
равен ( ) ( ) .011 212121 pppppp +=×−−+×+ Положив ,1=α находим, что
( )21max pp + достигается при 3470,0≈β , 3/2=γ и равно 0,5736.
Проанализируем поведение 1-го игрока. Если он придерживается
стратегии, обеспечивающей ему выбор 1-го/2-го элемента с вероятностями
1p и 2p соответственно, то его средний выигрыш равен
=−+=−−−+ 5736,06508,02057,1)1(5736,00772,06321,0 212121 pppppp
( ) 5736,05398,02057,1 21 −+= pp .
9
Положив ,5398,0≈α находим ,3476,0≈β ,7404,0≈γ
( ) 4710,05398,0max 21 ≈+ pp и, таким образом, выигрыш 1-го игрока
составляет 0057,05736,04710,02057,1 −≈−× .
То, что выигрыш 1-го игрока отрицательный, закономерно, поскольку
игра почти симметрична за исключением того, что 2-й игрок знает исход
выбора 1-го и адаптирует свою стратегию в соответствии с этим исходом.
Таким образом, оптимальные стратегии игроков такие: 1-й игрок
применяет стратегию 1–2 с .7404,0,3476,0 ≈γ≈β Узнав об исходе выбора
1-го игрока, 2-й игрок применяет стратегию 1–2. Параметры стратегии
приведены в табл. 1.
Таблица 1
Исход β γ
1 1 / e 1
2 0,3479 3 / 4
3 0,3470 2 / 3
2. Симметричная игра
Пусть игроки осуществляют просмотр независимо друг от друга, т.е.
исход просмотра каждого из игроков держится в тайне от другого до момента
сопоставления исходов. Найдем пару равновесных стратегий методом
нащупывания по Курно.
Пусть 1-й игрок применил некоторую стратегию, при которой исходы
1 и 2 реализуются с вероятностями 21, qq соответственно, а второй игрок
противопоставил стратегию, при которой эти исходы реализуются с
вероятностями 21, rr . Тогда выигрыш второго игрока составляет
( ) ( )212
2
1
12212112 1
11)()1()1( qqr
q
qrqqqrqrq +−
+
−
++=+−−++ .
Таким образом, наилучшим ответом второго игрока будет применение
стратегии 1–2 при
2
1
1
1
q
q
+
−
=α .
Положим .5,01 =α Пусть iβ — корень уравнения (3), соответствующий
iα .
Обозначим ( ),,1
)(
1 ii
i gq βα= ( ),,2
)(
2 ii
i gq βα= согласно (4). Положим
)(
2
)(
1
1
1
1
i
i
i
q
q
+
−
=α + .
При итеративном применении процедуры нащупывания по Курно
получаются такие предельные значения:
2161,0,3533,0,7423,0,3467,0,5318,0 21 ≈≈≈γ≈β≈α pp .
Заметим, что найденные значения γβα ,, близки к соответствующим
значениям для несимметричной игры.
Данная стратегия дает нулевой средний выигрыш против такой же
стратегии и положительный выигрыш против любой другой стратегии.
10
Вторая игровая ситуация —
борьба за выбор лучшего объекта при выборе из одного множества
Пусть теперь игроки осуществляют просмотр на одном множестве
элементов. При этом каждый объект просматривается обоими игроками
одновременно при следующих условиях. Как и в [1], каждый из игроков
имеет возможность выбора — останавливаться на текущем объекте или
продолжать просмотр. И точно также отсутствует возможность возврата к
ранее просмотренным объектам. Если на одном из объектов желает
остановиться только один из игроков, то он останавливается на нем и
выбывает из игры, другой игрок продолжает просмотр. Если же на некотором
объекте желают остановиться оба игрока, то право остановки разыгрывается
между ними жеребьевкой:
1-й/2-й игрок выигрывает жребий с вероятностью α−α 1/
соответственно. Выигравший жребий останавливается и выбывает из игры,
проигравший продолжает просмотр.
В [5] была рассмотрена задача, в которой целью каждого из игроков
является выбор наилучшего объекта с максимальной вероятностью. Далее
рассмотрим задачу, аналогичную по постановке, рассмотренной в [5]. Пусть
теперь целью каждого из игроков является выбор объекта, лучшего, чем тот,
который выберет противник (в этом случае игрок выигрывает). Оказывается,
что такое, на первый взгляд, несущественное изменение постановки задачи
приводит к радикальному изменению стратегий игроков.
В [1] было показано, что если изначально все перестановки элементов
naa ,...,1 равновероятны, то независимо от взаимного расположения
элементов 11,..., −kaa ранг элемента ka в последовательности kaa ,...,1 с
равными вероятностями k/1 принимает одно из возможных значений k,...,1
(где ранг 1 означает, что ka — наилучший, k — наихудший среди kaa ,...,1 ).
Тогда, согласно формуле произведения вероятностей, вероятность того, что
объект является i-м по качеству среди n при условии, что он является i-м по
качеству среди k (или, другими словами, вероятность того, что в
последовательности nk aa ,...,1+ не встретится ни одного объекта лучше ka ),
равна
.
)1)...(1(
)1)...(1(
!)!(
!)!(...
2
2
1
1),(
+−−
+−−
=
−
−
=
−
××
+
−+
×
+
−+
=
innn
ikkk
nik
kin
n
in
k
ik
k
ikikp (5)
Рассмотрим частный случай .1=α Тогда второй игрок сможет
остановиться на очередном элементе, если этого не захотел сделать первый
игрок.
Текущее состояние игры характеризуется парой ),,( ik где k — номер
просматриваемого элемента, i — его ранг среди k просмотренных.
Если один из игроков останавливается на некотором элементе, то об этом
становится известно другому игроку и его дальнейшая стратегия становится
тривиальной — остановиться на первом элементе лучше ka , если таковой
встретится. При этом с вероятностью ),( ikp такой элемент не встретится и
выигрывает игрок, сделавший остановку и с дополнительной вероятностью
— встретится и выигрывает его противник, продолживший просмотр.
Поэтому игру можно переформулировать таким образом: если остановку
11
сделал один из игроков, то он получает выигрыш 1),(2),( −= ikpikf
(эта величина может быть и отрицательной), его противник получает
выигрыш ),( ikf− и на этом игра заканчивается. Если остановку не сделал ни
один из игроков, то игра продолжается и с появлением элемента 1+ka с
равными вероятностями
1
1
+k
система переходит в одно из состояний
1,1),,1( +=+ kjjk .
При nk = согласно формуле (5) ,1),( =inp следовательно, 1),( =inf
при всех ni ,1= . По сути это означает, что если до n-го шага оба игрока не
остановились на каких-либо предыдущих элементах, то на n-м шаге первый
игрок выбирает na (который может иметь какой угодно ранг) и выигрывает у
второго игрока, не выбравшего никакого элемента.
Найдем оптимальные стратегии игроков. Стратегии будем описывать
множествами 21
~,~ AA , где 21
~,~ AA — подмножества },1,,1|),{( ninkik == . При
этом 2;1,~),( =∈ jAik j означает, что j-й игрок намерен остановиться на
элементе ),( ik , если будет такая возможность.
Назовем ценой игры ),( ikv средний выигрыш первого игрока при
условии, что игра находится в состоянии ),( ik и в дальнейшем игроки
придерживаются своих оптимальных стратегий. Обозначим
∑
=
=
k
i
ikv
k
kV
1
),(
1
)( — средний выигрыш на шаге k (усредненный по всем
состояниям )).,( ikv Чтобы найти оптимальные стратегии игроков, проанали-
зируем игру методом динамического программирования, двигаясь по
множеству состояний в обратном порядке, начиная с последнего шага.
Очевидно, что niinv ,1,1),( == и, таким образом, 1)( =nV .
Пусть определено )1( +kV , тогда
))).1(),,(min(),,(max(),( +−= kVikfikfikv (6)
Действительно, пусть игра находится в состоянии ).,( ik Тогда первый
игрок имеет альтернативу – останавливаться или нет. Если первый игрок
остановился, то его выигрыш составил ),,( ikf если нет, то право выбора,
останавливаться или нет, перешло ко второму игроку, т.е. он может
остановиться (и тогда выигрыш первого игрока составит ),( ikf− или не
остановиться (тогда игра продолжается и ожидаемый выигрыш первого
игрока равен )).1( +kV Поскольку второй игрок стремится минимизировать
выигрыш первого, то он выбирает минимум из этих двух величин. Поскольку
первый игрок понимает это и стремится максимизировать свой выигрыш, то
он выберет максимум из ),( ikf и )).1(),,(min( +− kVikf Покажем, что
0)( >kV для всех k. Действительно, .01)( >=nV Если ,0)1( >+kV то
согласно (2) все 0),( ≥ikv и есть такие, которые строго больше нуля, поэтому
.0)( >kV
12
Будем полагать, что ,~),( 1Aik ∈ если )).1(),,(min(),( +−> kVikfikf
Поскольку 0)1( >+kV , то последнее условие эквивалентно .0),( >ikf Далее,
,~),( 2Aik ∈ если )1(),()1(),( +−≥⇒+≤− kVikfkVikf , поэтому .~~
12 AA ⊃
Рассмотрим случай .1
2
1
<α< Тогда каждый из игроков имеет
альтернативу — останавливаться или нет, так что в состоянии (k, i) выигрыш
первого игрока описывается матричной игрой (табл. 2).
Пусть .0),( >ikf Тогда ),(),()12(),( ikfikfikf −>−α> и
),1(),( +<− kVikf таким образом, игра разрешима по доминированию –
обоим игрокам выгодно останавливаться, и, таким образом,
).,(),(,~),(,~),( 21 ikfikVAikAik =∈∈
Таблица 2
2-й игрок
1-й игрок
останавливаться не останавливаться
останавливаться ),()12( ikf−α ),( ikf
не останавливаться ),( ikf− )1( +kV
Пусть .0),( ≤ikf Тогда ),(),()12(),( ikfikfikf −≤−α≤ и
)1(),( +< kVikf . В этом случае стратегия первого игрока «останавливаться»
доминируется стратегией «не останавливаться», значит 1
~),( Aik ∉ . Если при
этом ),1(),( +≤− kVikf то оптимальная стратегия второго игрока –
останавливаться, и, таким образом, 2
~),( Aik ∈ и ),,(),( ikfikv −= а если
)1(),( +>− kVikf , то не останавливаться и 2),( Гik ∉ и )1(),( += kVikv .
Объединяя, имеем:
{ } { })1(),(|),(~,0),(|),(~
1 +−≥=>= kVikfikAikfikA ,
≤+−
>−α
=
;0),()),1(),,(min(
,0),(),,()12(
),(
ikfkVikf
ikfikf
ikv .),(
1
)(
1
∑
=
=
k
i
ikv
k
kV
Таким образом, средний выигрыш первого игрока в самом начале, при
условии, что оба игрока придерживаются своих оптимальных стратегий,
равен )1(VU = , а вероятность выигрыша равна
2
1)1( +
=
Vp .
Определим начальные условия. Если оба игрока не сделали
своего выбора до n-го (т.е. самого последнего) шага игры, то выигрывает
игрок, которому достался последний элемент, независимо от его
ранга, поэтому оба игрока должны на него претендовать. Следовательно,
при nk = для всех ni ,1= справедливы соотношения:
21
~),(,~),(,12),(,1),( AinAininvinf ∈∈−α== .
Рассмотрим случай .
2
1
=α Тогда данная антагонистическая игра
становится симметричной, и цена такой игры равна нулю. Заметим, что
стратегия { }0),(|),(~
>= ikfikA обеспечивает каждому игроку
13
неотрицательный выигрыш против любой стратегии противника, и,
разумеется, нулевой выигрыш против такой же стратегии.
Для некоторых значений n и α были сделаны расчеты в пакете Mathcad. В
табл. 3 приведены стратегии игроков при ,1;
4
3;
2
1,20 =α=n в табл. 4 —
значения U при различных значениях n и α.
Таблица 3
1/2,~;~
21 =αAA
k i
11–14 1
15–16 1–2
17 1–3
18 1–5
19 1–9
4/3,~
2 =αA
k i
9–12 1
13–14 2
15–16 3
17 5
18 7
19 15
1,~
2 =αA
k i
8–11 1
12–14 1–2
15 3
16 4
17 6
18 9
19 1–19
Таблица 4
α
n
1 / 2 5 / 8 3 / 4 7 / 8 1
10 0 0,087 0,154 0,206 0,238
100 0 0,077 0,136 0,183 0,222
1000 0 0,073 0,131 0,178 0,218
Выводы. При всех
∈α 1;
2
1 оптимальная стратегия первого игрока
остается неизменной: { },0),(|),(~
1 >= ikfikA а стратегия второго игрока
зависит от α и может быть найдена по приведенным выше формулам.
Можно показать, что 2
~A сужается с ростом α от
2
1 до 1, т.е. )(~)(~
22 β⊃α AA
при 1
2
1
≤β<α≤ .
Рассмотренные задачи являются лишь одной из многочисленных
возможных игровых ситуаций, возникающих при рассмотрении задачи
оптимального выбора. К сожалению, приходится прийти к выводу, что нет
общей методики решения задач данного типа — для каждой задачи требуется
индивидуальный подход. Неизменной остается лишь использование
марковского свойства игровых ситуаций и концепции сложного
рационального поведения игроков.
1. Дынкин Е.Б., Юшкевич А.А. Теоремы и задачи о процессах Маркова. — Москва: Наука,
1976. — С. 91–102.
2. Гусейн-Заде С. М. Задача выбора и оптимальное правило остановки
последовательности независимых испытаний // Теория вероятности и ее применение.
— 1966. — 11, № 3. — С. 534–537.
3. Мазалов В.В. Математическая теория игр и приложения. — СПб.: Лань, 2010. — 446 с.
4. Мазалов В.В. Игровые моменты остановки. — Новосибирск: Наука, 1987. — 191 с.
5. Доценко С.И. Задача выбора наилучшего объекта как игра двух лиц // Кибернетика и
Вычислительная техника. — 2011. — Вып. 164, — С. 43–53.
Киевский национальный
университет имени Тараса Шевченко Получено 11.06.2012
|
| id | nasplib_isofts_kiev_ua-123456789-45829 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0452-9910 |
| language | Russian |
| last_indexed | 2025-12-07T15:29:53Z |
| publishDate | 2012 |
| publisher | Міжнародний науково-навчальний центр інформаційних технологій і систем НАН України та МОН України |
| record_format | dspace |
| spelling | Доценко, С.И. 2013-06-18T17:42:13Z 2013-06-18T17:42:13Z 2012 Игровые ситуации в модифицированной задаче оптимального выбора / С.И. Доценко // Кибернетика и вычисл. техника. — 2012. — Вип. 168. — С. 3-13. — Бібліогр.: 5 назв. — рос. 0452-9910 https://nasplib.isofts.kiev.ua/handle/123456789/45829 681.5 Для задачи оптимального выбора наилучшего или второго по качеству объекта рассмотрена игровая ситуация, в которой участвуют два игрока, осуществляющие свой выбор на двух различных множествах объектов. Данная игровая ситуация рассмотрена в двух модификациях в зависимости от информации, доступной игрокам. В обеих ситуациях найдены оптимальные стратегии игроков, обеспечивающие равновесие по Нэшу. Также рассмотрена альтернативная игровая ситуация, в которой два игрока осуществляют просмотр на одном множестве объектов и целью каждого из них является выбор объекта, лучшего чем у противника. Для задачі оптимального вибору найкращого або другого за якістю об’єкту розглянуто ігрову ситуацію, в якій беруть участь два гравці, які здійснюють свій вибір на двох різних множинах об’єктів. Гравці порівнюють вибрані об’єкти. Дану ігрову ситуацію розглянуто в двох модифікаціях, в залежності від інформації, яка є доступною гравцям на момент прийняття ними рішення. В обох ситуаціях знайдено оптимальні стратегії гравців, що забезпечують рівновагу за Нешем. Також розглянуто альтернативну ігрову ситуацію, в якій два гравці проглядають об’єкти та здійснюють свій вибір на одній множині елементів. Метою кожного гравця є вибір об’єкту кращого, ніж у суперника. The optimal choice problem (also known as “secretary problem”) is one of the classic case in point in operations research field (namely stochastic optimization). The origin of this problem was just a puzzle, introduced by Martin Gardner. It turned out afterward that the “secretary problem” and its numerous modifications are good examples in both optimal stopping Markov chains and game theory. The basic principle of multisteps games is so called complex rational behavior concept: “I behave optimally. I know that my rival behaves optimally. I know that he knows that I behave optimally, etc.”. ru Міжнародний науково-навчальний центр інформаційних технологій і систем НАН України та МОН України Кибернетика и вычислительная техника Сложные системы управления Игровые ситуации в модифицированной задаче оптимального выбора Ігрові ситуації в модифікованій задачі оптимального вибору Game situations in the modified secretary problem Article published earlier |
| spellingShingle | Игровые ситуации в модифицированной задаче оптимального выбора Доценко, С.И. Сложные системы управления |
| title | Игровые ситуации в модифицированной задаче оптимального выбора |
| title_alt | Ігрові ситуації в модифікованій задачі оптимального вибору Game situations in the modified secretary problem |
| title_full | Игровые ситуации в модифицированной задаче оптимального выбора |
| title_fullStr | Игровые ситуации в модифицированной задаче оптимального выбора |
| title_full_unstemmed | Игровые ситуации в модифицированной задаче оптимального выбора |
| title_short | Игровые ситуации в модифицированной задаче оптимального выбора |
| title_sort | игровые ситуации в модифицированной задаче оптимального выбора |
| topic | Сложные системы управления |
| topic_facet | Сложные системы управления |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/45829 |
| work_keys_str_mv | AT docenkosi igrovyesituaciivmodificirovannoizadačeoptimalʹnogovybora AT docenkosi ígrovísituacíívmodifíkovaníizadačíoptimalʹnogoviboru AT docenkosi gamesituationsinthemodifiedsecretaryproblem |