We study the problem of dynamically allocating indivisible items to a group of agents in a fair manner. We assume that the items are goods and the valuation functions are additive without specification. Due to the negative results to achieve fairness, we allow adjustments to make fairness attainable with the objective to minimize the number of adjustments. We obtain positive results to achieve EF1 for the default setting, restricted additive or general identical valuations, and two agents with mixed manna. We further impose the contiguity constraint on the items and require that each agent obtains a consecutive block of items. We obtain both positive and negative results to achieve either EF1 or proportionality with an additive approximate factor. In particular, we establish matching lower and upper bounds to achieve approximate proportionality for identical valuations. Our results exhibit the large discrepancy between the identical model and nonidentical model in both contiguous and noncontiguous settings. All our positive results are computationally efficient.
翻译:我们以公平的方式研究将不可分割的物品动态地分配给一组代理人的问题,我们假定这些物品是货物,估价功能是不加具体说明的附加物。由于实现公平的消极结果,我们允许作出调整,以便实现公平,目的是尽量减少调整的数量。我们取得了积极结果,以便在默认设定、限制性添加物或一般相同估值以及两种混合配方配方的代理物中实现EF1。我们进一步对这些物品实行毗连性限制,并要求每个代理人获得连续的一组物品。我们取得正和负结果,既能达到EF1,又能达到一个添加物近似系数的相称性。特别是,我们建立了匹配的下限和上限,以达到相同估值的近似相称性。我们的结果显示,在相毗连和不相连的环境下,相同的模型和非相同的模型和不相同的模型之间存在很大的差异。我们所有的积极结果都是计算效率的。