×

Convergence analysis of iterated best response for a trusted computation game. (English) Zbl 1357.93064

Summary: We introduce a game of trusted computation in which a sensor equipped with limited computing power leverages a central computer 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 computer. 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.

MSC:

93C83 Control/observation systems involving computers (process control, etc.)
91A05 2-person games
91A10 Noncooperative games
93B40 Computational methods in systems theory (MSC2010)
68T05 Learning and adaptive systems in artificial intelligence
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Achlioptas, D.; McSherry, F., Fast computation of low rank matrix approximations, Journal of the ACM, 52, 2 (2007) · Zbl 1311.94031
[5] Brown, G. W., Iterative solutions of games by fictitious play, (Koopmans, T. C., Activity analysis of production and allocation (1951), Wiley: Wiley New York), 374-376 · Zbl 0045.09902
[8] Fudenberg, D., The theory of learning in games, Vol. 2 (1998), MIT press · Zbl 0939.91004
[10] Internet of things: privacy and security in a connected world. Report (2015), US Federal Trade Commission
[11] Marden, J. R.; Arslan, G.; Shamma, J. S., Joint strategy fictitious play with inertia for potential games, IEEE Transactions on Automatic Control, 54, 2, 208-220 (2009) · Zbl 1367.91035
[12] Reeves, D. M.; Wellman, M. P., Computing best-response strategies in infinite games of incomplete information, (Proceedings of the 20th conference on uncertainty in artificial intelligence (2004), AUAI Press), 470-478
[13] Robinson, J., An iterative method of solving a game, Annals of Mathematics, 54, 296-301 (1951) · Zbl 0045.08203
[15] Shamma, J. S.; Arslan, G., Unified convergence proofs of continuous-time fictitious play, IEEE Transactions on Automatic Control, 49, 7, 1137-1142 (2004) · Zbl 1366.91011
[16] Shamma, J. S.; Arslan, G., Dynamic fictitious play, dynamic gradient play, and distributed convergence to nash equilibria, IEEE Transactions on Automatic Control, 50, 3, 312-327 (2005) · Zbl 1366.91028
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.