Approximation and online algorithms for game theory

• Applicant: Professor Dr. Rob van Stee
• Subject Area: Theoretical Computer Science
• Term: from 2007 to 2012
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 46424266

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.

• DFG Programme: Research Grants