Оптимальная стратегия.

[Geen]

Имеется игра двух игроков с нулевой суммой, симметричная (игроки равноправны), с неполной информацией.
Игра устроена так. В начале раунда для каждого игрока генерируется "позиция" с вероятностью $p_{ik}$, где $i$ - номер позиции первого игрока, $k$ - номер позиции второго. Число позиций для каждого игрока равно $n$, матрица симметрична $p_{ik}=p_{ki}$. Каждый игрок знает свою позицию и не знает позицию другого.
Далее игроки (одновременно и независимо друг от друга) выбирают одно из двух действий. Назовём их условно "пас" (0) и "чек" (1).
Если оба выбрали пас, то выигрыш 0. Если один выбрал пас, а другой чек, то этот другой выигрывает 1 (соответственно, выбравший пас проигрывает 1). Если оба выбрали чек, то выигрыш первого игрока задаётся антисимметричной матрицей $a_{ik}=-a_{ki}$.
Например, для $n=2$, в общем случае игра описывается матрицей вероятностей

$$P=\begin{pmatrix} a&c \\ c & b \end{pmatrix}$$

и матрицей выигрышей

$$A=\begin{pmatrix} 0& \alpha\\ -\alpha & 0 \end{pmatrix}$$

($a,b,c>0$; без ограничения общности можно считать $\alpha>0$).

Обозначим стратегию первого игрока $s_i$, а второго - $s'_i$. Через $1_i$ обозначим "столбец" из всех единиц. Тогда, выигрыш первого игрока при заданных стратегиях описывается формулой (нижние индексы нумеруют позиции и пробегают значения $1..n$; верхние индексы нумеруют стратегии и пробегают значения $0..2^n-1$; по немым индексам подразумевается суммирование)

$$V^{ab}=s^a_ia_{ik}p_{ik}s'^b_k+s^a_ip_{ik}1_k-1_ip_{ik}s'^b_k$$

Для примера, упоминавшегося выше, матрица игры будет выглядеть так (стратегии первого игрока обозначают строки; цифры нумеруются слева-направо):

$$\begin{tabular}{c|cccc} & 00 & 01 & 10 & 11 \\ \hline 00 & 0 & -(b+c) & -(a+c) & -(a+b+2c) \\ 01 & b+c & 0 & b-a-\alpha c & -a-c-\alpha c \\ 10 & a+c & a-b+\alpha c & 0 & -b-c+\alpha c \\ 11 & a+b+2c & a+c+\alpha c & b+c-\alpha c & 0 \end{tabular}$$

Понятно, что цена игры 0 и оптимальной стратегией первого игрока является строка с неотрицательными значениями (вопрос 0: всегда ли такая есть?). (Оптимальная стратегия второго игрока точно такая же в силу антисимметричности матрицы игры.)
Для поминаемого примера "прямым перебором" находится, что выбор между стратегиями 10 и 11 определяется знаком величины $b+c-\alpha c$.

Вопрос 1: как эффективно находить оптимальную стратегию (при заданных матрицах $A$ и $P$) при больших $n$ (сто и более)?

На самом деле, матрица $A$ представляет собой произведение фиксированных вероятностей выигрыша на величину "приза": $a_{ik}=(2q_{ik}-1)w$.
Вопрос 2; как эффективно найти все значения приза, при которых происходит смена оптимальной стратегии?

[DeBill]

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

как эффективно находить оптимальную стратегию

Вовсе не факт, что, при более-менее общих данных $A,P$ найдутся чистые стратегии. Придется искать оптимальную среди смешанных - и тут все тяжело...

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

На самом деле, матрица $A$ представляет собой

Что-то она не антисимметрична...Игра с ненулевой суммой (есть плата за участие?)
Нда, давал я когда то курсовую: построить оптимальные стратегии для бриджа. Студент успешно справился с модельной задачей (в колоде - 2 карты, туз и двойка. Раздают поровну. Пас/чек. У кого больше - выиграл . И даже - с тремя картами. И даже - с четырьмя! На самом деле, для случая, когда на пространстве позиций есть отношение порядка (транзитивность), позиции - равновероятны, и выигрыш - фиксирован (равен размеру банка), действительно, есть чистые стратегии. И в случае монотонности вероятностей позиций (относительно заданного на них порядка) - тоже). Но в общем случае - увы.

[Geen]

DeBill в сообщении #1273667 писал(а):

Что-то она не антисимметрична...

Почему? $0\le q_{ik}\le 1$ - это вероятность выигрыша первого игрока при позициях $(i,k)$ и $q_{ki} = 1-q_{ik}$.

-- 10.12.2017, 16:48 --

Немного изменил обозначения в первом сообщении.

-- 10.12.2017, 17:04 --

Введём (антисимметричную) матрицу $B: b_{ik}=p_{ik}(2q_{ik}-1)$. Тогда выигрыш можно переписать в виде

$$V^{ab}=s^a_ib_{ik}s'^b_kw+(s^a_i-s'^b_i)(1_kp_{ki})$$

Понятно, что если $w$ мало, то оптимальной стратегией будет всегда выбирать чек ($s_i=1$).
Кажется верным, что при росте $w$ для одной позиции произойдёт "переключение" с чека на пас (в формуле выше свободные члены положительные, а среди коэффициентов при $w$ "половина" отрицательные). Тогда эту позицию можно найти решив $n$ линейных уравнений и выбрав наименьшее положительное $w$.

-- 10.12.2017, 17:36 --

DeBill в сообщении #1273667 писал(а):

Придется искать оптимальную среди смешанных

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

[Iam]

Для $ n=2, $ как будто, чистые.
Пусть $ P=(p_{s,t}), $ где $ p_{0,0}=q, p_{0,1}= p_{1,0}=p, p_{1,1}=1-2p-q. $
Смешанная стратегия 1-игрока: $ u=(u_0, u_1), $ где $ u_i $ – вероятность выдачи 1 в его i-позиции. Смешанная стратегия 2-игрока: $ v=(v_0, v_1). $
При возникновении (i,j)-позиции выигрыш 1-игрока (проигрыш 2-игрока) $ w(i,j) $ составит:
$ w(00)= u_0(1- v_0)- v_0(1- u_0)= u_0- v_0; $
$ w(01)= u_0(1- v_1)- v_1(1- u_0)+ \alpha u_0 v_1 = u_0- v_1+ \alpha u_0 v_1; $
$ w(10)= u_1(1- v_0)- v_0(1- u_1)- \alpha u_1 v_0 = u_1- v_0- \alpha u_1 v_0; $
$ w(11)= u_1(1- v_1)- v_1(1- u_1)= u_1- v_1. $
Функция выигрыша 1-игрока равна
$ W(u,v)=q[u_0- v_0]+p[u_0- v_1+ \alpha u_0 v_1+ u_1- v_0- \alpha u_1 v_0]+(1-2p-q)[ u_1- v_1]. $
С учетом ограничений нужно положить: $ u^*_0= v^*_0=1. $
Тогда $ W(u,v)= p[- v_1+ \alpha v_1+ u_1- \alpha u_1]+(1-2p-q)[ u_1- v_1]= $
$ = (u_1- v_1)[p(1-\alpha )+1-2p-q]= (u_1- v_1)(1-\alpha p-p-q), $ откуда
$ u^*_1=1 $ при $ \alpha p+p+q < 1 $ и $ u^*_1=0 $ при $ \alpha p+p+q >1; $
$ v^*_1=1 $ при $ \alpha p+p+q < 1 $ и $ v^*_1=0 $ при $ \alpha p+p+q >1. $
При $ \alpha p+p+q =1 $ можно поступать, как попало.

[Geen]

Кажется что-то не так
При $n=2$ чистых стратегий 4 для каждого игрока.

-- 11.12.2017, 19:30 --

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

Кажется верным, что при росте $w$ для одной позиции произойдёт "переключение" с чека на пас

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

[Iam]

"Да так,.., так как-то все..." (по Гоголю)
В чистых стратегиях...
Игроки имеют по 4 чистых стратегии:
$u=(u_0, u_1) \in \{(00),(01),(10),(11)\}, v=(v_0, v_1) \in \{(00),(01),(10),(11)\}.$
Выигрыш 1-игрока определяется матрицей

$$\begin{tabular}{c|cccc} & 00 & 01 & 10 & 11 \\ \hline 00 & 0 & -1+p+q & -p-q & -1 \\ 01 & 1-p-q & 0 & 1 - 2p - 2q - \alpha p & -p-q- \alpha p \\ 10 & p+q & -1+2p+2q+\alpha p & 0 & -1+p+q +\alpha p \\ 11 & 1 & p+q+\alpha p & 1-p-q-\alpha p & 0 \end{tabular}$$

из которой легко установить оптимальность чистых стратегий $u^*=( u^*_0, u^*_1), v^*=( v^*_0, v^*_1),$

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

$ u^*_0= v^*_0=1. $
$ u^*_1=1 $ при $ \alpha p+p+q < 1 $ и $ u^*_1=0 $ при $ \alpha p+p+q >1; $
$ v^*_1=1 $ при $ \alpha p+p+q < 1 $ и $ v^*_1=0 $ при $ \alpha p+p+q >1. $

Насчет того, что "при $ \alpha p+p+q =1 $ можно поступать, как попало", "несколько" переборщил (т. е. это относится к компонентам $u_1, v_1$ стратегий игроков).

[Geen]

Да, прошу прощения, проглядел этот момент

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

С учетом ограничений нужно положить: $ u^*_0= v^*_0=1. $

и немного испугался, что результаты разошлись

[Geen]

Извиняюсь, что поднимаю старую тему, но она мне всё не даёт покоя (временами).

На данный момент статус такой. Заменим $w$ на $v=1/w$ - смешанные стратегии линейны именно по $v$. Поскольку нас интересует стратегии, то принципиально ничего не изменится от умножения матриц $A$ и $P$ на произвольные положительные числа (всего лишь изменится "масштаб" по $v$). Далее, как было видно из формул в первом посте, матрица $P$ как таковая не нужна - достаточно знать её сумму по столбцам.
Т.е., имеется антисимметричная матрица $C$, вектор-строка $\bar q$ с положительными элементами, и вектор-столбцы стратегий $\mathbf{s}$ и $\mathbf{s'}$ первого и второго игрока соответственно (элементы векторов стратегий ограничены от 0 до 1). Тогда, выигрыш первого игрока даётся формулой

$$V=\mathbf{s}^{\mathsf{T}}C\mathbf{s'}+v\bar{q}(\mathbf{s}-\mathbf{s'})$$

Найдём производную выигрыша по компонентам стратегии первого игрока:

$$V_{,i}=c_{ik}s'_k+v\bar{q}_i$$

Будем считать, что множество позиций $\{1\,\ldotp\ldotp\,n\}$ разбито на три подмножества $I_+,\ I_*,\ I_-$ таким образом, что $s'_{i_+}=1$, $0< s'_{i_*}<1$ и $s'_{i_-}=0$.

Тогда (в этом утверждении я не на 100% уверен), если стратегия $\mathbf{s'}$ оптимальна, то должны выполнятся следующие соотношения:

$$V_{,{i_+}}>0,\ V_{,{i_*}}=0,\ V_{,{i_-}}<0$$

Далее, предыдущие уравнения не изменятся, если каждое из них разделить на соответствующее $\bar{q}_i$ и ввести матрицу $D$: $d_{ik}=c_{ik}/\bar{q}_i$ (в этой формуле нет суммирования!). То есть, уравнения будут такие:

$$\begin{array}{} d_{{i_+}{k}}s'_{k}+v=d_{{i_+}{k_*}}s'_{k_*}+d_{{i_+}{k_+}}1_{k_+}+v>0\\ d_{{i_*}{k}}s'_{k}+v=d_{{i_*}{k_*}}s'_{k_*}+d_{{i_*}{k_+}}1_{k_+}+v=0\\ d_{{i_-}{k}}s'_{k}+v=d_{{i_-}{k_*}}s'_{k_*}+d_{{i_-}{k_+}}1_{k_+}+v<0\end{array}$$

Второе из этих уравнений и объясняет почему смешанные стратегии линейны по $v$.

-- 14.02.2024, 15:03 --

Т.е., нам дана матрица $D$ (антисимметричная с точностью до умножения строк на положительные числа; в частности, на диагонали 0) и число $v$. И как бы надо найти решение $D\mathbf{s'}+v\mathbf{1}=0$, но с учётом ограничений $0\le\mathbf{s'}\le1$.

-- 14.02.2024, 15:17 --

Я всё ещё пытаюсь идти "по шагам" по $v$ начиная с $+\infty$ (при котором очевидное и единственное решение $\mathbf{s'}=1$) веря в то, что занание решения с одной стороны от точки может помочь найти решение с другой стороны.

[Geen]

Поясню свою проблему.
Рассмотрим матрицу

$$D=\begin{pmatrix} 0 & 3 & 2\\ -3 & 0 & 3\\ -2 & -3 & 0 \end{pmatrix}$$

Для этой матрицы решение следующее:

$$\begin{array}{c|ccc} v_j & s_1 & s_2 & s_3\\ \hline +\infty & & &\\ & 1 & 1 & 1\\ 5 & & &\\ & 1 & 1 & 0\\ 3 & & &\\ & 1 & -2/3+v/3 & 1-v/3\\ 2 & & &\\ & 1 & 0 & 0\\ 0 & & &\\ & 0 & 0 & 0\\ \end{array}$$

Все переходы между стратегиями находятся достаточно прямолинейно.

Теперь рассмотрим

$$D=\begin{pmatrix} 0 & -3 & 1\\ 3 & 0 & -4\\ -1 & 4 & 0 \end{pmatrix}$$

Решение теперь должно быть таким:

$$\begin{array}{c|ccc} v_j & s_1 & s_2 & s_3\\ \hline +\infty & & &\\ & 1 & 1 & 1\\ 2 & & &\\ & 4/3-v/3 & 1/3+v/3 & 1\\ 1 & & &\\ & 1 & 1/4-v/4 & 3/4+v/4\\ 0 & & &\\ & 0 & 0 & 0\\ \end{array}$$

И вот здесь не удаёт придумать алгоритм нахождения "перехода" в точке $v=1$

[SergeyGubanov]

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

В начале раунда для каждого игрока генерируется "позиция" с вероятностью $p_{ik}$, где $i$ - номер позиции первого игрока, $k$ - номер позиции второго.

Примерно с этого места ничего не понятно. Что такое "позиция"?

[Geen]

SergeyGubanov в сообщении #1629856 писал(а):

Что такое "позиция"?

Просто некий номер, в диапазоне от 1 до $n$. Это может быть число на кубике (который никто кроме игрока не видит до заявки чек/пас) или определённая комбинация розданных карт (например, если раздаётся одна карта, то это может быть её масть или достоинство).
Этот номер определяет средний выигрыш игрока ([в случае если]/[при условии что] оба заявили "чек") согласно матрице $C$.

[SergeyGubanov]

Для $n \gg 1$ я бы так играл. Для каждого $i$ сосчитал бы сумму

$$ \langle q_{i} \rangle= \sum_{k = 1}^{n} a_{i k} p_{i k} $$

Если $\langle q_{i} \rangle < -1$, то в позиции $i$ говорил бы "пас" и терял бы одну монетку за тур.

А если $\langle q_{i} \rangle \ge -1$, то в позиции $i$ говорил бы "чек" и терял бы в среднем меньше чем одну монетку за тур.

-- 19.02.2024, 15:30 --

Еще если вдруг следующая сумма меньше нуля

$$ \sum_{i = 1}^{n} \max ( -1, \langle q_{i} \rangle ) < 0, $$

то я бы играть вообще не стал (тогда жадный алгоритм не работает).

[Geen]

SergeyGubanov в сообщении #1630234 писал(а):

Для каждого $i$ сосчитал бы сумму

Лучше бы, конечно, писать в терминах матрицы $D$ и "штрафа за пас" $v$ - меньше несущественных параметров

SergeyGubanov в сообщении #1630234 писал(а):

Для $n \gg 1$ я бы так играл.

Смотрите в чём проблема. Пусть у нас такая матрица

$$D=\begin{pmatrix}0&5&400\\-5&0&600\\-400&-600&0\end{pmatrix}$$

Понятно, что при "разумных условиях" никто никогда не будет в третьей позиции говорить "чек". Но Вы, зачем то, учли эти "страшно большие" цифры из последнего столбца при вычислении $\langle q_i\rangle$. В результате Вы рекомендуете всегда во второй позиции говорить "чек", что явно далеко не всегда выгодно (например, при $v<5$ в этой позиции надо пасовать).

[SergeyGubanov]

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

Понятно, что при "разумных условиях" никто никогда не будет в третьей позиции говорить "чек". Но Вы, зачем то, учли эти "страшно большие" цифры из последнего столбца при вычислении $\langle q_i\rangle$.

Мне не понятно что обозначают числа в матрице $D$. Если они обозначают, что находясь во второй позиции я могу либо выиграть $5$ монет либо проиграть $600$ монет, то среднее $-595$ (то есть я не рекомендовал бы говорить "чек").

[Geen]

SergeyGubanov в сообщении #1630266 писал(а):

находясь во второй позиции я могу либо выиграть $5$ монет либо проиграть $600$ монет

Наоборот. Выиграть 600 или проиграть 5.