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

[Iam]

Mr_Spock в сообщении #1381707 писал(а):

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

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

При $\omega=\frac{1}{2}$, когда перекрывается весь остров...

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

Давайте отработаем на конкретном $\omega=1/4$,

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

При этих значениях $\omega$ всё и было понятно с самого начала.

podih
Просто хотелось для общего понимания определиться с $\omega$, ширина это полосы обнаружения или ее половина.
У вас был вопрос, связанный с максимизацией площади. Такой подход может увести в неправильном направлении. Достаточно убедиться, что указанная выше точка является равновесной.

[podih]

Iam в сообщении #1382455 писал(а):

Просто хотелось для общего понимания определиться с $\omega$,

Да, мой косяк, в этот раз почему-то такое значение пришло в голову.

Iam в сообщении #1382455 писал(а):

У вас был вопрос, связанный с максимизацией площади.

Вопрос мой вы сами приведите, а ответ на него я давал несколько раз, вот последний:

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

2. Вариант с площадью оптимально обеспечивается пролётом по центру. С берегом - пролётом скраю на пределе видимости радара: захватываем наибольшую длину берега.

Подведу итог:
1. При $\omega\geqslant0,5$ пират должен прятать сокровище на берегу, а полиция летать на дальности $\omega$ от одного из краёв.
2. При меньшей дальности радара будет интереснее. У обоих фигурантов смешанные стратегии.

[EUgeneUS]

Mr_Spock в сообщении #1382194 писал(а):

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

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

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

3. Вам нужно найти именно равновесие по Нэшу, из условий задачи.

4. Равновесие по Нэшу
а) иногда существует в дискретных играх в чистых стратегиях
б) всегда существует в дискретных играх в смешанных стратегиях
в) почти всегда существует в непрерывных играх в чистых стратегиях. Условия существования см. тут, теорема 4.

5. Поэтому в данной задаче правильно искать равновесие Нэша в чистых стратегиях, как написано в этом посте.
В самом деле - спрашивают про равновесие Нэша, его и нужно искать, а не (может быть) более оптимальные решения в смешанных стратегиях.

-- 18.03.2019, 08:19 --

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

2. При меньшей дальности радара будет интереснее. У обоих фигурантов смешанные стратегии.

И в этом случае будет существовать равновесие по Нэшу в чистых стратегиях.

Такие рассуждения:
1. в этом случае ($\omega < \frac{1}{2}$), полиция не может летать близко к краю круга, так как тогда остается область около центра, которая вообще не просматривается. Пират прячет там и выигрывает.
2. Значит нужно летать так, чтобы иметь хоть какое-то покрытие для любого радиуса.
3. А значит смещение полосы от центра: $x \leqslant \omega$
4. минимакс по $r$ и $x$ обязательно найдется.
5. Скорее всего (не проверял, могу ошибиться) получится, что $r=1$, $x=\omega$

[EUgeneUS]

Вольфрам Альфа

1. 3D график при $\omega > \frac{1}{2}$
Четко видно, где достигается максимин ($r=y=1$, $x=h=1-\omega$)

2. 3D график при $\omega \leqslant \frac{1}{2}$

Видно, что полиции (изменяет $x$, минимизирует функцию) выгодно смещаться к краю, но нельзя смещаться больше $\omega$ - у пирата возникают стратегии, где он прячет клад надежно (полиция не находит с вероятностью $1$).

[Iam]

EUgeneUS

EUgeneUS в сообщении #1382566 писал(а):

5. Поэтому в данной задаче правильно искать равновесие Нэша в чистых стратегиях, как написано в этом посте.

Там у меня рассуждения правильные, а в последней формуле ошибка: 4-й час утра, вместо min получил max. Вошел в тему, чтобы расслабиться перед сном, думал, что простенький вопрос На текущий момент состояние вопроса подытожил podih .

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

Подведу итог:
1. При $\omega\geqslant0,5$ пират должен прятать сокровище на берегу, а полиция летать на дальности $\omega$ от одного из краёв.
2. При меньшей дальности радара будет интереснее. У обоих фигурантов смешанные стратегии.

При $\omega>1/2$ имеется равновесная точка в чистых стратегиях (если не принимать во внимание смешанность по углам) - она описана выше. Это, как говорил великий комбинатор, "квазиунофантазия - ну это всем понятно".

[EUgeneUS]

Iam в сообщении #1382738 писал(а):

На текущий момент состояние вопроса подытожил podih .

на текущий момент это не совсем точный итог

"При меньшей" дальности радара ($\omega < 0.5$), также есть равновесие Нэша в чистых стратегиях. См. выше.. Хотя там нет строго доказательства, это решение наглядно видно на 3D графике.

[Iam]

Посмотрим случай $w=1/3$.
Пусть $x \in [0,2/3]$ – смещение полосы поиска от $0, r \in [0,1] $– расстояние клада от $0$.
Введем стратегии:
СВ $X^*$ распределена в точках $x_0=0, x_1=2/3, Pr\{X=2/3\}=p=2/3$;
СВ $R^*$ распределена в точках $r_0=1/3, r_1=1, Pr\{R=1\}=q=1/3c$,
где $c=\frac 1 \pi \arccos(1/3) $.
Для стратегий $X^*, R^*$ функция выигрыша (вероятность пропуска клада) равна
$P(X^*, R^*)=p+2cq-3c p q=2/3$.

1. Определим для стратегии $X^* $ гарантированную (верхнюю) цену игры $P^-(X^*)=\max_r P(X^*,r)$.
a) При $r \in [0, 1/3]$ имеем $P(X^*,r)=2/3$ .
b) При $r \in [1/3, 1] $
$P(X^*,r)=\frac 1 3 (\frac 2 \pi \arccos (1/3r))+\frac 2 3(1-\frac 1 \pi \arccos (1/3r))=2/3$.
Получили $P^-(X^*)=2/3$.

2. Определим для стратегии $R^* $ гарантированную (нижнюю) цену игры $P_-(R^*)=\min_x P(x,R^*)$.
a) При $x \in [0, 1/3] $
$P(x,R^*)= \frac 1 \pi [(1-q) \arccos (1-3x)+q \arccos (1/3+x) +q \arccos (1/3-x)]$;
$\min_x P(x,R^*)=2/3 (при x=0)$.
b) При $x \in [1/3, 2/3] $
$P(x,R^*)= (1-q)[1- \frac 1 \pi \arccos (3x-1)] +q [\frac 1 \pi \arccos (x+1/3) +1-\frac 1 \pi \arccos (x-1/3)];$
$\min_x P(x,R^*)=2/3 (при x=2/3) $.
Получили $P_-(R^*)=2/3$.

Таким образом, $(X^*, R^* )$ – равновесная ситуация.

Далее предположительно.
При $w \in (1/3,1/2)$ оптимальные стратегии каждого игрока будут смешениями не более трех чистых. Нужно смотреть точки: $x_0=0, x_1=3w-1, x_2=1-w$ и r_0=w, r_1=3w-1, r_2=1$.
Понятно также, какие точки нужно проверить для других областей $w$.
При $w\to \infty $ оптимальные распределения $X^*, R^* $ приближаются к непрерывным, которыми можно аппроксимировать оптимальные стратегии при малых значениях $w$.

[podih]

Iam
Я отложил задачу для малых $\omega$ в долгий ящик, после размышлений о её сложности. У пирата появляются возможности прятать клад в незатронутом центре, если полиция ищет на берегу. И наоборот. Возможны даже нелинейные функции распределения по радиусу. Соответственно растёт сложность стратегии у полиции.
Сейчас наиболее реальным считаю только численный метод.Долго, но позволяет опровергать аналитику.