Fair AI/ML 7 The Existence of Core for Max Distance Loss

The Existence of Core

Is the core empty?

In the paper, we have proved that Greedy Capture computes $2$-core in $O(kn)$ time for maximum distance loss.

Is the $2$ the lower bound for code?

Consider a graph $G=(V,E)$, where for every pair $i,j\in V$, $(i,j)\in E$ if $dist(i,j)=1$, else $dist(i,j)=2$.

If there exist a graph such that no matter how we assign the clusters, there always exist a clique of size at least $\lceil n/k\rceil$, then the lower bound of $2$ is proved.

My Answer (To be verified)

In any given aforementioned graph $G$, the cluster in the core always exist. (But this can not prove the actual core always exist.)

Consider the algorithm below:

Algorithm Split-and-Merge:

Input: Graph $G=(V,E)$, $k$

Output: Clustering $C=(C_1,\cdots,C_k)$ in the actual core

1. $n\gets\#V,C\gets\empty,X\gets V$
2. while $X\neq V$, do // SPLIT PHASE
   • $C'\gets MAXCLIQUE(V\diagdown X,E)$
   • $C\gets C\cup\{C'\}$
   • $X\gets X\cup C'$
3. while $|C|\gt k$, do // MERGE PHASE
   • $c_1\gets\arg\min_{c\in C}|c|,c_2\gets\arg\min_{c\in C\diagdown\{c_1\}}|c|,c'=c_1\cup c_2$
   • $C\gets C\diagdown\{c_1,c_2\},C\gets C\cup \{c'\}$
4. return $C$

🤔Proposition: Split-and-Merge always return the cluster in the actual core.

Claim: If a set of points form a cluster, which means, the cost of everybody is $1$. All of them have no incentive to form a coalition with anyone outside of the clique.

Thus before merging, any subset of $V$ that intersects at least two item-sets in $C$, can not be a clique.

❗By pigeonhole principle, before merging, any item-set in $C$ with size already greater than $\lceil n/k\rceil$ would not be picked in the merge phase! All data points in these clusters have no incentive to deviate.

In the merge phase, every point who would have been merged have the cost $2$. But they can not find other points to form a clique with size at least $\lceil n/k\rceil$.

Thus I strongly suspect that the actual core always exists.