TU Berlin

Internet Network ArchitecturesAll Publications

Page Content

to Navigation

All publications

The Price of Malice: A Game-Theoretic Framework for Malicious Behavior in Distributed Systems
Citation key MSW-PMGTFMBDS-09
Author Moscibroda, Thomas and Schmid, Stefan and Wattenhofer, Roger
Pages 125–155
Year 2009
ISSN 1542-7951
Journal Internet Mathematics (IM)
Volume 6
Number 2
Abstract Over the last years, game theory has provided insights into the behavior of distributed systems by modeling the players as utility maximizing agents. In particular, it has been shown that selfishness causes many systems to perform in a globally suboptimal fashion. Such systems are said to have a large Price of Anarchy. In this article, we extend this field of research by allowing some players to be malicious rather than selfish. We ask: What is the impact of malicious players on the system consisting of otherwise selfish players? In particular, we introduce the Price of Malice as a measure that captures how much the system's efficiency degrades in the presence of malicious players, compared to a purely selfish environment. As a specific example, we analyze the Price of Malice of a game which models the containment of the spread of viruses. In this game, each player or node can choose whether or not to install anti-virus software. Then, a virus starts from a random node and recursively infects all neighboring nodes which are not inoculated. We establish various results about this game. For instance, we quantify how much the presence of malicious players can deteriorate or–in case of highly risk-averse selfish players–improve the social welfare of the distributed system.
Link to publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe