摘要

本文探讨了在服务提供者和任务分配中，当拒绝选项不可用时，如何设计一个对双方都公平的策略。文章将问题建模为二分图中的在线匹配问题，并解决了两个最小-最大问题：一个是最小化任务的最大等待时间，另一个是最小化服务提供者的最大工作负载。通过线性规划方法，文章展示了如何高效地解决第二个问题，并保持对第一个问题的合理近似。文章还开发了新颖的方法，利用这两个最小-最大问题，并通过大量模拟实验验证了基于线性规划的启发式方法的显著性能。

原理

文章通过将任务分配给服务提供者的问题建模为二分图中的在线匹配问题，其中服务提供者和服务任务分别位于图的两边，边表示服务提供者执行特定类型任务的资格。文章提出了两个最小-最大问题：FAIR-T（最小化任务的最大相对等待时间）和FAIR-S（最小化服务提供者的最大工作负载）。通过线性规划（LP）方法，文章能够高效地解决FAIR-S问题，并展示了如何利用FAIR-S的解决方案来近似FAIR-T问题的解决方案。文章还提供了近似比的证明，并通过模拟实验验证了这些方法的有效性。

流程

文章提出的算法包括一个离线阶段和一个在线阶段。在离线阶段，算法解决FAIR-T或FAIR-S问题，并计算出任务分配给服务提供者的概率。在在线阶段，当任务到达时，算法根据离线阶段计算的概率随机选择一个服务提供者进行分配。文章还提出了一个启发式方法，该方法优先将任务分配给空闲的服务提供者，以减少任务的等待时间。

应用

文章提出的方法适用于需要动态分配任务给服务提供者的各种应用场景，如自动驾驶车辆的远程操作、在线广告匹配等。通过确保任务分配的公平性，可以提高服务提供者和任务用户的满意度，从而在多个行业中具有广泛的应用前景。