University of Konstanz
Graduiertenkolleg / PhD Program
Computer and Information Science

Graduation Talks


Clustering and optimization under distributed competition


Martin Hoefer, University Konstanz
Konstanz, Germany

date & place

Wednesday, 29.11.2006, 15:15 h
Room C252


Combinatorial optimization problems have long been studied in the area of efficient algorithms. In recent years the emergence of the Internet and the ever-growing size of the instances motivated the study of new distributed and competitive formulations. They capture the selfish nature of independent agents that build, maintain and operate in the Internet. Solution approaches in these models pose questions about cooperation and coordination of distributed rational agents. Under which conditions are they motivated to contribute towards a global optimum solution? How efficient is a solution that independent agents can agree upon? How hard is it to calculate stable outcomes?

The thesis considers two frameworks that allow to introduce competition into optimization. The resulting non-cooperative games can be used to model a wide range of problems including e.g. covering problems, network design, facility location, clustering, or the development of social networks. The thesis characterizes structure, efficiency and complexity of stable solutions, which are pure-strategy exact and approximate Nash equilibria. In general, cheap exact Nash equilibria might not exist or might be NP-hard to find. There are, however, cheap and stable approximate Nash equilibria, which represent a trade-off between efficiency, computational complexity and stability. Several special classes of games are analyzed, in which Nash equilibria are guaranteed to exist, to be as cheap as the optimum solution and/or to be polynomial-time computable.