On the Theoretical Foundations of Data Exchange Economies
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: I'm Tom.
Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.
Tom: We're looking at the paper: "On the Theoretical Foundations of Data Exchange Economies".
Jane: Here's the gist of the paper. The paper investigates theoretical foundations for data exchange economies by proposing a framework where agents voluntarily exchange data for mutual benefit without monetary compensation.
Tom: This framework is particularly relevant in settings involving non-profit organizations that seek to improve their ML models through data exchange with other organizations, yet are restricted from selling their data for profit.
Jane: Model and Core Desiderata The model describes a data exchange economy where agents possess datasets and voluntarily exchange parts of them, represented by an exchange matrix x.
Tom: The framework is built around two key properties: fairness, ensuring utility is proportional to contribution via credit-sharing functions like the Shapley value, and stability, guaranteeing no coalition can unanimously prefer a deviation over the current exchange.
Paper summary: Tom: The paper explains the thesis of "On the Theoretical Foundations of Data Exchange Economies" by proposing a framework where agents voluntarily exchange data for mutual benefit without monetary compensation. What exactly do they claim is this framework is relevant for?
Jane: They say this framework is particularly relevant in settings involving non-profit organizations that seek to improve their machine learning models through shared data, yet are restricted from selling that data for profit.
Lu: The authors introduce a model where agents possess datasets and voluntarily exchange parts of them, represented by an exchange matrix x. This framework is built around two key properties: fairness, ensuring utility is proportional to contribution via credit-sharing functions like the Shapley value, and stability.
Meng: Fairness requires agent utility to be at least the sum of their contributions to other agents utilities, formalized as ui(xi) greater than or equal to Pj psiij (xj) for all i where psiij (xj) measures agent i’s contribution to uj (xj).
Lalam: And stability means no subset can identify an exchange amongst themselves which they all strictly prefer over the current exchange. This is called core-stability.
Jane: So, what does this mathematical structure actually achieve? They show that for any monotone continuous utility functions and certain credit-sharing functions, there exist fair and core-stable exchanges for all of them.
Tom: The proof uses Brouwer’s fixed point theorem on a function f to show existence. But they also have to deal with some non-convexity issues by defining an approximate set X epsilon as exchanges where G(x, alpha epsilon) is almost acyclic.
Lu: They show that this approximate set X epsilon is homeomorphic to a convex compact set Z, which helps them prove the existence of these exchanges.
Meng: When we look at the computational side, they analyze the complexity for monotone L-Lipschitz utility functions and cross-monotone share functions. The problem of finding an epsilon core stable and epsilon fair exchange is in CLS when L over epsilon is polynomial in n.
Lalam: There’s also a local search algorithm they present that maintains the invariant that G(x, epsilon over n L) is acyclic and lexicographically reduces the surplus profile P(x) less than P of x minus L over two n squared.
Conclusion: Tom: So we've been looking at how this paper builds a formal structure for when organizations voluntarily swap data without any money changing hands to keep things fair and stable. What’s the big picture implication here for people outside of pure mathematics?
Jane: Right, so you’re asking what this means practically for people who aren't deep into the math? What’s the big picture implication here?
Tom: It basically shows that you can build a system where agents trade information for mutual benefit without any market price involved at all. Think of it like a really well-behaved sharing agreement between companies.
Lu: The authors are proving that even with this data exchange, we can maintain fairness through things like credit sharing functions, which is how utility gets distributed proportionally to who contributes what.
Meng: From my side, the interesting part for production is that if you design your internal data sharing around these fairness rules instead of just price signals, you have a theoretical structure to build those systems on. It's about the mechanism.
Lalam: I'm looking at this because it connects to how we think about data markets and federated learning—it contrasts our model with the old Arrow-Debreu markets by showing how data can be replicated without cost.
Jane: So, if we get this right, does it change how we think about why some organizations are willing to share sensitive information?
Tom: It suggests that the willingness isn't purely driven by a market price for that data; it can be driven by the structure of the exchange itself being fair and stable.
Lu: The core result they land on is that determining an exchange that is both reciprocal and exactly core-stable is in the class CLS, which is PPAD intersected with PLS. That’s a statement about how hard it is to find this perfect sharing agreement computationally.
Meng: And the complexity bound they give you, when the scaling factor L over epsilon is polynomial in n, means that finding this stable exchange isn't impossible to do in practice under those conditions. It’s manageable if your utility functions behave well.
Jane: So, it boils down to this idea: we can mathematically prove that a fair and stable data sharing economy exists, and it tells us how difficult it is for an AI system to actually find that perfect agreement when the data gets big.
Max Planck Institute for Informatics and Graduiertenschule Informatik · University of Illinois at Urbana-Champaign
cs.GT
Submitted: 2024-12-02
Updated: 2026-11-10
Comments: 40 pages. Appeared at EC 2025
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 87/100
The gist: The paper investigates theoretical foundations for data exchange economies by proposing a framework where agents voluntarily exchange data for mutual benefit without monetary compensation.
Key concepts
- Fairness
- This ensures that an agent's personal utility is at least as good as what they contribute to others' utilities. It formalizes the idea that agents should receive credit proportional to how much their data contributes to the overall exchange benefit, often modeled using Shapley values.
- Core-Stability
- This property guarantees that no group of agents can collectively find an alternative data exchange arrangement among themselves that would make every member of that group strictly better off than they are in the current arrangement. It prevents unilateral deviations from the agreed-upon exchange.
- CLS (PPAD ∩ PLS)
- This is a complexity class used to categorize computational problems. The paper shows that finding an approximate, $\epsilon$-core stable exchange can be solved within this class when the utility function's Lipschitz constant is related to $\epsilon$ and $n$ polynomially.
- Credit-Sharing Functions
- These are mathematical functions used to distribute the benefits of a data exchange among participating agents. They must satisfy specific properties like monotonicity and normalization, ensuring that the distribution of value is consistent and meaningful within the economic model.
Terminology
Summary
The paper investigates theoretical foundations for data exchange economies by proposing a framework where agents voluntarily exchange data for mutual benefit without monetary compensation. p. 0 In this setup, agents possessing datasets exchange data fairly and voluntarily, aiming
for mutual benefit without monetary compensation. This framework is particularly relevant in
settings involving non-profit organizations that seek to improve their ML models through data
exchange with other organizations, yet are restricted from selling their data for profit. In this setup, agents possessing datasets exchange data fairly and voluntarily, aiming
for mutual benefit without monetary compensation. This framework is particularly relevant in
settings involving non-profit organizations that seek to improve their ML models through data
exchange with other organizations, yet are restricted from selling their data for profit.Where the paper says it
Where the paper says it
Model and Core Desiderata
The model describes a data exchange economy where agents possess datasets and voluntarily exchange parts of them, represented by an exchange matrix x. The framework is built around two key properties: fairness, ensuring utility is proportional to contribution via credit-sharing functions like the Shapley value, and stability, guaranteeing no coalition can unanimously prefer a deviation over the current exchange. p. 0 This framework is particularly relevant in
settings involving non-profit organizations that seek to improve their ML models through data
exchange with other organizations, yet are restricted from selling their data for profit. We propose a general framework for data exchange from first principles, focusing on two
key properties: (i) fairness, ensuring that each agent receives utility proportional to their contribution to other agent utilities – agent contributions are quantifiable using well-established
credit-sharing functions, such as the Shapley value, and (ii) stability, guaranteeing that no coalition of agents can identify an exchange among themselves which they all unanimously prefer to
the current exchange. We highlight a subtle
but important feature of our core-stability desiderata: note that we do not impose any fairness
requirement on the deviating coalition, while we impose the same on our solution, i. , for a
coalition to deviate from the exchange x, it suffices for them to identify an exchange y (in
particular, the exchange where all agents in the coalition share everything within themselves)
which gives all agents in the coalition strictly higher utility than their utility in the exchange
x.Where the paper says it
Where the paper says it
Existence and Fixed Point Formulation
Theorem 1 shows the existence of fair and core-stable exchanges for all monotone continuous utility functions and any credit-sharing functions satisfying monotonicity, normalization, and efficiency. The proof uses Brouwer’s fixed point theorem on a function f to show existence. p. 4 In this paper, we also initiate the study on the computational complexity of ε-core-stable and εfair exchanges (obtained by adding an additive error of ε to reciprocity and core-stability). Our
existence proof (Section 3) invokes Brouwer’s fixed point theorem on a function f to show the
existence of a core stable and fair exchange. Y
−→e ∈C
(1 − xe) = 0 ∀C ∈ Kn
xij ∈ [0, 1]
Unfortunately, X still does not satisfy the desirable properties (like convexity) for our fixed
point formulation. Therefore, we now look into a relaxation of X: given a sufficiently small ε > 0,
we define a carefully chosen parameter α(ε) > 0, and the set of approximate core-stable exchanges
Xε as
Y
−→e ∈C
(1 − xe) ≤ α(ε)
n
∀C ∈ Kn
xij ∈ [0, 1 − 1/M]
5 Our choice of α(ε) ensures
that x ∈ Xε is ε-core stable. While set Xε is still non-convex, it still has desirable properties –
in particular, there exists a homeomorphism from Xε to a convex compact set!Where the paper says it
Where the paper says it
Where the paper says it
Computational Complexity and Local Search
The computational complexity analysis shows that for monotone L-Lipschitz utility functions and cross-monotone share functions, the problem of finding an ε-core stable and ε-fair exchange is in CLS (= PPAD ∩ PLS) when L/ε = poly(n). A local search algorithm is presented that maintains the invariant that G(x, ε/(nL)) is acyclic and lexicographically reduces the surplus profile P(x) < P(x) − L/(2n 2). p. 8 We briefly
outline our key ideas behind the local search procedure. At a high level, our algorithm maintains the invariant that G(x, ε/(nL)) is acyclic and reduces
the surplus of the agents with high surpluses. For instances satisfying the foregoing
conditions, we give a local search algorithm (defined formally in Section 4), that determines a εcore stable and ε-fair exchange. When the utility functions are L-Lipschitz, and L/ε = poly(n),
then our local search algorithm shows that the problem is in PPAD ∩ PLS = CLS [FGHS23].Where the paper says it
Where the paper says it
Membership in PLS and PPAD
The problem is shown to be in PLS by demonstrating a neighborhood structure where every exchange has a neighbor with strictly lower cost P(x') < P(x). Furthermore, the problem is shown to be in PPAD by embedding the domain Z into a larger polytope Z' and defining an almost fixed point problem for a continuous function g˜: Z' → Z'. This relies on showing that the required functions are polynomially computable under certain assumptions.
Exact Exchange Existence
Theorem 4 proves the existence of reciprocal and exactly core-stable exchanges by using sequential compactness arguments on the sets of reciprocal and ε-core-stable exchanges. This leads to a convergent subsequence that converges to an exchange x∗ which is both reciprocal and exactly core-stable. p. 3 However, as our first main result, we show the existence of fair and core-stable exchange
much more generally. A reciprocal and core-stable exchange exists for all monotone continuous utility functions and any credit-sharing functions satisfying monotonicity, normalization, and efficiency.Where the paper says it
Perturbation and Complexity Bounds
The authors introduce a perturbation of utilities and share functions to incorporate mild non-satiation, leading to Lemma 9 which shows that an approximate exchange w.r.t. perturbed utilities is a 3ε-core stable exchange w. p. 2 However, determining an exchange satisfying both the desiderata is
non-trivial. To build some intuition on the non-triviality of the problem, we highlight a problem that arises
when we approach the problem using a natural, iterative algorithm: (1) Maintain a fair exchange
x, (2) if x is not core-stable, identify a deviating coalition S and a deviating exchange y, (3) use S
and y to compute another fair exchange x
′
, where we strictly improve the utilities of the agents in
S, without reducing the utilities of the agents in N \S, and (4) update x ← x
′
, and repeat until we
get a fair, core-stable exchange. Further, it can be argued that this projection is unique, rational, and polynomial time
computable. Polynomial time computability crucially exploits the facts that (i) while our original
domain Z
′ may have exponentially many constraints, it still admits a poly-time separation oracle,
and (ii) the projection from z /∈ Z onto Z is rational and has polynomial bit length. Polynomial time computability crucially exploits the facts that (i) while our original
domain Z
′ may have exponentially many constraints, it still admits a poly-time separation oracle,
and (ii) the projection from z /∈ Z onto Z is rational and has polynomial bit length. This puts the
problem of determining a ε-core-stable and ε-reciprocal exchange in PPAD.Where the paper says it
Where the paper says it
Where the paper says it
Related Work
The paper relates its work to data markets, classic exchange markets, and federated learning paradigms. It contrasts the data exchange economy with classical Arrow-Debreu markets due to the replicable nature of data. p. 4 The above theorem contrasts computational results on finding solutions in classic exchange economies
with utility functions that mildly generalize linear utilities. It is well known that computing a
constant-factor approximation of an equilibrium in Arrow-Debreu markets with additively separable
piecewise linear concave (SPLC) utilities is already PPAD-hard, where L/ε is constant [CDDT09,
Rub18]. We assume that the utility functions are
monotone and continuous. The data exchange is operated through a central trusted server, similar to data market economies
[ADS19] and decentralized machine learning paradigms like federated learning [MMR+17], with
which all agents share their datasets and prediction tasks.Where the paper says it
Where the paper says it
Acknowledgments
The authors thank Stepan (Styopa) Zharkov for the proof of Theorem 4, suggesting the use of sequential compactness arguments together with Theorem 3. The paper is supported by NSF Grants CCF-1942321 and CCF-2334461. p. 0 Our framework opens up several intriguing theoretical avenues for future research
on data economics. ∗Work supported by NSF Grants CCF-1942321 and CCF-2334461.Where the paper says it
References
The paper cites numerous foundational works in economics, computer science complexity, and machine learning. Key references include Arrow and Debreu [AD54] for classic exchange economies, Scarf [Sca67] for core stability in matching, and results on complexity like CLS = PPAD ∩ PLS [FGHS23]. p. 4 The above theorem contrasts computational results on finding solutions in classic exchange economies
with utility functions that mildly generalize linear utilities. It is well known that computing a
constant-factor approximation of an equilibrium in Arrow-Debreu markets with additively separable
piecewise linear concave (SPLC) utilities is already PPAD-hard, where L/ε is constant [CDDT09,
Rub18]. We assume that the utility functions are
monotone and continuous. The data exchange is operated through a central trusted server, similar to data market economies
[ADS19] and decentralized machine learning paradigms like federated learning [MMR+17], with
which all agents share their datasets and prediction tasks. We assume that the utility functions are
monotone and continuous. The data exchange is operated through a central trusted server, similar to data market economies
[ADS19] and decentralized machine learning paradigms like federated learning [MMR+17], with
which all agents share their datasets and prediction tasks. 01968v1 [cs. GT] 2 Dec 2024
On the Theoretical Foundations of Data Exchange Economies∗
Hannaneh Akrami†
hakrami@mpi-inf.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Final Conclusion
Theorem 8 concludes that determining a ε-reciprocal and ε-core stable exchange is in CLS when L/ε = poly(n). This result demonstrates that the problem lies in PPAD ∩ PLS = CLS. p. 0 We present a local search algorithm for instances with
monotone submodular utility functions, where each agent’s data contribution is measured using
the Shapley value. We prove that this problem belongs to CLS (= PPAD ∩ PLS) under mild
assumptions. We prove that this problem belongs to CLS (= PPAD ∩ PLS) under mild
assumptions. Our framework opens up several intriguing theoretical avenues for future research
on data economics.Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Data exchange economy modeling allows non-profit organizations to improve machine learning models through data exchange without needing to sell their data for profit, as it focuses on fairness and stability rather than competitive prices. This enables collaborations in settings like hospitals or universities that are restricted from selling their assets for monetary gain.
-
The framework guarantees the existence of an exchange where
each agent receives utility proportional to their contribution to other agent utilities,
using credit-sharing functions like the Shapley value, ensuring reciprocity. This ensures that agents providinggood quality data
are reciprocated by valuable data in return, which is crucial for maintaining trust in collaborative systems. -
The algorithm provides a local search procedure that determines an epsilon core stable and epsilon fair exchange when utility functions are L-Lipschitz continuous and share functions are cross-monotone. This allows the system to find near-optimal data sharing arrangements efficiently under common ML assumptions, specifically showing membership in CLS = PPAD intersect PLS.
-
The computational complexity analysis shows that for instances with L/epsilon equal to a polynomial in n, the problem of finding an epsilon core stable and epsilon fair exchange is in CLS. This means the system can find these desirable exchanges using efficient algorithms when utility gains exhibit diminishing marginal returns with data.
-
The local search algorithm, Algorithm 4, iteratively improves a potential function P(x) by at least L over n squared in each step, leading to a final allocation x' such that P(x') < P(x) - L/2n squared in polynomial time poly(n, 1/epsilon, L). This provides a specific quantitative guarantee on the improvement of the data exchange quality.
-
The system can determine an epsilon reciprocal and epsilon core stable exchange in polynomial time when L/epsilon is a polynomial in n, establishing that this problem is in PLS and PPAD (CLS). This means the AI agent can reliably find these exchanges efficiently under specific conditions on utility functions and share functions.
Abstract
Organizations increasingly seek to share and access datasets to improve their ML models and derive insights. Despite the immense demand for quality data, data exchange and collaboration have not reached their full potential, as cited by the European Commission. One of the key reasons is the lack of reciprocity, where some participants perceive their contribution to others to be of higher value than what they receive in return. We propose a general framework for data exchange without payments, focusing on two main properties: (i) reciprocal fairness, which ensures that each agent receives utility proportional to their contribution to the total welfare -- contributions are quantifiable using well-established credit-sharing functions such as the Shapley share and proportional share, and (ii) core-stability, which guarantees that no coalition of agents can identify an exchange among themselves which they all unanimously prefer to the current exchange. Surprisingly, we show that fair and stable exchanges exist for all monotone continuous utility functions. Building on this, we investigate the computational complexity of finding approximate fair and stable exchanges. We present a local search algorithm for instances with monotone submodular utility functions and cross-monotone credit-sharing functions, e.g., Shapley share. We prove that this problem belongs to CLS (= PPAD PLS) under mild assumptions. Our framework opens up several intriguing theoretical avenues for future research on data economics.
Sources
- Towards Data Auctions with Externalities
- Optimal Mechanisms for Selling Information
- How to Sell Information Optimally: an Algorithmic Study
- Federated Learning in Vehicular Networks
- Auction Algorithms for Market Equilibrium with Weak Gross Substitute Demands
- Equilibrium Pricing of Semantically Substitutable Digital Goods
- Mechanisms that Incentivize Data Sharing in Federated Learning
Related papers
- How Many Votes is a Lie Worth? Measuring Strategyproofness through Resource Augmentation
- Effective Horizons for Prophet Inequalities with Discounted I.I.D. Rewards
- Truthful-in-Expectation Mechanism with Constant Maximin-Share Guarantee
- The Power of Recruiting the Smaller Side: Two Additional Traders Suffice in Two-Sided Markets
- From signaling to interviews in random matching markets
- Optimizing Social Utility in Sequential Experiments