Algorithms of Nework-sharing Games
Lead Research Organisation:
University of Liverpool
Department Name: Computer Science
Abstract
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.
Organisations
Publications
Ackermann H
(2011)
Uncoordinated Two-Sided Matching Markets
in SIAM Journal on Computing
Ackermann H
(2007)
Internet and Network Economics
Berenbrink P
(2007)
Distributed Selfish Load Balancing
in SIAM Journal on Computing
Bošnacki D
(2009)
On commutativity based Edge Lean search
in Annals of Mathematics and Artificial Intelligence
Daskalakis C
(2006)
The complexity of computing a Nash equilibrium
Elkind E
(2006)
Nash equilibria in graphical games on trees revisited
Elkind E
(2007)
Computing good nash equilibria in graphical games
Goldberg P
(2006)
Reducibility among equilibrium problems