On one Property of an Important Characteristic in a Defense/Attack Problem
Table of contents
Share
Metrics
On one Property of an Important Characteristic in a Defense/Attack Problem
Annotation
PII
S111111110000118-2-1
DOI
10.33276/S0000118-2-1
Publication type
Article
Status
Published
Authors
Ernst Presman 
Occupation: Chief Researcher
Affiliation: CEMI RAS
Address: Russian Federation Moscow
Abstract
In [1] and [2], the version of the Blot’s Defense - Assault game was considered, in which attackers have the additional possibility of checking (testing) each cell for the presence of a lock, while, as in the classical hypothesis testing problem, the test error prone. These papers describe the nature of the optimal strategy for the distribution of bombs in cells and introduce the indicator on which this strategy depends. In this paper, we study the properties of this indicator.
Keywords
Blotto game, Defense/Attack resource allocation model, hypotheses testing
Received
18.11.2018
Date of publication
20.11.2018
Number of purchasers
14
Views
1115
Readers community rating
0.0 (0 votes)
Cite Download pdf

To download PDF you should sign in

Additional services access
Additional services for the article
Additional services for all issues for 2018
1 Введение.
2 В работе [1] была рассмотрена игровая модель, которая в [2] в упрощенном виде была описана следующим образом. Защитники имеют k замков для того чтобы защитить n ячеек (объектов, сайтов, полей), в каждую из которых атакующие могут положить одну или несколько бомб (из m имеющихся), чтобы вызвать взрыв (разрушение ячейки). В отличие от традиционных версий игры Блотта нападающие имеют дополнительную возможность проверки (тестирования) каждой ячейки на наличие замка, при этом, как в классической задаче проверки гипотез, тест подвержен ошибкам. С вероятностью a тест показывает присутствие замка, если он действительно есть, и с вероятностью b показывает отсутствие замка, если его нет. В упомянутых работах были рассмотрены два варианта этой модели. В более сложной модели атакующие знают параметры модели , m, результаты тестов всех ячеек, и, в частности, значение случайной величины N, равной числу ячеек с отрицательным значением теста. Если в ячейке присутствует замок, то разрушения никогда не происходит, а если замка нет, то разрушение происходит, если взрывается хотя бы одна бомба заложенных в эту ячейку, при этом все бомбы, заложенные в незащищенные ячейки, взрываются независимо друг от друга с равной вероятностью. Целью атакующих является максимизация ожидаемого числа разрушенных ячеек. Было показано, что оптимальная стратегия атакующих определяется с помощью величины r(x) равной отношению условных вероятностей:
3 ,
4 где событие состоит в отсутствии замка в конкретной ячейке, событие состоит в том, что тест дал в этой ячейке отрицательный результат, соответствующий отсутствию замка, событие S состоит в том, что тест дал положительный результат, соответствующий отсутствию замка а событие N(x) состоит в том, что случайная величина N приняла значение x.
5 В упомянутых работах были получены два представления формулы для r(x) и высказана гипотеза, подтвержденная компьютерными вычислениями, о том, что r(x) > 1 и возрастает при возрастании x.
6 Цель настоящей работы состоит в доказательстве этого нетривиального утверждения. Нетривиальность определяется тем, что случайная величина N является суммой двух биномиальных распределений с разными вероятностями успеха и разным числом испытаний, и ее распределение g(x) является сверткой этих распределений, а формула для r(x) содержит отношение g(x-1) к g(x).
7 Основные результаты.
8 Пусть Sl,k сумма l бернуллиевских случайных величин, из которых k имеют параметр 1 - a, а остальные l - k имеют параметр b, 0 ≤ k l.
9 Положим
10

11

Будем считать также, что

12 В работах [1] и [2] было показано, что r(x) совпадает с . Рассматривался случай b + a > 1, что эквивалентно условию c > 1. Мы рассматриваем произвольное 0 < c < ∞.
13 Легко проверить, что
14 (1)
15 Аналогично
16 (2)
17 Используя формулу полной вероятности по последнему слагаемому в сумме Sm,k, считая без ограничения общности, что оно имеет параметр b, получаем следующее рекуррентное соотношение:
18 (3)
19 Отсюда следует, что
20 (4)
21 Утверждение 1. При фиксированных l ≥ 1, 1 ≤ k, xl функция rl,k(x), рассматриваемая как функция от a и b, зависит только от c и соответствующая функция rl,k(x), строго возрастает по c, при этом rl,k (x,1) = 1 и
22 (5)
23 Доказательство следует из (1) и индукции по l, основанной на (4), при этом матрица размера (l - 1, l - 1) переходит в матрицу размера (l, l), ((1 ≤ k, x l). В самом деле, из (1) следует, что Утверждение 1 справедливо для l = 1 (r1,1(1) = c). Далее, в силу предположения индукции, числитель в (3) строго возрастает по c, а знаменатель строго убывает, а значит правая часть (4) строго возрастает и зависит только от c. Равенство rl,k (x,1) = 1 следует из (1), (4) и предположения индукции. Свойство (4) следует из взаимной замены успеха и неудачи в схеме Бернулли.
24 Утверждение 2. При фиксированных l ≥ 2, 1 ≤ kl - 1, функция рассматриваемая как функция от x строго возрастает по x.
25 Доказательство опять проводится индукцией по l. Непосредственная проверка с использованием (1) и (4) показывает, что
26

27 а значит Утверждение 2 выполняется при l = 2 и l = 3.
28 Для дальнейшего проведения индукции положим. Тогда, согласно (4),
29

30 (6)
31 Сначала покажем, что
32 (7)
33 В самом деле, в левой части (7) стоит квадратичная функция, принимающая в точках x = 2 и x= l - 2 значение l - 4, что доказывает (7).
34 Поэтому, в силу предположения индукции, из (6) и (7) следует, что
35 ,
36 при , 2 ≤ xl – 2 (последнее неравенство вытекает из того, что согласно Утверждению 1, r(x), r(x + 1) > 1 при c > 1, r(x), r(x + 1) < 1 при c < 1.
37 Для завершения доказательства Утверждения 2 осталось проверить, что
38 (8)
39 поскольку неравенство следует из (8) и (5).
40 Используя формулу полной вероятности, получаем
41

42 Отсюда, с использованием (1) получаем
43

44 Благодарность. Выражаю благодарность авторам работ [1] и [2] за возможность ознакомиться с манускриптами их еще не опубликованных работ.

References

1. K. Sonin, J. Wilson, A. Wright (2018). Rebel capacity and random combat, manuscript

2. K. Sonin, I. Sonin (2018). Locks and Bombs, manuscript.

Comments

No posts found

Write a review
Translate