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

• URL: http://arxiv.org/abs/2601.02313v1
• Date: Mon, 05 Jan 2026 18:04:32 GMT
• Title: Game of Coding: Coding Theory in the Presence of Rational Adversaries, Motivated by Decentralized Machine Learning
• Authors: Hanzaleh Akbari Nodehi, Viveck R. Cadambe, Mohammad Ali Maddah-Ali,
• Abstract summary: Coding theory plays a crucial role in enabling reliable communication, storage, and computation.<n>In some emerging decentralized applications, particularly in decentralized machine learning (DeML), participating nodes are rewarded for accepted contributions.<n>We introduce the game of coding, a novel game-theoretic framework that extends coding theory to trust-minimized settings.
• Score: 16.147310961390534
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• One Token Embedding Is Enough to Deadlock Your Large Reasoning Model [91.48868589442837]
  We present the Deadlock Attack, a resource exhaustion method that hijacks an LRM's generative control flow.<n>Our method achieves a 100% attack success rate across four advanced LRMs.
  arXiv  Detail & Related papers  (2025-10-12T07:42:57Z)
• Adversarial generalization of unfolding (model-based) networks [0.0]
  We study the adversarial generalization of unfolding networks when perturbed with $l$-norm constrained attacks.<n>This is the first theoretical analysis on the adversarial generalization of unfolding networks.<n>We present a series of experiments on real-world data, with results corroborating our derived theory.
  arXiv  Detail & Related papers  (2025-09-18T19:17:07Z)
• Game of Coding With an Unknown Adversary [15.839621757142597]
  Motivated by emerging decentralized applications, the emphgame of coding framework has been introduced to address scenarios where the adversary's control over coded symbols surpasses the fundamental limits of traditional coding theory.<n>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.<n>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.
  arXiv  Detail & Related papers  (2025-02-10T23:06:10Z)
• A Quantum Algorithm for Assessing Node Importance in the st-Connectivity Attack [0.8739101659113155]
  This work describes a quantum approach to approximating the importance of nodes that maintain a target connection.<n>The approximation method relies on quantum subroutines for st-connectivity and approximating Shapley values.<n>We consider st-connectivity attack scenarios in which a malicious actor disrupts a subset of nodes to perturb the system functionality.
  arXiv  Detail & Related papers  (2025-02-01T14:40:52Z)
• Protocol Learning, Decentralized Frontier Risk and the No-Off Problem [56.74434512241989]
  We identify a third paradigm - Protocol Learning - where models are trained across decentralized networks of incentivized participants.<n>This approach has the potential to aggregate orders of magnitude more computational resources than any single centralized entity.<n>It also introduces novel challenges: heterogeneous and unreliable nodes, malicious participants, the need for unextractable models to preserve incentives, and complex governance dynamics.
  arXiv  Detail & Related papers  (2024-12-10T19:53:50Z)
• Game of Coding: Sybil Resistant Decentralized Machine Learning with Minimal Trust Assumption [20.564198591600647]
  This paper investigates the implications of increasing the number of nodes in the game of coding framework. We show that despite the increased flexibility for the adversary with an increasing number of adversarial nodes, having more power is not beneficial for the adversary.
  arXiv  Detail & Related papers  (2024-10-07T22:49:47Z)
• Sparse Decentralized Federated Learning [35.32297764027417]
  Decentralized Federated Learning (DFL) enables collaborative model training without a central server but faces challenges in efficiency, stability, and trustworthiness.<n>We introduce a sparsity constraint on the shared model, leading to Sparse DFL (SDFL), and propose a novel algorithm, CEPS.<n> Numerical experiments validate the effectiveness of the proposed algorithm in improving communication and efficiency while maintaining a high level of trustworthiness.
  arXiv  Detail & Related papers  (2023-08-31T12:22:40Z)
• Doubly Robust Instance-Reweighted Adversarial Training [107.40683655362285]
  We propose a novel doubly-robust instance reweighted adversarial framework. Our importance weights are obtained by optimizing the KL-divergence regularized loss function. Our proposed approach outperforms related state-of-the-art baseline methods in terms of average robust performance.
  arXiv  Detail & Related papers  (2023-08-01T06:16:18Z)
• Networked Communication for Decentralised Agents in Mean-Field Games [59.01527054553122]
  We introduce networked communication to the mean-field game framework.<n>We prove that our architecture has sample guarantees bounded between those of the centralised- and independent-learning cases.<n>We show that our networked approach has significant advantages over both alternatives in terms of robustness to update failures and to changes in population size.
  arXiv  Detail & Related papers  (2023-06-05T10:45:39Z)
• Spatial-Frequency Discriminability for Revealing Adversarial Perturbations [53.279716307171604]
  Vulnerability of deep neural networks to adversarial perturbations has been widely perceived in the computer vision community. Current algorithms typically detect adversarial patterns through discriminative decomposition for natural and adversarial data. We propose a discriminative detector relying on a spatial-frequency Krawtchouk decomposition.
  arXiv  Detail & Related papers  (2023-05-18T10:18:59Z)
• Adversarial Robustness with Semi-Infinite Constrained Learning [177.42714838799924]
  Deep learning to inputs perturbations has raised serious questions about its use in safety-critical domains. We propose a hybrid Langevin Monte Carlo training approach to mitigate this issue. We show that our approach can mitigate the trade-off between state-of-the-art performance and robust robustness.
  arXiv  Detail & Related papers  (2021-10-29T13:30:42Z)
• Byzantine-resilient Decentralized Stochastic Gradient Descent [85.15773446094576]
  We present an in-depth study towards the Byzantine resilience of decentralized learning systems. We propose UBAR, a novel algorithm to enhance decentralized learning with Byzantine Fault Tolerance.
  arXiv  Detail & Related papers  (2020-02-20T05:11:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.