Instead of insisting on the idea of determining a partition of the input data, and hence obtaining the clusters as a by-product of the partitioning process, in this presentation I propose to reverse the terms of the problem and attempt instead to derive a rigorous formulation of the very notion of a cluster. Clearly, the conceptual question “what is a cluster?” is as hopeless, in its full generality, as is its companion “what is an optimal clustering?” which has dominated the literature in the past few decades, both being two sides of the same coin. An attempt to answer the former question, however, besides shedding fresh light into the nature of the clustering problem, would allow us, as a consequence, to naturally overcome the major limitations of the partitional approach alluded to above, and to deal with more general problems where, e.g., clusters may overlap and clutter elements may get unassigned, thereby hopefully reducing the gap between theory and practice.

In our endeavor to provide an answer to the question raised above, we found that game theory offers a very elegant and general perspective that serves well our purposes. Hence, in the second, constructive part of the presentation I will describe a game-theoretic framework for clustering [21, 25, 22] which has found applications in fields as diverse as computer vision and bioinformatics. The starting point is the elementary observation that a “cluster” may be informally defined as a maximally coherent set of data items, i.e., as a subset of the input data C which satisfies both an internal criterion (all elements belonging to C should be highly similar to each other) and an external one (no larger cluster should contain C as a proper subset). We then formulate the clustering problem as a non-cooperative clustering game. Within this context, the notion of a cluster turns out to be equivalent to a classical equilibrium concept from (evolutionary) game theory, as the latter reflects both the internal and external cluster conditions mentioned above.