An Uncertainty-Aware Auction Mechanism for Federated Learning

Federated learning enables multiple data owners to collaboratively train a shared machine learning model without the need to disclose their local training data. However, it is not practical for all clients to unconditionally contribute their resources; thus, designing an incentive mechanism in federated learning becomes an important issue. Some existing studies adopt the framework of reverse auctions for incentive design, but they do not take the uncertainty of the training time of clients into account. Consequently, a situation may arise where a client is unable to meet the training deadline, and the server cannot wait indefinitely. In this paper, we propose a reverse auction framework that takes the uncertainty of training time into account. We formulate an expected social welfare maximization problem and prove its NP-hardness. We then introduce an efficient dynamic programming-based algorithm which can find an optimal solution in pseudo-polynomial time. Building upon this, we propose a truthful auction mechanism based on the well-known Vickrey-Clarke-Groves (VCG) mechanism. Furthermore, to reduce the time complexity, we introduce an additional truthful auction mechanism based on a greedy algorithm which achieves a near-optimal performance in polynomial time. Finally, the effectiveness of the proposed two auction mechanisms is verified through simulation experiments.