ALCOMFT-TR-03-107

Paul Wilfred Goldberg
Bounds for the Convergence Rate of Randomized Local Search in a Multiplayer, Uniform Resource Sharing Game
Warwick. Work package 4. November 2003.

Abstract: This paper studies a resource sharing game introduced by Koutsoupias and Papadimitriou, that is intended to model a set of users who share several internet-based resources. Some of the recent work on this topic has considered the problem of constructing Nash equilibria, which are choices of actions where each user has optimal utility given the actions of the other users. A related (harder) problem is to find sequences of utility-improving moves that lead to a Nash equilibrium, starting from some given assignment of resources to users.

We consider the special case where all resources are the same as each other. It is known already that there exist efficient algorithms for finding Nash equilibria; our contribution here is to show furthermore that Nash equilibria for this type of game are reached rapidly by Randomized Local Search, a simple generic method for local optimization. Our motivation for studying Randomized Local Search is that (as we show) it can be realised by a simple distributed network of users that act selfishly, have no central control and only interact via the effect they have on the cost functions of resources.

Postscript file: ALCOMFT-TR-03-107.ps.gz (120 kb).