Uni-dimensional Models of Coalition Formation: non-existence of Stable Partitions

Consider a finite population located along the real line, which generates a demand for public facilities. The set-up cost of each facility is the same and is given by a positive constant. In addition to contributing towards the facility cost, every user bears transportation cost to the facility location. These are classical prerequisites for the Uncapacitated Facility Location Problem; however our focus is on game-theoretic aspects of the problem. Assuming for simplicity that the set-up cost of facilities are equally shared among its members, we examine the existence of a ‘‘stable’’ set of facilities (or, equivalently, a partition of the set of players) such that no coalition (i. e. a nonempty subset of players) can set up a new facility that would reduce the total cost incurred by each member of the coalition. The simple majority condition requires that every group places the facility at the location of its median resident. In general, however, a median voter is not uniquely defined. This paper offers a universal counterexample that regardless of the selection of a median resident, a stable partition of individuals into users of various facilities fails to exist.