# Game of Coding With an Unknown Adversary

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 23 references that are in the map.
- First posted on arXiv 10 Feb 2025.

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

- [Strategic Classification from Revealed Preferences](https://mlsanity.com/paper/1710.07887/) (2017)
- [Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy](https://mlsanity.com/paper/1806.00939/) (2018)
- [Learning in Stackelberg Games with Non-myopic Agents](https://mlsanity.com/paper/2208.09407/) (2022)
- [Berrut Approximated Coded Computing: Straggler Resistance Beyond Polynomial Computing](https://mlsanity.com/paper/2009.08327/) (2020)
- [Learning to Play Sequential Games versus Unknown Opponents](https://mlsanity.com/paper/2007.05271/) (2020)
- [CodedSketch: A Coding Scheme for Distributed Computation of Approximated Matrix Multiplication](https://mlsanity.com/paper/1812.10460/) (2018)
- [Robust Stackelberg Equilibria](https://mlsanity.com/paper/2304.14990/) (2023)
- [Game of Coding: Sybil Resistant Decentralized Machine Learning with Minimal Trust Assumption](https://mlsanity.com/paper/2410.05540/) (2024)
- ["Zero Cost'' Majority Attacks on Permissionless Blockchains](https://mlsanity.com/paper/2308.06568/) (2023)

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

- [Game of Coding: Coding Theory in the Presence of Rational Adversaries, Motivated by Decentralized Machine Learning](https://mlsanity.com/paper/2601.02313/) (2026)
- [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)

Motivated by emerging decentralized applications, the game of coding framework has been recently introduced to address scenarios where the adversary's control over coded symbols surpasses the fundamental limits of traditional coding theory. Still, the reward mechanism available in decentralized systems, motivates the adversary to act rationally. While the decoder, as the data collector (DC), has an acceptance and rejection mechanism, followed by an estimation module, the adversary aims to maximize its utility, as an increasing function of (1) the chance of acceptance (to increase the reward), and (2) estimation error. On the other hand, the decoder also adjusts its acceptance rule to maximize its own utility, as (1) an increasing function of the chance of acceptance (to keep the system functional), (2) decreasing function of the estimation error. Prior works within this framework rely on the assumption that the game is complete, that is, both the DC and the adversary are fully aware of each other's utility functions. However, in practice, the decoder is often unaware of the utility of the adversary. To address this limitation, we develop an algorithm enabling the DC to commit to a strategy that achieves within the vicinity of the equilibrium, without knowledge of the adversary's utility function. Our approach builds on an observation that at the equilibrium, the relationship between the probability of acceptance and the mean squared error (MSE) follows a predetermined curve independent of the specific utility functions of the players. By exploiting this invariant relationship, the DC can iteratively refine its strategy based on observable parameters, converging to a near-optimal solution. We provide theoretical guarantees on sample complexity and accuracy of the proposed scheme.