# Decision problem for existence of arbitrage portfolio

Given $m$-dimensional vector $p$ (price vector), and $m\times n$ matrix $X$ ($m$ securities' payoffs in $n$ states) for arbitrary $m$ and $n$, is there an algorithm to decide if there exists $h\in \mathbb{R}^m$ (arbitrage portfolio) such that

$$hX\geq 0\quad \mbox{and}\quad hp<0 \qquad \tag{1}$$

If $X$, $p$ and $h$ can have only integer entries, can we still decide?

I know that by Farkas' Lemma that equation $(1)$ is true iff there exists $q\in \mathbb{R}^n$ such that

$$p=Xq\quad \mbox{and}\quad q\geq 0$$

But this doesn't seem to help answer the question, either.

-
In $\mathbb{R}^m$, both the problem and its dual are just linear programs, ie, $\min \{ h p | h X \geq 0 \}$, for which there are lots of solvers. I don't know much about discrete problems. – copper.hat Apr 4 '12 at 17:46
@copper.hat: Yes, you're right... For integer matrix and vectors, just solve $\min \{ h p | h X \geq 0 \}$ for $h$ using one of those algorithms, since $h$ must be rational, integer $\bar{h}$ can be obtained by multiplying h by a common multiple of its entries. – Eric Apr 5 '12 at 2:57