On the Theoretical Foundations of Data Exchange Economies

arXiv:2412.01968 · cs.GT · Submitted 2024-12-02 · Read on arXiv

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

Where the paper says it

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.

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. p. 0
Where the paper says it

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.

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

Where the paper says it

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.

Fairness requires agent utility to be at least the sum of their contributions to others' utilities, formalized as ui(xi) ≥ Pj ψij (xj) for all i. Core-stability means no subset S can identify an exchange y among themselves that gives all agents in S strictly higher utility than in the current exchange x. p. 2
Where the paper says it

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.

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

Where the paper says it

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.

To handle the non-convexity of the sets of fair and core-stable exchanges, the authors define an approximate set Xε as exchanges where G(x, α(ε)) is almost acyclic. p. 5
Where the paper says it

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

This set Xε is shown to be homeomorphic to a convex compact set Z. p. 6
Where the paper says it

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!

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

Where the paper says it

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.

This algorithm runs in time poly(n, 1/ε, L) under specific conditions. p. 4
Where the paper says it

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].

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

Where the paper says it

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.

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

Where the paper says it

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.

r.t original utilities. p. 7
Where the paper says it

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.

The final result establishes that determining an ε-reciprocal and ε-core stable exchange is in CLS when L/ε = poly(n). p. 7
Where the paper says it

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.

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

Where the paper says it

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].

The work also relates to federated learning by considering heterogeneous learning objectives. p. 1
Where the paper says it

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.

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

Where the paper says it

Our framework opens up several intriguing theoretical avenues for future research on data economics. ∗Work supported by NSF Grants CCF-1942321 and CCF-2334461.

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

Where the paper says it

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].

The paper also references specific data economics literature such as BGI+24, and results on federated learning like MMR+17. p. 1
Where the paper says it

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.

The list includes works on data markets [ADS19] and utility balancing [BGI+24]. p. 1
Where the paper says it

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.

The references cover a broad range of relevant theoretical areas for data exchange economies. p. 0
Where the paper says it

01968v1 [cs. GT] 2 Dec 2024 On the Theoretical Foundations of Data Exchange Economies∗ Hannaneh Akrami† hakrami@mpi-inf.

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

Where the paper says it

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.

The entire theoretical exploration opens up several intriguing avenues for future research on data economics. p. 0
Where the paper says it

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.

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

  1. 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.

  2. 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 providing good quality data are reciprocated by valuable data in return, which is crucial for maintaining trust in collaborative systems.

  3. 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.

  4. 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.

  5. 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.

  6. 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

Related papers