Порівняння стратегій пари опонентів у задачі “захоплення“ території
У роботi теорiя динамiчних систем конфлiкту застосовується до моделi, яка описує конфлiктний перерозподiл ресурсного простору (територiї) мiж альтернативними сторонами (парою опонентiв). В роботе теория динамичных систем конфликта применяется в модели, которая описывает конфликтное перераспределение...
Saved in:
| Published in: | Доповіді НАН України |
|---|---|
| Date: | 2016 |
| Main Author: | |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Видавничий дім "Академперіодика" НАН України
2016
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/104751 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Порівняння стратегій пари опонентів у задачі “захоплення“ території / І.В. Веригіна // Доповіді Національної академії наук України. — 2016. — № 5. — С. 7-12. — Бібліогр.: 4 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860161068565790720 |
|---|---|
| author | Веригіна, І.В. |
| author_facet | Веригіна, І.В. |
| citation_txt | Порівняння стратегій пари опонентів у задачі “захоплення“ території / І.В. Веригіна // Доповіді Національної академії наук України. — 2016. — № 5. — С. 7-12. — Бібліогр.: 4 назв. — укр. |
| collection | DSpace DC |
| container_title | Доповіді НАН України |
| description | У роботi теорiя динамiчних систем конфлiкту застосовується до моделi, яка описує конфлiктний перерозподiл ресурсного простору (територiї) мiж альтернативними сторонами (парою опонентiв).
В роботе теория динамичных систем конфликта применяется в модели, которая описывает конфликтное перераспределение ресурсного пространства (территории) между альтернативными сторонами (парой оппонентов).
The theory of conflict dynamical systems is applied to a model that discribes the conflicting redistribution
of a resource space (territory) between adversaries (a pair of opponents).
|
| first_indexed | 2025-12-07T17:54:58Z |
| format | Article |
| fulltext |
оповiдi
НАЦIОНАЛЬНОЇ
АКАДЕМIЇ НАУК
УКРАЇНИ
5 • 2016
МАТЕМАТИКА
http://dx.doi.org/10.15407/dopovidi2016.05.007
УДК 517.9
I. В. Веригiна
НТУ України “Київський полiтехнiчний iнститут”
E-mail: veringa@i.ua
Порiвняння стратегiй пари опонентiв у задачi
“захоплення“ територiї
(Представлено академiком НАН України I.О. Луковським)
У роботi теорiя динамiчних систем конфлiкту застосовується до моделi, яка опи-
сує конфлiктний перерозподiл ресурсного простору (територiї) мiж альтернативними
сторонами (парою опонентiв).
Ключовi слова: динамiчна система конфлiкту, iмовiрнiсна мiра, самоподiбна мiра, рiв-
новажний стан, конфлiктний перерозподiл ресурсного простору.
1. Постановка задачi. Розглянемо модель системи з двох протидiючих сторiн, назвемо їх
опонентами A та B, якi взаємодiють (конфлiктують) на спiльному ресурсному просторi Ω.
Вважаємо, що простором конфлiкту є вiдрiзок Ω = [0, 1]. Нехай простiр конфлiкту Ω =
= [0, 1] є структурованим, тобто подрiбненим на регiони Ω =
2∪
i1,...,ik=1
Ωi1...ik , k = 1, 2, . . .
(k — крок подрiбнення). При цьому мiра Лебега λ регiону Ωi1...ik визначається за формулою
λ(Ωi1...ik) = |Ωi1...ik | = qm1 qk−m
2 , m ∈ {0, 1, . . . , k},
де q1 + q2 = 1, q1, q2 > 0, а m — кiлькiсть iндексiв в Ωi1...ik , якi дорiвнюють 1, тобто
il : il = 1, 1 6 l 6 k.
Розподiл присутностi опонентiв A та B на Ω задається кусково-рiвномiрними ймовiрнi-
сними мiрами µ та ν вiдповiдно:
µ(Ωi1...ik) = pi1...ik , ν(Ωi1...ik) = ri1...ik ,
2∑
i1,...,ik=1
pi1...ik =
2∑
i1,...,ik=1
ri1...ik = 1.
© I. В. Веригiна, 2016
ISSN 1025-6415 Доп. НАН України, 2016, №5 7
Згiдно з теорiєю динамiчних систем конфлiкту (див. [1–3]), якщо pi1...ik > ri1...ik , то ево-
люцiя моделi вiдбувається таким чином, що у результатi конфлiктної взаємодiї мiра прису-
тностi опонента А у регiонi Ωi1...ik наближається до деякого ненульового значення, а мiра
присутностi опонента В у цьому ж регiонi стає нульовою. Тобто в регiонi Ωi1...ik “перема-
гає” опонент А. Говоримо, регiон Ωi1...ik буде “захоплений” або “контрольований” опонентом
А. Позначимо такий регiон ΩA
i1...ik
. I навпаки, якщо pi1...ik < ri1...ik , то регiон Ωi1...ik буде
“захоплений” або “контрольований“ опонентом В. Позначимо такий регiон ΩB
i1...ik
. У випад-
ку pi1...ik = ri1...ik обидва опонента в результатi конфлiктної взаємодiї з часом втрачають
свiй вплив у регiонi Ωi1...ik . Вважаємо, що такий регiон не належить жодному з опонентiв,
позначимо його ΩA=B
i1...ik
.
У цiй простiй моделi стратегiя кожного з опонентiв A, B фiксується одним числом: α, β
вiдповiдно. Нехай числа α та β такi, що 0 < α < 1, 0 < β < 1. Стартовий розподiл опонентiв
А та В на Ω задається формулами
pi1...ik = αm(1− α)k−m, ri1...ik = βm(1− β)k−m. (1)
У попереднiх дослiдженнях (див., наприклад, [3]) було показано, що, якщо на k-му кроцi
подрiбнення в регiонi Ωi1...ik “перемагає”, наприклад, опонент А, то через скiнченну кiлькiсть
крокiв подальшого подрiбнення всерединi цього регiону з’являться пiдрегiони, якi будуть
“контрольованi” опонентом В, i при продовженнi подрiбнення всерединi пiдрегiонiв, “кон-
трольованих” опонентом В, з’являться пiдрегiони, де “перемагатиме” опонент А, i так далi.
На кроцi подрiбнення k “зберемо” всi регiони, що “контролюються” А або В, та тi, де вони
втрачають свiй вплив. Мiри цих територiй позначимо: TA
k =
∑
|ΩA
i1...ik
|, TB
k =
∑
|ΩB
i1...ik
|,
TA=B
k =
∑
|ΩA=B
i1...ik
|. Нас цiкавить, як змiнюються розмiри територiй, “контрольованих” опо-
нентами А та В, якщо k необмежено зростає. Їх граничнi значення позначимо TA = lim
k→∞
TA
k ,
TB = lim
k→∞
TB
k , TA=B = lim
k→∞
TA=B
k . Доведемо, що цi границi iснують та їх можна явно об-
числити.
2. Основний результат. Нехай розподiли опонентiв у початковий момент конфлiктної
взаємодiї задано формулами (1). Не втрачаючи загальностi, вважаємо, що 0 < α < 0,5,
α < β < 1. Введемо коефiцiєнт, який пов’язує α та β i не залежить вiд k:
τ =
ln
1− α
1− β
ln
β
α
+ ln
1− α
1− β
=
ln
1− β
1− α
ln
α
β
+ ln
1− β
1− α
. (2)
Неважко бачити, що τ не перевищує 1.
Теорема. Якщо q1 > τ , то TA = 0 та TB = 1.
Якщо q1 < τ , то TA = 1 та TB = 0.
Якщо q1 = τ , то TA = TB = 1/2.
TA=B = 0.
Доведення.
1. Спочатку оцiнимо мiру територiї, на якiй опоненти рiвносильнi. Рiвнiсть pi1...ik =
= ri1...ik або αm(1 − α)k−m = βm(1 − β)k−m виконується лише, якщо
m = k
ln((1− β)/(1− α))
ln((α(1− β))/(β(1− α)))
, тобто m = kτ.
8 ISSN 1025-6415 Dopov. Nac. akad. nauk Ukr., 2016, №5
Якщо значення m = kτ цiле, то кiлькiсть регiонiв, де мiри опонентiв рiвнi, дорiвнює
Cm
k = Ckτ
k (тут Cm
k = k!/(m!(k − m)!) — число сполучень, що показує кiлькiсть способiв,
якими можна вибрати m-елементну пiдмножину з k-елементної множини). Розмiр кожного
такого регiону |Ωi1...ik | = qm1 qk−m
2 . Якщо значення m = kτ не є цiлим, то таких регiонiв не
iснує. Отже, лебегова мiра територiї, де мiри опонентiв рiвнi, визначається таким чином:
TA=B
k = Ckτ
k qkτ1 qk−kτ
2 , якщо kτ — цiле, та TA=B
k = 0, якщо kτ не є цiлим.
Для оцiнки TA=B
k застосуємо формулу Стiрлiнга, а саме: n! =
√
2πn(n/e)neθ, де n ∈ N,
|θ| < 1/(12n). Тодi для 0 < τ < 1 та, якщо kτ цiле, маємо
TA=B
k = Ckτ
k qkτ1 qk−kτ
2 =
k!
(kτ)!(k − kτ)!
qkτ1 qk−kτ
2 =
=
√
2πk
(
k
e
)k
eθ1qkτ1 qk−kτ
2
√
2πkτ
(
kτ
e
)kτ
eθ2
√
2πk(1− τ)
(
k(1− τ)
e
)k(1−τ)
eθ3
=
=
eθ√
2πkτ(1− τ)
qkτ1 (1− q1)
k−kτ
τkτ (1− τ)k−kτ
, де |θ| < 1
12k
+
1
12kτ
+
1
12k(1− τ)
.
При k → ∞ |θ| → 0, отже, eθ → 1. Розглянемо функцiю
f(τ) = ln
(
qkτ1 (1− q1)
k−kτ
τkτ (1− τ)k−kτ
)
= k(τ ln q1 + (1− τ) ln(1− q1)− τ ln τ − (1− τ) ln(1− τ)).
Помiтимо, що f(q1) = 0. За допомогою похiдної переконуємося, що τ = q1 є точкою макси-
муму функцiї f(τ). Отже, для всiх 0 < τ < 1 справджується f(τ) 6 0. Таким чином,
TA=B
k =
eθ√
2πkτ(1− τ)
ef(τ) 6 eθ√
2πkτ(1− τ)
.
Це означає, що при достатньо великих значеннях k (за умови kτ — цiле) величина TA=B
k стає
як завгодно малою. Враховуючи, що для нецiлих значень kτ TA=B
k = 0, робимо висновок,
що TA=B = lim
k→∞
TA=B
k = 0.
2. Зрозумiло, що TA
k + TB
k + TA=B
k = 1 для довiльного k = 1, 2, . . .. Тому з iснування
lim
k→∞
TA
k = TA випливає iснування lim
k→∞
TB
k = TB, а тодi TB = 1−TA. Отже, будемо оцiнювати
тiльки TA
k та доводити iснування TA.
3. Знайдемо такi m, щоб pi1...ik > ri1...ik (“виграє” опонент А). Згiдно з формулами (1)
потрiбно розв’язати нерiвнiсть
αm(1− α)k−m > βm(1− β)k−m, (3)
яка рiвносильна нерiвностi
m < k
ln((1− β)/(1− α))
ln((α(1− β))/(β(1− α)))
або m < kτ. (4)
Нехай m0 — максимальне з цiлих значень m, якi задовольняють нерiвнiсть (4), а отже
i (3). Таке m0 завжди iснує, множина розв’язкiв нерiвностi (3) непорожня, до неї завжди,
ISSN 1025-6415 Доп. НАН України, 2016, №5 9
як мiнiмум, належить m = 0. Таким чином, нерiвностi (3) та (4) виконуються для m =
= 0, 1, . . . ,m0, де kτ − 1 6 m0 < kτ .
При фiксованому m кiлькiсть регiонiв, де “виграє” А, дорiвнює Cm
k . Загальна кiлькiсть
регiонiв, де “виграє” А: NA
k = C0
k + C1
k + . . . + Cm0
k . Мiра Лебега кожного такого регiону
|ΩA
i1...ik
| = qm1 (1 − q1)
k−m = qm1 qk−m
2 . Загальна територiя, яка “контролюється” А: TA
k =
= C0
kq
0
1q
k
2+C1
kq
1
1q
k−1
2 +. . .+Cm0
k qm0
1 qk−m0
2 . Зазначимо, що це сума бiномiальних iмовiрностей.
А саме: нехай ξ — випадкова величина, що дорiвнює кiлькостi “успiхiв” у схемi Бернуллi,
де кiлькiсть незалежних випробувань k, iмовiрнiсть “успiху” у кожному з випробувань q1,
iмовiрнiсть того, що ξ набуває значення m за формулою Бернуллi: P (ξ = m) = Cm0
k qm0
1 qk−m0
2
(див., наприклад, [4]). Тодi TA
k — iмовiрнiсть того, що ξ набуває значень 0 6 m 6 m0. Отже,
TA
k = P (ξ 6 m0) 6 P (ξ 6 kτ). Застосовуючи нерiвнiсть Чебишова, а саме: P (|ξ − a| > ϵ) <
< D/ϵ2 (ϵ > 0), де a — математичне сподiвання: a = kq1, D — дисперсiя: D = kq1q2,
зробимо такi оцiнки.
a) Якщо q1 > τ , то
TA
k 6 P (ξ 6 kτ) = P (ξ − kq1 6 kτ − kq1) = P (kq1 − ξ > kq1 − kτ) 6
6 P (|ξ − kq1| > k(q1 − τ)) 6 D
(k(q1 − τ))2
=
q1q2
k(q1 − τ)2
.
Тодi lim
k→∞
TA
k = 0 = TA. Таким чином, за умови q1 > τ територiя, яку “контролює” опонент
А, при k → ∞ наближається до 0.
б) Якщо q1 < τ , то для достатньо великих значень k отримаємо kq1 < kτ − 1 6 m0 < kτ .
Тодi
TA
k = P (ξ 6 m0) > P (ξ 6 kτ − 1) > 1− q1q2
k
(
τ − 1
k
− q1
)2 .
Тодi
lim
k→∞
TA
k = 1 = TA.
в) Нехай q1 = τ . Оскiльки медiаною бiномiального розподiлу є одне з чисел [kq1] − 1,
[kq1], [kq1] + 1, а m0 = [kq1] або m0 = [kq1] − 1, то P (ξ 6 m0) прямує до 1/2. Отже, якщо
q1 = τ , то TA = TB = 1/2. Опоненти порiвну “контролюють” територiю.
Теорему доведено.
3. Частиннi випадки. Нехай подрiбнення простору Ω таке, що q1 = q2 = 1/2, назвемо
таке подрiбнення рiвномiрним.
3.1. Нехай стратегiї опонентiв А i В задаються числами α, β такими, що 0 < α < 1/2,
β = 1/2. Тобто розподiл А не є рiвномiрним, а розподiл В рiвномiрний. Тодi τ = ln((1 −
− α)/0,5)/ ln((1 − α)/α). Можна показати, що 0 < τ < 1/2, а тодi виконується умова τ <
< q1 = 1/2, що означає, що TA = 0, а TB = 1.
Коли стартовий розподiл опонента А не є рiвномiрним, а розподiл опонента В рiвномiр-
ний, то мiра територiї, яку “виграє” опонент В, наближається до 1.
3.2. Нехай 0 < α < 1/2, а 1/2−α > |1/2−β|, що означає, що значення β менш вiддалено
вiд 1/2, нiж α, тобто розподiл опонента В є ближчим до рiвномiрного, нiж опонента А. Тодi
10 ISSN 1025-6415 Dopov. Nac. akad. nauk Ukr., 2016, №5
α(1 − α) < β(1 − β), а тодi (1 − α)/(1 − β) < β/α, ln((1 − α)/(1 − β)) < ln(β/α) i тому
0 < τ < 1/2. Отже, виконується умова τ < q1 = 1/2, що означає, що TA = 0, а TB = 1.
Якщо, навпаки, розподiл опонента А є ближчим до рiвномiрного, тобто 1/2− α < β − 1/2,
то α(1 − α) > β(1 − β), а тодi (1 − α)/(1 − β) > β/α, ln((1 − α)/(1 − β)) > ln(β/α) i тому
τ > 1/2. Отже, виконується умова τ > q1 = 1/2, що означає, що TA = 1, а TB = 0.
Тобто якщо стартовий розподiл опонента є ближчим до рiвномiрного, нiж у iншого
опонента, то мiра територiї, яку контролює цей опонент, при великих значеннях k набли-
жається до 1, тодi як мiра територiї, яку контролює iнший опонент, наближається до 0.
Отже, стратегiя рiвномiрного розподiлу є бiльш оптимальною.
3.3. Нехай 0 < α < 1/2, а β = 1−α. Тодi τ = 1/2, а отже, q1 = τ та TA = TB = 1/2. Якщо
розподiли опонентiв однаково вiддаленi вiд рiвномiрного (але не збiгаються), то опоненти
порiвну дiлять територiю ресурсного простору.
3.4. Нехай подрiбнення простору Ω є таким, що q1 ̸= q2, тобто не є рiвномiрним, та
0 < α < β = q1. Оскiльки α < τ < β, то τ < q1, що означає TA = 0, а TB = 1. Отже, якщо
мiра присутностi опонента в регiонах дорiвнює мiрi Лебега цих регiонiв, то такий опонент
“виграє” територiю, мiра якої дорiвнює 1.
Цитована лiтература
1. Koshmanenko V. Theorem of conflicts for a pair of probability measures // Math. Method. Oper. Res. –
2004. – 59, No 2. – P. 303–313.
2. Koshmanenko V. The infinite direct of probability measures and structural similarity // Methods Funct.
Anal. Topology. – 2011. – 17, No 1. – P. 20–28.
3. Koshmanenko V. Existence theorems of the ω-limit states for conflict dynamical systems // Methods Funct.
Anal. Topology. – 2014. – 20, No 4. – P. 379–390.
4. Боровков А.А. Курс теории вероятностей. – Москва: Наука, 1972. – 287 с.
References
1. Koshmanenko V. Math. Method. Oper. Res., 2004, 59, No 2: 303–313.
2. Koshmanenko V. Methods Funct. Anal. Topology, 2011, 17, No 1: 20–28.
3. Koshmanenko V. Methods Funct. Anal. Topology, 2014, 20, No 4: 379–390.
4. Borovkov А.А. Course of probability theory, Moscow: Nauka, 1972 (in Russian).
Надiйшло до редакцiї 16.10.2015
И.В. Веригина
НТУ Украины “Киевский политехнический институт”
E-mail: veringa@i.ua
Сравнение стратегий пары опонентов в задаче “захвата” территории
В роботе теория динамичных систем конфликта применяется в модели, которая описыва-
ет конфликтное перераспределение ресурсного пространства (территории) между альтер-
нативными сторонами (парой оппонентов).
Ключевые слова: динамичная система конфликта, вероятностная мера, самоподобная мера,
равновесное состояние, конфликтное перераспределение ресурсного пространства.
ISSN 1025-6415 Доп. НАН України, 2016, №5 11
I. V. Verygina
NTU of Ukraine “Kiev Polytechnical Institute”
E-mail: veringa@i.ua
Comparison of the strategies of two opponents in the problem of
“conquest” of a territory
The theory of conflict dynamical systems is applied to a model that discribes the conflicting redi-
stribution of a resource space (territory) between adversaries (a pair of opponents).
Keywords: dynamical system of conflict, probability measure, self-similar measure, equilibrium
state, conflicting redistribution of a resource space.
12 ISSN 1025-6415 Dopov. Nac. akad. nauk Ukr., 2016, №5
|
| id | nasplib_isofts_kiev_ua-123456789-104751 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1025-6415 |
| language | Ukrainian |
| last_indexed | 2025-12-07T17:54:58Z |
| publishDate | 2016 |
| publisher | Видавничий дім "Академперіодика" НАН України |
| record_format | dspace |
| spelling | Веригіна, І.В. 2016-07-15T12:32:20Z 2016-07-15T12:32:20Z 2016 Порівняння стратегій пари опонентів у задачі “захоплення“ території / І.В. Веригіна // Доповіді Національної академії наук України. — 2016. — № 5. — С. 7-12. — Бібліогр.: 4 назв. — укр. 1025-6415 https://nasplib.isofts.kiev.ua/handle/123456789/104751 517.9 У роботi теорiя динамiчних систем конфлiкту застосовується до моделi, яка описує конфлiктний перерозподiл ресурсного простору (територiї) мiж альтернативними сторонами (парою опонентiв). В роботе теория динамичных систем конфликта применяется в модели, которая описывает конфликтное перераспределение ресурсного пространства (территории) между альтернативными сторонами (парой оппонентов). The theory of conflict dynamical systems is applied to a model that discribes the conflicting redistribution
 of a resource space (territory) between adversaries (a pair of opponents). uk Видавничий дім "Академперіодика" НАН України Доповіді НАН України Математика Порівняння стратегій пари опонентів у задачі “захоплення“ території Сравнение стратегий пары опонентов в задаче “захвата” территории Comparison of the strategies of two opponents in the problem of “conquest” of a territory Article published earlier |
| spellingShingle | Порівняння стратегій пари опонентів у задачі “захоплення“ території Веригіна, І.В. Математика |
| title | Порівняння стратегій пари опонентів у задачі “захоплення“ території |
| title_alt | Сравнение стратегий пары опонентов в задаче “захвата” территории Comparison of the strategies of two opponents in the problem of “conquest” of a territory |
| title_full | Порівняння стратегій пари опонентів у задачі “захоплення“ території |
| title_fullStr | Порівняння стратегій пари опонентів у задачі “захоплення“ території |
| title_full_unstemmed | Порівняння стратегій пари опонентів у задачі “захоплення“ території |
| title_short | Порівняння стратегій пари опонентів у задачі “захоплення“ території |
| title_sort | порівняння стратегій пари опонентів у задачі “захоплення“ території |
| topic | Математика |
| topic_facet | Математика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/104751 |
| work_keys_str_mv | AT verigínaív porívnânnâstrategíiparioponentívuzadačízahoplennâteritoríí AT verigínaív sravneniestrategiiparyoponentovvzadačezahvataterritorii AT verigínaív comparisonofthestrategiesoftwoopponentsintheproblemofconquestofaterritory |