Algorithmic and game-theoretic analysis of network design

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

Is it possible for a network operator to lure network users into a certain behavior by lying to them for a very long time, especially when they are automated? Can we extend the lifetime of a solar-renewable battery used to keep traveling cars connected to the Internet? What is the best way to lay highways so that we can use the roads already built to connect cities as soon as possible on average? These are some of the problems arising during the modelling, construction, operation, and use of networks. They are addressed in this proposal by using tools from algorithmic game theory and by designing efficient approximation algorithms when those problems are proven to be computationally hard.