Conflicting Congestion Effects in Resource Allocation Games

Michal Feldman () and Tami Tamir ()
Additional contact information
Michal Feldman: School of Business Administration and Center for the Study of Rationality, Hebrew University of Jerusalem, Jerusalem 91905, Israel
Tami Tamir: School of Computer Science, The Interdisciplinary Center, Herzliya, Herzliya 46150, Israel

Operations Research, 2012, vol. 60, issue 3, 529-540

Abstract: We study strategic resource allocation settings, where jobs correspond to self-interested players who choose resources with the objective of minimizing their individual cost. Our framework departs from the existing game-theoretic models mainly in assuming conflicting congestion effects, but also in assuming an unlimited supply of resources. In our model, a job's cost is composed of both its resource's load (which increases with congestion) and its share in the resource's activation cost (which decreases with congestion). We provide results for a job-scheduling setting with heterogeneous jobs and identical machines.We show that if the resource's activation cost is shared equally among its users, a pure Nash equilibrium (NE) might not exist. In contrast, the proportional sharing rule induces a game that admits a pure NE, which can also be computed in polynomial time. As part of the algorithm's analysis, we establish a new, nontrivial property of schedules obtained by the longest processing time algorithm. We also observe that, unlike in congestion games, best-response dynamics (BRD) are not guaranteed to converge to a Nash equilibrium. Finally, we measure the inefficiency of equilibria with respect to the minimax objective function, and prove that there is no universal bound for the worst-case inefficiency (as quantified by the “price of anarchy” measure). However, the best-case inefficiency (quantified by the “price of stability” measure) is bounded by 5/4, and this is tight. These results add another layer to the growing literature on the price of anarchy and stability, which studies the extent to which selfish behavior affects system efficiency.

Keywords: congestion games; cost sharing games; job scheduling; potential games; price of anarchy; price of stability; equilibrium existence (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1120.1051 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:60:y:2012:i:3:p:529-540

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().