Research map / Learning theory and algorithms / Submodular and game algorithms
Equilibrium of Data Markets with Externality
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Models fixed-price data markets with buyer externalities as a simultaneous game and shows a platform transaction cost based on predicted externalities yields a dominant-strategy or approximate pure equilibrium with strong welfare guarantees, extended to online learning and joint externality.
Problem
Fixed-price data markets where buyers can buy any set of datasets suffer negative externalities from each other due to free replicability; the equilibrium welfare of such markets is poor and buyers may not know their valuations a priori.
Approach
Model buyer interactions as a simultaneous game and introduce a platform transaction cost proportional to the difference between externality a buyer induces and suffers, computed from predicted externalities; this makes the buyer's dominant strategy the maximizer of effective utility with WRaE bounded by n(1-alpha) plus bias terms. Online learning uses a Hamming-metric zooming bandit adaptation.
Key results
- Without intervention the dominant-strategy equilibrium can have welfare regret of order n; with transaction cost alpha, WRaE is tightly bounded by n(1-alpha) plus bias terms.
- Under joint externality, an epsilon-PNE always exists with WRaE at most n/2 under the proposed transaction cost.
- Zooming-based learning gives instance-dependent effective regret; a worst-case bound of O(sqrt(2^k T log T)) follows from UCB-style analysis, and an improved bound O(k(sqrt(kT log T)+2^{0.58k} log T)) under a looser target-set condition.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| increase transaction-cost parameter α | standard externality model · synthetic AWS Data Exchange-derived market | social welfare | Helped |
| increase bias in the platform's externality estimate | standard externality model with transaction costs · synthetic AWS Data Exchange-derived market | social welfare | Hurt |
| use α=0.6 | standard externality model with transaction costs · synthetic AWS Data Exchange-derived market | social welfare | Helped |
| set α closer to 0.5 | joint externality model with transaction costs · synthetic AWS Data Exchange-derived market | social welfare | Helped |
| vary bias in the platform's externality estimate | joint externality model with transaction costs · synthetic AWS Data Exchange-derived market | social welfare | No clear effect |
Surprising findings
- Without intervention, the joint externality model can have no epsilon-pure equilibrium for epsilon < 1.
- The dominant-strategy equilibrium without intervention can have welfare regret of order n even though each buyer's choice is individually optimal.
Limitations
- Results depend on prediction bias of platform externality estimates; bias terms add to welfare regret.
- Experiments are synthetic rather than from real data market transactions.
- Joint externality guarantees are approximate (epsilon-PNE) rather than exact equilibria.
Experimental setup
Datasets: AWS Data Exchange categories (synthetic instantiation)
Benchmarks: synthetic data market simulation
Metrics: average percent increase in social welfare welfare regret at equilibrium effective regret cumulative welfare regret
Baselines: no intervention (alpha=0) UCB
Builds on: zooming algorithm UCB McDiarmid's inequality
Closest papers by meaning
- An Instrumental Value for Data Production and its Application to Data Pricing (ICML 2025 · similarity 0.86)
- Fair Online Bilateral Trade (NeurIPS 2024 · similarity 0.86)
- Heterogeneous Data Game: Characterizing the Model Competition Across Multiple Data Sources (ICML 2025 · similarity 0.85)
- Learning to Mitigate Externalities: the Coase Theorem with Hindsight Rationality (NeurIPS 2024 · similarity 0.85)
- Beyond Monotonicity: On the Convergence of Learning Algorithms in Standard Auction Games (AAAI 2025 · similarity 0.85)
- Decongestion by Representation: Learning to Improve Economic Welfare in Marketplaces (ICLR 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.