{"id":"442256b1-c0c2-4f47-a01e-6bd4010995fd","arxiv_id":"2412.01968","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Defines reciprocal fair and core-stable data exchanges, proves exact existence for monotone continuous utilities, and places approximate computation in the complexity class CLS for submodular settings.","lead":"An algorithm-theory paper defines a no-money data exchange economy and proves fair and stable exchanges always exist for continuous preferences, with complexity results for approximate solutions. It matters for hospitals, universities, and other non-profits that want to share data to improve machine learning without selling it.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4's key bound δ|Δ_j−Δ_i|≤1 is false, so the fixed-point map g is not proved to map Z into Z and the existence proof fails at an earlier step than the boundary issue.","rationale":"The reader's CONDITIONAL verdict is appropriate, and I agree that the existence proof needs repair. However, the most load-bearing defect is not the β_ij(z*)=0 boundary case, which appears repairable via a short 2-cycle argument, but the false normalization bound in Lemma 4. Without δ·|Δ_j−Δ_i|≤1, the function g is not shown to map the convex polytope Z to itself, so Brouwer's theorem cannot even be invoked. The counterexample above satisfies every stated assumption of Theorem 3, so the flaw is concrete and not merely a missing edge case. The paper's main conceptual contribution likely survives: choosing δ small enough, e.g., inversely polynomial in n and the utility range, would restore Lemma 4, and Claim 3's constants can be adjusted. But the manuscript as written contains a false lemma in the core proof. The continuity-of-shares overstatement and the fixed-point boundary gap are additional valid concerns, and all three support CONDITIONAL rather than ACCEPT.","tokens_in":38339,"tokens_out":31263,"duration_ms":506638,"concrete_test":"Evaluate Lemma 4 on the 3-agent instance u_1≡0, u_2(x)=x_{12}, u_3(x)=x_{13}, ψ_{12}=u_2, ψ_{13}=u_3, and all other shares 0, at a point z∈Z with z_{12}=z_{13}=M and all other off-diagonal z entries also M. Compute Δ_1, Δ_2, and δ; the asserted inequality δ|Δ_1−Δ_2|≤1 fails by a factor of about n. Then test the proposed repair: replace δ by 1/(n·max_i u_i(1)) and re-derive Lemma 4, checking that the lower bound δ≥1/(nL) and the ε-dependence in the proof of Claim 3 still hold with the same or slightly adjusted polynomial powers.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 3.2 defines δ = 1/max_i u_i(1) and Lemma 4 asserts δ·|Δ_j(f(z))−Δ_i(f(z))|≤1, using this to guarantee g_ij(z)∈Z and hence g(z)∈Z. The bound is false under the paper's own axioms. Since ψ_ij∈[0,1] and efficiency only forces Σ_i ψ_ij = u_j∈[0,1] per column, an agent can contribute close to 1 to each of the other n−1 agents while receiving zero utility, giving surpluses differing by up to n. Concrete n=3 instance: u_1≡0, u_2(x)=x_{12}, u_3(x)=x_{13}, ψ_{12}=u_2, ψ_{13}=u_3, all other ψ=0. These are continuous, monotone, normalized, and efficient share functions. At any z∈Z with x_{12},x_{13} close to 1 and the remaining z entries set to M so all cycle constraints hold, Δ_1≈2 and Δ_2≈−1, so δ=1/max(0,1,1)=1 and δ|Δ_1−Δ_2|≈3>1. Then g_{12} would multiply β^−_{12} by roughly 3 and can leave Z. Thus the Brouwer fixed-point step for Theorem 3 is not established as written. The defect is repairable by choosing δ polynomially smaller and adjusting the constants in Claim 3, but the current proof has a false inequality at the center of the existence argument.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a formal model of data exchange economies in which agents exchange fractional shares of datasets without monetary transfers. An exchange is reciprocal if each agent's utility is at least the sum of her contributions to other agents' utilities, and core-stable if no coalition can, by exchanging only among themselves, give every member strictly higher utility. The central theoretical claim is that a reciprocal and exactly core-stable exchange exists for all monotone continuous utility functions and all continuous monotone, normalized, efficient credit-sharing functions (Theorems 1, 3, and 4). The proof route is to identify a convex polytope Z of approximate core-stable exchanges via a logarithmic homeomorphism, define a continuous map g on Z that adjusts surplus differences, invoke Brouwer's fixed-point theorem, and pass to the limit through a compactness argument. The paper also claims computational results: under L-Lipschitz utilities and cross-monotone shares, a local-search algorithm finds an ε-reciprocal and ε-core-stable exchange, and for L/ε = poly(n) the problem lies in CLS (Theorems 2, 6, 7, and 8).","tokens_in":38646,"tokens_out":20222,"duration_ms":189542,"significance":"If the main existence theorem is correct, it is a substantial result: it would show that fair and stable no-money data exchange is possible under very weak assumptions on utilities and credit-sharing rules, and it would contrast with the PPAD-hardness results for classical exchange economies. The computational upper bound of CLS for the approximate problem under diminishing-returns assumptions is also a meaningful contribution, and the paper is careful to formulate the model, definitions, and oracle model. The paper does not ship code or machine-checked proofs, but the theoretical framework is coherent and the technical overview is informative. However, the formal proof of the existence theorem contains a false inequality in a central lemma and a missing boundary argument in the fixed-point step, so the main claims are not established as written.","major_comments":[{"comment":"The assertion δ·|Δ_j(f(z))−Δ_i(f(z))|≤1 is false under the paper's axioms. Efficiency only forces Σ_i ψ_ij = u_j ≤ 1 per column, so an agent can contribute close to 1 to each of the other n−1 agents while receiving zero utility, giving surpluses differing by up to n. For example, for n=3 set u_1≡0, u_2(x)=x_12, u_3(x)=x_13, ψ_12=u_2, ψ_13=u_3, and all other ψ=0; these functions are continuous, monotone, normalized, and efficient. At any z∈Z with x_12,x_13 close to 1 and the remaining entries set sufficiently large, Δ_1≈2 and Δ_2≈−1, and with δ=1/max_i u_i(1)=1 we get δ|Δ_2−Δ_1|≈3>1. Consequently g_12(z)=z−e_12·δ·β^-_12(z)·(Δ_1−Δ_2) can leave Z, so Lemma 4 and the Brouwer fixed-point step of Theorem 3 are not established. Theorem 4 and the PPAD construction in Section 4.3 inherit this gap. The defect appears repairable, for example by taking δ no larger than 1/((n+1)·max_i u_i(1)) and adjusting the constants in Claim 3, but the proof as written is incorrect.","section":"Section 3.2, Lemma 4 and Eq. (3)"},{"comment":"The passage from g(z*)=z* to h_ij(z*)=0 for all i,j is unjustified when β_ij(z*)=0. The fixed-point equation only gives β_ij(z*)·h_ij(z*)=0 for each pair, so a boundary point with β_ij(z*)=0 and h_ij(z*)≠0 is not excluded. The informal path argument in Section 1.3 is the only place where this boundary case is addressed, but it is not proved in Section 3.2, and it is not a direct consequence of the definition of Z. For instance, a tight Hamiltonian cycle with every edge exactly at the threshold z_e=log(1/α) can have G(f(z),α) contain no edges, so the asserted path from j to i need not exist. A formal argument showing that an imbalanced surplus pair cannot be blocked in all directions is required before the fixed point can be identified with a reciprocal exchange.","section":"Section 3.2, proof of Theorem 3"}],"minor_comments":[{"comment":"The definition δ = 1/max_i u_i(1^{n×n}) is undefined when all utilities are identically zero; the degenerate case should be handled explicitly, even though the result is trivial there.","section":"Section 3.2"},{"comment":"The pseudocode and the while loop do not specify the target agent j from Lemma 10; the reader must infer that a single fixed j is used throughout the threshold-based reduction, and this should be stated in the algorithm.","section":"Section 4.1.1, Algorithm 2"},{"comment":"The statement \"Given an exchange x which is not ε-core stable and ε-reciprocal\" should read \"not ε-reciprocal,\" since the algorithm maintains ε-core stability by the acyclicity invariant.","section":"Section 4.1, Theorem 5"},{"comment":"The caption writes \"∆ i(b) < ∆ i(c)\" where it appears to mean the surpluses of agents b and c; using Δ_b and Δ_c would avoid confusion.","section":"Section 1.3, Figure 3 caption"},{"comment":"The notation i_ℓ for \"the smallest integer i such that σ_i ≥ ℓ\" is confusing because σ_i is already indexed; renaming this index t_ℓ would improve readability.","section":"Section 3.3, proof of Theorem 4"}],"recommendation":"major_revision","confidential_remarks":"The paper proposes an interesting and ambitious framework, and the main existence theorem may well be true. However, the submitted proof has a verifiably false inequality in Lemma 4 and an unproved boundary case in the fixed-point argument. These are load-bearing for the central existence claim and for the PPAD half of the computational results. I would encourage the authors to repair these points and resubmit; I am not recommending rejection because the issues appear potentially fixable within the scope of the manuscript."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The core new idea here is solid: a data-exchange model where core-stability requires no reciprocity from deviating coalitions, and an exact existence proof plus PPAD/CLS membership for approximate versions. That is a real step beyond the independent work by Bhaskara et al. The acyclic-exchange-graph technique and the convexification via log-transformation are clever, and the local search algorithm for cross-monotone share functions is a genuine contribution.\n\nBut the central proof has a serious hole. Lemma 4 asserts that δ|Δ_j(f(z))−Δ_i(f(z))| ≤ 1 for δ = 1/max_i u_i(1). That is false. Surpluses can differ by Θ(n) because an agent can contribute close to 1 to each of n−1 other agents while receiving zero utility. Concretely, with n=3, u_1≡0, u_2(x)=x_12, u_3(x)=x_13, and ψ_12=u_2, ψ_13=u_3, all other ψ=0, the share functions satisfy all axioms, δ=1, but at a feasible z with x_12≈x_13≈1 we get Δ_1≈2 and Δ_2≈−1. The bound fails, so g may not map Z into Z, and the Brouwer fixed-point step is not established. This is an earlier and more fundamental failure than the boundary case β_ij(z*)=0 that a separate pass flagged; both need addressing. The good news is the defect looks repairable: take δ = 1/(n·max_i u_i(1)) and adjust the constants in the fixed-point map and the PPAD/CLS arguments.\n\nThere is also a mismatch between Theorem 1 and the formal Theorem 4: the former claims existence for all share functions satisfying monotonicity, normalization, and efficiency, but the latter additionally assumes continuity of share functions. Either the main theorem needs that extra assumption stated, or the proof must be extended.\n\nThe computational sections contain a few unproved technical steps, e.g., the description of Algorithm 2's reduction step and the rounding argument in Lemma 18, but these look like presentation gaps rather than deep flaws. Overall, the paper is worth engaging with: the model and high-level approach are novel, the counterexample to Lemma 4 is specific and checkable, and the authors are clearly thinking carefully. I would not cite the existence theorem in its current form, but I would cite the framework and the complexity results if the proof is fixed.\n\nRecommendation: send to peer review, but only with the expectation of major revision. The referee should insist on a correct proof of Lemma 4 and a clear statement of the continuity assumption on share functions in Theorem 1.","headline":"A promising data-exchange model with a genuinely stronger core-stability notion, but the main existence proof has a false inequality at its center and needs repair.","tokens_in":39179,"tokens_out":3507,"would_cite":false,"duration_ms":34077,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B26","91A12","91B50","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"A reciprocal and core-stable exchange exists for all monotone continuous utility functions and any share function satisfying monotonicity, normalization, and efficiency.","keywords":["data exchange","reciprocity","core stability","Shapley share","fixed-point existence","CLS complexity","Arrow-Debreu markets","submodular utilities"],"falsifier":"Take a three-agent instance with continuous monotone piecewise-linear utilities and Shapley shares, and enumerate all points z∈Z satisfying the fixed-point equations. If any boundary point has β^+_{ij}(z)=β^−_{ij}(z)=0 for every surplus-imbalanced pair while some Δ_i(z)≠0, then the missing path lemma is false and the written proof of Theorem 3 collapses; a numerical search could find such an instance or demonstrate that none exists, which would either refute or corroborate the proof's key step.","tokens_in":38142,"feed_emoji":"🤝","tokens_out":8589,"duration_ms":76812,"temperature":0.7,"pith_summary":"This paper asks whether a group of agents holding datasets can exchange data voluntarily, without money, in a way that is both fair and stable. It proves that yes: for every instance in which utilities are monotone and continuous, and contributions are measured by any share function satisfying monotonicity, normalization, and efficiency (the Shapley value is the leading example), there is an exchange in which each agent receives at least as much utility as they contribute, and no coalition can all improve by exchanging only among themselves. The existence argument works by mapping almost acyclic exchange graphs to a convex polytope and applying a fixed-point theorem. For approximate versions with Lipschitz utilities and diminishing returns, the paper gives a local-search algorithm and shows the search problem lies in CLS. This gives the general existence guarantee that a price-free, coalition-proof data exchange is possible, which is the setting relevant to non-profit data-sharing consortia.","feed_headline":"Fair, stable data exchanges always exist under minimal assumptions","feed_subtitle":"Proof guarantees no-money data sharing where everyone gets at least their contribution; approximate cases are in CLS.","key_machinery":"The load-bearing object is a pair: the exchange graph G(x,α) and the convex domain Z = {z∈[0,M]^{n×n}: every directed cycle has z-sum at least n log(1/α)}, related to an exchange x by x_{ij} = 1−exp(−z_{ij}). Points of Z correspond exactly to exchanges whose exchange graph is acyclic, hence ε-core-stable. On this domain the paper defines a continuous map g that changes each coordinate z_{ij} toward the balanced-surplus direction, scaled by the distance to the boundary of Z along that coordinate, so g always stays inside Z. The move is truncated by β^+_{ij}(z) and β^−_{ij}(z), the maximum distances one can travel from z along ±e_{ij} without leaving Z. A fixed point of g equalizes all surpluses, and because the sum of surpluses is identically zero, equal surpluses mean every agent is reciprocal.","core_discovery":"On the paper's own terms, the central discovery is Theorem 1: a reciprocal and core-stable exchange exists for all monotone continuous utility functions and all credit-sharing functions that are monotone, normalized, and efficient. The proof works with the surplus Δ_i(x)=∑_j ψ_{ij}(x_j)-u_i(x_i); by efficiency the surpluses sum to zero, so an exchange is reciprocal exactly when all surpluses are equal (at zero). Stability is captured through the exchange graph G(x,α), which records an edge (i,j) when i's data to j is still below 1−α; if this graph is acyclic, no coalition can deviate and give every member a strict utility gain. The paper maps the set of such almost-acyclic exchanges homeomorphically to a convex compact polytope, constructs a continuous map that nudges data from higher-surplus to lower-surplus agents, and uses Brouwer's fixed-point theorem. A separate compactness argument turns ε-core-stability into exact core-stability.","pith_inferences":["The convex almost-acyclic domain construction is a general recipe: any stability notion that can be certified by an acyclic graph can be bolted onto a continuous surplus-balancing map, so similar existence theorems should hold for other replicable-resource sharing problems with a central server.","The local-search and CLS results are stated for monotone submodular utilities with Shapley shares, but the proof actually uses only L-Lipschitzness and cross-monotonicity; the same polynomial-time guarantee should extend to any cross-monotone share function under a Lipschitz bound.","Whether the problem is CLS-complete or easier remains open; a natural next step is to try to embed a CLS-complete problem into the surplus-balancing dynamics, or to find a polynomial-time algorithm through the projection structure."],"forward_implications":["Non-profit data exchange consortia are guaranteed a concrete price-free exchange in which every participant receives utility at least matching its own contribution, even when datasets are complements or substitutes and utilities are only continuous and monotone.","The guarantee is robust to the choice of credit-sharing rule: any rule satisfying monotonicity, normalization, and efficiency works, so institutions can pick Shapley, proportional, or another attribution without losing existence.","For Lipschitz, diminishing-returns preferences, an ε-fair and ε-core-stable exchange can be found by polynomially many local-search steps when L/ε is polynomial, and the problem sits in PPAD ∩ PLS = CLS.","The fixed-point formulation can be projected onto a box with polynomially many constraints, putting the approximate problem in PPAD while preserving the acyclicity invariant."],"supporting_citations":[{"why":"Proves existence of competitive equilibria in classic exchange economies, the baseline whose price mechanism this paper replaces with price-free fairness.","marker":"[AD54]"},{"why":"Defines the Shapley value, the credit-sharing rule that satisfies the paper's three share axioms and drives the computational results.","marker":"[Sha51, Sha53]"},{"why":"Presents Scarf's lemma, the standard fixed-point tool for cores that the paper cannot use because deviating coalitions are not required to be reciprocal.","marker":"[Sca67]"},{"why":"Introduces top trading cycles, whose core-stability argument via acyclic structures inspires the exchange-graph certification used here.","marker":"[SS74]"},{"why":"Supplies sufficient conditions for fixed-point search to lie in PPAD, used to prove PPAD membership of the approximate problem.","marker":"[EY10]"},{"why":"Establishes CLS = PPAD ∩ PLS, the equality used to conclude the local-search problem lies in CLS.","marker":"[FGHS23]"},{"why":"Documents the non-expansiveness of Euclidean projection onto convex sets, used to prove polynomial continuity of the projected fixed-point function.","marker":"[BNO03]"},{"why":"Presents an independent data-exchange model with a weaker reciprocity-constrained core and randomized exchanges, which this paper's existence theorem generalizes.","marker":"[BGI+24]"}],"fun_headline_variants":["Fair, stable data exchanges always exist","Data exchange markets: fair and stable outcomes proven","Proof: Fair data sharing without money always possible","Existence of fair, stable data exchange established","Data economies: fair and stable exchanges guaranteed"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof that every fixed point equalizes all agents' surplus (contribution to others minus utility received) assumes that whenever surpluses differ, at least one pair has a coordinate that can be nudged inside the domain; the written proof does not show this for boundary points where the allowed nudge is zero.","fun_headline_variants_meta":{"raw":{"variants":["Fair, stable data exchanges always exist","Data exchange markets: fair and stable outcomes proven","Proof: Fair data sharing without money always possible","Existence of fair, stable data exchange established","Data economies: fair and stable exchanges guaranteed"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000196,"raw_usage":{"total_tokens":1413,"prompt_tokens":1050,"completion_tokens":363,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":666,"completion_tokens_details":{"reasoning_tokens":309}},"tokens_in":666,"tokens_out":363,"duration_ms":3810,"temperature":1.0,"reasoning_tokens":309,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T00:00:41.691043+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a three-agent instance with continuous monotone piecewise-linear utilities and Shapley shares, and enumerate all points z∈Z satisfying the fixed-point equations. If any boundary point has β^+_{ij}(z)=β^−_{ij}(z)=0 for every surplus-imbalanced pair while some Δ_i(z)≠0, then the missing path lemma is false and the written proof of Theorem 3 collapses; a numerical search could find such an instance or demonstrate that none exists, which would either refute or corroborate the proof's key step.","supporting_citations":[],"review_version":1}