Title: Strategies for repeated games with subsystem takeovers implementable by deterministic and self-stabilising automata

Authors: Shlomi Dolev, Elad Michael Schiller, Paul G. Spirakis, Philippas Philippas

Addresses: Department of Computer Science, Ben-Gurion University of the Negev, Beer Sheva 84105, Israel. ' Department of Computing Science, Chalmers University of Technology and Goteborg University, Rannvagen 6B, Goteborg S-412 96, Sweden. ' Research Academic Computer Technology Institute, N. Kazantzakis Street, University Campus, Rio, Patras 26500, Greece. ' Department of Computing Science, Chalmers University of Technology and Goteborg University, Rannvagen 6B, Goteborg S-412 96, Sweden

Abstract: Systems of selfish-computers are subject to transient faults due to temporal malfunctions; just as the society is subjected to human mistakes. Game theory uses punishment for deterring improper behaviour. Due to faults, selfish-computers may punish well-behaved ones. This is one of the key motivations for forgiveness that follows any effective and credible punishment. Therefore, unplanned punishments must provably cease in order to avoid infinite cycles of unsynchronised behaviour of |tit for tat|. We investigate another aspect of these systems. We consider the possibility of subsystem takeover. The takeover may lead to joint deviations coordinated by an arbitrary selfish-computer that controls an unknown group of subordinate computers. We present strategies that deter the coordinator from deviating in infinitely repeated games. We construct deterministic automata that implement these strategies with optimal complexity. Moreover, we prove that all unplanned punishments eventually cease by showing that the automata can recover from transient faults.

Keywords: game theory; Folk theorem; joint deviations; finite automata; self-stabilisation; subsystem takeover; autonomous systems; adaptive communications; transient faults; uncooperative repeated games; subordinate deviations; infinitely repeated games; selfish computers; involuntary misbehaviour; unplanned punishments.

DOI: 10.1504/IJAACS.2011.037747

International Journal of Autonomous and Adaptive Communications Systems, 2011 Vol.4 No.1, pp.4 - 38

Published online: 24 Jan 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article