The Library
Utilitarian resource assignment
Tools
Tools
Tools
Berenbrink, Petra, Goldberg, Leslie Ann, Goldberg, Paul W. and Martin, R. (Russell) (2004) Utilitarian resource assignment. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)
|
PDF
WRAP_cs-rr-405.pdf - Other - Requires a PDF viewer. Download (257Kb) | Preview |
Abstract
This paper studies a resource allocation problem introduced by Koutsoupias and Papadimitriou. The scenario is modelled as a multiple-player game in which each player selects one of a finite number of known resources. The cost to the player is the total weight of all players who choose that resource, multiplied by the ``delay'' of that resource. Recent papers have studied the Nash equilibria and social optima of this game in terms of the L_{infinity} cost metric, in which the social cost is taken to be the maximum cost to any player. We study the L_1 variant of this game, in which the social cost is taken to be the sum of the costs to the individual players, rather than the maximum of these costs. We give bounds on the size of the coordination ratio, which is the ratio between the social cost incurred by selfish behavior and the optimal social cost; we also study the algorithmic problem of finding optimal (lowest-cost) assignments and Nash Equilibria. Additionally, we obtain bounds on the ratio between alternative Nash equilibria for some special cases of the problem.
| Item Type: | Report | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Library of Congress Subject Headings (LCSH): | Resource allocation, L1 algebras | ||||
| Series Name: | Department of Computer Science research report | ||||
| Publisher: | University of Warwick. Department of Computer Science | ||||
| Official Date: | 2004 | ||||
| Dates: |
|
||||
| Number: | Number 405 | ||||
| Number of Pages: | 19 | ||||
| DOI: | CS-RR-405 | ||||
| Institution: | University of Warwick | ||||
| Theses Department: | Department of Computer Science | ||||
| Status: | Not Peer Reviewed | ||||
| Publication Status: | Unpublished | ||||
| Funder: | Sixth Framework Programme (European Commission) (FP6) | ||||
| Grant number: | IST-1999-14186 (ALCOM-FT) (FP6), IST-1999-14036 (RAND-APX) (FP6) | ||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
