Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.