Список заданий по ТИгр 2022 весна

1. Для комбинаторной игры $A=\{L|R\}$ определим игру $-A$. $-0=0$, для других игр пусть $L=\{g^L_1, g^L_2, \ldots\}$, $R=\{g^R_1, g^R_2, \ldots\}$, определим $-L=\{-g^L_1, -g^L_2, \ldots\}$, $-R$ определяется аналогично, $-A = \{-R|-L\}$. Что можно сказать про игру $A+(-A)$? Далее будем обозначать игру $A + (-B)$ как $A-B$.
2. На лекции было введено определение эквивалентности $A \approx B$ если для любой игры $C$ исход $A+C$ и $B+C$ одинаковый. Можно ввести альтернативное определение: скажем, что $A\approx B$, если $A-B$ проигрышная для текущего игрока (класс $P$). Докажите, что эти определения дают одно и то же отношение эквивалентности. Далее нам не очень интересно различать эквивалентные игры, поэтому мы будем для простоты называть их равными и использовать значок $=$.
3. Докажите формально, что сумма игр ассоциативна и коммутативна.
4. Профессор дал неправильное определение и определил противоположную игру для $A=\{L|R\}$ как $\mathbin{\scriptstyle\dot{\smash{\textstyle-}}} A = \{R|L\}$. Поясните, почему определение профессора плохо подходит для введения операции "минус" на играх.
5. Профессор дал неправильное определение и определил противоположную игру для $A=\{L|R\}$ как $!A = \{!L|!R\}$. Поясните, почему определение профессора плохо подходит для введения операции "минус" на играх.
6. Будем говорить, что игра $A$ является положительной, если в ней выигрывает игрок L и писать $A>0$. Докажите, что если $A > 0$ и $B > 0$, то $A+B>0$.
7. Будем говорить, что $A > B$, если $A-B>0$. Докажите, что отношение $>$ является антирефлексивным, антисимметричным и транзитивным (строгий порядок).
8. Определим неотрицательные целые числа по формуле $G_0 = \{|\}$, $G_n = \{G_{n-1}|\}$ (далее мы будем вместо $G_n$ писать просто $n$, но в этом задании без отдельного обозначения не обойтись). Докажите, что $G_n+G_m = G_{n+m}$.
9. Определите отрицательные целые числа. Докажите, что все законы для целых чисел как для группы по сложению выполнены. Мы вернемся к числам в одной из ближайших лекций, а пока переключаемся на матричные игры.
10. Приведите пример биматричной игры, в которой есть более одной различной точки равновесия по Нэшу, выигрыши игроков в которых различаются.
11. Лемма о масштабе Пусть матрица $A$ имеет седловую точку. Рассмотрим матрицу $B$, определенную соотношением $b_{ij} = ka_{ij}+d$, $k > 0$. Докажите, что матрица $B$ имеет седловую точку, причем множества координат седловых точек этих матриц совпадают.
12. Рассмотрим пример экономической игры с бесконечным множеством стратегий: дуополия Курно. На рынке есть две фирмы, стратегии которых заключаются в производстве $q_1$ и $q_2$ товара, соответственно. Цена за единицу товара равна $p-q_1-q_2$. Себестоимость единицы товара $c$. Соответственно, выигрыши игроков равны $u_1(q_1,q_2)=(p-q_1-q_2-c)q_1$ и $u_2(q_1,q_2)=(p-q_1-q_2-c)q_2$. Найдите равновесие по Нэшу для дуополии Курно.
13. Дуополия Бертрана. На рынке есть две фирмы, которые производят различные товары $A$ и $B$, соответственно, а их стратегии заключаются в установлении цены на товары $c_1$ и $c_2$, соответственно. После этого фирмы продают $Q_1 = q-c_1+kc_2$ и $Q_2 = q-c_2+kc_1$ единиц товара, соответственно. Себестоимость единицы товара $c$. Запишите выигрыши игроков в дуополии Бертрана и найдите равновесие по Нэшу.