  This paper derives a robust on-line equity trading algorithm that achieves
the greatest possible percentage of the final wealth of the best pairs
rebalancing rule in hindsight. A pairs rebalancing rule chooses some pair of
stocks in the market and then perpetually executes rebalancing trades so as to
maintain a target fraction of wealth in each of the two. After each discrete
market fluctuation, a pairs rebalancing rule will sell a precise amount of the
outperforming stock and put the proceeds into the underperforming stock. Under
typical conditions, in hindsight one can find pairs rebalancing rules that
would have spectacularly beaten the market. Our trading strategy, which extends
Ordentlich and Cover's (1998) "max-min universal portfolio," guarantees to
achieve an acceptable percentage of the hindsight-optimized wealth, a
percentage which tends to zero at a slow (polynomial) rate. This means that on
a long enough investment horizon, the trader can enforce a compound-annual
growth rate that is arbitrarily close to that of the best pairs rebalancing
rule in hindsight. The strategy will "beat the market asymptotically" if there
turns out to exist a pairs rebalancing rule that grows capital at a higher
asymptotic rate than the market index. The advantages of our algorithm over the
Ordentlich and Cover (1998) strategy are twofold. First, their strategy is
impossible to compute in practice. Second, in considering the more modest
benchmark (instead of the best all-stock rebalancing rule in hindsight), we
reduce the "cost of universality" and achieve a higher learning rate.
