2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Оптимальная стратегия.
Сообщение10.12.2017, 00:11 
Заслуженный участник
Аватара пользователя


01/09/13
4318
Имеется игра двух игроков с нулевой суммой, симметричная (игроки равноправны), с неполной информацией.
Игра устроена так. В начале раунда для каждого игрока генерируется "позиция" с вероятностью $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; как эффективно найти все значения приза, при которых происходит смена оптимальной стратегии?

 Профиль  
                  
 
 Re: Оптимальная стратегия.
Сообщение10.12.2017, 15:36 
Заслуженный участник


10/01/16
2315
Geen в сообщении #1273601 писал(а):
как эффективно находить оптимальную стратегию

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

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

 Профиль  
                  
 
 Re: Оптимальная стратегия.
Сообщение10.12.2017, 16:41 
Заслуженный участник
Аватара пользователя


01/09/13
4318
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 писал(а):
Придется искать оптимальную среди смешанных

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

 Профиль  
                  
 
 Re: Оптимальная стратегия.
Сообщение11.12.2017, 18:28 


01/11/14
195
Для $ 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  $ можно поступать, как попало.

 Профиль  
                  
 
 Re: Оптимальная стратегия.
Сообщение11.12.2017, 19:15 
Заслуженный участник
Аватара пользователя


01/09/13
4318
Кажется что-то не так :-)
При $n=2$ чистых стратегий 4 для каждого игрока.

-- 11.12.2017, 19:30 --

Geen в сообщении #1273673 писал(а):
Кажется верным, что при росте $w$ для одной позиции произойдёт "переключение" с чека на пас

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

 Профиль  
                  
 
 Re: Оптимальная стратегия.
Сообщение11.12.2017, 22:55 


01/11/14
195
"Да так,.., так как-то все..." (по Гоголю) :-)
В чистых стратегиях...
Игроки имеют по 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$ стратегий игроков).

 Профиль  
                  
 
 Re: Оптимальная стратегия.
Сообщение12.12.2017, 00:33 
Заслуженный участник
Аватара пользователя


01/09/13
4318
Да, прошу прощения, проглядел этот момент
Iam в сообщении #1274054 писал(а):
С учетом ограничений нужно положить: $ u^*_0= v^*_0=1. $
и немного испугался, что результаты разошлись :-)

 Профиль  
                  
 
 Re: Оптимальная стратегия.
Сообщение14.02.2024, 14:53 
Заслуженный участник
Аватара пользователя


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

На данный момент статус такой. Заменим $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$) веря в то, что занание решения с одной стороны от точки может помочь найти решение с другой стороны.

 Профиль  
                  
 
 Re: Оптимальная стратегия.
Сообщение14.02.2024, 21:13 
Заслуженный участник
Аватара пользователя


01/09/13
4318
Поясню свою проблему.
Рассмотрим матрицу $$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$

 Профиль  
                  
 
 Re: Оптимальная стратегия.
Сообщение16.02.2024, 17:57 
Аватара пользователя


14/11/12
1338
Россия, Нижний Новгород
Geen в сообщении #1273601 писал(а):
В начале раунда для каждого игрока генерируется "позиция" с вероятностью $p_{ik}$, где $i$ - номер позиции первого игрока, $k$ - номер позиции второго.
Примерно с этого места ничего не понятно. Что такое "позиция"?

 Профиль  
                  
 
 Re: Оптимальная стратегия.
Сообщение16.02.2024, 21:09 
Заслуженный участник
Аватара пользователя


01/09/13
4318
SergeyGubanov в сообщении #1629856 писал(а):
Что такое "позиция"?

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

 Профиль  
                  
 
 Re: Оптимальная стратегия.
Сообщение19.02.2024, 15:09 
Аватара пользователя


14/11/12
1338
Россия, Нижний Новгород
Для $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,
$$
то я бы играть вообще не стал (тогда жадный алгоритм не работает).

 Профиль  
                  
 
 Re: Оптимальная стратегия.
Сообщение19.02.2024, 15:48 
Заслуженный участник
Аватара пользователя


01/09/13
4318
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$ в этой позиции надо пасовать).

 Профиль  
                  
 
 Re: Оптимальная стратегия.
Сообщение19.02.2024, 19:07 
Аватара пользователя


14/11/12
1338
Россия, Нижний Новгород
Geen в сообщении #1630239 писал(а):
Понятно, что при "разумных условиях" никто никогда не будет в третьей позиции говорить "чек". Но Вы, зачем то, учли эти "страшно большие" цифры из последнего столбца при вычислении $\langle q_i\rangle$.
Мне не понятно что обозначают числа в матрице $D$. Если они обозначают, что находясь во второй позиции я могу либо выиграть $5$ монет либо проиграть $600$ монет, то среднее $-595$ (то есть я не рекомендовал бы говорить "чек").

 Профиль  
                  
 
 Re: Оптимальная стратегия.
Сообщение19.02.2024, 22:33 
Заслуженный участник
Аватара пользователя


01/09/13
4318
SergeyGubanov в сообщении #1630266 писал(а):
находясь во второй позиции я могу либо выиграть $5$ монет либо проиграть $600$ монет

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 20 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group