Bounded-Loss Private Prediction Markets
Prior work has investigated variations of prediction markets that preserve participants' (differential) privacy, which formed the basis of useful mechanisms for purchasing data for machine learning objectives. Such markets required potentially unlimited financial subsidy, however, making them impractical. In this work, we design an adaptively-growing prediction market with a bounded financial subsidy, while achieving privacy, incentives to produce accurate predictions, and precision in the sense that market prices are not heavily impacted by the added privacy-preserving noise. We briefly discuss how our mechanism can extend to the data-purchasing setting, and its relationship to traditional learning algorithms.
This paper studies prediction markets: mechanisms where a series of buyers arrive and make bets on the outcome of a future event, where the prices of bets at a certain point of time reflect the information gathered so far about this outcome. Previous work by Waggoner et al studies differentially-private prediction markets, where no individual buyer's trade is inferrable from the overall sequence of market prices (this is accomplished by adding some amount of noise to each of the revealed market states). These markets have the downside that the expected cost to the mechanism designer of maintaining this differential privacy is unbounded, growing perhaps linearly in T (number of rounds/buyers). This paper extends the previous work by proposing new mechanisms that have bounded total cost to the mechanism designer. Specifically, the authors:  1. The authors show that adding an appropriately chosen transaction fee to the mechanism of Waggoner et al causes the total loss of the mechanism to be bounded by O(log^2 T). (Intuitively, the noise added to maintain differential privacy creates a small arbitrage opportunity for each of the buyers; adding a transaction fee on that scale eliminates this).  2. The authors then show how to "amplify" this O(log^2 T)-loss mechanism to construct a mechanism with O(1)-total loss. This works in a way reminiscent of the doubling trick -- after enough buyers have participated in the current mechanism, the mechanism fee restarts with different parameters (i.e. half the transaction fee).   I am not very familiar with the peer prediction literature (including the previous paper by Waggoner et al which this paper builds off of significantly), but this seems like a very strong result, addressing perhaps the largest problem with the previous construction for differentially private prediction markets. In fact, it is not at all clear a priori that a differentially private prediction market with loss bounded by a constant necessarily exists (indeed, Cummings et al show that any of a large class of differentially private prediction markets -- ones that just add some amount of noise to the market states -- must necessarily have unbounded loss).  The paper is well-written and easy to read. The proofs in the main body of the paper appear correct (although I have not checked the proofs in the appendix).