Computation of arbitrage in frictional bond markets

In this paper we study the computational problem of arbitrage in a frictional market with a finite number of bonds and finite and discrete times to maturity. Types of frictions under consideration include fixed and proportional transaction costs, bid–ask spreads, taxes, and upper bounds on the number of units for transaction. We develop a necessary and sufficient condition for the existence of arbitrage. In addition, we obtain some negative result on computational difficulty in general for arbitrage under those frictions: it is NP-complete to identify whether there exists a cash-and-carry arbitrage transaction and it is NP-hard to find an optimal cash-and-carry arbitrage transaction.