Source-linked AI summary
A Marketplace for Data: An Algorithmic Solution
Anish Agarwal, Munther Dahleh, Tuhin Sarkar
TL;DR
The paper addresses the difficulty of obtaining relevant training data and designing a real-time marketplace that matches buyers with sellers while handling computational complexity. It proposes a mathematical market model and algorithms, with theoretical guarantees for zero-regret pricing, approximate Shapley payments, and robustness to replication.
Problem
Firms can struggle to obtain relevant, high-quality training data, while a marketplace must fairly allocate aggregate buyer payments among sellers despite computational complexity.
Method
The paper models a two-sided data market and constructs mechanisms for feature allocation, price updates, and revenue division using Multiplicative Weights, Myerson’s payment function, and fairness notions for replicable goods.
Results
The algorithms achieve zero regret for price updates, an ϵ-approximation to Shapley payments with high probability in O(M2) time, and ϵ-robustness to replication.
Takeaways & Limitations
The proposed mechanisms provide a theoretically analyzed framework for real-time data markets involving combinatorial values and freely replicable training features.
Takeaways & Limitations
The architecture does not account for a firm’s utility depending on which other firms receive the same dataset, and the most balanced replication-robust revenue division mechanism remains an open question.
Abstract
from arXiv · showhide
In this work, we aim to design a data marketplace; a robust real-time matching mechanism to efficiently buy and sell training data for Machine Learning tasks. While the monetization of data and pre-trained models is an essential focus of industry today, there does not exist a market mechanism to price training data and match buyers to sellers while still addressing the associated (computational and other) complexity. The challenge in creating such a market stems from the very nature of data as an asset: (i) it is freely replicable; (ii) its value is inherently combinatorial due to correlation with signal in other data; (iii) prediction tasks and the value of accuracy vary widely; (iv) usefulness of training data is difficult to verify a priori without first applying it to a prediction task. As our main contributions we: (i) propose a mathematical model for a two-sided data market and formally define the key associated challenges; (ii) construct algorithms for such a market to function and analyze how they meet the challenges defined. We highlight two technical contributions: (i) a new notion of 'fairness' required for cooperative games with freely replicable goods; (ii) a truthful, zero regret mechanism to auction a class of combinatorial goods based on utilizing Myerson's payment function and the Multiplicative Weights algorithm. These might be of independent interest.
1 INTRODUCTION
The paper motivates a real-time two-sided marketplace for ML training data, whose design must handle data’s replication, combinatorial value, task-dependent usefulness, and difficult prior verification. It proposes a mathematical market architecture and algorithms that match data to prediction tasks, allocate revenue, and update prices.
- 1 INTRODUCTION: Data marketplaces are needed because firms increasingly require high-quality training data for real-time ML prediction tasks.Relevant data can be difficult for firms—especially early adopters—to obtain independently.
- 1 INTRODUCTION: Data’s zero-cost replication, correlated signals, task-specific accuracy values, and difficult a priori usefulness verification complicate pricing and exchange.A dataset may be predictive for one task but have little use for another.
- 1 INTRODUCTION: Unlike ad and prediction markets, a data marketplace must discover which datasets are collectively predictive and cheap enough because buyers lack reliable priors on individual dataset usefulness.Free replication also makes conventional second-price auction approaches infeasible.
- 1 INTRODUCTION: The proposed marketplace models buyers, sellers, and their interactions while addressing combinatorial data, absent usefulness priors, and heterogeneous prediction tasks.The model formally frames truthful valuation, revenue maximization, fair seller payments, and efficient computation as core challenges.
- 1 INTRODUCTION: The algorithms provide truthful allocation and pricing, fair revenue division, and replication-robustness mechanisms for the proposed data market.The paper highlights a new fairness notion and a truthful, zero-regret combinatorial auction mechanism using Myerson’s payment function and Multiplicative Weights.
- 1 INTRODUCTION: In the motivating workflow, buyers submit prediction tasks and accuracy-based bids; the market supplies affordable features, fits an ML model, collects performance-based revenue, pays sellers, and updates prices.Evaluation may use an out-of-sample test set or future unseen demand.
2 THE MODEL - PARTICIPANTS AND DYNAMICS
The model represents sellers as providers of data features and buyers as purchasers seeking improved prediction accuracy. The marketplace maps bids, prices, prediction tasks, and available features into revenue, allocation, and predictions while simplifying price updates through a scalar price.
- Participants: Each seller supplies a data feature Xj ∈ R^T, with the model allowing multiple streams by treating each stream as another seller.Sellers cannot change stream quality, are assumed not to have privacy concerns, and do not know the prediction tasks in which their data will be used.
- Participants: Each buyer seeks an affordable collection of datasets for a prediction task Yn, represented as a vector of T labels.The model abstracts away the train-test partition of Yn for notational simplicity.
- Buyer valuation: A prediction gain function maps the task Yn and estimate Ŷn to prediction quality, while μn specifies the buyer’s value for a marginal accuracy increase.The model uses examples such as 1 − RMSE for regression and Accuracy for classification, with a common gain function across buyers.
- Marketplace: Buyer bids bn may differ from private valuations μn, and the marketplace sets a scalar price pn for the features when each buyer arrives.The scalar-price restriction avoids the computational difficulties of maintaining separate prices for every data stream and supports zero-regret price updating through prediction-quality control.
- Dynamics: The dynamics model fixed sellers and buyers arriving one at a time, with buyers receiving predictions rather than direct access to underlying features.The architecture also leaves unmodeled the externalities arising when a dataset’s value depends on what other firms access.
- Marketplace: The marketplace’s allocation function uses pn and bn to determine the quality of features allocated, while its revenue function determines revenue rn from price, bid, and prediction task.Allocation can modify feature quality through operations such as adding noise or subsampling; the marketplace’s learning algorithm produces the buyer’s estimate from the available features.
3 DESIRABLE PROPERTIES OF MARKETPLACE
The marketplace is required to make truthful, revenue-effective, fairly divided, and computationally efficient decisions in real time. Because data are combinatorial and freely replicable, fairness must extend beyond standard Shapley allocation to control replication effects.
- A functioning marketplace must elicit truthful buyer bids, maximize revenue, divide revenue fairly among sellers, and run efficiently.These properties target large-scale, real-time matching of buyers with many sellers.
- Truthful: Truthfulness requires allocation and revenue functions to incentivize buyers to bid their true valuation for increased prediction accuracy.The buyer's prediction task is assumed fixed.
- Revenue Maximizing: Revenue maximization is defined by vanishing worst-case average regret relative to the optimal fixed price chosen in hindsight, without distributional assumptions on buyers.The price-update function must produce prices whose average difference from the unknown hindsight optimum approaches zero as the number of buyers grows.
- Shapley Fair: Shapley fairness allocates each feature its average marginal value across subsets and is characterized by standard symmetry, zero-element, and additivity conditions.The Shapley allocation is the unique allocation satisfying the stated fairness conditions.
- Computational Limitation: The Shapley computation requires Θ(2^M) time, making the direct algorithm infeasible at scale despite its use as a comparison standard.The exponential dependence comes from averaging marginal values over all feature subsets.
- Efficient: Efficiency requires polynomial-time processing for each marketplace step, with per-step complexity that does not grow with the number of buyers.The model assumes the learning algorithm and gain function run in O(M), while real-time operation makes the computational requirement non-trivial.
4 MARKETPLACE CONSTRUCTION
The marketplace construction defines buyer-facing allocation and revenue functions, then addresses pricing, truthful payments, Shapley-based seller compensation, and replication robustness. Its algorithms combine monotone data degradation, Myerson’s payment function, Multiplicative Weights, and permutation sampling to provide computationally tractable guarantees.
- Allocation and Revenue Functions: The allocation function maps the current price and buyer bid to the quality of features used for the buyer’s prediction task.Higher bids cannot reduce prediction quality at a fixed price; examples use noise or masking to degrade data when bids fall below prices.
- Price Update Function: A single posted price is not optimal when different datasets have different predictive power across buyer types.In the two-feature counterexample, the optimal prices are µ1 for X1 and µ2 for X2.
- Allocation and Revenue Functions: Myerson’s payment function produces truthful buyer payments when buyer valuation is represented by a scalar marginal value for prediction accuracy.The construction collects revenue based on the buyer’s experienced accuracy increase rather than the particular datasets allocated.
- Price Update Function: Multiplicative Weights updates scalar prices online by treating candidate prices in an ϵ-net as experts, achieving zero regret relative to the optimal fixed price in hindsight.The update uses normalized revenue gains for candidate prices and is designed to balance the revenue tradeoff from prices that are too high or too low.
- Payment-Division Functions: Uniformly sampling feature permutations yields an ϵ-approximation to the Shapley allocation with high probability in O(M^2) time.This approximation addresses the exact Shapley algorithm’s Θ(2^M) running time while retaining seller compensation based on marginal contribution.
- Payment-Division Functions: The third algorithm achieves ϵ-robustness to replication, extending fairness requirements for data’s freely replicable goods.The construction targets undesirable revenue divisions that standard Shapley fairness can permit when sellers replicate data.
5 MAIN RESULTS
The paper provides algorithms for allocation, pricing, revenue division, and fairness in a two-sided data marketplace, with theoretical guarantees for truthfulness, revenue maximization, Shapley fairness, and robustness to replication.
- Robust revenue division: Algorithm 3, SHAPLEY-ROBUST, exponentially down-weights features according to similarity to protect revenue division from replicated data.Its output combines approximate Shapley values with a replication penalty based on a similarity metric.
- Truthfulness: Truthfulness is guaranteed by RF* when Assumption 1 holds, using Myerson’s payment function.The construction relies on a scalar buyer valuation parameter and yields truthful bids under the stated monotonicity condition.
- Revenue maximization: Algorithm 1 achieves revenue maximization through a zero-regret guarantee under Assumptions 1, 3, and 4.Theorem 5.2 states that the regret bound is independent of M, the number of features sold.
- Shapley fairness: Algorithm 2 computes an ϵ-approximation to the unique Shapley-fair vector in O(M), compared with exact computation requiring Θ(2^M) time.The approximation holds with probability 1−δ when K exceeds the stated sampling threshold.
- Robustness to replication: Algorithm 3 is ϵ-robust to replication with probability 1−δ while preserving the other stated Shapley-fairness conditions to ϵ-precision.The result depends on Assumption 2 and the specified choices of K and λ.
- Trade-off: Robustness to replication and the balance condition of Shapley fairness cannot simultaneously hold when seller identities are anonymized.This impossibility is stated in Proposition 5.1.
- Efficiency: The core allocation, pricing, and payment functions run in O(M), while revenue-division algorithms can run offline in O(M^2).The real-time functions must be recomputed for each buyer, whereas sellers are assumed fixed for revenue division.
6 CONCLUSION
The paper develops a mathematical architecture and algorithms for real-time two-sided data markets, using modeling choices that make buyer utility and pricing tractable. It contributes a replication-aware fairness notion and a truthful, zero-regret mechanism for a class of combinatorial goods, while identifying several open extensions.
- Modeling contributions: The proposed mathematical model parametrizes buyers, sellers, the marketplace, and their interaction as a foundation for real-time data marketplaces.The paper defines challenges, constructs algorithms, and analyzes their performance theoretically.
- Modeling contributions: Buyer utility depends on estimate quality rather than the particular datasets allocated, and the marketplace centrally sets feature prices for each buyer.These choices are introduced to make the problem tractable.
- Technical contributions: The paper introduces fairness for cooperative games with freely replicable goods and a truthful, zero-regret auction mechanism using Myerson’s payment function and Multiplicative Weights.The framework can apply when buyer utility or cost is modeled through a scalar parameter.
- Future work: Future work includes buyer externalities from replication, adaptive allocation functions, and revenue division mechanisms that better preserve balance while remaining replication-robust.These questions define the stated scope of the current framework.
A TRUTHFULNESS
The paper characterizes when a payment rule is truthful by linking truthful allocation to monotonicity of prediction-accuracy gains with respect to bids. Myerson’s payment function supplies the truthful construction under the paper’s scalar valuation model.
- Proof strategy: The proof defines h(z) as prediction-accuracy gain as a function of the bid for fixed model, metric, data, and price.Truthful payments imply that increased allocation cannot decrease accuracy, yielding monotonicity of h.
B PRICE UPDATE - PROOF OF THEOREM 5.2
Under Assumptions 1, 3, and 4, Algorithm 1 is analyzed by first bounding regret over a finite price net and then extending the bound to all feasible prices. The resulting average regret bound establishes revenue maximization.
- Assumptions: Theorem B.1 assumes nonnegative revenue, a price-Lipschitz revenue function with constant L, and a bounded price set with maximum Bmax.These conditions support the gain and approximation bounds used in the proof.
- Conclusion: The total average regret is bounded by a quantity of order O(1/√N), up to a positive constant C.The expectation is over the randomness in Algorithm 1.
- Regret bound: Algorithm 1 is first compared against the best fixed price in the finite net Bnet(ϵ).The proof uses logarithmic inequalities and an inductive relationship for the algorithm’s weights.
- Regret bound: The finite-net comparison is extended to every price in B by selecting a net price within ϵ of the optimal price and applying Lipschitz continuity.The resulting inequality is then rescaled by Bmax.
C FAIRNESS
This section analyzes fairness allocations based on Shapley values, their approximation, and robustness to replicated data. It also proves that balance and replication robustness are incompatible when seller identities are anonymized.
- Shapley allocation: Algorithm 2 achieves its stated approximate allocation guarantee when its sampling hyperparameter K is chosen using M, δ, and ϵ.The supplied theorem statement gives a logarithmic dependence on the confidence parameter and an inverse-square dependence on precision.
- Shapley allocation: Algorithm 2 computes an approximate Shapley allocation by averaging marginal contributions over random seller orderings.The marginal contributions are bounded, enabling Hoeffding’s inequality and a union bound across sellers.
- Robustness to replication: Algorithm 3 achieves ϵ-robustness to replication with probability 1−δ while preserving Conditions 2–4 of the fairness property to ϵ-precision.The construction uses replication-aware allocation and specified hyperparameters K and λ.
- Impossibility under anonymity: If seller identities are anonymized, the balance condition and robustness to replication cannot hold simultaneously.Identical-feature counterexamples show that anonymity makes a seller’s copy indistinguishable from another seller’s data.
D EFFICIENCY
The efficiency analysis bounds the marketplace’s core functions and allocation procedures in terms of the number of features M. Most marketplace functions run linearly, while the auxiliary computation runs quadratically.
- Runtime bounds: The functions AF*, RF*, and PF* run in O(M) time, while PD* runs in O(M^2) time.The linear bounds follow from a constant number of calls involving the M features or prices; pairwise similarities can be precomputed for PD*.
- Allocation cost: Computing the Shapley allocation for each feature requires M log(2/δ)/(2ϵ^2) calls to G and M.This dependence reflects the requested precision ϵ and confidence δ.
E OPTIMAL BALANCE-PRESERVING, ROBUST-TO-REPLICATION PENALTY FUNCTIONS
The paper characterizes penalty functions that preserve balance while making allocations robust to replicated data. It proves a necessary and sufficient condition and identifies exponential down-weighting as a minimal robust choice under a continuous relaxation.
- Characterization: A penalty function is robust to replication if and only if it satisfies the stated relation for cumulative similarity x and c additional copies.Here c is a nonnegative integer and x is nonnegative real.
- Proof strategy: The proof studies how a seller’s Shapley allocation changes when one feature is duplicated, using the ordering of the original feature and its copies.This establishes the necessity direction of the robustness characterization.
- Characterization: The sufficiency argument requires that replication-adjusted penalties satisfy (c + 1)f(x + c) ≤ f(x).Under Assumption 2, the replicated feature’s Shapley value is no larger than its original value.
- Replication effect: For many unique sellers, copying one dataset a fixed number of times changes the Shapley allocation by approximately −c/M, with the approximation tightening as M grows.The inequality becomes an equality when all original sellers have identical data.
- Exponential penalty: Under the relaxation c∈R+, exponential weighting is described as minimal because it ensures robustness with the least allocation penalty.Gronwall’s inequality yields an exponential upper bound f(x) ≤ Ce^−Kx for suitable C,K ≥ 0.