Loading...
Please wait, while we are loading the content...
Similar Documents
Bounds for the Convergence . . . (2004)
| Content Provider | CiteSeerX |
|---|---|
| Author | Goldberg, Paul W. |
| Abstract | This paper studies a load balancing 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. |
| File Format | |
| Publisher Date | 2004-01-01 |
| Access Restriction | Open |
| Subject Keyword | Nash Equilibrium Randomized Local Search Utility-improving Move Share Several Internet-based Resource Efficient Algorithm Central Control Load Balancing Game Local Optimization Simple Generic Method Optimal Utility Simple Distributed Network Cost Function Paper Study Special Case Recent Work |
| Content Type | Text |
| Resource Type | Article |
