PAC Learning Model

PAC Learnability of HG class H

Definition: An algorithm PAC-learns $H$ if, for any $\vec{v}\in H$, given in input a confidence parameter $\delta$, an error parameter $\epsilon$, drawing a sample $\mathcal S$ with probability at least $1-\delta$, it returns an $\epsilon$-approximation $\vec{v}^*\in H$ of $\vec{v}$, that is $$ \Pr_{\mathcal S\sim\mathcal D}{\vec{v}^*(S)\neq\vec{v}(S)}<\epsilon. $$ Sample complexity: $m$ polynomial in $n,\log(1/\delta),1/\epsilon$.

Computational complexity: polynomial in $n,\log(1/\delta),1/\epsilon$.

Observation: A valuation profile $\vec{v}$ is PAC-learnable iff a single valuation function $v_i$ is PAC-learnable.

If you learn $\vec v$, you also learn $v_i$, as $$ \Pr_{\mathcal S\sim\mathcal D}{v_i^(S)\neq v_i(S)}\leq\Pr_{\mathcal S\sim\mathcal D}{\vec{v}^\neq\vec{v}(S)}<\epsilon. $$ If you learn $v_i$, then you can learn $\vec v$:

Learn each $v_i$ independently with confidence $\delta/n$ and error $\epsilon/n$.

return $\vec v=(v_1,\cdots,v_n)$.

(Proof by union bound)

Pseudo-dimension

Let $\mathcal S=\langle(S_1,r_1),\cdots,(S_q,r_q)\rangle$ be a sequence of coalition/value pairs.

Class $H$ pseudo-shatters $\mathcal S$ if, for every possible binary labeling $l_1,\cdots,l_q$ of $\mathcal S$, there exists a function $v\in H$ s.t. $v(S_k)>r_k\Leftrightarrow l_k=1\land v(S_k)<r_k\Leftrightarrow l_k=0.$

Intuitively, the more $H$ is expressive, the bigger the sets that it can pseudo-shatter.

Definition: The pseudo-dimension $Pdim(H)$ of $H$, is the size of the longest sequence $\mathcal S$ that can be pseudo-shattered by $H$,

Theorem (2002): A hypothesis class $H$ with $Pdim(H)$ polynomial in $n$ is PAC-learnable using $m$ samples, where $m$ is polynomial in $Pdim(H),\log(1/\delta),1/\epsilon$, by any algorithm $A$ that returns a hypothesis $v^*$ consistent with the sample. Furthermore, if $Pdim(H)$ is not polynomial in $n$, $H$ is not PAC-learnable.

How to use the theorem for proving PAC-learnability?

Positive use:

Show that $Pdim(H)$ is polynomial in $n$, that is prove that any sequence greater than a certain sort length cannot be shattered.

Given an efficient algorithm for returning a hypothesis consistent with the sample.

Negative use:

Show that $Pdim(H)$ is not polynomial in $n$, that is show that there exist sequences of super-polynomial length that can be shattered.

PAC-learnability of W Games

W Games: $v_i(S)=\min_{j\in S}v_i(j)$.

Lemma: The pseudo-dimension of the hypothesis space $H$ of W games is $\leq n+1$.

Proof by showing that any sequence $\mathcal S$ with length $n+1$ can not be shattered by $H$.

Lemma: There exists an efficient algorithm $A$ that given any sample $\mathcal S$, returns a hypothesis $v^*$ consistent with $\mathcal S$.

Theorem: W games are PAC-learnable.

PAC-learnability of B Games

B Games: $v_i(S)=\max_{j\in S}v_i(j)-\xi|S|$, where $\xi$ is a negligible positive number.

Theorem: B games are PAC-learnable.

Similar argument for W games.

PAC-learnability of ASHG

A coalition $S$ can be represented by a Boolean vector $(x_1,\cdots,x_n)$ where $x_i=1$ means $i\in S$.

A valuation function $v$ in ASHG can be seen as a linear function of characteristic vectors. $$ v_i(S)=\sum_{j\in S}v_i(j)=\sum_{j\neq i}v_i(j)x_j $$ ASHG are PAC-learnable, because linear functions are PAC-learnable.

Lemma: The pseudo-dimension of the hypothesis space $H$ of ASHGs is $<n$.

PAC-learnability of FHG

FHG: $v_i(S)=\sum_{j\in S}v_i(j)/|S|$.

FHGs are PAC-learnable.

Non-learnable Class

Top Responsive HGs: Agents appreciation of a coalition depends on the most preferred subset within the coalition.

The choice set of agent $i$ in coalition $S$ is defined as $$ Ch(i,S)={T\subseteq S|(i\in T)\land(\forall U\subseteq S,T\succcurlyeq_i U)} $$ A game satisfies top-responsiveness if

$\forall i\in N\land S\in N_i,|Ch(i,S)=1$.
$\forall i\in N\land S,T\in N_i$: a. if $ch(i,S)\succ_ich(i,T)$ then $S\succ_iT$; b. if $ch(i,S)=ch(i,T)$ and $S\subseteq T$ then $S\succ_iT$.

Theorem: Top Responsive HGs are not PAC-learnable.

Proof by showing that there exists a sequence of length $q\geq 2^{(n-1)/2}$ that can be shattered by $H$.

$Pdim(H)$ is not polynomial in $n$.

PAC Stability in HG

Definition: An algorithm PAC-stabilizes $H$ if, for any $\vec v\in H$, given in input a confidence parameter $\delta$, an error parameter $\epsilon$, drawing a sample $\mathcal S$, with probability at least $1-\delta$,

it returns a $\epsilon$-stable coalition structure $\pi$ s.t. $\Pr_{\mathcal S\sim\mathcal D}(S$ core blocks $\pi)<\epsilon$.
or reports that the core is empty.

Sample complexity: $m$ polynomial in $n,\log(1/\delta),1/\epsilon$.

Computational complexity: polynomial in $n,\log(1/\delta),1/\epsilon$.

Theorem (2020): A HG class $H$ is efficiently PAC stabilizable iff there exists an efficient algorithm that returns a partition $\pi$ consistent with the sample, i.e., no coalition from the sample core-blocks $\pi$, or reports that the core is empty.

PAC Stabilizability of ASHG

Theorem: ASHGs are not PAC stabilizable.

Consider an instance of counterexample.

PAC Stabilizability of W Games

Theorem: W games are not PAC stabilizable.

Consider a counterexample.

A Positive Stabilizability Example

Friends and Enemies.

Theorem: FE games are PAC stabilizable.

Summary of Results

HG class	Learnability	Stabilizability
W games	yes	no
B games	yes	yes
ASGH	yes	no
FHG	yes	no
Friends & Enemies	yes	yes
Top Responsive	no	yes
Bottom Responsive	no	yes