Technical Summary: Quotient Semivalues for False-Name-Resistant Data Attribution

1. Problem Statement

Data valuation methods, such as Data Shapley, are designed to allocate payments and audit the contribution of training data to machine learning pipelines. However, these methods typically assume a fixed set of passive contributors. In real-world data markets, contributors are strategic agents who can manipulate the attribution mechanism to inflate their share.

The paper identifies false-name manipulation as a critical failure mode. A single latent provider can:

• Split a dataset across multiple pseudonymous identities (Sybil attacks).
• Duplicate high-value examples or create near-duplicates (paraphrases, augmentations, synthetic variants).
• Launder synthetic variants to exploit the evaluator's validation set.

The core issue is that standard Shapley-fair attribution over reported identities is not incentive-compatible. Because data value is often non-additive and complementary, splitting a dataset into multiple identities can increase the sum of the Shapley values received by the attacker compared to the value received by a single honest identity.

2. Methodology

2.1 Formal Model

The authors formalize the setting as a mechanism design problem over latent providers ($N$) and submitted identities ($m$).

• Data-Value Game: A monotone game where the value of a coalition is the utility of the learner trained on the union of payloads from that coalition.
• Manipulation Classes:
  • False-name split: Replacing one identity with $k \ge 2$ identities holding a partition or replication of the original data.
  • Variant attack: Submitting transformed copies (duplicates, paraphrases, synthetic data) under one or more identities.
• Gain Metric: The additive or multiplicative gain an attacker achieves by manipulating the identity structure compared to honest reporting.

2.2 Impossibility Result

The paper proves a fundamental impossibility theorem: Exact Shapley-fair attribution over reported identities is incompatible with unrestricted false-name-proofness.
Even on binary-valued, monotone games (e.g., unanimity games), a provider can increase their total payment by splitting their data into multiple pseudonyms. For example, in a two-player unanimity game where $v(\{A, B\}) = 1$, provider $A$ receives $1/2$. If $A$ splits into $A_1, A_2$ such that value requires all three ($A_1, A_2, B$), the new Shapley values are $1/3$ each, yielding a total of $2/3$ for $A$. This structural vulnerability extends to general semivalues (Banzhaf, Beta-Shapley), though the magnitude of the gain varies.

2.3 The Quotient Semivalue Mechanism

To resolve this, the authors propose the Quotient Semivalue mechanism, which shifts the strategic unit from raw submitted identities to evidence-backed attribution clusters.

1. Evidence Graph & Clustering:
   • An evidence function $e_\theta(u, u')$ determines if two units (examples, documents) are sufficiently similar (based on hashes, embeddings, provenance, etc.) to be treated as the same attribution object.
   • This forms a graph where connected components are clusters ($C_1, \dots, C_K$).
2. Cluster Representative Operator ($R_\theta$):
   • To prevent manipulation via within-cluster duplication (e.g., submitting 10 copies of an example to weight it higher), a canonical representative operator maps each cluster to a fixed set of canonical training units.
   • Strategies include: exact-duplicate collapse, capping the number of units per cluster, or weight-normalized unions.
3. Quotient Game:
   • A new cooperative game is constructed where the players are the clusters, not the identities.
   • The value of a coalition of clusters is the utility of the learner trained on the union of their canonical representatives.
4. Semivalue Calculation & Allocation:
   • Semivalues (Shapley, Banzhaf, etc.) are computed over the quotient game.
   • Within-Cluster Allocation: The payment to a cluster is distributed among the submitted identities within it. The mechanism requires a false-name-neutral allocation rule (e.g., allocation proportional to the count of canonical units contributed by each identity) to ensure that splitting an identity within a cluster does not increase the total share.

3. Key Contributions

1. Formal Model: A rigorous framework for data-provider manipulation involving latent providers, submitted identities, and transformation attacks.
2. Impossibility Theorem: Proof that no mechanism can be both exactly Shapley-fair on reported identities and unrestrictedly false-name-proof.
3. Quotient Semivalue Mechanism: A constructive solution that computes semivalues over evidence-backed clusters with a canonical representative operator.
4. Theoretical Guarantees:
   • Exact False-Name-Proofness: Achieved under "quotient-stable" manipulations (where the attacker cannot escape their honest cluster or alter the canonical representative) and false-name-neutral allocation.
   • Approximate Guarantees: Bounds on manipulation gain and fairness loss in terms of three measurable quantities: escaped-cluster mass (variants that form new clusters), value-estimation error, and clustering distance (drift in the representative).
5. DataMarket-Gym: A new benchmark for evaluating attribution mechanisms under strategic provider attacks, covering exact duplicates, near-duplicates, synthetic laundering, and Sybil splitting.

4. Experimental Results

The authors evaluate the mechanism on synthetic and real-world datasets (CIFAR-10, AG News, STL-10, IMDB).

• Synthetic Classification:
  • Baseline Shapley on raw identities showed a manipulation gain of 1.74 on duplicate/Sybil attacks.
  • Quotient Shapley with example-level evidence (cosine similarity $\theta=0.99$) reduced this gain to 0.96, effectively neutralizing the attack and returning to near-honest levels.
  • The mechanism is robust to the choice of semivalue (Shapley, Banzhaf, Beta-Shapley).
• Threshold Sensitivity:
  • The cosine threshold $\theta$ is critical. Too low a threshold causes "false merges" (independent providers grouped together), which can amplify Sybil gains. Too high a threshold fails to catch near-duplicates.
  • The paper identifies a domain-specific threshold reversal:
    • In image domains (CIFAR-10), high norms lead to high pairwise similarities; a tighter threshold ($\theta \ge 0.90$) is required to prevent chaining attacks.
    • In text domains (AG News), unit-normalized embeddings have lower pairwise similarities; a looser threshold ($\theta \le 0.90$) is optimal, as strict thresholds fail to link near-duplicates.
  • The optimal threshold is predictable from embedding statistics (pairwise p90 and chaining-floor mixed-component fraction).
• Real-World Transfer:
  • The mechanism transfers to frozen-feature pipelines (ResNet-18, MiniLM) without oracle access, confirming its practical viability.
  • Pure-split attacks (disjoint data with no overlap) remain undefended by similarity evidence alone, requiring non-example-level provenance (e.g., account linkage, KYC).

5. Significance and Claims

The paper claims that Shapley-fair data attribution is not automatically incentive-compatible when identities are endogenous. The significance of the work lies in:

• Shifting the Strategic Burden: Moving the attribution unit from mutable identities to evidence-backed clusters allows for a controlled trade-off between Shapley-style fairness and Sybil resistance.
• Conditional Possibility: While exact Shapley fairness is impossible under unrestricted manipulation, the quotient mechanism recovers a "controlled trade-off" when similarity and provenance signals can reliably collapse manipulated variants into the same unit.
• Practical Deployment: The mechanism is "semivalue-agnostic," meaning it can be deployed with various valuation backends (Shapley, Banzhaf, etc.) and is robust to estimator noise.
• Complementarity: The approach complements existing work on "Faithful Group Shapley Values" (which defends against shell-company aggregation of fixed datasets) by addressing the construction of the attribution unit itself when data content can be altered (duplicated, paraphrased, synthesized).

The authors conclude that the unit of attribution is a mechanism-design choice, and the quotient semivalue provides a robust framework for data markets where providers are strategic.