Convergence Analysis of Prediction Markets via Randomized Subspace Descent
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.
Summary of paper: The authors consider the rate of convergence to price equilibrium in prediction markets.They exploit techniques from convex analysis and programming to derive new such bounds for a variety of settings.In more detail, they consider a potential-based market maker and a number of traders whose preferences are modeled by a risk measure. The market maker can be interpreted as a constant-risk agent.All players have initial positions in k securities.Trading dynamics can be naturally interpreted as local rebalancing the positions of a subset of players to minimize their total risk (subject to the sum of their positions remaining the same). Thus the question of convergence rate is closely related to the question of convergence of gradient descent, where at each iteration only a subset of coordinates are allowed to be updated.The authors adapt techniques from the latter problems to prove convergence rate bounds for the former problems. Quality: I am in favor of further developing the connections between convex optimization and prediction market design and analysis.The question of convergence in prediction markets is clearly interesting and, perhaps surprisingly, does not seem very well understood yet.My one complaint about the paper is that the exact technical statement could be more clearly stated and discussed.For example, in Theorem 3, it seems that there is a lot of detail hidden within the "constant" R(x^0).Specifically, this depends not only on x^0, but also on the details of the projections (the \Pi_i's) and how "overlapping" they are.In the proof of Theorem 3 in the supplementary, the matrix A (used in the norm in (10) and subsequently) is undefined.Apparently, going by Section D.2, the devil is largely in the details of this A and its properties.The submission would benefit from a more transparent discussion in the main body about when the convergence rate is good and when it is not.Clarity: The writing is usually good, though see technical comments above.Originality: As far as I know, the connection between the convergence analysis of gradient descent variations and prediction markets is original.Significance: I think this is a significant contribution to the literature on prediction markets.