Теория игр и вероятности

[Mr_Spock]

Решаю задачу из курса теории игр.

Условие:

Пират прячет сокровища в накоторой точке на круглом острове единичного радиуса. Полиция пролетает над островом на самолете по некоторой прямой. Полиция найдет сокровище (и выйграет игру), если пролетит на расстоянии не дальше, чем $w$ от сокровища. Пират хочет минимозировать вероятность того, что полиция найдет сокровище, а полиция - максимизировать эту вероятность. Требуется найти равновесие Нэша.

Мои попытки решения:

Очевидно, что равновесие в чистых стратегиях невозможно(рассмотриваются нетривиальные случаи, в которых самолет не может увидеть весь остров за 1 пролет). Значит и пират, и самолет должны выбирать стратегии в соотвествии с некоторой функцией распределения вероятностей. Выбор пирата можно характеризовать расстоянием $r$ от клада до центра круга, а выбор самолета расстоянием $h$ от центра круга до прямой, по которой летит самолет. $r \in [0,1]$, $ h \in [0,1-w] $. Распишем вероятности $P$ нахождения самолетом клада при заданных $r$ и $h$. Для этого потребуется рассмотреть 2 случая:

Случай первый $h>w$:

$$ r<h-w: \qquad P_1(r,h) = 0 $$

$$ r \in [h-w,h+w]: \qquad P_2(r,h) = \frac{\arccos\left(\frac{h-w}{r}\right)}{\pi} $$

$$ r \in [h+w;1]: \qquad P_3(r,h) = \frac{\arccos\left(\frac{h-w}{r}\right) - \arccos\left(\frac{h+w}{r}\right)}{\pi} $$

Случай второй $h<w$:

$$ r<w-h: \qquad P_4(r,h) = 1 $$

$$ r \in [w-h,h+w]: \qquad P_5(r,h) = 1 - \frac{\arccos\left(\frac{h-w}{r}\right)}{\pi} $$

$$ r \in [h+w;1]: \qquad P_6(r,h) =1 - \frac{\arccos\left(\frac{h-w}{r}\right) + \arccos\left(\frac{h+w}{r}\right)}{\pi} $$

Данные формылы возникли из рассмотрения вопроса о том, какая часть окружности заданного радиуса $r$ лежит на полосе ширины 2$w$, находящейся на расстоянии $h$ от центра окружности.

Теперь для нахождения равновесия Нэша найдем такую функцию распределения вероятностей $p(r)$ для пирата, что математическое ожидание нахождения клада не зависело от выбора пути самолетом. Тогда самолет также выберет смешанную стратегию, уравнивающую матожидание выйгрыша пирата, и будет достигнуто равновесие Нэша. Данная функция должна удовлетворять следующим уравнениям (где $C$ некоторая константа) :

$$ \left\{ \begin{array}{ll} \int\limits_{0}^{h-w} P_1(r,h)p(r)\,dr + \int\limits_{h-w}^{h+w} P_2(r,h)p(r)\,dr +\int\limits_{h+w}^{1} P_3(r,h)p(r)\,dr = C \qquad \qquad \forall h>w\\ \int\limits_{0}^{w-h} P_4(r,h)p(r)\,dr + \int\limits_{w-h}^{h+w} P_5(r,h)p(r)\,dr +\int\limits_{h+w}^{1} P_6(r,h)p(r)\,dr = C \qquad \qquad \forall h<w\\ \end{array} \right. $$

Я не знаю как подступиться к решению данной системы. Мне интересно, нет ли более простого решения у подобных задач.

[podih]

Наименее посещаемый радаром полиции район острова это его окрайка. Наибольшую длину окрайки мы захватываем, летя по центру круга.
Отсюда простая и единственно верная стратегия:
1. Пират прячет сокровище на берегу.
2. Самолёт пролетает через центр в случайном направлении.
Успех поиска прямо пропорционален $(2 \cdot\pi -L)$, где L - длины берега, захваченные радаром, передняя и задняя.

[Mr_Spock]

podih в сообщении #1381793 писал(а):

Наименее посещаемый радаром полиции район острова это его окрайка. Наибольшую длину окрайки мы захватываем, летя по центру круга.
Отсюда простая и единственно верная стратегия:
1. Пират прячет сокровище на берегу.
2. Самолёт пролетает через центр в случайном направлении.
Успех поиска прямо пропорционален $(2 \cdot\pi -L)$, где L - длины берега, захваченные радаром, передняя и задняя.

Утверждение о наименьшей посещаемости части острова не верно. Наименьшая посещаемость частей острова зависит от стратегии самолета. Если пират будет прятать клад на краю острова, самолет будет летать по траектории максимизирующей покрываемую окраину круга (а это совсем не через центр). Так что в этом выборе стратегий нет равновесия (участник может поменять стратегию на более выгодную). Поэтому и рассматриваются смешанные стратегии.

[podih]

Я полицейский, вы пират. Потом поменяемся. Радар захватывает половину диаметра острова. Я летаю, предварительно сообщив стратегию пирату. Ройте. Разберёмся, что верно-неверно.
И не надо меня целиком цитировать. Можно вообще не цитировать, и так всё понятно.

[EUgeneUS]

podih в сообщении #1381793 писал(а):

Наибольшую длину окрайки мы захватываем, летя по центру круга.

по краю круга.

[podih]

EUgeneUS
Конечно, это я сморозил. Наибольшая площадь покрывается. Это отбивает у пирата желание рыть ближе к центру.

И такой тезис за моё решение. В задаче не приведено отношение дальности радара к диаметру. При более тонких стратегиях его пришлось бы задать.

Итак, пока шансы у пирата 2:1. Кто-нибудь может увеличить их при данной характеристике радара?

[EUgeneUS]

Определим $F(x)$:

$$ F(x)= \left\{ \begin{array}{ll} \frac{\arccos(x)}{\pi} \qquad \qquadx \in [-1,1]\\ 1 \qquad \qquad x<-1 \\ 0 \qquad \qquad x>1 \\ \end{array} \right. $$

Тогда вероятность обнаружить клад равна (для любых $r \in [0,1]$, $ h \in [0,1-w] $)

$P(h,r) = 1 - (F(\frac{w-h}{r})+ F(\frac{w+h}{r}))$

[EUgeneUS]

Раз более квалифицированные помощники не подошли, будем вспоминать давнишний курс по теории игр

непрерывная антагонистическая игра в смешанных стратегиях:

$\tilde{F}(\psi, \chi) = \int\limits_{[X \times Y]} F(x,y) d\psi(x) d\chi(y)$

Где
$x$, $y$ - чистые стратегии игроков, вообще говоря, многомерные
$X$, $Y$ - множества чистых стратегий игроков
$\psi(x)$, $\chi(y)$ - смешанные стратегии
$F$ - функция выигрыша первого игрока в чистых стратегиях
$\tilde{F}$ - функция выигрыша первого игрока в смешанных стратегиях

Задача сводится к нахождению $\psi_0$, $\chi_0$, таких, что:

$\tilde{F}(\psi_0, \chi_0) = \min\limits_{\chi(y)}\max\limits_{\psi(x)} \tilde{F}(\psi, \chi)$

Вообще говоря, это задача вариационного исчисления, так как $\tilde{F}$ функционал, а найти нужно функции.

[Mr_Spock]

Можете подсказать, что можно почитать для того, чтобы научиться решать такие вариационные уравнения? У меня не получилось найти хороший учебник.

[Iam]

Пусть $ (x, \alpha) $ – стратегия полиции, $(r, \beta) $ – координаты клада ($x$ - расстояние траектории самолета от 0).
Учитывая симметричность игры в чистых стратегиях относительно $\gamma=\alpha-\beta$ можно придти к равномерно распределенным СВ $ \alpha, \beta \in [0, 2 \pi ) $.
При этом вероятность пропуска клада $P=\frac 1 \pi (\arccos \frac {w-x} r + \arccos \frac {w+x}r ) $(здесь нужно аккуратно расписать условия на значения аргументов), откуда $P=\frac 2 \pi \arccos (w) (при w\le 1)$, т. е. $x=0, r=1$ и никому ничего менять не хочется.

Н.Н. Воробьев. Основы теории игр.

[podih]

Iam
Что-то не так в ваших расчётах. При $\omega=\frac{1}{2}$, когда перекрывается весь остров, ваша формула даёт $\frac{2}{3}$.
Мой вариант с той же стратегией полиции, но с пиратской стратегией рыть на берегу даёт оценку в пользу пиратства. Только в этом случае полиция будет летать на расстоянии $\omega$ от любого края - и опять будет в выигрыше.
Как совместить одномерную - береговую - и площадную стратегии, я пока не понял.

[Iam]

podih, есть детали - отвечу чуть позже.

[podih]

Iam
Вдогонку, для размышлений.
1. У пирата две возможности зарыть доллары (прям как в песне: Весь покрытый зеленью, абсолютно весь): по площади и на берегу. Возможно и то, и то с некоторой вероятностью.
2. Вариант с площадью оптимально обеспечивается пролётом по центру. С берегом - пролётом скраю на пределе видимости радара: захватываем наибольшую длину берега.
3. Про углы забыли. Конечно, случайные для обоих.
4. Давайте отработаем на конкретном $\omega=1/4$, дальше видно будет. При этом значении шансы равны: пролёт через середину радиуса покрывает половину как площади. так и берега, - это и есть седловая точка. Проверьте свою формулу при этом значении. при нулевом разрешении радара (а то в стёртой формуле вы сразу пообещали полиции половину без всякого радара), при покрытии всего остров. И лишь потом публикуйте.

[Iam]

Случай $1/2 \le w \le 1 $. Тогда $(x=1-w, r=1)$ – равновесная ситуация. Значение игры (вероятность пропуска) $P=\frac 1 \pi \arccos (2w-1). $
О радаре не знал - впервые слышу.
Посмотрите обозначение $w$ в задаче.

[podih]

Iam
Вместо попыток тролления про радар - чем ещё с вертолёта можно обнаружить клад? - лучше б внимательно к задаче отнеслись.
Посмотрел обозначение. Греческая буква омега. Разъясните, пожалуйста. Я ж пока вам объясняю.
При этих значениях $\omega$ всё и было понятно с самого начала.