Dynamic Fair Division Problem with General Valuations
Dynamic Fair Division Problem with General Valuations
复制标题
一般估值的动态公平分配问题
DOI：
10.24963/ijcai.2018/52
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Yingkai Li
中科院分区：
文献类型：
--
作者：
Bo Li;Yingkai Li
在本文中，我们关注的是如何在n个随着时间的推移到达和离开的玩家之间公平地动态分配可分割的资源。玩家可能对资源有不同的估值。众所周知，在动态环境下，精确的无嫉妒分配和比例分配可能不存在[Walsh， 2011]。因此，我们将研究在动态环境下，我们能在多大程度上保证公平。我们首先设计了两种O(log n)-比例和O(n)-无嫉妒的算法，用于一般估值的设置，并通过构造对手实例，使得所有动态算法必须至少是Omega(1)-比例和Omega(n/log n)-无嫉妒，我们证明了边界紧密到一个对数因子。此外，我们引入了参与者对资源的估值一致但需求不同的设置，这概括了[Friedman et al.， 2015]的设置。在这种情况下，我们证明了一个O（log n）的上界和一个紧密的下界。
In this paper, we focus on how to dynamically allocate a divisible resource fairly among n players who arrive and depart over time. The players may have general heterogeneous valuations over the resource. It is known that the exact envy-free and proportional allocations may not exist in the dynamic setting [Walsh, 2011]. Thus, we will study to what extent we can guarantee the fairness in the dynamic setting. We first design two algorithms which are O(log n)-proportional and O(n)-envy-free for the setting with general valuations, and by constructing the adversary instances such that all dynamic algorithms must be at least Omega(1)-proportional and Omega(n/log n)-envy-free, we show that the bounds are tight up to a logarithmic factor. Moreover, we introduce the setting where the players' valuations are uniform on the resource but with different demands, which generalize the setting of [Friedman et al., 2015]. We prove an O(log n) upper bound and a tight lower bound for this case.