We consider an atomic congestion game in which each player $i$ either participates in the game with an exogenous and known probability $p_{i}\in(0,1]$, independently of everybody else, or stays out and incurs no cost. We compute the parameterized price of anarchy to characterize the impact of demand uncertainty on the efficiency of selfish behavior, considering two different notions of a social planner. A prophet planner knows the realization of the random participation in the game; the ordinary planner does not. As a consequence, a prophet planner can compute an adaptive social optimum that selects different solutions depending on the players that turn out to be active, whereas an ordinary planner faces the same uncertainty as the players and can only compute social optima with respect to the player participation distribution. For both planners, we derive the precise price of anarchy, which arises from an optimization problem parameterized by the maximum participation probability $q=\max_{i} p_{i}$. For the case of affine costs, we provide an analytic expression for the ordinary and prophet price of anarchy, parameterized as a function of $q$.


翻译:暂无翻译

0
下载
关闭预览

相关内容

【2023新书】随机模型基础,815页pdf
专知会员服务
100+阅读 · 2023年5月10日
不可错过!700+ppt《因果推理》课程!杜克大学Fan Li教程
专知会员服务
69+阅读 · 2022年7月11日
自然语言处理顶会NAACL2022最佳论文出炉!
专知会员服务
42+阅读 · 2022年6月30日
不可错过!《机器学习100讲》课程,UBC Mark Schmidt讲授
专知会员服务
73+阅读 · 2022年6月28日
专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
161+阅读 · 2020年1月16日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
国家自然科学基金
0+阅读 · 2016年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Arxiv
0+阅读 · 2023年6月22日
Arxiv
23+阅读 · 2022年2月4日
VIP会员
相关VIP内容
【2023新书】随机模型基础,815页pdf
专知会员服务
100+阅读 · 2023年5月10日
不可错过!700+ppt《因果推理》课程!杜克大学Fan Li教程
专知会员服务
69+阅读 · 2022年7月11日
自然语言处理顶会NAACL2022最佳论文出炉!
专知会员服务
42+阅读 · 2022年6月30日
不可错过!《机器学习100讲》课程,UBC Mark Schmidt讲授
专知会员服务
73+阅读 · 2022年6月28日
专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
161+阅读 · 2020年1月16日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
相关基金
国家自然科学基金
0+阅读 · 2016年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员