# Differentially Private Games via Payoff Perturbation

Yijun Chen, Guodong Shi Y. Chen and G. Shi are with the Australian Center for
Field Robotics, The University of Sydney, NSW, Australia. (E-mail:
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

In this paper, we study network games where players are involved in
information aggregation processes subject to the differential privacy
requirement for players’ payoff functions. We propose a Laplace linear-
quadratic functional perturbation (LLQFP) mechanism, which perturbs players’
payoff functions with linear-quadratic functions whose coefficients are
produced from truncated Laplace distributions. For monotone games, we show
that the LLQFP mechanism maintains the concavity property of the perturbed
payoff functions, and produces a perturbed NE whose distance from the original
NE is bounded and adjustable by Laplace parameter tuning. We focus on linear-
quadratic games, which is a fundamental type of network games with players’
payoffs being linear-quadratic functions, and derive explicit conditions on
how the LLQFP mechanism ensures differential privacy with a given privacy
budget. Lastly, numerical examples are provided for the verification of the
advantages of the LLQFP mechanism.

##  I Introduction

Games on networks has gained increased traction in recent years. It has been
applied in a variety of fields such as online E-commerce in social
networks[1], route planning in transportation networks[2], and resource
allocations in wireless communication networks[3]. There are typically three
information aggregation processes in games for players to achieve network-
level goals: the distributed Nash equilibrium (NE) seeking[4, 5, 6], best-
response dynamics[7, 8, 9], and no-regret learning[10, 11, 12, 13].

What these frameworks have in common is that players need to share information
with others in a dynamic process, such as their actions, payoff gradients, or
payoffs, and then choose their actions for the next stage based on the
information received and their own payoff functions. Clearly, players’ payoff
functions are encoded in the shared information. However, players’ payoff
functions are often sensitive and private[14]. As a result, players’ payoff
functions are at risk of privacy leakage. Owing to differential privacy[15,
16], it is possible for players to share information and decide their actions
over time to achieve the desired outcome while keeping their payoff functions
from being compromised. Differentially private systems have been well studied
in the sense that lots of privacy algorithms are designed for various tasks
such as average consensus[17, 18], estimation and filtering[19], and convex
optimization[20, 21, 22]. As for differentially private games, the works of
[23, 24] have focused on privacy-preserving distributed Nash seeking strategy
design for aggregated games.

Problem of Interest  In this paper, we consider a network game where players
are interconnected through an interaction/communication network. Players are
involved in information aggregation processes that requires them to share
information to accomplish certain collective goal. The shared information that
encodes the sensitive information of payoff functions is monitored by
adversaries. As a result, we aim to protect the differential privacy of
players’ payoff functions.

We are inspired by [25, 22]. We propose a Laplace linear-quadratic functional
perturbation (LLQFP) mechanism, which perturbs players’ original payoff
functions with linear-quadratic functional perturbation. The coefficients of
those perturbation are generated by truncated Laplace distributions. The idea
is to let players participate in certain information aggregation process using
the perturbed payoff functions. If the LLQFP mechanism preserves differential
privacy, then it also enforces differential privacy of information aggregation
processes by the resilience to post-processing of differential privacy[16].

In the literature of differentially private information aggregation processes,
a common approach is to add noises to players’ shared information [21, 20, 26,
23, 24]. For this approach, perturbation has to be designed in accordance with
a diverse set of objectives during information aggregation processes.
Moreover, perturbation has to be added at all time steps, and therefore the
longer the operating time of information aggregation processes is, the more
amount of perturbation is required to add. Functional perturbation is easier
to implement since its design does not depend on specific tasks. In addition,
functional perturbation only adds perturbation once to produce the perturbed
payoff functions, regardless of the number of steps players participate in the
following information aggregation processes.

Functional perturbation was also proposed by [25, 22]. They studied the
distributed optimization problem subject to the requirement of differential
privacy. Their work decomposed the objective functions into an infinite
sequence of coefficients corresponding to the elements of a orthogonal basis
in a separable Hilbert space, and added noises to the infinite coefficient
sequence. Unfortunately, truncation is inevitable in practical
implementations. Our work focuses on generalizing functional perturbation to
the differentially private game setting. Instead of considering infinite
expansion, we propose a mechanism that does not involve the decomposition of
function space, but directly apply linear-quadratic functions as perturbation
avoiding the truncation problem.

Contributions In this paper, we study network games under the differential
privacy requirement for players’ payoff functions. We make the following
contributions:

  * •

We extend the notion of differential privacy to the network game setting, and
propose a Laplace linear-quadratic functional perturbation (LLQFP) algorithm,
which perturbs players’ original payoff functions with linear-quadratic
functional perturbation whose coefficients are generated according to
truncated Laplace distributions.

  * •

For monotone games, we show that the LLQFP algorithm maintains the concavity
property of the perturbed payoff functions and yields a $\gamma$-accurate
perturbed NE whose distance from the original NE is upper bounded by any
prescribed constant $\gamma$.

  * •

We investigate LQ games that players’ payoff functions are parameterized. It
serves as a tutorial example showing how Laplace parameters are selected to
ensure certain differential privacy requirement.

  * •

Experiments are conducted to verify the advantages of the LLQFP algorithm.

Organization The remainder of the paper is organized as follows. For privacy
concerns about players’ payoff functions in network games, we formalize our
problem in Section II. In Section III, we propose the LLQFP algorithm. In
Section IV, we consider monotone games, and show the advantages of the LLQFP
algorithm. In Section V, we consider LQ games, and investigate Laplace
parameter conditions that can guarantee certain different privacy requirement.
Numerical examples are presented in Section VI. This paper ends with
concluding remarks in Section VII.

##  II Problem Formulation

###  II-A Network Games

Consider a network game with $n$ players. The players are interconnected
through an interaction/communication network. The interaction/communication
network is associated with a graph $\mathrm{G}(\mathrm{V},\mathrm{E})$, where
$\mathrm{V}:=\\{1,2,\dots,n\\}$ represents the nodes (players), and
$\mathrm{E}$ defines the links (the interdependency among players). Each
player $i\in\mathrm{V}$ holds an action $x_{i}$ from a compact convex action
space $\mathcal{A}_{i}\subseteq\mathbb{R}$. The aggregated action profile of
all players and the action profile excluding player $i$ are denoted by
$\mathbf{x}:=[x_{1},\dots,x_{n}]^{\top}$ and
$\mathbf{x}_{-i}=[x_{1},\dots,x_{i-1},x_{i+1},\dots,x_{n}]^{\top}$,
respectively. Each player $i$ then receives her payoffs determined by a payoff
function, i.e., $u_{i}=f_{i}(x_{i},\mathbf{x}_{-i}),$ where the payoff
function $f_{i}\in C^{2}(\mathcal{A})$ is twice continuously differentiable
over $\mathcal{A}:=\Pi_{i\in\mathrm{V}}\mathcal{A}_{i}$.

A common solution concept in game theory is called Nash equilibrium. It
depicts an action profile under which no player may gain by simply modifying
her action while others maintain theirs unaltered. We denote the NE by
$\mathbf{x}^{\ast}:=[x_{1}^{\ast},\dots,x_{n}^{\ast}]^{\top}$.

######  Definition 1 (Nash equilibrium).

An action profile $\mathbf{x}^{\ast}$ is said to be a pure-strategy NE of a
game if $f_{i}(x_{i}^{\ast},\mathbf{x}_{-i}^{\ast})\geq
f_{i}(x_{i},\mathbf{x}_{-i}^{\ast}),\forall x_{i}\in\mathcal{A}_{i},\forall
i\in\mathrm{V}.$

Information Aggregation Processes In network games, there are many network-
level information aggregation operations that require players to share
dynamical states over a horizon $t\in\\{0,1,\dots,T\\}$ to accomplish
collective goals such as the distributed Nash seeking[4, 5, 6], best-response
dynamics[7, 8, 9], and no-regret learning[10, 11, 12, 13].

Example 1 (Distributed Nash seeking[4, 5, 6]) At time $t$, each player $i$
holds a dynamical state $\mathbf{y}_{i}(t)$ that typically consists of her
action and her estimate of other players’ actions. Then, each player $i$
shares $\mathbf{y}_{i}(t)$ with other players via certain
interaction/communication network. Next, each player $i$ updates her dynamical
state for $\mathbf{y}_{i}(t+1)$ based on the received players’ dynamical
states and her own payoff function $f_{i}$. The network-level objective is for
(perhaps part of) the sequence
$[\mathbf{y}_{1}(t);\dots;\mathbf{y}_{n}(t)],t=0,1,\dots$ to converge to a NE.

Example 2 (Best-response Dynamics[7, 8, 9]) At time $t$, each player $i$ holds
a dynamical state $\mathbf{y}_{i}(t)$ that represents her action. Then, each
$\mathbf{y}_{i}(t)$ is observed by or communicated with other players. Next,
each player $i$ updates her state $\mathbf{y}_{i}(t+1)$ as the action that
maximizes her payoff function given other players’ current actions. Best-
response dynamics is a behavioral model depicting how players strategically
make decisions in a sequential manner. Sometimes, best-response dynamics
converge to a NE.

Example 3 (No-regret Learning[10, 11, 12, 13]) At time $t$, each player $i$
holds a dynamical state $\mathbf{y}_{i}(t)$ that typically consists of her
action and her estimate of other players’ payoff gradients. Then, each player
$i$ shares $\mathbf{y}_{i}(t)$ with other players via certain
interaction/communication network. Next, each player $i$ updates her dynamical
state upon the received players’ dynamical states and her own payoff function
$f_{i}$. The network-level objective of no-regret learning is for the sequence
$\mathbf{y}_{i}(t),t=0,1,\dots$ to minimize the regret of player $i$ as the
cumulative loss compared with a plain/single action in hindsight.

###  II-B Problem Definition

Differentially Private Information Aggregation Processes  From the above
network-level information aggregation operations, it is clear that the
$\mathbf{y}_{i}(t),i=1,\dots,n,t=0,1,\dots,T$ encode the information of payoff
functions. Those states $\mathbf{y}_{i}(t)$ are shared by player $i$ with
other players. However, players’ payoff functions are often private and
contains sensitive information [14]. As a result, payoff functions face
privacy risk in the information aggregation processes.

Differential privacy has been a standard tool to protect an individual’s data
privacy in a system where aggregate information is publicly published, but
individual information is privately withheld [16]. Specifically, to protect
the differential privacy of players’ payoff functions, the mapping from
$\mathbf{f}:=[f_{1};\dots;f_{n}]$ to
$\mathbf{Y}:=[\mathbf{y}_{1}(0);\dots;\mathbf{y}_{1}(T);\dots;\mathbf{y}_{n}(0);\dots;\mathbf{y}_{n}(T)]$
should satisfy the following differential privacy condition.

######  Definition 2 ($\mathcal{W}$-adjacency [25]).

Given any normed vector space $(\mathcal{W},||\cdot||_{\mathcal{W}})$,
$\mathbf{f}$ and $\mathbf{f}^{{}^{\prime}}$ are said be $\mathcal{W}$-adjacent
if there exists $i_{0}\in\mathrm{V}$ such that

$\displaystyle f_{i}=f^{{}^{\prime}}_{i}\,,\qquad i\neq i_{0};$ (1a)
$\displaystyle f_{i_{0}}-f^{{}^{\prime}}_{i_{0}}\in\mathcal{W}.$ (1b)

The normed vector space $\mathcal{W}$ is a design choice that we specify later
according to the class of payoff functions.

######  Definition 3 ($(\epsilon,\delta)$-differential privacy).

The mapping $\mathcal{M}$ is said to preserve $(\epsilon,\delta)$-differential
privacy if for any subset
$\mathscr{M}\subseteq\textnormal{range}\big{(}\mathcal{M}\big{)}$,

$\mathbb{P}(\mathcal{M}(\mathbf{f})\in\mathscr{M})\leq
e^{\epsilon}\mathbb{P}(\mathcal{M}(\mathbf{f}^{\prime})\in\mathscr{M})+\delta,$
(2)

holds for any two $\mathcal{W}$-adjacent payoff functions $\mathbf{f}$ and
$\mathbf{f}^{\prime}$.

###  II-C Functional Perturbation

We propose a functional perturbation mechanism from $\mathbf{f}$ to
$\hat{\mathbf{f}}$ where certain perturbation is added to produce
$\hat{\mathbf{f}}$, and then players use $\hat{\mathbf{f}}$ to participate in
information aggregation processes. As a result, the privacy of players’ payoff
functions $\mathbf{f}$ may be protected in the sense that Definition 3 may be
satisfied. If the mapping from $\mathbf{f}$ to $\hat{\mathbf{f}}$ preserves
differential privacy, then differential privacy of the mapping from
$\mathbf{f}$ to $\mathbf{Y}$ is also enforced by the immune to post-processing
[16].

There are a few practical challenges in designing such a mechanism:

  * •

Differential privacy of the functional perturbation mechanism from
$\mathbf{f}$ to $\hat{\mathbf{f}}$ should be provable.

  * •

The basic regularity property of the game should be maintained. In particular,
if $\mathbf{f}$ are concave, $\hat{\mathbf{f}}$ should be also concave.

  * •

The distance between the NE of the original game and the NE of the perturbed
game should be upper bounded and adjustable by parameter tuning.

In this paper, we aim to develop a distributed algorithm to realize this
functional perturbation mechanism that can address the above challenges.

##  III The Proposed Algorithm

The truncated Laplace distribution truncated by $[-a,a]$ with mean zero and
scale parameter $\lambda$, denoted $\mathscr{L}_{tr}(a,\lambda)$, has
probability density function

$p(x;a,\lambda)=\left\\{\begin{array}[]{ll}Be^{-|x|/\lambda},&\mbox{for
}x\in[-a,a],\\\ 0\,,&\mbox{otherwise,}\end{array}\right.$ (3)

where $B=\frac{1}{2\lambda(1-e^{-a/\lambda})}.$

Denote the neighbors of player $i$ by the set
$\mathrm{N}_{i}\subset\mathrm{V}$. We sort the indices of player $i$’s
neighbors in ascending order in the set
$\mathrm{O}_{i}:=\\{i_{1},i_{2},\dots,i_{|\mathrm{N}_{i}|}\\}$. For example,
if player $j$ is player $i$’s $k$th neighbor, then $i_{k}=j.$

###  III-A LLQFP Algorithm

We next propose a Laplace linear-quadratic functional perturbation Algorithm
in Algorithm 1.

Algorithm 1 Laplace Linear-quadratic Functional Perturbation Algorithm

0: Laplace parameters $a,\lambda$; payoff functions $f_{1},\dots,f_{n};$

0: perturbed payoff functions $\hat{f_{1}},\dots,\hat{f_{n}}$

1: Each player $i\in\mathrm{V}$ independently generates a sequence random
numbers $\omega_{i,k}$, $k=1,\ldots,|\mathrm{N}_{i}|+2$, according to
$\mathscr{L}_{tr}(a,\lambda)$ in (3).

2: Each player $i\in\mathrm{V}$ computes  $\displaystyle
q_{ij}=\left\\{\begin{array}[]{ll}\frac{\omega_{i,(|\mathrm{N}_{i}|+1)}}{2}+\frac{a(|\mathrm{N}_{i}|+1)}{2},&j=i,\\\
\omega_{i,k},&j=i_{k},\\\ 0,&\mbox{otherwise,}\end{array}\right.$ (4d)
$\displaystyle\beta_{i}=\omega_{i,(|\mathrm{N}_{i}|+2)}.$ (4e)

3: Each player $i\in\mathrm{V}$ employs a perturbed payoff function based on
$\mathbf{q}_{i}:=[q_{i1},\dots,q_{in}]^{\top}$ and $\beta_{i}$:
$\hat{f}_{i}(x_{i},\mathbf{x}_{-i})=f_{i}(x_{i},\mathbf{x}_{-i})-x_{i}\mathbf{q}_{i}^{\top}\mathbf{x}-\beta_{i}x_{i}.$
(5)

4: return $\hat{f_{1}},\dots,\hat{f_{n}}$

Algorithm 1 perturbs the original payoff functions with linear-quadratic
functional perturbation whose coefficients are generated according to (3).
Each player $i$ first generates $|\mathrm{N}_{i}|+2$ independent truncated
Laplace noises, and then strategically inserts noises to her payoff function
in a linear-quadratic perturbation form. Each $\mathbf{q}_{i}$ in the
perturbed payoff function is not a simple stack of $|\mathrm{N}_{i}|+1$
truncated Laplace noises, but depends on the network structure and the
truncated bound $a$.

The work of [25, 22] also presented an analysis on the the mechanism of
functional perturbation via Laplace noises under the problem setting of
differentially private distributed convex optimization. The differences
between theirs and ours are as follows:

  * •

Their work was based on the assumption that the objective functions are twice
continuously differentiable functions with bounded gradients and Hessians. But
we are going to assume that the underlying game is a monotone game, which is
common in the game literature [27]. As a result, investigating whether the
basic properties of the game is maintained and characterizing the accuracy of
NE after applying Algorithm 1 are different form their framework.

  * •

Their work decomposed $\mathbf{f}$ into its coefficients by the infinite
expansion, and perturbed this infinite sequence by adding noise to all of its
elements. As a result, truncation is inevitable in practical implementations.
But we only consider linear-quadratic functional perturbation where the noise
coefficients are related with the underlying interaction graph of the game. In
a sense, the network structure of the game may be maintained.

###  III-B Positivity Guarantee

We now present a property of the coefficients generated according to
$\mathscr{L}_{tr}(a,\lambda)$, which is necessary for the Theorems later.

Denote
$\mathbf{d}_{i}=[q_{i1},\dots,q_{i(i-1)},2q_{ii},q_{i(i+1)},\dots,q_{in}]^{\top}$
and $\mathbf{D}=[\mathbf{d}_{1}\ \mathbf{d}_{2}\ \dots\ \mathbf{d}_{n}]$. Also
denote $\bm{\beta}=[\beta_{1},\dots,\beta_{n}]^{\top}$.

######  Lemma 1.

$\mathbf{D}^{\top}$ is a positive semidefinite matrix.

Proof. We focus on the magnitude of the diagonal element in each row, and the
sum of the magnitudes of all non-diagonal elements in that row. According to
(4d), we have $|2q_{ii}|\in[a|\mathrm{N}_{i}|,a(|\mathrm{N}_{i}|+2)]$ and
$\sum_{i\neq j}|q_{ij}|\in[0,a|\mathrm{N}_{i}|],\forall i\in\mathrm{V}$. Since
$|2q_{ii}|\geq\sum_{i\neq j}|q_{ij}|$, $\mathbf{D}^{\top}$ is diagonally
dominant. A symmetric diagonally dominant real matrix with nonnegative
diagonal entries is positive semidefinite. Hence, $\mathbf{D}^{\top}$ is a
positive semidefinite matrix. $\square$

##  IV Monotone Games

In what follows, we look at a class of strongly monotone games, present its
basic properties, and show the advantages of Algorithm 1.

For each $i\in\mathrm{V}$, we denote the gradient of $f_{i}$ with respect to
$x_{i}$ by $\nabla_{x_{i}}f_{i}:=\frac{\partial f_{i}}{\partial
x_{i}}\in\mathbb{R}$, and
$\bm{\phi}(\mathbf{x}):=[\nabla_{x_{1}}f_{1},\dots,\nabla_{x_{n}}f_{n}]^{\top}\in\mathbb{R}^{n}$.

We impose the following assumption of a class of strongly monotone games.

######  Assumption 1 ([23]).

For some $l_{m}>0$ and for all $\mathbf{x}^{\prime},\mathbf{x}\in\mathcal{A},$

$\sum_{i\in\mathrm{V}}(\phi_{i}(\mathbf{x})-\phi_{i}(\mathbf{x}^{\prime}))(x_{i}-x^{\prime}_{i})\leq-
l_{m}\|\mathbf{x}-\mathbf{x}^{\prime}\|^{2}.$ (6)

Assumption 1 implies that each player’s original payoff function $\mathbf{f}$
is strictly concave in $x_{i}$[27]. We introduce the definition of concavity
preservation.

######  Definition 4 (Concavity preservation [25]).

Let Assumption 1 hold. Algorithm 1 is said to be concavity-preserving if each
$\hat{f}_{i}$ is strictly concave in $x_{i}$ for all $i\in\mathrm{V}$.

###  IV-A Concavity Preservation

The following result proves that under Assumption 1, Algorithm 1 is concavity-
preserving.

######  Theorem 1.

Let Assumption 1 hold. Then, Algorithm 1 is concavity-preserving.

Proof. Under Assumption 1, each player $i$’s original payoff function is
strictly concave in $x_{i}$. We consider
$\mathbf{x}=[x_{1},\dots,x_{i},\dots,x_{n}]^{\top}$ and
$\mathbf{x}^{\prime}=[x_{1},\dots,x^{\prime}_{i},\dots,x_{n}]^{\top}$ and
obtain
$(\phi_{i}(\mathbf{x})-\phi_{i}(\mathbf{x}^{\prime}))(x_{i}-x^{\prime}_{i})<0.$

We then check the sign of
$(\hat{\phi}_{i}(\mathbf{x})-\hat{\phi}_{i}(\mathbf{x}^{\prime}))(x_{i}-x^{\prime}_{i})$
=
$(\phi_{i}(\mathbf{x})-\phi_{i}(\mathbf{x}^{\prime}))(x_{i}-x^{\prime}_{i})-2q_{ii}(x_{i}-x^{\prime}_{i})^{2}<0$,
which complies with Definition 4. $\square$

The next result shows that under Assumption 1, both original game and
perturbed game after Algorithm 1 admit a unique NE.

######  Theorem 2.

Let Assumption 1 hold. Then,

(i) the original game with the payoff functions $\mathbf{f}$ admits a unique
NE.

(ii) after Algorithm 1, the perturbed game with the perturbed payoff functions
$\hat{\mathbf{f}}$ admits a unique NE.

Proof. For (i), the class of strongly monotone games is a proper subclass of
monotone games, first introduced in [27]. Instead of the stronger requirement
in Assumption 1, the weaker assumption
$\sum_{i\in\mathrm{V}}c_{i}(\phi_{i}(\mathbf{x})-\phi_{i}(\mathbf{x}^{\prime}))(x_{i}-x^{\prime}_{i})<0$
is imposed. Every monotone game admits a unique NE [27, Theorem 2]. Therefore,
the original game under Assumption 1 also admits a unique NE.

For (ii), we are going to check whether the perturbed game is a monotone game
by investigating whether the sign of
$\sum_{i\in\mathrm{V}}(\hat{\phi_{i}}(\mathbf{x})-\hat{\phi_{i}}(\mathbf{x}^{\prime}))(x_{i}-x^{\prime}_{i})<0,\forall\mathbf{x}^{\prime},\mathbf{x}\in\mathcal{A},\mathbf{x}^{\prime}\neq\mathbf{x}.$
It is straightforward that

$\displaystyle\sum_{i\in\mathrm{V}}(\hat{\phi_{i}}(\mathbf{x})-\hat{\phi_{i}}(\mathbf{x}^{\prime}))(x_{i}-x^{\prime}_{i})$
$\displaystyle=$
$\displaystyle\sum_{i\in\mathrm{V}}(\phi_{i}(\mathbf{x})-\phi_{i}(\mathbf{x}^{\prime}))(x_{i}-x^{\prime}_{i})-\sum_{i\in\mathrm{V}}2q_{ii}(x_{i}-x^{\prime}_{i})^{2}<0.$

We draw the conclusion that the perturbed game is a monotone game, therefore
admitting a unique NE. $\square$

###  IV-B $\gamma$-accurate Nash equilibrium

According to Theorem 2, when Assumption 1 holds, both original game and
perturbed game admit a unique NE. We denote the original NE of the original
game by $\mathbf{x}^{\ast}$ and the perturbed NE of the perturbed game by
$\hat{\mathbf{x}}^{\ast}$.

We now introduce the definition of $\gamma$-accurate NE.

######  Definition 5 ($\gamma$-accurate NE).

Let Assumption 1 hold. The perturbed NE $\hat{\mathbf{x}}^{\ast}$ is said to
be $\gamma$-accurate if $\|\mathbf{x}^{*}-\hat{\mathbf{x}}^{*}\|\leq\gamma$.

In the following result, we derive an upper bound for the distance between the
original NE and the perturbed NE after Algorithm 1.

######  Theorem 3.

Let Assumption 1 hold. Further suppose that the original NE and perturbed NE
are both interior points in the action space $\mathcal{A}$. Then, the
perturbed NE is $\gamma$-accurate with

$\gamma=\frac{\sqrt{n}a+\sqrt{\sum_{i\in\mathrm{V}}(4|\mathrm{N}|^{2}_{i}+5|\mathrm{N}_{i}|+4)}a\|\mathbf{x}^{\ast}\|}{l_{m}}$
(7)

Proof. By taking the derivative of (5) w.r.t. $x_{i}$ and rewriting it in the
vector form, we obtain

$\hat{\bm{\phi}}(\mathbf{x})=\bm{\phi}(\mathbf{x})-\mathbf{D}^{\top}\mathbf{x}-\bm{\beta}.$
(8)

We now turn to the original NE and perturbed NE, whose existence and
uniqueness are guaranteed by Theorem 2. Moreover, in Theorem 3, we further
impose the assumption of interior NE. Substituting $\hat{\mathbf{x}}^{\ast}$
into Eq. (8), we have
$\bm{\phi}(\hat{\mathbf{x}}^{\ast})=\hat{\bm{\phi}}(\hat{\mathbf{x}}^{\ast})+\mathbf{D}^{\top}\hat{\mathbf{x}}^{\ast}+\bm{\beta}.$
The first-order condition for the interior NE is that
$\bm{\phi}(\mathbf{x}^{\ast})=0$ and
$\hat{\bm{\phi}}(\hat{\mathbf{x}}^{\ast})=0.$ Then, it yields
$\big{[}\bm{\phi}(\mathbf{x}^{\ast})-\bm{\phi}(\hat{\mathbf{x}}^{\ast})\big{]}-\mathbf{D}^{\top}(\mathbf{x}^{\ast}-\hat{\mathbf{x}}^{\ast})=-\bm{\beta}-\mathbf{D}^{\top}\mathbf{x}^{\ast}.$
Multiplying by $(\mathbf{x}^{\ast}-\hat{\mathbf{x}}^{\ast})^{\top}$, we
observe that

$\displaystyle-(\mathbf{x}^{\ast}-\hat{\mathbf{x}}^{\ast})^{\top}(\bm{\beta}+\mathbf{D}^{\top}\mathbf{x}^{\ast})$
$\displaystyle=$
$\displaystyle(\mathbf{x}^{\ast}-\hat{\mathbf{x}}^{\ast})^{\top}\big{[}\bm{\phi}(\mathbf{x}^{\ast})-\bm{\phi}(\hat{\mathbf{x}}^{\ast})\big{]}-(\mathbf{x}^{\ast}-\hat{\mathbf{x}}^{\ast})^{\top}\mathbf{D}^{\top}(\mathbf{x}^{\ast}-\hat{\mathbf{x}}^{\ast})$
$\displaystyle\overset{(a)}{\leq}$
$\displaystyle(\mathbf{x}^{\ast}-\hat{\mathbf{x}}^{\ast})^{\top}\big{[}\bm{\phi}(\mathbf{x}^{\ast})-\bm{\phi}(\hat{\mathbf{x}}^{\ast})\big{]}$
$\displaystyle\overset{(b)}{\leq}$ $\displaystyle-
l_{m}\|\mathbf{x}^{\ast}-\hat{\mathbf{x}}^{\ast}\|^{2}.$

The inequality (a) holds because $\mathbf{D}^{\top}$ is designed to be a
positive semidefinite matrix (See Lemma 1). The inequality (b) is exactly from
Eq. (6). Thus there holds
$(\mathbf{x}^{\ast}-\hat{\mathbf{x}}^{\ast})^{\top}(\bm{\beta}+\mathbf{D}^{\top}\mathbf{x}^{\ast})\geq
l_{m}\|\mathbf{x}^{\ast}-\hat{\mathbf{x}}^{\ast}\|^{2}>0.$

Further considering the Cauchy–Schwarz inequality, we finally obtain a bound
on the distance

$\displaystyle\|\mathbf{x}^{\ast}-\hat{\mathbf{x}}^{\ast}\|$ (9a)
$\displaystyle\leq$
$\displaystyle\frac{\|\bm{\beta}\|+\|\mathbf{D}\|\|\mathbf{x}^{\ast}\|}{l_{m}}$
(9b) $\displaystyle\leq$
$\displaystyle\frac{\sqrt{n}a+\sqrt{\sum_{i\in\mathrm{V}}(4|\mathrm{N}|^{2}_{i}+5|\mathrm{N}_{i}|+4)}a\|\mathbf{x}^{\ast}\|}{l_{m}}.$
(9c)

The proof is now completed.$\hfill\square$

######  Remark 1.

The upper bound (9c) is very conservative because it considers the worst-case
scenario in which all $q_{ij},\beta_{i},\forall i,j\in\mathrm{V}$ take their
maximum values. In comparison, the upper bound (9b) is a relatively small
bound, which is more likely to happen with high probability in realization.

##  V Linear-quadratic Games

A practical challenge of Algorithm 1 is how to select the Laplace parameters
$a$ and $\lambda$ that can ensure certain differential privacy requirement.
The selection depends on the class of payoff functions and the design choice
of $\mathcal{W}$-adjacency. In this section, we analyze a benchmark game whose
payoff functions are in the linear-quadratic form.

Denote the adjacency matrix of the interaction/communication network by
$\mathbf{G}\in\mathbb{R}^{n\times n}$, with each entry $g_{ij}\in\mathbb{R}$
denoting whether player $j\in\mathrm{V}$ is linked to player $i\in\mathrm{V}$
and also indicating the linkage intensity.

We now impose the assumption of linear-quadratic games.

######  Assumption 2.

The payoff functions of a linear-quadratic game are set as

$f_{i}(x_{i},\mathbf{x}_{-i})=-\frac{1}{2}x_{i}^{2}+b_{i}x_{i}+\sum_{j\in\mathrm{V}}g_{ij}x_{i}x_{j},\quad\forall
i\in\mathrm{V},$ (10)

where $b_{i}\in\mathbb{R}^{\geq 0}$ represents the marginal benefit of player
$i$.

Since each player $i$’s payoff functions is now parameterized by the
parameters $g_{ij}$ and $b_{i}$. Hence, it is reasonable to specify
$\mathcal{W}$-adjacency on these parameters. For example, we specify a
definition of $\mu$-adjacency for LQ games.

######  Definition 6 ($\mu$-adjacency).

Consider linear-quadratic payoff functions $\mathbf{f}$ and
$\mathbf{f}^{\prime}$. They are said to be $\mu$-adjacent if there exists
$i_{0}\in\mathrm{V}$ such that

$\displaystyle
g_{i1}=g^{\prime}_{i1},\dots,g_{in}=g^{\prime}_{in},b_{i}=b^{\prime}_{i},\quad
i\neq i_{0};$ (11a)
$\displaystyle\max\\{g_{i_{0}1}-g^{\prime}_{i_{0}1},\dots,g_{i_{0}n}-g^{\prime}_{i_{0}n},b_{i_{0}}-b^{\prime}_{i_{0}}\\}\leq\mu.$
(11b)

In what follows, we first present how the Laplace parameters $a$ and $\lambda$
are selected to guarantee $(\epsilon,\delta)$-differential privacy for one-
dimensional truncated Laplace mechanism, and then generalize this result to
differential private LQ games.

###  V-A One-dimensional Truncated Laplace Mechanism

The work of [28, 29, 30] investigated how the Laplace parameters are chosen to
meet the differential privacy criterion in the one-dimensional case. As
presented in (9c), Algorithm 1 leads to a biased perturbed NE. As a result, a
stringent analysis is required to determine the lower bounds of the Laplace
parameters that can produce a less biased perturbed NE. Compared with [28],
the following result relaxes the requirement for the Laplace parameters to
guarantee the differential privacy, and gives the tight lower bounds for $a$
and $\lambda$ in the one-dimensional case.

We consider one-dimensional truncated perturbation mechanism. Let $D$ be the
space of datasets of interest. Suppose there is a query as a function
$y:D\to\mathbb{R}$. Given $D$, a randomized mapping $\mathcal{K}$ will release
the one-dimensional response $\mathcal{K}(D)$ that is the summation of the
true query answer $y\in\mathbb{R}$ and a random noise $\eta\in[-a,a]$
following $\mathscr{L}_{tr}(a,\lambda)$, $\mathcal{K}(D)=y(D)+\eta$. The
sensitivity of one-dimensional true query is then given by $\Delta
y=\max_{D_{1},D_{2}\in D}|y(D_{1})-y(D_{2})|.$ The randomized mapping
$\mathcal{K}$ gives $(\epsilon,\delta)$-differential privacy if for any two
datasets $D_{1},D_{2}\in D$ differing in at most one element, and all
$\mathscr{K}\subseteq\textnormal{range}(\mathcal{K})$, there holds

$\mathbb{P}(\mathcal{K}(D_{1})\in\mathscr{K})\leq
e^{\epsilon}\mathbb{P}(\mathcal{K}(D_{2})\in\mathscr{K})+\delta.$ (12)

######  Lemma 2.

Given the privacy parameters $0<\delta<\frac{1}{2},\epsilon>0$, the randomized
mapping $\mathcal{K}$ preserves $(\epsilon,\delta)$-differential privacy if

$\displaystyle\lambda\geq\frac{\Delta y}{\epsilon-\ln(1-\delta)},$ (13a)
$\displaystyle a\geq\max\Big{\\{}\Delta
y,\lambda\ln\left(\frac{e^{\frac{\Delta
y}{\lambda}}-1}{2\delta}+1\right)\Big{\\}}.$ (13b)

Proof. We are seeking to show that for any $D_{1},D_{2}\in D$ differing in at
most one element, for any subset
$\mathscr{K}\subseteq\textnormal{range}(\mathcal{K}),$ Eq. (12) is satisfied.

Without loss of generality, we let $y(D_{1})\leq y(D_{2})$. Given
$\mathscr{K}\subseteq\textnormal{range}(\mathcal{K})$, there are $5$ cases to
consider, each of which should render Eq. (12) to be satisfied.

  * 1.

$\mathscr{K}\subseteq(-\infty,-a+y(D_{1})]:$ It is true that $0\leq
e^{\epsilon}\cdot 0+\delta$.

  * 2.

$\mathscr{K}\subseteq[-a+y(D_{1}),-a+y(D_{2})]:$ First, since
$\delta<\frac{1}{2}$, it is impossible to find the configuration for $a$ and
$\lambda$ that can make Eq. (12) valid when $a\leq\Delta y$. Second, we now
consider $y(D_{2})-y(D_{1})\leq\Delta y<a$. For any $D_{1}$ and $D_{2}$
differing in at most one element, to satisfy Eq. (12), we are going to show
that the probability mass in the interval $[-a+y(D_{1}),-a+y(D_{2})]$ does not
exceed $\delta$:

$\displaystyle\int_{\mathscr{K}}Be^{\frac{-|y-y(D_{1})|}{\lambda}}dy=$
$\displaystyle
B\lambda(e^{\frac{-a+y(D_{2})-y(D_{1})}{\lambda}}-e^{\frac{-a}{\lambda}})$
$\displaystyle\leq$ $\displaystyle
B\lambda(e^{\frac{-a+\Delta}{\lambda}}-e^{\frac{-a}{\lambda}})\leq\delta.$

The first inequality holds because $e^{\frac{-a+y(D_{2})-y(D_{1})}{\lambda}}$
increases when $y(D_{2})-y(D_{1})$ increases, while the second inequality
comes from the condition (13b).

  * 3.

$\mathscr{K}\subseteq[-a+y(D_{2}),a+y(D_{1})]:$ Equation (12) can be written
as $\int_{\mathscr{K}}Be^{\frac{-|y-y(D_{1})|}{\lambda}}dy\leq
e^{\epsilon}\int_{\mathscr{K}}Be^{\frac{-|y-y(D_{2})|}{\lambda}}dy+\delta.$
Using triangle inequality $|y-y(D_{2})|\leq|y-y(D_{1})|+|y(D_{1})-y(D_{2})|$
and combining the condition (13a), it is sufficient to show that
$\int_{\mathscr{K}}Be^{\frac{-|y-y(D_{1})|}{\lambda}}dy\leq
e^{\epsilon-\frac{\Delta}{\lambda}}\int_{\mathscr{K}}Be^{\frac{-|y-y(D_{1})|}{\lambda}}dy+\delta,$
or further, $1\leq e^{\epsilon-\frac{\Delta y}{\lambda}}+\delta\leq
e^{\epsilon-\frac{\Delta
y}{\lambda}}+\frac{\delta}{\int_{\mathscr{K}}Be^{\frac{-|y-y(D_{1})|}{\lambda}}dy}.$

  * 4.

$\mathscr{K}\subseteq[a+y(D_{1}),a+y(D_{2})]:$ It is true that $0\leq
e^{\epsilon}\int_{\mathscr{K}}Be^{\frac{-|y-y(D_{2})|}{\lambda}}dy+\delta.$

  * 5.

$\mathscr{K}\subseteq[a+y(D_{2}),\infty]:$ It is valid that $0\leq
e^{\epsilon}\cdot 0+\delta$.

In all, under conditions (13a) and (13b), the randomized mapping $\mathcal{K}$
preserves $(\epsilon,\delta)$-differential privacy. $\square$

###  V-B Differentially Private LQ Games

In what follows, Laplace parameter conditions are given to ensure certain
differential privacy requirement for LQ games.

Stack the non-zero elements $q_{ij}$ into $\mathbf{q}\in\mathbb{R}^{m}$ with
$m=n+\sum_{i\in\mathrm{V}}|N_{i}|$. Also stack $g_{ij}$ into
$\mathbf{g}\in\mathbb{R}^{m}$ such that each element in $\mathbf{g}$ is
matched with the corresponding element in $\mathbf{q}$. In particular, if the
$k$th element of $\mathbf{q}$ is $q_{ij}$, then the $k$th element of
$\mathbf{g}$ is $g_{ij}$. The dimension of
$\begin{bmatrix}\mathbf{g}\cr\mathbf{b}\end{bmatrix}$ is
$l=2n+\sum_{i\in\mathrm{V}}|N_{i}|$. Further define
$p=1+\max_{i\in\mathrm{V}}|N_{i}|$.

######  Theorem 4.

Consider a LQ game. Then given any $\epsilon,\delta,\mu>0$, the mapping
$\widehat{\mathcal{M}}(\mathbf{g},\mathbf{b})=\begin{bmatrix}\mathbf{g}-\mathbf{q}\cr\mathbf{b}-\bm{\beta}\end{bmatrix}$
achieves $(p\epsilon,p\delta)$-differential privacy under $\mu$-adjacency if

$\displaystyle\lambda\geq\frac{\mu}{\epsilon-\ln(1-\delta)},$ (14a)
$\displaystyle
a\geq\max\Big{\\{}\mu,\lambda\ln\left(\frac{e^{\frac{\mu}{\lambda}}-1}{2\delta}+1\right)\Big{\\}}.$
(14b)

Proof. Consider two $\mu$-adjacent linear-quadratic payoff functions
$\mathbf{f}$ and $\mathbf{f}^{{}^{\prime}}$ that are uniquely determined by
the pairs $(\mathbf{g},\mathbf{b})$ and
$(\mathbf{g}^{\prime},\mathbf{b}^{\prime})$, respectively.

Denote $\mathbf{v}=[\mathbf{g}^{\top}\
\mathbf{b}^{\top}]^{\top}\in\mathbb{R}^{l}$ and
$\mathbf{v}^{\prime}=[\mathbf{g}^{\prime\top}\
\mathbf{b}^{\prime\top}]^{\top}\in\mathbb{R}^{l}.$ Also define
$\mathrm{V}_{perturbed}=\\{1,2,\dots,l\\}$. Due to $\mu$-adjacency, there
exists $i_{0}\in\mathrm{V}$ such that the conditions (11a) and (11b) hold. We
denote by $\mathrm{V}_{diff}$ the indices of $b_{i_{0}}$ and
$g_{i_{0}j},j\in\mathrm{N}_{i_{0}}\cup\\{i_{0}\\}$, in $\mathbf{v}$. The
conditions (11a) and (11b) indicate that 1) $\mathbf{v}$ and
$\mathbf{v}^{\prime}$ differ in at most $|\mathrm{N}_{i_{0}}|+1$ elements; 2)
and for any $i\in\mathrm{V}_{diff},$ we have $|v_{i}-v^{\prime}_{i}|\leq\mu$.

Note that each $v_{i},i\in\mathrm{V}_{diff},$ is independent of any other
$v_{j},j\in\mathrm{V}_{perturbed}\neq i$. We decompose $\widehat{\mathcal{M}}$
and further notice that each component
$\widehat{\mathcal{M}}_{i}(v_{i}),i\in\mathrm{V}_{diff},$ can be viewed as a
randomization of $v_{i}$. We then apply Lemma 2 with $\Delta y=\mu$. It is
therefore straightforward that when the conditions (14a) and (14b) are
satisfied, each component
$\widehat{\mathcal{M}}_{i}(v_{i}),i\in\mathrm{V}_{diff},$ preserves
$(\epsilon,\delta)$-differential privacy.

We now examine the probability
$\mathbb{P}(\widehat{\mathcal{M}}(\mathbf{v})\in\widehat{\mathscr{M}})=\prod_{i\in\mathrm{V}_{perturbed}}\mathbb{P}(\widehat{\mathcal{M}}_{i}(v_{i})\in\widehat{\mathscr{M}}_{i}).$
There are at most $|\mathrm{N}_{i_{0}}|+1$ different elements indexed in
$\mathrm{V}_{diff}$ between $\mathbf{v}$ and $\mathbf{v}^{\prime}$, while the
remaining elements indexed in the set
$\mathrm{V}_{same}:=(\mathrm{V}_{perturbed}-\mathrm{V}_{diff})$ are the same.
Also, combining the fact that each component
$\widehat{\mathcal{M}}_{i}(v_{i}),i\in\mathrm{V}_{diff},$ is
$(\epsilon,\delta)$-differentially private, as a consequence, we can
substitute

$\displaystyle\prod_{i\in\mathrm{V}_{perturbed}}\mathbb{P}(\widehat{\mathcal{M}}_{i}(v_{i})\in\widehat{\mathscr{M}}_{i})$
$\displaystyle=$
$\displaystyle\prod_{i\in\mathrm{V}_{same}}\mathbb{P}(\widehat{\mathcal{M}}_{i}(v_{i})\in\widehat{\mathscr{M}}_{i})\prod_{i\in\mathrm{V}_{diff}}\mathbb{P}(\widehat{\mathcal{M}}_{i}(v_{i})\in\widehat{\mathscr{M}}_{i})$
$\displaystyle\leq$
$\displaystyle\prod_{i\in\mathrm{V}_{same}}\mathbb{P}(\widehat{\mathcal{M}}_{i}(v^{\prime}_{i})\in\widehat{\mathscr{M}}_{i})\prod_{i\in\mathrm{V}_{diff}}(e^{\epsilon}\mathbb{P}(\widehat{\mathcal{M}}_{i}(v^{\prime}_{i})\in\widehat{\mathscr{M}}_{i})+\delta)$

If we focus on the second product term and look at the additive contribution
of each of the $\delta$ terms, of which there are $|\mathrm{N}_{i_{0}}|+1$, we
notice that they are only ever multiplied by probabilities that are at most
one Therefore, each contributes at most an additive $\delta$:

$\displaystyle\prod_{i\in\mathrm{V}_{diff}}(e^{\epsilon}\mathbb{P}(\widehat{\mathcal{M}}_{i}(v^{\prime}_{i})\in\widehat{\mathscr{M}}_{i})+\delta)$
$\displaystyle\leq$ $\displaystyle
e^{(|\mathrm{N}_{i_{0}}|+1)\epsilon}\prod_{i\in\mathrm{V}_{diff}}\mathbb{P}(\widehat{\mathcal{M}}_{i}(v^{\prime}_{i})\in\widehat{\mathscr{M}}_{i})+(|\mathrm{N}_{i_{0}}|+1)\delta$

Then, we have

$\displaystyle\prod_{i\in\mathrm{V}_{perturbed}}\mathbb{P}(\widehat{\mathcal{M}}_{i}(v_{i})\in\widehat{\mathscr{M}}_{i})$
$\displaystyle\leq
e^{(|\mathrm{N}_{i_{0}}|+1)\epsilon}\mathbb{P}(\widehat{\mathcal{M}}(\mathbf{v}^{\prime})\in\widehat{\mathscr{M}})+(|\mathrm{N}_{i_{0}}|+1)\delta.$

Note that $i_{0}$ can be any $i\in\mathrm{V}$. Therefore,
$\widehat{\mathcal{M}}$ releases $(p\epsilon,p\delta)$-differential privacy
with $p=1+\max_{i\in\mathrm{V}}|N_{i}|$. $\square$

######  Remark 2.

Note that the privacy guarantee depends in a crucial way on how the notion of
adjacency is defined. Although we only prove the differential privacy from
$\mathbf{f}$ to $\hat{\mathbf{f}}$ for LQ games with $\mu$-adjacency in
Definition 6, it serves as a tutorial example and can be applied to other
monotone games as long as players’ payoff functions are explicitly given.

##  VI Numerical Examples

Consider a LQ game with $10$ players. Players are arranged in a ring lattice
with each player connected to $|\mathrm{N}_{i}|=4,\forall i\in\mathrm{V}$,
neighbors. (Thus, $p=5$.) Each linkage intensity is set as $0.08$. The action
space considered is relatively large, $\mathbf{x}_{i}\in[0,100],\forall
i\in\mathrm{V}$, to ensure interior original NE and perturbed NE. According to
[31], the original NE is calculated by
$\mathbf{x}^{\ast}=(\mathbf{I}-\mathbf{G})^{-1}\mathbf{b}$.

######  Experiment 1 (Validation of Theorems).

We consider $\mu=0.01$ and choose two parameter configurations

$\displaystyle\epsilon_{1}=\ln 2,\ \delta_{1}=0.05,a_{1}=0.034,\
\lambda_{1}=0.013;$ (S1) $\displaystyle\epsilon_{2}=3\ln 2,\
\delta_{2}=0.15,a_{2}=0.015,\ \lambda_{2}=0.0045,$ (S2)

where $a_{1},a_{2},\lambda_{1},\lambda_{2}$ are selected upon Theorem 4 to
guarantee differential privacy.

Under each parameter configuration, we conduct $500$ executions, in each of
which we apply Algorithm 1. Each perturbed NE is calculated by
$\hat{\mathbf{x}}^{\ast}=(\mathbf{I}-\mathbf{G}+\mathbf{D})^{-1}(\mathbf{b}-\bm{\beta})$.
We then compute $\|\mathbf{x}^{*}-\hat{\mathbf{x}}^{*}\|$, and $\gamma$
according to (9b).

Figure 1: The comparison of $\gamma$ and
$\|\mathbf{x}^{*}-\hat{\mathbf{x}}^{*}\|$ between two parameter configurations
(S1) and (S2).

In Fig. 1, we plot the comparison of $\gamma$ and
$\|\mathbf{x}^{*}-\hat{\mathbf{x}}^{*}\|$ between two parameter configurations
(S1) and (S2). The result of Fig. 1 is consistent with Theorem 3 that the
distance between the original NE and the perturbed NE is bounded by $\gamma$
while preserving differential privacy. $\square$

######  Experiment 2 (Benchmark with Existing Methods).

Based on Experiment 1, we further plot each player’s original NE and
distribution of the perturbed NE under two parameter configurations (S1) and
(S2) among $500$ executions.

The result of Fig. 2 shows that most perturbed NE under (S1) and (S2) are
located to the left of the original NE. The parameter configuration (S2) has a
weaker requirement for differential privacy. The perturbed NE under (S2) are
closer to the original NE, implying that one has to sacrifice the differential
privacy of payoff functions for the accuracy of NE.

Figure 2: The original NE and the distribution of the perturbed NE under the
parameter configurations (S1) and (S2). The y-axis represents the number of
times that player $i$’s perturbed NE action occurred within the intervals set
by the x-axis among $500$ executions.

To further show the relevance among the accuracy of NE, the privacy
requirement $\epsilon$ and the Laplace parameter $a$, we fix $\delta=0$ and
plot $\|\mathbf{x}^{*}-\hat{\mathbf{x}}^{*}\|/\|\mathbf{x}^{\ast}\|$ versus
$\epsilon$ and $a$ each for $50$ executions in Fig. 3. Roughly speaking, it
shows that as $\epsilon$ decreases (stricter privacy), the Laplace parameter
$a$ increases and thus the accuracy of NE decreases.

Compared with existing methods of state/communication perturbation[32, 20,
23], we both show the tradeoff between the accuracy of the optimal points/NE
and the privacy of objective functions/payoff functions, However, they prove
that $\lim_{k\to\infty}\mathbb{E}(\|\mathbf{x}(k)-\mathbf{x}^{\ast}\|^{2})$
has a upper bound depending on convergence rate and privacy level. According
to the structure of their privacy algorithm, they might produce a
asymptotically unbiased perturbed NE. Unlike those results, Algorithm 1 always
produces a biased perturbed NE. It arises from $\mathbb{E}(q_{ii})>0,\forall
i\in\mathrm{V}$ that are necessary to ensure the concavity of the perturbed
payoff function. However, they have to add perturbation to communications at
all time steps. For example, in [32], it takes roughly $4000$ steps to reach a
close distance from $\mathbf{x}^{\ast}$, in each of which perturbation is
added to players’ state. In contrast, we only add perturbation to the original
payoff functions once, after which the computation of the distributed NE is
deterministic. The number of linear-quadratic perturbation coefficients (non-
zero $q_{ij},\beta_{i},\forall i,j\in\mathrm{V}$) generated by Algorithm 1 is
only $60$, which is far less than theirs. $\square$

Figure 3: The plot of
$\|\mathbf{x}^{*}-\hat{\mathbf{x}}^{*}\|/\|\mathbf{x}^{\ast}\|$ versus
$\epsilon$ and $a$ each for $50$ executions.

######  Experiment 3 (Tradeoff between Privacy and Payoffs).

Upon Experiment 1, we further compute the players’ payoffs at the original NE
and the perturbed NE under two parameter configurations,
$\mathbf{f}(\mathbf{x}^{\ast})$ and $\mathbf{f}(\hat{\mathbf{x}}^{\ast})$, and
plot them in Fig. 4,.

From the result of Fig. 4, it is not surprising that players’ payoffs at the
perturbed NE under (S1) and (S2) are always lower than those at the original
NE. Players’ payoffs at the perturbed under (S1) are lower than those at the
perturbed NE under (S2). It indicates that the sacrifice of the accuracy of NE
for payoff functions’ privacy leads to the decline of players’ payoffs.

Figure 4: Players’ payoffs at the original NE, the perturbed NE in (S1), and
the perturbed NE in(S2). The y-axis represents the value of player $i$’s
payoffs.

$\square$

##  VII Conclusion

In this work, we investigated network games in which players participated in
information aggregation processes under the differential privacy requirement
for players’ payoff functions. The LLQFP mechanism was proposed. We turned to
monotone games, demonstrating that the LLQFP mechanism preserved the concavity
property and generated a bounded perturbed NE which was controllable by
Laplace parameter tuning. We also looked at LQ games as a pedagogical example
to explain, given what Laplace parameter conditions, differential privacy of
the LLQFP mechanism could be ensured. Finally, numerical examples were
presented to demonstrate the benefits of the LLQFP mechanism.

## References

  * [1] Y. Leng, Y. Chen, X. Dong, J. Wu, and G. Shi, “Privacy risks of social interaction structure: Network learning in quadratic games,” _Available at SSRN 3875878_ , 2021.
  * [2] L. Bianco, M. Caramia, S. Giordani, and V. Piccialli, “A game-theoretic approach for regulating hazmat transportation,” _Transportation Science_ , vol. 50, no. 2, pp. 424–438, 2016.
  * [3] D. Niyato and E. Hossain, “Competitive pricing for spectrum sharing in cognitive radio networks: Dynamic game, inefficiency of nash equilibrium, and collusion,” _IEEE journal on selected areas in communications_ , vol. 26, no. 1, pp. 192–202, 2008.
  * [4] F. Salehisadaghiani and L. Pavel, “Distributed nash equilibrium seeking: A gossip-based algorithm,” _Automatica_ , vol. 72, pp. 209–216, 2016.
  * [5] F. Parise, B. Gentile, S. Grammatico, and J. Lygeros, “Network aggregative games: Distributed convergence to nash equilibria,” in _2015 54th IEEE Conference on Decision and Control (CDC)_. IEEE, 2015, pp. 2295–2300.
  * [6] M. Ye and G. Hu, “Distributed nash equilibrium seeking by a consensus based approach,” _IEEE Transactions on Automatic Control_ , vol. 62, no. 9, pp. 4811–4818, 2017.
  * [7] E. Hopkins, “A note on best response dynamics,” _Games and Economic Behavior_ , vol. 29, no. 1-2, pp. 138–150, 1999.
  * [8] A. Matsui, “Best response dynamics and socially stable strategies,” _Journal of Economic Theory_ , vol. 57, no. 2, pp. 343–362, 1992.
  * [9] N. Nisan, M. Schapira, G. Valiant, and A. Zohar, “Best-response mechanisms.” in _ICS_. Citeseer, 2011, pp. 155–165.
  * [10] T. Lin, Z. Zhou, W. Ba, and J. Zhang, “Optimal no-regret learning in strongly monotone games with bandit feedback,” _arXiv preprint arXiv:2112.02856_ , 2021.
  * [11] M. Bravo, D. Leslie, and P. Mertikopoulos, “Bandit learning in concave n-person games,” in _Proceedings of the 32nd International Conference on Neural Information Processing Systems_ , ser. NIPS’18. Curran Associates Inc., 2018, p. 5666–5676.
  * [12] Z. Zhou, P. Mertikopoulos, S. Athey, N. Bambos, P. W. Glynn, and Y. Ye, “Learning in games with lossy feedback,” _Advances in Neural Information Processing Systems_ , vol. 31, 2018.
  * [13] G. J. Gordon, A. Greenwald, and C. Marks, “No-regret learning in convex games,” in _Proceedings of the 25th international conference on Machine learning_ , 2008, pp. 360–367.
  * [14] J. C. Harsanyi, “Morality and the theory of rational behavior,” _Social research_ , pp. 623–656, 1977.
  * [15] C. Dwork, “Differential privacy: A survey of results,” in _International conference on theory and applications of models of computation_. Springer, 2008, pp. 1–19.
  * [16] C. Dwork, A. Roth _et al._ , “The algorithmic foundations of differential privacy.” _Found. Trends Theor. Comput. Sci._ , vol. 9, no. 3-4, pp. 211–407, 2014.
  * [17] Z. Huang, S. Mitra, and G. Dullerud, “Differentially private iterative synchronous consensus,” in _Proceedings of the 2012 ACM workshop on Privacy in the electronic society_ , 2012, pp. 81–90.
  * [18] E. Nozari, P. Tallapragada, and J. Cortés, “Differentially private average consensus: Obstructions, trade-offs, and optimal algorithm design,” _Automatica_ , vol. 81, pp. 221–231, 2017.
  * [19] J. Le Ny and G. J. Pappas, “Differentially private filtering,” _IEEE Transactions on Automatic Control_ , vol. 59, no. 2, pp. 341–354, 2013.
  * [20] S. Han, U. Topcu, and G. J. Pappas, “Differentially private distributed constrained optimization,” _IEEE Transactions on Automatic Control_ , vol. 62, no. 1, pp. 50–64, 2016.
  * [21] Z. Huang, S. Mitra, and N. Vaidya, “Differentially private distributed optimization,” in _Proceedings of the 2015 international conference on distributed computing and networking_ , 2015, pp. 1–10.
  * [22] E. Nozari, P. Tallapragada, and J. Cortés, “Differentially private distributed convex optimization via functional perturbation,” _IEEE Transactions on Control of Network Systems_ , vol. 5, no. 1, pp. 395–408, 2018\.
  * [23] M. Ye, G. Hu, L. Xie, and S. Xu, “Differentially private distributed nash equilibrium seeking for aggregative games,” _IEEE Transactions on Automatic Control_ , vol. 67, no. 5, pp. 2451–2458, 2021.
  * [24] M. Shakarami, C. De Persis, and N. Monshizadeh, “Distributed dynamics for aggregative games: Robustness and privacy guarantees,” _International Journal of Robust and Nonlinear Control_ , vol. 32, no. 9, pp. 5048–5069, 2022\.
  * [25] J. Cortés, G. E. Dullerud, S. Han, J. Le Ny, S. Mitra, and G. J. Pappas, “Differential privacy in control and network systems,” in _2016 IEEE 55th Conference on Decision and Control (CDC)_. IEEE, 2016, pp. 4252–4272.
  * [26] C. Zhang, M. Ahmad, and Y. Wang, “Admm based privacy-preserving decentralized optimization,” _IEEE Transactions on Information Forensics and Security_ , vol. 14, no. 3, pp. 565–580, 2018.
  * [27] J. B. Rosen, “Existence and uniqueness of equilibrium points for concave n-person games,” _Econometrica: Journal of the Econometric Society_ , pp. 520–534, 1965.
  * [28] Q. Geng, W. Ding, R. Guo, and S. Kumar, “Tight analysis of privacy and utility tradeoff in approximate differential privacy,” in _International Conference on Artificial Intelligence and Statistics_. PMLR, 2020, pp. 89–99.
  * [29] W. L. Croft, J.-R. Sack, and W. Shi, “Differential privacy via a truncated and normalized laplace mechanism,” _arXiv preprint arXiv:1911.00602_ , 2019.
  * [30] N. Holohan, S. Antonatos, S. Braghin, and P. Mac Aonghusa, “The bounded laplace mechanism in differential privacy,” _arXiv preprint arXiv:1808.10410_ , 2018.
  * [31] C. Ballester, A. Calvó-Armengol, and Y. Zenou, “Who’s who in networks. wanted: The key player,” _Econometrica_ , vol. 74, no. 5, pp. 1403–1417, 2006.
  * [32] T. Ding, S. Zhu, J. He, C. Chen, and X. Guan, “Differentially private distributed optimization via state and direction perturbation in multiagent systems,” _IEEE Transactions on Automatic Control_ , vol. 67, no. 2, pp. 722–737, 2021.