Game of Coding for Vector-Valued Computations
This work addresses the challenge of secure and reliable decentralized machine learning in permissionless applications where nodes may be adversarial, though it is incremental as it builds on prior scalar-based results.
The paper tackles the problem of reliable decoding in adversarial settings for vector-valued computations, extending the game of coding framework to multi-dimensional Euclidean space and fully characterizing equilibrium strategies for a two-repetition code with at least one rational adversary.
Traditional coding theory guarantees valid decoding only if a minority of symbols are adversarially manipulated. In contrast, the game of coding framework ensures reliable decoding, even in the presence of an adversarial majority. This formulation is motivated by emerging permissionless applications, particularly decentralized machine learning (DeML), where computation tasks are outsourced to external volunteer nodes that are predominantly rational and reward-seeking. Prior investigations have analyzed the game of coding in the scalar setting. Since the results of most major computations in machine learning are vectors (e.g., computing the gradient of the loss for a machine learning model), we extend the framework in this paper to the general multi-dimensional Euclidean space. As a first, yet fundamental step, in this paper, we study a two-repetition code in which at least one node is controlled by a rational adversary, and we fully characterize the equilibrium and the optimal strategies of the players. Similar to the scalar case, this result serves as a cornerstone for addressing more general scenarios.