A Unified Framework for Pricing in Nonconvex Resource Allocation Games
研究非凸资源分配博弈中如何通过定价实现目标资源消耗，提出基于对偶和凸化技术的统一框架，适用于交通收费、瓦尔拉斯均衡、交易网络和拥塞控制等领域。
We consider a basic nonconvex resource allocation game, where the players’ strategy spaces are subsets of and cost functions are parameterized by some common vector and, otherwise, only depend on their 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. Resources can be priced, that is, the game is augmented by a price vector and players have quasi-linear overall costs, meaning that in addition to the original costs, a player needs to pay the corresponding price per consumed unit. We investigate the following question: for which aggregated consumption vectors can we find prices that induce an equilibrium realizing the targeted consumption profile? For answering this question, we revisit a duality-based framework and derive a new characterization of the existence of such and using convexification techniques. Our characterization implies the following result: If strategy spaces of players are bounded linear mixed-integer sets and the cost functions are linear or even concave, the equilibrium existence problem reduces to solving a well-structured LP. We then consider aggregate formulations assuming that cost functions are additive over resources and homogeneous among players. We derive a characterization of enforceable consumption vectors , showing that is enforceable if and only if is a minimizer of a certain convex optimization problem with a linear functional. We demonstrate that this framework can unify parts of four largely independent streams in the literature: tolls in transportation systems, Walrasian equilibria, trading networks, and congestion control. Besides reproving existing results we establish new enforceability results for these domains as well.