Utilitarian resource assignment

DOI10.1016/J.JDA.2005.06.009MaRDI QIDQ866544zbMATH OpenOpenAlexFDO

Authors Petra Berenbrink, Leslie Ann Goldberg, Paul W. Goldberg, Russell Martin

Publication date 14 February 2007

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0410018

(n)-person games, (n>2) (91A06) Applications of game theory (91A80) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

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_{i} n f t y$ 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.

Review text

The paper deals with the optimal resource allocation. Ther is a finite number of tasks and finite number of resources. To every task there should be assigned a resource. The authors investigate this problem from a game-theoretic point of view. Tasks are considered as agents, choice of a resource as a strategy. Instead of payoffs there are costs of assignments. The individual cost due to a task (agent) depends on the type of the resource, the size of a task and the sizes of all other tasks assigned to the same resource. The authors study the Nash equilibria for the individual costs. Their main goal is to estimate the ratio of the global cost (i.e. the sum of all individual costs) of such a Nash equilibrium and the minimal global cost.

Recommendations

Cites work

Cited in

(16)

This page was built for publication: Utilitarian resource assignment

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q866544)