AF: Small: Influencing and Improving Networks Formed by Strategic Agents

影响和改善由战略代理人形成的网络越来越多的处于科学研究前沿的、对我们的世界非常重要的网络是由大量独立的代理人开发、建立和维护的，所有这些独立的代理人都为自己的利益行事。这种具有战略代理的网络包括互联网、点对点文件共享方案、公司之间的商业合同，以及代表人群之间关系的社交网络。虽然这些网络不能完全控制，但它们通常会以有限的方式受到影响，有时会导致全球网络行为的显著改善。例如，这种影响可以包括激励一些代理改变行为，改变网络的一小部分，甚至提供一些额外的信息，使之产生巨大的不同。本项目将开发具有可证明保证的影响战略代理网络的方法和算法，以改善整体网络行为。本项目将研究由战略代理形成的各种网络，并将特别关注客户-提供商系统和互联网中自治系统(AS)之间的对等合同系统。在这项研究的过程中，将引入新的近似算法概念，并将产生一些技术来改善网络的全局质量，并防止不受欢迎的实体对网络产生不适当的影响。虽然自利代理人之间的相互作用已经在许多领域得到了研究，但关于如何仅用有限的权力来影响这类代理人的系统研究从未进行过。除了对算法博弈论和网络研究做出贡献外，这项研究还将在经济学、人工智能和社会科学方面开辟新的研究方向。

Influencing and Improving Networks Formed by Strategic AgentsAn 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.