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.
TL;DR
This paper introduces the first framework for private prediction markets that guarantees a bounded worst-case financial loss for the market maker. By combining a strategic transaction fee with an "adaptive growth" mechanism (similar to the doubling trick in online learning), the authors show how to protect participant privacy and incentivize accurate predictions without requiring an infinite budget.
The Problem: The Cost of Privacy
Prediction markets are powerful tools for aggregating information, often used to forecast elections or even crowdsource machine learning models. However, when participants contribute sensitive information (like personal medical data to improve a diagnostic model), their "trades" can leak private details.
Previous research successfully applied Differential Privacy (DP) to these markets to protect individuals. The catch? These private markets required a potentially unlimited financial subsidy. Because DP requires adding random noise to the market state, savvy traders can "bet against the noise," effectively performing arbitrage against the market maker. A 2016 study by Cummings et al. even suggested that unbounded loss might be an inherent tax on privacy. This paper challenges that notion, aiming to achieve the "holy grail" of private prediction markets: privacy, accuracy incentives, and a strictly capped budget.
Methods: Capping the Budget
The authors propose a two-step construction to fix the "leaky" budget and ensure the market maker's loss remains bounded:
- The Transaction Fee: They first show that a carefully calibrated transaction fee can offset the expected profit traders make from the privacy-preserving noise. If the fee is high enough to cover the "noise arbitrage" but low enough that traders with genuine information can still profit, the market maker’s loss becomes manageable—growing only logarithmically ($O(\log^2 T)$) with the number of participants $T$.
- Adaptive Market Size (The Doubling Trick): To turn that logarithmic growth into a truly constant budget, the authors use a sequence of "stages." The market starts small. If it reaches its capacity of participants, it "doubles" and moves to a new stage with a larger capacity and slightly adjusted parameters. The key insight is that completed stages actually generate a surplus from transaction fees, which then subsidizes the potential loss of the next, larger stage.
The mechanism relies on the "continual observation" technique from DP literature to add noise that is correlated over time, ensuring that the impact of noise on price accuracy remains low even as more trades occur.
Key Insights and Ideas
- Noise as Arbitrage: The fundamental conflict in private markets is that the randomness needed for privacy looks like a "bad trade" by the market maker that participants can exploit.
- Fees as a Privacy Tax: Instead of the market maker eating the cost of privacy, the transaction fee forces participants to "subsidize" the noise. This is socially acceptable because participants who have valuable information still expect a net profit.
- Informational vs. Non-Informational Traders: In a large market, only a few traders usually have "new" information. The "informational" traders might cost the market maker money, but the "non-informational" traders (who are just trading back and forth or responding to noise) pay fees that eventually turn the market maker’s loss into a profit.
- The Learning Connection: The authors demonstrate a deep link between their kernel-based market and Follow-the-Regularized-Leader (FTRL) algorithms, showing that market prices evolve similarly to weights in a kernelized online learning model.
Key Results
- Bounded Budget: The authors prove a constant upper bound on the designer's loss ($B$) that does not depend on the number of participants $T$. The bound is roughly proportional to $\frac{\sqrt{d}}{\alpha \epsilon} \log^2(\dots)$, where $d$ is the dimension of the prediction, $\alpha$ is the price accuracy, and $\epsilon$ is the privacy parameter.
- Privacy & Accuracy: The mechanism maintains $\epsilon$-differential privacy and $(\alpha, \gamma)$-precision, meaning market prices stay within $\alpha$ of the "true" (non-noisy) prices with high probability.
- Incentives: The market maintains a "$2\alpha$-incentive," meaning any participant who believes the true probability is more than $2\alpha$ away from the current market price has a strictly positive expected profit.
Limitations and Future Work
- Dimension Scaling: While the budget is constant relative to $T$, it still scales with the dimensionality of the outcome space. For very complex predictions, the required subsidy might still be high.
- Finite Outcome Spaces: In the section on "purchasing data" via kernels, the current proof assumes the set of possible labels ($Y$) is finite. The authors suggest this could be extended to infinite spaces using Gaussian process theory.
- Practical Implementation: The "doubling trick" involves discrete stages. The authors mention that a "continuous" version of liquidity adaptation (adjusting the market's sensitivity smoothly) would be a more elegant but mathematically more complex direction for future research.
Summary updated