  Incentive mechanism is crucial for federated learning (FL) when rational
clients do not have the same interests in the global model as the server.
However, due to system heterogeneity and limited budget, it is generally
impractical for the server to incentivize all clients to participate in all
training rounds (known as full participation). The existing FL incentive
mechanisms are typically designed by stimulating a fixed subset of clients
based on their data quantity or system resources. Hence, FL is performed only
using this subset of clients throughout the entire training process, leading to
a biased model because of data heterogeneity. This paper proposes a game
theoretic incentive mechanism for FL with randomized client participation,
where the server adopts a customized pricing strategy that motivates different
clients to join with different participation levels (probabilities) for
obtaining an unbiased and high performance model. Each client responds to the
server's monetary incentive by choosing its best participation level, to
maximize its profit based on not only the incurred local cost but also its
intrinsic value for the global model. To effectively evaluate clients'
contribution to the model performance, we derive a new convergence bound which
analytically predicts how clients' arbitrary participation levels and their
heterogeneous data affect the model performance. By solving a non-convex
optimization problem, our analysis reveals that the intrinsic value leads to
the interesting possibility of bidirectional payment between the server and
clients. Experimental results using real datasets on a hardware prototype
demonstrate the superiority of our mechanism in achieving higher model
performance for the server as well as higher profits for the clients.
