# Incentive Allocation in Vertical Federated Learning Based on Bankruptcy
Problem

Afsana Khan  Marijn ten Thij  Frank Thuijsman  Anna Wilbik  Department of
Advanced Computing Sciences
Maastricht University
Maastricht, The Netherlands

###### Abstract

Vertical federated learning (VFL) is a promising approach for collaboratively
training machine learning models using private data partitioned vertically
across different parties. Ideally in a VFL setting, the active party (party
possessing features of samples with labels) benefits by improving its machine
learning model through collaboration with some passive parties (parties
possessing additional features of the same samples without labels) in a
privacy preserving manner. However, motivating passive parties to participate
in VFL can be challenging. In this paper, we focus on the problem of
allocating incentives to the passive parties by the active party based on
their contributions to the VFL process. We formulate this problem as a variant
of the Nucleolus game theory concept, known as the Bankruptcy Problem, and
solve it using the Talmud’s division rule. We evaluate our proposed method on
synthetic and real-world datasets and show that it ensures fairness and
stability in incentive allocation among passive parties who contribute their
data to the federated model. Additionally, we compare our method to the
existing solution of calculating Shapley values and show that our approach
provides a more efficient solution with fewer computations.

##  1 Introduction

Organizations in recent times want to collaborate using data because data has
become an increasingly valuable asset for businesses. By collaborating and
sharing data, organizations can gain new insights, make better decisions, and
identify new opportunities. Collaboration enables organizations to combine
data from different sources and systems, and to analyze it in new and
innovative ways. Hence, they often opt for aggregating all their data to a
central server as a way to facilitate collaboration and gain the benefits of
centralized data management. However, traditional centralized machine learning
approaches can be problematic due to privacy concerns, scalability issues, and
single point of failure risks. To address these issues, distributed machine
learning approaches [17] have been developed, which involve training models on
decentralized data sources and aggregating the results. This approach allows
for better privacy, scalability, and fault tolerance, while still achieving
similar or better performance compared to centralized methods. Federated
learning (FL) [3], a form of distributed learning, solves the problem of
centralized learning in organizations by addressing the concern of privacy.
One of the main advantages of federated learning is that it allows
organizations to train machine learning models on decentralized data without
requiring data to be centralized or shared. This protects user privacy and
data confidentiality by keeping data on user devices, rather than sending it
to a central server for processing. In addition, federated learning can
improve model performance by training models on more diverse data, which is
particularly useful in organizations where data may be distributed across
different locations or business units. Federated learning can be classified
into three main types based on how the data is partitioned: horizontal
federated learning (HFL), vertical federated learning (VFL), and hybrid
federated learning. The choice among the types of FL depends on the nature of
the data and the specific requirements of the application.

  * •

Horizontal FL:  The data is partitioned based on samples, where each
participating party holds a subset of the samples. The objective is to train a
global model that can perform well on all samples. A practical example of
horizontal federated learning can be in healthcare where multiple hospitals
keep their patient data locally and collaboratively train a machine learning
model to predict medical conditions. They share only aggregated statistics or
model updates with a central server, ensuring privacy preservation while
leveraging diverse patient data. The trained model can provide valuable
insights for patient diagnosis and treatment across multiple institutions.

  * •

Vertical FL:  The data is partitioned based on features, where different
parties hold different sets of features for the same samples. The objective is
to train a model that can perform well on a joint set of features from all
participating devices. For instance, a tax office has information on
fraudulent tax returns filed by individuals, but they lack information on
financial transactions that could help them identify potential fraudulent
activity. To improve their fraud detection predictions, the tax office decides
to collaborate with several banks to access transaction data that could help
them better identify potential fraudulent activity.

  * •

Hybrid FL:  Hybrid FL is a combination of horizontal and vertical federated
learning, where both sample and feature partitioning are used. This approach
is used when the data is complex and both types of partitioning are required
to train an accurate model. An good example of hybrid FL could be a car rental
company willing to better predict the demand for their cars at airports
collaborates with airline companies to access the number of passengers on
flights to those airports. This would require combining data of multiple
airlines (horizontal partition) and the car rental company (vertical
partition).

Motivating data owners to participate in federated learning is crucial for its
success. Incentives help encourage data owners to contribute their data, which
is essential for improving model performance through diverse and
representative data sources. Shi et al. [16] proposed a framework in an HFL
setting based on the Gale-Shapley value to allocate proper incentives to
participants in the federation based on their contributions. After measuring
contributions, a reputation-driven reward allocation policy was used to
distribute the incentive budget among participants. Zhang et al. [23] proposed
a reward system for horizontal federated learning where clients can bid their
prices, and a selector chooses clients to participate in FL rounds based on
contribution quality. Reputation and payment depend on the quality of
contributions, evaluated by a ranking of cosine similarity between client
gradients and the final FL model. However, incentive mechanisms in HFL and VFL
vary due to differences in the roles of the data owners and goals of the
models. Unlike an HFL setting, there are two types of data owners or parties
involved in the federation in VFL.

  * •

Passive/Host Party: Parties that own the data (features) but not the labels or
ground truth that is used to train a machine learning model

  * •

Active/Guest Party: Parties that possess data with labels or ground truth and
wish to train a machine learning model using the data held by the host parties

Hence, it is clear that the active party in a VFL is the one who is going to
benefit from additional data from the passive parties. Therefore, it is
essential for the passive parties to have the motivation to contribute to the
learning process with their data. This can be achieved if there is a fair
reward allocation mechanism to distribute the profit gained from the
federation among the passive parties based on their contribution to the model.
In this paper, we propose a method of profit distribution among participants
of VFL process based on bankruptcy problem [1]. The idea behind the bankruptcy
problem is to allocate the bankrupt’s estate in a fair and efficient way,
taking into account the private claims of the creditors. The problem arises
because the estate may not be sufficient to satisfy all the claims of the
creditors, and thus a mechanism needs to be designed that fairly allocates the
estate among the creditors based on their claims. In context of VFL, the host
parties collaborate with the active party such that the active party is able
to maximize the performance of the federated model. The profit from the
maximization is then distributed among the passive parties depending on how
much they have contributed to the final model.

The rest of the paper is organized as follows: In Section 2, related works on
incentive mechanisms in federated learning settings have been presented.
Section 3 introduces the Bankruptcy problem in general while Section 4
describes our proposed method. The experimental setup is then provided in
Section 5 followed by the results in Section 6. Section 7 discusses some
issues in VFL that could be solved using the proposed method. Finally,
conclusions and future work are discussed in section 8.

##  2 Related Work

This section provides an overview of the existing incentive mechanisms in
federated learning. It highlights the different approaches that have been
taken to incentivize the participating parties to contribute their data to the
federated learning process. These approaches include concepts based on game
theory, contract theory and auction theory.

###  2.1 Game Theory

Some game theory concepts have been experimented with when it came to
designing incentive mechanisms in federated learning environments. These
approaches had two directions; contribution of participants and payment
allocations. Shapley value [13] is the most commonly used technique for
evaluating the contribution of the parties in the federation. On the other
hand, the Stackelberg [20] game is based on data pricing and more focused on
allocating monetary rewards to the parties from the profit obtained through
the federation.

####  2.1.1 Shapley Value

The Shapley value is a concept in cooperative game theory that measures the
contribution of each player to the overall value created by a group of
players. It is based on the idea that the value generated by a group is
distributed fairly among its members according to their respective
contributions. It takes into account all possible ways in which players can
join a coalition and calculates their average marginal contributions to the
coalition. In the context of FL, the Shapley value can be used to measure the
marginal contribution of each party to the model performance by evaluating the
change in model accuracy when a particular party’s data is included or
excluded from the training process. From the computed Shapley value of each
party, it is possible to incentivize participation by rewarding parties that
contribute the most to the federated model performance.

Liu et al. [12] proposed a Guided Truncation Gradient Shapley (GTG-Shapley)
approach for fairly evaluating participants’ contributions to the performance
of federated learning models, without exposing their private data. The
approach reconstructs FL models from gradient updates for Shapley value
calculation and uses a guided Monte Carlo sampling approach combined with
truncation to reduce computational costs. Another incentive mechanism has been
proposed in [19] for federated learning based on the enhanced Shapley value
method. The method measures income distribution by taking multiple influence
factors into account as weights, using the analytic hierarchy process (AHP)
[14] to find the corresponding weight value of each factor. Although most
incentive mechanims are focused in HFL settings, there are some approaches
proposed for VFL settings as well. Fan et al. [6] proposed a contribution
valuation metric called _VerFedSV_ based on Shapley value for vertical
federated learning. The VerFedSV metric satisfies desirable properties for
fairness and can be adapted to both synchronous and asynchronous vertical
federated learning algorithms. Similarly, Wang et al. [18] used Shapley value
in VFL to calculate the grouped feature importance of parties through
approximation, and used it as a measure of importance to decide the
contribution of each party.

####  2.1.2 Stackelberg Game

Stackelberg game is a non-cooperative game concept in game theory where one
player, called the leader, is allowed to make a move before the other player,
called the follower, makes their move. The follower observes the leader’s move
before making their own, and the leader takes into account the follower’s
response when making their initial move. Since Stackelberg game is used to
formulate the interactions between different players in the sell or
procurement of common products, this makes it more appropriate for the
incentive design in FL settings [15].
Zhan et al. [22] formulated the incentive mechanism for federated learning as
a two-stage Stackelberg game where the parameter server announces a total
reward, and each user determines its training strategy to maximize its own
utility. The parameter server is the leader and the data parties are the
followers in this game. In the context of VFL, the host parties can be modeled
as followers, and the guest party as the leader. The guest party sets a price
for each host party based on the value of its data and the importance of its
contribution to the global model. Each host then decides whether to
participate in the VFL process based on this price. If the price is too low,
the host may choose not to participate, while if the price is too high, the
organization may choose to keep its data and not share it [24].

###  2.2 Auction Theory

Auction theory is a branch of economics that studies how auctions work and how
bidders behave in different auction formats. It examines the optimal auction
design and rules to maximize the seller’s revenue or social welfare, and
analyzes the effects of auctions on efficiency, allocation, and distribution
of resources [8]. This concept can be applied to federated learning by
designing a mechanism for selecting the best models contributed by clients.
The mechanism can determine the rewards paid to clients for their
contributions and ensure that the contributions are of high quality.

A federated learning incentive mechanism has been proposed in [23] which the
reputation and reverse auction theory has been applied. In this approach, the
participants place bids for tasks, and reputation that acts as an indirect
measure of their data quality and reliability. Furthermore, combining their
reputation and bids under a limited budget, the participants are rewarded.
Zheng et al. [21] proposed a lightweight and incentive compatible mechanism
_FMore_ for federated learning in the application of mobile edge computing
(MEC) by extending the concept of multi-dimensional procurement auction [4].
This incentive mechanism encourages low-cost, high-quality edge nodes to
participate in the federated learning process. Moreover, Huong et al. [9] also
proposed an auction game model in context of MEC for the federated learning
service between the base station and mobile users, where the base station is
the buyer and mobile users are sellers. The base station initiates and
announces the FL task, and the mobile users decide the resources required for
model training. Each mobile user submits a bid that includes the resources,
local accuracy, and energy cost, and the base station acts as the auctioneer
to select the winners and determine the payment.

###  2.3 Contract Theory

Contract theory is a branch of economics that studies how contracts and
incentives can be used to overcome problems of asymmetric information and
achieve efficient outcomes. It focuses on the design of contracts that can
align the interests of different parties and mitigate risks [2]. In federated
learning, contract theory can be used to design incentive mechanisms that
encourage participants to contribute high-quality data and models to the
shared learning process, while also ensuring fairness and privacy protection.
This can involve the design of contracts that reward participants for their
contributions.
Liu et al. [11] proposed a contract-based aggregator for FL under a multi-
dimensional contract model that considers two possible types of agents. The
contract-based aggregator incentivizes agents to contribute high-quality data
and computational resources by offering them contracts that are individually
rational (IR) and incentive compatible (IC). In [5], data size and
communication time of the participants have been considered as decision
variables in the contract design for the federated learning process. For this
approach, selected participants must satisfy the requirement of communication
time and then the incentive design is simplified into a single-dimensional
contract problem. Li et al. [10] considered the FL scenario in healthcare
crowd sensing transformed the incentive design problem into an utility
maximization problem and established an incentive mechanism based on the
contract theory. Furthermore, Kang et al. [7] introduced an effective
incentive mechanism combining reputation with contract theory to motivate
high-reputation participants with high-quality data to participate in model
learning.

However, most of the existing approaches for incentive allocation in federated
learning deal with horizontally partitioned data, where the data is
partitioned based on the samples. In contrast, vertically partitioned data is
partitioned based on the features or attributes. To the best of our knowledge,
there is no existing work that has specifically addressed the incentive
allocation problem in vertically partitioned federated learning using game
theoretic approaches apart from the Shapley value. This motivated us to
propose a novel solution based on the bankruptcy problem with Talmud division
where the characteristic function is the model performance gain. The
experiments and results in this paper has demonstrated the efficiency of the
solution.

##  3 Preliminaries on Bankruptcy Problem

Bankruptcy problem involves dividing a set of available resources among a
group of creditors with specific claims. This sort of problem has been studied
in a game theoretic view considering it as a co-operative game where an Estate
$E$ is to be divided among $N$ players having claims from the estate. A
bankruptcy problem can be defined as an ordered pair

$(E;d)\in\mathbb{R}\times\mathbb{R}^{n}$ (1)

where $0\leq d_{1}\leq d_{2}....\leq d_{n}$ and $0\leq E\leq
d_{1}+d_{2}+...+d_{n}$

A division rule $f$ in a bankruptcy problem $(E;d)$ determines a solution or
payout $f(E;d)=(f_{1}(E;d),f_{2}(E,;d)....,f_{n}(E;d))$ to every creditor such
that

  * •

$f_{i}(E;d_{i})\geq 0$ for each $i\in N$

  * •

$\sum_{i=1}^{n}f_{i}(E;d)=E$

Several division rules have been proposed to address this problem, each with
its own principles and criteria for fairness. Some of the common division
rules include:

  * •

Proportional Rule: Under the proportional rule, each creditor receives a share
of the estate that is directly proportional to their claim.

  * •

Constrained Equal Awards Rule: The constrained equal awards (CEA) rule
provides an equal distribution of an estate among creditors, while ensuring
that no creditor receives more than what they have claimed.

  * •

Constrained Equal Losses: The constrained equal losses (CEL) rule divides
equally the difference between the aggregate claim and the estate, ensuring
that no creditor ends up with a negative transfer.

  * •

Talmud/Contest Garment Rule: According to this rule, if the estate is less
than half the claim of the creditor with lowest claim, the CEA rule is applied
on half of each of the creditor’s claims. Otherwise, each creditors receives
half of their claims, and the CEL rule is implemented. Algorithm 1 explains
how the Talmud division rule is applied in the bankruptcy problem.

Algorithm 1 Talmud division algorithm for bankruptcy problem

Order creditors from lowest to highest claim

Divide estate equally among all creditors until the lowest creditor receives
half of their claim

while Estate not empty and not all creditors have half their claim do

Remove lowest creditor

Divide estate equally among remaining creditors until the new lowest creditor
receives half of their claim

end while

Order creditors from highest to lowest claim

while Estate not empty do

Allocate to highest creditor(s) until their loss equals the loss of the next
highest creditor

end while

A bankruptcy problem is not itself a coalitional game as coalitions are not
observed here explicitly during the formulation. However, Aumann and Michael
in [1] designed the bankruptcy problem $(E;d)$ into a bankruptcy game and
later proved theoretically that the, solution of a bankruptcy problem using
Talmud’s division rule is the nucleolus of its corresponding bankruptcy game.
Therefore, it can be derived that, by directly solving the bankruptcy problem
using Talmud’s division rule, it is possible to determine the specific
allocation of estate among the creditors without explicitly constructing the
entire bankruptcy game. This simplifies the analysis and allows for a more
direct and focused approach to the estate allocation aspect of the bankruptcy
scenario.

##  4 Proposed Method

In a VFL setting, the active party has access to the labels while the passive
parties have access to additional features of the same samples. During the
federation process, the passive parties provide valuable data to the active
party which benefits it by improving its machine learning model, but the
passive parties are not getting access to the final model or any of the
benefits that come with it. Hence, the guest party needs to persuade the
passive parties to contribute to the federated model based on incentives. In
our proposed method we have designed this scenario as a bankruptcy problem to
address the issue of incentive allocation among the participants. In this
formulation, the passive parties in the vertical federated learning process
are considered as creditors with specific claims on the profit obtained from
the federation. The estate is defined as the difference in model performance
between the federated model and the local model of the active party. The local
model refers to the machine learning model that the active party would have
built using only its own data, without collaborating with any other party. The
federated model, on the other hand, is the machine learning model that is
built collaboratively by all the parties involved in the VFL setup. To
calculate the claim of a passive party, we can compare the performance of the
federated model when the guest party collaborates only with that particular
passive party to the local model of the active party. More specifically, the
claim of a passive party can be defined as the improvement in model
performance achieved by adding that only that particular party’s features to
the federated model.

Let’s assume that there are $N$ parties involved in a vertical federated
learning setup. The federated learning algorithm aims to train a machine
learning model $M_{f}$ that minimizes a certain objective function $F(M_{f})$
over all parties’ datasets, subject to certain constraints.
Now, let’s define the local model of the active party (say, party i) as
$M_{i}$, which is trained only on its own dataset $D_{i}$, without any
collaboration with other parties. We measure the performance of $M_{i}$ using
a certain evaluation metric, say $V$. Similarly, we can measure the
performance of the federated model $M_{f}$ using the same evaluation metric.
The estate, denoted by $E$, is defined as the difference in performance
between the federated model $M_{f}$ and the local model $M_{i}$, i.e.,

$E=V(M_{f})-V(M_{i})$ (2)

Now, let’s consider a passive party (say, party $j$) that wants to claim
credit for contributing to the federated model $M_{f}$. To calculate the claim
of party $j$, we can compare the performance of $M_{f}$ when party $j$
collaborates alone with party $i$ (the active party). More specifically, let’s
denote the model when party $j$ collaborates alone with party $i$ by $M_{ij}$.
We can measure the performance of $M_{ij}$ using the evaluation metric $V$.
The claim of party $j$, denoted by $C_{j}$, is then defined as the improvement
in performance achieved by adding party $j$’s features to the local model of
$i$, i.e.,

$C_{j}=V(M_{ij})-V(M_{i})$ (3)

Here, $M_{ij}$ is trained on both party $i$’s and party $j$’s data, while
$M_{i}$ is trained only on party $i$’s data. Therefore, the improvement in
performance achieved by adding party $j$’s features to $i$-th local model
represents the additional information that the passive party party $j$ has
contributed to the final model, beyond what the active party $i$ could have
achieved by training a local model only on its own data. Once the claims from
the passive parties and estate of the VFL are obtained, the proposed method
involves determining the Talmud bankruptcy problem solution and getting a
payout vector represented as

$\displaystyle P=[p_{1},p_{2},...,p_{N}]$ (4)
$\displaystyle\text{where}\sum_{i=1}^{N}p_{i}=E$

##  5 Experimental Setup

This section outlines the experimental setup used to evaluate the proposed
method. The classification problem was selected for simplicity and was used in
the evaluation.

###  5.1 Datasets

The proposed method was tested on a synthetic dataset as well as on two real
world datasets from the UCI repository (Table 1)

Dataset | Instances | Features
---|---|---
Synthetic Dataset | 10000 | 20
Heart Disease Dataset | 303 | 13
Bank Marketing Dataset | 11162 | 15
Table 1: Overview of Datasets

  * •

Synthetic Dataset:  Generated using _make_classification_ function provided by
the scikit-learn library for binary classification and also added Gaussian
noise to bring variation.

  * •

Heart Disease Dataset: Contains medical features to predict the presence of
heart disease.

  * •

Bank Marketing Dataset: Contains data on direct marketing campaigns of a
Portuguese banking institution to predict whether a client will subscribe to a
term deposit or not.

The datasets were pre-processed to address issues such as missing values and
duplicates. Additionally, categorical features in the datasets were encoded
using One-Hot-Encoding. To simulate a vertically federated environment, the
datasets were vertically divided into four partitions, with each partition
representing local data of a party. Among them one of the parties was
considered the active party with labels and the rest were passive parties.

Dataset | Selected Features
---|---
Synthetic | Heart Disease | Bank Marketing
$P_{a}$ (active) | target (label), features 1 through 3 | output (label), age, sex | deposit (label), poutcome
$P_{h1}$ (passive) | features 4 through 7 | chol, fbs, restecg, caa | balance, housing, loan, contact, day
$P_{h2}$ (passive) | features 8 through 14 | oldpeak, exng, slp, cp | month, campaign, pdays, previous
$P_{h3}$ (passive) | features 15 through 20 | thall, thalachh, trtbps | age, job, marial, education, default
Table 2: Distribution of features across the involved parties for each
experiment.

###  5.2 Model

The experimental setup consistes of an active party $P_{a}$ and three passive
parties $P_{h1},P_{h2},P_{h3}$. Each party holds some of the features required
for the machine learning model. We used a vertical federated logistic
regression model to train the model using the Algorithm 2 [25]. The datasets
were randomly divided into training and test sets, with 70% of the data used
for training and 30% for testing.

Algorithm 2 Vertical Federated Logistic Regression

1:$M$ $\rightarrow$ Number of Parties

2:$T$ $\rightarrow$ Number of Communication Rounds

3:$B$ $\rightarrow$ Number of Batches

4:Training Data $X=\\{X^{1},X^{2},..,X^{M}\\}$

5:Party $1$ $\rightarrow$ Active Party

6:Party $(2..M)$ $\rightarrow$ Passive Party

7:Initialize local model ${\theta_{0}}^{m},m$ $\epsilon$ $(1..M)$

8:for $each$ $communication$ $round$ $t=1,2,\ldots,T$ do

9: for $each$ $batch$ $data$ ${X_{b}}^{m}$ $\epsilon$
$({X_{1}}^{m},{X_{2}}^{m},..,{X_{B}}^{m})$ do

10: for $each$ $Party$ $m=1,2,..M$ do

11: Compute ${z_{b}}^{m}$ = ${X_{b}^{m}}$${\theta_{t}}^{m}$

12: if $m\neq 1$ then

13: send ${z_{b}}^{m}$ to Party $1$

14: end if

15: end for

16: Compute $\hat{y}_{b}$ = $\sum_{m=1}^{M}{z_{b}}^{m}$ and
$L(y_{b},\hat{y}_{b})$ on Party $1$

17: Compute $\frac{\partial L}{\partial z_{b}}$ on Party 1

18: Send $\frac{\partial L}{\partial{z_{b}^{m}}}$ to Party $m,m\epsilon(2,k)$

19: for $each$ $Party$ $m=1,2,..M$ do

20: ${{\theta}_{t}}^{m}\leftarrow{\theta_{t}}^{m}-\eta\frac{\partial
L}{\partial{z_{b}^{m}}}\frac{\partial{z_{b}^{m}}}{\partial{\theta}_{t}^{m}}$

21: end for

22: end for

23:end for

To evaluate the model’s performance, we used the F1-score as an evaluation
metric. We calculated the F1-score for the local model of $P_{a}$ when it uses
only its local data, $M(P_{a})$ and as well as also computed F1-scores for
models trained with each combination of passive parties with the active party:
$M(P_{a},P_{h1}),M(P_{a},P_{h2}),M(P_{a},P_{h3})$ and
$M(P_{a},P_{h1},P_{h2},P_{h3})$‘. Here, $M(P_{a},P_{h1},P_{h2},P_{h3}))$
denotes the federated model.

###  5.3 Estate and Claims for Bankruptcy Problem

The estate $E$, is considered to be the improvement in the federated model
performance when using the combined data of all parties compared to using the
data of $P_{a}$ alone. The estate is calculated as the difference between the
F1-score of the federated model and the F1-score of the local model of
$P_{a}$:

$\displaystyle E=F1(M(P_{a},P_{h1},P_{h2},P_{h3}))-F1(M(P_{a}))$ (5)

In addition, we calculated the claims for each passive party $P_{hi}$ where
$i\in{1,2..n}$, which measure their contribution to the overall model
performance. The claims are computed as the difference between the F1-score of
the federated model and the F1-score of the model trained with $P_{a}$ and
$P_{hi}$:

$Claim(P_{hi})=F1(M(P_{a},P_{hi}))-F1(M(P_{a}))$ (6)

Description | Estate | Host Party Claim | Host Party Payout | Host Party Shapley Value
---|---|---|---|---
$P_{h1}$ | $P_{h2}$ | $P_{h3}$ | $P_{h1}$ | $P_{h2}$ | $P_{h3}$ | $P_{h1}$ | $P_{h2}$ | $P_{h3}$
Heart Disease Dataset | $39.33$ | $33.98$ | $35.27$ | $28.43$ | $13.11$ | $13.11$ | $13.11$ | $6.77$ | $8.35$ | $6.34$
Bank Marketing Dataset | $28.03$ | $27.85$ | $20.17$ | $15.84$ | $10.055$ | $10.055$ | $7.92$ | $3.84$ | $1.60$ | $0.9$
Synthetic Dataset | $67.93$ | $3.04$ | $45.45$ | $35.89$ | $1.52$ | $37.99$ | $28.43$ | $5.36$ | $38.88$ | $24.65$
Dummy Player Property | $18.54$ | $0$ | $15.5$ | $12.77$ | $0$ | $7.91$ | $10.19$ | $-0.202$ | $15.39$ | $10.19$
Symmetry Property | $20.68$ | $15.5$ | $15.5$ | $12.77$ | $7.15$ | $7.15$ | $6.38$ | $4.768$ | $4.768$ | $6.769$
Table 3: Outcomes for the experiments performed in this study. Both property
experiments were performed using the Heart Disease Dataset. For the Dummy
Player Property, Host Party $P_{h1}$ was selected as the dummy player. For the
Symmetry property, Host Party $P_{h1}$ was defined to be the duplicate of
$P_{h2}$.

##  6 Results

This section presents the results of our proposed method for incentive
allocation in VFL setting based on the bankruptcy problem where Talmud’s
division rule has been applied. Additionally, we compared the solution which
is the nucleolus of the bankruptcy problem with the corresponding Shapley
values of the passive parties. The following subsections provide a detailed
analysis of the results.

###  6.1 Heart Disease Dataset

In Table 3, the $Estate$ column shows the estate value, which measures the
improvement in the model’s performance when using the combined data of all
parties compared to using the data of $P_{a}$ alone. In this case, the estate
value is 39.33, indicating a significant improvement in the model’s
performance when using the combined data of all parties. Here, $P_{h2}$ has
the highest claim value of 35.27, followed by $P_{h1}$ with a claim value of
33.98, and $P_{h3}$ with a claim value of 28.43.

The $Payout$ column shows the payout allocated from the estate for each
passive party, which is proportional to their claims. In this case, all
parties receive the same payout of 13.11, which is lower than their claim
values. This is because the total surplus value of the federated model is not
enough to fully compensate all parties according to their claims. When the
estate is relatively small compared to the sum of claims, it is divided
equally and all parties receive the same payout. We think this makes sense, as
it compensates the effort made for the federation, disregarding the individual
contribution.

###  6.2 Bank Marketing Dataset

In Table 3, for the bank marketing dataset, the estate was divided equally
among $P_{h1}$, $P_{h2}$, and $P_{h3}$ until $P_{h3}$ received half of their
claim value. Once $P_{h3}$ received half of its claims it was discarded
temporarily and $P_{h2}$ became the next lowest creditor (according to
Algorithm 1). The remaining estate was then again divided equally among
$P_{h2}$ and $P_{h1}$ until $P_{h2}$ received half of their claim value. At
this point, the estate was exhausted, and the remaining surplus value was not
enough to fully compensate $P_{h1}$ according to its claims. Therefore,
$P_{h1}$ received a payout that was the same as to $P_{h2}$.

###  6.3 Synthetic Dataset

For the synthetic dataset, the estate was initially divided equally among the
parties ($P_{h1}$, $P_{h2}$, and $P_{h3}$) until they received half of their
claim value. After each party received half of their claim value, the
remaining surplus value was allocated to the highest creditor, which was
$P_{h2}$ with a claim value of $45.45$. The surplus value was then allocated
to $P_{h2}$ until their loss ($7.46$) equaled the loss of the next highest
creditor, which was $P_{h3}$ with a claim value of $35.89$ and a payout of
$28.43$.

###  6.4 Interpreting Payouts in Practical Setting

In our proposed approach, the payouts obtained by each party can be compared
with the estate to find out what portion of the estate it received. This
percentage can be used to divide the incentive in a practical setting where
there is a budget for the federation. For example, if we consider the
experimental results for the bank marketing dataset, the percentages of the
payouts for $P_{h1},P_{h2}$ and, $P_{h3}$ would be $(10.055/28.03)*100\approx
36\%$, $(10.055/28.03)*100\approx 36\%$ & $(7.92/28.03)*100\approx 28\%$
respectively. Hence, if the total budget of the active party for this
federation is lets say, $10,000, each of the parties will receive a
compensation from this budget equal to their payout percentages.
Hence, this method can ensure that the participating parties are incentivized
to contribute high-quality and unique data, while also ensuring that the
incentive budget is allocated fairly among the parties.

###  6.5 Comparison with Shapley Value

The Shapley value represents the average marginal contribution of each passive
party to the overall model performance. It is important to note that the
Shapley value and the payout (or nucleolus) may differ due to the specific
formulation of the bankruptcy problem in the VFL setting. However, it has been
observed across all the datasets (Table 3) that, parties with higher claims
have higher Shapley values, indicating their higher contribution to the
overall model performance. While the Shapley value provides insights into the
relative importance of each party’s contribution to the model, it is not
sufficient to determine the exact amount of incentive that needs to be
allocated to each party.

Talmud’s bankruptcy solution is computationally more efficient than Shapley
values because it requires fewer computations as the number of passive parties
increases. Specifically, Talmud’s bankruptcy solution requires $O(n)$
computations, where $n$ is the number of passive parties, for computing the
claims of each passive party and allocating the surplus value to each party
based on their claims. On the other hand, computing Shapley values requires
evaluating the performance of the model for all possible combinations of
parties, which involves $O(2^{n})$ computations. This exponential increase in
computational complexity can be a significant challenge, especially for large
values of $n$.

While there are efficient algorithms for approximating Shapley values, they
may not be appropriate for VFL settings due to the inherent privacy
constraints. Approximating Shapley values in VFL requires approximating the
performance of the model for all possible combinations of parties, which can
be challenging due to the need to maintain data privacy and security.

Moreover, approximations are never exact and can introduce errors in the
computation of the Shapley values. These errors can lead to biased incentive
allocation and undermine the fairness and efficiency of the VFL collaboration.
In contrast, Talmud’s bankruptcy solution is a more robust and reliable
approach for incentive allocation, as it is based on a well-established and
proven method that is computationally efficient and fair.

##  7 Discussion

In this section we discuss two common problems in VFL; identifying malicious
data party and redundant data party and then, assess how our proposed approach
and Shapley values have addresses them. The problem of malicious data parties
can occur when a participating party intentionally provides data that is of
poor quality or contains malicious content that can compromise the integrity
of the model. On the other hand, redundant data party problem can occur when
multiple participating parties provide similar or redundant data to the
federated learning process. This can lead to an inefficient use of resources,
as the same data is used multiple times, and can also lead to over-fitting of
the model to the redundant data, reducing its ability to generalize to new
data.

###  7.1 Dummy Property

The malicious data problem in VFL can be has been tried to be solved by the
dummy player property in co-operative game theory. In general, the dummy
player refers to a player who does not contribute to the game’s value, and
whose presence or absence in any coalition does not affect the total value
generated by that coalition.
To simulate a dummy player or a party with malicious data in VFL, one of the
passive parties ($P_{h1}$ in Table 3) has been assigned randomly generated
data which represents its local data. Hence, this party should be the dummy
player and not contribute to the federated model. We calculate the payouts
using our proposed approach as well also the Shapley values for the Heart
disease dataset as an example.
If a passive party does not contribute to any coalition in the FL process,
they should not receive any share of the total profit from the federation. The
Shapley value identifies dummy players by computing the average marginal
contribution of a party to all possible coalitions. Since a dummy player or
the malicious data party $P_{h1}$ contributes nothing to any coalition, their
marginal contribution to every coalition is zero, and hence, the Shapley value
assigns them a value of zero, which is consistent with the concept of dummy
players in cooperative game theory.
Again, according to our proposed approach, if a party’s contribution to the
federated model is negative or zero due to malicious data, their claim will
also be zero or negative. Eventually applying Talmud’s division rule will
ensure that, the party with claim less than or equal to zero is not given any
incentive and only the estate is divided among parties with positive valued
claims.

###  7.2 Symmetry Property

The redundant party problem has been assessed with using the symmetry property
in game theory. According to symmetry property, if two players have identical
contributions to every coalition in the game, they should be treated equally
and receive the same share of the total value of the game.
To simulate a redundant data party in VFL, one of the passive parties (here
$P_{h1}$ has been assigned the same local data as $P_{h2}$. So basically,
$P_{h1}$ is the duplicate of $P_{h2}$. As earlier, The payouts were calculated
using our proposed approach as well also the Shapley values for the Heart
disease dataset.
From Table 3 we observe that the Shapley values as well as payouts are the
same for $P_{h1}$ and $P_{h2}$ since they both have redundant data. However,
it is important to note that parties with the same Shapley values may not
necessarily have the same data, and dropping one of them might not always be
the best decision. In some cases, parties with the same Shapley values may be
contributing equally to the federated model, even if their data is different.
Similarly, in our proposed approach, equal payouts may not necessarily
indicate that the claimants have the same data. The equal payouts simply mean
that the claimants are receiving a fair share of the model performance gains
based on their respective contributions. Therefore, while the symmetry
property is an important property in cooperative game theory, it should be
used in conjunction with party selection before the VFL process to identify
duplicate or similar contributing parties.

##  8 Conclusion

One of the emerging challenges in VFL which is allocating incentives to
passive parties in vertically partitioned federated learning has been
addressed in our paper. The proposed approach, based on the Bankruptcy Problem
using Talmud’s division rule, ensures fairness and stability in incentive
distribution among the passive parties. Through experiments on both synthetic
and real-world datasets, we have demonstrated that our method is comparable to
the existing approach of using Shapley values while also surpasses it in terms
of computational efficiency. This efficiency is particularly valuable when
dealing with large-scale federated learning scenarios involving numerous
parties and features. Overall, our approach presents a practical solution for
motivating passive parties to contribute their private data, thus enhancing
the accuracy and reliability of machine learning models while preserving
privacy. Future research could explore incorporating party selection mechanism
in VFL before the training process begins and then finally allocate incentives
in the end which would make the whole incentive allocation mechanism more
efficient. We will also test this approach on real world use cases in near
future.

## References

  * [1] Robert J Aumann and Michael Maschler, ‘Game theoretic analysis of a bankruptcy problem from the talmud’, Journal of economic theory, 36(2), 195–213, (1985).
  * [2] Patrick Bolton and Mathias Dewatripont, Contract theory, MIT press, 2004.
  * [3] Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloe Kiddon, Jakub Konečnỳ, Stefano Mazzocchi, Brendan McMahan, et al., ‘Towards federated learning at scale: System design’, Proceedings of machine learning and systems, 1, 374–388, (2019).
  * [4] Yeon-Koo Che, ‘Design competition through multidimensional auctions’, The RAND Journal of Economics, 668–680, (1993).
  * [5] Ningning Ding, Zhixuan Fang, and Jianwei Huang, ‘Incentive mechanism design for federated learning with multi-dimensional private information’, in 2020 18th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOPT), pp. 1–8. IEEE, (2020).
  * [6] Zhenan Fan, Huang Fang, Zirui Zhou, Jian Pei, Michael P Friedlander, and Yong Zhang, ‘Fair and efficient contribution valuation for vertical federated learning’, arXiv preprint arXiv:2201.02658, (2022).
  * [7] Jiawen Kang, Zehui Xiong, Dusit Niyato, Shengli Xie, and Junshan Zhang, ‘Incentive mechanism for reliable federated learning: A joint optimization approach to combining reputation and contract theory’, IEEE Internet of Things Journal, 6(6), 10700–10714, (2019).
  * [8] Paul Klemperer, ‘Auction theory: A guide to the literature’, Journal of economic surveys, 13(3), 227–286, (1999).
  * [9] Tra Huong Thi Le, Nguyen H Tran, Yan Kyaw Tun, Minh NH Nguyen, Shashi Raj Pandey, Zhu Han, and Choong Seon Hong, ‘An incentive mechanism for federated learning in wireless cellular networks: An auction approach’, IEEE Transactions on Wireless Communications, 20(8), 4874–4887, (2021).
  * [10] Li Li, Xi Yu, Xuliang Cai, Xin He, and Yanhong Liu, ‘Contract theory based incentive mechanism for federated learning in health crowdsensing’, IEEE Internet of Things Journal, (2022).
  * [11] Yuan Liu, Mengmeng Tian, Yuxin Chen, Zehui Xiong, Cyril Leung, and Chunyan Miao, ‘A contract theory based incentive mechanism for federated learning’, in Federated and Transfer Learning, 117–137, Springer, (2022).
  * [12] Zelei Liu, Yuanyuan Chen, Han Yu, Yang Liu, and Lizhen Cui, ‘Gtg-shapley: Efficient and accurate participant contribution evaluation in federated learning’, ACM Transactions on Intelligent Systems and Technology (TIST), 13(4), 1–21, (2022).
  * [13] Alvin E Roth, ‘Introduction to the shapley value’, The Shapley value, 1–27, (1988).
  * [14] Thomas L Saaty, What is the analytic hierarchy process?, Springer, 1988.
  * [15] Yunus Sarikaya and Ozgur Ercetin, ‘Motivating workers in federated learning: A stackelberg game perspective’, IEEE Networking Letters, 2(1), 23–27, (2019).
  * [16] Zhuan Shi, Lan Zhang, Zhenyu Yao, Lingjuan Lyu, Cen Chen, Li Wang, Junhao Wang, and Xiang-Yang Li, ‘Fedfaim: A model performance-based fair incentive mechanism for federated learning’, IEEE Transactions on Big Data, (2022).
  * [17] Joost Verbraeken, Matthijs Wolting, Jonathan Katzy, Jeroen Kloppenburg, Tim Verbelen, and Jan S Rellermeyer, ‘A survey on distributed machine learning’, Acm computing surveys (csur), 53(2), 1–33, (2020).
  * [18] Guan Wang, Charlie Xiaoqian Dang, and Ziye Zhou, ‘Measure contribution of participants in federated learning’, in 2019 IEEE international conference on big data (Big Data), pp. 2597–2604. IEEE, (2019).
  * [19] Xun Yang, Weijie Tan, Changgen Peng, Shuwen Xiang, and Kun Niu, ‘Federated learning incentive mechanism design via enhanced shapley value method’, Wireless Communications and Mobile Computing, 2022, (2022).
  * [20] Yugang Yu, George Q Huang, and Liang Liang, ‘Stackelberg game-theoretic model for optimizing advertising, pricing and inventory policies in vendor managed inventory (vmi) production supply chains’, Computers & Industrial Engineering, 57(1), 368–382, (2009).
  * [21] Rongfei Zeng, Shixun Zhang, Jiaqi Wang, and Xiaowen Chu, ‘Fmore: An incentive scheme of multi-dimensional auction for federated learning in mec’, in 2020 IEEE 40th international conference on distributed computing systems (ICDCS), pp. 278–288. IEEE, (2020).
  * [22] Yufeng Zhan, Peng Li, Zhihao Qu, Deze Zeng, and Song Guo, ‘A learning-based incentive mechanism for federated learning’, IEEE Internet of Things Journal, 7(7), 6360–6368, (2020).
  * [23] Jingwen Zhang, Yuezhou Wu, and Rong Pan, ‘Incentive mechanism for horizontal federated learning based on reputation and reverse auction’, in Proceedings of the Web Conference 2021, pp. 947–956, (2021).
  * [24] Zhixian Zhang, Xinchao Li, and Shiyou Yang, ‘Data pricing in vertical federated learning’, in 2022 IEEE/CIC International Conference on Communications in China (ICCC), pp. 932–937, (2022).
  * [25] Hangyu Zhu, Jinjin Xu, Shiqing Liu, and Yaochu Jin, ‘Federated learning on non-iid data: A survey’, Neurocomputing, 465, 371–390, (2021).