Convergence analysis of iterated best response for a trusted computation game

DOI10.1016/J.AUTOMATICA.2016.11.046MaRDI QIDQ518294zbMATH OpenOpenAlexFDO

Authors Shaunak D. Bopardikar, Alberto Speranzon, Cédric Langbort

Publication date 28 March 2017

Published in Automatica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.02329

zbMATH Keywords

adversarial machine learningcomputational methodsgame theoryiterated best response

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) 2-person games (91A05) Noncooperative games (91A10) Control/observation systems involving computers (process control, etc.) (93C83)

Abstract: We introduce a game of trusted computation in which a sensor equipped with limited computing power leverages a central node to evaluate a specified function over a large dataset, collected over time. We assume that the central computer can be under attack and we propose a strategy where the sensor retains a limited amount of the data to counteract the effect of attack. We formulate the problem as a two player game in which the sensor (defender) chooses an optimal fusion strategy using both the non-trusted output from the central computer and locally stored trusted data. The attacker seeks to compromise the computation by influencing the fused value through malicious manipulation of the data stored on the central node. We first characterize all Nash equilibria of this game, which turn out to be dependent on parameters known to both players. Next we adopt an Iterated Best Response (IBR) scheme in which, at each iteration, the central computer reveals its output to the sensor, who then computes its best response based on a linear combination of its private local estimate and the untrusted third-party output. We characterize necessary and sufficient conditions for convergence of the IBR along with numerical results which show that the convergence conditions are relatively tight.

Recommendations

• On the convergence to Nash equilibrium in problems of distributed computing
• Computation of Nash equilibria: Admissibility of parallel gradient descent
• Distributed Computation of Nash Equilibria in Linear-Quadratic Stochastic Differential Games
• Distributed robust adaptive equilibrium computation for generalized convex games
• Iterative computation of security strategies of matrix games with growing action set

Cites work

• A note on element-wise matrix sparsification via a matrix-valued Bernstein inequality
• Adversarial machine learning
• An iterative method of solving a game
• Convergence analysis of iterated best response for a trusted computation game
• Dynamic fictitious play, dynamic gradient play, and distributed convergence to Nash equilibria
• Fast computation of low-rank matrix approximations
• scientific article; zbMATH DE number 1233801 (Why is no real title available?)
• scientific article; zbMATH DE number 3069635 (Why is no real title available?)
• Joint Strategy Fictitious Play With Inertia for Potential Games
• Unified Convergence Proofs of Continuous-Time Fictitious Play

Cited in

(4)

• Equilibrium analysis and incentive-based control of the anticoordinating networked game dynamics
• Convergence analysis of iterated best response for a trusted computation game
• Game-Theoretic Analysis of an Incentivized Verifiable Computation System
• Characterizing oscillations in heterogeneous populations of coordinators and anticoordinators

This page was built for publication: Convergence analysis of iterated best response for a trusted computation game

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q518294)