# Optimally Improving Cooperative Learning in a Social Setting111This paper is
going to appear in ICML 2024

Shahrzad Haddadan
Rutgers Business School
<EMAIL_ADDRESS>
Cheng Xin
Department of Computer Science
Rutgers University
<EMAIL_ADDRESS>
Jie Gao
Department of Computer Science
Rutgers University
<EMAIL_ADDRESS>
###### Abstract

We consider a cooperative learning scenario where a collection of networked
agents with individually owned classifiers dynamically update their
predictions, for the same classification task, through communication or
observations of each other’s predictions. Clearly if highly influential
vertices use erroneous classifiers, there will be a negative effect on the
accuracy of all the agents in the network. We ask the following question: how
can we optimally fix the prediction of a few classifiers so as maximize the
overall accuracy in the entire network. To this end we consider an aggregate
and an egalitarian objective function. We show a polynomial time algorithm for
optimizing the aggregate objective function, and show that optimizing the
egalitarian objective function is NP-hard. Furthermore, we develop
approximation algorithms for the egalitarian improvement. The performance of
all of our algorithms are guaranteed by mathematical analysis and backed by
experiments on synthetic and real data.

##  1 Introduction

With the breakthrough of AI technologies and the availability of big data, we
are witnessing a flourish of AI models that are owned by different entities
and trained by using private or proprietary data, even for generic purposes
such as voice recognition, natural language processing or image segmentation.
These models do not stay in isolation. There is a natural opportunity for
these models to interact with each other and collectively improve their
performance.

One of the concrete application scenarios is in cybersecurity, where security
agents in a network collectively detect anomalous traffic patterns that are
potentially associated with cyber attacks. These security agents may be
affiliated with different entities in the network. They may or may not be able
to directly share their collected data due to privacy or other logistic
reasons but can share their beliefs on whether the network is under attack or
not, and if so, which type of attack. In such a scenario, improving the model
of one agent by collecting more data, recruiting domain experts to provide
high quality labels of observation data, or retraining using a more powerful
model can help to improve the quality of prediction locally. As these security
agents stay on a network, they naturally have the opportunity to exchange
their assessments. The quality improvement at one agent spills to other agents
in the network.

Another application scenario is in online social networks. With generative AI,
it is now a lot easier to create fake contents such as images and videos.
Consider an online social network in which agents share pictures and comment
on them, e.g., Instagram. Assume that some of these pictures may be AI
generated. While everyone can have his or her opinion on whether a wide-
spreading picture is real or fake, the participants who are more skilled in
image generation or who have access to powerful models can help the rest of
the network to discern real ones and fake ones.

It is not new to utilize data and models in a distributed setting. With the
explosion of personal data from smartphones and wearable devices and the
increasing awareness of data privacy, decentralized learning, as opposed to
users sharing their data to a central enterprise, has gained popularity in
recent years. Federated learning and gossip learning are such examples.
However in this scenarios, the decentralized agents are still tightly coupled
– they use the same model architecture and sometimes exchange gradient or
model parameters directly. In our work, we consider a loosely coupled,
cooperative setting where agents share a general task requirement and they
select individual model parameters and architecture, train their models on
their private data. Such agent autonomy is a necessity when the agents are not
affiliated with the same ownership. In addition, we consider the agents
sharing their predictions with other agents preferably those within proximity
or with established trust relationships. We call this model cooperative
learning in a social setting. Essentially each agent has her own view of the
world and through exchanging predictions with others, collectively we hope to
improve the accuracy for all agents.

When only predictions from other agents are shared, it is up to the individual
agent to decide how to update their models. On a first-order basis, we can
assume for now that the outcome of such information sharing can be
approximated by a weighted linear combination of the agent $u$’s own
assessment and the predictions from other neighbors. The weights can be either
fixed or time-varying, e.g., based on the trust level of neighbors. This leads
to two natural models, DeGroot (1974) and Friedkin & Johnsen (1990),
originally proposed in modeling opinion dynamics in social network. In DeGroot
model, each agent’s prediction is a simple weighted linear combination of
neighbors’ predictions. When the weight coefficients are fixed (or when the
updates are frequently enough for time-varying weights), all agents converge
to global consensus. In FJ model, each agent incorporates in the update step a
vector of personal assessment (which can be guided by the difference of local
data distribution). The model still converges, and each agent arrives at
possibly different predictions, reflecting adaptation to individual local data
distributions.

The generic framework captures how a group of networked agents build their
respective models collectively. When new training data is introduced to one
agent in the system, the other agents indirectly receive the benefit of it.
Therefore it is an interesting question to analyze the collective benefit and
also ask the optimization question of _where to inject new training data to
maximize the collective benefit_. This is the research question we focus on in
this paper.

###  1.1 Related Work

##### Decentralized learning

Training a single high-quality global model using decentralized data and
computation has been studied extensively in decentralized optimization (e.g.,
for kernel methods Colin et al. (2016), PCA Fellus et al. (2015), stochastic
gradient descent Blot et al. (2016), multi-armed bandit Lazarsfeld & Alistarh
(2023) and generalized linear models He et al. (2018)). Federated learning
Konečný et al. (2015, 2016a, 2016b); McMahan et al. (2017); Krishnan et al.
(2024) uses a client-server architecture and considers multiple local models,
trained using respective local data, with model parameters aggregated and
shared through a central global model. Gossip learning Ormándi et al. (2013);
He et al. (2018); Hegedűs et al. (2019, 2016); Giaretta & Girdzijauskas
(2019), on the other hand, does not assume a central node. Instead, each node
updates its own local parameters via training and then its updated parameters
are shared by information exchange with other nodes in the network. This
setting removes the single point of failure in the system and thus is more
robust and scalable, without compromised performance Hegedűs et al. (2016,
2021). These gossip learning protocols consider the exchange of local models
(or crucial parameters such as local gradients) directly. This requires that
all agents participating in gossip learning use the same type of models, which
is a limitation. It is also known that models or gradients can reveal
knowledge of the training data (thus raising concerns to data privacy, see a
recent survey here Zhang et al. (2023)).

##### Social learning

The study of learning and decision making in a social network has been studied
for longer than a decade. In these works, agents predict the status of the
world, and based on their prediction they take an action to maximize a utility
function. In a social setting these decisions are not made in a void, as each
agent observes the prediction of her neighbors or their actions, and
henceforth updates her prediction. These models are vastly studied by
economists who are interested in understanding whether the agents’ decisions
converge to the same value (consensus), how fast is the rate of convergence,
whether an equilibrium exists, and if the consensus leads agents to an optimal
decision (learning) Acemoglu et al. (2011); Arieli et al. (2021); Golub &
Jackson (2010); Golub & Sadler (2016); Rahimian & Jadbabaie (2017); Hązła et
al. (2019); Eckles et al. (2019); Bindel et al. (2015).

Given a social network, various works tackle optimization problems in which an
algorithm makes minimal changes in the network to maximize the improvement of
a desirable property. For instance, various works consider the problem of
maximizing information diffusion by seeding information in a number of
selected source vertices Kempe et al. (2003); Seeman & Singer (2013); Eckles
et al. (2019); Garimella et al. (2017) or by adding links Borgs et al. (2014);
D’Angelo et al. (2019). Some works optimally insert links into a network to
maximize the information flow between two groups of nodes Cinus et al. (2023);
Zhu et al. (2021); Adriaens et al. (2023); Haddadan et al. (2021, 2022);
Santos et al. (2021), and others optimaly alter innate opinion of users in the
FJ model to reduce polarization or disagreements Tsioutsiouliklis et al.
(2022); Abebe et al. (2018); Musco et al. (2018).

Our work bridges the above lines of work. We study a framework in which agents
are performing learning tasks and exchange their predictions until each makes
a final decision. Unlike prior decentralized learning works, our agents do not
necessarily use the same model nor they share any parameters, they solely
exchange their predictions. In this sense, our framework falls into the
context of social learning. However, instead of studying problems such as
existence of consensus or convergence rates, we focus on the problem of
optimally injecting information to a selected subset of agents to improve the
overall betterness in the network. Another difference with social learning
framework is that we do not consider one fixed model of information exchange,
in contrast, we assume a general linear model for information exchange.
Therefore, our methods are applicable to any linear model whether it describes
users of a social network, each evaluating the truthfulness of an online
content, or whether it describes intelligent systems in which agents cooperate
for a classification task.

###  1.2 Summary of Contributions

Motivated by prior works on decentralized and social learning, we consider a
new framework called _cooperative learning in a social setting_. In this
framework, we consider the problem of _optimally selecting $k$ agents and
improving their innate predictions to maximize the overall network
improvement_. We consider both an _aggregate_ objective function and an
_egalitarian_ one, and assume different levels of access to the model’s
parameters which are (1) the joint probability distribution of the classifiers
forming agents’ innate predictions, denoted by $\pi$, and (2) the expressed
social influence matrix, denoted by $\bar{W}$.

  1. 1.

We provide a polynomial time algorithm for the aggregate improvement problem.
This algorithm uses only the innate error rates and $\bar{W}$, and it does not
need any additional knowledge of $\pi$; see section 4.1.

  2. 2.

We show that solving the egalitarian improvement problem is hard: it is NP-
hard to solve it exactly even if both parameters are entirely known. We also
show that if $\bar{W}$ and only the innate error rates are available, without
any further assumption even finding an approximation solution is hard; see
theorems A.3 and A.4 .

  3. 3.

We provide two approximation algorithms for the egalitarian improvement
problem. The first algorithm, $\mathsf{EgalAlg}$ is a greedy algorithm and
needs full access to $\pi$. The second one, $\mathsf{EgalAlg}^{(\rm appx)}$,
approximates the greedy choice and only needs access to the innate error
rates, but it assume that the innate predictions are pairwise independent. We
show that with some modifications $\mathsf{EgalAlg}^{(\rm appx)}$works under
the assumption that the vertices have group dependency; see section 4.2.

  4. 4.

We compare the two algorithms for egalitarian improvement by running
experiments on real and synthetic graphs and compare their performance to four
benchmark methods. Our experiments show that by modifying only a few vertices,
we succeed in increasing the accuracy of a high percentage of network’s
agents; see Figure 1.

Figure 1: Comparison of # modified nodes for Accuracy $>90\%$ on different
dataset (lower is better).

##  2 Models and Problem Definition

Consider a set $\Omega$ whose elements are labeled as $+1$ or $-1$, i.e.,
there exists a function $y:\Omega\rightarrow\\{-1,+1\\}$ such that for any
$a\in\Omega$, $y(a)\in\\{-1,+1\\}$ is the (true) label of $a$. Consider a set
of agents $V=\\{v_{1},v_{2},\dots,v_{n}\\}$ who lack access to the true
labels. Given $a\in\Omega$, each agent $v_{i}$ uses a classifier $\hat{y}_{i}$
to predict the label of $a$, i.e., we have
$\hat{y}_{1},\hat{y}_{2},\dots,\hat{y}_{n}$ where for any $i$,
$\hat{y}_{i}:\Omega\rightarrow\\{-1,+1\\}$. The innate error rate of each
agent $v_{i}$ is defined as:

$\mathsf{err}(v_{i})=\operatorname*{\mathbb{E}}_{a\sim\Omega}\left[\mathbf{1}\left(\hat{y}_{i}(a)\neq
y(a)\right)\right]=\underset{a\sim\Omega}{\mathbb{P}}\left(\hat{y}_{i}(a)\neq
y(a)\right).$

We assume that this error is independent of true label. This assumption merely
makes our analysis simpler and without it our results can be generalized with
trivial modifications.

These predictions form the _innate assessment_ of the agents, which we denote
by $z^{(0)}(i,a)$, for arbitrary $i$ and $a$; thus,
$z^{(0)}(i,a)=\hat{y}_{i}(a)$. After, agents communicate with each other
through a _time varying averaging process_. At each point of time, each agent
$v_{i}$ communicates with a subset of other agents $\mathcal{N}^{(t)}(v_{i})$,
and her assessment will update as:

$z^{(t)}(i,a)=C_{i}\cdot\left(\sum_{v_{j}\in\mathcal{N}^{(t)}(v_{i})}W^{(t)}_{i,j}z^{(t-1)}(j,a)+\alpha_{i}\hat{y}_{i}(a)\right),$

where $W^{(t)}_{i,j}$ denotes the influence of $v_{j}$ on $v_{i}$ at time $t$,
$\alpha_{i}$ is $v_{i}$’s stubbornness, $C_{i}$ is a normalizing constant and
$z^{(t-1)}(i,a)$ and $z^{(t)}(i,a)$ respectively denote $v_{i}$’s assessment
before the $t$th round of communication and after it.

Formally, given $a\in\Omega$, let
$\mathbf{\hat{y}}(a)=\left(\hat{y}_{1}(a),\hat{y}_{2}(a),\dots\hat{y}_{n}(a)\right)$
and $\mathbf{z}^{(0)}(a)=\mathbf{\hat{y}}(a)$. Assume having a sequence of
$n\times n$ matrices $\left(W^{(t)}\right)_{t=1}^{\infty}$,
$\boldsymbol{\alpha}=(\alpha_{1},\alpha_{2},\dots,\alpha_{n})$ and
$\boldsymbol{C^{(t)}}=(C^{(t)}_{1},C^{(t)}_{2},\dots,C^{(t)}_{n})$. For any
$t\geq 1$ we have:

$\mathbf{z}^{(t)}(a)=\boldsymbol{C^{(t)}}\odot\left(W^{(t)}\mathbf{z}^{(t-1)}(a)+\boldsymbol{\alpha}\odot\mathbf{\hat{y}}(a)\right)~{},$
(1)

where $\odot$ denotes the Hadamard product which is defined to be the vector
(matrix) obtained from the pairwise product of the elements in two other
vectors (matrices). 222 Let $A,B\in\mathbb{R}^{n\times m}$, and $C=A\odot B$.
We have that $C\in\mathbb{R}^{n\times m}$ and $C_{ij}=A_{ij}\cdot B_{ij}$ Let
$\mathbf{z}^{*}(a)=\left(z^{*}(1,a),z^{*}(2,a),\dots,z^{*}(n,a)\right)$ be the
vector that the above process converges to i.e.,

$\mathbf{z}^{*}(a)=\lim_{t\rightarrow\infty}\mathbf{z}^{(t)}(a)~{}.$

We call $\mathbf{z}^{*}(a)$ the _the expressed prediction_ vector. We assume
that this limit has the following closed form:

$\exists\bar{W}\in\mathbb{R^{+}}^{n\times n}\ \text{ s. t. }\forall
a\in\Omega,\ \mathbf{z}^{*}(a)=\bar{W}\mathbf{\hat{y}}(a)^{\mathsf{T}}~{}.$
(2)

$\mathbb{R}^{+}$ being the set of all non-negative real numbers. We call
$\bar{W}$ the _expressed (social) influence_ matrix.

The above assumption is indeed proven to hold true in many well studied
models. To name a few:

##### DeGroot Model (DeGroot, 1974)

Given a row-stochastic matrix ${W\in\mathbb{R}^{+}}^{n\times n}$, DeGroot
Model evolves as:

$\mathbf{z}^{(t)}_{\textsc{DeGroot}}(a)=W\mathbf{z}^{(t-1)}_{\textsc{DeGroot}}(a),~{}\mathbf{z}^{(0)}_{\textsc{DeGroot}}(a)=\mathbf{\hat{y}}(a),$

It is known that

$\mathbf{z}^{*}_{\textsc{DeGroot}}(a)=\Pi\mathbf{\hat{y}}(a)~{},$

where $\Pi$ is a block diagonal matrix with blocks
$\Pi_{1},\Pi_{2},\dots,\Pi_{k}$, and each block corresponds to a strongly
connected component of the graph corresponding to $W$. In each block all rows
are identical.

##### Friedkin–Johnsen (FJ) Model (Friedkin & Johnsen, 1990)

Given an arbitrary matrix with non-negative weights $W$, for each $i\in[n]$
let $C_{i}=1/(1+\sum_{j\in\mathcal{N}(i)}W_{i,j})$. FJ model evolves as
follows:

$\displaystyle\mathbf{z}^{(t)}_{\textsc{FJ}}(a)=\boldsymbol{C}\odot\left(W\mathbf{z}^{(t-1)}_{\textsc{FJ}}(a)+\mathbf{\hat{y}}(a)\right),\
\ \mathbf{z}^{(0)}_{\textsc{FJ}}(a)=\mathbf{\hat{y}}(a).$

It is known that if $W$ is symmetric the FJ model converges to the following
closed form:

$\mathbf{z}^{*}_{\textsc{FJ}}(a)=(I+L)^{-1}\mathbf{\hat{y}}(a),$

where $L$ is the combinatorial Laplacian of the indirected graph corresponding
to $W$ and $I$ denotes the identity matrix.

Both DeGroot and FJ model use a constant matrix $W$ in their evolution. The
following shows a time varying evolution:

##### Finite time Models

Assume a finite sequence of row stochastic matrices
$W^{(1)},W^{(2)},\dots,W^{(T)}$, for any $t>T$, let $W^{(t)}$ be the identity
matrix and let $\boldsymbol{\alpha}$ be all zeros vector. It is
straightforward to see that the general equation of eq. 1 will converge to

$\mathbf{z}^{*}_{\textsc{Finite}}(a)=\bar{W}{\mathbf{\hat{y}}}(a),~{}\bar{W}=\prod_{i=1}^{T}W^{(i)}~{}.$

###  2.1 Statement of Problems

Assume any time varying averaging model which converges to a close form as eq.
2. Thus, for a given $a\in\Omega$ and $v_{i}\in V$ the _expressed_ prediction
of $v_{i}$ on $a$ is equal to

$z^{*}(i,a)=\sum_{j=1}^{n}\bar{W}_{ij}\hat{y}_{j}(a)~{}.$

Note that the value of $z^{*}(i,a)$ is a function of the expressed social
influence matrix $\bar{W}$ as well as the quality of all agents’ classifiers
which is formulated in the joint probability distribution of
$\mathbf{\hat{y}}$. If the true label $y(a)$ equals $+1$, the positive values
of $z^{*}(i,a)$ are preferable, otherwise negative values of $z^{*}(i,a)$ are
better. In other words, we would like $y(a)$ and $z^{*}(i,a)$ to have the same
sign. We define $\mathcal{Z}(i,a):V\times\Omega\rightarrow[-1,1]$ as follows:

$\mathcal{Z}(i,a)=y(a)\cdot z^{*}(i,a)~{}.$

The larger values for $\mathcal{Z}(i,a)$ correspond to the fact that agent
$v_{i}$ makes a good prediction on an object $a$. If $\mathcal{Z}(i,a)<0$ we
consider this prediction _faulty_.

##### Improving quality of selected classifiers

Assume that we have a tool to improve the quality of classifiers. Formally,
let $\varphi\in(0,1]$ be a given constant. For any arbitrary agent $v_{i}$ we
may improve $\hat{y}_{i}$ to $\tilde{y}_{i}:\Omega\rightarrow[0,1]$ as
follows:

$\forall a\in\Omega,~{}\tilde{y}_{i}(a)=(1-\varphi)\hat{y}_{i}(a)+\varphi
y(a)~{}.$ (3)

We would like to improve the quality of a selected subset of agents’
classifiers (innate predictions) to maximize the overall quality of expressed
predictions among all agents. Formally we are interested in selecting a subset
$S$ of $k$ agents, i.e., $S\subseteq V$, $\absolutevalue{S}=k$ and improve the
quality of the classifier as follows:

$\forall
a\in\Omega,~{}\tilde{y}_{i}(a)=\begin{cases}(1-\varphi)\hat{y}_{i}(a)+\varphi
y(a)~{}&\text{ if }v_{i}\in S\\\ \hat{y}_{i}(a)&\text{ if }v_{i}\notin S\\\
\end{cases}$ (4)

Let

$z_{\rm new}^{*}(i,a)=\sum_{j=1}^{n}\bar{W}_{ij}\tilde{y}_{j}(a)\ \
\&~{}\mathcal{\mathcal{Z}}_{\rm new}(i,a)=y(a)\cdot z_{\rm new}^{*}(i,a)~{}.$

In the first problem that we study, $S$ is selected to maximize an _aggregate_
objective function:

$\mathcal{G}^{({\rm
agg})}(S)\triangleq\operatorname*{\mathbb{E}}_{a\sim\Omega}\left[\sum_{i=1}^{n}\mathcal{\mathcal{Z}}_{\rm
new}(i,a)-\mathcal{Z}(i,a)\right]$ (5)

The above objective function is great, but it has the shortcoming of any other
aggregate objective function: it is possible that one agent benefits
enormously from it at the cost of many other agents getting extremely little.

Therefore, we also study the following _egalitarian_ objective function in
which we count the expected _number_ of agents whose faulty predictions will
improve.

$\mathcal{G}^{({\rm
egal})}(S){\triangleq}\operatorname*{\mathbb{E}}_{a\sim\Omega}\left[\sum_{i=1}^{n}\mathbf{1}(\mathcal{Z}(i{,}a){<}0\wedge\mathcal{Z}(i{,}a){<}\mathcal{\mathcal{Z}}_{\rm
new}(i{,}a))\right].$

We are now ready to formally state the problems.

######  Problem 1 (Aggregate improvement through improving $k$ selected
agents).

What is an optimal way to select a subset $S\subseteq V$ and update their
innate predictions as eq. 4 to maximize the following objective function:

${\rm OPT^{({\rm agg})}}=\underset{S\subseteq V\\\ ;|S|=k}{\rm{max}}\
\mathcal{G}^{({\rm agg})}(S)~{}.$

######  Problem 2 (Egalitarian improvement through improving $k$ selected
agents).

What is an optimal way to select a subset $S\subseteq V$ and update their
innate predictions as eq. 4 to maximize the following objective function:

${\rm OPT^{({\rm egal})}}=\underset{S\subseteq V\\\ ;|S|=k}{\max}\
\mathcal{G}^{({\rm egal})}(S)~{}.$

The above process has two main parameters: a joint probability distribution
$\pi:\Omega\times\\{-1,+1\\}^{V}\rightarrow[0,1]$, where for any $a\in\Omega$
and $\vec{b}\in\\{-1,+1\\}^{n}$,
$\pi(a,\vec{b})=\operatorname*{\mathbb{P}}(\wedge_{i=1}^{n}\hat{y}_{i}(a)=b_{i})$
as well as $\bar{W}$ which is the expressed influence matrix. While in most
applications $\bar{W}$ is either available in closed form (e.g., for DeGroot,
FJ or finite models) or it can be approximated using iterative methods, our
access to $\pi$ depends on assumptions which may vary depending on our
application. In fact, we present our algorithms assuming different access
levels to the joint probability distribution $\pi$.

##  3 Summary of Results

In this section, we present a summary of our main results. Let us first list
the assumptions we make on the access level to $\pi$ and $\bar{W}$:

######  Assumption 3.1 (Best scenario).

Assume having _complete_ knowledge of $\pi$.

The above assumption is reasonable if $\Omega$ is a small finite set. For
instance in cases where $\Omega$ can be partitioned to a few types and the
agents make the same predictions on any element of the same type, e.g., see
DeMarzo et al. (2003); Hązła et al. (2023); Gaitonde et al. (2021)

Clearly, it is possible that the above assumption does not hold true. However,
the algorithm needs to have _some knowledge_ of the probability distribution
of innate predictions.

######  Assumption 3.2 (some knowledge of $\pi$).

Assume having some knowledge of classifiers’ dependence/independence and the
innate error rates.

######  Assumption 3.3 (minimum knowledge of $\pi$).

Assume having only knowledge of innate error rates
$\\{\mathsf{err}(v_{i})\\}_{v_{i}\in V}$.

The summary of our main results is that 1 is easy, i.e., we show an exact
polynomial time algorithm for it assuming minimum knowledge of $\pi$. On the
other hand, we show that 2 is hard, i.e., we show that exactly solving it is
NP-complete even assuming full knowledge of $\pi$. Note that this hardness
also holds for the cases in which we have less knowledge of $\pi$. Later, we
show greedy algorithms for approximately solving it under different
assumptions.

Initially, in all of our results we assume access to the closed form of
$\bar{W}$. We then show that the guarantees still hold with a slight change
when an approximation of $\bar{W}$ is given.

######  Assumption 3.4 (knowledge to an approximation of $\bar{W}$).

Assume having knowledge of $\widehat{\bar{W}}$ such that

$\left|\widehat{\bar{W}}-\bar{W}\right|_{1}\leq\epsilon~{},$

where $\left|\cdot\right|_{1}$ is the $\ell_{1}$ norm and $\epsilon$ a
precision parameter.

###  3.1 Optimizing the aggregate objective function

######  Theorem 3.5.

There is an algorithm with run-time complexity $\Theta\left(n^{2}\right)$
which given $\bar{W}$ and $\\{\mathsf{err}(v_{i})\\}_{i=1}^{n}$ as input
parameters outputs $S$ such that $\mathcal{G}^{({\rm agg})}(S)={\rm OPT^{({\rm
agg})}}$.

######  Remark 3.6.

Let $\mathsf{ALG}$ be the algorithm whose performance guarantees are presented
in theorem 3.5. Let $S$ be the output of $\mathsf{ALG}$ when $\bar{W}$ is
given to it as input parameter, and let $S^{\prime}$ be the output if
$\widehat{\bar{W}}$ is given. We have:

$\mathcal{G}^{({\rm egal})}(S^{\prime})\geq\mathcal{G}^{({\rm
egal})}(S)-2k\epsilon~{}.$

We present this algorithm in sections 4.1 and A.1.

###  3.2 Optimizing the egalitarian objective function

We now present our results about 2.

We call a matrix with no negative entry _non-negative_. In DeGroot model if
$W$ is non-negative, $\bar{W}$ is also non-negative and in FJ model if $W$ is
non-negative and symmetric, $\bar{W}$ is also non-negative (Chebotarev &
Shamis, 2006) .

In this section we assume that $\bar{W}$ is non-negative.

######  Theorem 3.7.

Under 3.1 and assuming $\absolutevalue{\Omega}$ is polynomial in $n$ , 2 is
NP-hard.

Since 2 is NP-hard, we concentrate on finding an approximation algorithm for
it in different scenarios.

##### Approximate solution with full access to $\mathbf{\pi}$.

Assume that $\Omega$ is finite and for any $a\in\Omega$ and
$b\in\\{-1,+1\\}^{n}$ we can evaluate the probability of the event
$\bigwedge_{i=1}^{n}\hat{y}_{i}(a)=b(i)$.

######  Theorem 3.8.

There is a greedy algorithm with runtime $\Theta\left(|\Omega|n^{2}k\right)$
which by receiving $\pi$ and $\bar{W}$ as input parameters outputs $S$
satisfying

$\mathcal{G}^{({\rm egal})}(S)\geq(1-1/e){\rm OPT^{({\rm egal})}}.$

A pseudocode of our algorithm, $\mathsf{EgalAlg}$ is presented in section A.3,
an overview of main ideas is presented section 4.2. Note that the runtime of
$\mathsf{EgalAlg}$ grows linearly in $\absolutevalue{\Omega}$. Later, we
present $\mathsf{EgalAlg}^{(\rm appx)}$whose complexity _does not_ grow with
$\absolutevalue{\Omega}$ (see section 4.2). Therefore, even if $\pi$ is fully
known, by employing $\mathsf{EgalAlg}^{(\rm appx)}$, we may prefer to suffice
to a lower quality approximation to gain better time complexity.

##### Approximate solution with minimum information

While the previous result shows a constant approximation, the following
theorem shows that by only having the innate error rates
$\\{\mathsf{err}(v_{j})\\}_{j=1}^{n}$ and $\bar{W}$ we are not able to achieve
any good approximation.

######  Theorem 3.9.

Any solution to 2 which only uses $\bar{W}$ and innate error rates
$\\{\mathsf{err}(v_{j})\\}_{j=1}^{n}$ makes an error which can be as large as
$\Omega(n)$.

We restate and prove the above theorem in theorem A.4.

Motivated by the above results, we now present our results when more knowledge
about the classifiers are available. For instance, in addition to knowing the
error rates we assume that the classifiers are pairwise independent.

Using these assumptions we design $\mathsf{EgalAlg}^{(\rm appx)}$ and show
theoretical guarantees for its performance.

##### Approximate solution assuming independence.

Assume that the classifiers $\\{\hat{y}_{i}\\}_{v_{i}\in V}$ are pairwise
independent. We have:

######  Theorem 3.10.

There is a greedy algorithm, $\mathsf{EgalAlg}^{(\rm appx)}$, with run-time
$\Theta(n^{3}k)$ which by receiving $\\{\mathsf{err}(v_{i})\\}_{v_{i}\in V}$
and $\bar{W}$ as input parameters outputs $S$ satisfying

$\mathcal{G}^{({\rm egal})}(S)\geq[(1-1/e)-\Delta^{\rm ind}]\cdot{\rm
OPT^{({\rm egal})}}~{},$

where $\Delta^{\rm ind}$ is a parameter depending on the network. If the
network is _nicely structured_ $\Delta^{\rm ind}=o(1)$; see section 4.2.1 .

We generalize the assumption of pairwise independence to group dependence as
follows:

##### Approximate solution assuming group dependence.

Assume that some agents belong to opposing groups ${\mathcal{R}}$ and
${\mathcal{B}}$ and some agents are colorless; they are in ${\mathcal{W}}$.
The classifiers of the agents in ${\mathcal{W}}$ are independent, and the
classifiers of ${\mathcal{R}}$ and ${\mathcal{B}}$ agents have positive intra-
correlation and negative inter-correlation as described in definition 4.7.
This model describes a situation when have a classification task that can be
influenced by an exogenous factor, e.g, their position or political leaning.
Clearly by setting $V={\mathcal{W}}$ we will have the previous model. In this
case we have:

######  Theorem 3.11.

There is a greedy algorithm, $\mathsf{EgalAlg}^{(\rm appx)}$, with run-time
$\Theta(n^{3}k)$ which by receiving _individual and group_ error rates and
$\bar{W}$ as input parameters outputs $S$ satisfying

$\mathcal{G}^{({\rm egal})}(S)\geq[(1-1/e)-\Delta^{\rm gr}]\cdot{\rm
OPT^{({\rm egal})}}~{},$

where $\Delta^{\rm gr}\geq\Delta^{\rm ind}$ is a parameter depending on the
network and the dominance of colors ${\mathcal{R}}$ and ${\mathcal{B}}$ on
other agents. Not surprisingly, $\Delta^{\rm gr}$ becomes closer to
$\Delta^{\rm ind}$ as the number of colorless agents increases. If the network
is _nicely structured_ and _nicely colored_ $\Delta^{\rm gr}=o(1)$; See
section 4.2.2 .

The following remark holds ture both under pairwise Independence and group
dependency:

######  Remark 3.12.

Let $S$ be the output of $\mathsf{EgalAlg}^{(\rm appx)}$when $\bar{W}$ is
given to it as input parameter, and let $S^{\prime}$ be the output if
$\widehat{\bar{W}}$ is given. We have:

$\mathcal{G}^{({\rm egal})}(S^{\prime})\geq\mathcal{G}^{({\rm
egal})}(S)(1-8k\epsilon)~{}.$

##  4 Algorithms

In this section we present our algorithms. All of the algorithms are greedy.
We provide an exact solution for 1 in section 4.1. In section 4.2, because of
the NP-harness of 2, we present a _constant_ approximation algorithm for it;
we call this algorithm $\mathsf{EgalAlg}$ . We then present
$\mathsf{EgalAlg}^{(\rm appx)}$ which has a lower time complexity but worst
approximation guarantees assuming pairwise independence of agents. In this
case, our approximation ratio depends on the network structure. In section
4.2.2, we modify $\mathsf{EgalAlg}^{(\rm appx)}$ so that it works under a
milder assumption formalized as _group dependency_.

Pseudocodes for our egalitarian algorithms are presented in section A.3

###  4.1 The aggregate objective function

For any vertex $v_{j}$ let’s define the influence score and its approximation
by ${\rm Inf}(v_{j})=\sum_{i=1}^{n}\bar{W}_{ij}\mathsf{err}(v_{i})~{}.$ The
following lemma is proven in section A.1.

######  Lemma 4.1.

Let $U=\\{u_{1},u_{2},\dots,u_{k}\\}$ be top-$k$ vertices with highest value
of $\sum_{u_{j}\in U}{\rm Inf}(u_{j})$. We have that:

$\mathcal{G}^{({\rm agg})}(U)={\rm OPT^{({\rm agg})}}~{}.$

##### Proof of Theorem 3.5 and Remark 3.6

With the above lemma, we design an algorithm that for all $v_{j}$s calculates
their influence score, and outputs the top-$k$. The complexity of such
algorithm is $\Theta(n^{2}+n\log n+k)=\Theta(n^{2})$. In section A.1 we also
prove Remark 3.6.

###  4.2 The egalitarian objective function

Optimizing the egalitarian function is NP-hard (See theorem A.3). We show that
$\mathcal{G}^{({\rm egal})}:2^{V}\rightarrow[0,n]$ is monotonic and sub-
modular (See lemmas A.5 and A.6). Thus, a greedy algorithm will provides a
$(1-1/e)$ approximation Nemhauser & Wolsey (1978).

We now concentrate on obtaining the greedy choice. Formally, we define the
function ${\mathsf{gr}}(S):2^{V}\rightarrow V$ as follows:

${\mathsf{gr}}(S)=\underset{u\in V}{\rm argmax}\ \mathcal{G}^{({\rm
egal})}(S\cup\\{u\\})-\mathcal{G}^{({\rm egal})}(S)~{}.$ (6)

The following lemma is proven in section A.3.1:

######  Lemma 4.2.

For any $S\subseteq V$ we have:

${\mathsf{gr}}(S)=\underset{u\in V}{\rm
argmax}\sum_{\begin{subarray}{c}i=1:n\\\ \bar{W}_{iu}\neq
0\end{subarray}}\Delta{\mathcal{G}}_{i}(S,u)~{},$ (7)

where $\Delta{\mathcal{G}}_{i}(S,u)$ is defined to be333We use $\wedge$ and
$\vee$ to denote respectively the logical operations conjunction and
disjunction which are _“and”_ and _“or”_.

$\operatorname*{\mathbb{P}}_{a\sim\Omega}\left(\mathcal{Z}(i,a)\leq
0\wedge\left(\bigwedge_{\begin{subarray}{c}v_{j}\in S\\\ \bar{W}_{ji}\neq
0\end{subarray}}y(a){=}\hat{y}_{j}(a)\right)\wedge
y(a){\neq}\hat{y}_{u}(a)\right)$

##### Proof of theorem 3.8

Our proposed algorithm, $\mathsf{EgalAlg}$ starts with $S=\emptyset$.
Iteratively, ${\mathsf{gr}}(S)$ is added to $S$ until $\absolutevalue{S}=k$.
Assume that $\Omega$ is finite and we have access to $\pi$. Using lemma 4.2 we
obtain the greedy choice as follows: for any $a\in\Omega$ and $v_{i}\in V$, we
evaluate the validity of the event
$\left(\bigwedge_{\begin{subarray}{c}v_{j}\in S\\\ \bar{W}_{ji}\neq
0\end{subarray}}y(a){=}\hat{y}_{j}(a)\right)\wedge y(a){\neq}\hat{y}_{u}(a)$.
If this event is valid, we calculate $\mathcal{Z}(i,a)$ and verify
$\mathcal{Z}(i,a)<0$ which takes $n$ steps. We find best $u$ by using eq. 7
and iterating over all choices of $i\in V$ and $a\in\Omega$. The total runtime
for $k$ iterations is $\Theta(\absolutevalue{\Omega}n^{2}k)$.

####  4.2.1 Independent classifiers

In this section we consider the case where the classifiers
$\\{\hat{y}_{i}\\}_{v_{i}\in V}$ are pairwise independent which falls into the
scenario in which we have _some_ knowledge of $\pi$ (Assumption 3.2). In this
case we may estimate the greedy choice as a function of
$\\{\mathsf{err}(v_{i})\\}_{i=1}^{n}$ and $\bar{W}$.

Let’s state the main result of this section and then we present the steps that
lead us to the selection of the greedy choice:

######  Theorem 4.3.

Let $S$ be the output of a greedy algorithm which starts by taking
$S=\emptyset$ and for $k$ steps keeps updating $S$ to $S\cup\\{g\\}$ where

$g=\underset{u}{\rm argmax}\sum_{\begin{subarray}{c}i=1:n\\\ \bar{W}_{iu}\neq
0\end{subarray}}\widehat{\Delta{\mathcal{G}}}_{i}(S,u)~{},$

and $\widehat{\Delta{\mathcal{G}}}_{i}(S,u)$ is defined in lemma 4.6, we have:

$\mathcal{G}^{({\rm egal})}(S)\geq[(1-1/e)-\Delta^{\rm ind}]\cdot{\rm
OPT^{({\rm egal})}}~{},$

with $\Delta^{\rm ind}=\Theta(\absolutevalue{{\mathcal{A}}})$ and
$\mathcal{A}$ is the set of ambiguous vertices.

##### Ambiguous vertices

Consider the partitioning of $V$ with $V^{+}$ as low error vertices and
$V^{-}$ as high error vertices:

$V^{+}=\\{v_{j}\mid\mathsf{err}(v_{j})\leq 1/2\\}\;\&\
V^{-}=\\{v_{j}\mid\mathsf{err}(v_{j})>1/2\\}$

with respect to this partition we define the following vectors whose elements
are in $[0,1]$:

${\mathcal{E}}^{+}=\left(1-2\mathsf{err}(v_{j})\right)_{v_{j}\in V^{+}}\ \ \&\
\ {\mathcal{E}}^{-}=\left(2\mathsf{err}(v_{j})-1\right)_{v_{j}\in V^{-}}$

For any arbitrary vertex $v_{i}\in V$, low error and high error vertices
contribute in the value of $\mathcal{Z}(i,a)$ through the following
coefficient vectors:

$\bar{W}^{+}_{i}=(\bar{W}_{ij})_{v_{j}\in V^{+}}\quad\&\ \
\bar{W}^{-}_{i}=(\bar{W}_{ij})_{v_{j}\in V^{-}}$

The ambiguous vertices are those who _are not_ dominated by neither $V^{+}$ or
$V^{-}$. Formally,

######  Definition 4.4.

[Ambiguous vertices] Let
$\bar{W}_{i}=(\bar{W}_{i1},\bar{W}_{i2},\dots,\bar{W}_{in})$,
$\absolutevalue{\cdot}_{2}$ denote the $\ell_{2}$ norm and
$\langle\cdot,\cdot\rangle$ dot product. We call a vertex $v_{i}\in V$
_ambiguous_ if it satisfies:

$\absolutevalue{\frac{\langle\bar{W}_{i}^{+},{\mathcal{E}}^{+}\rangle}{\absolutevalue{\bar{W}_{i}}_{2}}-\frac{\langle\bar{W}_{i}^{-},{\mathcal{E}}^{-}\rangle}{\absolutevalue{\bar{W}_{i}}_{2}}}\leq
4\sqrt{\log n}~{}.$

A network is _nicely structured_ if it has no ambiguous vertex.

If a vertex is _non-ambiguous_ we can estimate the gain associated to it very
precisely:

######  Lemma 4.5.

Let $\Delta{\mathcal{G}}_{i}(S,u)$ and
$\widehat{\Delta{\mathcal{G}}_{i}}(S,u)$ be as defined respectively as in
lemma 4.2 and lemma 4.6. If a vertex is _non-ambiguous_ we have:

$\absolutevalue{\Delta{\mathcal{G}}_{i}(S,u)-\widehat{\Delta{\mathcal{G}}_{i}}(S,u)}\leq
o(n^{-1})~{}.$

We now present the following lemma related to the approximation of greedy
choice. All the proofs and details are presented in section A.4.

######  Lemma 4.6.

Let $\Delta{\mathcal{G}}_{i}(S,u)$ be as lemma 4.2. Let
$\widehat{\Delta{\mathcal{G}}_{i}}(S,u):2^{V}\times V\rightarrow[0,1]$ be
defined as follows:

$\widehat{\Delta{\mathcal{G}}_{i}}(S,u)\triangleq\mathbf{1}\left(\Psi_{i}(S,u)<0\right)\mathsf{err}(u)\prod_{\begin{subarray}{c}{v_{j}\in
S}\\\ \bar{W}_{ij}\neq 0\end{subarray}}(1-\mathsf{err}(v_{j}))~{}.$

We have:

$\absolutevalue{\widehat{\Delta{\mathcal{G}}_{i}}(S,u)-\Delta{\mathcal{G}}_{i}(S,u)}\leq\exp\left(-\frac{\Psi_{i}(S,u)^{2}}{4\sum_{i=1}^{n}\bar{W}_{ij}^{2}}\right)~{},$

where

$\Psi_{i}(S,u)=-\bar{W}_{iu}+\sum_{v_{j}\in
S}\bar{W}_{ij}+\sum_{\begin{subarray}{c}j=1:n\\\ j\not\in
S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}[1-2\mathsf{err}(j)]~{}.$

##### Proof of theorems 3.10 and 3.12

A complete pseudocode of our proposed algorithm, $\mathsf{EgalAlg}^{(\rm
appx)}$, is presented in section A.3 (algorithm 2). It is easy to see that the
runtime is dominated by $\Theta(n^{3}k)$. Note that the correctness of theorem
3.10 is directly concluded from theorem 4.3 by setting
$\absolutevalue{{\mathcal{A}}}=0$. We present the proof of theorems 4.3 and
3.12 in section A.4.2.

####  4.2.2 Group dependent classifiers

We now consider a case when agents are either _red_ , _blue_ or none
(_white_). The agents who are red or blue agent either all follow a group
decision, or they independently follow an individual decision. The group
decision of the blue agents is always the opposite of the group decision of
red agents.

######  Definition 4.7.

[Group Dependence] Assume that the set of agents $V$ can be partitioned as
$V={\mathcal{R}}\cup{\mathcal{B}}\cup{\mathcal{W}}$. We assume a set of
classifiers $\hat{y}^{\rm indv}_{1},\hat{y}^{\rm indv}_{2},\dots,\hat{y}^{\rm
indv}_{n}:\Omega\rightarrow\\{-1,+1\\}$ which are pairwise independent.
Furthermore, we assume two group classifiers $\hat{y}^{\rm
gr}_{{\mathcal{R}}},\hat{y}^{\rm
gr}_{{\mathcal{B}}}:\Omega\rightarrow\\{-1,+1\\}$ which satisfy:

$\forall a\in\Omega,\ \hat{y}^{\rm gr}_{{\mathcal{R}}}(a)\neq\hat{y}^{\rm
gr}_{{\mathcal{B}}}(a)~{}.$

Given a constant $\rho\in[0,1]$, these classifiers construct
$\\{\hat{y}_{1},\hat{y}_{2},\dots,\hat{y}_{n}\\}$ as follows:

With probability $\rho$ the red and blue agents follow their groups’ decision,
i.e.,

$\forall v_{i}\in{\mathcal{R}},\ \hat{y}_{i}(a)=\hat{y}^{\rm
gr}_{{\mathcal{R}}}(a)\wedge\forall v_{i}\in{\mathcal{B}},\
\hat{y}_{i}(a)=\hat{y}^{\rm gr}_{{\mathcal{B}}}(a)$

And the white agents independently follow their individual decisions, i.e, for
all $v_{i}\in{\mathcal{W}}$, $\hat{y}_{i}(a)=\hat{y}^{\rm indv}_{i}(a)~{}.$

Alternatively, with probability $1-\rho$ , all agents independently use their
individual classifiers. i.e,

$\forall v_{i}\in V,\ \hat{y}_{i}(a)=\hat{y}^{\rm indv}_{i}(a)~{}.$

In the above setting we use the following notation: For any $v_{j}\in V$ we
define $\mathsf{err}^{\rm
indv}(v_{j})=\operatorname*{\mathbb{P}}\left(\hat{y}^{\rm indv}_{j}(a)\neq
y(a)\right)$, and

$\mathsf{err}({\mathcal{R}})=\operatorname*{\mathbb{P}}\left(\hat{y}^{\rm
gr}_{\mathcal{R}}(a)\neq y(a)\right)\ \&\
\mathsf{err}({\mathcal{B}})=\operatorname*{\mathbb{P}}\left(\hat{y}^{\rm
gr}_{\mathcal{B}}(a)\neq y(a)\right)$

It is immediate from the definition that
$1-\mathsf{err}({\mathcal{B}})=\mathsf{err}({\mathcal{R}})$.

In this setting, the estimation of $\Delta{\mathcal{G}}_{i}(S,u)$ is more
involved and is presented in section 4.2.2. In this case, our greedy algorithm
uses $\\{\mathsf{err}^{\rm indv}(v_{j})\\}_{j=1}^{n}$,
$\mathsf{err}({\mathcal{R}})$, $\mathsf{err}({\mathcal{B}})$ and $\bar{W}$ or
its approximation. The final result follows:

######  Theorem 4.8.

Let $S$ be the output of a greedy algorithm which approximates greedy choice
as defined in lemma A.12. We have:

$\mathcal{G}^{({\rm egal})}(S)\geq[(1-1/e)-\Delta^{\rm gr}]\cdot{\rm
OPT^{({\rm egal})}}~{},$

where $\Delta^{\rm
gr}=\Theta(\rho\absolutevalue{{\mathcal{A}}^{{\mathcal{W}}}}+(1-\rho)\absolutevalue{{\mathcal{A}}})$,
$\mathcal{A}$ is the set of ambiguous vertices defined before and
${\mathcal{A}}^{{\mathcal{W}}}$ is the set of _${\mathcal{W}}$ -ambiguous_
vertices.

#####  $\boldsymbol{{\mathcal{W}}}$-Ambiguous vertices.

As in section 4.2.2, we partition ${\mathcal{W}}$ to low error vertices
${\mathcal{W}}^{+}$ and high error vertices ${\mathcal{W}}^{-}$. Similarly we
define ${\mathcal{E}^{\mathcal{W}}}^{+}$, ${\mathcal{E}^{\mathcal{W}}}^{-}$
and for any $v_{i}\in V$, ${\bar{W}^{{\mathcal{W}}+}_{i}}$ and
${\bar{W}^{{\mathcal{W}}-}_{i}}$; for details see section A.5.4. We define:

######  Definition 4.9.

[ ${\mathcal{W}}$-Ambiguous vertices ] Let
$\bar{W}^{\mathcal{W}}_{i}=(\bar{W}_{ij})_{v_{j}\in{\mathcal{W}}}$, and
$\absolutevalue{\cdot}_{2}$ be the $\ell_{2}$ norm and
$\langle\cdot,\cdot\rangle$ be dot product.

We call an agent $v_{i}\in V$, _${\mathcal{W}}$ -ambiguous_ if it satisfies

$\absolutevalue{\frac{\langle{\bar{W}^{{\mathcal{W}}+}_{i}},{\mathcal{E}^{\mathcal{W}}}^{+}\rangle}{\absolutevalue{\bar{W}_{i}^{\mathcal{W}}}_{2}}-\frac{\langle{\bar{W}^{{\mathcal{W}}-}_{i}},{\mathcal{E}^{\mathcal{W}}}^{-}\rangle}{\absolutevalue{\bar{W}_{i}^{\mathcal{W}}}_{2}}}\leq
4\sqrt{\log n}+\Delta\bar{W}_{i}~{},$

where
$\Delta\bar{W}_{i}=\absolutevalue{\sum_{v_{j}\in{\mathcal{R}}}\bar{W}_{ij}-\sum_{v_{j}\in{\mathcal{B}}}\bar{W}_{ij}}~{}.$
A _network_ is _nicely colored_ if no vertex is ${\mathcal{W}}$-ambiguous.

##### Proof of theorems 3.11 and 3.12

Pseudocode and details are presented in sections A.5, A.3 and A.5.5. Theorem
3.11 can be directly concluded from theorem 4.8 by setting
$\absolutevalue{\mathcal{A}}=\absolutevalue{{\mathcal{A}}^{\mathcal{W}}}=0$.

##  5 Experiments

In this section, we empirically validate the effectiveness of our proposed
methods for 2 through a series of meticulously designed experiments. We test
our algorithms $\mathsf{EgalAlg}$ and $\mathsf{EgalAlg}^{(\rm appx)}$
(pseudocodes in section A.3) benchmarked against random selections together
with three heuristic methods: selecting nodes based on degree (Degree), innate
error rate (ErrRate), and the product of degree and error rate (DegXErr).

##### Synthetic Datasets

Synthetic data is generated with three components: a random graph $G$, a
weight matrix $\bar{W}$ and initial opinions $\mathbf{\hat{y}}$. To generate
$G$, we employ Erdős-Rényi model (ER) Erdös & Rényi (1959), Barabási-Albert
model (PA) Barabási & Albert (1999) and Watts-Strogatz model (WS) Watts &
Strogatz (1998). We generate the weight matrix $\bar{W}$ using the FJ model.
Each $\hat{y}_{i}(a)$ is sampled from Bernoulli distribution with a randomly
chosen $p_{i}$.

Table 1: Comparison of experiments on five methods Egal=$\mathsf{EgalAlg}$, Appx=$\mathsf{EgalAlg}^{(\rm appx)}$, Rand=Random selection.  |  | Datasets
---|---|---
Score |  Method |  ER (128) |  PA (128) |  WS (128) |  RandW (128) |  BIO (297) |  CSPK (39) |  FB (620) |  WIKI (890)
Acc@ k=log(n) |  Rand |  0.11 |  0.88 |  0.53 |  0.18 |  0.80 |  0.63 |  0.35 |  0.48
Degree |  0.08 |  0.96 |  0.42 |  0.12 |  0.78 |  0.84 |  0.36 |  0.49
ErrRate |  0.22 |  1.00 |  0.76 |  0.47 |  0.96 |  0.94 |  0.53 |  0.54
DegXErr |  0.18 |  1.00 |  0.89 |  0.37 |  0.96 |  1.00 |  0.72 |  0.78
Appx |  0.18 |  1.00 |  0.87 |  0.41 |  0.94 |  0.84 |  0.62 |  0.64
Egal |  0.27 |  1.00 |  1.00 |  0.58 |  1.00 |  1.00 |  0.88 |  0.96
#k @ Acc>90% |  Rand |  >100 |  7 |  10 |  34 |  8 |  10 |  94 |  22
Degree |  >100 |  4 |  17 |  45 |  9 |  4 |  93 |  26
ErrRate |  71 |  2 |  7 |  18 |  3 |  3 |  19 |  13
DegXErr |  71 |  2 |  6 |  18 |  3 |  3 |  32 |  7
Appx |  61 |  1 |  5 |  18 |  3 |  5 |  30 |  15
Egal |  55 |  1 |  3 |  12 |  1 |  1 |  9 |  2
#k @ Acc>75% |  Rand |  83 |  8 |  16 |  61 |  15 |  14 |  37 |  55
Degree |  83 |  5 |  28 |  64 |  14 |  6 |  20 |  54
ErrRate |  46 |  3 |  10 |  31 |  5 |  4 |  14 |  26
DegXErr |  51 |  3 |  8 |  36 |  4 |  3 |  8 |  16
Appx |  47 |  2 |  9 |  35 |  6 |  7 |  11 |  39
Egal |  36 |  2 |  4 |  19 |  2 |  2 |  4 |  3

##### Real-World Graphs

We also evaluate our methods on four diverse real network datasets Rossi &
Ahmed (2015), BIO Duch & Arenas (2005); Bader et al. (2012), CSPK Bader et al.
(2013), FB Rozemberczki et al. (2019), WIKI Leskovec et al. (2010). Here we
also apply finite step FJ model to construct weight matrix $\bar{W}$ and
randomly sample $\mathbf{\hat{y}}$ from Bernoulli distributions.

Figure 2: Algorithms performance on ER (top) and WIKI (bottom).

We define our accuracy Acc to be the achieved egalitarian gain, normalized by
its upper bound. For each dataset, we progressively increase $k$. Obviously,
as $k$ increases, the accuracy should increase. Therefore, we fix the
threshold value $k=\log(n)$ for different datasets and compare the
corresponding Acc of different methods. We also report the number of modified
nodes $k$ required to achieve certain levels of accuracy. See table 1 for
details. Figure 2 shows two of these results on real and synthetic graphs and
more are presented in Figure 3. More details about experiments can be found in
appendix B. Code of our experiments is available through link
444https://github.com/jackal092927/social_learning_public.

From the results we can conclude that, in summary, all six algorithms can be
categorized into four tiers: Tier1={$\mathsf{EgalAlg}$},
Tier2={$\mathsf{EgalAlg}^{(\rm appx)}$}, Tier3={DegXErr, ErrRate},
Tier4={Degree, Rand}. We rank the efficiency of these methods as:
Tier1$\gg$Tier2$\geq$Tier3$\gg$Tier4. Our greedy algorithm $\mathsf{EgalAlg}$
in general performs best on all datasets. In some datasets the
$\mathsf{EgalAlg}^{(\rm appx)}$ algorithm outperforms algorithms in Tier3 & 4
when $k$ is very small, however, the performances of Tier2 & 3 algorithms
quickly become similar as $k$ increases. Tier4 algorithms are always the
slowest in improving our egalitarian objective function. On almost all
datasets, our greedy algorithm can achieve more than 80% accuracy within only
$\log n$ nodes selected to intervene, and it beats all the other baselines.
Our greedy approximation algorithm can achieve more than 70% accuracy. On all
datasets, it beats our two baselines in Tier4 and on some data sets it beats
all the baselines of Tier3 & 4.

## Conclusion

Given a network in which agents cooperatively perform a classification task,
we analyse the problem of optimally choosing $k$ vertices and improving their
innate predictions to maximize the overall network improvement.

##### Limitations and Future Directions

In this paper, our modeling relies on a few simplifications which may pose
limitations in the applicability of the methods, and they may be addressed in
future works:

  1. 1.

We assume that the social planner is capable of improving every agent’s innate
prediction equally through eq. 3. In reality, this improvement may depend on
the _agent_ , $i$, as well as the _data point_ , $a$.

  2. 2.

Our analyses are valid when the social influence graph has non-negative
weights and, in the current form, they do not generalize to graphs with
negative weights, e.g., signed graphs.

We believe that overcoming any of the above limitations would be an
interesting extension of our work, and we propose them as future directions.

## Acknowledgements

Xin and Gao would like to acknowledge NSF support through CCF-2118953,
CCF-2208663, DMS-2311064, DMS-2220271, and IIS-2229876.

## References

  * Abebe et al. (2018) Abebe, R., Kleinberg, J., Parkes, D., and Tsourakakis, C. E.  Opinion dynamics with varying susceptibility to persuasion.  In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pp. 1089–1098, 2018.
  * Acemoglu et al. (2011) Acemoglu, D., Dahleh, M. A., Lobel, I., and Ozdaglar, A.  Bayesian learning in social networks.  _The Review of Economic Studies_ , 78(4):1201–1236, 2011.
  * Adriaens et al. (2023) Adriaens, F., Wang, H., and Gionis, A.  Minimizing hitting time between disparate groups with shortcut edges.  In _Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_ , KDD ’23, pp. 1–10, 2023.
  * Arieli et al. (2021) Arieli, I., Sandomirskiy, F., and Smorodinsky, R.  On social networks that support learning.  In _Proceedings of the 22nd ACM Conference on Economics and Computation_ , EC ’21, pp. 95–96, 2021.
  * Bader et al. (2012) Bader, D. A., Meyerhenke, H., Sanders, P., and Wagner, D.  _Graph Partitioning and Graph Clustering_.  American Mathematical Society, 2012.
  * Bader et al. (2013) Bader, D. A., Meyerhenke, H., Sanders, P., and Wagner, D. (eds.).  _Graph Partitioning and Graph Clustering, 10th DIMACS Implementation Challenge Workshop, Georgia Institute of Technology, Atlanta, GA, USA, February 13-14, 2012. Proceedings_ , volume 588 of _Contemporary Mathematics_ , 2013. American Mathematical Society.  ISBN 978-0-8218-9869-7.  URL http://dblp.uni-trier.de/db/conf/dimacs/dimacs2012.html.
  * Barabási & Albert (1999) Barabási, A.-L. and Albert, R.  Emergence of scaling in random networks.  _Science_ , 286(5439):509–512, 1999.
  * Bindel et al. (2015) Bindel, D., Kleinberg, J., and Oren, S.  How bad is forming your own opinion?  _Games and Economic Behavior_ , 92:248–265, 2015.
  * Blot et al. (2016) Blot, M., Picard, D., Cord, M., and Thome, N.  Gossip training for deep learning.  In _9th NIPS Workshop on Optimization for Machine Learning_ , November 2016.
  * Borgs et al. (2014) Borgs, C., Brautbar, M., Chayes, J., and Lucier, B.  Maximizing social influence in nearly optimal time.  In _Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms_ , pp. 946–957. SIAM, 2014.
  * Chebotarev & Shamis (2006) Chebotarev, P. and Shamis, E.  On proximity measures for graph vertices.  arXiv math/0602073, 2006.
  * Cinus et al. (2023) Cinus, F., Gionis, A., and Bonchi, F.  Rebalancing social feed to minimize polarization and disagreement.  In _Proceedings of the 32nd ACM International Conference on Information and Knowledge Management_ , CIKM ’23, pp. 369–378, 2023.
  * Colin et al. (2016) Colin, I., Bellet, A., Salmon, J., and Clémençon, S.  Gossip dual averaging for decentralized optimization of pairwise functions.  In Balcan, M. F. and Weinberger, K. Q. (eds.), _Proceedings of The 33rd International Conference on Machine Learning_ , volume 48 of _Proceedings of Machine Learning Research_ , pp. 1388–1396. PMLR, 2016.
  * D’Angelo et al. (2019) D’Angelo, G., Severini, L., and Velaj, Y.  Recommending links through influence maximization.  _Theoretical Computer Science_ , 764:30–41, 2019.
  * DeGroot (1974) DeGroot, M. H.  Reaching a consensus.  _J. Am. Stat. Assoc._ , 69(345):118–121, 1974.
  * DeMarzo et al. (2003) DeMarzo, P. M., Vayanos, D., and Zwiebel, J.  Persuasion bias, social influence, and unidimensional opinions.  _The Quarterly journal of economics_ , 118(3):909–968, 2003.
  * Duch & Arenas (2005) Duch, J. and Arenas, A.  Community identification using extremal optimization.  _Physical Review E_ , 72:027104, 2005.
  * Eckles et al. (2019) Eckles, D., Esfandiari, H., Mossel, E., and Rahimian, M. A.  Seeding with costly network information.  In _Proceedings of the 2019 ACM Conference on Economics and Computation_ , EC ’19, pp. 421–422, 2019.
  * Erdös & Rényi (1959) Erdös, P. and Rényi, A.  On random graphs I.  _Publicationes Mathematicae Debrecen_ , 6:290, 1959.
  * Fellus et al. (2015) Fellus, J., Picard, D., and Gosselin, P.-H.  Asynchronous gossip principal components analysis.  _Neurocomputing_ , 169:262–271, December 2015.
  * Friedkin & Johnsen (1990) Friedkin, N. E. and Johnsen, E. C.  Social influence and opinions.  _J. Math. Sociol._ , 15(3-4):193–206, January 1990.
  * Gaitonde et al. (2021) Gaitonde, J., Kleinberg, J., and Tardos, É.  Polarization in geometric opinion dynamics.  In _Proceedings of the 22nd ACM Conference on Economics and Computation_ , pp. 499–519, July 2021.
  * Garimella et al. (2017) Garimella, K., Gionis, A., Parotsidis, N., and Tatti, N.  Balancing information exposure in social networks.  In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , volume 30, pp. 4666–4674, 2017.
  * Giaretta & Girdzijauskas (2019) Giaretta, L. and Girdzijauskas, Š.  Gossip learning: Off the beaten path.  In _2019 IEEE International Conference on Big Data (Big Data)_ , pp. 1117–1124, December 2019.
  * Golub & Jackson (2010) Golub, B. and Jackson, M. O.  Naive learning in social networks and the wisdom of crowds.  _American Economic Journal: Microeconomics_ , 2(1):112–149, 2010.
  * Golub & Sadler (2016) Golub, B. and Sadler, E.  Learning in social networks.  _The Oxford Handbook of the Economics of Networks_ , 2016.
  * Haddadan et al. (2021) Haddadan, S., Menghini, C., Riondato, M., and Upfal, E.  RePBubLik: Reducing polarized bubble radius with link insertions.  In _Proceedings of the 14th ACM International Conference on Web Search and Data Mining_ , WSDM ’21, pp. 139–147, 2021.
  * Haddadan et al. (2022) Haddadan, S., Menghini, C., Riondato, M., and Upfal, E.  Reducing polarization and increasing diverse navigability in graphs by inserting edges and swapping edge weights.  _Data Mining and Knowledge Discovery_ , 36(6):2334–2378, 2022.
  * Hązła et al. (2023) Hązła, J., Jin, Y., Mossel, E., and Ramnarayan, G.  A geometric model of opinion polarization.  _Mathematics of Operations Research_ , 49(1):251–277, 2023.
  * He et al. (2018) He, L., Bian, A., and Jaggi, M.  COLA: Decentralized linear learning.  In _Proceedings of the 32nd International Conference on Neural Information Processing Systems_ , NIPS’18, pp. 4541–4551, 2018.
  * Hegedűs et al. (2016) Hegedűs, I., Berta, Á., Kocsis, L., Benczúr, A. A., and Jelasity, M.  Robust decentralized low-rank matrix decomposition.  _ACM Trans. Intell. Syst. Technol._ , 7(4):1–24, May 2016.
  * Hegedűs et al. (2019) Hegedűs, I., Danner, G., and Jelasity, M.  Gossip learning as a decentralized alternative to federated learning.  In _Distributed Applications and Interoperable Systems_ , pp. 74–90. Springer International Publishing, 2019.
  * Hegedűs et al. (2021) Hegedűs, I., Danner, G., and Jelasity, M.  Decentralized learning works: An empirical comparison of gossip learning and federated learning.  _J. Parallel Distrib. Comput._ , 148:109–124, February 2021.
  * Hązła et al. (2019) Hązła, J., Jadbabaie, A., Mossel, E., and Rahimian, M. A.  Reasoning in Bayesian opinion exchange networks is $\mathsf{PSPACE}$-hard.  In Beygelzimer, A. and Hsu, D. (eds.), _Proceedings of the Thirty-Second Conference on Learning Theory_ , volume 99 of _Proceedings of Machine Learning Research_ , pp. 1614–1648. PMLR, 25–28 Jun 2019.
  * Kempe et al. (2003) Kempe, D., Kleinberg, J., and Tardos, E.  Maximizing the spread of influence through a social network.  In _Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , KDD ’03, pp. 137–146, 2003.
  * Konečný et al. (2015) Konečný, J., McMahan, B., and Ramage, D.  Federated optimization: Distributed optimization beyond the datacenter.  arXiv 1511.03575, November 2015.
  * Konečný et al. (2016a) Konečný, J., Brendan McMahan, H., Ramage, D., and Richtárik, P.  Federated optimization: Distributed machine learning for on-device intelligence.  arXiv 1610.02527, October 2016a.
  * Konečný et al. (2016b) Konečný, J., Brendan McMahan, H., Yu, F. X., Richtárik, P., Suresh, A. T., and Bacon, D.  Federated learning: Strategies for improving communication efficiency.  arXiv 1610.05492, October 2016b.
  * Krishnan et al. (2024) Krishnan, S., Jose Anand, A., Srinivasan, R., Kavitha, R., and Suresh, S.  _Handbook on Federated Learning: Advances, Applications and Opportunities_.  CRC Press, January 2024.
  * Lazarsfeld & Alistarh (2023) Lazarsfeld, J. and Alistarh, D.  The power of populations in decentralized learning dynamics.  arXiv 2306.08670, June 2023.
  * Leskovec et al. (2010) Leskovec, J., Huttenlocher, D., and Kleinberg, J.  Signed networks in social media.  In _Proceedings of the SIGCHI Conference on Human Factors in Computing Systems_ , pp. 1361–1370. ACM, 2010.
  * McMahan et al. (2017) McMahan, B., Moore, E., Ramage, D., Hampson, S., and Arcas, B. A. y.  Communication-Efficient Learning of Deep Networks from Decentralized Data.  In Singh, A. and Zhu, J. (eds.), _Proceedings of the 20th International Conference on Artificial Intelligence and Statistics_ , volume 54 of _Proceedings of Machine Learning Research_ , pp. 1273–1282. PMLR, 2017.
  * Musco et al. (2018) Musco, C., Musco, C., and Tsourakakis, C. E.  Minimizing polarization and disagreement in social networks.  In _Proceedings of the 2018 World Wide Web Conference_ , pp. 369–378, 2018.
  * Nemhauser & Wolsey (1978) Nemhauser, G. L. and Wolsey, L. A.  Best algorithms for approximating the maximum of a submodular set function.  _Mathematics of Operations Research_ , 3(3):177–188, 1978.
  * Ormándi et al. (2013) Ormándi, R., Hegedűs, I., and Jelasity, M.  Gossip learning with linear models on fully distributed data.  _Concurr. Comput._ , 25(4):556–571, February 2013.
  * Rahimian & Jadbabaie (2017) Rahimian, M. A. and Jadbabaie, A.  Bayesian learning without recall.  _IEEE Transactions on Signal and Information Processing over Networks_ , 3(3):592–606, 2017.
  * Rossi & Ahmed (2015) Rossi, R. A. and Ahmed, N. K.  The network data repository with interactive graph analytics and visualization.  In _Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence_ , pp. 4292–4293, 2015.
  * Rozemberczki et al. (2019) Rozemberczki, B., Davies, R., Sarkar, R., and Sutton, C.  GEMSEC: Graph embedding with self clustering.  In _Proceedings of the 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining_ , pp. 65–72. ACM, 2019.
  * Santos et al. (2021) Santos, F. P., Lelkes, Y., and Levin, S. A.  Link recommendation algorithms and dynamics of polarization in online social networks.  _Proceedings of the National Academy of Sciences_ , 118(50):e2102141118, 2021.
  * Seeman & Singer (2013) Seeman, L. and Singer, Y.  Adaptive seeding in social networks.  In _2013 IEEE 54th Annual Symposium on Foundations of Computer Science_ , pp. 459–468, 2013.
  * Tsioutsiouliklis et al. (2022) Tsioutsiouliklis, S., Pitoura, E., Semertzidis, K., and Tsaparas, P.  Link recommendations for PageRank fairness.  In _Proceedings of the ACM Web Conference 2022_ , pp. 3541–3551, 2022.
  * Watts & Strogatz (1998) Watts, D. J. and Strogatz, S. H.  Collective dynamics of ‘small-world’ networks.  _Nature_ , 393(6684):440–442, 1998.
  * Zhang et al. (2023) Zhang, R., Guo, S., Wang, J., Xie, X., and Tao, D.  A survey on gradient inversion: Attacks, defenses and future directions.  In _Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence_ , pp. 5678–5685, July 2023.
  * Zhu et al. (2021) Zhu, L., Bao, Q., and Zhang, Z.  Minimizing polarization and disagreement in social networks via link recommendation.  _Advances in Neural Information Processing Systems_ , 34:2072–2084, 2021.

##  Appendix A Additional material: proofs and details of algorithms

Let $\Omega^{+}=\\{a\in\Omega\mid y(a)=+1\\}$ and
$\Omega^{-}=\\{a\in\Omega\mid y(a)=-1\\}$. The following are some useful
lemmas that we will use throughout:

######  Lemma A.1.

Let $v_{j}\in V$ be an arbitrary agent. We have:

$\operatorname*{\mathbb{E}}_{a\sim\Omega^{+}}\left[\hat{y}_{i}(a)\right]=1-2\mathsf{err}(v_{i}),\quad\operatorname*{\mathbb{E}}_{a\sim\Omega^{-}}\left[\hat{y}_{i}(a)\right]=2\mathsf{err}(v_{i})-1~{}.$

###### Proof.

$\displaystyle\operatorname*{\mathbb{E}}_{a\sim\Omega^{+}}\left[\hat{y}_{i}(a)\right]$
$\displaystyle=+1\cdot\mathbb{P}\left(\hat{y}_{i}(a)=+1\right)-1\cdot\mathbb{P}\left(\hat{y}_{i}(a)=-1\right)$
$\displaystyle=+1\cdot\mathbb{P}(\hat{y}_{i}(a)=y(a))-1\cdot\mathbb{P}(\hat{y}_{i}(a)\neq
y(a))$ $\displaystyle=\left(1-\mathsf{err}(v_{i})\right)-\mathsf{err}(v_{i})$
$\displaystyle=1-2\mathsf{err}(v_{i})~{}.$

Similarly we have that

$\displaystyle\operatorname*{\mathbb{E}}_{a\sim\Omega^{-}}\left[\hat{y}_{i}(a)\right]$
$\displaystyle=+1\cdot\mathbb{P}\left(\hat{y}_{i}(a)\neq
y(a)\right)-1\cdot\mathbb{P}\left(\hat{y}_{i}(a)=y(a)\right)=\mathsf{err}(v_{i})-\left(1-\mathsf{err}(v_{i})\right)=2\mathsf{err}(v_{i})-1~{}.$

∎

######  Proposition A.2.

Given any non-negative $\bar{W}$ used in equation (2) and $S$ on which we
improve $\hat{y}_{j}$ to $\tilde{y}_{j}$, we have

$\forall v_{i}\in V,\ \mathcal{\mathcal{Z}}_{\rm
new}(i,a)>\mathcal{Z}(i,a)\iff\exists v_{j}\in
S,y(a)\hat{y}_{j}(a)=-1\wedge\bar{W}_{ij}>0~{}.$

###### Proof.

By looking at eq. 4, it is evident that if $\hat{y}_{j}(a)=y(a)$ then
$\tilde{y}_{j}(a)=\hat{y}_{j}(a)$. Thus, improving $v_{j}$ will only improve
prediction on $a\in\Omega$ iff $\hat{y}_{j}(a)\neq y(a)$ or equivalently
$\hat{y}_{j}(a)y(a)=-1$. Note that for any other $v_{i}\in V$,
$\tilde{y}_{j}(a)$ appears in $\mathcal{\mathcal{Z}}_{\rm new}(i,a)$ with
coefficient $\bar{W}_{ij}$. Since the matrix is non-negative we either have
$\mathcal{\mathcal{Z}}_{\rm new}(i,a)=\mathcal{Z}(i,a)$ or
$\mathcal{\mathcal{Z}}_{\rm new}(i,a)>\mathcal{Z}(i,a)$. Therefore, we will
have $\mathcal{\mathcal{Z}}_{\rm new}(i,a)>\mathcal{Z}(i,a)$ iff
$\hat{y}_{j}(a)y(a)=-1$ and $\bar{W}_{ij}\neq 0$. ∎

###  A.1 Missing proofs from section 4.1: Analysis of aggregate optimization

###### Proof of lemma 4.1.

Let $\Omega^{+}=\\{a\in\Omega\mid y(a)=+1\\}$ and
$\Omega^{-}=\\{a\in\Omega\mid y(a)=-1\\}$. We have that:

$\displaystyle\mathcal{G}^{({\rm agg})}(S)=$
$\displaystyle\operatorname*{\mathbb{E}}_{a\sim\Omega}\left[\sum_{i=1}^{n}\mathcal{\mathcal{Z}}_{\rm
new}(i,a)-\mathcal{Z}(i,a)\right]$ $\displaystyle=$
$\displaystyle\operatorname*{\mathbb{E}}_{a\sim\Omega^{+}}\left[\sum_{i=1}^{n}z_{\rm
new}^{*}(i,a)-z^{*}(i,a)\right]\mathbb{P}(a\in\Omega^{+})+\operatorname*{\mathbb{E}}_{a\sim\Omega^{-}}\left[\sum_{i=1}^{n}z^{*}(i,a)-z_{\rm
new}^{*}(i,a)\right]\mathbb{P}(a\in\Omega^{-})$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{n}\left(\operatorname*{\mathbb{E}}_{a\sim\Omega^{+}}\left[z_{\rm
new}^{*}(i,a)-z^{*}(i,a)\right]\mathbb{P}(a\in\Omega^{+})+\operatorname*{\mathbb{E}}_{a\sim\Omega^{-}}\left[z^{*}(i,a)-z_{\rm
new}^{*}(i,a)\right]\mathbb{P}(a\in\Omega^{-})\right)~{}.$ (8)

Note that:

$z^{*}(i,a)-z_{\rm
new}^{*}(i,a)=\sum_{j=1}^{n}\bar{W}_{ij}(\hat{y}_{j}(a)-\tilde{y}_{j}(a))=\sum_{j\in
S}\bar{W}_{ij}(\hat{y}_{j}(a)-\tilde{y}_{j}(a))=\varphi\sum_{j\in
S}\bar{W}_{ij}[\hat{y}_{j}(a)-y(a)]$

Thus,

$z^{*}(i,a)-z_{\rm new}^{*}(i,a)=\begin{cases}\varphi\sum_{j\in
S}\bar{W}_{ij}[\hat{y}_{j}(a)+1]&\text{if }a\in\Omega^{-}\\\ \varphi\sum_{j\in
S}\bar{W}_{ij}[\hat{y}_{j}(a)-1]&\text{if }a\in\Omega^{+}\end{cases}$

Using linearity of expectation and plugging in lemma A.1 we have:

$\operatorname*{\mathbb{E}}\left[z^{*}(i,a)-z_{\rm
new}^{*}(i,a)\right]=\begin{cases}\varphi\sum_{j\in
S}\bar{W}_{ij}[2\mathsf{err}^{(0)}(v_{i})-1+1]&\text{if }a\in\Omega^{-}\\\
\varphi\sum_{j\in S}\bar{W}_{ij}[1-2\mathsf{err}^{(0)}(v_{i})-1]&\text{if
}a\in\Omega^{+}\end{cases}$

Therefore,

$\operatorname*{\mathbb{E}}_{a\sim\Omega^{-}}\left[z^{*}(i,a)-z_{\rm
new}^{*}(i,a)\right]=2\varphi\ \mathsf{err}^{(0)}(v_{i})\sum_{j\in
S}\bar{W}_{ij}=\operatorname*{\mathbb{E}}_{a\sim\Omega^{+}}\left[z_{\rm
new}^{*}(i,a)-z^{*}(i,a)\right]~{}.$

Plugging in the above in section A.1 we obtain:

$\mathcal{G}^{({\rm agg})}(S)=2\varphi\sum_{j\in
S}\sum_{i=1}^{n}\bar{W}_{ij}\mathsf{err}^{(0)}(v_{i})[\mathbb{P}(a\in\Omega^{+})+\mathbb{P}(a\in\Omega^{-})]=2\varphi\sum_{j\in
S}\sum_{i=1}^{n}\bar{W}_{ij}\mathsf{err}^{(0)}(v_{i})~{}.$

This means by picking $k$ vertices with highest values of ${\rm
Inf}(j)=\sum_{i=1}^{n}\bar{W}_{ij}\mathsf{err}^{(0)}(v_{i})$ we will obtain
the optimal solution for 1. In order to find these values, we first need to
find all the values of ${\rm Inf}(j)$ for all $j\in V$. Which takes
$\Theta(n^{2})$ number of steps. Then we have to find top $k$ elements among
these values, which will take $\Theta(kn)$. ∎

###### Proof of remark 3.6.

Let $\widehat{\rm
Inf}(j)=\sum_{i=1}^{n}\widehat{\bar{W}}_{i,j}\mathsf{err}^{(0)}(v_{j})$. For
all $j$, we have that

$\left|{\rm Inf}(j)-\widehat{\rm
Inf}(j)\right|=\sum_{i=1}^{n}\left|\bar{W}_{ij}-\widehat{\bar{W}}_{ij}\right|\mathsf{err}^{(0)}(v_{j})\leq\sum_{i=1}^{n}\
\left|\bar{W}_{ij}-\widehat{\bar{W}}_{ij}\right|$

Note that the right-hand side is the $\ell_{1}$ norm of the $j$th column of
$\bar{W}-\widehat{\bar{W}}$, let’s denote the $j$th column of these matrix
respectively by $\bar{W}_{\cdot j}$ and $\widehat{\bar{W}}_{\cdot j}$. Since
the $\ell_{1}$ norm of a matrix is defined the be the maximum over $\ell_{1}$
norm of all of its columns we have that

$\forall j\ \left|{\rm Inf}(j)-\widehat{\rm
Inf}(j)\right|\leq\left|\bar{W}_{\cdot j}-\widehat{\bar{W}}_{\cdot
j}\right|_{1}\leq\epsilon~{}.$

In the previous theorem we showed that

$\mathcal{G}^{({\rm agg})}(S)=2\varphi\sum_{j\in S}{\rm Inf}(j)~{}.$

Since size of $S$ is $k$ and $\varphi\leq 1$ the total error is bounded by
$2k\epsilon$ . ∎

###  A.2 Missing proof from section 4.2: Analysis of egalitarian optimization

####  A.2.1 Hardness Results

######  Theorem A.3.

There is a polynomial time reduction from the set cover problem to 1.

###### Proof.

Consider an arbitrary $S\subseteq V$. We use proposition A.2 to simplify
$\mathcal{G}^{({\rm egal})}(S)$. For any $v_{i}\in V$, we define:
$\Omega_{v_{j}}\triangleq\\{a\in\Omega\mid y(a)\hat{y}_{j}(a)=-1\\}$. For any
$a\in\Omega$, we denote its probability by $\mu_{a}$. For a given $S$ we have:

$\displaystyle\mathcal{G}^{({\rm egal})}(S)$
$\displaystyle=\operatorname*{\mathbb{E}}_{a\sim\Omega}\left[\sum_{i=1}^{n}\mathbf{1}(\mathcal{Z}(i,a)<0\wedge\mathcal{Z}(i,a)<\mathcal{\mathcal{Z}}_{\rm
new}(i,a))\right]$
$\displaystyle=\sum_{a\in\Omega}\sum_{i=1}^{n}\mu_{a}\mathbf{1}(\mathcal{Z}(i,a)<0)\cdot\mathbf{1}\left(\bigvee_{v_{j}\in
S}\left(a\in\Omega_{v_{j}}\wedge\bar{W}_{ij}>0\right)\right)$
$\displaystyle=\sum_{(a,v_{i})\in\Omega\times
V}\mu_{a}\mathbf{1}(\mathcal{Z}(i,a)<0)\cdot\mathbf{1}\left(\bigvee_{v_{j}\in
S}\left(a\in\Omega_{v_{j}}\wedge\bar{W}_{ij}>0\right)\right)$ (9)

Using the above simplification, we now construct the following instance of the
weighted set cover problem:

Consider a bipartite graph where one part is $U=\\{(v_{i},a)\in
V\times\Omega\mid\mathcal{Z}(i,a)<0\\}$ and the other part is $S=V$. There is
an edge between any $v_{j}\in V$ to a pair $(v_{i},a)\in U$ iff
$a\in\Omega_{v_{j}}\wedge\bar{W}_{ij}>0$ and the weight of each pair
$(a,v_{i})$ is $\mu_{a}$. Under the new definition section A.2.1 is equivalent
to

$\mathcal{G}^{({\rm egal})}(S)=\sum_{(a,v_{i})\in
U}\mu_{a}\cdot\mathbf{1}\left(\bigvee_{v_{j}\in
S}\left(a\in\Omega_{v_{j}}\wedge\bar{W}_{ij}>0\right)\right)$

Note that

$\mathbf{1}\left(\bigvee_{v_{j}\in
S}\left(a\in\Omega_{v_{j}}\wedge\bar{W}_{ij}>0\right)\right)=1\iff\text{there
is an edge between $v_{j}$ and $(a,v_{i})$ and $v_{j}\in S$}~{}.$

The reduction is polynomial in sizes of $\Omega$ and $V$. Since we assume that
$\Omega$ has polynomial size, it is a polynomial time reduction. This
completes the proof. ∎

###### Proof of theorem 3.7.

The proof follows from theorem A.3 and the fact that set cover is NP-hard. ∎

######  Theorem A.4.

Consider 2 and assume $k=1$. There exist two networks with the same number of
agents, same $\bar{W}$ and same error rates
$\\{\mathsf{err}(v_{j})\\}_{j=1}^{n}$. In these network, only the joint
probability distributions $\pi_{1}$ and $\pi_{2}$ are different. There are
subsets $V_{1},V_{2}\subseteq V$ such that $V_{1}\cap V_{2}=\emptyset$. In the
first network we have that for any $u\in V_{1},\mathcal{G}^{({\rm
egal})}(u)=\Theta(n)$ and for any $u\notin V_{1}$ we have $\mathcal{G}^{({\rm
egal})}(u)=\Theta(1)$. In the second network for any $u\in V_{2}$ will have
$\mathcal{G}^{({\rm egal})}(u)=\Theta(n)$ and any $u\notin V_{2}$ will satisfy
$\mathcal{G}^{({\rm egal})}(u)=\Theta(1)$.

###### Proof.

Let $V=\\{u_{1},u_{2},u_{3},u_{4}\\}\cup\\{v_{1},v_{2},v_{3},\dots,v_{2n}\\}$.
We define $\bar{W}$ to be the following matrix:

$\bar{W}_{u_{1},v_{j}}=\bar{W}_{u_{2},v_{j}}=1$ for all $j=1:n$ , and
$\bar{W}_{u_{3},v_{j}}=\bar{W}_{u_{4},v_{j}}=1$ for all $j=n+1:2n$.

For each vertex in $V$ we also have a self loop of weight $1$, i.e.,
$\bar{W}_{u_{i}u_{i}}=\bar{W}_{v_{j}v_{j}}=1$ for all $i,j$.

The error rates of these agents are as follows: $\mathsf{err}(v_{j})=0$ for
all $j=1:2n$ and $\mathsf{err}(u_{i})=1/2$ for all $j=1:4$.

In the first network the error of $\hat{y}_{u_{1}}(a)$ is negatively
correlated with $\hat{y}_{u_{2}}(a)$ and $\hat{y}_{u_{3}}$ is positively
correlated with $\hat{y}_{u_{4}}$ as:

$\operatorname*{\mathbb{P}}\left(\hat{y}_{u_{1}}(a)\neq\hat{y}_{u_{2}}(a)\right)=1\quad\&\
\operatorname*{\mathbb{P}}\left(\hat{y}_{u_{3}}(a)=\hat{y}_{u_{4}}(a)\right)=1$

Both $\hat{y}_{u_{1}}$ and $\hat{y}_{u_{2}}$ are independent from
$\hat{y}_{u_{3}}$ and $\hat{y}_{u_{4}}$.

Let $V_{1}=\\{u_{3},u_{4}\\}$. We now show that $\mathcal{G}^{({\rm
egal})}(u_{3})=\mathcal{G}^{({\rm egal})}(u_{4})=n$ and for any $u\notin
V_{1}$, $\mathcal{G}^{({\rm egal})}(u)\in\\{0,1\\}$.

From lemma 4.2 we conclude that for any vertex $u$ we have:

$\mathcal{G}^{({\rm egal})}(u)=\sum_{i;\bar{W}_{iu}\neq
0}\operatorname*{\mathbb{P}}_{a\sim\Omega}\left(\mathcal{Z}(i,a)\leq 0\wedge
y(a)\neq\hat{y}_{u}(a)\right)$

Thus, it is immediate that for each $v_{j}$, we have $\mathcal{G}^{({\rm
egal})}(v_{j})=0$.

Consider $u_{1}$

$\displaystyle\mathcal{G}^{({\rm egal})}(u_{1})$
$\displaystyle=\sum_{i=1:n}\operatorname*{\mathbb{P}}_{a\sim\Omega}\left(\mathcal{Z}(i,a)\leq
0\wedge
y(a)\neq\hat{y}_{u_{1}}(a)\right)+\operatorname*{\mathbb{P}}_{a\sim\Omega}\left(\mathcal{Z}(u_{1},a)\leq
0\wedge y(a)\neq\hat{y}_{u_{1}}(a)\right)$

Since $u_{1}$ is connected to $v_{1},\dots v_{n}$, the last summand is $0$ if
$n>1$, and it is $1/2$ if $n=1$. In any case it is a constant. We now look at
the first summand.

$\displaystyle first\ summand$
$\displaystyle=\sum_{i=1:n}\operatorname*{\mathbb{P}}_{a\sim\Omega}\left((\hat{y}_{u_{1}}(a)+\hat{y}_{u_{2}}(a)+\hat{y}_{i}(a))\cdot
y(a)\leq 0\wedge y(a)\neq\hat{y}_{u}(a)\right)$
$\displaystyle=\sum_{i=1:n}\operatorname*{\mathbb{P}}_{a\sim\Omega}\left(y(a)^{2}\leq
0\wedge y(a)\neq\hat{y}_{u}(a)\right)=0$

The last equation follows from the fact that always
$\hat{y}_{u_{1}}(a)\neq\hat{y}_{u_{2}}(a)$, and $\hat{y}_{i}(a)=y(a)$.

Similarly we can show that $\mathcal{G}^{({\rm egal})}(u_{2})=\\{0,1/2\\}$.

For $u_{3}$, let $c$ be a constant which is $c\in\\{0,1/2\\}$. We have:

$\displaystyle\mathcal{G}^{({\rm egal})}(u_{3})$
$\displaystyle=\sum_{i=n+1:2n}\operatorname*{\mathbb{P}}_{a\sim\Omega}\left(\mathcal{Z}(i,a)\leq
0\wedge
y(a)\neq\hat{y}_{u_{3}}(a)\right)+\operatorname*{\mathbb{P}}_{a\sim\Omega}\left(\mathcal{Z}(u_{3},a)\leq
0\wedge y(a)\neq\hat{y}_{u_{3}}(a)\right)$
$\displaystyle=\sum_{i=1:n}\operatorname*{\mathbb{P}}_{a\sim\Omega}\left((\hat{y}_{u_{3}}(a)+\hat{y}_{u_{4}}(a)+\hat{y}_{i}(a))\cdot
y(a)\leq 0\wedge y(a)\neq\hat{y}_{u}(a)\right)+c$
$\displaystyle=\sum_{i=1:n}\operatorname*{\mathbb{P}}_{a\sim\Omega}\left((y(a)-2y(a))\cdot
y(a)\leq 0\right)\mathsf{err}(u_{3})+c$ $\displaystyle=n/2+c~{}.$

Similarly we have $\mathcal{G}^{({\rm egal})}(u_{4})\in\\{n/2,(n+1)/2\\}$.

Therefore, both $u_{3}$ and $u_{4}$ can be the optimal choice for this
network. And any other choice will have an error of magnitude $\Theta(n)$.

In the second network, we make the following change:

$\operatorname*{\mathbb{P}}\left(\hat{y}_{u_{1}}(a)=\hat{y}_{u_{2}}(a)\right)=1\quad\&\
\operatorname*{\mathbb{P}}\left(\hat{y}_{u_{3}}(a)\neq\hat{y}_{u_{4}}(a)\right)=1$

We still let both $\hat{y}_{u_{1}}$ and $\hat{y}_{u_{2}}$ are independent from
$\hat{y}_{u_{3}}$ and $\hat{y}_{u_{4}}$.

Using a similar analysis we can show that

$\mathcal{G}^{({\rm egal})}(u_{1})=\mathcal{G}^{({\rm egal})}(u_{2})=n/2+1\
\&\ \forall u\in V,\ u\neq u_{1},u_{2}\implies\mathcal{G}^{({\rm
egal})}(u)\in\\{0,1/2\\}~{}.$

∎

####  A.2.2 Monotonicity and submodularity of $\mathcal{G}^{({\rm egal})}$

######  Lemma A.5.

Assume $S^{\prime}\subseteq S\subseteq V$, we have: $\mathcal{G}^{({\rm
egal})}(S^{\prime})\leq\mathcal{G}^{({\rm egal})}(S)$ .

###### Proof.

From proposition A.2 that for any arbitrary $S\subseteq V$ we have:

$\mathcal{G}^{({\rm
egal})}(S)=\sum_{i=1}^{n}\operatorname*{\mathbb{P}}\left(y(a)z^{*}(i,a)\leq
0\wedge\bigvee_{\begin{subarray}{c}v_{j}\in S\\\ \bar{W}_{ij}\neq
0\end{subarray}}(y(a)\neq\hat{y}_{j}(a))\right)$

For $S^{\prime}\subseteq S$, we split the event
$\bigvee_{\begin{subarray}{c}v_{j}\in S\\\ \bar{W}_{ij}\neq
0\end{subarray}}(y(a)\neq\hat{y}_{j}(a))$ to the two following non-
intersecting events:

$\bigvee_{\begin{subarray}{c}v_{j}\in S\\\ \bar{W}_{ij}\neq
0\end{subarray}}(y(a)\neq\hat{y}_{j}(a))=\underbrace{\left(\bigvee_{\begin{subarray}{c}v_{j}\in
S^{\prime}\\\ \bar{W}_{ij}\neq
0\end{subarray}}(y(a)\neq\hat{y}_{j}(a))\right)}_{E_{i1}}\vee\underbrace{\left(\bigvee_{\begin{subarray}{c}v_{j}\in
S\setminus S^{\prime}\\\ \bar{W}_{ij}\neq
0\end{subarray}}(y(a)\neq\hat{y}_{j}(a))\wedge\bigwedge_{\begin{subarray}{c}v_{j}\in
S^{\prime}\\\ \bar{W}_{ij}\neq
0\end{subarray}}(y(a)=\hat{y}_{j}(a))\right)}_{E_{i2}}$

Since $E_{1}$ and $E_{2}$ are non-intersecting we have:

$\mathcal{G}^{({\rm egal})}(S)=\sum_{i=1}^{n}\mathbb{P}(y(a)z^{*}(i,a)<0\wedge
E_{i1})+\sum_{i=1}^{n}\mathbb{P}(y(a)z^{*}(i,a)<0\wedge E_{i2})~{}.$

Note that $\mathcal{G}^{({\rm
egal})}(S^{\prime})=\sum_{i=1}^{n}\mathbb{P}(y(a)z^{*}(i,a)<0\wedge E_{i1})$.
Therefore, we conclude the premise. ∎

######  Lemma A.6.

Consider arbitrary $S\subseteq V$ and $u,v\in{V}\setminus S$. We have:

$\mathcal{G}^{({\rm egal})}(S\cup\\{u,v\\})+\mathcal{G}^{({\rm
egal})}(S)\leq\mathcal{G}^{({\rm egal})}(S\cup\\{u\\})+\mathcal{G}^{({\rm
egal})}(S\cup\\{v\\})~{}.$

###### Proof.

Like previous lemma, we split the events of RHS and LHS to non-intersecting
smaller events.

Consider the following events:

$\displaystyle E_{FFF}(i)\equiv\left(\bigvee_{\begin{subarray}{c}v_{j}\in S\\\
\bar{W}_{ij}\neq 0\end{subarray}}\hat{y}_{i}(a)\neq
y(a)\right)\wedge\left(\hat{y}_{u}(a)\neq\hat{y}(a)\wedge\bar{W}_{iu}\neq
0\right)\wedge\left(\hat{y}_{v}(a)\neq y(a)\wedge\bar{W}_{iv}\neq 0\right)$
$\displaystyle E_{TFF}(i)\equiv\left(\neg\bigvee_{\begin{subarray}{c}v_{j}\in
S\\\ \bar{W}_{ij}\neq 0\end{subarray}}\hat{y}_{i}(a)\neq
y(a)\right)\wedge(\hat{y}_{u}(a)\neq\hat{y}(a)\wedge\bar{W}_{iu}\neq
0)\wedge\left(\hat{y}_{v}(a)\neq y(a)\wedge\bar{W}_{iv}\neq 0\right)$
$\displaystyle E_{TTF}(i)\equiv\left(\neg\bigvee_{\begin{subarray}{c}v_{j}\in
S\\\ \bar{W}_{ij}\neq 0\end{subarray}}\hat{y}_{i}(a)\neq
y(a)\right)\wedge\neg\left(\hat{y}_{u}(a)\neq\hat{y}(a)\wedge\bar{W}_{iu}\neq
0\right)\wedge\left(\hat{y}_{v}(a)\neq y(a)\wedge\bar{W}_{iv}\neq 0\right)$
$\displaystyle E_{TFT}(i)\equiv\left(\neg\bigvee_{\begin{subarray}{c}v_{j}\in
S\\\ \bar{W}_{ij}\neq 0\end{subarray}}\hat{y}_{i}(a)\neq
y(a)\right)\wedge\left(\hat{y}_{u}(a)\neq\hat{y}(a)\wedge\bar{W}_{iu}\neq
0\right)\wedge\neg\left(\hat{y}_{v}(a)\neq y(a)\wedge\bar{W}_{iv}\neq
0\right)$

and similar definitions for $E_{TTT}(i)$, $E_{FTT}(i)$, $E_{FTF}(i)$ and
$E_{FFT}(i)$.

$\mathcal{G}^{({\rm
egal})}(S\cup\\{u,v\\})=\sum_{i=1}^{n}\sum_{(X,Y,Z)\in\\{T,F\\}^{3}\setminus\\{(F,F,F)\\}}\operatorname*{\mathbb{P}}\left(y(a)z^{*}(i,a)\leq
0\wedge E_{X,Y,Z}(i)\right),$

$\mathcal{G}^{({\rm
egal})}(S)=\sum_{i=1}^{n}\sum_{(Y,Z)\in\\{T,F\\}^{2}}\operatorname*{\mathbb{P}}\left(y(a)z^{*}(i,a)\leq
0\wedge E_{T,Y,Z}(i)\right),$

$\mathcal{G}^{({\rm
egal})}(S\cup\\{u\\})=\sum_{i=1}^{n}\sum_{(X,Y,Z)\in\\{T,F\\}^{3}\setminus\\{(F,F,F),(F,F,T)\\}}\operatorname*{\mathbb{P}}\left(y(a)z^{*}(i,a)\leq
0\wedge E_{X,Y,Z}(i)\right)$

and finally

$\mathcal{G}^{({\rm
egal})}(S\cup\\{v\\})=\sum_{i=1}^{n}\sum_{(X,Y,Z)\in\\{T,F\\}^{3}\setminus\\{(F,F,F),(F,T,F)\\}}\operatorname*{\mathbb{P}}\left(y(a)z^{*}(i,a)\leq
0\wedge E_{X,Y,Z}(i)\right)$

By counting the number of appearances of each term on the RHS and LHS we may
conclude the premise. ∎

###  A.3 Pseudocode of the greedy algorithms

In this section we present our algorithms for egalitarian improvement.

##### Overview of algorithms

The first algorithm $\mathsf{EgalAlg}$ has access to $\pi$ and finds the
greedy choice accurately.

The second algorithm $\mathsf{EgalAlg}^{(\rm appx)}$ receives parameters
$mode$, $\vec{\boldsymbol{\mathsf{err}}}$ and $\bar{W}$ as input parameters.
If we assume pairwise independence of classifiers, $mode=\rm ind$ and
$\vec{\boldsymbol{\mathsf{err}}}$ contains agents’ error rates. If we assume
group dependency $mode=\rm gr$ and $\vec{\boldsymbol{\mathsf{err}}}$ contains
the agent’s individual error rates as well as $\mathsf{err}({\mathcal{R}})$
and $\mathsf{err}({\mathcal{B}})$. Depending on the mode of the algorithm,
$\mathsf{EgalAlg}^{(\rm appx)}$calls subsequent procedures
$\mathsf{EstGain}^{\rm ind}$ and $\mathsf{EstGain}^{\rm gr}$ for estimating
the greedy choice.

The pseudocodes are as follows and analysis is presented in subsequent
subsections:

$S=\emptyset$

for $i=1:k$ do

$maxval=0$

for $j=1:n$ do

$\Delta{\mathcal{G}}(S,v_{j})=0$

for $a\in\Omega$ do

for $\ell=1:n$ do

$E=\mathcal{Z}(i,a)\leq 0\wedge\left(\bigwedge_{\begin{subarray}{c}v_{j}\in
S\\\ \bar{W}_{ji}\neq 0\end{subarray}}y(a){=}\hat{y}_{j}(a)\right)\wedge
y(a){\neq}\hat{y}_{u}(a)$

if $E\equiv T$ and $\bar{W}_{\ell j}\neq 0$ then

$\Delta{\mathcal{G}}(S,v_{j})=\Delta{\mathcal{G}}(S,v_{j})+\pi(E)$

end if

end for

end for

if ${\Delta{\mathcal{G}}}(S,v_{j})\geq maxval$,

$g=v_{j}$

end for

$S=S\cup\\{g\\}$

end for

Algorithm 1 $\mathsf{EgalAlg}$$\left(\pi,\bar{W}\right)$ Algorithm 2
$\mathsf{EgalAlg}^{(\rm
appx)}$$\left(mode,\vec{\boldsymbol{\mathsf{err}}},\bar{W}\right)$

$S=\emptyset$

for $i=1:k$ do

$maxval=0$

for $j=1:n$ do

$\widehat{\Delta{\mathcal{G}}}^{\rm indv}(S,v_{j})=\mathsf{EstGain}^{\rm
ind}(S,v_{j},\\{\mathsf{err}(v_{i})\\}_{i=1}^{n},\bar{W})$ (algorithm 3)

$\widehat{\Delta{\mathcal{G}}}(S,v_{j})=\widehat{\Delta{\mathcal{G}}}^{\rm
indv}(S,v_{j})$

if mode = gr then

$\widehat{\Delta{\mathcal{G}}}^{\rm gr}(S,v_{j})=\mathsf{EstGain}^{\rm
gr}(S,v_{j},\\{\mathsf{err}(v_{i})\\}_{i=1}^{n},\mathsf{err}({\mathcal{R}}),\mathsf{err}({\mathcal{B}}),\bar{W})$
(algorithm 4)

$\widehat{\Delta{\mathcal{G}}}(S,v_{j})=\rho\widehat{\Delta{\mathcal{G}}}^{\rm
gr}(S,v_{j})+(1-\rho)\widehat{\Delta{\mathcal{G}}}^{\rm indv}(S,v_{j})$

end if

if $\widehat{\Delta{\mathcal{G}}}(S,v_{j})\geq maxval$,

$g=v_{j}$

end for

$S=S\cup\\{g\\}$

end for

Algorithm 3 $\mathsf{EstGain}^{\rm
ind}(S,u,\\{\mathsf{err}(v_{j})\\}_{j=1}^{n},\bar{W})$

$\widehat{\Delta{\mathcal{G}}}(S,u)=0$

for $\ell=1:n$ do

$\mathsf{tru}_{\ell}(S)=1$

for $v_{m}\in S$ do

if $\bar{W}_{\ell m}\neq 0$,

$\mathsf{tru}_{\ell}(S)=\mathsf{tru}_{\ell}(S)\times(1-\mathsf{err}(v_{m}))$

end for

if $\Psi_{\ell}(S,u)<0$ and $\bar{W}_{\ell u}\neq 0$

$\widehat{\Delta{\mathcal{G}}}(S,u)\ {+}{=}\
\mathsf{err}(u)\cdot\mathsf{tru}_{\ell}(S)$

end for

Algorithm 4 $\mathsf{EstGain}^{\rm
gr}(S,u,\\{\mathsf{err}(v_{j})\\}_{j=1}^{n},\mathsf{err}({\mathcal{R}}),\mathsf{err}({\mathcal{B}}),\bar{W})$

$\widehat{\Delta{\mathcal{G}}}(S,u)=0$

boolean $Case1=T$

boolean $Case2R=F$

boolean $Case2B=F$

boolean $Case3=F$

for $\ell=1:n$ do

$\mathsf{tru}_{\ell}(S)=1$

for $v_{m}\in S$ do

if $\bar{W}_{\ell m}\neq 0$ then

if $v_{m}\in{\mathcal{W}}$ then
$\mathsf{tru}_{\ell}(S)=\mathsf{tru}_{\ell}(S)\times(1-\mathsf{err}(v_{m}))$

if ($v_{m}\in{\mathcal{R}})\wedge Case1=T$ then

$Case1=F$

$Case2R=T$

end if

if ($v_{m}\in{\mathcal{B}})\wedge Case1=T$ then

$Case1=F$

$Case2B=T$

end if

if $(v_{m}\in{\mathcal{R}}\wedge Case2B=T)$ or $(v_{m}\in{\mathcal{B}}\wedge
Case2R=T)$ then

$Case2B=Case2R=F$

$Case3=T$

end if

end if

end for

if $Case1\wedge u\in{\mathcal{W}}$ then

$\Delta{\mathcal{G}}(S,u)+=\mathsf{tru}_{\ell}(S)\mathsf{err}(u)[\mathbf{1}(\Psi_{i}({\mathcal{B}}\cup
S),{\mathcal{R}}\cup\\{u\\})\mathsf{err}({\mathcal{R}})+\mathbf{1}({\mathcal{R}}\cup
S),{\mathcal{B}}\cup\\{u\\})\mathsf{err}({\mathcal{B}})]$

end if

if $Case1\wedge u\in{\mathcal{R}}$ then

$\Delta{\mathcal{G}}(S,u)+=\mathsf{tru}_{\ell}(S)\mathsf{err}(u)\mathbf{1}\Psi_{i}({\mathcal{R}}\cup
S,{\mathcal{B}}\cup\\{u\\})$

end if

if $Case1\wedge u\in{\mathcal{B}}$ then

$\Delta{\mathcal{G}}(S,u)+=\mathsf{tru}_{\ell}(S)\mathsf{err}(u)\mathbf{1}\Psi_{i}({\mathcal{B}}\cup
S,{\mathcal{R}}\cup\\{u\\})$

end if

if $Case2B\wedge u\in{\mathcal{W}}$ then

$\Delta{\mathcal{G}}(S,u)+=\mathsf{err}(u)\mathsf{err}({\mathcal{R}})\mathsf{tru}(S)\mathbf{1}\Psi({\mathcal{B}}\cup
S,{\mathcal{R}}\cup\\{u\\})$

end if

if $Case2R\wedge u\in{\mathcal{W}}$ then

$\Delta{\mathcal{G}}(S,u)+=\mathsf{err}(u)\mathsf{err}({\mathcal{B}})\mathsf{tru}(S)\mathbf{1}\Psi({\mathcal{R}}\cup
S,{\mathcal{B}}\cup\\{u\\})$

end if

if $Case2B\wedge u\in{\mathcal{R}}$ then

$\Delta{\mathcal{G}}(S,u)+=\mathsf{err}({\mathcal{R}})\mathsf{tru}(S)\mathbf{1}\Psi({\mathcal{B}}\cup
S,{\mathcal{R}})$

end if

if $Case2R\wedge u\in{\mathcal{B}}$ then

$\Delta{\mathcal{G}}(S,u)+=\mathsf{err}({\mathcal{B}})\mathsf{tru}(S)\mathbf{1}\Psi({\mathcal{R}}\cup
S,{\mathcal{B}})$

end if

end for

return $\Delta{\mathcal{G}}(S,u)$

####  A.3.1 Finding the greedy choice

Remember from the main text that

$\Delta{\mathcal{G}}_{i}(u,S)=\operatorname*{\mathbb{P}}_{a\sim\Omega}\left(\mathcal{Z}(i,a)\leq
0\wedge\left(\bigwedge_{\begin{subarray}{c}v_{j}\in S\\\ \bar{W}_{ji}\neq
0\end{subarray}}y(a){=}\hat{y}_{j}(a)\right)\wedge
y(a){\neq}\hat{y}_{u}(a)\right)~{}.$

###### Proof of Lemma 4.2.

It is immediate from proposition A.2 that for any arbitrary $S\subseteq V$ we
have:

$\mathcal{G}^{({\rm
egal})}(S)=\sum_{i=1}^{n}\operatorname*{\mathbb{P}}\left(y(a)z^{*}(i,a)\leq
0\wedge\bigvee_{v_{j}\in S}(\bar{W}_{ij}\neq 0\wedge
y(a)\neq\hat{y}_{j}(a))\right)$

Writing the above for $S\cup\\{u\\}$ and simplifying we obtain:

$\displaystyle\mathcal{G}^{({\rm egal})}(S\cup\\{u\\})=$
$\displaystyle\sum_{i=1}^{n}\operatorname*{\mathbb{P}}\left(y(a)z^{*}(i,a)\leq
0\wedge\bigvee_{v_{j}\in S\cup\\{u\\}}(\bar{W}_{ij}\neq 0\wedge
y(a)\neq\hat{y}_{j}(a))\right)$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{n}\operatorname*{\mathbb{P}}\left(y(a)z^{*}(i,a)\leq
0\wedge\bigvee_{v_{j}\in S}(\bar{W}_{ij}\neq 0\wedge
y(a)\neq\hat{y}_{j}(a))\right)$
$\displaystyle~{}+\operatorname*{\mathbb{P}}\left(y(a)z^{*}(i,a)\leq
0\wedge\bigwedge_{v_{j}\in S}(\bar{W}_{ij}=0\vee
y(a)=\hat{y}_{j}(a))\wedge(\bar{W}_{iu}\neq 0\wedge
y(a)\neq\hat{y}_{u}(a))\right)$ $\displaystyle=$
$\displaystyle\mathcal{G}^{({\rm egal})}(S)+\sum_{\begin{subarray}{c}i=1:n\\\
\bar{W}_{iu}\neq
0\end{subarray}}\operatorname*{\mathbb{P}}\left(y(a)z^{*}(i,a)\leq
0\wedge\left(\bigwedge_{\begin{subarray}{c}v_{j}\in S\\\ \bar{W}_{ij}\neq
0\end{subarray}}y(a)=\hat{y}_{j}(a)\right)\wedge
y(a)\neq\hat{y}_{u}(a)\right)$ $\displaystyle=$
$\displaystyle\mathcal{G}^{({\rm egal})}(S)+\sum_{\begin{subarray}{c}i=1:n\\\
\bar{W}_{iu}\neq 0\end{subarray}}\Delta{\mathcal{G}}_{i}(S,u)$

∎

The following lemma is a middle step for approximation of the greedy choice:

######  Lemma A.7.

Let $\Delta{\mathcal{G}}_{i}(S,u)$ be

$\Delta{\mathcal{G}}_{i}(S,u)=\operatorname*{\mathbb{P}}_{a\sim\Omega}\left(\mathcal{Z}(i,a)\leq
0\wedge\left(\bigwedge_{\begin{subarray}{c}v_{j}\in S\\\ \bar{W}_{ij}\neq
0\end{subarray}}y(a)=\hat{y}_{j}(a)\right)\wedge
y(a)\neq\hat{y}_{u}(a)\right)$

We have that

$\Delta{\mathcal{G}}_{i}(S,u)=\mathbb{P}\left(T_{i}(S)\wedge
F(u)\right)\Gamma_{i}(S,u)~{},$

where

$\displaystyle\Gamma_{i}(S,u)=$
$\displaystyle\operatorname*{\mathbb{P}}\left(a\in\Omega^{+}\right)\operatorname*{\mathbb{P}}_{a\in\Omega^{+}}\left(\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}\hat{y}_{j}(a)<-\sum_{v_{j}\in
S}\bar{W}_{ji}+\bar{W}_{iu}\right)$
$\displaystyle+\operatorname*{\mathbb{P}}\left(a\in\Omega^{-}\right)\operatorname*{\mathbb{P}}_{a\in\Omega^{-}}\left(\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}\hat{y}_{j}(a)>\sum_{v_{j}\in
S}\bar{W}_{ji}-\bar{W}_{iu}\right)~{}.$

and $T_{i}(S)$ and $F(u)$ are the following events:

$T_{i}(S)\doteq\bigwedge_{\begin{subarray}{c}v_{j}\in S\\\ \bar{W}_{ij}\neq
0\end{subarray}}\hat{y}_{j}(a)=y(a),\quad\quad F(u)\doteq\hat{y}_{u}(a)\neq
y(a)$

###### Proof.

Let $E$ denote the event

$E\triangleq\left(\bigwedge_{\begin{subarray}{c}v_{j}\in S\\\ \bar{W}_{ji}\neq
0\end{subarray}}y(a)=\hat{y}_{j}(a)\right)\wedge y(a)\neq\hat{y}_{u}(a)~{}.$

We may write

$\operatorname*{\mathbb{P}}\left(y(a)z^{*}(i,a)\leq 0\wedge
E\right)=\operatorname*{\mathbb{P}}\left(y(a)z^{*}(i,a)\leq 0\mid
E\right)\operatorname*{\mathbb{P}}(E)$

In order find $\operatorname*{\mathbb{P}}\left(y(a)z^{*}(i,a)\leq 0\mid
E\right)$, we split the probability based on the true label of $a$:

If $a\in\Omega^{+}$ we have:

$\operatorname*{\mathbb{P}}\left(y(a)z^{*}(i,a)\leq 0\mid
E\right)=\operatorname*{\mathbb{P}}\left(z^{*}(i,a)\leq
0\mid\left(\bigwedge_{\begin{subarray}{c}v_{j}\in S\\\ \bar{W}_{ij}\neq
0\end{subarray}}\hat{y}_{j}(a)=+1\right)\wedge\hat{y}_{u}(a)=-1\right)$

Note that

$z^{*}(i,a)=\sum_{j=1}^{n}\bar{W}_{ij}\hat{y}_{j}(a)$

thus,

$\operatorname*{\mathbb{P}}\left(y(a)z^{*}(i,a)\leq 0\mid
E\right)=\operatorname*{\mathbb{P}}\left(\sum_{{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}}\bar{W}_{ij}\hat{y}_{j}(a)+\sum_{v_{j}\in
S}\bar{W}_{ij}-\bar{W}_{iu}\leq 0\right)$

Similarly, if $a\in\Omega^{-}$ we have:

$\operatorname*{\mathbb{P}}\left(y(a)z^{*}(i,a)\leq 0\mid
E\right)=\operatorname*{\mathbb{P}}\left(z^{*}(i,a)\geq
0\mid\left(\bigwedge_{\begin{subarray}{c}v_{j}\in S\\\ \bar{W}_{ij}\neq
0\end{subarray}}\hat{y}_{j}(a)=-1\right)\wedge\hat{y}_{u}(a)=+1\right)$

Since

$z^{*}(i,a)=\sum_{j=1}^{n}\bar{W}_{ij}\hat{y}_{j}(a)$

we have:

$\operatorname*{\mathbb{P}}\left(y(a)z^{*}(i,a)\geq 0\mid
E\right)=\operatorname*{\mathbb{P}}\left(\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}\hat{y}_{j}(a)-\sum_{v_{j}\in
S}\bar{W}_{ij}+\bar{W}_{iu}\geq 0\right)$

Rearranging and putting together, we obtain the premise.

∎

###  A.4 Missing material from section 4.2.1: estimating greedy choice
assuming independence

###### Proof of lemma 4.6.

Let

$\mathsf{tru}_{i}(S)=\mathbb{P}\left(\bigwedge_{\begin{subarray}{c}v_{j}\in
S\\\ \bar{W}_{ij}\neq 0\end{subarray}}\hat{y}_{j}(a)=y(a)\right)~{}.$

Using independence and from lemma A.7 we can write

$\Delta{\mathcal{G}}_{i}(S,u)=\mathsf{err}(u)\mathsf{tru}_{i}(S)\Gamma_{i}(S,u)$
(10)

In lemma A.8 which follows this proof, we show that by taking

$\widehat{\Gamma}_{i}(S,u)=\begin{cases}0&\text{ if }\Psi_{i}(S,u)\geq 0\\\
1&\text{ otherwise}\end{cases}$

we have

$\absolutevalue{\widehat{\Gamma}_{i}(S,u)-\Gamma_{i}(S,u)}\leq\exp\left(-\frac{\Psi_{i}(S,u)^{2}}{4\sum_{i=1}^{n}\bar{W}_{ij}^{2}}\right)~{}\leq\exp\left(-\frac{\Psi_{i}(u)^{2}}{4\sum_{i=1}^{n}\bar{W}_{ij}^{2}}\right),$

Plugging in this approximation in eq. 10 we obtain:

$\widehat{\Delta{\mathcal{G}}_{i}}(S,u)=\begin{cases}\mathsf{err}(u)\mathsf{tru}_{i}(S)&\text{
if }\Psi_{i}(S,u)<0\\\ 0&\text{ otherwise}\end{cases}$ (11)

Note that since the classifiers are independent we have

$\displaystyle\mathsf{tru}_{i}(S)$
$\displaystyle=\mathbb{P}\left(\bigwedge_{\begin{subarray}{c}v_{j}\in S\\\
\bar{W}_{ij}\neq
0\end{subarray}}\hat{y}_{j}(a)=y(a)\right)=\prod_{\begin{subarray}{c}v_{j}\in
S\\\ \bar{W}_{ij}\neq
0\end{subarray}}\mathbb{P}\left(\hat{y}_{j}(a)=y(a)\right)=\prod_{\begin{subarray}{c}v_{j}\in
S\\\ \bar{W}_{ij}\neq 0\end{subarray}}\left(1-\mathsf{err}(v_{j})\right)~{}.$

We have $\mathsf{tru}_{i}(S),\mathsf{err}(u)\leq 1$, thus the error of
approximating $\Delta{\mathcal{G}}_{i}(S,u)$ using eq. 11 is at most
$\exp\left(-\frac{\Psi_{i}(u)^{2}}{4\sum_{i=1}^{n}\bar{W}_{ij}^{2}}\right)$ .

∎

######  Lemma A.8.

Assume that all the all the classifiers
$\hat{y}_{1}(a),\hat{y}_{2}(a),\dots,\hat{y}_{n}(a)$ are pairwise independent.
We can estimate $\Gamma_{i}(S,u)$ as follows:

$\widehat{\Gamma}_{i}(S,u)=\begin{cases}0&\text{ if }\Psi_{i}(S,u)>0\\\
1&\text{ otherwise}\end{cases}$

where,

$\Psi_{i}(S,u)=\sum_{v_{j}\in S}\bar{W}_{ij}+\sum_{\begin{subarray}{c}j=1:n\\\
j\not\in
S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}[1-2\mathsf{err}(j)]-\bar{W}_{iu}$

The error of this estimation is bounded by:

$\absolutevalue{\widehat{\Gamma}_{i}(S,u)-\Gamma_{i}(S,u)}\leq\exp\left(-\frac{\Psi_{i}(S,u)^{2}}{4\sum_{i=1}^{n}\bar{W}_{ij}^{2}}\right)~{}\leq\exp\left(-\frac{\Psi_{i}(u)^{2}}{4\sum_{i=1}^{n}\bar{W}_{ij}^{2}}\right),$

where

$\Psi_{i}(u)=\sum_{j=1}^{n}\bar{W}_{ij}[1-2\mathsf{err}(j)]-2\mathsf{err}(u)\bar{W}_{iu}~{}.$

###### Proof.

Let’s remember the definition of $\Gamma_{i}(S,u)$ from lemma A.7:

$\displaystyle\Gamma_{i}(S,u)=$
$\displaystyle\operatorname*{\mathbb{P}}\left(a\in\Omega^{+}\right)\operatorname*{\mathbb{P}}_{a\in\Omega^{+}}\left(\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}\hat{y}_{j}(a)<-\sum_{v_{j}\in
S}\bar{W}_{ij}+\bar{W}_{iu}\right)$
$\displaystyle+\operatorname*{\mathbb{P}}\left(a\in\Omega^{-}\right)\operatorname*{\mathbb{P}}_{a\in\Omega^{-}}\left(\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}\hat{y}_{j}(a)>\sum_{v_{j}\in
S}\bar{W}_{ij}-\bar{W}_{iu}\right)~{}.$ (12)

Assume first that $\Psi_{i}(S,u)>0$. We use the Hoeffding bound theorem A.20
to estimate

$\operatorname*{\mathbb{P}}_{a\in\Omega^{+}}\left(\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}\hat{y}_{j}(a)<-\sum_{v_{j}\in
S}\bar{W}_{ij}+\bar{W}_{iu}\right)\quad\&\
\operatorname*{\mathbb{P}}_{a\in\Omega^{-}}\left(\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}\hat{y}_{j}(a)>\sum_{v_{j}\in
S}\bar{W}_{ij}-\bar{W}_{iu}\right)$ (13)

In order to bound the first probability in eq. 13, note that
$\sum_{\begin{subarray}{c}j=1:n\\\ v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}\hat{y}_{j}(a)<-\sum_{v_{j}\in
S}\bar{W}_{ij}+\bar{W}_{iu}$ iff :

$\displaystyle\sum_{\begin{subarray}{c}j=1:n\\\ v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}\hat{y}_{j}(a)<\operatorname*{\mathbb{E}}\left[\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}\hat{y}_{j}(a)\right]-\operatorname*{\mathbb{E}}\left[\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}\hat{y}_{j}(a)\right]-\sum_{v_{j}\in
S}\bar{W}_{ij}+\bar{W}_{iu}$

furthermore, from lemma A.1 we have $a\in\Omega^{+}$ implies:

$\operatorname*{\mathbb{E}}\left[\sum_{\begin{subarray}{c}j=1:n\\\ v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}\hat{y}_{j}(a)\right]=\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}[1-2\mathsf{err}(j)]~{}.$

Thus,

$\displaystyle\operatorname*{\mathbb{P}}_{a\in\Omega^{+}}\left(\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}\hat{y}_{j}(a)<-\sum_{v_{j}\in
S}\bar{W}_{ij}+\bar{W}_{ui}\right)$ $\displaystyle=$
$\displaystyle\operatorname*{\mathbb{P}}_{a\in\Omega^{+}}\left(\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}\hat{y}_{j}(a)<\operatorname*{\mathbb{E}}\left[\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}\hat{y}_{j}(a)\right]-\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}[1-2\mathsf{err}(j)]-\sum_{v_{j}\in
S}\bar{W}_{ij}+\bar{W}_{iu}\right)$ $\displaystyle=$
$\displaystyle\operatorname*{\mathbb{P}}_{a\in\Omega^{+}}\left(\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}\hat{y}_{j}(a)<\operatorname*{\mathbb{E}}\left[\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}\hat{y}_{j}(a)\right]-\Psi_{i}(S,u)\right)$

Since $\hat{y}_{i}(a)$s are pairwise independent, and $\Psi_{i}(S,u)>0$ we may
use the Hoeffding bound to obtain:

$\displaystyle\operatorname*{\mathbb{P}}_{a\in\Omega^{+}}\left(\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}\hat{y}_{j}(a)<-\sum_{v_{j}\in
S}\bar{W}_{ij}+\bar{W}_{iu}\right)\leq\exp\left(-\frac{\Psi_{i}(S,u)^{2}}{\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}^{2}}\right).$

The second probability in eq. 13 may be bounded similarly as follows:

$\displaystyle\operatorname*{\mathbb{P}}_{a\in\Omega^{+}}\left(\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ji}\hat{y}_{j}(a)>\sum_{v_{j}\in
S}\bar{W}_{ji}-\bar{W}_{ui}\right)$ $\displaystyle=$
$\displaystyle\operatorname*{\mathbb{P}}_{a\in\Omega^{+}}\left(\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ji}\hat{y}_{j}(a)>\operatorname*{\mathbb{E}}\left[\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ji}\hat{y}_{j}(a)\right]-\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ji}[2\mathsf{err}(j)-1]+\sum_{v_{j}\in
S}\bar{W}_{ji}-\bar{W}_{ui}\right)$ $\displaystyle=$
$\displaystyle\operatorname*{\mathbb{P}}_{a\in\Omega^{+}}\left(\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ji}\hat{y}_{j}(a)>\operatorname*{\mathbb{E}}\left[\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ji}\hat{y}_{j}(a)\right]+\Psi_{i}(S,u)\right)$

Again, under pairwise independence and $\Psi_{i}(S,u)>0$ the above probability
is bounded as:

$\displaystyle\operatorname*{\mathbb{P}}_{a\in\Omega^{-}}\left(\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ji}\hat{y}_{j}(a)>\sum_{v_{j}\in
S}\bar{W}_{ji}-\bar{W}_{ui}\right)\leq\exp\left(-\frac{\Psi_{i}(S,u)^{2}}{\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin S\cup\\{u\\}\end{subarray}}\bar{W}_{ji}^{2}}\right).$

Putting together, we obtain: If $\Psi_{i}(S,u)>0$:

$\displaystyle\Gamma_{i}(S,u)=$
$\displaystyle\operatorname*{\mathbb{P}}\left(a\in\Omega^{+}\right)\operatorname*{\mathbb{P}}_{a\in\Omega^{+}}\left(\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ji}\hat{y}_{j}(a)<-\sum_{v_{j}\in
S}\bar{W}_{ji}+\bar{W}_{ui}\right)$ $\displaystyle\ \ \
+\operatorname*{\mathbb{P}}\left(a\in\Omega^{-}\right)\operatorname*{\mathbb{P}}_{a\in\Omega^{-}}\left(\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ji}\hat{y}_{j}(a)>\sum_{v_{j}\in
S}\bar{W}_{ji}-\bar{W}_{ui}\right)~{}$ $\displaystyle\leq$
$\displaystyle\exp\left(\frac{\Psi_{i}(S,u)^{2}}{\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ji}^{2}}\right)[\operatorname*{\mathbb{P}}(a\in\Omega^{+})+\operatorname*{\mathbb{P}}(a\in\Omega^{-})]=\exp\left(\frac{\Psi_{i}(S,u)^{2}}{\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin S\cup\\{u\\}\end{subarray}}\bar{W}_{ji}^{2}}\right)$

Note that $\Gamma_{i}(S,u)\geq 0$. Therefore, if $\Psi_{i}(S,u)>0$, we define
$\widehat{\Gamma}_{i}(S,u)=0$ and we will have:

$0\leq\Gamma_{i}(S,u)-\widehat{\Gamma}_{i}(S,u)\leq\exp\left(-\frac{\Psi_{i}(S,u)^{2}}{\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin S\cup\\{u\\}\end{subarray}}\bar{W}_{ji}^{2}}\right)~{}.$

Let’s now find a lower bound on
$\frac{\Psi_{i}(S,u)^{2}}{\sum_{\begin{subarray}{c}j=1:n\\\ v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ji}^{2}}$ which is independent of $S$. We
have:

$\displaystyle\sum_{\begin{subarray}{c}j=1:n\\\ v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ji}^{2}\leq\sum_{i=1}^{n}\bar{W}_{ji}^{2}~{}.$

and

$\displaystyle\Psi_{i}(S,u)$ $\displaystyle=\sum_{v_{j}\in
S}\bar{W}_{ij}+\sum_{\begin{subarray}{c}j=1:n\\\ j\not\in
S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}[1-2\mathsf{err}(j)]-\bar{W}_{iu}$
$\displaystyle\geq\sum_{\begin{subarray}{c}j=1:n\\\ j\neq
u\end{subarray}}\bar{W}_{ij}[1-2\mathsf{err}(j)]-\bar{W}_{iu}$
$\displaystyle=\sum_{j=1}^{n}\bar{W}_{ij}[1-2\mathsf{err}(j)]-2\mathsf{err}(u)\bar{W}_{iu}~{}=\Psi_{i}(u)~{}.$

Thus,

$0\leq\Gamma_{i}(S,u)-\widehat{\Gamma}_{i}(S,u)\leq\exp\left(-\frac{\Psi_{i}(S,u)^{2}}{\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ji}^{2}}\right)\leq\exp\left(-\frac{\Psi_{i}(u)^{2}}{\sum_{j=1}^{n}\bar{W}_{ji}^{2}}\right)~{}.$

Assume now that $\Psi_{i}(S,u)<0$. In this case we write the first probability
in eq. 13 as:

$\displaystyle\operatorname*{\mathbb{P}}_{a\in\Omega^{+}}\left(\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}\hat{y}_{j}(a)<-\sum_{v_{j}\in
S}\bar{W}_{ij}+\bar{W}_{iu}\right)=1-\operatorname*{\mathbb{P}}_{a\in\Omega^{+}}\left(\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}\hat{y}_{j}(a)\geq-\sum_{v_{j}\in
S}\bar{W}_{ij}+\bar{W}_{iu}\right)$ $\displaystyle=$ $\displaystyle
1-\operatorname*{\mathbb{P}}_{a\in\Omega^{+}}\left(\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}\hat{y}_{j}(a)\geq\operatorname*{\mathbb{E}}\left[\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}\hat{y}_{j}(a)\right]-\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}[1-2\mathsf{err}(j)]-\sum_{v_{j}\in
S}\bar{W}_{ji}+\bar{W}_{iu}\right)$ $\displaystyle=$ $\displaystyle
1-\operatorname*{\mathbb{P}}_{a\in\Omega^{+}}\left(\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}\hat{y}_{j}(a)\geq\operatorname*{\mathbb{E}}\left[\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}\hat{y}_{j}(a)\right]-\Psi_{i}(S,u)\right)$

Since $\Psi_{i}(S,u)<0$, we have $-\Psi_{i}(S,u)>0$ using the pairwise
independence of the classifiers, we employ the Hoeffding bound and obtain
that:

$\operatorname*{\mathbb{P}}_{a\in\Omega^{+}}\left(\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}\hat{y}_{j}(a)<-\sum_{v_{j}\in
S}\bar{W}_{ij}+\bar{W}_{iu}\right)\geq
1-\exp\left(-\frac{\Psi_{i}(S,u)^{2}}{\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}^{2}}\right)~{}.$

Similarly we have :

$\operatorname*{\mathbb{P}}_{a\in\Omega^{-}}\left(\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}\hat{y}_{j}(a)>\sum_{v_{j}\in
S}\bar{W}_{ij}-\bar{W}_{ui}\right)\geq
1-\exp\left(\frac{\Psi_{i}(S,u)^{2}}{\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}^{2}}\right)~{}.$

Putting together, we obtain: If $\Psi_{i}(S,u)<0$:

$\displaystyle\Delta{\mathcal{G}}_{i}(S,u)=$
$\displaystyle\operatorname*{\mathbb{P}}\left(a\in\Omega^{+}\right)\operatorname*{\mathbb{P}}_{a\in\Omega^{+}}\left(\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ji}\hat{y}_{j}(a)<-\sum_{v_{j}\in
S}\bar{W}_{ji}+\bar{W}_{ui}\right)$ $\displaystyle\ \ \
+\operatorname*{\mathbb{P}}\left(a\in\Omega^{-}\right)\operatorname*{\mathbb{P}}_{a\in\Omega^{-}}\left(\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ji}\hat{y}_{j}(a)>\sum_{v_{j}\in
S}\bar{W}_{ji}-\bar{W}_{ui}\right)~{}$ $\displaystyle\geq$
$\displaystyle[1-\exp\left(-\frac{\Psi_{i}(S,u)^{2}}{\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ji}^{2}}\right)][\operatorname*{\mathbb{P}}(a\in\Omega^{+})+\operatorname*{\mathbb{P}}(a\in\Omega^{-})]=1-\exp\left(-\frac{\Psi_{i}(S,u)^{2}}{\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin S\cup\\{u\\}\end{subarray}}\bar{W}_{ji}^{2}}\right)$

Note that $\Gamma_{i}(S,u)\leq 1$. Therefore, if $\Psi_{i}(S,u)<0$, we define
$\widehat{\Gamma}_{i}(S,u)=1$ and we will have:

$0\leq\widehat{\Gamma}_{i}(S,u)-\Gamma_{i}(S,u)\leq\exp\left(-\frac{\Psi_{i}(S,u)^{2}}{\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ji}^{2}}\right)\leq\exp\left(-\frac{\Psi_{i}(u)^{2}}{\sum_{j=1}^{n}\bar{W}_{ji}^{2}}\right)~{}.$

This completes our proof. ∎

####  A.4.1 Missing material from section 4.2.1 related to ambiguous vertices

######  Lemma A.9.

Let $V^{+}$ be those agents with error less than $1/2$ and $V^{-}$ be those
agents with error greater than $1/2$. i.e,

$V^{+}=\\{v_{j}\mid\mathsf{err}(v_{j})\leq 1/2\\}\quad\&\
V^{-}=\\{v_{j}\mid\mathsf{err}(v_{j})>1/2\\}$

and consider the following vectors

$\bar{W}^{+}_{i}=(\bar{W}_{ij})_{v_{j}\in
V^{+}}\quad\&~{}{\mathcal{E}}^{+}=\left(1-2\mathsf{err}(v_{j})\right)_{v_{j}\in
V^{+}}$

and

$\bar{W}^{-}_{i}=(\bar{W}_{ij})_{v_{j}\in
V^{-}}\quad\&~{}{\mathcal{E}}^{-}=\left(2\mathsf{err}(v_{j})-1\right)_{v_{j}\in
V^{-}}$

and

$\bar{W}_{i}=(\bar{W}_{i1},\bar{W}_{i2},\dots,\bar{W}_{in})$

We have that:

$\displaystyle\exp\left(-\frac{\Psi_{i}(u)^{2}}{4\sum_{i=1}^{n}\bar{W}_{ij}^{2}}\right)$
$\displaystyle\leq\exp\left(-\frac{1}{4}\left(\frac{\langle\bar{W}_{i}^{+},{\mathcal{E}}^{+}\rangle}{\absolutevalue{\bar{W}_{i}}_{2}}-\frac{\langle\bar{W}_{i}^{-},{\mathcal{E}}^{-}\rangle}{\absolutevalue{\bar{W}_{i}}_{2}}-2\right)^{2}\right)$
$\displaystyle\leq\exp\left(-\frac{1}{4}\left(M\cdot\frac{\absolutevalue{\bar{W}_{i}^{+}}_{2}}{\absolutevalue{\bar{W}_{i}}_{2}}\cdot\absolutevalue{{\mathcal{E}}^{+}}_{2}-\frac{\absolutevalue{\bar{W}_{i}^{-}}_{2}}{\absolutevalue{\bar{W}_{i}}_{2}}\cdot\absolutevalue{{\mathcal{E}}^{-}}_{2}-2\right)^{2}\right)$

where

$M=\frac{\max{\bar{W}_{i}^{+}}}{\min{\bar{W}_{i}^{+}}}\cdot\frac{1}{\min{\mathcal{E}}_{i}^{+}}~{}.$

###### Proof.

We show the above equation by finding an lower bound for
$\frac{\Psi_{i}(u)^{2}}{\sum_{i=1}^{n}\bar{W}_{ij}^{2}}$.

Consider an arbitrary vector $X$the $\ell_{2}$ norm is defined as:

$\absolutevalue{X}_{2}=\sqrt{\sum_{x_{j}\in X}x_{j}^{2}}$

Note that all of the above vectors only have positive elements.

We have:

$\displaystyle\frac{\Psi_{i}(u)^{2}}{\sum_{i=1}^{n}\bar{W}_{ij}^{2}}$
$\displaystyle=\left(\frac{\Psi_{i}(u)}{\absolutevalue{\bar{W}_{i}(V)}_{2}}\right)^{2}$
$\displaystyle=\left(\frac{\sum_{v_{i}\in
V^{+}}\bar{W}_{ij}(1-2\mathsf{err}(v_{j}))}{\absolutevalue{\bar{W}_{i}(V)}_{2}}-\frac{\sum_{v_{i}\in
V^{-}}\bar{W}_{ij}(2\mathsf{err}(v_{j})-1)}{\absolutevalue{\bar{W}_{i}(V)}_{2}}-\frac{2\mathsf{err}(u)\bar{W}_{iu}}{\absolutevalue{\bar{W}_{i}(V)}_{2}}\right)^{2}$
$\displaystyle=\left(\frac{\langle\bar{W}_{i}^{+},{\mathcal{E}}^{+}\rangle}{\absolutevalue{\bar{W}_{i}}_{2}}-\frac{\langle\bar{W}_{i}^{-},{\mathcal{E}}^{-}\rangle}{\absolutevalue{\bar{W}_{i}}_{2}}-\frac{2\mathsf{err}(u)\bar{W}_{iu}}{\absolutevalue{\bar{W}_{i}}_{2}}\right)^{2}$
(14)

where in the last equation $\langle\rangle$ denotes dot product.

Using P$\rm\acute{o}$lya-Szeg$\rm\ddot{o}$’s inequality we have:

$\frac{\langle\bar{W}_{i}^{+},{\mathcal{E}}^{+}\rangle}{\absolutevalue{\bar{W}_{i}}_{2}}\geq\frac{\absolutevalue{\bar{W}_{i}^{+}}_{2}}{\absolutevalue{\bar{W}_{i}}_{2}}\cdot\frac{\max{\bar{W}_{i}^{+}}}{\min{\bar{W}_{i}^{+}}}\cdot\frac{\absolutevalue{{\mathcal{E}}^{+}}_{2}}{\min{\mathcal{E}}^{+}}$

Using Cauchy Schwarz we have

$\frac{\langle\bar{W}_{i}^{-},{\mathcal{E}}^{-}\rangle}{\absolutevalue{\bar{W}_{i}}_{2}}\leq\frac{\absolutevalue{\bar{W}_{i}}_{2}}{\absolutevalue{\bar{W}_{i}^{-}}_{2}}\cdot{\absolutevalue{{\mathcal{E}}^{-}}_{2}}$

Therefore, letting
$M=\frac{\max{\bar{W}_{i}^{+}}}{\min{\bar{W}_{i}^{+}}}\cdot\frac{1}{\min{\mathcal{E}}_{i}^{+}}$

we have:

$\displaystyle\frac{\Psi_{i}(u)^{2}}{\sum_{i=1}^{n}\bar{W}_{ij}^{2}}$
$\displaystyle\geq\left(M\cdot\frac{\absolutevalue{\bar{W}_{i}^{+}}_{2}}{\absolutevalue{\bar{W}_{i}}_{2}}\cdot\absolutevalue{{\mathcal{E}}^{+}}_{2}-\frac{\absolutevalue{\bar{W}_{i}^{-}}_{2}}{\absolutevalue{\bar{W}_{i}}_{2}}\cdot\absolutevalue{{\mathcal{E}}^{-}}_{2}-\frac{2\mathsf{err}(u)\bar{W}_{iu}}{\absolutevalue{\bar{W}_{i}}_{2}}\right)^{2}$

The premise may be concluded from the fact that
$\frac{\mathsf{err}(u)\bar{W}_{iu}}{\absolutevalue{\bar{W}_{i}}_{2}}\leq 1$.

∎

###### Proof of lemma 4.5.

From lemma 4.6 we now that

$\absolutevalue{\widehat{\Delta{\mathcal{G}}_{i}}(S,u)-\Delta{\mathcal{G}}_{i}(S,u)}\leq\exp\left(-\frac{\Psi_{i}(u)^{2}}{4\sum_{i=1}^{n}\bar{W}_{ij}^{2}}\right)~{},$

and from lemma A.9 we have:

$\exp\left(-\frac{\Psi_{i}(u)^{2}}{4\sum_{i=1}^{n}\bar{W}_{ij}^{2}}\right)\leq\exp\left(-\frac{1}{4}\left(M\cdot\frac{\absolutevalue{\bar{W}_{i}^{+}}_{2}}{\absolutevalue{\bar{W}_{i}}_{2}}\cdot\absolutevalue{{\mathcal{E}}^{+}}_{2}-\frac{\absolutevalue{\bar{W}_{i}^{-}}_{2}}{\absolutevalue{\bar{W}_{i}}_{2}}\cdot\absolutevalue{{\mathcal{E}}^{-}}_{2}-2\right)^{2}\right)$

Putting together and assume that $v_{i}$ is not ambiguous. We have that:

$\displaystyle\absolutevalue{\widehat{\Delta{\mathcal{G}}_{i}}(S,u)-\Delta{\mathcal{G}}_{i}(S,u)}$
$\displaystyle\leq\exp\left(-\frac{\Psi_{i}(u)^{2}}{4\sum_{i=1}^{n}\bar{W}_{ij}^{2}}\right)\leq\exp\left(-\frac{1}{4}\left(M\cdot\frac{\absolutevalue{\bar{W}_{i}^{+}}_{2}}{\absolutevalue{\bar{W}_{i}}_{2}}\cdot\absolutevalue{{\mathcal{E}}^{+}}_{2}-\frac{\absolutevalue{\bar{W}_{i}^{-}}_{2}}{\absolutevalue{\bar{W}_{i}}_{2}}\cdot\absolutevalue{{\mathcal{E}}^{-}}_{2}-2\right)^{2}\right)$
$\displaystyle\leq\exp\left(-\frac{1}{4}\left(3\sqrt{\log
n}-2\right)^{2}\right)\leq\exp(-\frac{1}{4}(5\log n))=o(n^{-1})~{}.$

∎

####  A.4.2 Missing material from section 4.2.1: proof of the main theorems

In this subsection we present a pseudocode of our algorithm under the
assumption that the agents are pairwise independent.

The following theorem bounds the error of this algorithm:

######  Theorem A.10.

Assume that $S$ is the output of algorithm 2. We have that:

$\mathcal{G}^{({\rm egal})}(S)\geq[(1-1/e)-\Delta^{\rm ind}]\cdot{\rm
OPT^{({\rm egal})}}~{},$

where

$\Delta^{\rm
ind}=\sum_{i=1}^{n}\exp\left(-\frac{\Psi_{i}(u)^{2}}{\sum_{i=1}^{n}\bar{W}_{ij}^{2}}\right)~{}.$

###### Proof.

The proof immediately follows from the fact that we have a submodular and
monotone function and that the error greedy choice taken as

$g=\underset{u}{\rm
argmax}\sum_{i=1}^{n}\widehat{\Delta{\mathcal{G}}}_{i}(S,u)~{},$

and that for any $v_{i}$ we have

$\absolutevalue{\widehat{\Delta{\mathcal{G}}_{i}}(S,u)-\Delta{\mathcal{G}}_{i}(S,u)}\leq\exp\left(-\frac{\Psi_{i}(u)^{2}}{4\sum_{i=1}^{n}\bar{W}_{ij}^{2}}\right)~{},$

∎

###### Proof of theorem 4.3 and theorem 3.10 .

Using the above theorem theorem 4.3 and theorem 3.10 can be directly concluded
just by noticing that for any non-ambiguous vertex the error induced on the
greedy choice is at most $o(n^{-1})$. Thus, in total all of non-ambiguous
vertices together will have an error of $o(1)$. The ambiguous each can have an
error as large as $1$. ∎

##### Assuming having access to approximation $\widehat{\bar{W}}$.

If we only have access to $\widehat{\bar{W}}$, we may run
$\mathsf{EgalAlgo}^{\rm ind}$ using $\widehat{\bar{W}}$. In this case the
approximation guarantee can be concluded from the following lemma which is
similar to lemma A.8:

######  Lemma A.11.

Assume that all the all the classifiers
$\hat{y}_{1}(a),\hat{y}_{2}(a),\dots,\hat{y}_{n}(a)$ are pairwise independent.
We can estimate $\Gamma_{i}(S,u)$ (See section A.4) as follows:

$\widehat{\Gamma}_{i}(S,u)=\begin{cases}0&\text{ if
}\widehat{\Psi}_{i}(S,u)>0\\\ 1&\text{ otherwise}\end{cases}$

where,

$\widehat{\Psi}_{i}(S,u)=\sum_{v_{j}\in
S}\widehat{\bar{W}}_{ij}+\sum_{\begin{subarray}{c}j=1:n\\\ j\not\in
S\cup\\{u\\}\end{subarray}}\widehat{\bar{W}}_{ij}[1-2\mathsf{err}(j)]-\widehat{\bar{W}}_{iu}$

The error of this estimation is bounded by:

$\absolutevalue{\widehat{\Gamma}_{i}(S,u)-\Gamma_{i}(S,u)}\leq\exp\left(-\frac{\Psi_{i}(u)^{2}}{4\sum_{i=1}^{n}\bar{W}_{ij}^{2}}\right)(1+\epsilon)~{},$

where

$\Psi_{i}(u)=\sum_{j=1}^{n}\bar{W}_{ij}[1-2\mathsf{err}(j)]-2\mathsf{err}(u)\bar{W}_{iu}~{}.$

###### Proof.

Similar to the proof of lemma A.8 we may bound the two terms of
$\Gamma_{i}(S,u)$ as follows:

$\displaystyle\operatorname*{\mathbb{P}}_{a\in\Omega^{+}}\left(\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}{\bar{W}}_{ij}\hat{y}_{j}(a)<-\sum_{v_{j}\in
S}\bar{W}_{ij}+\bar{W}_{ui}\right)$ $\displaystyle\leq$
$\displaystyle\operatorname*{\mathbb{P}}_{a\in\Omega^{+}}\left(\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}\hat{y}_{j}(a)<\operatorname*{\mathbb{E}}\left[\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}{\bar{W}}_{ij}\hat{y}_{j}(a)\right]-\widehat{\Psi}_{i}(S,u)-2\epsilon\right)$

Similarly to the previous case if $\widehat{\Psi}_{i}(S,u)>0$ we may use
Hoeffding bound to bound the above probability as:

$\exp\left(-\frac{(\widehat{\Psi}_{i}(u)-2\epsilon)^{2}}{\sum_{j=1}^{n}\bar{W}_{ij}^{2}}\right)\leq\exp\left(-\frac{(\Psi_{i}(u)-4\epsilon)^{2}}{\sum_{j=1}^{n}\bar{W}^{2}_{ij}}\right)$

Let’s now bound RHS:

$\displaystyle\exp\left(-\frac{(\Psi_{i}(u)-4\epsilon)^{2}}{\sum_{j=1}^{n}\bar{W}_{ij}^{2}}\right)$
$\displaystyle\leq\exp\left(-\frac{\Psi_{i}(u)^{2}}{\sum_{j=1}^{n}\bar{W}^{2}_{ij}}+8\epsilon\frac{\Psi_{i}(u)}{\sum_{j=1}^{n}\bar{W}^{2}_{ij}}\right)\leq\exp\left(-\frac{\Psi_{i}(u)^{2}}{\sum_{j=1}^{n}\bar{W}^{2}_{ij}}+8\epsilon\right)$
$\displaystyle\leq\exp\left(-\frac{\Psi_{i}(u)^{2}}{\sum_{j=1}^{n}\bar{W}^{2}_{ij}}\right)\exp(8\epsilon)\leq(1+8\epsilon)\exp\left(-\frac{\Psi_{i}(u)^{2}}{\sum_{j=1}^{n}\bar{W}^{2}_{ij}}\right)$

If $\widehat{\Psi}_{i}(S,u)<0$ we may write:

$\displaystyle\operatorname*{\mathbb{P}}_{a\in\Omega^{+}}\left(\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}{\bar{W}}_{ij}\hat{y}_{j}(a)>-\sum_{v_{j}\in
S}\bar{W}_{ij}+\bar{W}_{ui}\right)$ $\displaystyle\leq$
$\displaystyle\operatorname*{\mathbb{P}}_{a\in\Omega^{+}}\left(\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}\hat{y}_{j}(a)>\operatorname*{\mathbb{E}}\left[\sum_{\begin{subarray}{c}j=1:n\\\
v_{j}\notin
S\cup\\{u\\}\end{subarray}}{\bar{W}}_{ij}\hat{y}_{j}(a)\right]-\widehat{\Psi}_{i}(S,u)+2\epsilon\right)$

and with a similar argument we obtain the same bound. Bounding the probability
in the case where $a\in\Omega^{-}$ can be done similarly. And the rest of the
proof holds similarly to proof of lemma A.8. ∎

###### Proof of remark 3.12 independent case .

The remark is a direct conclusion of the fact that the error of the greedy
choice is bounded by

$\sum_{i=1}^{n}\absolutevalue{\widehat{\Gamma}_{i}(S,u)-\Gamma_{i}(S,u)}\leq(1+\epsilon)\sum_{i=1}^{n}\exp\left(-\frac{\Psi_{i}(u)^{2}}{4\sum_{j=1}^{n}\bar{W}_{ij}^{2}}\right)~{}.$

∎

###  A.5 Missing proofs from section 4.2.2: Estimating greedy choice assuming
group dependence

Assume the assumption presented in definition 4.7 and remember the following
definition from previous sections

$\Delta{\mathcal{G}}_{i}(S,u)=\operatorname*{\mathbb{P}}_{a\sim\Omega}\left(\mathcal{Z}(i,a)\leq
0\wedge\left(\bigwedge_{\begin{subarray}{c}v_{j}\in S\\\ \bar{W}_{ij}\neq
0\end{subarray}}y(a)=\hat{y}_{j}(a)\right)\wedge
y(a)\neq\hat{y}_{u}(a)\right),$

and our goal is to estimate $\Delta{\mathcal{G}}_{i}(S,u)$ for all $S\subseteq
V$, $u\in V$ and $i\in[n]$.

We may write

$\Delta{\mathcal{G}}_{i}(S,u)=\Delta{\mathcal{G}}^{\rm
gr}_{i}(S,u)\rho+\Delta{\mathcal{G}}^{\rm indv}_{i}(S,u)(1-\rho)~{},$

, where the super-scripts show whether individual or group decisions have been
made. Estimation of $\Delta{\mathcal{G}}_{i}^{\rm indv}(S,u)$ can be obtained
using lemma 4.6 and by calling $\mathsf{EstGain}^{\rm ind}$ of algorithm 2.
Estimation of $\Delta{\mathcal{G}}^{\rm gr}_{i}(S,u)$ can be done through a
series of lemmas that we present here, and it depends on the whether vertices
of $S_{i}$, defined as $S_{i}\triangleq\\{v_{j}\in S\mid\bar{W}_{ij}\neq
0\\}$, intersects ${\mathcal{R}}$, ${\mathcal{B}}$ or both. A pseudocode is
presented at algorithms 2 and 4. Our analysis is presented in sections A.5.1,
A.5.2 and A.5.3. The following lemma summarizes these results:

######  Lemma A.12.

Assume the model presented in definition 4.7. Having a set $S$ let $g$ be the
vertex which maximizes the following function

$g=\underset{u\in V}{\rm argmax}\ \rho\sum_{\begin{subarray}{c}i=1:n\\\
{\mathcal{W}}_{ij}\neq 0\end{subarray}}\widehat{\Delta{\mathcal{G}}}_{i}^{\rm
gr}(S,u)+(1-\rho)\sum_{\begin{subarray}{c}i=1:n\\\ {\mathcal{W}}_{ij}\neq
0\end{subarray}}\widehat{\Delta{\mathcal{G}}}_{i}^{\rm indv}(S,u)$

Where $\widehat{\Delta{\mathcal{G}}}_{i}^{\rm gr}(S,u)$ may be obtained from
lemmas A.14, A.16 and A.17, and $\widehat{\Delta{\mathcal{G}}}_{i}^{\rm
indv}(S,u)$ may be obtained from lemma 4.6. We have that:

$\displaystyle\mathcal{G}^{({\rm
egal})}\left(S\cup\\{{\mathsf{gr}}(S)\\}\right)-\mathcal{G}^{({\rm
egal})}\left(S\cup\\{g\\}\right)\leq\rho\sum_{i=1}^{n}\exp\left(-\frac{(\Psi_{i}^{\mathcal{W}}(u)-\Delta\bar{W}_{i})^{2}}{4\sum_{v_{j}\in{\mathcal{W}}}\bar{W}_{ij}^{2}}\right)+(1-\rho)\sum_{i=1}^{n}\exp\left(-\frac{(\Psi_{i}(u))^{2}}{4\sum_{v_{j}\in
V}\bar{W}_{ij}^{2}}\right)$

We will use the following definitions and results throughout the section.

$\Delta{\mathcal{G}}^{\rm gr}_{i}(S,u)=\operatorname*{\mathbb{P}}^{\rm
gr}_{a\sim\Omega}\left(\mathcal{Z}(i,a)\leq
0\wedge{\mathcal{T}}_{i}(S)\wedge{\mathcal{F}}(u)\right)~{},$

where ${\mathcal{T}}_{i}(S)$ and ${\mathcal{F}}(u)$ are the following events:

${\mathcal{T}}_{i}(S)=\bigwedge_{\begin{subarray}{c}v_{j}\in
S_{i}\end{subarray}}y(a)=\hat{y}_{j}(a)\quad\&\
{\mathcal{F}}(u)=y(a)\neq\hat{y}_{u}(a)~{}.$

for any $v_{i}$ and $X\subseteq V$ we denote:

$\bar{W}_{i}(X)=\sum_{v_{j}\in X}\bar{W}_{ij}$

In addition, for any $X,Y\subseteq V$ we define,

$\Psi_{i}(X,Y)=\sum_{v_{j}\in V\setminus(X\cup Y)}[1-2\mathsf{err}^{\rm
indv}(v_{j})]+\bar{W}_{i}(X)-\bar{W}_{i}(Y)~{}.$

We will use the following lemma throughout:

######  Lemma A.13.

Let’s define

$\Gamma_{i}^{+}(X,Y)=\operatorname*{\mathbb{P}}_{a\in\Omega^{+}}\left(\sum_{v_{j}\in
V\setminus(X\cup Y)}\bar{W}_{ij}\hat{y}^{\rm
indv}_{j}(a)\leq\bar{W}_{i}(Y)-\bar{W}_{i}(X)\right)~{},$

and

$\Gamma_{i}^{-}(X,Y)=\operatorname*{\mathbb{P}}_{a\in\Omega^{-}}\left(\sum_{v_{j}\in
V\setminus(X\cup Y)}\bar{W}_{ij}\hat{y}^{\rm
indv}_{j}(a)\geq\bar{W}_{i}(X)-\bar{W}_{i}(Y)\right)~{}.$

We may estimate the above probabilities as

$\widehat{\Gamma}_{i}^{+}(X,Y)=\widehat{\Gamma}_{i}^{-}(X,Y)=\begin{cases}0&\text{if
}\ \Psi_{i}(X,Y)\geq 0\\\ 1&\text{if }\ \Psi_{i}(X,Y)<0\end{cases}$

We have that:

$\absolutevalue{\Gamma_{i}^{+}(X,Y)-\widehat{\Gamma}_{i}^{+}(X,Y)}\leq\exp\left(-\frac{(\Psi_{i}(X,Y))^{2}}{\sum_{v_{j}\in
V\setminus(X\cup Y)}\bar{W}_{ij}^{2}}\right)~{},$

and

$\absolutevalue{\Gamma_{i}^{-}(X,Y)-\widehat{\Gamma}_{i}^{-}(X,Y)}\leq\exp\left(-\frac{(\Psi_{i}(X,Y))^{2}}{\sum_{v_{j}\in
V\setminus(X\cup Y)}\bar{W}_{ij}^{2}}\right)~{}.$

###### Proof.

Assume $a\in\Omega^{+}$ in this case we have that

$\operatorname*{\mathbb{E}}_{a\in\Omega^{+}}\left[\hat{y}^{\rm
indv}_{j}(a)\right]=1-2\mathsf{err}^{indv}(v_{j})$

Thus,

$\displaystyle\sum_{v_{j}\in V\setminus(X\cup Y)}\bar{W}_{ij}\hat{y}^{\rm
indv}_{j}(a)\leq\bar{W}_{i}(Y)-\bar{W}_{i}(X)\iff$
$\displaystyle\sum_{v_{j}\in V\setminus(X\cup Y)}\bar{W}_{ij}\hat{y}^{\rm
indv}_{j}(a)\leq\operatorname*{\mathbb{E}}\left[\sum_{v_{j}\in
V\setminus(X\cup Y)}\bar{W}_{ij}\hat{y}^{\rm
indv}_{j}(a)\right]-\left(\operatorname*{\mathbb{E}}\left[\sum_{v_{j}\in
V\setminus(X\cup Y)}\bar{W}_{ij}\hat{y}^{\rm
indv}_{j}(a)\right]-\bar{W}_{i}(Y)+\bar{W}_{i}(X)\right)\iff$
$\displaystyle\sum_{v_{j}\in V\setminus(X\cup Y)}\bar{W}_{ij}\hat{y}^{\rm
indv}_{j}(a)\leq\operatorname*{\mathbb{E}}\left[\sum_{v_{j}\in
V\setminus(X\cup Y)}\bar{W}_{ij}\hat{y}^{\rm
indv}_{j}(a)\right]-\Psi_{i}(X,Y)$

If $\Psi_{i}(X,Y)>0$ we may use the Hoeffding bound to obtain:

$\operatorname*{\mathbb{P}}_{a\in\Omega^{+}}\left(\sum_{v_{j}\in
V\setminus(X\cup Y)}\bar{W}_{ij}\hat{y}^{\rm
indv}_{j}(a)\leq\bar{W}_{i}(Y)-\bar{W}_{i}(X)\right)\leq\exp\left(-\frac{\left(\Psi_{i}(X,Y)\right)^{2}}{\sum_{v_{j}\in
V\setminus(X\cup Y)}\bar{W}_{ij}^{2}}\right)~{}.$

If $-\Psi_{i}(X,Y)>0$, we write:

$\displaystyle\sum_{v_{j}\in V\setminus(X\cup Y)}\bar{W}_{ij}\hat{y}^{\rm
indv}_{j}(a)\geq\bar{W}_{i}(Y)-\bar{W}_{i}(X)\iff$
$\displaystyle\sum_{v_{j}\in V\setminus(X\cup Y)}\bar{W}_{ij}\hat{y}^{\rm
indv}_{j}(a)\geq\operatorname*{\mathbb{E}}\left[\sum_{v_{j}\in
V\setminus(X\cup Y)}\bar{W}_{ij}\hat{y}^{\rm
indv}_{j}(a)\right]-\Psi_{i}(X,Y)$

Thus,

$\operatorname*{\mathbb{P}}_{a\in\Omega^{+}}\left(\sum_{v_{j}\in
V\setminus(X\cup Y)}\bar{W}_{ij}\hat{y}^{\rm
indv}_{j}(a)\geq\bar{W}_{i}(Y)-\bar{W}_{i}(X)\right)\leq\exp\left(-\frac{\left(\Psi_{i}(X,Y)\right)^{2}}{\sum_{v_{j}\in
V\setminus(X\cup Y)}\bar{W}_{ij}^{2}}\right)$

Therefore,

$\displaystyle\operatorname*{\mathbb{P}}_{a\in\Omega^{+}}\left(\sum_{v_{j}\in
V\setminus(X\cup Y)}\bar{W}_{ij}\hat{y}^{\rm
indv}_{j}(a)\leq\bar{W}_{i}(Y)-\bar{W}_{i}(X)\right)$ $\displaystyle=$
$\displaystyle
1-\operatorname*{\mathbb{P}}_{a\in\Omega^{+}}\left(\sum_{v_{j}\in
V\setminus(X\cup Y)}\bar{W}_{ij}\hat{y}^{\rm
indv}_{j}(a)\geq\bar{W}_{i}(Y)-\bar{W}_{i}(X)\right)$ $\displaystyle\geq$
$\displaystyle
1-\exp\left(-\frac{\left(\Psi_{i}(X,Y)\right)^{2}}{\sum_{v_{j}\in
V\setminus(X\cup Y)}\bar{W}_{ij}^{2}}\right)~{}.$

Putting together we have:

$\absolutevalue{\Gamma_{i}^{+}(X,Y)-\widehat{\Gamma}_{i}^{+}(X,Y)}\leq\exp\left(-\frac{(\Psi_{i}(X,Y))^{2}}{\sum_{v_{j}\in
V\setminus(X\cup Y)}\bar{W}_{ij}^{2}}\right)~{},$

Similarly if $a\in\Omega^{-}$ we have:

$\operatorname*{\mathbb{E}}_{a\in\Omega^{-}}\left[\hat{y}^{\rm
indv}_{j}(a)\right]=2\mathsf{err}^{\rm indv}(v_{j})-1$

thus,

$\displaystyle\sum_{v_{j}\in V\setminus(X\cup Y)}\bar{W}_{ij}\hat{y}^{\rm
indv}_{j}(a)\geq\bar{W}_{i}(X)-\bar{W}_{i}(Y)\iff$
$\displaystyle\sum_{v_{j}\in V\setminus(X\cup Y)}\bar{W}_{ij}\hat{y}^{\rm
indv}_{j}(a)\geq\operatorname*{\mathbb{E}}\left[\sum_{v_{j}\in
V\setminus(X\cup Y)}\bar{W}_{ij}\hat{y}^{\rm
indv}_{j}(a)\right]+\left(-\operatorname*{\mathbb{E}}\left[\sum_{v_{j}\in
V\setminus(X\cup Y)}\bar{W}_{ij}\hat{y}^{\rm
indv}_{j}(a)\right]+\bar{W}_{i}(X)-\bar{W}_{i}(Y)\right)$

and

$\displaystyle-\operatorname*{\mathbb{E}}\left[\sum_{v_{j}\in V\setminus(X\cup
Y)}\bar{W}_{ij}\hat{y}^{\rm indv}_{j}(a)\right]+\bar{W}_{i}(X)-\bar{W}_{i}(Y)$
$\displaystyle=-\sum_{v_{j}\in V\setminus(X\cup
Y)}\bar{W}_{ij}[2\mathsf{err}^{\rm
indv}(v_{j})-1]+\bar{W}_{i}(X)-\bar{W}_{i}(Y)$
$\displaystyle=\Psi_{i}(X,Y)~{}.$

The rest of the proof follows similarly to the previous case. ∎

####  A.5.1 Case 1. Colorless $S_{i}$

Assume that $S_{i}\subseteq{\mathcal{W}}$,

######  Lemma A.14.

If $S_{i}\subseteq{\mathcal{W}}$ and $u\in{\mathcal{W}}$, for any arbitrary
$v_{i}$ we may take:

$\displaystyle\widehat{\Delta{\mathcal{G}}}^{\rm gr}_{i}(S,u)$
$\displaystyle=$ $\displaystyle\begin{cases}\mathsf{err}^{\rm
indv}(u)\cdot\prod_{\begin{subarray}{c}v_{j}\in S\\\ \bar{W}_{ij}\neq
0\end{subarray}}(1-\mathsf{err}^{\rm indv}(v_{j}))&\quad\text{if
}\Psi_{i}({\mathcal{R}}\cup S,{\mathcal{B}}\cup\\{u\\})<0\
\&\Psi_{i}({\mathcal{B}}\cup S,{\mathcal{R}}\cup\\{u\\})<0\\\
\mathsf{err}^{\rm indv}(u)\cdot\prod_{\begin{subarray}{c}v_{j}\in S\\\
\bar{W}_{ij}\neq 0\end{subarray}}(1-\mathsf{err}^{\rm
indv}(v_{j}))\cdot\mathsf{err}({\mathcal{R}})&\quad\text{if
}\Psi_{i}({\mathcal{R}}\cup S,{\mathcal{B}}\cup\\{u\\})>0\
\&\Psi_{i}({\mathcal{B}}\cup S,{\mathcal{R}}\cup\\{u\\})<0\\\
\mathsf{err}^{\rm indv}(u)\cdot\prod_{\begin{subarray}{c}v_{j}\in S\\\
\bar{W}_{ij}\neq 0\end{subarray}}(1-\mathsf{err}^{\rm
indv}(v_{j}))\cdot\mathsf{err}({\mathcal{B}})&\quad\text{if
}\Psi_{i}({\mathcal{R}}\cup S,{\mathcal{B}}\cup\\{u\\})<0\
\&\Psi_{i}({\mathcal{B}}\cup S,{\mathcal{R}}\cup\\{u\\})>0\\\
0&\quad\text{otherwise}\end{cases}$

and we have:

$\absolutevalue{\widehat{\Delta{\mathcal{G}}}_{i}^{\rm
gr}(S,u)-\Delta{\mathcal{G}}_{i}^{\rm
gr}(S,u)}\leq\exp\left(-\frac{(\Psi_{i}^{\mathcal{W}}(u)-\Delta\bar{W}_{i})^{2}}{4\sum_{v_{j}\in{\mathcal{W}}}\bar{W}_{ij}^{2}}\right)$

###### Proof.

$\displaystyle\operatorname*{\mathbb{P}}^{\rm
gr}_{a\sim\Omega}\left(\mathcal{Z}(i,a)\leq
0\wedge{\mathcal{T}}_{i}(S)\wedge{\mathcal{F}}(u)\right)$
$\displaystyle=\operatorname*{\mathbb{P}}^{\rm
gr}_{a\sim\Omega^{+}}\left(z(i,a)\leq
0\wedge{\mathcal{T}}_{i}(S)\wedge{\mathcal{F}}(u)\right)\mathbb{P}(a\in\Omega^{+})$
$\displaystyle\quad\quad+\operatorname*{\mathbb{P}}^{\rm
gr}_{a\sim\Omega^{-}}\left(z(i,a)\geq
0\wedge{\mathcal{T}}_{i}(S)\wedge{\mathcal{F}}(u)\right)\mathbb{P}(a\in\Omega^{-})~{}.$

We have:

$\displaystyle\operatorname*{\mathbb{P}}^{\rm
gr}_{a\sim\Omega^{+}}\left(z(i,a)\leq
0\wedge{\mathcal{T}}_{i}(S)\wedge{\mathcal{F}}(u)\right)$
$\displaystyle=\operatorname*{\mathbb{P}}^{\rm
gr}_{a\sim\Omega^{+}}\left(z(i,a)\leq
0\mid{\mathcal{T}}_{i}(S)\wedge{\mathcal{F}}(u)\right)\operatorname*{\mathbb{P}}_{a\sim\Omega^{+}}^{\rm
gr}\left({\mathcal{T}}_{i}(S)\wedge{\mathcal{F}}(u)\right)\ \&$
$\displaystyle\operatorname*{\mathbb{P}}^{\rm
gr}_{a\sim\Omega^{-}}\left(z(i,a)\leq
0\wedge{\mathcal{T}}_{i}(S)\wedge{\mathcal{F}}(u)\right)$
$\displaystyle=\operatorname*{\mathbb{P}}^{\rm
gr}_{a\sim\Omega^{-}}\left(z(i,a)\leq
0\mid{\mathcal{T}}_{i}(S)\wedge{\mathcal{F}}(u)\right)\operatorname*{\mathbb{P}}_{a\sim\Omega^{-}}^{\rm
gr}\left({\mathcal{T}}_{i}(S)\wedge{\mathcal{F}}(u)\right)$

Note that since $S\subseteq{\mathcal{W}}$ and $u\in{\mathcal{W}}$ we have:

$\operatorname*{\mathbb{P}}_{a\sim\Omega^{-}}^{\rm
gr}\left({\mathcal{T}}_{i}(S)\wedge{\mathcal{F}}(u)\right)=\operatorname*{\mathbb{P}}_{a\sim\Omega^{+}}^{\rm
gr}\left({\mathcal{T}}_{i}(S)\wedge{\mathcal{F}}(u)\right)=\mathsf{err}^{\rm
indv}(u)\cdot\prod_{\begin{subarray}{c}v_{j}\in S\\\ \bar{W}_{ij}\neq
0\end{subarray}}(1-\mathsf{err}^{\rm indv}(v_{j}))~{}.$

Furthermore,

$\displaystyle\operatorname*{\mathbb{P}}^{\rm
gr}_{a\sim\Omega^{+}}\left(z(i,a)\leq
0\mid{\mathcal{T}}_{i}(S)\wedge{\mathcal{F}}(u)\right)$ $\displaystyle=$
$\displaystyle\operatorname*{\mathbb{P}}_{a\sim\Omega^{+}}^{\rm
gr}\left(\sum_{\begin{subarray}{c}j=1:n\\\ v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}\hat{y}_{j}(a)+\sum_{v_{j}\in
S}\bar{W}_{ij}-\bar{W}_{iu}\leq 0\right)$ $\displaystyle=$
$\displaystyle\operatorname*{\mathbb{P}}_{a\sim\Omega^{+}}\left(\sum_{\begin{subarray}{c}v_{j}\in{\mathcal{W}}\\\
v_{j}\notin S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}\hat{y}^{\rm
indv}_{j}(a)+\sum_{v_{j}\in{\mathcal{R}}}\bar{W}_{ij}\hat{y}^{\rm
gr}_{j}(a)+\sum_{v_{j}\in{\mathcal{B}}}\bar{W}_{ij}\hat{y}^{\rm
gr}_{j}(a)+\sum_{v_{j}\in S}\bar{W}_{ij}-\bar{W}_{iu}\leq 0\right)$
$\displaystyle=$
$\displaystyle\operatorname*{\mathbb{P}}_{a\sim\Omega^{+}}\left(\sum_{\begin{subarray}{c}v_{j}\in{\mathcal{W}}\\\
v_{j}\notin S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}\hat{y}^{\rm
indv}_{j}(a)+\sum_{v_{j}\in{\mathcal{R}}}\bar{W}_{ij}-\sum_{v_{j}\in{\mathcal{B}}}\bar{W}_{ij}+\sum_{v_{j}\in
S}\bar{W}_{ij}-\bar{W}_{iu}\leq 0\right)\mathsf{err}({\mathcal{B}})$
$\displaystyle\quad+\operatorname*{\mathbb{P}}_{a\sim\Omega^{+}}\left(\sum_{\begin{subarray}{c}v_{j}\in{\mathcal{W}}\\\
v_{j}\notin S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}\hat{y}^{\rm
indv}_{j}(a)+\sum_{v_{j}\in{\mathcal{B}}}\bar{W}_{ij}-\sum_{v_{j}\in{\mathcal{R}}}\bar{W}_{ij}+\sum_{v_{j}\in
S}\bar{W}_{ij}-\bar{W}_{iu}\leq 0\right)\mathsf{err}({\mathcal{R}})$
$\displaystyle=$ $\displaystyle\Gamma_{i}^{+}({\mathcal{R}}\cup
S,{\mathcal{B}}\cup\\{u\\})\mathsf{err}({\mathcal{B}})+\Gamma_{i}^{+}({\mathcal{B}}\cup
S,{\mathcal{R}}\cup\\{u\\})\mathsf{err}({\mathcal{R}})~{}.$

Similarly we have that:

$\displaystyle\operatorname*{\mathbb{P}}^{\rm
gr}_{a\sim\Omega^{-}}\left(z(i,a)\geq
0\mid{\mathcal{T}}_{i}(S)\wedge{\mathcal{F}}(u)\right)$ $\displaystyle=$
$\displaystyle\operatorname*{\mathbb{P}}_{a\sim\Omega^{-}}^{\rm
gr}\left(\sum_{\begin{subarray}{c}j=1:n\\\ v_{j}\notin
S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}\hat{y}_{j}(a)-\sum_{v_{j}\in
S}\bar{W}_{ij}+\bar{W}_{iu}\geq 0\right)$ $\displaystyle=$
$\displaystyle\operatorname*{\mathbb{P}}_{a\sim\Omega^{-}}\left(\sum_{\begin{subarray}{c}v_{j}\in{\mathcal{W}}\\\
v_{j}\notin S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}\hat{y}^{\rm
indv}_{j}(a)+\sum_{v_{j}\in{\mathcal{R}}}\bar{W}_{ij}\hat{y}^{\rm
gr}_{j}(a)+\sum_{v_{j}\in{\mathcal{B}}}\bar{W}_{ij}\hat{y}^{\rm
gr}_{j}(a)-\sum_{v_{j}\in S}\bar{W}_{ij}+\bar{W}_{iu}\geq 0\right)$
$\displaystyle=$
$\displaystyle\operatorname*{\mathbb{P}}_{a\sim\Omega^{-}}\left(\sum_{\begin{subarray}{c}v_{j}\in{\mathcal{W}}\\\
v_{j}\notin S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}\hat{y}^{\rm
indv}_{j}(a)-\sum_{v_{j}\in{\mathcal{R}}}\bar{W}_{ij}+\sum_{v_{j}\in{\mathcal{B}}}\bar{W}_{ij}-\sum_{v_{j}\in
S}\bar{W}_{ij}+\bar{W}_{iu}\geq 0\right)\mathsf{err}({\mathcal{B}})$
$\displaystyle\quad+\operatorname*{\mathbb{P}}_{a\sim\Omega^{-}}\left(\sum_{\begin{subarray}{c}v_{j}\in{\mathcal{W}}\\\
v_{j}\notin S\cup\\{u\\}\end{subarray}}\bar{W}_{ij}\hat{y}^{\rm
indv}_{j}(a)-\sum_{v_{j}\in{\mathcal{B}}}\bar{W}_{ij}+\sum_{v_{j}\in{\mathcal{R}}}\bar{W}_{ij}-\sum_{v_{j}\in
S}\bar{W}_{ij}+\bar{W}_{iu}\geq 0\right)\mathsf{err}({\mathcal{R}})$
$\displaystyle=$ $\displaystyle\Gamma_{i}^{-}({\mathcal{R}}\cup
S,{\mathcal{B}}\cup\\{u\\})\mathsf{err}({\mathcal{B}})+\Gamma_{i}^{-}({\mathcal{B}}\cup
S,{\mathcal{R}}\cup\\{u\\})\mathsf{err}({\mathcal{R}})~{}.$

Therefore, $\operatorname*{\mathbb{P}}^{\rm
gr}_{a\sim\Omega}\left(\mathcal{Z}(i,a)\leq
0\wedge{\mathcal{T}}_{i}(S)\wedge{\mathcal{F}}(u)\right)$ is equal to

$\displaystyle\mathsf{err}^{\rm
indv}(u)\cdot\prod_{\begin{subarray}{c}v_{j}\in S\\\ \bar{W}_{ij}\neq
0\end{subarray}}(1-\mathsf{err}^{\rm
indv}(v_{j}))\cdot([\Gamma_{i}^{+}({\mathcal{R}}\cup
S,{\mathcal{B}}\cup\\{u\\})\mathsf{err}({\mathcal{B}})+\Gamma_{i}^{+}({\mathcal{B}}\cup
S,{\mathcal{R}}\cup\\{u\\})\mathsf{err}({\mathcal{R}})]\operatorname*{\mathbb{P}}(a\in\Omega^{+})$
$\displaystyle\quad+\ [\Gamma_{i}^{-}({\mathcal{R}}\cup
S,{\mathcal{B}}\cup\\{u\\})\mathsf{err}({\mathcal{B}})+\Gamma_{i}^{-}({\mathcal{B}}\cup
S,{\mathcal{R}}\cup\\{u\\})\mathsf{err}({\mathcal{R}})]\operatorname*{\mathbb{P}}(a\in\Omega^{-}))$

We may now employ lemma A.13 to estimate the above probabilities.

By replacing the estimations $\widehat{\Gamma}_{i}^{+}$ and
$\widehat{\Gamma}_{i}^{-}$ in the above formula we obtain:

$\displaystyle\widehat{\Delta{\mathcal{G}}}^{\rm gr}_{i}(S,u)$
$\displaystyle=$ $\displaystyle\begin{cases}\mathsf{err}^{\rm
indv}(u)\cdot\prod_{\begin{subarray}{c}v_{j}\in S\\\ \bar{W}_{ij}\neq
0\end{subarray}}(1-\mathsf{err}^{\rm indv}(v_{j}))&\quad\text{if
}\Psi_{i}({\mathcal{R}}\cup S,{\mathcal{B}}\cup\\{u\\})<0\
\&\Psi_{i}({\mathcal{B}}\cup S,{\mathcal{R}}\cup\\{u\\})<0\\\
\mathsf{err}^{\rm indv}(u)\cdot\prod_{\begin{subarray}{c}v_{j}\in S\\\
\bar{W}_{ij}\neq 0\end{subarray}}(1-\mathsf{err}^{\rm
indv}(v_{j}))\cdot\mathsf{err}({\mathcal{R}})&\quad\text{if
}\Psi_{i}({\mathcal{R}}\cup S,{\mathcal{B}}\cup\\{u\\})>0\
\&\Psi_{i}({\mathcal{B}}\cup S,{\mathcal{R}}\cup\\{u\\})<0\\\
\mathsf{err}^{\rm indv}(u)\cdot\prod_{\begin{subarray}{c}v_{j}\in S\\\
\bar{W}_{ij}\neq 0\end{subarray}}(1-\mathsf{err}^{\rm
indv}(v_{j}))\cdot\mathsf{err}({\mathcal{B}})&\quad\text{if
}\Psi_{i}({\mathcal{R}}\cup S,{\mathcal{B}}\cup\\{u\\})<0\
\&\Psi_{i}({\mathcal{B}}\cup S,{\mathcal{R}}\cup\\{u\\})>0\\\
0&\quad\text{otherwise}\end{cases}$

∎

######  Lemma A.15.