The convexity of the barter exchange problem

This article presents a mathematical model for a barter exchange problem involving multiple agents and assets, where each agent has a utility function based on selling one asset for another at a desired exchange rate. The authors define the set of acceptable trades for each agent and formulate the overall market constraint that the total amount of each asset sold must be greater than or equal to the total amount bought. The goal is to find the optimal trades that maximize the sum of all agents' utility functions subject to these constraints.

The convexity of the barter exchange problem In a universe of \ n\ assets and \ m\ trading agents, we consider a barter exchange problem in which the \ j\ -th agent has an initial endowment of \ \Delta {j}\geq0\ units of the \ i\ -th asset and he is willing to sell it for at least \ \Lambda {j}\geq0\ units of asset \ k\ according to a certain utility function. Of course, the more favorable the exchange rate, the higher is the utility of the trader. To capture this, one could consider the utility function of the \ j\ -th agent as \ \begin{align } U j x {j}, y {j} = y {j}-x {j} \frac{\Lambda {j}}{\Delta {j}} - \delta x {j}| 0,\Delta {j} - \delta y {j}|\mathbb{R} + \end{align }\ Where \ x {j}\ is the variable representing the amount of asset \ i\ that the \ j\ -th agent is willing to sell, \ y {j}\ is the amount of asset \ k\ that the \ j\ -th agent is willing to buy and the indicator functions are used to encode the natural constraints regarding: - The limited expenditure of asset \ i\ capped by the initial endowment \ \Delta {j}\ : \ \delta x {j}\| 0,\Delta {j} \ - The non-negative amount of asset \ k\ that the agent is willing to buy: \ -\delta y {j}\|\mathbb{R} + \ Notice that \ \text{dom} U j = 0,\Delta {j} \times\mathbb{R} +\ is an unbounded hyper-rectangle describing the set of trades which satisfy the natural trading constraints but that they might not be desirable for the agent when associated with a negative utility like the trade \ \Delta {j}, 0 \ . On the other hand, the zero-upper level set of this function \ \begin{align } U^{ 0 } j = \{ x {j}, y {j} \in \mathbb{R}^2 \;|\; y {j}-x {j} \frac{\Lambda {j}}{\Delta {j}} \geq 0, \; 0\leq x {j}\leq\Delta {j},\; y {j}\geq 0\} \end{align }\ denotes the set of trades which are acceptable for the agent because the effective exchange rate is at least the desired one, indeed for a positive supplied amount \ x {j} 0\ , one has that \ \begin{align } x {j} 0 \;\land \; x {j}, y {j} \in U^{ 0 } j \iff \frac{y {j}}{x {j}}\geq \frac{\Lambda {j}}{\Delta {j}}\;\land \; 0< x {j}\leq\Delta {j}\;\land\; y {j}\geq 0 \end{align }\ Moreover, notice also that the zero-trade is always acceptable for the agent, i.e. \ 0,0 \in U^{ 0 } j\ , being a trade associated with a utility of zero. Of course, in an unconstrained setting, the optimal trade would be \ 0,\infty \ being \ U j\ unbounded from above. So now it’s time to encode the constraints according to which the sum of the amounts collected by all the agents must be lower or equal to the sum of the amounts supplied by all the agents. To do this, one has to project in higher dimension the scalar amounts spent and collected by the agents. In particular, one can build the matrix \ M x\in\mathcal{M} n,m \ such that \ M x {i,j}=1\ if the \ i\ -th asset is sold by the \ j\ -th agent and \ M x {i,j}=0\ otherwise. In other words, denoting with \ e {xj}\in\mathbb{R}^n\ the unit vector of the canonical basis which is one if the \ i\ -th asset is sold by the \ j\ -th agent and zero otherwise, one has that \ \begin{align } M x = \begin{bmatrix} | & & |\\ e {x1} & \dots & e {xm}\\ | & & | \end{bmatrix} \end{align }\ Similarly, one can build the matrix \ M y\in\mathcal{M} n,m \ such that \ M y {i,j}=1\ if the \ i\ -th asset is bought by the \ j\ -th agent and \ M y {k,j}=0\ otherwise. \ \begin{align } M y = \begin{bmatrix} | & & |\\ e {y1} & \dots & e {ym}\\ | & & | \end{bmatrix} \end{align }\ As a result, stacking the amounts sold by each agent in the vector \ x= x 1,\dots,x m \ and the amounts bought by each agent in the vector \ y= y 1,\dots,y m \ , the constraint can be written as \ \begin{align } M x x \succeq M y y \end{align }\ Where the generalized inequality means that \ M x x - M y y \in\mathbb{R}^n +\ In other words, the goal is to find the optimal trades which solve the following optimization problem \ \begin{align } \sup {\{x, y\}} \quad& \sum {j=1}^m U j x {j}, y {j} \\ \text{s.t.} \quad& M x x \succeq M y y\\ \quad& x j = \langle e {xj}, x \rangle &\quad \forall j=1,\dots,m\\ \quad& y j = \langle e {yj}, y \rangle &\quad \forall j=1,\dots,m\\ \quad& x {j}, y {j} \in U^{ 0 } j &\quad \forall j=1,\dots,m \end{align }\ In explicit form, this corresponds to \ \begin{align } \sup {\{x, y\}} \quad& \sum {j=1}^m y {j}-x {j} \frac{\Lambda {j}}{\Delta {j}}\\ \text{s.t.} \quad& M x x \succeq M y y\\ \quad& x j = \langle e {xj}, x \rangle &\quad \forall j=1,\dots,m\\ \quad& y j = \langle e {yj}, y \rangle &\quad \forall j=1,\dots,m\\ \quad& y {j}-x {j} \frac{\Lambda {j}}{\Delta {j}}\geq0 &\quad \forall j=1,\dots,m\\ \quad& y {j} \geq 0 &\quad \forall j=1,\dots,m\\ \quad& x {j} \geq 0 &\quad \forall j=1,\dots,m\\ \quad& x {j} \leq \Delta {j} &\quad \forall j=1,\dots,m \end{align }\ Now call \ \Delta = \Delta 1,\dots,\Delta m \ , \ \Lambda = \Lambda 1,\dots,\Lambda m \ so that \ \text{diag} \Delta ^{-1} \Lambda\ is the vector of minimal exchange rates for each agent. The optimization problem can be rewritten as \ \begin{align } \sup {\{x, y\}} \quad& \langle 1, y- \text{diag} \Delta ^{-1} \text{diag} \Lambda x \rangle\\ \text{s.t.} \quad& M x x \succeq M y y\\ \quad& y \succeq\text{diag} \Delta ^{-1} \text{diag} \Lambda x\\ \quad& x \in \mathbb{R}^m +,\\ \quad&y \in \mathbb{R}^m +\\ \quad& x \preceq \Delta \end{align }\ Moreover, calling \ z=y- \text{diag} \Delta ^{-1} \text{diag} \Lambda x\ one can convert the barter exchange problem to an equivalent linear program \ \begin{equation} \begin{aligned} \sup {\{x, y, z\}} \quad& \langle 0,0,1 , x,y,z \rangle\\ \text{s.t.} \quad& \begin{bmatrix}\text{diag} \Delta ^{-1} \text{diag} \Lambda , -I, I\end{bmatrix} \begin{bmatrix} x\\ y\\ z \end{bmatrix}=0\\ \quad&\begin{bmatrix} -M x & M y & 0\\ I & 0 & 0 \end{bmatrix} \begin{bmatrix} x\\ y\\ z \end{bmatrix} \preceq \begin{bmatrix} 0\\ \Delta \end{bmatrix}\\ \quad& x \in \mathbb{R}^m +,\\ \quad& y \in \mathbb{R}^m +,\\ \quad& z \in \mathbb{R}^m + \end{aligned} \end{equation}\ Indeed, by calling \ \begin{align } &t= x,y,z \in\mathbb{R}^{3m}\\ &c= 0,0,1 \in \mathbb{R}^{3m}\\ &A=\begin{bmatrix}\text{diag} \Delta ^{-1} \text{diag} \Lambda , -I, I\end{bmatrix} \in \mathbb{R}^{m\times 3m}\\ &b=0 \in \mathbb{R}^m\\ &G=\begin{bmatrix} -M x & M y & 0\\ I & 0 & 0 \end{bmatrix} \in \mathbb{R}^{ n+m \times 3m} &h=\begin{bmatrix} 0\\ \Delta \end{bmatrix} \in \mathbb{R}^{n+m} \end{align }\ one has that the problem above can be written as \ \begin{align } \sup {t} \quad& \langle c, t \rangle\\ \text{s.t.} \quad& A t = b\\ \quad& G t \preceq h\\ \quad&t\succeq 0 \end{align }\ resembling the standard form of a linear program in standard form.