189 2022 ACML 2022

# Noise Robust Core-stable Coalitions of Hedonic Games

Prashant Trivedi<EMAIL_ADDRESS>
IEOR  Indian Institute of Technology Bombay  Nandyala Hemachandra
<EMAIL_ADDRESS>
IEOR  Indian Institute of Technology Bombay

###### Abstract

In this work, we consider the coalition formation games with an additional
component, ‘noisy preferences’. Moreover, such noisy preferences are available
only for a sample of coalitions. We propose a multiplicative noise model
(equivalent to an additive noise model) and obtain the prediction probability,
defined as the probability that the estimated PAC core-stable partition of the
_noisy_ game is also PAC core-stable for the _unknown noise-free_ game. This
prediction probability depends on the probability of a combinatorial construct
called an ‘agreement event’. We explicitly obtain the agreement probability
for $n$ agent noisy game with $l\geq 2$ support noise distribution. For a
user-given satisfaction value on this probability, we identify the noise
regimes for which an estimated partition is noise robust; that is, it is PAC
core-stable in both noisy and noise-free games. We obtain similar robustness
results when the estimated partition is not PAC core-stable. These noise
regimes correspond to the level sets of the agreement probability function and
are non-convex sets. Moreover, an important fact is that the prediction
probability can be high even if high noise values occur with a high
probability. Further, for a class of top-responsive hedonic games, we obtain
the bounds on the extra noisy samples required to get noise robustness with a
user-given satisfaction value.

We completely solve the noise robustness problem of a $2$ agent hedonic game.
In particular, we obtain the prediction probability function for $l=2$ and
$l=3$ noise support cases. For $l=2$, the prediction probability is convex in
noise probability, but the noise robust regime is non-convex. Its minimum
value, called the safety value, is 0.62; so, below 0.62, the noise robust
regime is the entire probability simplex. However, for $l\geq 3$, the
prediction probability is non-convex; so, the safety value is the global
minima of a non-convex function and is computationally hard.

###### keywords:

Prediction probability; noise regimes; combinatorial events; safety value;
non-convex optimisation; global minima; weak supervision; PAC stability;
multiplicative noise

††editors: Emtiyaz Khan and Mehmet Gönen

##  1 Introduction

Coalition formation games are of great interest to researchers because they
model natural interactions among multi-agent societies. The coalition
formation process can be formalized using the framework of hedonic games. In
these games, each agent has a preference over the coalitions they form with
the other agents. An outcome of a hedonic game consists of dividing the agent
set into disjoint coalitions called partition. Such a partition is referred to
as coalition structure. A desirable property in hedonic games is the formation
of a stable coalition structure. However, any stability notion (Bogomolnaia
and Jackson, 2002; Aziz and Savani, 2016) assumes the complete information of
each agent’s preferences, i.e., the entire ranking of coalitions by each agent
is known. This is one of the strong assumptions in hedonic games. Nonetheless,
there is significant work in finding a stable partition of the agent set, if
it exists (Brandt et al., 2016).

Authors in Sliwinski and Zick (2017) relax the assumption of complete
information and assume that the preferences over only some coalitions are
available; they introduce the notion of $\epsilon$-Probably Approximately
Correct ($\epsilon$-PAC) stability to learn the stable outcome of the hedonic
game. Apart from the assumption about the complete information, we can have
preferences corrupted by noise, i.e., the exact preferences of agents are not
available; instead, the preferences with errors are observed. We call such
observed erroneous preferences, noisy preferences. A consequence of these
noisy preferences is that a partition that is not stable in a noisy game can
be stable in a noise-free game with non-trivial probability or vice-versa.

In this work, one of our goals is to find the probability that a stable
partition learned from the observed noisy sample is the same as that of the
stable partition of the unknown noise-free game (Sec. 2). We obtain similar
results when one starts with a particular partition that is not PAC stable for
the noisy game. In such a case, we are interested in the probability that the
estimated partition is also not core-stable for a noise-free game (Sec. 3). We
call these probabilities the prediction probabilities. These prediction
probabilities depend on a probability of an event called the ‘agreement
event’. We also obtain the noise regimes where the agreement probabilities are
more than a user-given threshold.

As a motivation, let us consider a stylized model of a market for a specific
product that three manufacturers $N=\\{1,2,3\\}$ serve. Each manufacturer has
preferences, denoted by $\succ_{i},~{}\forall~{}i\in N$, over the coalitions
they want to form with other manufacturers. Based on their preferences, a
market analyst would like to predict the coalition structure that these three
manufacturers form. However, these preferences being private to manufacturers,
the market analyst collects them through a noisy channel (or estimates them
based on the market’s history). For simplicity, assume that the analyst has
noisy preferences, denoted by $\succ^{\prime}_{i},~{}\forall~{}i\in N$, of all
the agents (a complete information model) as in the game (1) below:
$\displaystyle{\color[rgb]{1,0,0}\\{12\\}\succ_{1}^{\prime}\\{1\\}}\succ_{1}^{\prime}\\{123\\}\succ_{1}^{\prime}\\{13\\}$
(1)
$\displaystyle\\{12\\}\succ_{2}^{\prime}\\{2\\}\succ_{2}^{\prime}\\{123\\}\succ_{2}^{\prime}\\{23\\}$
$\displaystyle\\{123\\}\succ_{3}^{\prime}\\{23\\}\succ_{3}^{\prime}\\{13\\}\succ_{3}^{\prime}\\{3\\}$
$\displaystyle{\color[rgb]{1,0,0}\\{1\\}\succ_{1}\\{12\\}}\succ_{1}\\{123\\}\succ_{1}\\{13\\}$
(2) $\displaystyle\\{12\\}\succ_{2}\\{2\\}\succ_{2}\\{123\\}\succ_{2}\\{23\\}$
$\displaystyle\\{123\\}\succ_{3}\\{23\\}\succ_{3}\\{13\\}\succ_{3}\\{3\\}$

The noisy core-stable partition as predicted by the market analyst is
$\tilde{\pi}=\\{\\{12\\},\\{3\\}\\}$. However, suppose the noise-free
preferences are as in game (2) (these are not known to market analyst). Based
on these noise-free preferences the unique core-stable partition is
$\pi=\\{\\{1\\},\\{2\\},\\{3\\}\\}$. So, while the market analyst concludes
that the manufacturers form a coalition based on the available noisy
preferences, they will not. Thus, the market analyst needs to know the
prediction probability, the probability that the predicted partition based on
the available noisy preferences is the same as the partition of the unknown
noise-free game in (2). An interesting phenomenon in the noisy hedonic game is
that even if the market analyst misses identifying a core-stable partition,
the market has one with non-trivial probability. We consider this in Sec. 3,
via their complimentary event.

As a generalization to the above three manufacturers’ model, we assume that a
learner has preferences over some coalitions collected via a noisy channel.
Based on these noisy preferences, the learner’s task is to predict the core-
stable partition for an unknown noise-free game based on these partial and
noisy preferences. We propose a noise model to investigate noise regimes where
the predicted noisy partition is the same as an unknown noise-free partition.
It addresses an important aspect of noise-robustness, meaning these partitions
are the same with high probability. Specifically, our major contributions are:
(a) In Sec. 2, we propose a multiplicative noise model and obtain the
prediction probability. This probability depends on a combinatorial construct
called ‘agreement event’. For a user-given value on agreement probability, we
obtain the noise regimes where an estimated partition of the noisy game is
noise-robust.
(b) In Subsec. 2.1, we obtain the lower and upper bounds on the number of
noisy samples required to get PAC stable partition for the top-responsive
class of hedonic games.
(c) In Sec. 3, we obtain the prediction probability function that a partition
$\tilde{\pi}$ is not PAC stable for the noise-free game given that it is not
PAC stable for the noisy game.
(d) In Sec. 4, we consider a noisy game with 2 agents with complete
information on each agent’s preferences. The allowable noise regimes for
noise-robustness are non-convex, even though the agreement probability is a
convex function.
(e) We now mention some observations of 2 agent game. The prediction
probability is non-convex when the noise distribution has $l\ (\geq 3)$
support. Thus, computing the safety value, i.e., the minimum prediction
probability, is computationally hard. So, for user satisfaction values below
this safety value, the prediction probability is 1, regardless of the noise
values and their probabilities. Also, the noise values that render a user
given minimum prediction probability form non-contiguous regions (superlevel
sets). A counter-intuitive fact is that the prediction probabilities can be
high for some high noise values occurring with high probability. A simple
illustration is in the 2 support case, where the prediction probability is 1
even when the value of both agents is inflated with probability 1.

###  1.1 Notations and preliminaries

This Sec. provides some notations, definitions, and other related backgrounds
that we use in the paper subsequently. Let $N=\\{1,2,\dots,n\\}$ be the set of
agents and for each agent $i\in N$, let $\mathcal{C}_{i}=\\{S\subseteq
N~{}|~{}i\in S\\}$ be the set of coalitions containing agent $i$. A hedonic
game is a pair $(N,\succeq)$, where
$\succeq=(\succeq_{1},\succeq_{2},\dots,\succeq_{n})$. Here $\succeq_{i}$ is a
reflexive, transitive, and complete preference ranking of agent $i\in N$ over
the set $\mathcal{C}_{i}$. The preference $\succeq_{i}$ of agent $i\in N$
represents its willingness to form a coalition with other agents.

For any two distinct coalitions $S,T\subseteq\mathcal{C}_{i}$ we say
$S\succ_{i}T$ if agent $i\in N$ prefers coalition $S$ over $T$. Also,
$S\sim_{i}T$ iff $S\succeq_{i}T$ and $T\succeq_{i}S$, that is agent $i$ is
indifferent to coalition $S$ and $T$. Since the preferences are reflexive,
transitive and complete there exists a value function $\textbf{{v}}:S\subseteq
N\mapsto\mathbb{R}^{|S|}$ such that $\textbf{{v}}(S)=(v_{i}(S))_{i\in S}$
111Note that $(v_{i}(S))_{i\in S}$ is a vector of size $|S|$ with each element
$v_{i}(S)$ for agent $i\in S$., where $v_{i}(S)\in\mathbb{R}^{+}$ is the
valuation of an agent $i$ in coalition $S$. For any coalitions
$S,T\in\mathcal{C}_{i}$, it satisfies that
$S\succeq_{i}T\iff{v}_{i}(S)\geq{v}_{i}(T)$ (Mas-Colell et al., 1995;
Narahari, 2014). The valuation $v_{i}(S)$ often depends on value
$v_{i}(j)\in\mathbb{R}^{+}$ of agent $j$ in the eyes of agent $i$, here
$i,j\in S$. We use $(N,\textbf{{v}})$ to denote the hedonic game.

A typical partition of the agent set in the hedonic game $(N,\textbf{{v}})$ is
denoted by $\pi$. Let the coalition containing $i\in N$ in partition $\pi$ be
$\pi(i)$. The hedonic game’s outcome is finding a ‘stable’ partition according
to some stability criterion. A partition is ‘stable’ if no agent or a group of
agents can deviate from it to reach a subjectively better outcome. Various
stability criteria are introduced in Bogomolnaia and Jackson (2002) and are
nicely reviewed by Aziz and Savani (2016). However, in this paper, we use
core, one of the popular stability criteria. A coalition $S$ core blocks a
partition $\pi$, if every agent $i$ in coalition $S$ strictly prefers $S$ to
$\pi(i)$, i.e., $S\succ_{i}\pi(i),~{}\forall~{}i\in S$. Further, a coalition
structure $\pi$ is said to be core-stable if there is no coalition that core
blocks $\pi$, meaning there is at least one agent $i\in S$ who prefers
$\pi(i)$ over $S$, i.e., $\pi(i)\succeq_{i}S$.

Recently, for a partial information hedonic game, authors in Sliwinski and
Zick (2017) have proposed the PAC learning framework to find a $\epsilon$-PAC
stable outcome for several classes of hedonic games. We briefly describe the
$\epsilon$-PAC stability framework here (Sliwinski and Zick, 2017). Given a
sample
$\mathcal{S}=\\{(S_{1},\textbf{{v}}(S_{1})),\dots,(S_{m},\textbf{{v}}(S_{m}))\\}$,
where $S_{1},S_{2},\dots,S_{m}$ are drawn i.i.d. from a distribution over
$2^{N}$ and the corresponding values v’s are obtained from $\mathcal{D}$. An
algorithm $\mathcal{A}$ is said to PAC stabilize a class $\mathcal{H}$ of
hedonic games if for any hedonic game $(N,\textbf{{v}})\in\mathcal{H}$, after
seeing examples in $\mathcal{S}$ it can propose a partition $\pi$ that is
unlikely to be core blocked by a coalition sampled from $\mathcal{D}$ with
high probability. Formally, for any error and the confidence parameter
$\epsilon,\delta>0$, a partition $\pi$ is $\epsilon$-PAC stable under
$\mathcal{D}$ if $\mathcal{A}$ outputs a $\epsilon$-PAC stable coalition
structure or reports that the core is empty, i.e.,

$\mathbb{P}_{\mathcal{S}}[\mathbb{P}_{T\sim\mathcal{D}}[T~{}\text{{core
blocks}}~{}\pi\text{{ in noise-free game }}(N,\textbf{{v}})]<\epsilon]\geq
1-\delta,$ (3)

here, the number of samples $m$ are required to be polynomial in
$n,\frac{1}{\epsilon}~{}\text{and}\log\frac{1}{\delta}$.

As mentioned above, the $\epsilon$-PAC stability notion assumes the correct
preferences over the sample of coalitions. However, it is not the case in most
realistic scenarios. Often the preferences are erroneous, i.e., corrupted by
noise. In this work, we relax both the assumptions of correct and complete
knowledge of the preferences. Let the value of each agent in any coalition be
corrupted by an unknown noise distribution, $\mathcal{N}$. We denote the
complete, reflexive and transitive noisy preferences by
$\succeq^{\prime}=(\succeq_{1}^{\prime},\succeq_{2}^{\prime},\dots,\succeq_{n}^{\prime})$.
The noisy hedonic game is therefore represented by $(N,\succeq^{\prime})$ or
equivalently $(N,\tilde{\textbf{{v}}})$, where
$\tilde{\textbf{{v}}}(S)=(\tilde{v}_{i}(S))_{i\in S}$ is such that
$\tilde{v}_{i}(S)\in\mathbb{R}^{+}$. Formally, we are given a sample
$\mathcal{\tilde{S}}=\\{(S_{1},\tilde{\textbf{{v}}}(S_{1})),\dots,(S_{\tilde{m}},\tilde{\textbf{{v}}}(S_{\tilde{m}}))\\}$
from the noisy hedonic game $(N,\tilde{\textbf{{v}}})$. Here
$S_{1},S_{2},\dots,S_{m}$ are drawn i.i.d. from a distribution over $2^{N}$
and the corresponding values $\tilde{\textbf{{v}}}$’s are obtained from
$\mathcal{\widetilde{D}}$. So, we can find a $\tilde{\epsilon}$-PAC stable
partition (this can be done by using an algorithm similar to one given in say,
Sliwinski and Zick (2017); Alcalde and Revilla (2004)) if it exists. Let
$\tilde{\pi}$ be an $\tilde{\epsilon}$-PAC stable partition of the noisy
hedonic game, i.e., with probability at least $1-\delta$, we have,

$\mathbb{P}_{\tilde{\mathcal{S}}}[\mathbb{P}_{T\sim\mathcal{\widetilde{D}}}[T~{}\text{{core
blocks}}~{}\tilde{\pi}\text{{ in noisy game
}}(N,\tilde{\textbf{{v}}})]<\tilde{\epsilon}]\geq 1-\delta.$ (4)

Again, the number of samples required are $\tilde{m}$ which is polynomial in
$n,\frac{1}{\tilde{\epsilon}}$, and $\log\frac{1}{\delta}$. The entire paper
uses the inner probability given in Equation (3) for the noisy game. However,
for the noise-free game, we are interested in the probability given in
Equation (5) below. This is because we only have samples from the noisy game;
hence, the outer probability is taken on noisy samples for noisy and noise-
free games.

Let $\alpha_{i}(S)\sim\mathcal{N}$ be the noise realized to an agent $i\in
S\subseteq N$. We assume that for each agent $i\in S$, the noise is the same,
i.e., $\alpha_{i}(S)=\alpha(S)\in\mathbb{R}^{+},~{}\forall~{}i\in S$. To
ensure noise distribution support, $\mathcal{N}_{sp}$ is non-empty we assume
that it contains $1$ and other noise values. So, the noisy value is
$\tilde{v}_{i}(S)\coloneqq\alpha(S)\cdot v_{i}(S),~{}\forall~{}i\in S\subseteq
N$. We call this noise model the multiplicative noise model; this is
equivalent to the additive noise model as given in Remark 1.3 below. In
Sections 2.2, and 3.1, we also consider scaling at various levels by taking
$l\geq 2$ support on the noise distribution (the same level for all members of
a given coalition). Another motivation for the same noise level scaling for
each agent in the coalition is the following: A learner is collecting the
valuation of each coalition via a noisy channel. So, we assume that a noisy
channel affects the value of the entire coalition by the same amount. Hence,
each agent in a coalition will have the same noise impact, irrespective of its
identity. However, suppose an agent $i$ is a member of two coalitions
$S,T\in\mathcal{C}_{i}$. The noise valuation of agent $i$ in coalition $S$ is
$\alpha(S)v_{i}(S)$, and $\alpha(T)v_{i}(T)$ in coalition $T$, so, we also
have different noise values for the same agent depending on the coalition.
Moreover, the assumption of common scaling $\alpha(S)$ is necessary to carry
out the Probably Approximately Correct (PAC) analysis. The PAC stability
definition uses a hypothesis class, in our case, the class of hedonic games.
The common $\alpha(S)$ preserves the class of hedonic games under noise, which
need not be the case when we scale the value of each coalition at the
individual agent level. For example, if the noise-free game belongs to the
class of additively separable hedonic games (ASHGs), the noisy game with agent
dependent noise scaling $\alpha_{i}(S),~{}\forall~{}i\in S$ may not be ASHG,
but it is within ASHG class with common noise scaling $\alpha(S)$. So, we use
a common scaling that restricts noisy and noise-free games to the same class.
We believe this assumption can be relaxed by taking the larger class of
hedonic games; however, we might need additional conditions to ensure the
class-preserving property.

It is important to note that our noisy hedonic game setup can be reduced to
the noise-free setup in a very specialized setting, i.e., only if
$\alpha(S)=1$ for all coalitions $S$.

Suppose $\tilde{\pi}$ is any partition of the noisy game
$(N,\tilde{\textbf{{v}}})$. We aim to find the probability that any
$T\sim\mathcal{\widetilde{D}}$ core blocks $\tilde{\pi}$ in the noise-free
game $(N,\textbf{{v}})$, i.e.,

$\mathbb{P}_{T\sim\tilde{\mathcal{D}}}[T~{}\text{{core
blocks}}~{}\tilde{\pi}\text{{ in noise-free game }}(N,\textbf{{v}})].$ (5)

We call the above probability, prediction probability. In each case, i.e.,
when $\tilde{\pi}$ is $\tilde{\epsilon}$-PAC stable partition of the noisy
game or not, we bound these prediction probability in Sections 2 and 3,
respectively. Prediction probability is a performance measure associated with
noise robustness, as defined below:

######  Definition 1.1 ($\zeta$ noise-robust core-stable partition
$\tilde{\pi}$).

A partition $\tilde{\pi}$ is $\zeta$ noise-robust core-stable partition if (a)
$\tilde{\pi}$ is $\tilde{\epsilon}$-PAC stable partition of noisy game
$(N,\tilde{\textbf{{v}}})$, and (b) prediction probability in Equation (5) is
less than $\epsilon$, where $\epsilon=1-(1-\tilde{\epsilon})\zeta$ with
$\zeta\in(0,1]$.

######  Definition 1.2 ($\eta$ noise-robust non core-stable partition
$\tilde{\pi}$).

A partition $\tilde{\pi}$ is $\eta$ noise-robust non core-stable partition if
(a) $\tilde{\pi}$ is not $\tilde{\epsilon}$-PAC stable partition of noisy game
$(N,\tilde{\textbf{{v}}})$ and (b) prediction probability in Equation (5) is
more than $1-\epsilon$, where $\epsilon=1-(1-\tilde{\epsilon})\eta$ with
$\eta\in(0,1]$.

######  Remark 1.3.

Additive noise model: Our noise model is a fairly generic one. For example, if
the noise is additive, i.e., $\tilde{v}_{i}(S)=\alpha(S)+v_{i}(S)$ then,
taking exponential on both sides, we have
$e^{\tilde{v}_{i}(S)}=e^{\alpha(S)+v_{i}(S)}=e^{\alpha(S)}\cdot e^{v_{i}(S)}$.
With $\tilde{V}_{i}(S)=e^{\tilde{v}_{i}(S)}$, $\Gamma(S)=e^{\alpha(S)}$, and
$V_{i}(S)=e^{v_{i}(S)}$, we have $\tilde{V}_{i}(S)=\Gamma(S)V_{i}(S)$. Hence,
for robustness to an additive noise model, one can reduce it to a noisy
hedonic game $(N,\widetilde{\textbf{{V}}})$ with multiplicative noise
$\Gamma(S)$.

######  Remark 1.4.

Note that in Equation (5) we use noise-free values v’s to check whether a
coalition can potentially block a given noisy core-stable partition
$\tilde{\pi}$. However, we only have samples from the noisy game, so we use
$T\sim\mathcal{\widetilde{D}}$ instead of $T\sim\mathcal{D}$.

##  2 Partial information noisy game with $\tilde{\pi}$ as
$\tilde{\epsilon}$-PAC stable partition

Let
$\mathcal{\tilde{S}}=\\{(S_{1},\tilde{\textbf{{v}}}(S_{1}),\dots,(S_{\tilde{m}},\tilde{\textbf{{v}}}(S_{\tilde{m}}))\\}$
be a sample of coalitions drawn i.i.d from the distribution
$\mathcal{\widetilde{D}}=\mathcal{D}\times\mathcal{N}$ over $2^{N}$. Let
$\tilde{\pi}$ be $\tilde{\epsilon}$-PAC stable outcome of noisy game
$(N,\tilde{\textbf{{v}}})$. Therefore, with probability at least $1-\delta$,
$\forall~{}\tilde{\epsilon}>0$, we have

$\displaystyle\mathbb{P}_{T\sim\mathcal{\widetilde{D}}}[T~{}core~{}blocks~{}\tilde{\pi}]<\tilde{\epsilon},~{}~{}or\hskip
8.53581pt\mathbb{P}_{T\sim\tilde{\mathcal{D}}}[\tilde{v}_{i}(T)>\tilde{v}_{i}(\tilde{\pi}(i)),~{}~{}\forall~{}i\in
T]$ $\displaystyle<\tilde{\epsilon},$ (6) $\displaystyle or\hskip
8.53581pt\mathbb{P}_{T\sim\tilde{\mathcal{D}}}[\cup_{i\in
T}~{}~{}\tilde{v}_{i}(\tilde{\pi}(i))\geq\tilde{v}_{i}(T)]$ $\displaystyle\geq
1-\tilde{\epsilon}.$

For an unknown noise-free hedonic game $(N,\textbf{{v}})$, we now find the
prediction probability given in Equation (5). To this end, we first define set
$\mathcal{R}(T)$ for any coalition $T$ as
$\mathcal{R}(T)\coloneqq\\{\tilde{\pi}(i)\in\tilde{\pi}~{}|~{}i\in T\\}$,
i.e., for all agents $i\in T$, it is the set of all coalitions containing
agent $i$ in the partition $\tilde{\pi}$. Moreover, for any coalition $T$, and
partition $\tilde{\pi}$, we define an agreement event $M(\tilde{\pi},T)$
containing the set of all noise levels $\alpha(\tilde{\pi}(i))$ and
$\alpha(T)$ such that all the coalitions $\tilde{\pi}(i)\in\mathcal{R}(T)$ are
preferred over coalition $T$ by every agent $i\in T$ in both noisy and noise-
free game. Formally, it is defined as

$M(\tilde{\pi},T)\coloneqq\\{(\\{\alpha(\tilde{\pi}(i))\\}_{\tilde{\pi}(i)\in\mathcal{R}(T)},\alpha(T)):\cap_{i\in
T}\\{v_{i}(\tilde{\pi}(i))\geq
v_{i}(T)~{}\cap~{}\alpha(\tilde{\pi}(i)){v}_{i}(\tilde{\pi}(i))\geq\alpha(T){v}_{i}(T)\\}\\}.$

Let
$f_{T}(\textbf{{p}},\boldsymbol{\alpha})\coloneqq\mathbb{P}_{T\sim\mathcal{\widetilde{D}}}[M(\tilde{\pi},T)]$
be the probability of agreement event $M(\tilde{\pi},T)$, where p is the
probability mass function of noise values $\boldsymbol{\alpha}$ 222Here
$\boldsymbol{\alpha}$ contains all possible noise values, and p is the
probability mass function of noise values in $\boldsymbol{\alpha}$.. Note that
$M(\tilde{\pi},T)$ is not known, since the noise-free values $v_{i}(T)$ and
$v_{i}(\tilde{\pi}(i))$ are not known. However, for $l\geq 2$ support noise
distribution we obtain explicit expressions for
$f_{T}(\textbf{{p}},\boldsymbol{\alpha})$ in Sec. 2.2. We also use
$f_{T}(\textbf{{p}},\boldsymbol{\alpha})$ later as user satisfaction value.
The following Theorem gives probability that unknown noise-free game
$(N,\textbf{{v}})$ has $\tilde{\pi}$ as $\epsilon$-PAC stable partition
($\epsilon$ is identified in the Theorem 2.1 below in terms of
$\textbf{{p}},\boldsymbol{\alpha}$ and $\tilde{\epsilon}$) if noisy game
$(N,\tilde{\textbf{{v}}})$ has $\tilde{\pi}$ as $\tilde{\epsilon}$-PAC stable
partition.

######  Theorem 2.1.

Let $\tilde{\pi}$ be $\tilde{\epsilon}$-PAC stable outcome of the noisy game
$(N,\tilde{\textbf{{v}}})$. Then, $\tilde{\pi}$ is $\epsilon$-PAC stable for
noise-free game $(N,\textbf{{v}})$, i.e.,
$\mathbb{P}_{T\sim\tilde{\mathcal{D}}}[\cup_{i\in
T}~{}~{}v_{i}(\tilde{\pi}(i))\geq v_{i}(T)]\geq 1-\epsilon$, where
$\epsilon>0$ satisfies
$(1-\tilde{\epsilon})f_{T}(\textbf{p},\boldsymbol{\alpha})=1-\epsilon$ with
$f_{T}(\textbf{p},\boldsymbol{\alpha})=\mathbb{P}[M(\tilde{\pi},T)]$.

######  Proof 2.2.

Consider the following probability

$\displaystyle\mathbb{P}_{T\sim\tilde{\mathcal{D}}}[\cup_{i\in
T}~{}v_{i}(\tilde{\pi}(i))\geq v_{i}(T)]$
$\displaystyle\geq\mathbb{P}_{T\sim\mathcal{\widetilde{D}}}[\cup_{i\in
T}v_{i}(\tilde{\pi}(i))\geq v_{i}(T)|\cup_{j\in
T}\tilde{v}_{j}(\tilde{\pi}(j))\geq\tilde{v}_{j}(T)]$
$\displaystyle~{}~{}~{}~{}~{}\times~{}\mathbb{P}_{T\sim\mathcal{\widetilde{D}}}[\cup_{j\in
T}\tilde{v}_{j}(\tilde{\pi}(j))\geq\tilde{v}_{j}(T)]$
$\displaystyle\geq(1-\tilde{\epsilon})\mathbb{P}_{T\sim\mathcal{\widetilde{D}}}[\cup_{i\in
T}v_{i}(\tilde{\pi}(i))\geq v_{i}(T)|\cup_{j\in
T}\tilde{v}_{j}(\tilde{\pi}(j))\geq\tilde{v}_{j}(T)]$
$\displaystyle\geq(1-\tilde{\epsilon})\mathbb{P}[(\cup_{i\in
T}v_{i}(\tilde{\pi}(i))\geq v_{i}(T))\cap(\cup_{j\in
T}\tilde{v}_{j}(\tilde{\pi}(j))\geq\tilde{v}_{j}(T))]$
$\displaystyle~{}~{}~{}~{}~{}(\because\mathbb{P}(A|B)\geq\mathbb{P}(A\cap B))$
$\displaystyle=(1-\tilde{\epsilon})\mathbb{P}[\cup_{j\in T}\cup_{i\in
T}\\{v_{i}(\tilde{\pi}(i))\geq
v_{i}(T)\cap\tilde{v}_{j}(\tilde{\pi}(j))\geq\tilde{v}_{j}(T)\\}]$
$\displaystyle\geq(1-\tilde{\epsilon})\mathbb{P}[\cap_{i\in
T}\\{v_{i}(\tilde{\pi}(i))\geq
v_{i}(T)\cap\tilde{v}_{i}(\tilde{\pi}(i))\geq\tilde{v}_{i}(T)\\}]$
$\displaystyle=(1-\tilde{\epsilon})\mathbb{P}[M(\tilde{\pi},T)]=(1-\tilde{\epsilon})f_{T}(\textit{{p}},\boldsymbol{\alpha})=1-\epsilon.$

This ends the proof.

In Theorem 2.1, we have
$(1-\tilde{\epsilon})f_{T}(\textit{{p}},\boldsymbol{\alpha})=1-\epsilon$ for
any $\tilde{\epsilon}>0$. This implies
$\epsilon=1-(1-\tilde{\epsilon})f_{T}(\textit{{p}},\boldsymbol{\alpha})=\tilde{\epsilon}$
if $f_{T}(\textit{{p}},\boldsymbol{\alpha})=1$. So, for an arbitrary
$\epsilon>0$, we have arbitrary $\tilde{\epsilon}>0$ if
$f_{T}(\textit{{p}},\boldsymbol{\alpha})=1$. However, it is not true even in
the $l=2$ support noise model. For example, as we see in Sec. A.1 of the
Appendix that we have $f_{T}(p,\alpha)=1$ iff $p=0$ or $p=1$, i.e., when
values of all the coalitions are either scaled by some scalar $\alpha>1$, or
they are retained. Therefore, we relax the requirement of
$f_{T}(\textit{{p}},\boldsymbol{\alpha})=1$, and ask for
$f_{T}(\textit{{p}},\boldsymbol{\alpha})=\zeta$ for user-given $\zeta$. In
some situations, the $\zeta$ captures the satisfaction value of an external
agent trying to predict the partition of a noise-free game without having its
knowledge. That is, a higher $\zeta$ is preferred. In particular, if
$\zeta=1$, we have $\epsilon=\tilde{\epsilon}$.

######  Theorem 2.3.

If a partition $\tilde{\pi}$ is $\tilde{\epsilon}$-PAC stable for the noisy
game $(N,\tilde{\textbf{{v}}})$ and for $\epsilon=1-(1-\tilde{\epsilon})\zeta$
it is $\epsilon$-PAC stable for the noise-free game $(N,\textbf{{v}})$, then
it is also $\zeta$ noise-robust core-stable.

######  Proof 2.4.

Recall, from Theorem 2.1, we have
$\mathbb{P}[T~{}core~{}blocks~{}\tilde{\pi}~{}for~{}(N,\textbf{{v}})]\leq\epsilon$.
Here $\epsilon=1-(1-\tilde{\epsilon})f_{T}(\textbf{{p}},\boldsymbol{\alpha})$.
Setting $f_{T}(\textbf{{p}},\boldsymbol{\alpha})=\zeta$, we have
$\epsilon=1-(1-\tilde{\epsilon})\zeta=1-\zeta+\tilde{\epsilon}\zeta$. So, for
this $\epsilon$, the partition $\tilde{\pi}$ is $\zeta$ noise-robust core-
stable from Definition 1.1.

The agreement probability $f_{T}(\textit{{p}},\boldsymbol{\alpha})$ being the
same as user-given satisfaction value $\zeta$ identifies the noise regimes
$I^{\star}(T,\zeta)$ for which at least the $\zeta$ fraction of preferences
are preserved. The following Theorem shows that the noise-regime for which a
partition $\tilde{\pi}$ is core-stable in both noisy and noise-free games with
a user-given satisfaction value $\zeta$ is indeed non-empty.

######  Theorem 2.5.

Let $\tilde{\pi}$ be $\tilde{\epsilon}$-PAC stable partition of noisy game
$(N,\tilde{\textbf{{v}}})$ and it is $\epsilon$-PAC stable for noise-free game
$(N,\textbf{{v}})$. Then, for a sample
$\mathcal{S}_{t}=\\{T_{1},\dots,T_{m_{t}}\\}$ drawn i.i.d. from
$\mathcal{\widetilde{D}}$ we obtain a non-empty noise regime
$I^{\star}(\mathcal{S}_{t},\zeta)=\cap_{i=1}^{m_{t}}I^{\star}(T_{i},\zeta)$
for which $\tilde{\pi}$ is $\zeta$ noise-robust core-stable partition.
Moreover, $\tilde{\pi}$ is $\zeta$ noise-robust core-stable partition for the
noise regime $I^{\star}(\zeta)=\cap_{T\subseteq N}I^{\star}(T,\zeta)$.

######  Proof 2.6.

For any coalition $T$, we first note that $I^{\star}(T,\zeta)\neq\emptyset$,
because
$\alpha(\tilde{\pi}(i))=1,~{}\forall\tilde{\pi}(i)\in\mathcal{R}(T);~{}\alpha(T)=1$
is always an element of $M(\tilde{\pi},T)$. So, for
$\mathcal{S}_{t}=\\{T_{1},\dots,T_{m_{t}}\\}$ we have non-empty noise regimes
$I^{\star}(T_{1},\zeta),\cdots,I^{\star}(T_{\tilde{m}_{t}},\zeta)$. Also,
$\alpha(S)=1,~{}\forall~{}S\subseteq N$ is a common element of each
$I^{\star}(T,\zeta),~{}\forall~{}T\in\mathcal{S}_{t}$. Therefore,
$I^{\star}(\mathcal{S}_{t},\zeta)=\cap_{i=1}^{m_{t}}I^{\star}(T_{i},\zeta)\neq\emptyset$,
i.e., is non-empty. Hence, partition $\tilde{\pi}$ is $\zeta$ noise robust on
the sample $\mathcal{S}_{t}$ with noise regime $I^{*}(\mathcal{S}_{t},\zeta)$
in accordance to Theorem 2.1 and Definition 1.1. Moreover,
$I^{\star}(\zeta)\neq\emptyset$ because of the same reason as mentioned above.
The $\zeta$ noise-robustness follows from Theorem 2.1 and 2.3.

In the next Section, we provide the relation between $m$, and $\tilde{m}$,
i.e., the number of samples used to get $\epsilon$ and $\tilde{\epsilon}$-PAC
stable partition $\tilde{\pi}$ in noise-free and noisy game, respectively for
top-responsive hedonic games (Alcalde and Revilla, 2004) and other hedonic
games.

###  2.1 Sample size for top-responsive and other games

In a top-responsive game, the value of each agent in a given coalition depends
on the most preferred sub-coalition. Formally, the top-responsive games are
described via choice sets $Ch(i,S)$, defined as $Ch(i,S)\coloneqq\\{X\subseteq
S:\forall~{}Y\subseteq S,i\in Y:X\succeq_{i}Y\\}$. The game satisfies the top-
responsiveness if (a) $\forall~{}i\in N$, and
$S\in\mathcal{C}_{i},|Ch(i,S)|=1$, and (b) $\forall~{}i\in N$, and
$S,T\in\mathcal{C}_{i}$ if $Ch(i,S)\succ_{i}Ch(i,T)$ then $S\succ_{i}T$ or if
$Ch(i,S)=Ch(i,T)$, and $S\subset T$, then $S\succ_{i}T$.

######  Theorem 2.7.

For a top-responsive game, let $\tilde{m}$ be the number of samples required
to get $\tilde{\epsilon}$-PAC stable partition in noisy game
$(N,\tilde{\textbf{{v}}})$, and $m$ be the samples required for $\tilde{\pi}$
to be $\epsilon$-PAC partition in unknown noise-free game $(N,\textbf{{v}})$.
Then $m\zeta\leq\tilde{m}\leq
m+(2n^{3}+2n^{4})\left(\frac{(1-\tilde{\epsilon})+\tilde{\epsilon}\zeta}{\tilde{\epsilon}(1+\tilde{\epsilon}\zeta)}\log\frac{2n^{3}}{\delta}\right).$

######  Proof 2.8.

Recall, to get $\tilde{\epsilon}$-PAC stable partition in the noisy top-
responsive games authors in (Sliwinski and Zick, 2017) provide $\tilde{m}$ for
top-responsive games as
$\tilde{m}=(2n^{3}+2n^{4})\left(\frac{1}{\tilde{\epsilon}}\log\frac{2n^{3}}{\delta}\right)$.
However, from Theorem 2.1 we have $(1-\tilde{\epsilon})\zeta=1-\epsilon$, this
implies $\epsilon=(1-\zeta)+\zeta\tilde{\epsilon}\geq\zeta\tilde{\epsilon}$.
Thus, for $\epsilon$-PAC stability of partition $\tilde{\pi}$ in a top-
responsive noise-free game the number of samples $m$ are given by
$m=(2n^{3}+2n^{4})\left(\frac{1}{\epsilon}\log\frac{2n^{3}}{\delta}\right)\leq(2n^{3}+2n^{4})\left(\frac{1}{\zeta\tilde{\epsilon}}\log\frac{2n^{3}}{\delta}\right)=\frac{\tilde{m}}{\zeta}$.
This gives an upper bound. For a lower bound, again consider
$(1-\tilde{\epsilon})\zeta=1-\epsilon$, therefore we have
$\epsilon=(1-\zeta)+\zeta\tilde{\epsilon}\leq 1+\zeta\tilde{\epsilon}$. That
is $\frac{1}{\epsilon}\geq\frac{1}{1+\zeta\tilde{\epsilon}}$. Thus, we have

$\displaystyle m$
$\displaystyle=(2n^{3}+2n^{4})\left(\frac{1}{\epsilon}\log\frac{2n^{3}}{\delta}\right)\geq(2n^{3}+2n^{4})\left(\frac{1}{1+\zeta\tilde{\epsilon}}\log\frac{2n^{3}}{\delta}\right)$
$\displaystyle=(2n^{3}+2n^{4})\left(\left\\{\frac{1}{\tilde{\epsilon}}-\frac{(1-\tilde{\epsilon})+\tilde{\epsilon}\zeta}{\tilde{\epsilon}(1+\tilde{\epsilon}\zeta)}\right\\}\log\frac{2n^{3}}{\delta}\right)=\tilde{m}-(2n^{3}+2n^{4})\left(\frac{(1-\tilde{\epsilon})+\tilde{\epsilon}\zeta}{\tilde{\epsilon}(1+\tilde{\epsilon}\zeta)}\log\frac{2n^{3}}{\delta}\right).$

From the lower and upper bounds, we have the result.

The above Theorem gives a bound on the extra samples required to get
$\epsilon$-PAC stable partition of the unknown noise-free game given
$\tilde{\epsilon}$-PAC stable partition of the noisy game. Again the number of
samples to get $\epsilon=(1-(1-\tilde{\epsilon})\zeta)$-PAC stable outcome in
an unknown noise-free game are bounded by the number of samples $\tilde{m}$,
the satisfaction value $\zeta$, and the confidence parameter $\delta$. In
particular, the number of samples $m$ are polynomial in
$n,\frac{1}{\epsilon},\log\left(\frac{1}{\delta}\right)$, but its upper bound
is non-linear in $\zeta$.

We next relate the number of samples and errors in noisy and unknown noise-
free games. Let $\tilde{\pi}$ be $\tilde{\epsilon}$-PAC stable partition of
noisy game when $\tilde{m}$ samples are used. Suppose, we get
$(\tilde{\epsilon}-\tilde{\epsilon}^{\prime})$-PAC partition of the noisy game
on increasing the noisy samples to $\tilde{m}+\tilde{m}^{\prime}$. Let
$\tilde{\pi}$ be $(\tilde{\epsilon}-\tilde{\epsilon}^{\prime})$-PAC stable for
the noisy game that uses $\tilde{m}+\tilde{m}^{\prime}$ samples. Let
$\epsilon_{new}$ be the error incurred to get $\tilde{\pi}$ partition with
$\tilde{m}+\tilde{m}^{\prime}$ samples in a given noise-free game, then
$\epsilon_{new}=1-(1-(\tilde{\epsilon}-\tilde{\epsilon}^{\prime}))f_{T}(\textit{{p}},\boldsymbol{\alpha})=1-(1-\tilde{\epsilon})f_{T}(\textit{{p}},\boldsymbol{\alpha})-\tilde{\epsilon}^{\prime}f_{T}(\textit{{p}},\boldsymbol{\alpha})=\epsilon-\tilde{\epsilon}^{\prime}f_{T}(\textit{{p}},\boldsymbol{\alpha})\leq\epsilon$.

######  Theorem 2.9.

For an unknown noise-free game, let $\tilde{\pi}$ be $\epsilon_{new}$-PAC
stable partition with $\tilde{m}+\tilde{m}^{\prime}$ noisy samples, and it is
$\epsilon$-PAC stable partition with $\tilde{m}$ noisy samples, then
$\epsilon_{new}\leq\epsilon$.

######  Remark 2.10.

The results of Theorem 2.7 and Theorem 2.9 can be generalized to any class of
hedonic games by suitably obtaining the sample complexity of that class. This
is because the number of samples required in noise-free game is function of
$n,\frac{1}{\epsilon},\log\left(\frac{1}{\delta}\right)$.

To get some more insights we next identify the agreement probability
$f_{T}(\textbf{{p}},\boldsymbol{\alpha})$ defined for partial information
noise model with $l\geq 2$ noise support in the following subsection. We use
the base case of $l=2$ noise support case in the proofs of results in the next
Section. these are deferred to Sec. A.1 of the Appendix.

###  2.2 $n$ agent $l$ support partial information noisy game

We now consider the $l\geq 2$ support case, i.e.,
$\mathcal{N}_{sp}=\\{\alpha_{1},\alpha_{2},\ldots,\alpha_{l}\\}$ with
respective probabilities $p_{1},p_{2},\ldots,p_{l}$, and
$\sum_{j\in[l]}p_{j}=1$. Here $p_{j}=\mathbb{P}(\alpha(S)=\alpha_{j})$ and
$\alpha_{j}>0,~{}\forall~{}j\in[l]$. Moreover, without loss of generality we
assume that $\alpha_{i}<\alpha_{j},~{}\forall~{}i<j$. For above noise support
the following Theorem give expression of
$f_{T}(\textit{{p}},\boldsymbol{\alpha})$. To this end, for any coalition $T$
and for all $r,s$ such that $\alpha_{r}>\alpha_{s}$, define
$\mathcal{I}(\alpha_{r},\alpha_{s},T)=\left\\{\tilde{\pi}(i)\in\mathcal{R}(T)~{}\bigg{|}~{}\frac{\tilde{v}_{i}(\tilde{\pi}(i))}{\tilde{v}_{i}(T)}\geq\frac{\alpha_{r}}{\alpha_{s}}\right\\}$.

######  Theorem 2.11.

Let $\tilde{\pi}$ be a $\tilde{\epsilon}$-PAC stable outcome of the noisy game
$(N,\tilde{\textbf{{v}}})$ and let $\tilde{\pi}$ be a $\epsilon$-PAC stable
outcome of noise-free game $(N,\tilde{\textbf{{v}}})$, where $\epsilon$ is
identified as in Theorem 2.1. Then for noise support
$\mathcal{N}_{sp}=\\{\alpha_{1},\alpha_{2},\dots,\alpha_{l}\\}$, the
$f_{T}(\textbf{p},\boldsymbol{\alpha})$ is given by:

$f_{T}(\textit{{p}},\boldsymbol{\alpha})=\begin{cases}1,\hfill
if~{}\tilde{\pi}(i)=T,~{}\forall~{}i\in T,\\\
\sum_{r,s\in[l]:\alpha_{r}>\alpha_{s}}p_{s}^{|\mathcal{R}(T)|-|\mathcal{I}(\alpha_{r},\alpha_{s},T)|+1}\times\\{(p_{r}+p_{s})^{|\mathcal{I}(\alpha_{r},\alpha_{s},T)|}-p_{s}^{|\mathcal{I}(\alpha_{r},\alpha_{s},T)|}\\}\\\
+\sum_{a=1}^{l}p_{a}\left(\sum_{b=1}^{a}p_{b}\right)^{|\mathcal{R}(T)|},\hfill
otherwise.\end{cases}$

The proof uses the principle of Mathematical induction on noise support $l\geq
2$ with base case of $l=2$ support (Lemma A.2 of the SM). The detailed proof
is available in Appendix A.

######  Remark 2.12.

If we allow $f_{T}(\textbf{p},\boldsymbol{\alpha})=\zeta$ for all coalitions
$T\subseteq N$ for some user-given satisfaction value $\zeta$, we have noise
set $I^{\star}(\zeta)$ in accordance to Theorem 2.5. This noise set
corresponds to the superlevel sets of the prediction probability function. For
this super level set the partition $\tilde{\pi}$ is $\zeta$ noise-robust core-
stable. Later, Sec. 4 shows that these superlevel sets are non-convex by
explicitly deriving the prediction probability.

##  3 Partial information noisy game when $\tilde{\pi}$ is not
$\tilde{\epsilon}$-PAC stable partition

So far we have assumed that $\tilde{\pi}$ is $\tilde{\epsilon}$-PAC stable
partition of the noisy game $(N,\tilde{\textbf{{v}}})$; however, that is not
always the case. For example $\tilde{\pi}=\\{\\{1\\},\\{23\\}\\}$ is not core
stable for the game in (1). In this section, we consider the other case where
an estimated partition $\tilde{\pi}$ is not $\tilde{\epsilon}$-PAC stable for
the noisy game $(N,\tilde{\textbf{{v}}})$. Note that $\tilde{\pi}$ not being
$\tilde{\epsilon}$-PAC stable doesn’t mean that the noisy game
$(N,\tilde{\textbf{{v}}})$ has no stable partition. Given a sample
$\mathcal{\tilde{S}}$, we say $\tilde{\pi}$ is not $\tilde{\epsilon}$-PAC
stable partition of noisy game $(N,\tilde{\textbf{{v}}})$ if there is a
coalition $T$ that core blocks it with probability at least
$1-\tilde{\epsilon}$. Formally,
$\forall~{}\tilde{\epsilon}>0,~{}\exists~{}T\sim\mathcal{\widetilde{D}}$, such
that

$\mathbb{P}[\cap_{i\in
T}~{}~{}\tilde{v}_{i}(T)>\tilde{v}_{i}(\tilde{\pi}(i))]\geq
1-\tilde{\epsilon}.$ (7)

Our interest is in finding the prediction probability (Equation (5)) that a
noise-free game does not have $\tilde{\pi}$ as $\epsilon$-PAC stable outcome
($\epsilon$ to be identified in terms of $\tilde{\epsilon}$) when the noisy
game does not have $\tilde{\pi}$ as $\tilde{\epsilon}$-PAC stable partition.
To this end, for any coalition $T$, we again define an agreement event
$F(T,\tilde{\pi})$ 333 Though we use the same names, the agreement event in
Sec. 2 is different from this agreement event.. It contains all the noise
values
$(\alpha(T),\\{\alpha(\tilde{\pi}(i)))\\}_{\tilde{\pi}\in\mathcal{R}(T)})$
such that coalition $T$ is preferred over all the coalitions
$\tilde{\pi}(i)\in\mathcal{R}(T)$ by every agent $i\in T$ in both the noisy
and noise-free games. Formally,

$F(T,\tilde{\pi})\coloneqq\\{(\alpha(T),\\{\alpha(\tilde{\pi}(i))\\}_{\tilde{\pi}(i)\in\mathcal{R}(T)}):\cap_{i\in
T}\\{v_{i}(T)\geq
v_{i}(\tilde{\pi}(i))\cap\alpha(T){v}_{i}(T)\geq\alpha(\tilde{\pi}(i)){v}_{i}(\tilde{\pi}(i))\\}\\}.$

For probability mass p and noise value set $\boldsymbol{\alpha}$, let
$h_{T}(\textbf{{p}},\boldsymbol{\alpha})\coloneqq\mathbb{P}_{T\sim\mathcal{\widetilde{D}}}[F(T,\tilde{\pi})]$
be the agreement probability. Note that $F(T,\tilde{\pi})$ and hence
$h_{T}(\textbf{{p}},\boldsymbol{\alpha})$ are not known since the noise-free
values $v_{i}(T)$ and $v_{i}(\tilde{\pi}(i))$ are not known. However, for
$l\geq 2$ support noise distribution $\mathcal{N}$ we obtain
$h_{T}(\textbf{{p}},\boldsymbol{\alpha})$ explicitly in Sec. 3.1.

######  Theorem 3.1.

Suppose the noisy game $(N,\tilde{\textbf{{v}}})$ does not have $\tilde{\pi}$
as $\tilde{\epsilon}$-PAC stable outcome, i.e., equation (7) is satisfied.
Then the prediction probability given in Equation (5) is given by:
$\mathbb{P}[\cap_{i\in
T}({v}_{i}(T)>{v}_{i}(\tilde{\pi}(i)))]\geq(1-\tilde{\epsilon})h_{T}(\textbf{p},\boldsymbol{\alpha})$,
where $\epsilon>0$ satisfy
$(1-\tilde{\epsilon})h_{T}(\textbf{p},\boldsymbol{\alpha})=1-\epsilon.$

######  Proof 3.2.

Consider the following: $\mathbb{P}_{T\sim\mathcal{\widetilde{D}}}[\cap_{i\in
T}~{}({v}_{i}(T)>{v}_{i}(\tilde{\pi}(i)))]$

$\displaystyle\geq\mathbb{P}_{T\sim\mathcal{\widetilde{D}}}[\cap_{i\in
T}~{}({v}_{i}(T)>{v}_{i}(\tilde{\pi}(i)))~{}|~{}\cap_{i\in
T}(\tilde{v}_{i}(T)>\tilde{v}_{i}(\tilde{\pi}(i)))]\times\mathbb{P}_{T\sim\mathcal{\widetilde{D}}}[\cap_{i\in
T}(\tilde{v}_{i}(T)>\tilde{v}_{i}(\tilde{\pi}(i)))]$
$\displaystyle\geq(1-\tilde{\epsilon})~{}\mathbb{P}[\cap_{i\in
T}({v}_{i}(T)>{v}_{i}(\tilde{\pi}(i)))~{}|~{}\cap_{i\in
T}(\tilde{v}_{i}(T)>\tilde{v}_{i}(\tilde{\pi}(i)))]$
$\displaystyle\geq(1-\tilde{\epsilon})~{}\mathbb{P}[\cap_{i\in
T}\\{{v}_{i}(T)>{v}_{i}(\tilde{\pi}(i))\cap\tilde{v}_{i}(T)>\tilde{v}_{i}(\tilde{\pi}(i))\\}]\hskip
11.38109pt(\because\mathbb{P}(A|B)\geq\mathbb{P}(A\cap B))$
$\displaystyle=(1-\tilde{\epsilon})~{}h_{T}(\textit{{p}},\boldsymbol{\alpha})=1-\epsilon.$

This ends the proof.

Let $\eta$ be the probability of noise agreement event for which coalition $T$
core blocks $\tilde{\pi}$, i.e., $\eta\coloneqq
h_{T}(\textit{{p}},\boldsymbol{\alpha})$. Thus
$\epsilon=(1-\eta)+\eta\tilde{\epsilon}$ and hence partition $\tilde{\pi}$ is
$\eta$ noise-robust non core-stable in accordance to Definition 1.2. Moreover,
if $\eta=1$ then $\tilde{\epsilon}=\epsilon$ so, for arbitrary
$\tilde{\epsilon}>0$, we also have arbitrary $\epsilon>0$.

######  Remark 3.3.

Similar to Sec. 2, for a user-given $\eta$, we get a noise set
$I^{\star}(T,\eta)$ on p for coalition $T$, i.e., the noise set in which the
coalition $T$ core blocks $\tilde{\pi}$ with error more than $1-\epsilon$.
This is obtained by setting
$\mathbb{P}[F(T,\tilde{\pi})]=h_{T}(\textbf{{(}p)},\boldsymbol{\alpha})=\eta$;
that is, $I^{\star}(T,\eta)$ is $\eta$ level set of agreement probability
function $\mathbb{P}[F(T,\tilde{{\pi}})]$; in other words, it is a super level
set of the prediction probability. Hence, $\tilde{\pi}$ is $\eta$ noise-robust
non core-stable in this noise set $I^{\star}(T,\eta)$.

To better understand the noise robustness, we provide the expression of
$h_{T}(\textit{{p}},\boldsymbol{\alpha})$ for $l\geq 2$ support noise models
in the following subsection. For $l=2$ support noise model, we refer the
readers to Lemma A.5 of the SM. The detailed analysis of the $2$ support model
gives many more insights and also serves as the base case in the proof of
results in the next Section.

###  3.1 $n$ agents $l$ support partial information noisy game without core

In this section, we obtain the expression of the agreement probability
$h_{T}(\textbf{{p}},\boldsymbol{\alpha})$ for $l\geq 2$ support noise model,
$\mathcal{N}_{sp}=\\{\alpha_{1},\alpha_{2},\ldots,\alpha_{l}\\}$. To this end,
for all $r,s$ such that $\alpha_{r}>\alpha_{s}$ define
$\mathcal{J}(\alpha_{r},\alpha_{s},T)=\left\\{\tilde{\pi}(i)\in\mathcal{R}(T)~{}\bigg{|}~{}\frac{\tilde{v}_{i}(\tilde{\pi}(i))}{\tilde{v}_{i}(T)}\geq\frac{\alpha_{s}}{\alpha_{r}}\right\\}$.
It contains the set of all coalitions in the set $\mathcal{R}(T)$, such that
$\alpha_{r}>\alpha_{s}$, and
$\frac{\tilde{v}_{i}(\tilde{\pi}(i))}{\tilde{v}_{i}(T)}\geq\frac{\alpha_{s}}{\alpha_{r}}$.
The following Theorem provides the expression of
$h_{T}(\textit{{p}},\boldsymbol{\alpha})$. For proof refer to Sec. A.3 of the
SM.

######  Theorem 3.4.

For $n$ agent noisy hedonic game $(N,\tilde{\textbf{{v}}})$ with
$\mathcal{N}_{sp}=\\{\alpha_{1},\alpha_{2},\ldots,\alpha_{l}\\}$, the
agreement probability $h_{T}(\textbf{p},\boldsymbol{\alpha})$ is given by:

$h_{T}(\textbf{p},\boldsymbol{\alpha})=\begin{cases}1,\hfill
if~{}\tilde{\pi}(i)=T,~{}\forall~{}i\in T,\\\
\sum_{r,s\in[l]:\alpha_{r}>\alpha_{s}}p_{r}^{|\mathcal{R}(T)|-|\mathcal{J}(\alpha_{r},\alpha_{s},T)|+1}\times\\{(p_{s}+p_{r})^{|\mathcal{J}(\alpha_{r},\alpha_{s},T)|}-p_{r}^{|\mathcal{J}(\alpha_{r},\alpha_{s},T)|}\\}\\\
+\sum_{a=1}^{l}p_{a}\left(\sum_{b=a}^{l}p_{b}\right)^{|\mathcal{R}(T)|},\hfill
otherwise.\end{cases}$

######  Remark 3.5.

Let $h_{T}(\textbf{p},\boldsymbol{\alpha})=\eta$ for some user-given
satisfaction value $\eta$, we get a set of noise values in accordance to the
Remark 3.3. In this case, the noise set depends on $|\mathcal{R}(T)|$, and
$|\mathcal{J}(\alpha_{r},\alpha_{s},T)|,~{}\forall~{}\alpha_{r}>\alpha_{s}$
for coalition $T$. Also, the partition $\tilde{\pi}$ is $\eta$ noise-robust
non core-stable in the noise set $I^{\star}(T,\eta)$.

######  Remark 3.6.

Theorem 3.1 provides the probability that $\tilde{\pi}$ is not $\epsilon$-PAC
stable outcome in noise-free game $(N,{\textbf{{v}}})$, when it is not
$\tilde{\epsilon}$-PAC stable outcome in noisy game. Therefore, the
probability that a noise-free game has $\tilde{\pi}$ as $\epsilon$-PAC stable
outcome, given that the noisy game does not have $\tilde{\pi}$ as
$\tilde{\epsilon}$-PAC stable outcome is compliment of the probability in
Theorem 3.1.

##  4 2 agent full information model

This Section considers the complete information game with 2 agents. So,
valuations on all coalitions are known in the noisy game; hence, a noisy core-
stable partition is also known. Even though this Section is a particular case
of previous sections, we get many valuable insights that enhance our
understanding regarding noise robustness in noisy hedonic games. For example,
we have this counter-intuitive fact that the prediction probability can be
high if the noise value occurs with a high probability. A concrete
illustration is that the prediction probability turns out to be 1 when values
of all agents are inflated by $\alpha>1$ with probability 1; in fact, both
games have the same preferences and hence identical partitions.

###  4.1 2 support noise distribution

Let the noise support be $\mathcal{N}_{sp}\in\\{1,\alpha\\}$ with $\alpha>1$,
such that
$\mathbb{P}[\mathcal{N}_{sp}=\alpha]=p=1-\mathbb{P}[\mathcal{N}_{sp}=1]$. Note
that $\alpha>1$ is not a restrictive condition; even if we allow $\alpha<1$,
we will get results similar to the ones presented below. Given a noisy game
and its corresponding core-stable partition, we aim to find the prediction
probability that a core-stable partition of the unknown noise-free game is the
same as a core-stable partition of a noisy game. Formally, for a user-given
$\zeta\in(0,1]$, we find
$\mathbb{P}[\pi=\tilde{\pi}~{}|~{}noisy~{}game]\geq\zeta$.

We want to emphasize that the above prediction probability is the same as the
one given in Equation (5). Since, in a 2 agent complete information game, the
noisy core-stable partition $\tilde{\pi}$ always exists; hence
$\tilde{\epsilon}=0$ in Theorem 2.1. So, with
$f_{T}(\textbf{{p}},\boldsymbol{\alpha})=\zeta$ we have
$\mathbb{P}_{T\sim\mathcal{\widetilde{D}}}[T\text{ does not core blocks
}\tilde{\pi}~{}in~{}(N,\textbf{{v}})]\geq\zeta$. Consider the following 2
agents’ noisy game.

$\tilde{v}_{1}(12)>\tilde{v}_{1}(1);\hskip
5.69054pt\tilde{v}_{2}(12)>\tilde{v}_{2}(2).$ (game 1)

Clearly, $\tilde{\pi}=\\{12\\}=N$ is the core-stable outcome of the above
noisy game. The following Lemma gives the prediction probability for the above
game.

######  Lemma 4.1.

For noisy game 1 with complete information on $\tilde{\textbf{{v}}}$, and
$\mathcal{N}_{sp}=\\{1,\alpha\\}$, we have

$\displaystyle\mathbb{P}[\pi=\tilde{\pi}~{}|~{}game~{}1]=\begin{cases}1-p(1-p^{2}),&if~{}\alpha\geq\overline{r}\\\
1-p(1-p),&if~{}\underline{r}\leq\alpha<\overline{r}\\\
1,&if~{}\alpha<\underline{r},\end{cases}$ (8)

where
$\overline{r}=\max\left\\{\frac{\tilde{v}_{1}(12)}{\tilde{v}_{1}(1)},\frac{\tilde{v}_{2}(12)}{\tilde{v}_{2}(2)}\right\\}$,
and
$\underline{r}=\min\left\\{\frac{\tilde{v}_{1}(12)}{\tilde{v}_{1}(1)},\frac{\tilde{v}_{2}(12)}{\tilde{v}_{2}(2)}\right\\}$.

Also, this prediction probability $\mathbb{P}[\pi=\tilde{\pi}~{}|~{}game~{}1]$
is convex in $p$. So, while the minimal value for
$\mathbb{P}[\pi=\tilde{\pi}~{}|~{}game~{}1]$ occurs for noise probabilities
around $p=0.5$ (depending on $\alpha,\overline{r}$ and $\underline{r}$), the
maximal value of it is $1$ at $p=0$ and $p=1$.

The proof is deferred to Sec. A.4.1 of the SM. The above lemma has following
insights: the prediction probability depends on three factors, $p$, $\alpha$,
and $\tilde{\textbf{{v}}}$. Note that $p$ is not known because the noise
distribution is unknown. We know $\tilde{\textbf{{v}}}$’s hence
$\underline{r}$, and $\overline{r}$ are known. If $p$ is close to $0.5$, then
the prediction probability $\mathbb{P}[\pi=\tilde{\pi}~{}|~{}game~{}1]$ is
close to $0.62$, for $\alpha\geq\overline{r}$, and close to $0.75$ for
$\underline{r}\leq\alpha<\overline{r}$. So, the prediction probability is the
least when noise is random. We call this minimum prediction probability the
safety value.

Suppose we allow the user-given satisfaction value on the prediction
probability, i.e., we relax the condition
$\mathbb{P}[\pi=\tilde{\pi}~{}|~{}game~{}1]=1$, and allow a user-given
satisfaction value, $\zeta\in(0,1]$ on the prediction probability, i.e.,
$\mathbb{P}[\pi=\tilde{\pi}~{}|~{}game~{}1]=\zeta$. So, for different ranges
of $\alpha$, we get an interval of the noise probabilities $p$ allowable to
attain a user-given probability $\zeta$. For example, if $\zeta=0.9$, then the
noise regime, $I^{\star}(\zeta=0.9)=[0,0.101]\cup[0.946,1]$, if
$\alpha\geq\overline{r}$; it is $[0,0.113]\cup[0.887,1]$, if
$\underline{r}\leq\alpha<\overline{r}$; and it is $[0,1]$, if
$\alpha<\underline{r}$. So, for the noise set $I^{\star}(\zeta=0.9)$, the
core-stable partition of the noise-free game is the same as the core-stable
partition of the noisy game 1 with probability $0.9$. Thus, the noise regime
achieving a user given satisfaction value can be non-convex. Figure 1
illustrates these observations.

Figure 1: In two agent hedonic game 1 with 2 support noise model, we plot the
prediction probability $\mathbb{P}[\pi=\tilde{\pi}~{}|~{}game~{}1]$ for
different ranges of $\alpha$.

Note that in Equation (8) we have obtained the conditional probability
$\mathbb{P}[\pi=\tilde{\pi}~{}|~{}game~{}1]$. One can obtain a similar
prediction probability for other noisy games, which we call game 2, game 3,
and game 4, whose details are available in Sec. A.4.2 of the SM. We summarize
the main observations of 2 agents 2 support noise in the Theorem below:

######  Theorem 4.2.

Consider 2 agent noisy hedonic game with 2 support noise model, then the
prediction probability that $\pi=\tilde{\pi}$ given any noisy game $k$,
$k=1,2,3,4$ is:

$\mathbb{P}[\pi=\tilde{\pi}~{}|~{}game~{}k]=\begin{cases}1,&\text{under any
condition in A},\\\
q(p,\tilde{v}_{1}(\cdot),\tilde{v}_{2}(\cdot),\alpha),&otherwise,\end{cases}$
(9)

for some function $q(p,\tilde{v}_{1}(\cdot),\tilde{v}_{2}(\cdot),\alpha)<1$,
depending on $\tilde{v}_{1}(\cdot),\tilde{v}_{2}(\cdot)$ and $\alpha$. The
conditions in A are (a) $k=1$, and $\alpha<\underline{r}$; (b) $k=2$ and
$\frac{1}{\alpha}\geq\overline{r}$; (c) $k=3$ and
$\frac{1}{\alpha}\geq\frac{\tilde{v}_{1}(12)}{\tilde{v}_{1}(1)}$; and (d)
$k=4$ and $\frac{1}{\alpha}\geq\frac{\tilde{v}_{2}(12)}{\tilde{v}_{2}(2)}$.

Moreover, if $p=0$ or $p=1$, we have
$\mathbb{P}[\pi=\tilde{\pi}~{}|~{}game~{}k]=1$, for all $k=1,2,3,4$.

For a 2 support noise model, the probability that a noise-free game has the
same core-stable partition as the noisy game is $1$ in many cases, including
$p=1$, i.e., when all values are inflated by $\alpha$. Thus, the allowable
noise regimes for high prediction probabilities can include high noise values.
Moreover, $q(p,\tilde{v}_{1}(\cdot),\tilde{v}_{2}(\cdot),\alpha)\geq 0.62$ is
the safety value. So, we have a lower bound on the prediction probability.

###  4.2 3 support noise distribution

Next, consider the 3 support noise,
$\mathcal{N}_{sp}=\\{1,\alpha_{1},\alpha_{2}\\}$, where $\alpha_{1}>1$, and
$0<\alpha_{2}<1$. Let
$\mathbb{P}[\alpha(S)=\alpha_{1}]=p_{1};~{}\mathbb{P}[\alpha(S)=\alpha_{2}]=p_{2};~{}and~{}\mathbb{P}[\alpha(S)=1]=1-p_{1}-p_{2}$.
Given the noisy game 1, the prediction probability for 3 support noise is
given in the Lemma below.

######  Lemma 4.3.

For the 3 support noise model the prediction probability
$\mathbb{P}[\pi=\tilde{\pi}~{}|~{}game~{}1]$ is

$\mathbb{P}[\pi=\tilde{\pi}~{}|~{}game~{}1]=\begin{cases}g(p_{1},p_{2}),&~{}if~{}~{}\alpha_{1}\geq\overline{r}~{};~{}\frac{1}{\alpha_{2}}\geq\overline{r}~{};~{}\frac{\alpha_{1}}{\alpha_{2}}\geq\overline{r}\\\
1,&~{}if~{}~{}\alpha_{1}<\underline{r}~{};~{}\frac{1}{\alpha_{2}}<\underline{r}~{};~{}\frac{\alpha_{1}}{\alpha_{2}}<\underline{r}\end{cases}$
(10)

where
$g(p_{1},p_{2})=p_{1}^{3}+p_{2}^{3}+2(p_{1}(1-p_{1}-p_{2})^{2}+p_{2}^{2}(1-p_{1}-p_{2})+p_{1}p_{2}(1-p_{1}-p_{2})+p_{1}p_{2}^{2})+p_{1}^{2}p_{2}+p_{1}^{2}(1-p_{1}-p_{2})+p_{2}(1-p_{1}-p_{2})^{2}+(1-p_{1}-p_{2})^{3}$.

There are $\mathbf{106}$ more cases in the above Lemma, where in each case,
the prediction probability is strictly less than 1 (Sec. A.5.1 of SM). Unlike
2 support model (Sec. 4.1) in this case they are _non-convex_ ; a counter-
example is available in Sec. A.5.2 of Appendix

##  5 Related work

Stability notions in hedonic games: Researchers have extensively studied
hedonic games in the computational social choice community. Some early works
in coalition formation games describing the economic situations include that
of Dreze and Greenberg (1980); Elkind and Wooldridge (2009). The agents
collaborate and have personal preferences on different coalitions. Based on
these preferences, agents seek a partition of the agent set. However, which
partition to form led to various notions of stability (Bogomolnaia and
Jackson, 2002; Banerjee et al., 2001; Aziz and Brandl, 2012). Some of them are
core stability, Nash stability, and perfect. In this work, we use core
stability. In particular, the core for the simple hedonic games is available
in Banerjee et al. (2001).

Representation of hedonic games: In many real-life scenarios, there are
multiple agents, so storing the hedonic game in a machine takes exponential
space. In literature, various concise representations are used because they
(often) only require polynomial space. So, apart from various stability
notions, much literature is on representing the hedonic games. Some of them
includes individually rational lists of coalitions (IRLC) (Ballester, 2004),
hedonic coalition nets (HCNs) (Elkind and Wooldridge, 2009), additively
separable games, fractional hedonic games, $\mathcal{B}$-games,
$\mathcal{W}$-games, top-responsive games (Alcalde and Revilla, 2004). A
detailed survey of the hedonic games is available in Aziz and Savani (2016);
Aziz et al. (2019); Cechlárová and Hajduková (2004). In our work, we only use
partial information and $\epsilon$-PAC stable notion for the existence of
partition $\tilde{\pi}$. However, our work is valid for any class of hedonic
games as long as both noise-free and noisy values have the same
representation.

Existence of solution concepts: Another line of literature focuses on the
algorithmic aspects of solution concepts of hedonic games. Regarding solution
concepts like core stability and nature of partitions, there are two
questions: does there exist a partition $\pi$ satisfying the solution
concept’s properties; if there is such a $\pi$, find one. To this end, for
different classes of hedonic games, there are various algorithms and hardness
results such as Sung and Dimitrov (2010); Rahwan et al. (2009); Woeginger
(2013).

PAC learning in hedonic games: Uncertainty in the agents’ preferences in the
cooperative games has been carefully analyzed by Balcan et al. (2015). The
authors used the PAC learning model to learn an underlying game. A new
connection is established between PAC learnability and core stability for
various classes of TU cooperative games. It turned out that only a few classes
of TU games are learnable and stable. Sliwinski and Zick (2017) extended the
PAC learning approach to the premise of hedonic games, where complete
information about individual preferences is unavailable. We incorporate noise
in the preferences and use PAC bounds to obtain the prediction probabilities.

##  6 Discussion and looking ahead

This work considers the noisy hedonic game with partial information on
preferences. Given a PAC stable partition of the noisy game, we find the
prediction probability that unknown noise-free game has PAC stable partition.
This requires a combinatorial construct called agreement event and its
probability. For $l\geq 2$ noise support, we obtain the agreement probability
as a function of noise probabilities. For a user-given satisfaction value on
agreement probability, we obtain the noise set such that a given partition is
noise-robust. An interesting observation is that the prediction probability
can be high for some high noise values with high probabilities. In particular,
for a 2 agent game with $2$ noise support, we obtain the noise set for which
the prediction probability is more than a user-given satisfaction value. We
have noise robustness for the entire noise probability simplex for the
prediction probability below $0.62$, i.e., the safety value. However, if the
prediction probability function exceeds this safety value, the noise robust
regime is non-convex. For the case of $3$ noise support, finding a safety
value is difficult as it is a global minimum of a non-convex prediction
probability function. We obtain the bounds on the extra noisy samples required
to get the PAC stable partition in a noise-free game. These extra samples are
polynomial in the number of agents and the user-given satisfaction value on
agreement probability.

The aspects we investigated offer many other rich possibilities; we mention
some of them here. Firstly, since the prediction probability function for $3$
support noise distribution is non-convex, which renders the computation of the
fundamental limit of noise robustness hard, one may investigate suitable
approximations. Another possibility is to consider other noise models where
the value of each coalition is perturbed at the individual player level.

We would like to thank the anonymous Reviewers for their useful comments and
suggestions. While working at this problem Prashant Trivedi was partially
supported by the Teaching Assistantship offered by Government of India. Some
part of this work was done when Nandyala Hemachandra was visiting IIM
Bangalore on a sabbatical leave.

## References

  * Alcalde and Revilla (2004) José Alcalde and Pablo Revilla.  Researching with whom? Stability and manipulation.  _Journal of Mathematical Economics_ , 40(8):869–887, 2004.
  * Aziz and Brandl (2012) Haris Aziz and Florian Brandl.  Existence of stability in hedonic coalition formation games.  In _Proceedings of the 11th AAMAS_ , pages 763–770, 2012.
  * Aziz and Savani (2016) Haris Aziz and Rahul Savani.  Hedonic Games (Chapter 15).  In F. Brandt, V. Conitzer, J. Lang U. Endriss, and A.D. Procaccia, editors, _Handbook of Computational Social Choice_. Cambridge University Press, Cambridge, 2016.
  * Aziz et al. (2019) Haris Aziz, Florian Brandl, Felix Brandt, Paul Harrenstein, Martin Olsen, and Dominik Peters.  Fractional hedonic games.  _ACM TEAC_ , 7(2):1–29, 2019.
  * Balcan et al. (2015) Maria-Florina Balcan, Ariel D Procaccia, and Yair Zick.  Learning cooperative games.  In _Proceedings of the 24th IJCAI_ , pages 475–481, 2015.
  * Ballester (2004) Coralio Ballester.  NP-completeness in hedonic games.  _Games and Economic Behavior_ , 49(1):1–30, 2004\.
  * Banerjee et al. (2001) Suryapratim Banerjee, Hideo Konishi, and Tayfun Sönmez.  Core in a simple coalition formation game.  _Social Choice and Welfare_ , 18(1):135–153, 2001\.
  * Bogomolnaia and Jackson (2002) Anna Bogomolnaia and Matthew O Jackson.  The stability of hedonic coalition structures.  _Games and Economic Behavior_ , 38(2):201–230, 2002.
  * Brandt et al. (2016) Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D Procaccia.  _Handbook of computational social choice_.  Cambridge University Press, 2016.
  * Cechlárová and Hajduková (2004) Katarína Cechlárová and Jana Hajduková.  Stability of partitions under $\mathcal{BW}$-prefernces and $\mathcal{WB}$\- preferences.  _International Journal of Information Technology & Decision Making_, 3(04):605–618, 2004.
  * Dreze and Greenberg (1980) Jacques H Dreze and Joseph Greenberg.  Hedonic coalitions: Optimality and stability.  _Econometrica (pre-1986)_ , 48(4):987, 1980.
  * Elkind and Wooldridge (2009) Edith Elkind and Michael J Wooldridge.  Hedonic coalition nets.  In _AAMAS (1)_ , pages 417–424, 2009.
  * Mas-Colell et al. (1995) Andreu Mas-Colell, Michael Dennis Whinston, and Jerry R Green.  _Microeconomic theory_ , volume 1.  Oxford University Press New York, 1995.
  * Narahari (2014) Yadati Narahari.  _Game theory and mechanism design_ , volume 4.  World Scientific, 2014.
  * Rahwan et al. (2009) Talal Rahwan, Sarvapali D Ramchurn, Nicholas R Jennings, and Andrea Giovannucci.  An anytime algorithm for optimal coalition structure generation.  _Journal of Artificial Intelligence Research_ , 34:521–567, 2009.
  * Sliwinski and Zick (2017) Jakub Sliwinski and Yair Zick.  Learning Hedonic Games.  In _IJCAI_ , pages 2730–2736, 2017.
  * Sung and Dimitrov (2010) Shao-Chin Sung and Dinko Dimitrov.  Computational complexity in additive hedonic games.  _European Journal of Operational Research_ , 203(3):635–639, 2010.
  * Woeginger (2013) Gerhard J Woeginger.  Core stability in hedonic coalition formation.  In _International Conference on Current Trends in Theory and Practice of Computer Science_ , pages 33–50. Springer, 2013.

##  Appendix A Proof of Theorem 2.11

######  Proof A.1.

We prove this via induction on noise support $l\geq 2$. The base case with
$l=2$ support is available in Lemma A.2 of the SM. Let us assume that it is
true for $l=k$, i.e., there are sets
$\mathcal{I}(\alpha_{r},\alpha_{s},T)=\left\\{\tilde{\pi}(i)\in\mathcal{R}(T)~{}\bigg{|}~{}\frac{\tilde{v}_{i}(\tilde{\pi}(i))}{\tilde{v}_{i}(T)}\geq\frac{\alpha_{r}}{\alpha_{s}}\right\\}$,
such that $\alpha_{s}<\alpha_{r},~{}\forall~{}1\leq s<r\leq k$.

For this $k$ we have
$f_{T}(p_{j},\alpha_{j};j\in[k])=:f_{T}(\textit{{p}},\boldsymbol{\alpha})$ (by
assumption), here $[k]=\\{1,2,\dots,k\\}$

$f_{T}(\textit{{p}},\boldsymbol{\alpha})=\sum_{a=1}^{k}p_{a}\left(\sum_{b=1}^{a}p_{b}\right)^{|\mathcal{R}(T)|}+\sum_{r,s\in[k]:\alpha_{r}>\alpha_{s}}p_{s}^{|\mathcal{R}(T)|-|\mathcal{I}(\alpha_{r},\alpha_{s},T)|+1}((p_{r}+p_{s})^{|\mathcal{I}(\alpha_{r},\alpha_{s},T)|}-p_{s}^{|\mathcal{I}(\alpha_{r},\alpha_{s},T)|}).$

We will now show that this is true for $l=k+1$. To this end, for all $s\in[k]$
such that for $\alpha_{k+1}>\alpha_{s}$ we define
$\mathcal{I}(\alpha_{k+1},\alpha_{s},T)=\left\\{\tilde{\pi}(i)\in\mathcal{R}(T)~{}\bigg{|}~{}\frac{\tilde{v}_{i}(\tilde{\pi}(i))}{\tilde{v}_{i}(T)}\geq\frac{\alpha_{k+1}}{\alpha_{s}}\right\\}$.
Now, there are two cases,
$\mathcal{I}(\alpha_{k+1},\alpha_{s},T)=\emptyset,~{}\forall~{}\alpha_{s},~{}s\in[k]$,
or $\mathcal{I}(\alpha_{k+1},\alpha_{s},T)\neq\emptyset$ for at least for one
$s\in[k]$.

Case 01:
[$\mathcal{I}(\alpha_{k+1},\alpha_{s},T)=\emptyset,~{}\forall~{}\alpha_{s},~{}s\in[k]$].
With one more element in noise support, apart from the existing
$\\{\alpha(\tilde{\pi}(i)\\}_{\tilde{\pi}(i)\in\mathcal{R}(T)}$, and
$\alpha(T)$ for $k$ support case it will also have $\alpha(T)=\alpha_{k+1}$,
and
$\alpha(\tilde{\pi}(i))\in\\{\alpha_{1},\alpha_{2},\dots,\alpha_{k+1}\\},~{}\forall~{}\tilde{\pi}(i)\in\mathcal{R}(T)$.
The probability of such $\alpha$’s is
$p_{k+1}\left(\sum_{b=1}^{k+1}p_{b}\right)^{|\mathcal{R}(T)|}$. Therefore, the
overall probability is

$\sum_{a=1}^{k}p_{a}\left(\sum_{b=1}^{a}p_{b}\right)^{|\mathcal{R}(T)|}+p_{k+1}\left(\sum_{b=1}^{k+1}p_{b}\right)^{|\mathcal{R}(T)|}=\sum_{a=1}^{k+1}p_{a}\left(\sum_{b=1}^{a}p_{b}\right)^{|\mathcal{R}(T)|}.$

Case 02: [$\mathcal{I}(\alpha_{k+1},\alpha_{s},T)\neq\emptyset$ for at least
for one $s\in[k]$]. In this case, apart from the existing
$\\{\alpha(\tilde{\pi}(i))\\}_{\tilde{\pi}(i)\in\mathcal{I}(\alpha_{r},\alpha_{s},T)}$,
and $\alpha(T)$ for $k$ support, we also have
$\\{\alpha(\tilde{\pi}(i))\\}_{\tilde{\pi}(i)\in\mathcal{I}(\alpha_{k+1},\alpha_{s},T)}$,
$\alpha(T)$ such that
$\alpha(\tilde{\pi}(i))=\alpha_{s},~{}\forall~{}\tilde{\pi}(i)\in\mathcal{R}(T)\setminus\mathcal{I}(\alpha_{k+1},\alpha_{s},T)$,
and $\alpha(T)=\alpha_{k+1}$. Thus, for $k+1$ support the probability is:

$\displaystyle\sum_{r,s\in[k]:\alpha_{r}>\alpha_{s}}p_{s}^{|\mathcal{R}(T)|-|\mathcal{I}(\alpha_{r},\alpha_{s},T)|+1}((p_{r}+p_{s})^{|\mathcal{I}(\alpha_{r},\alpha_{s},T)|}-p_{s}^{|\mathcal{I}(\alpha_{r},\alpha_{s},T)|})$
$\displaystyle\hskip
42.67912pt+~{}p_{s}^{|\mathcal{R}(T)|-|\mathcal{I}(\alpha_{k+1},\alpha_{s},T)|+1}((p_{k+1}+p_{s})^{|\mathcal{I}(\alpha_{k+1},\alpha_{s},T)|}-p_{s}^{|\mathcal{I}(\alpha_{k+1},\alpha_{s},T)|}).$

From case 01 and case 02 above, for $k+1$ support we have,

$\displaystyle f_{T}(p_{j},\alpha_{j};j\in[k+1])$
$\displaystyle=\sum_{r,s\in[k+1]:\alpha_{r}>\alpha_{s}}p_{s}^{|\mathcal{R}(T)|-|\mathcal{I}(\alpha_{r},\alpha_{s},T)|+1}\left((p_{r}+p_{s})^{|\mathcal{I}(\alpha_{r},\alpha_{s},T)|}-p_{s}^{|\mathcal{I}(\alpha_{r},\alpha_{s},T)|}\right)$
$\displaystyle~{}~{}+\sum_{a=1}^{k+1}p_{a}\left(\sum_{b=1}^{a}p_{b}\right)^{|\mathcal{R}(T)|}$

Therefore, from the principle of Mathematical induction, this is true for any
$l\geq 2$.

###  A.1 $n$ agents $2$ support partial information noise model

In a two support noise model we have $\mathcal{N}_{sp}=\\{1,\alpha\\}$ with
$\alpha>1$, such that for any coalition $S\subseteq N$,
$\mathbb{P}[\alpha(S)=\alpha]=p=1-\mathbb{P}[\alpha(S)=1]$. We derive the
agreement probability, $f_{T}(p,\alpha)$ in the following lemma. Note that
this lemma serves as the base case in the Mathematical induction based proof
of the Theorem 2.11 in the main paper.

######  Lemma A.2.

Let $\tilde{\pi}$ be $\tilde{\epsilon}$-PAC stable partition of noisy game
$(N,\tilde{\textbf{{v}}})$, and let $\tilde{\pi}$ be a $\epsilon$-PAC stable
outcome of the noise-free game $(N,\textbf{{v}})$, where $\epsilon$ is
identified in Theorem 2.1 of the paper. Then the agreement probability
$f_{T}({p},{\alpha})$ is given by

$f_{T}({p},{\alpha})=\begin{cases}1,&if~{}\tilde{\pi}(i)=T,~{}\forall~{}i\in
T\\\
p+(1-p)^{|\mathcal{R}(T)|+1-|\mathcal{I}(\alpha,T)|},&otherwise\end{cases}$

where
$\mathcal{I}(\alpha,T)=\left\\{\tilde{\pi}(i)\in\mathcal{R}(T)~{}\bigg{|}~{}\frac{\tilde{v}_{i}(\tilde{\pi}(i))}{\tilde{v}_{i}(T)}\geq\alpha\right\\}.$

######  Proof A.3.

Recall from Theorem 2.1 in main paper we have the following

$\mathbb{P}_{T\sim\mathcal{\tilde{D}}}[\cup_{i\in
T}~{}v_{i}(\tilde{\pi}(i))\geq
v_{i}(T)]\geq(1-\tilde{\epsilon})f_{T}(\textit{{p}},\boldsymbol{\alpha}).$

Also, recall that the agreement event is defined as

$M(\tilde{\pi},T)\coloneqq\\{(\\{\alpha(\tilde{\pi}(i))\\}_{\tilde{\pi}(i)\in\mathcal{R}(T)},\alpha(T)):\cap_{i\in
T}\\{v_{i}(\tilde{\pi}(i))\geq
v_{i}(T)~{}\cap~{}\alpha(\tilde{\pi}(i)){v}_{i}(\tilde{\pi}(i))\geq\alpha(T){v}_{i}(T)\\}\\},$

and $f_{T}({p},{\alpha})=\mathbb{P}[M(\tilde{\pi},T)]$ is the probability of
agreement event. Moreover,

$\mathcal{R}(T)\coloneqq\\{\tilde{\pi}(i)~{}|~{}i\in T\\};\hskip
8.53581pt\mathcal{I}(\alpha,T)=\left\\{\tilde{\pi}(i)\in\mathcal{R}(T)~{}\bigg{|}~{}\frac{\tilde{v}_{i}(\tilde{\pi}(i))}{\tilde{v}_{i}(T)}\geq\alpha\right\\}.$

To find the agreement probability, $f_{T}(\textbf{{p}},\boldsymbol{\alpha})$
we consider two cases $\mathcal{I}(\alpha,T)=\emptyset$, and
$\mathcal{I}(\alpha,T)\neq\emptyset$. For these cases we identify the possible
noise values $\\{\alpha(\tilde{\pi}(i))\\}_{\tilde{\pi}(i)\in\mathcal{R}(T)}$,
$\alpha(T)$ that are element of $M(\tilde{\pi},T)$.

  * •

Case 01: $[\mathcal{I}(\alpha,T)=\emptyset]$. In this case, we have following
elements in $M(\tilde{\pi},T)$.

    * –

$\alpha(\tilde{\pi}(i))=1,~{}\forall~{}\tilde{\pi}(i)\in\mathcal{R}(T)$ and
$\alpha(T)=1$. The probability of such choice of $\alpha$’s is

$(1-p)^{|\mathcal{R}(T)|+1}.$ (11)

    * –

$\alpha(\tilde{\pi}(i))=\alpha$ for exactly one
$\tilde{\pi}(i)\in\mathcal{R}(T)$, and $\alpha(\tilde{\pi}(i))=1$ for
remaining coalitions in $\mathcal{R}(T)$, and $\alpha(T)=\alpha$. Probability
of such choice of $\alpha$’s is $(p\times(1-p)^{|\mathcal{R}(T)|-1})\times p$.
And there are $|\mathcal{R}(T)|\choose 1$ ways of selecting exactly one
coalition $\tilde{\pi}(i)\in\mathcal{R}(T)$. Thus, the probability of above
$\alpha$’s is ${|\mathcal{R}(T)|\choose 1}p(1-p)^{|\mathcal{R}(T)|-1}p$.

In general, for any $k\in\\{0,1,\dots,|\mathcal{R}(T)|\\}$ coalitions
$\tilde{\pi}(i)\in\mathcal{R}(T)$, take $\alpha(\tilde{\pi}(i))=\alpha$.
Moreover, $\alpha(\tilde{\pi}(i))=1$ for remaining $|\mathcal{R}(T)|-k$
coalitions and take $\alpha(T)=\alpha$. Further, we have
${|\mathcal{R}(T)|\choose k}$ similar choices. So, the probability of the
above choice of $\alpha$’s is

$\displaystyle\sum_{k=0}^{|\mathcal{R}(T)|}\left\\{{|\mathcal{R}(T)|\choose
k}p^{k}(1-p)^{|\mathcal{R}(T)|-k}\right\\}\times p$
$\displaystyle=p\times\left(\sum_{k=0}^{|\mathcal{R}(T)|}{|\mathcal{R}(T)|\choose
k}p^{k}(1-p)^{|\mathcal{R}(T)|-k}\right)$ (12) $\displaystyle=p.$

This is because for any coalition $S$, we have
$\mathbb{P}[\alpha(S)=\alpha]=p=1-\mathbb{P}[\alpha(S)=1]$ and the fact that
binomial probabilities summed up to 1.

  * •

Case 02: $[\mathcal{I}(\alpha,T)\neq\emptyset]$. Then, in addition to the
above possible cases, we will have a few other cases, which are:

    * –

$\alpha(\tilde{\pi}(i))=\alpha$ for exactly one
$\tilde{\pi}(i)\in\mathcal{I}(\alpha,T)$, $\alpha(\tilde{\pi}(i))=1$ for
remaining coalitions in $\mathcal{R}(T)$ and $\alpha(T)=1$. Probability of
such choice of $\alpha$’s is
$p(1-p)^{|\mathcal{R}(T)|-1}(1-p)=p(1-p)^{|\mathcal{R}(T)|}$. And there are
$|\mathcal{I}(\alpha,T)|\choose 1$ ways of choosing exactly one coalition
$\tilde{\pi}(i)\in\mathcal{I}(\alpha,T)$. Thus the overall probability is
${|\mathcal{I}(\alpha,T)|\choose 1}p(1-p)^{|\mathcal{R}(T)|}$.

In general, we have $\alpha(\tilde{\pi}(i))=\alpha$ for any
$k\in\\{1,2,\dots,|\mathcal{I}(\alpha,T)|\\}$ coalitions
$\tilde{\pi}(i)\in\mathcal{I}(\alpha,T)$. Moreover, $\alpha(\tilde{\pi}(i))=1$
for remaining $|\mathcal{R}(T)|-k$ coalitions, and $\alpha(T)=1$. Probability
of such choice of $\alpha$’s is
$p^{k}(1-p)^{|\mathcal{R}(T)|-|\mathcal{I}(\alpha,T)|}(1-p)$. And there are
$|\mathcal{I}(\alpha,T)|\choose k$ ways of selecting $k$ coalitions
$\tilde{\pi}(i)\in\mathcal{I}(\alpha,T)$. Thus the overall probability is

$\sum_{k=1}^{|\mathcal{I}(\alpha,T)|}{|\mathcal{I}(\alpha,T)|\choose
k}p^{k}(1-p)^{|\mathcal{R}(T)|-|\mathcal{I}(\alpha,T)|}(1-p).$ (13)

The probability of event $M(\tilde{\pi},T)$, i.e.,
$\mathbb{P}[M(\tilde{\pi},T)]$ is obtained by adding probabilities given in
Equations (11), (12) and (13).

$\displaystyle\mathbb{P}[M(\tilde{\pi},T)]$ $\displaystyle=$
$\displaystyle(1-p)^{|\mathcal{R}(T)|+1}+p+\sum_{k=1}^{|\mathcal{I}(\alpha,T)|}{|\mathcal{I}(\alpha,T)|\choose
k}p^{k}(1-p)^{|\mathcal{R}(T)|-|\mathcal{I}(\alpha,T)|}(1-p)$ $\displaystyle=$
$\displaystyle(1-p)^{|\mathcal{R}(T)|+1}+p+(1-p)^{|\mathcal{R}(T)|-|\mathcal{I}(\alpha,T)|+1}\Bigg{[}1-(1-p)^{|\mathcal{I}(\alpha,T)|}\Bigg{]}$
$\displaystyle=$ $\displaystyle
p+(1-p)^{|\mathcal{R}(T)|-|\mathcal{I}(\alpha,T)|+1}.$

This ends the proof.

If $\tilde{\pi}(i)\neq T$ for at least one $i\in T$, then
$f_{T}({p},{\alpha})=1,~{}\forall~{}\alpha$ if and only if $p=0$ or $p=1$.
That is, if the value of all the coalitions are retained, or if values of all
of them are inflated by $\alpha$, then for all $i\in T$, and for all
$\tilde{\pi}(i)\in\mathcal{R}(T)$, one has $\tilde{\pi}(i)\succeq_{i}T$, and
$\tilde{\pi}(i)\succeq_{i}^{\prime}T$. Thus, $\tilde{\pi}$ is $\epsilon$-PAC
stable outcome of unknown noise-free game and hence $\tilde{\pi}$ is noise-
robust.

######  Corollary A.4.

When $\tilde{\pi}=N$, i.e., the grand coalition is $\tilde{\epsilon}$-PAC
stable outcome in the noisy game, then $\mathcal{R}(T)=\\{N\\}$ for any
coalition $T$. Thus, $\mathcal{I}(\alpha,T)=\emptyset$, or
$\mathcal{I}(\alpha,T)=\\{N\\}$. Therefore, $f_{T}(p,\alpha)$ simplifies to

$f_{T}({p},{\alpha})=\begin{cases}1,&~{}if~{}\mathcal{I}(\alpha,T)=\\{N\\}\\\
(1-p)^{2}+p,&~{}if~{}\mathcal{I}(\alpha,T)=\emptyset.\end{cases}$ (14)

###  A.2 $n$ agents $2$ support partial information noisy games without core

Suppose $\tilde{\pi}$ is not $\tilde{\epsilon}$-PAC stable partition fo the
noisy game $(N,\tilde{\textbf{{v}}})$. Moreover, let the noise support be
$\mathcal{N}_{sp}=\\{1,\alpha\\}$, the following lemma provides the expression
of $h_{T}({p},{\alpha})$. Note that this lemma serves as the base case for the
Mathematical induction based proof of Theorem 3.4 in the main paper.

######  Lemma A.5.

Suppose $\tilde{\pi}$ is not a $\tilde{\epsilon}$-PAC stable outcome of the
noisy game $(N,\tilde{\textbf{{v}}})$, then the agreement probability
$h_{T}(p,\alpha)$ for noise support $\mathcal{N}_{sp}\in\\{1,\alpha\\}$ is
given by

$h_{T}({p},{\alpha})=\begin{cases}1,&if~{}\tilde{\pi}(i)=T,~{}\forall~{}i\in
T\\\
(1-p)+p^{|\mathcal{R}(T)|+1-|\mathcal{J}(\alpha,T)|},&otherwise,\end{cases}$
(15)

where
$\mathcal{J}(\alpha,T)\coloneqq\left\\{\tilde{\pi}(i)\in\mathcal{R}(T)~{}\bigg{|}~{}\frac{\tilde{v}_{i}(\tilde{\pi}(i))}{\tilde{v}_{i}(T)}\geq\frac{1}{\alpha}\right\\}.$

######  Proof A.6.

From Theorem 3.1 of the main paper, we have the following

$\mathbb{P}[\cup_{i\in T}v_{i}(\tilde{\pi}(i))\geq
v_{i}(T)]\geq(1-\tilde{\epsilon})h_{T}(\textit{{p}},\boldsymbol{\alpha}).$

To get $h_{T}({p},{\alpha})\coloneqq\mathbb{P}[F(T,\tilde{\pi})]$ we consider
two cases viz. $\mathcal{J}(\alpha,T)=\emptyset$, and
$\mathcal{J}(\alpha,T)\neq\emptyset$. For these cases, we identify the
possible noise values elements of $F(T,\tilde{\pi})$.

  * •

Case 01: [$\mathcal{J}(\alpha,T)=\emptyset$]. In this case, we have the
following possibilities:

    * –

$\alpha(\tilde{\pi}(i))=\alpha,~{}\forall~{}\tilde{\pi}(i)\in\mathcal{R}(T)$,
and $\alpha(T)=\alpha$. Probability of such a choice of $\alpha$’s is

$p^{|\mathcal{R}(T)|+1}.$ (16)

    * –

$\alpha(\tilde{\pi}(i))=1$ for $k\in\\{0,1,\dots,|\mathcal{R}(T)|\\}$
coalitions $\tilde{\pi}(i)\in\mathcal{R}(T)$, and
$\alpha(\tilde{\pi}(i))=\alpha$ for remaining $|\mathcal{R}(T)|-k$ coalitions.
Moreover, $\alpha(T)=1$. Probability of such choice of $\alpha$’s is
$(1-p)^{k}p^{|\mathcal{R}(T)|-k}(1-p)$. Further, there are
$|\mathcal{R}(T)|\choose k$ ways of selecting $k$ coalitions $\tilde{\pi}(i)$
from $\mathcal{R}(T)$. Thus, the overall probability is

$\sum_{k=0}^{|\mathcal{R}(T)|}{|\mathcal{R}(T)|\choose
k}(1-p)^{k}p^{|\mathcal{R}(T)|-k}(1-p)=1-p.$ (17)

  * •

Case 02: [$\mathcal{J}(\alpha,T)\neq\emptyset$]. In addition to the above
possible cases, we have a few other cases:

    * –

$\alpha(\tilde{\pi}(i))=1$ for any
$k\in\\{1,2,\dots,|\mathcal{J}(\alpha,T)|\\}$ coalitions
$\tilde{\pi}(i)\in\mathcal{J}(\alpha,T)$. Moreover,
$\alpha(\tilde{\pi}(i))=\alpha$ for remaining coalitions in $\mathcal{R}(T)$.
Also, $\alpha(T)=\alpha$. Probability of such choice of $\alpha$’s is
$(1-p)^{k}p^{|\mathcal{R}(T)|-k}p=(1-p)^{k}p^{|\mathcal{R}(T)|-k+1}$. And
there are $|\mathcal{J}(\alpha,T)|\choose k$ ways of selecting $k$ coalitions
$\tilde{\pi}(i)\in\mathcal{J}(\alpha,T)$. Thus the overall probability is

$\sum_{k=1}^{|\mathcal{J}(\alpha,T)|}{|\mathcal{J}(\alpha,T)|\choose
k}(1-p)^{k}p^{|\mathcal{R}(T)|-k+1}.$ (18)

The probability $\mathbb{P}[F(T,\tilde{\pi})]$ is obtained by adding
probabilities given in Equations (16), (17) and (18).

$\displaystyle\mathbb{P}[F(T,\tilde{\pi})]$ $\displaystyle=$ $\displaystyle
p^{|\mathcal{R}(T)|+1}+(1-p)+\sum_{k=1}^{|\mathcal{J}(\alpha,T)|}{|\mathcal{J}(\alpha,T)|\choose
k}(1-p)^{k}p^{|\mathcal{R}(T)|-k+1}$ $\displaystyle=$ $\displaystyle
p^{|\mathcal{R}(T)|+1}+(1-p)+p^{|\mathcal{R}(T)|-|\mathcal{J}(\alpha,T)|+1}\Bigg{[}1-p^{|\mathcal{J}(\alpha,T)|}\Bigg{]}$
$\displaystyle=$
$\displaystyle(1-p)+p^{|\mathcal{R}(T)|-|\mathcal{J}(\alpha,T)|+1}.$

This ends the proof.

If $\tilde{\pi}(i)\neq T$ for at least one $i\in T$, then
$h_{T}({p},{\alpha})=1,~{}\forall~{}\alpha$ if $p=0$ or $p=1$. That is, if the
value of all coalitions are retained, or if value of all of them are inflated
by $\alpha$, then coalition $T\succeq_{i}\tilde{\pi}(i)$, and
$T\succeq_{i}^{\prime}\tilde{\pi}(i)$ for all $i\in T$. Thus, neither noise-
free nor noisy game will have $\tilde{\pi}$ as PAC stable outcome. Moreover,
if we allow $h_{T}(p,\alpha)=\eta$ for some user-given satisfaction $\eta$, we
get a noise set in accordance to the Remark 3.3 in the main paper. In this
case, the noise set also depends on $|\mathcal{R}(T)|$, and
$|\mathcal{J}(\alpha,T)|$ for coalition $T$. Hence, the partition is $\eta$
noise-robust non core-stable for the noise set $I^{\star}(T,\eta)$.

###  A.3 Proof of Theorem 3.4

######  Proof A.7.

We will prove this via Mathematical induction on the noise support $l\geq 2$.
Clearly, this is true for $l=2$ (from Lemma A.5 above). Let us assume that it
is true for $l=k$, i.e.; there are sets

$\mathcal{J}(\alpha_{r},\alpha_{s},T)=\left\\{\tilde{\pi}(i)\in\mathcal{R}(T)~{}\bigg{|}~{}\frac{\tilde{v}_{i}(\tilde{\pi}(i))}{\tilde{v}_{i}(T)}\geq\frac{\alpha_{s}}{\alpha_{r}}\right\\},$

such that the support
$\alpha(S)=\\{\alpha_{1},\dots,\alpha_{k}\\},~{}\forall~{}S\subseteq N$ where
$\alpha_{s}<\alpha_{r},~{}\forall~{}1\leq s<r\leq k$. For this $k$ we have
$f_{T}(p_{j},\alpha_{j}:j\in[k])=:h_{T}(\textit{{p}},\boldsymbol{\alpha})$ (by
assumption)

$h_{T}(\textit{{p}},\boldsymbol{\alpha})=\sum_{a=1}^{k}p_{a}\left(\sum_{b=a}^{k}p_{b}\right)^{|\mathcal{R}(T)|}+\sum_{r,s\in[k]:\alpha_{r}>\alpha_{s}}p_{r}^{|\mathcal{R}(T)|-|\mathcal{J}(\alpha_{r},\alpha_{s},T)|+1}((p_{r}+p_{s})^{|\mathcal{J}(\alpha_{r},\alpha_{s},T)|}-p_{r}^{|\mathcal{J}(\alpha_{r},\alpha_{s},T)|}).$

We will now show that this is true for $l=k+1$. To this end define
$\mathcal{J}(\alpha_{k+1},\alpha_{s},T)$ for all $s\in[k]$ such that
$\alpha_{k+1}>\alpha_{s}$

$\mathcal{J}(\alpha_{k+1},\alpha_{s},T)=\left\\{\tilde{\pi}(i)\in\mathcal{R}(T)~{}\bigg{|}~{}\frac{\tilde{v}_{i}(\tilde{\pi}(i))}{\tilde{v}_{i}(T)}\geq\frac{\alpha_{s}}{\alpha_{k+1}}\right\\}.$

Now, there are two cases,
$\mathcal{J}(\alpha_{k+1},\alpha_{s},T)=\emptyset,~{}\forall~{}\alpha_{s},~{}s\in[k]$,
or $\mathcal{J}(\alpha_{k+1},\alpha_{s},T)\neq\emptyset$ for at least for one
$s\in[k]$.

Case 01:
[$\mathcal{J}(\alpha_{k+1},\alpha_{s},T)=\emptyset,~{}\forall~{}\alpha_{s},~{}s\in[k]$].
Apart from the existing
$\\{\alpha(\tilde{\pi}(i)\\}_{\tilde{\pi}(i)\in\mathcal{R}(T)}$ and
$\alpha(T)$ for $k$ support case, with this extra $k+1$, it will also have
$\alpha(T)=\alpha_{k+1}$ and
$\alpha(\tilde{\pi}(i))=\alpha_{k+1},~{}\forall~{}\tilde{\pi}(i)\in\mathcal{R}(T)$.
The probability of such extra $\alpha$’s is
$p_{k+1}\left(\sum_{b=k+1}^{k+1}p_{b}\right)^{|\mathcal{R}(T)|}$. Therefore,
the overall probability is

$\sum_{a=1}^{k}p_{a}\left(\sum_{b=a}^{k}p_{b}\right)^{|\mathcal{R}(T)|}+p_{k+1}\left(\sum_{b=k+1}^{k+1}p_{b}\right)^{|\mathcal{R}(T)|}=\sum_{a=1}^{k+1}p_{a}\left(\sum_{b=a}^{k+1}p_{b}\right)^{|\mathcal{R}(T)|}.$

Case 02: [$\mathcal{J}(\alpha_{k+1},\alpha_{s},T)\neq\emptyset$ for at least
one $s\in[k]$]. In this case, apart from all $\alpha(T)$ and
$\\{\alpha(\tilde{\pi}(i))\\}_{\tilde{\pi}(i)\in\mathcal{J}(\alpha_{r},\alpha_{s},T)}$,
we have
$\\{\alpha(\tilde{\pi}(i))\\}_{\forall~{}\tilde{\pi}(i)\in\mathcal{J}(\alpha_{k+1},\alpha_{r},T)},\alpha(T)$.
For this set, the possible pairs are such that
$\alpha(\tilde{\pi}(i))=\alpha_{r},~{}~{}\forall~{}\tilde{\pi}(i)\in\mathcal{R}(T)\setminus\mathcal{J}(\alpha_{k+1},\alpha_{r},T)$,
and $\alpha(T)=\alpha_{k+1}$. Thus, their combined probability is
$p_{k+1}^{|\mathcal{R}(T)|-|\mathcal{J}(\alpha_{k+1},\alpha_{s},T)|+1}((p_{k+1}-p_{s})^{|\mathcal{J}(\alpha_{k+1},\alpha_{r},T)|}-p_{k+1}^{|\mathcal{J}(\alpha_{k+1},\alpha_{r},T)|})$.
Hence for $k+1$ support, the probability is

$\displaystyle\sum_{r,s\in[k]:\alpha_{r}>\alpha_{s}}p_{r}^{|\mathcal{R}(T)|-|\mathcal{J}(\alpha_{r},\alpha_{r},T)|+1}((p_{r}+p_{s})^{|\mathcal{J}(\alpha_{r},\alpha_{s},T)|}-p_{r}^{|\mathcal{J}(\alpha_{r},\alpha_{s},T)|})$
$\displaystyle\hskip
22.76219pt+~{}p_{k+1}^{|\mathcal{R}(T)|-|\mathcal{J}(\alpha_{k+1},\alpha_{s},T)|+1}((p_{k+1}+p_{s})^{|\mathcal{I}(\alpha_{k+1},\alpha_{s},T)|}-p_{k+1}^{|\mathcal{J}(\alpha_{k+1},\alpha_{s},T)|}).$

From case 01 and case 02 with $k+1$ support, we have

$\displaystyle h_{T}(p_{j},\alpha_{j};j\in[k+1])$ $\displaystyle=$
$\displaystyle\sum_{r,s\in[k+1]:\alpha_{r}>\alpha_{s}}p_{r}^{|\mathcal{R}(T)|-|\mathcal{J}(\alpha_{r},\alpha_{s},T)|+1}\left((p_{r}+p_{s})^{|\mathcal{J}(\alpha_{r},\alpha_{s},T)|}-p_{r}^{|\mathcal{J}(\alpha_{r},\alpha_{s},T)|}\right)$
$\displaystyle~{}~{}~{}~{}~{}+\sum_{a=1}^{k+1}p_{a}\left(\sum_{b=a}^{k+1}p_{b}\right)^{|\mathcal{R}(T)|}.$

Furthermore, it is true for $k+1$ support. Thus, from the principle of
Mathematical induction, this is true for any $l\geq 2$.

###  A.4 2 agent 2 support model

In this Section, we will provide further details about the 2 agents’ full
information noisy game with 2 support of the noise distribution. First, we
consider the following noisy game.

$\tilde{v}_{1}(12)>\tilde{v}_{1}(1);\hskip
5.69054pt\tilde{v}_{2}(12)>\tilde{v}_{2}(2).$ (game 1)

We also consider the other possible noisy games with 2 agents in later
subsections.

####  A.4.1 Proof of Lemma 4.1

######  Proof A.8.

For noisy game 1, we have $\tilde{\pi}=N$. Now, consider the noise support
$\mathcal{N}_{sp}=\\{1,\alpha\\}$, where $\alpha>1$ such that
$\mathbb{P}[\alpha(S)=\alpha]=p=1-\mathbb{P}[\alpha(S)=1]$, for some fixed and
unknown $p$. Given noisy game 1, there are 8 possible combinations of
$\alpha$’s (because each coalition has two options). We will now enumerate all
such possibilities:

  1. 1.

$\alpha(1)=1;\alpha(2)=1;~{}\alpha(12)=1$. The probability of such alpha is
$(1-p)^{3}$. Thus, the noise-free values are
$v_{1}(1)=\tilde{v}_{1}(1);~{}v_{2}(2)=\tilde{v}_{2}(2),v_{1}(12)=\tilde{v}_{1}(12)~{}and~{}v_{2}(12)=\tilde{v}_{2}(12)$.
Therefore, The noise-free game is:

$\displaystyle{v}_{1}(12)>{v}_{1}(1);\hskip 5.69054pt{v}_{2}(12)>{v}_{2}(2).$

From this game we have $\pi=\tilde{\pi}=N$.

  2. 2.

$\alpha(1)=1;\alpha(2)=1;~{}\alpha(12)=\alpha$ Probability of such alpha’s is
$p(1-p)^{2}$. Thus the actual values are
$v_{1}(1)=\tilde{v}_{1}(1);~{}v_{2}(2)=\tilde{v}_{2}(2),v_{1}(12)=\frac{\tilde{v}_{1}(12)}{\alpha}~{}and~{}v_{2}(12)=\frac{\tilde{v}_{2}(12)}{\alpha}$.
Therefore, the actual preferences will depend on the relative values of
$\alpha$ and $\tilde{\textbf{{v}}}$. If $\alpha$ and $\tilde{\textbf{{v}}}$’s
are such that $\frac{\tilde{v}_{1}(12)}{\alpha}>\tilde{v}_{1}(1)$ and
$\frac{\tilde{v}_{2}(12)}{\alpha}>\tilde{v}_{2}(2)$, then $\pi=N$, otherwise
$\pi=\\{\\{1\\},\\{2\\}\\}$.

  3. 3.

$\alpha(1)=1;\alpha(2)=\alpha;~{}\alpha(12)=1$. The probability of such alpha
is $p(1-p)^{2}$. Thus, the actual values are
$v_{1}(1)=\tilde{v}_{1}(1);~{}v_{2}(2)=\frac{\tilde{v}_{2}(2)}{\alpha},v_{1}(12)=\tilde{v}_{1}(12)~{}and~{}v_{2}(12)=\tilde{v}_{2}(12)$.
Since, $\tilde{v}_{2}(12)>\tilde{v}_{2}(2)>\frac{\tilde{v}_{2}(2)}{\alpha}$.
The noise-free game is:

$\displaystyle{v}_{1}(12)>{v}_{1}(1);\hskip 5.69054pt{v}_{2}(12)>{v}_{2}(2).$

So, we have $\pi=\tilde{\pi}=N$.

  4. 4.

$\alpha(1)=\alpha;~{}\alpha(2)=1;~{}\alpha(12)=1$. Probability of such alpha’s
is $p(1-p)^{2}$. Thus, the actual values are
$v_{1}(1)=\frac{\tilde{v}_{1}(1)}{\alpha};~{}~{}v_{2}(2)=\tilde{v}_{2}(2),v_{1}(12)=\tilde{v}_{1}(12)~{}and~{}v_{2}(12)=\tilde{v}_{2}(12)$.
Since, $\tilde{v}_{1}(12)>\tilde{v}_{1}(1)>\frac{\tilde{v}_{1}(1)}{\alpha}.$
Therefore The noise-free game is:

$\displaystyle{v}_{1}(12)>{v}_{1}(1);\hskip 5.69054pt{v}_{2}(12)>{v}_{2}(2).$

From this game we have $\pi=\tilde{\pi}=N$.

  5. 5.

$\alpha(1)=1;\alpha(2)=\alpha;~{}\alpha(12)=\alpha$. The probability of this
alpha is $p^{2}(1-p)$. Thus, the actual values are
$v_{1}(1)=\tilde{v}_{1}(1);~{}v_{2}(2)=\frac{\tilde{v}_{2}(2)}{\alpha},v_{1}(12)=\frac{\tilde{v}_{1}(12)}{\alpha}~{}and~{}v_{2}(12)=\frac{\tilde{v}_{2}(12)}{\alpha}$.
The actual preferences will depend on the relative values of $\alpha$ and
$\tilde{\textbf{{v}}}$. If $\alpha$ and $\tilde{\textbf{{v}}}$’s are such that
$\frac{\tilde{v}_{1}(12)}{\alpha}>\tilde{v}_{1}(1)$, then $\pi=N$, otherwise
$\pi=\\{\\{1\\},\\{2\\}\\}$.

  6. 6.

$\alpha(1)=\alpha;\alpha(2)=1;~{}\alpha(12)=\alpha$. The probability of such
alpha is $p^{2}(1-p)$. Thus, the actual values are
$v_{1}(1)=\frac{\tilde{v}_{1}(1)}{\alpha},~{}~{}v_{2}(2)=\tilde{v}_{2}(2);~{}v_{1}(12)=\frac{\tilde{v}_{1}(12)}{\alpha}~{}and~{}v_{2}(12)=\frac{\tilde{v}_{2}(12)}{\alpha}$.
The actual preferences will depend on the relative values of $\alpha$ and
$\tilde{\textbf{{v}}}$. If $\alpha$ and $\tilde{\textbf{{v}}}$’s are such that
$\frac{\tilde{v}_{2}(12)}{\alpha}>\tilde{v}_{2}(2)$, then $\pi=N$ otherwise
$\pi=\\{\\{1\\},\\{2\\}\\}$.

  7. 7.

$\alpha(1)=\alpha;\alpha(2)=\alpha;~{}\alpha(12)=1$. Probability of such
alpha’s is $p^{2}(1-p)$. Thus, the actual values are
$v_{1}(1)=\frac{\tilde{v}_{1}(1)}{\alpha},~{}~{}v_{2}(2)=\frac{\tilde{v}_{2}(2)}{\alpha};~{}v_{1}(12)=\tilde{v}_{1}(12)~{}and~{}v_{2}(12)=\tilde{v}_{2}(12)$.
Since, $\tilde{v}_{1}(12)>\tilde{v}_{1}(1)>\frac{\tilde{v}_{1}(1)}{\alpha}.$
and, $\tilde{v}_{2}(12)>\tilde{v}_{2}(2)>\frac{\tilde{v}_{2}(2)}{\alpha}.$ The
noise-free game is:

$\displaystyle{v}_{1}(12)>{v}_{1}(1);\hskip 5.69054pt{v}_{2}(12)>{v}_{2}(2).$

From this game we have $\pi=\tilde{\pi}=N$.

  8. 8.

$\alpha(1)=\alpha;\alpha(2)=\alpha;~{}\alpha(12)=\alpha$. The probability of
such alpha is $p^{3}$. Thus, the actual values are
$v_{1}(1)=\frac{\tilde{v}_{1}(1)}{\alpha},~{}~{}v_{2}(2)=\frac{\tilde{v}_{2}(2)}{\alpha};~{}v_{1}(12)=\frac{\tilde{v}_{1}(12)}{\alpha}~{}and~{}v_{2}(12)=\frac{\tilde{v}_{2}(12)}{\alpha}$.
Therefore, the noise-free game is:

$\displaystyle{v}_{1}(12)>{v}_{1}(1);\hskip 5.69054pt{v}_{2}(12)>{v}_{2}(2).$

From this game it is clear that $\pi=\tilde{\pi}=N$.

Recall,
$\overline{r}=\max\left\\{\frac{\tilde{v}_{1}(12)}{\tilde{v}_{1}(1)},\frac{\tilde{v}_{2}(12)}{\tilde{v}_{2}(2)}\right\\}$,
and
$\underline{r}=\min\left\\{\frac{\tilde{v}_{1}(12)}{\tilde{v}_{1}(1)},\frac{\tilde{v}_{2}(12)}{\tilde{v}_{2}(2)}\right\\}$.
Out of 8 cases there are 5 cases (case 1,3,4,7,8) in which the grand coalition
$\pi=\tilde{\pi}=N$ is formed in noise-free game. In these conditions, the
relative value of $\tilde{v}_{1}(\cdot),\tilde{v}_{2}(\cdot)$ should satisfy
$\alpha\geq\overline{r}$, and this constitute the first expression
$p^{3}+p^{2}(1-p)+2p(1-p)^{2}+(1-p)^{3}$ of
$\mathbb{P}[\pi=\tilde{\pi}~{}|~{}game~{}1]$. Apart from this, if the
inflation interval is $\underline{r}\leq\alpha<\overline{r}$, then
$\pi=\tilde{\pi}=N$ is also possible from case (6) with probability
$p^{2}(1-p)$. Thus, $p^{2}(1-p)$ will be added to the above prediction
probability. So, we have $\mathbb{P}[\pi=\tilde{\pi}~{}|~{}game~{}1]$
corresponding to it. Moreover, finally, if $\alpha<\underline{r}$, all cases
are allowable, and hence the grand coalition will always form in the noise-
free game. Thus,

$\mathbb{P}[\pi=\tilde{\pi}~{}|~{}game~{}1]=\begin{cases}p^{3}+p^{2}(1-p)+2p(1-p)^{2}+(1-p)^{3},&if~{}\alpha\geq\overline{r}\\\
p^{3}+2p^{2}(1-p)+2p(1-p)^{2}+(1-p)^{3},&if~{}\underline{r}\leq\alpha<\overline{r}\\\
1,&if~{}\alpha<\underline{r}.\end{cases}$ (19)

Simplifying these polynomials, we have

$\displaystyle\mathbb{P}[\pi=\tilde{\pi}~{}|~{}game~{}1]=\begin{cases}1-p(1-p^{2}),&if~{}\alpha\geq\overline{r}\\\
1-p(1-p),&if~{}\underline{r}\leq\alpha<\overline{r}\\\
1,&if~{}\alpha<\underline{r}.\end{cases}$ (20)

This ends the proof.

If we allow some user given satisfaction $\zeta$ on the prediction
probability, i.e., $\mathbb{P}[\pi=\tilde{\pi}~{}|~{}game~{}1]=\zeta$, we get
the following noise interval

$I^{\star}(\zeta=0.9)=\begin{cases}[0,0.101]\cup[0.946,1],&~{}if~{}\alpha\geq\overline{r};\\\
[0,0.113]\cup[0.887,1],&~{}if~{}\underline{r}\leq\alpha<\overline{r}\\\
1,&~{}if~{}\alpha<\underline{r}.\end{cases}$ (21)

####  A.4.2 Details of the other 2 agent noisy games

Here we will give the prediction probabilities for other possible noisy games
with 2 agents and 2 noise support.

Both agents prefer staying alone in noisy game

As opposed to the noisy game 1, in noisy game 2 both agents prefer to stay
alone. The noisy preferences of agents are as follows:

$\tilde{v}_{1}(1)>\tilde{v}_{1}(12);\hskip
5.69054pt\tilde{v}_{2}(2)>\tilde{v}_{2}(12).$ (game 2)

Clearly $\tilde{\pi}=\\{\\{1\\},\\{2\\}\\}\neq N$ is the core-stable outcome.
The following lemma provides prediction probability,
$\mathbb{P}[\pi=\tilde{\pi}~{}|~{}game~{}2]$ for noisy game 2.

######  Lemma A.9.

For noisy game 2 with full information of $\tilde{\textbf{{v}}}$’s, the
prediction probability that unknown noise-free game has $\pi=\tilde{\pi}$ as a
core-stable outcome is

$\displaystyle\mathbb{P}[\pi=\tilde{\pi}~{}|~{}game~{}2]=\begin{cases}1-p^{2}(1-p),&if~{}\frac{1}{\alpha}<\underline{r}\\\
1,&if~{}\frac{1}{\alpha}\geq\underline{r}.\end{cases}$ (22)

Moreover, the minimal and maximal values of above prediction probability are
$0.85$ (when $p=2/3$), and $1$, respectively.

Similar to game 1, the probability of formation of partition
$\pi=\\{\\{1\\},\\{2\\}\\}$ in an unknown noise-free game is always more than
$0.85$. So, the safety value is $0.85$. The prediction probability is $1$ when
$\frac{1}{\alpha}\geq\underline{r}$ for any noise probability $p$. Moreover,
for some user-given satisfaction $\zeta$, we obtain the corresponding $p$ by
setting $\mathbb{P}[\pi=\\{\\{1\\},\\{2\\}\\}~{}|~{}game~{}2]=\zeta$. In
particular, we have

$I^{\star}(\zeta=0.9)=\begin{cases}[0,0.413]\cup[0.867,1],&~{}if~{}\frac{1}{\alpha}<\underline{r}\\\
[0,1],&~{}\frac{1}{\alpha}\geq\underline{r}.\end{cases}$ (23)

It is easy to see that the allowable $p$ is larger than the interval given in
Equation (21) for game 1. So, the partition
$\tilde{\pi}=\\{\\{1\\},\\{2\\}\\}$ is noise robust for larger number of
inflation probabilities $p$. Again the noise set will shrink if we increase
the satisfaction $\zeta$.

Figure 2: The prediction probability
$\mathbb{P}[\pi=\tilde{\pi}~{}|~{}game~{}2]$. For $\zeta=0.9$, the noise
regimes are given in Equation (23).

Agent 1 prefers to stay alone and agent 2 prefers grand coalition in noisy
game

Now, we consider a noisy game where agent 1 prefers to stay alone, whereas
agent 2 prefers the grand coalition. In particular, the preferences in the
noisy game are

$\tilde{v}_{1}(1)>\tilde{v}_{1}(12);\hskip
5.69054pt\tilde{v}_{2}(12)>\tilde{v}_{2}(2).$ (game 3)

Again $\tilde{\pi}=\\{\\{1\\},\\{2\\}\\}\neq N$ is noisy core-stable outcome.
The prediction probability, $\mathbb{P}[\pi=\tilde{\pi}~{}|~{}game~{}3]$ is
given in the Lemma below.

######  Lemma A.10.

For noisy game 3 with full information of $\tilde{\textbf{{v}}}$’s, the
prediction probability that unknown noise-free game has $\pi=\tilde{\pi}$ as a
core-stable outcome is given by:

$\displaystyle\mathbb{P}[\pi=\tilde{\pi}~{}|~{}game~{}3]=\begin{cases}1-p(1-p),&if~{}\frac{1}{\alpha}<\frac{\tilde{v}_{1}(12)}{\tilde{v}_{1}(1)}\\\
1,&if~{}\frac{1}{\alpha}\geq\frac{\tilde{v}_{1}(12)}{\tilde{v}_{1}(1)}.\end{cases}$
(24)

Moreover, the minimal and maximal values of above prediction probability are
$0.75$ (when $p=0.5$), and $1$, respectively.

Similar to game 1 and game 2 the probability of formation of partition
$\pi=\\{\\{1\\},\\{2\\}\\}$ in an unknown noise-free game is always more than
$0.75$ that is the safety value for game 3. The prediction probability is $1$
when $\frac{1}{\alpha}\geq\frac{\tilde{v}_{1}(12)}{\tilde{v}_{1}(1)}$ for any
noise probability $p$. Moreover, for some user-given satisfaction, $\zeta$ we
obtain the corresponding $p$ by setting
$\mathbb{P}[\pi=\\{\\{1\\},\\{2\\}\\}~{}|~{}game~{}3]=\zeta$. In particular,

$I^{\star}(\zeta=0.9)=\begin{cases}[0,0.113]\cup[0.887,1],&~{}if~{}\frac{1}{\alpha}<\frac{\tilde{v}_{1}(12)}{\tilde{v}_{1}(1)}\\\
[0,1],&~{}if~{}\frac{1}{\alpha}\geq\frac{\tilde{v}_{1}(12)}{\tilde{v}_{1}(1)}.\end{cases}$
(25)

The following figure shows the prediction probabilities for game 3.

Figure 3: The prediction probability
$\mathbb{P}[\tilde{\pi}=\pi~{}|~{}game~{}3]$. For $\zeta=0.9$, we obtain the
noise regimes as given in Equation (25).

Agent 1 prefers grand coalition and agent 2 prefers to stay alone

Finally, consider a noisy game symmetric to game 3. Here agent 1 prefers a
grand coalition, and agent 2 prefers to stay alone. In particular, we have the
following preferences.

$\tilde{v}_{1}(12)>\tilde{v}_{1}(1);\hskip
5.69054pt\tilde{v}_{2}(2)>\tilde{v}_{2}(12).$ (game 4)

Again $\tilde{\pi}=\\{\\{1\\},\\{2\\}\\}\neq N$ is a noisy core-stable
outcome. In the following lemma, we find the prediction probability when noisy
game 4 is considered.

######  Lemma A.11.

For noisy game 4 with full information of $\tilde{\textbf{{v}}}$’s, the
prediction probability that noise-free game has $\pi=\tilde{\pi}$ as as core-
stable outcome is given by:

$\displaystyle\mathbb{P}[\pi=\tilde{\pi}~{}|~{}game~{}4]=\begin{cases}1-p(1-p),&if~{}\frac{1}{\alpha}<\frac{\tilde{v}_{2}(12)}{\tilde{v}_{2}(2)}\\\
1,&if~{}\frac{1}{\alpha}\geq\frac{\tilde{v}_{2}(12)}{\tilde{v}_{2}(2)}.\end{cases}$
(26)

So, the minimal and maximal values of above prediction probability are $0.75$
(when $p=0.5$) and $1$ respectively.

In this case also, the noise regime can be obtained using
$\mathbb{P}[\pi=\tilde{\pi}~{}|~{}game~{}4]=\zeta$. In particular,

$I^{\star}(\zeta=0.9)=\begin{cases}[0,0.113]\cup[0.887,1],&~{}if~{}\frac{1}{\alpha}<\frac{\tilde{v}_{2}(12)}{\tilde{v}_{2}(2)}\\\
[0,1],&~{}if~{}\frac{1}{\alpha}\geq\frac{\tilde{v}_{2}(12)}{\tilde{v}_{2}(2)}.\end{cases}$
(27)

Figure 4 shows the prediction probabilities for game 4.

Figure 4: The prediction probability
$\mathbb{P}[\pi=\tilde{\pi}~{}|~{}game~{}4]$. For $\zeta=0.9$, we obtain the
noise regimes as given in Equation (27).

###  A.5 2 agents 3 support noise model

In this section, we consider two player noisy hedonic game with three support
noise model, i.e., $\mathcal{N}_{sp}=\\{1,\alpha_{1},\alpha_{2}\\}$, with
$\alpha_{1}>1$, and $\alpha_{2}<1$. Note that $\alpha_{1},\alpha_{2}>0$. Let
$\mathbb{P}[\alpha(S)=\alpha_{1}]=p_{1};~{}\mathbb{P}[\alpha(S)=\alpha_{2}]=p_{2};~{}and~{}\mathbb{P}[\alpha(S)=1]=1-p_{1}-p_{2}$.
That is the value of each coalition is either inflated with probability
$p_{1}$, or deflated with probability $p_{2}$ or retained with probability
$1-p_{1}-p_{2}$. The following lemma provides the prediction probability for
game 1.

####  A.5.1 Proof of Lemma 4.3

######  Proof A.12.

For game 1, with $l=3$ support of noise there are 27 possible cases for
$\alpha$’s. Since there are 3 coalitions, each coalition’s value can either be
retained, inflated by $\alpha_{1}$, or deflated by $\alpha_{2}$. We will now
enumerate all of them:

  1. 1.

$\alpha(1)=1;\alpha(2)=1;~{}\alpha(12)=1$ Probability of such alpha’s is
$(1-p_{1}-p_{2})^{3}$. Thus, the actual values are
$v_{1}(1)=\tilde{v}_{1}(1);~{}v_{2}(2)=\tilde{v}_{2}(2),v_{1}(12)=\tilde{v}_{1}(12)~{}and~{}v_{2}(12)=\tilde{v}_{2}(12)$.
The noise-free game is: ${v}_{1}(12)>{v}_{1}(1)$; ${v}_{2}(12)>{v}_{2}(2)$.
So, $\pi=\tilde{\pi}$ in this case.

  2. 2.

$\alpha(1)=1;\alpha(2)=1;~{}\alpha(12)=\alpha_{1}$. Probability of such
alpha’s is $p_{1}(1-p_{1}-p_{2})^{2}$. Thus, the actual values are
$v_{1}(1)=\tilde{v}_{1}(1);~{}v_{2}(2)=\tilde{v}_{2}(2),v_{1}(12)=\frac{\tilde{v}_{1}(12)}{\alpha_{1}}~{}and~{}v_{2}(12)=\frac{\tilde{v}_{2}(12)}{\alpha_{1}}$.
The noise-free game preferences are unclear; they will depend on the relative
values of $\alpha_{1}$ and $\tilde{v}$. If $\alpha_{1}$ and $\tilde{v}$’s are
such that $\frac{\tilde{v}_{1}(12)}{\alpha_{1}}>\tilde{v}_{1}(1)$ and
$\frac{\tilde{v}_{2}(12)}{\alpha_{1}}>\tilde{v}_{2}(2)$ then $\pi=N$,
otherwise $\pi=\\{\\{1\\},\\{2\\}\\}$.

  3. 3.

$\alpha(1)=1;\alpha(2)=\alpha_{1};~{}\alpha(12)=1$. Probability of such
alpha’s is $p_{1}(1-p_{1}-p_{2})^{2}$. Thus, the actual values are
$v_{1}(1)=\tilde{v}_{1}(1);~{}v_{2}(2)=\frac{\tilde{v}_{2}(2)}{\alpha_{1}},v_{1}(12)=\tilde{v}_{1}(12)~{}and~{}v_{2}(12)=\tilde{v}_{2}(12)$.
Since
$\tilde{v}_{2}(12)>\tilde{v}_{2}(2)>\frac{\tilde{v}_{2}(2)}{\alpha_{1}}.$ The
noise-free game is: ${v}_{1}(12)>{v}_{1}(1)$; ${v}_{2}(12)>{v}_{2}(2)$. So,
$\pi=\tilde{\pi}$ in this case.

  4. 4.

$\alpha(1)=\alpha_{1};~{}\alpha(2)=1;~{}\alpha(12)=1$. Probability of such
alpha’s is $p_{1}(1-p_{1}-p_{2})^{2}$. Thus, the actual values are
$v_{1}(1)=\frac{\tilde{v}_{1}(1)}{\alpha_{1}};~{}~{}v_{2}(2)=\tilde{v}_{2}(2),v_{1}(12)=\tilde{v}_{1}(12)~{}and~{}v_{2}(12)=\tilde{v}_{2}(12)$.
Since,
$\tilde{v}_{1}(12)>\tilde{v}_{1}(1)>\frac{\tilde{v}_{1}(1)}{\alpha_{1}}$. The
noise-free game is: ${v}_{1}(12)>{v}_{1}(1)$; ${v}_{2}(12)>{v}_{2}(2)$. So,
$\pi=\tilde{\pi}$ in this case.

  5. 5.

$\alpha(1)=1;\alpha(2)=\alpha_{1};~{}\alpha(12)=\alpha_{1}$. Probability of
such alpha’s is $p_{1}^{2}(1-p_{1}-p_{2})$. Thus, the actual values are
$v_{1}(1)=\tilde{v}_{1}(1);~{}v_{2}(2)=\frac{\tilde{v}_{2}(2)}{\alpha_{1}},v_{1}(12)=\frac{\tilde{v}_{1}(12)}{\alpha_{1}}~{}and~{}v_{2}(12)=\frac{\tilde{v}_{2}(12)}{\alpha_{1}}$.
The noise-free game preferences are unclear; they will depend on the relative
values of $\alpha_{1}$ and $\tilde{v}$. If $\alpha_{1}$ and $\tilde{v}$’s are
such that $\frac{\tilde{v}_{1}(12)}{\alpha_{1}}>\tilde{v}_{1}(1)$, then
$\pi=N$, otherwise $\pi=\\{\\{1\\},\\{2\\}\\}$.

  6. 6.

$\alpha(1)=\alpha_{1};\alpha(2)=1;~{}\alpha(12)=\alpha_{1}$. Probability of
such alpha’s is $p_{1}^{2}(1-p_{1}-p_{2})$. Thus, the actual values are
$v_{1}(1)=\frac{\tilde{v}_{1}(1)}{\alpha_{1}},~{}~{}v_{2}(2)=\tilde{v}_{2}(2);~{}v_{1}(12)=\frac{\tilde{v}_{1}(12)}{\alpha_{1}}~{}and~{}v_{2}(12)=\frac{\tilde{v}_{2}(12)}{\alpha_{1}}$.
The noise-free game preferences are unclear; they will depend on the relative
values of $\alpha_{1}$ and $\tilde{v}$. If $\alpha_{1}$ and $\tilde{v}$’s are
such that $\frac{\tilde{v}_{2}(12)}{\alpha_{1}}>\tilde{v}_{2}(2)$, then
$\pi=N$, otherwise $\pi=\\{\\{1\\},\\{2\\}\\}$.

  7. 7.

$\alpha(1)=\alpha_{1};\alpha(2)=\alpha_{1};~{}\alpha(12)=1$. Probability of
such alpha’s is $p_{1}^{2}(1-p_{1}-p_{2})$. Thus, the actual values are
$v_{1}(1)=\frac{\tilde{v}_{1}(1)}{\alpha_{1}},~{}~{}v_{2}(2)=\frac{\tilde{v}_{2}(2)}{\alpha_{1}};~{}v_{1}(12)=\tilde{v}_{1}(12)~{}and~{}v_{2}(12)=\tilde{v}_{2}(12)$.
Since,
$\tilde{v}_{1}(12)>\tilde{v}_{1}(1)>\frac{\tilde{v}_{1}(1)}{\alpha_{1}}.$ and,
$\tilde{v}_{2}(12)>\tilde{v}_{2}(2)>\frac{\tilde{v}_{2}(2)}{\alpha_{1}}.$ The
noise-free game is: ${v}_{1}(12)>{v}_{1}(1)$; ${v}_{2}(12)>{v}_{2}(2)$. So,
$\pi=\tilde{\pi}$ in this case.

  8. 8.

$\alpha(1)=\alpha_{1};\alpha(2)=\alpha_{1};~{}\alpha(12)=\alpha_{1}$. The
probability of such alpha is $p_{1}^{3}$. Thus, the actual values are
$v_{1}(1)=\frac{\tilde{v}_{1}(1)}{\alpha_{1}},~{}~{}v_{2}(2)=\frac{\tilde{v}_{2}(2)}{\alpha_{1}};~{}v_{1}(12)=\frac{\tilde{v}_{1}(12)}{\alpha_{1}}~{}and~{}v_{2}(12)=\frac{\tilde{v}_{2}(12)}{\alpha_{1}}$.
The noise-free game is: ${v}_{1}(12)>{v}_{1}(1)$; ${v}_{2}(12)>{v}_{2}(2)$.
So, $\pi=\tilde{\pi}$ in this case.

  9. 9.

$\alpha(1)=1;\alpha(2)=1;~{}\alpha(12)=\alpha_{2}$. Probability of such
alpha’s is $p_{2}(1-p_{1}-p_{2})^{2}$. Thus, the actual values are
$v_{1}(1)=\tilde{v}_{1}(1);~{}v_{2}(2)=\tilde{v}_{2}(2),v_{1}(12)=\frac{\tilde{v}_{1}(12)}{\alpha_{2}}~{}and~{}v_{2}(12)=\frac{\tilde{v}_{2}(12)}{\alpha_{2}}$.
Since $\alpha_{2}<1$, thus
$\frac{\tilde{v}_{1}(12)}{\alpha_{2}}>\tilde{v}_{1}(12)>\tilde{v}_{1}(1)=v_{1}(1)$.
Similarly,
$\frac{\tilde{v}_{2}(12)}{\alpha_{2}}>\tilde{v}_{2}(12)>\tilde{v}_{2}(2)=v_{2}(2)$.
The noise-free game is: ${v}_{1}(12)>{v}_{1}(1)$; ${v}_{2}(12)>{v}_{2}(2)$.
So, $\pi=\tilde{\pi}$ in this case.

  10. 10.

$\alpha(1)=1;\alpha(2)=\alpha_{2};~{}\alpha(12)=1$. Probability of these
alpha’s is $p_{2}(1-p_{1}-p_{2})^{2}$. Thus, the actual values are
$v_{1}(1)=\tilde{v}_{1}(1);~{}v_{2}(2)=\frac{\tilde{v}_{2}(2)}{\alpha_{2}},v_{1}(12)=\tilde{v}_{1}(12)~{}and~{}v_{2}(12)=\tilde{v}_{2}(12)$.
The noise-free game preferences are unclear; they will depend on the relative
values of $\alpha_{2}$ and $\tilde{v}$. If $\alpha_{2}$ and $\tilde{v}$’s are
such that $\tilde{v}_{2}(12)>\frac{\tilde{v}_{2}(2)}{\alpha_{2}}$ then
$\pi=N$, otherwise $\pi=\\{\\{1\\},\\{2\\}\\}$.

  11. 11.

$\alpha(1)=\alpha_{2};~{}\alpha(2)=1;~{}\alpha(12)=1$. Probability of such
alpha’s is $p_{2}(1-p_{1}-p_{2})^{2}$. Thus, the actual values are
$v_{1}(1)=\frac{\tilde{v}_{1}(1)}{\alpha_{2}};~{}~{}v_{2}(2)=\tilde{v}_{2}(2),v_{1}(12)=\tilde{v}_{1}(12)~{}and~{}v_{2}(12)=\tilde{v}_{2}(12)$.
The noise-free game preferences are unclear; they will depend on the relative
values of $\alpha_{2}$ and $\tilde{v}$. If $\alpha_{2}$ and $\tilde{v}$’s are
such that $\tilde{v}_{1}(12)>\frac{\tilde{v}_{1}(1)}{\alpha_{2}}$ then
$\pi=N$, otherwise $\pi=\\{\\{1\\},\\{2\\}\\}$.

  12. 12.

$\alpha(1)=1;\alpha(2)=\alpha_{2};~{}\alpha(12)=\alpha_{2}$. probability of
such alpha’s is $p_{2}^{2}(1-p_{1}-p_{2})$. Thus, the actual values are
$v_{1}(1)=\tilde{v}_{1}(1);~{}v_{2}(2)=\frac{\tilde{v}_{2}(2)}{\alpha_{2}},v_{1}(12)=\frac{\tilde{v}_{1}(12)}{\alpha_{2}}~{}and~{}v_{2}(12)=\frac{\tilde{v}_{2}(12)}{\alpha_{2}}$
Since $\alpha_{2}<1$, thus
$\frac{\tilde{v}_{1}(12)}{\alpha_{2}}>\tilde{v}_{1}(12)>\tilde{v}_{1}(1)=v_{1}(1)$,
and
$\frac{\tilde{v}_{2}(12)}{\alpha_{2}}>\frac{\tilde{v}_{2}(2)}{\alpha_{2}}$.
The noise-free game is: ${v}_{1}(12)>{v}_{1}(1)$; ${v}_{2}(12)>{v}_{2}(2)$.
So, $\pi=\tilde{\pi}$ in this case.

  13. 13.

$\alpha(1)=\alpha_{2};\alpha(2)=1;~{}\alpha(12)=\alpha_{2}$. Probability of
such alpha’s is $p_{2}^{2}(1-p_{1}-p_{2})$. Thus, the actual values are
$v_{1}(1)=\frac{\tilde{v}_{1}(1)}{\alpha_{2}},~{}~{}v_{2}(2)=\tilde{v}_{2}(2);~{}v_{1}(12)=\frac{\tilde{v}_{1}(12)}{\alpha_{2}}~{}and~{}v_{2}(12)=\frac{\tilde{v}_{2}(12)}{\alpha_{2}}$.
Since $\alpha_{2}<1$ thus
$\frac{\tilde{v}_{2}(12)}{\alpha_{2}}>\tilde{v}_{2}(12)>\tilde{v}_{2}(2)=v_{2}(2)$,
and
$\frac{\tilde{v}_{1}(12)}{\alpha_{2}}>\frac{\tilde{v}_{1}(1)}{\alpha_{2}}$.
The noise-free game is: ${v}_{1}(12)>{v}_{1}(1)$; ${v}_{2}(12)>{v}_{2}(2)$.
So, $\pi=\tilde{\pi}$ in this case.

  14. 14.

$\alpha(1)=\alpha_{2};\alpha(2)=\alpha_{2};~{}\alpha(12)=1$. Probability of
such alpha’s is $p_{2}^{2}(1-p_{1}-p_{2})$. Thus, the actual values are
$v_{1}(1)=\frac{\tilde{v}_{1}(1)}{\alpha_{2}},~{}~{}v_{2}(2)=\frac{\tilde{v}_{2}(2)}{\alpha_{2}};~{}v_{1}(12)=\tilde{v}_{1}(12)~{}and~{}v_{2}(12)=\tilde{v}_{2}(12)$.
The noise-free game preferences are unclear; they will depend on the relative
values of $\alpha_{2}$ and $\tilde{v}$. If $\alpha_{2}$ and $\tilde{v}$’s are
such that $\tilde{v}_{1}(12)>\frac{\tilde{v}_{1}(1)}{\alpha_{2}}$ and
$\tilde{v}_{1}(12)>\frac{\tilde{v}_{2}(2)}{\alpha_{2}}$ then $\pi=N$,
otherwise $\pi=\\{\\{1\\},\\{2\\}\\}$.

  15. 15.

$\alpha(1)=1;\alpha(2)=\alpha_{1};~{}\alpha(12)=\alpha_{2}$. Probability of
such alpha’s is $p_{1}p_{2}(1-p_{1}-p_{2})$. Thus, the actual values are
$v_{1}(1)=\tilde{v}_{1}(1),~{}~{}v_{2}(2)=\frac{\tilde{v}_{2}(2)}{\alpha_{1}};~{}v_{1}(12)=\frac{\tilde{v}_{1}(12)}{\alpha_{2}}~{}and~{}v_{2}(12)=\frac{\tilde{v}_{2}(12)}{\alpha_{2}}$.
Since
$\frac{\tilde{v}_{1}(12)}{\alpha_{2}}>\tilde{v}_{1}(12)>\tilde{v}_{1}(1)$ and
$\frac{\tilde{v}_{2}(12)}{\alpha_{2}}>\tilde{v}_{2}(12)>\tilde{v}_{2}(2)>\frac{\tilde{v}_{2}(2)}{\alpha_{1}}$.
The noise-free game is: ${v}_{1}(12)>{v}_{1}(1)$; ${v}_{2}(12)>{v}_{2}(2)$.
So, $\pi=\tilde{\pi}$ in this case.

  16. 16.

$\alpha(1)=1;\alpha(2)=\alpha_{2};~{}\alpha(12)=\alpha_{1}$. Probability of
such alpha’s is $p_{1}p_{2}(1-p_{1}-p_{2})$. Thus, actual values are
$v_{1}(1)=\tilde{v}_{1}(1),~{}~{}v_{2}(2)=\frac{\tilde{v}_{2}(2)}{\alpha_{2}};~{}v_{1}(12)=\frac{\tilde{v}_{1}(12)}{\alpha_{1}}~{}and~{}v_{2}(12)=\frac{\tilde{v}_{2}(12)}{\alpha_{1}}$.
The noise-free game preferences are unclear; it will depend on the relative
values $\alpha_{1}$, $\alpha_{2}$ and $\tilde{v}$. If $\alpha_{1}$,
$\alpha_{2}$ and $\tilde{v}$’s are such that
$\frac{\tilde{v}_{1}(12)}{\alpha_{1}}>\tilde{v}_{1}(1)$ and
$\frac{\tilde{v}_{2}(12)}{\alpha_{1}}>\frac{\tilde{v}_{2}(2)}{\alpha_{2}}$
then $\pi=N$, otherwise $\pi=\\{\\{1\\},\\{2\\}\\}$.

  17. 17.

$\alpha(1)=\alpha_{1};\alpha(2)=1;~{}\alpha(12)=\alpha_{2}$. Probability of
such alpha’s is $p_{1}p_{2}(1-p_{1}-p_{2})$. Thus, the actual values are
$v_{1}(1)=\frac{\tilde{v}_{1}(1)}{\alpha_{1}},~{}~{}v_{2}(2)=\tilde{v}_{2}(2);~{}v_{1}(12)=\frac{\tilde{v}_{1}(12)}{\alpha_{2}}~{}and~{}v_{2}(12)=\frac{\tilde{v}_{2}(12)}{\alpha_{2}}$.
Since
$\frac{\tilde{v}_{1}(12)}{\alpha_{2}}>\tilde{v}_{1}(12)>\tilde{v}_{1}(1)$ and
$\frac{\tilde{v}_{2}(12)}{\alpha_{2}}>\tilde{v}_{2}(12)>\tilde{v}_{2}(2)$. The
noise-free game is: ${v}_{1}(12)>{v}_{1}(1)$; ${v}_{2}(12)>{v}_{2}(2)$. So,
$\pi=\tilde{\pi}$ in this case.

  18. 18.

$\alpha(1)=\alpha_{2};\alpha(2)=1;~{}\alpha(12)=\alpha_{1}$. Probability of
such alpha’s is $p_{1}p_{2}(1-p_{1}-p_{2})$. Thus, the actual values are
$v_{1}(1)=\frac{\tilde{v}_{1}(1)}{\alpha_{2}},~{}~{}v_{2}(2)=\tilde{v}_{2}(2);~{}v_{1}(12)=\frac{\tilde{v}_{1}(12)}{\alpha_{1}}~{}and~{}v_{2}(12)=\frac{\tilde{v}_{2}(12)}{\alpha_{1}}$.
The noise-free game preferences are unclear; it will depend on the relative
values of $\alpha_{1}$, $\alpha_{2}$, and $\tilde{v}$. If $\alpha_{1}$,
$\alpha_{2}$ and $\tilde{v}$’s are such that
$\frac{\tilde{v}_{1}(12)}{\alpha_{1}}>\frac{\tilde{v}_{1}(1)}{\alpha_{2}}$ and
$\frac{\tilde{v}_{2}(12)}{\alpha_{1}}>\tilde{v}_{2}(2)$ then $\pi=N$,
otherwise $\pi=\\{\\{1\\},\\{2\\}\\}$.

  19. 19.

$\alpha(1)=\alpha_{1};\alpha(2)=\alpha_{2};~{}\alpha(12)=1$. Probability of
such alpha’s is $p_{1}p_{2}(1-p_{1}-p_{2})$. Thus, the actual values are
$v_{1}(1)=\frac{\tilde{v}_{1}(1)}{\alpha_{1}},~{}~{}v_{2}(2)=\frac{\tilde{v}_{2}(2)}{\alpha_{2}};~{}v_{1}(12)=\tilde{v}_{1}(12)~{}and~{}v_{2}(12)=\tilde{v}_{2}(12)$.
The noise-free game preferences are unclear; it will depend on the relative
values of $\alpha_{1}$, $\alpha_{2}$, and $\tilde{v}$. If $\alpha_{1}$,
$\alpha_{2}$ and $\tilde{v}$’s are such that
$\tilde{v}_{2}(12)>\frac{\tilde{v}_{2}(2)}{\alpha_{2}}$ then $\pi=N$ otherwise
$\pi=\\{\\{1\\},\\{2\\}\\}$.

  20. 20.

$\alpha(1)=\alpha_{2};\alpha(2)=\alpha_{1};~{}\alpha(12)=1$. Probability of
such alpha’s is $p_{1}p_{2}(1-p_{1}-p_{2})$. Thus, the actual values are
$v_{1}(1)=\frac{\tilde{v}_{1}(1)}{\alpha_{2}},~{}~{}v_{2}(2)=\frac{\tilde{v}_{2}(2)}{\alpha_{1}};~{}v_{1}(12)=\tilde{v}_{1}(12)~{}and~{}v_{2}(12)=\tilde{v}_{2}(12)$.
The noise-free game preferences are unclear; it will depend on the relative
values of $\alpha_{1}$, $\alpha_{2}$, and $\tilde{v}$. If $\alpha_{1}$,
$\alpha_{2}$ and $\tilde{v}$’s are such that
$\tilde{v}_{1}(12)>\frac{\tilde{v}_{1}(1)}{\alpha_{2}}$ then $\pi=N$,
otherwise $\pi=\\{\\{1\\},\\{2\\}\\}$

  21. 21.

$\alpha(1)=\alpha_{1};\alpha(2)=\alpha_{1};~{}\alpha(12)=\alpha_{2}$.
Probability of such alpha’s is $p_{1}^{2}p_{2}$. Thus, the actual values are
$v_{1}(1)=\frac{\tilde{v}_{1}(1)}{\alpha_{1}},~{}~{}v_{2}(2)=\frac{\tilde{v}_{2}(2)}{\alpha_{1}};~{}v_{1}(12)=\frac{\tilde{v}_{1}(12)}{\alpha_{2}}~{}and~{}v_{2}(12)=\frac{\tilde{v}_{2}(12)}{\alpha_{2}}$.
Since,
$\frac{\tilde{v}_{1}(12)}{\alpha_{2}}>\tilde{v}_{1}(12)>\tilde{v}_{1}(1)>\frac{\tilde{v}_{1}(1)}{\alpha_{1}}$,
and
$\frac{\tilde{v}_{2}(12)}{\alpha_{2}}>\tilde{v}_{2}(12)>\tilde{v}_{2}(2)>\frac{\tilde{v}_{2}(2)}{\alpha_{1}}$.
The noise-free game is: ${v}_{1}(12)>{v}_{1}(1)$; ${v}_{2}(12)>{v}_{2}(2)$.
So, $\pi=\tilde{\pi}$ in this case.

  22. 22.

$\alpha(1)=\alpha_{1};\alpha(2)=\alpha_{2};~{}\alpha(12)=\alpha_{1}$.
Probability of such alpha’s is $p_{1}^{2}p_{2}$. Thus, the actual values are
$v_{1}(1)=\frac{\tilde{v}_{1}(1)}{\alpha_{1}},~{}~{}v_{2}(2)=\frac{\tilde{v}_{2}(2)}{\alpha_{2}};~{}v_{1}(12)=\frac{\tilde{v}_{1}(12)}{\alpha_{1}}~{}and~{}v_{2}(12)=\frac{\tilde{v}_{2}(12)}{\alpha_{1}}$.
The noise-free game preferences are unclear; it will depend on the relative
values of $\alpha_{1}$, $\alpha_{2}$, and $\tilde{v}$. If $\alpha_{1}$,
$\alpha_{2}$ and $\tilde{v}$’s are such that
$\frac{\tilde{v}_{2}(12)}{\alpha_{1}}>\frac{\tilde{v}_{2}(2)}{\alpha_{2}}$
then $\pi=N$ otherwise $\pi=\\{\\{1\\},\\{2\\}\\}$.

  23. 23.

$\alpha(1)=\alpha_{1};\alpha(2)=\alpha_{2};~{}\alpha(12)=\alpha_{2}$.
Probability of such alpha’s is $p_{1}p_{2}^{2}$. Thus, the actual values are
$v_{1}(1)=\frac{\tilde{v}_{1}(1)}{\alpha_{1}},~{}~{}v_{2}(2)=\frac{\tilde{v}_{2}(2)}{\alpha_{2}};~{}v_{1}(12)=\frac{\tilde{v}_{1}(12)}{\alpha_{2}}~{}and~{}v_{2}(12)=\frac{\tilde{v}_{2}(12)}{\alpha_{2}}$.
Since,
$\frac{\tilde{v}_{1}(12)}{\alpha_{2}}>\tilde{v}_{1}(12)>\tilde{v}_{1}(1)>\frac{\tilde{v}_{1}(1)}{\alpha_{1}}$.
The noise-free game is: ${v}_{1}(12)>{v}_{1}(1)$; ${v}_{2}(12)>{v}_{2}(2)$.
So, $\pi=\tilde{\pi}$ in this case.

  24. 24.

$\alpha(1)=\alpha_{2};\alpha(2)=\alpha_{1};~{}\alpha(12)=\alpha_{1}$.
Probability of such alpha’s is $p_{1}^{2}p_{2}$. Thus, the actual values are
$v_{1}(1)=\frac{\tilde{v}_{1}(1)}{\alpha_{2}},~{}~{}v_{2}(2)=\frac{\tilde{v}_{2}(2)}{\alpha_{1}};~{}v_{1}(12)=\frac{\tilde{v}_{1}(12)}{\alpha_{1}}~{}and~{}v_{2}(12)=\frac{\tilde{v}_{2}(12)}{\alpha_{1}}$
Clearly, the preferences in the noise-free game are not clear; it will depend
on the relative values of $\alpha_{1}$, $\alpha_{2}$ and $\tilde{v}$. If
$\alpha_{1}$, $\alpha_{2}$ and $\tilde{v}$’s are such that
$\frac{\tilde{v}_{1}(12)}{\alpha_{1}}>\frac{\tilde{v}_{1}(1)}{\alpha_{2}}$
then $\pi=N$ otherwise $\pi=\\{\\{1\\},\\{2\\}\\}$.

  25. 25.

$\alpha(1)=\alpha_{2};\alpha(2)=\alpha_{1};~{}\alpha(12)=\alpha_{2}$.
Probability of such alpha’s is $p_{1}p_{2}^{2}$. Thus, the actual values are
$v_{1}(1)=\frac{\tilde{v}_{1}(1)}{\alpha_{2}},~{}~{}v_{2}(2)=\frac{\tilde{v}_{2}(2)}{\alpha_{1}};~{}v_{1}(12)=\frac{\tilde{v}_{1}(12)}{\alpha_{2}}~{}and~{}v_{2}(12)=\frac{\tilde{v}_{2}(12)}{\alpha_{2}}$.
Since,
$\frac{\tilde{v}_{2}(12)}{\alpha_{2}}>\tilde{v}_{2}(12)>\tilde{v}_{2}(2)>\frac{\tilde{v}_{2}(2)}{\alpha_{1}}$.
The noise-free game is: ${v}_{1}(12)>{v}_{1}(1)$; ${v}_{2}(12)>{v}_{2}(2)$.
So, $\pi=\tilde{\pi}$ in this case.

  26. 26.

$\alpha(1)=\alpha_{2};\alpha(2)=\alpha_{2};~{}\alpha(12)=\alpha_{1}$.
Probability of such alpha’s is $p_{1}p_{2}^{2}$. Thus, the actual values are
$v_{1}(1)=\frac{\tilde{v}_{1}(1)}{\alpha_{2}},~{}~{}v_{2}(2)=\frac{\tilde{v}_{2}(2)}{\alpha_{2}};~{}v_{1}(12)=\frac{\tilde{v}_{1}(12)}{\alpha_{1}}~{}and~{}v_{2}(12)=\frac{\tilde{v}_{2}(12)}{\alpha_{1}}$.
The noise-free game preferences are unclear; it will depend on the relative
values $\alpha_{1}$, $\alpha_{2}$ and $\tilde{v}$. If $\alpha_{1}$,
$\alpha_{2}$ and $\tilde{v}$’s are such that
$\frac{\tilde{v}_{1}(12)}{\alpha_{1}}>\frac{\tilde{v}_{1}(1)}{\alpha_{2}}$ and
$\frac{\tilde{v}_{2}(12)}{\alpha_{1}}>\frac{\tilde{v}_{2}(2)}{\alpha_{2}}$
then $\pi=N$ otherwise $\pi=\\{\\{1\\},\\{2\\}\\}$.

  27. 27.

$\alpha(1)=\alpha_{2};\alpha(2)=\alpha_{2};~{}\alpha(12)=\alpha_{2}$. The
probability of such alpha is $p_{2}^{3}$. Thus, the actual values are
$v_{1}(1)=\frac{\tilde{v}_{1}(1)}{\alpha_{2}},~{}~{}v_{2}(2)=\frac{\tilde{v}_{2}(2)}{\alpha_{2}};~{}v_{1}(12)=\frac{\tilde{v}_{1}(12)}{\alpha_{2}}~{}and~{}v_{2}(12)=\frac{\tilde{v}_{2}(12)}{\alpha_{2}}$.
The noise-free game is: ${v}_{1}(12)>{v}_{1}(1)$; ${v}_{2}(12)>{v}_{2}(2)$.
So, $\pi=\tilde{\pi}$ in this case.

Since
$\overline{r}=\max\left\\{\frac{\tilde{v}_{1}(12)}{\tilde{v}_{1}(1)},\frac{\tilde{v}_{2}(12)}{\tilde{v}_{2}(2)}\right\\}$,
and
$\underline{r}=\min\left\\{\frac{\tilde{v}_{1}(12)}{\tilde{v}_{1}(1)},\frac{\tilde{v}_{2}(12)}{\tilde{v}_{2}(2)}\right\\}$.
From above cases, we see that in 14 out of 27 cases (case
1,3,4,7,8,9,12,13,15,17,21,23,25,27) we have $\pi=\tilde{\pi}=N$ in noise-free
game. In these cases, the relative value of
$\tilde{v}_{1}(\cdot),\tilde{v}_{2}(\cdot)$ should satisfy
$\alpha_{1}\geq\overline{r},\frac{1}{\alpha_{2}}\geq\overline{r},\frac{\alpha_{1}}{\alpha_{2}}\geq\overline{r}$.
The prediction probability in this case is given below as $g(p_{1},p_{2})$.
Whereas if we allow for the cases, say
$\alpha_{1}<\underline{r}~{};~{}\frac{1}{\alpha_{2}}<\underline{r}~{};~{}\frac{\alpha_{1}}{\alpha_{2}}<\underline{r}$,
then the prediction probability is 1. So, these are the two extreme cases.
However, if we take any other range of $\alpha$’s, the prediction probability
will be more than $g(p_{1},p_{2})$ and less than 1. Thus,

$\mathbb{P}[\pi=\tilde{\pi}~{}|~{}game~{}1]=\begin{cases}g(p_{1},p_{2}),&~{}if~{}~{}\alpha_{1}\geq\overline{r}~{};~{}\frac{1}{\alpha_{2}}\geq\overline{r}~{};~{}\frac{\alpha_{1}}{\alpha_{2}}\geq\overline{r}\\\
1,&~{}if~{}~{}\alpha_{1}<\underline{r}~{};~{}\frac{1}{\alpha_{2}}<\underline{r}~{};~{}\frac{\alpha_{1}}{\alpha_{2}}<\underline{r},\end{cases}$
(28)

where
$g(p_{1},p_{2})=p_{1}^{3}+p_{2}^{3}+2(p_{1}(1-p_{1}-p_{2})^{2}+p_{2}^{2}(1-p_{1}-p_{2})+p_{1}p_{2}(1-p_{1}-p_{2})+p_{1}p_{2}^{2})+p_{1}^{2}p_{2}+p_{1}^{2}(1-p_{1}-p_{2})+p_{2}(1-p_{1}-p_{2})^{2}+(1-p_{1}-p_{2})^{3}$.

####  A.5.2 Safety value via global minima for 2 agents and 3 support noise
model

Here we will show that the above prediction probability given in Equation (28)
can be non-convex in $p_{1},p_{2}$. So, the global minima are difficult to
hope for.

Note that $\frac{\partial g(p_{1},p_{2})}{\partial
p_{1}}=3p_{1}^{2}-(p_{2}-1)^{2}$ and $\frac{\partial g(p_{1},p_{2})}{\partial
p_{2}}=-2p_{1}(p_{2}-1)-3p_{2}^{2}+6p_{2}-2$. Hence, we have
$\frac{\partial^{2}g(p_{1},p_{2})}{\partial^{2}p_{1}}=6p_{1}$,
$\frac{\partial^{2}g(p_{1},p_{2})}{\partial
p_{1}p_{2}}=\frac{\partial^{2}g(p_{1},p_{2})}{\partial
p_{2}p_{1}}=-2(p_{2}-1)$, and $\frac{\partial^{2}g(p_{1},p_{2})}{\partial
p_{2}^{2}}=-2p_{1}-6p_{2}+6$. Thus, the Hessian of $g(p_{1},p_{2})$ is

$H(g(p_{1},p_{2}))=\begin{bmatrix}6p_{1}&-2(p_{2}-1)\\\
-2(p_{2}-1)&-2p_{1}-6p_{2}+6\end{bmatrix}.$

For $p_{1}=0.3$ and $p_{2}=0.5$, we have

$H(g(p_{1},p_{2}))=\begin{bmatrix}0.18&1\\\ 1&2.4\end{bmatrix}.$

The eigenvalues are $\lambda_{1}=2.78$, and $\lambda_{2}=-0.20$. So,
$g(p_{1},p_{2})$ is not a convex function. Therefore, finding the global
minima is difficult.

Though the above prediction probability is non-convex, one can get the noise
set such that the prediction probability is more than a given satisfaction
$\zeta$. Similar to the 2 support cases, where the prediction probability was
a convex function, but the noise regimes were disjoint intervals, in 3 support
cases also, we get disjoint sets. However, computing the exact safety value is
problematic because it is the global minima of the non-convex prediction
probability function. Note that the safety value is a fundamental limit such
that below a user-given satisfaction $\zeta$, the partition is noise robust in
the entire noise probability simplex.

As earlier, in the noise regimes where the prediction probability is more than
$\zeta$, a partition $\tilde{\pi}$ that is core-stable in a noisy game will
remain core-stable in a noise-free game.