Though deliberation is a critical component of democratic decision-making, existing deliberative processes do not scale to large groups of people. Motivated by this, we propose a model in which large-scale decision-making takes place through a sequence of small group interactions. Our model considers a group of participants, each having an opinion which together form a graph. We show that for median graphs, a class of graphs including grids and trees, it is possible to use a small number of three-person interactions to tightly approximate the wisdom of the crowd, defined here to be the generalized median of participant opinions, even when agents are strategic. Interestingly, we also show that this sharply contrasts with small groups of size two, for which we prove an impossibility result. Specifically, we show that it is impossible to use sequences of two-person interactions satisfying natural axioms to find a tight approximation of the generalized median, even when agents are non-strategic. Our results demonstrate the potential of small group interactions for reaching global decision-making properties.
A median of a family of vertices in a graph is any vertex whose distance-sum to that family is minimum. In the framework of metric spaces the problem of minimizing a distance-sum is often referred to as the Fermat problem. On the other hand, medians have been studied from a purely order-theoretic or combinatorial point of view (for instance, in statistics, or in Jordan’s work [12] on trees). The aim of this paper is to investigate the mutual relationship of the metric and the ordinal combinatorial approaches to the median problem in the class of median graphs. A connected graph is a median graph if any three vertices admit a unique median (see Avann [l]). Note that trees and the covering graphs of distributive lattices are median graphs. Very little is known about medians in arbitrary graphs (cf. Slater [20]); so far, only trees (Zelinka [22], and many others) and the covering graphs of distributive lattices (Barbut [4]) have been considered. In both cases we get that (i) the medians of any family form an interval (a path in a tree, an order-theoretic interval in a distributive lattice), and (ii) medians of odd numbered families are unique (see Slater [19] for trees, and Barbut [4] for distributive lattices). These results point to the fact that (i) and (ii) must be true for any median graph. After recalling some basic definitions and facts concerning median graphs and median semilattices (for further information, see Bandelt and Hedlikova [3]), we establish (i) and (ii) for arbitrary median graphs. Our results are based on theorems of Avann, Sholander, and Barbut. In trees medians have nice local properties (cf. [7]). Indeed, median sets are related to mass centers (Zelinka [22]) and security centers (Slater [18]). In Section 3 this is extended to median graphs. The study of medians applies to social choice theory (see Barbut 151, and Barthelemy and Monjardet [8]). The median procedure is strongly related to the simple majority rule: the median of a family (A,, . . . , Azk+ ,) of subsets of a set X may be written as U n Ai (Barbut’s formula).  We consider a competitive facility location problem on a network, in which consumers are located on the vertices and wish to connect to the nearest facility. Knowing this, competitive players locate their facilities on vertices that capture the largest possible market share. In 1991, Eiselt and Laporte established the first relation between Nash equilibria of a facility location game in a duopoly and the solutions to the 1-median problem. They showed that an equilibrium always exists in a tree because a location profile is at equilibrium if and only if both players select a 1-median of that tree [4]. In this work, we further explore the relations between the solutions to the 1-median problem and the equilibrium profiles. We show that if an equilibrium in a cycle exists, both players must choose a solution to the 1-median problem. We also obtain the same property for some other classes of graphs such as quasi-median graphs, median graphs, Helly graphs, and strongly-chordal graphs. Finally, we prove the converse for the latter class, establishing that, as for trees, any median of a strongly-chordal graph is a winning strategy that leads to an equilibrium. Abstract This paper gives new perspectives in competitive location theory by considering new norms in two-dimensional problems and by considering (for the first time) the competitive location problem on a graph. The results in competitive location theory are generalized by exploiting an isomorphism to the literature in voting theory and by developing new results for competitive location problems on a graph. We define a general notion of single-peaked preferences based on abstract betweenness relations. Special cases are the classical example of single-peaked preferences on a line, the separable preferences on the hypercube, the “multi-dimensionally single-peaked” preferences on the product of lines, but also the unrestricted preference domain. Generalizing and unifying the existing literature, we show that a social choice function is strategy-proof on a sufficiently rich domain of generalized single-peaked preferences if and only if it takes the form of voting by issues (“voting by committees”) satisfying a simple condition called the “Intersection Property.” Based on the Intersection Property, we show that the class of preference domains associated with “median spaces” gives rise to the strongest possibility results; in particular, we show that the existence of strategyproof social choice rules that are non-dictatorial and neutral requires an underlying median space. A space is a median space if, for every triple of elements, there is a fourth element that is between each pair of the triple; numerous examples are given (some well-known, some novel), and the structure of median spaces and the associated preference domains is analysed.