Approximation and Computation of Arbitrage in Frictional Foreign Exchange Market (Extended Abstract)

AbstractIn this paper we study the computational complexity of arbitrage in a frictional foreign exchange market with bid-ask spreads, bound and integrality constraints. We show that the problem of detecting the existence of arbitrage is NP-complete in the general case and, moreover, for some fixed ϵ > 0, approximating the optimal version of the problem within a factor of nϵ is NP-hard where n is the number of foreign currencies. On the other hand, we show that the optimal problem can be solved in polynomial time for two special cases of the constant number of currencies or a star-shaped exchange graph