Pricing in Resource Allocation Games Based on Duality Gaps
share
We consider a basic resource allocation game, where the players' strategy spaces are subsets of R^m and cost/utility functions are parameterized by some common vector u and, otherwise, only depend on the own strategy choice. A strategy of a player can be interpreted as a vector of resource consumption and a joint strategy profile naturally leads to an aggregate consumption vector. We assume that resources can be priced, that is, the game is augmented by a price vector λ∈R^m_+ and players have quasi-linear overall costs/utilities meaning that in addition to the original costs/utilities, a player needs to pay the corresponding price per consumed unit. We investigate the following question: for which aggregated consumption vectors u can we find prices λ that induce an equilibrium realizing the targeted consumption profile? For answering this question, we develop a duality-based framework and derive a characterization of the existence of such u and λ. We show that our characterization can help to unify parts of three largely independent streams in the literature -- tolls in transportation systems, Walrasian market equilibria and congestion control in communication networks. Besides reproving existing results we establish novel existence results by drawing connections to polyhedral combinatorics and discrete convexity.
READ FULL TEXT