Source-linked AI summary
An Incentive Mechanism for Federated Learning in Wireless Cellular network: An Auction Approach
Tra Huong Thi Le, Nguyen H. Tran, Yan Kyaw Tun, Minh N. H. Nguyen, Shashi Raj Pandey, Zhu Han, Choong Seon Hong
TL;DR
Federated learning needs incentives because mobile users incur energy costs when contributing local training resources. The paper formulates the BS–user interaction as an auction and proposes a primal-dual greedy mechanism for winner selection and social-welfare maximization. The mechanism is reported to guarantee truthfulness, individual rationality, and computational efficiency, while its social welfare is 400% larger than the fixed price scheme.
Problem
Mobile users may not participate in federated learning because local model training incurs energy costs, requiring the BS to stimulate participation.
Method
The paper models the BS as an auctioneer and mobile users as sellers, using a primal-dual greedy mechanism with critical-value payments.
Results
The mechanism guarantees truthfulness, individual rationality, and computational efficiency, and achieves social welfare 400% larger than the fixed price scheme.
Takeaways & Limitations
Auction-based incentives provide a mechanism for purchasing wireless FL participation while targeting social-welfare maximization.
Abstract
from arXiv · showhide
Federated Learning (FL) is a distributed learning framework that can deal with the distributed issue in machine learning and still guarantee high learning performance. However, it is impractical that all users will sacrifice their resources to join the FL algorithm. This motivates us to study the incentive mechanism design for FL. In this paper, we consider a FL system that involves one base station (BS) and multiple mobile users. The mobile users use their own data to train the local machine learning model, and then send the trained models to the BS, which generates the initial model, collects local models and constructs the global model. Then, we formulate the incentive mechanism between the BS and mobile users as an auction game where the BS is an auctioneer and the mobile users are the sellers. In the proposed game, each mobile user submits its bids according to the minimal energy cost that the mobile users experiences in participating in FL. To decide winners in the auction and maximize social welfare, we propose the primal-dual greedy auction mechanism. The proposed mechanism can guarantee three economic properties, namely, truthfulness, individual rationality and efficiency. Finally, numerical results are shown to demonstrate the performance effectiveness of our proposed mechanism.
I. INTRODUCTION
The paper addresses mobile-user participation and wireless-resource allocation challenges in federated learning by designing an auction-based incentive mechanism. The proposed primal-dual greedy auction targets social welfare while guaranteeing truthfulness, individual rationality, and computational efficiency.
- Motivation: Federated learning requires many mobile users because each device has few data samples for high-quality model training.
- Motivation: Energy costs from model training may discourage independent and uncontrollable mobile users from participating.
- Motivation: The BS must stimulate participation while allocating limited wireless resources to avoid congestion and maintain training performance.
- Auction framework: The paper models the BS–mobile-user interaction as an auction in which users bid on resource combinations, local accuracy, and energy cost.
- Auction framework: The primal-dual greedy mechanism selects winners and uses critical-value payments to maximize social welfare despite an NP-hard selection problem.
- Contributions: The mechanism is reported to be truthful, individually rational, computationally efficient, and effective in numerical evaluation.
II. RELATED WORKS
Prior federated-learning studies address resource allocation, client selection, communication, and incentives through optimization, Stackelberg games, contract theory, and learning-based methods. This paper distinguishes its auction by allowing active cost reporting and selecting winners for social-welfare optimization.
- Existing FL optimization: Earlier work considered resource allocation, client selection, energy or latency reduction, fairness, and communication optimization in federated learning.
- Client selection: Several studies used client-selection protocols or algorithms based on computing power, wireless states, or reinforcement learning.
- System optimization: Other approaches jointly optimized device selection, beamforming, aggregation, or computing, caching, and communication in edge systems.
- Incentive mechanisms: Incentive studies applied Stackelberg games, contract theory, crowdsourcing, or Nash-equilibrium and deep-reinforcement-learning methods.
- Positioning: Unlike Stackelberg and contract-theory approaches, auctions let mobile users actively report costs so the BS can assess their status and requests.
- Positioning: Compared with prior procurement auctions, this work bids resource combinations, local accuracy, and cost, while selecting winners to optimize social welfare.
III. SYSTEM MODEL: FEDERATED LEARNING SERVICES MARKET
The system contains one BS and multiple users that iteratively train local models and aggregate them into a global federated-learning model. The model exposes a trade-off between local accuracy, resource expenditure, and global accuracy.
- System model: One BS and a set of users cooperatively perform federated learning using each user’s local dataset and model parameters.
- Federated-learning process: Each global iteration sends the global parameter to users, collects local gradients or parameters, aggregates them at the BS, and broadcasts the update.
- Federated-learning process: Users solve local learning problems with gradient methods and local accuracy ε_n, then transmit their local parameters to the BS.
- Federated-learning process: The process repeats until the global accuracy γ is reached after multiple communication rounds.
- Accuracy–resource trade-off: Higher local accuracy can improve global accuracy for a fixed number of BS iterations, but requires excessive local iterations and resources.
- Accuracy–resource trade-off: The incentive environment is intended to motivate smaller ε_n values through increased payment, supporting better local accuracy under the stated performance relationship.
B. Computation and Communication Models for Federated Learning
The model describes users’ computation and uplink communication costs in federated learning, then outlines how the BS advertises tasks, receives bids, allocates resources, and pays winners.
- Computation model: User computation consumes energy for local iterations, with CPU frequency and chipset capacitance determining the computing cost.The model denotes CPU cycles per operation and the effective capacitance parameter for the computing chipset.
- Communication model: The uplink transmits local model updates using subchannels, antennas, and transmission power, while the downlink carries the global model.The achievable uplink rate depends on channel gain, noise, assigned antennas, and subchannels.
- System scope: The paper considers uplink bandwidth allocation because it relates to the cost users experience while learning the global model.The downlink is used for global-model transmission, but only uplink allocation is considered.
- Communication model: The local update size is denoted by σ, and transmission time and energy are derived from the uplink rate and transmission power.The section defines total time and total energy consumption for one global iteration.
- Auction interaction: The BS initializes and advertises the FL task, receives users’ resource-and-cost bids, selects winners, allocates resources, and pays participating users.Each bid includes subchannel number, antenna number, local accuracy, and claimed training cost.
IV. DECIDING MOBILE USERS’S BID
Users determine bids by relating requested communication and computation resources to energy cost under FL accuracy and delay requirements. The resulting optimization is nonconvex, so the paper proposes an iterative low-complexity solution.
- Bid construction: Each bid specifies subchannels and antennas, and users calculate corresponding transmission power, computation frequency, and cost.The bid-generation process is repeated for every submitted bid, so the bid index is omitted during analysis.
- Resource allocation: The maximum antenna and subchannel resources are energy-optimal according to the stated optimization model.This conclusion follows from the paper’s formulation P1.
- Accuracy and delay: Local accuracy determines the lower bound on global iterations, while the FL task imposes a delay requirement.The passage gives 0 = C1 log(1/γ) 1−εn as the lower bound on global iterations corresponding to local accuracy εn.
- Cost modeling: The cost model approximates users’ energy costs because actual costs can vary across global iterations.The approximation is introduced to make the optimization more tractable.
- Iterative solution: Because P2 is nonconvex and global optimality is challenging, the paper proposes a low-complexity iterative algorithm.The algorithm first solves P2 with fixed εn and then updates εn using the resulting fn and pn.
1) Optimization of Uplink Transmission Power:
The uplink-power subproblem is handled through a low-complexity bisection procedure, while the broader optimization alternates among subproblems and updates local accuracy until convergence to a local optimum.
- Power optimization: Bisection is used to solve the quasiconvex power-related optimization with a specified accuracy.The general quasiconvex approach solves a convex feasibility problem at each step.
- Power optimization: The power-allocation objective is represented by a monotonically increasing transcendental function that is negative at pn = 0.The optimal power is obtained by evaluating this function rather than repeatedly solving a convex feasibility problem.
- Iterative algorithm: The iterative algorithm initializes a feasible solution, repeatedly updates the optimization variables, and stops when P2’s objective value converges.Its steps include solving subproblems P3 and P4 and updating the relevant variables.
- Local-accuracy optimization: For fixed ξ, H(ξ) is convex, so εn can be obtained by setting its first-order derivative to zero.The resulting expression gives the optimal local accuracy parameter.
- Convergence: The objective value of P2 is non-increasing and bounded below by zero, so Algorithm 3 converges to a local optimum.This is a convergence guarantee for the proposed iterative procedure, not global optimality.
B. Complexity Analysis
The complexity analysis decomposes Algorithm 3 into the costs of solving P3 and P4, then expresses total complexity through the number of outer iterations and the accuracies of the inner methods.
- Complexity decomposition: The main per-step computational burden lies in solving problems P3 and P4.Algorithm 3 iteratively solves these two subproblems.
- Subproblem complexity: O(Le log2(1/ϵ1)) is the complexity for solving P3 with bisection accuracy ϵ1 and Le iterations for optimizing fn and pn.The complexity is stated for the P3 solution procedure.
- Subproblem complexity: O(log2(1/ϵ2)) is the complexity for solving P4 with accuracy ϵ2 using the Dinkelbach method.P4 is treated separately from the bisection-based solution of P3.
- Total complexity: The total complexity is HeS, where He is the number of iterations for P3 and P4 and S = O(Le log2(1/ϵ1)) + O(log2(1/ϵ2)).The expression combines the inner subproblem costs across the iterative procedure.
A. Problem Formulation
The formulation models federated-learning participation as a social-welfare auction constrained by BS bandwidth and antenna resources. Because the resulting minimization knapsack problem is NP-hard, the mechanism targets truthfulness, individual rationality, and computational efficiency through a primal-dual greedy approach.
- Each bid describes a mobile user’s requested subchannels, antennas, local accuracy, and claimed cost.
- The BS’s utility equals its satisfaction from local accuracy minus payments to mobile users, while total utility defines social welfare.
- The allocation problem enforces bandwidth and antenna limits, allows each mobile user to win at most one bid, and uses binary winning variables.
- The resulting P6 minimization knapsack problem is NP-hard, so no polynomial-time algorithm can always find its optimal solution.
- The proposed primal-dual greedy mechanism seeks truthfulness, individual rationality, and computation efficiency, with truthfulness identified as the most challenging property.
B. Approximation Algorithm Design
The approximation design relaxes the integer allocation problem, constructs a dual formulation, and greedily allocates resources using normalized bid values. The analysis establishes feasibility and an explicit approximation ratio for the resulting algorithm.
- The greedy algorithm sorts bids by normalized value and allocates resources to bidders with larger normalized values.
- Algorithm 4 provides a feasible solution to P7.
- The proof checks feasibility separately for winning and losing mobile users before deriving the approximation bound through duality.
- The upper bound of the integrality gap and Algorithm 4’s approximation ratio are given as 1 + κΥ/(Υ−S), with Υ = ηbBmax + ηaAmax and S = maxn,i sni.
D. Payment
The payment design uses critical values derived from the highest normalized losing bidder and represents mobile-user bids through virtual bidders. This supports monotone allocation, truthful payments, individual rationality, and computational efficiency.
- The critical value is the minimum value required to win the requested resource bundle, determined using the strongest losing bidder if the winner were absent.
- Representing each mobile user’s bid combinations as virtual bidders allows the payment rule to compare individual bids through normalized values.
- The payment for a winning bid is based on the bidder’s local-accuracy satisfaction minus a critical value.
- The proposed mechanism is truthful because it combines monotone allocation with critical-value payments.
- The winner-determination algorithm is monotone because increasing a bid or decreasing the weighted resource requirement can increase winning chances.
- The mechanism is individually rational and computationally efficient; losing users receive utility 0, while payment computation takes at most N(N −1) iterations.
VI. SIMULATION RESULTS
Simulations evaluate bid costs, accuracy, social welfare, and resource-related metrics under varying resource limits, tolerance times, user counts, and pricing schemes. The proposed greedy auction generally outperforms fixed-price baselines while remaining below optimal solutions.
- Simulation setup: The simulations vary resource, computation, communication, and timing parameters to evaluate the proposed mechanism.The study uses iterative bid evaluation, varying maximum requested sub-channels, antennas, and tolerance time, alongside fixed system and channel assumptions.
- Bid cost and accuracy: As Bmax increases, requested local accuracy decreases, while the resulting energy cost increases with sub-channels and antennas.Lower requested local accuracy increases global and local rounds needed to achieve global accuracy, raising cost.
- Bid cost and accuracy: When Tmax increases from 100 to 500, bid cost decreases because users can reduce CPU frequency and transmission rate while satisfying delay constraints.The figure reports local accuracy and energy cost as functions of Tmax.
- Social welfare comparisons: Social welfare rises with the number of mobile users across schemes; the proposed greedy scheme is below both optimal solutions but above the lower bound.More users provide more opportunities to select higher-value winning bids.
- Social welfare comparisons: The proposed greedy scheme provides much higher social welfare than fixed linear, sublinear, and superlinear price schemes.Fixed-price welfare first increases and then becomes zero as the basic price grows too high relative to bid valuations.
- Normalized comparisons: Fixed-price schemes can utilize more resources and mobile users than the proposed scheme but provide less social welfare because they depend heavily on resource prices.Figure 6 compares social welfare, resource utilization, and the percentage of users across pricing variants relative to the proposed greedy scheme.
VII. CONCLUSION
The paper designs incentives for mobile-user participation in federated learning by modeling the BS–user interaction as an auction that maximizes social welfare. It combines energy-cost-based bidding with iterative bid evaluation and primal-dual greedy winner selection, and reports economic guarantees and strong simulation performance.
- The paper addresses incentive mechanism design to stimulate mobile users to participate in federated learning.
- It formulates the BS–mobile-user interaction as an auction game that maximizes social welfare and derives bids from users’ minimal energy costs.
- A low-complexity iterative algorithm evaluates bids, while a primal-dual greedy algorithm addresses the NP-hard winner-selection problem.
- The proposed auction mechanism guarantees truthfulness, individual rationality, and computation efficiency.
- The proposed mechanism achieves higher social welfare than fixed-price schemes, with one reported comparison reaching 400% larger welfare.