Algorithmic game theory and graph theory

点击翻译按钮获取中文摘要

Fundamental problems in computer science revolve around the discovery of efficient algorithms. In the past 5-6 years, computer scientists have witnessed an explosive growth of interest in algorithmic game theory which deals with models where there are no trusted coordinator and the outcome depends on the cooperation or competition by parties of different interests. One aspect of my research will focus on network routing and its generalizations as a non-cooperative game - a line of research in algorithmic game theory. As an example, this work includes a precise analysis of the extension of the classical selfish routing model to the model in which we incorporate the concept of "time" (when all users of a link do not experience the same latency).