Approximation and online algorithms for game theory

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

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.