资源论文Dynamic Fair Division Problem with General Valuations

Dynamic Fair Division Problem with General Valuations

2019-11-05 | |  51 |   30 |   0
Abstract 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 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. Then by constructing the adversary instances such that all dynamic algorithms must be at least ?(1)-proportional and ?( logn n )-envy-free, we show that the bounds are tight up to a logarithmic factor. Moreover, we introduce a setting where the players’ valuations are uniform on the resource but with different demands, which generalizes the setting of [Friedman et al., 2015]. We prove an O(log n) upper bound and a tight lower bound for this case.

上一篇:Tractable (Simple) Contests

下一篇:Integrating Demand Response and Renewable Energy in Wholesale Market

用户评价
全部评价

热门资源

  • Learning to Predi...

    Much of model-based reinforcement learning invo...

  • Stratified Strate...

    In this paper we introduce Stratified Strategy ...

  • The Variational S...

    Unlike traditional images which do not offer in...

  • A Mathematical Mo...

    Direct democracy, where each voter casts one vo...

  • Rating-Boosted La...

    The performance of a recommendation system reli...