1
$\begingroup$

I have a question about Ex 1.11 of "Linear Optimization" by Bertsimas, Tsitsiklis:

Suppose that there are $N$ available currencies, and assume that one unit of currency $i$ can be exchanged for $r_{ij}$ units of currency $j$. (Naturally, we assume that $r_{ij} > 0$.) There also certain regulations that impose a limit $u_i$ on the total amount of currency $i$ that can be exchanged on any given day. Suppose that we start with $B$ units of currency $1$ and that we would like to maximize the number of units of currency $N$ that we end up with at the end of the day, through a sequence of currency transactions. Provide a linear programming formulation of this problem. Assume that for any sequence $i_1, \dots, i_k$ of currencies, we have $r_{i_1 i_2} r_{i_2 i_3} \dots r_{i_{k-1} i_k} r_{i_k i_1} \leq 1$, which means that wealth cannot be multiplied by going through a cycle of currencies.

I think I am probably misunderstanding the question, but we have B units of currency 1 at the start and at most $u_1$ of currency 1 can be exchanged so I think the most of currency N we can get is $min(u_1, B)*r_{1N}$. This is because if B > $u_1$ then at most $u_1$ can be exchanged and there is no point in converting to any other intermediate currency and then currency N because this leads to at most the same amount of currency N as without converting to intermediate currencies, as otherwise we are profitting by arbitrage. And if B <= $u_1$ then we convert all B units of currency 1 to N in a single transaction. Can anyone tell me if I am missing something?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

The idea is that by converting via one or more intermediate currencies, you could end up with a larger amount of the target currency N than you would get if you were to convert directly from currency 1 to currency N. If there was no limit $u_i$ then there would exist exactly one chain that maximizes the total amount of currency N and you would use your full budget B to follow this chain. But because there's a limit you will have to split the money over multiple chains including chains with lower profits.

Hint: there can never be more than N conversions in a single chain.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Why at most N conversions? $\endgroup$
    – prubin ♦
    Nov 17 at 15:55
  • $\begingroup$ @prubin there are only $N$ currencies available. Let's say $N=3$. Then the longest chain would be $i_1$ -> $i_2$ -> $i_3$. A longer chain would involve converting back to an earlier currency, e.g $i_1$ -> $i_2$ -> $i_1$-> $i_3$. But that would imply that I can infinitely repeat this cycle and continue to increase my value. Perhaps I should have written 'the longest chain contains at most N conversions', because technically you could split the budget and have several parallel flows of money, e.g. $i_1$->$i_3$ and $i_1$->$i_2$->$i_3$ if $u_2$ = $B/2$, thereby having 4>N conversions. $\endgroup$
    – Joris Kinable
    Nov 17 at 16:38
  • $\begingroup$ Suppose that $N=6,$ $B=10,$ and $r_{ij}=1$ for $(i,j)\in\left\{ (1,2),(1,3),(2,4),(2,5),(3,5),(4,6),(5,6)\right\} $ and $r_{ij}=\epsilon$ otherwise, where $\epsilon$ is very close to 0. The best we can hope for is to end up with 10 units of currency 6. Suppose further that $u=(10,5,5,1,9,\infty)$, noting that $u_{6}$ is irrelevant. ... $\endgroup$
    – prubin ♦
    Nov 18 at 19:50
  • $\begingroup$ ... The optimal solution is $1\rightarrow2:5,$ $1\rightarrow3:5,$ $2\rightarrow4:1,$ $2\rightarrow5:4,$ $3\rightarrow5:5,$ $4\rightarrow6:1$ and $5\rightarrow6:9$, where $i\rightarrow j:k$ means convert $k$ units of currency $i$ into currency $j$ (with exchange ratio 1 to 1). That has 7 transfers. $\endgroup$
    – prubin ♦
    Nov 18 at 20:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.