Algorithmic Tools for Games with Applications to E-Commerce and Networks

• Antragsteller: Professor Dr. Piotr Krysta
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2004 bis 2008
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5423618

Many of the practical optimization problems are difficult for computers. That is, when the size of the input data increases, the time needed for a computer also becomes extremely large. The real life applications coming from the Internet introduce the additional difficulties that we do not have the precise input data and the users (agents) behave selfishly. The data is a private property of the agents, and they usually tend to maximize their own benefit. In such situations the algorithm has to additionally ``force'' the agents to cooperate for the common welfare. This falls into the classical paradigm of non-cooperative game theory, and, in particular mechanism design. The central solution concepts here are dominant strategies and a notion of Nash equilibria: changing the strategy of a single agent cannot improve its own profit. The main idea behind mechanism design is to find an algorithm, called a mechanism, that makes payments to the agents to motivate them to report their private data truthfully. Game theory and mechanism design have been studied by economists and game theorists for decades, but only very recently by computer scientists. The reason for this arises from modeling situations that naturally occur in the Internet, and many applications there, e.g., networking protocols, electronic commerce, non-cooperative software agents, etc. Hence, efficient algorithmic solutions for problems related to economics, game theory and mechanism design are needed. We plan to work on the design of algorithmic tools for such problems, where we address the fundamental theoretical questions and aim at solutions that would also have practical impact. The main research areas we would like to address are related to auctions, network design with selfish agents, strategies for playing games and algorithmic aspects of equilibria. Our main tools come from approximation algorithms, combinatorial optimization, and probabilistic analysis. We would like to point here that using the tools from approximation algorithms to deal with the problems motivated by game theory is a quite new research direction. The results obtained so far towards this direction are very encouraging, but still there are lots of interesting and challenging open problems.

• DFG-Verfahren: Emmy Noether-Nachwuchsgruppen (Aktionsplan Informatik)
• Internationaler Bezug: Großbritannien