本文研究了在具有加法估值函数的代理之间对不可分割混合资源的在线公平分配。在标准的在线模型中，每个时间步到达一个不可分割的物品；每个代理可以为其分配一个正值、负值或零值，并且必须在下一个物品到达之前不可逆地分配该物品。
我们希望保持一定的公平性保证，重点关注无嫉妒性（EF）及其最重要的放松形式之一：至多一项的无嫉妒性（EF1）。由于在没有额外假设的情况下，该问题的强负结果和稀缺正结果，我们通过引入缓冲区来增强算法，允许存储和重新排列有限数量的物品。
这种设置自然地介于完全在线情况（无缓冲区）和完全离线情况（缓冲区足够大以容纳所有物品）之间。我们表明，配备合理大小缓冲区的算法可以为个性化的 $k$-值实例提供强保证，即每个代理对物品分配至多 $k$ 个不同值的实例。
具体而言，我们构造了在每个时间步都是 EF1、在大多数时间步都是 EF 的分配，使用的缓冲区大小与 $k$ 和代理数量成线性关系。我们的方法依赖于新颖的组合论证以及构造一系列无嫉妒的匹配来分配大多数物品。
最后，我们将结果扩展到一般的加法估值函数，并依赖于同符号两个值之间的最大每代理比率。此外，我们还通过对使用较小缓冲区的不可行性结果识别了我们方法的局限性。
博主点评： 本研究将在线公平分配与重排序缓冲区结合，探索了在复杂资源分配场景中如何保持公平性。这一方法不仅增强了传统在线算法的能力，还为未来的研究提供了新的思路，尤其是在处理不可分割资源时的灵活性和效率。该研究的结合创新为公平性理论提供了实用的算法保障，值得深入关注。