Bounded-Loss Private Prediction Markets

Rafael M. Frongillo, Bo WaggonerNeurIPS 2018 · OpenReview

Introduction

Prediction markets are powerful mechanisms for aggregating information and have recently emerged as a novel way to "purchase" data for machine learning models. In these setups, participants are financially rewarded for contributing data that improves a global model. However, a fundamental conflict exists in this ecosystem between privacy and profitability.

To protect participant data using Differential Privacy, market makers must inject random noise into market prices. Unfortunately, clever traders can exploit this randomness, creating arbitrage opportunities that drain the market maker's budget. Previous research suggested that maintaining a truly private market might require an infinite financial subsidy to cover these losses as more participants join. This paper addresses a critical question: Can we guarantee differential privacy in a prediction market without risking bankruptcy?

The Proposed Mechanism

The authors introduce a novel mechanism that achieves a strictly bounded financial loss, making it a viable tool for crowdsourcing sensitive machine learning data. They accomplish this through two primary strategies:

1. Transaction Fees as a Shield

By implementing a carefully calculated transaction fee, the market maker can neutralize the expected profit from noise-based arbitrage. The fee is calibrated to match the market's "precision" (the amount of injected noise). Consequently, traders only find it profitable to participate if their actual information outweighs the cost of the fee.

This creates a "dead zone" around the current price. If a trader's belief differs from the market price only slightly (likely due to the privacy noise), the fee makes trading unattractive. This effectively separates informed traders from noise-exploiting traders, slowing the budget drain from linear growth to a much more manageable logarithmic growth ($O(\log^2 T)$).

2. The Adaptive "Doubling Trick"

To transition from a logarithmic budget drain to a strictly constant budget—one that does not grow at all with the number of participants ($T$)—the authors employ an adaptive, staged approach. Syntactically similar to the "doubling trick" used in online learning algorithms, the market runs in stages. Transaction fees collected in one stage are used to subsidize the next, larger stage.

These strategies are built upon a cost-function framework that extends standard automated market makers (like the Logarithmic Market Scoring Rule) into the Reproducing Kernel Hilbert Space (RKHS) to accommodate complex machine learning hypotheses.

Key Theoretical Results

As a theoretical work focused on mechanism design, the paper relies on mathematical proofs rather than empirical datasets. The core contributions include:

  • Bounded Loss (Theorem 3): The primary result proves that the adaptive market achieves $(\epsilon, \delta)$-differential privacy with a total financial loss bounded by a constant, regardless of how many participants join the market.
  • Incentive Compatibility: The mechanism maintains "$\alpha$-incentive," ensuring participants still have a strictly positive expected profit if their private information improves upon the market's current noisy prediction.
  • Market Precision: The injected privacy noise does not break the market's utility; prices remain accurate within a defined margin ($\alpha$) with high probability.
  • Self-Sustaining Dynamics: A surprising insight is that a private market can eventually become profitable for the designer. Once informed traders correct the price to its true value, subsequent participants merely pay transaction fees without increasing the market maker's risk.
  • Connection to Learning Theory: The authors demonstrate that their market update rules are essentially a kernelized version of the "Follow-the-Regularized-Leader" (FTRL) optimization algorithm, reinforcing the deep connection between prediction markets and machine learning.

Limitations and Future Directions

While the budget is theoretically bounded, the derived mathematical constant ($B$) in the proofs is quite large. Practical implementation will require optimizing these constants to make the initial budget affordable for typical researchers.

Additionally, the current proofs assume the predicted random variables are bounded; extending this framework to unbounded variables remains an open challenge. Finally, the authors suggest that future research should explore "parameterized" settings (such as linear regression) rather than strictly kernel-based settings, which may yield greater efficiency for specific real-world machine learning tasks.

Summary updated

Abstract

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.
BibTeX
@inproceedings{frongillo2018bounded,
  author = {Rafael M. Frongillo and Bo Waggoner},
  title = {{Bounded-Loss Private Prediction Markets}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=SyE9Ew-_WS},
}

Loading related content...

Figure