We study a dynamic allocation problem in which $T$ sequentially arriving divisible resources need to be allocated to $n$ fixed agents with additive utilities. Agents' utilities are drawn stochastically from a known distribution, and decisions are made immediately and irrevocably. Most works on dynamic resource allocation aim to maximize the utilitarian welfare of the agents, which may result in unfair concentration of resources at select agents while leaving others' demands under-fulfilled. In this paper, we consider the egalitarian welfare objective instead, which aims at balancing the efficiency and fairness of the allocation. To this end, we first study a fluid-based policy derived from a deterministic approximation to the underlying problem and show that it attains a regret of order $\Theta(\sqrt{T})$ against the hindsight optimum, i.e., the optimal egalitarian allocation when all utilities are known in advance. We then propose a new policy, called Backward Infrequent Re-solving with Thresholding ($\mathsf{BIRT}$), which consists of re-solving the fluid problem at most $O(\log\log T)$ times. We prove the $\mathsf{BIRT}$ policy attains $O(1)$ regret against the hindsight optimum, independently of the time horizon length $T$ and initial welfare. We also present numerical experiments to illustrate the significant performance improvement against several benchmark policies.


翻译:我们研究一个动态的分配问题,即按顺序将美元分解的资源分配给具有添加公用事业的固定代理商。代理商的公用事业是从已知的分布中随机提取的,决定是立即和不可撤销的。大多数关于动态资源分配的工作都旨在最大限度地提高代理商的实用福利,这可能导致资源在特定代理商的不公平集中,而同时又使其他人的需求得不到充分满足。在本文件中,我们考虑平等福利目标,目的是平衡分配的效率和公平性。为此,我们首先研究一种基于流动性的政策,其取自对根本问题的确定性近似,并表明它获得了对美元(sqrt{T})的排序的遗憾,即当所有公用事业都预先知道时,最佳的平等分配。我们然后提出一项新政策,称为 " 后退再解决 ",目的是平衡分配的效率和公平性。为此,我们首先研究一项基于对根本问题的确定性近似似似似似似似似似地从一个美元(sqourta)美元(sqrorality expression) expressive $ral exision. we produceal lacialtial $rational $rus.

0
下载
关闭预览

相关内容

强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
VCIP 2022 Call for Special Session Proposals
CCF多媒体专委会
1+阅读 · 2022年4月1日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
IEEE TII Call For Papers
CCF多媒体专委会
3+阅读 · 2022年3月24日
ACM TOMM Call for Papers
CCF多媒体专委会
2+阅读 · 2022年3月23日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
vae 相关论文 表示学习 1
CreateAMind
12+阅读 · 2018年9月6日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
3+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Arxiv
0+阅读 · 2022年7月11日
Arxiv
0+阅读 · 2022年7月11日
Arxiv
0+阅读 · 2022年7月10日
VIP会员
相关资讯
VCIP 2022 Call for Special Session Proposals
CCF多媒体专委会
1+阅读 · 2022年4月1日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
IEEE TII Call For Papers
CCF多媒体专委会
3+阅读 · 2022年3月24日
ACM TOMM Call for Papers
CCF多媒体专委会
2+阅读 · 2022年3月23日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
vae 相关论文 表示学习 1
CreateAMind
12+阅读 · 2018年9月6日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
3+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员