Federated Learning with Fair Worker Selection: A Multi-Round Submodular
  Maximization Approach
  In this paper, we study the problem of fair worker selection in Federated
Learning systems, where fairness serves as an incentive mechanism that
encourages more workers to participate in the federation. Considering the
achieved training accuracy of the global model as the utility of the selected
workers, which is typically a monotone submodular function, we formulate the
worker selection problem as a new multi-round monotone submodular maximization
problem with cardinality and fairness constraints. The objective is to maximize
the time-average utility over multiple rounds subject to an additional fairness
requirement that each worker must be selected for a certain fraction of time.
While the traditional submodular maximization with a cardinality constraint is
already a well-known NP-Hard problem, the fairness constraint in the
multi-round setting adds an extra layer of difficulty. To address this novel
challenge, we propose three algorithms: Fair Continuous Greedy (FairCG1 and
FairCG2) and Fair Discrete Greedy (FairDG), all of which satisfy the fairness
requirement whenever feasible. Moreover, we prove nontrivial lower bounds on
the achieved time-average utility under FairCG1 and FairCG2. In addition, by
giving a higher priority to fairness, FairDG ensures a stronger short-term
fairness guarantee, which holds in every round. Finally, we perform extensive
simulations to verify the effectiveness of the proposed algorithms in terms of
the time-average utility and fairness satisfaction.
