Nonlinear Equilibrium Transitions in a Potential Game Model for Federated Learning

Kang Liu; Ziqi Wang; Enrique Zuazua

cs.LGNov 18, 2024

Nonlinear Equilibrium Transitions in a Potential Game Model for Federated Learning

Authors: Kang Liu, Ziqi Wang, Enrique Zuazua

Organizations: Institut de Mathématiques de Bourgogne, Université Bourgogne Europe, CNRS, Dijon, 21000, France · Chair for Dynamics, Control, Machine Learning and Numerics – Alexander von Humboldt Professorship, Department of Mathematics, Friedrich-Alexander-Universität Erlangen-Nürnberg, Cauerstrasse 11, Erlangen, 91058, Germany · Chair of Computational Mathematics, Fundación Deusto, Avenida de las Universidades, 24, Bilbao, 48007, Basque Country, Spain · Departamento de Matemáticas, Universidad Autónoma de Madrid, Ciudad Universitaria de Cantoblanco, Madrid, 28049, Spain

Abstract

In federated learning (FL), a central server typically allocates training efforts to clients. However, from a market-oriented perspective, clients may independently choose their training efforts based on rational self-interest. To study this setting, we propose a potential game framework in which each client's payoff is determined by its individual effort and the rewards provided by the server. The rewards are influenced by the collective efforts of all clients and can be modulated by a reward factor. We first establish the existence of Nash equilibria (NEs) and then investigate their uniqueness in a stationary setting. We show that the NEs depend nonlinearly on the reward factor and exhibit a nonsmooth transition at a critical value, where the stationary potential loses strict curvature, leading to nonunique NEs and a jump between low-effort and high-effort branches. Furthermore, we prove the convergence of the best-response algorithm for computing NEs in our FL game. Finally, we apply the clients' rational efforts derived from the NEs to FL training with various datasets and models, thereby validating the effectiveness of the identified critical reward factor. The source code is available at https://github.com/DCN-FAU-AvH/FL-Potential-Game

Figures & tables

Figure 1 : In the FL game (left), each client

i

maximizes the payoff

P_{i}

, and the NE

s^{*}

satisfies

P_{i}(s_{i}^{*},s_{-i}^{*})\geq P_{i}(s_{i},s_{-i}^{*})

for all

s_{i}\in\mathcal{S}_{i}

. The equilibrium efforts

s^{*}

( e.g. , local epochs) then drive the FL training stage (right), where the model parameters are updated according to

\theta_{i}^{t+1}=\operatorname{Update}_{i}(\theta^{t},s_{i}^{*})

Figure 2 : Illustration of the nonlinear threshold structure and jump phenomenon.

Symbol	Name	Eq.	Definition and role
$\lambda^{*}$	Jump point	( 3.3 )	The critical reward factor where non-uniqueness occurs.
$\lambda_{1}$	Activation point	( 3.8 )	If $\lambda\in(0,\lambda_{1})$ , the unique NE is at minimum efforts.
$\lambda_{2}$	Saturation point	( 3.8 )	If $\lambda\in(\lambda_{2},+\infty)$ , the unique NE is at maximum efforts.
$c_{1}$	Lower jump bound	( 3.4 )	If $\lambda\in(\lambda_{1},\lambda^{})$ , the unique NE satisfies $\bar{s}^{}<c_{1}$ .
$c_{2}$	Upper jump bound	( 3.4 )	If $\lambda\in(\lambda^{},\lambda_{2})$ , the unique NE satisfies $\bar{s}^{}>c_{2}$ .

Table 1 : Summary of the critical thresholds, see Theorem 3.2 and Corollary 3.7 for more details.

Panel of Figure 3 — Figure 3 : Two-player stationary potential landscape of Example 3.6 . At $\lambda=\lambda^{*}$ , a flat ridge appears along $s_{1}=s_{2}$ , yielding infinitely many NEs on the feasible diagonal segment. In contrast, for $\lambda<\lambda^{*}$ and $\lambda>\lambda^{*}$ , the potential has a unique maximizer, corresponding to a unique NE.

Panel of Figure 4 — Figure 4 : Average training effort $\bar{s}^{*}$ as a function of the server’s reward factor $\lambda$ . The activation point $\lambda_{1}$ , jump point $\lambda^{*}$ , and saturation point $\lambda_{2}$ are indicated in the legends.

		Balanced, non-IID, $m=1{,}000$					Imbalanced, non-IID, $m=3{,}000$
		$\lambda_{1}=1.998,\ \lambda^{*}=2.904,\ \lambda_{2}=4.685$					$\lambda_{1}=2.003,\ \lambda^{*}=2.886,\ \lambda_{2}=4.790$
		NE		Test accuracy			NE		Test accuracy
Case	Regime	$\lambda$	$\bar{s}^{*}$	CIFAR-10	CIFAR-100	IMDB	$\lambda$	$\bar{s}^{*}$	FEMNIST
Case 1	pre-activation	1.99	1.00	0.434	0.120	0.535	2.00	1.00	0.124
Case 2	pre-jump	2.90	1.32	0.477	0.142	0.523	2.88	1.32	0.232
Case 3	post-jump	2.91	16.41	0.558	0.208	0.796	2.89	15.94	0.665

Table 2 : Summary of experimental cases. Cases 1–4 correspond, respectively, to the pre-activation, pre-jump, post-jump, and post-saturation regimes, that is, before

\lambda_{1}

, immediately before

\lambda^{*}

, immediately after

\lambda^{*}

, and after

\lambda_{2}

. Test accuracies are averaged across different FL algorithms.

Figure 5 : Results of FL training under four NE cases across different datasets and algorithms. The largest gain is observed when moving from Case 2 to Case 3 in all experiments.

Explore similar work

Stable and Budget-Feasible Coalition Formation for Clustered Federated Learning: A Hedonic Potential-Game Approach
Jul 29, 2026Cengis HasanFederated Learning Coalition Formation
Cognifinity, Luxembourg
Multi-Agent Privacy Game in Federated Learning: A Unified Mean-Field View
Jul 25, 2026Kun Zhao, Xu ChenFederated Learning Privacy
Federated Learning by Utility-Constrained Stochastic Aggregation for Improving Rational Participation
May 18, 2026M Yashwanth, Arunabh Singh, Ashok Nayak +2Federated Learning Participation
Indian Institute of Science, Bangalore · Indian Institute of Technology Bombay · IIIT Hyderabad

Jul 29, 2026, cs.GTJ/K move · Enter open · S save

Stable and Budget-Feasible Coalition Formation for Clustered Federated Learning: A Hedonic Potential-Game Approach

Cengis Hasan

Cognifinity, Luxembourg

Federated Learning Coalition Formation Game Theory Incentives Nash Equilibrium

Open paper AskPDF arXiv

Clustered federated learning benefits from organizing heterogeneous participants into coalitions that train coalition-specific models, but such clustering is sustainable only if participants prefer their assigned coalition and the required transfers are affordable. We develop a transferable-surplus model separating learning benefit, system cost, participant cost, and monetary transfers; an allocation rule converts coalition surplus into hedonic preferences, and weak budget feasibility guarantees nonnegative retained coordinator surplus. For symmetric pairwise allocations the induced game is an exact potential game: a Nash-stable partition exists, every strict better-response process converges, and with destination consent accepted better responses reach an individually stable partition. We characterize feasibility of bounded pair incentives and verify the exponentially many budget constraints in polynomial oracle time when retained slack is submodular. Decomposing welfare into participant potential and retained slack yields additive and multiplicative price-of-stability guarantees, the latter asymptotically tight; exact balance gives welfare-optimal stability only on the pairwise-representable class, and budget feasibility alone permits unbounded welfare loss. Global potential maximization equals weighted maximum-agreement correlation clustering, and approximation followed by stabilization satisfies an end-to-end welfare bound governed by retained slack and negative-edge mass, attained by an explicit construction. In a preregistered five-seed CIFAR-10 study the mechanism reaches the certified estimated-table welfare optimum on every primary instance, equal-surplus sharing has no Nash-stable outcome on three, and pairwise validation gain gives far more reliable pair signs than gradient alignment.

Abstract

Explore similar work

Stable and Budget-Feasible Coalition Formation for Clustered Federated Learning: A Hedonic Potential-Game Approach

Multi-Agent Privacy Game in Federated Learning: A Unified Mean-Field View

Federated Learning by Utility-Constrained Stochastic Aggregation for Improving Rational Participation