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. The use of game-theoretical concepts to model environments with competitive entities has been the field of economists for many years. Algorithmic game theory is particularly suited for studying networks of selfish users and/or operators. The proposed work aspires to a paradigm shift in the use of algorithmic game theory from one-shot games to repeated games that now include a history of previous plays. We propose to do that by exploiting the constraints imposed on the players due to their automated (algorithmic) nature. Hence, the proposed work should reveal new connections between computer science and economics through the big volume of work already done by economists on repeated games and reputation effects. On a more practical level, the proposal introduces a new set of problems in approximation algorithms that are related to energy conservation and infrastructure construction in networks. Although more limited in scope than the objectives above, they nevertheless present us with the opportunity of immediate impact on the environment (by, for example, the clever scheduling of energy dispensation used for data transmission) or the cost of network infrastructure (by, for example, the time-efficient scheduling of building new roads). Such problems are usually hard to solve exactly, and, therefore, we propose the development of algorithms that produce provably good approximate solutions.