Optimized Data Sharing with Differential Privacy: A Game-theoretic Approach
Nan Wu, *,‡ , David Smith, *,§ , and Mohamed Ali Kaafar, *,‡‡Macquarie University, * CSIRO’s Data61, § Australian National University
nan.wu5@hdr.mq.edu.au, david.smith@data61.csiro.au, dali.kaafar@mq.edu.au

Abstract
We study and optimize the differentially private learning
outcomes from data shared amongst multiple separate dataowners according to a classical privacy versus accuracy
trade-off using a game-theoretic approach. A dynamic noncooperative game, with imperfect information, provides thisoptimal tradeoff, with differentially private models that learn
from the data. In this model, we make an optimal choice ofprivacy budget parameter from the Laplace mechanism, according to pure differential privacy. The data analysis model
uses differentially private gradient queries, as privacy aware
supervised-machine learning. Then, we use non-cooperative
game theory to analyse and optimize the utility-leakage tradeoff to minimize learning loss achieving a unique Nash equilibrium (mutual best response). We quantify the quality of the
trained model with a novel method to capture the trade-off
between privacy and utility (accuracy). Our novel method uses
fixed-point theory in gradient descent learning to predict thecontraction mapping of the outcomes. We validate the collaborative learning method applied with our non-cooperative gameover a partitioned real financial dataset, demonstrating benefitsof sharing data for all data-owners, with significant benefits insocial welfare from applying our game.

Introduction
For the sake of enhancing efficiency and capacity of theinternet of things (IoT), edge computing allows data to betransferred and processed at the edge of the network suchas at a cloud aggregator or end devices (Dwork and Pappas 2017; Shi et al. 2016). In such networks, data analysis
methods using machine learning (ML) can unlock valuable
insights for improving revenue or quality-of-service from,potentially proprietary, private datasets (Hunt et al. 2018;
Graepel, Lauter, and Naehrig 2012). The shared informationfrom the data owners in a particular IoT network can thencontribute to training ML models.
Due to the nature of learning, having large high-quality
datasets improves the quality of trained ML models interms of the accuracy of predictions on potentially untested
data (Dwork, Roth et al. 2014). The subsequent improvements in quality motivate multiple data owners to shareand merge their datasets in order to create larger training
Copyright c 2021, Association for the Advancement of Artificial
Intelligence (www.aaai.org). All rights reserved.

datasets for federated training (Li et al. 2017; Konečnỳ et al.
2016). For instance, financial institutions may wish to merge
their transaction or lending datasets to improve the qualityof trained ML models for fraud detection or computing interest rates. However, this shared information between data
owners will inevitably have sensitive data which the owners
wish to protect. As such data owners are independent of eachother, they will be concerned about their own data safety in acollaborative learning settings.
We consider multiple learners aim to train separate privacyaware ML models with similar structures based on their own
datasets and differentially private (DP) responses from otherlearners and private data owners as shown in Figure 1. Eachdata owner trains a separate ML model and sends the differentially private response to other participants for collaborative
learning. This is similar to distributed ML on arbitrary connected graphs. This way, we can extend the results to moregeneral communication structures with the learner not necessarily at the center. Note that the latter configuration where
the communication structure among the learner and the data
owners is set up as a star graph with the learner at the centerhas been considered in prior research, e.g. (Wu et al. 2020;
Farokhi et al. 2020).
In this paper we first use Banach fixed point theory to geta more accurate prediction of the learning loss (Jung 2017).
The next challenge is to significantly improve the utilityprivacy trade-off in terms of the quality of the trained ML
models; so our results of learning outcome prediction can beused in conjunction with the cost of sharing private data of
consumers with the learner (in terms of loss of reputation, legal costs, implementation of privacy-preserving mechanisms,
and communication infrastructure). To address this, we establish a game-theoretic framework for modelling interactions
across a data market. The learner can compensate the data
owners for access to their private data, by essentially paying
them for choosing larger privacy budgets(i.e.,more relaxedprivacy). After negotiations between the data owners and thelearners for setting privacy budgets, the ML models can betrained and tradeoff between learning loss and privacy level.
Related Work. Optimization of the trade-off between privacy and utility has been discussed well in the literature(Kalantari, Sankar, and Sarwate 2018; Brenner and Nissim
2010; Ghosh, Roughgarden, and Sundararajan 2012; Gupteand Sundararajan 2010). In a previous paper, the problem

queryDP response
query
Data owner 1

Data owner 4

DP response
query

Data owner 3

DP response
Figure 1: The communication structure between the distributed data owners (learners) for submitting queries andproviding differentially-private (DP) responses to each other.
The dashed lines are DP responses and solid lines are queries.

System Model
We assume that there are several data owners training theirown machine learning parameters with both their own dataset
and other private datasets. They send queries to each otherand respond with a randomised answer as in Figure 1.
Thus, the system setup incorporates multiple data owners
sharing data by sending a query and answering with good, but
not precise accuracy. For brevity, a data owner that trains theirmodel according to others responses is denoted as an analyst,
whilst when a data owner replies to a query, by adding noise
to the query, we denote that owner as an agent. Importantly,
a data owner trains its own ML model simultaneously in ourfederated learning model.
In this work, we assume that an agent i perturb query’s
exact answer by adding Laplace noise with variance σi2 : zi =yi +ni , where ni is a zero-mean random variable with respect
to Differential Privacy. The agent sends to the analyst boththe perturbed query answer and the the variance that provides
the accuracy.
We extend the existing framework to multiple learners
aiming to train their own ML models according to each others’
separate privacy aware sub-gradient responses.

Definitions
A group of N ∈ N private agents or data owners N :={1, . . . , N } are connected to each other and train their own
ML model over an undirected communication graph as in
Figure 1.

DP responsequery

DP response

query

query

DP response

query

query

Contributions
In this paper, we evaluate the collaborative learning modelwith DP from a fixed-point view of linear regression contraction problem. This way, we make a precise prediction of thelearning parameter in ML model. We distributedly optimize
the trade-off of utility and privacy in collaborative learning
using a non-cooperative game, with imperfect information,
between multiple data owners. More specifically, this paper
makes the following contributions:• We build a non-cooperative game model for these learners
to optimally trade-off accuracy and privacy, according to
privacy budget and gain with minimised learning loss.
• We demonstrate a unique Nash equilibrium for this game,providing a mutual best response in terms of the differentially private shared data and its learning loss. Moreover, this unique Nash equilibrium is demonstrated to be
maintained with imperfect information with data owners
simultaneously sharing, and learning from, each others’
data.
• We use a Banach fixed-point of view on gradients responses to modify the learning algorithm and to evaluate
learning iteration speed.
• Our numerical tests built on real financial datasets, where
each learner is training for an expectation of annual loan
rate with a list of users’ data including sensitive information, demonstrate the significant benefits of learning using
our game with differentially-private collaborative machinelearning.

Data owner 2
DP response

DP responseof optimizing utility for differential privacy using linear programming has been solved (Bordenabe, Chatzikokolakis, andPalamidessi 2014). In another work (Xu et al. 2015) , thetrade-off between data utility and privacy preservation is
discussed with respect to how game theory can be used tocomplete this trade-off. In (Xu et al. 2015) a sequential gamemodel is constructed between data user and data collector
followed by backward induction reaching a subgame perfectNash Equilibrium. In another work, (Xu et al. 2016), theauthors focus on the idea of exchanging private information
for money or other incentives provided to the data owner by
the data collector. And then they discuss how to use gametheory to obtain an agreement between the parties involvedin this trade.
Distributed/Collaborative Privacy-Preserving Machine
Learning (ML) has been investigated in (Shokri and
Shmatikov 2015; Huang et al. 2018; Zhang, He, and Lee
2018; Zhang and Zhu 2017; Wu et al. 2020). Stochastic gradient descent is utilized in distributed ML models with additive
Gaussian/Laplace noise to ensure differential privacy. By
appropriately selecting step size in the stochastic gradientdescent, the quality of the trained ML model based on theprivacy budget can be forecast according to (Wu et al. 2020).
In a work by (Jung 2017), authors study the basic gradientdescent iterations in ML models from the contraction viewof a specific operator with a differentiable objective function.
They show how gradient descent can be accelerated in ML
models, preserving fixed-points with faster convergence, by
the contraction mapping theorem.

Each agent has access to a set of private training datai
Di := {(xi , yi )}ni=1⊆ X × Y ⊆ Rpx × Rpy , where xi andyi , respectively, denote inputs and outputs.
In linear regression for training home loan datasets, eachdata owner i computes its private datasets Xi , and use arandomised privacy algorithm to perturb the answer thenreplies to the query sender. Let (Di , i ∈ N ) denote theaggregate of all the training datasets. Each data owner, forinstance, could be a private bank/financial institution. In thiscase, the private datasets can represent information about
loan applicants (such as gender, age, salary, and employment
status). Categorical attributes, such as gender, can always betranslated into numerical ones according to a rule as inputs,
and historically approved interest rates per annum by thebank are outputs.
The participants in a collaborative machine learning model
are interested in finding the relationship between explanatory
variables and real valued outcomes by using a ML model
M : RkXk → RkYk , where X are inputs and Y are outputs
come from the available training datasets Di , ∀i ∈ N .
The training model is to solve the optimization problem ofminimising the learning loss in
#
"
1 X X
∗
g2 (M(x; θ), y) ,θ ∈ arg min g1 (θ) +nθ∈Θj∈N {x,y}∈Dj(1)P
where g1 (θ) is a regularizing term, n :=`∈N n` , andΘ := {θ ∈ Rpθ | kθk∞ ≤ θmax }. g2 (M(x; θ), y) is theloss function which measures the distance between the ML
outcome M(x; θ) and the real output y. In a linear regression
training model, this problem can become to optimize withg1 (θ) = 0 and g2 (M(x; θ), y) = kM(x; θ) − yk22 which is a
Mean Squared Error(MSE) function in equation (1).
Also, in a collaborative training model with a similar structure to (Wu et al. 2020), the data owners not only train with
their local dataset but also with other learning agents’ datasets.
So the data owners send queries to each other. Q denotes theoutput space of the query. In this paper, the query used is the
sub-gradient of the loss function g2 (·).
Because we use a MSE function for g2 loss function, it
is a convex function of θ. In the absence of privacy concerns, every data owner i trains its ML model with both thedataset from itself and the original private dataset from neighbouring data owners with unfettered access. The ML modelfor data owner i can be trained by following the projected
sub-gradient descent iteration :θi [k + 1] = ΠΘi [θi [k] − ρk ξgx,y(θi [k])],2(2)where ρk > 0 is the step-size at iteration k, ξgx,y(θi [k]) =2∂θ g2 (M(x; θ), y) is a sub-gradient of the loss function g2 (·)
with respect to the variable θ at θ[k] (Shor 2012), and ΠΘ [·]denotes a projection operator into the set Θ defined asΠΘ [a] := arg minb∈Θ ka − bk2 to prevent overfitting. For
continuously differentiable functions, the gradient is the only
sub-gradient.

The update law for learning iterations can be rewritten as"#
ρk X X
θ[k + 1] = ΠΘ θ[k] −ξg2x,y (θ[k]) ,n`∈Nj {x,y}∈D`#"ρk Xn` Q` (D` ; k) , (3)= ΠΘ θ[k] −n`∈Nj \{j}where ξg2x,y is a sub-gradient of g2x,y , and Q` (D` ; k) is aquery that can be submitted by the learning agent to data
owner ` ∈ N in order to provide the aggregate sub-gradient:X
1Q` (D` ; k) =ξg2x,y (θ[k]).
(4)n`{x,y}∈D`

Responding to the query Q` (D` ; k) clearly intrudes on theprivacy of the individuals in dataset D` . Therefore, data
owner ` only responds in a differentially-private manner byreporting the noisy aggregate:Q` (D` ; k) = Q` (D` ; k) + w` [k],(5)where w` [k] is an additive noise to establish differential privacy with privacy budget ` over the total iterations number
T.
The response of data owner is -differentially private overthe learning iterations T .
Definition 1 (Differential Privacy). The response policy ofdata owner ` ∈ N is ` -differentially private over the horizon
T if




T
0
T
P (Q` (D` ; k))k=1 ∈ Y ≤ exp(` )P (Q` (D` ; k))k=1 ∈ Y ,where Y is any Borel-measurable subset of QT (Wu et al.
2020).

Banach fixed point contraction
Now we are going to interpret gradient methods as fixed-point
iterations to analyze convergence properties and contraction
rates.
In this work, we assume collaborative learning with multiple data owners who are training their own machine learningmodels respectively. If there is no concern for privacy, thetrained dataset is the same for each data owner and is theaggregate of all data (Dj , j ∈ N ). However in our case we
assume that data owners do not wish to share all dataset details, rather each learner i trains their ML model with theirown dataset Di and the sub-gradient response from other data
owners. When there is no differentially-private noise added tothe query responses, we use Dall = (Dj , j ∈ N ) to denotethe aggregate of the training datasets in the collaborative ML
model.
The object of the interest is to minimize the loss function
g2 (·) in equation (1). In linear regression, we wish to predict
the output Y by a linear combination of the features:
Y 0 = θX 0 .

The loss function is to minimize the following Mean Square
Error f (θ):
f (θ) = kθX 0 − Y 0 k22
Our linear regression model in equation (3) can be turned
into be the following iteration problem:"
ρk 2
θi [k + 1] = θi [k] −(θi [k]Xi0 − Yi0 )Xi
(6)
n` ni
#
X
2
0
0
+
( (θj [k]Xj − Yj )Xj + w(j; k; j )) ,nj

Lemma 2. Assume that for some q ∈ [0, 1), we havekT ρ a − T ρ bk ≤ qka − bk,(10)for any a, b ∈ Rn . Then, the operator T ρ has a unique fixed
point θ0 and the iterates θ(k) satisfykθ(k) − θ0 k ≤ q k kθ(0) − θ0 k.

(11)

The contraction rate q is as following:q ≥ kI −ρni 2∇ f (θ)kn`(12)j∈N \{i}Then we define this iteration problem for linear regression
model as a contraction problem from a fixed point of viewon gradient methods.
Definition 2. The operation of the fixed point iterations problem is T ρ : Rn : R : θ → T (θ)
"
#
ρk 2
0
0
T (θi [k + 1]) = θi [k] −(θi [k]Xi − Yi )Xi + Qi [k]
n` ni
(7)
where Qi [k] is the received query responses from all otherdata owners at iteration k:
X
2
Qi [k] =( (θj [k]Xj0 − Yj0 )Xj + w(j; k; j ))njj∈N \{i}(8)For brevity, we extract the first part in equation (8) together
with the sub-gradient of data owner i to be the sub-gradientof the aggregation of all datasets (Di , i ∈ N ). Then D` =(Di , i ∈ N ), X` = (Xi , i ∈ N ),Y` = (Yi , i ∈ N ).
Lemma 1. We have ∇f (θ) = 0 if and only if the vectorθ ∈ Rn is a fixed point of the operator T ρ . Thus, ∇f (θ) = 0
if and only if T ρ (θ) = θ, θ` = (Y`0 − n`2−1 E(` )X`−1 )X`0−1 .
See proof in Appendix.
∂T (θ)
2ρk= I ⊗ I − 2 · (X`> · X` )> ⊗ I
∂θ
n`

(9)

By properly select the value for step size ρk , ∂T∂θ(θ) = 0 canbe reached.
A straightforward approach to finding the fixed-point ofan operator T ρ is by the fixed-point iteration
θ(k+1) = T ρ θ(k) .
However, because all data owners are training their own
learning model and update their learning parameter θj after
each iteration, Qi changes in each iteration. Also noise powerw(j; k; j ) from each data owner j is changing in each DP
query response.
Then, we look into the contraction rate for this fixed-point
iteration problem.

See proof in Appendix.
Following equation (11) and (12), we can find the smallest
q and then get a minimum value for total ML iteration timeT.
The learning loss parameter can be predicted by using
Lemma 2, with a knowledge of previous iteration k − 1 contracting parameter T ρ (θk−1 ) and θk−1 . We thus note, that
then, when the game is played between data owners, this implies imperfect information because each owner is updating
there chosen epsilon according to the last known parameterk − 1 as opposed to the kth parameter.:T ρ (θk ) = T ρ (θk−1 ) + (θk − θk−1 )(I − ρ∇2 f (θ)
2ρ X
nj E(w(j; k; j )))
−
n`

(13)

j∈N\{i}= T ρ (θk−1 ) + (θk − θk−1 )(I −
−

2ρ
n`

X

2ρ 0
X X`
n` `

nj E(w(j; k; j )))j∈N \{i}Following equation (13), the learning parameter θ at next
iteration k + 1 can be predicted in iteration k, and thus theloss function. This is related to the total number of data sizen` and the privacy budget value j from all other data owners
j ∈ N \ {i}.
Theorem 1. The learning parameter θk+1 for next iteration
can be predicted by current and previous learning parameterθk−1 and θk :
θk+1 = θk + (θk − θk−1 )(I −
−

2ρ
n`

X

2ρ 0
X X`
n` `

(14)

nj E(w(j; k; j )))j∈N \{i}Corollary 1. When k is large enough and the ML models for
all players have reach a dynamic fixed point, the learningparameter θk can be predicted as:θk+1 = θk − (θk − θk−1 )

2ρ
n`

X

nj E(w(j; k; j ))j∈N \{i}(15)Algorithm 1 Non-cooperative game implementation
Require: T
Ensure: (θ[k])Tk=1
1: Initialize θ[1]2: for k = 1, . . . , T − 1 do
3:Learner submits query Q` (D` ; k) to data owners in N
4:
5:

Data owners return DP responses Q` (D` ; k)Learner follows the update rule


X n`
ρ
θ[k + 1] = θ[k] − 2 ξg1 (θ[k]) +Q` (D` ; k) ,
T k
n
`∈N

6:
7:

for i = 1, . . . , nplayers do
Learner i compute new,i byreal value in dataset. The more accurate learning predictionis, the lower the cost.
The second component f at time slot k represents the
Banach contraction parameter at k, hence dynamic, and is
non-negative continuous and increasing given as follows:f (i ) =(13) T ρ (θk )

(17)

2ρ
= T ρ (θk−1 ) + (θk − θk−1 )(I − X`0 X`n`2ρ X
nj w(j, k, j ))−n`j∈N \{i}As stochastic gradient descent is utilized, we use the averaging magnitude of the noise power for brevity.
mi,k X 1
w(i, k, i ) = 2
.
(18)
n
2i

new,i = arg min Ji (1 , 2 , ...nplayers )

8:
end for
9: end fori∈N

Game Model
We adopt a dynamic noncooperative repeated game G =[N , i , Ji,τ (·)] at each time stage τ of gameplay, where n =1, ..., N are the player/data-owners in N ; i = [0.1, 10] is the(pure) strategy set for the ith data owner; and Ji,τ (·) is thecost function for data owner i . The space of action profiles
for the N players in each stage is  = 1 × 2 ×, . . . N .
The game G is finitely repeated T < ∞ times, with imperfect information. With respect to imperfect information,
all data owners send data to each other, and decisions are
made concurrently by data owner i, without the knowledgeof others’ −i decisions; this process is then repeated T times.
A data owner may be reluctant to give a less noisy responseto the analyst. However, this will in return incurs a cost for
its own training model. We model these considerations into
cost functions. The higher the variance of the perturbationnoise is, the lower the cost for privacy violation is. On theother hand, high noise variance reduce the accuracy of thelearning model and hence incurs a higher training loss.
Each data owner i ∈ N chooses an action i ∈ [0.1, 10] tominimize cost
Ji (i , −i ) = ci (i ) + f (i )(16)Assumption 1. For all participants i, cost function ci (i )is assumed to be non-negative continuous non decreasing
function regarding to privacy budget i .
The first component ci : R → R in the cost function isreferred as disclosure cost , which is thus non-negative continuous decreasing (Zhan et al. 2020; Taghizadeh, Kebriaei, andNiyato 2020). We use ci = a ∗ bi , where a and b ∈ [2, 3, 4]
are scale constant value constant selected with respect to theterm f (i ). It measures how much it costs to perturb the response. A lower noise variance, will then increase the cost.
The second component is the loss function in the learningmodel. It gives the distance between the prediction and thewhere mi,k is a parameter chosen according to the step sizein each iteration in learning.
That is increasing the precision (lower noise variance)
leads to a higher disclosure cost. In contrast, increasing theaccuracy helps training learning model and decrease the prediction cost.

Unique Nash Equilibrium
A Nash Equilibrium is a strategy profile ε∗ satisfying∗i ∈ arg min Ji (i , −i )(19)for all i ∈ N .
We first observe that i is a nonempty, convex, compact
subspace of a Euclidean space RN . At each iteration, eachhas a strategy space that is continuous and defined by a minimum, a maximum, and all  in between.
Proposition 1. ∗ is a unique Nash equilibrium with costfunctions Ji (i , −i ) that are continuous and strictly convex.
See proof in Appendix.

Experimental Validation
In this section, numerical tests are in two scenarios.
The first scenario is collaborative learning with privacy
concerns. In this case, there are multiple data owners training
with both their own datasets and the Sub-gradient response
which contains useful information in ML training model fromeach other. Differentially private noise is added to the query
response to ensure privacy.
The second scenario is collaborative learning with privacy
concerns with game theory adjusting the magnitude of differentially private noise. In this case, for each data owner i,the privacy budget i is updated in each game stage so as
to balance the utility and privacy leakage regarding to thelearning loss and privacy budget respectively.
The Home Loans dataset and the interest rates prediction Application We use a lending dataset with a linear

10

10 6

data1
data2
data3

9

Learning Loss (MSE)

8

5
4

7
3
2

f (θ[k])

6

10 4

1
5
2

4

6

8

10

4

3

2

10

2

1

10 -1

10 0

10 1

Figure 2: Statistic of Learning loss (MSE) versus privacy
budget . The solid blue line is the prediction of the learning
loss value by fixed point contraction method
Number of players
SC(with game)
RMSE(with game)
Average SC(without game)
RMSE(without game) for all players
SC(without game)
RMSE(without game) for all players
SC(without game)
RMSE(without game) for all players

3 players1.32302.62e20.64330.03
1.60e30.1
2.32341.85e2
1
3.3446
23.33
10

0
0

Privacy budget

4 players
1.20601.70e20.52500.04
8.26e20.1
2.72331.00e21
4.880318.42
10

5 players
0.564083.6
0.31600.05
4.87e20.1
3.582455.4
1
4.949424.02
10

Table 1: Social Cost (SC) and Learning Loss(RMSE) for
different players with and without gameregression model to demonstrate the value of the methodology and to validate the theoretical results. The dataset contains information regarding nearly 890,000 loans made on apeer-to-peer lending platform, called the Lending Club. The
inputs contain loan attributes, such as total loan size, andborrower information, such as number of credit lines, stateof residence, and age. The outputs are the interest rates ofthe loans per annum. We encode categorical attributes, suchas state of residence and loan grade assigned by the Loan
Club, with integer numbers. We split this dataset into several
non-overlapping datasets for different data owners and test
datasets.
Then, we compared the learning loss between different
data owners in two different scenarios:
1. Collaborative ML training with privacy concerns,
2. Collaborative learning with privacy concerns with gametheory adjusting the magnitude of DP noise.
We use five data owners with 1000, 2783, 7743, 21545,
59949 entities for each of them. This is to make sure there

1

2

3

4

5

6

7

8

9

10

iteration k

Figure 3: Utility and cost of one data owner as a function of
the perturbation .
are relative large and small datasets in our data market. The
learning loss for collaborative learning with no privacy is set
as the baseline, where DP noise magnitude is set to be zero.
First, we demonstrate the performance of the learningparameter prediction, which is shown as learning loss in
Mean Square Error (MSE), versus privacy budget value in
Figure 2. The result is stochastic because the data owners provide differentially-private responses to the gradient queries.
The prediction of the learning loss value is fitted to the reallearning outcome. Then, we test the outcome of the gamereaches equilibrium. In Figure 3, data1, data2 and data3 areplots for payoff function, cost, and utility respectively. Thereexists one minimum value for the payoff function at the endof the game. After the game for multiple data owners withcollaborative learning is performance as desired, we invest
how game helps in choosing the best response of privacy
budget value  for all players as in Table 1.
As shown in Figure 4, the average learning loss with  =10 for all data owners is the lowest. With the increase of
the DP noise magnitude, the average learning loss increases
non-linearly. The Equilibrium result between the learning
loss and privacy budget  is shown in red plots in this figure.
The average learning loss is close to the case when privacy
budget  = 1. There is a significant improvement in privacy,
which is about 47.5%.

Social Welfare
Then we evaluate the social welfare for all players at the endof the game. We pick three cases with 3, 4, and 5 players forvalidation. We define the social cost per player :1X
SC =Ji (i,k=T ).
Ni∈N

As shown in Figure 5, the social cost for collaborative
learning with game is lower in the case when  = 1 with any
number of players. The outcome of the game shows that theFigure 4: Learning loss (RMSE) versus privacy budget  for
3, 4, and 5 data owners in collaborative learning with andwithout gamelearning loss and privacy budget not only reaches a balance atthe equilibrium but also minimises the social cost per player.
The social cost without game is higher than with game for allcases other than for  = 0.1. This is due to the DP noise at = 0.1 is way too large and the learning loss value for all
players are equivalent high. Thus, social welfare is preserved
as desired.

Conclusion
In this paper, we interpreted gradient methods as fixed-point
iterations, and used the concept of Banach contraction to
make a prediction of training loss among a privacy concerned
collaborative machine learning model. Then, we constructeda game based on linear regression. Our analysis of the Nashequilibrium assumed complete information, that is that agentsknow the costs and features of other agents. Our model also
assumed that the private budget chosen by each player isknown by each other player. We established the existence ofa unique Nash Equilibrium for the game, which also gave
good social welfare across data owners.

References
Bordenabe, N. E.; Chatzikokolakis, K.; and Palamidessi, C.
2014. Optimal geo-indistinguishable mechanisms for location privacy. In Proceedings of the 2014 ACM SIGSAC
conference on computer and communications security, 251–
262.
Brenner, H.; and Nissim, K. 2010. Impossibility of differentially private universally optimal mechanisms. In 2010
IEEE 51st Annual Symposium on Foundations of Computer
Science, 71–80. IEEE.
Dwork, C.; and Pappas, G. J. 2017.
Privacy in
information-rich intelligent infrastructure. arXiv preprint
arXiv:1706.01985 .

Figure 5: Social cost (SC) versus privacy budget  for 3, 4,
and 5 data owners in collaborative learning with and without
game

Dwork, C.; Roth, A.; et al. 2014. The algorithmic foundations of differential privacy. Foundations and Trends R in
Theoretical Computer Science 9(3–4): 211–407.
Farokhi, F.; Wu, N.; Smith, D.; and Kaafar, M. A. 2020.
The Cost of Privacy in Asynchronous Differentially-Private
Machine Learning. arXiv preprint arXiv:2003.08500 .
Ghosh, A.; Roughgarden, T.; and Sundararajan, M. 2012.
Universally utility-maximizing privacy mechanisms. SIAM
Journal on Computing 41(6): 1673–1693.
Graepel, T.; Lauter, K.; and Naehrig, M. 2012. ML confidential: Machine learning on encrypted data. In International
Conference on Information Security and Cryptology, 1–21.
Springer.
Gupte, M.; and Sundararajan, M. 2010. Universally optimal
privacy mechanisms for minimax agents. In Proceedingsof the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, 135–146.
Huang, Z.; Hu, R.; Gong, Y.; and Chan-Tin, E. 2018.
DP-ADMM: ADMM-based Distributed Learning withDifferential Privacy.
Preprint: arXiv preprint
arXiv:1808.10101 .
Hunt, T.; Song, C.; Shokri, R.; Shmatikov, V.; and Witchel,E. 2018. Chiron: Privacy-preserving machine learning as aservice. arXiv preprint arXiv:1803.05961 .
Jung, A. 2017. A fixed-point of view on gradient methods
for big data. Frontiers in Applied Mathematics and Statistics
3: 18.
Kalantari, K.; Sankar, L.; and Sarwate, A. D. 2018. Robust Privacy-Utility Tradeoffs under Differential Privacy andHamming Distortion. IEEE Transactions on Information
Forensics and Security 13(11).
Konečnỳ, J.; McMahan, H. B.; Yu, F. X.; Richtárik, P.; Suresh,
A. T.; and Bacon, D. 2016. Federated learning: Strategies

for improving communication efficiency. arXiv preprint
arXiv:1610.05492 .
Li, P.; Li, J.; Huang, Z.; Li, T.; Gao, C.-Z.; Yiu, S.-M.; andChen, K. 2017. Multi-key privacy-preserving deep learningin cloud computing. Future Generation Computer Systems
74: 76–85.
Shi, W.; Cao, J.; Zhang, Q.; Li, Y.; and Xu, L. 2016. Edge
computing: Vision and challenges. IEEE Internet of Things
Journal 3(5): 637–646.
Shokri, R.; and Shmatikov, V. 2015. Privacy-preserving
deep learning. In Proceedings of the 22nd ACM SIGSAC
conference on computer and communications security, 1310–
1321. ACM.
Shor, N. Z. 2012.
Minimization methods for nondifferentiable functions, volume 3 of Springer Series in Computational Mathematics. Berlin, Heidelberg: Springer.
Taghizadeh, A.; Kebriaei, H.; and Niyato, D. 2020. Mean
Field Game for Equilibrium Analysis of Mining Computational Power in Blockchains. IEEE Internet of Things Journal.
Wu, N.; Farokhi, F.; Smith, D.; and Kaafar, M. 2020.
The Value of Collaboration in Convex Machine
Learning with Differential Privacy.
In 2020 IEEE
Symposium on Security and Privacy (SP), 485–498.
Los Alamitos, CA, USA: IEEE Computer Society.
ISSN 2375-1207.
doi:10.1109/SP40000.2020.00025.
URL
https://doi.ieeecomputersociety.org/10.1109/
SP40000.2020.00025.
Xu, L.; Jiang, C.; Chen, Y.; Wang, J.; and Ren, Y.
2016. A framework for categorizing and applying privacypreservation techniques in big data mining. Computer 49(2):54–62.
Xu, L.; Jiang, C.; Wang, J.; Ren, Y.; Yuan, J.; and Guizani, M.
2015. Game theoretic data privacy preservation: Equilibrium
and pricing. In 2015 IEEE International Conference on
Communications (ICC), 7071–7076.
Zhan, Y.; Li, P.; Qu, Z.; Zeng, D.; and Guo, S. 2020. A
learning-based incentive mechanism for federated learning.
IEEE Internet of Things Journal .
Zhang, T.; He, Z.; and Lee, R. B. 2018. Privacy-preserving
machine learning through data obfuscation. arXiv preprint
arXiv:1807.01860 .
Zhang, T.; and Zhu, Q. 2017. Dynamic differential privacy
for ADMM-based distributed classification learning. IEEE
Transactions on Information Forensics and Security 12(1):
172–187.

Proof of Lemma 1
We have ∇f (θ) = 0 if and only if the vector θ ∈ Rn is a
fixed point of the operator T ρ . Thus, ∇f (θ) = 0 if and only
if T ρ (θ) = θ, θi = (Yi0 − 21 Qi Xi−1 )Xi0−1 .
Proof. Let θ be a fixed point of T ρ , i.e.,ρ

T (θ) = θ.

Then,
T ρ (θ) − θ = 0,
"
#
ρ
0
0
2(θi Xi − Yi )Xi + Qi = 0,n`
(Yi0 − θi Xi0 )Xi =

1
Qi ,
2

1
Qi Xi−1 ,21
θi Xi0 = Yi0 − Qi Xi−1 ,210θi = (Yi − Qi Xi−1 )Xi0−1 .
2
Yi0 − θi Xi0 =As Qi is different in each iteration k, such fixed point isthen dynamic regarding to the received responses from allother data owners. In stead, the expectation of the fixed pointis calculated with regard to the aggregation of all datasets
D` = (Di , i ∈ N ), X` = (Xi , i ∈ N ),Y` = (Yi , i ∈ N ),and a expectation value of DP noise E(` ) from each data
owner.
Proof.
T ρ (θ) − θ = 0,"#ρ2(θX`0 − Y`0 )Xi + (n` − 1)E(` ) = 0,
n`

(22)

n` − 1
E(` ),
2n` − 1
E(` )X`−1 ,Y`0 − θX`0 =2n` − 1
θX`0 = Y`0 −E(` )X`−1 ,2n` − 1
E(` )X`−1 )X`0−1 .
θ = (Y`0 −2(Y`0 − θX`0 )Xi =Proof of Lemma 2
Assume that for some q ∈ [0, 1), we havekT ρ a − T ρ bk ≤ qka − bk,
n

(23)

ρ

for any a, b ∈ R . Then, the operator T has a unique fixed
point θ0 and the iterates θ(k) satisfykθ(k) − θ0 k ≤ q k kθ(0) − θ0 k.

(24)

Proof. Conversely, we assume there are two different fixed
points, such thata = T ρ (a), b = T ρ (b).
kT ρ (a) − T ρ (b)k = ka − bkThen, by (23),

(20)

(21)

ka − bk ≤ qka − bkSo, q ≥ 1 or ka − bk = 0.
However, since q ∈ [0, 1), we must have a = b. Thus,
there is only one fixed point exists.

Proof of Proposition 1
Proof.
∇J() = ∇(c) + ∇f ()ρ
T (a) − T (b) = (a − b) −(ni ∇f (a) + Qa ) (25)n`
− (ni ∇f (b) + Qb )ρρ= (a − b) −−ρni(∇f (a) − ∇f (b))
n`∂E(` )
∂
m X 2
.
=− 2
n
3i

∇J( = 0) ∝

(31)

i∈N

∂ 2 E(` )
∂2
m X 6
= 2
.
n
4i

∇2 J( = 0) ∝ρ(Qa − Qb )
n`

(30)

(32)

i∈N

Because ∇f (.) is a continuous and differentiable function.
So there exist a point m = ca + (1 − c)b, c ∈ [0, 1] such thatρni[(a − b)∇2 f (m) (26)n`ρ
+ 2E(` )] − (Qa − Qb )
n`
ρni 2
ρni
= (a − b)(I −∇ f (m)) − 2E(` )n`n`ρ− (Qa − Qb )n`

T ρ (a) − T ρ (b) = (a − b) −Assume Qa = Qb , soT ρ (a) − T ρ (b) = (a − b)(I −
−2

ρni 2
∇ f (m))
n`

(27)

ρni
E(` )n`ρni 2∇ f (m))k ≤ qka − bkn`ρni 2q ≥ kI −∇ f (m)kn`k(a − b)(I −(28)

Proof.
 
1P
E(` ) =E

X`∈N n``∈N n`= P`∈N n``∈N

8Ξ2 T 2 X 1
=
.
n2
2`
`∈N

(29)
2

n2` E{kw` [k]k22 }

`∈N

2 X

1

n` w` [k]

`∈N

2 X


1
= P

2

8Ξ2 T 2
2`

2

∇J( = 0) < 0 and ∇ J( = 0) > 0
So this cost function ∇J() is strictly convex with respect
to action . This concludes the proof.