An increasing number of networks on the forefront of scientific research, and of great importance to our world, are developed, built, and maintained by a large number of independent agents, all of whom act in their own interests. Such networks with strategic agents include the Internet, peer-to-peer file sharing schemes, business contracts between companies, and social networks representing relationships between groups of people. While these networks cannot be fully controlled, they can often be influenced in a limited way, sometimes resulting in dramatic improvement of the global network behavior. For example, this influence can include giving a few agents incentives to behave differently, altering a small part of the network, or even providing some extra information that makes a huge difference. This project will develop methods and algorithms with provable guarantees for influencing networks of strategic agents in order to improve the overall network behavior.
This project will study the formation of various networks by strategic agents, and will especially focus on the system of customer-provider and peering contracts between Autonomous Systems (AS's) in the Internet. In the process of this research, new approximation algorithm concepts will be introduced, and will yield techniques for improving the global qualities of a network, and for preventing undesirable entities from gaining undue influence over it. While interactions of self-interested agents have been studied in numerous fields, a systematic study of how to influence such agents with only a limited amount of power has never been done. Besides contributing to algorithmic game theory and the study of networks, this research will open up new research directions in economics, AI, and the social sciences.
An increasing number of networks on the forefront of scientific research, and of great importance to our world, are developed, built, and maintained by a large number of independent agents, all of whom act in their own interests. While these networks cannot be fully controlled, they can often be influenced in a limited way, sometimes resulting in dramatic improvement of the global network behavior. This project studied when good stable outcomes exist for networks created by self-interested agents, and quantified and developed mechanisms for "nudging" the agents in order to create better stable outcomes. The focus was especially on three general types of networks (1) Physical networks, such as road networks build by several agencies with different interests, (2) Matching, for example matching students with schools or kidneys with recipients, and (3) Autonomous Systems in the Internet, who both create a network of contracts and choose how to locally route traffic to their neighbors. For these general contexts, this project resulted in insights for when good stable outcomes arise from interaction by self-interested agents, and mechanisms that can influence the participating agents to cooperate or to create better stable outcomes. The focus was on provable guarantees and algorithm design. At a very high level, the insights gained from this project are that when networks are being created by independent selfish agents (especially social networks), it is crucial to understand the incentive structure of the agents. If this structure is known and understood, then our results can be used to propose new mechanisms which will perform close-to-optimally. Moreover, our results demonstrate that in many scenarios, a small amount of targeted incentives (e.g., by the government) can be used to create much better stable solutions. While our results are very general, they are also quite abstract. The next step would be to apply the insights and algorithms from this project to more realistic case studies, e.g., to online social networks or real-world matching scenarios such as the ones mentioned above.
