Какое число показать?

[EUgeneUS]

wrest в сообщении #1693460 писал(а):

Для стратегии "С вероятностью 1/3 Алиса покажет меньшее число, а спрячет бОльшее." правильный текст такой

Да, я эту ошибку обнаружил.
Итак по результатам.

II. "Смешанная стратегия Алисы" (с исправленной функцией)
Стратегии Боба:
1 и 2. Как ожидалось - уходим в ноль.
3,4,5 - не уходим в ноль.

Это означает, что найденная смешанная стратегия Алисы не работает, если Боб анализирует показанное число.

I. "Чистая стратегия Алисы".
Тут в стратегиях Боба 1 и 2 ожидаемой результат не получился, надо пересчитать

[wrest]

EUgeneUS
Вообще, пока что наилучшая игра за Алису даёт Бобу выигрыш 1/6
Если даже найдётся ненулевая стратегия, но Алиса проигрывает меньше чем чем 1/6 -- тоже неплохо :)

[EUgeneUS]

wrest в сообщении #1693460 писал(а):

Напишите пож-ста удалось ли запускать в вебе -- надо ли чтобы я позапускал?

Да, запускаю в вебе. Норм.

-- 06.07.2025, 19:44 --

I. "Чистая стратегия Алисы".

Вот такая нашлась интересная:
i. Если $y < x$ - показываем $x$, прячем $y$
ii. Если $x < y < ((2 - \sqrt{2})x + \sqrt{2} - 1)$ - показываем $y$, прячем $x$
iii. Если $((2 - \sqrt{2})x + \sqrt{2} - 1) < y $ - показываем $x$, прячем $y$

В крайних стратегиях Боба даёт нули. Но не в середине.

[Shadow]

wrest в сообщении #1693443 писал(а):

Боб угадал в 91% случаев и заработал чуть больше 1/6, Алиса в пролёте

Алиса в пролете, потому что Боб отказался от стратегии "Боб" и начал играть "Анти-Алиса". Стратегия работает только в том случае, если Бобу известна стратегия Алисы, а Алисе стратегия Боба - нет (хотя быстро поймет:)). А почему так? А если Алиса начнет играть "Анти-Боб"?. Согласитесь, всегда говорить "спрянато меньшее число" - наитупейшая из всех возможных стратегий, если она известна. И тогда Боб должен включить "Анти-Анти-Боб" и этим "анти" нет конца.
Начнем с нуля
У Боб есть нулевая стратегия - Не гляда ни на что, случайно и равновероятно говорить "спрятано меньшее" или "спрятано большее". Что бы там Алиса не прятала, его равновероятно выиграет либо он, либо она. Выигрыш ноль.
С ничьей в кармане, можно поборотся и за победу. (но честно, без всяких "анти").
Интуитивно не хочется кидать монетку, если увижу число $0,000001$ или $0.99999$
Боб рассуждает так:
Если увижу число меньше $x$, скажу что спрятано большее.
Если увижу число, больше $y$ - что спрятано меньшее.
В остальных случаях кидаю монетку.

Расчеты показывают, что Боб не может ни при каких $x,y$ сделать выигрыш Алисы отрицательным. Минимум равен нулю при $x=0,y=1$.
Будет хитреть - включатся ваякие бесконечные "анти".

-- 06.07.2025, 19:47 --

Shadow в сообщении #1693470 писал(а):

У Боб есть нулевая стратегия - Не гляда ни на что, случайно и равновероятно говорить "спрятано меньшее" или "спрятано большее". Что бы там Алиса не прятала, его равновероятно выиграет либо он, либо она.

Начал сомневаться. Если всегда говорит "спрятано большее", примерно в половину случаев будет выигрыш, но большее. Ногда Алиса включит Анти-Боб. Вот задача...
Значит, последнее замечание не противоречит основному выводу - хитрить не надо.

[mihaild]

Shadow в сообщении #1693470 писал(а):

Стратегия работает только в том случае, если Бобу известна стратегия Алисы, а Алисе стратегия Боба - нет (хотя быстро поймет:)). А почему так? А если Алиса начнет играть "Анти-Боб"

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

[wrest]

Shadow в сообщении #1693470 писал(а):

Стратегия работает только в том случае, если Бобу известна стратегия Алисы, а Алисе стратегия Боба - нет (хотя быстро поймет:)).

Вы немножко не понимаете условия. Представьте это так, что Алиса и Боб играют лишь один раз. Но Алис и Бобов тыщи. Все Алисы должны между собой договориться ДО этой одной единственной игры. И все Бобы тоже должны. Причем, Бобы слышат переговоры Алис и знают о чем договариваются Алисы. Игры проходят одномоментно, поэтому ни каждая из Алис ни любой из Бобов не могут воспользоваться историей и как-то подстроиться по ходу дела, т.к. у каждого экземпляра есть только одна игра из одного раунда. Считайте что после переговоров но до начала игры их парами Алиса+Боб расселяют в закрытые комнаты.
Можете считать ещё так, что Алис и Бобов по одному экземпляру, но после каждого розыгрыша им стирают память об этом розыгрыше и они думают что каждый розыгрыш - первый. При этом, по прежнему, Боб знает стратегию Алисы, и Алиса знает, что Боб знает (она сама записывает стратегию и передаёт Бобу).

Вследствие того, что Боб знает стратегию Алисы, а Алиса знает чтоб Боб знает её стратегию, и если задача имеет решение, то и Алиса знает стратегию Боба.

[worm2]

worm2 в сообщении #1693339 писал(а):

Очевидно, этот максимум получится, если взять $f(x,y)=\theta(\operatorname{sgn}(x-y)(x+y-4xy))$, где $\theta$ — функция Хэвисайда, равная 0 при отрицательном аргументе и 1 при положительном

Что-то меня осенило: ведь $f(x,y)$ сразу восстанавливается по любой известной функции $g$: $f(x,y)=\theta\left(\operatorname{sgn}(x-y)\left[x(1-g(y))+y(1-g(x))\right]\right)$. А это значит, мы можем, подставив это выражение для $f$ под знак интеграла, вести оптимизацию только по функции одного аргумента $g(x)$. Не то, чтобы я сразу понял, как это делать (вроде бы теория минимизации функционала хорошо разработана, но функция какая-то дикая), но худо-бедно можно "перебрать все функции" с каким-то немелким шагом, для компьютера это не очень большая проблема.
Не уверен, что у меня всё получилось правильно, вероятно, я наошибался, но результаты численного моделирования намекают, что оптимальная стратегия для Боба такова: существуют некие оптимальные $x_1$ и $x_2$, $0<x_1<x_2<1$, что если Бобу предъявляют число, меньшее $x_1$, то он говорит "это минимум, а спрятан максимум", если предъявлено число, большее $x_2$, то Боб говорит "это максимум", в противном случае (на интервале $[x_1, x_2]$) Боб выбирает ответ с вероятностью $0.5$.

[wrest]

worm2
Вот вам стратегия Боба для $x_1=1/3,x_2=2/3$

bob_strat_worm2_x1x2(S)={
    my(x1=1/3,x2=2/3);
    if(S<x1,return(1));
    if(S<x2,
           if(random(2),return(1),return(-1)),
           return(-1));
    error("Bob failed to choose with given S=",S);
}

-- 07.07.2025, 01:06 --

worm2 в сообщении #1693477 писал(а):

существуют некие оптимальные $x_1$ и $x_2$, $0<x_1<x_2<1$,

Причем из соображений симметрии и общей гармонии математического мира, $x_2=1-x_1$, да?

[EUgeneUS]

mihaild в сообщении #1693473 писал(а):

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

Дополню, так сказать, для полноты картины.
1. Если стратегия выбирается детерминировано всеми игроками - это называется "чистые стратегии".
2. Если стратегии выбираются игроками случайным образом (но с известным распределением вероятностей) - это называется "смешанные стратегии".
3. Равновесие Нэша в чистых стратегиях может не существовать.
4. Равновесие Нэша в смешанных стратегиях всегда существует. Но не уверен, что условия этой теоремы покрывают эту задачу.

-- 07.07.2025, 06:42 --

worm2 в сообщении #1693477 писал(а):

Что-то меня осенило: ведь $f(x,y)$ сразу восстанавливается по любой известной функции $g$: $f(x,y)=\theta\left(\operatorname{sgn}(x-y)\left[x(1-g(y))+y(1-g(x))\right]\right)$. А это значит, мы можем, подставив это выражение для $f$ под знак интеграла, вести оптимизацию только по функции одного аргумента $g(x)$.

Так оно и делается стандартным образом.

worm2 в сообщении #1693477 писал(а):

но результаты численного моделирования намекают, что оптимальная стратегия для Боба такова: существуют некие оптимальные $x_1$ и $x_2$, $0<x_1<x_2<1$, что если Бобу предъявляют число, меньшее $x_1$, то он говорит "это минимум, а спрятан максимум", если предъявлено число, большее $x_2$, то Боб говорит "это максимум", в противном случае (на интервале $[x_1, x_2]$) Боб выбирает ответ с вероятностью $0.5$.

Боб знает стратегию Алисы, поэтому он для любого числа может сказать: оно чаще бывает большим, или чаще бывает меньшим. А это значит, что у Боба чистая стратегия $g:[0,1] \to \{0,1\}$
При этом области, где ноль, а где единица могут быть любыми (будет зависеть от стратегии Алисы).

-- 07.07.2025, 06:49 --

worm2 в сообщении #1693477 писал(а):

Не то, чтобы я сразу понял, как это делать (вроде бы теория минимизации функционала хорошо разработана, но функция какая-то дикая),

Можно попробовать так:
1. Чтобы избавиться от сигнов и хэвисайдов разбить область интегрирования на области $x>y$ и $x<y$
2. Для одной из областей сделать замену $x \leftrightarrow y$
3. воспользоваться (если это делаем до постановки $f(x,y) = ...$):

worm2 в сообщении #1693339 писал(а):

Думаю, можно считать, что $f(x,y)=1-f(y,x)$.

3. После чего интегралы опять должны свернуться, но уже не по всему квадрату, а по треугольнику.

-- 07.07.2025, 07:17 --

Ещё можно так зайти.
Чтобы свести игру в ноль, Алиса должна показывать числа так, чтобы любое показанное число равновероятно могло оказаться бОльшим или меньшим в паре.
Отсюда следует что, чем ближе число в паре к $0.5$ тем чаще его нужно показывать.
Отсюда следует, что если
а) $x=y$ - показываем равновероятно.
б) $x+y=1$ - показываем равновероятно.

То есть на диагоналях: $f(x, x) = f(x, 1-x) = 0.5$

в) Если $x=0.5$ - показываем всегда его. Аналогично для $y$.
Тогда: $f(0.5, y) = 1; f(x, 0.5) = 0$

($f(x, y)$ - вероятность, с которой показывается $x$)

Забавная функция получается, с разрывом в $(0.5; 0.5)$

[EUgeneUS]

Вообще говоря, разрыв может оказаться не в точке, а по диагоналям (одной или двум).

[Shadow]

worm2 в сообщении #1693477 писал(а):

оптимальная стратегия для Боба такова: существуют некие оптимальные $x_1$ и $x_2$, $0<x_1<x_2<1$, что если Бобу предъявляют число, меньшее $x_1$, то он говорит "это минимум, а спрятан максимум", если предъявлено число, большее $x_2$, то Боб говорит "это максимум", в противном случае (на интервале $[x_1, x_2]$) Боб выбирает ответ с вероятностью $0.5$.

wrest в сообщении #1693478 писал(а):

Причем из соображений симметрии и общей гармонии математического мира, $x_2=1-x_1$, да?

Вы, кажется, не обратили внимание моему сообщению

Shadow в сообщении #1693470 писал(а):

Боб рассуждает так:
Если увижу число меньше $x$, скажу что спрятано большее.
Если увижу число, больше $y$ - что спрятано меньшее.
В остальных случаях кидаю монетку.

Расчеты показывают, что Боб не может ни при каких $x,y$ сделать выигрыш Алисы отрицательным. Минимум равен нулю при $x=0,y=1$.

Проведем расчеты:
$0\le x \le y \le 1$. Числа в интервале $(0,x)$ называем малыми, в $(x,y)$ - средними, $(y,1)$ - большими.

Алиса:
Если оба числа средние, решает Фортуна - выигрыш ноль.
Если одно малое, а другое - среднее, прячу малого - решает Фортуна кому оно достанется.
Аналогично, если одно большое, а другое-среднее прячу большого, решает Фортуна.
И теперь ненулевые случаи:
1. Если оба числа малые выигрываю я - меньшее из них.
Вероятность $x^2$, ср. выигрыш: $x/3$

(Оффтоп)

Расчет основан на том, что при равномерном распределении на $(0,1)$ мат.ожидание меньшего из чисел $1/3$, а бОльшего - $2/3$. Тут равномерное распределение на $(0,x)$

2. Если оба числа большие выигрываю я - бОльшее из них.
Вероятност $(1-y)^2$, выигрыш $y+2/3(1-y)$

3.(Единственный случай, когда Боб в плюсе): Одно число малое, другое - большое. Выигрывает Боб, меньшее из них.
Вероятность $2x(1-y)$, выигрыш (мой) $-x/2$

И Боб минимизирует функцию $F(x,y)=x^2\cdot \frac x 3+(1-y)^2[y+\frac 2 3(1-y)]-2x(1-y)\cdot \frac x 2$
при $0 \le x \le y\le 1$

(Оффтоп)

С целью облекчения вычислений, я не делал разницу между задачами:
Мат.ожидание меньшего из двух чисел, равномерно распределенные на $(0,x)$
и
Мат.ожидание меньшего из двух чисел, равномерно распределенные на $(0,1)$, при условии, что оба они меньше $x$
Возможно, зря.

[EUgeneUS]

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

Чтобы свести игру в ноль, Алиса должна показывать числа так, чтобы любое показанное число равновероятно могло оказаться бОльшим или меньшим в паре.

Попробуем это формализовать.
(тут $f(x,y)$ - вероятность, что будет показано $x$).

Для числа из интервала $(x, x+dx)$:

1. $dx P_1(x) = dx \int\limits_{0}^{1} f(x,y) dy$ - вероятность, что выпало и будет показано.
2. $dx P_2(x) = dx \int\limits_{0}^{x} f(x,y) dy$ - вероятность, что выпало, и будет показано, и является бОльшим в паре.
3. $P_3(x) = \frac{\int\limits_{0}^{x} f(x,y) dy}{\int\limits_{0}^{1} f(x,y) dy}$ - вероятность, будет показано, и является бОльшим в паре, при условии, что выпало.

Из $P_3(x) = 1/2$ получаем интегральное уравнение:

$$\int\limits_{0}^{x} f(x,y) dy = \frac{1}{2} \int\limits_{0}^{1} f(x,y) dy$$

аналогично для $y$

$$\int\limits_{0}^{y} (1-f(x,y)) dx = \frac{1}{2} \int\limits_{0}^{1} (1-f(x,y)) dx$$

[EUgeneUS]

Shadow в сообщении #1693470 писал(а):

Боб рассуждает так:
Если увижу число меньше $x$, скажу что спрятано большее.
Если увижу число, больше $y$ - что спрятано меньшее.
В остальных случаях кидаю монетку.

Обратите внимание, что Бобу не нужно бросать монетку.
Боб знает стратегию Алисы.
А значит Боб знает: показанное число чаще бывает бОльшим в паре или меньшим (при условии, что оно показано).
Есть ещё вариант: Боб знает, что показанное число равновероятно может быть бОльшим в паре или меньшим (при условии, что оно показано).
Но тогда от решения Боба ничего не зависит, и опять ему кидать монетку нет необходимости.

[mihaild]

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

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

В игре "каждый загадывает натуральное число, выигрывает загадавший большее" равновесия нет. Нужно чтобы на множестве стратегий можно было ввести топологию, относительно которой оно компактно, а выигрыш непрерывен.
Тут пространство стратегий - измеримые подмножества, грубейшая топология, относительно которой выигрыш непрерывен - видимо, порожденная $L_1$ нормой индикаторов. Если так, то оно не компактно.
Доказательство отсутствия равновесия Нэша - тоже ответ :)

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

Но тогда от решения Боба ничего не зависит, и опять ему кидать монетку нет необходимости

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

[mihaild]

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

Боб знает, что показанное число равновероятно может быть бОльшим в паре или меньшим

Тут, кстати, важна не вероятность быть больше/меньше, а среднее.