Poster
Convergence Analysis of Prediction Markets via Randomized Subspace Descent
Rafael Frongillo · Mark Reid

Mon Dec 7th 07:00 -- 11:59 PM @ 210 C #95 #None
in Poster Session »

Prediction markets are economic mechanisms for aggregating information about future events through sequential interactions with traders. The pricing mechanisms in these markets are known to be related to optimization algorithms in machine learning and through these connections we have some understanding of how equilibrium market prices relate to the beliefs of the traders in a market. However, little is known about rates and guarantees for the convergence of these sequential mechanisms, and two recent papers cite this as an important open question.In this paper we show how some previously studied prediction market trading models can be understood as a natural generalization of randomized coordinate descent which we call randomized subspace descent (RSD). We establish convergence rates for RSD and leverage them to prove rates for the two prediction market models above, answering the open questions. Our results extend beyond standard centralized markets to arbitrary trade networks.

Author Information

Rafael Frongillo (CU Boulder)
Mark Reid (Australia National University)

More from the Same Authors