Algorithms of Nework-sharing Games

网络共享游戏算法

基本信息

批准号：
GR/T07343/02
负责人：
Paul Wilfred Goldberg
金额：
--
依托单位：
University of Liverpool
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2006
资助国家：
英国
起止时间：
2006 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=GR%2FT07343%2F02
关键词：
Algorithms 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.

我们考虑游戏理论情况，其中一组用户希望使用一组共享资源执行任务。（示例包括道路流量和计算机网络流量。）使用资源的成本取决于其吸引的使用量，并与使用成比例增加。如果用户可以根据观察到的资源成本自由修改自己的选择，那么他们将倾向于在资源上均匀地分配自己。我们希望他们能找到NASH均衡，在这种情况下，没有用户凸轮修改她的选择以降低她的成本。对于这些拥堵游戏的某些情况，可能会有许多可能的NASH均衡，这提出了有关它们如何变化的整体成本，以及找到最佳和最差的研究问题。同样，某些纳什均衡是否比其他平衡更合理，因为在某种意义上是更稳定的理由。其他问题涉及算法在找到NASH均衡的时间。拟议的研究的重点是可用于查找NASH均衡的标准而不是临时算法，例如在其他优化问题的背景下进行了研究的随机搜索技术以及标准的游戏理论方法，例如虚拟游戏。我们建议研究这些算法发现的平衡类型，以及它们收敛的时间。

项目成果

期刊论文数量（9）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Reducibility among equilibrium problems

DOI：
10.1145/1132516.1132526
发表时间：
2006-01-01
期刊：
STOC'06. Proceedings of the 38th Annual ACM Symposium on Theory of Computing
影响因子：
0
作者：
Goldberg, P. W.;Papadimitriou, C. H.
通讯作者：
Papadimitriou, C. H.

Internet and Network Economics

互联网和网络经济学

DOI：
10.1007/978-3-642-10841-9_6
发表时间：
2009
期刊：
影响因子：
0
作者：
Briest P
通讯作者：
Briest P

The complexity of computing a Nash equilibrium

DOI：
10.1145/1132516.1132527
发表时间：
2006-01-01
期刊：
STOC'06. Proceedings of the 38th Annual ACM Symposium on Theory of Computing
影响因子：
0
作者：
Daskalakis, C.;Goldberg, P. W.;Papadimitriou, C. H.
通讯作者：
Papadimitriou, C. H.

Frugality ratios and improved truthful mechanisms for vertex cover