О ситуациях равновесия в задаче поочередного преследования
Рассматривается задача поочередного преследования одним преследователем двух убегающих в предположении, что убегающие могут выбирать скорость убегания между нулем и заданной величиной u. Для разных соотношений скоростей преследователя и убегающих исследованы ситуации равновесия по Нэшу. Розглядаєтьс...
Збережено в:
| Опубліковано в: : | Теорія оптимальних рішень |
|---|---|
| Дата: | 2009 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2009
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/46633 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | О ситуациях равновесия в задаче поочередного преследования / С.И. Доценко // Теорія оптимальних рішень: Зб. наук. пр. — 2009. — № 8. — С. 16-21. — Бібліогр.: 2 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859778981265408000 |
|---|---|
| author | Доценко, С.И. |
| author_facet | Доценко, С.И. |
| citation_txt | О ситуациях равновесия в задаче поочередного преследования / С.И. Доценко // Теорія оптимальних рішень: Зб. наук. пр. — 2009. — № 8. — С. 16-21. — Бібліогр.: 2 назв. — рос. |
| collection | DSpace DC |
| container_title | Теорія оптимальних рішень |
| description | Рассматривается задача поочередного преследования одним преследователем двух убегающих в предположении, что убегающие могут выбирать скорость убегания между нулем и заданной величиной u. Для разных соотношений скоростей преследователя и убегающих исследованы ситуации равновесия по Нэшу.
Розглядається задача почергового переслідування одним переслідувачем двох утікачів за припущення, що втікачі можуть вибирати швидкість утікання між нулем та заданою величиною u. Для різних співвідношень швидкостей переслідувача та втікачів досліджено ситуації рівноваги за Нешем.
The problem of successive pursuit with one pursuer and two escapers is considered. It is assumed that each escaper can choose his speed between zero and given value u. For different relations between pursuer and escaper Nash equilibrium situations are considered.
|
| first_indexed | 2025-12-02T09:35:41Z |
| format | Article |
| fulltext |
Теорія оптимальних рішень. 2009, № 8 16
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Рассматривается задача по-
очередного преследования одним
преследователем двух убегающих
в предположении, что убегающие
могут выбирать скорость убега-
ния между нулем и заданой вели-
чиной u. Для разных соотношений
скоростей преследователя и убе-
гающих исследованы ситуации
равновесия по Нэшу.
С.И. Доценко, 2009
ÓÄÊ 519.8
Ñ.È. ÄÎÖÅÍÊÎ
Î ÑÈÒÓÀÖÈßÕ ÐÀÂÍÎÂÅÑÈß
 ÇÀÄÀ×Å
ÏÎÎ×ÅÐÅÄÍÎÃÎ ÏÐÅÑËÅÄÎÂÀÍÈß
Введение. В данной работе рассматривается
задача поочередного преследования одним
преследователем (далее Р) двух убегающих
(E1, E2) при следующих предположениях.
1. В начальный момент времени Р и оба
убегающих находятся на одной прямой, при-
чем Р находится между убегающими.
2. Каждый из убегающих стремится мак-
симизировать время собственной поимки
и безразличен к времени поимки другого
убегающего. Р стремится минимизировать
суммарное время поимки обоих убегающих.
3. Игроки придерживаются сложного ра-
ционального поведения, т. е. каждый игрок
знает структуру игры, и что ее знают осталь-
ные, оптимизирует собственный критерий
(п. 2) и полагает, что другие также оптими-
зируют свои критерии.
Рассмотрены такие случаи: 1) скорость P
равна v, скорости E v1, v2 соответственно,
причем 1 2max( , )v v v> . Данный случай до-
статочно простой, не представляет интереса
и носит вспомогательный характер при рас-
смотрении второго случая; 2) в начальный
момент времени P находится посредине меж-
ду убегающими. При этом перед началом
преследования каждый из убегающих при-
нимает решение – оставаться все время на
месте (быть неподвижным) или убегать с за-
даной скоростью u, где u < v. В данном слу-
чае между убегающими возникает би-
матричная игра, причем структура точек
равновесия по Нэшу различна при разных
значениях u ⁄ v.
О СИТУАЦИЯХ РАВНОВЕСИЯ В ЗАДАЧЕ ПООЧЕРЕДНОГО ПРЕСЛЕДОВАНИЯ
Теорія оптимальних рішень. 2009, № 8 17
Первый случай. Скорость P равна v, скорости Е1, Е2 равны v1, v2 соответст-
венно, причем
1 2max( , )v v v> . Рассмотрим логику E. Пусть P вначале погонит-
ся за мной, тогда для максимизации времени жизни нужно убегать в направле-
нии «от него». Пусть P вначале погонится за вторым E, который также будет
убегать в направлении “от него”. Чтобы в момент поимки другого E оказаться
от P на максимальном расстоянии, нужно опять убегать в направлении «от P».
Логика P такова: вначале нужно догнать одного из E, потом другого. Легко по-
казать, что стратегии, когда P гонится за одним из Е, затем не достигнув его и
«передумав», за другим, не являются оптимальными для Р. Таким образом, по-
иск оптимальной стратегии преследователем сводится к перебору двух вариан-
тов – кого из двух убегающих Е1 или Е2, преследовать первым. При соблюдении
всеми игроками рациональных стратегий, игра не выходит за пределы прямой.
Пусть Р вначале гонится за Е1, затем за Е2. Тогда время поимки Е1 равно
1
11
1
vv
s
T
−
= . При этом в момент поимки Е1 расстояние между P и Е2 будет рав-
но 1 1 2 1 1 2
1 1 2 2 1
1
( ) ( )v v s v v s
r vT s v T
v v
+ + −
= + + =
−
, для поимки E2 понадобится еще
время
))((
)()(
21
2112
2
12
1
vvvv
svvsvv
vv
r
T
−−
−++
=
−
= . Таким образом суммарное время
поимки составляет:
1 2 1 1 2
1 1 1
1 2
2 ( )
.
( )( )
vs v v s
T T T
v v v v
+ −
= + =
− −
(1)
В силу симметрии задачи, суммарное время поимки в случае, когда вначале
преследуют E2, получаем из данной формулы заменой s1↔s2, v1↔v2, и таким
образом
))((
)(2
21
122
2
vvvv
svvvs
T
−−
−+
= . (2)
Неравенство 21 TT ∨ равносильно неравенству 2112 )()( svvsvv +∨+ .
Пусть 21 vv = , тогда 21 TT ∨ равносильно 21 ss ∨ и P вначале будет пресле-
довать ближайшего из Е.
Пусть 21 ss = , тогда 21 TT ∨ равносильно 12 vv ∨ и P вначале будет пресле-
довать Е с большей скоростью.
Второй случай. Пусть в начальный момент времени P находится посредине
между убегающими. При этом перед началом преследования каждый из убе-
гающих принимает решение – оставаться все время на месте (быть неподвиж-
ным) или убегать с заданой скоростью u, где vu < . Если оба Е придерживаются
С.И. ДОЦЕНКО
Теорія оптимальних рішень. 2009, № 8 18
одинаковой стратегии (стоять-стоять или бежать-бежать), то Р случайным
образом с вероятностью ½ выбирает первую жертву. Если один из Е стоит,
а другой убегает, то Р выгоднее преследовать убегающего (поскольку предпола-
гается рациональное поведение всех игроков, то считается, что так и будет).
Таким образом, у Е1 и у Е2 возникает дилемма. С одной стороны, очевидно, убе-
гать лучше, чем стоять, с другой стороны, лучше быть второй жертвой, чем пер-
вой (а выбор стратегии “стоять” способствует этому).
Данная ситуация описывается биматричной игрой в нормальной форме.
Пусть Е1 выбирает строки, Е2 – столбцы, 1 соответствует выбору “стоять”,
2 – “убегать”, А, В – матрицы времени жизни Е1, Е2 соответственно.Тогда
−
−
−
−
−
==
−
−
−
−
−
=
22 )(
)2(
)(
)3(
2
,
)(
)2(
)(
)3(2
uv
uvs
uvv
uvs
uv
s
v
s
AB
uv
uvs
uv
s
uvv
uvs
v
s
A
T
. (3)
Данная игра разрешима по доминированию при
( ) ( )11 21 12 22 11 21 12 22, ,a a a a a a a a≥ ≥ ∨ ≤ ≤ , иначе игра имеет решение в сме-
шанных стратегиях.
Неравенство 2111 aa ≥ сводится к
2
v
u ≤ , а 2221 aa ≥ – к 03 22
≥+− vuvu ,
откуда .382,0
2
53
vvu ≈
−
≤
Таким образом, если vu
2
53 −
≤ , то игра разрешима в чистых стратегиях,
и решением игры является “стоять-стоять”.
Если
2
v
u ≥ , то игра имеет решение по доминированию “бежать-бежать”.
Если
22
53 v
uv <<
−
, то тогда a11 > a21, a12 < a22, b11 < b12, b21 > b22 и игра
имеет две точки равновесия в чистых стратегиях “стоять-стоять” и “бежать-
бежать”. При этом точка “бежать-бежать” доминирует по Паретто точку
“стоять-стоять”. Кроме того, в данной ситуации существует равновесие в чисто
смешанных стратегиях, где вероятности выбора стратегий игроками находятся
по формулам
О СИТУАЦИЯХ РАВНОВЕСИЯ В ЗАДАЧЕ ПООЧЕРЕДНОГО ПРЕСЛЕДОВАНИЯ
Теорія оптимальних рішень. 2009, № 8 19
xy
x
xy
y
JAJ
JA
x
JBJ
BJ
x
1
1
*
21
1
*
1 ,
−
−
−
−
== (4)
а выигрыши игроков составляют
1 21 1
1 1
, ,
y x y xJ A J J B J
− −
τ = τ = (5)
где (1,...,1) , (1,...,1).T
x yJ J= =
Для биматричной игры 2×2 данные формулы приобретают упрощенный вид
−−+
−
−−+
−
=
21122211
1211
21122211
2122*
1 ;
bbbb
bb
bbbb
bb
x ,
−−+
−
−−+
−
=
21122211
2111
21122211
1222*
2 ;
aaaa
aa
aaaa
aa
x ,
22122211
2
22122211
1
)det(
,
)det(
bbbb
B
aaaa
A
−−+
=
−−+
= ττ . (6)
Обоснование данных формул, а также детальный анализ биматричной игры
2×2 см, например, в [1, с. 66] или [2, с. 217]. Отметим здесь лишь то, что данные
формулы применимы лишь для случая, когда биматричная игра неразрешима по
доминированию, иначе решение не будет иметь физического смысла (вычислен-
ные вероятности стратегий будут меньше 0 или больше 1). Обратим внимание
на то, что формально стратегии зависят только от “чужой”, а выигрыш от при-
менения этих стратегий – от “своей” матрицы времени жизни.
В данном случае
[ ]22
21222 3
)(
uuvv
uvv
s
aa −+−
−
=− ,
2 2
11 21 2
2
3 2
( ) ( )
v u s
a a s v uv u
v v u v v u
−
− = = − + − −
,
2
2
12212211
)( uvv
su
aaaa
−
=−−+ ,
+−−+−
=
2
22
2
22
*
1
23
;
3
u
uuvv
u
uuvv
x ,
21
)(
u
uvs −
=τ . (7)
Поскольку игра симметричная, то * *
2 1 2 1,x x= τ = τ .
С.И. ДОЦЕНКО
Теорія оптимальних рішень. 2009, № 8 20
Данная точка равновесия как бы искуственная, т. е. она существует и удов-
летворяет всем уловиям точки равновесия, но вряд ли игроки будут придержи-
ваться таких смешаных стратегий.
Рассмотрим такую несимметричную игру. Пусть теперь Р имеет “антипа-
тию” к Е1, т. е. в симметричных ситуациях “стоять-стоять” и “бежать-бежать”
P вначале будет преследовать Е1. Если же E1 стоит, а Е2 убегает, то P будет вна-
чале преследовать Е2 (предполагается, что собственные интересы выше “антипа-
тии”). Данная ситуация описывается биматричной игрой
2
(3 ) 3
( )
, .
(3 ) (3 )
( ) ( )
s s v u s s
v v v u v v u
A B
s v u s v us s
v v u v uv u v u
−
− −
= =
− −
− −− −
(8)
Заметим, что при всех допустимых значениях u справедливы неравенства
a11 < a21, a12 > a22, b21 < b22 и таким образом поведение точек равновесия зависит
лишь от соотношения b11 и b12.
Если vu
3
2
> , то b12 > b11 и игра разрешима по доминированию “стоять-
бежать”.
Если vu
3
2
< , то b11 > b12 и игра не имеет точек равновесия в чистых страте-
гиях, а единственное равновесие в смешаных стратегиях, которое находится по
формулам (6).
( )
2
22 21 2
(3 )
,
s uv u
b b
v u v
−
− =
−
2 2
11 12 2
(3 5 2 )
,
( )
s u uv v
b b
v u v
− +
− =
−
( )
vuv
vuvus
bbbb
2
22
12212211
)(
2
−
+−
=−−+ ;
vuv
uvs
aa
)(
)2(
1222
−
+−
=− ,
vuv
su
aa
)(
2111
−
−=− ,
vuv
sv
aaaa
)(
2
12212211
−
−=−−+ (9)
отсюда
+−
+−
+−
−
=
)(2
253
;
)(2
3
22
22
22
2
*
1
vuvu
vuvu
vuvu
uuv
x ,
−
=
v
u
v
uv
x
2
;
2
2*
2 . (10)
О СИТУАЦИЯХ РАВНОВЕСИЯ В ЗАДАЧЕ ПООЧЕРЕДНОГО ПРЕСЛЕДОВАНИЯ
Теорія оптимальних рішень. 2009, № 8 21
Данная точка равновесия в чисто смешаных стратегиях также искусственна
хотя бы потому, что для достижения выигрыша
uv
s
−
=1τ для Е1 нет необходи-
мости вычислять и придерживаться *
1x , достаточно просто придерживаться
стратегии “бежать”.
С.І. Доценко
ПРО СИТУАЦІЇ РІВНОВАГИ У ЗАДАЧІ ПОЧЕРГОВОГО ПЕРЕСЛІДУВАННЯ
Розглядається задача почергового переслідування одним переслідувачем двох утікачів за
припущення, що втікачі можуть вибирати швидкість утікання між нулем та заданою
величиною u. Для різних співвідношень швидкостей переслідувача та втікачів досліджено
ситуації рівноваги за Нешем.
S.I. Dotsenko
ON NASH EQUILIBRIUM IS SUCCESSIVE PURSUIT PROBLEM
The problem of successive pursuit with one pursuer and two escapers is considered. It is assumed<
that each escaper can choose his speed between zero and given value u. For different relations be-
tween pursuer and escaper Nash equilibrium situations are considered.
1. Доценко С.І. Теорія ігор. Навч. посібник, 2008. – 84 с. Розміщений на сайті факультету
кібернетики КНУ, www.unicyb.kiev.ua
2. Мащенко С.О., Волошин О.Ф. Теорія прийняття рішень. Навч. посібник. – Київський
національний університет імені Тараса Шевченка, 2006 . – 303 c.
Получено 23.03.2009
|
| id | nasplib_isofts_kiev_ua-123456789-46633 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0013 |
| language | Russian |
| last_indexed | 2025-12-02T09:35:41Z |
| publishDate | 2009 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Доценко, С.И. 2013-07-04T18:24:32Z 2013-07-04T18:24:32Z 2009 О ситуациях равновесия в задаче поочередного преследования / С.И. Доценко // Теорія оптимальних рішень: Зб. наук. пр. — 2009. — № 8. — С. 16-21. — Бібліогр.: 2 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/46633 519.8 Рассматривается задача поочередного преследования одним преследователем двух убегающих в предположении, что убегающие могут выбирать скорость убегания между нулем и заданной величиной u. Для разных соотношений скоростей преследователя и убегающих исследованы ситуации равновесия по Нэшу. Розглядається задача почергового переслідування одним переслідувачем двох утікачів за припущення, що втікачі можуть вибирати швидкість утікання між нулем та заданою величиною u. Для різних співвідношень швидкостей переслідувача та втікачів досліджено ситуації рівноваги за Нешем. The problem of successive pursuit with one pursuer and two escapers is considered. It is assumed that each escaper can choose his speed between zero and given value u. For different relations between pursuer and escaper Nash equilibrium situations are considered. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень О ситуациях равновесия в задаче поочередного преследования Про ситуації рівноваги у задачі почергового переслідування On Nash equilibrium is successive pursuit problem Article published earlier |
| spellingShingle | О ситуациях равновесия в задаче поочередного преследования Доценко, С.И. |
| title | О ситуациях равновесия в задаче поочередного преследования |
| title_alt | Про ситуації рівноваги у задачі почергового переслідування On Nash equilibrium is successive pursuit problem |
| title_full | О ситуациях равновесия в задаче поочередного преследования |
| title_fullStr | О ситуациях равновесия в задаче поочередного преследования |
| title_full_unstemmed | О ситуациях равновесия в задаче поочередного преследования |
| title_short | О ситуациях равновесия в задаче поочередного преследования |
| title_sort | о ситуациях равновесия в задаче поочередного преследования |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/46633 |
| work_keys_str_mv | AT docenkosi osituaciâhravnovesiâvzadačepoočerednogopresledovaniâ AT docenkosi prosituacíírívnovagiuzadačípočergovogopereslíduvannâ AT docenkosi onnashequilibriumissuccessivepursuitproblem |