How should Shapley payments be sampled and audited?

research/shapley-sampling

Auditing sampled Shapley payments: exact estimator variances in a saturating game, permutation sampling is exactly efficient but stratified sampling has 6–8× lower variance (zero for equal contributors) at up to 7% budget error, antithetic reversal gives 1.6× lower RMSE, Hoeffding sample counts are 4–5× conservative.

9 tests

What it found

In a saturating contribution game v(S)=1−exp(−Σw_i) every estimator variance is exact. Permutation sampling always pays out exactly v(N) but is noisy; size-stratified sampling has 6–8× lower variance (exactly zero for equal contributors) yet misses the pot by up to 7% in a run; reversing each permutation cuts RMSE 1.6× at no cost; Hoeffding sample counts are 4–5× larger than needed, and stratification finds the top-3 payees with about 4× fewer samples. Stylised, n≤10.

A figure from its own output

Figure produced by research/shapley-sampling: rank_recovery — shapley-sampling/experiments/rank_recovery.svg, written by the project's own experiment code.

Paper, code and results

More in Paying contributors

How precise should a training-contest leaderboard be?Winner-take-all training contests scored on a noisy holdout: effort V a_n √m/s with a_2 = a_3 = 1/(2√π) exactly, a precision ceiling V/σ² ≤ λ_max(n) beyond which no pure equilibrium exists (below the zero-rent limit), and the resulting optimal holdout size.
What does it cost to buy decentralised compute?Buying k units of decentralised compute by reverse auction: exact VCG payment k(k+1)/(n+1) is exactly 2× winners' cost, optimal reserve is exactly v/2, first-price equilibrium matches by revenue equivalence.
What does it cost to make workers race?Paying the first k of n finishers makes speed a contest: π'(1)=(1−k/n)(H_n−H_{n−k}), equilibrium speed R(n−k)(H_n−H_{n−k})/(nc), exact round time nc/((n−k)R); paying all finishers buys no speed, a budget favours winner-take-all until an accuracy floor k_min binds, and recruiting more workers barely speeds the round.
Who drops out of a race when workers have unequal costs?Paying the first k of n finishers when costs differ: proof of the π'(1) telescoping identity, exact exit rule (slow workers idle iff c_s/c_f ≥ n_f/(n_f−k), never for k ≥ n_f), cost ratio 4 excludes slow workers for k ≤ 3 of 4 fast, convex costs make headcount buy speed.
How much accuracy can a market buy from contributors who value their privacy?Buying private data with a telescoping log-score market: payment equals information, best Gaussian-mechanism noise in closed form, participation iff κa<1 so precision is capped at λ/(cΔ²) for any number of contributors, and early arrivals over-collect (1–22% welfare loss).
Paying for improvements, not for overfittingPaying for model improvements against a hidden holdout: telescoping budget, a payment-feedback overfitting attack (paid 0.15 while true loss worsens 0.37), and the Ladder fix with its measured cost.

All 8 Paying contributors projects →

Other research topics

Proper scoring & elicitation28 Effort & peer prediction9 Verification games & slashing19 Detection & tolerances14 Markets as routers13 Prediction-market design9 Paying contributors8 Decentralised training systems23 Digital twins & sim-to-real164 LLM chip design loops40 Robot manufacturing loops53 Ambient AI assistant46 Self-replicating manufacturing34 Simulation-first design64 Engineered clothing45 Task-specific AI accelerators40 Algorithmic chip-design loops42 Open-source purpose-built robots44 The software-engineering loop43 Adversarial human imitation41 Open-source residential construction41 Autonomous multi-angle capture34 Sensing, imaging and 3D31 Energy supply and dense energy storage39 Robot societies among people31 Agentic co-design of low-cost robots27 Laundry-hanging robots25 Machine learning on qualitative data23 Robots on the building site27 Civilizations & group psychology1 History & human sciences1

Produced with AI assistance (Claude). Results are from the code in this repository and are simulated or stylised unless the abstract says otherwise; nothing here implies affiliation with or endorsement by any lab, researcher or company cited. MIT licensed.