Strategies for repeated games with subsystem takeovers

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Strategies for repeated games with subsystem takeovers: implementable by deterministic and self-stabilizing automata (extended abstract)

Full text

Pdf (205 KB)

Source

International Conference on Autonomic Computing and Communication Systems archive
Proceedings of the 2nd International Conference on Autonomic Computing and Communication Systems table of contents

Turin, Italy

Article No. 37

Year of Publication: 2008

ISBN:978-963-9799-34-9

Authors

Shlomi Dolev	Ben-Gurion University of the Negev, Israel
Elad M. Schiller	Chalmers University of Technology, Sweden
Paul G. Spirakis	Research Academic Computer Technology Institute, Greece
Philippas Tsigas	Chalmers University of Technology, Sweden

Sponsors

: ICST
ACM: Association for Computing Machinery
: Create-Net

Publisher

ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering) ICST, Brussels, Belgium, Belgium

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 43, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

ABSTRACT

Systems of selfish-computers, such as the Internet, are subject to transient faults due to hardware/software temporal malfunctions; just as the society is subjected to human mistakes due to a moment of weakness. Game theory uses punishment for deterring improper behavior. 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 be proven to have ceased in order to avoid infinite cycles of unsynchronized behavior of "tit for tat".

We investigate another aspect of selfish-computer systems. We consider the possibility of subsystem takeover, say, by the use of hostile malware. 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 (and its subordinates) from deviating in infinitely repeated games. We construct deterministic and finite 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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Ittai Abraham , Danny Dolev , Rica Gonen , Joe Halpern, Distributed computing meets game theory: robust mechanisms for rational secret sharing and multiparty computation, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146393]
	2	I. Abraham, D. Dolev, and J. Y. Halpern. Lower bounds on implementing robust and resilient mediators. In R. Canetti, editor, TCC, volume 4948 of Lecture Notes in Computer Science, pages 302--319. Springer, 2008.
	3	Amitanand S. Aiyer , Lorenzo Alvisi , Allen Clement , Mike Dahlin , Jean-Philippe Martin , Carl Porth, BAR fault tolerance for cooperative services, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom
	4	Lorenzo Alvisi, BAR--Where Distributed Computing Meets Game Theory, Proceedings of the 3rd Latin-American symposium on Dependable Computing, September 26-28, 2007, Morella, Mexico [doi>10.1007/978-3-540-75294-3_19]
	5	Nir Andelman , Michal Feldman , Yishay Mansour, Strong price of anarchy, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.189-198, January 07-09, 2007, New Orleans, Louisiana
	6	R. J. Aumann. Acceptable points in general cooperative n-person games. Contributions to the Theory of Games, 4:287--324, 1959.
	7	R. J. Aumann. The core of a cooperative game without side payments. Transactions of the American Mathematical Society, 98(3):539--552, 1961.
	8	R. J. Aumann et al. Survey of Repeated Games. Essays in Game Theory and Mathematical Economics in Honor of Oskar Morgenstern, 4, 1981.
	9	R. J. Aumann and L. S. Shapley. Long-term Competition: A Game-theoretic Analysis. Dept. of Economics, Los Angeles University of California, 1992.
	10	R. Axelrod. On Six Advances in Cooperation Theory. Analyse and Kritik, 22(1):130--151, 2000.
	11	B. Bernheim and D. Ray. Collective Dynamic Consistency in Repeated Games. Games and Economic Behavior, 1(4):295--326, 1989.
	12	B. Bernheim and M. Whinston. Coalition-proof Nash equilibria. II. Applications. Journal of Economic Theory, 42(1):13--29, 1987.
	13	C. Borgs, J. Chayes, N. Immorlica, A. Kalai, V. Mirrokni, and C. Papadimitriou. The Myth of the Folk Theorem. Report 07-082, Electronic Colloquium on Computational Complexity (ECCC), 2007. ISSN 1433--8092, 14th Year, 82nd Report.
	14	E. Britannica. Encyclopaedia Britannica Online. Encyclopaedia Britannica, 2004.
	15	H. Cao and A. Arora. Stabilization in dynamic systems with varying equilibrium. In T. Masuzawa and S. Tixeuil, editors, Stabilization, Safety, and Security of Distributed Systems, 9th International Symposium, SSS 2007, Paris, France, November 14--16, 2007, volume 4838 of Lecture Notes in Computer Science, pages 67--81. Springer, 2007.
	16	A. Clement, J. Napper, H. Li, J.-P. Martin, L. Alvisi, and M. Dahlin. Theory of BAR games architecture. technical report TR-06-63, The University of Texas at Austin, Department of Computer Sciences., November 29 2006.
	17	Allen Clement , Jeff Napper , Harry Li , Jean-Philipe Martin , Lorenzo Alvisi , Michael Dahlin, Theory of BAR games, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281172]
	18	A. Dasgupta, S. Ghosh, and S. Tixeuil. Selfish stabilization. In A. K. Datta and M. Gradinariu, editors, Stabilization, Safety, and Security of Distributed Systems, 8th International Symposium, SSS 2006, Dallas, TX, USA, November 17--19, 2006, volume 4280 of Lecture Notes in Computer Science, pages 231--243. Springer, 2006.
	19	Constantinos Daskalakis , Paul W. Goldberg , Christos H. Papadimitriou, The complexity of computing a Nash equilibrium, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132527]
	20	Edsger W. Dijkstra, Self-stabilizing systems in spite of distributed control, Communications of the ACM, v.17 n.11, p.643-644, Nov. 1974 [doi>10.1145/361179.361202]
	21	Shlomi Dolev, Self-stabilization, MIT Press, Cambridge, MA, 2000
	22	S. Dolev, E. M. Schiller, and P. Spirakis. Game authority: for robust distributed selfish-computer systems. Technical report, Dynamically Evolving, Large-scale Information Systems (DELIS), 2006. Accessible via http://delis.upb.de/docs/.
	23	S. Dolev, E. M. Schiller, P. G. Spirakis, and P. Tsigas. Game authority: for robust distributed selfish-computer systems. Technical report, Department of Computer Science and Engineering, Chalmers University of Technology and Goteborg University, March 2006.
	24	Shlomi Dolev , Elad M. Schiller , Paul G. Spirakis , Philippas Tsigas, Game authority for robust andscalable distributed selfish-computer systems, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281171]
	25	K. Eliaz. Fault Tolerant Implementation. Review of Economic Studies, 69(3):589--610, 2002.
	26	Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 2007
	27	J. Y. Halpern. Computer science and game theory: A brief survey. CoRR, abs/cs/0703148, 2007.
	28	S. Hart. Robert Aumann's Game and Economic Theory. Scandinavian Journal of Economics, 108(2):185--211, 2006.
	29	Ara Hayrapetyan , Éva Tardos , Tom Wexler, The effect of collusion in congestion games, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132529]
	30	E. Kalai and W. Stanford. Finite Rationality and Interpersonal Complexity in Repeated Games. Econometrica, 56(2):397--410, 1988.
	31	Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 2006
	32	Harry C. Li , Allen Clement , Edmund L. Wong , Jeff Napper , Indrajit Roy , Lorenzo Alvisi , Michael Dahlin, BAR gossip, Proceedings of the 7th symposium on Operating systems design and implementation, November 06-08, 2006, Seattle, Washington
	33	D. Moreno and J. Wooders. Coalition-Proof Equilibrium. Games and Economic Behavior, 17(1):80--112, 1996.
	34	J. Nash. Equilibrium point in n-person games. Proc. Nat. Acad. Sci. USA, 36:48--49, 1950.
	35	Noam Nisan , Tim Roughgarden , Eva Tardos , Vijay V. Vazirani, Algorithmic Game Theory, Cambridge University Press, New York, NY, 2007
	36	M. J. Osborne and A. Rubinstein. A Course in Game Theory. MIT Press, 1994.
	37	D. Pearce. Repeated games: cooperation and rationality. Advances in Economic Theory: Sixth World Congress, 1992.
	38	A. Rubinstein. Strong perfect equilibrium in supergames. International Journal of Game Theory, 9(1):1--12, 1980.
	39	A. Rubinstein. Essays in Game Theory in Honor of Michael Maschler, chapter Equilibrium in supergames. Springer-Verlag, 1994. N. Meggido, editor.
	40	R. Selten. Spieltheoretische Behandlung eines Oligopolmodells mit Nachfragetragheit. Zeitschrift fur die gesamte Staatswissenschaft, 12:301--324, 1965.