Approximation and online algorithms for game theory

互联网用户和服务提供商的行为是自私和自发的，没有监督和调节网络运行的权威，以实现某种社会最优，如最小总时延。一个有趣而热门的问题是，这会导致多大的性能损失。这就产生了新的算法问题，我们调查缺乏协调的成本，而不是缺乏信息(在线算法)或缺乏无限的计算资源(近似算法)。我们今天正在开发的许多复杂技术的未来取决于我们确保参与者合作的能力，尽管他们的目标和利益不同。意识到一些性能损失是不可避免的，我计划使用在线算法和近似算法中的技术来在这个有趣和具有挑战性的领域获得进一步的结果。特别是，我将继续致力于算法机制设计，重点是让自私的代理透露他们真正的私人数据，以优化性能。这需要使用拍卖机制，或者(更经常的)为手头的问题设计合适的(单调)近似算法。在互联网的背景下，用户不断地出现和消失，考虑在线(好的或及时的)算法来解决这类问题也是很自然和重要的。

Internet users and service providers act selfishly and spontaneously, without an authority that monitors and regulates network operation in order to achieve some social optimum such as minimum total delay. An interesting and topical question is how much performance is lost because of this. This generates new algorithmic problems, in which we investigate the cost of the lack of coordination, as opposed to the lack of information (online algorithms) or the lack of unbounded computational resources (approximation algorithms). The future of much of the complex technology that we are developing today depends on our ability to ensure that participants cooperate despite their diverse goals and interests. Realizing that some performance loss is unavoidable, I plan to use techniques from online algorithms and approximation algorithms to get further results in this interesting and challenging area. In particular, I will continue to work on algorithmic mechanism design, which focuses on getting selfish agents to reveal their true private data in order to optimize performance. This requires using an auction mechanism or (more often) designing suitable (monotone) approximation algorithms for the problem at hand. In the context of the Internet, where users appear and disappear continuously, it is also natural and important to consider online (nice or prompt) algorithms for such problems.