Algorithms of Nework-sharing Games

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

We consider game-theoretic situations in which a set of users wish to carry out tasks using a set of shared resources. (Examples include road traffic and computer network traffic.) The cost of using a resource depends on the amount of usage it attracts, and increases in proportion with usage.If users are free to modify their choices based on the observed costs of resources, they will tend to distribute themselves evenly over the resources. We expect them to find a Nash equilibrium, in which no user cam modify her selection so as to reduce her cost.For some instances of these congestion games there may be many possible Nash equilibria, and this raises the research questions of how they vary in overall cost, and how hard it is to find the best and the worst. Also, whether some Nash equilibria are more plausible than others on the grounds that that are in some sense more stable. Other questions relate to the time taken by algorithms to find Nash equilibria. The focus of the proposed research is on standard rather than ad-hoc algorithms that may be used to find Nash equilibria, for example randomized search techniques that have been studied in the context of other optimization problems, and standard game-theoretic approaches such as fictitious play. We propose to study the types of equilibria found by these algorithms, and the time taken by them to converge.