# Game of Coding: Coding Theory in the Presence of Rational Adversaries, Motivated by Decentralized Machine Learning

arXiv: https://arxiv.org/abs/2601.02313 · HTML: https://mlsanity.com/paper/2601.02313/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 33 references that are in the map.
- First posted on arXiv 5 Jan 2026.

## Builds on (most cited first, 15 of 15)

- [Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy](https://mlsanity.com/paper/1806.00939/) (2018)
- [SafetyNets: Verifiable Execution of Deep Neural Networks on an Untrusted Cloud](https://mlsanity.com/paper/1706.10268/) (2017)
- [Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication](https://mlsanity.com/paper/1705.10464/) (2017)
- [VeriML: Enabling Integrity Assurances and Fair Payments for Machine Learning as a Service](https://mlsanity.com/paper/1909.06961/) (2019)
- [On the Optimal Recovery Threshold of Coded Matrix Multiplication](https://mlsanity.com/paper/1801.10292/) (2018)
- [opML: Optimistic Machine Learning on Blockchain](https://mlsanity.com/paper/2401.17555/) (2024)
- [CodedSketch: A Coding Scheme for Distributed Computation of Approximated Matrix Multiplication](https://mlsanity.com/paper/1812.10460/) (2018)
- [Entangled Polynomial Codes for Secure, Private, and Batch Distributed Matrix Multiplication: Breaking the "Cubic" Barrier](https://mlsanity.com/paper/2001.05101/) (2020)
- [Game of Coding: Sybil Resistant Decentralized Machine Learning with Minimal Trust Assumption](https://mlsanity.com/paper/2410.05540/) (2024)
- [General Coded Computing: Adversarial Settings](https://mlsanity.com/paper/2502.08058/) (2025)
- [SoK: Blockchain Technology and Its Potential Use Cases](https://mlsanity.com/paper/1909.12454/) (2019)
- [SAKSHI: Decentralized AI Platforms](https://mlsanity.com/paper/2307.16562/) (2023)
- [Game of Coding With an Unknown Adversary](https://mlsanity.com/paper/2502.07109/) (2025)
- [textttRange-Arithmetic: Verifiable Deep Learning Inference on an Untrusted Party](https://mlsanity.com/paper/2505.17623/) (2025)
- [Multi-Party Proof Generation in QAP-based zk-SNARKs](https://mlsanity.com/paper/2103.01344/) (2021)

## Built on by (most cited first, 2 of 2)

- [mathsfVISTA: Decentralized Machine Learning in Adversary Dominated Environments](https://mlsanity.com/paper/2605.07841/) (2026)
- [Learning from Acceptance: Cumulative Regret in the Game of Coding](https://mlsanity.com/paper/2605.09754/) (2026)

## Abstract (arXiv)

Coding theory plays a crucial role in enabling reliable communication, storage, and computation. Classical approaches assume a worst-case adversarial model and ensure error correction and data recovery only when the number of honest nodes exceeds the number of adversarial ones by some margin. However, in some emerging decentralized applications, particularly in decentralized machine learning (DeML), participating nodes are rewarded for accepted contributions. This incentive structure naturally gives rise to rational adversaries who act strategically rather than behaving in purely malicious ways. In this paper, we first motivate the need for coding in the presence of rational adversaries, particularly in the context of outsourced computation in decentralized systems. We contrast this need with existing approaches and highlight their limitations. We then introduce the game of coding, a novel game-theoretic framework that extends coding theory to trust-minimized settings where honest nodes are not in the majority. Focusing on repetition coding, we highlight two key features of this framework: (1) the ability to achieve a non-zero probability of data recovery even when adversarial nodes are in the majority, and (2) Sybil resistance, i.e., the equilibrium remains unchanged even as the number of adversarial nodes increases. Finally, we explore scenarios in which the adversary's strategy is unknown and outline several open problems for future research.