On the Existence and Complexity of Core-Stable Data Exchanges

We thank the reviewer for the insightful comments. Here, we will address the questions and concerns respectively as follows.

Weakness: In general, I think that the paper shows a clever application of very classical and well studied notions in cooperative game theory and there is not much novelty in there from a theoretical perspective. I find the theoretical results per-se a bit weak: the only technically interesting one (at least to me) is the reduction to show PPAD-completeness. Moreover, it is well known that the concept of core stability is very hard to achieve in general: as much as they are still interesting, the hardness results are not surprising to me. The Scarf’s algorithm used in the last section of the paper is known as well and not novel. Thus, if I have to judge this paper as a theoretical one, I think it is below the threshold for acceptance.

Response: While we respect the reviewer’s opinion, we remark that there are several problems where core-like guarantees are computable in polynomial time or the problem lies in a smaller complexity class.

1. In the exchange markets with rivalrous goods, a core-stable solution can be computed through a competitive equilibrium in polynomial time (under specific agent preferences),
2. The top trading cycle algorithm (which runs in polynomial time) determines a core-stable solution in housing allocation,
3. Further, since data is a non-rivalrous asset (agents are therefore not competing for this asset), the hardness results that exist in traditional economies need not generalize. For instance, the work of [ACGM] looks at computing core-stable allocations in settings where utility functions are just the accuracy functions and do not involve costs. In such a setting, core-stable allocations are trivial. Further, as [ACGM] prove in their paper, finding allocations that are simultaneously core-stable and fair is in the complexity class CLS (and thus unlikely to be PPAD-hard).

Lastly, we would like to highlight that our hardness results continue to hold even when restricted to coalitions of constant size—a fact that we found somewhat surprising.

Question: Are there alternative concepts to core stability that are interesting to consider in this context?

Response: Core-stability is usually the gold standard desiderata in co-operative economies, as it implies other guarantees like individual rationality, Pareto-optimality, etc. One could also consider relaxations of core-stability where deviating coalitions (depending on their size) need to achieve substantially larger utility, e.g., if a group of $k$ agents need to deviate from the grand coalition, then the deviating exchange must guarantee each of them obtains a utility that is strictly larger than $f(k)$ times their utility in the grand coalition, where $f(\cdot)$ is a decreasing function with $f(n) = 1$. Note that $f(k) = 1$ for all $k$ in standard core-stability. Such guarantees have been investigated in the context of public decision making in social choice [Fain et al. '18] and Federated learning [Chaudhury et al'22]. One may hope to get better computational guarantees in this relaxed version.

[Chaudhury et al'22] Fairness in Federated Learning via Core-Stability. In NeurIPS'22.

[Fain et al. '18] Fair Allocation of Indivisible Public Goods. In EC'18

We thank the reviewer for the insightful comments. Here, we will address the questions and concerns respectively as follows.

Weakness 1: While I am not an expert in the area, my main concern is the overlap, both in conceptually contribution and originality to [ACGM, 2024 - On the Existence and Complexity of Core-Stable Data Exchanges]. This work, cited in the paper but not thoroughly discussed, also consider data exchanges that satisfy core stability. While the utility model is slightly different -- no explicit mention of cost and the utility is considered generally -- I don't see the utility function formulation here as being any more attractive. The conditions they require for core stability is that the utility be monotone: this is extremely natural and more general than here. They also give a local search algorithm that returns an epsilon-core stable allocation. Their work simultaneously also satisfies a fairness desideratum.

Response: We appreciate the reviewer’s comparison with [ACGM]. However, we emphasize that there are major important distinctions between our setting and that in [ACGM]. In particular, as the reviewer points out, [ACGM] does not account for costs, making its utilities monotone in the data exchange. It becomes trivial to obtain a core-stable data exchange in their setting – everyone exchanges all the data. This way, no agent can achieve a higher utility in any exchange. Therefore, ACGM investigates core stability in conjunction with another desideratum, i.e., fairness, and proves their existence results.

In contrast, our work departs significantly from this assumption, by explicitly incorporating costs incurred by agents for the data sharing– a feature intrinsic to real-world data sharing (see next response, and also our answer to question 2 of reviewer 5sUM). In our model, an agent’s utility is defined as payoff minus cost, both of which are monotonic in data exchange, but in opposite directions. As a result, the overall utility is non-monotonic, which introduces significant complexity. In particular, [ACGM]’s results do not carry over, as we demonstrate in Example 1, a core-stable exchange may not even exist under the generality of ACGM’s model when such costs are taken into account. This motivates our investigation into sufficient conditions—such as concave payoffs and convex costs—that still capture important and realistic scenarios while allowing for meaningful analysis. Conceptually, our utility model aligns more closely with practical distributed learning frameworks such as federated learning, where agents must consider both the benefits and costs of participation. We appreciate the reviewer’s suggestion and will include a more detailed comparison with ACGM in the next revision of our paper to make these distinctions clearer.

Weakness 2: In light of this aforementioned work, I struggle to understand the contribution of this work. While I am convinced there's mathematical novelty here, at a conceptual level, what makes the results here more relevant/applicable to data exchanges than the prior work? What more is being said here that is of practical significance to data exchanges. At the very least, a fairly meaningful discussion about the relation to this prior work is necessary in my opinion given the significant overlap - there is very little of it in the work. The only mention is that the earlier work does not consider cost (at the very end of the paper) which I am not sure is as important in data exchanges.

Response: We believe that modelling costs incurred during data sharing is very fundamental and has already been extensively used in collaborative machine learning paradigms like federated learning [Murhekar et al. '23], [Murhekar et al. '25], [Karimireddy et al. '22]. All the foregoing work cite costs associated with acquisition (e.g., retailers offering reduced prices/ discounts/ vouchers to customers in exchange for their data, buying data from third party data collectors), storage, cleaning, and privacy (anonymizing data for privacy considerations and setting up physical and legal infrastructure for sharing it) in a data sharing. [Castro Fernandez. '23] argues that a proper cost-utility tradeoff analysis is required for any kind of data sharing.

"Without a clear cost-benefit analysis, participants default in not sharing. As a consequence, many opportunities to create valuable data-sharing consortia never materialize, and the value of data remains locked."-- [Castro Fernandez. '23]

Data exchange is an interesting economy under the umbrella of data sharing, where agents share data for mutual benefit (please also see our answer to reviewer 5sUM, question 2, where we elaborateon the origin and the form of some of the cost functions in data economies).

Incorporating costs makes the utility functions (payoff minus costs) non-monotone and significantly more complex to deal with. Despite this, we identify some natural sufficient conditions under which core-stable guarantees are achievable and also outline an algorithm that works well in practice.

[Murhekar et al. '23]: Incentives in Federated Learning: Equilibria, Dynamics, and Mechanisms for Welfare Maximization, NeurIPS 2023

[Murhekar et al. '25]: You Get What You Give: Reciprocally Fair Federated Learning, ICML 2025

[Karimireddy et al. '22]: Mechanisms that Incentivize Data Sharing in Federated Learning, In Workshop on Federated Learning NeurIPS 2022.

[Castro Fernandez. '23] Data-Sharing Markets: Model, Protocol, and Algorithms to Incentivize the Formation of Data-Sharing Consortia, In SIGMOD'23

We thank the reviewer for the insightful comments. Here, we will address the questions and concerns respectively as follows.

Weaknesses: The empirical evaluation is limited, as the Pivoting Algorithm is tested on only one dataset and is not compared against any other approximation scheme.

Response: We thank you for the suggestion on the evaluation. We have managed to add one more dataset from the latest official San Francisco road map [DataSF], which is continuously updated on a daily basis. This dataset includes 35,000 street intersections along with the corresponding source and destination roads for each intersection. We construct the graph by treating intersections as edges and the roads as vertices, and adopt the same parameter setting in our paper. Given that the graph is smaller and sparser than the road map of New York used in our paper, we have tested our method for 10 to 80 agents. We report the average statistics for the performance pivoting algorithm as follows:

Time and size for the coalition matrix

Time and iterations of the pivoting algorithm

[DataSF] List-of-Streets-and-Intersections, Geographic-Locations-and-Boundaries, San Francisco Open Data.

Question 1: Is the core-stable solution unique in general?

Response: In general, there can be multiple core-stable exchanges. Consider two agents, and let $x_{12}$ denote the data transferred from agent 1 to 2 and $x_{21}$ denote the data transferred from agent 2 to 1. Agent 1’s accuracy is given by $x_{21}$ and cost is given by $x_{12}$ (therefore net utility is $x_{21}-x_{12}$). Symmetrically, agent 2’s accuracy is given by $x_{12}$ and cost is given by $x_{21}$ (therefore net utility is $x_{12} - x_{21}$). One can easily observe that any exchange that sets $x_{12} = x_{21}$ is core-stable and there are several of them.

Question 2: Which particular solution is approximated by the Pivoting Algorithm?

Response: In continuation of the answer to question 1, there can be multiple core-stable data exchanges, and since we do not impose any additional selection criteria, our algorithm can return any stable data exchange. Studying how to steer the algorithm toward desirable core-stable solutions—possibly via objective-guided pivots—is an interesting direction for future work. We also urge the reviewer to check our response to reviewer 5sUM, question 1, where we motivate payment mechanisms that can help us find core-stable data exchanges with additional desiderata.

Question 3: With respect to fairness—as mentioned at the end of the article—is there any chance that the Shapley value of your cooperative game lies in the core? If so, could it be approximated?

Response: Shapley value is in the core for games with Transferable Utilities (TU). In TU games, a single value $v(S)$ is assigned to each coalition $S$ of agents. The goal is to design a credit sharing rule, such that the grand coalition is core-stable, i.e., under this credit sharing rule, no coalition of agents can deviate and all get strictly better credit. In such a setting, Shapley value is in the core, i.e., choosing the credit sharing rule as the Shapley share ensures that the grand coalition is core-stable. Our setting is a Non-Transferable Utility (NTU) game, where one cannot freely transfer utility between players. In these settings, for each coalition, there are feasible data-exchanges that determine agent utilities.

However, one could design a budget-balanced payment mechanism that can make our game behave closely to a TU game, albeit some drawbacks. Please see our answer to reviewer 5sUM, question 2 for a more detailed explanation.

We thank the reviewer for the insightful comments. Here, we will address the questions and concerns respectively as follows.

Question 1: Is it possible to involve monetary transfer in the setting? Either between agents or involving economic issue related to the platform of data exchange (for example charging a small fraction of payoffs for each exchange).

Response: This is indeed an excellent question. While it is certainly possible to design payment rules tailored to specific applications, we believe that several important challenges must be carefully considered in the design of such rules.

• Budget Constraints: In practice, agents often have limited budgets and may not be able to make or receive large payments as the mechanism dictates. This can violate the feasibility of the mechanism, even if it is theoretically sound.
• Mechanism Consistency Across Coalitions: Core-stability guarantees with payments generally rely on the assumption that deviating coalitions continue to use the same payment rule. In decentralized and heterogeneous environments, there is no natural reason to expect this consistency, which may limit the robustness of such mechanisms.

That said, we still believe that several interesting theoretical questions can be explored building upon our current framework—particularly in the context of computing core-stable data exchanges while simultaneously satisfying additional desiderata. We elaborate our points.

We can introduce a payment rule for every exchange in a coalition. Let $\mathrm{pay}\_i(x,S)$ denote the payment that $i$ receives from the exchange $x$ in coalition $S$. Ideally, we would ensure that $\sum_{i \in S} \mathrm{pay}\_i(x,S) = 0$, implying that the mechanism is budget-balanced. The utility of each agent after payment is $a_i(x_{-i}, S) - c_i(x_i, S) + \mathrm{pay}_i(x,S)$. Two natural questions that follow are,

1. Can we design a payment rule such that a core-stable data exchange can be computed in polynomial time?
2. Can we design payments that align with additional desiderata? For instance payment mechanisms can be designed in order to award agents contributing “valuable data” (data that increases the total utilitarian welfare), e.g., $\mathrm{pay}\_i(x,S) = \psi_i(x, S) - (a_i(x_{-i}, S) - c_i(x_i)),$ where $\psi_i(x,S)$ denotes the contribution of agent $i$’s data to the total utilitarian welfare. This way each agent’s final utility in any contribution will be equal to $\psi_i(x,S)$. Under such payment mechanisms, does a core-stable data exchange exist? If it does, what is its computational complexity?

If required, we can add this discussion to the next version of our paper.

Question 2: Please explain more to justify the assumption of the convex cost functions.

Response: A detailed view on the privacy cost and data acquisition can be found in Li and Raghunathan [Li and Raghunathan'14]: They adopt the financial compensation model from Laudon [Laudon'96]. Typically, data collectors (e.g. grocery store) collect (private) data from agents (eg. buyers) in return for financial compensation (e.g., a membership cards/ gift cards/ coupons of a grocery store). This compensation is often referred to as sunk cost. [Li and Raghunathan '14] (Section 3.1) describe two common methods through which the data collectors release the foregoing data to data buyers:

• Random Selection (Results in Linear (trivially convex) cost functions): Here, the data buyer requests for data records of a particular type (specified by attributes/ sensitivity level etc.)-- essentially all the data records are homogeneous. Given a request of $k$ records, the data collector, randomly chooses $k$ data records of a particular type. This results in a cost function which is linear in the total number of records requested.
• Ordered Selection (Results in Convex cost functions) : In contrast, if the data buyer does not impose constraints on record types—seeking broad or general-purpose information—the data collector may choose to release records in order of increasing individual cost or sensitivity. Early records are cheaper or less sensitive, while later records may carry greater privacy risks or legal implications. This ordering naturally leads to convex cost functions, reflecting increasing marginal cost as more data is released.

Further, several prior works on incentive design and fairness in distributed learning systems, particularly in federated learning [Murhekar et al.'23], [Murhekar et al.'25], [Karimireddy et al.'22] adopt convex cost functions for modeling the agents’ costs.

We also completely agree with the reviewer that an alternative way of sharing records is just sharing them in the order they are collected: However, the initial data points are easier or cheaper to collect (e.g., publicly available or high-frequency), whereas accessing additional, rarer, or more private data often incurs increasing marginal costs—due to privacy concerns, regulatory hurdles, and operational constraints, thereby again leading to convex cost functions.

[Li and Raghunathan '14]:Pricing and disseminating customer data with privacy awareness. Decision support systems, 2014.

[Laudon '96]: Markets and privacy. Communications of the ACM, 1996.

[Murhekar et al. '23]: Incentives in Federated Learning: Equilibria, Dynamics, and Mechanisms for Welfare Maximization, NeurIPS 2023

[Murhekar et al. '25]: You Get What You Give: Reciprocally Fair Federated Learning, ICML 2025

[Karimireddy et al. '22]: Mechanisms that Incentivize Data Sharing in Federated Learning, In Workshop on Federated Learning NeurIPS 2022.