Research map / Multi-agent systems and games / Games and equilibria
On the Existence and Complexity of Core-Stable Data Exchanges
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies core-stable data exchanges among agents with concave payoffs and convex costs, proving existence via balancedness (Scarf), PPAD-hardness and NP-hardness results, and a pivoting algorithm validated empirically on a road-map mean-estimation task.
Problem
Whether core-stable data exchanges exist and how hard they are to compute when agents trade data subject to sharing costs, with payoff from acquired data and cost of shared data.
Approach
Models data exchange as an n-person non-transferable-utility game, shows it is balanced under concave payoffs and convex costs (hence a core exists), and derives a Scarf-based pivoting algorithm; hardness is shown by reduction from approximate fractional hypergraph matching.
Key results
- Pivoting algorithm finds a 0.1-core-stable exchange; with n=27 agents, the average runtime of pivoting is up to 38.37 seconds and iterations grow modestly (avg 238.3, max 1434).
- Core-stable exchanges always exist under concave payoffs and convex costs (balanced game argument).
- Finding a core-stable exchange is PPAD-hard even when blocking coalitions are restricted to constant size; deciding existence in general instances is NP-hard.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Require concave payoff functions and convex cost functions | Data exchange economy · Core-stable data exchange existence | existence | Helped |
| Relax payoff concavity while retaining the other sufficient condition (ablation) | Data exchange economy · Core-stable data exchange existence | existence | Hurt |
| Relax cost convexity while retaining the other sufficient condition (ablation) | Data exchange economy · Core-stable data exchange existence | existence | Hurt |
| Increase the number of agents from 3 to 27 | Pivoting algorithm · Road-map simulation | iterations: 238.3 iterations; up to 1434 | Hurt |
| Use the pivoting algorithm to compute a 0.1-core-stable exchange with coalition size fixed to 3 | Data exchange economy · Road-map simulation, n=3–27 | mean pivoting runtime (seconds): 0.001 seconds for n=3 to 38.37 seconds for n=27; average 7.36 seconds | Mixed |
| Use pivoting after constructing the coalition matrix | Pivoting algorithm · Road-map simulation, n=27 | runtime (seconds): 9,821.54 seconds; 118.08 seconds | Helped |
Surprising findings
- Core-stable exchanges may fail to exist even with only three agents when concavity or convexity assumptions are relaxed.
- Verifying core-stability is coNP-complete for linear payoffs and convex costs.
Limitations
- Worst-case pivoting steps are not polynomially bounded; hardness results mean no efficient general algorithm is expected.
- Model assumes no externalities and shared data is not redistributed; empirical study uses one synthetic setup on a road map.
Experimental setup
Datasets: road map dataset (4.4K nodes, 9.6K edges)
Metrics: number of coalitions formed number of concave optimization calls runtime of coalition matrix construction and pivoting pivoting iterations
Builds on: Scarf's theorem fractional hypergraph matching PPAD-hardness Bondareva-Shapley theorem
Closest papers by meaning
- Fairness in Federated Learning via Core-Stability (NeurIPS 2022 · similarity 0.87)
- You Get What You Give: Reciprocally Fair Federated Learning (ICML 2025 · similarity 0.86)
- FedCross: Intertemporal Federated Learning Under Evolutionary Games (AAAI 2025 · similarity 0.84)
- A Cramér–von Mises Approach to Incentivizing Truthful Data Sharing (NeurIPS 2025 · similarity 0.84)
- Cooperative Bargaining Games Without Utilities: Mediated Solutions from Direction Oracles (NeurIPS 2025 · similarity 0.84)
- Fair Federated Learning via the Proportional Veto Core (ICML 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.