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

[mihaild]

(задача с math.se, ответ мне нравится, мое решение - не нравится)
Алиса и Боб играют в игру. Алиса получает два независимых равномерно распределенных на $[0, 1]$ числа $x$ и $y$. Одно (по своему выбору) она прячет, другое показывает Бобу. Боб должен угадать, больше показанное число спрятанного, или меньше. Если Боб угадывает правильно - Алиса платит ему сумму, равную спрятанному числу, если неправильно - Боб платит Алисе сумму, равную спрятанному числу.
Чему равен средний выигрыш при оптимальных стратегиях, и какие это стратегии?

[EUgeneUS]

Если всегда сумма выигрыша - спрятанное число, то в смешанных стратегиях всё симметрично.
И Боб и Алиса могут гаратнировать себе "в среднем ноль".
Оптимальная стратегия для обоих, не глядя на выпавшие числа для Алисы (для Боба на показанное число), случайно с вероятностью 0.5 выбирать один из своих вариантов.

[mihaild]

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

Оптимальная стратегия для обоих, не глядя на выпавшие числа для Алисы (для Боба на показанное число), случайно с вероятностью 0.5 выбирать один из своих вариантов

Если Алиса не глядя показывает выбирает одно из двух чисел равновероятно, то Боб в среднем выигрывает, отвечая "спрятанное число больше". Если выпали числа $x < y$, то с вероятностью $1/2$ Боб выигрывает $y$, а с вероятностью $1/2$ проигрывает $x$. Так что "выбирать вариант не глядя" - не равновесие.

[wrest]

mihaild
Тут как обычно имеется в виду, что игроки не помнят историю, т.е. не меняют стратегию, верно?

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

[mihaild]

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

[Geen]

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

Если всегда сумма выигрыша - спрятанное число, то в смешанных стратегиях всё симметрично

Это почему так? Игроки ведь несимметричны.

-- 04.07.2025, 18:54 --

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

И Боб и Алиса могут гаратнировать себе "в среднем ноль".

Помнится, именно Вы предлагали покер на трёх картах....

[wrest]

Ок, после не очень долгих бесед с ИИ я подозреваю, что знаю ответ. Алиса, похоже, обречена

[EUgeneUS]

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

Если Алиса не глядя показывает выбирает одно из двух чисел равновероятно, то Боб в среднем выигрывает, отвечая "спрятанное число больше". Если выпали числа $x < y$, то с вероятностью $1/2$ Боб выигрывает $y$, а с вероятностью $1/2$ проигрывает $x$. Так что "выбирать вариант не глядя" - не равновесие.

$p$ - вероятность, что Алиса спрятала большее число.
тогда $1-p$ - вероятность, что Алиса спрятала меньшее число.
$P$ - случайная величина, принимающее значение $1$, если Алиса спрятала большее число и $0$ в противном случае.

$q$ - вероятность того, что Боб скажет "спрятано большее число".
тогда $1-q$ - вероятность того, что Боб скажет "спрятано меньшее число".
$Q$ - случайная величина, принимающее значение $1$, если Боб сказал "спрятано большее число" и $0$ в противном случае.

$Z$ - случайная величина, равная спрятанному числу.

Тогда выигрыш Боба: $B = Z (PQ + (1-P)(1-Q)) - Z(Q(1-P) + P(1-Q)) = Z (4PQ - 2P - 2Q +1)$
Если $Z, P, Q$ - независимы, попарно и в совокупности (а это так в смешанных стратегиях), то матожидание выигрыша Боба:

$$E(B) = E(Z) (4pq - 2p - 2q +1)$$

Если Алиса, не глядя показывает одно из двух чисел равновероятно, то $p = 0.5$, и матожидание выигрыша Боба:

$$E(B) = E(Z) (2q - 1 - 2q +1) = 0$$

при любом $q$.

-- 04.07.2025, 19:19 --

Geen в сообщении #1693268 писал(а):

Это почему так? Игроки ведь несимметричны.

Я не умею рисовать красивые таблички из теории игр в LaTeX

Игроки не симметричны только в том смысле, что Боб видит показанное число.
Но если Алиса показывает число, не глядя на них, это не даёт Бобу ничего.

-- 04.07.2025, 19:21 --

Geen в сообщении #1693268 писал(а):

Помнится, именно Вы предлагали покер на трёх картах....

Я уж и забыл, если честно

[mihaild]

EUgeneUS
$Z$ и $P$ не независимы, даже если Алиса не смотрит на числа.

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

Ок, после не очень долгих бесед с ИИ я подозреваю, что знаю ответ

Сохраните, пожалуйста, беседу. Потому что мне ничего разумного по этой задаче от LLM добиться не удалсь :)

[EUgeneUS]

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

Если $Z, P, Q$ - независимы, попарно и в совокупности (а это так в смешанных стратегиях), то матожидание выигрыша Боба:

$$E(B) = E(Z) (4pq - 2p - 2q +1)$$

Более того.
Пусть $Z,Q$ - могут быть зависимыми случайными величинами, но они независимы попарно и в совокупности с $P$. Сделали предположение, что показанное число как-то зависит от $Z$, а выбор Боба $Q$ как-то зависит от показанного числа.

Тогда матожидание выигрыша Боба:

$$E(B) = 4E(ZQ)p - 2p - 2E(ZQ)p +1$$

При $p=0.5$ всё равно Алиса (и Боб) "выходит в ноль".

-- 04.07.2025, 19:30 --

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

$Z$ и $P$ не независимы, даже если Алиса не смотрит на числа.

Тем не менее, решение Боба всегда говорить "спрятанное число больше" не приводит к его выигрышу.
Потому что в этом случае $Q\equiv 1$, и от $Q$ ничего не зависит, и $Q$ ни от чего не зависит.

[wrest]

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

Но если Алиса показывает число, не глядя на них, это не даёт Бобу ничего.

Допустим, Алиса не глядя показала Бобу число например $0,1$
Ясно же, что закрытое число скорее всего (с вероятностью $0,9$) больше? Тогда Боб говорит "меньше" и выигрывает...

-- 04.07.2025, 19:35 --

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

Потому что мне ничего разумного по этой задаче от LLM добиться не удалсь :)

Оно предложило очень иезуитский подход Алисы, при котором она проигрывает 0,25
Стратегия Алисы такая:

Цитата:

Если сумма чисел $x+y<1$, Алиса показывает большее из них. Если $x+y>1$, она показывает меньшее.

[EUgeneUS]

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

Допустим, Алиса не глядя показала Бобу число например $0,1$
Ясно же, что закрытое число скорее всего (с вероятностью $0,9$) больше? Тогда Боб говорит "меньше" и выигрывает...

Нет. Неважно какое число показала Алиса. Оно ровно с вероятностью $0.5$ больше (или с той же вероятностью меньше), чем спрятанное.

-- 04.07.2025, 19:44 --

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

Оно предложило очень иезуитский подход Алисы, при котором она проигрывает 0,25

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

[wrest]

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

Нет. Неважно какое число показала Алиса. Оно ровно с вероятностью $0.5$ больше (или с той же вероятностью меньше), чем спрятанное.

Так это пока мы на него не посмотрели.

Пусть числа выпадают Бобу и Алисе (по одному числу). Числа выпадают равновероятно в диапазоне $[0;1]$
Числа выпали, они закрыты и дальше не изменяются. Боб открывает своё число и оно оказывается равным $0,1$. Какова вероятность (после того как Боб открыл своё число), что у Алисы число больше чем $0,1$?

[mihaild]

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

Тем не менее, решение Боба всегда говорить "спрятанное число больше" не приводит к его выигрышу.
Потому что в этом случае $Q\equiv 1$, и от $Q$ ничего не зависит, и $Q$ ни от чего не зависит.

Так проблема в зависимости $P$ и $Z$.

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

Оно ровно с вероятностью $0.5$ больше (или с той же вероятностью меньше), чем спрятанное

Вероятность того, что Боб угадал, действительно $1/2$ независимо от его стратегии. Но стратегия "говорить что спрятанное число больше" дает бОльшие по модулю выигрыши, чем проигрыши. $E(B|x, y) = \frac{\max(x, y) - \min(x, y)}{2} > 0$. После интегрирования по $x,y$ тоже получится положительное число.

[worm2]

Если Алиса и Боб смотрят на числа, то, получается, стратегия Алисы — это функция двух переменных $f:[0,1]^2\to[0,1]$, а стратегия Боба — функция одной переменной $g:[0,1]\to[0,1]$.
И цена игры — это интеграл от хитрой комбинации этих функций. Причём при равновесии Нэша этот интеграл не должен зависеть ни от конкретной функции $f$ при оптимальной $g$, ни от конкретной функции $g$ при оптимальной $f$.
Как-то сложно. Я пока ниасилил.