Тривиальный натуральный обмен

Пусть мы хотим сделать честную систему обмена $n$ товаров, чтобы при этом можно было поменять любой товар на любой другой и не было арбитража.

💡

Кратко про то, что такое арбитраж. Арбитраж - это ситуация, когда путем некоторых действий можно из ничего получить что-то. В нашем случае, могуть быть два вида арбитража: простой и сложный. Простой арбитраж это обмен последовательности товаров друг на друга и обмен на исходный так, чтобы в результате исходного товара получилось больше, чем было раньше. Сложный арбитраж это то же самое, но с несколькими товарами одновременно. К счастью он у нас и не возникнет. Следует так же выделить простейший простой арбитраж, который мы назовем тривиальным: товар $p$ обменивается на товар $q$ и затем сразу же обменивается обратно.

Для анализа таких систем хочется иметь способ осмысленно работать с всеми возможными обменами товаров. Для этого введем матрицу курса обменов $K$:

$K$ - назовем матрицей курса обменов, если ее элементы $k_{ij}$ - количество $j$-го товара, которое можно получить за один $i$-ый товар.

Сразу же очевидны некоторые свойства этой матрицы:

• $K$ - вещественная квадратная матрица размера $n\times n$

• $k_{ii}=1\ \ \ \forall\ i=1..n$

• $k_{ij}k_{ji}=1$

Последнее свойство задает как честность покупки и продажи, которая осуществляется по одной и той же цене, так и запрещает тривиальный арбитраж.

Потребуем кроме этого невозможность простого арбитража:

• $k_{\alpha_1\alpha_2}k_{\alpha_2\alpha_3}..k_{\alpha_{m-1}\alpha_m}k_{\alpha_m\alpha_1}=1$ для любых $\alpha_1..\alpha_m=1..n$

Для упрощения записи введем пару обозначений:

• будем обозначать элемент матрицы $k_{ij}$ как $i\to j$

• в произведении элементов матрицы будем сокращать рядом стоящие элементы: $k_{ij}k_{jp}=(i\to j)(j\to p)=i\to j\to p$

Тогда запрет простого арбитража можно записать проще:

❗

$\alpha_1\to\alpha_2\to\alpha_3\to..\to\alpha_{m-1}\to\alpha_m\to\alpha_1=1$ для любых $\alpha_1..\alpha_m=1..n$

В частности, тривиальный арбитраж:

$i\to j\to i = 1$

При наличии указанного свойства запрета простого арбитража оказывается, что матрица $K$ имеет простое описание. Убедимся в этом, исследовав ее подробнее.

Во-первых найдем определитель матрицы. Для этого можно взять стандартное определение определителя через сумму произведений:

$\det(K)=\sum_{\sigma\in S_n}(-1)^{sgn(\sigma)}\prod_{i=1}^n k_{i\sigma(i)}$

Вспоминая, что любую перестановку можно записать в виде непересекающихся циклов(перестановок-смещений): $\sigma=\sigma_1..\sigma_l$, упрощаем произведение:

$\prod_{j=1}^l\prod_{i\in\sigma_j}i\to\sigma(i)=\prod_{j=1}^l 1=1$

Отсюда $det(K)=0$. Значит в некотором смысле "размерность $K$" меньше $n$. Далее мы увидим, что можно избавиться от одного товара, не меняя коэффициенты обмена.

Для начала рассмотрим простой случай, когда есть некая валюта, за которую все товары можно купить/продать. Обозначим за $p_i$ - цену i-го товара. Тогда естественно задать матрицу $K$ следующим образом:

$i\to j=\frac{p_i}{p_j}$

Очевидно, что соблюдаются все свойства матрицы обмена, в том числе и свойство отсутствия простого арбитража. При таком задании матрицы обмена, видно, что ее можно представить в качестве следующего произведения:

$K=\begin{pmatrix} \frac{p_1}{p_1} & .. & \frac{p_1}{p_n} \\ : & \ddots & : \\ \frac{p_n}{p_1} & .. & \frac{p_n}{p_n} \end{pmatrix}=\begin{pmatrix} p_1 \\ : \\ p_n \end{pmatrix}\begin{pmatrix} \frac{1}{p_1} & .. & \frac{1}{p_n} \end{pmatrix}$

Что позволяет легко обращаться с данной матрицей далее. Например при вычислении вектора обмена - сколько товаров одного вида можно получить, имея на руках $c_i$ штук $p_i$-ого товара:

$\begin{pmatrix}c_1 & .. & c_n\end{pmatrix}K=\begin{pmatrix}c_1 & .. & c_n\end{pmatrix}\begin{pmatrix}p_1 \\ : \\ p_n\end{pmatrix}\begin{pmatrix}\frac{1}{p_1} & .. & \frac{1}{p_n}\end{pmatrix}=S\begin{pmatrix}\frac{1}{p_1} & .. & \frac{1}{p_n}\end{pmatrix}=\begin{pmatrix}\frac{S}{p_1} & .. & \frac{S}{p_n}\end{pmatrix}$

Где $S=c_1p_1+..+c_np_n$ - суммарная стоимость наших товаров.

Хорошо, если бы матрица $K$ всегда имела такой вид. Рассмотрим случай, когда у нас нет валюты, за которую можно купить любой товар. Но пусть есть один товар(не умаляя общности он будет под номером 1), который можно обменять на любой другой, то есть $1\to i\neq 0$, тогда можно определить цены товаров, как

$p_i=i\to 1=\frac{1}{1\to i}$

И далее, как раньше, элементы матрицы будут задаваться, как:

$k_{ij}=\frac{p_i}{p_j}=\frac{i\to 1}{j\to 1}=i\to 1\to j$

То есть, вся матрица будет задаваться коэффициентами обмена первого товара. Значит его можно убрать из списка товаров, сделать валютой и применить теорию с валютой, описанную выше.

Теперь, пусть некоторые товары нельзя обменять друг на друга: $i→j=j→i=0$. Это потребует небольшого уточнения определения матрицы $K$, но ничего страшного не произойдет. Тогда (кажется, что) матрица $K$ будет представима в блочно-диагональном виде:

$K=\begin{pmatrix}K_1 & 0 & 0 & 0 & 0 \\ 0 & K_2 & 0 & 0 & 0 \\ 0 & 0 & \ddots & 0 & 0 \\ 0 & 0 & 0 & K_{l-1} & 0 \\ 0 & 0 & 0 & 0 & K_l\end{pmatrix}$

Причем матрицы $K_1..K_l$ не содержат нулевые элементы, то есть набор товаров разделен на $l$ групп, в которых любой товар внутри группы можно обменивать на любой другой товар той-же группы. Мне лень строго это доказывать, но кажется, что это верно, в силу следующего факта:

$\left\{\begin{matrix}i\to j=0 \\ i\to k\neq 0\end{matrix}\right.\Rightarrow\left\{\begin{matrix}i\to j=0 \\ k\to i\neq 0\end{matrix}\right.\Rightarrow k\to j=k\to i\to j=0$

Если это действительно так, то для каждой группы можно взять любой товар из нее, как валюту для этой группы и уменьшить общий набор товаров до $n-l$ при этом упростив всю матрицу обмена до вектора цен.