# Federated Learning with Fair Worker Selection: A Multi-Round Submodular Maximization Approach

arXiv: https://arxiv.org/abs/2107.11728 · HTML: https://mlsanity.com/paper/2107.11728/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 43 references that are in the map.
- First posted on arXiv 25 Jul 2021.

## Builds on (most cited first, 10 of 10)

- [Agnostic Federated Learning](https://mlsanity.com/paper/1902.00146/) (2019)
- [Federated Learning in Mobile Edge Networks: A Comprehensive Survey](https://mlsanity.com/paper/1909.11875/) (2019)
- [Fair Resource Allocation in Federated Learning](https://mlsanity.com/paper/1905.10497/) (2019)
- [A Survey on Federated Learning Systems: Vision, Hype and Reality for Data Privacy and Protection](https://mlsanity.com/paper/1907.09693/) (2019)
- [Client Selection for Federated Learning with Heterogeneous Resources in Mobile Edge](https://mlsanity.com/paper/1804.08333/) (2018)
- [The Frontiers of Fairness in Machine Learning](https://mlsanity.com/paper/1810.08810/) (2018)
- [Scheduling Policies for Federated Learning in Wireless Networks](https://mlsanity.com/paper/1908.06287/) (2019)
- [Combinatorial Sleeping Bandits with Fairness Constraints](https://mlsanity.com/paper/1901.04891/) (2019)
- [Online Influence Maximization (Extended Version)](https://mlsanity.com/paper/1506.01188/) (2015)
- [Providing Long-Term Participation Incentive in Participatory Sensing](https://mlsanity.com/paper/1501.02480/) (2015)

## Built on by (most cited first, 2 of 2)

- [To Store or Not? Online Data Selection for Federated Learning with Limited Storage](https://mlsanity.com/paper/2209.00195/) (2022)
- [Asynchronous Wireless Federated Learning with Probabilistic Client Selection](https://mlsanity.com/paper/2311.16741/) (2023)

## Abstract (arXiv)

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.