Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.