Equivalent Setting

Those three conditions is equivalent to APPROVAL VOTING.

Each data point is a voter.
Each voter approve a subset of other data points

Cost Definition

The maximum and average costs are therefore defined equivalently and accordingly.

The maximum cost:

cost(i)=\begin{cases} 1\text{ if }\exist j\in C_i,i\text{ doesn't approve }j\\ 0\text{ otherwise} \end{cases}

The minimum cost:

cost(i)=\frac{\#j\in C_i\text{, s.t. }i\text{ doesn't approve}}{|C_i|}

It’s not hard to prove that Split and Merge algorithm also computes a clustering in the core with BINARY, ASYMMETRIC, NON-METRIC “distance”.

On Average Cost

🎯Theorem (On Average Cost): Split and Merge algorithm computes a clustering in $\lceil n/k\rceil$ -core.

Assume there exist a subset $V$ of $\lceil n/k\rceil$ agents where each agent would improve more than multiplicative factor $\lceil n/k\rceil$ .
In Split and Merge algorithm, the average cost of data point $i$ is at most $\frac{|C_i|-1}{|C_i|}$ .
Therefore, for each subset of $\lceil n/k\rceil$ , there exist one agent does not improve its cost (from $1$ to $0$ ). (Consider maximum cost, Split and Merge computes the solution in the core, which means for each subset of $\lceil n/k\rceil$ , not all agent would be strictly better off.)
Thus, the average cost of this agent is at most $1$ . Possible improved average cost is at least $\frac{1}{\lceil n/k\rceil}$ , meaning that the improvement can not be greater than factor of $\lceil n/k\rceil$ .

Can we improve this $\lceil n/k\rceil$ factor? No idea… 🤔

Following Directions on Average Cost

From the paper, we learn that for symmetric, metric, arbitrary distance, the lower bound of core approximation factor is $1.3$ .

🤔But what if we consider binary distance remove symmetric and metric limitation? Could the core be non-empty in this case?

🤔What about graphs with certain structures? (scale-free, small-world networks…)