Profitable Prediction Market Making

We take advantage of the correspondence between online learning algorithms design for negative regrets under certain predictable (or regular) losses and protable prediction market makers design under some patterns of trade sequences. Thus, we adopt the optimistic (or double) lazy-update mirror descent algorithm: when in each time step, a leader is called a \strong" one compared with the other non-minimizers in terms of its much little current cumulative loss, the regret would be negative in this case, and the more frequent changes of leaders the more negative of the regret. Moreover, if the immediately previous loss vector is a good estimator of the current loss vector, the regret stays negative. On the other hand, we are using the modified double-update multiplicative update algorithm of for catching the switches of \dominant experts" quickly enough to beat a fixed best expert in hindsight in cumulative losses thereby to obtain negative regrets.國立清華大學, 科技部, AAAC, 演算法與計算理論學會補正完