期刊
JOURNAL OF ECONOMIC THEORY
卷 156, 期 -, 页码 317-342出版社
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jet.2014.04.005
关键词
Atomic; Congestion; Correlated equilibrium; Price of anarchy; Splittable
类别
资金
- NSF [CCF-1016885]
- ONR Young Investigator Award
- ONR PECASE Award
- AFOSR MURI Grant
- German Academic Exchange Service (DAAD)
Congestion games are multi-player games in which players' costs are additive over a set of resources that have anonymous cost functions, with pure strategies corresponding to certain subsets of resources. In a splittable congestion game, each player can choose a convex combination of subsets of resources. We characterize the worst-case price of anarchy a quantitative measure of the inefficiency of equilibria in splittable congestion games. Our approximation guarantee is parameterized by the set of allowable resource cost functions, and degrades with the degree of nonlinearity of these cost functions. We prove that our guarantee is the best possible for every set of cost functions that satisfies mild technical conditions. We prove our guarantee using a novel local smoothness proof framework, and as a consequence the guarantee applies not only to the Nash equilibria of splittable congestion games, but also to all correlated equilibria. (C) 2014 Elsevier Inc. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据