Convergence of a Two-Player Version of Macqueen's k-means Algorithm

We extend Macqueen's version of the k-means algorithm (Macqueen, 1967) by assuming that the clustering involves two players. Player 1, the sender, equipped with its type, emits data at no cost, and Player 2, the receiver, equipped with Player 1's data, takes a decision. In particular, types are pooled with regard to the decisions associated with the data. Pure perfect Bayesian equilibria (PBE) in this game are characterized by partitions of the sender's types in which no type prefers to be pooled with types it is not currently pooled with, given the decisions of the receiver, optimally chosen at each cell of the partition. In this context, the k-means inductive step proceeds as follows: given the currently achieved partition, (i) the sender moves a type from its cell to a cell he prefers (e.g. with a closer mean); (ii) the receiver recomputes the cell-contingent decision accordingly (e.g. recomputes the means). However, since players might have different objective functions, the usual convergence argument invoked in Macqueen's context (monotonicity of stages (i) and (ii) with regard to identical objective functions) no more holds. Instead, we give a combinatorial argument to achieve convergence, for every initial partition and every path taken by the algorithm. We do this for the family of objective functions that are concave, single-peaked and single-crossing, with an upward bias of the sender. The family covers, but goes much beyond, the usual Euclidean distance. However, our argument crucially relies on the order on types and decisions.