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.