论文标题
在随机需求下的有限资源的顺序分配
Sequential Fair Allocation of Limited Resources under Stochastic Demands
论文作者
论文摘要
我们考虑将有限的资源分配在一组代理之间的问题，并以未知（随机）实用程序依次到达。我们的目标是找到一个公平的分配 - 同时帕累托效率和嫉妒的分配。当所有实用程序都是预先知道的时，对于大型的实用程序功能，上述desiderata是可以同时实现（并且可以有效地计算）。但是，在连续的环境中，没有任何策略可以同时保证所有可能实现的效用。自然的在线公平分配目标是最大程度地减少每个代理商最终分配与事后公平分配的偏差。这可以同时保证帕累托效率和嫉妒。但是，由此产生的动态程序具有状态空间，在代理数量中是指数的。我们提出了一个简单的策略，HopeOnline，旨在使用当前的可用资源和未来实用程序的“预测”直方图“匹配”前公平分配向量。我们在受移动食品银行分配启发的数据集中证明了政策的有效性。
We consider the problem of dividing limited resources between a set of agents arriving sequentially with unknown (stochastic) utilities. Our goal is to find a fair allocation - one that is simultaneously Pareto-efficient and envy-free. When all utilities are known upfront, the above desiderata are simultaneously achievable (and efficiently computable) for a large class of utility functions. In a sequential setting, however, no policy can guarantee these desiderata simultaneously for all possible utility realizations. A natural online fair allocation objective is to minimize the deviation of each agent's final allocation from their fair allocation in hindsight. This translates into simultaneous guarantees for both Pareto-efficiency and envy-freeness. However, the resulting dynamic program has state-space which is exponential in the number of agents. We propose a simple policy, HopeOnline, that instead aims to `match' the ex-post fair allocation vector using the current available resources and `predicted' histogram of future utilities. We demonstrate the effectiveness of our policy compared to other heurstics on a dataset inspired by mobile food-bank allocations.
