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.