Games on Networks and Quantifying the Resulting Solutions

点击翻译按钮获取中文摘要

The emergence of large networks like the Web and the Internet is one of the most profound shifts in focus in computer science since its perception. Unlike a single computer, these networks are simultaneously built, operated, and used by multiple parties with a diverse set of goals and with constantly changing degree of cooperation and competition. One of the main challenges faced by computer science today is to successfully build and manage systems used by such diverse set of users. The future of much of the complex technology developed today depends on our ability to ensure that participants cooperate despite their diverse goals and interests. The project uses the tools of game theory for studying the behavior of such a diverse, competing and cooperating set of users in networks modeling the interaction between parts of information and computer systems controlled by different parties. Each participant in an algorithm is viewed as a player in a non-cooperative game, where each player acts to selfishly optimize his or her own objective function. The research approaches some of the traditional algorithmic questions in networks from the perspective of game theory ranging from how networks are formed by cooperating selfish users, how such networks are used to disseminate information, how economies work on such networks. In each case the main issue considered by this project is the quality loss due to selfish behavior of the participants. The project aims to understand what are simple and natural frameworks that lead to efficient systems.