The Worst-Case Efficiency of Cost Sharing Methods in Resource Allocation Games

Tobias Harks () and Konstantin Miller ()
Additional contact information
Tobias Harks: Department of Quantitative Economics, Maastricht University, 6200 MD Maastricht, The Netherlands
Konstantin Miller: Telecommunication Networks Group, Technische Universität Berlin, 10587 Berlin, Germany

Operations Research, 2011, vol. 59, issue 6, 1491-1503

Abstract: Resource allocation problems play a key role in many applications, including traffic networks, telecommunication networks, and economics. In most applications, the allocation of resources is determined by a finite number of independent players, each optimizing an individual objective function. An important question in all these applications is the degree of suboptimality caused by selfish resource allocation. We consider the worst-case efficiency of cost sharing methods in resource allocation games in terms of the ratio of the minimum guaranteed surplus of a Nash equilibrium and the maximal surplus. Our main technical result is an upper bound on the efficiency loss that depends on the class of allowable cost functions and the class of allowable cost sharing methods. We demonstrate the power of this bound by evaluating the worst-case efficiency loss for three well-known cost sharing methods: incremental cost sharing, marginal cost pricing, and average cost sharing.

Keywords: resource allocation games; cost sharing methods; network routing games; marginal cost pricing; inefficiency of equilibria (search for similar items in EconPapers)
Date: 2011
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.1110.0979 (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:59:y:2011:i:6:p:1491-1503

Access Statistics for this article

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