We consider resource allocation games with heterogeneous users and identical resources. In the
game theoretic approach each job chooses a resource in attempt to minimize its incurred cost.
Most of the previous work has considered cost structures with either negative congestion effects (e.g., job scheduling and
network routing games), where a job prefers to be assigned to a lightly-loaded resource, or positive congestion effects (e.g., cost sharing in network design games), where a job prefers to share its resource with many jobs.
Practically, a job assigned to some resource incurs a cost which is composed of both
its load and its share in the resource's activation cost, thus both effects take place simultaneously.
We study resource allocation games with a cost function that encompasses both the positive and the negative congestion effects.
We consider two sharing rules of the activation cost, namely \emph{uniform}, where the resource's
activation cost is shared equally among its users, and \emph{proportional}, where the resource's activation cost is shared among its users
proportionally to their size. We also challenge the assumption that there exists a fixed set of resources, and consider settings with both limited and unlimited set of resources.
We provide results with respect to equilibrium existence,
computation, convergence and quality. We show that under the uniform
sharing rule a pure Nash equilibrium (NE) might not exist. In
contrast, under the proportional sharing rule, a pure NE always
exists. Moreover, we provide an algorithm for computing a NE in
polynomial time. Yet, starting at an arbitrary profile of actions,
best-response dynamics might not converge to a NE. In addition, we
provide tight bounds for the price of anarchy (i.e., ratio between
the worst NE and the social optimum) and show that even the best NE
might not be optimal.
our framework to obtain the same approximation ratio for this
problem. To the best of our knowledge, this is the first time the
theoretical bound of$1-e^{-1}$ is (almost) matched for both of these problems.