max planck institut
informatik
informatik
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, there are two main directions in which we work, using techniques from online algorithms and approximation algorithms. The first is that of 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 algorithms for such problems.
The second main direction is that of coordination mechanisms, which try to minimize performance loss by distinguishing between agents and encourage them towards socially better choices in different ways (not necessarily in a truthful way), e.g. by introducing artificial delays. We are interested in comparing Nash equilibria to the optimal solution that could be reached in a centralized setting, where there is a single controller and no freedom for the agents. The price of stability is the ratio of best equilibrium and the best optimal design. The best Nash equilibrium is the optimal solution that can be proposed from which no user will 'defect'. Taking another point of view, we are also interested in evaluating the loss to the system due to its deliberate lack of coordination. Understanding the worst-case distance of a Nash equilibrium from the social optimum in simple situations is also a prerequisite for making progress in the area of (algorithmic) mechanism design. This worst-case distance is known as the coordination ratio or the price of anarchy.
Our second main topic is online algorithms, with a focus on various scheduling and bin packing problems. In online problems, the input arrives incrementally and irrevocable decisions need to be made before the complete input is known. The performance of algorithms in this setting is then compared to the best possible output with complete knowledge of the input. Thus, the focus here is on the limitations caused by a lack of information, as opposed to the limitations caused by a lack of running time (approximation algorithms).
Note that online problems are also a kind of algorithmic games, since there is a contest between the online algorithm (that tries to achieve a low competitive ratio) and the optimal offline algorithm, also called the adversary, that tries to force a high competitive ratio.