Nash equilibria in stabilizing systems

• Published in: Theoretical computer science 2011-07, Vol.412 (33), p.4325-4335
• Main Authors: Gouda, M.G., Acharya, H.B.
• Format: Article
• Language: English
• Subjects: Applied sciences; Computer networks; Computer science; control theory; systems; Computer systems and distributed systems. User interface; Exact sciences and technology; Gain; Global analysis, analysis on manifolds; Incentives; Mathematics; Miscellaneous; Nash equilibrium; Perturbation-prone; Perturbation-proof; Sciences and techniques of general use; Selfishness; Software; Stabilizing system; Theoretical computing; Topology. Manifolds and cell complexes. Global analysis and analysis on manifolds
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/j.tcs.2010.11.027

The objective of this paper is three-fold. First, we specify what it means for a fixed point of a stabilizing distributed system to be a Nash equilibrium. Second, we present methods that can be used to verify whether or not a given fixed point of a given stabilizing distributed system is a Nash equilibrium. Third, we argue that in a stabilizing distributed system, whose fixed points are all Nash equilibria, no process has an incentive to perturb its local state, after the system reaches one fixed point, in order to force the system to reach another fixed point where the perturbing process achieves a better gain. If the fixed points of a stabilizing distributed system are all Nash equilibria, then we refer to the system as perturbation-proof. Otherwise, we refer to the system as perturbation-prone. We identify four natural classes of perturbation-(proof/prone) systems. We present system examples for three of these classes of systems, and show that the fourth class is empty.