Algorithmic and game-theoretic analysis and implementation of network design

网络问题是最基本的优化问题之一。无论通过它们传输的商品是数据还是商品，它们的设计都必须优化时间、成本或收入等指标。人们早就知道，尽管这些网络可能非常不同，但它们的建模可以捕捉到它们潜在的共同特征。这一趋势的最新表现(与网络流量、路由、容错等较早的示例一起)在研究互联网等大数据和通信网络时引入了自私行为；虽然这对大多数计算机科学家来说是一个新的范式，但经济学家和运输界已经研究了50多年。基于拍卖机制设计的网络协议设计就是这样一个例子。这项研究的目的是从算法的角度探索这些新范例在网络设计中的应用，同时研究更传统的方面，如开发、分析和实现更好的网络流和路由问题的近似算法。在一个比以往任何时候都更加相互联系的世界里，这项研究提案的预期是对信息、商品、服务等的更有效分配产生重大影响。

Network problems are among the most basic optimization problems. Whether the goods transfered through them are data or commodities they must be designed so as to optimize metrics such as time, costs, or revenue. It has been long known that although these networks may be very different, their modelling can capture their underlying common characteristics. A very recent manifestation of this trend (alongside the older examples of network flow, routing, fault tolerance etc.) is the introduction of selfish behaviour in the study of large data and communication networks such as the Internet; while this is a new paradigm for most computer scientists, it has been studied for more than 50 years by economists and the transportation community. The design of network protocols based on auction mechanism design is another such example. The purpose of this research is to explore the application of these new paradigms in network design from an algorithmic point of view, alongside the study of more `traditional' aspects such as the development, analysis and implementation of better approximation algorithms for network flow and routing problems. In a world that is more inter-connected than ever, the expectation of this research proposal is to have a significant impact on the more efficient distribution of information, goods, services etc.