  This work initiates research into the problem of determining an optimal
investment strategy for investors with different attitudes towards the
trade-offs of risk and profit. The probability distribution of the return
values of the stocks that are considered by the investor are assumed to be
known, while the joint distribution is unknown. The problem is to find the best
investment strategy in order to minimize the probability of losing a certain
percentage of the invested capital based on different attitudes of the
investors towards future outcomes of the stock market.
  For portfolios made up of two stocks, this work shows how to exactly and
quickly solve the problem of finding an optimal portfolio for aggressive or
risk-averse investors, using an algorithm based on a fast greedy solution to a
maximum flow problem. However, an investor looking for an average-case
guarantee (so is neither aggressive or risk-averse) must deal with a more
difficult problem. In particular, it is #P-complete to compute the distribution
function associated with the average-case bound. On the positive side,
approximate answers can be computed by using random sampling techniques similar
to those for high-dimensional volume estimation. When k>2 stocks are
considered, it is proved that a simple solution based on the same flow concepts
as the 2-stock algorithm would imply that P = NP, so is highly unlikely. This
work gives approximation algorithms for this case as well as exact algorithms
for some important special cases.
