On the Existence and Complexity of Core-Stable Data Exchanges
Authors: Jiaxin Song
Pooja Ravi Kulkarni
Parnian Shahkar
Bhaskar Ray Chaudhury
Venue: NeurIPS 2025 poster ()
Keywords: Data Economics
Core-Stability
Complexity
Scarf's Lemma
Primary area: theory

Abstract: The rapid growth of data-driven technologies and the emergence of various data-sharing paradigms have underscored the need for efficient and stable data exchange protocols. In any such exchange, agents must carefully balance the benefit of acquiring valuable data against the cost of sharing their own. Ensuring stability in these exchanges is essential to prevent agents—or groups of agents—from departing and conducting local (and potentially more favorable) exchanges among themselves. 
To address this, we study a model where $n$ agents participate in a data exchange. Each agent has an associated payoff for the data acquired from other agents and a cost incurred during sharing its own data. The net utility of an agent is payoff minus the cost. We adapt the classical notion of *core-stability* from cooperative game theory to data exchange. 
A data exchange is core-stable if no subset of agents has any incentive to deviate to a different exchange. 
We show that a core-stable data exchange is guaranteed to exist when agents have concave payoff functions and convex cost functions-- a setting typical in domains like PAC learning and random discovery models. We show that relaxing either of the foregoing conditions may result in the nonexistence of core-stable data exchanges. Then, we prove that finding a core-stable exchange is *PPAD-hard*, even when the potential blocking coalitions are restricted to constant size. To the best of our knowledge, this provides the first known PPAD-hardness result for core-like guarantees in data economics. Finally, we show that data exchange can be modelled as a *balanced* $n$-person game. This immediately gives a pivoting algorithm via Scarf's theorem [Scarf1967core]. We show that the pivoting algorithm works well in practice through our empirical results.

On the Existence and Complexity of Core-Stable Data Exchanges
Jiaxin Song
Pooja Ravi Kulkarni
University of Illinois, eebana-Champaige j jiaxins80i11inois. edu
Northwestern University
pooja.kulkard kulkarni wwwtthwettrrrn.nnmmmmmo.o edu
Parnian Shahkar
Bhaskar Ray Chaudhury
University of California, Irvine shahkarp@uci.edd
University of Illinois, trbaan-Champaign
braycha@illinois.
Abstract
The rapid growth of data-driven technologies and the emergence of various data- sharing paradigms have underscored the need for efficient and stable data exchange protocols. In any such exchange, agents must carefully balance the benefit acquiring valuable data against the cost of sharing their in these exchanges is essential to prevent agents-or groups of agents-from departing and conducting local (and potentially more favorable) exchanges among themselves. To address this, we study model where agents participate in a data exchange. Each agent has an associated payoff for the data acquired from other agents and cost incurred during sharing its own data. The net utility of an agent is payoff minus the cost. We adapt the classical notion of stab-itayyl from cooperative game theory to data exchange. A data exchange is core-stable if no subset of agents has any incentive to deviate to a different exchange. We show that core-stable data exchange is guaranteed to exist when agents have concave payoff functions and convex cost functions- a setting typical in domains like PAC learning and random discovery models. We show that relaxing either the foregoing conditions may result in the nonexistence of core-stable data exchanges. Then, we prove that finding a core-stable exchange is PPAD-hard, even when the potential blocking coalitions are restricted to constant size. This provides the first known PPAD-hardness result for core-like guarantees in data economics [BGI 24a ACGM25). Finally, we show that data exchange can be modeled as balanced n-person game. This immediately gives pivoting algorithm via Scarf's 's theorem [Sca67]. We show that the pivoting algorithm works well practice through our empirical results.
Ensuring stability
Introduction
From accelerating vaccine development in healthcare to improving fraud detection in financial services and advancing self-driving technology in the automotive industry, high-quality data has become the bedrock of algorithmic decision-making and Al-driven solutions in the 21st century. However, this valuable data is often fragmented i.e., distributed across multiple organizations. This decentralization makes data sharing and collaboration critical for effective decision- making. For instance, in healthcare, capturing nuanced relationships between disease patterns, socio-cconomic factors, genetic information, and rare conditions requires training machine learning models large, diverse datasets that extend beyond curated datasets within individual organizations IRHL+201 Similarly, in autonomous vehicle technology, self-driving cars must be exposed to wide range
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

of driving scenarios, including varying terrains, climates, and traffic regulations across countries, making essential to train models on diverse datasets from multiple regions [XPHS23]. Collaborative data economics offers both unique opportunities and challenges: Unlike most economic assets, data non-rivalrous- meaning multiple organizations can simultaneously benefit from the same data. This creates the potential for significantly greater collective value compared to traditional market economies, where assets are typically rivalrous. However, the benefits of data sharing are tempered by concerns over privacy, security, and the risk of losing a competitive advattage. As result, despite its vast potential, data collaboration has not yet reached its full scale. As the European Council aptly notes [Com20]:
"In spite of the economic potential, data sharing between companies has not taken off sufficient scale. This is due to a lack of economic incentives, including the fear of losing a competitive edge." "
We introduce a collaborative data exchange economy, where a group of agents, each having an endowment of data, aim to engage in mutually beneficial data exchanges. Each agent derives (i) a payoff from the data acquired (indicative of the agent"s value for the marginal improvement in predictive payoff of their ML model from the acquired data) and (ii) incurs a cost for sharing their own data. The agent's 's net utility from the data exchange is defined as the payoff minus the cost. In our model, shared data cannot be redistributed by other agents. Specifically, when we say that agent i shares its data with agent j. we mean that agent i allows agent) j to refine its machine learning model using samples of i's data. However, this does not entail direct data sharing between i and j. Instead, we adopt a framework similar to standard collaborative learning paradigms, such as Federated Learning [MMR + 17), where j trains on i's data by only receiving the gradients of the loss function on i's data, allowing agent to update its model without direct access to i's data.
Desiderata. The gold-standale desiderata in a collaborative economy is core-stability- a data exchange is core-stable if no group of agents can identify local exchange among themselves that they all strictly prefer to the current exchange. Core-stability implies other desired guarantees like (i) individual rationality: every agent participating in the data exchange gains more in utility than they lose in the cost of sharing their own data, and (ii) Pareto-optimality: there exists no exchange that all agents strictly prefer to the current exchange. This paper delves into the conditions under which core-stable exchanges exist within this collaborative data exchange economy and explores how to compute such exchanges.
1.1 Our Contributions
Data Exchange Model. In an instance of our problem, there are n agents N, where each agent i owns dataset D,. In a data exchange x (#i,) Fiy E [0, 1] represents the fraction of Dj shared with j. - represents the data bundle (I1,5, "2, Fn,) that receives from the data exchange, and x, represents the data bundle (4,, 24,2, Fsa) that i gives to the data exchange. Given a data exchange x, an agent's 's utility ux(x) given by
(x(x) - p;( - (x:)),
where pi(=-)) E Ryo and (a,)) E Rzo denote the payoff agent has from x=; and the cost incurred by sharing for agent i respectively. We assume (0) (0))) = -0, which means that agent receives no benefit and suffers no cost if she is not exchanging any data with others. Further,
consistent with the existing literature on data-sharing [MYC 23 KG122 BHPS21al, Pr(-) and c;(+)
are monotone in Zy and F.g for all j. i.e., more data acquired gives higher payoff, and more data
shared leads to higher costs.
Core-Stability, A data exchange x is core-stable if there exists no coalition of agents U C N, and an exchange D among agents in U such that u; uz(x=") > u, (ar) for all E U.
On the Existence of Core-Stable Exchanges. Our first observation is that core-stable data exchange may not always exist, even when there are only three agents. This motivates studying natural conditions that guarantee the existence of core-stable data exchange. To this end, we prove that when agents have concave payoff functions and convex cost functions, core-stable data exchange always exists. The foregoing conditions capture a broad range of interesting instances [BHPS21a] KG122 Convexity of cost is natural choice since it captures the property of increasing marginal costs. For

---

instance, data sharing through ordered selection, i.e., sharing records in ascending order of costs involved for collecting the records, results in convex cost functions. There are more models that result in strictly convex cost functions ([RR14). Similarly, several important MI models exhibit concave payoff functions; for instance, payoffs in linear or random discovery models [BPS211], random coverage models (BHPS2Ib), and general PAC learning [MRT18] are all concave. Furthermore, there is empirical evidence that the accuracy function in neural networks under the cross-entropy loss is also concave (0)) We further show that relaxing either of these conditions, i.e., concavity of payoff or convexity of cost, can lead to instances that do not admit core-stable exchanges.
Theorem When agents have concave payoff payofffunctio functions and convex cost functions, core-stable data exchange always exists. One can construct instances relaxing only one of the foregoing conditions (either concavity in payoff or convexity costs) that do not admit any corelstable data exchanges.
Computational Results. We allow oracle access to the value and super gradient of the utility functions. particular, we have the following two types of queries: Value query U(i, return the utility that agent receives from the data exchange æ, uz(x)); Supergradident query VU(i, æ)): return the supergradident of utility function u, (x()) at x if (-) is concave.
We first prove that given an arbitrary instance, determining whether it admits a core-stable data exchange is NP-hard. Thereafter, we investigate the computational complexity of identifying core- stable exchanges under sufficient conditions. We show that finding a core-stable exchange under our sufficient conditions is PPAD-hard. Even we restrict the blocking coalitions to comprise of only constantly many agents, the problem remains PPAD-hard. To the best of our know ledge, this is the first
proof for core-like guarantees in data economies [BGI+ 24a ACGM25). Our
proof technique could be potentially useful for settling the complexity of the problems in BGI 24a ACGM25).
Theorem 2. Determining core-stable data exchanges when agents have concave monotone payoff functions and convex monotone cost functions is PPAD hard. The hardness holds even when we restrict ourselves to our deviating coalitions of constant size. Further, for instances exhibiting non-concave payoffs and non-convex costs, it is NP-hard to determine whether core-stable data exchange exists.
On the positive side, our existence proof yields a pivoting algorithm to find a s-approximate core- stable data exchange. Typically, pivoting algorithms (Simplex [Dan90], Complementary Pivot Algorithms [CDRPO8)) are well-suited for practical implementation. suggesting that the problem may have effective algorithmic solutions in practice, despite the PPAD-hardned In Section 4 we validate the practical efficacy of our algorithm through simulations to [BGI++4a) In particular, we observe that the number of " "pivoting" operations, which in theory may not be polynomially bounded, grows linearly with the number of agents.
estimation task similar
1.2 Related Work
Our work draws on concepts, techniques, and problems from several disciplines, including cooperative game theory, game complexity, and data economics. Providing comprehensive survey of all related work is beyond the scope of this paper. Instead, we focus on (i) federated learning- a parallel framework to ours which also involves incentives and other economic processes involving data an asset, and (ii) some related stability problems in cooperative games and their complexity.
Federated Learning. Federated learning (FL.) offers
and effective distributed learning paradigm in which a group of agents with local data samples collaboratively train shared machine learning model MMR + 17]. This approach has seen widespread success in applications like autonomous vehicles [ESC20] and digital healthcare (DRZ 21, XGS 21). Data exchange can be viewed as a private learning paradigm, where each agent exchanges its own data for other valuable data to train its own private ML model. In contrast, FL is a public learning paradigm, where all agents collaboratively train the same model using data shared among them. Despite these differences. both FL and data exchange face similar challenges in designing principles and mechanisms to incentivize participation. As a result, FL has incorporated a range of concepts from game theory, including Stackelberg games [KPT+20) PTB+19), non-cooperative games [ZFX+19 CZX1.21]. auctions [RSR+21], incentives in collaboration [ADNM225 PSS25), and budget-balanced reward 2S5+
mechanisms MYC+22 23
3

---

Data Markets. Data markets are two-sided real-time platforms facilitating pricing and selling data to data-seekers. Theoretical research on data markets has recently gained traction, given the current importance of data economies. There is a long line of work [AP AP90, BBS18 [KL that investigates eevenue-maximinn
strategies of monopolist data seller. In fact, several studies investigate the pricing of data/ information from first principles in different settings [MDJM21 Pei20 CV20, [BG22]. Competitive pricing and allocation rules have also been discussed in the context of digital goods that behave similarly to data [VVOO) There is another line of theoretical work studying the data exchange economy [BGI 24a ACGM25). The setting of [ACGM25] is the most relevant one to ours, and they also consider the same data sharing model. In contrast to work, [ACGM25] assumes no cost within data sharing, which makes it trivial to obtain a core- core-stable data exchange in their setting everyone exchanges all the data. This way. no agent can achieve higher utility in any exchange. Therefore, [ACGM25] investigates core stability in conjunction with another desideratum, i.e., fairness, and proves their existence results. The utility function of our setting is generalization - an agent's 's utility is defined as payoff minus cost. As a result, the overall utility may not be non-monotonic, which introduces significant complexity. In particular, [ACGM25] is results do not carry over, as we demonstrate in Example D core-stable exchange may not even exist under the generality of [ACGM25]'s 's model when such costs are taken into account. This motivates our investigation into sufficient conditions such as concave payoff's 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 [MYC 23, MSS $e$$$25 25 PSS25
Cooperative Games and their Complexity. Cooperative games focus analyzing mechanisms and studying stable configurations in environments where agents voluntarily cooperate, in contrast to non-cooperative games where agents act independently and selfishly. Similar to Nash Equilibrium in non-cooperative games, pore-stability is the canonical stability notion in cooperative games. The exis- tence of core-stability has been investigated thoroughly within transerable utility (Bondareva-Shapley theorem [Sha67] [Bon63]) and non-transferable utility cooperative games (Scarf's Theorem [Sca67]) )). Scarf's theorem has since been used show the existence of stability in other cooperative settings like stable marriages [FHS23], fractional dominating antichains [AF03] and fractional stable hy hypergraph matching (AF03). Kin08) showed that computing the core of an n person game (outcome of the Scarf's 's theorem) is PPAD-complete. The hardness of Scarf has then been used to show the hardness of several other cooperative problems (see KPR+09) for detailed outline).
Convex Cost Functions. Theorem 3 shows the existence of core-stable data exchange under convex cost functions. Such cost functions have been discussed in the literature [LR14]. As discussed by [LR14] Section 3.1], when data collectors (e.g.. grocery store) collect (private) data from agents (e.g.. buyers) in return for financial compensation (e.g., membership card), the resulting marginal costs grow with the amount of data collected, which naturally leads to convexity. For example, early records are cheaper or less sensitive, while later records may carry greater privacy risks or legal implications. Similar convex models are also adopted in incentive and faireess studies for federated learning (e.g., [MYC+23 25 KGJ22)
2 Existence of Core-Stable Data Exchanges
Basic Notations and Definitions, A coalition is a non-empty subset of the agents and a deviation in data exchange is pair (U, ",), where U is a subset of agents and z is data exchange within U. i.e., T2 > 0 only if i,j E U. A deviation blocks the data exchange æ if u, (xx") > (x) for all core-stable if there does not exist a deviation that blocks æ. Formally,
i E U. An exchange
Definition 1 (Core-Stability and Relaxations). A data exchange is core-stable if for any U S [n], there does not exist an exchange x" over U such that ux( ) > uy (z()) for all i E U. Further, æ is core-stable with respect to s if the above constraint holds for all U C [n]] with |U| < s. x is a-core-
stable if for any U C [n)], there does not exist an exchange x. over U such that u, (x (x) + for all E U.
In this section, we provide complete picture on the existence of core-stable data exchanges. In Section [.]] we show that a core-stable data exchange may not always exist, even for the case of three agents. Despite this, we show that core-stable data exchange always exists in Section 2.2 when (i)

---

the payoff functions are concave and (ii) the cost functions are convex. From here on, we refer to the foregoing two conditions as sufficient conditions. We also show that core-stable data exchange may not always exist if one of the two sufficient conditions is unsatisfied.
2.1 Non-existence of Core-Stable Data Exchange
We first give the reader the main idea of why a core-stable data exchange may not always exist.
Example 1. Consider a data exchange instance with three agents, as illustrated in Figure I where the nodes represent the agents. For any agent i E [3], the green number (denoted by Pÿá) on the incoming edge (j. i) denotes the payoff agent receives if agent shares her full dataset, while the red number (denoted by c2.z) on the outgoing edge () indicates the cost incurred by agent i for sharing her full dataset with agent j. For example, as shown in Fig. 7 when agent 1 shares her entire dataset with agent 2, agent 2 receives payoff of 1/4 while agent incurs cost of 1/4.
Figure 1: Payoff and cost for one-unit sharing, where numbered node represents an agent and the arrow i + j represents that agent is sharing her entrie dataset with agent j. i.e., Fi,j = 1. The green number on the arrow means the payoff that agent receives by the single share, and the red number means the cost that agent incurs.
+5/8
1/22
+5/8
+1/6
1/8
+3/0
-1/0
+3/8
1/88
-1/4
+1/4
For any agent E [3], define her payoff and cost functions as follows.
Pi(Fa,; F3,1) Pos..
(Fa,s - 4)+ + P3. (xz, - (1-c))+ (1)
b Payoff:
e
1 Ce (i,g)) = Ciaax Fi, + CL,B F2.8 + - -ii, 31,3:
Cost:
where
and (+) = max(-,0) 0). The idea behind the payoff is agent benefits from agent j's share only when Ij 1 1-E Meanwhile, the cost function discourages agent from sharing a fraction in the range (0, 1 - e]. as it does not yield a positive payoff for the other agent and only incurs cost. In addition, no agent can share data with two other agents without incurring high cost (which negates the benefit of getting any amount of data).
The values Pa.; PR... Ci Ci,8 are curated carefully so that (I) If nobody shares anything, couple of agents deviate and start sharing data with one another. (2) If only two agents exchange data, there is always one agent who prefers sharing with the third non-included agent, therefore she deviates with the non- cen-included agent. (3) a cyclic data exchange among the three agents, there always exists an agent for whom the cost of sharing data is more than the gain of receiving data, therefore, she prefers to deviate and have no data exchange. Therefore, for any data exchange, there exists a subset of agents that gain strictly higher utility by deviation, implying core stable exchange does not exist. We refer the reader to Appendix A.3 for further details, and a complete landscape of non- non-existence scenarios.
2.2 Existence of Core-stable Data Exchange under Sufficient Conditions
Despite the non-existence in the general setting, we next show that core-stable data exchanges exist for broad class of interesting instances that exhibit concave payoff functions and convex cost functions. To prove existence, we formulate the data exchange problem as an n-person game (proposed by [Sca67]) and then show that the game balanced, which implies that core exists.
An n-person game consists of n agents and a function V().. For every subset S of N, function VSS) specifies the set of outcomes V VSS), which consists of set of utility vectors that are achievable by the coalition S. A utility vector u is attainable by S if u E V(S). The game is balanced for any collection of coalitions T along with collection of nonnegative weights {ōs (ōs)ser, if EShes 5g = holds for all E N, then utility vector u is attainable by N if us is attainable by S for all S E T.
Next, we formulate the data exchange problem into the framework of the n-person game. Define V(-) as follows: for every subset S C N, V(S) is the set of nonnegative utility vectors when only
5

---

agents in S exchanging data. As the utility function is continuous and achieves zero when no data exchanged, we demonstrate that V(S) is nonempty and also downward closed (i.e., if V(S) and u² S u, then u' V(S)) for any subset S C N. In addition, for any collection of coalitions T, weights (ōg
E T and utility vector u that meet the precondition of the balanced game, assume the utility vector us is achieved by data exchange æg. Consider the combination of the data exchanges a= EsET ô5 æs. As (.) :) is concave, for any i E N, we have
(x(=))= ui Σ ös 2s
N E
85 u, (xs)
Σ
85 un Ui.
SET
SETHES
SETHES
As V(N) is nonempty and downward closed, then utility vector u is attainable by N. Therefore, the data exchange game balanced and the core exists. We defer the complete proof to Appendix AA.
Theorem 3. A core-stable data exchange always exists the payoff functions {ps (pe are concave, the cost functions fei are convex.
We remark that the above existence also extends to non-monotone payoff's and costs as long as they are concave and convex, respectively.
3 The Complexity of Finding Core-Stable Data Exchanges
In this section, we explore the computational complexity of identifying core-stable data exchanges. We first show that for instances that do not meet our sufficient conditions, determining the existence of a core-stable data exchange is NP-hard. Next, we shift our focus to finding core-stable data exchanges for instances that satisfy sufficient conditions and establish that this problem PPAD-hard. We defer the full details of the NP-hardness proof to the Appendix and give overview of the PPAD-hardness, which constitutes our main technical result.
Theorem 4. It is NP-hard to determine the existence of stable data exchange.
3.1 PPAD-Hardness of Finding Core-Stable Data Exchange
We perform reduction from the Approximate Fractional Hypergraph Matching problem which is known to be PPAD-hard [KK8 Cs622).
Definition 2 (Approximate Fractional Hypergraph Matching Problem). In an instance of the fractional hypergraph matching, we are given a hypergraph G (V, E) and preference order > over hyperedges E incident to v for every vertex e E V. Denote by e' E. e if To e or e' = e. Let E(v) denote the set of hyperedges that contain/are incident to A fractional matching f in G, assigns to each edge e E, a value f(e) E [0, 1] such that Ee: EEB(o) f(e) S for all V.
Definition 3 (Stable fractional matching). A fractional matching f is (1 e)-stable if for every edge there exists a vertex v such that EetE(()) e' 2 1
Finding an approximately stable fractional matching remains PPAD-hard for any e 1/2201111 even in 3-uniform hypergraphs with maximum vertex degree three Cs522 IKT8. We reduce the problem of finding an approximately stable fractional matching the problem of finding core-stable data exchange. We give the detailed proof in Appendix B.2. of the Appendix, but include shorter overview the reduction the main body.
Theorem 2. Determining core-stable data exchanges when agents have concave monotone payoff functions and convex monotone cost functions PPAD-hard. The hardness holds even when we restrict ourselves to our deviating coulitions of constant size. Further, for instances exhibiting non-concave payoffs and non-convex costs, it NP-hard to determine whether core-stable data exchange exists.
Overview of the Reduction. To see the connection to our problem, we urge the reader interpret the vertices of G as agents, the hyperedges E as coalitions, and the matching f as a function that assigns to each edge (coalition) a value. The stability criterion fractional hypergraph matching requires that for each hyperedge (coalition) e, there is at least one vertex v incident to (one agent that is part of the coalition e) such that the total aggregated value on edges preferred strictly or equal to by v is large: EeeElo)e f(e') > c

---

Given an instance of fractional hypergraph matching, we construct a data exchange instance, where we have agent v. corresponding to a vertex v in G. Further, each blocking coalition corresponds to hyperedge. We then show that if the core-stability condition holds in the data exchange problem - -i.e., for every blocking coalition corresponding to a hyperedge c, and any exchange within that coalition, there exists an agent Uo who prefers the current exchange - then for the corresponding hyperedge e in G, we have Ee f(e)) 2 1 - e for the agent v.
The data exchange instance is constructed in the following way: Given an instance (G = EV, f>o hvE)) of fractional hypergraph matching, with [E(+)] I 3 and every hyperedge containing three vertices (if one hyperedge has less than three vertices, we can add dummy vertices to it), we construct an edge-agent e, for every edge e, and vertex-agent v. for every vertex Every vertex agent v. is only interested in (has non-zero marginal utility for) the data of the edge agents corresponding to the hyperedges incident to v, and every edge agent C. is only interested in the data hosted by the vertex agents corresponding to the vertices incident to e. Moreover, for every A > O, every edge agent ep willing to exchange A units of its data with the vertex agents corresponding to the vertices in e, for A units of data from them, i.e., the payoff gain from receiving A units of data from the vertex agents compensates the cost of sharing A units of data with them. The payoff of a vertex agent Ue. is defined as Eee((v) ([ea, (.. where w(Va: eu) is the utility agent Vo gets from unit data of ea. We set the weights (w(+, -)) such that ~ e', implies w(U., ea) w(va, eaa) The cost of any vertex agent Vas Cv. (2:) is .. (Eevve Te,,e. - -1 for a sufficiently large r, which ensures that EeEE(e) E(w) e. S 1 + y for a sufficiently small ? > O, as otherwise agent va will have negative utility and data exchange æ will not be individually rational, and consequently not core-stable.
Core Stability + Stable Matching. Now we show that ensuring core-stability in data exchange implies stability in fractional hypergraph matching. To this end. first observe that in fractional hypergraph matching, the stability criterion involves one variable per hyperedge, which appears in the inequality associated with every vertex incident to that hyperedge (See Definition 33 However, for core-stability in data exchange, inequality in Definition[]ime iivolvvs distinct variables (in particular variables Te.. er..e. for every vertex v incident to e, as the payoff and cost functions of v. are functions of these variables). To overcome the foregoing dilemma, we introduce more agents (call them intermediate agents), and carefully design their cost and payoff functions, such that if x is core-stable data exchange, then Te.." = T'...n R Fv = Ivy for all v, e/ incident to e. In particular, for each edge e, we introduce set of intermediate vertices Le = {ie E E(v) such that each ie acts as an intermediary between Ca and Ca. The payoff and cost functions of the intermediate agents are designed in such a way that we ensure the exchanges between intermediary vertices with their corresponding vertex agents and edge agents are almost the same(See Figure O We refer the reader to Appendix (B.2.2 for full details. Still, for the remainder of this Section, we proceed assuming that in a core-stable data exchange, all pairwise data exchanges between an edge agent and its corresponding vertex agents have the same value. We set f(e) to this value.
Lemma 1. If data exchange x: is core-stable, then the fractional matching I is (1 (1-63 e)sttabl...
Proof. We first show that is valid fractional matching: Recall that by the design of the cost functions of the vertex agents, we ensure that EeeE(v) Toa.e. I 11+ r for all v. Since we ensure that Zva.ea = Tea, = f(e,, we have EcEB(r) f(e) S 11+1 s 1 + e for a sufficiently small Therefore, f is a fractional matching.
We next show that f also satisfies the stability criterion. Observe that the payoff of any vertex agent (i) u(Ca; U Va) Since Tea.ti = =((c for all v incident to e, the payoff of v, can be expressed as E.E E(E w(va,ea) [(e). Consider the coalition C formed by the edge agent e, and the vertex agents corresponding the vertices in Consider the data exchange y obtained by setting ye..", = you..e. 1 for all incident to e in G. Also, recall that we are working under the assumption that all pairwise exchanges between the vertex agents and edge agents corresponding to the hyperedge e have the same value in the exchange x. By the construction of ue, (-), we have
V, is Fe
Wea (y) > Ue. [x: Since is core-stable, at least one of the vertex agents, say Va, must have Uv. (x) 2 Ue. (z). Therefore for any vertex agent Da in C, we have u, (y) = w(e.: va) 1 (note
'ee use the notation a+ to represent max(a, 0).
2 As y can be obtained by increasing all pairwise exchange by the same additive factor
7

---

that the cost is zero as the total data received is equal to 1). Since there exists an agent in C with
Un (2)) 2 una (z), we have,
w(ea: va) Uv (z) Uv (x)
E
w(e's vo) vo)f(e) S ie Σ f(e)
Σ f(e),
c'EE(o)
c/se'
where / = max EF(D)e w(ea, l va) (equals zero if there is no e' E E(u) such that e' X e), and V = Ea() w va). Observe that v 2 woeaa va) > w. Now, substituting Ee'o te S (e) as
1 Deiezze [(e,, we have
w(ea va) w
Σ f(e) + w. 1 1- E f(e) cf
2 w(ea: va)= = E f(e) 2
1
c'iczze
e/
Given that [F(b)] & 3 for all v, we can set
d 11 1
is v's favorite edge e is v's second favorite edge otherwise,
w(ea, Va)
H
H
implying that Eetarz f(e) that f is a stable matching.
2
2 - 6 for a sufficiently large d. This implies a+I
4 The Pivoting Algorithm and Empirical Results
In this section, we adapt the pivoting algorithm [ca67] to find core-stable data exchange under sufficient conditions- when payoff functions are concave, and cost functions are convex, and coalitions are constrained to be of constant size. As we mentioned in Section 2.2] our game is balanced and therefore we can get a pivoting algorithm (PA) following the proof of existence of core for balanced game theorem in Scarf'ss theorem [Sca67]. It is worth noting that, when the number of agents is not constant, even verifying whether given data exchange is core-stable is coNP-complete, and we defer the proof to Appendix
4.1 The Pivoting Algorithm
We first define matrices: coalition matrix C and the utility matrix U, both with dimension m. Given a coalition S C [n]. we aim to identify all possible utility vectors resulting from data exchanges within S. Since this set may be infinite, we instead consider discretized approximation of the utility space. Suppose v E V(S), We create the ktth column in the coalition matrix C: C.A 1 if E S and 0 otherwise, which the characteristic vector of the coalition. Meanwhile, we insert a column into the utility matrix U at the same coordinate: u,, = M for i & S and u, 2 for i E S where M is very large number" Note that to compute the utility matrix, we need to find all achievable utility values in the grid. To this end, we assume that the payoff of every agent is uniformly bounded") by B. For fixed e > O, we create grid of size e, so utility of every agent will be an integer multiple of Given a coalition of size k:, there are most (B/e)* possible utility vectors. Using the Ellipsoid method, we can approximate the feasibility of each in polynomial time, as shown in the following claim (proof deferred to Appendix C.T).
Claim 5. Given coalition S C [n]] and utility profile (w))es, we can compute in polynomial time either a data exchange such that (x(x) 2 Us for all E S or return that no data exchange satisfies u; (x) 2 for all i E S.
After constructing the two matrices, we reduce finding core-stable data exchange to solving Scarf's s Lemma (as elaborated in Appendix C.3) Then we apply PA. It maintains two evolving bases: a cardinal basis for C and an ordinal basis for U, where each basis consists of set of column indices. the two bases differ, PA respectively performs the cardinal pivot step and the ordinal pivot step to adjust the two bases. These bases evolve iteratively until equal. As the total search space is finite, PA terminates in finite time. We defer a detailed description to Appendix C.4
'The intuition behind choosing a large M is that we do not want an agent outside the coalition block deviation to this coalition. In fact, we assign slightly different M to these entries to make these entries non-identical. By scaling down the payoff functions, hardness results still hold.
8

---

Running Uie
Coalitions
Phzze maat
Ittrations
27
10
6.2
# of agents
of agents
# of agents
(a) Calls and Coalitions
(b) Running time
(c) Number of iterations
Figure 2: Performance of PA on the constructed data exchange instance.
4.2
Empirical Results
Next, we empirically test the performance of PA on real-world datasets. We construct a data exchange instance using the same road map dataset Troa as the previous work [BGI+ 24b). The graph contains 4.4K nodes and 9.6K edges. The data exchange instance is constructed as follows: each agent i corresponds to a path P.. The agents aim to estimate the delays on their roads. Assume each agent possesses 2 random samples of the delay for every edge e included in her path with identical variance o² The payoff of agent is determined by the sum the variance of the mean of the random samples of every edge that path P; includes. For every edge E P. the initial variance of the mean is given by oZ/zz- Hence, the initial sum of variance of agent i given by ΣeEp, o e In an exchange æ, Fi represents agent i will shares Zij" z data samples with agent j for every e E P.n.P The payoff function p-(-) of agent is induced by the decrease of the sum of variance, follows:
o²
p((x)) =
Σ jinE P, j 33
eEP.
eEP.
Meanwhile, we assume that every agent i incurs cost of (x) = us EeEp, He 2e EjieEP Rij. where le represents the cost of sharing per random sample of edge
Simulation Setup. We run PA on the above data exchange instance to find a 0.1-core-stable exchange, fixing each coalition size to 3, and varying the number of agents as n = 3/ for E [9). We adopt the same method as [BGI+24b] to sample an agent i from the road map: Sample a random node u and then sample a length / uniformly at random between and the depth of the BFS tree rooted at v. Then we sample another node uniformly at random from all nodes within layer I, choose the shortest path from u to c, and assign it to agent i. The variance of each edge, de, is a random number in range [0, 1]. and He is set as (1 - σ²)) 10 10-3 In addition, every agent starts with z random data samples for every edge in her path, where z is chosen uniformly at random in the range [4, 9]. All experiments were run MacBook Pro with Apple M3 Pro CPU and 18 GB RAM. The implementation uses Python 3. 12 and SciPy [VGO* 20) (v1.13.0) for concave optimization.
Performance. We evaluate PA's performance on the constructed data exchange instance using three metrics: (i) number of coalitions formed; (ii) number of concave optimization calls; and (iii) runtime for coalition matrix construction and pivoting. For each agent size, we repeat the construction and PA execution 20 times and report the mean. Results are shown in Figure with the first subfigure displaying optimization calls and coalition sizes. Both reach the maximum when n = 27, where the number calls and size of coalitions are respectively 7.17 x 10 and 2, 914. In addition, Figure 2b shows the time of constructing the coalition matrix (Phase I) and PA (Phase II). The most (least) expensive sample includes 198 (resp. 533) possible coalitions, and the time of constructing the coalition matrix is 9, 821.54 .54 (resp. 151.36) seconds, while the running time of the pivoting algorithm 118.08 (resp. 2.36) seconds. The time of constructing the coalition matrix grows significantly in polynomial time, while the time of PA is much smaller and less affected by the number of agents. On average, PA terminates 7.36 seconds, ranging from 0.001 seconds for n 3 to 38.37 seconds for n 27. The third subfigure (Figure 2ch shows the number of iterations until termination. We observe a modest, seemingly quadratic growth in iterations with the number of agents. PA takes an average of 238.3 3 iterations and up to 1434 in the worst case.

---

Discussion and Conclusion
We introduced general model of data exchange and studied the existence and computation of core-stable solutions within it. We identified interesting sufficient conditions for the existence of core-stable exchanges. We outline computational barriers and end with an algorithm that can be expected to be efficient in practice. We see this paper as an initiation for studying stability in data exchange economies. Currently, our model is very general in its assumptions, and we expect more efficient algorithms for some special cases, e.g., (i) accuracy functions from Gaussian inference or PAC learning (usually p.
1/(E, TyeZys)), and cost functions being linear, or (ii) when there are only constantly many payoff and cost functions, corresponding fixed types of agents.
Another promising direction is to explore additional desiderata beyond stability. For in- stance, [BGI+ ACGM255] investigate exchanges that satisfy both core-stability and fairness criterion, where each agent's 's final payoff is proportional to their contribution to the payoffs of others. However, their model does not incorporate costs for data sharing- making core-stability alone trivial to achieve (set all Tiy = 1). An intriguing question is whether one can compute exchanges that are both core-stable and fair when agents incur costs for data-sharing. In essence, this involves integrating our cost-aware framework with the fairness-oriented approach of [BGI+ 24a ACGMM25).
Finally, we believe that questions of stability merit investigation in more general models- particularyy those involving externalities. Such externalities arise naturally in competitive environments, where collaboration between two agents may negatively impact the utility of others (e.g., collaborating agents can capture a greater share of the market). these settings, we suspect that core-stability is unlikely to hold. However, it would be interesting to explore whether suitable mechanisms such as structured rules for splitting the joint utility gains can facilitate the existence core-stable data exchanges despite the presence of externalities.
Acknowledgements
The research of Bhaskar Ray Chaudhury and Jiaxin Song is supported by an NSF CAREER grant CCF No. 2441580. The research of Parnian Shahkar was supported by NSF grant CCF-2454115. The research of Pooja Kulkarni was supported by NSF grant CCF-2334461. Most of the work was done when the author, Pooja Ravi Kulkarni, was a student at UIUC. We also thank the anonymous reviewers for their helpful comments and suggestions.
References
[ACGM25) Hannaneh Akrami, Bhaskar Ray Chaudhury, Jugal Garg, and Aniket Murhekar. On the theoretical foundations of data exchange economies. In Proceedings of the 26th ACM Conference Economics and Computation, pages 444 444, 2025.
[ADNMM25] Saced Alaei, Ali Daei Naby, Ali Makhdoumi, and Azarakhsh Malekian. Incentivizing data collaboration: A mechanism design approach. Available at SSRN 5297868, 2025.
[AF03] Ron Aharoni and Tamás Fleiner. On lemma of scarf. Journal of Combinatorial Theory, Series B, 87(1):72-80 -0, 2003.
[AP86] Anat R Admati and Paul Pfleiderer. A monopolistic market for information. Journal of Economic Theory, 39(2):000-438, 1986.
[AP90] Anat R Admati and Paul Pfieiderer. Direct and indirect sale of information. Econo- metrica: Journal of the Econometric Society, pages 901-928, 1990.
[BBG22] Dirk Bergemann, Alessandro Bonatti, and Tan Gan. The economics of social data. The RAND Journal of Economics, 53(2):263-22 2022.
[BBS18] Dirk Bergemann, Alessandro Bonatti, and Alex Smolin. The design and price of information. American economic review, 108(1):1-48, 2018.
[BGI+24a] Aditya Bhaskara, Sreenivas Gollapudi, Sungjin Im, Kostas Kollias, Kamesh Munagala, and Govind S. Sankar. Data exchange markets via utility balancing. WWW, pages 57-65. ACM, 2024.
10

---

[BG] Aditya Bhaskara, Sreenivas Gollapudi, Sungjin Im, Kostas Kollias, Kamesh Munagala, and Govind S. Sankar. Data exchange markets via utility balancing. In Proceedings of the ACM Web Conference 2024, WWW '24, page 57-65, New York, NY, USA, 2024. Association for Computing Machinery.
[BHPS2Ia] Avrim Blum, Nika Haghtalab. Richard Lanas Phillips, and Han Shao. One for one, or all for all: Equilibria and optimality of collaboration in federated learning. In ICML, volume 139 of Proceedings of Machine Learning Research, pages 1005-1014, PMLR, 2021.
[BHPS2Ib] Avrim Blum, Nika Haghtalab, Richard Lanas Phillips, and Han Shao. One for one, or all for all: Equilibria and optimality of collaboration in federated learning. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 1005-1014. PMLR, 18-24 Jul 2021.
[BKL12] Moshe Babaioff, Robert Kleinberg, and Renato Paes Leme. Optimal mechanisms for selling information. CoRR, 204.5999, 2012.
[Bon63] Olga N Bondareva. Some applications of linear programming methods to the theory cooperative games. Problemy Kibernet, 10: 19, 1963.
[CDRPO8] Bruno Codenotti, Stefano De Rossi, and Marino Pagan. An experimental analysis of lemke-howson algorithm. arXiv preprint arXiv:0811.3247, 2008
[Com20] European Commission.
european strategy for data. 2020. Avail-
able at https: -our-ex.... europa. su/Leegal-cotten//Il 1593073685620kuri1
52020000066
[Cs622] Gergely Csáji. On the complexity of stable hypergraph matching, stable multicom- modity flow and related problems. Theoretical Computer Science, 931:1-16, 2022.
[CV20] Yang Cai and Grigoris Velegkas. How sell information optimally: An algorithmic study. arXiv preprint arXiv:201 145700 2020.
[CZXL21] Wenqing Cheng, Yuze Zou, Jing Xu, and Wei Liu. Dynamic games for social model training service market via federated learning approach. JEEE Transactions on Computational Social Systems, 911):64775, 2021.
[Dan90] George B Dantzig, Origins of the simplex method. A history of scientific computing, pages 141-151. 1990.
[DR Ittai Dayan, Holger R Roth, Aoxiao Zhong, Ahmed Harouni, Amilcare Gentili, Anas Z Abidin, Andrew Liu, Anthony Beardsworth Costa, Bradford Wood, Chien-Surg Tsai, et al. Federated learning for predicting clinical outcomes in patients with covid-19 Nature medicine, 17(10):1735-1723 2021.
[ESC20] Ahmet M Elbir, Burak Soner, and Sinem Coleri. Federated learning in vehicular networks. arXiv preprint arXiv:2006.01412, 2020.
[FHS23] Yuri Faenza, Chengyue He, and Jay Sethuraman. Scarf's algorithm and stable marriages. arXiv preprint arXiv:2303.009 2023.
[IK18] Takashi Ishizuka and Naoyuki Kamiyama. On the complexity of stable fractional hy- pergraph matching, In 29th International Symposium Algorithms and Computation (ISAAC 2018). Schloss- Schloss-Dagstubl- Dagstubl-LLibniz Zentrum für Informatik. 2018.
[JV10] Kamal Jain and Vijay Vazirani. Equilibrium pricing of semantically substitutable digital goods. arXiv preprint arXiv:1007.4588: 2010.
[KGJ22] Sai Praneeth Karimireddy, Wenshuo Guo, and Michael Jordan. Mechanisms that incentivize data sharing in federated learning. CoRR, 0ww//2207.04557, 2022.
[Kin08] Shiva Kintali. Scarf is ppad-complest arXiv preprint ar arXiv:0812.1601.

---

[KMH* 20]
20] Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford. Jeftrey Wu, and Dario Amodei. Scaling laws for neural language models. CoRR, abs/2001 .00361, 2020.
[KPR *09] Shiva Kintali, Laura J. Poplawski, Rajmohan Rajaraman, Ravi Sundaram, and Shang- Hua Teng. Reducibility among fractional stability problems. In FOCS, pages 283-292. IEEE Computer Society, 2009.
[0] Latif Khan, Shashi Raj Pandey, Nguyen H Tran, Walid Saad, Zhu Han, Minh NH Nguyen, and Choong Seon Hong. Federated learning for edge networks: Resource optimization and incentive mechanism. IEEE Communications Magazine, 58(10)888-
93, 2020.
[LR14] Xiao-Bai Li and Srinivasan Raghunathan. Pricing and disseminating customer data with privacy awareness. Decision support systems, 59:63-73, 2014.
[MDJM2I] Sameer Mehta, Milind Dawande, Ganesh Janakiraman, and Vijay Mookerjee. How to sell a data set? pricing policies for data monetization. Information Systems Research, 32(4):1281-1297, 2021.
[MMR+ + 17] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communicationn-eficcenn learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273-1282. PMLR, 2017.
[MRTI8] M. Mohri, A. Rostamizadeh, and A. Talwalkar. Foundations of Machine Learning, second edition. Adaptive Computation and Machine Learning series. MIT Press, 2018.
[MSS+25] 25] Aniket Murhekar, Jiaxin Song, Parnian Shahkar, Bhaskar Ray Chaudhury, and Ruta Mehta. You get what you give: Reciprocally fair federated learning. Forty-second International Conference on Machine Learning, 2025.
[MYC*23] Aniket Murhekar, Zhuowen Yuan, Bhaskar Ray Chaudhury, Bo Li, and Ruta Mehta. Incentives in federated learning: Equilibria, dynamics, and mechanisms for welfare maxinization. In NeurIPS, 2023.
[Pei20] Jian Pei. A survey on data pricing: from economics to data science. IEEE Transactions on knowledge and Data Engineering. 84(10):4586-4600) 2020.
[PSS25] Ariel D Procaccia, Han Shao, and Itai Shapira. Incentives in federated learning with heterogeneous agents. arXiv preprint arXiv:2509.21612, 2025.
[PTB + 19] Shashi Raj Pandey, Nguyen H Tran, Mehdi Bennis, Yan Kyaw Tun, Zhu Han, and Choong Seon Hong. Incentivize build: A crowdsoureing framework for federated learning. In Proceedings-IEEB Global Communications Conference, GLOBECOM, page 9014329, 2019.
[RHL$20 Nicola Ricke, Jonny Hancox, Wenqi Li, Fausto Milletari, Holger R Roth, Shadi Albarqouni, Spyridon Bakas, Mathieu N Galtier, Bennett A Landman, Klaus Maier- Hein, et al. The future of digital health with federated learning. NPJ digital medicine, 3(1):1-7, 2020.
[roa] Street network new york in GraphML. htte:Mll.tttttt//// http::httts//ttt kaggle. wttpggle..omddaaaaeeee com/datasets/ htwp:/p//ssteeeeetteeeeeeoeeeeee new- in- graphml Accessed: 2023-09-
20.
[RSR+ Palash Roy, Sujan Sarker, Md Abdur Razzaque, Md Mamun-or Rashid, Mohm- mad Mehedi Hassan, and Giancarlo Fortino. Distributed task allocation in mobile device cloud exploiting federated learning and subjective logic. Journal of Systems Architecture, 113:101972, 2021.
[Sca67] Herbert Searf. The core of an person game, Econometrica: Journal of the Econometric Society, pages 50-69, 1967.
12

---

[Sha67] Lloyd S Shapley. On balanced sets and cores. Naval research logistics quarterly. 14(4):453-460, 1967.
[Sho12] Naum Zuselevich Shor. Minimization methods for mon-differentiablefurnnce vol- ume 3. Springer Science & Business Media, 2012.
[VGO+20] Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, CJ Carey, Ilhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-272, 2020.
[Vis21] Nisheeth Vishnoi. Algorithms for convex optimization, Cambridge University Press, 2021.
[XGS+21] Jie Xu, Benjamin S Glicksberg, Chang Su, Peter Walker, Jiang Bian, and Fei Wang. Federated learning for healthcare informatics. Journal of Healthcare Informatics Research, 5(1):1-19, 2021.
[XPHS23] Hanson Xu, Michael Pan, Xu Huang, and Allen Shen. Federated learning in tonomous vehicles using cross-border training. NVIDIA Developer Blog, 2023.
|ZFX 19] Yuze Zou, Shaohan Feng, Jing Xu, Shimin Gong, Dusit Niyato, and Wenging Cheng. Dynamic games in federated learning training service market. In 2019 IEEE Pacific Rim Conference on Communications, Computers and Signal Processing (PACRIM), pages 1-6. IEEE, 2019.
13

---

A Existence of Core-Stability
In this section, we provide complete picture on the existence of core-stable data exchanges. In Appendix A.2 we show a core-stable data exchange always exists when (i) the payoff functions are concave and (ii) the cost functions are convex. From here on, we refer to the foregoing two conditions as sufficient conditions. Then we show that core-stable data exchange may not always exist if one of the two sufficient conditions is unsatisfied, even when we have only three agents.
A.1 N-Person Game, Balanced Game
The definition of the core of an n-person game was proposed by Scarf [Sca67]. An n-person game with con-transferable utilities consists of n agents (denoted by N) and function V--). Let IR to be subspace of R where the entries corresponding to coordinates indexed by S can take values in Rgo. while the entries for coordinates not in S are set to O. For every subset S of N, function V()) returns set of outcomes VSS) consisting of set of utility vectors, which belong to R and represent all the achievable utilities of agents in S when they collaborate exclusively with other agents in 8. Next, we introduce the notion of balanced game.
Definition 4 (Balanced Game). A collection T' of subsets of agents is said to be balanced, if there exists an assignment ( such that, for every agent E N, have Es:es òg We say utility vector is attainable by S if u V(S). If is utility vector for agents, let us denote the projection of u onto the agents in S. A game balanced and only if for any balanced collection T and any u, if us is attainable by all S in T, then is attainable by N.
The core of an n-person game is defined almost the same as core-stable exchange. A core is a utility vector that is attainable by the entire agent set N and cannot be blocked by any coalition. Given utility vector u. if a coalition of agents can get higher utility for all of its members, then the vector said to be blocked by that coalition. As shown in (Sca67], the core of any n-person balanced game exists if (-) satisfies the following mild assumptions.
Lemma [Sca67]). The core of any balanced n-person game exists if the function V-) is assumed that:
For each S C N, V(S) is a closed set;
If E VSS) and E S with y S then y E V(S):
The set of vectors in V(S) in which each player in S receives no less than the maximum that she can obtain by herself is nonempty and bounded.
A.2 Existence of core-stable data exchange under Sufficient Conditions
We first formalize the data exchange problem into the framework of an n-person game. The function V(-) is specified as follows: for every subset S N, we define V(S) as the set of nonnegative utility vectors that are attainable by the agent set S. Formally,
V(S) {u,()))) æ E [0, 1|ss and u. (x) > 0, N)
where [0, 1|s55 denotes the set all data exchanges among S, i.c., only shares between agents in S can take values in [0, 1] while other fractions are forced to be zero. Next, we show the game is balanced when the payoff functions (-()) are concave and cost functions c.()) are convex, which would then imply that a core exists.
Theorem 3. strelstable data exchange always exists if the payoff functions {pi)ieN are concave, the cost functions {cz (ci)ieN convex.
Proof. We demonstrate that the function V(.) meets the pre-conditions of Lemma 2 First, we claim that VSS) is a closed set for any S C N. For any sequence {u/ E V(S) converging to some utility vector u", we show u² E VSS). By the definition of V(S), u² is attainable by
'This is coordinate-wis. comparison of the vectors. Given vectors b E ded < b if and only if a, S b, for all i E [d].
14

---

Algorithm 1: Update the data exchange æ iteratively
Input: 6 >> 0, utility vector y and an exchange a: on a specified agent set S C N;
2 Let t- 0 and x. <=;;
3 while there exists an agent E S such that u. (x²) 2 y/4 do
Let + k 1 and x be the copy of the last exchange;
Pick an arbitrary agent E S with j A i and positive shares with agent i, i.e., 25, > 0:
Decrease the share oyy, until æ5,, = or u, (x(x") = y/3
return x;;
some exchange x² As the space of data exchanges [0, 1] is compact, there exists a subsequence (x)(() j converging to some exchange x' E VSS). By the continuity of the utility functions, we have u, uz limp--oc U4 (1())(())= on for any i E S. Thus, u² is attainable by agent set S.
Next, we show that if u E (SS) and y E S with y S. u, then E V(S). Suppose u is attainable by some exchange æ. We now run the procedure described in Algorithm which iteratively adjusts the current exchange until the utility vector is quite close to y. We then show that y is also included in V(S) as follows. First, we show that the procedure always terminates.
Claim 6. For any 0, Algorithm 7 will terminate in finite steps.
Proof. Let 1),;(z)) (x)) be the infinum of E [0, 1] such that u4(ar + e.e,)) ux(x) + e. If such t does not exists (2 + it-ee eja)) < (x(x)) + for any E [o, 1)), we set ().(())) ) = 1. For every agent E S, we let (;()) minjesssti (z)) We first prove the following property.
inf 0, for any iE
Suppose for contradiction that inf (x)) = O. Then, there exists a sequence of exchanges and values of t, (a= (4) such that (x + 4 -j.a)) > (x(* + e and lim 4. = As the whole space of exchanges is compact, there exists a subsequence {a:(()) converging to some exchange x and (Q(1) + 0. Also, u, (z((((())))))))))))))))))))))( + (u()) ej,s) > (((x((()) + e for any By taking the limit on both sides, get the contradiction > 0 and u, is continuous. Therefore, we can further conclude that,
inf (2) = inf min (1) min inf ng.; ())= > 0, for any i min jES
(inf (infm:())) > 0. 20
jE837i i x
EES
Denote the minimum by A. We can observe that all the shares Fyss are iteratively decreased each round. If step terminates until (x(x)) = Yr. Zyys will be decreased by a value of at least A by the definition of (x)) For that reason, we know that, at each round, one of the following two must happen: (1) one positive Fy,i is turned to zero; (2) one Fy.s decreases by least A. As the sum of Tj is bounded by [ the number of iterations is at most | / + 1, which is finite.
According to Claim 6 we can find data exchange xxc) over S for every e O, such that its utility vector = (x:()) )) s satisfies yi S (x) I y: + As the set (SS) closed, by taking to 0+. we know that V(S).
Thirdly, when one in S shares anything with another one, all the utilities will be zero. So 0 is attainable by S. Besides, as all the utility functions are continuous and the space of all exchanges is closed, the utility vectors of V(S) are bounded. Thus,
conclude that the function V satisfies
the conditions in Lemma 2
Finally, show that the data exchange game is balanced. For any balanced collection T and any ug is attainable by all S in T. we need show that also attainable by N. We let æ5 to be the share of agent to agent) j in the data exchange that attains utility vector us. We then construct new exchange x over N by
Σ 8g 2
Fij
SETGES
15

---

As 2 S 1 and ESETHES ös = 1, 2i, S 1, which satisfies the feasibility constraints. Besides, since pi is concave and 6j is convex, the utility function u; (z)) is concave, which means that
((
(x(x)) = ui
Σ
85 I
SETRES
s,tE(n)/
Σ
òg ui Ma(x
(By concavity of pi(+) and convexity of c+(+))
SETRES
Σ SETUES
U4 U4
(As us is attainable by S)
Hence, (2) 2 for any E By the second property of V.),, is also attainable by N. Thus, data exchange game is balanced and has a core u. By the definition of the core, we know u is attainable by some exchange æ of the agents, and is not blocked by any utility vector of ((S) for any S [n]. For any utility vector u' that is attainable by S but not included in V(S), we know there must exist agent in S receiving negative utility, which means that S cannot form a deviating coalition either. Therefore, æ is a core-stable data exchange.
A.3 Non-existence of Core-Stable Data Exchange For Instances Not Satisfying Sufficient Conditions
We first provide more details of the construction discussed in Section 2.1 By the construction of the payoff function, one agent receives a positive payoff only when she receives a share larger than 1 from another agent. As the cost function monotone, we can reduce fraction Vi,j smaller than 1 - c, which does not decrease the utility of any agent and hence, does not affect the core stability of the data exchange æ. Below, we assume that zi.j is either that the denominator of the third term of the cost function, é, is assumed to be sufficiently small constant, such that if ai and Hh are both larger than 1 e, the cost will no less than (1 -c) which is pretty larger than the maximum payoff agent i can receive (i.e., Pi.o + Pi.s). Hence, agent i would have the incentive to deviate, which implies that every agent cannot have positive shares with both two other agents.
if is
larger than 1-c c. Observe
Exchange
Ageuts
21.2
21.3
22.1
22.3
#5.1
Z3.2
M2
2.33.3
0
0
U
0
0
(1,2)
0
0
0
0.25
0.125
28
[1. 2,
e
0
2
0
0.25 +
< 0.125 +
0
[2.3)
0
0.25
0.125
21.333
0
0.125
0.25
x
(1
0
1
0.25
0.125
[1,2,3]
0
0
2
11-e
2 1 -i-e
0.25 +
<
0.125 +
[1.3]
0
0.125
0.25
[1,
2,
1 1
fe
00.125 +
(3)
III
2,
2
2 1
- 0..225 +
0.25 +
< 0.5
1
(1)
0
Table 1: Deviation (U, x0 ") for each case of data exchange æ. The row with æ is the original exchange and the row with t is the deviation. Cells in gray are the utilities of agents in the coalition U.
Next, we construct a simple graph G = (V, E)) with three vertices, with each of them corresponding to an agent. There is an edge from to j agent shares more than c unit of data with agent j. Therefore, every agent has an out-degree of at most 1 and there is no source in the graph. It suffices discuss the following three cases.
Case Nobody shares anything, i.e., æi.j = 0 for any i,j [n].
Case II: Only two agents are exchanging data. Thus, there are three possible subcases: (i)
E {(1, 2), (2, 1)): (ii) E = (11,3), 1)), (iii) E {(2,3). 3), (3,2)}
Case III: All three agents are exchanging. By the properties of the graph, there are only two possible subcases: (i) E {(1,2), (2, (3, 1)} or; (i) E (11,),, (3, 2), 1)).
16

---

4:11.
1.5
Cost
1.0
0.5
00/ 0012
466 o
0.40 0.000 6.60
1.0
0.8
0.6
x1.2
X1,3
0.0
Figure 3: Cost function (-) of agent 1
However, shown in Table for each case, there exists coalition U and an exchange x" such that every agent in can improve her utility. In particular, for the first case, agent and agent 2 have the incentive to form coalition. For either of the second cases, there exists one agent of the two having the incentive to form a coalition with the other agent. For either of the third cases, there always exists one agent with negative utility who improve her utility by deviating alone. Therefore, conclude that it is impossible to find a core-stable exchange in both the three cases, which concludes the exi-xxistence.
Remark can be noticed that, in Table each agent the coalition improves her utility by at least 0.125 in each case, which even proves stronger result a-core-stable does not always exist in an arbitrary instance even when a is a positive constant number.
Next, we showthat when either of the two sufficient conditions concavity of payoff functions or convexity of cost functions relaxed, core-stable data exchange may always exist, when having only three agents.
Proposition 1. Even if both payoff and cost functions are continuous, core-stable data exchange does not always exist if either the concavity of payoff or the convexity of cost is relaxed.
A.3.1 Linear Payoff and Concave Cost
We have already provided an instance where core-stable data exchange does not exist when both the concavity of payoff and the convexity of cost functions are removed. Next, we show also holds when there are three agents and only the convexity of cost is removed.
Let the payoff functions of the three agents (r()).p2( P)))) Pa(-) )-) be defined linear functions. In particular, Pı(x) Pi.a Ti,a + Pr,3 Ti where (a, 3) = [3] {i) and pi.j is defined by Figure
The cost functions are defined follows. Fix sufficiently large constant C We take agent as an example and start by defining her costs for some particular sharing (71,2;21,3))
0
if (41,2, = (0,0) 0)
c.3/c. F1,3
if 11,2 = 0 and Æ1.3
ei (2122,
21122
if 2 = 0 and F1,2 S
if if 2 e or 11,3 2
Then we define the costs for the remaining points (x1.2, 21,3) in [0, 1] [0, As shown in Figure 3
consider the four planes Pt, P2, P3 formed by connecting four points respectively, where plane Pi
formed by points (0, O, 0), (c. C). (c. O, C12). (0, C), plane P2 is formed by points (c,0, 012). (1, O, c1,2), (1, C),, (c, e, C),, plane P3 is formed by points (0, (, (1.3), (0, (,,,s. (c,1,)), C), and plane P1 is formed by points (E, (c, 1, C), (1, e, C),, (1,
Consider the union of the three planes P Pi U Pg U P3 U Pa. Since their projections on the J1,2 F1.3 plane do not overlap (except the intersection line), for every 41,3) E [0. 1] [0, 1), there is just one possible such that (11,2, c) E P. We then define ei (11,2, as follows:
Ca (1a)) = such that (11,2, c) E P.
Besides, as the constant is sufficiently large, we can observe that function ei is concave. We symmetrically define 02 and c3 the above and they concave for the same reason.
17

---

U2
Sn+1
U2
C2
Figure 4: Illustration of reduction of Theorem where each node corresponds to an agent.
Next, as C is sufficiently large, every agent cannot share fractions of at most e with the other two agents simultaneously.
Then we show a core-stable exchange still does not exist in this case. We prove it by contradiction. Assume is core-stable exchange. Then still discretize the data exchange If xi S c, then we reduce it to zero, which only reduces the utility of agent j by e. Otherwise, if z5.j > E, then we increase it to 1, which does not affect agent i's cost, since her two shares cannot be larger than simultaneously and the other share is reduced to zero. It can be noticed that ži,j turns to one or zero for any i,j [3] after the discretization. In addition, the discretization operation only decreases the utility of each agent by 2c.
However, since 2s is sufficiently small, our previous discussion demonstrates that there always exists a deviation (U, x²)) that significantly improves the utility every agent in U, no matter how integral exchange performs, which means that there still exists blocking ær before the discretization and contradicts assumption of ctre-stability of x.
A.3.2 Convex Payoff' and Convex Cost
We now construct data exchange instance where core-stable exchange does not exist for convex payoff functions and convex cost functions. Set the number of agents as three and use the same payoff function as Section 2.1 Define the cost function as follows:
(x))
(Di,a + 2g,3 - 1)+ + Ci Ii,a + Ci,B Z1,3:
where () = [3] \ (i). As the payoff functions are the same, we can still discretize the data exchange make every æijj = 0 or Fi, 1 It can be observed that, for every agent i, it is impossible that Fi, and T; are both at least c, since the incurred cost will become larger than 1/e 2e), which is much larger than the payoff she receive. Using the same analysis before, we can conclude that there always exists a deviation from æ.
B The Complexity of Finding Core-Stable Data Exchanges
B.1 Hardness of Determining the Existence of a Core-Stable Data Exchange
Theorem 4. NP-hard to determine the existence of a core-stable data exchange.
Overview of the Reduction. We reduce from the 3SAT problem, which is known to NP- complete. Given a ASA instance, create data exchange instance with two parts, illustrated in Figure 4 distinguished by shallow and dotted curves. The nodes represent the agents, and only agent 31 appears in both areas. The lightly shaded area the left corresponds to the instance discussed, where core-stable exchanges do not exist. In addition, we create a gadget using the input 3S AT instance in the right area. Each agent receives positive payoff only if she simultaneously receives almost all data from every agent who points to her. In addition, we sets a threshold for every agent such that she incurs large cost if the total fraction she shares exceeds the threshold.
Agent 81 receives payoffs from both areas and takes the maximum as her final payoff and serves as variable that determines whether core-stable exchange exists. When the input AT instance is
18

---

U2
83
Sn+1
U2
C2
C
(a) Illustration the directed graph gadget used in Theorem where diamond nodes represent super agents, square nodes represent literal agents, circle nodes represent selection agents and triangle nodes represent clause agents, Clause C1 is in form of C₁ = (vn V...) ). An arrow + represents data share 2i.5 affecting the payoff of agent The graph within the dotted ellipse represents the graph G.
12
Up
A1
81
82
$3
Sn
Sn+1
A2
01
12
Up
C2
C
(b) The data exchange =Y, where truth assignment is e1 false, vq true, Cr true and arrow i + j in gray shadow represents agent sharing one unit data with agent j.
YES instance, then we are able to construct data exchange according to the assignment such that (almost) every agent in the right area receives the maximum payoff. Hence, no agent the right area has an incentive to deviate from the data exchange. However, if the input 3S instance is NO instance, the construction guarantees that no agent in the right area should exchange data with any other agent. Otherwise, the threshold requirement of some agent would be violated, which would lead to large cost and give her an incentive to deviate. Therefore, the data exchange only happens in the left area, which is the instance discussed in the last section, and we know that the core-stable exchange does not exist.
We now present the formal proof for Theorem
Proof. We show a reduction from the 3SAT problem. Given a 3SAT instance with variables U1.... Un and clauses CI...., Cm. we construct a directed graph gadget G = (V, E') (as shown in Fig. 5a and then use it to construct a data exchange instance. For each variable v. we construct two literal vertices Y; and o; and a selection vertex S;. For each clause Cy. we construct clause vertex Cj. The vertices are connected as follows: (i) For each variable
we create two arcs from literal vertex v and U; to s; Meanwhile, we create two ares (s1+1, 0/) and ($1+1, 0z); (ii) Then, we create path from $1 to 8x+1 that goes through all the clause vertices CI..... Cm. (iii) Finally, for each clause C, if literal M/ appears in C,. we construct an are from Cj to Üg. If o; Cj, construct an are from C₁ from C, to in in Fig. [5a Observe that the out-degree of every clause vertex is exactly We now construct data exchange instance follows: Let every vertex of G correspond For simplicity, we use the same notation to denote both the vertices and their corresponding agents. We slightly abuse N to denote the set of normal agents. In addition, we introduce two super agents A₁ and Ag and connect them with the selection agent $1 with bi-directional arcs.
For example, if C, is in form of C, = (v1 V v..)), then we construct are
normal agent.
The payoff function of each agent a is in form of Pa (x) max (pX (z)) p. (æ)). where P. (x) only depends on data shares from normal agents and p (x) only depends the shares
Payoff Function.
19

---

from the two super agents. In particular, (x) O for any normal agent e other than $1. For any super agent A {Ai, A2). pl (z) set to zero. We now proceed to define p (z) and (z))).
The payoff function p (a:) for every normal agent v E V is defined as follows:
For each selection agent s, let T and Feg,s be the fractions of shares received from the agents with ares incident to s. When satl, we set F = F22,s as the share from C.. Define P (x) = 1/e (max(Xv,,se Tegis) - -))+ Hence, the maximum payoff p of a selection agent is 1.
For any other agent v, let p (z) maximum payoff these agents can receive is also 1.
((.E 1/e- (Zu,e - (1 e))+. This implies that the
Next, define P. (a: for the two super agents A2, and the selection agent $1. Fix 7 >> 0 as a constant smaller than e. Consider the counter-example presented in Appendix [A.3] We consider agents A1, A2, and 81 be the three agents 2, and 3 (respectively) in that data exchange instance. Let pá (ar) be the payoff function of any agent a E {A1, A2, 81) from Appendix A.3 scaled by a factor of 7y
Cost Function. and cg (z: are set as zero for any super agent and any normal agent (except for $1).
The cost function is also in the form of (a = (x) + c (z), where cx (x)
The cost function cy (a:) for every normal agent u E V consists of two parts: the first part is a sum of concave functions where each term becomes small constant if Te,u > while the second part is convex function that becomes super large if the total out-shares is larger than a threshold. Formally, we set cy (x) (m.aeE min(1/e- Te.u. 1) + 1/e (n - Te)+. Let T 3 for any clause agent e and T = 1 for any normal agent v. ca (x) is defined similarly. For any agent E {A1, A2, }1 her cost function a (x) is inherited from Appendix A.3) scaled by factor of y.
When the input AT instance is YES instance, we define a data exchange æx according to the assignment as follows: (i) The two super agents share one unit of data with each other; (ii) If a literal 4, (1: or 6;) is assigned true, let her share one unit of data with s; and let 8;+1 share one unit of data with her; (iii) Let selection agent $1 share one unit of data with clause agent Cn and every clause agent shares
unit of data with her adjacent agent; In particular, Cn shares one unit of data with Cn-1. Cn-1 shares one unit of data with CR-2, and so on; (iv) For each clause agent Cy, if a literal É within it is assigned false, then let Cj share one unit of data with the agent corresponding to the negation of L. We present graphical explanation of xx in Figure 5b
Claim 7. If the ASAT instance is YES instance, the data exchange x is a core-stable exchange.
Proof. First, it can be verified that every agent has positive utility in xY. Then prove xx is core-stable by contradiction. Suppose that a deviation x") exists. We first discretize z as follows: for every Zi.j, if æi. utility. In addition, since all the cost functions are monotone, the operation weakly decreases the cost of agent i, which further increases agent i's utility. Thus, the discretization operation does not affect the feasibility of the deviation.
can decrease Zij to zero it does not affect agent j's
After discretization, if U contains some normal agent, we claim there must exist one selection agent still with positive out-shares v Suppose for contradiction, a. If U contains clause agents, there must exist one clause agent in U not receiving any shares in x" Hence, the utility of that clause agent will be non- non-posiiive in = which gives her no incentive to deviate from xY. Otherwise, if & does not contain any clause agent, any literal agent should not be included either, as the payoff of these agents only depends on the clause agents and selection agents. Loss of clause agent makes a literal agent receive significantly less utility than in xY, These imply that U should not contain any normal agent, and this contradicts our assumption. Therefore, there must exist one selection agent with positive shares in U. That means the cost of that selection agent is at least e by the definition of her cost function. Meanwhile, as her maximum payoff is 1, her utility in = cannot exceed her payoff in x which causes contradiction.
selection agents share nothing in
Last, if the coalition does not contain any normal agent, it can also be verified that the two super agents cannot strictly increase their utility simultancously.
20

---

When the input 3T instance is NO instance, we prove the non-existent eeeeexxittene of core-stable exchange by contradiction. For the sake of contradiction, we assume a core-stable exchange x² exists. In fact, we find that, to guarantee core stability, the shares among the normal agents V can only be zero, i.e., si for any + E N.
Claim 8. F.. = 0 for any two distinct normal agents i,j if the AS instance is a NO instance.
Proof. Let U be the set of normal agents who share positively with other normal agents. If U is empty, the claim is proved. Assume that U is nonempty. We next demonstrate that an agent v in U must exist with a zero payoff, which means she has negative utility since she has a positive share which incurs a positive cost. Our discretization operation ensures that every agent in U has an out-share of at least 1 - e, which makes her incur a cost of at least c.
Since <>>> > % it implies p. (x) < and p (æ) should be positive for any U. By the definition of py the fractional data shared on every edge incident to every clause agent or literal agent in U should be larger than e. Similarly, the fractional data shared one of the incident edges of every selection agent in U should also be larger than 1 - 6. Since U is nonempty, by the structure of the directed graph gadget, the following agents should be included in U: (i) every selection agent; (ii) at least one of U, and Ty for any i E [n]] (iii) every clause agent.
By the structure of the graph gadget, it can be observed that the following agents should be included in U: (i) every selection agent: (ii) at least one of U; and üg for any E [ra] (iii) every clause agent. Next, interpret U as an assignment of the input 3SAT instance. If i and 02 are both included, we only keep an arbitrary one. Then we create an assignment as follows: if 02 is included, then U; assigned true. Otherwise, if 0g is included, v is assigned false. Since the 3S instance is a NO instance, no matter how the assignment is given, one clause C2 will be unsatisfied, which means all the literals within it are assigned false. Hence, the negations of all three literals are included in U, and C, should share 1 - unit of data with each of them. Mcanwhile, C, should also share at least - e unit of data with her adjacent clause agent (or selection agent), which makes the sum of fractions on her out-edges to be no less than 4(1 - e). Thus, her incurred cost will be at least 1/e- (4- 4e 3) = 1/e- (1-4e) 4e), which is much larger than her maximum payoff as e a sufficiently small constant. So there must exist one clause agent receiving negative utility in U, and such agent has no incentive to deviate, which leads to a contradiction. Thus, there must exist an agent v in U whose payoff is zero while her cost is positive, but such an agent has a negative utility and has no incentive to deviate, but this leads to contradiction as well. Therefore, U must empty, which concludes the claim.
3)
Based on Claim 8 only data exchanges between and the two super agents Ai and Ag can be positive. However, by the analysis of the counter-example in Appendix [A.3] a deviation always exists no matter how they exchange. Therefore, there is no core-stable data exchange when the 3S is NO instance, which concludes the correctness of the reduction.
B.2
PPAD-Hardness of Finding Core-Stable Exchange under the Sufficient Conditions
In this part, we show that the problem of finding core-stable exchange is PPAD hard for concave payoff functions and convex cost functions, where core streletable exchange is shown to exist in Sec- tion 2.2 It is worth noting that, the hardness result still holds when the size of coalitions is restricted by a fixed constant.
We first introduce the problem of APPROXIMATE FRACTIONAL HYPERGRAPH MATCHING, where we are given a hypergraph = EV, a preference system O (>v)vev and number e E [0. 1]. The goal is to determine whether there exists a fractional matching f E + [0,1] such that Ee eE:(() f(e) S 1 for all V. The matching is stable if there exists a vertex v in e such that
EVeE()): e' f(e') > 1-16- é for every edge e. A stable fractional matching is known to exist even if E is set as zero [FF0]. Finding a stable fractional matching is PPAD-complete when is
set as 1 E/2 [K Theorem 4]. Furthermore, by applying their result to the setting in [C<522). the copD-commpessenss still holds even when each edge has a size of exactly and every vertex is incident to at most three edges.
21

---

Te de
Diese
vertex agents
Te,le
edge agent
intermediate agent
Figure 6: Graphical explanation of the edge gadget for the PPAD-hardness reduction.
B.2.1 Overview of the Reduction
Given hypergraph instance instance as follows. For every hyperedge e, we construct an edge agent (denoted by for simplifi- cation). Meanwhile, we create three vertex agents for the three vertices included in e, denoted by Ve, ui ve Note that if a vertex appears in multiple hyperedges, we do not create separate vertex agents for each occurrence. Instead, we create a unique vertex agent and simply refer to it by different names on different hyperedges. Additionally, we create one intermediate agents i, for every edge, who serve as the bridge facilitating data exchanges between edge agents and vertex agents. For every edge E E, we correspond intermediate agent it to vertex agent uy for t [3]. We present graphical illustration of the edge gadget Fig. (6]
(V; E) and preference system O, we construct the data exchange
Fix e > 0 be a sufficiently small constant such that 10/ 1/4 2 1/220 E and e < 10-3, Let 11/4 H -1/2 and r 3(d + + 1)/c. Next, let us define the payoff and cost functions of the agents in the above data exchange instance.
Payoff Functions. For every vertex agent E V, we introduce a payoff function (x) for every hyperedge including it, and her total payoff is defined as the sum of these payoffs, i.c., (o(x) Eevve L (xr). Consider hyperedge e E including v. Then we define pf (a)) as follows:
(d + H 11) Fig.
if is v's favorite hyperedge, if is v's second preferred hyperedge, if e v's least preferred hyperedge.
(x)))
(d H) Fin Fig.
The payoff function of every intermediate agent ie is Pt, (x) = min (Ze.i. Fot Pogiier Roga..) In addition, the payoff function of the edge agent is defined as pe (xx) = Z4,.e.
Cost Functions. For every vertex agent v. define her cost function using the truncation function. The cost will be pretty large if her total shares with the intermediate agents exceed 1.
(x) rr.
Σ Tella -1
(3)
E:UEE
Meanwhile, the cost function of an intermediate agent ie is defined as G. (x) (1 max (Ii (1 Te.i.- We can check that all the payoff functions are concave and the cost functions are convex. Meanwhile, can be observed that the utility of every agent is equal to zero when the data exchange is O.
Fig,et (fe P of ). The cost function of edge agent is defined as ca(ar)
B.2.2 Mapping from Data Exchange Fractional Hypergraph Matching
Next, we construct a hypergraph mapping from core-stable data exchange æ. Since every agent receives utility of zero in the data exchange 0, any core-stable data exchange must ensure that the utility every agent nonnegative. Otherwise, an agent receiving negative utility would have an incentive to deviate. We then adjust the fractions to ensure that no agent's 's utility decreases. Note that each agent's payoff and cost functions are monotonie with respect to every coordinate of the data exchange. For every intermediate agent ig, since her cost function is defined as the maximum
22

---

of her out-shares ee, Fign oi, m2 we can adjust all the four fractions to be equal to the maximum of them, which weakly increase other agents' utility without increasing her cost. In addition, consider the edge agent and the three vertex agents corresponding to the intermediate agent. the payoff of the intermediate agent is the minimum of the fractions of shares from the four agents, we can adjust the four fractions to be equal to the minimum of them, which weakly increases the utility of other agents without decreasing the payoff of the intermediate agent. As the utility of all agents does not decrease during the above adjustment, the tweaked data exchange still core-stable. In the following proof, we assume that Tig,e = Li,,"! = ii,,,² = ii,,, and Te,i, = Feggie It = Frg.ie for every intermediate agent ée- Denote the former value by (e) and the latter value by (e). We first have the following lemma of the relationship between the two fractions f (e) and f (e) for every hyperedge
Lemma 3. For every hyperedge
E, we have (1 (1-
Proof. First observe that, the utility of the edge agent e given by
Pe(x) (x) f (e) -e) (1
which should be nonnegative as the data exchange is core-stable. This implies that (e) 2 61- (e). In addition, the utility of the intermediate agent is given by
Pie (a: Ci (a:) (e) (1 -11-6 (e).
which is also nonnegative. This implies that (e) 2 (1 -)) ff (e) and concludes the lemma.
Lemma 4. For every vertex E V, we have Eevec ft (e) $ c1+
Proof. Observe that, the utility of every vertex agent v is given by
Po(x)) cx(xx)=
Σ (x) co(ax) S Σ (d ++
(
-
evrE
< 3 (d+
(e)
(c)
(the degree of u is at most 3)
elcEe
which should be nonnegative. As = 3(d + H + 1)/e, then we have Ee:wc (+(e) 11+
Now ready construct the fractional hypergraph matching on that hypergraph. Define the I-c
flow ʃ E > [0, 1] as follows: for every edge E E, we let f(e) = max(f+(())
I+c
which is valid fractional matching by Lemma
B.2.3 From Core-Stability to Stable Matching
Finally, show the fractional matching constructed above is stable fractional matching. For every hyperedge e E E, if f(e)= Z L then the stability constraint is met by every vertex v included the
hyperedge since Eerezze f(e) 2 fle) and e assumed to be < 220 Below we consider the case when f(e) < 1- Itc.
Then we can see that
1+c
max (e), S f(e)
T- <1
Denote the maximum of ft) and (e) by x-- Let define A. = 1 x= This variable is positive since max max(f+(e)) f
< 1. Consider a coalition U consisting of the edge agent e, the intermediate agents ie and the three vertex agents ui v2 va. Define the data exchange x" as s. xx,t + A. for every s, f E U. Observe that the edge agent and the intermediate agent all receive higher utility in deviation.
Claim 9. (x:" > (x)) and us, (x. > Mi, (z))
Proof. For the intermediate agent i.. as all the in-shares (out-shares) are shifted by A, simultaneously. Her payoff increases by 4A, while her cost increases by 4(1 <)A,. Thus, her total payoff increases by 4e Similarly, the payoff of the edge agent e increases by A, while her cost increases by (1 e) Therefore, her total payoff increases by eA..
D
23

---

Since x is core-stable exchange, there must exist an agent in U receiving less utility in æ". By Claim 9 such agent must be one of the three vertex agents. Denote the agent by e for simplicity. Let f(e)), I' (e2) and f(ex) respectively be the flows for e1, 62, 63 respectively being vertex v's most favorite, second favorite, and least favorite edge. Hence, we know f(e)) + f(22) + f(ex) S 1. We now discuss the following three cases according to the ranking of e in vertex e's preference order >..
Case I: is v's favorite edge. In the new data exchange x", we know the maximum fraction is equal to as A. = 1 x². Hence, it holds that = = Ti..o + Ae 2 (1 - =)a= + A. Z (1 -)) (x= + Ae) = 1 1--e e. Meanwhile, since the total out-shares of agent is Ze.t. which is at most and does not exceed the threshold of Equation (3). her incurred cost is zero. Thus, the utility of agent u in æ", (x(x") is at least
uo(x") 2 (1-c) c) (d H +)
On the other hand, we can observe that the utility of agent in exchange x is at most Up (2)) = Pet (x) + (=) + (a:
f +1) (d
-
(ea) H
1 +
$ 1 -
(f(ei) (d+ f(e)) (d+ f(es) H)
1 1
$ 1
(f(e)) -d (d+ 1) f(e)) -d (d+ Hd+
1 c
1 - (f(e)) + H)
Since uo(x)= Uo (x(xx)) it follows that
f(e)) (1 (1-e)² (d+ H) (1- (1-4-09) I+e
2 1 - (d (d+H) 2 102
1+E
In this case, the utility of agent v in data exchange x² is at least (x) > (d+H)-(1-e)) Since ((2)(()(())+ < 1, we have f(e3) S ((e))))_((e))) Thus, the utility of agent v æ at most
Case II: e v's second favorite edge.
(x)) V (e1) (d H +
(f)
1 +
<
(f(e)) (d H (1+++)))+())((( (d+ + f(es) H)
1 c
1 +t
< 1 -
(f(e)) (d+ H +1 (
f(e)) (d+ H) + (1- f(e) - f(ez)) H
1 1t
1-c ((f(e)) + f(2)) (d+1) + H)
For this reason, we further derive that
d
(1 (1- (1 (1 (1- (1 c) -H
f(es) + f(22) > I+I 1 3c) 3c H 2 7/111
1 1+6
2 (1 - 1/)
Case III: e is u's least favorite edge. In this case, we know the utility of agent w in x least Mor (xx > H (1 -ee), +). Meanwhile, the utility of agent iú in x is at most
ux(x) S (f + f (e2) (es)) (d+
+1)
< 1+e (f(e)) + f(e2) + f(aa)) (d+ H + 1),
which further implies that
(1 c)-
H
((a) + ((2)) + f(es)
2 (1 (1-3e) (1 1/4)211 > 46 1/4,
1 1+ d+ +
We can observe that, in all three cases, the total flow on edges where v has weakly better preference than e is at least 1 10c 1/1, which is larger than - 1/220 by the setting of e, which indicates that the hypergraph matching is stable.
24

---

C Pivoting Algorithm
C.1 Complexity of Construction of Coalition Matrix
Claim 5. Given coalition S S [n]] and utility profile (2% iiss, can compute in polynomial time either a data exchange a such that uz(2) 2 vi for all E S or return that no data exchange satisfies uz(2) 2 U/ for all i S.
Proof Sketch. For each agent E S, we create a new utility function uf(() that caps the original utility function at oz (x(x)) min(u;( wi Next, consider the following concave program.
Ed((2) iES
max
subject to 0 0 Fuf 11, ViJjES
Let K. = {æ : æ., [0. 1]. Ji E 5} be the feasible domain. We then apply the Ellipsoid method to find an approximate solution with distance of at most to the optimal solution. By [Vis2] Theorem 13.1]. it suffices to find a first-order oracle for Eies (x))). As v.()) the minimum of (.(-) and v.. its supergradient can be answered in (1) time using [Sho Theorem 1.13].
Denote the solution found by the Ellipsoid method by a and the optimal solution by x". Then
En (x)xx) 2 Σ u' v'(")) -. iES
iES
We output æ if Eies (x) 2
En and NO otherwise. Below, demonstrate the desirable
property of the output answer. If a data exchange x: is returned, then Eies (x) 2 > Eies 1 c.
Since ui (z) < holds for every E S, then (x) 2 U; which means u, (xx)) 2 V;
If
the output NO, we prove by contradiction that no data exchange can meet (x 2 U for every agent i. If such data exchange æ exists, then the optimal solution is at least Eies B. Hence, as the
approximation ratio is set as e, the found solution will have an objective value of at least Σ
which violates the assumption that the output answer NO. Therefore, the claim is proved. O
C.2 Hardness of Verifying Core-Stability
Theorem 10. It is comp-complete to verify whether exchange is core- when the payoff functions are linear and the cost functions are convex.
V1
U2
Un
Un
$2
$3
yt
8n+ I
U1
02
0 1
On
C..
C2
C1
Figure 7: Construction of the graph gadget for the reduction from 3SAT to VERIFY CORE-STABILTY. The blue round nodes represent the selection vertices, the red square nodes represent the variable vertices, and the orange triangle nodes represent the clause vertices. Each clause agent has an outgoing edge to the negation of each literal it contains. For example, if C, (v1 V... ), there will be a are (Cn, 01) constructed.
25

---

Proof. The problem VERIFY exchange x' and a coalition that can deviate to, can verified in polynomial time whether blocks at. Next, we show the coNP- by reducing from the AS problem. Given a ASAT problem instance with m clauses C = (Ci) and n variables V = (1x) we construct a data exchange instance DD as follows.
is in CoNP since once we are given another data
First, we construct graph gadget and use it to construct data exchange instance then. For each variable vi we construct two literal vertices U; and U; and a selection vertex 8;. For each clause Cj. we construct a vertex Cj. Then we connect these vertices as follows (see Figure : For each variable 24 we create two ares from literal vertex 2 and literal vertex 0, to 8;. Meanwhile, we create ares (st+1, v4) and (s++1, By). Then, we create path from $1 to Sx+1 that goes through all the clause vertices Ca.... CT. Moreover, for each clause Cj. if variable V2 occurs positively within Cj. then we construct an are from Cj to f;z- Else, if o occurs negatively within C, we construct an are from Cj to ni. For example, in Figure 7 if C, is in form of Cn = (v1 V ...),, then we construct an are from Cn to U1. Hence, we observe that, for each clause vertex, its out-degree is exactly 4 and its in-degree is 1.
Now, we construct the data exchange instance D. Denote the set of all vertices by V and the out- degree (in-degree) of each vertex by deut (d."). The data exchange instance involves two types of agents: (1) The first one generous agent, denoted by gi (2) The second is a set of agents { {ax vev, where V is the set of all vertices in the graph gadget. We call these "normal" agents. In what follows, when referring the agents, we will alternatively use the label of the corresponding graph vertex.
The payoff functions and cost functions are constructed as follows: The generous agent receives no payoff from the normal agents and incurs no cost when sharing data. Her utility is always zero in any data exchange. For each normal agent, we define her payoff function as follows.
Payoff Functions. Fix a small constant such that < 6 < 1/4. Define the function pr( for each normal agent as the sum of payoffs from the following two sources:
Payoff from the generous agent: For every selection vertex i = 8j for j E [nx and every clause vertex Cj for j E [n], we define pf (a) = (1 6) Fg... For every literal variable we let (x() = (di c) F.
Payoff from other normal agents: mentioned, the generous agent gets no payoff from the shares of these normal agents. For each normal agent i E V, we define a. (a) = E Lja.- That means, for each normal agent pi, her payoff from V is equal to the sum of the fraction of shares from agents that are adjacent to her in the graph gadget.
Cost Functions. Next, we define the cost functions for each agent. The cost function of the generous agent g is defined as the constant zero. The cost functions of the normal agents are given as follows:
Selection/Litera agent
cxxx)=
Σ jEV Fi.j -1) 1)+
Clause agent
cx)))
(E, jEV Fts 3)
where j is a sufficiently small constant smaller than 1 4c. The idea behind the construction is that each normal agent will incur large cost if the total fraction of her shares with other agents is larger than a threshold.
We construct the two oracles U and Vu as follows: We answer U(i x) as the utility ps (<()) (a( as constructed above, which takes constant time since the out-degree of every vertex is bounded. Additionally, as every utility function can be rewritten the maximum of O(1) linear functions, can figure out the supergradient Vu, ()) in (()) time.
Now we show that deciding whether the following data exchange x is a-core-stable is equivalent to deciding whether the input AT instance is satisfiable, where
{
if g. otherwise.
0 = (I11) where Fi.jj
26

---

Note that the generous agent is sharing her entire data with every normal agent, while the fractions of all other shares are set to zero. Hence, in x,, the utility of the generous agent is equal to zero, i.e., uy(x²) = O. In addition, every normal agent only gets data from the generous agent. Each selection agent or each clause agent receives a utility of 1 6 while each literal agent receives ux(==)= = d
Next, we show a YES to NO mapping and NO to YES mapping. Let us first show the former one. As the input AS instance is a YES instance, there exists truth assignment such that each clause is satisfied. We then define deviation (U, x²) containing all the literal agents assigned true, all selection agents, and all clause agents as follows. If a variable 0ú is assigned as true, then we let Fe,,e; and Te..s, O. Meanwhile, we let 8;+1 share 1 to 2s and 0 to 82 for every E [n]. If a variable is assigned as false, then we define the shares symmetrically. Let selection agent $1 share one unit of data with clause agent Cn. and every clause agent shares one unit of data with her adjacent agent. In particular, Cn shares one unit of data with Cn-1. Cn-1 shares one unit of data with 22 and so on, In addition, for each clause agent, Cj. for each literal & it contains, if the literal is assigned as false, then we let C share 1 unit of data with the agent corresponding to the negation of l. For literal agents not assigned true in the assignment, we just throw them away and only include the other agents in U.
Proposition 2. The deviation (U, x blocks the original exchange x..
Proof. As the input 3SAT instance is YES instance, know that each clause is satisfied. Hence, for each clause agent, at least one literal of it is assigned true. So, the total fractions of shares of the clause agent are most (3 1) + 1 = 3, which is more than the threshold of the cost function. Hence, her cost will still be equal to zero. In addition, as she also receives one unit of data from the adjacent agent, her utility will be equal to 1.
For each literal agent e é By or ūy included in U, we know 83+1 shares 1 unit of data to her, and any clause agent containing its negation also shares one unit of data to her. Thus, her total utility will be equal to d:". Also, as she just shares one unit of data with the selection agent, it does not exceed the threshold of the cost function. Thus, her utility also more than her old utility d:" -.
Finally, we know each selection agent also receives an entire dataset from one of the adjacent literal agents and shares one unit of data with a literal agent. Hence, her utility is equal to 1 1, which is also larger than her old utility in x (which is ---]) e).
Now, we prove the remaining part of the reduction - the NO to YES mapping. If the input AT instance is NO instance, we now prove the data exchange is core-stable by contradiction. Suppose there exists possible deviation (U, x²) from x." First, as the generous agent always has the utility of zero, she does not have the incentive to deviate. Hence, U must be a subset of V.
Next, we demonstrate that when U is a subset of V, it cannot guarantee that every agent in U receives a higher utility than in æ². If U includes one selection agent (denoted by sj without loss of generality), as she has the incentive to deviate, she should get more than 1 - e in the data exchange x". Hence, one of By and ūj must be included in U as c >> O. Similarly, 85+1 should also be included in U, and continuing this process, we can eventually conclude that all selection agents and clause agents should be included in U. In addition, at least one of the two literal agents V; and G; included for every i E [n). We arbitrarily choose one from each pair, and next construct an assignment yp for the input AT AT instance as follows. If 0; included, then we assign the variable o; as false, (P(1;) = false. Otherwise, we assign it as true, (v()))) = true. For every included literal agent, her utility in the old data exchange x0 is d - e. Hence, as she has the incentive to deviate, she has received at least a 1 1- fraction from every clause agent adjacent to her. As the input 3SAT instance is NO instance, there must exist a clause C, where all the literals are assigned false. Hence, all three literal agents corresponding to three literals within C, should be included in U, and the clause agent C2 should share a fraction of at least - e with them. Therefore, the utility of the clause agent would be at most 1 - 1//-- (4 (1 - - 3)+ 1 1--1/ 1/p-- (1 - 4c) < 0 as μ < 1 1-4c 4e and 0. This implies the utility of that clause agent is smaller than in the original data exchange x and causes the contradiction.
Therefore, when the input AT instance is NO instance, we can conclude that the exchange x! is core-stable, which concludes the coNP-hardness of determining whether a. is core-stable in the constructed data exchange instance.
D
27

---

C.3 Scarf's Lemma
In the main text of our paper, we show the data exchange game is balanced and then conclude the existence of core-stable data exchange. Next, show that approximate core-stable data exchange can be constructed using the coalition matrix and the solution of Scarf's Lemma.
Lemma (Scarf's Lemma). Let n < m and B E IR R=xm such that the first n columns of B form an identical matrix. Let b non-negative vector in RS such that the set {x B X b} is bounded. Let C be n x matrix such that Ci S Ci,k S Cij whenever i, j S m, # j and k. > n. Then there exists a subset O S [m]] with size of n such that
b for some ô Rgo such that ōj 0 for & O, and
* For every & E [m], there exists i E [m] such that Ci S Gig for all j O.
Note that since we discretize the utility space in the construction of the coalition matrix, we are already away from possible utility vector. Further, Claim 5 gives whether a particular utility vector is possible up to an e' error. Therefore, we have all possible utility vectors up to (e + error. By setting é' e, we have the following proposition.
Proposition 3. For any utility vector v that is attainable by a coalition S, there exists a utility vector of the columns of U such that u, 2 2 for any E S.
Based on that, we can construct a core-stable data exchange by applying Scarf's Lemma. Lemma 6. For any > O, there exists a e-core-stable data exchange when the payoff functions are concave and the cost functions are convex.
Proof. First construct the coalition matrix C and utility matrix U using parameter e/2 as described in Section 4.1 To meet the preconditions of Scarf's Lemma, we slightly modify C and U by considering all the singleton coalitions (where only one agent forms coalition). Therefore, C is then changed to an augmented matrix with an identity matrix in the left part while a zero matrix is added to the left of U. Similarly, add slightly different M to the blanks in the first n columns of U like discussed before.
The two matrices then meet the preconditions of Scarf's lemma. We next construct data exchange according to the solution (O,5) as follows: 8; xx' where x' is the data exchange archiving the i-th utility column of U. According to the second guarantee of Scarf's s Lemma and the concavity of the utility function, the deviation corresponding to every column U cannot block æ. Therefore, we can then conclude that is e-core-stable.
by Proposition 3
C.4 Pivoting Algorithm
Next, we show the pseudo-codes of the pivoting algorithm for finding an e-core-stable exchange in Algorithm 2 which mainly follows the constructive proof Scarf's Lemma [Sca67]. line we first construct the two matrices: coalition matrix C and utility matrix U with the input approximation parameter e. Then we apply the pivoting algorithm to find a solution Scarf's Lemma, which further induces e-core-stable data exchange. For completeness, we first introduce the concepts of cardinal basis and ordinal basis. Denote the size of the two matrices by n X m, where m is the number of possible coalitions.
Definition 5 (Cardinal basis). Let b Consider the polytope p (C b). A set of columns B is a cardinal basis for bC, if (i) [B| = n and; (ii) the submatrix induced by B has a full rank.
Definition 6 (Ordinal basis). A subset of columns O is called ordinal basis for the utility matrix U if (i) [O| = n and; (ii) for every column j E [m], there exists a row E [m]] such that U. 2 U..- where U min,eo Ut.-
During PA, it respectively maintains two bases B and O for each of the two matrices C and U. These bases evolve until they are equal. To get to this, we will pivot to new basis in each matrix. A pivot step in the coalition matrix C is defined like the usual linear programming pivoting step. A pivoting step in the utility matrix U is called an ordinal pivot step.
28

---

Algorithm 2: Pivoting algorithm for finding e-core-stable exchange
Input: Payoff functions {i cost functions {ci); and the parameter >
Construct C and U with parameter > 0, payoff functions {u+(-)} and cost functions {c(());
3 Update C - (4n. C) and U +- (0 U) and then fill the blanks U with slightly different sufficiently large value M. Let the size of C and U be X
Let B + (1,2....,,7) and + (l,...,77 ,. jegmaa U1.5
5 while B do do Cardinal Pivot
Let j be the column in O \ B, Cg be the submatrix induced by B and by be the column indexed by j:
Let x and respectively be the solution of the linear equations CB x = 1 and Cp -y- = by: Li:
Let < argmin J:g, >0 y
Update B by B B B-B\Guu11
// update the cardinal basis
11
if = O then
L break;
> Ordinal Pivot
14
Let je be the column in 0 \ B be pivoted out;
15
Let is be the row minimizer of column jr, i.e. Uieci = argmin Joo
Let jr argmin (jt)) (
Let i, be the row minimizer of column Jr, ie., Uinjr argmin
Let K < { [m]] O U,, U ooli for all i i,);
19
j" f- argmax Cz,
Update the ordinal basis by 0 ( \ {ic); // update the ordinal basis
Find the solution å of the linear equation Cn ô = 1;
22 Let + Eigmm) 5; xx with æt corresponding the data exchange achieving utility vector u;
return the data exchange ar;
Definition 7 (Cardinal Pivot). For the coalition matrix C, given a basis B = (Ji,.. Jn) for the its columns, we can take any column & and remove one of the columns from B to get new basis using standard linear algebra. Such a movement is called cardinal pivor.
matrix consisting
Definition 8 (Ordinal Pivot). For the utility matrix U, given a hasis O = (Ji,..., In) consisting of columns of the matrix, we can take any column in the basis and replace it with unique column from outside the basis. Such step is called an ordinal pivot step.
Once PA terminates, we get an identical basis B, which both cardinal basis and ordinal basis. Then we solve the linear equation C3 5 and get the weights for each column. Afterward, in Line [2] we calculate the weighted data exchange x Σ, 8 x with x' the data exchange corresponding to the i-th column. The data exchange is guaranteed to be e-core-stable by Lemma
29

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justifiicton right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]", ", it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: We highlight our contribution at the end of the introduction and discuss the scope in the abstract.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
30

---

Justification: We leave some future directions of our work in the related work section, which reflect some limitations of our work.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-ten system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We provide all the proofs for the results. Some of them are deferred to the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results. the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We give detailed description of the parameter setting of the experiments in Section 4.
31

---

Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We include all the codes in the Supplementary files, including codes and graph data.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ ctiips.cc/puulic/guuii
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
32

---

At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We discuss the details of the experimental setup and the used dataset in Section
4.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We duplicate each experiment twenty times and report the mean of the statistics of each metric, as described in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We describe the computer resources in Section 4.
Guidelines:
33

---

The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: stcttps:/nneripsst http://///eeapp.ccppppcleeee/e//
Answer: [Yes]
Justification:
Our research totally complies with the NeurlPS code of ethic.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We give the motivation of our work and the strengths of our mechanism in the introduction section.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications,
authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
34

---

Answer: [NA]
Justification:
Our paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
The used dataset and Python library are all correctly cited in Section 4.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
35

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification:
The paper does not use LLM in any way.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our L.MM policy / ce. /c////aaneeeeccc//222////11 for what should or should be described.
36


Reviews:
[{"review_id": "kUz3qqttQo", "reviewer": "Reviewer_5sUM", "summary": "The paper investigates the existence and computational complexity of core-stable data exchanges in collaborative data economies. It models data exchange as a cooperative game where agents balance payoffs from acquired data against sharing costs, aiming to prevent coalitions from deviating to more favorable local exchanges. The study establishes conditions for core-stability, analyzes its computational hardness, and show the practical performance of the pivoting algorithm.", "questions": "1. Is it possible to involve monetary transfer in the setting? Either between agents or involving enconomic issue related to the platform of data exchange (for example charging a small fraction of payoffs for each exchange).\n2. Please explain more to justify the assumption of the convex cost functions.", "limitations": "NA", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. It is novel to model the data exchange problem through cooperative game setting. The core stability is a good solution concept to evaluating the feasibility of data exchange platform.\n2. Concrete theoretical results on the existence and complexity.\n\nWeaknesses:\n1. The assumptions (concave payoffs, convex costs) may not hold in real data exchange scenario. To be specific, for the concave payoffs, it is common that the payoff function w.r.t. acquired data is a step function, just as Example 1 illustrates. Intuitively, for instance, a learning model may not learn anything befere the size of training data is beyond some threshold. Notice that the author has provided several previous works on ML models with concave payoffs, I would not regard this as a big issue. As for the convexity of cost function, I cannot understand the illustration provided in Sec 1.1. Why do one share records in ascending order of costs involved for collecting the records? A direct way of sharing records is just sharing them in the order that they are collected, while it depends that collocting records requires increasing or decreasing marginal costs?", "was_revised": true, "final_justification": "The author addressed my concern on the assumptions and questions on settings.", "rebuttal": "We thank the reviewer for the insightful comments. Here, we will address the questions and concerns respectively as follows. \n\n> **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).\n\n**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.\n\n* **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.\n* **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.\n\nThat 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.\n\nWe 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, \n\n1. **Can we design a payment rule such that a core-stable data exchange can be computed in polynomial time?**\n2. **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?\n\nIf required, we can add this discussion to the next version of our paper.\n\n\n>**Question 2:** Please explain more to justify the assumption of the convex cost functions. \n\n**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:\n\n* **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.\n* **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.\n\n\n\nFurther, 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.\n\nWe 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. \n\n[Li and Raghunathan '14]:Pricing and disseminating customer data with privacy awareness. Decision support systems, 2014.\n\n[Laudon '96]: Markets and privacy. Communications of the ACM, 1996.\n\n[Murhekar et al. '23]: Incentives in Federated Learning: Equilibria, Dynamics, and Mechanisms for Welfare Maximization, NeurIPS 2023\n\n[Murhekar et al. '25]: You Get What You Give: Reciprocally Fair Federated Learning, ICML 2025\n\n[Karimireddy et al. '22]: Mechanisms that Incentivize Data Sharing in Federated Learning, In Workshop on Federated Learning NeurIPS 2022."}, {"review_id": "FCyJubcdHn", "reviewer": "Reviewer_XfeZ", "summary": "Data exchanges consider the agents sharing (not selling) data in a manner that is beneficial to all. Agents have utility in receiving data from others and cost in sharing their own data. This works studies the problem of finding core-stable solutions: one which is individually rational for all parties and another allocation does not that that all agents strictly prefer. They show that a core-stable solution exists if the payoff is concave and the cost convex, with counterexamples possible if either does not hold. Under an oracle model, it is shown that it is NP-Hard to determine if a core-stable allocation exists; under the sufficient stated conditions where such a solution does exist, it is PPAD to compute it. That said, a more practical algorithm is proposed to find epsilon-core stable allocations using a pivoting algorithm.", "questions": "See above.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "I found the paper to be very well written and clearly exposited. The technical model is clean and well justified and the concept of core-stability is natural in this setting. Further, the technical results are fairly complete insofar as a theory paper goes. \n\nWhile 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 desiderata.\n\nIn 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 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.", "was_revised": true, "final_justification": "The authors provided more context on the conceptual contributions of the work.", "rebuttal": "We thank the reviewer for the insightful comments. Here, we will address the questions and concerns respectively as follows. \n\n> **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.\n\n**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. \n\nIn 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.\nConceptually, 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.\n\n> **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.\n\n**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. \n\n\"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\nvalue of data remains locked.\"-- [Castro Fernandez. '23]\n\nData 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).\n\n\nIncorporating 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. \n\n\n[Murhekar et al. '23]: Incentives in Federated Learning: Equilibria, Dynamics, and Mechanisms for Welfare Maximization, NeurIPS 2023\n\n[Murhekar et al. '25]: You Get What You Give: Reciprocally Fair Federated Learning, ICML 2025\n\n[Karimireddy et al. '22]: Mechanisms that Incentivize Data Sharing in Federated Learning, In Workshop on Federated Learning NeurIPS 2022.\n\n[Castro Fernandez. '23] Data-Sharing Markets: Model, Protocol, and Algorithms to Incentivize the Formation of Data-Sharing Consortia, In *SIGMOD'23*"}, {"review_id": "MZQYdbO1K4", "reviewer": "Reviewer_f3Pk", "summary": "The article considers a setting where agents can share data with one another in a federated manner, obtaining a payoff from the data they receive while incurring a cost for sharing their own. Data sharing is modeled as continuous, allowing for varying levels between no sharing and full sharing.\n\nThe authors focus on core-stable exchanges—vectors of exchange levels in which no coalition of agents can deviate and strictly improve the payoffs of all its members. By modeling the setting as a cooperative game, the authors study the existence and computational complexity of such exchanges, establishing sufficient conditions for their existence as well as hardness results for their computation.\n\nTo address these challenges, the authors propose an approximation scheme based on the Pivoting Algorithm, which is then empirically evaluated on a real-world dataset.", "questions": "Regarding the set of core-stable solutions, could you please comment on the following points:\n1. Is the core-stable solution unique in general?\n2. Which particular solution is approximated by the Pivoting Algorithm?\n3. 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?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- The article is well written.\n- The proposed model is interesting and relevant.\n- The paper is theoretically strong.\n- The results are quite complete, including existence proofs, computational hardness results, and the proposal of an approximation scheme for the desired solution.\n\nWeaknesses\n- The empirical evaluation is limited, as the Pivoting Algorithm is tested on only one dataset and is not compared against any other approximation scheme.", "was_revised": true, "final_justification": "The paper is good. The setting is interesting and the article is quite rigorous. The authors replied to all my concerns. I've decided to keep my good score.", "rebuttal": "We thank the reviewer for the insightful comments. Here, we will address the questions and concerns respectively as follows. \n\n\n> **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.\n\nResponse: 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:\n\nTime and size for the coalition matrix\n\n\n\n| n | 10 | 20 | 30 | 40 | 50 | 60 | 70 | 80 |\n| -------- | -------- | -------- |-------- |-------- |-------- |-------- |-------- |-------- |\n| Time (sec) |0.84| 1.56 |10.25 |15.78 | 22.81 | 61.15 | 71.18 |123.61|\n| Size | 1 | 10 |161 |239 |424 |913 | 1003 | 1366\n\n\n\nTime and iterations of the pivoting algorithm\n\n|n | 10 | 20 | 30 | 40 | 50 | 60 | 70 | 80 |\n| -------- | -------- | -------- |-------- |-------- |-------- |-------- |-------- |-------- |\n|Time (sec) | 0.01 | 0.03 | 0.04 | 3.38 | 9.24 | 79.33 |165.49 |205.14|\n|Iter | 1 | 12 |20 |156 |241 | 797 |1042 | 1154\n\n\n[DataSF] List-of-Streets-and-Intersections, Geographic-Locations-and-Boundaries, San Francisco Open Data.\n\n\n> **Question 1:** Is the core-stable solution unique in general?\n\n\n**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. \n\n> **Question 2:** Which particular solution is approximated by the Pivoting Algorithm?\n\n**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.\n \n\n> **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?\n\n**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. \n\nHowever, 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."}, {"review_id": "oTd3PgAskL", "reviewer": "Reviewer_TXg6", "summary": "The paper considers a simple data-exchange scenario, in which every agent gains a payoff $p_i$ from getting data from another agent and looses a cost $c_i$ of sharing its own data, i.e. $u_i(x) = p_i(x_{-i}) -c_i(x_i)$, where $x_{-i}$ is the data bundle that $i$ receives from the exchange and $x_i$ is the one that $i$ gives. The authors study the classical notion of core stability in this context and show, in particular, that a core-stable data exchange always exists when the payoffs are concave and the costs convex. In the other cases, core-stable exchanges are not guaranteed to exist. They also show NP-hardness of assessing existence (when the sufficient conditions are not met) and PPAD-completeness of the problem of finding core-stable exchanges, even constraining the coalition size and under the sufficient conditions for existence and how one can use a pivoting algorithm (PA) to achieve approximate core stability. Lastly, they assess PA’s performance via experiments.", "questions": "Are there alternative concepts to core stability that are interesting to consider in this context?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Positive points**:\nThe model explained in the paper is quite simple and general, as well as the conditions proved to be sufficient for the existence of a core-stable data exchange. The authors discuss how these conditions often hold in practice, which is a good point to state. I also appreciate the fact that, after showing hardness results, they propose a solution which seems to be usable in practice to approximate core-stability.\n\n**Negative points**:\nIn 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.\n\n**Minor comments**:\nSupergradident -> Supergradient on lines 92/93", "was_revised": true, "final_justification": "I slightly raused my score based on the rebuttal phase. The authors addressed some of my concerns (especially the ones on the complexity results), in a convincing way.", "rebuttal": "We thank the reviewer for the insightful comments. Here, we will address the questions and concerns respectively as follows. \n\n> **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.\n\n**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.\n1. 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),\n2.  The top trading cycle algorithm (which runs in polynomial time) determines a core-stable solution in housing allocation, \n3.   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).\n\nLastly, 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.\n\n> **Question:** Are there alternative concepts to core stability that are interesting to consider in this context?\n\n**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. \n\n[Chaudhury et al'22] Fairness in Federated Learning via Core-Stability. In NeurIPS'22.\n\n[Fain et al. '18] Fair Allocation of Indivisible Public Goods. In EC'18"}]

Author rebuttal:

Meta-review: The submitted paper studies the stability of a data exchange protocol in which agents need to balance the benefits of acquiring data against the costs of sharing their own. Building on the concept of core-stability from cooperative game theory, the authors show that core-stable exchanges exist when agents have concave payoff functions and convex cost functions, common in domains like PAC learning. Relaxing these conditions can lead to instability. They also prove that finding a core-stable exchange is PPAD-hard. Furthermore, the authors provide a pivoting algorithm to find core-stable exchanges.

**Strengths**
* Theoretical contributions: The authors provide results on the existence of core-stable solutions under sensible conditions (real-world applicability is debateable) and demonstrate the computational hardness of determining such solutions.
* Practical relevance: The presented pivoting algorithm is a practical approach to approximate core-stable solutions, and its performance is evaluated on real-world datasets.
* Clarity and completeness: The paper is well-written, with a clear exposition of the model, theoretical results, and empirical evaluation.

**Weaknesses**
* Assumptions on payoffs and costs: The assumptions of concave payoffs and convex costs, while justified, may not hold in real-world data exchange scenarios. The authors provided detailed justifications in the rebuttal and are encouraged to include those in the revised version of the paper.
* Empirical evaluation: The empirical evaluation is limited, as the pivoting algorithm is tested on only two datasets and is not compared against other approximation schemes. A comparison with other approximation schemes would strengthen the paper.
* Overlap with prior work: One reviewer noted some overlap with [ACGM, 2024], which also studies core-stable data exchanges (they consider a special case of the submitted paper). The authors clarified the distinctions (e.g., incorporation of costs and non-monotonic utilities) but a more detailed discussion of related work would strengthen the paper.
* Theoretical novelty: One reviewer found some of the theoretical contributions somewhat incremental when viewed in the context of cooperative game theory but the authors elaborated in their rebuttal on the value of their results and how they add to existing ones. They should include this discussion in their updated paper.

**Discussion and rebuttal summary**
The authors actively engaged with the reviewers during the rebuttal phase and addressed all concerns in detail, resulting in an improved recommendation by two reviewers. The authors made an unanimous acceptance recommendation for significant contributions to the study of core-stable data exchanges, with a arguably stylized but still relevant model, rigorous theoretical results, and a practical algorithm for approximating solutions. While there are some limitations, the authors have addressed these concerns convincingly during the rebuttal phase. Hence I am following the reviewers’ recommendations and suggest the acceptance of the paper.
Decision: Accept (poster)