--- title: "Design a Win-Win Strategy That Is Fair to Both Service Providers and Tasks When Rejection Is Not an Option" authors: - "Yohai Trabelsi" - "Pan Xu" - "Sarit Kraus" doi: "10.24963/ijcai.2024/29" url: "https://ijcai.org/proceedings/2024/29" pdf: "https://ijcai.org/proceedings/2024/0029.pdf" venue: "Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence" year: 2024 pages: "257-264" track: "Main Track" keywords: - "Agent-based and Multi-agent Systems: MAS: Resource allocation" --- # Design a Win-Win Strategy That Is Fair to Both Service Providers and Tasks When Rejection Is Not an Option Yohai Trabelsi, Pan Xu, Sarit Kraus *Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence*, pages 257-264. DOI: [10.24963/ijcai.2024/29](https://doi.org/10.24963/ijcai.2024/29) ## Abstract Assigning tasks to service providers is a frequent procedure across various applications. Often the tasks arrive dynamically while the service providers remain static. Preventing task rejection caused by service provider overload is of utmost significance. To ensure a positive experience in relevant applications for both service providers and tasks, fairness must be considered. To address the issue, we model the problem as an online matching within a bipartite graph and tackle two minimax problems: one focuses on minimizing the highest waiting time of a task, while the other aims to minimize the highest workload of a service provider. We show that the second problem can be expressed as a linear program and thus solved efficiently while maintaining a reasonable approximation to the objective of the first problem. We developed novel methods that utilize the two minimax problems. We conducted extensive simulation experiments using real data and demonstrated that our novel heuristics, based on the linear program, performed remarkably well. ## Full text ## 1 Introduction In resource allocation, numerous problems can be represented as online matching in bipartite graphs. One side of the graph comprises service providers (interchangeably called workers in this paper), while the other consists of allocated task types. The graph's edges indicate the qualifications of service providers to perform tasks of specific types. In online matching problems, a common scenario involves one dynamic side and one static side. This dynamic-static setup finds application in various contexts, such as matching riders(dynamic) to drivers(static) [Dickerson et al., 2021], connecting search queries(dynamic) to advertisers in sponsored search(static) [Delong et al., 2022], and facilitating the teleoperation of autonomous vehicles (AVs) [Ackerman Viden et al., 2023]. The primary objective in these problems is to optimize some criteria from the perspective of the allocator. Some other works are dedicated to optimizing allocation fairness. For example, in the domain of ride-sourcing, a method to achieve allocation fairness was proposed in [Lesmana et al., 2019]. Additionally, certain studies address cases where fairness should be maintained for both online tasks and offline workers [Esmaeili et al., 2023]. Our work is motivated by the teleoperation of AVs that has garnered increasing attention recently (e.g., [Zhang, 2020; Ackerman Viden et al., 2023; Tener and Lanir, 2022]). The primary role of teleoperation is to aid AVs by intervening in challenging driving situations1. Ensuring a fair allocation of teleoperators to driving tasks is crucial for enhancing the satisfaction of both teleoperators and AVs' users. Particularly, if certain intervention requests have significantly longer waiting times or if some teleoperators are disproportionately busier than others, such imbalances can lead to dissatisfaction among those affected. In addition, as a person in the vehicle is awaiting the teleoperator's intervention, a rejection of a request is unacceptable. Another property of this application is that the teleoperators (workers) are reusable, which means they are ready to perform a new intervention request (task) once they finish a previously allocated request. We model the problem as online matching in a bipartite graph and propose several approaches to optimize fairness for both the tasks (e.g., intervention requests) and the workers (e.g., teleoperators) involved in the process. Our notion of fairness is aligned with Rawls' theory of justice [Rawls, 1999]. We introduce two minimax problems within the given context. The first concerns fairness regarding tasks relative to waiting times, while the second focuses on Rawlsian fairness for service providers based on their workload. In both scenarios, task rejection is not permissible. We demonstrate that the second problem can be efficiently formulated as a linear problem. Notably, the solution to the second problem mirrors the first when task durations from each worker conform to the same distribution. In cases where this isn't true, we show that the second problem's solution approximates the first problem's solution, supported by a provable approximation ratio. Our study concludes with extensive simulations that underscore the efficacy of these minimax problems. Furthermore, we devise innovative heuristics that leverage the minimax solutions. These heuristics enhance task fairness while preserving favorable outcomes for worker fairness. Our main contributions are: (1) We propose two models to promote fairness among tasks and workers. (2) We present an LP-based algorithmic framework, which can exactly solve fairness maximization among workers and approximately among tasks, and we provide a tight approximation bound. (3) We empirically implement and compare different methods, including several baselines, on datasets involving the teleoperation of AVs. 1As mentioned in [Tener and Lanir, 2022], the AVs will need this intervention, at least in the near future. ## 1.1 RelatedWork In this section, we describe previous works about fair allocation and allocation with delays. Notably, to our knowledge, our work distinguishes itself by being the first to consider fairness and allocation delays together. Fair allocation Some studies address fair allocation, focusing on only one side of the graph, as seen in [Ma et al., 2020]. Although their fairness approach resembles ours, it pertains solely to one side of the graph, which falls short of our requirements. Other research, like [Patro et al., 2020], deals with fairness in recommendation systems. However, the fairness objectives in recommendation systems significantly differ from those in task allocation contexts. Practical solutions for enhancing fairness for both service providers and tasks are explored in works such as [Zhou et al., 2023]. Regrettably, this branch of research lacks theoretical performance bounds for their solutions. The fairness principles in [Esmaeili et al., 2023] closely align with ours. They consider both workers (offline side) and tasks (online side), embracing Rawlsian welfare [Rawls, 1958]. Nonetheless, task rejection is permissible in their scenario if workers are unavailable. Allocation with delayed assignments The original online matching problem was introduced in [Karp et al., 1990], where static nodes (workers) are instantly paired with dynamic nodes (tasks) upon arrival. However, real scenarios often lack immediate worker availability for tasks, prompting consideration for task execution delays over outright rejection. Numerous works tackle resource allocation with potential task delays. However, many of these approaches (e.g., [Righter, 1987; Li et al., 2023]) prioritize utility maximization without factoring in task wait times or worker workload. Some leverage reinforcement learning for such issues yet often make batch decisions, leading to suboptimal outcomes. Moreover, theoretical guarantees are frequently absent. An LP-based method for delayed allocations is presented in [Ackerman Viden et al., 2023], optimizing a complex utility function that accounts for task waiting times but overlooks worker workload. Another pertinent domain involves queue admission control systems with multiple classes. Here, diverse customer types (tasks) arrive dynamically, and a decision-maker determines which task to accept, as demonstrated in [Rigter et al., 2022]. However, several studies in this realm do not distinguish between workers, while others permit task rejection. To our knowledge, the problem of two-sided fair allocation when task rejection is not allowed has not yet been addressed. ## 2 Preliminaries Suppose we use a bipartite graph 𝐺 = (𝐼, 𝐽, 𝐸) to model the worker-task network, where 𝐼 denotes the set of offline workers (e.g., teleoperators), 𝐽 the set of types of tasks, and an edge 𝑒 = (𝑖, 𝑗) indicates the feasibility of worker 𝑖 to serve the task (of type) 𝑗 . Note that at certain points within this paper, we abuse the notation by referring to 𝑗 as a task instead of a task type. We also abuse the notation by referring to an edge 𝑒 = (𝑖, 𝑗) as (𝑖 𝑗). Tasks of type 𝑗 ∈ 𝐽 arrive following an independent Poisson process of rate πœ† 𝑗 > 0. For each edge 𝑒 = (𝑖, 𝑗) ∈ 𝐸, we assume it takes worker 𝑖 an exponentially distributed service time2 of rate πœ‡π‘– 𝑗 > 0 to complete a task of type 𝑗 (i.e., with mean of 1/πœ‡π‘– 𝑗 )3. For each worker 𝑖 and task 𝑗 , let N𝑖 βŠ† 𝐽 and N𝑗 βŠ† 𝐼 denote the set of neighbors of 𝑖 and 𝑗 in the graph 𝐺. The assigning rule is as follows. Upon the arrival of a task of type 𝑗 , we (as the central coordinator) have to assign it to a feasible worker 𝑖 ∈ N𝑗 immediately: if 𝑖 is free (or available) at that time, then 𝑖 will serve 𝑗 right away; otherwise, 𝑗 will join the virtual queue of 𝑖 and it will stay there until being served by 𝑖. Table 1: A glossary of notations throughout this paper. | 𝐺 | Input network graph 𝐺 = (𝐼, 𝐽, 𝐸). | |----------------|-----------------------------------------------| | 𝐼 (𝐽) | Set of worker (task) types. | | N𝑖 (N𝑗 ) | Set of neighbors of 𝑖 ( 𝑗). | | 𝑖 ∼ 𝑗 ( 𝑗 ∼ 𝑖) | Equivalent to 𝑖 ∈ N𝑗 ( 𝑗 ∈ N𝑖). | | πœ† 𝑗 | Arrival rate of task type 𝑗 ∈ 𝐽. | | πœ†π‘– | Arrival rate on worker 𝑖 ∈ 𝐼. | | Exp(πœ‡) | Exponential distribution of rate πœ‡ > 0. | | Exp(πœ‡π‘– 𝑗 ) | Service time taken by worker 𝑖 to service 𝑗 . | | πœŒπ‘– ∈ [0, 1] | Workload of worker 𝑖 ∈ 𝐼. | | 𝑀 𝑗 | Expected (absolute) waiting time of 𝑗 . | | ¯𝑀 𝑗 | Expected (relative) waiting time of 𝑗 . | | πœ… β‰₯ 1 | maxπ‘–βˆˆπΌ οΏ½ maxπ‘—βˆΌπ‘–, 𝑗 β€² βˆΌπ‘– πœ‡π‘– 𝑗/πœ‡π‘–, 𝑗 β€² οΏ½ . | ## 2.1 Allocation Policy and Related Concepts Consider an allocation policy πœ‹(x) (possibly randomized), characterized as a vector x = {π‘₯𝑖 𝑗 |(𝑖 𝑗) ∈ 𝐸}, where π‘₯𝑖 𝑗 ∈ [0, 1] denotes the percentage of task (of type) 𝑗 assigned to and served by worker 𝑖. In the following, we discuss a few important properties and concepts related to πœ‹(x). Let Q𝑖 be the virtual queue maintained by worker 𝑖 ∈ 𝐼. Arrival rate on Q𝑖, denoted by πœ†π‘–. Observe that x = (π‘₯𝑖 𝑗 ) can be viewed alternatively as the probability that πœ‹ assigns each arriving 𝑗 to 𝑖. Thus, we claim that Q𝑖 admits a Poisson arrival process of rate πœ†π‘– := οΏ½ π‘—βˆˆN𝑖 πœ† 𝑗 Β· π‘₯𝑖 𝑗 . By the property of the Poisson process (See section 2.3.2 at [Gallager, 2011]), conditioning on the arrival of task (of type) Β― 𝑗 ∈ 𝐽 on 𝑖, we claim that Pr[ Β― 𝑗 = 𝑗] = π‘₯𝑖 𝑗 Β· πœ† 𝑗/πœ†π‘– for each 𝑗 ∈ N𝑖. Service time on Q𝑖 , denoted by S𝑖 . The analysis above shows that the task joining Q𝑖 is of type 𝑗 ∈ N𝑖 with probability equal to π‘₯𝑖 𝑗 Β· πœ† 𝑗/πœ†π‘–. Thus, the overall service time S𝑖 = οΏ½ π‘—βˆˆN𝑖 πœ’π‘– 𝑗 Β· 2This assumption is justified in [Devore, 2008]. Note that the theoretical analysis does not depend on it. We could use any distribution if the mean and the variance of service time are known. 3Note that the assumption does not necessarily suggest the most likely outcome is for tasks to be finished in an extremely short time. Consider a task type with an exponentially distributed service time of rate πœ‡, denoted as 𝑋 = Exp(πœ‡). We observe that for any given threshold π‘Ž > 0, Pr[𝑋 β‰₯ π‘Ž] = 𝑒 -πœ‡π‘Ž , which can be close to one when πœ‡ is small. Exp(πœ‡π‘– 𝑗 ), where πœ’π‘– 𝑗 = 1 indicates that the task joining 𝑖 is of type 𝑗 with E[πœ’π‘– 𝑗 ] = π‘₯𝑖 𝑗 Β· πœ† 𝑗/πœ†π‘–, and Exp(πœ‡π‘– 𝑗 ) represents the exponentially distributed service time of 𝑖 for 𝑗 of rate πœ‡π‘– 𝑗 . Thus, S𝑖 follows a hyperexponential distribution [Gupta and Goyal, 1964] with mean equal to Workload of worker 𝑖, denoted by πœŒπ‘– . By definition, where πœŒπ‘– can be re-interpreted as the probability that the worker 𝑖 is busy or the proportion of time the worker 𝑖 is busy averaged over a long period. Note that πœŒπ‘– < 1 is the key condition ensuring the virtual queue Q𝑖 can enter a stable state. This is also a condition we should impose on every worker 𝑖 ∈ 𝐼 when designing policy πœ‹(x) since otherwise, 𝑖 could always stay occupied in the long run (thus, not acceptable to 𝑖) and every task 𝑗 assigned to 𝑖 could risk an infinitely long waiting time (not acceptable to 𝑗). Waiting time on worker 𝑖, denoted by π‘Šπ‘–. By the analysis above, we see that the queue Q𝑖 on worker 𝑖 qualifies as an 𝑀/𝐺/1 (using the standard Kendall's notation [Kendall, 1953]), which means it admits a Poisson arrival process, a general service time distribution, and a single worker. By the Pollaczek-Khinchin mean formula [Asmussen, 2003], where the numerator is equal to Absolute and relative waiting time of 𝑗 , denoted by π‘Šπ‘— and π‘Š 𝑗 . Recall that under πœ‹(x), a task 𝑗 will be assigned to a feasible worker 𝑖 ∈ N𝑗 with probability π‘₯𝑖 𝑗 . Thus, the expected (absolute) waiting time of 𝑗 should be where 𝑀𝑖 is the expected waiting time on queue Q𝑖 , as shown in (3). The relative waiting time of 𝑗 on Q𝑖 is defined as the ratio of waiting time on Q𝑖 to the service time of 𝑖 for 𝑗 , which has a mean of 1/πœ‡π‘– 𝑗 . Thus, the expected relative waiting time of 𝑗 should be ## 2.2 Two Fairness-Related Objectives In this paper, we propose the following two fairness metrics and objectives when optimizing a policy πœ‹(x). FAIR-T: Fairness promotion among tasks, denoted by minmaxπ‘—βˆˆπ½ ¯𝑀𝑗 . We quantify the overall fairness among users achieved by policy πœ‹(x) as the maximum expected relative waiting time among all task types, i.e., maxπ‘—βˆˆπ½ ¯𝑀𝑗 . A formula for calculating the relative waiting time is shown in (5). Note that here we choose the relative version instead of the absolute one (i.e., max 𝑗 ∈𝐽 𝑀 𝑗 ) following, for example, the paper [Maister and others, 1984] that asserts that "the more valuable the service, the longer the customer will wait." A compelling example is that:"Special checkout counters were originally provided because customers with only a few items felt resentful at having to wait a long time for what was seen as a simple transaction. Customers with a full cart of groceries were much more inclined to tolerate lines." FAIR-S: Fairness promotion among workers, denoted by minmaxπ‘–βˆˆπΌ πœŒπ‘–. Recall that for each worker 𝑖 ∈ 𝐼, the workload πœŒπ‘– ∈ (0, 1), as defined in (2), captures the percentage of busy time on worker 𝑖. Thus, the maximum workload, i.e., maxπ‘–βˆˆπΌ πœŒπ‘–, reflects the highest degree of being occupied among all workers under policy πœ‹ (x). By opting for minimization of the maximum workload, denoted by minmaxπ‘–βˆˆπΌ πœŒπ‘–, we aim to minimize the occupation time of the most occupied worker as substantially as feasible. ## 2.3 Two Optimization Programs Consider an allocation policy πœ‹(x) parameterized by x = (π‘₯𝑖 𝑗 ), where π‘₯𝑖 𝑗 with (𝑖 𝑗) ∈ 𝐸 denotes the percentage of task of type 𝑗 assigned to worker 𝑖. For ease of notation, we will use 𝑖 ∼ 𝑗 (and 𝑗 ∼ 𝑖) to represent 𝑖 ∈ N𝑗 (and 𝑗 ∈ N𝑖) throughout this paper. We formulate FAIR-T and FAIR-S as minmax programs as follows. We refer to the above programs as PT and PS, respectively. Let x βˆ— 𝑑 and x βˆ— 𝑠 be optimal solutions to PT and PS, respectively. Lemma 1. πœ‹(x βˆ— 𝑑 ) and πœ‹(x βˆ— 𝑠 ) are optimal policies under FAIRT and FAIR-S, respectively. Proof. We focus on showcasing the case of FAIR-T and the programPT. The proof for the other case is similar. Note that the term shown in (6) captures the precise objective we aim to optimize. To prove our claim, we need to demonstrate that all constraints in PT hold true for any viable policy of πœ‹(x). Constraint (7) is reasonable because every policy must assign each incoming task to a feasible worker without rejection, thereby ensuring that the total percentages assigned for each type sum up to one. Constraint (8) is valid as the workload of any worker (i.e., the percentage of busy time) should not exceed one. Constraint (9) holds true since π‘₯𝑖 𝑗 represents the percentage of tasks of type 𝑗 assigned to worker 𝑖. β–‘ Lemma 1 suggests that the optimal policies for FAIR-T and FAIR-S each can be obtained by solving minmax programs represented by PT and PS respectively. Note that PS can be reformulated as a linear program (LP) by introducing an auxiliary variable 𝜌 and modifying the objective as min 𝜌, along with additional constraints 𝜌 β‰₯ πœŒπ‘– for all 𝑖 ∈ 𝐼. Consequently, we can efficiently solve PS and obtain an optimal policy for FAIR-S. However, for programPT, the objective is non-linear and can be neither convex nor concave even under very special settings, posing a technical challenge for direct optimization; see detailed discussions in the full version of the paper [Trabelsi et al., 2024]. Nevertheless, under certain conditions, PT can be effectively and accurately approximated by PS, as proven in Theorem 1. Lemma 2. The optimal values of PT and PS each remain invariant if we treat any task type 𝑗 ∈ 𝐽 with an arrival rate of πœ† 𝑗 as π‘˜ different online types, each having the same set of neighbors as 𝑗 , with an arrival rate of πœ† 𝑗/π‘˜ for any integer π‘˜. The above lemma suggests that for fairness maximization among either workers under metric FAIR-S or tasks under metric FAIR-T, we can assume without loss of generality that all tasks take a uniform arrival rate by creating an appropriate number of copies for each task type. In other words, the variation among tasks' arrival rates makes no difference to fairness promotion, compared with the difference among service times. In the remaining sections, we assume without loss of generality that πœ† 𝑗 = πœ† for all 𝑗 ∈ 𝐽. ## 3 The Relation Between the Two Fairness Optimization Problems Consider a general setting denoted by 𝝁 := (πœ‡π‘– 𝑗 ), where πœ‡π‘– 𝑗 with (𝑖 𝑗) ∈ 𝐸 represents the parameter for the exponential distribution of the service time taken by worker 𝑖 to serve task 𝑗 . Let πœ‚π‘‘ (𝝁, x) denote the objective value of PT(𝝁) with respect to the input 𝝁 and a feasible solution x = (π‘₯𝑖 𝑗 ). Similarly, πœ‚π‘  (𝝁, x) denotes the objective value of PS(𝝁). When the context is clear, we may omit either the first or second argument for πœ‚π‘‘ and πœ‚π‘ . For any given input 𝝁, let πœ‚ βˆ— 𝑑 (𝝁) and πœ‚ βˆ— 𝑠 (𝝁) denote the optimal values of PT(𝝁) and PS(𝝁) respectively. Theorem1. Let x βˆ— 𝑠 be an optimal solution to PS(𝝁). We have where πœ… = maxπ‘–βˆˆπΌ οΏ½ maxπ‘—βˆΌπ‘–, 𝑗 β€² βˆΌπ‘– πœ‡π‘– 𝑗/πœ‡π‘–, 𝑗 β€² οΏ½ β‰₯ 1, which captures the maximum pairwise ratio among the expectations of all service time on each given worker. For a private case of Theorem 1- where πœ… = 1 we prove that πœ‚π‘‘ (𝝁, x βˆ— 𝑠) = πœ‚ βˆ— 𝑑 (𝝁) (Theorem 2). These results serve as the bedrock of the whole proof for Theorem 1(See [Trabelsi et al., 2024] for the whole proof of Theorem 1). Toward the proof of πœ… = 1, we first define the following minimax programs and show their equivalence to PT and PS, respectively, for πœ… = 1. Lemma 3. For πœ… = 1, the programs PT and PT are equivalent and the programs PS and PS are also equivalent. Proof. Note that πœ… = 1 suggests that πœ‡π‘– 𝑗 takes some uniform value of πœ‡π‘– 𝑗 = πœ‡π‘– for every 𝑗 ∼ 𝑖. Recall that πœ† 𝑗 = πœ† for all 𝑗 ∈ 𝐽 due to Lemma 2. Under these assumptions, we see that the expressions of πœŒπ‘– and ¯𝑀𝑗 in (2) and (5) can be simplified as where the equality on the last line is due to οΏ½ π‘–βˆΌπ‘— π‘₯𝑖 𝑗 = 1 for every 𝑗 ∈ 𝐽 (no rejection allowed). Substituting lines 17 and 21with the value of πœŒπ‘– and line 15with the value of ¯𝑀𝑗 implies that the programs PTandPS are equivalent toPTandPS. β–‘ Consider a given setting with 𝝁 = (πœ‡π‘– 𝑗 ) satisfying πœ‡π‘– 𝑗 = πœ‡π‘– for all 𝑗 ∼ 𝑖 and πœ† 𝑗 = πœ† for all 𝑗 ∈ 𝐽. For ease of notation, we use πœ‚ βˆ— 𝑑 and πœ‚ βˆ— 𝑠 to denote optimal values of PT and PS, respectively, with respect to the given setting. By default, we assume both have feasible solutions.4 We denote by πœ‚π‘‘ (x βˆ— 𝑠) the value of PT on x βˆ— 𝑠 in the given setting. It is tempting to prove that πœ‚π‘‘ (x βˆ— 𝑠) = πœ‚ βˆ— 𝑑 for πœ… = 1 by showing that PT and PS each possess an optimal solution such that {πœŒπ‘– } all take a uniform value, say 𝜌. Following this "claim", PT is then reduced to min1/(1 - 𝜌) - 1 with 𝜌 = πœŒπ‘– for all 𝑖 ∈ 𝐼, while PS is reduced to min 𝜌 with 𝜌 = πœŒπ‘– for all 𝑖 ∈ 𝐼. This establishes Theorem 2 since min 1/(1 - 𝜌) - 1 is equivalent to min 𝜌. The example below disproves this idea, unfortunately. Example 1. [PT and PS each possess a unique optimal solution with non-uniform values of {πœŒπ‘– } and { ¯𝑀 𝑗 }.] Consider a graph 𝐺 = (𝐼, 𝐽, 𝐸) such that |𝐼 | = π‘š = 2 and |𝐽| = 𝑛 ≫ 1 (A relevant figure is in [Trabelsi et al., 2024]). The input setting is as follows. πœ‡π‘– 𝑗 = πœ‡ for all (𝑖 𝑗) ∈ 𝐸 and πœ† 𝑗 = πœ† for all 𝑗 ∈ 𝐽. Let πœ™ = πœ†/πœ‡ with 𝑛 Β· πœ™ < 1. 𝑖 = 2 is connected to all 𝑗 ∈ 𝐽, while 𝑖 = 1 is connected only to 𝑗 = 1. We can verify that (1) PT and PS each have a unique optimal solution and the two are the same, which is x βˆ— = (π‘₯𝑖 𝑗 ) with π‘₯11 = 1, π‘₯21 = 0, and π‘₯2 𝑗 = 1 for all 1 < 𝑗 ≀ 𝑛; (2) for PS: 𝜌1(x βˆ— ) = πœ™, and 𝜌2(x βˆ— ) = (𝑛 - 1)πœ™ < 1; for PT: ¯𝑀1(x βˆ— ) = 1/(1 - 𝜌1(x βˆ— )) - 1 = 1/(1 - πœ™) - 1 and ¯𝑀𝑗 = 1/(1-𝜌2(x βˆ— )) -1 = 1/(1- (𝑛-1)πœ™) -1 for 1 < 𝑗 ≀ 𝑛. We will now present two lemmas that establish together the correctness of Theorem 2. Proof. Since x βˆ— = (π‘₯𝑖 𝑗 ) is an optimal solution to PS, πœ‚ βˆ— 𝑠 = maxπ‘–βˆˆπΌ πœŒπ‘– (x βˆ— ) := 𝜌 βˆ— . Observe that for each 𝑗 ∈ 𝐽, which suggests that πœ‚π‘‘ (x βˆ— ) = max𝑗 ¯𝑀𝑗 (x βˆ— ) ≀ 1/(1-𝜌 βˆ— )-1 = 1/(1 - πœ‚ βˆ— 𝑠) - 1. β–‘ The lemma's proof is in the full version of the paper [Trabelsi et al., 2024]. We're now set to present results for πœ… = 1. Theorem 2. Consider an input 𝝁 = (πœ‡π‘– 𝑗 ) with πœ… = 1. Let x βˆ— 𝑠 be an optimal solution to PS. We have that the value of PT on the solution of x βˆ— 𝑠 is equal to its optimal value, i.e., πœ‚π‘‘ (x βˆ— 𝑠) = πœ‚ βˆ— 𝑑 . Proof. The above two lemmas together imply that πœ‚π‘‘ (x βˆ— 𝑠) ≀ πœ‚ βˆ— 𝑑 . x βˆ— 𝑠 is feasible to PT since PT and PS share the same set of constraints, and thus, πœ‚π‘‘ (x βˆ— 𝑠) β‰₯ πœ‚ βˆ— 𝑑 , which establishes Theorem 2. β–‘ 4Infeasibility to either Program PT or PS suggests that no policy can lead to meaningful fairness among tasks (finite max expected waiting time) or among workers (a non-zero ratio of being free). ## 4 Experiments ## 4.1 Algorithms and Heuristics This section presents an algorithm derived from solutions to one of the minimax problems. We also describe a heuristic based on this algorithm, which gives preference to assigning tasks to available workers, thereby enhancing allocation through the effective workload of free workers. In addition, this section introduces two real-time greedy heuristics, which function as baseline methodologies. Minimaxproblemsbasedalgorithm: Wefirst describeAlgorithm 1. This algorithm has offline and online phases. In the offline phase (line 2), a solution to one of the minimax problems is computed. In the online phase (lines 4-7), when a task arrives, the task is assigned to the queue of a worker according to the probabilities computed by the program in the offline phase. This algorithm has two variants: One solves PT in the offline phase while the other solves PS. Minimax problems based heuristic: A notable issue with Algorithm 1 is that tasks can wait for a busy worker despite other available workers. This leads to suboptimal performance. To address this, we create a heuristic based on Algorithm 1. Like Algorithm 1, in Algorithm 2, task assignment probabilities are computed offline tomitigate this problem. In the online phase, incoming tasks are assigned to free workers. If multiple workers are free, their precomputed probabilities (from the offline phase) are normalized to sum to 1. A worker is subsequently chosen randomly, guided by these normalized probabilities. If there are no free workers, the tasks are assigned according to their probabilities as in Algorithm 1. Algorithm 2 describes this heuristic. As in Algorithm 1, there are two variants of Algorithm 2: One solves PT in the offline phase, while the other solves PS. This method targets reduced waiting times, especially during low-load periods. However, this change might decrease worker workload or waiting times for other tasks, as it deviates fromcalculated optimal probabilities. In practice, we find that the trade-off for worker and task fairness is reasonable, given the substantial benefits for all tasks' fairness. Computational complexity of Algorithms 1 and 2 Both algorithms 1 and 2 have offline and online phases. The offline phase is identical for both algorithms and requires the solution of PT or PS. Following [Cohen et al., 2021], the runtime for solving the linear program- PS can be as low as 𝑂 βˆ— (𝑁 2+1/6 log(𝑁/𝛿)), where 𝛿 is the relative accuracy and 𝑁 = |𝐸| is the number of edges in the graph 𝐺. We leave the complexity of solving PT to future work. In any case, the complexity of the offline phase dominates the complexity of the online phase. The two greedy heuristics Similar to [Ackerman Viden et al., 2023], we devised two greedy heuristics as baselines for comparison. The first minimizes maximum task waiting times, and the second minimizes maximum worker workload. In the first, incoming tasks are assigned to workers with the shortest estimated waiting time, calculated by summing average expected task durations for tasks in the queue. The elapsed time for ongoing tasks is subtracted from their average duration to update estimates. For the second, tasks are assigned ## Algorithm 1: An LP-based algorithm for FAIR-T and FAIR-S. - 1 Offline Phase: - 2 Solve PT (PS) and let {π‘₯𝑖 𝑗 } be an optimal solution. - 3 Online Phase: - 4 for each task of type 𝑗 that arrive on time 𝑑 do - 5 Let Q𝑖 be a queue of worker 𝑖 - 6 Choose randomly a worker 𝑖 following the probabilities in {π‘₯𝑖 𝑗 } - 7 Update Q𝑖 = Q𝑖 βˆͺ {( 𝑗 , 𝑑)}. to less utilized workers based on current workload upon task arrival. This approach considers executed tasks, using actual durations rather than expected durations. The first heuristic is denoted as GTW (Greedy Task Waiting time) and the second as GWU (Greedy Worker Workload). ## 4.2 Experimental Settings We ran experiments on the teleoperation domain. As already mentioned in Section 1, the teleoperation of AVs involves intervention tasks that are assigned to the teleoperators who perform them. We adapted the dataset of [Ackerman Viden et al., 2023] for our two-sided fairness study. More details about the experimental settings and additional experimental results are in the full version of the paper [Trabelsi et al., 2024]. Source code and data for running the experiments are available at [Trabelsi, 2024]. The tasks, their durations and their arrival rates Our study built upon the four task types defined by Viden et al. (2023). Their dataset provided valuable insights into the average duration times for each teleoperator (worker) and task type in a simulation. We explored three distinct approaches to define task duration in our experiments. All approaches involved sampling durations from exponential distributions, but the difference lay in the means of these distributions. The teleoperators and the tasks they can perform Using the dataset of Viden et al. (2023), we initially had 10 teleoperators (workers) and 4 task types. We form a bipartite graph with 10 teleoperators on one side and 4 task types on the other. The dataset provides average task completion times for each teleoperator-task pair. An edge is established between a teleoperator and a task type if their average time matches or exceeds the task type's median value. Following this process, a teleoperator who consistently performed tasks slower than the median was identified and subsequently excluded from the graph. More experiments on a synthetic dataset in which the numbers of teleoperators and task types are varied can be found in [Trabelsi et al., 2024]. Experimental environment and more settings Each experiment spanned a virtual 4-week period. Due to algorithmic stochasticity, each experiment was repeated 10 times. ## 4.3 Results and Discussion Effect of changing πœ… In Figures 1(a,b), we illustrate the performance of various methods across diverse πœ… values. In Figure 1(a), we measure the maximum task waiting time. We ## Algorithm 2: A heuristic for FAIR-T (FAIR-S). - 1 Offline Phase: - 2 Solve PT (PS) and let {π‘₯𝑖 𝑗 } be an optimal solution. - 3 Online Phase: - 4 for each task of type 𝑗 that arrive on time 𝑑 do - 5 Let Q𝑖 be a queue of worker 𝑖 and let 𝐹 be the subset of free workers on time 𝑑 - 6 If 𝐹 β‰  βˆ…, randomly choose a free worker 𝑖 with probability {π‘₯𝑖 𝑗 / οΏ½ 𝑖 β€² ∈𝐹 π‘₯𝑖 β€² 𝑗 } - 7 Otherwise choose randomly a worker 𝑖 following the probabilities in {π‘₯𝑖 𝑗 } - 8 Update Q𝑖 = Q𝑖 βˆͺ {( 𝑗 , 𝑑)}. see that the gap between SIM(PS) and SIM(PT), as well as the gap between SIM-F(PS) and SIM-F(PT), increase with πœ…. This aligns with the fact that with higher values of πœ…, the approximation ratio of PS's solution relative to PT's objective is greater. However, the ratio between the different methods measured in practice is lower than the worst-case theoretical ratio given by Theorem 1 (which is greater than πœ… 3 ). In Figure 1(b), we measure the maximum worker workload. The differences between SIM(PT) vs SIM(PS) are very small for πœ… ≀ 3, but they become more significant for πœ… ∈ {4, 5}. Surprisingly, there is a different effect with SIM-F(PT) and SIM-F(PS). SIM-F(PT) performs slightly better than SIMF(PS). We conjecture that the initial selection of free workers has a more detrimental effect in SIM-F(PS), which integrates two distinctly different methods, in contrast to the relatively similar approaches in SIM-F(PT). We also see that for larger values of πœ…, both SIM(PT) and SIM(PS) perform worse than for lower values. Effect of changing the task load Figures 1(c,d) might help the teleoperation center's owner decide whether the current number of workers is sufficient. It is noticeable that in Figure 1(c) there is a significant jump from 120000 to 140000 tasks per day. This means that perhaps the owner should employ more workers in this case. Referring to Figure 2(d) may lead us to similar conclusions. Employing more workers is advisable if individual worker workload is excessively high. Effect of changing the task balance Figures 1(e,f) represent the performance of the different algorithms when changing the task balance. The left bar represents an even distribution for each task type (0.25). The second bar represents a higher probability for the first type (0.7) and a lower probability for the other types (0.1). The other bars are similarly defined for the other task types. In Figures 1(e,f), higher arrival distribution of the first task type leads to elevated waiting times and worker workload. Consequently, the teleoperation center's owner could enhance fairness by upskilling operators who are not qualified for the task or hiring new ones proficient in it. Alternatively, training could be provided to expedite task completion. The negligible error bars in all figures show that the error approaches 0 if the experiments are carried out over a sufficiently long period of time, as we have done. Figure 1: Y axis is the maximum waiting time(in seconds) for a task(a,c and e) and the max. worker workload(b,d and f). The X axis in (a,b) is the value of πœ…(x axis) and the task load is of 120000 tasks per day. In (c,d), the X axis is the task load and πœ… is set to 1. In (e,f) the X axis is for different balances of arrival distribution: first bar is for equal distribution for each task type. In the second bar, the first type has probability of 70% and the others have 10%. the other bars are defined similarly for the second, third and forth task types (task load was 80000 tasks per day and πœ… is set to 1). In the legend: SIM(PT) and SIM(PS) denote Algorithm 1's results for PT and PS in simulation. SIM-F(PT) and SIM-F(PS) are Algorithm 2's results (in which we assign to a free worker first) for PT and PS in simulation. πΊπ‘‡π‘Š and πΊπ‘Šπ‘ˆ are the results of the greedy heuristics targeting task waiting time and worker workload in simulation. Error bars represent a confidence interval of 0.95. ![Image](https://ijcai.org/proceedings/2024/fulltext/29/image_000000_c43696774621f97da6db5ff795c43bc019cd99eced8c86f664a716118723758c.png) Computed optimal values vs simulation values In all experiments that we ran, the computed expected maximum waiting time (OPT(PT)) and the computed expected maximum worker workload (OPT(PS)) closely align with simulationderived values (SIM(PT) and SIM(PS) respectively). Additionally, the alignment of OPT(PT) and OPT(PS) at πœ… = 1 is consistent with Theorem 1. Choosing the best algorithm The heuristic GTW, which minimizes the maximum task waiting time, performs well at maximum task waiting time and performs poorly at maximum worker workload. Conversely, the greedy heuristic that minimizes the maximum worker workload, GWU, performs well at the maximum worker workload and performs poorly at maximum task waiting time. The methods that offer the best tradeoff between two dimensions of fairness are SIM-F(PT) and SIM-F(PS). However, since PT is nonlinear, there is no tool that guarantees to find an optimal solution for PT, and therefore PT-dependent approaches such as SIM-F(PT) might be unsolvable. Therefore, if πœ… = 1 or at least a small number close to 1, we might want to use SIM-F(PS). However, SIM(PS) might be slightly better if worker workload is more important than task waiting times (but still important). If πœ… is large, it is advisable to consider using a tool that approximates a solution for PT with SIM-F(PT). The figures show that the available tools work adequately in such cases, despite the lack of theoretical guarantees (at least for small problems). Another option is to try both SIM-F(PT) and SIM-F(PS) and pick the one that gives the best results. ## 5 Conclusion This paper addresses two-sided fairness problems represented as online bipartite matching with accommodated delays. We introduce two minimax problems: PT to minimize the maximum workload of workers and PS to minimize the maximum waiting time of tasks. We show that the second problem can be formulated as a linear program and thus solved efficiently. Moreover, we showed that the policy using a solution for PS approximates the solution for PT, and we then presented an upper bound on the approximation ratio. Finally, we compared the performance of different approaches (most of them used the solutions to the problems) and empirically evaluated their performance. Future research may explore different definitions of fairness. In addition, it is promising to extend our approach to scenarios where workers are also arriving dynamically. To demonstrate the need in such scenarios one might consider the teleoperation application where teleoperators (workers) can join or leave the crew. Considering different distributions for both task arrivals and task durations can provide more depth and insights into the study. Finally, it might be beneficial to consider some robust version, say, minimization of the maximum possible absolute waiting time among users, which is equivalent to the minimization of the maximum absolute waiting time among all workers. ## Acknowledgements This research has been partially supported by the Israel Science Foundation under grant 1958/20 and the EU Project TAILOR under grant 952215. Work of Pan Xu was partially supported by NSF CRII Award IIS-1948157. ## References 1. [Ackerman Viden et al., 2023] Osnat Ackerman Viden, Yohai Trabelsi, Pan Xu, Karthik Abinav Sankararaman, Oleg Maksimov, and Sarit Kraus. Allocation problem in remote teleoperation: Online matching with offline reusable resources and delayed assignments. In Proceed- ings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, pages 513-521, 2023. 2. [Asmussen, 2003] SΓΈren Asmussen. Random walks. Applied Probability and Queues, pages 220-243, 2003. 3. [Cohen et al., 2021] Michael B Cohen, Yin Tat Lee, and Zhao Song. Solving linear programs in the current matrix mul- tiplication time. Journal of the ACM (JACM), 68(1):1-39, 2021. 4. [Delong et al., 2022] Steven Delong, Alireza Farhadi, Rad Niazadeh, and Balasubramanian Sivan. Online bipartite matching with reusable resources. In Proceedings of the 23rd ACM Conference on Economics and Computation, pages 962-963, 2022. 5. [Devore, 2008] Jay L Devore. Probability and statistics for engineering and the sciences. 2008. 6. [Dickerson et al., 2021] John P Dickerson, Karthik A Sankararaman, Aravind Srinivasan, and Pan Xu. Alloca- tion problems in ride-sharing platforms: Online matching with offline reusable resources. ACM Transactions on Eco- nomics and Computation (TEAC), 9(3):1-17, 2021. 7. [Esmaeili et al., 2023] Seyed Esmaeili, Sharmila Duppala, Davidson Cheng, Vedant Nanda, Aravind Srinivasan, and John P Dickerson. Rawlsian fairness in online bipartite matching: Two-sided, group, and individual. In Proc. 37th AAAI, number 5, pages 5624-5632, 2023. 8. [Gallager, 2011] Robert G Gallager. Discrete stochastic pro- cesses. OpenCourseWare: Massachusetts Institute of Tech- nology, 2011. 9. [Gupta and Goyal, 1964] SK Gupta and JK Goyal. Queues with poisson input and hyper-exponential output with finite waiting space. Operations Research, 12(1):75-81, 1964. 10. [Karp et al., 1990] Richard M. Karp, Umesh V. Vazirani, and Vijay V. Vazirani. An optimal algorithm for on-line bipar- tite matching. STOC-90, 1990. 11. [Kendall, 1953] David G Kendall. Stochastic processes oc- curring in the theory of queues and their analysis by the method of the imbedded markov chain. The Annals of Mathematical Statistics, pages 338-354, 1953. 12. [Lesmana et al., 2019] Nixie S Lesmana, Xuan Zhang, and Xiaohui Bei. Balancing efficiency and fairness in on- demand ridesourcing. Advances in neural information pro- cessing systems, 32, 2019. 13. [Li et al., 2023] Zihao Li, Hao Wang, and Zhenzhen Yan. Fully online matching with stochastic arrivals and depar- tures. In Proc. 37th AAAI, number 10, pages 12014-12021, 2023. 14. [Ma et al., 2020] Will Ma, Pan Xu, and Yifan Xu. Group- level fairness maximization in online bipartite matching. arXiv preprint arXiv:2011.13908, 2020. 15. [Maister and others, 1984] David H Maister et al. The psy- chology of waiting lines. Citeseer, 1984. 16. [Patro et al., 2020] Gourab K Patro, Arpita Biswas, Niloy Ganguly, Krishna P Gummadi, and Abhijnan Chakraborty. Fairrec: Two-sided fairness for personalized recommenda- tions in two-sided platforms. In Proceedings of the web conference 2020, pages 1194-1204, 2020. 17. [Rawls, 1958] John Rawls. Justice as fairness. The philo- sophical review, 67(2):164-194, 1958. 18. [Rawls, 1999] John Rawls. A Theory of Justice. Harvard University Press, Cambridge, MA, 1999. 19. [Righter, 1987] Rhonda Righter. The stochastic sequential assignment problem with random deadlines. Probability in the Engineering and Informational Sciences, 1(2):189- 202, 1987. 20. [Rigter et al., 2022] Marc Rigter, Danial Dervovic, Parisa Hassanzadeh, Jason Long, Parisa Zehtabi, and Daniele Magazzeni. Optimal admission control for multiclass queues with time-varying arrival rates via state abstrac- tion. In Proc. 36th AAAI, number 9, pages 9918-9925, 2022. 21. [Tener and Lanir, 2022] Felix Tener and Joel Lanir. Driving from a distance: Challenges and guidelines for autonomous vehicle teleoperation interfaces. In Proceedings of the 2022 CHI Conference on Human Factors in Computing Systems, pages 1-13, 2022. 22. [Trabelsi et al., 2024] Yohai Trabelsi, Pan Xu, and Sarit Kraus. Design a win-win strategy that is fair to both service providers and tasks when rejection is not an op- tion. https://github.com/yohayt/two sided fairness/blob/ main/full version.pdf?raw=true, 2024. 23. [Trabelsi, 2024] Yohai Trabelsi. Code and data: Design a win-win strategy that is fair to both service providers and tasks when rejection is not an option. https://github.com/ yohayt/two sided fairness, 2024. Accessed: 05/05/2024. 24. [Zhang, 2020] Tao Zhang. Toward automated vehicle tele- operation: Vision, opportunities, and challenges. IEEE Internet of Things Journal, 7(12):11347-11354, 2020. 25. [Zhou et al., 2023] Quan Zhou, Jakub Mareček, and Robert Shorten. Subgroup fairness in two-sided markets. Plos one, 18(2):e0281443, 2023.